Not Self-Decidable: LLMs Cannot Draw the Boundary of What an Agent Verifier Can Check

AI summary

Overview

Research area: Runtime verification of AI agents — specifically, how a verifier should decide which natural-language rules can be enforced by a fixed, mechanical check and which require an LLM judge.

Technical level: Intermediate. The argument is conceptual (a routing/decidability distinction) rather than mathematically heavy, but the paper leans on a dense empirical program: 832 predicates, six corpora, four models, multiple rubric variants and perturbation instruments.

Scope in one sentence: Across roughly 22,000 model labels, this paper shows that LLMs cannot reliably report which criteria a fixed check can settle, that their errors run in opposite directions on regulatory text and together on agent rule-sets, and that the boundary must instead be constructed by executing and intervening on synthesized checks.

What This Paper Is About

A verifier for an agent has to split the rules it enforces into two buckets: those a fixed, interpretation-free procedure can settle (the obligation "logs are retained for twenty-four months") and those that need a judge ("the disclosure is adequate"). Where requirements come from outside — finance, healthcare, law — the agent enforces rules it did not write, so that split falls to runtime, recurring for every predicate of every rule on every action. The paper calls the assumption that a model can make this call itself self-decidability, and shows it does not hold.

Key Contributions

1. The problem, named and located. The paper identifies self-decidability — whether a model can tell which criteria a fixed check can settle and which need a judge — as the routing decision every agent verifier makes before it checks anything. It is prior to the accuracy question the LLM-as-judge literature studies, and every escalation-based remedy silently assumes it has been solved.

2. CoVer (corroborate-then-verify). A procedure that keeps the model's answer off the critical path: agreement across independent models only nominates a predicate, and admitting it requires an interventional test the panel does not control. The paper shows the obvious alternative — agreement with a reference judge — measures whether a check is reproducible rather than whether a predicate is decidable, and replaces it with a gate that consults no estimator.

3. The measurements. 832 predicates from six corpora, each labelled by four foundation models across three labs under four rubric variants and two perturbation instruments: roughly 22,000 model calls.

4. The specification ablation. A pre-registered test showing that a far more prescriptive rubric buys agreement without buying correctness — specification moves the panel toward each other and away from the answer.

Main Findings

• Models can draw the line when it is clear. On the calibration endpoints IFEval (decidable pole) and MT-Bench (judgment pole), all four models agree near-perfectly (κ 0.92–0.99) with over- and under-claim near zero. The one exception reported is Opus over-claiming 10% on clear judgment.

• The boundary collapses on regulatory text. Across the 231 predicates of regulatory text, agreement falls to κ 0.20–0.50 under the fixed rubric, and the error is bidirectional: Llama (37%) and Sonnet (22%) lean toward over-claiming while GPT-4o (74%) and Opus (54%) lean toward under-claiming. The most opposed pair agrees at only κ 0.20.

• There is no conservative model to pick. The bias is model-specific, cross-lab and domain-specific. On the 231 regulatory-text predicates GPT-4o calls 41 decidable against Llama's 145, with GPT-4o's set lying inside Llama's on all but 2; on the 73 agent rules the containment reverses, Llama's 48 sitting inside GPT-4o's 62 on all but 1. GPT-4o, the heaviest under-claimer on statutes, becomes the heaviest over-claimer on agent rules.

• Every model flips to the unsafe direction on agent rules. On the operational agent rule-set over-claiming runs GPT-4o 71%, Sonnet 62%, Llama 46%, Opus 29% (κ 0.38–0.64). A reasoning-era model added after the measurements extends the split rather than repairing it, over-claiming 41% on regulatory text and 92% on agent rules.

• The contested zone is the central mass, not a tail. Measured ground-truth-free as the cross-model disagreement rate, the borderline covers 65% of EU AI Act predicates, 52% of FINRA and 33% of agent rules, against 23% synthetic. The rate rises monotonically with panel size, so these are lower bounds.

• The disagreement is a bug, not humility. The labels are opposed across models rather than converging, localised to the operationally critical middle, and unstable within a single model: under a loophole-free deterministic-template perturbation Opus flips its own borderline label 33% of the time against 5% on controls, and GPT-4o 44% against 7%. On 53 FINRA rules a human annotator sorted blind, agreement is again κ 0.34–0.48.

• Corroboration recovers a high-precision core, and its failure mode is instructive. Unanimous agreement yields a decidable set at 99.2% precision on gold-labelled synthetic data and 97.0% on regulatory text, but on the agentic corpus, where all four over-claim together, it falls to 83%.

