PaperlayerView exact revision on arXiv

Source-linked AI summary

DynSTEER: Dynamic Stage-wise Trajectory Evaluation and Execution-time Review for Agents

Zhichao Shi, Xuhui Jiang, Wenjie Zhang, Xiaojun Wu, Cehao Yang, Chengjin Xu, Jian Guo, Yuanzhuo Wang

arXiv:2609.14637v3cs.AI

TL;DR

Whole-trajectory review can be too coarse to locate failures, while atomic-step scoring is noisy and single-reference evaluation does not capture diverse valid paths. DynSTEER evaluates milestone-bounded stages, adapts review, compiles path-tolerant milestone graphs, and terminates unrecoverable executions. It reports over 85% higher discriminability than whole-trajectory evaluation and saves 17.74% of execution steps.

  • Problem

    Whole-trajectory review is too coarse to capture concrete failures and evidence, atomic-step scoring is noisy, and single-reference evaluation struggles to represent diverse valid paths.

    Source: §1 · p. 1, §2.1 · p. 3

  • Method

    DynSTEER segments rollouts at key execution nodes, adapts multi-level review to stage results, compiles path-tolerant milestone graphs from task inputs, and terminates unrecoverable executions.

    Source: §1 · pp. 1–2

  • Results

    DynSTEER improves discriminability by over 85% versus whole-trajectory evaluation and saves 17.74% of execution steps.

    Source: §5 · p. 10

  • Takeaways & Limitations

    DynSTEER provides a principled and cost-aware foundation for LLM-agent evaluation and optimization.

    Source: §5 · p. 10

    Milestone graph construction uses evaluator-visible task inputs, not hidden reference paths or terminal unit tests.

    Source: §3.1 · p. 3

Abstract

from arXiv · show

Large language model agents are increasingly deployed for long-horizon task execution, raising a central granularity question for trajectory evaluation: whole-trajectory verification is too coarse to capture concrete failures and their associated evidence in long trajectories, while atomic-step scoring is too fine-grained, noise-sensitive, and computationally expensive. This granularity gap makes a single-reference trajectory paradigm inadequate for assessing the rich space of valid agent execution paths and delays timely feedback and early stopping in long-horizon tasks. To address these issues, we propose DynSTEER, a dynamic stage-wise framework for agent trajectory evaluation. DynSTEER bridges the granularity gap through stage-wise dynamic evaluation that segments rollouts at key execution nodes and adapts its multi-level review strategy based on stage-level results; it compiles a path-tolerant milestone graph from available task inputs to preserve diverse legal paths without reference leakage; and it supports terminating unrecoverable agent executions to curb resource waste. Experimental results show that DynSTEER improves evaluation discriminability by over 85\% compared with whole-trajectory evaluation and saves 17.74\% of execution steps. The code is available at https://github.com/zhichao-stone/DynSTEER

1 INTRODUCTION

DynSTEER addresses the mismatch between coarse whole-trajectory review and noisy atomic-step scoring, while accommodating diverse valid paths and enabling earlier intervention. It combines stage-wise adaptive review, path-tolerant milestone graphs, and early termination; reported experiments improve discriminability and reduce execution steps.

1 INTRODUCTION

  • Whole-trajectory verification is too coarse for locating failures, while atomic-step scoring lacks context and treats ordinary retries or harmless observations as noise.A single-reference paradigm also struggles to reflect diverse valid execution paths, and post-hoc review can allow already-failed runs to continue wasting resources.Source: §1 · p. 1
  • DynSTEER segments rollouts at execution nodes, adapts multi-level review to stage results, and builds path-tolerant milestone graphs from task inputs.Multi-candidate simulated planning and majority consensus preserve necessary task invariants while accommodating legitimate paths without reference leakage.Source: §1 · p. 2
  • Over 85% improvement in discriminability versus whole-trajectory evaluation and 17.74% fewer execution steps are reported for DynSTEER.The experiments cover ToolSandbox and SWE-bench Pro.Source: §1 · p. 2
  • DynSTEER detects unrecoverable execution prefixes and terminates them to curb resource waste.Its stage-wise review isolates context-rich evidence windows for scoring and first-error localization.Source: §1 · p. 2

2 RELATED WORK

Prior work evaluates trajectories, adapts benchmark suites, or predicts early outcomes, but the reviewed approaches leave gaps in path diversity, within-task intervention, and semantically grounded stopping. DynSTEER combines stage-wise review, path-tolerant milestone graphs, and execution-time stopping.

