- Rating
- 4(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper presents EvoSteer, an online self-evolving graph orchestration framework for LLM-based multi-agent systems. In contrast to existing post-hoc optimization approaches, EvoSteer employs a trainable orchestrator to dynamically construct and refine communication graphs during task execution, guided by runtime feedback and learned value estimates. The framework incorporates online graph editing and repair, Anchored Trajectory Balance for reference-relative credit assignment across subtrajectories, and Validated Skill Admission, which leverages paired rollouts and sequential statistical testing to regulate the admission of reusable skills. Extensive experiments across 12 benchmarks spanning question answering, mathematical reasoning, code generation, and interactive decision-making demonstrate consistent improvements over existing orchestration and skill-evolution baselines. Further ablation studies and cross-backbone evaluations substantiate the effectiveness and transferability of the proposed framework.
Critical strengths
- Clear problem formulation and compelling research motivation. The paper clearly identifies the limitations of post-hoc orchestration and provides a well-motivated formulation that emphasizes the importance of dynamic graph adaptation and repair during task execution.
- Interesting and well-designed optimization approach. The proposed AnchorTB introduces a reference-anchored subtrajectory credit assignment mechanism that provides more informative learning signals for optimizing orchestration policies.
- Comprehensive experimental evaluation. The paper presents extensive experiments across 12 benchmarks, complemented by thorough ablation studies and cross-backbone evaluations that demonstrate empirical performance and generalizability.
Critical weaknesses
- Gap between theoretical guarantees and practical implementation. The theoretical guarantees of AnchorTB rely on shared state flows, whereas the practical implementation employs trajectory-dependent estimates. This discrepancy raises concerns about the extent to which the theoretical analysis supports the implemented optimization procedure.
- Substantial computational overhead and limited efficiency analysis. The framework introduces considerable computational overhead through repeated training rollouts and skill validation. However, comprehensive end-to-end cost-efficiency comparisons with existing baselines are lacking, making it difficult to assess whether the performance improvements justify the additional computational expense.
Questions for authors
- Could the authors clarify whether the theoretical guarantees of AnchorTB extend to its practical implementation, particularly when trajectory-dependent estimates are employed?
- How does EvoSteer perform relative to existing baselines under matched inference-time token and computational budgets?
4 comments
Response to Reviewer mHBG (2/2): Cost and matched budgets
W2 / Q2. Cost and matched budgets.
EvoSteer scores highest at a per-problem test cost within the range of the other orchestrators, and its one-time training needs fewer GPU hours than any other trained orchestrator, with skill validation taking 13.7% of its training tokens. The table reports both (IID / OOD: mean of the six benchmarks), with each baseline in its authors' configuration on the same executor and training tasks:
| Method | Training: H800 hours / tokens | Test tokens / problem | IID avg | OOD avg |
|---|---|---|---|---|
| Qwen3.5-9B | – | 3.2k | 54.52 | 47.14 |
| Self-consistency@6 | – | 19.7k | 56.92 | 48.26 |
| Best-of-N@4 | – | 20.3k | 55.47 | 47.97 |
| SFT | 7 / 3.0M | 3.6k | 52.32 | 48.41 |
| GRPO† | 35 / 0.8B | 4.9k | 55.91 | 49.35 |
| AFlow (search) | API / 2.75B | 16.0k | 77.46 | 70.52 |
| AgentFlow | 124 / 1.73B | 31.6k | 79.80 | 75.89 |
| FlowSteer | 231 / 4.67B | 43.4k | 82.11 | 77.84 |
| SkillFlow | 189 / 1.42B | 22.0k | 83.06 | 78.05 |
| EvoSteer | 96 / 1.58B | 21.7k | 87.84 | 82.40 |
Q2. Matched test-time budgets. Test tokens count every orchestrator and agent call, prefill plus decode, averaged over the twelve benchmarks. With the same backbone and nearly the same tokens (90% and 94% of EvoSteer's), self-consistency and best-of-N add at most 2.4 points on average over a single call, whereas EvoSteer adds 33.3 IID and 35.3 OOD points: extra samples cannot supply retrieval, execution feedback or in-run repair. Among orchestrators, EvoSteer uses fewer tokens than AgentFlow and FlowSteer, about as many as SkillFlow and more than AFlow (which scores over 10 points lower), yet is best on all twelve benchmarks (Table 1).
Training cost. EvoSteer trains once, for 240 steps, in 96 H800 hours, fewer than AgentFlow (124), SkillFlow (189) and FlowSteer (231); its 1.58B tokens are below those of AgentFlow, FlowSteer and AFlow's search (2.75B) and close to SkillFlow's (1.42B). Only the single-model fine-tunes, SFT and GRPO†, use fewer GPU hours, and they score over 30 points lower. Of EvoSteer's tokens, 26.5% are natural rollouts, 13.7% paired rollouts for skill validation, 59.8% prefill-only rescoring for the AnchorTB loss, and 0.004% the skill author. This cost is paid once: the trained orchestrator transfers unchanged to six other executors (Sec. 5.2), and at test time no reference, paired or validation rollouts are drawn (App. D). Skill validation is also what keeps admitted skills useful, since admitting every candidate instead lowers MedQA and AIME (Fig. 6d).
We thank the reviewer again. All additional experiments and revisions have been incorporated into the revised version. If our responses and revisions address your concerns, we would be deeply grateful if you could kindly reconsider raising the score further. Thank you very much!
Response for the Rebuttal
Thank you for the detailed response. The authors have addressed most of my concerns by clarifying the relationship between AnchorTB’s theoretical guarantees and its practical implementation. They have also provided valuable computational cost comparisons that further strengthen the paper.
These clarifications have increased my confidence in the paper, and I will raise my score.
Thank you very much for your kind feedback and for raising your score.We are glad that our response has addressed your concerns, and we would greatly appreciate it if you could also raise your confidence score. Thank you again for your time and constructive comments.
Response to Reviewer mHBG (1/2): Theory and the implemented optimization
We thank the reviewer for the positive assessment and valuable suggestions, and answer each point below.
W1 / Q1. Theory and implementation.
In short, yes: the guarantees that describe the implemented optimization step hold exactly for the trajectory-dependent estimates, and the distribution-level guarantee holds for the shared flow used on the trained policy's own trajectories.
Why a shared flow is required, and where the implementation departs from it. A shared flow assigns one value to each state, whichever continuation is later scored. This is the definition of a flow under which the classical balance results are proven (Malkin et al., 2022; Bengio et al., 2023; Madan et al., 2023), including the reference-relative form we build on (Venkatraman et al., 2024), and without it zero loss would say nothing about the sampled distribution (Remark B.3). Our implementation meets it except in one deliberate place. The structure correction is read from the previous batch and the learned residual is a function of the state, so both are shared, and the task anchor is the same for every trajectory of the trained policy. Only the reference's own rollouts, which also supply the task anchor, leave themselves out, so that a rollout's reward does not enter its own anchor, as in RLOO (App. B.1–B.2). Keeping it in would make the anchor exactly shared but pull it toward that rollout's outcome, and a learned shared scalar is biased: in Prop. B.9 it settles at ElogRβ rather than logZ.
Q1. Which guarantees extend to the implementation. The first group concerns a single recorded trajectory. These results use only the anchor values on that trajectory and never compare trajectories, so a different value on another trajectory does not affect them (Prop. B.1), and they are exactly what the implementation computes. The loss on a trajectory is zero exactly when every span on it balances; each action's coefficient is the sum of the residuals of the spans containing it, which is the per-action credit of Prop. 2; and the loss gradient for the orchestrator is this coefficient times the action's log-probability gradient, with the measured anchors detached (Remark A.6, Lemma A.17). Changing the anchors moves residuals, loss and coefficients only by a bounded amount (Prop. B.5), and the estimator properties, such as the measured anchor's range and the bound on v^'s calibration error (Prop. B.8), also hold as implemented.
The second group, that balanced flows give the target distribution and nearly balanced ones a nearly correct distribution (Props. A.8, A.15), compares one state across all its continuations and therefore needs a shared flow. The flow on the trained policy's own trajectories is exactly such a flow, so whenever it nearly balances on every reference-supported history, the policy is provably close to the target (Prop. A.15); on reference rollouts, the self-exclusion changes residuals and credit within the bound of Prop. B.5. The theory thus specifies the exact update the implementation performs, and what a nearly balanced solution guarantees about the trained policy.