• Specification suppresses disagreement rather than resolving it. Under R-spec the contested rate falls 30.9 pp on the EU AI Act and 19.6 pp on FINRA. But of the 71 regulatory-text predicates R-spec converts from contested to unanimous, the manufactured consensus is correct 57.7% of the time (Wilson 95%: 46.2–68.5) against 88.8% (80.5–93.8) for consensus that formed unprompted. The converted set is 74.6% decidable, so a router that always said "decidable" would score 74.6%. Twenty-nine of R-spec's 30 errors are under-claims. On operational agent rules it buys nothing (33% → 33%). An equally correct variant with eight different worked examples resolves a different third of the predicates (Jaccard 63.3%) and is 75.9% accurate against R-spec's 57.7% (z = 2.16, p = 0.031).

• A reference judge certifies nothing. Calibration agreement predicts held-out agreement almost perfectly, rising monotonically from 29.6% to 76.7% across four buckets, but the true-decidable rate across those same buckets runs 55.6, 75.0, 62.8, 62.3 and 79.1% and moves nowhere. At τ = 1 the gate admits 43/173 predicates at 79.1% precision — but 38 of the 173 have a reference verdict that never varies, and the gate takes 16 of those, scoring 100.0% there against 66.7% (Wilson 95%: 47.8–81.4) on the 27 varying predicates it admits, a lift of 4.4 points over their 62.2% base rate. The abstract summarises this as agreement climbing from 30% to 77% across calibration bands while the genuinely decidable share does not move.

• The interventional gate carries real signal, and not enough of it. Tightening invariance from half to full agreement lifts precision from 66.7% to 85.0% against a 67.1% base rate. Of the seven false-decidables that survive unanimity, the gate rejects five, admitting 6.7 predicates per false-decidable against unanimity's 5.9. On the seeded half it admits 10 predicates at 90.0% precision with one false-decidable, against unanimity's 19 at 89.5% with two. It does not clear the bar of beating unanimity's precision at comparable elimination: it removes 27.4% of judge calls where unanimity removes 56.2%.

• The needed instrument fails. A self-consistency test built to measure consistency across independent attempts (K = 5 extractions at temperature 1.0 on a fixed prefix of 12 records) separates decidable from judgment at chance: AUC 0.42–0.48 on the 20 predicates that reached it. The median predicate of both classes is perfectly self-consistent — an estimator's agreement with itself certifies no more than its agreement with a judge.

• Each layer has one thing it cannot check. Corroboration cannot certify itself, agreement cannot certify mechanicality, and intervention cannot certify faithfulness.

• Limitations reported by the authors. The agentic corpus is narrow: 73 predicates over 20 rule families from one deployed credit agent, with over-claim rates resting on its 24 true-judgment predicates, so Wilson 95% intervals run roughly 35 pp wide. Ground truth on the regulatory corpora is an LLM-assigned proxy. The interventional evaluation rests on 36 synthetic action records. Appendix E states six further limitations.

Methodology in Plain English

The authors start from the observation that any agent verifier must sort each rule predicate into one of two buckets — settle it with code, or spend a model call on a judge — and that no one has tested whether models can make that sorting call.

They build corpora that bracket the boundary. IFEval sits at the clearly decidable pole and MT-Bench at the clearly judgment pole; the contested middle is policy text from the EU AI Act and FINRA, plus an operational AI-agent rule-set, with a gold-labelled synthetic corpus as a control. Predicates were decomposed from rule text by an LLM under a fixed schema, blind to the labelling being studied. Four models from three labs — Claude Sonnet, Claude Opus, GPT-4o and Llama-3.1-70B — each label every predicate against a fixed rubric at temperature 0 with no hedging permitted.

They then red-team their own harness: one variant (R-proc) restates the same criterion procedurally to isolate surface form, another (R-spec) adds a decision procedure, boundary rules and worked examples to isolate underspecification. They pre-committed to the bar that a fall of more than 5 pp in contested rate on a real corpus would support the objection that they measured their own prompt rather than model unreliability.

For the proposed fix, CoVer, they avoid asking models anything further after nomination. A predicate is decomposed into named fact-slots and a decision rule; a model fills the slots and code evaluates the rule. Four gates must pass: structure (the check must not reduce to an identity on one slot), groundedness (slots must be readable from attested fields the agent cannot write), sensitivity (the verdict must move when a slot is intervened on) and invariance (the verdict must hold under deterministic rewording). A failing gate escalates the predicate rather than admitting it, so the router fails closed. The gate is evaluated on the agent rule-set — the corpus where corroboration fails — running 73 predicates against 36 synthetic action records with a seeded split so the operating point is chosen on one half and reported on the other.

