PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-Evaluating Recursive Agents

TianYi Lyu, Xiaozhe Li, Yang Li, Yongkang Chen, Kefei Tian, Junbo Niu, Zican Hu, Hongbo Liu, Mingliang Xiong, Qingwen Liu

arXiv:2610.04902v1cs.AI

TL;DR

Recursive agents must handle self-invented subtasks that lack ground-truth checks, while node-level verifier or judge rewards are costly and do not assess decomposition. SERA trains a shared policy to generate rubrics aligned with verified outcomes and to reward decomposition, improving results over RAO on both benchmarks.

  • Problem

    Recursive agents invent intermediate subtasks without ground-truth checks, while verifier- or judge-based node rewards are costly and do not assess decomposition quality.

    Source: §1 · pp. 1–2

  • Method

    SERA trains one shared policy to decompose, solve, and evaluate subtasks, ranking rubric scores against verified outcomes and rewarding leaf coverage.

    Source: §1 · p. 2, §3.4 · p. 4, §5 · p. 9

  • Results

    SERA improves over RAO by 5.38 points on TextCraft-Synth and 13.14 points on TextWorld-Sync.

    Source: §4.1 · p. 6

  • Takeaways & Limitations

    Training rubric generation drives the largest gains, and learned rubrics also select candidate resolutions during inference-time tree search.

    Source: §1 · p. 2, §5 · p. 9

    Evaluation covers only Qwen3-4B on two synthetic benchmarks, leaving generalization to larger models and real-world agent tasks untested.

    Source: §5 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

Recursive agents use one shared policy to decompose tasks, solve subtasks, and evaluate delegated work, but intermediate subtasks lack ground-truth checks. SERA trains self-generated rubrics and a separate decomposition reward, and uses the learned rubrics to select candidate resolutions at inference.

1 INTRODUCTION

  • Verifier- or judge-based node rewards are coarse and costly, and they do not assess whether the agent chose the right subtasks.Intermediate subtasks often lack ground-truth checks, unlike final outcomes.Source: §1 · pp. 1–2
  • A recursive agent must decompose problems, solve subtasks, and evaluate delegated work, with each capability receiving its own signal on shared weights.Every child is a fresh instance of the parent policy.Source: §1 · p. 2
  • Before delegation, the parent writes weighted natural-language success criteria, which yield a continuous, subtask-specific score for the child’s output.Writing criteria before the child runs prevents fitting them to the trajectory they later score.Source: §1 · p. 2
  • SERA trains rubric generation to rank verified successes above failures; the judge trains the rubric generator rather than directly rewarding nodes.The paper identifies training rubric generation as the central empirical finding for improving execution with shared weights.Source: §1 · p. 2
  • A leaf-coverage reward credits a delegation by its subtree’s share of leaf-level work in a solved tree, helping most when subtasks are interdependent.The reward adds little for shallow, near-independent subtasks and helps with dependency chains, shared state, or coordination.Source: §1 · p. 2
  • SERA reports state-of-the-art results on TextCraft-Synth and TextWorld-Sync, with further gains from using learned rubrics for inference-time tree search.The rubric selects among candidate resolutions during depth-first search, with the best resolution propagated upward.Source: §1 · p. 2

2 RELATED WORK

Prior work studies recursive delegation, process supervision, hierarchical credit, and learned rubrics, but often fixes workers or separates the evaluator from the policy. SERA applies learned rubric generation to dynamically generated recursive subtasks using the policy itself as evaluator.

Recursive and multi-agent training

  • Recursive and multi-agent work scales agents through task decomposition, but most methods use a fixed scaffold; newer delegation training is often depth-1 or uses restricted workers.RAO combines recursion beyond depth 1, asynchronous subagents, and end-to-end RL for root agents and subagents; SERA adopts it as its primary baseline but changes the node signal.Source: §2 · p. 2, Figure 1 · p. 3
  • Unlike RAO’s binary verifier or judge label, SERA gives each node a trained continuous rubric and directly credits decomposition quality.RAO is the primary baseline, and its node signal does not assess whether the right subtasks were created.Source: Figure 1 · p. 3

Dense rewards and process supervision for agents

  • Process supervision and agentic credit assignment densify signals on flat trajectories, while hierarchical RL assigns cross-level credit with fixed subtask types or hierarchy depth.SERA instead operates on dynamically generated trees whose hierarchy, subtasks, and evaluator vary by rollout.Source: §2 · p. 3

