Recursive Agent Optimization
Apurva Gandhi, Satyaki Chakraborty, Xiangjun Wang, Aviral Kumar, Graham Neubig
cs.LG, cs.AI, cs.CL, cs.MA
2026-05-08
RAO trains agents with RL to spawn subtasks on copies of themselves. An 8K-context recursive agent lifts hard-task success from a single agent's 0% to 88% and reaches tasks beyond its context window.
A single agent on long-horizon tasks runs into three troubles: the history keeps growing, every step re-stuffs the whole history into the context (tokens balloon quadratically with steps), and it has to explore alone. The usual fix is to wrap the model in a multi-agent scaffold, but the model itself was never trained on when to split, how to split, or how to merge. CMU and Amazon AGI Labs' position: scaffolds should not merely be designed around models; models should be trained to use them.
A recursive agent is one that, at inference, calls a launchsubagent primitive and spawns a fresh instance of itself on a subtask, which can spawn again, forming an execution tree. Each sub-agent gets a clean context window, which expands the effective working memory. The hard part: a rollout is no longer a flat trajectory but a dynamically grown tree, credit assignment across it is hard, and the same policy at every node has to both solve and decompose.
At inference the recursive agent is a CodeAct-style Python REPL; the recursion primitive is an async function launchsubagent. Async means several subtasks can run concurrently, or sequentially when later subtasks depend on earlier ones; the return type is unrestricted, and the parent handles children through ordinary Python control flow. Recursion depth and per-instance steps are bounded.
For training, RAO gives every node a local reward: its own task success rate plus lambda times the mean success rate of its immediate children. Mean, not count, so the policy cannot farm the bonus by spawning relentlessly. lambda=0 reduces to pure local reward; use 0 when the policy already delegates enough at init, 0.4 (as in Oolong) when it needs a nudge. The success signal can be an exact verifier, an LLM judge, or root-task success as a proxy.
The objective sums over depth; for each root it samples G rollout trees, computes advantage with a leave-one-out baseline on root rewards (shared across all nodes in a tree), and applies depth-level inverse-frequency weighting so the mass of deep trajectories does not swamp the shallow ones. This is a GRPO-style leave-one-out baseline with a CISPO variant, async RL, staleness up to 3. The authors stress that recursive execution generates a self-induced curriculum: each level's subtasks tend to be simpler versions of the parent, so the training-efficiency gain is not only at inference.
TextCraft-Synth (synthetic Minecraft crafting, binned by depth):
| Setting | Method | Overall SR | Hard |
| 8K train, 8K eval | Single | 0.24 | 0% |
| 8K train, 8K eval | Recursive | 0.95 | 88% |
| 40K train, 256K eval | Single | 0.73 | 20% |
| 40K train, 256K eval | Recursive | 0.96 | 88% |
An 8K-trained recursive agent nearly matches the 40K-trained recursive model and takes hard-task success from a single agent's 0% to 88%. That is the beyond-the-context-window result.
Long-context Oolong-Real (30B model, 32K training): recursive averages 0.320 against a single agent's 0.203, leading in every context bucket; 0.320 is close to Claude-Sonnet-4, o3, and GPT-5-mini at 0.35 to 0.37 (numbers from another paper). DeepDive, 50 held-out deep-research tasks: 0.24 to 0.40.
Wall-clock is honest: speedup only when tasks parallelize. TextCraft has 83.9% concurrent delegations, and on hard tasks recursion is 2.5x faster than a single agent (despite 2.8x more steps). DeepDive is only 1.6% concurrent, heavily sequential, and 18x slower. Tokens flip: on TextCraft hard tasks recursion uses 1.2M versus a single agent's 8.6M (about 7x less) because the single agent's history balloons quadratically; on Oolong and DeepDive recursion uses 20 to 30x more tokens, because it does more real work and reaches harder problems.
Recursion is an inference-time scaling primitive: one model both solves and decides how to split, and depth adapts to difficulty (DeepDive uniquely solved tasks average depth 4, commonly solved 2.9). For engineers who want a small model to reach long-context or hard tasks, a 30B recursive agent approaching frontier long-context performance is attractive. It also hands the field a concrete RL recipe for recursive and multi-agent systems: local reward plus child-success mean plus depth weighting.
The authors concede: training is per-domain with no cross-domain transfer; tasks with heterogeneous subtasks (retrieval, verification, implementation, debugging) are untested; evaluation looks only at final success, not compute efficiency; heterogeneous recursion (a big model with small specialists) is untouched; and running full rollouts inside the RL loop is expensive, with surrogate sampling left open. Other gaps: