PaperlayerView exact revision on arXiv

Source-linked AI summary

Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success

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

arXiv:2610.40444v1cs.AIcs.CL

TL;DR

Final task success can conceal whether intermediate tool calls remain executable, leaving first failures and recovery unmeasured. The paper evaluates prefixes under tool and state semantics and finds that terminal outcomes and prefix reliability can diverge, while validation’s reliability benefit depends on the environment.

  • Problem

    Terminal success alone does not show how long a rollout remains executable, where validity first breaks, or whether success follows recovery.

    Source: §1 · p. 2

  • Method

    The paper formalizes prefix executability and evaluates rollouts with PEC, FED, TER, AUC-PEC, and RR under tool, precondition, dependency, and state constraints.

    Source: §1 · p. 2

  • Results

    Across the three-benchmark audit, prefix reliability and terminal outcome provide complementary information, and validation improves prefix reliability on BFCL-v3 and ToolSandbox while its benefit is environment-dependent.

    Source: §1 · p. 2, §4 · p. 9

  • Takeaways & Limitations

    Prefix-level measures provide a reliability signal for comparing agents, locating first failures, and identifying success after recovery alongside terminal outcomes.

    Source: §1 · p. 2, §4 · p. 9

    Executability assumes explicit schemas, preconditions, and benchmark-accessible state; partially observed web or GUI settings may require state estimation or learned preconditions, and executability does not certify semantic correctness.

    Source: Limitations · p. 9

Abstract

from arXiv · show

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 $\tau^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.

1 Introduction

Final task success can conceal invalid intermediate tool calls, leaving a gap in how tool-use reliability is evaluated. The paper introduces prefix executability to measure trajectory validity, locate first failure, and assess recovery alongside terminal outcomes.

1 Introduction

  • Outcome-only scores can miss rollouts that become non-executable through schema violations, unmet preconditions, stale references, or invalid state transitions.A later repair may still produce the desired final state, hiding where the trajectory first failed.Source: §1 · pp. 1–2
  • The evaluation gap is whether a naturally generated rollout remains executable to each prefix, where its first invalid prefix occurs, and whether success follows recovery.Prior evaluation work includes step-wise skill, intermediate-condition, trajectory, process-quality, procedure, and robustness assessments.Source: §1 · pp. 1–2
  • Prefix executability checks the actual emitted rollout under tool and state semantics, crediting alternative executable sequences while recording first failure, survival, and recovery.The protocol formalizes PEC, FED, TER, AUC-PEC, and RR for variable-horizon trajectories.Source: §1 · p. 2
  • The study applies the protocol to BFCL-v3 multi-turn, ToolSandbox, and Airline/Retail τ 3-bench, covering 564 task instances per model–method condition and 6,768 rollouts.It also probes whether pre-execution validation improves reliability when terminal-success rankings tell a different story.Source: §1 · p. 2

2 Prefix-Level Executability Evaluation

The paper defines executability at the action and prefix levels, then evaluates rollout survival, first failure, full-trajectory validity, and recovery under explicit tool and state semantics. It applies these measures across three benchmarks and compares unvalidated and verified plan-conditioned agents.

2.1 Executable Prefixes

  • An action is executable when its tool is available, arguments fit the schema, preconditions hold in the current state, and referenced values are present and type-consistent.A prefix is executable only when every action executes successfully under the states induced by earlier actions; this permits alternative valid sequences.Source: §2.1 · p. 3

2.2 Prefix-Level Reliability Metrics

  • FED records the first non-executable prefix, while PEC(k) measures the fraction of all rollouts that reach depth k with an executable prefix.The fixed-cohort curve can decline because of failure or termination before depth k; eligible-depth PEC instead conditions on reaching k.Source: §2.2 · pp. 3–4
  • TER measures full-trajectory executability, AUC-PEC summarizes normalized prefix survival, and RR measures final success after an invalid prefix.AUC-PEC rewards later first failures; TER equals PEC at the common horizon only when episodes share a fixed horizon.Source: §2.2 · p. 4

2.3 What Prefix-Level Metrics Add

  • Reference-match metrics may penalize alternative executable trajectories and do not localize first failure, while terminal success cannot show uninterrupted execution or recovery.The proposed metrics cover prefix survival, first-error depth, full-trajectory validity, normalized prefix area, and recovery.Source: §2.3 · p. 5, Table 1 · p. 5