Rubric-based reinforcement learning

  • Rubric-learning methods co-train rubrics and policies, but assume flat or fixed-stage computation with a separate rubric model; SERA uses its policy as evaluator on variable recursive trees.SERA trains rubric generation with a ranking objective anchored to verified outcomes.Source: §2 · p. 3

3 METHOD

SERA trains one shared policy to decompose tasks, solve subtasks, and evaluate outcomes with separate learning signals. It alternates updates for these objectives and reuses learned rubrics to select resolutions at inference time.

3.1 PROBLEM SETUP

  • The shared policy recursively solves or delegates a root task, forming a tree in which intermediate subtasks receive self-evaluated rewards.The root outcome is evaluated by the environment; multiple independent trees are sampled per root task for variance reduction.Source: §3.1 · pp. 3–4

3.2 SELF-EVALUATED EXECUTION REWARD

  • Parents commit frozen, weighted natural-language success criteria before a child runs, and the same policy scores the completed child against them.A separate no-gradient invocation produces a binary completion gate and per-criterion scores; incomplete attempts receive zero.Source: §3.2 · p. 4

3.3 LEAF-COVERAGE REWARD FOR DECOMPOSITION

  • Each delegation earns leaf-coverage credit only when the root task succeeds, proportional to the leaf-level work organized by its subtree.Leaf nodes represent atomic subproblems contributing directly to the final answer; the reward is applied to delegation-goal tokens, not execution or rubric tokens.Source: §3.3 · p. 4

3.4 TRAINING RUBRIC GENERATION FROM VERIFIED OUTCOMES

  • Rubric generation is trained with a ranking objective on counterfactual rollouts, requiring rubrics to score verified subtask successes above failures.Verified outcomes come from an environment verifier or external judge and are used only for rubric-generation training; ordinary execution uses the policy’s frozen rubric scores.Source: §3.4 · pp. 4–5

3.5 ADVANTAGE ESTIMATION AND POLICY OBJECTIVE

  • Three raw rewards use separate leave-one-out baselines before their advantages feed a shared policy objective, with depth weighting intended to equalize gradient contribution across recursion depths.Trees are averaged before the decomposition baseline so trees with many delegation events do not dominate it.Source: §3.5 · pp. 5–6

3.6 ALTERNATING OPTIMIZATION SCHEDULE

  • SERA alternates shared-policy updates for execution, leaf-coverage decomposition, and rubric generation, then reuses learned rubrics to rank candidate resolutions in inference-time tree search.Each optimizer step activates one objective; execution receives the largest share, while leaf-coverage and rubric-generation updates are periodic.Source: §3.1 · p. 4, §3.6 · p. 6

4 EXPERIMENTS

Experiments compare SERA with prompting, single-agent RL, and recursive-agent baselines on two benchmarks with different subtask-verification regimes. SERA places first or second on both benchmarks, with ablations and test-time selection examining its components.

4 EXPERIMENTS

  • TextCraft-Synth has independently verifiable crafting subtasks, whereas TextWorld-Sync uses LLM-judge labels for subtasks that cannot be independently verified.Source: §4 · p. 6

4.1 EXPERIMENTAL RESULTS

  • SERA improves over RAO by 5.38 points on TextCraft-Synth and 13.14 points on TextWorld-Sync, averaging 74.31% and 65.07%, respectively.Source: §4.1 · p. 6, Table 1 · p. 7
  • Prompted delegation adds only 3.27 points on TextCraft-Synth and 3.79 on TextWorld-Sync, while recursive-agent training substantially outperforms single-agent RL baselines.Source: §4 · p. 6, §4.1 · p. 7
  • Without rubric training, continuous rubric rewards add only 3.33 points on TextCraft-Synth and trail RAO by 0.83 points on TextWorld-Sync; rubric training adds 2.58 and 9.16 points, but requires rubric-based execution rewards.Source: §4.1 · p. 7
  • Decomposition training improves TextWorld-Sync by 4.81 points, concentrated on Hard (+8.58) and Extreme (+17.43) tasks, but trails the no-decomposition variant by 0.53 points on TextCraft-Synth.Source: §4.1 · p. 7
  • SERA reduces verifier calls on TextCraft-Synth from 550.94K to 257.96K and TextWorld-Sync judge calls from 147.80K to 35.79K, with input tokens falling from 633.80M to 125.32M.Source: §4.1 · pp. 7–8, Table 2 · p. 7

