acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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://anonymous.4open.science/r/DynSTEER

Primary area:
foundation or frontier models, including LLMs
Keywords:
agent evaluation, trajectory evaluation, dynamic evaluation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_DdKNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes DynSTEER, a dynamic stage-wise framework for evaluating LLM agent trajectories. Instead of evaluating entire trajectories or individual steps, DynSTEER divides agent executions into meaningful stages using automatically generated milestone graphs. It dynamically adjusts evaluation dimensions and judge levels based on stage-level performance and uncertainty. Additionally, it introduces an early-stopping mechanism to terminate potentially unrecoverable executions and reduce computational costs. Experiments on ToolSandbox and SWE-bench Pro show that DynSTEER improves model discriminability by over 85% compared to whole-trajectory evaluation while reducing execution steps.

Critical strengths
  1. Novel Stage-wise Evaluation Framework. The paper proposes a stage-wise trajectory evaluation framework that addresses the limitations of both whole-trajectory and step-level evaluation. The combination of milestone graphs and adaptive multi-level judges is an interesting approach to evaluating agent execution quality.

  2. Improved Evaluation Efficiency. The proposed early-stopping mechanism can identify potentially unrecoverable trajectories and reduce unnecessary execution steps. The experimental results demonstrate promising improvements in model discriminability and computational efficiency across two benchmarks.

Critical weaknesses
  1. Lack of Ground-Truth Validation for Evaluation Quality. Although the authors introduce several evaluation metrics, I believe that metrics such as model discriminability, which measure how well the proposed method separates the scores of different agents, do not necessarily demonstrate that the evaluation method is better or more accurate. The authors should construct a small-scale benchmark with ground-truth annotations to directly validate the effectiveness of their evaluation method.

  2. Unclear Practical Value of Trajectory Scoring. The authors do not clearly explain the practical significance of assigning scores to agent trajectories. For example, are these scores intended for data filtering or as reward signals for reinforcement learning? I believe the authors should demonstrate the effectiveness of the proposed scoring method on at least one downstream post-training task.

Questions for authors

Mentioned in Critical Weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer DdKN

Thank you for your helpful comments. Our responses to your questions are as follows.

Response to Q1

Ground-truth validation of a trajectory evaluator is difficult because the evaluation community does not yet provide an established independent meta-evaluation oracle for open-ended agent trajectories. The paper therefore uses the systematic separation criterion DS, following Benchmark²: Systematic Evaluation of LLM Benchmarks (Qian et al., arXiv:2601.03986, 2026). DS is defined at Line 339–348, Page 7, and combines score dispersion with the fraction of model pairs separated beyond a margin.

The controlled evidence is the dynamic-component ablation in Table 3 and Section 4.3, where source trajectories, milestone graphs, minefield checks, and models are held fixed (Line 659–661 and Line 693, Page 13). DS rises from 0.0228 for WHOLE-TRAJ to 0.0311 for -w/o dynamic, 0.0439 with dynamic judge level removed, 0.0414 with dynamic weighting removed, and 0.0528 for full DynSTEER (Line 380–386 and Line 405–425, Page 8). This supports the claimed gain in systematic model discrimination rather than asserting human-quality accuracy.

Response to Q2

The intended use of DynSTEER scores is evaluation-centric: auditable process diagnosis, failure localization, safety analysis, and model comparison. These uses are directly tied to the paper’s evaluation objective and do not require changing the learning objective of an agent.

Using the scores as filtering rewards or post-training objectives is a different research problem. It requires a dedicated training protocol, preference-pair construction policy, optimization analysis, and safety controls. Such a study is outside the scope of evidence for an evaluation paper. The appropriate claim is that DynSTEER supplies auditable process-level signals for evaluation and diagnosis, not that it has been validated as a downstream training reward.

Reviewer_ip6COpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes DynSTEER, a stage-level framework for evaluating LLM-agent trajectories that sits between whole-trajectory and atomic-step evaluation. Before execution, it compiles a path-tolerant milestone DAG from task inputs only, using multiple LLM-generated candidate graphs, deterministic validity checks, and majority consensus. During execution, it scores evidence windows anchored at each milestone's immediate dominator and adapts dimension weights and judge levels (rule-based to specialist LLM) according to stage scores and uncertainty. It also stops runs on fatal actions, persistently low scores, or frontier stagnation. Experiments replay recorded trajectories from four agent backbones on ToolSandbox and SWE-bench Pro, reporting discriminability gains over whole-trajectory evaluation and counterfactual step savings.

