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

We thank the reviewers for their thoughtful comments.

Reviewer cz1F noted that SOAR achieved state-of-the-art results among open-source inductive approaches on the ARC benchmark by transcending the limitations of based models through iterative self-improvement. They also noted the quality of our experimental paradigm, how it supports our claims, while praising both writing and visual illustrations.

This said, the reviewer expressed three concerns that we address below:

Discussion of CodeRL: We’d like to thank the reviewer for pointing out this work. SOAR and CodeRL both aim to improve program synthesis by improving pretrained language models with feedback from execution, but do so using different approaches:

• Learning signal: SOAR uses hindsight learning to learn from both successes and failures (rich signal) while CodeRL uses the fraction of unit tests passed (weaker signal)

• Exploration: SOAR uses a state-of-the-art method based on genetic algorithms to search the space of programs (REX), which enables a better exploration of program space than simply sampling from the current RL policy, as done in CodeRL.

• Learning algorithm: CodeRL leverages a complex actor-critic architecture while SOAR relies on a straightforward supervised finetuning procedure. Finetuning is conducted on a small fraction of the generated data (50 programs out of 6000 generated per task), making the approach computationally cheaper (RL trains on all generated programs).

• Refinement: CodeRL trains a separate policy and critic to perform refinements (code repairs) from code execution feedback, while SOAR uses a single model for generation and refinement. Our paper further demonstrates positive transfer between these two tasks (training on each makes the other better).

• Complexity: SOAR implements a simple algorithm: search, relabel, finetune, while CodeRL relies on several specialized modules including: pretraining of the policy with collected code data, warm up of the policy with ground truth programs, freezing of the policy to pre-train the critic on ground truth data, reward shaping, and others.

Overall, SOAR proposes a cleaner, simpler approach that’s easier to scale based on several key ideas: iterative improvement, finetuning of generation and refinement (positive transfer), and hindsight relabelling. The revised version of the paper now discusses this relevant work and its relation to ours.

Extensive computational resources (6k programs per task): SOAR is only trained on 50 programs per task at each generation and does not fundamentally require 6k programs per task during the search phase. If we’re sampling so many attempts, it’s because ARC is difficult, and base models are unlikely to generate interesting programs in only a few trials. This number is comparable (and even lower) to the ones used in related approaches (e.g. 20k in Li et al., 2024; 8k in Greenblatt, 2024). An interesting future work could be to look at the optimal budget allocation between running longer searches or running more refinement iterations. The optimal search budget might vary across iterations too, as finetuning might itself accelerate search by increasing the ability of the generation and refinement model to encounter successful programs earlier on (see answer to Reviewer ifzp). We note that SOAR is only useful to improve upon program synthesis domains that could not be solved by search alone, which is why it requires substantial computational resources. We added a short discussion about the significant search budget and the necessity to adapt this parameter to the domain at hand in the revised version of the manuscript.

Generalization to other domains: We picked the ARC benchmark because it was designed for the purpose of evaluating general program synthesis algorithms: it is hard, diverse, relatively out of distribution for LLMs, and explicitly designed to test core reasoning abilities beyond pattern matching.

Given our limited computing budget, we decided to focus our resources on a deep study of the SOAR approach on ARC, as opposed to a shallower study on several benchmarks. This allowed us to make the space of design decisions explicit and study which worked best using carefully controlled experiments as several reviewers have noted.

This said, SOAR is a general framework that doesn’t rely on any ARC-specific assumption and can directly be transposed to any programming-by-example domain including code synthesis like APPS. Our paper describes the methodology clearly and how to navigate the space of design decisions with careful experimentation. We thus expect SOAR to generalize across domains, but, as we acknowledge in the paper, leave the empirical verification of this claim to future work.

Please let us know if the above discussion answers your concerns and consider raising your score if it does. If it doesn’t, let us know which concerns remain so we can try to address them. Thank you!

We thank the reviewer for their helpful feedback.

The Reviewer noted the importance of the problem we tackle and the quality and pedagogy of our experimental section but raised several concerns which we address below.

