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

Hard program-synthesis problems can exceed one-shot language-model capabilities, while evolutionary search with fixed models faces diminishing returns. SOAR alternates evolutionary sampling and refinement with fine-tuning on search traces; after four training iterations, it solves an extra 10–19% of tasks across model sizes.

  • Problem

    For harder synthesis problems, evolutionary search relies on LLMs whose sampling and refinement capabilities remain fixed, limiting the approach as additional candidates and refinements yield diminishing returns.

    Source: §1 · p. 1

  • Method

    SOAR alternates evolutionary search that samples and refines candidate programs with fine-tuning on search traces to improve the model’s future sampling and refinement.

    Source: §1 · p. 1, §3 · p. 3

  • Results

    10–19% extra tasks are solved across model sizes after four SOAR training iterations.

    Source: §1 · p. 2

  • Takeaways & Limitations

    SOAR’s results indicate that self-improvement from search experience can bootstrap reasoning capabilities in general-purpose language models without demonstrations or DSLs.

    Source: §5 · p. 9

    SOAR is evaluated only on ARC, and computational efficiency remains a limitation.

    Source: §5 · p. 9

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

SOAR couples evolutionary program search with hindsight fine-tuning on its own search attempts, improving sampling and refinement over iterations. On ARC, it reaches 52% test performance, with additional gains from iterative improvement and test-time training.

Introduction

  • Program synthesis is challenging because the space of possible implementations is vast, making it difficult to find a program that satisfies all constraints.Users can specify their goals through constraints, examples, or natural language rather than precise instructions.Source: §1 · p. 1
  • SOAR alternates LLM-driven evolutionary sampling and refinement with hindsight fine-tuning on search traces, creating a cycle in which improved models enable more effective search.The search experience then provides better training data for further model improvements.Source: §1 · p. 1
  • SOAR learns only from its own successes and failures, synthesizes general-purpose Python, uses execution feedback for iterative repair, scales to larger open-weight LLMs, and combines test-time training with search.These design choices extend earlier self-improvement work on ARC.Source: §1 · pp. 1–2
  • On ARC, GPT-4.1 solves 8.00% and Claude-4-Sonnet 20.75% of test tasks; search raises open-source models from 1-2% to 14-26%, but fixed capabilities impose a ceiling.ARC tasks require inferring grid transformations from only a few examples.Source: §1 · p. 2
  • 52% final test performance; after four training iterations SOAR solves an extra 10-19% of tasks, while test-time training adds 3-5% across model sizes.The gains come from learning to sample and refine better programs from search experience, without task-specific human engineering or training data.Source: §1 · p. 2

2. Related Work

SOAR differs from prior synthesis and evolutionary-search approaches by continuously improving its language model from synthesis experience rather than treating it as fixed. On ARC, it extends prior search and expert-iteration methods with Python synthesis, feedback-driven refinement, and adaptation from past attempts.

Program synthesis methods

  • SOAR learns Python program synthesis from past attempts, unlike traditional search or learned components for constrained languages that depend on engineered priors, operators, or offline data.Prior approaches used genetic programming or sequential Monte Carlo, learned program samplers, or search-speeding decision mechanisms (Goldberg; Holland; Koza, 1994; Langdon & Poli, 2013; Liang et al., 2010; Saad et al., 2019; Balog et al., 2016; Ellis et al., 2021; Shi et al., 2022).Source: §2 · p. 2

Related work on LLMs and search

Learning from search traces

  • Where prior reasoning-trace training uses successful self-generated or search-produced traces, SOAR learns from both successful and failed attempts and improves refinement for test-time evolutionary search.Prior work includes self-generated traces (Zelikman et al., 2022; 2024; Guo et al., 2025) and traces from classical search (Gandhi et al., 2024).Source: §2 · p. 3

ARC synthesis approaches

  • ARC work spans direct output-grid prediction and transformation-program synthesis, from synthetic-data-finetuned transduction to DSL search and LLM-based Python program sampling and refinement.Initial LLM transduction performed poorly (Xu et al., 2023; Gendron et al., 2023; Mirchandani et al., 2023), while synthetic-data finetuning improved results (Li et al., 2024; Akyürek et al., 2024); inductive approaches include DSL search and Python synthesis (Wang et al., 2023; Li et al., 2024).Source: §2 · p. 3

