PaperlayerView exact revision on arXiv

Source-linked AI summary

EvoSteer: Online Self-Evolving Graph Orchestration via Reference-Anchored Credit Assignment

Mingda Zhang, Hanwen Zhang, Qiang Huang, Zijia Wang, Pengfei Guo, Yuchen Zhang, Jionghao Zhu, Xiaoying Tang

arXiv:2609.38661v2cs.AI

TL;DR

Existing orchestration generally revises teams only after a trajectory, while shared terminal credit and uncalibrated skill admission leave action-level responsibility and skill effects insufficiently resolved. EvoSteer builds and repairs teams during execution, assigns action credit against a frozen reference, and tests candidate skills with paired sequential evidence. It outperforms baselines across twelve benchmarks and improves every executor backbone.

  • Problem

    Existing orchestration revises teams after trajectories, while shared terminal credit and uncalibrated skill admission leave challenges in in-run repair, action-level credit, and skill validation.

    Source: §1 · pp. 1–2

  • Method

    EvoSteer builds and repairs a running team from execution features and a learned value estimate, uses AnchorTB for reference-relative action credit, and validates candidate skills with paired sequential tests.

    Source: §1 · p. 2

  • Results

    EvoSteer is best on all twelve benchmarks, ahead of the strongest baseline by 2.81 EM and 4.01 accuracy points on IID averages.

    Source: §5.2 · p. 7

  • Takeaways & Limitations

    The trained orchestrator transfers unchanged to six other executors and improves all 72 backbone–benchmark scores.

    Source: §5.2 · p. 7

Abstract

from arXiv · show

In recent years, LLM-based multi-agent systems have been widely applied to orchestrate tool-using agents into executable communication graphs. However, existing self-evolving orchestration still faces key challenges, including post-hoc evolution that revises the team only after the trajectory ends, credit diffusion that gives every action the same terminal advantage under confounded baselines, and skill admission that is uncalibrated and never retired. To address these challenges, we propose EvoSteer, a new paradigm of Online Self-Evolving Graph Orchestration -- the orchestrator builds a running team and repairs its plausible but failing steps from execution features and a learned value estimate. To support this paradigm, we introduce Anchored Trajectory Balance (AnchorTB), a regression-style flow-matching loss that assigns each orchestration action a coefficient by balancing subtrajectories against a frozen reference. Built on the learned flow, we further propose Validated Skill Admission, in which a candidate skill is tried before promotion and promoted only if paired evidence passes a sequential test under a shared nominal testing budget. Moreover, AnchorTB combines measured task-level reference reward statistics with prefix-dependent corrections. Experimental results on twelve datasets show that EvoSteer significantly outperforms baselines across question answering, mathematical reasoning, code generation, and interactive decision making. Our code is available at https://github.com/beita6969/evosteer.

1 INTRODUCTION

Graph orchestration makes multi-agent execution controllable, but teams are typically revised only between runs, leaving plausible failures unrepaired mid-execution. EvoSteer edits the running team, assigns action-level credit against a frozen reference, and validates skill admission; it outperforms baselines across the evaluated benchmarks.

1 INTRODUCTION

  • Existing orchestration revises skills, prompts, or topology only after batches of runs, so plausible failures cannot be repaired while execution continues.A misconfigured team can therefore be costly to detect even when its outputs look plausible.Source: §1 · p. 1
  • The paper identifies post-hoc evolution, credit diffusion, and uncalibrated skill admission as three challenges for existing methods.Shared terminal advantages can give every action the same coefficient; point-estimate admission can consolidate accidental strategies, and admitted skills are not tested for retirement.Source: §1 · p. 2
  • EvoSteer builds and repairs a running team from execution features and a learned value estimate, with reruns and drops available as in-run edits.Each atomic edit executes immediately, and its feedback and value estimate enter the state.Source: §1 · p. 2
  • AnchorTB assigns orchestration actions coefficients by balancing subtrajectories against a frozen reference, combining measured task-level reward statistics with prefix-dependent corrections.Validated Skill Admission lets candidates be tried before promotion and uses paired rollouts with a sequential sign test under a shared testing budget.Source: §1 · p. 2
  • EvoSteer outperforms workflow-search, orchestration-training, and skill-evolution baselines on every benchmark and improves all seven executors.The evaluation spans question answering, mathematical reasoning, interactive decision making, and code generation.Source: §1 · p. 2

