Organizations: Northwest Polytechnical University Xi’an · Nanyang Technological University · East China Normal University · Tongji University · Peking University
Benchmarks judge language-model agents mainly by whether they reach the correct final state, not by how they got there. Endpoint scoring cannot separate an agent that retrieved exactly the evidence a decision required from one that read most of the environment, nor an agent that never located the evidence from one that stopped a single action short. Settling this needs a reference cost, and authored solutions establish only that a task is solvable, not that no shorter route exists. We present DetourBench, which constrains the environment until that minimum is computable. Each task is a finite, partially observable transition system with unit-cost accesses whose resources become globally addressable after discovery. Exhaustive search yields the full-information minimum action count L0 with a replayable witness; from graph-recoverable terminal states it also yields exact residual work RT, which separates an episode that stopped one access short from one that wandered, while an irreversible wrong commitment is recorded as having no finite residual distance rather than assigned one. Success, attainment, residual progress, and normalized detour are reported separately. Across 375 scored episodes --- five model endpoints, 25 integrated tasks, three repeats --- success ranges from 58.7% to 96.0% while conditional attainment ranges from 0.803 to 0.890 and orders the models differently. Among recoverable failures, residual work separates near-complete trajectories from costly incompletion and from irreversible commitment. We open-source the instances, oracle witnesses, and evaluation harness at https://github.com/DatagridsAI/DetourBench.
Figures & tables
Figure 1: Endpoint evaluation versus trajectory-aware measurement. Endpoint success conflates direct and circuitous successful trajectories and assigns the same outcome to recoverable near-misses and irreversible failures. DetourBench compares charged accesses with the full-information minimum Lo and computes residual work RT from recoverable terminal states, separating outcome, oracle-relative excess interaction, and residual-distance progress.
Figure 2: DetourBench transition semantics and evaluation pipeline. Agents interact with partially observable finite transition systems in which discovered resource identifiers remain globally addressable. Exhaustive search computes the full-information minimum charged accesses Lo and residual work RT . Success, conditional attainment, residual progress, normalized detour, redundant interaction, and irreversible failure are reported separately.
signposted
unsignposted
Model
Query
Pass@1
Pass 3
Waste
Query
Pass@1
Pass 3
Waste
qwen3.6-plus
100%
98%
95%
0.0
5%
42%
32%
4.2
deepseek-v3.2
96%
69%
40%
1.4
68%
38%
8%
3.2
glm-5.2
87%
71%
48%
1.9
32%
37%
32%
4.3
claude-opus-4-8
77%
85%
62%
1.0
2%
42%
40%
4.2
Table 1: Controlled intervention. Query is the fraction of episodes that enter the point-in-time view. Waste is the mean number of out-of-scope provisions read. Deleting one sentence is the only difference between the arms.
Model
Episodes
Successes
Success rate
Cond. attainment
Succ. RSR
Claude
75
72
96.0%
0.890
0.026
Kimi
75
69
92.0%
0.861
0.023
DeepSeek
75
46
61.3%
0.803
0.023
Qwen
75
45
60.0%
0.806
0.040
GLM
75
44
58.7%
0.836
0.034
Table 2: Results on the 25-task Integrated Workflow Suite ( N=375 ). Conditional attainment and RSR are averaged over successful episodes (best in bold; lower RSR is better). Model identifiers correspond to endpoints in Section 5 .
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Complete graph for Task 18 (freight-dispatch cutoff, Lo=20 ). All 35 nodes and 45 discovery edges are shown. Blue nodes and orange edges are accessed by one replayed shortest witness ( Lo=20 ); pale gray nodes and edges are reachable optional or distractor resources. Green dashed connectors unpack the review action’s ten visited-resource prerequisites. Committing Plan A reaches success, whereas committing Plan B or Plan C is an absorbing wrong transition. Because discovered identifiers remain globally addressable, the witness may alternate among evidence families without incurring a navigation or backtracking cost. The rendering is generated directly from the released graph and oracle; labels are shortened, but no nodes or discovery edges are omitted.
Audit
Finding
Action
Paired-arm equivalence
All 53 Currency pairs and 30 of 32 Breadth pairs passed content equivalence; the controlled experiment reports the 40 Currency pairs every model was run on. All 142 Sufficiency and Disposition pairs failed because their arms differed beyond the intended intervention.
Only equivalence-validated pairs remain eligible for controlled comparisons.
Instance diversity
Eight nominal seeds initially produced only five distinct underlying problems across 40 artifacts.
Case-specific variables were incorporated into generation and distinctness was re-audited.
Answer balance
Early Sufficiency and Disposition generators produced a fixed correct answer direction.
Both answer directions are now instantiated and checked during validation.
Scoring normalization
Exact-string matching treated equivalent citation formats as different answers, producing 38 false negatives among 61 inspected episodes.
Structured outputs are canonicalized before semantic comparison.
Appendix
Table 3: Summary of benchmark-construction audits.
Model
Mean charged
Attainment
RSR
Claude
17.0
0.882
0.000
Kimi
17.7
0.850
0.019
Qwen
21.0
0.717
0.014
DeepSeek
21.3
0.705
0.015
GLM
21.7
0.693
0.000
Appendix
Table 4: Task 3, exact oracle Lo=15 , three repeats per model. RSR counts invalid and duplicate accesses only.
Model
Failures
Recoverable
Tasks
Wrong
Progress
NDR
Claude
3
3
1
0
0.519
1.037
Kimi
6
6
4
0
0.830
0.678
DeepSeek
29
29
13
0
0.712
0.791
Qwen
30
28
16
2
0.779
0.727
GLM
31
31
14
0
0.829
0.678
Total
99
97
–
2
0.770
0.737
Appendix
Table 5: Failure decomposition. Progress and NDR are means over recoverable failures only, and Tasks is how many distinct instances those failures come from. The columns are not a model comparison: the five sets of failing instances are largely disjoint and no instance yields a recoverable failure from all five models, so nothing here is ranked.
ID
Task
Domain
Separates by
Lo
Success
succ Δ
att Δ
1
Fall-protection standard
Regulatory
outcome
9
7/15
1.00
0.107
2
Direct advisory fix
Software
cost
10
15/15
0.00
0.091
3
Transitive policy check
Software
cost
15
15/15
0.00
0.190
4
Multi-parent remediation
Software
cost
15
15/15
0.00
0.118
5
Multiple safe versions
Software
cost
13
15/15
0.00
0.147
6
Conflicting fix evidence
Software
cost
15
15/15
0.00
0.130
Appendix
Table 6: Per-task results. Success is aggregated over five models and three repeats. † marks the six tasks evaluated under the later prompt revision; dropping them and recomputing on the remaining nineteen leaves the success ordering unchanged and the cost ordering unchanged except that Qwen and DeepSeek, which we do not order, swap. Tasks 21–24 were added after review; task 25 was run with tasks 1–20 but omitted from their manifest. For tasks 1–20 the released manifest paper_selection_20.json maps each ID to its artifact directory, graph and oracle hashes, task revision, and prompt version; it also records each task’s pre-renumbering build number, which the artifact directory names carry. Hashes remain the authoritative identity.
Model
Episodes
Successes
Success rate
Cond. att.
Succ. RSR
Progress
NDR
HY4-Preview
72
52
72.2%
0.821
0.025
0.819
0.696
Appendix
Table 7: HY4-Preview on tasks 1–24 (3 repeats, later prompt revision). Columns as in Table 2 ; progress and NDR are over recoverable failures, as in Table 5 .
Quantity
Minimum
Median
Mean
Maximum
Graph nodes
16
30
33.7
62
Search states generated
12
87
1,272
13,541
Runtime (ms)
0.07
0.85
20.3
273.4
Peak memory (MiB)
0.02
0.09
1.74
23.97
Appendix
Table 8: Cost of the exact oracle across the 25 frozen tasks.
Large language model agents solve tasks by generating trajectories that interleave planning, tool calls, and intermediate results. Current evaluation metrics reduce such a trajectory to a binary success flag, compare it against a reference by exact matching, or delegate judgment to another language model. A success flag cannot distinguish sound solutions from lucky ones, nor explain why runs fail. Exact matching penalizes valid plans reordered or decomposed differently. We reframe trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, and instantiate it via an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency graphs. The resulting score, termed OTAP (Optimal Transport for Agentic Planning), is a normalized discrepancy score. Its idealized, globally minimized entropy-free objective is invariant to dependency-preserving relabelings of a fixed graph and has a redundant-insertion sensitivity analysis under stated assumptions. Its unbalanced marginals handle missing or hallucinated steps without forcing a match; granularity invariance remains an open problem that soft coupling mitigates only in part. On controlled perturbations and three public benchmarks, OTAP separates valid from invalid trajectories in a regime where semantics-only metrics score below chance. Its performance is encouraging across these settings, while controlled edge-noise experiments reveal sensitivity to dependency extraction. Where a formal verifier exists, strict surface metrics predict validity better than OTAP does, which places OTAP in open-ended domains where no verifier is available. A blinded study of 236 trajectories finds the strongest agreement with OTAP among the six compared metrics. Structure-aware baselines achieve higher clean-graph AUROC, while OTAP has the smallest absolute AUROC decline under the tested edge noise.
Babak Barazandeh, Subhabrata Majumdar, George Michailidis
Computation cost is a critical challenge for LLM agent systems, as their long-horizon trajectories continuously accumulate computational overhead. While existing studies focus on improving the overall efficiency of agent systems, the efficiency of individual steps remains largely unexplored. In this paper, we propose and formulate a new research problem: redundant step detection, aiming to detect these steps that consume substantial computational resources while contributing little or nothing to task completion. To support this initiative, we introduce RedundancyBench, a new benchmark that contains 1,920 trajectories collected from 6 different LLMs with 3,613 step-level annotations. Using RedundancyBench, we develop and evaluate 6 frontier LLMs and Jev as redundant step detectors, summarizing their strengths and limitations. Our experiments reveal that the redundant step detection is still challenging even for SOTA models, such as Claude-Opus-5, particularly without prior information. Code and dataset in this paper are both available in https://anonymous.4open.science/r/RedundancyBench-E0CB.
Liang Zhu, Bo Yang, Zhinuo Zhou +5
Huawei Technologies, Noah Arks’ Lab · Institute of Computing Technology, Chinese Academy of Sciences
Interactive agent benchmarks map an agent run to a binary outcome through outcome checks. When these checks rely on surface level signals or fail to capture the agent's actual action path, they cannot reliably determine whether the run succeeded. For example, a benchmark task may ask whether Alice's shipping address was changed, while the outcome check only verifies that the agent clicked "Save." This does not guarantee that the intended state change occurred, since the agent may have modified the wrong record. Treating such a run as successful therefore makes the reported score misleading. Benchmark quality thus depends not only on task design, but also on the reliability of outcome detection. We address this problem by introducing an outcome evidence reporting layer for existing benchmarks, without modifying their tasks, agents, or evaluators. The layer performs three functions. First, before scoring, it specifies which stored artifacts are required to verify the claimed outcome for each case. Second, it applies a locked checklist to each completed run and assigns one of three evidence labels: Evidence Pass, Evidence Fail, or Unknown. Third, it reports evidence supported score bounds that quantify uncertainty arising from Unknown cases. Rather than silently counting, discarding, or hiding uncertain cases inside a single aggregate success rate, the framework keeps them explicitly visible. We evaluate the outcome evidence layer on five public benchmarks: ANDROIDWORLD, AGENTDOJO, APPWORLD, tau3 bench retail, and MINIWOB. The resulting reports separate several empirically distinct failure modes.