R$^2$Orch: Recursive Self-Improvement for Agent Orchestration via Self-Play within a Skill-Internalization Loop

📌 Highlights

R2Orch's central claim is that an orchestration learner should improve its task curriculum and its skill scaffold together. The Proposer seeks tasks that remain learnable without the candidate skill, while the Director learns graph construction from the resulting self-play groups.

The strongest empirical result is breadth: R2Orch is reported as best on all twelve benchmarks and is evaluated at zero skills. Its IID average is 89.79, compared with 86.00 for PATS and 82.34 for FlowSteer; its OOD average is 78.79, compared with 76.13 for PATS and 73.52 for FlowSteer.

The main caveat is initialization: the authors customize the initial skills by hand for each dataset, so the method's autonomy begins after a human-provided scaffold.

• Inner loop: Proposer task selection plus Director self-play.
• Outer loop: posterior-based skill withdrawal and failure distillation.
• Deployment target: successful graph construction with an empty skill context.
• Evidence: six IID and six OOD benchmarks across QA, math, code, and interactive tasks.

🎯 Introduction

The paper studies learned orchestration in which a Director composes an agent graph from role prompts, model routes, layers, hand-offs, and an output node. Earlier approaches either optimize over a fixed human-collected task pool, improve with skills that remain in context, or withdraw skills using success-rate, budget, or validation-gap rules.

The authors identify three linked problems: hand-designed curricula do not adapt to the evolving Director, group-based RL loses its advantage signal when all rollouts share an outcome, and a skill's raw success rate mixes the effect of the skill with the difficulty of the selected task. R2Orch makes task selection and skill withdrawal mutually informative through two channels: Recursive Learnability sends an objective to the inner loop, and Skill Withdrawal sends controlled evidence back to the outer loop.

The paradigm comparison emphasizes that the intended endpoint is not simply a strong skill-assisted frontier. It is a Director whose graph-building policy retains performance as the scaffold shrinks to zero.

🔬 Methodology

The Director constructs a graph through a trajectory of atomic edits, and frozen Workers execute the resulting graph. Equation 1 formalizes the edit process, while Equation 2 states the zero-skill deployment objective. The inner and outer policies use proximal updates in Equation 3, with the Director optimizing graph outcomes and the Proposer optimizing task rewards.

Each task receives a randomized rollout group. If K_x is the retrieved skill set and k_x is the candidate under test, the hidden part reads K_x without k_x and the visible part reads K_x. Equation 4 makes this mixture explicit. The Director is updated with a group-relative leave-one-out estimator, so graph trajectories with different verifier outcomes create the learning signal.

Recursive Learnability uses the hidden-part outcome variance as its target. Equation 8 makes the mechanism clear: learnability is 4p(1-p), so all-correct and all-incorrect groups provide no signal, while mixed groups provide the strongest signal. Equation 9 turns the hidden outcome estimate into a Proposer reward with collapse handling, discounting, and empirical-Bayes smoothing.

Skill Withdrawal estimates a candidate skill's marginal benefit from the visible-minus-hidden success contrast in the same randomized group. These contrasts accumulate in a per-skill Bayesian-bootstrap posterior; the outer loop withdraws a sufficiently tested skill when its expected positive benefit is small and admits a new skill when the posterior risk of non-benefit is low.

• The rollout group is shared by training and evaluation.
• Most rollouts hide the candidate skill, directly preparing zero-skill behavior.
• The Proposer is rewarded for learnability after withdrawal, not only for current success.
• Withdrawal decisions use skill-specific paired contrasts rather than aggregate success rates.

📊 Experiments

The evaluation uses six IID benchmarks supplying training tasks and IID tests: HotpotQA, NQ-Open, MedQA, AIME 2026, MBPP+, and ALFWorld. Six held-out OOD benchmarks are TriviaQA, MuSiQue, GPQA, MATH-Hard, SWE-Bench, and WebShop. The reported metrics are success-oriented: higher exact match, F1, accuracy, Pass@1, success rate, and Resolved scores are better. Each test set contains 128 items, except AIME 2026 with 30 items, and results are five-run means with standard deviations.