2 RELATED WORK

EvoSteer differs from prior orchestration and skill-evolution work by editing a team during execution and testing candidate skills within a live episode.

Agent Task Orchestration

  • Prior orchestration work searches graphs under execution feedback, evolves teams between runs, mutates topology between rounds, repairs finished trajectories, or audits prefixes, but leaves the running team fixed.EvoSteer instead reruns and drops agents in the running team and measures flows from a frozen reference.Source: §2 · p. 3

Skill Self-Evolution

  • Skill-evolution methods use replay, paired trajectories, attribution, success-count posteriors, or tests, while EvoSteer tests skills in a live episode under one budget per run.Candidates remain selectable while they are being tested.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries define the communication graph and action-by-action orchestration trajectory, then specify a reward-proportional history target relative to a frozen reference.

3 PRELIMINARIES

  • A typed agent communication graph has role-and-skill agent nodes, protocol-bearing directed edges, and an output node and rule that determine the final answer.The edge protocol determines whether and how a source result revises its target.Source: §3 · p. 3
  • An orchestration trajectory is a complete sequence of actions from an empty team to a legal stop, with each action executed before the next is chosen.Actions include adding agents or edges, binding skills, setting output, rerunning or dropping agents, and stopping; execution feedback is retained in the history.Source: §3 · p. 3
  • The training target is a reward-proportional history distribution relative to a frozen reference policy and executor transitions.Its reward weighting keeps positive mass for failures and weights a full score e^β times a zero score.Source: §3 · p. 3

4 METHODOLOGY: EVOSTEER

EvoSteer combines online team construction and repair, reference-anchored action credit, and sequentially validated skill admission. These components use execution feedback and a frozen reference to guide decisions within the orchestration loop.

4.1 ONLINE SELF-EVOLVING GRAPH ORCHESTRATION

  • The orchestrator builds and runs teams using execution features and a reference value estimate, with reruns and new edges available as ordinary actions.Execution feedback and a fixed-length feature vector are appended to the state after each action.Source: Figure 3 · p. 4, §4.1 · p. 4
  • One policy shares construction and repair actions, including rerun and drop, and its legal action mask depends on the current graph, roles, skills, output modes, and budget.A lightweight value head estimates reference continuation reward from execution features and task type; the head is frozen for each rollout batch, and its estimate and one-step change are shown to the orchestrator.Source: §4.1 · p. 4

4.2 ANCHORED TRAJECTORY BALANCE

  • AnchorTB combines measured reference anchors with learned residuals and prefix-dependent corrections to represent state flows.Its task-level anchor uses a shrinkage estimate of reference mean reward; prefix corrections are read one batch behind, with pseudo-count shrinkage for rare structures and a bound on correction size.Source: §4.2 · p. 5
  • AnchorTB assigns each action a regression coefficient from all subtrajectories containing it, balancing those subtrajectories against the frozen reference.For a history of length T, equally weighted subtrajectory residuals contribute to each action’s coefficient; the terminal value overrides the learned parameterization.Source: §4.2 · pp. 5–6

4.3 VALIDATED SKILL ADMISSION

  • Sequential sign tests promote a candidate, retire it, or let evidence accumulate, while the shared testing budget limits total nominal level to α.The paired comparisons count wins, losses, and ties; directional tests are applied when new evidence arrives.Source: §4.3 · p. 6
  • Validated Skill Admission lets a candidate be tried before promotion and promotes or retires it only when paired evidence passes a sequential test under a shared alpha-spending budget.Candidates occupy a slot and can be bound before validation; paired rollouts share the task, runtime, and value-head snapshot, differing in whether the candidate is bound.Source: §4.3 · p. 6

5 EXPERIMENTS

EvoSteer is evaluated on six IID and six held-out OOD benchmarks, where it leads the baselines and transfers across executor backbones. Component analyses assess online orchestration, AnchorTB, and validated skill admission.

