PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-Improving Language Models for Evolutionary Program Synthesis: A Case Study on ARC-AGI

Julien Pourcel, Cédric Colas, Pierre-Yves Oudeyer

arXiv:2507.14172v2cs.LGcs.AIcs.NE

TL;DR

Program synthesis involves vast implementation spaces, and fixed-capability LLMs limit the gains available from evolutionary search on difficult tasks. SOAR alternates evolutionary search with hindsight learning that finetunes LLM sampling and refinement from its own successful and failed search attempts. SOAR reaches 52% final test performance, with iterative self-improvement adding 10–19% solved tasks across model sizes and test-time training adding 3–5%.

  • Problem

    Program synthesis involves vast implementation spaces, and fixed-capability LLMs limit the gains available from evolutionary search on difficult tasks.

  • Method

    SOAR alternates evolutionary search with hindsight learning that finetunes LLM sampling and refinement from its own successful and failed search attempts.

  • Results

    SOAR reaches 52% final test performance, with iterative self-improvement adding 10–19% solved tasks across model sizes and test-time training adding 3–5%.

  • Takeaways & Limitations

    Self-improvement enables program-synthesis systems to exceed fixed-model search plateaus and adapt continuously on target tasks.

  • Takeaways & Limitations

    SOAR is evaluated only on ARC and currently requires 6,000 synthesis attempts per task, limiting demonstrated domain scope and computational efficiency.

Abstract

from arXiv · show

Many program synthesis tasks prove too challenging for even state-of-the-art language models to solve in single attempts. Search-based evolutionary methods offer a promising alternative by exploring solution spaces iteratively, but their effectiveness remain limited by the fixed capabilities of the underlying generative model. We propose SOAR, a method that learns program synthesis by integrating language models into a self-improving evolutionary loop. SOAR alternates between (1) an evolutionary search that uses an LLM to sample and refine candidate solutions, and (2) a hindsight learning phase that converts search attempts into valid problem-solution pairs used to fine-tune the LLM's sampling and refinement capabilities\, -- \,enabling increasingly effective search in subsequent iterations. On the challenging ARC-AGI benchmark, SOAR achieves significant performance gains across model scales and iterations, leveraging positive transfer between the sampling and refinement finetuning tasks. These improvements carry over to test-time adaptation, enabling SOAR to solve 52\% of the public test set. Our code is open-sourced at: https://github.com/flowersteam/SOAR

1. Introduction

Program synthesis must search vast implementation spaces, while fixed-capability LLMs and traditional search methods plateau on hard tasks. SOAR addresses this by learning sampling and refinement from its own search experience, achieving strong ARC-AGI gains.

  • Motivation: Traditional evolutionary search depends heavily on intelligent program generators and mutation operators, otherwise requiring massive computation to explore candidate programs.LLMs can provide targeted sampling and refinement, but fixed model capabilities create diminishing returns from additional search.
  • Contribution: SOAR alternates evolutionary search with hindsight finetuning so the model improves its program-sampling and refinement capabilities from its own search attempts.The framework learns from both successful and failed synthesis attempts without human-engineered data.
  • Motivation: ARC challenges models to infer grid transformations from only a few examples, making it a demanding benchmark for program synthesis and core reasoning.Current language models struggle substantially on this task family.
  • Results: 52% final performance on ARC-AGI’s public test set establishes SOAR’s strongest reported result and outperforms prior open-weight-LLM program-synthesis methods.After four training iterations, SOAR solves an extra 10–19% of tasks across model sizes.
  • Results: SOAR’s test-time training adds 3–5% solved tasks across model sizes when target tasks are available without their ground-truth solutions.This combines adaptation to target tasks with the search process.

2. Related Work

