betaFeedback

WorksComputer Science

DetourBench: Trajectory-Level Evaluation of Interactive Agents with Exact Minimum-Action Bounds

Abstract

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 L0L_0 with a replayable witness; from graph-recoverable terminal states it also yields exact residual work RTR_T, 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.

Introduction

Interactive-agent benchmarks commonly score whether an agent completed the task [16, 15, 6, 13, 8]. While necessary, endpoint scoring is silent about process (Figure 1): it conflates direct and exhaustive paths, and gives identical zeros to agents that never located evidence and those stopping a single action short [5, 7].

Endpoint evaluation versus trajectory-aware measurement

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 LoL_o and computes residual work RTR_T from recoverable terminal states, separating outcome, oracle-relative excess interaction, and residual-distance progress.

Measuring these differences requires a defensible reference cost. Authored solutions establish solvability but rarely prove minimality, while cost-weighted evaluations require assumptions about the relative prices of tools [3]. DetourBench instead measures structural interaction under uniform access costs. We restrict each task to a finite transition system in which resources are partially observable but become globally addressable after discovery: once an identifier is revealed, the agent can invoke it directly without navigation or backtracking costs. Exhaustive search over the complete transition graph then computes the minimum number of charged accesses required for success, denoted LoL_o, and produces a replayable shortest-path witness.

The same search supports failure-aware evaluation. For an unfinished episode whose terminal state remains graph-recoverable, it computes the exact residual work RTR_T: the minimum number of further accesses needed for success. This allows success, oracle-relative attainment, normalized detour, and residual-distance progress to be reported separately. An irreversible wrong commitment is represented explicitly rather than assigned a finite residual distance. LoL_o is an offline optimum over the declared transition system, not the cost of an optimal policy under partial observability; § 3 bounds what that leaves out.

DetourBench applies this measurement contract to two complementary collections. The Controlled Mechanism Suite holds graph structure, targets, and oracle bounds fixed while varying a local information cue. The Integrated Workflow Suite combines multiple records, constraints, and workflow actions in longer authored tasks. Both use the same transition semantics, solver, evaluator, and artifact-versioning protocol. Mechanical replay, provenance, necessity audits, pair diffs, and hash consistency gate which artifacts and trajectories may be reported.

The measurement finds cases endpoint scoring cannot. On eight of twenty-five tasks every model succeeds on every repeat, so success separates nothing at all, and conditional attainment still spreads the models by 0.07 to 0.19 — three to nine times the variation across repeats of the same model. On the failing side, residual work tells a trajectory that stopped one access short from one that exhausted its budget far from the goal and from one that committed irreversibly — three situations a binary score records identically.

Our contributions are:

  1. Exact oracle-relative trajectory measurement. We compute instance-specific full-information minima and replayable witnesses, together with exact residual work for graph-recoverable failures.

  2. A shared benchmark and validation contract. Controlled and integrated tasks use unified execution semantics and fail-closed checks for mechanical validity, provenance, pair integrity, and artifact consistency.

  3. A diagnostic multi-model evaluation. Across 375 episodes from five endpoints on 25 tasks, eight tasks are solved by every model on every repeat while cost still orders them,

and residual work decomposes the failures a binary score records identically. §5 states the selection screen these tasks passed.

DetourBench is deliberately formulated as a controlled diagnostic probe with exact graph-theoretic bounds, designed to isolate unnecessary and missing evidence accesses, rather than as a representative sample of natural workflows.

Related Work

Agent and trajectory evaluation. Interactive-agent benchmarks commonly emphasize final task completion, while process-oriented approaches inspect intermediate behavior. AgentBoard [5] measures progress through annotated subgoals, and CORE [7] encodes each task as a deterministic automaton over a manually verified set of acceptable tool-use paths, scoring correctness, ordering, prefix criticality, harmful calls, and efficiency against it. AgentRewardBench [4] instead studies the reliability of automatic trajectory evaluators. Both AgentBoard and CORE admit several acceptable routes rather than one canonical ordering, so the difference is not rigidity but provenance: their references are authored and establish that a route is acceptable, while ours is search-derived and establishes that no shorter one exists.

Interaction and path efficiency. Success weighted by Path Length (SPL) in embodied navigation [1] established the principle our attainment measure inherits: compare an observed successful trajectory with an instance-specific shortest path. Two things differ. SPL scores a failed episode zero, so it cannot distinguish an agent that stopped one action short from one that never located the evidence, and it has no representation for an irreversible wrong commitment; those three cases are what our failure-side measurement separates, using the same search that produces the bound. This is not a corner case on our suite — roughly a third of episodes fail on three of the five models, and the ordering those failures induce differs from the ordering on success. The shortest path is also over a different object: SPL’s optimum is a distance in a metric space, ours is over a combinatorial state of visited resources, acquired credentials, and an outcome flag, in which prerequisites make reachability history-dependent and one transition is absorbing.