Closest related work

  • Compared with CodeIt’s expert iteration using a hand-designed DSL, SOAR uses Python, adds execution-feedback refinement, and scales to larger open-weight LLMs.CodeIt uses hindsight relabelling to turn failures into positive training pairs (Butt et al., 2024); SOAR also refines sampling and refinement operators solely from synthesis attempts and combines test-time training with search, avoiding dependence on human engineering and datasets.Source: §2 · p. 3

3. Method

SOAR alternates evolutionary program search with finetuning on search traces, so improved sampling and refinement can support more effective later search. Its method defines ARC as example-driven synthesis, implements sampling and feedback-guided refinement, learns from search attempts, and extends the loop to test-time adaptation.

3.1. Problem definition

  • ARC program-by-example synthesis seeks a Python function matching the provided colored-grid training pairs and producing correct outputs for test inputs.The broader PBE formulation seeks a program that maps every provided input x to its output y.Source: §3.1 · p. 3

3.2. Program synthesis as evolutionary search with LLM-based sampling and refinement

  • SOAR independently samples 3k candidate solutions, then spends a 3k-refinement budget using REX, which combines Thompson sampling based on training-example accuracy with an exploration bonus.It groups programs by test output grid, scores each by summed example accuracy, and returns two candidate solutions.Source: §3.2 · p. 4

3.3. Learning to search via self-improved sampling and refinement

  • Hindsight relabeling turns every sampled program into a valid solution for a synthetic task, expanding sparse correct-solution data into 2.4M examples before subsampling to at most 50 per task.Selection balances 25 top-performing and 25 bottom-performing solutions by accuracy.Source: §3.3 · pp. 4–5
  • Successful refinements of incorrect programs form a separate finetuning dataset, subsampled across bins of parent-program accuracy to improve refinement from execution feedback.The accuracy bins are 0%, 1–34%, 34–98%, and 100%.Source: §3.3 · p. 5

3.4. Closing the loop: iterative self-improvement on training and testing tasks

  • At each training iteration, the finetuned model powers the next search; at test time, SOAR further adapts through sampling-only finetuning using training-example accuracy and hindsight relabeling.The described test-time method does not use refinement finetuning.Source: §3.4 · p. 5

4. Experiments

SOAR improves ARC program synthesis through iterative search and learning, reaching 52.00% on ARC-test after train-time and test-time adaptation. Experiments also show improved sampling and refinement, gains across iterations, and different diversity trends for solved and unsolved tasks.

4.1. Program synthesis methods must leverage search

  • 20.75% for Claude-4-Sonnet and 8.00% for GPT-4.1 were one-shot ARC-test rates, while Sample&Refine-6k improved results across Qwen-2.5-Coder sizes.Qwen-2.5-Coder models achieved 1.00–2.25% one-shot success; Sample&Refine-6k let the 7B model beat GPT-4.1 and models ≥32B beat Claude-4-Sonnet.Source: Table 1 · p. 6, §4.1 · p. 6

4.2. Learning to sample and refine programs

  • Greedy-diverse hindsight data produced the best finetuned sampling accuracy, balancing successful solutions with diversity in training examples.The method combines 25 greedily selected solutions with 25 that solved the fewest training examples; unlike correct-only training, hindsight relabeling also creates problem-solution pairs from sampled programs.Source: §4.2 · p. 6, Table 2 · p. 7
  • Joint finetuning improved sampling and search over base and task-specific models, while diverse refinement reached 42.88% ARC-train when refining solutions sampled by a non-finetuned model.Both refinement-example strategies substantially improved refinement, with diverse sampling marginally better; joint learning showed synergy between sampling and refinement.Source: Table 4 · p. 7, §4.2 · p. 7, Table 3 · p. 7

4.3. Learning to search with iterated self-improvement

  • Across iterations, ARC-train solutions increased by 27% for 7B, 24% for 14B, 20% for 32B, 19% for 72B, and 22% for Mistral.Larger models started with stronger search, but smaller models improved more steeply early on and had larger relative gains; pooling search traces from five models outperformed each individually, though majority voting trailed oracle performance by 9.5% on average.Source: §4.3 · p. 7, Figure 2
  • 52.00% ARC-test accuracy was SOAR’s peak after combining solutions across model sizes; two test-time training iterations added 5% performance.The 7B model rose from 14.25% to 36.25%, while the 14B, 32B, 72B, and Mistral-Large-2 models reached 42.75%, 44.37%, 44.87%, and 45.5%, respectively; oracle performance was 57.25%.Source: Figure 3 · p. 8, §4.3 · p. 8