Prior program-synthesis systems learn search components or use LLMs as fixed generators and mutation operators. SOAR differs by continuously adapting its underlying model from both successful and failed search traces, without human-engineered data or domain-specific languages.

  • Program synthesis: Earlier synthesis research learned program samplers or search decision mechanisms from data, building on traditional methods whose performance depends on engineered priors and mutation operators.These approaches include neural sampling conditioned on input-output examples and learned mechanisms for accelerating search.
  • LLM-guided search: Recent LLM systems generate programs directly or mutate existing solutions, enabling both convergent refinement and divergent solution generation while retaining fixed model capabilities.The cited methods span program synthesis, evolutionary mutation, and generation of diverse artifacts.
  • LLM-guided search: SOAR continuously adapts its underlying language model, unlike prior LLM-based search methods that treat the model as a fixed component.This targets the central limitation of static search loops: experience does not improve the generator or mutation operator.
  • Self-improvement: SOAR internalizes search traces through hindsight learning, leveraging failed attempts as well as successful ones and learning both sampling and refinement.This extends prior reasoning approaches that primarily train on successful self-generated or search-produced traces.
  • ARC systems: Compared with CodeIt, SOAR replaces a hand-designed DSL and human engineering with general-purpose program synthesis, iterative refinement, and test-time adaptation.The supplied related-work passage identifies this contrast while noting SOAR’s dependence on past synthesis attempts rather than human-generated datasets.

3. Method

SOAR solves ARC tasks by alternating LLM-driven evolutionary search with finetuning on search traces. It samples and refines Python programs, uses execution feedback and weighted voting, and creates synthetic training pairs through hindsight relabeling.

  • Self-improvement loop: SOAR alternates Sample&Refine evolutionary search with finetuning, using each improved model to generate richer search traces for the next iteration.Search samples and refines candidate programs; learning updates the underlying LLM for future tasks.
  • Problem definition: ARC is a programming-by-example task where a Python function must reproduce training grid outputs and generate hidden test outputs for new inputs.Each task contains 2–10 colored-grid training pairs and test inputs.
  • Sample&Refine search: SOAR initially samples 3k Python programs and performs 3k execution-feedback refinements, treating refinement as a generative multi-armed bandit.REX combines Thompson sampling based on training accuracy with exploration.
  • Sample&Refine search: The system starts with 6k candidate programs and selects test outputs using weighted majority voting, weighting each grid by the example accuracy of programs that produced it.This aggregates 3k sampled and 3k refined programs.
  • Learning to search: Hindsight relabeling turns every sampled program into a valid training pair by defining a synthetic task from the outputs that program actually produces.This expands sampling data beyond the rare programs that solve their intended tasks; the resulting dataset contains 6k datapoints per each of 400 ARC-train tasks before subsampling.
  • Learning to search: Finetuning separately improves sampling from correct or hindsight-relabeled programs and refinement from successful corrections, with capped and balanced examples to preserve diversity.Sampling uses up to 25 top- and 25 bottom-performing solutions per task, while refinement data is balanced across parent-program accuracy bins.

4. Experiments

Experiments show that SOAR improves program sampling and refinement through iterative self-training, raising ARC performance across model sizes, test-time adaptation, and ensemble settings. The method also breaks through plateaus caused by fixed model capabilities and search budgets, although solution diversity declines on solved tasks.

  • Learning to sample and refine: Greedy-diverse data generation produced the best sampling accuracy, while diverse sampling marginally improved refinement to 42.88% when refining non-finetuned samples.These comparisons support balancing successful solutions with training-data diversity.
  • Learning to sample and refine: Joint finetuning improved both sampling and search over base and task-specific models, indicating positive transfer between sampling and refinement capabilities.The results suggest shared representations of program structure and transformation patterns benefit both tasks.
  • Iterated self-improvement: After four training iterations, SOAR solved an additional +27% of 7B, +24% of 14B, +20% of 32B, +19% of 72B, and +22% of Mistral ARC-train problems.All model sizes improved, with smaller models showing steeper early gains and the 7B model nearly doubling its performance.
  • Test-time adaptation: Test-time training added 5% ARC-test performance, raising the 7B model from 14.25% to 36.25% and the 14B model from 19.87% to 42.75%.These gains followed training on models fine-tuned through four ARC-train iterations.
  • Iterated self-improvement: 52.00% ARC-test accuracy was achieved by combining solutions across model sizes with majority voting, while the oracle reached 57.25%.The pooled ensemble outperformed individual model sizes, reflecting complementary problem-solving strategies.
  • Escaping scaling plateaus: SOAR lifted model-size and search-budget plateaus, whereas fixed-capability search saturated beyond 32B and after roughly 5.2k attempts.The improvement came from learning better sampling and refinement behaviors rather than only increasing parameters or search computation.
  • Solution diversity across iterations: Solution diversity steadily decreased across iterations for solved problems, while diversity on unsolved problems initially declined and then plateaued.The authors identify explicit diversity-enhancing strategies as a possible way to sustain exploration.

