cs.AINov 16, 2026

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

Authors: Hanlin Tian, Sihan Zhu, Zhao Yang, Yuxiang Wang, Zhiquan Hu, Yu Mi, Hongquan Zhu, Qiufei Hu

Organizations: Northwest Polytechnical University Xi’an · Nanyang Technological University · East China Normal University · Tongji University · 

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.

Figures & tables

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories

    Jul 19, 2026Babak Barazandeh, Subhabrata Majumdar, George MichailidisLLM Agent EvaluationAI Agent Evaluation

  2. Redundant or Necessary? A Benchmark for Detecting Redundant Steps in Agent Trajectories

    May 28, 2026Liang Zhu, Bo Yang, Zhinuo Zhou +5LLM Agent EvaluationAgent Trajectory Analysis