2.4 First-Failure Annotation Protocol

  • Each first invalid action receives one mutually exclusive primary cause: schema, dependency, precondition, state-consistency, or information failure.These diagnostic labels do not enter the PEC, TER, AUC-PEC, or RR calculations.Source: §2.4 · p. 5

2.5 Validation Intervention

  • Dual-Loop uses a planner, a verifier for tool existence, schema, preconditions, and bindings, and plan revision until verification succeeds before execution.Only the ReAct executor issues environment tool calls; planner and verifier messages count as method-side computation, not tool actions.Source: §2.5 · p. 5

2.6 Benchmarks and Experimental Setup

  • The evaluation uses BFCL-v3 and ToolSandbox samples plus all Airline/Retail base-split tasks in τ 3-bench, with action-level logging of executability, failure, cause, and later success.The BFCL-v3 and ToolSandbox grid uses 200 instances per benchmark and paired task IDs across methods; the τ 3-bench coverage is limited to its Airline and Retail base splits.Source: §2.6 · pp. 5–6

2.7 Agent Variants and Experimental Controls

  • The four variants are ReAct, Prompt Planning, Plan-Conditioned ReAct, and Dual-Loop; Dual-Loop adds pre-execution verification to the plan-conditioned executor.Executor settings are held constant within each LLM condition, and planner and verifier calls count as method cost rather than tool actions.Source: §2.7 · p. 6

3 Benchmark Results

Across the benchmark results, terminal success and prefix reliability diverge, and validation’s advantage is not consistent across environments. Prefix-depth, recovery, and cost measures further qualify how to interpret those outcomes.

3.1 Main Benchmark Results

  • On BFCL/ToolSandbox with GPT-5.4, Plan-Cond. ReAct final success is 0.94/0.69, but Dual-Loop TER is 0.94/0.94 and AUC-PEC is 0.96/0.95.These are point estimates; Table 2 reports 95% confidence intervals.Source: §3.1 · p. 6, Table 2 · p. 7
  • For BFCL/Llama-4 Plan-Conditioned ReAct, 138/148 successful episodes (93.2%) followed an invalid prefix, despite TER 0.05 and final success 0.74.Dual-Loop entered the RR-eligible regime far less often; its observed RR was zero on BFCL, with small eligible sets making the conditional estimates imprecise.Source: §3.1 · pp. 7–8

3.2 Prefix Survival by Depth

  • At BFCL PEC@4, Plan-Conditioned ReAct scores 0.42, 0.33, and 0.05 across model conditions, versus Dual-Loop’s 0.82, 0.82, and 0.78.These fixed-cohort statistics jointly reflect reaching the depth and having an executable prefix; late-depth declines can also reflect termination.Source: §3.2 · p. 8, Figure 1 · p. 8

3.3 Transfer, Cost, and the Boundary of Validation

  • The Airline/Retail audit does not establish the consistent validation advantage seen on BFCL-v3 and ToolSandbox, and its possible stale-plan explanation is not a causal finding.The text presents interactive user feedback and state changes as a possible reason advance plans may become stale.Source: §3.3 · p. 8
  • In the τ 3 audit, Dual-Loop changes mean tokens/agent-call latency versus Plan-Conditioned ReAct by +3%/+22%, +12%/+7%, and −3%/−1% for GPT-5.4, GPT-4.1, and Llama-4.Totals include verification and revision as well as downstream execution savings, but exclude simulator and evaluator calls.Source: §3.3 · p. 8
  • In the verifier-sensitivity study, GPT-5.4 at Kval = 5 changes TER by +0.006 [−0.018, 0.030] while adding 40.7k tokens and 176.9s; paired intervals include zero.The deterministic-acceptance wrapper also changes executor guidance, so the study does not isolate verification logic from extra computation.Source: §3.3 · pp. 8–9

4 Conclusion

The paper formalizes prefix executability as a complementary evaluation of tool-use trajectories alongside terminal success. It also identifies runtime and offline uses for the prefix-local predicate while noting what the metrics do not certify.

