Your agent finished the task. Did every step work? What prefix executability shows

A new arXiv paper replays every tool call an agent made and marks the first one that could not run. On 200 function-calling tasks, one agent finished 94 % of them, yet only 47 % of its runs ran clean from start to end.

Most agent benchmarks ask one question at the end: was the task done? If yes, the run counts. This week's paper asks what happened on the way there, and the answer is less comfortable than the score.

The paper is Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success by Amir H. Rezaeian, Weiyi Sun, Yassine Benajiba and Dan Roth (arXiv 2610.40444, submitted 29 October 2026; the arXiv page says it is accepted to NeurIPS 2026). I checked every number below against the paper's text.

The problem

An agent that uses tools makes a chain of calls: look up an order, get its ID, cancel it, send a confirmation. A call can be invalid for plain reasons. It uses an ID that was never fetched, leaves out a required value, or skips a step that has to come first. Many agents notice, try again and still get the job done, and a benchmark that only checks the end state gives that run full marks.

For someone building with agents this matters, because the retry is not free. It costs time and money, and in a real system a wrong call can change something before the agent repairs it.

The idea

The authors check every prefix of the call sequence: the first call alone, the first two, the first three, and so on. A deterministic checker, with no AI model acting as judge, replays them in order against the tool definitions and the state of the task. It asks whether each call could actually run: is the tool available, are the arguments valid, are the referenced values present, do the preconditions hold. The first call that fails is the first error.

From that they build a few measures. The one I use below is the trajectory executability rate: the share of runs in which every call was executable from start to finish.

The numbers

All figures are from the paper's BFCL v3 multi-turn sample: 200 tasks, 50 from each of four categories. Every row is GPT-5.4 with high reasoning effort, in four set-ups.

Set-up Runs executable all the way Tasks finished
Plain ReAct loop (no plan) 0.69 0.61
Writes a plan, may ignore it 0.78 0.78
Follows its own plan, unchecked 0.47 0.94
Follows its plan, plan checked before running 0.94 0.94

Read the third row twice. The set-up with the best finished-task score, 94 %, is the one where fewer than half of the runs were clean. The plain loop, which finished only 61 %, had cleaner runs than it did.

GPT-4.1 and Llama-4-Maverick show the same split. Following its own unchecked plan, GPT-4.1 finished 93 % of tasks with 35 % clean runs, and Llama-4 finished 74 % with 5 % clean runs.

How can an agent finish a task through invalid calls? By repairing. For Llama-4 following its own plan, the paper counts 148 successful runs, and in 138 of them (93.2 %) the agent reached the goal after an earlier invalid call. Only 10 of the successes were fully executable.

What checking the plan did

The fourth row adds one step: before anything runs, a separate model inspects the plan. The same share of tasks finished (94 %), and clean runs went from 47 % to 94 %. For GPT-4.1 clean runs went from 35 % to 96 %, and for Llama-4 from 5 % to 88 %, with Llama-4's finished tasks going up too (74 % to 79 %).

The catch

The paper is open about where this stops, and the Short I made says it as plainly as the result.

  • It did not hold everywhere. On the second benchmark, ToolSandbox (200 sampled tasks), plan checking raised clean runs for GPT-5.4 from 0.48 to 0.94, but finished tasks went down, from 0.69 to 0.63. On τ³-bench, an airline and a retail set of 164 tasks, the authors say the audit "does not establish the consistent validation advantage" seen on the other two. There, plain ReAct had the cleanest runs (0.95).
  • A call that runs can still be the wrong call. The checker tests whether a call can execute, not whether it was the right thing to do. The paper says executability does not certify correctness.
  • It is an audit, not a leaderboard. The samples are 200 tasks each, and there is no comparison against constrained decoding, which would stop some invalid calls from being written at all.
  • Checking costs something. The plan-checking set-up adds model calls, and the paper says its experiments do not fully separate the value of the check from the extra compute.

What it changes in practice

  1. Log whether each call was valid, not only whether the task ended well. If you already store tool calls, one replay against the tool definitions gives you the number. It is the cheapest new dashboard I can think of.
  2. Treat "finished, but repaired" as its own bucket. It is where silent cost and risk sit. A fall in finished tasks is easy to see; a rise in repairs is not.
  3. Check a plan before it runs when a bad call is costly. The gain in this paper is clearest on the multi-turn function-calling benchmark, and not consistent on the short customer-service tasks.
  4. Prefer a check that can refuse to a rule that asks nicely. This is the same reason I move rules out of prompt text and into hooks that check a command before it runs, written up in Claude Code hooks: run each one in warn mode for a week first. A hook that can say no works whether or not the model remembers the sentence.

The 40-second version

Watch the Short on YouTube.

Paper: Rezaeian, Sun, Benajiba, Roth. Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success. arXiv:2610.40444, 2026. arxiv.org/abs/2610.40444

More posts

All posts →
  1. 21 Nov 2026

    Same agent, rebuilt workspace, a quarter of the bill: what EnvOpt showsA new arXiv paper leaves the model and the harness alone and lets another AI rebuild the workspace the agent works in. On 200 test tasks, the same Claude Haiku 4.5 agent cost $42.36 before and $11.55 after, and passed more tasks.

    AI · 7 min
  2. 21 Nov 2026

    CLAUDE.md vs AGENTS.md: which one Claude Code reads, and why I keep only oneWhen a repository has both files, Claude Code reads CLAUDE.md and leaves AGENTS.md alone unless you import it. I found five of my repositories set up the wrong way round: the real instructions in AGENTS.md, and a CLAUDE.md that only pointed at it.

    How I build · 5 min
  3. 20 Nov 2026

    Running several Claude Code agents at once: worktrees, handoffs and one check per phaseWhat broke when I put many Claude Code agents on the same repositories, and the four rules that stayed: one worktree per agent, small file-disjoint jobs, a rewritten handoff, and one full check per phase.

    How I build · 5 min