Self-Evaluating Recursive Agents

TianYi Lyu; Xiaozhe Li; Yang Li; Yongkang Chen; Kefei Tian; Junbo Niu; Zican Hu; Hongbo Liu

cs.AIOct 4, 2026

Self-Evaluating Recursive Agents

Authors: TianYi Lyu, Xiaozhe Li, Yang Li, Yongkang Chen, Kefei Tian, Junbo Niu, Zican Hu, Hongbo Liu,

Organizations: Tongji University · Independent · Shanghai Artificial Intelligence Laboratory · Shanghai Jiaotong University ·

Abstract

Recursive language-model agents decompose tasks and delegate subtasks to child instances of the same policy, forming a tree of work. Training them, however, is hard: the final outcome is verifiable, but the self-invented intermediate subtasks are numerous and carry no ground truth. Existing methods score each node with a verifier or judge, which is costly at scale and blind to decomposition quality. We argue that a recursive agent must learn three coupled capabilities within one set of weights: decomposing problems into subtasks, solving them, and evaluating the outcomes, each requiring its own training signal. SERA (Self-Evaluating Recursive Agents) turns evaluation into a learned capability of the policy itself. Before delegating, the parent writes a rubric of weighted success criteria for each child subtask; a ranking objective against verified outcomes then trains rubric generation so that the criteria track genuine subtask success. In addition, a complementary leaf-coverage signal provides direct credit for task decomposition. Our central finding is that training the policy to generate aligned rubrics is what drives the gains: because the same weights both evaluate and execute, learning to judge subtasks sharpens the agent's ability to solve them. Notably, external supervision is also reduced: the judge is consulted only to train the rubric generator, while solving is trained against the agent's own rubric scores, which outperform direct use of the judge. Beyond training, the learned rubric doubles as an inference-time selector for tree search. On TextCraft-Synth and TextWorld-Sync, SERA improves over strong recursive-agent baselines by 5.38 and 13.14 points on average, and rubric-guided tree search at inference adds a further 2.43 points on TextWorld-Sync.

Figures & tables

Figure 1: Recursive Agent Optimization with rubric-based trajectory scoring. A shared-policy root agent delegates subtasks recursively; each completed SubAgent trajectory can receive a Rubric Reward together with the Program or LLM Judge reward.

Single-Agent
Method	TextCraft					TextWorld
Method	Easy	Medium	Hard	Extreme	Avg.	Easy	Medium	Hard	Extreme	Avg.
Qwen3-4B-Instruct	79.37 $\pm$ 0.79	13.77 $\pm$ 1.78	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	23.10 $\pm$ 0.42	26.57 $\pm$ 0.29	25.43 $\pm$ 1.12	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	13.00 $\pm$ 0.29
CISPO	94.56 $\pm$ 0.30	32.86 $\pm$ 0.62	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	33.07 $\pm$ 0.22	99.14 $\pm$ 0.00	56.29 $\pm$ 1.41	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	38.86 $\pm$ 0.35
GRPO	90.48 $\pm$ 0.64	23.47 $\pm$ 0.93	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	28.96 $\pm$ 0.35	99.14 $\pm$ 0.00	58.00 $\pm$ 2.68	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	39.29 $\pm$ 0.67
Multi-Agent

Table 1: Main results on TextCraft-Synth and TextWorld-Sync, grouped into single- and multi-agent methods. Success rates (%) are per difficulty level; the shaded Avg. column is the task-count-weighted mean over the four levels, averaged over 3 seeds (

\pm

std). Bold / underline : best/second-best per column. D = Decomposition reward, RT = Rubric Training.

Method	TextCraft	TextWorld
Method	Verifier (K)	Judge Calls (K)	Input (M)	Output (M)
RAO	550.94	147.80	633.80	16.13
RAO + D	381.65	84.22	371.20	9.10
RAO + RT	769.02	251.46	847.18	27.07
SERA w/o D & RT	20.24	0.00	0.00	0.00
SERA w/o D	366.52	43.70	136.35	5.34

Table 2: External-supervision cost accumulated over training. On TextCraft-Synth, subtask outcomes come from a free program verifier, so we report only its call count; on TextWorld-Sync, from an external LLM judge, so we also report input/output token usage. Calls in thousands (K), tokens in millions (M).

Training-free rubric generation
Generator	Scorer	Training	Easy	Medium	Hard	Extreme	Avg.
Policy	Policy	–	98.87 $\pm$ 1.04	96.87 $\pm$ 0.27	73.28 $\pm$ 1.53	3.92 $\pm$ 1.70	72.26 $\pm$ 0.18
Kimi	Policy	–	98.87 $\pm$ 1.04	97.97 $\pm$ 0.27	68.38 $\pm$ 3.21	3.19 $\pm$ 1.12	71.41 $\pm$ 0.37
Kimi	Kimi	–	97.73 $\pm$ 0.39	97.34 $\pm$ 1.51	77.45 $\pm$ 1.70	4.17 $\pm$ 1.70	73.10 $\pm$ 1.11
Policy (global)	Policy	–	99.09 $\pm$ 1.04	91.55 $\pm$ 2.82	62.01 $\pm$ 2.58	2.45 $\pm$ 0.42	67.77 $\pm$ 1.14
Trained rubric generation

Table 3: Ablation of rubric design choices on TextCraft-Synth. All rows use rubric scores as the execution reward and differ only in three axes: the Generator that writes the rubric (the SERA Policy , the external frontier Kimi judge, or a single global policy rubric reused across subtasks—otherwise per-subtask), the Scorer that applies it, and the Training of rubric generation (“–” none; Rank our verified-outcome ranking objective; Rank+Disc. adds the label-free discriminativeness reward of Ding et al. [5] ). Success rates (%) by difficulty with overall average, averaged over 3 seeds. Bold / underline : best/second-best per column.

Qwen3-4B-Instruct (no SERA training)
Selector	Easy	Medium	Hard	Extreme	Avg.
Policy judge ( $N{=}2$ )	54.67 $\pm$ 1.67	11.62 $\pm$ 4.06	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	16.57 $\pm$ 1.42
Kimi judge ( $N{=}2$ )	56.95 $\pm$ 2.31	15.05 $\pm$ 1.47	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	18.00 $\pm$ 0.93
No selection ( $N{=}1$ )	54.19 $\pm$ 0.59	12.95 $\pm$ 0.33	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	16.79 $\pm$ 0.21
SERA -trained policy
Policy judge ( $N{=}2$ )	99.43 $\pm$ 0.49	85.90 $\pm$ 1.15	55.71 $\pm$ 1.51	28.95 $\pm$ 0.33	67.50 $\pm$ 0.54

Table 4: Test-time scaling by bottom-up rubric-guided node selection on TextWorld-Sync, comparing Qwen3-4B-Instruct (no SERA training) with the SERA -trained policy. At each node we sample

N

candidate resolutions and keep the one scored highest by the rubric, applied either by the policy itself ( Policy judge ) or by an external frontier model ( Kimi judge );

N{=}1

is a single rollout without selection. Success rates (%) by difficulty with overall average; mean

\pm

std over three runs. Bold / underline : best/second-best per column.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Recursive execution and trajectory scoring with a shared policy. Parents delegate subtasks to child agents and commit rubrics before child execution. The scoring sources shown have different roles across methods: external outcomes directly reward execution in RAO, whereas policy-generated rubric scores reward subtask execution in SERA. SERA uses external subtask labels to train rubric generation through a separate ranking objective.

Setting	TextCraft-Synth	TextWorld-Sync
Hardware	2 $\times$ 8 H200 GPUs
Batch size / group size	8 / 8 root tasks
Root / SubAgent steps	20 / 20
Maximum recursion depth	3
Training temperature	1.0
Optimizer	Adam, $\mathrm{lr}=3\times 10^{-6}$

Appendix

Table 5: SERA training and evaluation settings. Values shown as ranges are due to small entrance-specific prompt/completion budget differences within the same benchmark.

Method	Subtask execution reward	Update ratio	External subtask labels used for
RAO	Binary outcome	$1:0:0$	Execution rewards
RAO + D	Binary outcome	$12:4:0$	Execution rewards
RAO + RT	Binary outcome	$16:0:2$	Execution rewards and Rubric training
SERA w/o D & RT	Policy rubric score	$1:0:0$	None
SERA w/o D	Policy rubric score	$16:0:2$	Rubric training
SERA	Policy rubric score	$16:2:2$	Rubric training

Appendix

Table 6: Subtask execution rewards, alternating update ratios, and uses of external supervision. D denotes decomposition training; RT denotes rubric-generation training. Ratios follow execution:D:RT, with one objective active per update. External subtask labels come from the program verifier on TextCraft-Synth and the LLM judge on TextWorld-Sync.

Single-Agent
Method	TextCraft	TextWorld
CISPO	29h 06m	7h 43m
GRPO	28h 17m	8h 06m
Multi-Agent
RAO	29h 36m	13h 08m
RAO + D	24h 57m	11h 06m

Appendix

Table 7: Training wall-clock time to the evaluated checkpoint on 2

\times

8 H200 GPUs, under the shared settings of Table 5 . Times are implementation- and hardware-dependent and are meaningful only as relative comparisons within a benchmark. Prompting-only baselines involve no training and are omitted. D = Decomposition reward, RT = Rubric Training.

Task family	Structure and coordination requirement
Fork–join	Independent dish branches converge on shared preparation and consumption, requiring their results to be coordinated.
Critical path	One branch has a longer workload; launching it early reduces delays before the branches can join.
Load balanced	Branch workloads differ, requiring work to be distributed across agents.
Resource constrained	Inventory capacity, available tools, or a shared step budget limit concurrent work.
Dependency gate	A branch can proceed only after a prerequisite, such as opening a door, has been satisfied.
Conflict	Branches compete for a unique shared tool, such as a knife or stove, requiring coordinated access.

Appendix

Table 8: Coordination structures in TextWorld-Sync. The seven task families vary branch dependencies, workload allocation, resource constraints, and recursion. Every family uses a shared world and requires completion of all dishes for root-task success.

LLM Agent Training

Large language model agent training teaches models to plan, use tools, and learn from multi-step interaction with environments.

See all 586 papers

Recursive Agent Optimization
May 7, 2026Apurva Gandhi, Satyaki Chakraborty, Xiangjun Wang +2Agentic RL Inference-Time Scaling
Carnegie Mellon University · Amazon AGI Labs
Recursive Agent Harnesses
Jun 11, 2026Elias Lumer, Sahil Sen, Kevin Paul +1Tool-Augmented Language Model Agents LLM Agent Orchestration
PricewaterhouseCoopers, U.S.
Drafting Agents, Not Just Tokens: Speculative Recursive Self-Improvement for Agentic Systems
Oct 12, 2026Xin Xu, Ke Cheng, Hao Wang +11LLM Agent Self-Improvement Recursive Self-Improvement
Tencent AMS, Beijing, China · State Key Laboratory of General Artificial Intelligence, School of Intelligence Science and Technology, Peking University, Beijing, China · CCSE lab, Beihang University. +3

May 7, 2026J/K move · Enter open · S save

Recursive Agent Optimization

Apurva Gandhi, Satyaki Chakraborty, Xiangjun Wang, Aviral Kumar+1

Carnegie Mellon University · Amazon AGI Labs

Agentic RL Inference-Time Scaling LLM Agent Training

Open paper AskPDF arXiv

We introduce Recursive Agent Optimization (RAO), a reinforcement learning approach for training recursive agents: agents that can spawn and delegate sub-tasks to new instantiations of themselves recursively. Recursive agents implement an inference-time scaling algorithm that naturally allows agents to scale to longer contexts and generalize to more difficult problems via divide-and-conquer. RAO provides a method to train models to best take advantage of such recursive inference, teaching agents when and how to delegate and communicate. We find that recursive agents trained in this way enjoy better training efficiency, can scale to tasks that go beyond the model's context window, generalize to tasks much harder than the ones the agent was trained on, and can enjoy reduced wall-clock time compared to single-agent systems.

Abstract

LLM Agent Training

Explore similar work

Recursive Agent Optimization

Recursive Agent Harnesses

Drafting Agents, Not Just Tokens: Speculative Recursive Self-Improvement for Agentic Systems