4 Conclusion

  • The protocol defines PEC, FED, TER, AUC-PEC, and RR for variable-horizon rollouts, complementing terminal outcomes with prefix reliability and recovery information.Across the three-benchmark audit, prefix reliability and terminal outcome provide complementary information.Source: §4 · p. 9
  • A prefix-local executability check can support runtime monitoring, repair, replanning, or escalation, while aggregated signals can inform offline prompt, budget, and agent choices.These uses remain complementary to the paper’s evaluation focus.Source: §4 · p. 9
  • Prefix executability exposes whether and where a trajectory becomes invalid, but does not itself certify semantic correctness, safety, privacy, or fairness.The conclusion calls for reporting uninterrupted executability, recovery, terminal success, and agent-side cost together.Source: §4 · p. 9

Limitations

The audit is limited to sampled or benchmark-specific task sets, and its executability checks depend on explicit schemas, preconditions, and accessible state. The intervention and reported cost evidence also constrain how broadly its comparisons can be interpreted.

Evaluation scope

  • BFCL-v3 and ToolSandbox each contribute 200 sampled tasks, ToolSandbox covers supported local-tool scenarios, and τ 3 coverage is limited to Airline/Retail base splits.Task-level intervals do not capture within-task repeated-seed variation; main-grid intervals are marginal, while paired intervals appear only in the verifier-sensitivity study.Source: Limitations · p. 9

Assumptions and validity

  • Executability assumes explicit schemas, preconditions, and benchmark-accessible state, and it does not certify semantic correctness.Partially observed web or GUI environments may require state estimation or learned preconditions; rankings are not established against a matched schema-constrained-decoding baseline.Source: Limitations · p. 9

Intervention and cost

  • The intervention combines validation and revision with extra inference, and its acceptance wrapper changes executor guidance without isolating validation from compute or context effects.Per-method cost telemetry is available for the τ 3 audit, but the BFCL-v3/ToolSandbox grid reports aggregate runtime only.Source: Limitations · p. 9

Scope of conclusions

  • Broader claims require additional domains, repeated runs, and matched constrained-decoding and repair controls.In consequential applications, executable trajectories may still be unsafe, biased, privacy-violating, or misaligned; the paper calls for domain-specific safeguards and human oversight.Source: Limitations · pp. 9–10

A Relationship to Prior Evaluation Protocols

Prefix executability evaluates whether observed actions satisfy schemas, state preconditions, and data dependencies, while crediting any sequence that meets those conditions rather than requiring a reference path.

A Relationship to Prior Evaluation Protocols

  • Executable alternative action sequences receive credit regardless of agreement with a reference trajectory.This distinguishes execution-feasibility checks from reference-trajectory agreement while complementing task outcomes, intermediate milestones, and semantic process quality.Source: A Relationship to Prior Evaluation… · p. 12
  • Prefix metrics complement evaluations of task outcomes, intermediate milestones, reference-trajectory agreement, and semantic process quality.Source: A Relationship to Prior Evaluation… · p. 12
  • Table A.1 compares evaluation units and signals across trajectory and process protocols.Prefix executability checks schema, state-precondition, and dependency compliance; alternative sequences receive full credit when executable, complementing outcome, milestone, reference-match, and semantic-process evaluations.Source: Table A.1 · p. 12, A Relationship to Prior Evaluation… · p. 12

B Exact Properties, Consistency, and Relationship to Final Success

The appendix establishes exact properties of prefix-level metrics and decomposes terminal success into fully executable and prefix-failure regimes. It also specifies how first failure is determined while preserving the full observed rollout for final success and recovery analysis.

