AGAR: a reinforcement learning substrate for LLM program evolution

Haoran Li; Zengle Ge; Xiaomin Yuan; Yui Lo; Haoxin Li; Songlin Zhou; Qianhui Liu; Jiahua Ying

cs.AIOct 6, 2026

AGAR: a reinforcement learning substrate for LLM program evolution

Authors: Haoran Li, Zengle Ge, Xiaomin Yuan, Yui Lo, Haoxin Li, Songlin Zhou, Qianhui Liu, Jiahua Ying, +6 more

Organizations: University of the Chinese Academy of Sciences · Baidu · Tsinghua University · Institute of Automation, Chinese Academy of Sciences · Shanghai University

Abstract

Given a task and an evaluator, a language model can rewrite a candidate program while a search loop decides which rewrites survive, offering a practical route to algorithm discovery. But that loop is governed by five constants set by hand: which parent to select, how hard to mutate, how to keep diversity, what to remember, and a scalar score that never says which part of the program earned it. Reinforcement learning already has an estimator for each. The obstacle is that program evolution is not usually written down as a decision process. We formalize it as a Markov decision process whose action is the modular prefix the model is conditioned on, rather than the program it emits. Credit assignment, value estimation, adaptive exploration, and experience memory can then attach to distinct components. AGAR (Algorithm Generation As RL) provides the resulting substrate: any estimator can be replaced or switched off without changing the controller, making the transfer auditable one mechanism at a time, with no gradient training of the backend model. Across 19 tasks, two backends, and three seeds under one harness, AGAR improves on the stronger of two published baselines on most tasks, with gains concentrated in the competitive-programming family. The formalization also yields a checkable reading of prior work: these systems are implicitly zero-discount, not by choice, but because fitness is exogenous to an individual rather than a return over successors, leaving a discount factor nothing to act on.

Figures & tables

Figure 1: The transfer as a whole. Left to right: the mixed-granularity state $s_{t}$ ; the policy $\pi$ , whose action $a_{t}$ is the modular text prefix $M_{1}$ – $M_{3}$ produce, with $M_{4}$ supplying retrieved context rather than an action factor; the environment, in which the frozen black-box LLM sees only that prefix plus the task description and parent code, and a pluggable selection operator folds the result back into the population; and the reward terms of Eq. equation 2 . The outer arrows are the two loops that make this RL rather than a re-labelling: the TextGrad update over the module guidelines $\theta_{i}$ (top), and the $s_{t}\to s_{t+1}$ transition the search itself performs (bottom).

Figure 2: The substrate. Top: the streaming loop — fill $W$ slots, wait for any completion, dispatch a replacement immediately — with the controller as sole writer of the population and the $W$ in-flight rollouts reading a dispatch-time snapshot and writing only their own trajectory. The four pipeline stages ( select , generate , evaluate , judge ) are the substrate’s; the replaceable modules sit in the select slot. Shared resource pools are acquired per use and returned. Bottom: the same loop in the three moments used throughout this paper, with $\tau$ defined as the population-version difference between dispatch and landing.

Backend	OE	SE	AGAR Base	AGAR Combo
DeepSeek-V4-Flash	$0.855{\pm}0.193$	$0.919{\pm}0.138$	$0.949{\pm}0.107$	$\mathbf{0.990{\pm}0.024}^{\diamond}$
GLM-5.2	$0.897{\pm}0.131$	$0.929{\pm}0.093$	$\mathbf{0.979{\pm}0.045}$	$0.972{\pm}0.052$

Table 1: Best-at-budget, normalized mean

\,\pm\,

std across all 19 tasks (3 seeds per system). Each task score is divided by the per-task maximum over all four systems before averaging, so the best system on each task scores 1.0 and the number is comparable across tasks. Per-task raw scores are in Appendix D.10 .

\diamond

two of the 19 tasks have fewer than 3 seeds completed for AGAR ( ahc015 , ahc027 ).

Task	$L_{0}$	$L_{1}$	$L_{2}$	$L_{3}$	$L_{0}\!\to\!L_{3}$
ahc008	0.5441	0.7380	0.5452	0.9041	$+66.2\%$
ahc015	0.9687	0.9835	0.9336	0.8284	$-14.5\%$
ahc016	0.6670	0.7316	0.9160	1.0188	$+52.7\%$
ahc024	0.8659	0.8819	0.8774	0.8636	$-0.3\%$
ahc039	0.8797	0.8978	0.9404	0.8843	$+0.5\%$
Mean	0.7851	0.8465	0.8425	0.8998	$\mathbf{+14.6\%}$