5.1 EXPERIMENTAL SETUP

  • Six IID benchmarks provide training tasks and tests, while six held-out OOD benchmarks test generalization; each test set has 128 items, except AIME 2026 with 30.Baselines use Qwen3.5-9B as executor and trained model unless labeled otherwise; scores are five-run means.Source: §5.1 · p. 7

5.2 MAIN RESULTS AND BACKBONE TRANSFER (RQ1–RQ3)

  • EvoSteer is best on all twelve benchmarks, ahead of the strongest baseline on IID and OOD averages.The reported margins are 2.81 EM and 4.01 accuracy points on IID averages, and 3.36 and 2.53 on OOD.Source: §5.2 · p. 7, Table 1 · p. 7
  • The trained orchestrator transfers unchanged to six other executors, improving all 72 backbone–benchmark scores and shrinking IID spread from 17.5 to 4.3 points.Weaker executors gain more; gains are largest on interactive tasks and smallest on math, where frozen scores are near the ceiling.Source: §5.2 · p. 7, Figure 5 · p. 8

5.3 COMPONENT ANALYSIS (RQ4, RQ5)

  • Removing interleaving, execution features, rerun/drop, or value estimates costs 5.69, 4.12, 3.57, or 5.07 IID points, respectively.The untrained architecture adds 21.01 IID and 24.04 OOD points over the frozen executor; AnchorTB training adds 12.31 and 11.22.Source: §5.3 · p. 9
  • AnchorTB beats tempered TB, TB, PPO, and GRPO by 3.17–8.81 IID points, using 28% less update compute than tempered TB.The measured anchor predicts reference-rollout correctness at AUC 0.812 versus 0.506 for the task-family mean; the learned part lowers loss below the anchor-only level.Source: §5.3 · p. 9
  • Validated admission improves all six IID datasets (+5.95), whereas admitting every candidate hurts MedQA and AIME 2026.Replacing the sequential test with a fixed success count costs 5.17 IID points; the loss is nearly the same for counts from 1 to 10.Source: §5.3 · p. 9

6 CONCLUSION

EvoSteer combines graph construction, repair, and skill growth in a learned loop, with actions executed as issued. AnchorTB credits actions against a frozen reference, and paired sequential tests govern skill retention.

6 CONCLUSION

  • EvoSteer unifies construction, repair, and skill growth in one learned loop.Each action executes as issued; paired sequential tests decide which skills are kept.Source: §6 · p. 9
  • AnchorTB credits orchestration actions against a frozen reference.Source: §6 · p. 9
  • EvoSteer beats all baselines on twelve benchmarks and improves every executor backbone.Source: §6 · p. 9

AI USE STATEMENT

The authors report AI assistance in editing, typesetting, layout, and related-work discovery, and state that they manually reviewed the assisted material.

AI USE STATEMENT

  • Generative AI tools assisted with text polishing, LaTeX typesetting, page layout, and placement or sizing of existing figures and tables.Source: AI USE STATEMENT · p. 10
  • AI tools also supported retrieval and discovery of related work; the authors state that bibliographic entries came from Google Scholar.Source: AI USE STATEMENT · p. 10
  • The authors say they manually verified AI-assisted material against implementation and experimental records and take responsibility for the final paper and artifacts.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

The authors state that the work follows the ICLR Code of Ethics and reports no human participants or personal information.

ETHICS STATEMENT

  • The authors commit to scientific integrity, transparency, and reproducibility, and report results without fabrication, falsification, or intentional misrepresentation.Source: ETHICS STATEMENT · p. 10
  • The statement says implementation and evaluation details are provided to facilitate verification and reproduction.Source: ETHICS STATEMENT · p. 10
  • The study uses existing benchmarks, models, and resources under their intended purposes and applicable licenses, with no human participants or personal information.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

The reproducibility statement identifies the released code, splits, configuration, evaluation materials, and reporting of five-run means and standard deviations. The appendix formalizes reference-relative flow properties and the conditions under which zero residuals recover the target distribution.