CORE’s efficiency measure is the closest contemporary comparison. It divides the longest acceptable path not exceeding the agent’s own length by that length, which makes the reference adapt to the trajectory being scored and leaves efficiency undefined for an agent shorter than every acceptable path. Our reference is instead a fixed per-instance minimum that no legal route can beat, so attainment is defined for every success and comparable across episodes of very different length. CostBench [3] evaluates planning under heterogeneous tool prices and dynamic failures, while work on efficient tool-integrated reasoning directly optimizes models to reduce unnecessary calls [14]. DetourBench instead uses uniform access costs to isolate structural interaction count; it does not measure latency, token consumption, or economic cost.

Partial observability and benchmark validity. Comparing observed trajectories to full-information optima connects to online search and POMDPs [9, 2]. Without current-location costs, search depends on proximal cues or information scent [10], motivating our controlled cue intervention. Audits show underspecified tasks and scoring shortcuts threaten benchmark validity [17, 11, 12, 8]; DetourBench addresses these via replayable witnesses, provenance, pair diffs, and cryptographic manifests.

Methodology

Measurement scope

Figure 2 summarizes the semantics and the evaluation pipeline. DetourBench measures structural interaction under uniform access costs. For each instance it compares an observed trajectory with the shortest successful trajectory available to an evaluator that knows the complete transition system, so the reference is a full-information offline optimum: exact under the declared semantics, and not the cost of an optimal policy under partial observability. Excess over it is therefore oracle-relative detour, made precise once the measures are defined.

DetourBench transition semantics and evaluation pipeline

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 LoL_o and residual work RTR_T. Success, conditional attainment, residual progress, normalized detour, redundant interaction, and irreversible failure are reported separately.

Transition and execution semantics

An instance defines a finite action set, a deterministic transition function δ\delta, and states

st=(Vt,Kt,zt),(1)s_t = (V_t, K_t, z_t), \tag*{(1)}

where VtV_t is the set of accessed resources, KtK_t is the set of acquired credentials, and zt∈{active,success,wrong}z_t \in\{\text{active},\text{success},\text{wrong}\} is the outcome state. Seed resources belong to V0V_0. Each environment action aa has a source σ(a)\sigma(a), resource prerequisites RV(a)R_V(a), and credential prerequisites RK(a)R_K(a). While the task is active, the enabled actions are

A(st)={a:σ(a)∈Vt,RV(a)⊆Vt,RK(a)⊆Kt}.(2)A(s_t) = \{a : \sigma(a) \in V_t, R_V(a) \subseteq V_t, R_K(a) \subseteq K_t\}. \tag*{(2)}

The agent observes only ot=Ω(st)o_t = \Omega(s_t). Accessing a resource may reveal additional action identifiers or credentials. While zt=activez_t = \text{active}, both VtV_t and KtK_t grow monotonically, and previously enabled actions remain available. Once an identifier has been revealed, it can be invoked directly; the environment has no current-location or backtracking cost.

At model turn uu, the agent may emit an ordered batch of candidate accesses. The environment dispatches them sequentially until the batch ends, the access budget is reached, or a terminal transition occurs. Let a~u\tilde{a}_u denote the prefix actually dispatched. The charged trajectory and its cost are

τ=a~1⊕a~2⊕⋯ ,Cτ=∑u∣a~u∣.(3)\tau= \tilde{a}_1 \oplus\tilde{a}_2 \oplus\cdots,\qquad C_\tau= \sum_u \lvert\tilde{a}_u\rvert. \tag*{(3)}

Thus, cost counts dispatched environment accesses rather than model turns. Every access reaching the environment dispatcher is charged, including disabled, invalid, or duplicate accesses that leave the task state unchanged. Pure model responses that dispatch no access are uncharged. A separate predeclared model-turn limit prevents infinite no-access loops and does not enter CτC_\tau.

Where a task contract offers a textual submission, it is uncharged and contracted into the terminal state during search; in our suite, all completions occurred through charged terminal actions. An episode ends at success, an absorbing wrong commitment, the access budget, the model-turn limit, or an explicit final submission.

Exact oracle and residual work

Let G\mathcal{G} be the set of success states. Exhaustive breadth-first search over the finite reachable state space computes

Lo=min⁡τ:s0→GCτ,(4)L_o = \min_{\tau:s_0\to\mathcal{G}} C_\tau, \tag*{(4)}

where only charged accesses contribute to path cost. The search predecessor map yields a shortest successful trajectory τo\tau_o, which is replayed under the same transition function used for model episodes. The graph, success conditions, oracle length, and replayable witness are frozen together. All admitted instances satisfy Lo≥1L_o \ge1.

For an episode ending in an active state sTs_T, residual work is

RT=d∗(sT,G),(5)R_T = d^*(s_T,\mathcal{G}), \tag*{(5)}

the minimum further charged accesses required for success. Resources and credentials are monotone, so nothing already enabled becomes unavailable, and the one-shot actions some instances declare are terminal: spending one leaves the active state rather than stranding the episode inside it. Every active terminal snapshot is therefore graph-recoverable. Consequently,

0≤RT≤Lo,Cτ+RT≥Lo.(6)0 \le R_T \le L_o,\qquad C_\tau+ R_T \ge L_o. \tag*{(6)}

Successful episodes have RT=0R_T = 0; no finite residual distance is assigned after an absorbing wrong commitment. Graph-recoverability refers to the transition system and does not imply sufficient remaining budget to execute the residual path.

Trajectory measures

