The Verification Tax: Fundamental Limits of AI Auditing in the Rare-Error Regime

Jason Z Wang

cs.LGApr 14, 2026

The Verification Tax: Fundamental Limits of AI Auditing in the Rare-Error Regime

Authors: Jason Z Wang

Organizations: Independent

Abstract

The most cited calibration result in deep learning -- post-temperature-scaling ECE of 0.012 on CIFAR-100 (Guo et al., 2017) -- is below the statistical noise floor. We prove this is not a failure of the experiment but a law: the minimax rate for estimating calibration error with model error rate epsilon is Theta((Lepsilon/m)^{1/3}), and no estimator can beat it. This "verification tax" implies that as AI models improve, verifying their calibration becomes fundamentally harder -- with the same exponent in opposite directions. We establish four results that contradict standard evaluation practice: (1) self-evaluation without labels provides exactly zero information about calibration, bounded by a constant independent of compute; (2) a sharp phase transition at mepsilon approx 1 below which miscalibration is undetectable; (3) active querying eliminates the Lipschitz constant, collapsing estimation to detection; (4) verification cost grows exponentially with pipeline depth at rate L^K. We validate across five benchmarks (MMLU, TruthfulQA, ARC-Challenge, HellaSwag, WinoGrande; ~27,000 items) with 6 LLMs from 5 families (8B-405B parameters, 27 benchmark-model pairs with logprob-based confidence), 95% bootstrap CIs, and permutation tests. Self-evaluation non-significance holds in 80% of pairs. Across frontier models, 23% of pairwise comparisons are indistinguishable from noise, implying that credible calibration claims must report verification floors and prioritize active querying once gains approach benchmark resolution.

Figures & tables

Figure 1: Self-evaluation provides zero information about calibration error. Left: Confidence vs. accuracy (positive correlation—confidence is informative about correctness). Right: Confidence vs. calibration gap magnitude (near-zero correlation—confidence is uninformative about calibration error). Three models on MMLU.

Figure 2: Left: Phase transition—detection power vs.

m\cdot\varepsilon

across four error rates (synthetic). Right: Leaderboard noise—pairwise accuracy gaps vs. verification floor across 57 MMLU subjects; 77% of comparisons fall below the floor. See Appendix for enlarged version.

Benchmark	$n$	$\varepsilon$	$\delta_{\mathrm{floor}}$	Typical $\Delta$	Ratio	Verifiable?
MMLU (per-subj)	250	0.15	0.0843	0.02–0.05	0.4 $\times$	✗
MMLU (full)	14,042	0.15	0.0220	0.02–0.05	1.6 $\times$	$\sim$
TruthfulQA	817	0.40	0.0788	0.05–0.15	1.3 $\times$	$\sim$
BBQ (per-cat)	500	0.30	0.0843	0.03–0.10	0.8 $\times$	✗
ToxiGen	940	0.25	0.0643	0.05–0.12	1.3 $\times$	$\sim$
HumanEval	164	0.30	0.1223	0.05–0.20	1.0 $\times$	$\sim$

Table 1: Verification floor analysis for major AI benchmarks.

\delta_{\mathrm{floor}}=(L\varepsilon/n)^{1/3}

with

L{=}1

. Ratio

=\Delta_{\mathrm{typ}}/\delta_{\mathrm{floor}}

; values

<1

indicate claims below the verification floor.

Model A	Model B	Benchmark	$n$	Gap	$\delta_{\mathrm{acc}}$	Verifiable?
GPT-4o	Claude 3.5 Sonnet	HumanEval	164	0.017	0.0663	NO
Llama-3.1-405B	Qwen3-Next-80B	TruthfulQA	817	0.016	0.0341	NO
GPT-4	Claude 3 Opus	MMLU	14,042	0.004	0.0060	NO
GPT-4	Gemini 1.5 Pro	HumanEval	164	0.045	0.0663	NO
GPT-4o	Claude 3.5 Sonnet	GPQA Diamond	198	0.057	0.0709	NO
GPT-4	Gemini 1.5 Pro	MMLU	14,042	0.005	0.0060	NO