Critical strengths
  1. A well-motivated and principled design for stage-level evaluation. The paper targets a real gap between coarse whole-trajectory and noisy atomic-step evaluation. It grounds stages in a milestone graph built only from task inputs, using ready-frontier matching and dominator-anchored windows. The result is an auditable, path-tolerant evaluation that needs no reference trajectories and offers a reusable formulation for process-level evaluation.

  2. Reference-free blueprint compilation. The compiled milestone graphs match expert annotations on ToolSandbox with 82.9% tool-operation Micro-F1. Existing milestone-based evaluators depend on hand-annotated milestones, so this result shows that such annotations can largely be derived from task inputs alone.

Critical weaknesses
  1. The evidence does not show that DynSTEER evaluates better. The main evidence is a higher discriminability score (DS). DS measures how far apart model scores are, not whether the scores are correct, and any method that adds variance would raise it. The paper never checks stage scores against an independent reference such as human judgments, and first-error localization appears only in one case study. The comparison is also confounded. WHOLE-TRAJ and DynSTEER use different scoring procedures (Appendix B.2), and the "w/o dynamic judge level" ablation replaces the LLM judges with a rule-based one. Since the main contribution is a better evaluator, the reported gains cannot yet be credited to stage-wise evaluation or adaptive routing.

  2. The early-termination results do not show that stops are correct or that cost is saved. All stops are counterfactual points in replayed trajectories, and the paper does not report how many stopped runs would have succeeded. Appendix E.2 contains one such run: WHOLE-TRAJ scores it 1.0, yet it triggers the low-score stop. Removing policy stopping also causes the largest DS drop in Table 2 (0.0528 to 0.0286), so part of the DS gain may come from counting stopped runs as failures. The step savings also leave out the cost of blueprint generation and judge calls. Early termination is both a core contribution and a source of the DS gain, so false stops would weaken the efficiency claim and the main result together.

Questions for authors

Main questions

  1. Do stage scores agree with an independent quality reference, such as human ratings of process quality? How does DynSTEER compare with a whole-trajectory baseline that uses the same judge model and rubrics? How accurately does DynSTEER locate the first error, measured against annotated first-error steps?
  2. How is "Mean Score" in Table 1 computed from stage scores, and how are stopped runs and unfinished stages scored? How are the overall step savings of 17.74% and 8.40% computed? The per-model values in Table 1 average to 17.80% and 8.00%.
  3. How is the dimension-level uncertainty computed at each judge level, including the rule-based cheap judge? Appendix B.3 sets the stagnation threshold to 16 observations, but the stop in Appendix E.1 fires after 8. Which value is used? How sensitive are the results to the thresholds in Appendix B.3?
  4. Edge-wise majority voting over acyclic candidates can still produce a cycle. How is this handled before transitive reduction? How do errors in the compiled graph change stage scores and stop decisions, given that minefield recall is 75.3% (Table 3)? Rerunning ToolSandbox with the expert-annotated graphs would answer this directly.
  5. What fraction of stopped runs would have succeeded if run to completion? What is the end-to-end cost of DynSTEER, including blueprint generation and judge calls, compared with WHOLE-TRAJ?
  6. The ToolSandbox shares in Figure 3(a) add up to 96.2% rather than 100%. Is a category missing, or are different denominators used?

Minor suggestions for improving the paper

The following are small suggestions that I hope will help polish the paper.

  1. The text inside Figure 1 is quite small at normal viewing size. Enlarging it would make the figure easier to read.
  2. It would help readers to spell out "DAG" (directed acyclic graph) at its first occurrence.
  3. The appendices are not ordered by their first mention in the main text, which is C, F, D, A, B, and then E. Reordering them, or adjusting the references, would make the supporting material easier to follow.
  4. Using the same percentage notation across the three panels of Figure 3 would make them more consistent.
  5. In the experiments section, the text and the figures use different decimal precision (e.g., 57.56% vs. 57.6%). Aligning them would improve consistency.
2 comments
AuthorsOpenReview ↗