B Exact Properties, Consistency, and Relationship to Final Success

  • PEC is non-increasing with depth because an executable prefix reaching depth k + 1 must also reach depth k; early termination counts as not reaching a later depth in the fixed-cohort measure.The fixed denominator is the cohort size at every depth, and no censoring model is required.Source: B Exact Properties, Consistency, and… · pp. 12–13
  • For every evaluated cohort, TER is bounded above by AUC-PEC, which is bounded above by 1; with variable horizons, AUC-PEC is mean normalized per-trajectory area and common-horizon identities do not apply.Mean FED is generally not determined by TER or AUC-PEC alone.Source: B Exact Properties, Consistency, and… · p. 13
  • Terminal success is the sum of successes on fully executable trajectories and successes after a prefix failure, so TER alone does not determine final success across methods.When both regimes occur, success is a mixture of conditional success rates; the relationship with TER is not universally monotone because those rates can also vary.Source: B Exact Properties, Consistency, and… · p. 13
  • Under i.i.d. task–rollout sampling, empirical PEC at a fixed depth, TER, AUC-PEC, and final success are strongly consistent estimates of their population counterparts.The finite-cohort identities apply to the reported deterministic stratified cohorts; population consistency and concentration require the stated sampling assumption.Source: B Exact Properties, Consistency, and… · pp. 13–14
  • When the population has prefix failures, the RR estimator converges to the probability of success conditional on prefix failure as the sample grows.RR is undefined for a finite cohort with no eligible prefix-failure episodes.Source: B Exact Properties, Consistency, and… · p. 14

C.1 Executability Checks and First-Failure Classification

  • The scorer checks the actual emitted trajectory deterministically against benchmark tool and state semantics, without a learned judge, human step labels, or a single gold action sequence.The LLM-based pre-execution verifier is separate, and its acceptance does not establish that the emitted trajectory is executable.Source: §C.1 · pp. 14–15
  • First-failure replay starts from the benchmark state and checks emitted actions in order, stopping at the first failed predicate or rejected transition while retaining the observed episode.A terminal no-tool action counts as executable only when benchmark semantics permit completion without a tool call.Source: §C.1 · pp. 14–15
  • The first failed action fixes FED and ends prefix replay, but the full rollout is retained, allowing later execution and task success to count as recovery without restoring prefix survival.The checker evaluates emitted actions against tool availability, interface and validators, available type-compatible references, information requirements, state preconditions, and accepted transitions.Source: §C.1 · pp. 14–15

C.2 Illustrative Contact-Repair Comparison

The contact-repair example shows how a run can succeed after an invalid action, while the Dual-Loop details specify how pre-execution validation and executor actions are handled. The verifier checks candidate plans locally, but benchmark replay remains authoritative for trajectory metrics.

C.2 Illustrative Contact-Repair Comparison

  • The contact-removal example rejects a phone number where a stored identifier is required; looking up the identifier enables an executable alternative.The repaired run can still have terminal success despite zero complete-trajectory executability, distinguishing recovery from error-free execution.Source: §C.2 · p. 15

D Dual-Loop Validation Details

  • Only executor-emitted environment actions enter the prefix metrics; planner and verifier messages influence behavior but are not scored as benchmark actions.The executor trajectory is scored as emitted, including deviations from a verified plan, early termination, or invalid calls.Source: D Dual-Loop Validation Details · p. 16, Figure D.1 · p. 16, §D.1 · p. 16

D.1 Objects and Information Boundary

  • The planner proposes a finite dependency-aware candidate plan from the user goal, tool specification, and initial state summary; plan length need not match the executed horizon.The verifier accepts or rejects the plan without access to the reference trajectory, hidden success label, or future observations.Source: §D.1 · p. 16

D.2 Verifier Checklist

  • The verifier checks schemas, dependencies, information availability, explicit preconditions, and state consistency, but its local checklist is not a proof of global optimality.Benchmark replay remains authoritative for FED, TER, final success, and RR.Source: §D.2 · pp. 16–17

D.3 Repair Loop and Iteration Budgets

  • Rejected plans receive targeted feedback and may be revised up to Kval = 5; BFCL-v3 and ToolSandbox execution separately cap ReAct at Kexec = 10 iterations.Validation iterations are unscored pre-execution search; only executor actions and the terminal no-tool action contribute to the scored horizon.Source: §D.3 · p. 17

D.4 Metric Accounting and Controls

Metric accounting excludes planning and verification from benchmark actions and bases prefix measures on the executor’s emitted trajectory. Comparisons hold key execution conditions fixed while treating inference costs separately.