2.1 AGENT TRAJECTORY EVALUATION

  • Trajectory evaluators provide intermediate visibility but often rely on a single reference path and review full rollouts post hoc without adapting to an agent’s weak links.Single-path matching can penalize legitimate exploratory strategies.Source: §2.1 · pp. 2–3

2.2 DYNAMIC EVALUATION FOR AGENTS

  • Existing dynamic evaluation mainly selects or perturbs test suites; during an individual task, evaluation remains largely passive and lacks real-time control of review focus or execution.ToolSandbox provides stateful simulations with predefined milestones and safety minefields.Source: §2.2 · p. 3

2.3 EFFICIENT EVALUATION AND EARLY STOPPING STRATEGIES

  • Benchmark distillation reduces task count but leaves long rollouts intact, while tabular early predictors lack domain semantics, failure attribution, and awareness of tool constraints or hazards.DynSTEER instead adapts review to weak or ambiguous stages, compiles path-tolerant milestone graphs, and uses execution-time stopping to eliminate wasteful computation.Source: §2.3 · p. 3

3 METHODOLOGY

DynSTEER coordinates milestone-graph generation, stage-wise trajectory evaluation, and execution-time early termination. It uses task inputs and dual-clock observation to align actions with milestones, isolate evidence, and adapt review to stage results.

3 METHODOLOGY

  • DynSTEER combines stage-wise dynamic evaluation, path-tolerant milestone graphs, and execution-time early termination as three coordinated components.The method aligns closed actions with the milestone graph and uses stage results to inform review and stopping.Source: §3 · p. 3, §3.3 · p. 5

3.1 TASK INPUTS AND DUAL-CLOCK OBSERVATION

  • The raw event clock indexes every observation for immediate fatal-action interception, while the closed-action clock advances after tool return and agent yield for milestone settlement.Graph construction uses evaluator-visible inputs; hidden reference paths and terminal unit tests are not used.Source: §3.1 · p. 3, Figure 2 · p. 4

3.2 MILESTONE GRAPH GENERATION VIA SIMULATED PLANNING

  • Before execution, DynSTEER compiles task inputs into a path-tolerant milestone graph, retaining milestones and precedence relations supported by a majority of valid candidates.Candidate plans undergo schema, acyclicity, and binding-consistency checks; transitive reduction removes redundant dependencies to yield a minimal DAG.Source: §3.2 · pp. 4–5

3.3 STAGE-WISE DYNAMIC TRAJECTORY EVALUATION

  • Stage evaluation matches actions only against the ready frontier, then bounds milestone evidence from its immediate dominator to the current step.Scoring covers task-relevant subsets of seven dimensions; the resulting context preserves intermediate reasoning and supports first-error localization.Source: §3.3 · p. 5

3.4 UNCERTAINTY-ADAPTIVE REVIEW AND EXECUTION-TIME EARLY TERMINATION

  • Uncertainty-adaptive review shifts weights and escalates judge levels toward weak or ambiguous dimensions, while stopping rules terminate hazardous, persistently low-quality, or stagnant executions.DynSTEER uses cheap structural, standard multi-field, and expensive specialist judges; selective deliberation focuses costly review on weak links and relaxes confident stages to rule-based checks.Source: §3.4 · pp. 5–6

4 EXPERIMENTS

Experiments evaluate DynSTEER on ToolSandbox and SWE-bench Pro, testing discriminability, component contributions, milestone-graph reliability, and early stopping. Results show higher model discrimination, reduced execution steps, and milestone graphs that accommodate diverse valid paths.

4.1 EXPERIMENTAL SETUP

  • Experiments used four agent backbones on ToolSandbox and SWE-bench Pro, with a uniform Qwen3-Max-2026-01 evaluator at temperature 0.2.ToolSandbox is a stateful tool-use benchmark; SWE-bench Pro tests repository-level software engineering through multi-file edits and test-based resolution.Source: §4.1 · p. 6, §4 · p. 6