Response to Reviewer ip6C (Q1-Q3)

Thank you for your detailed and constructive comments. Our responses to your questions are as follows.

Response to Q1

The appropriate evaluation criterion here is DS, following Benchmark²: Systematic Evaluation of LLM Benchmarks (Qian et al., arXiv:2601.03986, 2026). DS is explicitly a model-separation metric: it combines population dispersion with the fraction of model pairs whose mean scores differ by more than a margin (Line 339–348, Page 7). It is not presented as human-quality agreement.

The relevant same-judge control is the -w/o dynamic arm in Table 3 and Section 4.3: adaptive routing and weighting are disabled, so every dimension uses the same fixed cheap judge. All ablations also use the same source trajectories, milestone graphs, minefield checks, and models (Line 659–661 and Line 693, Page 13). Relative to WHOLE-TRAJ’s DS of 0.0228, -w/o dynamic reaches 0.0311, -w/o dynamic judge level reaches 0.0439, -w/o dynamic weighting reaches 0.0414, and full DynSTEER reaches 0.0528; removing policy stop gives 0.0286 (Line 380–386 and Line 405–425, Page 8). These results separate stage-wise organization, dynamic routing/weighting, and stopping. Appendix E.2 provides a concrete first-error example: WHOLE-TRAJ gives 1.0000 to a trajectory with four erroneous intermediate calls, whereas DynSTEER assigns the weak stage 0.272 and triggers the low-score policy (Line 911–929, Page 17–18).

Response to Q2

Mean Score first computes the trajectory score as the mean of all evaluated and synthetic pending stage scores, multiplied by one minus the maximum fatal-minefield penalty; it then averages these trajectory scores over matched cases and repeats. Unfinished milestones contribute zero-valued synthetic pending stages.

Saved Steps% is a micro aggregate:

1 − sum(policy-prefix steps) / sum(full-trajectory steps).

The arithmetic mean of the per-model rows is a macro average, so it may not equal the pooled micro value. A full re-audit over 6,108 ToolSandbox pairs gives a 20.02% stop rate and 19.05% micro Saved Steps%; model-level micro savings are 12.63%, 17.64%, 23.72%, and 22.48% for DeepSeek-V4-Flash, DeepSeek-V4-Pro, Qwen-Plus, and Qwen3-Max, respectively. The recomputed DS at ε=0.01 on the 0–1 scale is 0.0500.

Response to Q3

For every dimension, uncertainty_d = 1 − confidence_d. The cheap judge computes deterministic structural confidence. Its base confidences are: progress 0.92, state consistency 0.82, tool quality 0.78, efficiency 0.62, safety 0.84, interaction quality 0.48, and recovery 0.55; warnings reduce confidence by at most 5×0.03, and non-failed/non-missing cases receive at most a 0.12 missing-field penalty. Deterministic failures are treated as low uncertainty, not high uncertainty. Standard and expensive judges compute agreement confidence by discretizing repeated dimension scores into 0.25 anchors and measuring normalized entropy over those anchors; a single pass uses the conservative confidence 0.62.

The main artifacts use ready-frontier patience 8, not 16. Appendix E.1’s “eight consecutive observations” refers to the best score for the ready target milestone remaining unchanged; it is consistent with the runtime patience value of 8. The sensitivity pilot gives: baseline 33/300 stops and 3.03% false stops; fail threshold 0.30, 34 stops and 2.94%; fail threshold 0.50, 33 stops and 0%; patience 12, 33 stops and 3.03%; patience 16, 34 stops and 2.94%; patience 24, 33 stops and 0%. Saved Steps remain 17.14%–17.50%.

AuthorsOpenReview ↗

Response to Reviewer ip6C (Q4-Q6)

Response to Q4

Candidate graphs are checked for schema validity, acyclicity, binding consistency, and reachability before consensus (Line 200–206, Page 4; Line 758–770, Page 15). Majority edges are not merged as an unguarded union. The implementation inserts edges in deterministic order; an edge that would form a cycle in the already accepted set is skipped and logged as edge_cycle_conflict, after which transitive reduction is applied to the accepted acyclic set (consensus and reduction: Line 781–788, Page 15).

