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

cs.AISep 29, 2026

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

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

Organizations: The Chinese University of Hong Kong, Shenzhen, China · Dalian University of Technology, China · Fudan University, China · University of Oxford, UK · North China Electric Power University, China · The University of Texas Health Science Center at Houston, USA

Abstract

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.

Figures & tables

Figure 1: Outputs that look plausible can still be headed for failure. EvoSteer reads a low continuation estimate off the execution record and edits the running team, here routing the checker’s report back to the solver; dashed: the same team left unedited.

Figure 2: Three lines of work and ours. (a) Post-hoc evolution revises the team only after the run. (b) Outcome-driven optimization spreads one terminal reward over every step. (c) Skill evolution admits by judges or replay. (d) EvoSteer edits the team inside the same run, deciding from measured execution features and a reference value estimate, and admits a skill only after a sequential test.

Figure 3: EvoSteer architecture. Top:

\pi_{\theta}

builds and runs the team from execution features

f_{t}

and reference estimate

\hat{v}_{k}

; rerun and new edges are ordinary actions. Bottom left: AnchorTB balances subtrajectories against

\rho

;

\tilde{u},\delta

abbreviate trajectory-specific flow estimates and residuals. Bottom right: paired rollouts and a sign test under a shared nominal

\alpha

budget promote or retire candidate

\sigma

Panel of Figure 4 — Figure 4: AnchorTB on a three-action history: ① score each action against the frozen reference; ② anchor each state with a measured, stop-gradient anchor (blue) and a learned residual (pink); ③ form all $K_{3}=6$ span residuals; ④ sum each action’s spans into its coefficient.

Variant	IID						OOD
	HotpotQA	NQ-Open	MedQA	AIME	MBPP+	ALFWorld	TriviaQA	MuSiQue	GPQA	MATH	SWE	WebShop
	Ans EM	Ans EM	Acc.	Acc.	Pass@1	SR	Ans EM	Ans EM	Acc.	Acc.	Resolved	SR
Qwen3.5-9B (frozen)	57.66	23.59	71.41	48.67	78.91	46.88	44.22	39.22	61.72	89.06	15.94	32.66
EvoSteer arch., untrained	82.34	73.28	82.97	53.33	87.66	73.59	90.47	71.88	75.31	90.00	29.53	69.84
Fixed orchestration paradigms
Single agent with tools	75.94	67.19	80.78	48.67	85.63	70.16	86.25	61.41	70.31	89.84	27.03	66.09

Table 2: Component ablation and paradigm comparison (untrained: initial

\pi_{\theta}

). Paradigms (same executor and budget) fix the team before execution: a ReAct-style agent with all tools, a hand-designed template, a planner that writes the graph once, and a workflow searched offline on training tasks. Ablations:

-

interleaved execution builds the graph first;

-

execution features drops

f

from the state of

\pi_{\theta}

;

-

learnable repair masks rerun and drop ;

-

reference value head withholds

\hat{v}_{k}

and

\Delta\hat{v}

;

-

measured flows learns

u_{q}

as a free scalar;

-

flow corrections turns off

c(g)

and

b_{\psi}

;

-

skill evolution runs without any skills;

-

sequential validation admits after

k=5

successes.

Panel of Figure 5 — Figure 5: Backbone transfer and training dynamics. (a) IID scores of six other frozen executors (dashed) and with the same trained orchestrator (solid); the radius is linear over 20–80 on the inner half and 80–100 on the outer half. (b) Accuracy of $\pi_{\theta}$ and of the frozen $\rho$ , and loss against the anchor-only level, over 240 steps. (c) OOD scores per task domain.