4.2 RQ1: STAGE-WISE DYNAMIC EVALUATION, ERROR FOCUS, AND MODEL DISCRIMINABILITY

  • 85.2% and 164.0% relative DS gains over WHOLE-TRAJ were measured on ToolSandbox and SWE-bench Pro, respectively.DS rose from 0.0270 to 0.0500 on ToolSandbox and from 0.0324 to 0.0857 on SWE-bench Pro.Source: Table 1 · p. 7, §4.2 · p. 7
  • Stage-wise review traces frontier progress and assigns lower evidence to repeated tool-state failures, safety violations, or stalls, exposing process weaknesses despite eventual task resolution.Comparisons use identical source trajectories, attributing the gains to evaluator sensitivity to process quality rather than different rollouts.Source: §4.2 · p. 7
  • 17.74% and 8.40% of Whole-Traj execution steps were removed on ToolSandbox and SWE-bench Pro, respectively.Model-level savings ranged from 11.44–22.14% on ToolSandbox and 2.38–12.19% on SWE-bench Pro; judge calls were roughly 10–20% of agent execution steps.Source: §4.2 · pp. 7–8
  • Mean repeat-level standard deviation fell from 0.66 to 0.59 on ToolSandbox and from 6.41 to 3.24 on SWE-bench Pro; model-pair orders were preserved for five of six and four of six pairs.Kendall τ was 0.67 on ToolSandbox and 0.33 on SWE-bench Pro; DeepSeek-V4-Flash ranked first on both.Source: §4.2 · p. 8

4.3 RQ2: COMPONENT CONTRIBUTIONS TO DISCRIMINABILITY AND EARLY STOPPING

  • Removing any dynamic component or early stopping reduced discriminability, but every ablated configuration remained more discriminative than WHOLE-TRAJ.Disabling policy stopping reduced DS from 0.0528 to 0.0286; dynamic weighting and judge-level escalation contributed complementary separation signals.Source: §4.3 · p. 8

4.4 RQ3: MILESTONE GRAPH GENERATION RELIABILITY

  • 82.9% Micro-F1, 87.3% Macro-F1, 82.7% Fatal Minefield F1, and 100% valid-DAG compilation indicate tool coverage, safety detection, and branch-preserving validity.Expert-referenced GED similarity was 0.789; the compiled graphs support stage partitioning and retain alternative valid paths.Source: §4.4 · pp. 8–9

4.5 RQ4: EARLY-STOP BEHAVIOR AND COUNTERFACTUAL SAVINGS

  • Fatal Minefield Interception dominated ToolSandbox stopped runs, while Frontier Stagnation dominated SWE-bench Pro stopped runs and contributed 4.86% of its 8.40% aggregate savings.Frontier Stagnation covered the largest unique-task share on both benchmarks: 24.56% on ToolSandbox and 12.82% on SWE-bench Pro.Source: §4.5 · p. 9

5 CONCLUSION

The conclusion presents DynSTEER as a stage-wise framework for proactive execution review rather than post-hoc terminal verification. It combines adaptive stage review, path-tolerant milestone graphs, and termination of unrecoverable executions.

5 CONCLUSION

  • DynSTEER improves evaluation discriminability by over 85% compared with whole-trajectory evaluation and saves 17.74% of execution steps.The conclusion describes this as a principled and cost-aware foundation for LLM-agent evaluation and optimization.Source: §5 · p. 10
  • The framework segments rollouts at key execution nodes and adapts multi-level review to stage-level results.It also compiles path-tolerant milestone graphs without reference leakage and terminates unrecoverable executions.Source: §5 · p. 10
  • DynSTEER shifts trajectory evaluation from passive, post-hoc terminal verification toward proactive execution review.Source: §5 · p. 10

A BENCHMARK DATASET DETAILS

The appendix describes ToolSandbox as a stateful tool-use benchmark and SWE-bench Pro as a repository-level software-engineering benchmark. The latter’s public test split contains 731 tasks from 11 repositories.

A BENCHMARK DATASET DETAILS

  • ToolSandbox evaluates complex multi-turn tool use in an interactive, stateful world with persistent entities, temporal relationships, and strict data invariants.Its scenarios are summarized in Table 4.Source: A BENCHMARK DATASET DETAILS · p. 12
  • The benchmarks cover distinct settings: stateful tool-use scenarios in ToolSandbox and repository-level software-engineering tasks in SWE-bench Pro.Source: A BENCHMARK DATASET DETAILS · p. 12
  • SWE-bench Pro provides repository-level software-engineering tasks requiring multi-file edits and test-based resolution.Its public test split contains 731 tasks from 11 repositories; Table 5 reports the repository-stratified experimental sample.Source: A BENCHMARK DATASET DETAILS · p. 12