4.2 ABLATION STUDY

  • On TextCraft-Synth, verified-outcome ranking raises average success from 72.26% to 74.84%, while adding label-free score dispersion lowers it to 65.77%.Source: §4.2 · p. 8, Table 3 · p. 8

4.3 TEST-TIME SCALING WITH LEARNED SELF-EVALUATION

  • On TextWorld-Sync, rubric-guided selection raises SERA average success from 65.07% to 67.50% (+2.43 points), while an untrained policy judge yields no average gain.Source: Table 4 · p. 9, §4.3 · p. 9

5 CONCLUSION

SERA trains recursive agents to decompose tasks, solve subtasks, and evaluate outcomes through distinct signals on a shared policy. Its learned rubric also supports inference-time selection, while evaluation remains limited to two synthetic benchmarks and leaves robustness under noisy verification open.

5 CONCLUSION

  • SERA’s largest gains come from training the shared policy to generate rubrics aligned with verified outcomes, while leaf-coverage rewards separately train decomposition.The conclusion says the learned rubric signal outperforms direct use of the judge and that leaf-coverage gains are largest on tasks requiring coordination among interdependent subtasks.Source: §5 · p. 9
  • The learned rubric can select candidate resolutions during inference-time tree search, further improving task success without additional training.The search proceeds depth-first and propagates the best rubric-scored resolution upward.Source: §5 · p. 9
  • Evaluation covers only Qwen3-4B on two synthetic benchmarks; generalization to larger models or real-world tasks and robustness to sparse or noisy verification remain untested.Rubric training still depends on verified outcomes, and the leaf-coverage reward treats all leaf nodes equally.Source: §5 · p. 9

A RECURSIVE EXECUTION AND SUPERVISION

  • In SERA, parents freeze a subtask-specific rubric before a child runs, then apply it to the child’s trajectory and final environment state for execution reward.External outcomes train rubric generation; the policy’s rubric scores reward subtask execution, unlike RAO’s direct use of external outcomes.Source: A RECURSIVE EXECUTION AND SUPERVISION · p. 13

B.1 SHARED OPTIMIZATION AND EVALUATION PROTOCOL

The RL experiments fine-tune Qwen3-4B-Instruct-2507 with a shared optimization setup, while recursive rollouts use fixed task, tree, and depth budgets.

B.1 SHARED OPTIMIZATION AND EVALUATION PROTOCOL

  • The RL experiments use Qwen3-4B-Instruct-2507 as the base policy, fine-tune all parameters with Adam, and share the CISPO objective.Source: §B.1 · p. 13
  • Each update samples eight root tasks and K = 8 independently sampled trees per root, with 20 environment steps for the root and each child and maximum recursion depth three.Source: §B.1 · p. 14
  • The recursive RL methods also share leave-one-out advantage estimation and inverse-frequency depth weighting; Table 5 details optimization, rollout, and evaluation settings.Table 5 notes that ranges reflect small entrance-specific prompt/completion budget differences within the same benchmark.Source: §B.1 · p. 14, Table 5 · p. 14

B.2 REWARD SOURCES AND ALTERNATING UPDATES

SERA alternates execution, decomposition, and rubric-generation objectives on one shared policy, with different reward sources and data requirements. The update allocation reserves most steps for execution and interleaves less frequent decomposition and rubric training.

B.2 REWARD SOURCES AND ALTERNATING UPDATES

  • Execution updates train solving and delegation with rubric scores, decomposition updates train delegation alone, and rubric-training updates train rubric-generation actions alone.Each optimizer step activates one objective rather than summing the three raw rewards.Source: §B.2 · p. 14
  • Rubric-generation training uses counterfactual rollouts and external subtask labels, while decomposition training uses ordinary execution trees.TextCraft-Synth labels come from a program verifier and TextWorld-Sync labels from an external LLM judge.Source: §B.2 · p. 14, Table 6 · p. 15
  • SERA uses execution:D:RT updates at 16:2:2, while SERA w/o D uses 16:0:2 and execution-only variants use 1:0:0.RAO + D uses 12:4:0; these ratios allocate update frequency rather than weight a combined reward.Source: §B.2 · p. 14
  • All recursive methods hold total optimizer-update counts fixed, so decomposition and rubric-training stages displace execution updates rather than adding updates.The methods use different stage allocations within that fixed budget.Source: §B.2 · p. 14