Why This Matters

The paper targets a precondition that every escalation-based remedy in production assumes but nobody has measured. If a verifier over-claims decidability, the predicate is never escalated and the safety mitigation is silently switched off — an error that is directional, repeated across a fleet, and invisible.

Real-world applications:

• Financial services compliance. FINRA-style obligations and a deployed credit agent are directly in scope; a misrouted judgment predicate means an unsupervised system certifies compliance it never assessed.
• Healthcare claims and disclosure. Where governing text splits into arithmetic on timestamps and judgment calls about adequacy, the routing error determines whether a judgment is automated away.
• Regulated AI deployment under the EU AI Act. The paper measures the contested rate on EU AI Act predicates at 65%, the highest of any corpus it reports.
• Agentic guardrails and automated policy compliance. Any agent enforcing rules it did not author — where the predicate set is externally imposed and the deploying party neither chooses its obligations nor may rephrase the hard ones — faces the same runtime split.

Industry relevance: The two error directions carry different costs. Over-claiming costs a missed violation; under-claiming costs an extraneous inference one call at a time, which the paper describes as how a year's inference budget disappears in four months. Because a rule passes only if all its predicates are handled correctly together, the chance every routing call is right degrades geometrically as rules lengthen, and no deployment escapes both errors by simply choosing a model.

Future Directions

• Build the cross-record consistency instrument. The paper diagnoses its invariance gate as a statistic within one record where the difficulty gradient is a property between records, and states that the instrument this calls for measures consistency across independent attempts rather than invariance under paraphrase. It reports the attempt it built as failing at chance (AUC 0.42–0.48).
• Certify faithfulness. A check can be grounded, sensitive and invariant while verifying only part of what its predicate asks — one agent obligation carries three deontic clauses and its rule covers one. Establishing faithfulness would mean putting a judge back in, and the paper leaves this open.
• Widen the agentic evidence base. The current agent corpus is 73 predicates over 20 rule families from one deployed credit agent, with intervals roughly 35 pp wide on the over-claim rates; magnitudes need replication even though the direction is robust.
• Replace proxy ground truth. The regulatory corpora rely on an LLM-assigned proxy, mitigated only by leading on the ground-truth-free disagreement metric and by 53 blind human labels on FINRA rules.

Target Audience

Researchers and engineers working on LLM-as-judge methods, agent runtime verification, and verifier design will find the core argument most relevant, as will compliance and governance teams deploying agents under externally written rules in finance, healthcare and law. Practitioners who currently treat a capable model as a good-enough oracle for any evaluation query are the paper's explicit target. Readers need enough familiarity with classification agreement statistics to follow the κ and precision/coverage tables, but the central claim — that self-decidability is a boundary the verifier must construct rather than a capability to elicit from a model — is stated and argued in plain terms.

Authors’ abstract

A verifier for an agent faces rules of two kinds: the ones a fixed check can settle and the ones that require a judge. A team that derives its own checks fixes that split up front. Where the requirements come from outside, as in finance, healthcare and law, the agent enforces rules it did not write, so the split falls to runtime, recurring for every predicate of every rule on every action at a rate no reviewer can audit. Every escalation scheme assumes a model can make that decision itself, that it is self-decidable. Across six corpora, including the EU AI Act, FINRA guidance and a deployed credit agent, we collect roughly 22,000 labels from four models built by three labs. They agree almost perfectly where the answer is obvious and collapse on regulatory text; their errors run in opposite directions, so no model can be trusted as the conservative choice; and on the deployed agent's own rule-set they err together, over-claiming that a fixed check will do, the direction that never gets escalated. We introduce CoVer (corroborate-then-verify), which treats unanimity as a nomination, admitting a predicate only when the check synthesized for it survives intervention, reading fields the agent cannot write and holding under deterministic rewording. That gate rejects most of what corroboration wrongly admits, at a cost in coverage we report rather than tune away. The obvious alternative, agreement with a reference judge, certifies nothing: it climbs from 30% to 77% across calibration bands while the genuinely decidable share does not move, because a judge drawn from the population under indictment ratifies the blind spot it shares. Self-decidability is not a capability to elicit from a model but a boundary the verifier must construct.