ReGE: Stronger Agents through Experience Synthesis

AI summary

Overview

Research area: AI agents and agentic reinforcement-free improvement — specifically, how an agent can reuse the records of its own repeated attempts at an interactive task to do better on a fresh attempt. Technical level: Intermediate (readers should be comfortable with LLM agent loops, tool use, and benchmarking, but the core idea is conceptually simple). Scope: The paper introduces the ReGE framework, presents its main implementation ReGE-Syn (plus the variants ReGE-Sel and ReGE-A), and evaluates them on four agentic benchmarks with GPT and Claude model lines, with ablations on BrowseComp-Plus.

What This Paper Is About

When an agent attempts an interactive task repeatedly — running commands, querying databases, navigating a phone UI — each attempt produces useful residue: discovered facts, working commands, intermediate values, and failure lessons. These discoveries are spread unevenly across attempts, and the full records are long and of unknown correctness. ReGE asks how to compress that recorded experience into compact, self-contained guidance that a fresh run of the same base model can follow from the task's initial environment state. The goal is to raise task success without parameter updates, without a stronger teacher model, and without making guidance construction the dominant inference cost.

Key Contributions

1. Joint synthesis of execution experience (ReGE-Syn). A single "coach" call reads bounded execution records and available artifacts from multiple prior attempts together and produces one self-contained guide that connects concrete findings with proposed operations and relevant pitfalls.
2. Capability gains at low guidance-construction cost. Across four benchmarks, ReGE improves accuracy by an average of 9.9 percentage points for GPT and 8.8 percentage points for Claude over unguided execution, while on matched BrowseComp-Plus subsets cutting guidance-construction tokens by 98.2% (GPT) and 95.5% (Claude) relative to adapted AggAgent.
3. A cost-efficiency demonstration. With ReGE, the lower-priced gpt-5.6-luna reaches 67.4% average success on a matched task subset, comparable to the 67.0% of the higher-priced gpt-5.6-sol, at 28% of its cost including source-pool generation.
4. Diagnostic ablations on what makes experience useful. The paper isolates the value of process records versus final artifacts only, the effect of source-pool size and quality, and alternative guidance forms (selected trajectory, explanation-plus-answer, execution plan).

Main Findings

