When a language-model agent books a flight, refunds an order, or edits a spreadsheet, it talks to software through a standard message format. The best known is the Model Context Protocol (MCP), a shared schema that lets any model call any tool server. These formats check that a message is well formed, and in some designs that it is cryptographically signed. They never check whether the values inside it came from anywhere real. An agent can send a perfectly valid, signed "cancel reservation XYZ123" in which XYZ123 is a hallucination, meaning a fluent invention with no basis in anything the user said or any tool returned.
We propose a gate that sits in the protocol layer, between any agent and any tool server. It traces every argument of a state-changing tool call back to a specific earlier user message or tool result, and holds calls whose arguments cannot be traced. Its strictness is tuned on a small set of calibration tasks. The tuning comes with an explicit finite-sample statement: with confidence $1-\delta$, the rate of tasks in which an ungrounded write is committed stays below $\alpha$. The procedure also says plainly when the benchmark is too small to support the $\alpha$ you asked for.
Core Claim
The claim has two parts. First, a model-agnostic provenance score computed at the protocol boundary is a better predictor of harmful hallucinated writes than an LLM judge or self-consistency voting. "Better" here means lower false-block rate at matched risk. Second, the natural unit for statistical calibration in agent settings is the whole task, not the individual step. Treating each task as one draw sidesteps the within-trajectory dependence that breaks standard conformal guarantees. The price is that small agent benchmarks can only certify coarse risk levels, and we make that price quantitative.
Concretely, when no violations are observed on $n$ calibration tasks, the one-sided 95% upper bound on the violation probability is roughly $3/n$ (the binomial "rule of three"). A target of $\alpha=0.05$ therefore needs about 60 clean tasks. A target of $\alpha=0.01$ needs about 300, which is more than τ-airline's 50 tasks or TOOLATHLON's 108 contain.
Where This Sits in Prior Work
Three papers motivate the gap. LACP defines standard PLAN/ACT/OBSERVE message types with signatures and transaction IDs, but it will faithfully deliver and commit a signed ACT carrying invented parameters. We add a semantic check at exactly that commit point. MCPVerse shows that native function calling over MCP beats prompt-based tool definitions, which hallucinate at rates above 70% in large tool spaces. That result tells us the remaining errors live inside well-formed calls, and those are what we target. TOOLATHLON documents agents asserting completion falsely and inventing recovery paths over roughly 20-turn trajectories, with top success of 38.6%.
Two papers supply methods we reuse. LEDGERMIND grounds reasoning in a provenance ledger with entity and numeric consistency checks. It restricts repair to DROP/RETRY/ABSTAIN operators, and it reports that free-form self-repair amplifies hallucinations. We borrow the entity and numeric checks and the typed repair operators. LEDGERMIND's ledger, however, is internal to one agent's prompt loop, uncalibrated, and evaluated on 200 queries. We move the check outside the agent, into protocol middleware, so it applies unchanged to any backbone. TRAC combines conformal prediction with Bonferroni-style global testing to certify factual coverage in single-turn retrieval QA. We reuse its multiple-testing composition, but for closed-loop multi-turn control. TRAC relies on static exchangeability, which fails once tool observations change the state.
Two further papers constrain the design. τ-bench shows that single-trial success badly overstates reliability. GPT-4o on retail falls from 61.2% at one trial to under 25% when it must succeed on all of eight trials, a measure called pass^k. Any claim we make must therefore be reported under repeated trials. Do Language Models Know When They're Hallucinating References? shows that asking a model directly whether it hallucinated yields overconfident affirmations, which rules out self-query gates as the main detector.
Research Program
The gate is an MCP proxy. For each incoming tool call it keeps a ledger of every user utterance and every tool result in the episode, each with a message ID. Each argument of a write call receives a support score. The score is high when the value matches a ledger entry: exactly for identifiers, within tolerance for numbers, and after entity normalization for names. It is lower when the value is only derivable through a transformation, such as a sum of observed prices. It is zero when the value appears nowhere in the ledger. The call's score is the minimum over its arguments.
A call below the threshold $\lambda$ is not executed. Instead the agent receives a typed OBSERVE rejection naming the unsupported argument, which is effectively a LEDGERMIND-style RETRY, or the task escalates via ABSTAIN after two rejections. Read-only calls always pass. Blocking reads buys nothing, and reads are how agents gather the provenance they need.
Calibration works at the task level. The harm for task $i$ at threshold $\lambda$ is $L_i(\lambda)\in\{0,1\}$, which equals 1 if any committed write in the closed-loop run diverges from the benchmark's gold actions or final database state. This label is independent of the provenance score, so the calibration is not circular. Because blocking changes what the agent does next, $L_i(\lambda)$ need not decrease as $\lambda$ rises, and ordinary conformal risk control does not apply. We therefore use a small grid $\lambda_1<\dots<\lambda_G$ and run every calibration task in closed loop at each value. For each $\lambda_g$ we test the null hypothesis that its risk exceeds $\alpha$ using an exact binomial $p$-value. The selected set is
$$\hat\Lambda=\{\lambda_g : p_g(\alpha)\le \delta/G\},$$
where $\delta$ is the allowed failure probability and $G$ the grid size. This is the Bonferroni composition TRAC uses. We deploy the least restrictive member of $\hat\Lambda$, and if the set is empty we report that $\alpha$ cannot be certified at this $n$.
The guarantee holds for tasks drawn from the same pool as calibration. It does not hold across domains, and the experiments test that boundary directly.
Baselines
The naive reference point is the agent running over MCP native function calling with schema validation only. This is the standard today, and MCPVerse shows it is already much better than prompt-based definitions. The published number to track on τ-bench airline is Claude-3-5-Sonnet-20241022 at pass^1 0.460 and pass^4 0.225 on the official leaderboard (τ-bench). On retail, GPT-4o reaches 61.2% at a single trial. For TOOLATHLON the reference is Claude-4.5-Sonnet at 38.6% success, and for MCPVerse it is Claude-4-Sonnet at 44.2% at Max-Scale. We found no reported result on Lacuna for the rate of committed ungrounded writes on any of these benchmarks, so we measure it ourselves for every baseline.
The strongest competitor is an LLM-judge gate: a separate model reads the ledger and the proposed call and outputs a support probability. We put that probability through the same task-level calibration. It is the strongest alternative because it can recognize legitimate derivations that string matching misses, and MCPEval already treats LLM judging as a standard evaluation lens (MCPEval).
A second competitor is a self-consistency gate, in the spirit of the indirect-query consistency checks of the reference-hallucination study. It samples five candidate calls and commits only if a calibrated fraction agree.
A third is a LEDGERMIND-style prompt condition. Here the agent is instructed to keep its own evidence ledger and to use typed repair, with no external gate.
All conditions use the same backbone models, calibration and test splits, number of trials, and grid size. The judge and self-consistency gates are charged their extra model calls in a reported token budget. Two ablations isolate the key ingredient. One runs the provenance gate at a fixed hand-picked threshold with no calibration. The other runs the calibrated procedure on the LLM-judge score. Together they separate the value of the provenance signal from the value of the calibration.
Beating the strongest baseline means two things at the certified $\alpha$. First, the test-set violation rate stays at or below $\alpha$ across resampled splits. Second, the gate blocks fewer correct writes than the calibrated LLM-judge gate, producing a higher pass^k, at lower cost. We would also count it a win if the gate raises same-backbone pass^4 above the no-gate reference, because rejected calls turn into retries rather than silent failures.
Why not just…?
Why not just use an LLM judge to check each call? This is the real threat, and the proposal is built to test it head on. The judge gets the identical calibration, so the comparison is purely about the signal. Our prediction is that the judge will over-trust plausible identifiers. That is the same overconfidence direct queries show in the reference-hallucination study, and it forces a strict threshold that blocks many correct calls. If the calibrated judge matches provenance on false-block rate, the lesson is that calibration is the contribution and the scorer is interchangeable. We will report it that way.
Why not just use a stronger model? Stronger models still fail badly: the best TOOLATHLON agent succeeds on 38.6% of tasks, and pass^k decay on τ-bench appears for every leaderboard model. More importantly, a better backbone gives no certified bound on anything. We run the gate across four backbones to check whether its benefit shrinks as model quality rises.
Why not just let the agent reflect and fix its own call? LEDGERMIND reports that free-form self-repair adds new fabrications while fixing old ones. The prompt-only ledger condition measures how much of our gain comes from moving the check outside the agent.
Why not just report bootstrap confidence intervals and add more tasks? Intervals describe an evaluation; they do not control deployed behavior, and they are part of our reporting in any case. Generating more tasks synthetically, as MCPEval does with GPT-4o-produced trajectories, shifts the task distribution. We test this directly by calibrating on synthetic tasks and checking coverage on the human-written ones.
Proposed Experiments and Decisive Checks
The primary testbed is τ-bench, with its tools wrapped as an MCP server. It provides gold actions, database-state checking, and pass^k. We use 50/50 random calibration/test splits of retail (115 tasks), repeated over 20 resamplings, with $\alpha\in\{0.05,0.1,0.2\}$, $\delta=0.1$, and $G=5$. Airline (50 tasks) is used first as a held-out domain and second as a within-domain case where only coarse $\alpha$ should be certifiable.
TOOLATHLON (108 tasks, native MCP, state-based checking) and MCPVerse (250 tasks, Standard and Max-Scale modes) test whether the gate transfers to messier real tool servers. Harm is labeled there from final-state checks, plus manual audit of blocked calls.
Metrics are the per-task violation rate with exact binomial intervals; pass^1 through pass^4; false-block rate, meaning blocked calls matching gold; escalation rate; and token cost.
Three results would change our minds. The first check is coverage. If realized test violation exceeds $\alpha$ in more than a $\delta$ fraction of resamplings, the task-level exchangeability argument is wrong. The second is signal. If the calibrated LLM-judge gate achieves equal false-block rate, the provenance scorer adds nothing. The third is transfer. Calibrating on retail and testing on airline should show the guarantee failing under shift, and we will measure by how much.
We will also check the $3/n$ prediction empirically: the smallest $\alpha$ each benchmark can certify should track its task count. That result converts the small-sample worry into a concrete sizing rule for anyone building agent benchmarks.
References
- LLM Agent Communication Protocol (LACP) Requires Urgent Standardization: A Telecom-Inspired Protocol is Necessary
- MCPVerse: An Expansive, Real-World Benchmark for Agentic Tool Use
- The Tool Decathlon: Benchmarking Language Agents for Diverse, Realistic, and Long-Horizon Task Execution
- LEDGERMIND: Provenance-Constrained Multimodal Agentic Reasoning with a Structured Evidence Ledger
- TRAC: Trustworthy Retrieval Augmented Chatbot
- τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains
- Do Language Models Know When They're Hallucinating References?
- MCPEval: Automatic MCP-based Deep Evaluation for AI Agent Models