Against direct prompting, SFT, GRPO, workflow search, agent-RL, skill-internalization, and self-play baselines, R2Orch is reported as best on all twelve benchmarks while tested with zero skills. Its IID average is 89.79 and its OOD average is 78.79. Particularly large reported advantages appear on AIME 2026, ALFWorld, and WebShop, where the ablations also show the largest losses.

The component ablations support the proposed mechanism. Removing Recursive Self-Play Orchestration reduces the AIME score to 59.33 and WebShop SR to 71.72; removing Recursive Learnability reduces them to 64.00 and 83.13; fixing the scaffold instead of withdrawing skills reduces them to 66.67 and 76.09. The full system reaches 81.33 on AIME and 91.09 on WebShop.

The Director trained with Qwen3.5-9B Workers improves all six other Worker backbones without retraining. The paper reports that the IID range across backbones narrows from 25.7 to 6.4 points, while OOD gains are largest on interactive tasks and smallest on math, which is already near its ceiling.

• RQ1: R2Orch leads on all twelve IID and OOD benchmarks.
• RQ2: The trained Director transfers to six other Worker backbones.
• RQ3: Both self-play and the shrinking scaffold contribute to zero-skill performance.
• RQ4: Recursive Learnability selects mixed-outcome tasks and avoids solved candidates.
• RQ5: All twelve reported withdrawals satisfy the paper's posterior decision rule, with posterior E[Δ+] at most 0.019.

fig:intro

Caption: A recursion needs two channels: the outer loop sets the inner loop's objective, and the inner loop, Proposer--Director self-play on a randomized rollout group, returns the evidence for withdrawing skills.

Why It Matters: This figure gives the central systems view: objective information flows downward from skill management to task selection, while rollout evidence flows upward to support skill withdrawal.

fig:paradigms

Caption: Paradigm comparison. (a) Learned orchestration trains on a hand-designed static curriculum. (b) Self-improving agents measure the frontier with skills present, a skill-anchored frontier where advantages collapse once skills leave. (c) Skill scaffolds withdraw guidance through success-rate gates, unreliable evaluation signals pinned by self-play. (d) R2Orch nests two loops joined by downward (objective) and upward (evidence) channels.

Why It Matters: It situates the method against fixed curricula, skill-conditioned self-improvement, and success-rate-based scaffold removal.

fig:method

Caption: Overview of R2Orch. Top: Proposer--Director self-play (inner loop) and skill withdrawal (outer loop) share one randomized rollout group. Bottom left: Recursive Learnability scores a task with the candidate skill hidden. Bottom right: Skill Withdrawal withdraws or admits each skill by the posterior of its paired contrast.

Why It Matters: This is the most useful implementation diagram because it connects task selection, Director updates, paired contrasts, posterior decisions, and skill revision in one cycle.

fig:transfer

Caption: Training dynamics and backbone transfer. (a) Held-out accuracy with skills and at zero skills. (b) Graph types over the six IID datasets per Proposer objective (final counts at the curve ends). (c) The Proposer's probability mass on unseen, unsolved ($p=0$), learnable ($0<p<1$), and solved ($p=1$) candidates by previous success rate $p$ (power-scaled axis). (d) Probability of choosing a solved candidate as a moving average over 10 cycles (dots: single cycles) for the trained Proposer, the untrained model with the same prompt, and random choice. (e) Backbone transfer: the Director trained with Qwen3.5-9B Workers is used unchanged at zero skills with six other backbones. Radars: IID scores wi...

Why It Matters: The figure tests whether zero-skill accuracy catches up with skill-assisted accuracy and whether the learned Director transfers across Worker backbones.

fig:objective

