PaperlayerView exact revision on arXiv

Source-linked AI summary

Recursive Self-Evolving Agents via Held-Out Selection

Michael Nguyen, Quoc Nguyen, Paul Vuong

arXiv:2606.28374v1cs.AI

TL;DR

Existing context-evolution methods lack apples-to-apples evidence across benchmarks, making their relative merits and failure modes unclear. RSEA evolves a three-layer natural-language state for a frozen agent and commits candidates only through strict held-out selection. Across four benchmarks, no artifact wins universally, while the gate prevents significant regressions and enables strong gains where procedural strategy is the bottleneck.

  • Problem

    Existing context-evolution methods are usually evaluated on isolated benchmarks with unmatched baselines or backbones, obscuring relative merits and failure modes.

  • Method

    RSEA rewrites a strategy, reusable skills, and procedural playbook from trajectories, committing candidates only when disjoint held-out performance does not regress.

  • Results

    Across four benchmarks, no artifact universally wins; RSEA reaches 79.4% with retry on ALFWorld and never significantly regresses against the base agent, while ungated evolution can collapse.

  • Takeaways & Limitations

    Held-out selection, rather than any universally superior artifact, is the central reliability mechanism for recursive context evolution.

  • Takeaways & Limitations

    The study is limited to weight-frozen natural-language states, with modest transfer evaluations and a strict gate that guarantees safety on held-out validation rather than every small test draw.

Abstract

from arXiv · show

LLM agents are increasingly improved without weight updates by evolving a natural-language artifact, such as 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, a Recursive Self-Evolving Agent that carries a compact three-layer natural-language state: an imperative strategy, reusable skills, and a procedural playbook. Across generations, RSEA rewrites all three layers from its own trajectories and commits a candidate only if it does not regress on a disjoint held-out split, using a strict keep-better gate. Across four diverse benchmarks, ALFWorld, GAIA, (\tau)-bench, and WebShop, and six faithful baselines, ReAct, Reflexion, GEPA, AWM, ACE, and Dynamic Cheatsheet, all evaluated on one shared local backbone, we find three main results. First, no artifact universally wins. RSEA is the strongest single-pass method on ALFWorld, reaching 69.3% compared with 64.6% for ReAct (McNemar (p=0.015)), and reaches 79.4% with retry, the best overall result. However, concrete-workflow induction, represented by AWM, is best on the strong-backbone tool-use tasks. Second, unguarded context evolution is high-variance and unsafe. Dynamic Cheatsheet, which curates context online without a held-out gate, is near-best on ALFWorld at 70.7%, yet collapses on WebShop, with a score of 0.14 compared with 0.43 for ReAct. Third, RSEA's strict held-out selection is what makes recursive self-evolution monotone-safe: it never significantly underperforms the base agent on any benchmark and falls back to vanilla ReAct when evolved context would hurt.

1 Introduction

Context-evolution methods improve frozen LLM agents, but their benefits and failures are benchmark-dependent. RSEA addresses this variability with a strict held-out selection gate over a structured evolving state.

  • Across four benchmarks, no context artifact universally wins, motivating apples-to-apples evaluation on one shared backbone.The study compares six representative methods under matched evaluation conditions.
  • 70.7% on ALFWorld versus 0.136 on WebShop exposes context distraction in ungated Dynamic Cheatsheet, compared with ReAct scores of 0.429 on WebShop.The online method is near-best on ALFWorld yet suffers a catastrophic WebShop regression.
  • RSEA centers reliability on a gate that commits rewritten context only when it does not regress on disjoint held-out data.The method carries strategy, reusable skills, and a procedural playbook, rewriting all three from trajectories.
  • 79.4% makes RSEAR the best overall ALFWorld result, while RSEA’s single-pass evolved prior significantly beats ReAct, GEPA, and AWM.On strong-backbone tool-use benchmarks, no artifact dominates and AWM provides the only consistent small lift.
  • Removing held-out selection overfits the evolve pool, reaching 100% in-sample performance but dropping 33 points on test.The ablation shows the cost of eliminating the selection safeguard.