Panel of Figure 6 — Figure 6: Objective comparison and mechanism analysis (definitions in Appendix D ). (a) OOD scores and cost per training objective. (b) Row minus column, IID mean (pp); TTB: tempered TB. (c) AUC for predicting reference-rollout correctness. (d) Paired skill gain, admitting all or only validated candidates. (e) In-run edits by type and outcome. (f) Gain of value-guided replanning in training.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Group	Setting
Backbones	orchestrator, reference, executor: one shared base model ( Qwen3.5-9B ); skill author: DeepSeek-V4-Flash, called only in author windows
Adapter	LoRA rank 64, $\alpha=128$ , on q/k/v/o_proj, out_proj, and in_proj_qkv; AdamW ( $\beta_{1}=0.95$ ), lr $5\times 10^{-6}$
Heads	$b_{\psi}$ : zero-initialized MLP on $[h_{\rho};f]$ ; value head: two-layer MLP on $30{+}6$ inputs (one task-type slot per IID benchmark)
AnchorTB	$\beta=2$ ; all subtrajectories equally weighted; gradient-norm clip 1.0
Baselines	$(\kappa_{q},\kappa_{c},\kappa_{g})=(0.5,4,2)$ ; prior success rate capped at 20 counts; bucket minimum 8; pseudo-count $n_{0}=8$ ; correction bound $c_{\max}=0.25$
Skill slots	at most three validated skills and one candidate per task type

Appendix

Table 3: Configuration of the frozen implementation used for the experiments.

	IID avg.		OOD avg.
Skill author	Ans EM	Acc.	Ans EM	Acc.
DeepSeek-V4-Flash (main setting, Table 1 )	88.67	87.42	90.08	78.55
GPT-5.6-Luna	90.16	89.28	90.55	79.34
Qwen3.5-9B (the executor)	87.81	86.64	88.98	76.99

Appendix

Table 4: EvoSteer with different skill authors: five-run means averaged as in Table 1 (Ans EM over the question-answering benchmarks, Acc. over the others).

Explore similar work

SkillFlow: Flow-Driven Recursive Skill Evolution for Agentic Orchestration
May 13, 2026Mingda Zhang, Tiesunlong Shen, Haoran Luo +4Skill Evolution Orchestration
The Chinese University of Hong Kong, Shenzhen · National University of Singapore · Nanyang Technological University +1
Focus Is All You Need: Adaptive Goal-aware Attention Orchestration for Multi-Agent Graph Systems
Jul 26, 2026Mingzhou Fan, Siyuan Xu, Mingxuan YuanReasoning Paths
EXG: Self-Evolving Agents with Experience Graphs
May 18, 2026Yuxin Jin, Siyuan Zhang, Hanchen Wang +3Self-Evolving Agents Reasoning Benchmark
University of Technology Sydney Sydney, Australia · The University of New South Wales Sydney, Australia

May 13, 2026, cs.AIJ/K move · Enter open · S save

SkillFlow: Flow-Driven Recursive Skill Evolution for Agentic Orchestration

Mingda Zhang, Tiesunlong Shen, Haoran Luo, Wenjin Liu+3

The Chinese University of Hong Kong, Shenzhen · National University of Singapore · Nanyang Technological University+1

Skill Evolution Orchestration

Open paper AskPDF arXiv

In recent years, a variety of powerful LLM-based agentic systems have been applied to automate complex tasks through task orchestration. However, existing orchestration methods still face key challenges, including strategy collapse under reward maximization, high gradient variance with opaque credit assignment, and unguided skill evolution whose decisions are typically made by directly prompting an LLM to judge rather than derived from principled training signals. To address these challenges, we propose SkillFlow, a flow-based framework that takes a trainable Supervisor as the agent and a structured environment with dynamic skill library and frozen executor, automating task orchestration through multi-turn interaction. SkillFlow employs Tempered Trajectory Balance (TTB), a regression-based flow-matching loss that samples trajectories proportional to reward, preserving diverse orchestration strategies rather than collapsing to a single mode. The same flow objective yields a jointly learned backward policy that provides transparent per-step credit assignment at zero additional inference cost. Building on these flow diagnostics, a recursive skill evolution mechanism determines when to evolve, what skills to create or prune, and where decision gaps lie -- closing the loop from training signal to autonomous capability growth. Experimental results on 14 datasets show that SkillFlow significantly outperforms baselines across question answering, mathematical reasoning, code generation, and real-world interactive decision making tasks. Our code is available at https://anonymous.4open.science/r/SkillFlow-E850.

Abstract

Explore similar work

SkillFlow: Flow-Driven Recursive Skill Evolution for Agentic Orchestration

Focus Is All You Need: Adaptive Goal-aware Attention Orchestration for Multi-Agent Graph Systems

EXG: Self-Evolving Agents with Experience Graphs