Table 2: Substrate ladder (raw task score, mean over 3 seeds, every cell run to the full 100 fitness evaluations). Backend: DeepSeek-V4-Flash.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Task	$W$	$n$	Mean	Median	p95	Max	$>\;W{-}1$
ahc011 (C++)	1	60	0.00	0	0	0	0.0%
ahc011 (C++)	2	330	0.90	1	2	5	13.0%
ahc011 (C++)	4	322	2.74	3	5	10	20.8%
ahc011 (C++)	8	333	6.05	6	12	22	18.6%
eplb (Python)	1	250	0.00	0	0	0	0.0%
eplb (Python)	2	306	0.97	1	2	3	15.4%

Appendix

Table 3: Distribution of

\tau

(number of population updates between dispatch and landing), pooled over 3 seeds per configuration. The last column is the fraction of rollouts that exceed the naive bound

W{-}1

System	What it does	Difference in AGAR
AlphaEvolve ( Novikov et al., 2025 )	Fixed prompt template + evolutionary search	Prefix is learnable
ShinkaEvolve ( Lange et al., 2025 )	Bandit over LLMs + novelty sampling	Full tool transfer, not only a bandit
EvoX ( Liu et al., 2026 )	Co-evolves solutions and search strategy	Strategy improved by a critic against explicit $J$ , not by selection
SMC-Evolve ( Jiang et al., 2026 )	Principled sampling, fixed rules	Rules are learned, not fixed
TextGrad ( Yuksekgonul et al., 2024 )	General-purpose text optimization	Coupled to an RL objective in an evolutionary loop
RLHF / GRPO ( Ouyang et al., 2022 ; Shao et al., 2024 )	RL to train LLM parameters	No parameter training; text-space optimization

Appendix

Table 4: AGAR relative to the closest prior systems. The pattern is the same in each row: prior work fixes a rule that our formalization turns into a component optimized against

J

RL tool	Rule replaced	Module	What changed
Credit assignment	Success never attributed	$M_{1}$	Textual attribution along genealogy, not numerical backup along chain
Value estimation	Must evaluate to rank	$M_{2}$	Pre-evaluation ranking ; scalar $V$ estimated, not learned
Adaptive exploration	Fixed temperature	$M_{3}$	Discrete explore/exploit decision + parent choice
Entropy regularization	Island diversity	$M_{3}$ (floor)	Explicit $\lambda H(\pi)$ in Eq. equation 2
Experience replay	Population is memory	$M_{4}$	Two tiers: durable abstract rules; per-direction path detail
Policy improvement	Hand-tuned hyperparams	Meta: TextGrad	Text-space improvement operator (§ 4 )

Appendix

Table 5: The transfer. Each RL tool keeps its function but changes its form to work without an empirical backup (column 4 is the honest column).

Explore similar work

Combining LLMs and Genetic Search for ARC-AGI-2
Sep 23, 2026Val DyachenkoLarge Language Model-Guided Optimization Genetic Programming
RLDISCOVER: LLM-driven co-evolution of reinforcement learning algorithms
Oct 6, 2026Haoran Li, Zengle Ge, Xiaomin Yuan +14
University of the Chinese Academy of Sciences · Baidu · Tsinghua University +4
EvoTrainer: Co-Evolving LLM Policies and Training Harnesses for Autonomous Agentic Reinforcement Learning
Jun 2, 2026Guhong Chen, Yingcheng Shi, Yongbin Li +6RL for Code Generation Agentic RL
1Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences · 2Tongyi Lab , Alibaba Group · 3Alibaba Group +1

Sep 23, 2026, cs.NEJ/K move · Enter open · S save

Combining LLMs and Genetic Search for ARC-AGI-2

Val Dyachenko

Large Language Model-Guided Optimization Genetic Programming LLM-Based Program Synthesis ARC-AGI

Open paper AskPDF arXiv

LLMs can generate programs for ARC-AGI-2 tasks, but the provided compute only allows a small number of attempts to generate, debug and validate solutions. Genetic algorithms can search and test many more programs, but random search rarely starts in a useful neighborhood of the solution space. We combine the two methods through a compact domain specific language (DSL). First, a quantized Qwen3.5-4B LLM generates an initial set of programs for each ARCAGI-2 task. Then, we use those programs to seed an initial population of starting programs, and use genetic algorithms to evolve these programs towards a solution to the given task. The DSL is designed such that every mutated program remains valid and can be executed. The initial programs proposed by the LLM solve 2 (3.3%) of the first 60 tasks of the ARC-2 public evaluation set. The genetic algorithm solves an additional 4, giving 6 correct test outputs in total (10.0%). If we try using evolving solutions without this LLM seeding, we do not arrive at any solutions at all. The results show that genetic search can improve programs generated by LLMs and produce additional correct solutions.

Abstract

Explore similar work

Combining LLMs and Genetic Search for ARC-AGI-2

RLDISCOVER: LLM-driven co-evolution of reinforcement learning algorithms

EvoTrainer: Co-Evolving LLM Policies and Training Harnesses for Autonomous Agentic Reinforcement Learning