REPRODUCIBILITY STATEMENT

  • Code, exact training and test splits, and full configuration are public; test scores are five-run means with standard deviations reported in Table 1.The statement also lists the documented environment, action space, value estimate, objective, skill-admission procedure, benchmarks, evaluation settings, proofs, hyperparameters, metrics, protocol, and compute.Source: REPRODUCIBILITY STATEMENT · p. 10

A ANCHORED TRAJECTORY BALANCE

  • The appendix analyzes reward-tilted history laws, recorded-trajectory regression loss, and skill validation, with results conditional on their stated assumptions.It distinguishes algebraic identities on recorded trajectories from distributional or statistical results that require assumptions.Source: A ANCHORED TRAJECTORY BALANCE · p. 14

A.1 FORMAL SETTING, HISTORIES, AND LEGAL ACTIONS

  • Complete histories form a rooted tree with unique parentage; the executor kernel is fixed across policies, and reference-reachable continuations are assumed to terminate almost surely.A frozen context determines legal actions and masks, and finite-horizon results assume a bounded action horizon.Source: §A.1 · pp. 14–15

A.2 PATH LAWS AND POSITIVE AFFINE TILTING

  • The reward-tilted target is normalized and preserves reference support; for β > 0, its mean reward is strictly higher exactly when reference reward has positive variance.At β = 0, the target equals the reference distribution.Source: §A.2 · p. 15

A.3 CONDITIONAL RELATIVE FLOWS AND UNIQUENESS

  • The conditional target flow is the reference expectation of the reward tilt, and it is unique with a finite horizon or, on an infinite-depth tree, among bounded solutions.The conditional flow lies in [1, e^β].Source: §A.3 · p. 16

A.4 IDEAL ZERO-RESIDUAL CONSISTENCY

  • For a shared flow with the terminal reward boundary, zero residuals on supported trajectories recover the target policy; checking singleton intervals suffices.Under full coverage, zero expected loss implies the consistency conditions used in this result.Source: §A.4 · p. 17

A.5 FIXED-EXECUTOR REALIZABILITY AND ITS OBSTRUCTION

The appendix characterizes when action choices under a fixed executor can realize the reward-tilted target, then analyzes subtrajectory credit, approximation bounds, gradient routing, and implemented anchors. Its conditions and sensitivity results specify limits on exact realization and on how estimates vary.

A.5 FIXED-EXECUTOR REALIZABILITY AND ITS OBSTRUCTION

  • Action choices realize the target under a fixed executor only when its target successor law matches the fixed kernel; deterministic executors satisfy the condition, and the irreducible executor contribution vanishes exactly when it holds.When realizable, the action policy is uniquely determined on reference support.Source: §A.5 · pp. 17–18

A.6 SUBTRAJECTORY ALGEBRA AND CREDIT COEFFICIENTS

  • Singleton intervals expose local errors hidden by a zero full-trajectory residual; each action coefficient aggregates the intervals containing that action.There are (t + 1)(T − t) such intervals for action t.Source: §A.6 · p. 19

A.7 APPROXIMATE CONSISTENCY UNDER UNIFORM RESIDUAL CONTROL

  • With exact terminal boundary and uniformly controlled residuals, the induced log-density error is bounded and total variation is at most tanh(ε).The bound is stated for the shared-flow setting under the reference-law assumptions.Source: §A.7 · pp. 19–20

A.8 MIXED-BEHAVIOR REGRESSION AND GRADIENT BOUNDS

  • On recorded batches, θ gradients pass through action log-probabilities and ψ through residual values; anchors are detached, behavior may lag one update, and paired rollouts force the first action.Source: §A.8 · p. 20

B SHRINKAGE BASELINES, STRUCTURAL POOLING, AND THE VALUE HEAD

B.1 IMPLEMENTED TRAJECTORY-INDEXED FLOWS

  • With c = 0, bψ = 0, β > 0, and q = 5/6, the common root receives two different trajectory-indexed flow values.Those values are log(1 + aβ/6) and log(1 + 5aβ/6), both in [0, β].Source: §B.1 · p. 21