2 Related Work

Related work spans reasoning agents, tool learning, prompt optimization, self-evolution, reinforcement learning, memory, and diverse benchmarks. RSEA differs by keeping the policy and interface fixed while making structured natural-language state and held-out selection central.

  • LLM agents that reason and act: RSEA keeps the reasoning-and-acting loop unchanged and isolates the contribution of evolved natural-language context from the agent scaffold.It intervenes through an evolved state rather than changing the underlying action loop.
  • Tool-use agents and tool learning: Unlike tool-evolution methods, RSEA evolves natural-language strategy over a fixed tool interface, clarifying when strategy adds little beyond detailed APIs.Its τ-bench and WebShop results frame this complementarity.
  • Prompt and context optimization: Prompt optimizers commonly use a single flat artifact, whereas RSEA argues that held-out selection governs whether context evolution helps or hurts.The comparison shifts attention from optimizer sophistication to commitment policy.
  • Self-evolving and self-improving agents: RSEA shares self-evolution goals with weight- and structure-changing approaches but is deliberately weight-frozen and centers a strict held-out gate.The gate is identified as the decisive ingredient for safety.
  • Reinforcement learning for LLM agents: Unlike reinforcement-learning approaches, RSEA avoids RL’s cost and instability while exploiting execution feedback through rewriting and selection.
  • Agent memory, experiential learning, and overfitting: RSEA’s selection-first framing targets both artifact collapse and overfitting by preventing evolved context from being committed without held-out evidence.
  • Context adaptation: Context-adaptation methods differ in artifact form, update operator, and selection rule, with selection identified as the main reliability boundary.
  • Benchmarks, multi-agent systems, and the broader landscape: The deliberately diverse benchmark slate is intended to expose benchmark dependence that single-benchmark studies miss.

3 Background and Motivation

Context adaptation injects an evolving artifact into a frozen policy, but existing methods often use single-form artifacts and unguided commitment. RSEA targets both limitations with a three-layer state and a strict held-out gate.

  • Context adaptation seeks an artifact c that improves a frozen policy without changing its parameters, differing in form, update operator, and selection rule.The selection rule is presented as the key reliability distinction.
  • Existing methods conflate high-level strategy, reusable sub-routines, and concrete procedures in single-form artifacts, while unguided commitment can distract the base policy.RSEA responds with a three-layer form and strict held-out selection.

4 Method: RSEA

RSEA evolves a compact strategy–skills–playbook state from execution trajectories while preserving a frozen best state through held-out keep-better selection. Retry adds within-task correction to the evolved prior.

  • Three-layer evolving state: RSEA’s state contains an imperative strategy, reusable skills, and ordered playbook procedures representing complementary kinds of knowledge.The state is rendered as a compact preamble injected before each task.
  • RSEA evolution: Each generation rolls out the current state on an evolve set, self-rewrites all three layers, evaluates the candidate on held-out validation, and returns the frozen best state.The algorithm uses a frozen policy and runs the returned state on held-out test data.
  • The self-rewrite operator: The rewrite operator derives transferable rules from successful and failed trajectories and may rewrite or drop layers to avoid unbounded context growth.It edits structured layers jointly rather than monotonically appending to a flat artifact.
  • Strict held-out keep-better selection: Held-out keep-better selection accepts non-regressing candidates for exploration but updates the frozen best state only on strict improvement, otherwise returning vanilla ReAct.This asymmetry permits lateral search while guaranteeing the returned validation state is not worse than the empty state.
  • RSEAR: evolution × retry: RSEAR combines the frozen evolved prior with a Reflexion-style retry loop, providing a good starting policy and within-task self-correction.The two components contribute near-independent gains.

5 Experimental Setup