Table 2: Pairwise accuracy gaps vs. verification floor for frontier models. Comparisons sorted by gap/floor ratio (ascending). “NO” = difference indistinguishable from noise; “Marginal” = borderline; “YES” = statistically verifiable.

Figure 3: Active verification on real MMLU data. Left: Active vs. passive estimation error (log-log). Right: Error at fixed

m{=}2000

vs.

\hat{L}

—active (hatched) is

L

-independent; passive correlates with

L

Figure 4: Compositional verification tax (synthetic). Left: Estimation error vs.

m

for pipeline depths

K{=}1,\ldots,5

. Right: Sample cost to reach

\delta{=}0.05

vs.

K

(log-linear), with exponential fit (base 1.73).

Figure 5: (a) Minimax estimation error vs. error rate (fixed

m{=}10{,}000

L{=}1

). Sun et al.’s

\varepsilon

-independent rate is flat; ours decreases with

\varepsilon

, revealing a

2.7\times

gap at frontier error rates (

\varepsilon{=}0.05

). (b) Required samples for meaningful verification (

\delta{=}\varepsilon/2

). Both curves grow as

\varepsilon\to 0

; the verification horizon (dashed) marks where passive verification exceeds typical benchmark sizes.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Subject	$n$	L405B	L4-Mav	Q3-80B	Max gap	$\delta_{\mathrm{floor}}$	Verif.	Instab.
Professional Law	1534	0.72	0.68	0.68	0.040	0.175	✗	0.15
Moral Scenarios	895	0.87	0.47	0.67	0.402	0.179	✓	0.00
Miscellaneous	783	0.92	0.92	0.94	0.018	0.108	✗	0.44
Professional Psychology	612	0.87	0.86	0.87	0.005	0.133	✗	0.73
High School Psychology	545	0.93	0.92	0.96	0.037	0.104	✗	0.02
High School Macroeconomics	390	0.88	0.78	0.89	0.108	0.137	✗	0.27

Appendix

Table 3: Per-subject MMLU rankings for the 20 largest subjects.

\delta_{\mathrm{floor}}

is the verification floor; gaps below

\delta_{\mathrm{floor}}

are noise (marked ✗). Instability = fraction of 200 bootstraps where ranking changes.

Figure 6: Verification floors across 5 benchmarks. Only MMLU (

n{=}14{,}042

) has a floor safely below 0.05. Smaller benchmarks cannot verify typical calibration improvements.

Benchmark	Model	$N$	$\varepsilon$	ECE	$\hat{L}$	$\delta_{\mathrm{floor}}$	Self-eval $r$ ( $p$ )
MMLU	Llama-3.1-405B	14,042	0.160	0.1183	1.61	0.0264	$+0.35$ ( $p=0.36$ )
MMLU	Llama-4-Maverick	14,042	0.273	0.2620	1.00	0.0269	—
MMLU	Qwen3-Next-80B	14,042	0.165	0.1427	5.00	0.0389	$-0.50$ ( $p=0.67$ )
TruthfulQA	Llama-3.1-405B	817	0.234	0.1947	2.84	0.0933	$-0.43$ ( $p=0.34$ )
TruthfulQA	Llama-4-Maverick	817	0.656	0.6293	3.36	0.1391	$-0.20$ ( $p=0.80$ )
TruthfulQA	Qwen3-Next-80B	817	0.250	0.2224	3.64	0.1036	$-0.10$ ( $p=0.87$ )

Appendix

Table 4: Verification tax across five benchmarks and three models.

\hat{L}

is the estimated Lipschitz constant,

\delta_{\mathrm{floor}}

is the verification floor, and Self-eval

r

is the Spearman correlation between confidence and