Controlling for compute costs: We thank the reviewer for raising this point. In the revised manuscript, we now address it directly with a new figure: https://anonymous.4open.science/r/arc_example-EBB9/compute_match_14b.pdf. Performance improves with both model size and search budget, each following separate scaling laws. SOAR enables us to break through these plateaus and achieve higher performance levels. As shown in Figure 4, adding search and then iterative improvements via SOAR surpasses the performance ceiling reached by merely scaling model size (e.g. Claude-level performance). The new figure shows a similar pattern for the search budget. Performance with the base model (generation 0) plateaus after about 8k search attempts. In contrast, SOAR at generation 1 (after 6k search attempts, followed by finetuning, and then another 6k attempts) outperforms the base model even after 12.6k attempts (+7.5%). This 12.6k budget matches the one used by SOAR gen 1 (6k + 6k search + ~5% compute for finetuning, cf explanation below). After generation 1, search seems to plateau even earlier (~5k), but SOAR still achieves significant performance gains across generations. This experiment answers the reviewer’s question: Would using the same compute budget to generate more solutions with the base model yield similar performance gains as SOAR? The answer is no. The base model stagnates at ~8k attempts, with performance at 12.6k attempts remains on par with its 6k result. Thus, SOAR achieves superior results within the same compute constraints. The revised manuscript includes a new figure illustrating this, reinforcing that SOAR overcomes performance plateaus in model size and search budget scaling, achieving higher plateaus.
Finetuning costs: Finetuning is inexpensive compared to the search phase. FLOPs per iteration is $6N \times (100 \cdot T)$, where $N$ is LLM parameters and $T$ is tokens per completion. With ≤100 datapoints per task, sampling FLOPs is $2N \times (6000 \cdot T \cdot n)$, making finetuning ~5% of total FLOPs—nearly negligible. Additionally, autoregressive generation is slower (token-by-token forward passes), while finetuning processes sequences in one forward and backward pass, per Austin et al. ("How to Scale Your Model", 2025).

Possible leaking across test tasks: In the official ARC-AGI Kaggle competition and related literature, there are no strict constraints on the order of task processing or the use of unsupervised data across tasks. This flexibility allows methods to leverage examples from other tasks in an unsupervised fashion, though it’s unclear whether this provides a significant advantage over refining strong candidate solutions within a single task. Several prior works (e.g., Akyürek, et al. 2024 ) adopt similar practices.

Relation to the STaR algorithm: The confusing comment has been clarified. SOAR isn’t an implementation of STaR but shares its spirit, enhancing LLM reasoning by bootstrapping from self-generated data. STaR applies this to reasoning tasks with chain-of-thought text, using binary signals to identify correct reasoning for finetuning. SOAR adopts a similar approach, finetuning on self-generated programs from a search process, guided by hindsight relabeling of input-output pairs, training both generation and refinement. This is now clearer in the paper.

Comparison with FunSearch and Evolution of Heuristics: SOAR enhances search algorithms using LLM models for generation and mutation. FunSearch, like REX, is one such algorithm. While SOAR could be compared to FunSearch, it’s not a direct competitor (REX is): SOAR can be used to improve upon FunSearch by training its generation and refinement capabilities. In particular, FunSearch also uses a “crossover” operator to generate candidate programs from two seed programs. These could also be trained with SOAR using the exact same iterative finetuning paradigm. This is also applied to the evolution of thoughts of EoH. Studying SOAR’s impact on FunSearch, especially training crossover for performance gains, is future work due to limited resources. We address these in our related work section.

Generalization to other domains (eg bin packing): Please refer to our answer to Reviewer cz1F who also commented on this point (last point in our answer).

Minor points:

• We corrected the typos pointed by the reviewer

Please let us know if the above discussion answers your concerns and consider raising your score if it does. If it doesn’t, let us know which concerns remain so we can try to address them. Thank you!

We thank Reviewer FfTX for their helpful feedback.

The reviewer noted that the approach is reasonable, intuitive and novel. They commented on the strength and extensive details of our experimental studies, acknowledging that they supported our claims. This said, they raised several concerns that we address here:

Too many components in the method: This kind of feedback is particularly helpful to help us simplify the presentation of the method. We argue SOAR is simple: 1) use some kind of search algorithm to generate candidate programs (REX for us); 2) select interesting programs and apply hindsight relabelling; 3) finetune; 4) repeat. Section 4.2 explores step 2’s design space for ARC-AGI, not a “mad scramble” but a guide for adaptation, and we think that it will help others adapt SOAR to their use case. The revised manuscript better separates the high-level idea from this exploration.

Need for qualitative analyses (features across generations and models, examples and error analysis): We agree that qualitative analyses are important here. Our analyses found the following trends across generations (true of all model sizes, numbers for Qwen 14B):

• The proportion of error-free programs rises on average from 0.92 (gen 0) to 0.98 (gen 4).
• Complexity increases given the increase in Lines of codes from 16.6 to 24.5, number of control structures (5.2 to 9.5) and the maximum depth of control structures in the AST from 3.4 to 4.7. Interestingly, the number of helper functions remains stable (1.5 -> 1.4).

To discuss qualitative results, we created an anonymous repository containing interesting examples at https://anonymous.4open.science/r/arc_example-EBB9/. We choose one example for each of the following categories, but feel free to explore other examples:

• Examples of tasks solved only by smaller models: e.g. example in solved_by_smaller_models_only

• Examples of tasks only solved by later generations: e.g. example in solved_in_later_generations

• Examples of failures and successes e.g. examples in other folders

The revised version of the manuscript will include graphs of the trends across models and generations in the Appendix, a link towards the codebase and the repository of examples. This will open the opportunity for others to study generated programs in more detail and discover new insights. One way could be to use LLMs to label each program along various dimensions: eg, does it use recursion? Does it identify objects? Symmetry? And ask LLMs to describe the overall solving strategy, then use these features to analyze how their distribution shifts across generations and models, whether the diversity of strategy used increases or decreases with finetuning, or when a solution is found. These analyses are left for future work, either by us or by anyone else using the dataset of generated programs we will release with the paper.

Practical constraints of the AGI-Benchmark: This work did not run in the Kaggle competition but was constrained by limited compute resources. Experiments for the 14B model cost an estimated USD 4000 (excluding method development costs). This explains why we focused on a single domain: preferring conducting carefully experiments and exploration of the design space (Section 4.2) rather than superficially reporting final success rates on several benchmarks. These computational constraints forced us to use data-efficient finetuning methods (LoRA, unsloth) and capping examples per task we could train on (50/6000 generated codes). The revised manuscript makes these constraints more explicit and discloses a more detailed cost of our experiments to clarify some of the design choices.

Does SOAR break through scaling plateaus? Does SOAR overcome scaling plateaus? In Figure 4, dashed lines represent one-shot closed-source large LLMs, not scaling plateaus. Here, “scaling plateaus” refer to the leveling-off of each curve as model size increases. Each enhancement shifts to a higher scaling law, breaking these plateaus. Our new figure (compute_match_14b.pdf in the repo) shows scaling search also hits plateaus, which self-improvement surpasses.

The Claude+Search comparison (Greenblatt, 2024) is absent from Figure 4 (42%). We believe SOAR could break this plateau too, though applying it to Claude is infeasible (closed model, high cost). Updated Figure 5 and the new figure clarify these points.

Minor concerns and suggestions:

• GA references: We added the GA references suggested and complemented our EC related work.

• Majority voting: Majority voting is here necessary to decide which final solution to submit to a given task given a whole search trajectory and is therefore used in all search approaches.

• We corrected typos

Please let us know if the above discussion answers your concerns and consider raising your score if it does. If it doesn’t, let us know which concerns remain so we can try to address them. Thank you!

We thank the reviewer xjKq for their review of our manuscript and appreciate the recognition of the key aspects of our approach.

The review itself did not include any critique or suggestion for improvement, but it did not come with the highest recommendation either ("Weak accept").