B DETAILED EXPERIMENTAL CONFIGURATION

The appendix specifies task selection, benchmark-specific WHOLE-TRAJ implementation, runtime parameters, and component ablations. Experiments use four backbones and three repeats per task, replaying the same source trajectories for paired comparisons.

B DETAILED EXPERIMENTAL CONFIGURATION

B.1 TASK SELECTION AND FILTERING

The experiments use locally controlled ToolSandbox scenarios, a repository-stratified SWE-bench Pro sample, and a separate stratified ToolSandbox subset for ablations.

ToolSandbox

  • 509 ToolSandbox scenarios run in fully local, sandboxed environments to support reproducibility, state inspection, and hermetic execution.The setup avoids live API downtime, schema drift, network latency, rate limits, external data leakage, and uncontrolled API cost.Source: §B.1 · pp. 12–13

SWE-bench Pro

  • 39 matched SWE-bench Pro tasks remain after infrastructure-failure pairs are removed from a repository-stratified 100-task sample.The sample began with 100 tasks drawn from a 731-task, 11-repository public test split; the retained set is smaller than the complete split.Source: §B.1 · p. 13

Component-ablation subset

  • The component ablation samples 100 of the 509 ToolSandbox scenarios, stratified by task type and safety category.It uses the same four backbones, three repeats, source trajectories, and paired-comparison protocol as the main experiment.Source: §B.1 · p. 13

B.2 WHOLE-TRAJ IMPLEMENTATION

The appendix specifies the whole-trajectory baselines, runtime settings, ablation variants, execution-time evaluation algorithm, graph validation, and milestone-graph aggregation.

B.2 WHOLE-TRAJ IMPLEMENTATION

  • WHOLE-TRAJ scores a complete trajectory as one unit, using ToolSandbox’s native evaluator or an outcome-informed audit on SWE-bench Pro.The SWE-bench Pro audit receives the task, repository context, complete trajectory, final patch, and terminal patch/test outcome.Source: §B.2 · p. 13

B.3 RUNTIME PARAMETERS

  • Runtime settings fix the judge and graph-generation models, agent limits, and stage, uncertainty, and early-stop thresholds.The listed settings include six candidate graphs, up to four generation batches, and frontier stagnation after 16 observations without ready-frontier progress.Source: §B.3 · p. 13

B.4 COMPONENT-ABLATION DEFINITIONS

  • Ablations disable dynamic weighting, adaptive judge routing, or policy stopping while retaining the same source trajectories, graphs, minefield checks, and models.When policy stopping is disabled, replay covers the full source trajectory, so Saved Steps is not applicable.Source: §B.4 · p. 13

C.1 DYNSTEER EXECUTION-TIME STAGE EVALUATION AND CONTROL ALGORITHM

  • Algorithm 1 synthesizes and aggregates milestone graphs, evaluates matched stages, updates review policy, and halts on minefield or early-stop criteria.It separates the closed-action clock from the evaluated-stage clock; unmatched actions can trigger stagnation monitoring without advancing the review-policy index.Source: §B.4 · p. 14, §C.1 · p. 14

C.2 CANDIDATE CONTRACT VALIDATION

  • Candidate validation filters malformed schemas, unavailable operations, cyclic precedence, and invalid or incompatible parameter bindings before consensus.The checks also verify milestone identifiers, dependencies, and output-field references.Source: §C.2 · p. 15

C.3 BLUEPRINT CONSENSUS AGGREGATION DETAILS

  • The blueprint pipeline admits milestone nodes and precedence edges by majority support, then applies transitive reduction to remove redundant shortcut edges.Candidate graphs are represented by nodes, directed precedence edges, and tool argument bindings.Source: §C.3 · p. 15

C.4 IMMEDIATE DOMINATOR STAGE ANCHORING PROOF

Immediate dominators define the evidence window for each settled milestone, preserving its required path context while separating independent branches.

C.4 IMMEDIATE DOMINATOR STAGE ANCHORING PROOF

  • A node’s immediate dominator is the unique strict dominator that does not dominate any other strict dominator of that node.A dominator is present on every directed path from the augmented entry node to the target.Source: §C.4 · p. 15
  • For a settled milestone, its evidence window spans from the immediate dominator’s settlement step through the milestone’s settlement step.This captures the intermediate steps executed between those two points.Source: §C.4 · p. 15
  • The window preserves causal dependencies while partitioning concurrent, independent branches.The target milestone cannot be reached without traversing its immediate dominator.Source: §C.4 · p. 15

