Prefix Executability: A Health Checkup, Not a Death Certificate, for Tool-Use Agents

Oracle AI researchers (Amir H. Rezaeian, Weiyi Sun, Yassine Benajiba, Dan Roth) argue that the industry's standard evaluation of tool-using agents—final success rate (task done: 1, not done: 0)—is like a coroner's report with only the conclusion. Their paper proposes Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success (arXiv:2610.40444), turning that report into a full medical record.

What "executable" means

An action in a rollout τ̂ = (a₁, …, a_T) is executable iff, at state s_t:

• the tool exists in the environment (schema/availability),
• arguments pass the interface's validators,
• referenced intermediate values exist with matching types (no stale IDs),
• explicit preconditions hold and the benchmark accepts the state transition.

Crucially, this is judged by a deterministic scorer on the benchmark side—no LLM judges (which could share the agent's hallucinations), and no reference-trajectory matching (which would penalize equally valid alternative paths).

From one action to a whole trajectory

A prefix τ̂≤k is executable iff every action in it executes successfully under states induced by prior actions. Define FED (First-Error Depth) = min{k : prefix k is not executable}; FED = T+1 if the whole rollout is clean. From this atom, the paper builds:

• PEC(k) = Pr[FED > k] — a discrete survival curve (Kaplan–Meier style, explicitly citing Kaplan & Meier 1958). It decomposes exactly as P̂C(k) = (n_k/N) · P̂C_elig(k), where n_k counts rollouts alive to depth k; the pooled curve mixes deaths with early endings, the conditional curve isolates purity among survivors.
• TER = Pr[FED = T+1] — the fraction of end-to-end executable trajectories.
• AUC-PEC = E[(FED−1)/T] — horizon-normalized "healthy lifespan share," with the clean inequality chain 0 ≤ TER ≤ AUC-PEC ≤ 1.
• RR = Pr[Y=1 | FED ≤ T] — recovery rate after *naturally occurring* errors (distinct from fault-injection work like "Beyond Success Rate").
• A first-error taxonomy (diagnostic only, not scored): schema → dependency → precondition → state-consistency → information failures.
• A decomposition identity: Pr[Y=1] = q·s + (1−q)·r, where q = TER, s = success rate among never-erroring rollouts, r = RR. Final success is exactly the sum of "never sick" and "sick but recovered"—so high success and low executability can coexist.

The twin experiment: same 0.94, two personalities

Nested intervention ladder: ReAct, Prompt Planning, Plan-Conditioned ReAct, and Dual-Loop (adds a plan verifier checking tool existence, schema, preconditions, variable bindings before execution). Models: GPT-5.4 (reasoning=high), GPT-4.1, Llama-4-Maverick-Instruct. Benchmarks: BFCL-v3 multi-turn and ToolSandbox (200 stratified tasks each), plus τ³-bench (164 tasks, 1,968 episodes). Total: 564 task instances, 6,768 rollouts.

GPT-5.4 + BFCL-v3:

| Method | TER | AUC-PEC | Success | RR-Eligible | |---|---|---|---|---| | ReAct | 0.69 | 0.83 | 0.61 | 61 | | Prompt Planning | 0.78 | 0.85 | 0.78 | 44 | | Plan-Conditioned ReAct | 0.47 | 0.54 | 0.94 | 106 | | Dual-Loop | 0.94 | 0.96 | 0.94 | 12 |

By the death certificate, Plan-Cond and Dual-Loop tie at 0.94. By the checkup: Plan-Cond has 106 fall-recovering trajectories (RR 0.88) vs Dual-Loop's 12; PEC@4 for Plan-Cond is as low as 0.05 under one model, meaning many trajectories don't survive step 4. ToolSandbox replicates the pattern (Plan-Cond: success 0.69, TER 0.48; Dual-Loop: success 0.63, TER 0.94). Dual-Loop beats Plan-Cond by ~0.46–0.47 TER on both benchmarks under GPT-5.4, and the gap holds across all GPT-4.1 and Llama-4 cells.

Llama's extreme case: 93.2% of successes carry wounds

Llama-4 + Plan-Conditioned ReAct on BFCL: TER = 0.05 (only 10 of 200 fully executable), mean FED = 1.96 (dead by step two on average), yet final success = 0.74. Of 148 successful trajectories, 138 (93.2%) succeeded only after an error (r ≈ 0.726 among the 190 that stumbled). Example (Appendix C.2): deleting a contact without first retrieving its identifier—rejected as a dependency failure—then recovering. The practitioner's question "74% success, production-ready?" reads very differently once you know every success rode on an invalid API call in a real environment.

Verification is not a panacea: the τ³ lesson

On τ³-bench (Sierra Airline/Retail), the Dual-Loop verification bonus disappears. Under GPT-5.4, Plan-Cond keeps the top success point estimate (0.51) while ReAct leads TER/AUC-PEC (0.95/0.95); under Llama-4, all three methods tie on success (0.18) while TER spans 0.52–0.60. The authors' clearly-labeled explanation: BFCL rewards pre-specified plans that rarely change, but τ³'s users interject and state refreshes—pre-verified plans go stale mid-interaction. Verification cost data: Dual-Loop vs Plan-Cond token/latency deltas on τ³ were roughly +3%/+22% (GPT-5.4), +12%/+7% (GPT-4.1), −3%/−1% (Llama-4). A verifier-sensitivity study (164 tasks, swapped verifier models and budgets) found all paired 95% CIs crossing zero—e.g., a GPT-4 verifier at K_val=5 changed TER by only +0.006 for 40.7k extra tokens and 176.9 seconds. The paper draws the boundary of its method rather than claiming a cure-all.

What the paper does not claim

• Executability ≠ correctness, safety, or fairness; it guarantees "runs in the environment," not "does the right thing."
• Not a full leaderboard sweep: 200 sampled tasks per benchmark, τ³ limited to the two base splits.
• Schema-constrained decoding baselines were not evaluated; constrained decoding blocks format errors but not object existence, data provenance, preconditions, or transition acceptance.

Why it matters

• Evaluation should move on: final success cannot answer how long a trajectory lived, where it first broke, or whether it recovered.
• Rank flips are the point: plan-conditioning can raise success via higher recovery, not reliability—prefix metrics expose the mechanism.
• Runtime potential: executability is prefix-local, computable immediately after each candidate action—enabling pre-dispatch interception, repair, replanning, or human escalation before dirty state propagates. The paper lists this as future work, but retrospective diagnostics alone could already change release testing: add "full-executability rate" and "mean FED" columns next to success rate.

The deepest move is borrowed: treating trajectories as objects with survival times and applying a century-old statistical framework (Kaplan & Meier, 1958) to agent evaluation. New conceptual shell, old skeleton—the good kind of science.

References

1. Rezaeian, A. H., Sun, W., Benajiba, Y., & Roth, D. (2026). *Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success*. arXiv:2610.40444. https://arxiv.org/abs/2610.40444 2. Yao, S., et al. (2023). ReAct: Synergizing Reasoning and Acting in Language Models. https://openreview.net/forum?id=WE_vluYUL-X 3. Patil, S. G., et al. (2025). The Berkeley Function Calling Leaderboard (BFCL). https://proceedings.mlr.press/v267/patil25a.html 4. Lu, J., et al. (2025). ToolSandbox. https://aclanthology.org/2025.findings-naacl.65/ 5. Yao, S., et al. (2025). τ-bench. https://openreview.net/forum?id=roNSXZpUDN 6. Barres, V., et al. (2026). τ³-bench. https://sierra.ai/blog/bench-advancing-agent-benchmarking-to-knowledge-and-voice 7. Chen, Z., et al. (2024). T-Eval. https://aclanthology.org/2024.acl-long.515/ 8. He, P., et al. (2026). TRAJECT-Bench. https://openreview.net/forum?id=TZWnWvsQ0X 9. Kim, W., et al. (2026). TRACE. https://proceedings.mlr.press/v306/kim26bg.html 10. Lewandowska, K. (2026). Beyond success rate. https://trustagenticai.github.io/AAAI2026/AAAI-Workshop/17.pdf 11. Kaplan, E. L., & Meier, P. (1958). Nonparametric estimation from incomplete observations. *JASA*, 53(282), 457–481. https://doi.org/10.1080/01621459.1958.10501452 12. Erdogan, L. E., et al. (2025). Plan-and-Act. https://proceedings.mlr.press/v267/erdogan25a.html