4.4. Escaping scaling plateaus through self-improvement

  • SOAR lifted model-size and search-budget plateaus: fixed-capability search flattened beyond 32B or about 5.2k attempts, while learning to refine raised the ceiling.Qwen-2.5-7B reached 36.25% ARC-test after two test-time training iterations, outperforming o3-mini and Claude-4-Sonnet; this passage also reports better performance than prior methods relying on human-generated data or larger closed-source models (Li et al., 2024; Greenblatt, 2024).Source: Figure 4 · p. 8, §4.4 · pp. 8–9, Figure 5 · p. 9

4.5. Solution diversity across iterations

  • Solution diversity decreased across iterations on tasks SOAR solved, but on unsolved tasks it dropped initially and then plateaued.The authors suggest relabeling may help preserve exploration on unsolved tasks and note that explicit diversity-enhancing strategies could further support exploration and continual improvement.Source: §4.5 · p. 9

5. Discussion

SOAR improves program synthesis through an iterative loop of evolutionary search and learning, with cross-model diversity supporting gains while computational cost and diminishing progress remain challenges.

Discussion

  • SOAR maintains solution diversity on unsolved problems but converges to lower diversity on solved ones, and this is insufficient to sustain continual progress.The authors attribute maintained diversity likely to hindsight relabeling and suggest diversity-aware finetuning, quality-diversity methods, or generating new problems; Figure 6 measures diversity by average pairwise cosine distance in CodeRankEmbed space.Source: Figure 6 · p. 9, §5 · p. 10
  • On ARC, SOAR improves from its own search experience without demonstrations or DSLs, despite the benchmark’s resistance to pattern matching and reliance on core reasoning.The discussion presents this as evidence that self-improvement alone can bootstrap strong reasoning capabilities in general-purpose language models.Source: §5 · p. 9
  • Ensembling solutions across model sizes gives SOAR its best ARC-test performance (52%).The discussion identifies cross-model diversity as a key driver of performance gains.Source: §5 · p. 9
  • SOAR overcomes scaling plateaus, while smaller models can learn faster and solve tasks larger models miss; aggregated multi-model, multi-iteration training yields the strongest improvements.Source: §5 · p. 9
  • SOAR could upgrade static-search systems such as FunSearch and AlphaEvolve by letting them learn from search traces; richer operators such as crossover are another extension.The cited systems use program synthesis without adapting their models (Liu et al., 2024); crossover is discussed by Meyerson et al. (2024).Source: §5 · p. 9
  • 6,000 synthesis attempts per task per iteration are currently required, SOAR is evaluated only on ARC, and its steady gains diminish over time.The discussion leaves open whether diminishing gains are intrinsic or methodological and suggests rerouting search budget toward harder tasks or improving optimization methods.Source: §5 · pp. 9–10

Impact Statement · A. Comparison with prior work

SOAR illustrates how iterative model improvement can overcome performance plateaus, while its slowdown and potential broader implications underscore the need for safeguards and oversight.

Impact Statement

  • Iterative model improvement helps overcome performance plateaus encountered when scaling model size and search budget.The authors suggest this principle could benefit applications including software development and scientific discovery.Source: Impact Statement · p. 10
  • The results show clear performance slowdowns rather than unbounded improvement, indicating limitations of this specific approach.Source: Impact Statement · p. 10
  • Self-directed learning could inspire future systems with broader capabilities, making safeguards and oversight important in their development.Source: Impact Statement · p. 10
  • The work uses open-source language models and commits to releasing its complete codebase upon publication.Source: Impact Statement · p. 10
  • The authors describe transparency as crucial to responsible development and urge future researchers to maintain openness while considering societal impacts.Source: Impact Statement · p. 10

A. Comparison with prior work

  • SOAR outperforms previous induction methods on the ARC benchmark.Table 6 compares inductive methods on ARC.Source: Table 6 · p. 14

B. Scaling laws · C. Model ensembling

SOAR’s scaling analysis compares iterative training with compute-matched sampling, and reports that generation 1 outperforms the base-model Sample&Refine baseline at the same computational budget. The sections also describe ARC-test evaluations across training iterations and model combinations, without supplying their outcomes in the provided passages.