Graph quality is measured directly against ToolSandbox expert annotations in Section 4.4: Tool Operation Micro-F1 82.9%, Macro-F1 87.3%, Fatal Minefield F1 82.7% with 91.8% precision and 75.3% recall, topological GED similarity 0.789, and a 100% valid-DAG compilation rate (Line 427–455, Page 8). These expert-referenced statistics quantify the impact of graph mismatch on milestone coverage, safety alignment, and topology. Moreover, Section 4.3’s ablations retain the same milestone graphs and minefield checks, so the DS comparisons there are not caused by changing the graph (Line 693, Page 13).

Response to Q5

In the 6,108-run ToolSandbox audit, 174/1,223 stopped prefixes would have succeeded, yielding a 14.23% overall false-stop rate (Wilson 95% CI 12.38%–16.30%). The per-criterion results are:

CriterionValid stopsStop shareComplete-run successesWould-success / false-stop rateWilson 95% CI
Fatal minefield70457.56%00.00%0.00%–0.54%
Frontier stagnation28523.30%196.67%4.31%–10.18%
Persistent low score23419.13%15566.24%59.96%–71.99%
Total1,223100.00%17414.23%12.38%–16.30%

Persistent low score is not the main stopping strategy: it accounts for only 19.13% of stops. The false-stop cases are concentrated in this secondary rule: it contributes 155/174 = 89.08% of would-success cases. This is expected for a secondary resource-triage rule that prevents long continuation in weak, low-value, non-progressing states rather than claiming irrecoverability. Fatal minefield and frontier stagnation dominate the policy and have low would-success rates. The low-score threshold is adjustable: in a qwen-only 100-case sensitivity pilot, fail thresholds 0.30, 0.40, and 0.50 yield false-stop rates of 2.94%, 3.03%, and 0%, respectively. Gross/safe saved steps are 8,819/8,529.

The available cost audit is: adaptive replay completed 277/300 qwen-only evaluations, used 755 judge calls and 4,412,604 recorded judge tokens (token records available for 188 runs), and saved 341/1,966 closed-action steps (17.34%). Among complete timing records, full execution took 5,109.2s and the stopped prefix 3,360.3s, saving 1,748.9s; evaluator overhead was 6,099.6s. Thus, before including blueprint generation, the net wall-clock cost is +4,350.7s. Step saving and evaluator overhead must be reported separately: the current replay implementation saves execution steps but does not yet yield a wall-clock net saving.

Response to Q6

Thank you for pointing out this figure error. We checked the source statistics; the mistake came from accidentally selecting the wrong denominator cell in the Excel sheet used to construct the figure. The corrected primary-reason shares are:

fatal minefield        704 / 1,223 = 57.56%
frontier stagnation   285 / 1,223 = 23.30%
persistent low score  234 / 1,223 = 19.13%
total                1,223 / 1,223 = 100.00%
Reviewer_MhCoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

DynSTEER compiles milestone graphs from task inputs, evaluates agent trajectories in stages with adaptive judge routing, and applies early stopping. Experiments on ToolSandbox and SWE-bench Pro report improved discriminability and counterfactual execution savings.

Critical strengths

The framework addresses a relevant evaluation problem with concrete, auditable components, including separate event/action clocks and ready-frontier matching.

Critical weaknesses
  1. Higher discriminability does not establish evaluation accuracy. DS measures score dispersion and model-score gaps, rather than agreement with independently assessed trajectory quality (Eq. 10). Independent validation of stage/trajectory scores is missing, and stage-to-trajectory aggregation and stopped-run scoring are unspecified. On ToolSandbox, the comparison also changes the scorer and reference graph alongside evaluation granularity
  2. Early stopping lacks false-stop validation. All stops are counterfactual replays (App. B), without per-criterion false-stop analysis. In Case E.2, low-score stopping is triggered on a trajectory that ultimately completes the required milestones, supporting detection of inefficient execution but not irrecoverability. This is consequential: removing stopping reduces DS from 0.0528 to 0.0286 on the 100-scenario ablation subset
Questions for authors
  1. How are stage scores aggregated, and how are stopped runs and unsettled milestones scored?

  2. For each stopping criterion, what fraction of virtually stopped trajectories ultimately succeed?

  3. Can you provide independent quality validation and a controlled whole-trajectory baseline using the same judge, graph, and stopping decisions?

1 comment
AuthorsOpenReview ↗