Let Sτ∈{0,1}S_\tau\in\{0,1\} indicate terminal success. For successful episodes, conditional attainment is

Aτ={Lo/Cτ,Sτ=1,undefined,Sτ=0.(7)A_\tau= \begin{cases} L_o/C_\tau, & S_\tau= 1,\\ \text{undefined}, & S_\tau= 0. \end{cases} \tag*{(7)}

Thus, Aτ∈(0,1]A_\tau\in(0,1] measures successful interaction relative to the full-information minimum. It is reported jointly with success rather than used as a stand-alone model score.

For successful or active graph-recoverable episodes, we define

Pτ=1−RTLo,NDRτ=Cτ+RT−LoLo.(8)P_\tau= 1 - \frac{R_T}{L_o},\qquad\mathrm{NDR}_\tau= \frac{C_\tau+ R_T - L_o}{L_o}. \tag*{(8)}

Here Pτ∈[0,1]P_\tau\in[0,1] is normalized residual-distance reduction, while NDRτ≥0\mathrm{NDR}_\tau\ge0 is excess charged interaction relative to the offline optimum. For wrong-terminal episodes, RTR_T, PτP_\tau, and NDRτ\mathrm{NDR}_\tau are undefined; their frequency is reported separately.

What an omniscient reference does and does not concede. LoL_o is computed by a searcher that knows the whole graph, so it is fair to ask whether NDR charges an agent for discovery no policy could avoid. The construction rule in §4 bounds how much of it can be: evidence a decision requires is encoded as a prerequisite, so the solver reaches the target only by traversing it. We verify this rather than assert it: every annotated evidence node in the evaluated suite lies on the shortest successful route, with no exceptions. What the oracle keeps is not the ability to skip evidence but the ability to pick the right lookalike candidate first. We do not net that advantage out, so NDR is excess relative to hindsight-optimal selection rather than a claim that any particular access was unreasonable; separating the two needs an informed reference policy the released suite does not contain.

Finally, let IτI_\tau be the number of dispatched accesses that are invalid under the transition contract, and let DτD_\tau be the number of valid re-accesses that leave the whole state sts_t unchanged, outcome flag included, so a state-advancing workflow action is never counted as a repeat. The two sets are disjoint. For successful episodes,

RSRτ=Iτ+DτCτ,(9)\mathrm{RSR}_\tau= \frac{I_\tau+ D_\tau}{C_\tau}, \tag*{(9)}

with lower values indicating fewer invalid or duplicate accesses. RSR is undefined on failure because early termination can produce a deceptively low ratio. Unlike NDR, RSR captures only directly identifiable invalid or state-preserving repetition.

Access budgets

The exact oracle is a reference cost rather than an episode limit. Each instance also declares an information-complete witness of length LiL_i, which exposes all resources marked necessary for an informed terminal decision. Its frozen access budget is

B=⌈mmax⁡(Lo,Li)⌉,(10)B = \lceil m\max(L_o, L_i) \rceil, \tag*{(10)}

where the multiplier mm is fixed before the primary evaluation; we use m=1.5m = 1.5 throughout, so an instance with Lo=12L_o = 12 is run under a budget of 18. On every instance in the released suite Li=LoL_i = L_o, because necessity is enforced through prerequisites that the shortest route must already satisfy; the maximum is therefore inactive here and B=⌈mLo⌉B = \lceil mL_o \rceil in practice. We keep the general form because an instance whose informed witness exceeds its oracle route would otherwise receive a budget that forbids an informed decision. Neither LiL_i nor BB is used as an efficiency numerator. The release reports LoL_o, LiL_i, mm, BB, and B/LoB/L_o for every evaluated instance; no budget is increased during an episode.

Of the 99 failures in the integrated suite, 95 exhaust this budget. They end a median of three accesses from the goal (mean residual 3.02, mean progress 0.766), and 47 of them end within two accesses. Duplicate and invalid accesses make up 7.6% of their charged steps, so the budget is spent mostly on valid, non-repeated accesses. This is consistent with resolving uncertainty among lookalike candidates, but we do not separate reasonable uncertainty resolution from avoidable exploration, and we do not vary mm; budget sensitivity is left to future work.

Benchmark Construction and Validation

Collections

A task specifies a construction procedure, an instance is one frozen executable realization, and an episode is one model run on an instance. DetourBench contains two collections. The Controlled Mechanism Suite builds paired instances across six mechanisms; only the 40 Currency pairs survived the equivalence audit in a form usable for a controlled comparison (§B), and they are what § 5 reports.

The Integrated Workflow Suite contains longer authored tasks grounded in software, clinical, financial, banking, logistics, regulatory, legal, corporate-registry, transit, customs, and security records. These tasks combine multiple sources, scenario constraints, credentials, and workflow actions. Each integrated task contributes one frozen instance, and the twenty-five evaluated here are listed in Appendix G.

Construction and controlled pairing

Construction begins with source records rather than a prompt alone. A builder emits the resource and action graph, prerequisites, terminal conditions, and authored scenario facts. Source-derived content is linked to supporting spans, while authored overlays are labeled separately. A removal audit deletes each node on the oracle route and re-runs the exact search; for tasks 21–24 we also execute content counterfactuals that change one fact and check that the decision flips. Elsewhere semantic roles are documented, not executed (Appendix § 9).

The solver computes LoL_o, generates a shortest-path witness, and replays it under the model-facing evaluator. Each released task ships its graph, initial state, task specification, source corpus, oracle, replayable witness, budget, verifier report, and freeze manifest, and every trajectory records the graph and oracle hashes it ran against.

A controlled pair holds source records, transition topology, actions, target, answer, and oracle bound fixed while changing one declared cue sentence, analogous to holding instructions fixed while toggling access to private task conventions [12]. Canonical artifact diffs admit a pair only when the observed difference is confined to that cue. Additional textual or structural differences cause the pair to be excluded from controlled analysis.

Validation and freeze

Every reported artifact passes four gates: mechanical validity requires schema checks and witness replay; construct validity requires source provenance, labeled overlays, and a structural removal audit, with documented semantic roles for most tasks and executed content counterfactuals for four (Appendix § 9); generation validity checks uniqueness, answer degeneracy, and controlled-pair integrity; and artifact validity freezes the graph, oracle, prompt, metric, evaluator, and budget, with the graph and oracle carrying cryptographic hashes that every trajectory records and every analysis re-checks before reporting.

Development pilots identify malformed graphs, shortcut answers, ambiguous prompts, and evaluator defects. A repair creates a new artifact version and invalidates earlier trajectories. Because model behavior informed some revisions, freezing guarantees artifact consistency but does not make the benchmark an untouched test set. Experimental selection based on model behavior is disclosed separately in § 5. Analysis fails closed on a version or hash mismatch, a runtime budget change, or an incomplete model–task–repeat cell.

Experiments and Results

We evaluate whether outcome-only scoring masks differences in execution efficiency and partial progress. Two experiments do this from opposite directions: a controlled intervention on the mechanism suite, where one sentence is added or withheld and everything else is held fixed, and an observational run over the integrated suite. They use different instances and are reported separately, never pooled; qwen3.6-plus and glm-5.2 appear in both.

A controlled cue intervention

The mechanism suite lets one variable move. Both arms share graph, targets, oracle bound, and correct answer, and the point-in-time view is an available action with its URL on the edge in each; only the seed sentence naming it is removed. We run 40 paired problems, four models, three repeats per arm: a balanced 4×40×3×2=9604 \times40 \times3 \times2 = 960-episode design, 120 episodes per model per arm; Table 1 reports both arms.

Modelsignposted Querysignposted Pass@1signposted Pass³signposted Wasteunsignposted Queryunsignposted Pass@1unsignposted Pass³unsignposted Waste
qwen3.6-plus100%98%95%0.05%42%32%4.2
deepseek-v3.296%69%40%1.468%38%8%3.2
glm-5.287%71%48%1.932%37%32%4.3
claude-opus-4-877%85%62%1.02%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.

Across 160 pairs, removing the sentence drops view use by 63 points and success by 41, while raising out-of-scope reads by 2.9 per episode. In view use, 131 of the 160 model–problem pairs move toward the unsignposted arm, 27 do not move, and 2 move the other way. Successful episodes take longer routes: conditional attainment falls from 0.826 to 0.644 on Qwen and 0.794 to 0.629 on Claude. The endpoint was never withheld, only the sentence pointing at it.

passkpass^{k} separates two failure modes pass@1pass@1 conflates: in the unsignposted arm deepseek-v3.2 holds 38% under pass@1pass@1 but 8% under pass3pass^{3}, landing the answer occasionally rather than reliably, while claude-opus-4-8 falls less under pass3pass^{3}, so its failures are a stable per-problem property.

In the signposted arm 32 of the 40 problems pass above 70% against 13 in the unsignposted arm, so the signposted arm is near a ceiling for current models and the intervention stays measurable because the other one is not.

Because the intervention changes which episodes succeed, we also compare attainment only where both arms succeed: on the n=176n = 176 model–problem–repeat pairs that succeed in both arms, drawn from 31 problems, withholding the signpost lowers conditional attainment from 0.763 to 0.637 (Δ=−0.126\Delta= -0.126; 95% problem-cluster bootstrap interval [−0.156-0.156, −0.099-0.099], 20,000 resamples of problems with all their pairs, seed 20261107) and raises out-of-scope reads from 0.91 to 2.72. Averaged per problem, the decline holds on 23 of the 31 problems (t30=−6.1t_{30} = -6.1).

Experimental setup

The Integrated Workflow Suite contains 25 versioned tasks: 20 frozen before review (tasks 1–20), four authored afterwards (tasks 21–24), and one run alongside tasks 1–20 but left out of their manifest (task 25). We evaluate five model endpoints (claude-opus-5, deepseek-v4-pro, qwen3.6-plus, glm-5.2, kimi-k3) attempting every task three times through a shared scaffold (25 × 5 × 3 = 375 episodes).

Fixed budgets are enforced without runtime unlocking. Infrastructure aborts were rerun; all valid, invalid, and duplicate accesses are charged. In this suite, all completions occurred through charged terminal accesses. All 375 runs carry cryptographic graph and oracle hashes; six tasks (17, 20, and 21–24) ran under a later prompt revision (Appendix G). The task is the unit of comparison: repeats characterize within-task variability, not 75 independent samples.

Outcome and successful-run efficiency

Table 2 reports endpoint success together with attainment and RSR on successful episodes. These conditional metrics should be read jointly with success because models need not succeed on the same tasks.

ModelEpisodesSuccessesSuccess rateCond. attainmentSucc. RSR
Claude757296.0%0.8900.026
Kimi756992.0%0.8610.023
DeepSeek754661.3%0.8030.023
Qwen754560.0%0.8060.040
GLM754458.7%0.8360.034

Table 2. Results on the 25-task Integrated Workflow Suite (N=375N = 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.

Across models, 276 of 375 episodes succeed. Claude and Kimi obtain the highest success rates and conditional attainment. Among the remaining models, however, outcome and efficiency orderings differ: GLM has the lowest success rate but higher conditional attainment than DeepSeek and Qwen. This is a descriptive ranking reversal because conditional attainment is computed on model-specific successful subsets. Averaging per task rather than per episode keeps GLM above both (0.811 vs. 0.793 for Qwen and 0.789 for DeepSeek). Restricting to the thirteen tasks solved by all models again puts GLM third (0.851 vs. 0.829 for Qwen and 0.824 for DeepSeek). Qwen and DeepSeek differ by at most 0.005 and swap on the nineteen tasks run under the original prompt, so we do not order them. Successful-run RSR ranges from 0.023 to 0.040. Its ordering differs from both success and attainment because RSR isolates invalid and duplicate accesses, whereas attainment captures all charged work beyond the Exact oracle.

Matched success with different costs

Eight tasks—2, 3, 4, 5, 6, 14, 19, and 25—are solved in all three repeats by all five models. Their between-model attainment spreads range from 0.074 to 0.190. Because every episode succeeds, these differences cannot be attributed to unequal success counts.

The widest is task 3 (Lo=15L_o = 15, spread 0.190), where mean accesses run from 17.0 to 21.7 across models. The extra cost is not repetition: the best and worst models both record RSR = 0.000 (zero repeats or invalid calls) yet differ in attainment by 0.189. RSR detects overt repeats; attainment also catches valid but unnecessary exploration (Appendix § 10). These tasks establish cost variation exists, not prevalence, as separation was a screening criterion.

Failure-aware analysis

Of the 375 scored episodes, 99 fail: 95 exhaust the access budget, two stop in a recoverable state, and two enter an absorbing wrong state. Table 5 (Appendix § 11) reports progress and NDR over the 97 failures that remain active and recoverable. Wrong-terminal episodes are excluded because they have no finite residual distance.

ModelFailuresRecoverableTasksWrongProgressNDR
Claude33100.5191.037
Kimi66400.8300.678
DeepSeek29291300.7120.791
Qwen30281620.7790.727
GLM31311400.8290.678
Total9997–20.7700.737

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.

These columns are not a model comparison: the five models fail on largely disjoint task sets (Claude on 1 instance, Kimi on 4, DeepSeek on 13, GLM on 14, Qwen on 16). Across all 97 recoverable failures, progress ranges from well short of the goal to one access away, and the two absorbing commitments have no residual distance at all. On task 18 (Lo=20L_o = 20), six failures collapse to one binary score; our decomposition separates two that stopped one access from success, three that exhausted budget at 0.85–0.95 progress, and one absorbing commitment with no residual distance (Appendix § 12).

Selection boundary

The 20-task manifest was frozen on August 28, 2026; model behavior informed authoring for eight tasks and replacement of two uninformative instances. Tasks 21–24 were authored after review; two of them (21 and 22) were revised after earlier model runs, and only the final revision, on which all five models were run, is reported. Task 25 was run with tasks 1–20 under the original prompt and passes the same screen, but was left out of the frozen manifest; we add it here. The 8/17 cost/outcome split reflects selection choices rather than prevalence. Retention rules, excluded candidates, and hashes are in Appendix § 8.

Conclusion and Limitations

DetourBench evaluates interactive agents through trajectory-level transition systems with provable minimum-action bounds LoL_o and exact residual work RTR_T, preventing efficient success, exploratory success, recoverable near-misses, and irreversible error from collapsing into one score. Experiments confirm this distinction is practical: one withheld sentence moves the same model on the same task, eight tasks separate models purely by cost under 100% success, and binary failure scores decompose into near-complete, costly-incomplete, and irreversible cases.

Four limitations bound this: model-informed screening reflects released suite properties rather than population prevalence; three repeats limit stochastic analysis; the omniscient oracle does not net out lookalike selection advantage; and exactness holds under authored semantics, whose semantic necessity is executed for only four tasks. Future work should evaluate pre-registered held-out suites, widen repeat and model coverage, add human baselines, and develop informed reference policies separating discovery from planning error.

Complete Integrated Task Graph

Figure 3. Complete graph for Task 18 (freight-dispatch cutoff, Lo=20L_o = 20). All 35 nodes and 45 discovery edges are shown. Blue nodes and orange edges are accessed by one replayed shortest witness (Lo=20L_o = 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.

Construction and selection audits

Construction audits materially restricted which artifacts were eligible for analysis. The counts below are paired artifacts as they stood at audit time, before repair and freeze, and each pair is two renderings of one problem. Table 3 summarizes the principal findings and the corresponding corrective actions. Rejected artifacts remain available in the release but are not used to support the reported comparisons.

AuditFindingAction
Paired-arm equivalenceAll 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 diversityEight 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 balanceEarly Sufficiency and Disposition generators produced a fixed correct answer direction.Both answer directions are now instantiated and checked during validation.
Scoring normalizationExact-string matching treated equivalent citation formats as different answers, producing 38 false negatives among 61 inspected episodes.Structured outputs are canonicalized before semantic comparison.

Table 3. Summary of benchmark-construction audits.

The formal 20-task evaluation set was selected after observing model behavior. Two instances that separated the models by neither measure were replaced by tasks 1 and 14. A task was retained if models differed in empirical success rate or, when all models succeeded, if the between-model conditionalattainment spread was at least twice the mean within-model standard deviation across the three repeats. This rule and the excluded candidates are recorded in paper_selection_20.json. Tasks 21–24 were authored after review and did not pass through this screen; each separates the models by outcome. Task 25 was evaluated in the same August runs as tasks 1–20 but is not in that manifest; it passes the screen by cost (attainment spread 0.074 against a mean within-model standard deviation of 0.020, ratio 3.8). Tasks 21–25 are released with their own frozen graphs, oracles, and hashes.

ModelMean chargedAttainmentRSR
Claude17.00.8820.000
Kimi17.70.8500.019
Qwen21.00.7170.014
DeepSeek21.30.7050.015
GLM21.70.6930.000

Table 4. Task 3, exact oracle Lo=15L_o = 15, three repeats per model. RSR counts invalid and duplicate accesses only.

Necessity audits: what is checked

Structural removal. For every task we delete each node on the oracle route (all edges into it and out of it) and re-run the exact search of Appendix I. Of the 314 such nodes across the 25 tasks, removing 309 leaves the target unreachable. The other five have substitutes: one section in task 1 (the bound rises from 9 to 10), three records in task 9 (bounds 13, 11, and 11), and one search page in task 19 (bound unchanged at 16). This check shows that the route needs these nodes; it does not show that their content matters to the decision, because necessity is enforced through prerequisites.

Executed content counterfactuals. Tasks 21–24 each ship a frozen necessity_audit.json in which a domain decision function is re-run on edited inputs. Each task runs four edits: change one key fact, change a relation or scope, remove a required piece of evidence, and, as a negative control, replace the distractor records. In all four tasks every edit gives the expected result, and an independent reference implementation agrees on the baseline and all four edits. In task 23 (customs ruling revocation), for example, the baseline determination is reliance protection at a 5.3% duty rate. Moving the entry date from 1993-04-15 to 1993-06-01, or setting good-faith reliance to false, changes it to the revocation tariff at 20.0%. Removing required evidence leaves no determination. Replacing the twelve distractor records leaves the baseline unchanged. These counterfactuals are authored edits to the inputs, not revised observations, and they cover a finite set of edits rather than every node.

Documented roles. For tasks 8–20 the release records an authored semantic role for each evidence node or edge, without an executed content counterfactual; tasks 1–7 and 25 carry the structural check only. For these 21 tasks semantic necessity rests on the authored scenario, which is part of the limitation stated in Section 6.

Task 3, transitive policy check: per-model costs

All five models solve task 3 on every repeat, so endpoint success assigns them the same score. Their charged accesses do not agree, and neither does what the extra accesses consist of (Table 4).

The two models with an RSR of exactly zero are the most and least efficient on this task. Neither repeats an access or issues an invalid one, so a redundancy measure rates them identically, while their attainment differs by 0.189: GLM spends 6.7 accesses beyond the bound on unrelated dependencies, rejected remediation candidates, and release metadata, all of them valid and none of them repeated. That gap is invisible to RSR and is exactly what an oracle-relative measure is for.

Failure decomposition across models

Table 5 gives the per-model counts behind the decomposition reported in § 5.

Task 18 failure decomposition

Task 18 makes the distinction concrete. Its exact oracle requires Lo=20L_o = 20 accesses, with a budget of 30. Claude and Kimi succeed in all three repeats, using 21.7 and 23.7 accesses on average. DeepSeek, Qwen, and GLM each succeed once, but their failed trajectories terminate in different states.

DeepSeek and GLM each produce one recoverable gave_up trajectory after reaching committed_a, only one required access from success. Both have progress 0.95, with NDR values of 0.30 and 0.35, respectively. Their budget-exhausted runs are less efficient: DeepSeek ends with progress 0.85 and NDR 0.65, while GLM reaches progress 0.95 but incurs NDR 0.55 through additional exploration. Qwen likewise has one budget-exhausted run with progress 0.85 and NDR 0.65, but its other failure commits to rejected_b, an absorbing wrong state for which residual metrics are undefined.

Binary scoring assigns all six trajectories the same failure value. The graph-based decomposition instead separates a one-step-away recoverable execution, inefficient budget exhaustion, and an irreversible incorrect commitment.

Per-task evaluation results

Table 6 reports the 25 evaluation tasks, 1–20 in manifest order followed by the four authored after review and task 25. Success spread is the difference between the largest and smallest model success rates. Attainment spread is computed across model-level conditional attainment values that are defined for the task. The table reports raw descriptive spreads rather than normalizing them by a standard deviation estimated from only three repeats.

IDTaskDomainSeparates byLoL_oSuccesssuccΔ\DeltaattΔ\Delta
1Fall-protection standardRegulatoryoutcome97/151.000.107
2Direct advisory fixSoftwarecost1015/150.000.091
3Transitive policy checkSoftwarecost1515/150.000.190
4Multi-parent remediationSoftwarecost1515/150.000.118
5Multiple safe versionsSoftwarecost1315/150.000.147
6Conflicting fix evidenceSoftwarecost1515/150.000.130
7Thiazide refill provenanceClinicaloutcome126/151.000.028
8Warfarin INR conflictClinicaloutcome118/151.000.250
9Opioid refill packetClinicaloutcome118/151.000.249
10NSAID class reviewClinicaloutcome1212/150.670.225
11ACE inhibitor in pregnancyClinicaloutcome1214/150.330.205
12Encounter episode boundaryClinicaloutcome127/151.000.150
13Restatement relianceFinanceoutcome1211/151.000.113
14Reissued card lifecycleBankingcost1715/150.000.139
15Card PIN resetBankingoutcome1413/150.670.188
16Settled comment letterFinanceoutcome1211/150.670.064
17Pinned upgrade bundle†Softwareoutcome107/151.000.079
18Freight dispatch cutoffLogisticsoutcome209/150.670.209
19Periodontal onset dateClinicalcost1615/150.000.109
20Boundary dispute triage†Legaloutcome1910/151.000.259
21Lapsed-entity consolidation†Corporateoutcome149/151.000.075
22Weekend timetable exception†Transitoutcome1411/151.000.122
23Ruling revocation reliance†Customsoutcome147/151.000.263
24Build-tag CVE exemption†Securityoutcome146/151.000.019
25PyPI multi-parent remediationSoftwarecost1615/150.000.074

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.

The eight tasks labeled cost have zero success spread because every model succeeds in every repeat. The remaining seventeen tasks separate models by endpoint outcome. Since this categorization follows the model-informed screen described above, the resulting 8/17 split is a property of the released evaluation set rather than a population estimate.

The release contains the frozen graphs, oracles, and artifact hashes, and the harness that reruns every episode against a configured endpoint; recorded model trajectories are not part of the public release. The harness sets no temperature or top-pp, so endpoints sample at provider defaults, and it stops an episode after 60 model turns; no reported episode reached that limit (the longest used 24). Tasks 1–20 and 25 were run on August 27–29, 2026, and tasks 21–24 on November 4–5, 2026.

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.

Additional endpoint: HY4-Preview

After the main runs were frozen we ran one further endpoint, HY4-Preview, on tasks 1–24 with three repeats (72 episodes; it was not run on task 25), against the same frozen graphs, oracles, bounds, and budgets; every episode’s graph and oracle hashes match the released artifacts. All 72 episodes used the later prompt revision marked † in Table 6. That revision rewords the system prompt and also the not-ready message, which now tells the agent that prerequisite records remain unread. The comparison with Table 2 is therefore not like-for-like on the 18 unmarked tasks, and we report HY4-Preview separately rather than ranking it.

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.

ModelEpisodesSuccessesSuccess rateCond. att.Succ. RSRProgressNDR
HY4-Preview725272.2%0.8210.0250.8190.696

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.

All 20 failures exhaust the budget; none submits a wrong determination, so all are recoverable, and they fall on 12 of the 24 tasks. On the seven of these tasks that every main-run model solves on every repeat (task 25 is the eighth), HY4-Preview succeeds in 20 of 21 episodes.

Cost of the exact oracle

We timed the exact search on the 25 frozen task graphs in single-threaded CPython 3.10 on an Intel Xeon server. Runtime is the median of five runs; peak memory is measured with tracemalloc in one further run; states are the distinct (visited set, inventory) states the breadth-first search generates before it reaches the target. All 25 recomputed bounds equal the frozen LoL_o.

QuantityMinimumMedianMeanMaximum
Graph nodes163033.762
Search states generated12871,27213,541
Runtime (ms)0.070.8520.3273.4
Peak memory (MiB)0.020.091.7423.97

Table 8. Cost of the exact oracle across the 25 frozen tasks.

The most expensive instance is task 20 (13,541 states, 273 ms, 24 MiB). These figures describe the released graphs; because the search state is a set of visited resources, they are not a bound for substantially larger graphs.

References

  1. [1]Peter Anderson, Angel Chang, Devendra Singh Chaplot, Alexey Dosovitskiy, Saurabh Gupta, Vladlen Koltun, Jana Kosecka, Jitendra Malik, Roozbeh Mottaghi, Manolis Savva, and Amir R. Zamir. On evaluation of embodied navigation agents. arXiv preprint arXiv:1807.06757, 2018. URL https://arxiv.org/abs/1807.06757.
  2. [2]Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1–2):99–134, 1998. doi: 10.1016/S0004-3702(98)00023-X.DOI
  3. [3]Jiayu Liu, Cheng Qian, Zhaoch en Su, Qing Zong, Shijue Huang, Bingxiang He, and Yi R. Fung. CostBench: Evaluating multi-turn cost-optimal planning and adaptation in dynamic environments for LLM tool-use agents. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12826–12858. Association for Computational Linguistics, 2026. doi: 10.18653/v1/2026.acl-long.584.DOI
  4. [4]Xing Han Lü, Amirhossein Kazemnejad, Nicholas Meade, Arkil Patel, Dongchan Shin, Alejandra Zambrano, Karolina Stançzak, Peter Shaw, Christopher J. Pal, and Siva Reddy. AgentRewardBench: Evaluating automatic evaluations of web agent trajectories. In The Second Conference on Language Modeling, 2025. URL https://openreview.net/forum?id=FQcUZMP1vu.arxiv.org/abs/2504.08942
  5. [5]Chang Ma, Junlei Zhang, Zhihao Zhu, Cheng Yang, Yujiu Jin, Zhenzhong Lan, Lingpeng Kong, and Junxian He. AgentBoard: An analytical evaluation board of multi-turn LLM agents. In Advances in Neural Information Processing Systems, volume 37, pages 74325–74362, 2024. doi: 10.52202/079017-2365.
  6. [6]Grégoire Mialon, Clémentine Fourrier, Craig Swift, Thomas Wolf, Yann LeCun, and Thomas Scialom. GAIA: A benchmark for general AI assistants. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=fibxvahvs3.arxiv.org/abs/2311.12983
  7. [7]Panagiotis Michelakis, Yiannis Hadjiyanis, and Dimitrios Stamoulis. CORE: Full-path evaluation of LLM agents beyond final state. In NeurIPS 2025 Workshop on Language, Agent, and World Models, 2025. URL https://arxiv.org/abs/2509.20998.
  8. [8]OpenAI. Introducing SWE-bench Verified, August 2024. URL https://openai.com/index/introducing-swe-bench-verified/.
  9. [9]Christos H. Papadimitriou and Mihalis Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84(1):127–150, 1991. doi: 10.1016/0304-3975(91)90263-2.DOI
  10. [10]Peter Pirolli and Stuart Card. Information foraging. Psychological Review, 106(4):643–675, 1999. doi: 10.1037/0033-295X.106.4.643.DOI
  11. [11]Jiaqi Shao, Hanck Chen, Wei Zhang, Maxm Pan, and Bing Luo. Do agent benchmarks measure capability? protocol validity in the age of agentic AI. arXiv preprint arXiv:2607.22368, 2026. URL https://arxiv.org/abs/2607.22368.
  12. [12]Hanlin Tian, Minhao Li, Yu Mi, Sihan Zhu, Zhao Yang, Yuxiang Wang, Hongquan Zhu, and Qiufei Hu. Ignorance or incompetence? constructing knowledge-gated, verifiable tasks for LLM agents. arXiv preprint arXiv:2608.30322, 2026. URL https://arxiv.org/abs/2608.30322.
  13. [13]Harsh Trivedi, Tushar Khot, Mareike Hartmann, Ruskin Manku, Vinty Dong, Edward Li, Shashank Gupta, Ashish Sabharwal, and Niranjan Balasubramanian. AppWorld: A controllable world of apps and people for benchmarking interactive coding agents. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 16022–16076. Association for Computational Linguistics, 2024. doi: 10.18653/v1/2024.acl-long.850.DOI
  14. [14]Hongru Wang, Cheng Qian, WanJun Zhong, Xiusi Chen, Jiahao Qiu, Shijue Huang, Bowen Jin, Mengdi Wang, Kam-Fai Wong, and Heng Ji. Acting less is reasoning more! teaching model to act efficiently. arXiv preprint arXiv:2504.14870, 2025. URL https://arxiv.org/abs/2504.14870.
  15. [15]Tianbao Xie, Danyang Zhang, Jixuan Chen, Xiaochuan Li, Sheng Zhao, Ruisheng Cao, Toh Jing Hua, Zhoujun Cheng, Dongchan Shin, Fangyu Lei, Yitao Liu, Yiheng Xu, Shuyan Zhou, Silvio Savarese, Caiming Xiong, Victor Zhong, and Tao Yu. OSWorld: Benchmarking multimodal agents for open-ended tasks in real computer environments. In Advances in Neural Information Processing Systems, volume 37, 2024. doi: 10.52202/079017-1650.
  16. [16]Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abhishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. WebArena: A realistic web environment for building autonomous agents. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=rmw1l98uQ.arxiv.org/abs/2307.13854
  17. [17]Yuxuan Zhu, Tengjun Jin, Yada Pruksachatkun, Andy Zhao, Shu Liu, Sasha Cui, Sayash Kapoor, Shayne Longpre, Kevin Meng, Rebecca Weiss, Fazl Bare z, Rahul Gupta, Jwala Dhamala, Jacob Merizian, Mario Giulianelli, Harry Coppock, Cozmin Udude, Jasjeet Sekhon, Jacob Steinhardt, Antony Kellermann, Sarah Schwettmann, Matei Zaharia, Ion Stoica, Percy Liang, and Daniel Kang. Establishing best practices for building rigorous agentic benchmarks. arXiv preprint arXiv:2507.02825, 2025.

Paper details

vlnc:W_9ft8758r
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents