Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success

Amir H. Rezaeian; Weiyi Sun; Yassine Benajiba; Dan Roth

cs.AIOct 29, 2026

Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success

Authors: Amir H. Rezaeian, Weiyi Sun, Yassine Benajiba, Dan Roth

Organizations: Oracle AI

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 $τ^3$ -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.

Figures & tables

Metric / signal	Ref.-free	Exec.-state	Prefix signal	Recovery
Exact Call Match	No	No	No	No
Trajectory Match	No	No	No	No
Final Success ( $Y$ )	Yes	Yes	No	Indirect
$\mathrm{PEC}(k)$	Yes	Yes	Survival at $k$	No
$\widehat{\mathrm{PEC}}_{\mathrm{elig}}(k)$	Yes	Yes	Conditional at $k$	No
TER	Yes	Yes	Full horizon	No

Table 1: Coverage of standard and prefix-level evaluation metrics. Ref.-free means that a metric can credit alternative executable trajectories rather than requiring agreement with a single reference path. Exec.-state means that the metric depends on environment execution or explicit validation semantics.

\mathrm{PEC}(k)

is the fixed-cohort survival curve in Eq. ( 3 );

\widehat{\mathrm{PEC}}_{\mathrm{elig}}(k)

is the empirical eligible-depth diagnostic in Eq. ( 6 ). TER is the endpoint event

\mathrm{FED}=T+1

, mean

\mathrm{FED}_{i}

summarizes first-error depth, AUC-PEC summarizes the horizon-normalized prefix-survival profile, and RR conditions on

\mathrm{FED}\leq T

Dataset	LLM	Method	TER	Mean FED	AUC-PEC	RR- Eligible	RR	Final Success
BFCL	GPT-5.4 (high)	ReAct	0.69 [0.63,0.76]	5.61 [5.28,5.92]	0.83 [0.79,0.87]	61	0.00 [0.00,0.06]	0.61 [0.55,0.68]
		Prompt Planning	0.78 [0.72,0.83]	5.72 [5.39,6.05]	0.85 [0.81,0.89]	44	0.00 [0.00,0.08]	0.78 [0.72,0.83]
		Plan-Cond. ReAct	0.47 [0.40,0.54]	4.11 [3.73,4.50]	0.54 [0.48,0.60]	106	0.88 [0.80,0.93]	0.94 [0.90,0.96]
		Dual-Loop	0.94 [0.91,0.97]	6.41 [6.12,6.70]	0.96 [0.93,0.98]	12	0.00 [0.00,0.24]	0.94 [0.90,0.97]
	GPT-4.1	ReAct	0.62 [0.55,0.69]	5.18 [4.84,5.51]	0.76 [0.72,0.81]	76	0.00 [0.00,0.05]	0.52 [0.45,0.58]
		Prompt Planning	0.79 [0.72,0.84]	5.84 [5.54,6.16]	0.87 [0.83,0.91]	43	0.02 [0.00,0.12]	0.77 [0.71,0.82]

Table 2: Benchmark results with

200

stratified sampled instances for BFCL multi-turn and

200

multi-label-stratified sampled instances for ToolSandbox under three LLM conditions. All entries are empirical estimates; table headers omit hats for readability. Bracketed values are

95\%

confidence intervals. Intervals for TER, mean FED, AUC-PEC, and final success use

10{,}000

task-level percentile bootstrap resamples; RR intervals use Wilson score intervals with the RR-Eligible denominator. RR-Eligible counts episodes with

\mathrm{FED}\leq T

and is reported without an interval. Bold point estimates mark column maxima within each dataset–LLM block, including ties at the displayed precision; boldface does not indicate statistical significance. Higher TER, AUC-PEC, and final success indicate stronger respective scores; mean FED must also be interpreted with rollout horizon; RR is better only conditional on entering the failure regime and should be interpreted with RR-Eligible.

Figure 1: Prefix-executability curves on the $200$ -instance BFCL multi-turn sample and the $200$ -instance ToolSandbox sample using GPT-5.4 (high). Each point plots $\widehat{\mathrm{PEC}}(k)$ with the fixed-cohort estimator in Eq. ( 4 ). The BFCL panel displays depths $k\leq 10$ ; under Eq. ( 3 ), late-depth declines can reflect both prefix failures and termination. Appendix Table G.1 reports early-depth checkpoints for all LLM conditions.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Evaluation	Primary signal	Relation to prefix executability
T-Eval [ 7 ]	Component capabilities: planning, reasoning, retrieval, understanding, instruction following, and review.	Diagnoses component abilities; PEC tracks executable prefixes across depths, and FED identifies the first invalid action.
ToolSandbox [ 4 ]	Task-specified required and prohibited conditions over states and traces.	Checks required or prohibited conditions; PEC/FED localize first non-executability and survival over depth.
$\tau$ -bench [ 6 ] and $\tau^{3}$ -bench [ 23 ]	Task outcomes in policy-constrained user–agent–environment interaction, including terminal goal-state checks.	Provide stateful environments where prefix metrics complement terminal reward.
TRAJECT-Bench [ 8 ]	Reference-based tool/argument/order matching and reference-free, LLM-judged trajectory satisfaction.	Combines reference-based and judged trajectory quality; prefix metrics measure benchmark-grounded executability, first failure, and recovery.
ToolPRMBench [ 9 ]	Correct/incorrect step cases for process-reward-model evaluation.	Assesses process judges; prefix metrics use benchmark execution semantics without a learned reward model.
AgentProcessBench [ 10 ]	Human-labeled step effectiveness; step and first-error prediction accuracy.	Evaluates agreement with human process labels; prefix metrics directly test benchmark execution feasibility.