Response to Reviewer MhCo

Thank you for your valuable comments. Our responses to your questions are as follows.

Response to Q1

The stage-to-trajectory aggregation is as follows. DynSTEER first constructs a dominator-anchored evidence window and computes the composite stage score as a weighted sum over the seven evaluation dimensions (Line 225–245, Page 5). Algorithm 1 specifies that an accepted stage requires a ready-milestone match and successful hard-constraint/pass-threshold checks; failed and unmatched attempts remain in the audit record, and stagnation is monitored separately (Line 745–755, Page 14).

Formally, for a terminated run,

trajectory score
= mean(all evaluated stage scores and all synthetic pending-stage scores)
  × (1 − maximum fatal-minefield penalty).

An unfinished milestone contributes a synthetic pending stage with score 0. It is marked FAIL if that milestone was ever ready or attempted, and MISSING otherwise. Hence stopped runs and unsettled milestones are included in the denominator rather than silently dropped. Table 1’s Mean Score is the average of these trajectory scores over the matched case/repeat population.

Response to Q2

The counterfactual outcome audit gives the following results. ToolSandbox contains 509 cases × 4 models × 3 repeats, i.e. 6,108 paired runs. There are 1,223 valid policy stops. Among them, 174 would have succeeded if execution continued, so the overall false-stop rate is 14.23% (Wilson 95% CI 12.38%–16.30%).

By primary stopping criterion:

CriterionValid stopsStop shareComplete-run successesWould-success / false-stop rateWilson 95% CI
Fatal minefield70457.56%00.00%0.00%–0.54%
Frontier stagnation28523.30%196.67%4.31%–10.18%
Persistent low score23419.13%15566.24%59.96%–71.99%
Total1,223100.00%17414.23%12.38%–16.30%

Fatal minefield and frontier stagnation account for 80.87% of policy stops and have low would-success rates (0.00% and 6.67%), so they are the primary failure signals. Persistent low score is not the main stopping strategy: it accounts for only 19.13% of stops, although it contributes 155/174 = 89.08% of the would-success cases. Its high would-success rate reflects the intended role of the stopping layer: preventing an agent from continuing for a long time in a weak, low-value, non-progressing state. The frontier-stagnation criterion handles explicit lack of frontier progress. Its threshold is configurable: in a qwen-only 100-case sensitivity pilot, fail thresholds 0.30, 0.40, and 0.50 yield false-stop rates of 2.94%, 3.03%, and 0%, respectively.

Gross saved steps are 8,819; safe saved steps, counting only stops whose complete run fails, are 8,529. Thus, gross/safe saved steps are 8,819/8,529, and the low-score rule should be interpreted as process-quality resource triage, not as an irrecoverability proof.

Response to Q3

A standalone “ground-truth” meta-evaluation is not currently a well-posed requirement for this setting: agent-trajectory evaluation lacks an agreed independent quality oracle, and a newly constructed human/rubric meta-benchmark would itself introduce annotator and rubric bias. The quantitative criterion used here is Discriminability Score (DS), following Benchmark²: Systematic Evaluation of LLM Benchmarks (Qian et al., arXiv:2601.03986, 2026). The paper defines DS as score dispersion combined with the fraction of model pairs separated beyond a margin (Line 339–348, Page 7).

The controlled experiment is the dynamic-component ablation in Table 3 and Section 4.3. Appendix B states that all ablations retain the same source trajectories, milestone graphs, minefield checks, and models (Line 659–661 and Line 693, Page 13); -w/o dynamic further disables adaptive routing and weighting, so every dimension is scored by the same fixed cheap judge. The DS values are: WHOLE-TRAJ 0.0228, -w/o dynamic 0.0311, -w/o dynamic judge level 0.0439, -w/o dynamic weighting 0.0414, and DynSTEER 0.0528; removing policy stopping lowers DS to 0.0286 (Line 380–386 and Line 405–425, Page 8). This isolates the contribution of dynamic stage evaluation from changes to the graph, minefield checks, source trajectories, and model population. The first-error behavior is also illustrated in Appendix E.2, where WHOLE-TRAJ assigns 1.0000 to a fluke success while DynSTEER identifies four erroneous intermediate calls and scores the weak stage 0.272 (Line 911–929, Page 17–18).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.