5. Discussion

SOAR suggests that iterative self-improvement can overcome scaling plateaus by jointly improving program sampling and refinement, while exposing limits in diversity, efficiency, and domain coverage.

  • 5. Discussion: Iterative improvement of sampling and refinement helps program synthesis systems overcome performance plateaus associated with scaling model size and search budget.SOAR’s broader implication is a cycle in which evolutionary search and learning raise the system’s capabilities beyond its initial model.
  • 5. Discussion: SOAR maintains diversity on unsolved tasks but converges toward lower diversity on solved tasks, and the retained diversity may not sustain continual progress.The paper attributes the maintained diversity partly to hindsight relabeling of failed programs, while proposing explicit diversity optimization as future work.
  • 5. Discussion: SOAR improves without human-written demonstrations or domain-specific languages, using its own search experience to bootstrap reasoning on ARC.ARC is designed to resist pattern matching and require core reasoning, making this self-improvement result especially relevant to the benchmark’s intended challenge.
  • 5. Discussion: Cross-model diversity is associated with the strongest gains: aggregating solutions across models and iterations improves training, while ensembling reaches 52% on ARC-test.Smaller models can learn faster and sometimes solve tasks that larger models miss.
  • 5. Discussion: SOAR could upgrade static search systems by allowing them to learn from their own search traces, with richer operators such as crossover identified as an extension.The proposed advantage is specifically over approaches that keep the underlying model fixed during search.
  • 5. Discussion: The method is evaluated only on ARC and currently requires 6,000 synthesis attempts per task per iteration, limiting evidence about broader applicability and efficiency.The authors also report diminishing gains over time and leave open whether the limit is intrinsic or methodological.

Impact Statement

The paper presents iterative model improvement as a route beyond scaling plateaus, while emphasizing safety considerations and transparent release practices for self-improving systems.

  • Impact Statement: Iterative model improvement can help overcome performance plateaus encountered when scaling model size and search budget.The paper frames this as a principle potentially relevant to applications from software development to scientific discovery.
  • Impact Statement: Self-improving AI systems raise safety considerations because self-directed learning could support future systems with broader capabilities.The authors report slowdowns rather than unbounded improvement for this approach and call for safeguards and oversight.
  • Impact Statement: The authors plan to release the complete codebase and present openness as important for responsible development of increasingly capable AI systems.They also encourage researchers building on the work to consider potential societal impacts.
  • Impact Statement: Table 6 compares inductive methods on ARC and reports that SOAR outperforms previous induction performance.The supplied caption establishes the comparison scope and the reported overall outcome, but not individual cell values.

B. Scaling laws

The scaling-law analysis examines how ARC performance changes across training iterations, model combinations, and compute-matched baselines on training and test problems.

  • B. Scaling laws: Finetuning accounts for approximately 5% of total FLOPs per iteration, making it nearly negligible relative to the search phase.The stated accounting uses 6N × (100 · T) finetuning FLOPs versus 2N × (6000 · T · n) sampling FLOPs.
  • B. Scaling laws: Figure 7 compares ARC-train performance across iterations for Qwen-2.5-Coder-7b against a gen-0 baseline matched to SOAR(1-train) FLOPs.The comparison increases generation-zero samples to 12,600 to match the combined training and inference compute of SOAR(1-train).
  • B. Scaling laws: Figure 10 compares ARC-test scores across combinations of Qwen-2.5, Qwen-2.5-Coder, and Mistral-Large-2 models.The caption names the model families but does not report individual scores.

D. Implementation details