Appendix

Table A.1: Evaluation units and signals across trajectory and process evaluation protocols.

Step	Emitted action	Benchmark outcome
1	Attempt to remove a contact using its phone number as its stored identifier.	Rejected because no matching identifier exists; state unchanged.
2	Search for the contact by phone number.	Returns the contact’s stored identifier.
3	Remove the contact using the returned identifier.	Accepted; the requested contact is removed.

Appendix

Table C.1: Illustrative repair after an invalid first action. The complete observed trajectory is retained even though prefix survival ends at the first step.

Figure D.1: Dual-Loop validation intervention. The planner proposes a structured candidate plan, the verifier either accepts it or returns targeted feedback, and the executor emits the only environment-facing actions scored by the prefix-level metrics.

GPT-5.4 (high)
Method	TER	Mean FED	AUC-PEC	RR (s/n)	Final success
ReAct	.95 [.91,.98]	5.92 [5.53,6.31]	.95 [.91,.98]	.22 [.06,.55] (2/9)	.43 [.35,.51]
Prompt	.94 [.90,.98]	5.73 [5.34,6.13]	.94 [.91,.98]	.10 [.02,.40] (1/10)	.46 [.38,.54]
Plan-Cond.	.93 [.88,.96]	5.84 [5.45,6.24]	.93 [.89,.96]	.25 [.09,.53] (3/12)	.51 [.43,.59]
Dual-Loop	.93 [.89,.97]	5.74 [5.36,6.14]	.93 [.89,.97]	.27 [.10,.57] (3/11)	.46 [.38,.53]
GPT-4.1

Appendix

Table F.1: Complete Airline/Retail base-split audit. Brackets are

95\%

intervals. For RR, s/n is the exact recovery-success/eligible count. Prompt denotes Prompt Planning; Plan-Cond. denotes Plan-Conditioned ReAct. All values are empirical estimates.

Model	ReAct	Prompt	Plan-Cond.	Dual-Loop
GPT-5.4 (high)	86k / 57s	94k / 68s	95k / 68s	98k / 83s
GPT-4.1	142k / 65s	156k / 70s	161k / 73s	180k / 78s
Llama-4 Maverick	374k / 61s	409k / 66s	412k / 67s	399k / 66s

Appendix

Table F.2: Mean agent tokens / mean cumulative agent-call latency on the Airline/Retail audit; k denotes thousands of tokens and s denotes seconds. Prompt and Plan-Cond. abbreviate Prompt Planning and Plan-Conditioned ReAct.

Configuration	$\Delta$ TER	$\Delta$ AUC-PEC	$\Delta$ Final	$\Delta$ Tokens / $\Delta$ Latency
Deterministic acceptance	$+.000$ [ $-.018,+.018$ ]	$-.003$ [ $-.018,+.008$ ]	$-.073$ [ $-.140,-.012$ ]	$-8.4$ k / $-3.2$ s
GPT-5.4 $K_{\mathrm{val}}=1$	$-.006$ [ $-.030,+.012$ ]	$-.010$ [ $-.030,+.005$ ]	$-.012$ [ $-.079,+.055$ ]	$+0.7$ k / $+43.1$ s
GPT-4.1 $K_{\mathrm{val}}=5$	$+.000$ [ $-.018,+.018$ ]	$+.000$ [ $-.007,+.008$ ]	$-.085$ [ $-.165,-.006$ ]	$+7.1$ k / $+30.9$ s
GPT-5.4 $K_{\mathrm{val}}=5$	$+.006$ [ $-.018,+.030$ ]	$+.006$ [ $-.015,+.030$ ]	$+.000$ [ $-.073,+.073$ ]	$+40.7$ k / $+176.9$ s

Appendix

Table F.3: Matched verifier-sensitivity differences against the paired Plan-Conditioned ReAct rerun, with

95\%

paired task-bootstrap intervals. Model names identify the verifier; the planner and executor remain GPT-5.4-high. The deterministic-acceptance condition makes no verifier call and changes the executor’s instructions.

Dataset	LLM	Method	PEC@1	PEC@2	PEC@3	PEC@4
BFCL	GPT-5.4 (high)	ReAct	0.95 [0.93,0.98]	0.90 [0.85,0.94]	0.81 [0.75,0.86]	0.68 [0.61,0.74]
		Prompt Planning	0.96 [0.93,0.98]	0.88 [0.83,0.93]	0.82 [0.77,0.88]	0.70 [0.64,0.77]
		Plan-Cond. ReAct	0.77 [0.70,0.82]	0.61 [0.55,0.69]	0.49 [0.42,0.56]	0.42 [0.36,0.49]
		Dual-Loop	0.98 [0.96,0.99]	0.97 [0.94,0.99]	0.94 [0.91,0.97]	0.82 [0.77,0.88]
	GPT-4.1	ReAct	0.93 [0.89,0.96]	0.84 [0.79,0.89]	0.74 [0.68,0.80]	0.61 [0.55,0.68]
		Prompt Planning	0.97 [0.94,0.99]	0.93 [0.89,0.96]	0.86 [0.81,0.91]	0.71 [0.65,0.77]

Appendix

Table G.1: Depth-wise prefix executability for the

200

-instance BFCL multi-turn sample and the

200

-instance ToolSandbox sample under three LLM conditions. All entries are empirical estimates. Bracketed values are

95\%

percentile confidence intervals from

10{,}000

task-level bootstrap resamples. PEC@

k

uses the fixed-cohort survival estimate in Eq. ( 4 ): the numerator counts rollouts with

\mathrm{FED}>k

, and the denominator is all evaluated rollouts in the dataset-LLM-method block.

Tool-Use Evaluation

Tool-use evaluation measures whether AI agents select, call, and rely on tools correctly, efficiently, and safely across realistic tasks.

See all 99 papers

Beyond Function Calling: Benchmarking Tool-Using Agents under Tool-Environment Unreliability
Jun 24, 2026Yang Tian, Zhengpeng Shi, Yu Zhou +1AI Agent Reliability AI Agent Benchmarks
School of AI, Shanghai Jiao Tong University1 · School of Cyber Science and Engineering, Southeast University2
Beyond Task Completion: A Verification-vs.-Conformance Gap in Tool-Evolving Agents
Apr 1, 2026Alibek Kaliyev, Artem MaryanskyyAI Agent Reliability Tool-Use Evaluation
The University of Texas at Austin · Austin, Texas, USA · Uber +1
ToolFailBench: Diagnosing Tool-Use Failures in LLM Agents
Jul 6, 2026Harsh SoniAI Agent Reliability Tool-Use Evaluation
UC Berkeley

Jun 24, 2026J/K move · Enter open · S save

Beyond Function Calling: Benchmarking Tool-Using Agents under Tool-Environment Unreliability

Yang Tian, Zhengpeng Shi, Yu Zhou, Bo Zhao

School of AI, Shanghai Jiao Tong University1 · School of Cyber Science and Engineering, Southeast University2

AI Agent Reliability AI Agent Benchmarks Tool-Using Agents Tool Use LLM Agent Reliability

Open paper AskPDF arXiv

Large language models are increasingly deployed as agents that solve tasks by interacting with external tool environments. Although recent tool-use benchmarks increasingly cover complex task settings, they still largely assume clean, stable, and trustworthy tool environments, leaving tool-environment unreliability insufficiently examined. We introduce ToolBench-X, a benchmark for evaluating agents under recoverable reliability hazards. ToolBench-X contains executable multi-step tasks across diverse domains and sequential, parallel, and mixed workflows, each paired with deterministic tools and a canonical final answer for automatic evaluation. Starting from clean tool environments, ToolBench-X injects five structured hazard types: Specification Drift, Invocation Error, Execution Failure, Output Drift, and Cross-source Conflict. Crucially, each injected instance remains solvable through at least one valid recovery path, such as retrying, fallback, verification, or cross-checking. Experiments reveal a substantial reliability gap: agents that perform well with reliable tools often fail under recoverable hazards. Further analysis shows that failures are driven less by tool-use volume or inference budget than by limited hazard diagnosis and ineffective recovery. Targeted recovery hints recover many failed tasks, while test-time scaling yields more limited gains. These results suggest that tool-use evaluation should move beyond function-call accuracy toward task completion under unreliable tool environments. The code and data is available at https://github.com/Foreverskyou/ToolBench-X.

Abstract

Tool-Use Evaluation

Explore similar work

Beyond Function Calling: Benchmarking Tool-Using Agents under Tool-Environment Unreliability

Beyond Task Completion: A Verification-vs.-Conformance Gap in Tool-Evolving Agents

ToolFailBench: Diagnosing Tool-Use Failures in LLM Agents