Self-Evaluating Recursive Agents

AI summary

Overview

Research area: Artificial Intelligence — reinforcement learning for recursive language-model agents (agents that decompose a task and delegate subtasks to child copies of the same policy).

Technical level: Advanced. The paper assumes familiarity with policy-gradient RL, advantage baselines, and multi-agent scaffolds.

Scope: One sentence — the paper introduces SERA, a training method that teaches a single shared policy to decompose tasks, solve subtasks, and score its own subtasks with self-generated rubrics, and evaluates it on TextCraft-Synth and TextWorld-Sync.

What This Paper Is About

Recursive agents split a hard task into subtasks and hand each one to a child instance of the same model, forming a tree of work. The final answer can be checked, but the intermediate subtasks the agent invents have no ground truth, so existing methods ask an external verifier or LLM judge to label every node — which is expensive, gives only coarse pass/fail credit, and says nothing about whether the agent picked the right subtasks. This paper's goal is to make evaluation a learned capability of the policy itself, so that judging and solving reinforce each other inside one set of weights.

Key Contributions

1. A three-capability framing of recursive-agent training: decomposing, solving, and evaluating subtasks all live in one shared policy, and each is shown to need its own training signal.

2. A learned self-evaluation mechanism. Before delegating, the parent writes a frozen, weighted rubric of success criteria for the child; rubric generation is trained with a margin-ranking loss that forces it to score verified successes above verified failures on the same subtask.

3. A leaf-coverage decomposition reward that credits a delegation by the fraction of the solved task's leaf-level work its subtree organizes, giving direct credit for the structure of the tree rather than only for execution.

4. Empirical results and a reusable inference-time selector on TextCraft-Synth and TextWorld-Sync, including use of the learned rubric to rank candidate node resolutions during bottom-up tree search.

Main Findings

• Best or second-best average on both benchmarks. SERA reaches 74.31% average on TextCraft-Synth (second, behind RAO + RT at 72.47%? — no, second overall) and 65.07% on TextWorld-Sync (first), improving over the RAO baseline by 5.38 and 13.14 points respectively.

• Delegation must be explicitly trained. The prompted multi-agent baseline beats its single-agent counterpart by only 3.27 points on TextCraft-Synth and 3.79 on TextWorld-Sync, whereas RAO beats single-agent GRPO by 39.97 and 12.64 points and single-agent CISPO by 35.86 and 13.07 points.

• Rubric rewards without rubric training barely help. Replacing binary per-node rewards with continuous scores from an untrained rubric generator (SERA w/o D & RT) improves average by only 3.33 points on TextCraft-Synth and falls 0.83 points below RAO on TextWorld-Sync.

• Training rubric generation is the main driver. Adding rubric training (SERA w/o D) lifts average success by 2.58 points on TextCraft-Synth and 9.16 points on TextWorld-Sync over the untrained-rubric variant, with Hard and Extreme success on TextCraft-Synth up 6.62 and 7.60 points.

• Rubric training needs rubric-based execution rewards. RAO + RT keeps binary execution rewards; it is competitive on TextCraft-Synth (72.47% average) but drops to 45.62% on TextWorld-Sync, below RAO's 51.93%.

• A trained 4B self-evaluator beats a frontier judge. Training-free per-subtask policy rubrics already reach 72.26% on TextCraft-Synth, versus 71.41% with Kimi as generator and 73.10% with Kimi as both generator and scorer. After training, 74.84% beats the strongest training-free configuration (73.10%) by 1.74 points, with the margin on Hard (79.90 vs 77.45) and Extreme (11.52 vs 4.17).

• Per-subtask rubrics matter. A single global policy rubric reused across all subtasks drops success to 67.77%, a 4.49-point gap from per-subtask rubrics.

• Score dispersion is the wrong training signal. Adding the label-free discriminativeness reward of Ding et al. drops success to 65.77%, a 9.07-point decrease.

• Decomposition reward helps mainly on interdependent tasks. SERA beats SERA w/o D by 4.81 points on TextWorld-Sync, concentrated on Hard (+8.58) and Extreme (+17.43), but trails by 0.53 points on TextCraft-Synth; added to RAO alone it changes average by 0.00 and −0.60 points.

• External supervision is cut substantially. TextCraft program-verifier calls fall from 550.94K to 257.96K (about 2.1x); TextWorld judge calls from 147.80K to 35.79K (4.1x) and input tokens from 633.80M to 125.32M (5.1x). Removing external calls entirely (SERA w/o D & RT) yields only 51.10% on TextWorld versus SERA's 65.07%.