B.2 HIERARCHICAL SHRINKAGE AND ITS RANGE

  • Under valid bounded counts and positive shrinkage strengths, the hierarchical reward estimate remains in [0, 1], and the measured flow is clipped to [0, β].For bounded nonbinary rewards, the estimate represents a mean score; for binary rewards, it represents a success probability.Source: §B.2 · pp. 21–22

B.3 ANCHOR SENSITIVITY AND RESIDUAL STABILITY

  • Clipped anchor changes are bounded by aβ|p − p′| + |c − c′|, while residual-head changes are added outside the measured part’s clipping range.The measured part lies in [0, β].Source: §B.3 · p. 22

B.4 RATIO-FIRST STRUCTURAL POOLING

The section develops ratio-first structural pooling, characterizes the value head as a feature-conditional regression, and distinguishes the implemented AnchorTB optimum from the ideal flow.

B.4 RATIO-FIRST STRUCTURAL POOLING

  • Pooling averages reward-to-reference ratios across eligible prefix visits, with a pseudo-observation; repeated visits can be correlated and structural reads lag one batch.With no visits but a positive prior count, the correction is zero; under the stated bounds, the ratio and clipped log correction are bounded.Source: §B.4 · p. 23
  • Ratio-first pooling retains a finite-sample Jensen gap, and random denominators can make expected ratios differ from ratios of expectations.Visit pooling weights records by visit count, so repeated visits sharing a terminal reward are not independent task observations.Source: §B.4 · p. 23

B.5 VALUE-HEAD PROJECTION AND CALIBRATION

  • The value head’s squared-risk minimizer is the conditional mean given its features, and its mean-calibration error is bounded by its excess risk.Equality with the ideal reference value requires compatible continuation data and sufficient features; the implemented head estimates success probability for binary rewards and expected score otherwise.Source: §B.5 · p. 24

B.6 THE IMPLEMENTED OPTIMUM AND THE IDEAL FLOW

  • For a one-action executor with β > 0, the implemented AnchorTB loss is minimized at u0 = β/2, not the ideal root log[(1 + e^β)/2].The minimum loss is β^2/4, reflecting the difference between expected log reward and log expected reward.Source: §B.6 · p. 24

C SEQUENTIAL VALIDATION AND THE TRAINING LOOP

This section specifies paired skill validation and its sequential error accounting, then describes the training loop and its data routing. The tests compare candidate and control rollout regimes under stated registration and future-data conditions.

C SEQUENTIAL VALIDATION AND THE TRAINING LOOP

  • Paired validation compares specified rollout regimes, while the training loop closes the section by integrating validation with orchestration learning.The section describes fixed-look directional tests and error accounting for an adaptive run.Source: C SEQUENTIAL VALIDATION AND THE… · p. 25, §C.5 · p. 29

C.1 PAIRED INTERVENTION REGIMES AND EFFECT ESTIMANDS

  • The paired intervention binds a candidate at the first action of an initially empty team, while control keeps it unavailable; the effect measures threshold-pass differences, not mean-score changes.Later decisions continue under the frozen reference policy, and the effect includes those downstream decisions.Source: §C.1 · p. 25

C.2 EXACT FIXED-LOOK DIRECTIONAL TESTS

  • Under the registered i.i.d. pair model, directional tests use win and loss counts; a stronger fixed-context sign condition also yields valid tests, and two directions at one look spend at most the assigned level.Within-pair dependence is allowed; conditional sign independence is required for the stronger fixed-context result.Source: §C.2 · pp. 25–26

C.3 ADAPTIVE SELECTION, REPEATED PROBLEMS, AND REPEATED LOOKS

  • Correlated duplicate pairs or reusing screening outcomes to select a candidate can invalidate ordinary fixed-candidate p-values, even when nominal spending is followed.The protocol instead selects from registration information and validates on future data; repeated looks also retain their planned indices and valid null law.Source: §C.3 · p. 27

C.4 NOMINAL SPENDING AND CONDITIONAL COUNTABLE FWER

  • Globally unique directional allocations used at most once spend no more than α, and the whole-run false-rejection bound holds when the actual protocol ensures conditional validity.The sufficient protocol fixes candidate details and planned cumulative sample sizes at registration, excludes reused screening outcomes, and avoids outcome-selective pair inclusion.Source: §C.4 · pp. 27–28