B. Scaling laws

  • SOAR generation 1 reaches far superior performance to base-model Sample&Refine at the same computational budget.Figure 8 compares SOAR with a 6k search budget against base-model Sample&Refine with a 12.6k budget, matched to SOAR generation 1’s FLOPs including finetuning costs.Source: B. Scaling laws · p. 14, Figure 8 · p. 16
  • Finetuning is estimated to account for ∼5% of total FLOPs, making it nearly negligible relative to search.The estimate assumes ≤100 datapoints per task: 50 refinement and 50 solution datapoints.Source: B. Scaling laws · p. 14
  • Sampling FLOPs per iteration are estimated as 2N × (6000 · T · n), compared with finetuning costs of 6N × (100 · T).Here, N is the number of LLM parameters and T is tokens per completion; autoregressive generation is slower because it uses token-by-token forward passes, while finetuning processes sequences in one forward and backward pass.Source: B. Scaling laws · p. 14
  • Figure 7 plots Qwen-2.5-Coder-7b ARC-train performance across iterations, with 12,600 generation-zero samples to match SOAR(1-train)’s total FLOPs.The caption says the matched total includes both training and inference.Source: Figure 7 · p. 15
  • Figure 9 reports ARC-test performance across training iterations for a generation-zero model.The caption’s description of what that model was trained on is incomplete in the supplied passage.Source: Figure 9 · p. 17

C. Model ensembling

  • Figure 10 evaluates ARC-test scores for combinations of Qwen-2.5, Qwen-2.5-Coder, and Mistral-Large-2 models.The supplied caption identifies the model combinations but provides no score values or winning combination.Source: Figure 10 · p. 18

D. Implementation details · D.1. Weighted Majority Voting Algorithm · Weighted Majority Voting Algorithm:

The algorithm groups model responses by their test outputs and uses weighted voting over serialized output patterns to select final predictions.

D.1. Weighted Majority Voting Algorithm

  • Responses are grouped by their test output grids, and weighted voting selects the most reliable predictions.The algorithm processes each response’s predictions for a set of input grids.Source: §D.1 · p. 18

Weighted Majority Voting Algorithm:

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

For test-time training, SOAR modifies its greedy-diverse data selection to use majority voting because test accuracy is unavailable, selecting likely-correct solutions for training.

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

  • Without test accuracy, SOAR uses majority voting to identify the most probable correct solution for test-time training.The procedure is a minor modification to the sampling strategy within greedy-diverse data selection.Source: §D.2 · p. 19
  • The sampling procedure groups responses by test output grid, weights groups by majority vote, and allocates samples across groups using a multinomial draw.Within each group, responses are sampled by normalized quality scores based on c × train_accuracy; if all scores are zero, weights are uniform.Source: §D.2 · p. 19

D.3. REX Modification

The REX modification keeps the recommended C = 20 while targeting its computational cost through faster sampling, parallel instances, and more actionable refinement feedback.

D.3. REX Modification

  • REX uses C = 20, following the original publication’s hyperparameter analysis recommendations.Source: §D.3 · p. 19
  • Four completions are sampled simultaneously per prompt, reducing repeated prompt-processing costs.The change exploits inference systems that incur prompt-processing costs once when generating multiple output sequences.Source: §D.3 · p. 19
  • Four independent REX instances run concurrently across compute nodes, promoting search diversity and mitigating premature convergence.The strategy draws conceptual parallels to island genetic algorithms and has promising precedent in FunSearch.Source: §D.3 · pp. 19–20
  • Code that errors on an input grid is removed so refinement focuses on partially correct solutions and more actionable feedback.Source: §D.3 · p. 20

D.4. Training

At each iteration, the Instruct model is fine-tuned with a response-only LoRA-based training recipe, while equally accurate shorter programs are preferred to keep inference faster.

D.4. Training

  • Training used Unsloth, AdamW at 5e-5, batch size 1, 64-step gradient accumulation, 0.1 warmup, and 0.05 weight decay.Only responses were trained, in bfloat16 precision, starting from the Instruct model at each iteration.Source: §D.4 · p. 20
  • LoRA used rank 256 and α = 32, except Mistral-Large-2 used rank 64; models above 14 billion parameters used RS-LoRA or RS-QLoRA.The order of each example’s grid was randomly shuffled to enhance generalization.Source: §D.4 · p. 20
  • When programs tied on training accuracy, the system preferentially sampled those with fewer characters to avoid slowing inference on lengthy examples.This was intended to maintain faster inference without compromising accuracy.Source: §D.4 · p. 20

