arXiv:2604.12951v1 [cs.LG] 14 Apr 2026
The Verification Tax: Fundamental Limits of AI Auditing in the Rare-Error Regime
Jason Z Wang Independent [email protected]
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 ε is Θ((Lε/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 m · ε ≈ 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 LK . 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.
1
Introduction
The base rate problem—that rare conditions are hard to detect—is among the oldest results in statistics. We show that AI auditing faces the same fundamental barrier. The “disease” is miscalibration: the gap between a model’s stated confidence and its actual accuracy. As errors become rare, miscalibration becomes a rare condition, and the verification cost grows without bound. We call this the verification tax. In one line: better models are harder to audit. This result completes a programme initiated by Sun et al. [2023], who established the O(n−2/3 ) upper bound for ECE estimation (NeurIPS 2023 Spotlight), and extended by Futami and Fujisawa [2024], who generalized the rate information-theoretically (NeurIPS 2024). Both left two questions open: (1) Is n−1/3 the optimal rate? (2) How does the model’s error rate ε affect verification difficulty? We resolve both. The lower bound (Theorem 2) matches the upper bound (Theorem 3), establishing (Lε/m)1/3 as the minimax rate. The ε-dependence—absent from all prior work—reveals a phase transition, a scaling duality, and a verification horizon. The tax is a law: no estimator can beat Θ((Lε/m)1/3 ). Under meaningful verification (δ = Θ(ε)), sample complexity grows as Ω(1/ε2 ). Capability and verifiability are governed by the same exponent in opposite directions (Theorem 4). Preprint.
But the rate is the scaffolding. The paper’s contributions are four results that contradict standard assumptions in AI evaluation [Liang et al., 2023, Zheng et al., 2023, Chiang et al., 2024]: Surprise 1: Self-evaluation is bounded by a constant (§3). Any estimator that does not use ground-truth labels—including LLM-as-Judge, self-consistency, chain-of-thought verification, and all model-derived signals—has worst-case calibration error ≥ 1/2 for L ≥ 1. The bound is independent of the number of queries. White-box model access does not help unless it identifies a low-dimensional parametric family. Surprise 2: There is a sharp phase transition (§4). Below m · ε ≈ 1, miscalibration is undetectable by any method. We show that most published safety benchmark improvements fall below the verification floor (Table 4), and 65% of MMLU per-subject rankings are noise. Surprise 3: Active querying p eliminates L (§5). When the auditor chooses which inputs to test, the minimax rate improves to Θ( ε/m)—the Lipschitz constant disappears entirely. We validate this on production LLMs: all three models collapse to the same active rate despite L̂ ∈ [1.4, 2.5]. Surprise 4: Composition is exponential (§6). A K-component AI pipeline has verification cost Ω(LK · ε/δ 3 ). A 10-step agent loop with L = 2 costs 1,024× a single-step model. This applies to chain-of-thought, retrieval-augmented generation, and agentic systems. Together, these results imply that the dominant practices in AI evaluation—passive benchmarking, self-evaluation, and end-to-end testing of complex pipelines—operate in provably information-less regimes. We demonstrate this empirically and show that every frontier model exceeds the verification horizon (§7). Concrete scale. The law already bites on today’s benchmarks. On MMLU (n=14,042, ε≈0.16, L̂≈1.4), the calibration floor is about 0.028, while the corresponding accuracy floor is only 0.006: calibration is about 4.7× harder to verify than accuracy. On TruthfulQA (n=817), the floor rises to 0.093–0.139, large enough to swamp many reported improvements. Even if frontier models reach ε ≈ 0.05 on MMLU, the passive floor remains ≈ 0.016–0.018. The practical implication is simple: below-floor gains should be treated as ties unless the evaluator uses much larger holdouts or active querying.
2
The Verification Tax
Setup. Let f be a classifier with confidence p(x) ∈ [0, 1]. The calibration P gap is¯∆(p) = η(p) − p where η(p) = E[Y =ŷ | p(X)=p]. The binned ECE is ECEB = b (nb /n)|∆ b |. We consider L-Lipschitz calibration functions F(L) = {∆ : |∆(p1 ) − ∆(p2 )| ≤ L|p1 − p2 |} and the minimax [ risk R∗ (m, ε, L) = inf ECE [ sup∆∈F (L) E[|ECE − ECE|], where ε = Pr[Y ̸= ŷ] is the error rate. p √ Theorem 1 (Le Cam Lower Bound). R∗ (m, ε, L) ≥ c1 ε/m, where c1 ≥ 1/(4 2). Proof sketch. Construct P0 (calibrated, ECE = 0) and P1 (miscalibrated by δ) p at p0 = 1 − ε. KL divergence: mδ 2 /ε. Setting KL = 1 via Bretagnolle–Huber gives R∗ ≥ (1/2e) ε/m. Full proof: Appendix H. Theorem 2 (Minimax Lower Bound). Under score-mass concentration near 1−ε, R∗ (m, ε, L) ≥ c2 (Lε/m)1/3 · (log m)−c3 . Proof sketch. The full proof (Appendix B) constructs two product priors on L-Lipschitz calibration functions directly in the Bernoulli observation model, following the two-prior method of Lepski et al. [1999]. The construction uses a signed measure that separates L1 norms while controlling the Bernoulli KL divergence, yielding the rate (Lε/m)1/3 up to logarithmic factors without invoking asymptotic equivalence to white noise. An alternative derivation via Brown–Low equivalence [Brown and Low, 1996] is in Appendix K. Theorem 3 (Matched Upper Bound). Histogram binning with B ∗ = ⌊(L2 m/ε)1/3 ⌋ achieves [ B ∗ − ECE|] ≤ C(Lε/m)1/3 . E[|ECE 2
Proof sketch. Bias ≤ L/B, variance ≤
p
εB/m. Optimize at B ∗ = (L2 m/ε)1/3 .
The polynomial rate (Lε/m)1/3 is established by matching upper and lower bounds. The lower bound ′ carries a logarithmic correction (log m)−c inherited from the structure of L1 functional estimation: the non-smoothness of |t| at zero requires a Fourier-analytic construction whose truncation introduces the logarithmic loss. This is the same gap identified by Lepski et al. [1999] twenty-seven years ago, and it remains open whether the gap belongs in the lower bound or the upper bound. We conjecture that the minimax rate is exactly Θ((Lε/m)1/3 ) with no logarithmic correction. Resolving this would settle a longstanding question in nonparametric functional estimation, independent of the AI auditing application. Theorem 4 (Scaling Duality). If ε(N ) = c0 N −α for α > 0, then under meaningful verification (δ = Θ(ε)), the sample complexity satisfies m(N ) = Ω(N α ). Capability and verifiability scale with the same exponent in opposite directions. Corollary 5 (Phase Transition). Taking δ = ε: detection is impossible for m < c21 /ε and possible for m > C/ε. The transition occurs at m∗ ≍ 1/ε. Corollary 6 (Benchmark Resolution Limit). For a benchmark of n items, the minimum detectable calibration difference between two models is δmin = (Lε/n)1/3 . Rankings of models whose differences fall within δmin are statistically indistinguishable from noise.
3
Surprise 1: Self-Evaluation Provides Zero Information
Theorem 7 (Self-Verification Impossibility). Let z(x) = g(x, θ) be any auxiliary signal derived from the model. Any estimator V (x1 , p1 , z1 , . . . , xm , pm , zm ) that does not use true labels satisfies: sup∆∈F (L) E[|V − ECE(∆)|] ≥ min(L, 1)/2. Proof. ∆0 ≡ 0 and ∆1 ≡ min(L, 1) produce identical observations (xi , pi , zi ) for any model. Any label-free estimator returns the same value under both, so it errs by ≥ min(L, 1)/2 on at least one. Corollary 8 (LLM-as-Judge Impossibility). Let J be any evaluator model. If J’s evaluation of subject model S relies solely on (xi , fS (xi ))—inputs and outputs, without ground-truth labels—then sup∆ E[|VJ − ECE|] ≥ 1/2 for L ≥ 1, regardless of J’s capability or the number of evaluations. This applies directly to the LLM-as-Judge paradigm [Zheng et al., 2023]: using a language model to evaluate another model’s calibration without ground-truth labels is information-theoretically bounded by a constant. Corollary 9 (Hallucination Detection Wall). Factual accuracy is a special case of calibration. Self-consistency methods (sampling multiple responses, checking agreement) operate without labels and incur worst-case error ≥ 1/2. Self-reported hallucination rates have zero information-theoretic content. Corollary 10 (Instance-Dependent Self-Verification Impossibility). For any label-free estimator V and any δ ∈ (0, min(L, 1)]: sup∆∈F (L), ECE(∆)=δ E[|V − ECE(∆)|] ≥ δ/2. That is, for every ECE value δ, there exists a calibration function with that ECE that any label-free estimator will mis-estimate by at least δ/2. Proof. Fix δ. Let ∆0 ≡ 0 (ECE = 0) and ∆δ with ECE = δ. Both produce identical label-free observations. For any V : E[|V − 0|] + E[|V − δ|] ≥ δ. Thus max{E[|V − ECE(∆0 )|], E[|V − ECE(∆δ )|]} ≥ δ/2. Theorem 11 (White-Box Irrelevance). p Let S = σ(θ, A, Dtrain ). Any S-measurable estimator using m fresh samples satisfies RS∗ ≥ c ε/m. White-box access √ helps only by constraining ∆ to a parametric family (Corollary: d-dimensional family ⇒ O(1/ m) rate). Empirical validation. Figure 1 confirms the theory on MMLU (14,042 items, 3 models). Left: confidence predicts accuracy (Spearman ρ = 0.55–0.95, all p < 0.05). Right: confidence does not predict calibration gap magnitude (ρ = 0.39–0.53, 2/3 non-significant). Self-confidence tells you whether you are right, not how wrong your confidence is. 3
(a) Confidence vs. Accuracy 0.8
|Calibration Gap|
Accuracy
0.8
(b) Confidence vs. |Calibration Gap|
Llama-3.1-405B: rs = 0.95 *** Llama-4-Maverick: rs = 0.55 * Qwen3-Next-80B: rs = 0.82 ***
0.6 0.4 Llama-3.1-405B Llama-4-Maverick Qwen3-Next-80B
0.2 0.4
0.5
0.6
0.7
Confidence
0.8
0.9
Llama-3.1-405B Llama-4-Maverick Qwen3-Next-80B
Llama-3.1-405B: rs = 0.39 n.s. Llama-4-Maverick: rs = 0.53 * Qwen3-Next-80B: rs = 0.42 n.s.
0.6 0.4 0.2
1.0
0.4
0.5
0.6
0.7
Confidence
0.8
0.9
1.0
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.
Table 1: Verification floor analysis for major AI benchmarks. δfloor = (Lε/n)1/3 with L=1. Ratio = ∆typ /δfloor ; values < 1 indicate claims below the verification floor. Benchmark MMLU (per-subj) MMLU (full) TruthfulQA BBQ (per-cat) ToxiGen HumanEval SWE-bench Verified GPQA Diamond WinoGender GSM8K ARC-Challenge
4
n
ε
δfloor
Typical ∆
Ratio
Verifiable?
250 14,042 817 500 940 164 500 198 720 1,319 1,172
0.15 0.15 0.40 0.30 0.25 0.30 0.70 0.50 0.10 0.08 0.10
0.0843 0.0220 0.0788 0.0843 0.0643 0.1223 0.1119 0.1362 0.0518 0.0393 0.0440
0.02–0.05 0.02–0.05 0.05–0.15 0.03–0.10 0.05–0.12 0.05–0.20 0.05–0.15 0.05–0.15 0.02–0.08 0.02–0.05 0.02–0.05
0.4× 1.6× 1.3× 0.8× 1.3× 1.0× 0.9× 0.7× 1.0× 0.9× 0.8×
✗ ∼ ∼ ✗ ∼ ∼ ✗ ✗ ✗ ✗ ✗
Surprise 2: Phase Transition and the Demolition
The phase transition (Corollary 5) predicts a sharp wall at m ·ε ≈ 1. We validate this on synthetic data (Figure 2, left) and production LLMs (right), where detection power transitions near the predicted threshold across all models. The benchmark demolition. Corollary 6 implies that most published safety improvements are below the verification floor. Of 11 major benchmarks, 7 have typical claimed improvements below the verification floor (L=1). Zero are robustly verifiable. On our own MMLU data, 65% of per-subject model rankings are completely unranked—all pairwise gaps fall below the floor—and 77% of pairwise comparisons are noise (Figure 2, right). Are the differences between frontier models real? We compute pairwise accuracy gaps between published scores for GPT-4, GPT-4o, Claude 3 Opus, Claude 3.5 Sonnet, Gemini 1.5 Pro, Gemini Ultra, and Llama-3-405B across four benchmarks. Of 64 pairwise comparisons, 23% are unverifiable or marginal (Table 4). On GPQA Diamond (n=198), zero of three model pairs are statistically distinguishable. On HumanEval (n=164), 40% of pairs are unverifiable or marginal. Even on MMLU (n=14,042), GPT-4 vs. Claude 3 Opus (gap 0.4%, floor 0.6%) is noise. The top of the leaderboard is, in substantial part, a tie. 4
Phase Transition in Calibration Detection (Beta DGP) 1.0
Detection power
0.8 0.6 0.4 = 0.02 = 0.05 = 0.1 = 0.2 m =1
0.2 0.0 101
100
102
Normalized sample size m
(a) Distribution of Pairwise Gaps
(b) Size vs. Ranking Instability
Below floor (132) Above floor (39) Median floor = 0.137
70
0.8 0.7
Ranking Instability Fraction
60
Count
50 40 30 20
0.5 0.4 0.3 0.2 0.1
10 0
0.6
0.0 0.0
0.1
0.2
0.3
0.4
0.5
Pairwise Accuracy Gap
0.6
0.7
0.8
0
200
400
600
800
1000
1200
Subject Size (number of items)
1400
1600
Figure 2: Left: Phase transition—detection power vs. m · ε 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.
5
Surprise 3: Active Querying Eliminates L
∗ Theorem 12 (Active Verification Rate). With adaptive confidence-level selection, Ractive (m, ε, L) = p Θ( ε/m). The Lipschitz constant disappears entirely.
Proof sketch. Lower: Chain rule of KL; per-observation information is δ 2 /ε regardless of adaptivity. Upper: Two-phase explore-exploit. p Phase 1: resolve sign of ∆pon N grid points. Phase 2: estimate |∆| in resolved bins. Set N = L m/ε; both terms become O( ε/m). Full proof: Appendix C.
The gap between passive ((Lε/m)1/3 ) and active ( ε = 0.16: active is ∼5× more efficient.
p
ε/m) is (L2 m/ε)1/6 . For L = 2.5, m = 10,000,
Empirical validation on MMLU. Figure 3 validates Theorem 12 on production data. Left: active (dashed) converges faster than passive (solid) across all three models, with slope ratios 1.38–1.48 (theory: 1.50). Right: at fixed m=2000, active errors are {0.0091, 0.0092, 0.0077} across models with L̂ ∈ {1.41, 2.01, 2.45} (coefficient of variation 8%)—confirming L-independence. 5
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. Model A
Model B
GPT-4o Llama-3.1-405B GPT-4 GPT-4 GPT-4o GPT-4 Llama-3-405B Llama-3.1-405B GPT-4 GPT-4o
Claude 3.5 Sonnet Qwen3-Next-80B Claude 3 Opus Gemini 1.5 Pro Claude 3.5 Sonnet Gemini 1.5 Pro Qwen3-Next-80B Qwen3-Next-80B Llama-3-405B Gemini 1.5 Pro
δacc
Verifiable?
HumanEval TruthfulQA MMLU HumanEval GPQA Diamond MMLU MMLU MMLU HumanEval GPQA Diamond
164 817 14,042 164 198 14,042 14,042 14,042 164 198
0.017 0.016 0.004 0.045 0.057 0.005 0.005 0.005 0.056 0.069
0.0663 0.0341 0.0060 0.0663 0.0709 0.0060 0.0060 0.0060 0.0663 0.0709
NO NO NO NO NO NO NO NO NO NO
Pairs
Unverifiable
Marginal
Verifiable
14,042 817 164 198
45 6 10 3
13% 17% 30% 67%
2% 0% 10% 33%
84% 83% 60% 0%
—
64
19%
5%
77%
Overall
(b) Error at m=2,000 Mean ECE estimation error
(a) Active vs. Passive on Real MMLU
10 1
Mean ECE estimation error
Gap
n
Benchmark MMLU TruthfulQA HumanEval GPQA Diamond
n
Benchmark
m 1/3
10 2
Passive (3 models) Active (3 models) Theory references 102
m 1/2
103
Number of samples m
0.008 0.006 0.004 0.002 0.000
104
Passive Active
405B (L=1.4)
Maverick (L=2.0)
Qwen3-80B (L=2.5)
Figure 3: Active verification on real MMLU data. Left: Active vs. passive estimation error (log-log). Right: Error at fixed m=2000 vs. L̂—active (hatched) is L-independent; passive correlates with L.
6
Surprise 4: Composition Is Exponential
Theorem 13 (Compositional Verification Tax). For a K-component pipeline with per-component Q Lipschitz L1 , . . . , LK : Lsys ≤ k Lk + 1, and msys = Ω(Lsys · ε/δ 3 ). For homogeneous Lk = L > 1: msys = Ω(LK · ε/δ 3 )—exponential in pipeline depth. Maximum verifiable depth: Kmax = ⌊logL (Mtotal δ 3 /ε)⌋. An agent with 10 reasoning steps at L=2: 1,024× cost. At L=2, K=20: over 106 ×. The Lipschitz composition model applies to continuous reasoning chains (chain-of-thought, iterative refinement). Discontinuous components such as retrieval or tool use have Lk = ∞, making end-to-end verification infeasible at any sample size for such pipelines. Theorem 14 (General Verification Tax). For any verification functional V (∆, µG ) = R |∆(p)| dµG (p) with L-Lipschitz integrand, effective noise σ 2 , and effective sample meff : passive p rate Θ((Lσ 2 /meff )1/3 ); active rate Θ( σ 2 /meff ). Instantiations: calibration (G = population), fairness (meff = mπ), robustness (σ 2 = εpert ). Corollary 15 (Fairness Tax). For a group with proportion π, verification requires m ≥ (1/π) · Lε/δ 3 . A 5% minority group costs 20× the full population. 6
(b) Cost vs. Pipeline Depth
10 2
10 3
Empirical fit (base=1.73) L K reference (L=2.5)
105
10 1
Samples to reach
Mean ECE estimation error
(a) Error vs. m by Pipeline Depth
K=1 K=2 K=3 K=4 K=5
103
104
1
104
Number of samples m
2
3
Pipeline depth K
4
5
Figure 4: Compositional verification tax (synthetic). Left: Estimation error vs. m for pipeline depths K=1, . . . , 5. Right: Sample cost to reach δ=0.05 vs. K (log-linear), with exponential fit (base 1.73).
7
The Verification Horizon
Theorem 16 (Verification Horizon). Let ε(N ) = c0 N −α and Mtotal be total labeled data. The verification floor is δfloor (N ) = (Lε(N )/Mtotal )1/3 . Meaningful verification requires N < N ∗ = (c20 Mtotal /L)1/(2α) . Under Chinchilla scaling (α ≈ 0.5, c0 ≈ 1, L = 1, Mtotal = 14,000): N ∗ ≈ 107 —well below current frontier models (> 1011 ). Across the domains we audit, every frontier system exceeds the passive horizon by orders of magnitude; representative calculations are deferred to Appendix G. ∗ Active verification shifts the horizon to Nactive = (c0 Mtotal )1/α , but no current evaluation framework supports active querying at scale. Regulatory infeasibility. The fairness tax (Corollary 15) compounds with the base verification tax across demographic subgroups. If evaluation must certify calibration to precision δ across K groups with minimum proportion πmin , then m ≥ KLε/(πmin δ 3 ). Under illustrative EU AI Act Annex III settings (K=10, πmin =0.05, δ=0.02, ε=0.05), this requires 1.25M labels against ∼700K available medical-imaging labels. Appendix G reports the broader cross-framework comparison and assumptions. Verification half-life. Under ECE drift rate λ, every verification expires after t1/2 = δ/λ. Representative domains range from months (medical AI) to hours (financial trading), so even successful audits must be periodically renewed.
8
Empirical Validation
All four surprises are validated on five benchmarks (MMLU: 14,042; TruthfulQA: 817; ARCChallenge: 1,172; HellaSwag: 10,042; WinoGrande: 1,267) with 6 LLMs from 5 families (8B–405B), yielding 27 benchmark–model runs with logprob-based confidence scores. All quantities carry 95% bootstrap CIs (1,000 replicates; Appendix S). Figure 5 shows how the ε-dependent rate diverges from prior work as models improve. Results. (1) Self-confidence is uninformative about calibration gap: across 14 benchmark–model pairs, 89% show non-significant Spearman correlation between confidence and calibration gap (p > 0.05), with permutation tests confirming on MMLU and TruthfulQA (Fig. 1). Theorem 7 is a worst-case bound; the rare significant pairs involve extreme miscalibration (ECE > 0.6). (2) Phase transition at m · ε ≈ 1 confirmed on all benchmarks. (3) Active querying achieves L-independent rates on MMLU with slope ratio 1.38–1.48 (theory: 1.50) and L-independence CV = 8% (Fig. 3). (4) Compositional cost grows exponentially in synthetic pipelines (Fig. 4) and a real 2-stage pipeline has L̂sys = 3.05 vs. single-model 1.41 (2.16×; Appendix S). These empirical results align with the 7
(a) Estimation error vs. error rate
(b) Sample cost of meaningful verification 107
10 2
Frontier
10 2
105
m=100k
104
m=10k
103 102
Sun et al. (L/m)1/3 Our passive (L /m)1/3 Our active General /m
10 3
Passive: m = 8L/ 2 Active: m = 4/
106
2.7× gap
Required samples m
Minimax estimation error
10 1
101 10 2
10 1
Error rate
10 1
Error rate
Figure 5: (a) Minimax estimation error vs. error rate (fixed m=10,000, L=1). Sun et al.’s εindependent rate is flat; ours decreases with ε, revealing a 2.7× gap at frontier error rates (ε=0.05). (b) Required samples for meaningful verification (δ=ε/2). Both curves grow as ε → 0; the verification horizon (dashed) marks where passive verification exceeds typical benchmark sizes. practical checklist advertised in the introduction: report the floor, treat below-floor gaps as ties, and switch to active querying when passive resolution saturates. ECE vs. accuracy floors. The p verification tax ((Lε/n)1/3 ) gives the floor for calibration comparisons; the standard binomial floor (2 ε(1 − ε)/n) gives the floor for accuracy comparisons. On MMLU (n=14,042, ε=0.16, L=1.4): accuracy floor = 0.006, ECE floor = 0.028—a 4.7× gap. Models that are distinguishable on accuracy may still be indistinguishable on calibration. Representative audit tables and the full five-benchmark breakdown are deferred to the appendix. Extended results across all five benchmarks (14 benchmark–model pairs, ε ∈ [0.04, 1.0], verification floors 0.026–0.139) are in Appendix S. Four of five benchmarks have mean verification floors ≥ 0.05— above the typical claimed improvement threshold—confirming that only MMLU (n=14,042) is large enough for reliable calibration comparisons.
9
Related Work
Calibration estimation. Sun et al. [2023] and Futami and Fujisawa [2024] established O(n−1/3 ) ECE upper bounds without tracking ε-dependence. We provide the matching lower bound and reveal the phase transition. Hu et al. [2024] study calibration testing (Ω(ε−2.5 ) complexity); Blasiok et al. [2023] introduce calibration distance. Active and sequential evaluation. Kossen et al. [2021] propose practical active testing; Theorem 12 provides the matching minimax rate. Shekhar and Ramdas [2024] develop sequential fairness tests; our sequential result (Appendix M) provides the matching lower bound. Nonparametric functionals. Our lower bound builds on Lepski et al. [1999]. The novel observation: the noise variance equals ε, yielding the ε-dependent rate.
10
Conclusion
The verification tax is a law: Θ((Lε/m)1/3 ) for passive verification, with no escape via model access, self-evaluation, or strategic miscalibration. Better models are harder to audit; passive benchmarking fails exactly when frontier gaps become small; and active querying is the only route that asymptotically removes the Lipschitz penalty. Practically, papers should report verification floors beside calibration claims, size holdouts via m ≥ Lε/δ 3 , and treat leaderboard gaps below the floor as ties rather than progress. Prediction. Under current scaling trends (α ≈ 0.5), next-generation frontier models will achieve ε ≈ 0.05–0.08 on MMLU. At this error rate, the verification floor on MMLU (n=14,042) is 8
δfloor ≈ 0.016–0.018, so we predict that most claimed calibration gains in next-generation technical reports will remain below the detectable floor. Anonymous software. An anonymized implementation of the verification-floor, holdout-sizing, and verifiability-assessment tools is included in the supplementary material and can be publicly released upon publication. Limitations and open problems. Our analysis assumes Lipschitz calibration, leaves a logarithmic gap between Theorems 2 and 3, uses worst-case Lipschitz accumulation in composition, and focuses on ECE rather than alternative calibration functionals. Closing the log gap and handling discontinuous or multiclass settings remain open.
References Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1727–1740, 2023. Lawrence D Brown and Mark G Low. Asymptotic equivalence of nonparametric regression and white noise. Annals of Statistics, 24(6):2384–2398, 1996. Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios N Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph E Gonzalez, and Ion Stoica. Chatbot arena: An open platform for evaluating LLMs by human preference. In International Conference on Machine Learning, 2024. Futoshi Futami and Masahiro Fujisawa. An information-theoretic analysis of expected calibration error. In Advances in Neural Information Processing Systems, volume 37, 2024. Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321–1330. PMLR, 2017. Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1–36, 2021. Lunjia Hu, Kevin Perera, and Sebastian Casalaina-Martin. Testing calibration in nearly-linear time. In Advances in Neural Information Processing Systems, volume 37, 2024. Also accepted at STOC 2025. Jannik Kossen, Sebastian Farquhar, Yarin Gal, and Tom Rainforth. Active testing: Sample-efficient model evaluation. In International Conference on Machine Learning. PMLR, 2021. Oleg V Lepski, Arkadi Nemirovski, and Vladimir Spokoiny. On estimation of the Lr norm of a regression function. Probability Theory and Related Fields, 113(2):221–253, 1999. Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al. Holistic evaluation of language models. Transactions on Machine Learning Research, 2023. Michael Nussbaum. Asymptotic equivalence of density estimation and Gaussian white noise. Annals of Statistics, 24(6):2399–2430, 1996. Shubhanshu Shekhar and Aaditya Ramdas. Auditing fairness by betting. Advances in Neural Information Processing Systems, 36, 2024. Shuo Sun, Jiaqi Song, and Alfred O Hero. On the estimation of expected calibration error. In Advances in Neural Information Processing Systems, volume 36, 2023. Spotlight. Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, 2009. Aad W van der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P Xing, et al. Judging LLM-as-a-judge with MT-Bench and chatbot arena. In Advances in Neural Information Processing Systems, volume 36, 2023. 9
Appendix A
Full Proof of Theorem 7 and Corollaries
Theorem 7 (Self-Verification Impossibility). Fix any model with weights θ. The outputs (p(xi ), z(xi )) are deterministic functions of xi and θ; they do not depend on ∆. Construct: ∆0 (p) = 0 for all p (ECE = 0); ∆1 (p) = min(L, 1) near 1 − ε (ECE = min(L, 1)). Both are constant and hence in F(L). Both produce identical observations. Any label-free estimator V returns the same value under both: E[|V −ECE(∆0 )|]+E[|V −ECE(∆1 )|] ≥ |ECE(∆0 )−ECE(∆1 )| = min(L, 1). Taking sup: sup∆ E[|V − ECE|] ≥ min(L, 1)/2. □ Corollary 8 (LLM-as-Judge). Judge J observes only (xi , fS (xi ))—the same label-free observation space. The two worlds (∆0 , ∆1 ) produce identical inputs and outputs for S, hence identical observations for J. The bound follows directly. Corollary 9 (Hallucination Detection). Factual accuracy: Pr[fact correct | confidence p] = η(p). Calibration gap ∆(p) = η(p) − p. Self-consistency generates k responses from (x, θ)—all deterministic functions of the model, independent of ∆. The bound applies. Corollary (Pseudo-Label Circularity). Self-labeling with ŷi = arg max f (xi ) yields ECE = 0 for any deterministic classifier. Corollary (Distribution Shift). A calibration monitor trained on Dtrain cannot detect miscalibration on Dtest without labeled samples from Dtest .
B
Self-Contained Lower Bound via Bernoulli Two-Prior Method
We prove Theorem 2 directly in the Bernoulli observation model, without invoking asymptotic equivalence to Gaussian white noise. Setup. We observe m i.i.d. pairs (pi , Yi ) where pi ∼ µ and Yi | pi ∼ Bern(pi + ∆(pi )), with ∆ ∈ F(L). Step 1: Parametric submodel. Assume µ has density ≥ cµ > 0 on a window W = [1−ε−w/2, 1−ε+w/2]. Partition W into N subintervals IR1 , . . . , IN of width h = w/N . Let g : R → [0, 1] be a smooth bump supported on [0, 1] with g = 1, ∥g∥22 = κg , and Lipschitz PN constant 1. For θ ∈ [−1, 1]N , define: ∆θ (p) = Lh j=1 θj g((p − tj + h/2)/h), where tj are the interval midpoints. Each bump has height Lh, width h, and Lipschitz constant L. Disjoint supports ensure ∆θ ∈ F(L). Step 2: Sufficient statistics. In interval Ij , there are nj ≈ mcµ h observations. The per-bin P calibration gap estimate Zj = n−1 j i:pi ∈Ij (Yi − pi ) satisfies E[Zj ] ≈ Lhθj ḡj and Var(Zj ) ≈ ε/(mcµ h). Setting α = Lhḡj and σ 2 = ε/(mcµ h), the problem reduces to the sequence model Zj ≈ αθj + σξj with approximately independent ξj . Step 3: ECE as L1 functional. The ECE restricted to W is ECEW ≈ cµ w · α · F1 (θ) where PN F1 (θ) = N −1 j=1 |θj |. Lower-bounding F1 estimation suffices. Step 4: Two-prior construction (following Lepski et al., 1999, §4.3). Construct product priors R ⊗N ⊗N N π = ν , π = ν on [−1, 1] where ν − ν = ηµ for a signed measure µ with µ = 0 and 0 1 1 0 0 1 R |t|µ(dt) = 2δ (the separation in L1 norm). Both νj are perturbations of Uniform([−1, 1]) with density 1/2. The per-coordinate KL is KL(pν1 ∥pν0 ) ≤ 4α2 η 2 /σ 2 . Step 5:√Bayesian Le Cam bound. Total KL: KLtotal = 4N α2 η 2 /σ 2 . Setting KL√ total = 1: η = σ/(2α N ). The Bayesian Le Cam bound gives: R∗ ≥ c · δη − N −1/2 = cδσ/(2α N ) − N −1/2 . √ √ Step 6: Optimization over N . Substituting σ/α = εN /(Lw3/2 ḡ mcµ ) and optimizing over N yields N ∗ = Θ((m/ε)1/3 ) and: ∗ RECE ≥ c′
Lε m
1/3
10
′′
/(log m)c
The logarithmic factor arises from the Fourier approximation of |t| in constructing µ, not from the observation model. This is the same factor as in Lepski et al. [Lepski et al., 1999]. □
C
Full Proof of Theorem 12 (Active Verification)
Lower bound. The Le Cam lower bound from Theorem 1 applies unchanged to adaptive strategies. Construct the same two hypotheses: P0 (calibrated, ECE = 0) and P1 (miscalibrated by δ near p = 1 − ε, ECE = δ). Under adaptive querying, the auditor selects pi based on all previous observations (p1 , y1 , . . . , pi−1 , yi−1 ). By the chain rule of KL divergence: KL(P0m ∥P1m ) =
m X
E [KL(P0 (· | pi )∥P1 (· | pi ))]
(1)
i=1
Each term is at most δ 2 /ε (the per-observation KL when pi is in the miscalibrated region, zero otherwise). Adaptivity does not increase the per-observation information: conditioned on pi , the label yi is a single Bernoulli draw whose KL p is δ 2 /ε regardless of previous observations. Therefore 2 ∗ KL ≤ mδ /ε, and Le Cam gives Ractive ≥ c ε/m. Upper bound. We construct a two-phase adaptive strategy. Phase 1 (Exploration): Select N equally-spaced confidence levels {pj = j/N }N j=1 in the interval [1 − ε − w, 1 − ε + w] for a window widthp w = O(1). Query each level m/(2N ) times. The empirical ˆ j ) has standard error σj = 2εN/m. Classify each bin as: estimate ∆(p ˆ j )| > 2σj — the sign of ∆(pj ) is known with high probability. • Resolved: |∆(p ˆ j )| ≤ 2σj — the sign is uncertain. • Unresolved: |∆(p p The unresolved zone has width at most 4σj /L = O( εN/m/L) by the Lipschitz constraint (the function can only stay near zero for a region of width ≤ |∆|max /L). Phase 2 (Exploitation): Use the remaining m/2 queries on resolved bins to estimate |∆(pj )| = ∆(pj )p · sign(∆(pj )) (sign is known, so no absolute value problem). This is a simple average with error ε/m. Total error: p • Resolved bins: estimation error O( ε/m). • Unresolved bins: the contribution to ECE is at most (max |∆| in zone) × (width of zone). Since |∆| ≤ 2σj in the zone and the width is O(σj /L), this contributes O(σj2 /L) = O(εN/(mL)). p p Choose N = L m/ε to balance the two terms. Both become O( ε/m). □
D
Regulatory Infeasibility: Full Derivation
From Theorem 3, verification to accuracy δ requires m ≥ Lε/δ 3 . For K demographic groups with minimum proportion πmin , the effective sample size per group is mπmin . Each group requires Lε Lε/(πmin δ 3 ) total samples. Summing: mtotal ≥ K · πmin δ3 . EU AI Act Annex III (K=10, πmin =0.05, δ=0.02, ε=0.05, L=1): m ≥ 10 · 1 · 0.05/(0.05 · 0.000008) = 1,250,000. Available: ∼707K (CheXpert + MIMIC-CXR + NIH ChestXray14). Gap: 1.8×. FDA SaMD (K=8, πmin =0.05, δ=0.01, ε=0.02): m ≥ 3,200,000. Gap: 4.5×. Under active verification, the requirement drops to Kε/(πmin δ 2 ), making all three frameworks feasible—but requiring infrastructure that does not yet exist. 11
Table 3: Per-subject MMLU rankings for the 20 largest subjects. δfloor is the verification floor; gaps below δfloor are noise (marked ✗). Instability = fraction of 200 bootstraps where ranking changes. Subject Professional Law Moral Scenarios Miscellaneous Professional Psychology High School Psychology High School Macroeconomics Elementary Mathematics Moral Disputes Prehistory Philosophy High School Biology Nutrition Professional Accounting Professional Medicine High School Mathematics Clinical Knowledge Security Studies High School Microeconomics High School World History Conceptual Physics
E
n
L405B
L4-Mav
Q3-80B
Max gap
δfloor
Verif.
Instab.
1534 895 783 612 545 390 378 346 324 311 310 306 282 272 270 265 245 238 237 235
0.72 0.87 0.92 0.87 0.93 0.88 0.79 0.85 0.91 0.86 0.95 0.92 0.74 0.92 0.57 0.90 0.79 0.95 0.92 0.86
0.68 0.47 0.92 0.86 0.92 0.78 0.68 0.86 0.90 0.85 0.80 0.87 0.70 0.88 0.07 0.84 0.81 0.89 0.93 0.64
0.68 0.67 0.94 0.87 0.96 0.89 0.89 0.85 0.92 0.85 0.95 0.88 0.74 0.92 0.65 0.90 0.81 0.95 0.93 0.90
0.040 0.402 0.018 0.005 0.037 0.108 0.214 0.003 0.019 0.016 0.155 0.046 0.046 0.048 0.581 0.060 0.020 0.063 0.008 0.255
0.175 0.179 0.108 0.133 0.104 0.137 0.155 0.137 0.116 0.136 0.121 0.126 0.168 0.118 0.215 0.129 0.151 0.107 0.108 0.152
✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ ✗ ✗ ✓
0.15 0.00 0.44 0.73 0.02 0.27 0.00 0.80 0.46 0.53 0.28 0.43 0.48 0.47 0.00 0.36 0.55 0.10 0.80 0.00
Extended Benchmark Analysis
Leaderboard noise. Across 57 MMLU subjects, we compute pairwise accuracy gaps between 3 models and compare to per-subject verification floors. Results: 37/57 subjects (65%) are completely unranked; 56/57 (98%) have at least one unranked pair; 132/171 pairwise comparisons (77%) fall below the floor. Mean ranking instability under 80%-bootstrap: 29.1%.
F
Extended Empirical Results
Five-benchmark validation. We validate across MMLU (14,042), TruthfulQA (817), ARCChallenge (1,172), HellaSwag (10,042), and WinoGrande (1,267) with 3 models, yielding 14 valid benchmark–model pairs. Figure 6 shows verification floors per benchmark; Figures 7–9 show detailed TruthfulQA analysis. Real 2-stage pipeline. A pipeline of Llama-3.1-405B (stage 1) and Qwen3-Next-80B (stage 2) on MMLU yields L̂sys = 3.05 vs. single-model L̂ = 1.41 (2.16×), confirming that composed systems have higher Lipschitz constants and correspondingly higher verification floors (Figures 10–11). Permutation tests. For the self-evaluation claim (Theorem 7), we supplement Spearman correlations with 10,000-permutation tests under H0 : confidence is independent of calibration gap. Results: MMLU 2/3 models p > 0.10 (non-significant); TruthfulQA 2/3 models p > 0.10. The positive control (confidence vs. accuracy) is significant on both benchmarks (p < 0.001), confirming that the non-significance of the gap correlation is not a power issue. Bootstrap methodology. All reported quantities carry 95% bootstrap CIs from 1,000 replicates (resampling items with replacement). Lipschitz estimates have wide CIs (e.g., Llama-405B: L̂ = 1.41 [1.13, 3.02]) because finite-difference estimation is inherently noisy; ECE and ε CIs are tight (e.g., ECE = 0.118 [0.113, 0.124]).
G
Verification Horizon and Regulatory Tables
H
Full Proof of Theorem 1 (Le Cam Lower Bound)
Construct two hypotheses. Fix a classifier whose score distribution places all mass at p0 = 1 − ε. 12
Verification Floor by Benchmark =0.05 (typical improvement)
Verification floor floor
0.12 0.10 0.08 0.06 0.04 0.02 0.00
mmlu
truthfulqa
arc_challenge
hellaswag
winogrande
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. Table 4: Verification tax across five benchmarks and three models. L̂ is the estimated Lipschitz constant, δfloor is the verification floor, and Self-eval r is the Spearman correlation between confidence and |calibration gap| across bins (non-significant p > 0.05 supports Theorem 7). N
ε
ECE
L̂
δfloor
Self-eval r (p)
14,042 14,042 14,042
0.160 0.273 0.165
0.1183 0.2620 0.1427
1.61 1.00 5.00
0.0264 0.0269 0.0389
+0.35 (p = 0.36) — −0.50 (p = 0.67)
Llama-3.1-405B Llama-4-Maverick Qwen3-Next-80B
817 817 817
0.234 0.656 0.250
0.1947 0.6293 0.2224
2.84 3.36 3.64
0.0933 0.1391 0.1036
−0.43 (p = 0.34) −0.20 (p = 0.80) −0.10 (p = 0.87)
ARC-Challenge ARC-Challenge ARC-Challenge
Llama-3.1-405B Llama-4-Maverick Qwen3-Next-80B
867 1,171 1,172
0.054 0.477 0.039
0.0466 0.4723 0.0382
5.00 1.00 1.00
0.0679 0.0741 0.0322
−0.50 (p = 0.67) — —
HellaSwag HellaSwag HellaSwag
Llama-3.1-405B Llama-4-Maverick Qwen3-Next-80B
1,083 4,625 9,447
0.113 0.168 0.097
0.1299 0.1625 0.0838
1.50 1.00 5.00
0.0538 0.0331 0.0372
−0.92 (p = 0.00) — −0.50 (p = 0.67)
WinoGrande WinoGrande
Llama-4-Maverick Qwen3-Next-80B
701 1,198
1.000 0.208
0.9577 0.1922
1.00 5.00
0.1126 0.0954
+1.00 (p = 0.00) +0.00 (p = 1.00)
Benchmark
Model
MMLU MMLU MMLU
Llama-3.1-405B Llama-4-Maverick Qwen3-Next-80B
TruthfulQA TruthfulQA TruthfulQA
• P0 : Y | p(X) = p0 ∼ Bern(1 − ε). Calibrated: η(p0 ) = p0 , so ECE = 0. • P1 : Y | p(X) = p0 ∼ Bern(1 − ε − δ). Miscalibrated: ECE = δ. Both hypotheses use a constant calibration gap (Lipschitz constant 0), so ∆ ∈ F(L) for all L > 0. The KL divergence of m i.i.d. samples is: KL(P0m ∥P1m ) = m · KL(Bern(1 − ε)∥Bern(1 − ε − δ)) =
mδ 2 mδ 2 ≤ ε(1 − ε) ε
where the last inequality uses 1 − ε ≤ 1 and the KL approximation KL(Bern(p)∥Bern(p + δ)) ≈ δ 2 /(p(1 − p)) (valid for δ ≤ ε/2). By Le Cam’s lemma [Tsybakov, 2009]: R∗ ≥
m m δ δ (1 − TV(P0m , P1m )) ≥ e−KL(P0 ∥P1 ) 2 2
where p the second inequality uses Bretagnolle–Huber. Setting KL = 1 (i.e., δ = p (1/2e) ε/m ≈ 0.184 ε/m. □ 13
p
ε/m): R∗ ≥
1.0
Accuracy / Cal. gap
0.8
TruthfulQA: Self-Eval vs Accuracy and Gap Qwen3-Next-80B acc Qwen3-Next-80B gap Llama-4-Maverick acc Llama-4-Maverick gap
Llama-3.1-405B acc Llama-3.1-405B gap Perfect cal.
0.6 0.4 0.2 0.0 0.2 0.0
0.2
0.4
0.6
Mean confidence
0.8
1.0
Figure 7: TruthfulQA self-evaluation analysis. Confidence tracks accuracy more reliably than calibration gap, consistent with the self-verification impossibility result.
TruthfulQA: Subsampling Convergence Qwen3-Next-80B floor Llama-4-Maverick floor Llama-3.1-405B floor Qwen3-Next-80B Llama-4-Maverick Llama-3.1-405B
|ECE ECE|
10 1
10 2
10 3
102
Sample size m
Figure 8: TruthfulQA subsampling convergence. Estimation error shrinks with sample size but remains bounded below by the benchmark’s verification floor. H.1
Direct Bernoulli Lower Bound (Alternative to Brown–Low)
For readers who prefer a self-contained argument avoiding asymptotic equivalence, we sketch a direct Assouad-type lower bound in the Bernoulli model. Partition [0, 1] into B equal-width bins. Consider the class of calibration functions ∆ω (p) = h · ωb for p ∈ Ib , where ω = (ω1 , . . . , ωB ) ∈ {−1, +1}B and h >P 0 is chosen so that ∆ω is L-Lipschitz (requiring h ≤ L/(2B)). Each ∆ω has ECE = h (since b (1/B)|h · ωb | = h). For any two configurations ω, ω ′ differing in one coordinate b, the KL divergence of the m/B observations in bin b is: m (2h)2 4mh2 KL = · ≤ B ε(1 − ε) Bε 14
TruthfulQA: Phase Transition 1.0
Detection power
0.8 0.6 0.4 0.2
Qwen3-Next-80B Llama-4-Maverick Llama-3.1-405B m = 1 (theory)
0.0 101
100
102
m
Figure 9: TruthfulQA phase transition. Detection power rises sharply once m · ε clears the theoretical transition scale.
Pipeline vs. Single-Model Error 2-stage pipeline Single model (405B)
Mean |ECE ECEtrue|
10 1
10 2
10 3
102
103
Sample size m
104
Figure 10: Real 2-stage pipeline verification error. The pipeline has consistently higher estimation error than the single model across sample sizes.
By Assouad’s lemma [Tsybakov, 2009], the minimax risk satisfies: ! r Bh 2mh2 ∗ R ≥ 1− 2 Bε Setting h = c
p
Bε/m for a small constant c and B = ⌊(Lm/ε)1/3 ⌋ gives: R∗ ≥ c′
15
Lε m
1/3
System Lipschitz: Single vs. Pipeline 3.0
L (Lipschitz constant)
2.5 2.0
2.2×
1.5 1.0 0.5 0.0
2-stage pipeline
Single model (Llama-405B)
Figure 11: Real 2-stage pipeline Lipschitz comparison. The estimated system Lipschitz constant is 2.16× the single-model value, explaining the larger verification tax. Table 5: Real-model verification audit. L̂ via finite differences; 95% bootstrap CIs in brackets (MMLU). Model
m
ε
MMLU (14,042 items per model) Qwen3-Next-80B 14,042 .165 [.158,.171] Llama-4-Maverick 14,042 .273 [.266,.280] Llama-3.1-405B 14,042 .160 [.154,.166] TruthfulQA (817 items per model) Qwen3-Next-80B 817 Llama-4-Maverick 817 Llama-3.1-405B 817
L̂
ECE
δfloor
2.45 [1.70,4.85] 2.01 [1.42,4.75] 1.41 [1.13,3.02]
.143 [.137,.149] .262 [.255,.270] .118 [.113,.124]
.031 [.027,.038] .034 [.030,.045] .025 [.023,.032]
3.64 3.36 2.84
.222 .629 .192
.104 .139 .093
.250 .656 .234
This recovers the (Lε/m)1/3 rate directly from the Bernoulli model, confirming the Brown–Low reduction. The constant c′ is weaker than the one obtained via Lepski et al. [1999], but the argument is fully self-contained. □
I
Full Proof of Theorem 3 (Matched Upper Bound)
Bias-variance decomposition. With B equal-width bins and m total samples: 1. Bias. Within each bin of width 1/B, the calibration gap ∆ varies by at most L/B (Lipschitz). By the Bridge Lemma, |ECEB − CEsmooth | ≤ L/B. 2. Variance. Each bin b has nb ≈ m/B samples. (Under bounded density cµ ≤ dµ/dp ≤ Cµ ; equal-mass binning achieves nb = m/B exactly when µ concentrates.) The empirical calibration ˆ b ) ≤ σ 2 /nb ≈ σ 2 B/m, where σ 2 = maxb E[η(p)(1 − η(p)) | p ∈ Ib ]. gap has variance Var(∆ p [ B − ECEB |] ≤ σ 2 B/m. Estimation error: E[|ECE p 3. Total error. L/B + σ 2 B/m. 16
Table 6: Verification horizon N ∗ for frontier models across domains. Gap = N/N ∗ ; values > 1 indicate the model exceeds the horizon. N
∗ Npass
∗ Nact
Gap
Exceeds
General NLP (MMLU-scale) Medical imaging Legal Financial Code (HumanEval-scale) Autonomous driving
1.80e + 12 1.80e + 12 1.80e + 12 1.80e + 12 1.80e + 12 1.80e + 12
1.40e + 4 5.00e + 5 1.00e + 4 2.00e + 4 5.00e + 3 1.00e + 5
1.96e + 8 2.50e + 11 1.00e + 8 4.00e + 8 2.50e + 7 1.00e + 10
128571428.57 3600000.00 180000000.00 90000000.00 360000000.00 18000000.00
✓ ✓ ✓ ✓ ✓ ✓
GPT-4o GPT-4o GPT-4o GPT-4o GPT-4o GPT-4o
General NLP (MMLU-scale) Medical imaging Legal Financial Code (HumanEval-scale) Autonomous driving
2.00e + 11 2.00e + 11 2.00e + 11 2.00e + 11 2.00e + 11 2.00e + 11
1.40e + 4 5.00e + 5 1.00e + 4 2.00e + 4 5.00e + 3 1.00e + 5
1.96e + 8 2.50e + 11 1.00e + 8 4.00e + 8 2.50e + 7 1.00e + 10
14285714.29 400000.00 20000000.00 10000000.00 40000000.00 2000000.00
✓ ✓ ✓ ✓ ✓ ✓
Claude 3 Opus Claude 3 Opus Claude 3 Opus Claude 3 Opus Claude 3 Opus Claude 3 Opus
General NLP (MMLU-scale) Medical imaging Legal Financial Code (HumanEval-scale) Autonomous driving
1.75e + 11 1.75e + 11 1.75e + 11 1.75e + 11 1.75e + 11 1.75e + 11
1.40e + 4 5.00e + 5 1.00e + 4 2.00e + 4 5.00e + 3 1.00e + 5
1.96e + 8 2.50e + 11 1.00e + 8 4.00e + 8 2.50e + 7 1.00e + 10
12500000.00 350000.00 17500000.00 8750000.00 35000000.00 1750000.00
✓ ✓ ✓ ✓ ✓ ✓
Claude 3.5 Sonnet Claude 3.5 Sonnet Claude 3.5 Sonnet Claude 3.5 Sonnet Claude 3.5 Sonnet Claude 3.5 Sonnet
General NLP (MMLU-scale) Medical imaging Legal Financial Code (HumanEval-scale) Autonomous driving
7.00e + 10 7.00e + 10 7.00e + 10 7.00e + 10 7.00e + 10 7.00e + 10
1.40e + 4 5.00e + 5 1.00e + 4 2.00e + 4 5.00e + 3 1.00e + 5
1.96e + 8 2.50e + 11 1.00e + 8 4.00e + 8 2.50e + 7 1.00e + 10
5000000.00 140000.00 7000000.00 3500000.00 14000000.00 700000.00
✓ ✓ ✓ ✓ ✓ ✓
Gemini 1.5 Pro Gemini 1.5 Pro Gemini 1.5 Pro Gemini 1.5 Pro Gemini 1.5 Pro Gemini 1.5 Pro
General NLP (MMLU-scale) Medical imaging Legal Financial Code (HumanEval-scale) Autonomous driving
5.40e + 11 5.40e + 11 5.40e + 11 5.40e + 11 5.40e + 11 5.40e + 11
1.40e + 4 5.00e + 5 1.00e + 4 2.00e + 4 5.00e + 3 1.00e + 5
1.96e + 8 2.50e + 11 1.00e + 8 4.00e + 8 2.50e + 7 1.00e + 10
38571428.57 1080000.00 54000000.00 27000000.00 108000000.00 5400000.00
✓ ✓ ✓ ✓ ✓ ✓
Llama-3-405B Llama-3-405B Llama-3-405B Llama-3-405B Llama-3-405B Llama-3-405B
General NLP (MMLU-scale) Medical imaging Legal Financial Code (HumanEval-scale) Autonomous driving
4.05e + 11 4.05e + 11 4.05e + 11 4.05e + 11 4.05e + 11 4.05e + 11
1.40e + 4 5.00e + 5 1.00e + 4 2.00e + 4 5.00e + 3 1.00e + 5
1.96e + 8 2.50e + 11 1.00e + 8 4.00e + 8 2.50e + 7 1.00e + 10
28928571.43 810000.00 40500000.00 20250000.00 81000000.00 4050000.00
✓ ✓ ✓ ✓ ✓ ✓
Llama-4-Maverick Llama-4-Maverick Llama-4-Maverick Llama-4-Maverick Llama-4-Maverick Llama-4-Maverick
General NLP (MMLU-scale) Medical imaging Legal Financial Code (HumanEval-scale) Autonomous driving
1.70e + 10 1.70e + 10 1.70e + 10 1.70e + 10 1.70e + 10 1.70e + 10
1.40e + 4 5.00e + 5 1.00e + 4 2.00e + 4 5.00e + 3 1.00e + 5
1.96e + 8 2.50e + 11 1.00e + 8 4.00e + 8 2.50e + 7 1.00e + 10
1214285.71 34000.00 1700000.00 850000.00 3400000.00 170000.00
✓ ✓ ✓ ✓ ✓ ✓
Qwen3-Next-80B Qwen3-Next-80B Qwen3-Next-80B Qwen3-Next-80B Qwen3-Next-80B Qwen3-Next-80B
General NLP (MMLU-scale) Medical imaging Legal Financial Code (HumanEval-scale) Autonomous driving
8.00e + 10 8.00e + 10 8.00e + 10 8.00e + 10 8.00e + 10 8.00e + 10
1.40e + 4 5.00e + 5 1.00e + 4 2.00e + 4 5.00e + 3 1.00e + 5
1.96e + 8 2.50e + 11 1.00e + 8 4.00e + 8 2.50e + 7 1.00e + 10
5714285.71 160000.00 8000000.00 4000000.00 16000000.00 800000.00
✓ ✓ ✓ ✓ ✓ ✓
Model
Domain
GPT-4 GPT-4 GPT-4 GPT-4 GPT-4 GPT-4
17
Table 7: Data requirements for regulatory compliance verification. Gap = mreq /mavail ; values > 1 indicate infeasibility with current data. Framework EU AI Act Annex III NIST AI RMF FDA SaMD
K 10 5 8
πmin 0.05 0.10 0.05
δ 0.020 0.010 0.010
ε
mreq
0.050 0.030 0.020
mactive 6
1.25 × 10 1.50 × 106 3.20 × 106
mavail 4
2.50 × 10 1.50 × 104 3.20 × 104
Gap 5
7.07 × 10 5.00 × 105 7.07 × 105
1.8× 3.0× 4.5×
p 4. Optimization. Setting L/B = σ 2 B/m: B ∗ = (L2 m/σ 2 )1/3 , total error (Lσ 2 /m)1/3 . In the rare-error regime σ 2 ≈ ε, recovering the headline rate. □
J
Verification Dynamics, Recalibration Trap, and Half-Life
J.1
Verification Dynamics
Suppose a model is deployed at rate r samples per unit time and ε(t) = c0 t−β . The verification floor at time t is δfloor (t) = (Lc0 /r)1/3 t−(β+1)/3 . Meaningful verification (δfloor (t) < ε(t)) reduces to (L/(rc20 ))1/3 < t(1−2β)/3 . This is satisfied for large t when β < 1/2, violated when β > 1/2, ∗ and equivalent to L/(rc20 ) < 1 when β = 1/2. Critical exponent: β ∗ = 1/2 (passive), βactive =1 (active). □ J.2
Recalibration Trap
With ECEK = γ K ECE0 , the improvement from round K to K + 1 is γ K ECE0 (1 − γ). Distinguishing requires (Theorem 1) mK ≥ ε/(γ 2K ECE20 (1 − γ)2 ). Setting mK = Mtotal gives K ∗ = ⌊log(Mtotal (1 − γ)2 ECE20 /ε)/(2 log(1/γ))⌋. Worked example (MMLU). γ = 0.5, ε = 0.05, ECE0 = 0.10, Mtotal = 14,000: K ∗ = ⌊6.55/1.386⌋ = 4. After 4 halving rounds, MMLU cannot verify further improvement. J.3
Verification Half-Life
Let ECE drift rate λ satisfy |ECE(t) − ECE(0)| ≤ λt. (i) The verification becomes invalid after t1/2 = δ/λ. (ii) Perpetual verification requires data rate r ≥ Lελ/δ 4 . Domain estimates (assuming L = 1, ε = 0.05): Medical AI (λ = 0.01/month, δ = 0.02): t1/2 = 2 months, r ≈ 3,100/month. Content moderation: 6 months, 620/month. Financial trading (λ = 0.1/week, δ = 0.01): t1/2 = 17 hours. Autonomous driving: 15 days. Static benchmarks have the same half-life: a benchmark constructed at t = 0 decays at rate λ, formalizing the case for periodic refresh.
K
Alternative Derivation of Theorem 2 via Asymptotic Equivalence
Step 1: Reduction to nonparametric regression. Within a window of width w around p = 1 − ε, where the score distribution concentrates, the calibration verification problem reduces to estimating the L1 norm of a regression function. Specifically: For p ∈ [1 − ε − w/2, 1 − ε + w/2], define ∆(p) = η(p) − p. The labels Yi given p(Xi ) = p are Bern(η(p)) = Bern(p + ∆(p)), with variance η(p)(1 − η(p)) ≈ ε in the rare-error regime. The ECE restricted to this window is: Z 1−ε+w/2 |∆(p)| dµ(p)
ECEwindow = 1−ε−w/2
This is precisely the L1 norm of ∆ on the window, weighted by µ. Step 2: Identification with L1 functional estimation in white noise. 18
(2)
By the asymptotic equivalence of nonparametric regression and Gaussian white noise [Brown and R Low, 1996, Nussbaum, 1996], estimating |∆(p)|dp R from m observations with per-observation variance ε is asymptotically equivalent to estimating |f (t)|dt in the white noise model: dX(t) = f (t)dt + (m/ε)−1/2 dW (t),
t ∈ [0, 1]
(3)
with effective sample size neff = m/ε and f ∈ Σ(β = 1, L) (Lipschitz = Hölder with β = 1). Step 3: Application of Lepski, Nemirovski & Spokoiny (1999). By Theorem 2.2 of Lepski et al. [1999], the minimax rate for estimating the L1 norm of a β-Hölder function in white noise with sample size n is: ′
∗ ≥ c · n−β/(2β+1) /(log n)c RL 1
(4)
For β = 1 (Lipschitz) and n = neff = m/ε: ′
∗ RL ≥ c · (m/ε)−1/3 /(log(m/ε))c = c · 1
ε 1/3
′
/(log m)c
m Incorporating the Lipschitz constant L (which scales the function class): 1/3 Lε R∗ (m, ε, L) ≥ c2 /(log m)c3 m
(5)
(6)
Technical conditions: • Score-mass concentration: The score distribution µ must place mass ≥ ρ in a window of width w around 1 − ε. We state this as an assumption. This holds for well-trained classifiers: overconfident models concentrate predictions near the top. • The Brown–Low equivalence requires m sufficiently large relative to the smoothness. The minimum m is m ≥ C(L)/ε for a constant depending on L. • Lipschitz constant: Since ∆(p) = η(p) − p and p 7→ p is 1-Lipschitz, we have L∆ ≤ Lη + 1. We use L throughout for L∆ . Clarification on the asymptotic regime. The Brown–Low equivalence is applied in the limit m → ∞ with ε fixed. The error rate ε is a property of the model under audit, not an asymptotic parameter. For any fixed ε ∈ (0, 1/2), the Bernoulli label variance ε(1 − ε) ≥ ε/2 > 0 is bounded away from zero, satisfying the regularity conditions. The ε-dependence in the rate (Lε/m)1/3 arises from substituting σ 2 = ε(1 − ε) ≈ ε into the white-noise minimax rate with neff = m/ε, not from taking ε → 0 within the equivalence framework.
L
Supplementary Details for Theorem 11
The proof of Theorem 11 in the main text is complete. We note that the result extends straightforwardly to any side information S that is independent of the fresh evaluation labels conditional on the scores. This includes: model weights, architecture specifications, training data, training logs, gradient histories, and any derived quantity (e.g., Fisher information matrices, Hessian spectra, pruning masks). The key insight is that calibration is a property of the model-world interface, not of the model alone.
M
Full Proof of Sequential Verification
Lower bound. Under the two Le Cam hypotheses (P0 : ECE = 0, P1 : ECE = δ), the log-likelihood ratio after t observations is: t X p1 (yi | pi ) Λt = log (7) p0 (yi | pi ) i=1 This is a random walk with per-step drift: EP0 [Λ1 ] = −KL(P0 (· | pi )∥P1 (· | pi )) ≈ − 19
δ2 ε
(8)
By Wald’s identity for sequential testing [Tsybakov, 2009], any test between P0 and P1 with error probabilities ≤ α satisfies: log(1/α) ε log(1/α) E[τ ] ≥ (9) = KL(P0 ∥P1 ) δ2 Since any sequential verification protocol with accuracy δ at confidence 1 − α must distinguish ECE = 0 from ECE = δ with probability ≥ 1 − α, the lower bound follows. Upper bound. We construct a confidence sequence for the ECE using the method of mixtures [Howard et al., 2021]. Define the running ECE estimate: [t = ECE
B X nb,t b=1
t
ˆ b,t ∆
(10)
ˆ b,t is the empirical calibration gap in bin b after t observations. where ∆ By Theorem 1 of Howard et al. [2021], there exists a time-uniform confidence sequence (Ct )t≥1 such that: [ t − ECE| > Ct ≤ α Pr ∃t ≥ 1 : |ECE (11) p with Ct = O( ε log(log(t)/α)/t). Define the stopping time τ = inf{t : Ct ≤ δ}. Solving Ct ≤ δ: r ε log(log(t)/α) ε log(log(t)/α) ≤ δ =⇒ t ≥ t δ2
(12)
For the dominant term, E[τ ] = O(ε log(1/α)/δ 2 ), matching the lower bound up to constants. □
N
Temperature Scaling Analysis
We provide the full proof of the temperature scaling rate proposition. Step 1: MLE for the temperature parameter. Given scores p1 , . . . , pm and labels y1 , . . . , ym , the negative log-likelihood is: ℓ(T ) = −
m X
[yi log σ(logit(pi )/T ) + (1 − yi ) log(1 − σ(logit(pi )/T ))]
(13)
i=1
This is a 1D convex optimization. The MLE T̂ is unique. Step 2: Asymptotic normality of MLE. By standard M-estimation theory [van der Vaart, 1998]: √ d m(T̂ − T ∗ ) − → N (0, I(T ∗ )−1 ) (14) where I(T ∗ ) is the Fisher information. At T ∗ = 1, the score function is: ∂ log p(Y | p, T ) = −(Y − p) · logit(p) ∂T T =1
(15)
So:
I(1) = E[(Y − p)2 · logit(p)2 ] = E[p(1 − p) · logit(p)2 ] (16) In the rare-error regime with scores concentrated near 1−ε: logit(1−ε) ≈ log(1/ε) and p(1−p) ≈ ε, giving: I(1) ≈ ε · log2 (1/ε) (17) This is positive and grows as ε → 0 — rare errors make temperature estimation easier because logits p are more spread out. The MLE satisfies: |T̂ − T ∗ | = Op (1/ m · I(T ∗ )). Step 3: Translating to calibration error. By Taylor expansion of ∆(p; T ) around T ∗ = 1: ∆(p; T̂ ) ≈
∂∆ · (T̂ − 1) = p(1 − p) · logit(p) · (T̂ − 1) ∂T T =1 20
(18)
So the smooth CE is: Z CEsmooth =
Z |∆(p; T̂ )| dµ(p) ≈ |T̂ − 1| · |
p(1 − p)|logit(p)| dµ(p) {z }
(19)
κ
p where κ is a constant depending on the score distribution. Substituting |T̂ −1| = Op (1/ m · I(T ∗ )): ! 1 κ = Op √ CEsmooth = Op p (20) m m · I(T ∗ ) with a constant that depends on ε through I(T ∗ ) and κ. This is the parametric rate m−1/2 , not the nonparametric rate (Lε/m)1/3 . Step 4: Connection to binned ECE. Via the Bridge Lemma: ECEB ≤ CEsmooth + L/B. Taking √ B = O( m/L): √ ECEB = O(1/ m) (21) √ Comparison to nonparametric rate: The ratio is (1/ m)/(Lε/m)1/3 = (Lε)−1/3 /m1/6 , which shrinks with m. For m = 10,000 and Lε = 0.05: ratio ≈ 0.05. Temperature scaling is ∼20× more data-efficient than nonparametric ECE estimation. □
O
Verification Transfer Details
We provide the full proof of the verification transfer proposition. Step 1: Problem reduction. Since ∆1 (p) is known (from prior verification), estimating ECE(M 2) = R R |∆2 (p)| dµ(p) reduces to estimating the shift h(p) = ∆2 (p) − ∆1 (p), then computing |∆1 (p) + ĥ(p)| dµ(p). Step 2: Lower bound (detection cost). Two-sample Le Cam between H0 : ∆2 = ∆1 and H1 : ∆2 = ∆1 + h with ∥h∥∞ = δft . From m2 fresh samples near p ≈ 1 − ε2 : KL(H0m2 ∥H1m2 ) ≈
2 m2 δft ε2
(22)
2 Indistinguishable when KL ≤ 1, requiring m2 = Ω(ε2 /δft ).
Step 3: Upper bound (estimation with transfer).p Apply Theorem 3 to h instead of ∆2 . The histogram estimator for h has bias Lh /B and variance ε2 B/m2 . Optimizing: B ∗ = (L2h m2 /ε2 )1/3 , giving: 1/3 ! Lh ε2 ∥ĥ − h∥ = O (23) m2 By the triangle inequality:
Z [ 2) ≤ ECE(M2 ) − ECE(M
|ĥ(p) − h(p)| dµ(p) = O
Lh ε2 m2
1/3 ! (24)
3 Setting this equal to δft : m2 = O(Lh ε2 /δft ).
Step 4: When does transfer help? From-scratch: m2 = Θ(Lε2 /δ 3 ). With transfer: m2 = 3 Θ(Lh ε2 /δft ). Transfer helps when δft < δ and Lh ≤ L. With δft = δ/10, saving is 1000×. Transfer provides no benefit when δft ≥ δ. □
P
Corrections: Correlation, Heterogeneity, Pre-Calibration
The core theorems assume i.i.d. labeled samples with independent Bernoulli noise. In practice, several deviations may arise. 21
Temporal correlation. If evaluation samples arrive sequentially and exhibit temporal dependence, the effective sample size is reduced by a factor depending on the mixing time. For β-mixing sequences with coefficient β(k) ≤ c · ρk , the effective sample size is meff ≈ m · (1 − ρ). All bounds apply with m replaced by meff . Domain heterogeneity. When the evaluation set spans multiple domains with different error rates, the per-domain verification floor (Fix 3) accounts for this heterogeneity. The overall ECE is a weighted average of domain-specific ECEs, and Jensen’s inequality ensures the overall verification floor is no larger than the worst per-domain floor weighted by domain proportion. Pre-calibration via RLHF. Models that have undergone reinforcement learning from human feedback may have artificially smooth calibration functions (small L), which reduces the verification tax. However, if the RLHF procedure oversmooths, the remaining miscalibration may be concentrated at specific confidence levels, violating the uniform Lipschitz assumption. Domain-specific Lipschitz estimates should be used in such cases.
Q
Numerical Sanity Checks
Q.1
Sharp Le Cam Constants
For each ε, we numerically optimize the Le Cam lower bound over the separation parameter δ, using the exact Bernoulli KL divergence (not the quadratic approximation). We compute three versions: the p Bretagnolle–Huber bound R∗ ≥ (δ/2) exp(−KL), the Pinsker bound R∗ ≥ (δ/2)(1 − KL/2), and the exact bound via the Bernoulli likelihood ratio test. Table 8 reports the tightest constant for each ε. Table 8: Sharp Le Cam constants c1 (ε) and nonparametric estimation sample sizes. The Le Cam constant governs detection; the estimation column uses m ≥ Lε/δ 3 with L = 1, δ = 0.01. ε
c1 (ε)
mdetect (Le Cam)
mestimate (nonparametric)
0.01 0.02 0.05 0.10 0.15 0.20 0.25 0.30 0.35
0.3780 0.3638 0.3474 0.3326 0.3206 0.3093 0.2982 0.2873 0.2759
15 27 61 111 155 192 223 248 267
10,000 20,000 50,000 100,000 150,000 200,000 250,000 300,000 350,000
The constant c1 (ε) is monotonically decreasing in ε: smaller error rates yield tighter constants because the Bernoulli variance is smaller and the KL approximation is sharper. All values fall in [0.28, 0.38], consistent with the theoretical prediction c1 ≥ 1/(2e) ≈ 0.184 from the quadratic KL approximation. The exact constants are roughly 2× larger, reflecting the tightness gained from exact Bernoulli KL computation.
R
Synthetic Experiments
Setup. Calibration gap ∆(p) = A sin(2πkp) with L = 2πkA. Scores from Beta((1−ε)/ε, 1). Labels Y ∼ Bern(p + ∆(p)). Optimal B ∗ . Results. (1) Phase transition validates at mε ≈ 1 (Fig. 2). (2) Passive slope converges to −1/3 as k increases (zero-crossings drive worst-case). (3) Active-passive gap widens with L. 22
Convergence Rate vs Number of Zero-Crossings ( = 0.10) 1.25
log10 (mean |ECE ECE|)
1.50 1.75 2.00 2.25 2.50 2.75 3.00
k = 1 (slope=-0.45) k = 4 (slope=-0.50) k = 8 (slope=-0.48) k = 16 (slope=-0.47) k = 32 (slope=-0.44) k = 64 (slope=-0.39) Theory: 1/3
2.5
3.0
3.5
log10 (m)
4.0
4.5
Figure 12: Synthetic slope study: estimation error versus sample size for increasing numbers of zero-crossings.
S
Real-Model Experiment Details
MMLU experimental protocol. We query each NIM-hosted model with the standard 4-way multiple-choice prompt (“Answer the following multiple choice question. Reply with ONLY the letter (A, B, C, or D)”). For each question, we extract the logprobs of the four answer tokens A, B, C, D at the first generated position, apply softmax over those four logits, and take the maximum as the model’s confidence. The model’s predicted answer is the argmax. Records with API errors (e.g., 403 Forbidden, content-filter rejection) are excluded. Each model run uses a single deterministic temperature-0 generation per question. Confidence saturation (full data, N = 14,042 each). On the complete MMLU set, max-softmax confidence is heavily concentrated near 1: Llama-3.1-405B has mean confidence 0.96 with 77% of questions saturated (> 0.99); Qwen3-Next-80B has mean 0.98 with 86% saturated; Llama-4Maverick-17B has mean 0.99 with 92% saturated. The 405B model has the most spread (lowest saturation rate), as expected for a larger and more capable model. Saturation affects the resolution of high-confidence bins but not the convergence rate, which is governed by the optimal bin count B ∗ . Lipschitz constant estimation. For each model, we partition the score range into 20 equal-width bins, compute the empirical accuracy in each bin with at least 30 samples, take the calibration gap ˆ b = accb − pb at each bin center, and form the adjacent-bin slope |∆ ˆ b+1 − ∆ ˆ b |/|pb+1 − pb |. We ∆ report the 75th percentile of these slopes, capped at L̂ = 5, as a robust estimate. This is sensitive to bin choice and noise; we recommend the audit floor be reported with L̂ from at least two binning resolutions. Pseudo-classifier control experiment. As a sanity check before running the real-model experiment, we constructed a 10-class softmax classifier from Gaussian logits with ε ≈ 0.10 (N = 20,000, fulldataset ECE ≈ 0.31). Subsampling at m ∈ {50, . . . , 104 } with optimal B ∗ bins (200 replicates per m) confirms that (i) the verification floor (red dashed in Figure 14) tracks the empirical std of 23
Slope Convergence to Minimax as k 0.350
Fitted slope
0.375 0.400
Empirical slopes Minimax theory: 1/3 Parametric rate: 1/2
0.425 0.450 0.475 0.500 100
101
Number of zero-crossings k
Figure 13: Synthetic slope convergence to the minimax −1/3 rate as zero-crossings increase. estimates across the full range, and (ii) the phase transition near m · ε ≈ 1 is visible (Figure 15). The pseudo-classifier results match the MMLU real-model findings of Section 8. S.1
Named Model Comparisons
Full methodology: pairwise accuracy gaps between 10 frontier models on 4 benchmarks using p published scores from technical reports and model cards. Verification floor: δacc = 2 ε(1 − ε)/n. The main-text Table 4 shows the top comparisons; full data (64 pairs) is in the supplementary materials.
T
Full Proof of Theorem 13 (Compositional Verification)
Lipschitz composition. By the chain rule, if gk is Lk -Lipschitz in its first argument, then gK ◦ · · · ◦ g1 QK Q is ( k=1 Lk )-Lipschitz. Since ∆sys (p) = ηsys (p) − p and p 7→ p is 1-Lipschitz, Lsys ≤ k Lk + 1. Verification cost. Applying Theorem 3 with L = Lsys : msys = Θ(Lsys ε/δ 3 ). For homogeneous Lk = L: Lsys ≈ LK , giving exponential scaling. □ Agent loop bound. For an agent with K reasoning iterations and L = 2: L10 = 1024, L20 > 106 . Caveats. The Lipschitz composition model is optimistic in two directions: discontinuous components (e.g., discrete retrieval) yield Lk = ∞, making end-to-end verification impossible at any sample size; conversely, contractive components (Lk < 1) reduce the effective Lsys . Empirical estimation of Lsys via finite-difference approximation is recommended before applying the exponential bound. Independence of per-component calibration gaps is also assumed; correlated miscalibration can either help or hurt depending on structure. Worked example. A two-stage retriever–classifier with L = 2 each gives Lsys ≤ 5, requiring 5× the data of a single classifier. With L = 3: 10×. A three-stage pipeline at L = 2: 9×; at L = 3: 28×.
24
End-to-End Verification: Pseudo-Classifier (
0.10)
0.35 0.30
ECE
0.25 Verification floor (L /m)1/3 True ECE (0.310) ECE estimate (mean ± std)
0.20 0.15 0.10 0.05 102
104
103
Sample size m
Figure 14: Pseudo-classifier control: ECE estimate ± std versus m, with the verification floor overlaid.
Real-Model Phase Transition: ECE Detection 1.0
Detection power
0.8 0.6 0.4 0.2
m =1
0.0 100
101
Normalized sample size m
102
103
Figure 15: Pseudo-classifier control: detection power versus m · ε, with the predicted phase transition at m · ε = 1.
25