• Experience guidance beats unguided execution on every benchmark reported. GPT average success rises from 54.7% (Control) to 64.6% (ReGE); Claude rises from 58.5% to 67.3%. On Terminal-Bench 2.0 with GPT, success goes from 41.6% to 56.2%.
• Construction is cheap, execution dominates cost. On matched BrowseComp-Plus queries, ReGE-Syn uses 4.2k construction tokens versus 232.9k for AggAgent on GPT (98.2% saving) and 9.6k versus 211.7k on Claude (95.5% saving), with observed success (75.2% vs 75.3% on GPT; 86.2% vs 87.0% on Claude). Combined construction-plus-execution tokens fall 15.7% (GPT) and 35.4% (Claude) relative to AggAgent, counting input plus output and excluding source generation.
• Guidance can reduce student effort. For claude-sonnet-5, ReGE-Syn uses 0.86× the student output tokens and 0.88× the steps of Control on Terminal-Bench 2.0, and 0.70× output tokens and 0.50× steps on Spider2-Lite (SQL calls fall by 50%). On AndroidWorld the ratios are essentially flat (1.02× and 1.01×).
• Process records, not just final answers, carry the gain. Comparing final-artifact-only synthesis to full ReGE-Syn on Claude over 300 queries: success 85.0% vs 88.3%, and mean student steps 14.6 vs 9.1. Queries with exactly one submitted source answer (6.3% of queries) account for 90% of the net additional successes (47.4% → 94.7%). On queries solved only with full input (5.7% of queries), 94.1% of final-artifact-only runs exhaust the 40-step budget without submitting an answer. Even when all four sources submit answers, mean student steps fall from 8.9 to 4.8.
• More sources help, up to a point. With a coach but zero source attempts (closed-book), success is 75.7%, essentially the 74.7% of Control. One, two, and four sources give 84.3%, 86.3%, and 88.3%. The paper cautions that source coverage and input length increase together, so this is not a matched-inference-cost comparison.
• Mixed-quality pools give the largest gains. Across Terminal-Bench 2.0, Spider2-Lite, and AndroidWorld, mixed pools (some sources succeed, some fail) show gains of 13.0 to 21.6 percentage points; on BrowseComp-Plus the gains reach 48.0 points on GPT and 35.2 on Claude. When all sources fail, gains are small and inconsistent (GPT Terminal-Bench 0.0% → 9.4%; GPT Spider2-Lite remains 0.0% for both).
• Joint synthesis yields compact guidance. ReGE-Syn produces guidance of 5,063 characters versus 20,571 for Direct history and 19,590 for Independent summaries, at 88.3% success (vs 88.3% and 86.9%), with total tokens of 215.8k versus 268.9k and 316.5k — reductions of 19.8% and 31.8%.
• Alternative guidance forms are competitive. On 290 Claude queries, ReGE-A (explanation plus answer) reaches 90.7% success at 0.68× total tokens, and ReGE-Sel (one judge-selected trajectory) reaches 89.3% at 0.80× total tokens, against ReGE-Syn's 88.3%. ReGE-A does not win everywhere: on 100 BrowseComp-Plus queries with gpt-5.6-luna it solves 80% versus 82% for ReGE-Syn.
• Concrete guidance is verified and adapted, not copied. In the Terminal-Bench 2.0 db-wal-recovery case, a source attempt found the XOR decoding key 0x42 and another lost main.db-wal by opening the database before backing up; the student backed up files, verified the key, moved the main.db-shm cleanup earlier than the guide suggested, exported 11 ordered records to recovered.json, and passed all seven official tests. In AndroidWorld's BrowserMultiply, none of four Claude sources completed the task but two found the long-press → More options → Open with → Chrome route; the student used it, recorded 9, 10, 9, 5, 5, submitted 20,250, and succeeded in 19 steps within the same 22-step budget.
• A cheaper newer model is less accurate. ReGE exceeds gpt-6-luna by 18.1 points on average, though gpt-6-luna costs $0.009 per task versus $0.214 for ReGE including source-pool generation ($0.034 with an existing pool).

Methodology in Plain English

The setup has three stages, all run with the same base model and no weight updates.

First, source generation: the model attempts the same task four times, producing a "source pool" of trajectories (four attempts per task on all benchmarks). These attempts are rendered into text programmatically — reasoning or action narratives and commands in step order, followed by final artifact paths and contents — with fixed truncation (at most 120 rendered steps per source; reasoning truncated to 200 characters and commands to 160 characters per step; each artifact capped at 6,000 characters; if the combined serialization exceeds 350,000 characters, artifact bodies are dropped and paths retained). Raw per-step observations and benchmark correctness labels are withheld.

Second, guidance construction: a single "coach" call receives the task instruction and the whole rendered pool and is asked to write an executable step-by-step plan — numbered steps in execution order, critical facts (exact paths, values, commands, formats) placed at the steps where they matter, and pitfalls to avoid — that is self-contained, since the student never sees the attempts. If the evidence supports a final answer or artifact, the coach states it along with how to verify it.

Third, student execution: a fresh run starts from the task's initial environment state. Files and environment changes from the source attempts do not carry over, so the student must adopt, adjust, or skip the proposed operations based on its own current observations, and the benchmark grader scores the resulting state or submission.

Comparisons are made against one unguided execution (Control), an adapted Reflexion (up to three executions with label-free self-evaluation), adapted AggAgent (iterative tool-based inspection of source records, with its final response converted into guidance for a fresh student), Independent summaries (an agentic PDR adaptation that summarizes each trajectory separately and concatenates them), plus Self-Consistency voting and Best-of-N as references without student re-execution. Cost is counted as input plus output tokens after source generation unless stated otherwise.

Why This Matters