D.5. Inference

Inference used SGLang to generate parallel candidate programs with task-specific few-shot prompting and accuracy-based early stopping.

D.5. Inference

  • SGLang sampled 50 completions in parallel for each task.Inference used temperature 1 and Min-p 0.05.Source: §D.5 · p. 20
  • Each task prompt included one ARC training-set example drawn from a different task than the previous generation, except in the first iteration.Source: §D.5 · p. 20
  • Generation stopped independently in sampling and refinement once a task had at least 100 solutions with perfect ARC training accuracy.This early stopping criterion was used to reduce computational cost.Source: §D.5 · p. 20

E. Learning to generate and refine programs jointly … I.2. ARC Problem 0d3d703e

This section examines joint training for ARC program generation and refinement through search behavior, potential risks, prompts, and task-specific examples. It presents implementations—both incorrect and correct for some tasks—across a range of grid transformations.

E. Learning to generate and refine programs jointly

  • Joint fine-tuning improves generation and refinement over refinement-only and separate task-specific models; refinement-only improves generation over generation-only, while generation-only hurts refinement.The authors describe a positive interaction between the capabilities and suggest they share knowledge about program structure and transformation patterns.Source: Table 7 · p. 21, E. Learning to generate and refine… · p. 21

F. Program synthesis using a mix of induction and transduction

  • Hybrid transduction-and-induction solutions can skew majority voting by copying prompted outputs and fail to generalize beyond training dimensions; filtering code that contains computed outputs can mitigate this.The examples combine Python-computed properties such as matrix dimensions with hardcoded outputs.Source: F. Program synthesis using a mix of… · p. 21

G. Prompts

  • The prompts request general transform code from input-output examples for sampling, and code repair for refinement, emphasizing accuracy across provided and test inputs.The excerpt reports an initial implementation that failed all five training pairs before showing a repair response.Source: G. Prompts · pp. 22, 23, 25

H.1. ARC Problem 6b9890af

  • For each color, code extracts a bounding box and creates a square size-by-size resized array, sampling source positions at row and column steps rows/(size−1) and cols/(size−1), or zero when the respective dimension is one.Source: §H.1 · pp. 26–27

H.2. ARC Problem 72ca375d

  • The 72ca375d example searches for the largest nonzero, same-color rectangle by extending candidate runs horizontally and vertically and tracking their area.The search stops extending a rectangle when a cell differs from the candidate color.Source: §H.2 · p. 27
  • For ARC Problem 72ca375d, the program returns a largest rectangle when it is 2×4; otherwise, it finds the connected component matching the rectangle’s starting color and extracts its bounding box.The excerpt shows the largest-component search and the rectangle-dimension check.Source: §H.2 · p. 28

H.3. ARC Problem 1f642eb9

  • For ARC Problem 1f642eb9, the program uses depth-first search to label orthogonally connected regions of color 5, then begins constructing a component-number map.The supplied code excerpt ends during the subsequent grid traversal.Source: §H.3 · pp. 28–29

H.4. ARC Problem ef26cbf6

  • For ARC Problem ef26cbf6, the program copies a neighboring non-8 color into a cell, or searches past zeros in that direction for a nonzero color.It checks the four orthogonal directions and writes the discovered color into a transformed grid.Source: §H.4 · p. 29

H.5. ARC Problem 1f876c06

  • For ARC Problem 1f876c06, the program connects each digit’s consecutive occurrences with a straight line of that digit.It iterates over digits 1–9 and steps row-wise and column-wise toward the next occurrence.Source: §H.5 · pp. 29–30

I.1. ARC Problem 22168020

  • The transform applies fill_gaps to each grid row and column, assigning a line’s start_value to entries in the gap-filling loop.Source: §I.1 · p. 31

I.2. ARC Problem 0d3d703e

  • For ARC Problem 0d3d703e, the correct program remaps colors 3↔4, 1↔5, 2↔6, and 8↔9 cell by cell.Unlisted colors remain unchanged.Source: §I.2 · p. 32

Related papers

Loading 2507.14172v2…