Research map / Large language models / Agents, code and math
Self-Improving Language Models for Evolutionary Program Synthesis: A Case Study on ARC-AGI
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SOAR, which alternates evolutionary LLM program sampling/refinement on ARC with hindsight-relabeled fine-tuning of the same LLM, reaching 52% on ARC-AGI public test with test-time training.
Problem
Program synthesis with fixed LLM sampling and refinement capabilities plateaus under search; the paper asks whether learning from the model's own search attempts can lift these ceilings on ARC-AGI.
Approach
Integrates LLM sampling and execution-feedback refinement inside an evolutionary loop (Sample&Refine with REX bandit), then fine-tunes the LLM on its own successful and failed attempts via hindsight relabeling (creating valid problem-solution pairs from programs by executing them on inputs), iterating and adding test-time training on target tasks.
Key results
- SOAR with Qwen-2.5-Coder models and test-time training combined via majority voting reaches 52.00% on ARC-test, versus 42.75% for the best single-model Sample&Refine baseline reported in the table (14B), with oracle 57.25%.
- Iterated self-improvement adds roughly +19% to +27% solved tasks on ARC-train across model sizes after four iterations (e.g., 7B from ~14% to ~41%).
- Qwen-2.5-Coder-7B rises from 14.25% (Sample&Refine-6k) to 36.25% on ARC-test with SOAR, beating GPT-4.1 (8%) and Claude-4-Sonnet (20.75%) one-shot results.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Iterated self-improvement (SOAR) over Sample&Refine search | Qwen-2.5-Coder-7B · ARC-test | % solved: 14.25 to 36.25 | Helped |
| Iterated self-improvement (SOAR) over Sample&Refine search | Qwen-2.5-Coder-14B · ARC-test | % solved: 19.87 to 42.75 | Helped |
| Training on pooled data from all models and iterations instead of own data (ablation) | Base model for SOAR test-time training (Qwen-2.5-Coder-7B) · ARC-test | % solved: 19.9 to 33.0 | Helped |
| Joint finetuning for sampling and refinement vs separate specialized models (ablation) | Qwen-2.5-Coder-14B · ARC-train Sample&Refine-6k | % solved: 44.42 vs 43.88 | Helped |
| Finetuning refinement capability (diverse data) with sampling from base model (ablation) | Qwen-2.5-Coder-14B · ARC-train Sample&Refine | % solved: 34.83 to 42.88 | Helped |
| Finetuning sampling with greedy-diverse hindsight-relabelled data (ablation) | Qwen-2.5-Coder-14B · ARC-train Sample-3k | % solved: 29.29 to 36.46 | Helped |
| Hindsight relabelling with greedy-diverse selection vs correct-only solutions for sampling finetuning (ablation) | Qwen-2.5-Coder-14B · ARC-train Sample-3k | % solved: 34.67 (correct-only) vs 36.46 (greedy-diverse) | Helped |
| Uniform hindsight relabelling data for sampling finetuning (ablation) | Qwen-2.5-Coder-14B · ARC-train Sample-3k | % solved: 32.38 vs 34.67 (correct-only) | Hurt |
| Pooling search traces from 5 models before majority voting | ARC-train search · ARC-train | % solved: pooled 5x6k outperforms each individual model | Helped |
| Ensembling SOAR models across sizes via majority voting | SOAR Qwen-2.5-Coder and Mistral models · ARC-test | % solved: best single 45.50 to 52.00 ensemble | Helped |
| Test-time training iterations on ARC-test problems | SOAR models trained on all training data · ARC-test | % solved: extra ~5% on ARC-test | Helped |
| Removing the learning phase (search only, SOAR no learning) at larger model sizes | Qwen-2.5-Coder models with fixed sampling/refinement · ARC-test scaling | % solved: curves flatten beyond 32B | No clear effect |
Surprising findings
- Fine-tuning for refinement improves sampling performance (positive transfer), and joint fine-tuning outperforms specialized models.
- Training on pooled data from multiple models and iterations yields better base models than training on each model's own data, and pooled majority voting beats each individual model.
Limitations
- Requires 6,000 synthesis attempts per task per iteration, making it computationally expensive and gains diminish over iterations.
- Solution diversity drops on solved tasks, and majority voting leaves a 9.5% gap to oracle performance.
- Only evaluated on ARC; generalization to other domains untested.
Experimental setup
Datasets: ARC-AGI train (400 tasks) ARC-AGI test (400 tasks)
Benchmarks: ARC-AGI public test set (ARC-test) ARC-AGI train set (ARC-train)
Metrics: % tasks solved (pass@2 with majority voting) oracle accuracy
Baselines: Claude-4-Sonnet GPT-4.1 o3-mini Gemini-2.5-Pro CodeIt BARC-induction Sample&Refine-6k Mistral-Large-2
Builds on: CodeIt REX hindsight relabeling RS-LoRA Unsloth
Closest papers by meaning
- Simple Baselines are Competitive with Code Evolution (NeurIPS 2026 · similarity 0.89)
- From I/O to Code with Discovery Agent (NeurIPS 2026 · similarity 0.88)
- PACE: Two-Timescale Self-Evolution for Small Language Model Agents (NeurIPS 2026 · similarity 0.86)
- CATArena: Evaluating Evolutionary Capabilities of Code Agents via Iterative Tournaments (ICML 2026 · similarity 0.86)
- Program Synthesis via Test-Time Transduction (NeurIPS 2025 · similarity 0.86)
- Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.