Caption: Proposer objectives, selection cost, and skill withdrawals (RQ4, RQ5); only the Proposer's objective changes in (a)--(d) (AZR: Absolute Zero). (a) IID scores. (b) Row minus column of the mean OOD score. (c) Rollouts and tokens per effective group; bubble area: A100 hours. (d) Training (pink) and selection (blue) rollouts per cycle. (e) Seen-task picks over cycles 50--199 by previous success rate $p$: realized success and share of mixed new groups. (f) The seed cards' held-out gain over no cards, before training and around each withdrawal (95\% CI).

Why It Matters: It directly compares Proposer objectives, selection cost, task-choice behavior, and the evidence surrounding skill withdrawals.

🔮 Conclusion

The paper's evidence supports a coherent division of labor between the two loops. Recursive Learnability keeps the Proposer focused on tasks that can still generate a group-relative learning signal after withdrawal, while Skill Withdrawal limits the performance cost of removing skills whose measured marginal benefit has become small.

The resulting Director is evaluated at zero skills and leads the reported baselines across all twelve benchmarks. The transfer experiment further suggests that the learned graph roles and hand-offs are not tied completely to the original Qwen3.5-9B Worker backbone.

🛠️ Future Research Improvements

The clearest next research direction is to remove the paper's dependence on hand-customized initial skills. A useful extension would test whether the same failure-to-skill distillation mechanism can bootstrap a scaffold from generic instructions or automatically discovered procedures.

The evaluation should also expand beyond public static benchmarks and simulated interactive environments. Testing on changing task distributions, real tool interfaces, and longer-horizon workflows would clarify whether paired contrasts remain stable when verifier noise and environment state become more complex.

Further work should separate the cost of Director training, task selection, skill distillation, and withdrawal, then study how posterior thresholds and minimum-record requirements affect convergence, retained skills, and zero-skill performance.

🏭 Potential Industry Use Scenarios

R2Orch could be relevant to multi-agent systems that must coordinate specialized Workers for research, customer support, software maintenance, or operations workflows. The graph representation provides explicit roles and hand-offs, while the zero-skill target is attractive when prompt-time scaffolds are expensive, sensitive, or difficult to maintain.

The paired hidden-versus-visible evaluation could support controlled retirement of procedural prompts or agent skills in production-like systems, provided reliable verifiers and isolated evaluation traffic are available. The cross-backbone transfer result also suggests a possible architecture in which orchestration policies are reused as underlying Worker models change.

Deployment should remain sandboxed for tool-using agents. The paper itself notes that self-improving orchestration can be misused, so industry adoption would require permission boundaries, audit logs, rollbackable skill changes, and independent safety evaluation.

💬 Critical Analysis

The strongest aspect of R2Orch is that its mechanism and evaluation target align: the Director is trained mostly without the candidate skill, the Proposer is rewarded using hidden-context learnability, and withdrawal is based on a paired estimate of the skill's marginal effect. This is more diagnostic than using a single success rate that simultaneously reflects task choice and skill utility.

The ablations provide meaningful support for both loops. Uniform task selection, current-scaffold learnability, failure reward, fixed scaffolds, preset budgets, and validation gaps all trail the full method on at least some benchmarks, with the largest differences on AIME 2026, ALFWorld, and WebShop. However, the benchmark results do not by themselves establish that the learned graph structure is causally responsible for every gain, because the full system also changes task selection, scaffold state, and training context together.

Reproducibility depends on details that engineers should verify in the implementation: how initial skills are customized, how failures are distilled, how verifiers behave, how posterior decisions are calibrated, and how compute is allocated across training and selection. The paper reports that Recursive Learnability uses no extra selection rollouts because the hidden group already provides the signal, but the broader operational cost of maintaining skills, ledgers, and repeated graph rollouts remains an important deployment question.

• Strong internal logic: curriculum selection, training context, and withdrawal evidence are coupled.
• Strong empirical breadth: twelve benchmarks, zero-skill evaluation, and six-backbone transfer.
• Main external-validity concern: hand-built initial skills and benchmark-centered evaluation.
• Main reproducibility concern: verifier, skill-distillation, posterior, and compute-allocation details.