Prefix Executability: An Oracle Paper on Why an Agent Can Succeed and Still Break Along the Way

A tool-using agent can reach the right final state and still have made invalid calls on the way, then repaired them. A paper posted to arXiv on October 29, 2026 (2610.40444, "Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success", from Oracle AI, with a comment saying it is accepted to NeurIPS 2026) puts numbers on that gap. In one setting it reports a final success rate of 0.74 while only 5% of episodes were fully executable. This article is a reading of the paper, not a test of it.

I read the full HTML version of the paper, including the method, results and limitations sections. I did not read the appendices in detail or re-run anything. All numbers below are the authors' own, from their benchmarks and models.

The idea

The paper defines an action as executable if the selected tool is available, the arguments fit its schema, explicit preconditions hold in the current state, and any referenced intermediate values exist and have the right type. A prefix of a tool-call sequence is executable if every action in it executes successfully under the states produced by the earlier actions. This checks feasibility instead of agreement with one reference path, so it can credit alternative valid sequences. The scorer is deterministic and uses no LLM judge.

The metrics

• First-Error Depth (FED): the first step at which the prefix stops being executable. A fully executable trajectory of T calls has FED equal to T plus one.
• Prefix Executability Curve (PEC): the share of all started rollouts that reach depth k with an executable prefix. The paper notes it is a fixed-cohort survival curve, so it falls when a rollout fails or when it simply ends before depth k.
• Trajectory Executability Rate (TER): the share of rollouts whose full trajectory is executable.
• AUC-PEC: a horizon-normalized area, equal to the average of (FED minus 1) divided by T. It rewards later first failures.
• Recovery Rate (RR): the share of rollouts with at least one invalid prefix that still reach final success.

The authors also label the first invalid action with one primary cause: schema, dependency, precondition, state-consistency or information failure. Those labels are diagnostic only and are not used in the metrics.

What they tested

• Benchmarks: BFCL v3 multi-turn (200 stratified tasks, 50 from each of four categories), ToolSandbox (200 tasks, restricted to supported local-tool scenarios), and the complete Airline (50) and Retail (114) base splits of tau-cubed-bench.
• Models: GPT-5.4 at high reasoning effort, GPT-4.1 and Llama-4-Maverick-Instruct.
• Agent variants: ReAct, Prompt Planning, Plan-Conditioned ReAct, and Dual-Loop, which adds a verifier that checks a plan against tool schemas, preconditions and variable bindings before execution.
• Total: 6,768 rollouts over 564 tasks per model and method condition. Intervals are 95% task-level bootstrap intervals.

The authors say Dual-Loop is a controlled probe, not their main architectural claim.

What they found

Rankings diverge. Plan-Conditioned ReAct, where the plan is fed to the executor without verification, often shows higher final success than non-plan baselines while substantially lowering TER and AUC-PEC.

A worked example from the paper. On BFCL v3 with Llama-4 Maverick and Plan-Conditioned ReAct, 10 of 200 episodes were fully executable and all 10 succeeded. Another 138 of the 190 episodes with a prefix failure also succeeded. So TER is 0.05, RR is about 0.726 and final success is 0.74. Of the 148 successes, 138 (93.2%) came after an earlier invalid prefix.

Early survival. BFCL PEC at depth 4 for Plan-Conditioned ReAct is 0.42, 0.33 and 0.05 across the three models, versus 0.82, 0.82 and 0.78 for Dual-Loop.

Validation helps on two benchmarks. Pre-execution validation consistently improves TER, AUC-PEC and early PEC across the three models on BFCL v3 and ToolSandbox. Dual-Loop also enters the recovery-eligible regime much less often (for example 12, 7 and 25 episodes on BFCL, against 106, 130 and 190 for Plan-Conditioned ReAct). The paper warns that Dual-Loop's observed RR on BFCL is zero and that the small eligible sets make those estimates imprecise.

It does not transfer cleanly to tau-cubed-bench. With GPT-5.4, Plan-Conditioned ReAct has the highest final success (0.51) while plain ReAct has the highest TER and AUC-PEC (0.95 and 0.95). With GPT-4.1, Prompt Planning leads final success (0.51) and ReAct leads TER and AUC-PEC (0.84 and 0.91). The authors offer a possible explanation, that interactive user feedback can make advance plans stale, and label it "a testable interpretation, not an identified causal mechanism".

Cost. In the tau-cubed audit, Dual-Loop changes mean tokens and cumulative agent-call latency relative to Plan-Conditioned ReAct by about plus 3% and plus 22% for GPT-5.4, plus 12% and plus 7% for GPT-4.1, and minus 3% and minus 1% for Llama-4. In a separate sensitivity study, all paired 95% intervals for TER and AUC-PEC changes include zero. A GPT-5.4 verifier with a validation budget of 5 changed TER by plus 0.006 (interval minus 0.018 to 0.030) while adding 40.7k tokens and 176.9 seconds.

Limits the authors state

• It is an audit, not a full leaderboard. BFCL and ToolSandbox are 200-task samples, and tau-cubed coverage is only the Airline and Retail base splits.
• Intervals describe variation across tasks, not repeated runs within a task.
• Executability needs explicit schemas, preconditions and accessible state. Partially observed web or GUI environments may need state estimation or learned preconditions.
• Executability does not certify semantic correctness, safety, privacy or fairness.
• They did not evaluate a matched schema-constrained-decoding baseline, so the rankings are not established under that constraint.
• The intervention combines validation with extra inference, and the sensitivity study does not fully separate the two.
• BFCL and ToolSandbox cost data is aggregate runtime only.

What I would check

These are my untested suggestions.

1. Log, for your own agent traces, the first call that fails a schema or precondition check, and report that depth next to task success.

2. Count how many of your successes came after an invalid call, using the paper's recovery arithmetic.

3. If an invalid call has a real cost in your system, such as a payment or a write, weigh first-error depth above final success.

4. Try a verifier step only where plans stay valid. The tau-cubed result suggests it may not help when user feedback changes the state.

5. Add a schema-constrained decoding baseline before crediting a verifier, since the paper did not run one.

What I would not conclude

• That plan-conditioned agents are worse. Their final success was higher in several settings, and the paper says this is not a contradiction.
• That verification is a free win. The authors report cost increases and intervals that include zero in their sensitivity study.
• That prefix executability measures correctness. The paper says it does not.
• That the numbers generalize beyond these benchmarks, models and samples.

Frequently asked questions

What is prefix executability?

A trajectory-level check of whether every prefix of an agent's tool-call sequence stays executable under tool schemas, preconditions and data dependencies.

What is First-Error Depth?

The step number of the first invalid action in a rollout, or the trajectory length plus one if none is invalid.

How can success be high while executability is low?

Because an agent can repair an invalid call later. The paper's example has final success of 0.74 with TER of 0.05.

Which benchmarks and models were used?

BFCL v3 multi-turn, ToolSandbox and the Airline and Retail splits of tau-cubed-bench, with GPT-5.4, GPT-4.1 and Llama-4-Maverick.

Does pre-execution validation help?

It improved TER, AUC-PEC and early PEC on BFCL v3 and ToolSandbox. On tau-cubed-bench the benefit was not consistent, per the authors.

Does the metric need an LLM judge?

No. The benchmark-side scorer is deterministic. The verifier in Dual-Loop is separate and LLM-based.

Did you reproduce the results?

No. I read the paper.

Sources

All read on November 2, 2026.

• Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success, arXiv 2610.40444 (HTML version and arXiv metadata)

Not read: the appendices in detail, the full results tables, the cited benchmark papers, and any code release.