The study compares RSEA and six context-evolution baselines under a shared evaluation harness across four agent benchmarks. RSEA injects a recursively evolved state into ReAct and uses held-out selection to control updates.

  • Experimental fairness: All methods use the same locally served backbone, decoding budget, rollout budget, and injection point for controlled comparison.Qwen2.5-7B is used on ALFWorld, while Qwen3-30B-A3B-Instruct is used on GAIA, τ-bench, and WebShop.
  • Benchmarks: The evaluation covers ALFWorld, GAIA, τ-bench, and WebShop with disjoint development or evolve, validation, and evaluation splits.For tool-use tasks, seed-shuffled test-pool slices are used because the official development split is saturated.
  • RSEA procedure: RSEA recursively rewrites a three-layer state from evolve-set trajectories and freezes it only after held-out validation improvement.The state is injected as a preamble into a standard ReAct loop.
  • Baselines and metrics: Baselines include ReAct, Reflexion, GEPA, AWM, ACE, and Dynamic Cheatsheet, with ALFWorld also reporting matched retry variants.Results use success rate for ALFWorld, GAIA, and τ-bench, and mean dense score for WebShop.

6 Results on ALFWorld: the evolved prior significantly helps

On ALFWorld, RSEA is the strongest single-pass context method, while adding retry produces the best overall result. Its gains align with the task families targeted by the evolved skills and playbook.

  • Overall results: 79.4% is RSEAR’s best overall ALFWorld success, above ReAct, single-pass RSEA, and every no-evolution baseline.RSEAR also trends above the strongest retry baselines Reflexion at 76.4%, ACER at 76.7%, and GEPAR at 75.8%.
  • Overall results: 69.3% makes single-pass RSEA significantly better than ReAct at 64.6% on ALFWorld.RSEA also exceeds GEPA at 63.9% and AWM at 65.4%, while tying ACE and Dynamic Cheatsheet.
  • Task-family analysis: Examine-task success rises from 6.7% to 26.7% with RSEA and to 44.4% with retry.The evolved skill directly addresses the base agent’s dominant failure, while pick_two and pick_and_place gain 7–9 points from playbook procedures.
  • Task-family analysis: RSEA’s only reported regression is a mild 6.5-point decrease on clean tasks, which retry recovers.The task-family correspondence connects human-readable evolved content to the observed gains.

7 Transfer to GAIA, τ-bench, and WebShop

Across GAIA, τ-bench, and WebShop, no natural-language artifact universally dominates. AWM is marginally best on the strong-backbone tool-use tasks, while RSEA’s held-out gate prevents regressions by falling back toward ReAct.

  • Cross-benchmark comparison: AWM is marginally best on the strong-backbone tool-use benchmarks, reaching 51.7% on τ-bench and 0.460 on WebShop.The results suggest concrete procedures offer more than abstract policies when domain documentation already encodes much of the needed knowledge.
  • Cross-benchmark comparison: RSEA never significantly regresses against ReAct and is statistically tied with it on τ-bench, WebShop, and GAIA.On WebShop, every evolved candidate hurt held-out validation, so RSEA retained an empty state and scored 0.437 versus ReAct’s 0.429.
  • Selection and variance: Dynamic Cheatsheet reaches 70.7% on ALFWorld but falls to 0.136 on WebShop versus ReAct’s 0.429 and 36.7% on τ-bench.Its unguarded online curation is therefore high-reward when context helps and catastrophic when it does not.
  • Selection and variance: Held-out validation improves across generations when signal exists, while the strict gate rejects regressive candidates when it does not.τ-bench validation rises from 0.20 to 0.36, whereas WebShop candidates are rejected.

8 Ablations

The ablations show that RSEA’s three-layer state contributes overlapping procedural knowledge, while held-out selection prevents overfitting and bounds regressions.

  • Layer ablation: Every tested state-layer subset improved over ReAct’s 64.2%, but skills and playbook produced the largest individual gains at 69.8% each.The full state reached 68.5%, indicating that the layers overlap rather than provide strictly additive signals.
  • Selection ablation: Across the benchmark comparison, RSEA is significantly best on ALFWorld and never regresses elsewhere, whereas ungated Dynamic Cheatsheet is high-variance.The table caption identifies RSEA’s ALFWorld significance and Dynamic Cheatsheet’s best-on-ALFWorld, worst-on-WebShop/τ-bench pattern.
  • Selection ablation: 100% in-sample selection fell to 66.7% on test without held-out selection, versus 67.3% for held-out RSEA and 63.6% for ReAct.The same ablation shows a 33-point train–test gap, while transfer results show catastrophic WebShop regression without a gate.
  • Selection ablation: The strict gate accepts candidates that do not regress on held-out validation while freezing the best state only after strict improvement.This design allows lateral exploration but falls back to the simpler state when improvement is unsupported.

