Evaluate every tool-call prefix — prefix executability — What does it mean?
The news. On October 29, 2026, Rezaeian, Sun, Benajiba and Roth posted a paper on arXiv that proposes scoring tool-using agents by whether every prefix of their tool-call sequence stays executable. They test it on stratified samples of BFCL-v3 multi-turn and ToolSandbox, and on the full Airline and Retail base splits of τ³-bench. Read the paper →
Imagine a mountain trail with numbered checkpoints, and a hiker who reaches the summit. A summit photo says the hiker arrived, but it does not say whether they walked the trail or skipped checkpoint 3, got lost, and backtracked to find the missing stamp. That is how most tool-use benchmarks score agents today: they look at the summit photo. The paper argues that a final-success score cannot tell a clean run from one that broke early and was patched later, and that the difference matters when each call costs money or changes real data.
The unit the paper checks is the prefix: the first k tool calls of a run. A call is executable when the tool is available, its arguments fit the tool's schema, its explicit preconditions hold in the current state, and any value it refers to (an identifier returned by an earlier call, for example) actually exists with the right type. A prefix is executable only if every call in it executes under the states the earlier calls produced. The check does not compare against one gold path, so a different but valid order of calls is not punished. The paper says its benchmark-side scorer is deterministic and uses no LLM judge.
Back on the trail, the metrics become simple questions. First-Error Depth is the number of the first checkpoint you did not reach legally. The Prefix Executability Curve asks, for each checkpoint number k, what share of all hikers have been legal through k so far. Because it divides by all hikers who started, a hiker who finishes early also drops off the curve at the later depths, so a falling curve can mean an invalid call or simply a shorter run. The paper also tracks the conditional version that only counts runs long enough to reach depth k.
Two more numbers summarize a whole run. TER counts the hikers who never put a foot wrong, and AUC-PEC is the average of (FED minus 1) divided by the run length, so a first mistake near the end costs less than one near the start. Recovery Rate then asks about the hikers who did stumble: what share still reached the summit? The paper states that 0 ≤ TER ≤ AUC-PEC ≤ 1, and that the number of runs eligible for recovery equals N × (1 − TER).
| Metric | Question it answers | How it is computed |
|---|---|---|
| FED | Where did the first invalid call occur? | Smallest k whose prefix is not executable |
| PEC(k) | What share of runs is still valid through call k? | Fraction of all N runs with FED greater than k |
| TER | How often is the entire run valid? | Fraction of runs with no invalid call |
| AUC-PEC | How late does the first error come, on average? | Mean of (FED − 1) / run length |
| RR | After an invalid call, how often does the run still succeed? | Success rate among runs with at least one invalid prefix |
The paper's own numbers show why the split matters. In its BFCL-v3 multi-turn sample with Llama-4 Maverick and a plan-conditioned ReAct agent (a ReAct agent that follows a plan written before any tool call, with no check of that plan), only 10 of 200 runs were fully executable, so TER is 10 / 200 = 0.05. All 10 succeeded. Of the other 190 runs, which each contained an invalid prefix, 138 still succeeded, so RR is 138 / 190, about 0.73. Final success is (10 + 138) / 200 = 0.74. That means 93.2% of the successful runs (138 of 148) reached the goal after an earlier invalid call. A leaderboard that prints 0.74 shows a capable agent. The prefix view shows an agent that almost never runs cleanly and mostly succeeds after an earlier invalid call.
The same divergence appears between methods. With GPT-5.4 on BFCL-v3 and ToolSandbox, the plan-conditioned ReAct agent had the highest or tied-highest final success (0.94 on BFCL, 0.69 on ToolSandbox), yet its TER was 0.47 and 0.48. A "Dual-Loop" variant reached TER 0.94 on both. In Dual-Loop a planner proposes a structured plan, a verifier checks tool existence, schema fit, preconditions and variable bindings, and the planner revises using the verifier's feedback within an iteration budget. Once a plan is approved, it conditions a ReAct executor, which alone makes real tool calls. Checking the plan before spending any call is like a guide who inspects the route map before the hike starts. The paper presents Dual-Loop only as a controlled probe of the metrics, not as its main contribution.
The paper also states where the idea stops. On the τ³-bench Airline and Retail audit, the validation advantage seen on BFCL-v3 and ToolSandbox was not consistent: with GPT-5.4 plain ReAct had the best TER and AUC-PEC (0.95 each) while plan-conditioned ReAct had the best final success (0.51). The authors suggest, as a testable guess and not a proven cause, that a plan written in advance can go stale when a user and the environment change state during the run. The reported orderings are point estimates and are not claimed as paired significance results. The Recovery Rate also needs care: its sample is small for strong agents (Dual-Loop had only 7 to 25 eligible runs per BFCL condition), so read it together with the eligible count.
You can use the idea without the paper's tooling. If your tool environment can replay each call against a schema and state, log the index of the first rejected call for every run, then report the share of clean runs next to your success rate. This extends the compounding errors argument: errors that enter early cost more because everything after them depends on them. It also adds a trajectory-level view to golden cases, and for live traffic it is a natural signal for online versus offline evals. For a related approach that locates the first bad step inside a trace, see TELBench span-level error localization.
Goes deeper in: AI Agents → Evals & Diagnostics → Compounding Errors