Recursive Self-Evolving Agents via Held-Out Selection
Michael Nguyen, Quoc Nguyen, Paul Vuong · 2026
Read Recursive Self-Evolving Agents via Held-Out Selection by Michael Nguyen, Quoc Nguyen, Paul Vuong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28374.txt.
Introduction
Michael Nguyen, Quoc Nguyen, and Paul Vuong study language-model agents that improve themselves by rewriting their own playbooks, no retraining required. Such agents evolve natural-language artifacts, reflections, workflows, or cheat sheets, and glowing reports usually come from the one benchmark where the trick happened to shine.
Nguyen and colleagues run an apples-to-apples comparison across four benchmarks and six established baselines on one shared model. Their RSEA agent rewrites a three-layer state of strategy, skills, and procedures, but commits a rewrite only if it avoids regression on held-out tasks. Nothing won everywhere. Ungated rivals swung wildly, near-best on one benchmark and collapsing on another. Removing RSEA's held-out gate caused severe overfitting. Reliability, they argue, comes from the selection gate, not the artifact.
Catalog record
| CREATOR | Michael Nguyen, Quoc Nguyen, Paul Vuong |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28374
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Recursive Self-Evolving Agents via Held-Out Selection Michael Nguyen, Quoc Nguyen, Paul Vuong Abstract LLM agents are increasingly improved without weight updates, by evolving a natural-language artifact – reflections, workflows, playbooks, cheatsheets, or optimized prompts – that conditions a frozen policy. Such methods are typically reported as wins on the single benchmark where they help. We study them apples-to-apples and surface a sharper picture. We introduce RSEA (Recursive Self-Evolving Agent), which carries a compact three-layer natural-language state – an imperative strategy , reusable skills , and a procedural playbook – and across generations rewrites all three layers from its own trajectories, committing a candidate only if it does not regress on a disjoint held-out split (a strict keep-better gate). Across four diverse benchmarks (ALFWorld, GAIA, τ \tau -bench, WebShop) and six faithful baselines (ReAct, Reflexion, GEPA, AWM, ACE, Dynamic Cheatsheet), all on one shared local backbone, we find: (i) no artifact universally wins – RSEA is the strongest single-pass method on ALFWorld ( 69.3 % 69.3\% vs. ReAct 64.6 % 64.6\% , McNemar p = 0.015 p{=}0.015 ; 79.4 % 79.4\% with retry, best overall), while concrete-workflow induction (AWM) is best on the strong-backbone tool-use tasks; (ii) unguarded context evolution is high-variance and unsafe – Dynamic Cheatsheet, which curates context online with no held-out gate, is near-best on ALFWorld ( 70.7 % 70.7\% ) yet collapses on WebShop (score 0.14 0.14 vs. ReAct 0.43 0.43 ); and (iii) RSEA’s strict held-out selection is what makes recursive self-evolution monotone-safe : it never significantly underperforms the base agent on any benchmark, falling back to vanilla ReAct when evolved context would hurt. Controlled ablations show that every layer of the evolved state helps and that removing held-out selection causes severe overfitting (a perfect in-sample score but a 33 33 -point drop to test). We argue the reliability of context evolution comes less from the artifact and more from the selection gate , and release the full harness, the six baseline re-implementations, and pre-registered manifests. 1 Introduction A central paradigm for building self-improving LLM agents adapts the context rather than the weights: the policy is frozen and an evolving natural-language artifact – accumulated reflections, induced workflows, curated playbooks, online cheatsheets, or optimized system prompts – is injected at inference. Context adaptation is attractive for concrete reasons: it is interpretable and auditable, integrates new knowledge at runtime, transfers across model versions, and – with long-context inference and KV-cache reuse – is increasingly cheap to serve. Despite rapid progress, these methods are almost always evaluated in isolation : a single benchmark, weak or non-matched baselines, and a backbone or decoding budget that varies between methods. This makes their relative merits and, crucially, their failure modes hard to read. When we re-run six representative methods on one shared backbone across four diverse agent benchmarks, two uncomfortable facts emerge. First, which artifact helps is benchmark-dependent: a method that tops one benchmark is middling or harmful on another. Second, and more importantly, evolving context is not a free lunch. We name the failure mode context distraction : an injected artifact that degrades an otherwise-capable base policy. Context distraction is not hypothetical – in our study an unguarded online method (Dynamic Cheatsheet) goes from near-best on ALFWorld ( 70.7\% ) to a WebShop score of 0.136 versus the ReAct baseline’s 0.429 , a catastrophic regression caused entirely by the context it added. We argue that the reliability of context evolution comes less from the artifact being evolved and more from the selection gate that decides whether to commit it. An evolution loop that commits whatever it produces inherits the variance of its own rewrites; one that commits a change only when it improves held-out performance cannot do worse than not evolving at all. We make this gate the design center of our method rather than an afterthought. Concretely, we present RSEA (Recursive Self-Evolving Agent). RSEA carries a compact three-layer natural-language state – strategy (an imperative preamble), skills (reusable sub-routines), and playbook (procedures distilled from successes) – and across generations (i) rolls the current state out on a small evolve pool, (ii) rewrites all three layers from the resulting trajectories, and (iii) commits the candidate only if it does not regress on a disjoint validation split, updating the frozen best state only on a strict improvement. Only the frozen best state is run on a held-out test split, so there is no leakage. RSEA {}_{\text{R}} injects this frozen prior into a per-task retry loop. Contributions. (1) A formulation of cross-task NL self-evolution centered on a strict held-out keep-better gate that makes the operation monotone-safe (§ 4 ). (2) A faithful, single-backbone re-implementation of six classic and recent baselines on a shared harness (§ 5 ). (3) A four-benchmark study with multi-seed statistics and paired tests, yielding an honest scope condition rather than a universal-win claim (§ 6 – 7 ). (4) Controlled ablations that isolate the contribution of each state layer and quantify the cost of removing held-out selection (§ 8 ). Key findings. (a) On ALFWorld (134 tasks \times 5 seeds, 7B) the single-pass evolved prior significantly beats ReAct, GEPA, and AWM, and RSEA {}_{\text{R}} is best overall ( 79.4\% ). (b) On the strong-backbone tool-use benchmarks no NL artifact dominates; RSEA is statistically tied with ReAct (and never significantly worse), while AWM’s concrete workflows give the only consistent small lift. (c) Methods without a held-out gate are high-variance and can catastrophically regress; RSEA’s strict gate converts “context evolution” from a coin-flip into a monotone-safe operation. (d) Ablations show every layer of the evolved state helps (the layers overlap rather than being strictly complementary) and that removing held-out selection overfits the evolve pool ( 100\% in-sample, a 33 -point drop to test). Figure 1: No context-evolution artifact universally wins, and unguarded evolution is unsafe. Single-pass methods across four benchmarks on one shared backbone (ALFWorld 7B; GAIA/ \tau -bench/WebShop 30B). RSEA (red) is the strongest single-pass method on ALFWorld and never significantly underperforms ReAct (grey) elsewhere; AWM is best on the tool-use tasks; and Dynamic Cheatsheet – which curates context online with no held-out gate – is near-best on ALFWorld yet collapses on WebShop (0.14 vs. ReAct 0.43). RSEA’s strict held-out gate is what makes evolution monotone-safe. 2 Related Work LLM agents that reason and act. A now-standard recipe interleaves free-form reasoning with tool/environment actions: ReAct ( 58 ) couples chain-of-thought with acting, elaborated with deliberate search ( 57 ) , self-critique and revision ( 26 ) , learned tool use ( 34 ) , and grounded planning in embodied or open-ended worlds ( 9 ; 42 ) . Recent work strengthens the reasoning substrate – multi-perspective, semiotically grounded logical reasoning ( 71 ) , “system-2” vision-language-action policies ( 37 ; 4 ) , and spatio-temporal chains of thought for control ( 60 ) – while cognitive-architecture and survey treatments organize the pieces into memory, planning, and action modules ( 39 ; 43 ; 30 ; 52 ) . RSEA keeps this loop unchanged and intervenes only through an evolved natural-language state, isolating the contribution of context from scaffold. Tool-use agents and tool learning. A large body studies how agents select and compose tools ( 33 ) : mastering tools via self-driven