The weighted majority voting implementation converts model responses into output patterns, scores them using frequency and training accuracy, and selects the highest-weight patterns.

  • D. Implementation details: The algorithm serializes each response’s complete test outputs into a pattern key, grouping responses that produce identical output-grid patterns.This pattern extraction is the first stage of the weighted majority voting procedure.
  • D. Implementation details: Each unique pattern receives weight = count + c × train_accuracy, combining response frequency with mean training-example accuracy.The scaling parameter is set to c = 1000 to strongly penalize patterns with low training accuracy.
  • D. Implementation details: The procedure selects the top n_output patterns by weight as the final outputs, with n_output = 2 during testing.The algorithm’s inputs include responses, training accuracies, the scaling parameter c, and the requested number of outputs.

D.2. Majority voting data selection for test time training data

Test-time training data are selected without test accuracy by grouping responses with identical output grids and weighting groups through majority voting.

  • Majority voting identifies the most probable correct solution when test accuracy is unavailable during test-time training.The selected solution is then used to train the models.
  • Responses are grouped according to their test output grids, and each group receives a normalized majority-voting weight.
  • Samples are allocated across groups using a multinomial draw, then selected within each group using quality scores based on training accuracy.Uniform within-group weights are used when all quality scores are zero.

D.3. REX Modification

The REX modification accelerates evolutionary refinement through probabilistic program selection, multiple completions, parallel instances, and feedback filtering.

  • REX algorithm: REX selects programs probabilistically using heuristic value and prior selection counts, then refines the selected program and adds its completions to the archive.The heuristic value is based on example accuracy, and refinement includes code execution on the problem.
  • Accelerated Refinement via Multiple Completions: Four completions are sampled simultaneously per prompt to reduce refinement time by sharing prompt-processing costs.
  • Parallelized REX Instances: Four independent REX instances run concurrently across compute nodes, promoting search diversity and reducing premature convergence.The strategy is conceptually analogous to island genetic algorithms.
  • Prioritize Actionable Feedback: Programs that generate errors on any input grid are removed so refinement focuses on partially correct code with more actionable feedback.

D.4. Training

SOAR fine-tuning uses parameter-efficient adaptation with specified optimization settings, while preferring shorter programs when accuracy is tied.

  • Training setup: Training starts from the Instruct model at each iteration and uses LoRA-based fine-tuning with AdamW, a 5e-5 learning rate, and 64-step gradient accumulation.Larger models use RS-LoRA or RS-QLoRA in bfloat16 precision.
  • Program prioritization: When programs have equal training accuracy, the system preferentially samples shorter programs to improve inference speed without reducing accuracy.

D.5. Inference

Inference generates many candidate programs in parallel, uses few-shot ARC examples, and stops each task after enough perfect training solutions are found.

  • Inference: Inference samples 50 completions in parallel for each task and halts generation after at least 100 solutions reach perfect ARC training accuracy.
  • Inference: Each prompt includes one few-shot ARC training example drawn from a different task in the previous generation, or the current generation initially.
  • SOAR Framework: The SOAR framework initializes an archive, samples 3k programs per task, and expands candidates to 6k through REx refinement before execution and filtering.

E. Learning to generate and refine programs jointly

SOAR studies whether one model can learn both program generation and refinement, finding complementary transfer between these capabilities while filtering brittle, non-generalizing solutions.

  • Joint generation and refinement: Positive transfer from refinement to generation improves program generation more than generation finetuning alone, while generation finetuning can reduce refinement performance.The experiment compares base, fine-gen, fine-ref, and jointly finetuned models across generation and search accuracy.
  • Joint generation and refinement: Jointly learning generation and refinement produces positive interaction effects, indicating shared knowledge about program structure and transformation patterns.The authors describe this synergy as important for improving both capabilities.
  • Search and voting: The method evaluates candidates by example accuracy, groups them by test-output grid, and uses weighted voting to favor outputs produced by more accurate programs.This ensemble reduces the influence of individual program errors while aggregating patterns across successful solutions.
  • Induction and transduction: Hybrid transduction-induction solutions can copy training outputs into hardcoded conditionals, skewing majority voting toward potentially incorrect solutions.Such solutions compute simple properties such as dimensions and map them to hardcoded outputs rather than learning generalizable patterns.
  • Induction and transduction: Hardcoded conditional solutions generalize poorly because they work only for input dimensions encountered during training, so the pipeline filters problematic outputs using validation checks.The stated check tests whether computed outputs using the solution appear in the code.
Loading 2507.14172v2…