Agents tend to optimize, select, or constrain execution structures before decisive runtime outcomes are observed. However, such pre-execution commitment creates an orchestration bottleneck: when intermediate evidence invalidates the pending continuation, agents must either execute stale steps or replan broadly, compounding errors, wasting computation, and discarding progress. We thus propose Trace-grounded Route Orchestration via Validation and Editing (TROVE), which revises only what runtime evidence invalidates. Offline, TROVE distills evaluated workflow-search traces into atomic and composite skills and an outcome-conditioned transition graph, preserving stable fragments while exposing outcome-dependent decisions. Online, it treats a planned route as provisional: after committing one top-level skill, the controller retains a valid continuation, inserts a trace-supported local response, or replaces only the invalid suffix. Evaluation across code-generation, question-answering, and math reasoning benchmarks with different LLM backbones show that TROVE delivers a stronger quality-efficiency trade-off than existing baselines of dataset-level optimization, query-level architecture selection, and graph-constrained scheduling. Quality gains are largest when outcomes change the appropriate continuation, whereas early termination yields substantial efficiency gains on near-saturated tasks. Ablations further show that composite skills capture most offline benefits, insertion enables local correction, and suffix replacement primarily improves efficiency. These findings establish selective route editing as a general principle for adaptive agent orchestration.
Figures & tables
Figure 1: Motivating HotpotQA example. After review (2) detects missing evidence in draft (1), AFlow still executes its fixed format suffix and scores 0. Our TROVE instead applies Insert to add revise (3), followed by Replace to substitute stop (4) for the obsolete suffix, preserving the useful prefix and raising the score to 1.
Figure 2: Offline experience extraction and online route revision in TROVE. Offline, standardized atomic skills are organized into stable composite skills and a transition graph (left). Online, a planner proposes a provisional route, but the controller executes only its head and observes the resulting state. The pending suffix is then retained, extended by inserting a locally supported skill, or replaced through replanning. Only the selected next skill is committed before the execution–observation loop repeats (right).
Backbone
Method
Code
QA
Math
HumanEval
MBPP
DROP
HotpotQA
MATH
GSM8K
Score ↑
Time ↓
Score ↑
Time ↓
Score ↑
Time ↓
Score ↑
Time ↓
Score ↑
Time ↓
Score ↑
Time ↓
DeepSeek-V4-Flash
AFlow ( Zhang et al. 2025b )
93.89
21.75
91.79
43.10
88.50
15.56
78.58
25.41
74.07
68.88
96.02
57.73
MaAS ( Zhang et al. 2025a )
87.02
13.52
81.82
35.13
81.64
22.98
77.37
26.60
68.11
131.83
96.68
108.23
LAS ( Xiang et al. 2026 )
94.66
13.81
92.08
22.02
–
–
–
–
–
–
–
–
Our TROVE
97.71
8.10
93.55
12.63
90.39
14.89
80.16
23.97
80.86
26.08
97.16
9.63
Table 1: Combined task quality and online elapsed time on the held-out test partitions. Score is reported in percent and time in minutes. HumanEval and MBPP use pass@1, DROP and HotpotQA use mean token F1, and MATH and GSM8K use accuracy. Within each backbone and benchmark, bold and underlining independently mark the best and second-best value for each metric. “–” indicates that LAS does not publicly release a trained gate for that non-code benchmark.
Figure 3: Sample-level incidence of TROVE’s online route edits with DeepSeek-V4-Flash. Bars stack Insert and Replace ; labels give the total percentage of samples whose realized route differs from its proposal. Terminal pruning counts as replacement, while timeout-incomplete paths and identity confirmations are excluded.
Variant
Accuracy (%) ↑
Time (min) ↓
Full TROVE
92.37
24.36
Without Offline
77.86
33.62
Without Composite
78.63
33.30
Without Insert
82.44
39.10
Without Replace
90.84
40.15
Table 2: Qwen3-8B HumanEval test ablation. Time is online test elapsed wall time.
Large language model agents increasingly rely on execution traces to master complex interactive tasks. However, current paradigms are bottlenecked by shallow trajectory retrieval and flat skill summarization, fundamentally ignoring the temporal dependencies and outcome-conditioned topology of agent behavior. We introduce Trace2Tower, a transition-aware EigenTrace framework that distills raw trajectories into a robust skill hierarchy. Trace2Tower abstracts step-level interactions into canonical events, constructing a unified graph governed by semantic compatibility, transition dynamics, and outcome evidence. Through a novel contrastive spectral decomposition, it isolates stable, success-aligned behavioral modes while rigorously suppressing failure-prone shortcuts. These modes organically populate a dynamic skill tower of action templates, procedural routines, and overarching task strategies, continuously refined via verifier-guided feedback. On ALFWorld, Trace2Tower achieves 87.31% success requiring only 10.35 steps and 0.26 invalid actions; on WebShop, it reaches 50.67% exact success. Across both benchmarks, Trace2Tower significantly outperforms existing baselines in task mastery and context-efficient experience reuse.
Jiazheng Sun, Boyu Yang, Binhao Yuan +2
College of Computer Science and Artificial Intelligence, Fudan University Shanghai 200433, China
Compound AI systems promise capabilities beyond those of individual models, yet their success depends critically on effective orchestration. Existing routing approaches face two limitations: (1) input-level routers make coarse query-level decisions that ignore evolving task requirements; (2) RL-trained orchestrators are expensive to adapt and often suffer from routing collapse, repeatedly invoking one strong but costly option in multi-turn scenarios. We introduce SkillOrchestra, a framework for skill-aware orchestration. Instead of directly learning a routing policy end-to-end, SkillOrchestra learns fine-grained skills from execution experience and models agent-specific competence and cost under those skills. At deployment, the orchestrator infers the skill demands of the current interaction and selects agents that best satisfy them under an explicit performance-cost trade-off. Extensive experiments across ten benchmarks demonstrate that SkillOrchestra outperforms SoTA RL-based orchestrators by up to 22.5% with 700x and 300x learning cost reduction compared to Router-R1 and ToolOrchestra, respectively. These results show that explicit skill modeling enables scalable, interpretable, and sample-efficient orchestration, offering a principled alternative to data-intensive RL-based approaches. The code is available at: https://github.com/jiayuww/SkillOrchestra.
Jiayu Wang, Yifei Ming, Zixuan Ke +3
University of Wisconsin-Madison · Salesforce AI Research
Efforts to improve LLM-based agents typically focus on modifying the agent itself, yet success also depends on the environment in which an agent acts. Tools mediate this interaction: a tool's description shapes how an agent calls it, and its implementation determines the results and errors the agent receives afterwards. Many tools, such as APIs and MCP servers, are shared by many agents and maintained by providers who cannot change those agents. We introduce AT-AT (Automatic Tool Optimization from Agent Traces), an agentic tool optimizer that improves a shared toolset offline from historical agent executions while holding the agents fixed. A lightweight coding agent reads agent trajectories and their evaluation results, and selectively edits tool descriptions and, when permitted, implementations. On τ2-bench-verified, AT-AT achieves the highest task completion rates in the Airline and Telecom domains at lower cost than strong prompt- and tool-optimizer baselines, and its Telecom gain is statistically significant under paired permutation tests. Optimizing the tools within a coding agent harness also improves held-out performance on TerminalBench-2 and TBLite. When applied to three production MCP servers at a large enterprise, AT-AT lowered cost or tool error rates on every server and increased held-out task passes on one. By turning accumulated execution traces into updates to shared tool environments, AT-AT provides a path toward continual improvement of agent systems through environment-side learning.