D.4 Metric Accounting and Controls

  • Candidate plans, verifier decisions, and feedback affect metrics only through the executor’s subsequent environment-facing behavior.Validation can improve prefix metrics only by changing the actions emitted; it does not modify benchmark state before execution.Source: §D.4 · p. 17
  • RR applies only to rollouts with FEDi ≤Ti; rejected plans before execution are ineligible because no benchmark prefix has failed.A verified plan followed by an invalid executor call counts as an ordinary prefix failure.Source: §D.4 · p. 17
  • Variants share task identifiers, tool specifications, executor horizon caps, and decoding rules, while Dual-Loop adds validation, revision, and inference cost.Planner and verifier calls are outside the scored trajectory but should be included when comparing token use, latency, or deployment cost.Source: §D.4 · p. 17

D.5 Limitations of the Intervention

The validation intervention has limits arising from what its verifier can assess and the additional inference it requires.

D.5 Limitations of the Intervention

  • The verifier can miss hidden-state constraints, underspecified intent, or semantic requirements outside the tool interface, and can reject executable alternatives.Pre-execution validation also adds inference cost.Source: §D.5 · p. 17

E Additional Experimental Settings and Compute Resources

The experiments use fixed decoding, output, and execution budgets, alongside hosted model APIs and local orchestration. The Airline/Retail audit covers both complete base splits, while its agent-cost measurements are reported separately from the broader benchmark grid.

E Additional Experimental Settings and Compute Resources

  • The 4,800-rollout BFCL-v3/ToolSandbox grid uses a 4,000-token response cap, Kexec = 10, and a separate Kval = 5 for Dual-Loop.LLM conditions use least-stochastic supported settings; validation attempts are method-side computation, not tool actions in Ti.Source: E Additional Experimental Settings and… · p. 18
  • Hosted API inference dominated runtime: the BFCL-v3/ToolSandbox grid took approximately 72 hours using 16 asynchronous request workers and a CPU-only local worker.The local worker had 16 vCPUs and 64 GB RAM, with no local GPU; offline metric computation took under 1 hour.Source: E Additional Experimental Settings and… · p. 18

F.1 Airline and Retail Audit Protocol

  • The Airline/Retail audit covers all 50 Airline and 114 Retail base-split tasks, with one rollout per task, model, and method.Its task-level intervals describe variation across tasks under the fixed protocol, not within-task variation across repeated runs.Source: §F.1 · p. 18, Table F.1 · p. 19

F.2 Agent-Side Token Use and Latency

  • Dual-Loop changes mean tokens/latency versus ReAct by approximately +14%/+46% for GPT-5.4, +27%/+20% for GPT-4.1, and +7%/+8% for Llama-4 Maverick.Relative to Plan-Conditioned ReAct, the approximate differences are +3%/+22%, +12%/+7%, and −3%/−1%, respectively; these are net episode-level costs.Source: Table F.2 · p. 19, §F.2 · pp. 19–20

F.3 Matched Verifier Sensitivity

In the matched verifier-sensitivity study, TER and AUC-PEC intervals include zero, while final-success intervals are negative for two configurations. The depth-wise PEC checkpoints provide fixed-cohort prefix-reliability diagnostics, with late-depth declines also reflecting early termination.

F.3 Matched Verifier Sensitivity

  • The 164 Airline/Retail tasks used a shared initial plan and execution horizon; paired task-bootstrap intervals capture task variation, not repeated-run variability.Table F.3 compares against a separately evaluated, task-paired Plan-Conditioned ReAct rerun; planner and executor remain GPT-5.4-high.Source: §F.3 · p. 20, Table F.3 · p. 20
  • All TER and AUC-PEC intervals include zero; final-success intervals are negative for deterministic acceptance and GPT-4.1, while the other two include zero.Equivalence was not tested.Source: §F.3 · p. 20
  • These contrasts are configuration-specific: deterministic acceptance changes executor instructions, while LLM verifiers also change inference cost.They do not isolate verification logic from executor instructions and computational budget.Source: §F.3 · p. 20

G Depth-Wise PEC Checkpoints

  • Table G.1’s fixed-cohort PEC checkpoints use all 200 rollouts per block; each value combines reaching depth k with executable prefixes, while late declines may reflect early termination.The checkpoints are prefix-reliability diagnostics, not eligible-depth conditional accuracy or path-efficiency scores.Source: G Depth-Wise PEC Checkpoints · pp. 20–21, Table G.1 · p. 21
Loading 2610.40444v1…