D THEORETICAL DESIGN OF THE DYNAMIC WEIGHTING MECHANISM

The weighting analysis describes how repeated exponential tilting shifts evaluation from average scores toward persistent weak dimensions, while uncertainty guides review allocation.

D THEORETICAL DESIGN OF THE DYNAMIC WEIGHTING MECHANISM

  • The mechanism shifts comparison from average levels toward complementary failure patterns, rather than guaranteeing separation for every model pair.Dispersion can compress when a high-average model also has the deepest weakness.Source: D THEORETICAL DESIGN OF THE DYNAMIC… · pp. 15, 17
  • A linearly growing cumulative score deficit produces an exponentially growing weight ratio, directing review toward persistent weaknesses.The passage describes this cumulative reallocation as a soft-min form of attention.Source: D THEORETICAL DESIGN OF THE DYNAMIC… · p. 16
  • As focus sharpens, every model’s tilted score decreases in proportion to the weighted variance of its dimension profile.A flat profile changes little, whereas a profile with a distinct weakness changes sharply.Source: D THEORETICAL DESIGN OF THE DYNAMIC… · p. 16
  • In the stated example, the limiting model-pair gap is 0.200 under exponential tilting versus a uniform gap of 0.100.Both tilted scores decrease, with the model having the deeper weakness pulled down faster.Source: D THEORETICAL DESIGN OF THE DYNAMIC… · pp. 16–17
  • Lower scores and higher uncertainty increase a dimension’s future review attention, with uncertainty prompting stronger review before evidence is discarded.Once evidence is resolved, subsequent updates respond to refined score and uncertainty estimates.Source: D THEORETICAL DESIGN OF THE DYNAMIC… · pp. 16–17

E.1 CASE 1: EARLY TERMINATION OF INFINITE SEARCH FRONTIER STAGNATION

  • In the search-frontier case, stagnation triggers a stop at replay observation 43, mapped to source batch 22, with counterfactual savings of 7 batches and 16.36 seconds.The complete trajectory recorded 29 batches and 41.04 seconds; the matched prefix recorded 22 batches and 24.68 seconds. These are paired counterfactual savings, not a live interruption.Source: §E.1 · p. 17

E.2 CASE 2: FIRST-ERROR LOCALIZATION VS. FLUKE SUCCESS

The reminder example contrasts eventual task completion with stage-local review of the execution path. The prompt excerpts specify constraints for milestone-graph generation and evidence-grounded stage judging.

E.2 CASE 2: FIRST-ERROR LOCALIZATION VS. FLUKE SUCCESS

  • The reminder agent's path included a failed distraction API call with malformed arguments before it found add reminder after retries.The task was to set a reminder for a specified date and time.Source: §E.2 · pp. 17–18
  • Whole-Traj scored 1.0000, while DynSTEER scored the m0 stage 0.897 and target-message stage 0.272, exposing four erroneous API calls hidden by eventual completion.The low target-message stage score triggers the low-score policy.Source: §E.2 · p. 18

F PROMPT TEMPLATES FOR MILESTONE GENERATION AND STAGE JUDGES

  • The unified judge evaluates whether a stage meets its goal within the supplied interval, scoring only rubric dimensions from step and structured evidence.The prompt distinguishes completed, partial, claimed, and unsupported work; code computes the stage score from dimension scores.Source: F PROMPT TEMPLATES FOR MILESTONE… · p. 18
  • Specialist judge prompts restrict scoring to a named dimension and its dimension-specific focus.The excerpts show representative prompt rules rather than every rule.Source: F PROMPT TEMPLATES FOR MILESTONE… · pp. 18–19
  • Candidate milestone graphs retain only necessary goals under a complete feasible interpretation, while seeking genuine diversity and forbidding unsupported dynamic literals or invalid dependencies.The prompt requires true, non-commutable dependency edges and prohibits cycles.Source: F PROMPT TEMPLATES FOR MILESTONE… · p. 20

AI USE STATEMENT

  • The authors used generative AI for writing and implementation assistance, but not to generate research ideas or conduct data analysis.They report reviewing AI-assisted work and taking responsibility for the final content.Source: AI USE STATEMENT · p. 21
Loading 2609.14637v3…