Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success
Amir H. Rezaeian, Weiyi Sun, Yassine Benajiba, Dan Roth
Careful, well-formalized evaluation protocol with a clear message, but conceptually incremental, crowded space, and the headline divergence and validation benefit are narrow (fail to transfer to τ³-bench).
Abstract
Tool-use benchmarks often score agents by final task success, but terminal outcomes can obscure whether the intermediate tool-call trajectory was executable. We propose prefix executability as a trajectory-level evaluation protocol for tool-using agents. The protocol measures whether every prefix of a predicted tool-call sequence remains executable under tool schemas, state preconditions, and data dependencies, and summarizes reliability using Prefix Executability Curves (PEC), First-Error Depth (FED), Trajectory Executability Rate (TER), horizon-normalized AUC-PEC, and Recovery Rate (RR). We instantiate the protocol on stratified samples from BFCL-v3 multi-turn and ToolSandbox, and on the complete Airline/Retail base splits of -bench. We observe that outcome-only and prefix-level rankings diverge: agents whose execution is conditioned on an unverified plan often achieve higher point-estimate final success than non-plan-conditioned baselines while substantially lowering TER and AUC-PEC. These divergences are precisely the failure modes that prefix executability is designed to expose: they reveal whether apparent success rests on an executable trajectory, where invalidity first enters, and whether success follows recovery from an earlier failure. As a validation intervention, explicit pre-execution plan checking can improve executable-prefix survival while maintaining competitive terminal success. These results show that final success alone is insufficient for evaluating tool-use agents and that prefix-level executability provides an actionable reliability signal for comparing agents, diagnosing failures, and assessing validation mechanisms.
AI Impact Assessments
(1 model)Scientific Impact Assessment: Prefix Executability
Core Contribution
The paper proposes prefix executability as a trajectory-level evaluation protocol for tool-using LLM agents. It defines First-Error Depth (FED) and builds a metric family on it: the Prefix Executability Curve (PEC, a fixed-cohort survival function), Trajectory Executability Rate (TER), horizon-normalized AUC-PEC, and Recovery Rate (RR). Executability is checked by a deterministic, reference-free scorer that tests schema validity, dependency binding, preconditions, and state acceptance. A rollout is "executable" up to the first rejected transition, so alternative valid paths get credit and no gold trajectory is needed.
The central empirical claim is that outcome-only and prefix-level rankings diverge. For example, Plan-Conditioned ReAct has the highest final success on BFCL (0.94 with GPT-5.4), but its TER is 0.47. With Llama-4 on BFCL, TER is 0.05 while success is 0.74, so 93% of successes come after an earlier invalid prefix. A "Dual-Loop" planner-verifier is used as a probe and restores TER to about 0.9.
The conceptual novelty is modest. The metric family is essentially survival analysis applied to action validity, and the executability predicate largely reuses existing benchmark validators. The useful parts are the clean formalization, the decomposition P(Y)=q·s+(1−q)·r, and the explicit separation of "success" from "success after recovery."
Methodological Rigor
Strengths:
Weaknesses:
Potential Impact
The protocol is easy to adopt: any benchmark with a simulated environment and validators can compute FED and TER from logs. It could become a standard diagnostic alongside success rate, especially for stateful or high-stakes workflows such as transactions and database mutations. It also yields a prefix-local predicate usable for runtime monitoring and for process-level reward shaping in RL for agents. This suggests uses as a verifiable, non-LLM step-level reward.
Limits on impact:
Timeliness & Relevance
Agent reliability and evaluation beyond pass-rate is a live concern, and the NeurIPS Evaluations & Datasets track is a natural venue. The paper is timely, but the novelty is incremental relative to concurrent trajectory-evaluation work.
Strengths & Limitations
Strengths:
Limitations:
Clarity
The writing is precise and well organized, though dense and heavy with caveats and notation. Tables are large, and the main message is clear.
Overall
This is a competent, careful, moderately useful evaluation-methodology contribution. It is likely to be cited as one among several trajectory-aware evaluation proposals, and it is unlikely to reshape practice.
Generated Oct 30, 2026
Comparison History (0)
Careful, well-formalized evaluation protocol with a clear message, but conceptually incremental, crowded space, and the headline divergence and validation benefit are narrow (fail to transfer to τ³-bench).