• The learned rubric works at inference. On TextWorld-Sync, policy-guided selection with N=2 raises SERA from 65.07% to 67.50% (+2.43 points), with Extreme rising from 22.86% to 28.95%; this matches an external Kimi-K3 judge (67.29%). Without SERA training, policy selection yields −0.22 points and Kimi selection only +1.21, with Hard and Extreme stuck at zero.

Methodology in Plain English

The system trains one Qwen3-4B-Instruct-2507 model (fully fine-tuned with Adam) to do three jobs, each with its own reward, updated in alternation at a fixed ratio of 16:2:2.

1. Solving, scored by its own rubric. When a parent decides to delegate, it first writes a short list of weighted natural-language success criteria for that child and freezes it before the child runs, so criteria cannot be fitted to the trajectory they later grade. After the child finishes, another no-gradient invocation of the same model applies the frozen rubric, producing a pass/fail gate and a per-criterion score; the weighted sum is the node's reward. The root keeps the environment's reward.

2. Decomposing, scored by leaf coverage. Each delegation is credited by the share of the final tree's leaf nodes that sit inside its subtree, multiplied by whether the root task succeeded. Delegations in failed trees get zero. Averaging per tree before the baseline prevents trees with many delegations from dominating.

3. Evaluating, scored by ranking against verified outcomes. At each delegation point the environment is cloned and B rollouts of the same subtask are sampled; a verifier (TextCraft-Synth) or LLM judge (TextWorld-Sync) labels each as success or failure. The rubric is trained with a margin-ranking loss so it scores successes above failures. This avoids the co-adaptation trap of rewarding rubrics through task reward, since generator and solver share weights.

Advantages use leave-one-out baselines — other trees' root outcomes for execution, per-tree mean leaf reward for decomposition, other valid events for rubric ranking — and all three share a CISPO clipped policy-gradient loss with inverse-frequency depth weights so each recursion depth contributes equally. Training uses at most 20 environment steps per agent and recursion depth up to 3, with 250 optimizer updates on TextCraft-Synth (training on Medium difficulty, evaluating on all four levels) and 400 on TextWorld-Sync.

Why This Matters

The paper reframes recursive-agent training: instead of bolting an external judge onto a delegation scaffold, it turns evaluation into part of the policy, so judging and solving share weights and improve together. It also shows this reduces reliance on costly external labels rather than increasing them.

Real-world applications:

• Repository-scale code changes, where a parent agent splits a large edit into interdependent sub-edits and must decide whether each child's patch actually did its job without running a full test suite on every node.
• Multi-hop research assistance, where evidence must be gathered across retrieval steps and each delegated search needs a quality check before its result is trusted upstream.
• Cost-sensitive agent deployments, where per-node LLM-judge calls dominate the bill and a learned in-policy evaluator amortizes that cost (the paper reports judge calls falling 4.1x and input tokens 5.1x on TextWorld-Sync).
• Test-time scaling budgets, where the same learned rubric ranks alternative branches during tree search, buying extra accuracy (2.43 points on TextWorld-Sync) with no additional training.

Industry relevance: teams building coding, browsing, or research agents already pay for verifier or judge calls at every node; a trained self-evaluator that matches an external frontier judge (67.50% vs 67.29% in the selection experiment) is a direct cost and latency lever, and the 4B-parameter setting shows the effect is not limited to frontier-scale models.

Future Directions

• Weighting leaves by importance. The paper weights all leaves equally because no signal measures an individual leaf's contribution, and names subtask-level importance weights as a natural extension.
• When rubric training saturates. Prior work notes static rubrics saturate as the policy improves; the paper's verified-outcome ranking avoids the failure of dispersion-based signals, but whether a fixed judge or verifier remains a useful anchor over longer training is not reported.
• Transferring the decomposition reward. It helps on TextWorld-Sync's interdependent tasks but slightly hurts TextCraft-Synth (−0.53 points), leaving open how to detect when decomposition credit is worth applying.
• Tuning the alternating schedule. The 16:2:2 ratio was chosen with execution getting the largest share; the paper states the ratio can be adjusted per domain without changing the method, so how sensitive results are to it is not reported.

Target Audience

Researchers and engineers working on LLM agents and RL post-training — particularly those building recursive, multi-agent, or delegation-based scaffolds — along with practitioners who want to replace per-node LLM-judge calls with a learned evaluator, and students who already know policy-gradient basics and want a concrete case study in designing separate credit signals over a shared policy.

Authors’ 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 \emph{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.