Research impact. The paper reframes multi-attempt aggregation for agents: rather than voting on answers or summarizing trajectories independently, it consolidates bounded execution records jointly into guidance for a re-execution in a reset environment — a setting where prior artifacts are not inherited. It also reports a cost-accounting discipline (construction tokens versus execution tokens, with and without source pools) that is often missing from agent-improvement work, and it isolates process information as the driver of gains rather than final answers alone.

Real-world applications.

• Agent swarms and parallel agent systems: cheaply consolidating the records of many parallel sub-agents working the same task into one guide for a fresh run.
• Software and systems operations: debugging, recovery, and configuration tasks where a prior attempt's discovered keys, paths, and ordering constraints (as in the database write-ahead-log recovery case) matter more than its final answer.
• Browser and GUI automation: tasks where a working navigation route is the reusable asset, even when no attempt finished the task.
• Cost-sensitive deployment: substituting a lower-priced model guided by its own attempts for a higher-priced model, at a fraction of the per-task cost.

Industry relevance. The headline economic result — a lower-priced model matching a higher-priced sibling at 28% of its cost including source-pool generation, and $0.034 per task when a pool already exists, close to the $0.041 of one unguided gpt-5.6-luna execution — is directly actionable for teams deciding whether to pay for a stronger model or to spend compute on repeated attempts plus a single synthesis call.

Future Directions

• Broader evaluation. The authors state that budget constraints limited evaluation to four benchmarks, with ablations on selected subsets, and call for broader task settings and repeated executions under aligned settings.
• Matched-cost scaling of source pools. The paper notes that source coverage and input length grow together when adding attempts, so whether gains hold at matched inference cost remains open; a six-source check on 100 Claude BrowseComp-Plus queries gave 81%, 82%, 85%, and 89% for one, two, four, and six sources (+4/−0 for six versus four, p = .125), which is suggestive but not conclusive.
• Choosing the guidance form automatically. ReGE-A beats ReGE-Syn on Claude BrowseComp-Plus but loses on GPT, so when to emit an execution plan versus an explanation-plus-answer is unresolved.
• Exploiting fully failed pools. Improvements when every source attempt fails are small and inconsistent (e.g., 0.0% → 9.4% on GPT Terminal-Bench 2.0, 0.0% on GPT Spider2-Lite), leaving room for methods that extract more from uniformly unsuccessful experience.

Target Audience

Researchers and engineers working on LLM agents, tool-use, and inference-time compute scaling will get the most from this paper, particularly those interested in multi-sample aggregation, agent memory, and cost-aware agent design. It is also useful for practitioners deciding between a stronger base model and a repeated-attempt-plus-synthesis pipeline, and for anyone building parallel or "swarm" agent systems that need to consolidate many recorded runs. Readers need only a working familiarity with agent loops and benchmark evaluation; the mathematical content is limited to notation for the coach and student policies.

Authors’ abstract

Repeated attempts at interactive tasks uncover facts, useful operations, and failures that can inform subsequent execution. We introduce ReGE, a framework for turning this recorded experience into guidance for a fresh attempt. Its main implementation, ReGE-Syn, uses a single coach call to jointly synthesize bounded execution records and available artifacts into self-contained guidance, connecting task-specific findings with proposed actions and relevant pitfalls. A student starts from the task's initial environment state and adapts this guidance to current observations. Source generation, synthesis, and student execution use the same base model, without parameter updates or a stronger teacher. Across four benchmarks, ReGE improves accuracy by an average of 9.9 percentage points for GPT and 8.8 percentage points for Claude compared with unguided execution. On matched BrowseComp-Plus subsets, ReGE-Syn reduces guidance-construction tokens by 98.2\% on GPT and 95.5\% on Claude relative to adapted AggAgent, with observed success. Combined construction and execution tokens decrease by 15.7\% and 35.4\%, respectively, counting input plus output and excluding source generation. BrowseComp-Plus ablations further associate access to process information with fewer student steps and show that joint synthesis produces substantially shorter guidance than Direct history or Independent summaries, with observed success. These results demonstrate how agents can use their own recorded experience to improve subsequent task completion, and suggest a low-cost way to consolidate the execution records of parallel agent systems such as agent swarms.