|\text{calibration gap}|

across bins (non-significant

p>0.05

supports Theorem 7 ).

Figure 7: TruthfulQA self-evaluation analysis. Confidence tracks accuracy more reliably than calibration gap, consistent with the self-verification impossibility result.

Figure 8: TruthfulQA subsampling convergence. Estimation error shrinks with sample size but remains bounded below by the benchmark’s verification floor.

Figure 9: TruthfulQA phase transition. Detection power rises sharply once

m\cdot\varepsilon

clears the theoretical transition scale.

Figure 10: Real 2-stage pipeline verification error. The pipeline has consistently higher estimation error than the single model across sample sizes.

Figure 11: Real 2-stage pipeline Lipschitz comparison. The estimated system Lipschitz constant is

2.16\times

the single-model value, explaining the larger verification tax.

MMLU (14,042 items per model)
Model	$m$	$\varepsilon$	$\hat{L}$	$\mathrm{ECE}$	$\delta_{\mathrm{floor}}$
Qwen3-Next-80B	14,042	.165 [.158,.171]	2.45 [1.70,4.85]	.143 [.137,.149]	.031 [.027,.038]
Llama-4-Maverick	14,042	.273 [.266,.280]	2.01 [1.42,4.75]	.262 [.255,.270]	.034 [.030,.045]
Llama-3.1-405B	14,042	.160 [.154,.166]	1.41 [1.13,3.02]	.118 [.113,.124]	.025 [.023,.032]
TruthfulQA (817 items per model)
Qwen3-Next-80B	817	.250	3.64	.222	.104

Appendix

Table 5: Real-model verification audit.

\hat{L}

via finite differences; 95% bootstrap CIs in brackets (MMLU).

Model	Domain	$N$	$N^{*}_{\text{pass}}$	$N^{*}_{\text{act}}$	Gap	Exceeds
GPT-4	General NLP (MMLU-scale)	$1.80e+12$	$1.40e+4$	$1.96e+8$	128571428.57	✓
GPT-4	Medical imaging	$1.80e+12$	$5.00e+5$	$2.50e+11$	3600000.00	✓
GPT-4	Legal	$1.80e+12$	$1.00e+4$	$1.00e+8$	180000000.00	✓
GPT-4	Financial	$1.80e+12$	$2.00e+4$	$4.00e+8$	90000000.00	✓
GPT-4	Code (HumanEval-scale)	$1.80e+12$	$5.00e+3$	$2.50e+7$	360000000.00	✓
GPT-4	Autonomous driving	$1.80e+12$	$1.00e+5$	$1.00e+10$	18000000.00	✓

Appendix

Table 6: Verification horizon

N^{*}

for frontier models across domains. Gap

=N/N^{*}

; values

>1

indicate the model exceeds the horizon.

Framework	$K$	$\pi_{\min}$	$\delta$	$\varepsilon$	$m_{\text{req}}$	$m_{\text{active}}$	$m_{\text{avail}}$	Gap
EU AI Act Annex III	10	0.05	0.020	0.050	$1.25\times 10^{6}$	$2.50\times 10^{4}$	$7.07\times 10^{5}$	1.8 $\times$
NIST AI RMF	5	0.10	0.010	0.030	$1.50\times 10^{6}$	$1.50\times 10^{4}$	$5.00\times 10^{5}$	3.0 $\times$
FDA SaMD	8	0.05	0.010	0.020	$3.20\times 10^{6}$	$3.20\times 10^{4}$	$7.07\times 10^{5}$	4.5 $\times$

Appendix

Table 7: Data requirements for regulatory compliance verification. Gap

=m_{\text{req}}/m_{\text{avail}}

; values

>1

indicate infeasibility with current data.