9 Compute and Cost

RSEA adds bounded inference context and O(G) meta-LLM calls, with its strict gate ensuring this overhead is spent only to match or beat ReAct.

  • 9 Compute and Cost: RSEA’s evolution uses O(G) meta-LLM calls, with one rewrite per generation; τ-bench used 190 meta and selection calls in total.At inference, the rendered preamble is bounded to at most a few hundred tokens, unlike online methods whose context can grow unboundedly.
  • 9 Compute and Cost: Layer ablation evaluates subsets on the ALFWorld test set with the identical ReAct loop and temp-0.6 multi-seed decoding.The selection ablation uses the same ALFWorld setting to isolate the selection rule.
  • 9 Compute and Cost: The strict gate means RSEA’s additional overhead is spent to match or beat ReAct, never to underperform it.This is the favorable risk profile that the other methods lack.

10 Discussion and Limitations

RSEA’s benefits depend on the agent bottleneck: procedural strategy favors evolved language state, while strong tool-use or retrieval settings offer less room for improvement. The study also limits its claims to weight-frozen natural-language evolution and modest, noisy evaluation settings.

  • 10 Discussion and Limitations: Evolved natural-language state helps most when procedural strategy bottlenecks text-action agents, and least when strong tool APIs or retrieval and grounding dominate.This scope condition is presented as a predictor of transfer to new agent settings.
  • 10 Discussion and Limitations: RSEA makes held-out checking strict and central, converting high-variance context evolution into a safer operation when unguarded commitment causes failures.The framing connects Dynamic Cheatsheet’s WebShop collapse to committing context without a held-out check.
  • 10 Discussion and Limitations: The evaluation uses one shuffled split seed and modest sizes, while live web retrieval in GAIA introduces run-to-run noise.The reported gap of at most one task flips sign across runs.
  • 10 Discussion and Limitations: The study covers weight-frozen natural-language states rather than code- or weight-updating self-improvement, and validation safety may not hold for every small test draw.The strict gate guarantees safety on held-out validation, not universally across test draws.
  • 11 Conclusion: Across the paper’s conclusion, no natural-language artifact universally wins, while RSEA gains where strategy is the bottleneck and avoids significant regressions elsewhere.The authors release the harness, baseline re-implementations, and manifests for faithful comparison.

A Evolved states (qualitative)

The evolved states expose the procedural knowledge RSEA adds: concrete action rules explain its ALFWorld gains, while already-satisfied tool policies explain neutrality on τ-bench.

  • A Evolved states (qualitative): The states are interpretable, allowing the paper to inspect why RSEA helps on ALFWorld but remains neutral on the strong tool-use backbone.This qualitative inspection complements the benchmark results.
  • A Evolved states (qualitative): ALFWorld’s evolved state encodes reusable rules for failed actions, object handling, examination, and pick-and-place procedures.These strategy, skill, and playbook elements directly target failure modes of the 7B ReAct agent and yield the significant gain.
  • A Evolved states (qualitative): τ-bench’s evolved state summarizes identity authentication, confirmation, order verification, and order-specific exchange policies already largely followed by the 30B agent.The held-out gain is therefore neutral, consistent with the paper’s scope condition.
  • B Reproducibility: All methods use one locally served backbone and decoding budget, with identical task and reflection LLMs.ALFWorld uses five seeds with paired McNemar tests, while transfer benchmarks use disjoint seed-shuffled splits and paired tests over tasks.
Loading 2606.28374v1…