This decision suggests there may be opportunities to strengthen our work, and we would be happy to address any additional feedback or suggestions for improvement.

Please consider raising your score if you have no concerns. If you do, please let us know what they are so we can try to address them. Thank you!

We thank Reviewer 5bhq for their time and constructive feedback.

The reviewer understood our work and noted the strength of our experimental study and how its results support our claims. This said, the reviewer raised several concerns that we have addressed below.

Are results controlled for compute budget? Thank you for raising this question. Section 4.2 aims at answering the three main questions:

• Does finetuning for generation help generation? → Yes. We compare with the base model thus do not control for finetuning costs (one is not trained, seed response to reviewer ifzp for detail analysis between finetuning and inference cost), but we control for the search budget (3k each)

• Does finetuning for refinement help refinement? → Yes. Same search budget of 6k on each side, not controlled for finetuning cost (one is not trained)

• Does finetuning the model for both works better than finetuning two models, one for each task? → Yes. We control for search (6k) and finetuning costs: specialized models are finetuned on 50 examples per task each, while the combined model is trained on the 100 pooled examples once.

Do models of different sizes solve problems in different ways? Do models of varying sizes approach problems differently? Combining results from models sized 7B, 14B, and 32B yields up to a +4.75% improvement on the training set—a notable gain for the challenging ARC task. This suggests some complementarity: smaller models (e.g., 7B) still contribute value when paired with the largest (32B).

Future work will explore why, but we conducted some simple analyses to start answering this question: Some models give plausible solutions, but they don’t handle edge cases well; they just implement a high-level idea of the transformation with missing details. We further identified examples of tasks solved by smaller models but unsolved by the 32B model that we make available here: https://anonymous.4open.science/r/arc_example-EBB9/. See more details in our answer to Reviewer FfTX discussing generated programs qualitatively.

Comparison to transduction approaches to ARC (Akyürek et al.): Our approach relies on program induction and indeed underperforms some transduction approaches predicting output grids directly (e.g Akyürek et al.’s 47.1% with test-time training, or OpenAI’s o1).

One thing to note is that transduction approaches are more susceptible to data contaminations: the test set output grids have been publicly available for years (e.g. on GitHub and Kaggle). Induction methods, on the other hand, need to predict correct transformation programs which are not found online. Akyürek et al. also note that their method was developed using a subset of the test set, raising concerns about overfitting to those specific examples. Whether transduction methods overfit or not, we believe it is valuable to pursue both approaches independently, as we do not know which one will solve ARC in the end. Program synthesis also has many applications beyond the ARC domain. Moreover, programs are more interpretable and open a window on the reasoning process of LLMs that transduction methods do not offer.

Reliance on Qwen base models: We selected Qwen series models for their strong coding skills relative to their size. Experiments show that better base models yield superior final performance, though smaller models can match the initial performance of larger ones using SOAR. We expect SOAR to work with any model capable of finding correct solutions via search, with stronger models producing better outcomes. Limited compute resources prevented testing SOAR on other models, leaving this for future validation. SOAR could be adjusted to boost weaker models by increasing compute per iteration (longer searches, more finetuning) or adding iterations. Future work might explore pooling outputs from diverse models (e.g., Mistral, Gemma, Llama) to enhance complementarity, as seen in our experiments. While Qwen models excel, smaller alternatives like Mistral 3.1 or Gemma-3, improving in reasoning, could substitute. These ideas are now in the updated manuscript.

Assumption of access to full test set: We now discuss this assumption in the manuscript but we note that this is a common assumption, as it is the format used in the original Kaggle competition. Our approach could in principle be used on one task at a time. This would require training a separate model for each task which would be computationally expensive and might hinder possible effects of generalization across tasks.

Confusing terminology Generation vs Search: The Sample approach (pure generation and ensembling) is indeed a form of (simple) search. We updated the paper with less ambiguous terms: Sample vs Sample&Refine. Please let us know if the above discussion answers your concerns and consider raising your score if it does. If it doesn’t, let us know which concerns remain so we can try to address them. Thank you!