$\varepsilon$	$c_{1}(\varepsilon)$	$m_{\mathrm{detect}}$ (Le Cam)	$m_{\mathrm{estimate}}$ (nonparametric)
0.01	0.3780	15	10,000
0.02	0.3638	27	20,000
0.05	0.3474	61	50,000
0.10	0.3326	111	100,000
0.15	0.3206	155	150,000
0.20	0.3093	192	200,000

Appendix

Table 8: Sharp Le Cam constants

c_{1}(\varepsilon)

and nonparametric estimation sample sizes. The Le Cam constant governs detection; the estimation column uses

m\geq L\varepsilon/\delta^{3}

with

L=1

\delta=0.01

Figure 12: Synthetic slope study: estimation error versus sample size for increasing numbers of zero-crossings.

Figure 13: Synthetic slope convergence to the minimax

-1/3

rate as zero-crossings increase.

Figure 14: Pseudo-classifier control: ECE estimate

\pm

std versus

m

, with the verification floor overlaid.

Figure 15: Pseudo-classifier control: detection power versus

m\cdot\varepsilon

, with the predicted phase transition at

m\cdot\varepsilon=1

Uncertainty Calibration

Uncertainty calibration aligns model confidence and predictive intervals with observed correctness and outcome frequencies.

See all 264 papers

AI Evaluation Should Measure Verification Cost, Not Correctness Alone
Aug 9, 2026Viviana Crescitelli, Generoso Immediato, Fabio Persia +1Language Model Generation Evaluation Generative AI Evaluation
Hitachi, Ltd., Tokyo, Japan · Hitachi Rail, Naples, Italy · Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila, Italy
Evaluating and Recalibrating Probabilistic Classifiers from One-Bit Threshold Queries
Sep 4, 2026Roman Plaud, Antoine Saillenfest, Matthieu Labeau +2Language Model Calibration Uncertainty Calibration
Institut Polytechnique de Paris · Onepoint, France · Ghent University
A Semantic-Sampling Framework for Evaluating Calibration in Open-Ended Question Answering
May 8, 2026Zhanliang Wang, Jiancong Xiao, Ruochen Jin +3LLM Evaluation Confidence Estimation in Language Models
University of Pennsylvania, Philadelphia, PA · Dartmouth College, Hanover, NH

Aug 9, 2026J/K move · Enter open · S save

AI Evaluation Should Measure Verification Cost, Not Correctness Alone

Viviana Crescitelli, Generoso Immediato, Fabio Persia, Stefania Costantini

Hitachi, Ltd., Tokyo, Japan · Hitachi Rail, Naples, Italy · Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila, Italy

Language Model Generation Evaluation Generative AI Evaluation

Open paper AskPDF arXiv

The reliability of AI generative models is typically measured by output correctness, yet in practice it depends on the effort required to verify those outputs. We argue that current evaluation metrics overlook a critical failure mode: Verification-Cost Errors (VCEs), defined as incorrect input-output pairs that a declared fraction of the verifier population fails to identify within the verification budget available in a given deployment context. Unlike standard notions of "hallucination", VCEs are defined operationally, by the failure of correct identification within budget rather than by any property of the output itself. Plausibility and authoritative presentation are hypothesised contributors to that failure, not defining conditions. To capture this asymmetry, we introduce the notion of verification cost relative to a deployment budget as an operational dimension that current evaluation does not routinely capture. The quantity is presented as a conceptual instrument rather than a finalized metric. Evidence from code generation and multi-modal document understanding shows that high benchmark accuracy can mask significant verification effort in practice. We therefore take the position that correctness alone is insufficient as a measure of reliability. AI evaluation should explicitly account for verification cost, reflecting whether errors can be detected under realistic resource constraints.

Abstract

Uncertainty Calibration

Explore similar work

AI Evaluation Should Measure Verification Cost, Not Correctness Alone

Evaluating and Recalibrating Probabilistic Classifiers from One-Bit Threshold Queries

A Semantic-Sampling Framework for Evaluating Calibration in Open-Ended Question Answering