C.5 TRAINING ALGORITHM AND DATA ROUTING

  • Each training step rolls out natural and, when applicable, paired candidate-control trajectories, re-scores actions, fits value heads, updates AnchorTB, accumulates test outcomes, and saves state.Natural healthy non-paired trajectories supply task, category, and global baseline statistics; paired paths can supply AnchorTB regression and structural buckets.Source: §C.5 · pp. 28–29

C.6 PROOFS OF THE MAIN-TEXT PROPOSITIONS

  • The main-text propositions combine legal-repair history preservation, the action coefficient and estimator components, and candidate-slot transitions with nominal test accounting.Their statistical interpretation relies on fixed-look validity and the conditional whole-run result.Source: §C.6 · p. 29

D EXPERIMENTAL DETAILS

The experimental details specify the benchmark splits, metrics, baselines, transfer protocol, and diagnostics used to evaluate EvoSteer. They also report results for alternate skill authors and resource use.

D EXPERIMENTAL DETAILS

  • The six IID benchmarks provide training tasks with disjoint test items, while six OOD benchmarks are evaluation-only; most test sets contain 128 items.AIME 2026 uses 30 test problems; the passage also specifies the MATH-Hard and GPQA subsets.Source: D EXPERIMENTAL DETAILS · p. 29
  • Metrics include answer exact match and F1, accuracy, Pass@1, success rate, and SWE-Bench Verified resolved rate, each defined for its benchmark task.ALFWorld success rate counts task completion within 50 steps.Source: D EXPERIMENTAL DETAILS · p. 29
  • Unless labeled otherwise, methods use Qwen3.5-9B as frozen executor and trained model, share training tasks, and use baselines’ reported best configurations.The DeepSeek-V4-Flash column prompts that model directly; GRPO† fine-tunes the backbone, unlike Figure 6 GRPO within EvoSteer’s architecture.Source: D EXPERIMENTAL DETAILS · p. 29
  • At test time the trained orchestrator, value head, and skill library are frozen, and transfer swaps only the executor; OOD benchmarks use matched IID task types.The six-run aggregation? No: every test score is a mean over five independent runs.Source: D EXPERIMENTAL DETAILS · pp. 30–31
  • At most 1.56 points, self-written skills lower the averages; the stronger author raises every average, and all three settings stay above Table 1’s strongest baseline in every column.Table 4 reports five-run means, averaging Ans EM over question-answering benchmarks and Acc. over the others.Source: D EXPERIMENTAL DETAILS · p. 30, Table 4 · p. 30
  • Training EvoSteer for 240 steps used 95.98 H800 GPU hours and 1,580,691,323 tokens; Figure 5–6 diagnostics define reference, anchor-only, skill-gain, edit, and replanning comparisons.Every test score is averaged over five independent runs, with standard deviations also reported for Table 1.Source: D EXPERIMENTAL DETAILS · p. 31

E.1 CODE THAT PASSES THE VISIBLE TEST

A code result passes the visible test yet fails hidden tests, so the orchestrator uses a value drop to trigger a mid-run rerun. The corrected code passes all three tests.

E.1 CODE THAT PASSES THE VISIBLE TEST

  • The episode ends with the corrected planner set as output, all three tests passing, and reward 1.0.The orchestrator sets the output after the rerun, then stops.Source: §E.1 · p. 33
  • The orchestrator reruns code after its value estimate drops by 0.216 to 0.353, and the rewrite passes all three hidden tests.The code had looked finished and passed the only visible test, but was wrong on a hidden case.Source: §E.1 · pp. 31, 33
  • The first code counts equal pairs, returning 1 for (1, 2, 2) instead of the expected 2; the rerun counts equal numbers and passes all three tests.The task’s sole visible assertion was (1,1,1) == 3, which both implementations passed.Source: §E.1 · pp. 31–33
  • The bound skill warns against inferring behavior from a single assertion, and the corrected rewrite follows that pitfall guidance.Four of the other five rollouts fail; the only other passing rollout binds the same skill.Source: §E.1 · pp. 31, 33

Related papers

Loading 2609.38661v2…