Source-linked AI summary
TROVE: Adaptive Agent Skill Orchestration via Trace-Grounded Route Validation and Editing
Tianxing Wang, Mingming Zhao, Shuai Huang, Huiyang Xu, Chaoyue Niu, Shengzhong Liu, Fan Wu
TL;DR
Pre-execution workflow commitments become stale when intermediate outcomes invalidate pending continuations, forcing agents to waste computation or discard progress. TROVE distills workflow-search traces into skills and an outcome-conditioned graph, then selectively retains, inserts, or replaces route segments after each committed skill. Across code, question-answering, and mathematics tasks, it improves the quality-efficiency trade-off over established orchestration baselines, with the strongest quality gains when outcomes change the appropriate continuation.
Problem
Existing orchestration methods make structural decisions before decisive outcomes are observed, so pending continuations can become invalid as execution unfolds.
Method
TROVE distills evaluated workflow-search traces into executable composite skills and an outcome-conditioned transition graph, then uses one-step commitment with retain, insert, or suffix-replacement route edits.
Results
Across 18 backbone-benchmark settings, TROVE achieves the best or tied-best task score in 15 and the shortest online time in 16, outperforming dataset-level, query-level, and graph-constrained baselines.
Takeaways & Limitations
Selective route editing improves task quality and online efficiency, with quality gains largest when intermediate outcomes change the appropriate continuation and early termination saving time on near-saturated tasks.
Abstract
from arXiv · showhide
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.
1 Introduction
Agent orchestration must adapt a provisional workflow when runtime outcomes invalidate its pending continuation. TROVE addresses this by preserving useful executed structure while making only the smallest sufficient route edits.
- Motivation: Runtime outcomes can make queued agent steps stale, causing unnecessary errors and computation when workflows continue without validation.Examples include required revision after review, redundant verification after success, and invalid downstream steps after tool failure.
- Motivation: TROVE validates the pending route after each execution boundary and preserves the executed prefix, valid steps, and artifacts while replanning only an invalid suffix.This contrasts with restarting or regenerating the entire future.
- TROVE: TROVE distills evaluated workflow-search traces into executable composite skills and an outcome-conditioned transition graph.Stable fragments become reusable skills, while outcome-dependent continuations remain explicit.
- TROVE: Online, TROVE commits to one top-level skill, then retains a valid successor, inserts a local response, or replaces only the invalid suffix after observing the outcome.Its proposal horizon spans multiple skills, but its commitment horizon remains one action.
- Evaluation: Across 18 backbone-benchmark settings, TROVE achieves the best or tied-best task score in 15 and the shortest online time in 16.Relative to AFlow, it improves task score in 16 settings and reduces time in 16 settings.
2 Related Work
Prior work constructs workflows, skills, or execution-time adaptations at different structural levels. TROVE instead edits the unresolved suffix of a task-specific provisional route while preserving its executed prefix and still-valid intent.
- Automated Workflow Construction: Workflow-construction methods optimize operation-level graphs, dataset-level workflows, or complete agent-system designs from task feedback and prior designs.GPTSwarm optimizes graph prompts and connectivity, AFlow searches reusable executable workflows, and ADAS programs complete agent systems.
- Skill-Oriented Methods: Skill-oriented methods vary between predefined executable policies, synthesized programs, and reusable behaviors extracted from prior interactions.SayCan selects actions using linguistic relevance and environmental feasibility, while Code as Policies synthesizes executable programs.
- Execution-Time Planning and Route Adaptation: Execution-time controllers differ in how much future structure they preserve after feedback, ranging from next-action generation to adaptation within state machines or workflow graphs.ReAct generates the next action, plan-level methods refine plans, and LAS adapts within a predefined workflow DAG.
- Execution-Time Planning and Route Adaptation: TROVE retains a valid successor, inserts a transition-supported local response, or replaces the suffix only when broader replanning is required.This preserves the executed prefix without restricting adaptation to a predefined DAG.
3 Design of TROVE
TROVE addresses continuation invalidation by preserving valid route structure while editing only the smallest invalid portion. It builds reusable skills and outcome-conditioned transitions offline, then performs one-step online execution with selective retention, insertion, or suffix replacement.
- Problem Formulation: Continuation invalidation occurs when observed outcomes make a planned successor missing, unnecessary, incomplete, or unable to make progress.
- Problem Formulation: TROVE commits to one top-level skill at a time, retaining the executed prefix and revising only the unexecuted route when outcomes invalidate the continuation.It occupies a middle ground between wholesale workflow replacement and step-wise replanning.
- Offline Experience Extraction: Offline, TROVE standardizes operators as atomic skills, reuses evaluated search traces, and organizes stable local fragments into composite skills.Composite promotion requires stable ordering and dependencies, a coherent subgoal, a consistent interface, and execution independent of the outer route.
- Offline Experience Extraction: Outcome-dependent continuations remain explicit in a transition graph whose edges derive from evaluated local workflow modifications rather than skill adjacency alone.Offline score and time changes provide comparative evidence for retaining responses, but are not online routing inputs.
- Online Skill Execution and Route Revision: Online, a planner proposes a provisional route while the controller executes only its first skill and observes the resulting boundary outcome.The graph supplies bounded continuation hints and outcome-conditioned candidates rather than constructing a complete workflow.
- Online Skill Execution and Route Revision: When the pending successor is invalid, TROVE queries the transition graph and chooses a supported response or broader replacement while preserving completed work.The graph may provide a candidate for local route revision; otherwise, the controller can use replanning for the unexecuted suffix.
4 Evaluation
TROVE is evaluated on six held-out benchmarks across three LLM backbones against orchestration methods spanning offline workflow optimization, query-level architecture selection, and online scheduling. It generally improves task quality and reduces online time, with route-edit patterns and ablations clarifying when adaptation helps most.
- Experimental Setup: TROVE is evaluated on six code-generation, mathematical-reasoning, and question-answering benchmarks using held-out test partitions and three LLM backbones.The benchmarks are HumanEval, MBPP, MATH, GSM8K, DROP, and HotpotQA; test-time structures are frozen before evaluation.
- Experimental Setup: The comparison covers dataset-level workflow optimization, query-level pre-execution architecture selection, and node-level online scheduling.These categories correspond to AFlow, MaAS, and LAS, respectively.
- Main Results: Against AFlow, TROVE improves score in 16 settings by 0.12–31.37 points and reduces time in 16 by 2.9–86.7%.Against MaAS, it improves or ties score in 17 settings and reduces time in all 18; on LAS-supported code settings, it improves score in five of six and reduces time in all six.
- Efficiency: Across six DeepSeek-V4-Flash test partitions, TROVE uses 13.45M online tokens versus AFlow’s 21.11M, a 36.3% reduction.The reduction is driven primarily by MBPP and GSM8K, while DROP and HotpotQA require more tokens under TROVE.
- Task and Backbone Differences: Quality gains are larger when task difficulty changes the appropriate continuation, whereas high-scoring or evidence-heavy tasks mainly benefit through efficiency.TROVE gains 6.79 points over AFlow on DeepSeek-V4-Flash MATH while reducing time by 62.1%; GSM8K is near a performance ceiling but still shows large time savings.
- Route Adaptation: Runtime route edits occur on 54.20% of HumanEval samples, 98.97% of MATH samples, and 100% of GSM8K samples, but only 2.88% of HotpotQA samples.For HumanEval, edits indicate corrective adaptation; for mathematics, they mostly reflect terminal pruning after early completion; QA generally retains the initial route.
- Ablation Study: Removing composite skills reduces HumanEval accuracy by 13.74 points and adds 8.94 minutes, while removing insertion reduces accuracy by 9.93 points and adds 14.74 minutes.Removing replacement decreases accuracy by only 1.53 points but increases time by 15.79 minutes, indicating a stronger efficiency than correctness role in this setting.
5 Conclusion
The paper frames continuation invalidation as a distinct orchestration problem and proposes TROVE to validate and minimally edit unexecuted routes while preserving completed work. Across six benchmarks and three LLM backbones, selective route revision improves task quality and online efficiency over several orchestration baselines.
- Conclusion: Continuation invalidation requires validating and minimally editing an unexecuted route when runtime outcomes undermine the planned continuation.The formulation preserves completed work while revising only the affected future route.
- Conclusion: TROVE distills evaluated workflow-search trajectories into executable composite skills and an outcome-conditioned transition graph, then combines them with a retain–insert–replace controller.The controller is designed to preserve useful progress while responding to runtime feedback.
- Conclusion: Experiments across six benchmarks and three LLM backbones show that selectively revising provisional skill routes improves task quality and online efficiency over dataset-level, query-level, and graph-constrained orchestration.The conclusion positions selective route editing as a broader principle for adaptive agent orchestration.