B.3 TRAINING RUNTIME

Training runtime varies by benchmark: SERA is faster than the other recursive methods on TextCraft-Synth but slower than RAO on TextWorld-Sync. On TextWorld-Sync, the longer runtime accompanies a 13.14-point average accuracy gain over RAO.

B.3 TRAINING RUNTIME

  • Runtime comparisons use identical hardware, 2 × 8 H200 GPUs, and are meaningful only within each benchmark.All recursive methods share the same total optimizer-update budget; stage costs and benchmark rollout costs contribute to runtime differences.Source: §B.3 · p. 15, Table 7 · p. 15
  • 24h06m makes SERA the fastest multi-agent method on TextCraft-Synth, below RAO’s 29h36m and SERA w/o D & RT’s 47h02m; SERA is also most accurate there.The authors attribute the lower cost to concentrating rubric computation in periodic rubric-generation training rather than scoring every execution step against a rubric.Source: §B.3 · p. 15, Table 7 · p. 15
  • On TextWorld-Sync, SERA takes 24h14m versus RAO’s 13h08m, while gaining 13.14 points in average accuracy over RAO.The authors attribute benchmark runtime differences to rollout costs, including sequential interaction under TextWorld’s shared-state dependencies.Source: §B.3 · p. 15, Table 7 · p. 15

C TEXTWORLD-SYNC DATASET CONSTRUCTION

TextWorld-Sync extends CookingWorld to evaluate recursive delegation under shared-state constraints, distinguishing local subtask completion from joint task success.

C TEXTWORLD-SYNC DATASET CONSTRUCTION

C.1 SHARED WORLD AND AGENT-LOCAL CONTEXTS

  • Agents share objects, inventories, tools, doors, recipe progress, and task score, while retaining separate locations, histories, observations, and step budgets.Environment reads and state transitions are serialized and committed atomically, so concurrent planning can expose dependencies while preserving consistent updates.Source: §C.1 · p. 16

C.2 PROCEDURAL TASKS AND COORDINATION STRUCTURES

TextWorld-Sync procedurally generates multi-dish tasks with varied coordination structures and evaluates success at the root-task level.

C.2 PROCEDURAL TASKS AND COORDINATION STRUCTURES

  • The generator samples multiple disjoint recipes per seed and assigns ingredients to dishes, with independent branches delegable in parallel subject to resource and dependency constraints.Instances are recorded in a fixed manifest and reconstructed at runtime by a multi-dish adapter.Source: §C.2 · p. 16
  • The root evaluator requires every ingredient to be collected and correctly processed and every dish prepared and consumed; an individual completed dish yields partial progress, not task termination.Source: §C.2 · p. 16
  • Because the root-level check does not label arbitrary policy-generated subtasks, SERA uses an external judge for rubric-training labels on this benchmark.Source: §C.2 · p. 16
  • Seven task families vary branch dependencies, workload allocation, resource constraints, and recursion, while all use a shared world and require every dish for root-task success.The families range from independent branches to shared-resource conflicts and nested dependencies.Source: Table 8 · p. 16, §C.2 · p. 16

C.3 DATASET SPLITS AND DIFFICULTY LEVELS

The datasets use difficulty levels based on constraint number and scale, with fixed training, validation, and test splits.

C.3 DATASET SPLITS AND DIFFICULTY LEVELS

  • TextWorld-Sync has 1,500 training, 200 validation, and 1,400 test tasks; training includes 900 Medium, 150 Hard, and 450 Extreme tasks.Validation and test each contain 50 and 350 tasks per difficulty, respectively.Source: §C.3 · p. 16
  • TextCraft-Synth training uses a fixed subset of 852 Medium tasks and evaluates on 632 tasks spanning all four difficulty levels.Its setup tests transfer from Medium training tasks across recipe depths; TextWorld-Sync training covers several coordination-difficulty levels.Source: §C.3 · pp. 16–17
  • Tasks are assigned to Easy, Medium, Hard, or Extreme according to the number and scale of their constraints.Source: §C.3 · p. 16

Related papers

Loading 2610.04902v1…