Experts Don't Cheat: Learning What You Don't Know By Predicting Pairs

ArXiv: 2402.08733

🎯 Pitch

A model trained to predict pairs of answers can reveal its own ignorance by how much it “cheats” when given one answer to guess the other—a behavior proven to be the exact measure of missing knowledge. This trick yields provably correct epistemic uncertainty estimates even for underfitted models, dramatically improving over all baselines.

---

1. Executive Summary

This paper introduces a general strategy for teaching generative models to estimate the gaps between their own predictions and the true conditional distribution they aim to approximate, without requiring distributional assumptions about that process. Using CIFAR-10H perceptual uncertainty data, a synthetic digits-of-π language modeling task, and a Frozen Lake gridworld, the authors propose training models to predict pairs of independent responses drawn from the true conditional, then allowing the model to “cheat” by observing one response while predicting the other—the amount of cheating quantifies epistemic uncertainty via a cheat-corrected epistemic variance metric (operationalized as the ratio of marginal to self-conditioned probabilities, $C_\text{Cheat}^\theta(y|x)$). The paper proves that this cheating behavior is equivalent to second-order calibration, a principled extension of ordinary calibration requiring models to report the covariance of the true probabilities around their predictions, and demonstrates that cheat-corrected estimates achieve substantially better second-order calibration than ensemble, SNGP, or evidential deep learning baselines—for instance, reducing expected second-order calibration error (ECE-2) from 0.048–0.521 to 0.009–0.022 on CIFAR-10H variants—establishing that accurate epistemic uncertainty quantification is achievable with only paired training data, even when the model underfits the true process.

2. Context and Motivation

The Core Problem: Generative Models Cannot Tell You What They Don't Know

When a generative model $p^\theta_{Y|X}$—such as a large language model or an image classifier trained on human annotations—is trained to imitate a stochastic real-world process $p_{Y|X}$, a fundamental question arises: how close is the model's predicted distribution to the true conditional distribution for a given input? This is not the same as asking how confident the model is in its prediction. A model can be highly confident ($p^\theta_{Y|X}(y|x)$ is close to 1) while being catastrophically wrong about the true probability $p_{Y|X}(y|x)$. Conversely, a well-calibrated model can report low probabilities for many outputs—not because it lacks knowledge, but because the true process is inherently stochastic.

The paper identifies this as a decomposition problem: the model's uncertainty about $Y$ given $X$ comes from two fundamentally different sources that are confounded in any single probability estimate $p^\theta_{Y|X}(y|x)$:

1. Aleatoric uncertainty: the irreducible noise intrinsic to the process itself. If the true conditional $p_{Y|X}$ assigns probability 0.3 to "The digit is 7" and 0.7 to "The digit is 4" for a given query about $\pi$, a perfectly knowledgeable model should report low probability for any single answer—this reflects the randomness in the world, not the model's ignorance.

2. Epistemic uncertainty: the model's lack of knowledge about $p_{Y|X}$, arising from limited capacity, insufficient data, or misspecification. If the model's predicted distribution $p^\theta_{Y|X}(\cdot|x)$ differs from $p_{Y|X}(\cdot|x)$ because it hasn't learned the correct mapping from inputs to outcome probabilities, this gap represents genuine ignorance that could lead to hallucinations or unsafe decisions.

The critical insight the paper opens with (Section 1) is that the probability value $p^\theta_{Y|X}(y|x)$ alone cannot distinguish between these two cases. As the authors state:

"If we want to determine whether our model knows enough about $p_{Y|X}$ for us to trust its responses, we cannot rely on the value of $p^\theta_{Y|X}(y|x)$ alone, since it may just be small because $p_{Y|X}(y|x)$ was small."

This is not merely a theoretical curiosity. The practical consequences are severe and well-documented in the literature the paper cites (Section 1):

• Hallucination in language models (Ji et al., 2022; Kalai & Vempala, 2023): models confidently generate false statements because they cannot recognize when their training data didn't cover the relevant facts. A model queried about digit 5641 of $\pi$ might not know the answer, but has no mechanism to signal this ignorance versus the inherent randomness of valid stylistic variation in responses.

• Unjustified decisions under distribution shift (Hébert-Johnson et al., 2018): models trained on one population make confident but incorrect predictions on subpopulations they don't represent well, without any warning that their uncertainty estimates are unreliable.

• "Self-delusions" in sequential decision making (Ortega et al., 2021): agents trained via imitation learning conflate correlation with causation when they can't observe all relevant variables, confidently taking actions that appear safe in training but are actually dangerous when unobserved confounders vary.

The paper frames these failures as instances of a single underlying deficit: models lack the ability to estimate their own approximation error—the gap between $p^\theta_{Y|X}$ and $p_{Y|X}$—in a way that separates epistemic from aleatoric uncertainty.

Why Existing Approaches Fail: The Calibration Paradox and the Misspecification Trap

The paper identifies two broad categories of existing approaches and explains why neither solves the problem.

The Calibration-Only Approach

A natural first attempt is to require the model to be first-order calibrated (Definition 2.1): the predicted probability $p^\theta_{Y|X}(y|x)$ should equal the true conditional probability $p_{Y|X}(y|x)$ on average over all inputs $x$ that receive the same prediction. This is the standard definition of calibration studied extensively in the literature (Guo et al., 2017; Kumar et al., 2019; Vaicenavicius et al., 2019).

The paper makes a crucial observation that is often underappreciated: a perfectly calibrated model can still be arbitrarily far from $p_{Y|X}$ for individual inputs. This follows directly from the definition: calibration only requires that $p^\theta_{Y|X}(\cdot|x)$ equals the average of the true distribution $p_{Y|X}$ across all inputs in the same equivalence class under the model's grouping function $\Phi$:

$p^\theta_{Y|X}(y|x) = \mathbb{E}[p_{Y|X}(y|X) \mid X \in [x]_\Phi]$

The paper illustrates this with a coin-flip example (Section 2.1): a calibrated predictor that outputs $p^\theta(\text{Heads}|x) = 50\%$ could be perfectly knowledgeable (it knows coin $x$ is fair) or completely ignorant (it can't distinguish coin $x^+$ with bias 0.9 from coin $x^-$ with bias 0.1, and averages across them). Both predictors are equally well-calibrated, but one is optimal and the other is useless for decision-making.

This gap—between the model's per-input prediction and the true per-input probability—is called the grouping loss (Perez-Lebel et al., 2022; Kull & Flach, 2015), and the paper notes that while it can sometimes be lower-bounded, it is generally impossible to upper-bound without additional assumptions. This is the theoretical impasse: cross-entropy or marginal likelihood can tell you the model is improving toward $p_{Y|X}$, but without knowing the entropy of $p_{Y|X}$ itself, you cannot know how much room for improvement remains. The paper explicitly invokes Barber (2020), who proved that distribution-free inference about $p_{Y|X}$ is impossible when given only single samples $Y$ per $X$—any confidence interval for $p_{Y|X}(y|x)$ must be wide enough to also contain either 0 or 1 with high probability, making it useless for distinguishing aleatoric from epistemic uncertainty.

The Epistemic Uncertainty Quantification (EUQ) Approach

Given the limitations of first-order calibration, a substantial literature has developed around epistemic uncertainty quantification: methods that attempt to estimate how much the model's predictions could vary given the evidence, usually by imposing some form of Bayesian or ensemble-based reasoning. The paper surveys several prominent families (Section 2.3):

• Gaussian Processes (Bernardo et al., 1998) and Bayesian neural networks (Goan & Fookes, 2020): impose a prior over the function space and compute posterior variance over predictions.
• Ensembles (Lakshminarayanan et al., 2016): train multiple models from different random initializations and use the variance of their predictions as an epistemic uncertainty estimate.
• Monte Carlo dropout (Gal & Ghahramani, 2015): use dropout at test time to simulate sampling from an approximate posterior.
• Epistemic neural networks / Epinets (Osband et al., 2021): augment a base network with a learned network that takes random "index" vectors as input, producing diverse predictions.
• Evidential deep learning (Sensoy et al., 2018): predict parameters of a Dirichlet (or other) distribution over output distributions rather than a point estimate, with a regularized loss intended to incentivize honest uncertainty reporting.

The paper's critique of these methods is sharp and empirically grounded. The fundamental problem is misspecification: all of these methods make implicit or explicit assumptions about the form of the true process $p_{Y|X}$, and when those assumptions are violated, the uncertainty estimates become unreliable—often in ways that are dangerously overconfident.

The paper demonstrates this concretely in Figure 3, which is worth understanding in detail because it motivates the entire approach:

• The experimental setup: a 1D binary regression problem where $p_{Y|X}(1|x)$ has both low-frequency and high-frequency variation (specifically, a sinusoidal pattern with frequency that increases near $x=0$). A dataset of 25,000 $X$ values is used, each with two i.i.d. $Y$ samples.

• The failure modes: With a large training set:

  • Ensembles and Gaussian Process classifiers converge to highly confident predictions (low reported epistemic uncertainty), but their predicted probabilities miss the high-frequency variation near $x \approx 0$—they underfit while claiming high confidence. The GP is misspecified because its kernel prior assumes a consistent length scale that doesn't match the true function; the ensemble converges to consistent but wrong predictions because the model architecture lacks capacity to represent the high-frequency components.

  • Evidential deep learning (Sensoy et al., 2018) shows the opposite problem: it reports high uncertainty near $x \approx 2.0$ where it actually fits the data well—it is underconfident. This stems from the regularization term in the evidential loss, which biases uncertainty estimates upward (a phenomenon formally analyzed by Bengs et al., 2022, 2023).

• The critical implication: "even the largest models are likely to underfit in some regions of $\mathcal{X}$, making this a serious concern if we wish to reliably estimate how far $p^\theta_{Y|X}$ actually is from $p_{Y|X}$" (Section 2.3). This is not a small-sample problem—it persists even with abundant data when the model is structurally incapable of representing the true function.

The paper frames this as a principled limitation: existing EUQ methods rely on the model's internal representation of uncertainty (posterior variance, ensemble disagreement, etc.), but when the model is misspecified, its "beliefs" about what it doesn't know are themselves wrong. A GP with a too-smooth kernel genuinely "believes" the function is smooth, so it reports low uncertainty in regions where it is actually making errors.

The Missing Ingredient: A Signal Independent of Model Assumptions

The paper's diagnosis is that all existing approaches conflate the model's subjective uncertainty with the objective gap between $p^\theta_{Y|X}$ and $p_{Y|X}$. What's needed is an external signal—something from the data itself, not from the model's internal representation—that can reveal when the model's predictions diverge from the true conditional, regardless of the model's architecture or assumptions.

This is where the paper's central intuition enters: if you can observe two independent responses from $p_{Y|X}$ for the same input, you have an external signal about the variance of the true conditional that is independent of any model assumptions. The key observation is that while $p^\theta_{Y|X}(y|x)$ alone conflates aleatoric and epistemic uncertainty, the correlation between two independent draws reveals epistemic uncertainty in a way that can be operationalized through the model's own behavior.

The cheating analogy (Figure 1, Section 1) crystallizes this: if a model's prediction $p^\theta_{Y|X}(\cdot|x)$ already matches $p_{Y|X}(\cdot|x)$ exactly, then observing an independent sample $y_1 \sim p_{Y|X}(\cdot|x)$ provides no additional information—the model shouldn't change its prediction for $y_2$. But if $p^\theta_{Y|X}(\cdot|x)$ differs from $p_{Y|X}(\cdot|x)$, the model can improve its prediction of $y_2$ by "cheating" off $y_1$. The amount of cheating—how much the model's predicted probability for $y_2$ changes after observing $y_1$—directly quantifies the gap between the model's marginal prediction and the true conditional.

How the Paper Positions Itself

The paper makes two distinct but complementary arguments about its contribution, which shape the entire technical development:

First, the paper offers a theoretical resolution to the impossibility result of Barber (2020). Barber proved that distribution-free confidence intervals for $p_{Y|X}$ cannot be tight when only single samples $(X, Y)$ are available. The paper shows that this impossibility can be circumvented when paired responses $(X, Y_1, Y_2)$ are available, without making any assumptions about the functional form of $p_{Y|X}$. This is significant because it identifies paired data—not stronger assumptions—as the key ingredient that makes epistemic uncertainty quantification tractable.

Second, the paper proposes a practical training procedure that requires only a small modification to standard maximum-likelihood training: instead of training on individual $(X, Y)$ pairs, train on triples $(X, Y_1, Y_2)$ where $Y_1, Y_2$ are independent draws from $p_{Y|X}(\cdot|X)$. The model learns to predict the joint distribution $p^\theta_{Y_1,Y_2|X}(y_1, y_2|x)$, and the epistemic uncertainty naturally emerges from the model's own autoregressive structure—when predicting $y_2$ after $y_1$, the model will learn to "cheat" by copying information from $y_1$ to $y_2$ precisely when there are patterns the model hasn't captured in its marginal predictions.

Third, the paper connects these ideas through the formalism of second-order calibration (Definition 2.3). This definition extends ordinary calibration by requiring the model to report not just the average of $p_{Y|X}$ across equivalence classes, but also the covariance matrix—how much the true probability vector varies around the model's prediction within each equivalence class. The paper proves (Theorem 3.2) that second-order calibration of individual predictions is mathematically equivalent to first-order calibration of pair predictions, establishing that the cheating-based training procedure directly targets the right theoretical objective.

The relationship to prior work is carefully delineated in Section 5 (Related Work):

• Not another Bayesian or ensemble method: The approach does not impose a prior or require multiple model copies. The uncertainty signal comes from the data (specifically, from the correlation structure between paired responses), not from the model's internal representation.

• Not a conformal prediction method: While the paper does develop distribution-free confidence intervals (Section 4.2, Algorithm 1) that share the spirit of conformal prediction, the core method does not require a held-out calibration set—the epistemic uncertainty estimates emerge during training from the pair-prediction objective.

• Distinct from task-specific post-hoc methods: Approaches like semantic uncertainty (Kuhn et al., 2022) or self-consistency (Wang et al., 2022) compare multiple model samples at inference time using task-specific similarity metrics. In contrast, this paper requires multiple data samples at training time but only single model evaluations at inference time, and uses a task-agnostic signal (the model's own cheating behavior).

• Not a "distribution over distributions" method: Unlike evidential deep learning (Sensoy et al., 2018) or prior networks (Malinin & Gales, 2018), the paper's "second-order" is about second moments (covariance matrices), not second-order distributions (Dirichlet or Normal-Inverse-Wishart priors over simplex-valued parameters). This distinction is emphasized explicitly in Section 5.

The paper's empirical demonstration strategy follows from this positioning. Rather than claiming superior accuracy (though accuracy is maintained), the key evaluation criterion is second-order calibration error (ECE-2, defined in Section 6.1): how closely does the model's reported epistemic variance match the actual squared error between its marginal prediction and the true conditional? This metric directly tests whether the model honestly reports what it doesn't know—the core capability that existing methods lack.

The experiments span three deliberately different settings—image classification with human annotator noise (CIFAR-10H), synthetic language modeling (digits of $\pi$), and partially-observable sequential decision making (Frozen Lake)—to demonstrate that the approach works across output space sizes (10–30 classes, exponential sequence space, action trajectories) and across different types of epistemic uncertainty (underfitting from limited capacity in the digits task, misspecification from hidden confounders in Frozen Lake).

3. Technical Approach

3.1 Reader orientation (approachable technical breakdown)

This is primarily a theoretical framework paper with empirical validation: the core idea is that training a model to predict pairs of independent responses from the true conditional distribution, and then allowing it to "cheat" by seeing one response while predicting the other, causes the model's cheating behavior to automatically quantify how far its own predictions are from the truth. The system being built is not a new architecture, but a training procedure plus an inference-time scoring method that extracts epistemic uncertainty estimates from a model trained on paired data, without requiring any distributional assumptions about the true process.

3.2 Big-picture architecture (diagram in words)

The system has four major components that interact through a training-then-inference pipeline:

1. Paired Data Collection — for each input $X$, collect two independent responses $Y_1, Y_2 \sim p_{Y|X}(\cdot|X)$ from the true stochastic process. This can be done by querying two random human annotators, running two independent simulations, or sampling twice from the same expert policy. The critical requirement is that $Y_1$ and $Y_2$ are independent and identically distributed given $X$.

2. Joint Pair Predictor $p^\theta_{Y_1,Y_2|X}$ — a model (neural network) trained to predict the joint distribution over pairs of responses given the input. The model is typically structured autoregressively: it predicts $Y_1$ first, then predicts $Y_2$ conditioned on $Y_1$ and $X$. This structure is what enables "cheating": the model can use information from $Y_1$ to improve its prediction of $Y_2$.

3. Cheat-Corrected Metrics — at inference time, given a specific response $y$ for a query $x$, the model computes two probabilities: the marginal probability $p^\theta_{Y_1|X}(y|x)$ (what the model thinks before cheating), and the conditional probability $p^\theta_{Y_2|Y_1,X}(y|y,x)$ (what the model thinks after seeing $y$ once and predicting it again). The ratio of these gives the cheat-corrected epistemic confidence $C_\text{Cheat}^\theta(y|x)$, and their difference gives the cheat-corrected epistemic variance $\hat{V}^\theta_\text{Cheat}(y|x)$.

4. Distribution-Free Calibration Adjustment (optional, Algorithm 1) — for settings where the pair predictor may not be perfectly calibrated, a held-out calibration set of paired responses can be used to conservatively rescale the variance estimates to produce provably-correct frequentist confidence intervals for $p_{Y|X}(y|x)$, without any assumptions about the form of $p_{Y|X}$.

Information flows as follows: training data $\\{(X^{(i)}, Y_1^{(i)}, Y_2^{(i)})\\}$ → train joint pair predictor via standard cross-entropy → at inference, for a new query $x$ and candidate response $y$, extract $p^\theta_{Y_1|X}(y|x)$ and $p^\theta_{Y_2|Y_1,X}(y|y,x)$ → compute $C_\text{Cheat}^\theta(y|x)$ and $\hat{V}^\theta_\text{Cheat}(y|x)$ → optionally calibrate with Algorithm 1 → use as epistemic uncertainty measures for selective decoding, hallucination detection, or confidence intervals.

3.3 Roadmap for the deep dive

• First, the pair prediction training objective and factorization (Section 3.4.1): how the model is structured and trained, what loss is minimized, and why the autoregressive factorization naturally incentivizes cheating behavior.

• Second, the epistemic variance and confidence metrics (Section 3.4.2): the mathematical definitions of $\hat{V}^\theta_\text{Cheat}$ and $C_\text{Cheat}^\theta$, how they are computed from model outputs at inference time, and what they represent operationally.

• Third, the theoretical framework: second-order calibration (Section 3.4.3): the formal definitions that connect first-order calibration on pairs to second-order calibration on marginals, and why this connection matters for constructing reliable error bounds.

• Fourth, the theoretical guarantees (Section 3.4.4): what properties hold when the model is perfectly calibrated, including bounds on deviation from $p_{Y|X}$ and statistical hallucination rates, and the formal statements of Theorems 4.2, 4.5, and 4.6.

• Fifth, the architectural choices and regularizations (Section 3.4.5): how the output layer is designed to satisfy symmetry and positive semidefiniteness constraints for different output space types (binary, finite enumeration, sequences), and what regularizations are applied to prevent negative variance estimates.

• Sixth, the distribution-free calibration adjustment (Section 3.4.6): the algorithm for robustifying imperfectly-calibrated models using a held-out paired dataset, its inputs, its guarantees, and how it circumvents the impossibility result of Barber (2020).

3.4 Detailed, sentence-based technical breakdown

This paper provides a principled theoretical framework and training methodology for extracting epistemic uncertainty estimates from models trained on paired response data, without making distributional assumptions about the true conditional $p_{Y|X}$. The core idea is that cheating behavior under an autoregressive pair-prediction objective reveals exactly the epistemic uncertainty: if a model's marginal prediction $p^\theta_{Y|X}(\cdot|x)$ already matches the true conditional $p_{Y|X}(\cdot|x)$, then observing an independent sample $y_1$ provides no additional information for predicting $y_2$; conversely, if the marginal prediction is wrong, the model can improve its prediction of $y_2$ by conditioning on $y_1$. The magnitude of this improvement—operationalized through ratios and differences of probabilities—quantifies the gap between the model's prediction and the truth.

---

3.4.1 Pair Prediction Training: Objective and Factorization

The training procedure is a direct modification of standard maximum-likelihood estimation. Instead of training a model to predict individual responses $Y$ given inputs $X$ by minimizing the cross-entropy loss $-\mathbb{E}[\log p^\theta_{Y|X}(Y|X)]$, the method trains a model to predict pairs of independent responses $(Y_1, Y_2)$ given $X$ by minimizing:

$-\mathbb{E}_{X \sim p(X), \, Y_1, Y_2 \stackrel{\text{i.i.d.}}{\sim} p_{Y|X}(\cdot|X)} \left[ \log p^\theta_{Y_1,Y_2|X}(Y_1, Y_2 | X) \right]$

where:

• $X$ is an input (e.g., an image, a text prompt, an environment state),
• $Y_1$ and $Y_2$ are two independent samples from the true conditional distribution $p_{Y|X}(\cdot|X)$, meaning $Y_1 \perp\\!\\!\\!\perp Y_2 \mid X$ and both follow the same distribution $p_{Y|X}(\cdot|X)$,
• $p^\theta_{Y_1,Y_2|X}$ is the model's predicted joint distribution over the pair, parameterized by $\theta$.

What it computes: the standard cross-entropy loss between the model's predicted joint distribution over $(Y_1, Y_2)$ and the actual observed pair, averaged over the training distribution of inputs and paired responses. This is identical in form to ordinary maximum-likelihood training, except the target space is $\mathcal{Y} \times \mathcal{Y}$ rather than $\mathcal{Y}$.

Why this form: cross-entropy is a strictly proper scoring rule for distributions (Kull & Flach, 2015), meaning its unique minimizer is the true conditional distribution $p_{Y_1,Y_2|X} = p_{Y|X} \cdot p_{Y|X}$ (the product of two independent draws). This property is crucial: if the model has sufficient capacity and training data, it will converge to the true joint distribution. Moreover, as the paper notes (Section 3), calibration—meaning the predicted probabilities match the true conditional probabilities on average—tends to emerge in high-capacity models trained with cross-entropy (Błasiok et al., 2023; OpenAI, 2023). The paper leverages this: training a model to predict pairs using cross-entropy incentivizes the model to become calibrated over $\mathcal{Y} \times \mathcal{Y}$, which, as Theorem 3.2 will show, directly implies second-order calibration over $\mathcal{Y}$.

Model factorization: the paper explicitly factorizes the joint distribution autoregressively:

$p^\theta_{Y_1,Y_2|X}(y_1, y_2 | x) = p^\theta_{Y_1|X}(y_1 | x) \cdot p^\theta_{Y_2|Y_1,X}(y_2 | y_1, x)$

where:

• $p^\theta_{Y_1|X}(y_1|x)$ is the marginal distribution for the first response—the model's initial guess before cheating,
• $p^\theta_{Y_2|Y_1,X}(y_2|y_1,x)$ is the conditional distribution for the second response given the first—the model's prediction after observing $y_1$.

Why this factorization: this autoregressive structure is what enables the "cheating" behavior that the entire method depends on. When the model predicts $Y_2$ after seeing $Y_1$, it can—and will, if training is successful—learn to use information from $Y_1$ to improve its prediction of $Y_2$. The key insight is that this improvement will only occur when there are aspects of $Y_1$ that are predictable from $X$ but not captured by the marginal $p^\theta_{Y_1|X}$. In other words, the model learns to "cheat" whenever its own marginal prediction is inaccurate. The paper captures this intuition: "an expert doesn't need to cheat, so if you let your model cheat and it does, it must not know the answer to your question" (Section 3).

This factorization is implemented differently depending on the output space $\mathcal{Y}$:

• For binary classification ($\mathcal{Y} = \\{0, 1\\}$), the joint is parameterized via two outputs: the marginal probability $\mu(x) = p^\theta(Y_1=1|x)$ and the correlation $\rho(x)$ between $Y_1$ and $Y_2$ (Section E, Proposition E.2).
• For finite enumeration ($\mathcal{Y} = \\{1, \ldots, K\\}$), a $K \times K$ symmetric softmax output layer is used, where the $(i,j)$ entry gives $p^\theta(Y_1 = i, Y_2 = j|x)$ (Section E).
• For sequences (exponentially large $\mathcal{Y}$), an autoregressive sequence model (Transformer) generates $Y_1$ first, then generates $Y_2$ conditioned on $Y_1$ and $X$, with both padded to a constant length to maintain consistent positional embeddings (Section F.3.2).

An important practical detail for sequence models: the paper pads $Y_1$ and $Y_2$ to a constant length and uses a separator token <SEP> between the input and the responses. This ensures that the positional embeddings of $Y_2$ tokens are consistent regardless of $Y_1$'s length, which the authors found improved performance by reducing noise in the confidence metric (Appendix E).

---

3.4.2 Cheat-Corrected Epistemic Metrics: Variance and Confidence

Given a trained pair predictor $p^\theta_{Y_1,Y_2|X}$, the paper defines two inference-time metrics that extract epistemic uncertainty estimates for any specific response $y$ to any query $x$. Both metrics compare the model's prediction before and after "self-cheating"—i.e., conditioning on $y$ as if it were the observed $Y_1$ when predicting $Y_2 = y$.

Cheat-Corrected Epistemic Variance (Definition 4.1):

$\hat{V}^\theta_\text{Cheat}(y | x) \triangleq p^\theta_{Y_1|X}(y | x) \cdot \left( p^\theta_{Y_2|Y_1,X}(y | y, x) - p^\theta_{Y_1|X}(y | x) \right)$

where:

• $p^\theta_{Y_1|X}(y|x)$ is the marginal probability of response $y$—the model's prediction before cheating,
• $p^\theta_{Y_2|Y_1,X}(y|y,x)$ is the conditional probability of response $y$ as $Y_2$ given that $Y_1$ was also $y$ and the input was $x$—the model's prediction after self-cheating,
• $\hat{V}^\theta_\text{Cheat}(y|x)$ is a scalar in $[-\epsilon, p^\theta_{Y_1|X}(y|x)(1-p^\theta_{Y_1|X}(y|x))]$ that estimates the epistemic variance of the true probability $p_{Y|X}(y|x)$ around the model's prediction.

What it computes: the product of the marginal probability and the difference between the conditional and marginal probabilities. Operationally, this is computed by scoring the same response $y$ twice under the model: once marginalizing over $Y_1$ (to get $p^\theta_{Y_1|X}(y|x)$), and once by concatenating two copies of $y$ and extracting the conditional probability of the second copy given the first (to get $p^\theta_{Y_2|Y_1,X}(y|y,x)$). The resulting value, when the model is calibrated, represents the variance of the true $p_{Y|X}(y|X)$ across inputs $X$ in the same equivalence class—i.e., the squared distance between the model's prediction and the truth.

Why this form: if $p^\theta_{Y_1|X}(\cdot|x)$ already equals $p_{Y|X}(\cdot|x)$ exactly, then seeing $Y_1 = y$ provides no additional information about $Y_2$ beyond what the model already knows, so $p^\theta_{Y_2|Y_1,X}(y|y,x) = p^\theta_{Y_1|X}(y|x)$, and $\hat{V}^\theta_\text{Cheat}(y|x) = 0$. If the marginal prediction is wrong, the model can use $Y_1$ to improve its prediction of $Y_2$, making the conditional probability larger than the marginal, yielding $\hat{V}^\theta_\text{Cheat}(y|x) > 0$. The form $p \cdot (p_{\text{cond}} - p)$ emerges from the decomposition of the pair covariance $\hat{\Sigma}^\theta_{Y_1,Y_2|X}(x)_{y,y} = p^\theta_{Y_1,Y_2|X}(y,y|x) - (p^\theta_{Y_1|X}(y|x))^2$, which, when the model is calibrated, equals the diagonal entry of the epistemic covariance matrix (Theorem 3.2). The autoregressive factorization $p^\theta_{Y_1,Y_2|X}(y,y|x) = p^\theta_{Y_1|X}(y|x) \cdot p^\theta_{Y_2|Y_1,X}(y|y,x)$ then yields the given expression.

Cheat-Corrected Epistemic Confidence (Definition 4.3):

$C^\theta_\text{Cheat}(y | x) \triangleq \frac{p^\theta_{Y_1|X}(y | x)}{p^\theta_{Y_2|Y_1,X}(y | y, x)}$

(or 0 if $p^\theta_{Y_1|X}(y|x) = 0$), where the same notation applies.

What it computes: the ratio of the marginal probability to the self-conditioned probability. This is a normalized measure between 0 and 1 (when the model is calibrated) that indicates how close the model's prediction is to the truth: values near 1 indicate that the model believes $p^\theta_{Y_1|X}(y|x) \approx p_{Y|X}(y|x)$, while values near 0 indicate a large gap.

Why this form: the ratio normalizes for the "aleatoric" difficulty of the response $y$. Even if the model perfectly matches $p_{Y|X}$, the marginal probability $p^\theta_{Y_1|X}(y|x)$ may be small simply because $y$ is inherently unlikely under the true process. The conditional probability $p^\theta_{Y_2|Y_1,X}(y|y,x)$ accounts for this: it estimates how likely $y$ is among situations where $y$ actually occurred. The ratio therefore cancels out the aleatoric component and isolates the epistemic component. Proposition 4.4 proves that $C^\theta_\text{Cheat}(y|x) = 1$ if and only if $p^\theta_{Y_1|X}(y|x) = p_{Y|X}(y|x)$ (when calibrated), giving it a clean operational interpretation.

Both metrics can be computed from a single evaluation of the model: feed the concatenation $(x, y, y)$ through the autoregressive model, sum the log-probabilities separately for the first $y$ and the second $y$, and take the difference (for $\hat{V}^\theta_\text{Cheat}$) or ratio (for $C^\theta_\text{Cheat}$). The paper provides worked examples for the digits-of-$\pi$ task in Appendix A (Figures 9 and 10), showing how token-level log-probability differences accumulate across the sequence.

A critical practical issue: when the model is not perfectly calibrated (which is always the case in practice), $\hat{V}^\theta_\text{Cheat}$ can be negative and $C^\theta_\text{Cheat}$ can exceed 1. This occurs because, without calibration, the factorization $p^\theta_{Y_1,Y_2|X}(y,y|x) = p^\theta_{Y_1|X}(y|x) \cdot p^\theta_{Y_2|Y_1,X}(y|y,x)$ does not guarantee the joint matrix is symmetric or positive semidefinite. The paper addresses this through architecture design (enforcing symmetry in the output layer for finite $\mathcal{Y}$) and regularization (penalizing negative eigenvalues), discussed in Section 3.4.5.

---

3.4.3 The Theoretical Framework: First-Order and Second-Order Calibration

The paper builds its theoretical guarantees on two nested definitions of calibration, which formalize what it means for a model to "know what it knows."

First-Order Calibration (Definition 2.1):

A predictor $p^\theta_{Y|X}: \mathcal{X} \to \Delta_\mathcal{Y}$ is first-order calibrated if there exists a grouping function $\Phi: \mathcal{X} \to \mathcal{Z}$ such that, for every input $x$ and response $y$:

$p^\theta_{Y|X}(y | x) = \mathbb{E}\left[ p_{Y|X}(y | X) \;\middle|\; \Phi(X) = \Phi(x) \right]$

where:

• $\Phi$ is any function that maps inputs to equivalence classes in some space $\mathcal{Z}$,
• $[x]_\Phi = \\{x' \in \mathcal{X} : \Phi(x') = \Phi(x)\\}$ is the set of inputs indistinguishable by $\Phi$,
• $p_{Y|X}(\cdot|X)$ is the true conditional distribution.

What it states: the model's predicted probability for any response equals the average true probability across all inputs that receive the same label from $\Phi$. The grouping function $\Phi$ represents what the model "knows": it can partition inputs into equivalence classes, and within each class, it reports the correct average. The coarsest such grouping is given by the model's own output vector $\Phi^\theta_{Y|X}(x) = (p^\theta_{Y|X}(y_1|x), \ldots, p^\theta_{Y|X}(y_K|x))$, as established by Proposition 2.2.

Why this definition: it captures the intuitive notion that a calibrated model's confidence should match empirical frequencies. But critically, it also exposes the limitation: calibration does not guarantee $p^\theta_{Y|X}(\cdot|x) = p_{Y|X}(\cdot|x)$ for each individual $x$; it only guarantees equality on average across sets of $x$ that the model cannot distinguish. The gap between the per-input prediction and the per-input truth is the grouping loss, which cannot be bounded without additional signals.

Second-Order Calibration (Definition 2.3):

A predictor $p^\theta_{Y|X}: \mathcal{X} \to \Delta_\mathcal{Y}$ and a covariance estimator $\hat{\Sigma}^\theta: \mathcal{X} \to \mathbb{R}^{\mathcal{Y} \times \mathcal{Y}}$ are second-order calibrated if there exists a grouping function $\Phi$ such that, for every input $x$:

$p^\theta_{Y|X}(y | x) = \mathbb{E}\left[ p_{Y|X}(y | X) \;\middle|\; X \in [x]_\Phi \right]$

$\hat{\Sigma}^\theta(x) = \text{Cov}\left[ \mathbf{p}_{Y|X}(\cdot | X),\, \mathbf{p}_{Y|X}(\cdot | X) \;\middle|\; X \in [x]_\Phi \right]$

where:

• $\mathbf{p}_{Y|X}(\cdot|X) \in \Delta_\mathcal{Y}$ is the $K$-dimensional vector of true probabilities for input $X$ (viewed as a random vector conditional on $X$),
• $\text{Cov}[\cdot, \cdot \mid X \in [x]_\Phi]$ is the $K \times K$ covariance matrix of these probability vectors across inputs in the same equivalence class.

What it states: second-order calibration extends first-order calibration by requiring the model to report not just the average of $p_{Y|X}$ within each equivalence class, but also the covariance—how much the true probability vector varies from input to input within the class. The diagonal entry $\hat{\Sigma}^\theta(x)_{y,y}$ is the variance of $p_{Y|X}(y|X)$ within $[x]_\Phi$, which directly quantifies the expected squared error between the model's prediction and the truth for response $y$.

Why this matters: a second-order calibrated model can answer the question "how far might my prediction $p^\theta_{Y|X}(y|x)$ be from the true probability $p_{Y|X}(y|x)$ for this specific $x$?" The answer is given by the variance: if $\hat{\Sigma}^\theta(x)_{y,y}$ is small, the model is confident that its prediction is accurate for all inputs in this equivalence class (i.e., the grouping loss is small). If it's large, the model acknowledges that its prediction is a crude average over inputs with very different true probabilities.

The Equivalence Theorem (Theorem 3.2):

The paper's central theoretical result establishes that first-order calibration on pairs is equivalent to second-order calibration on marginals. Formally:

If $p^\theta_{Y_1,Y_2|X}$ is first-order calibrated at predicting pairs $(Y_1, Y_2)$, then its marginal $p^\theta_{Y_1|X}$ and its pair covariance $\hat{\Sigma}^\theta_{Y_1,Y_2|X}$ are second-order calibrated at predicting $p_{Y|X}$. Moreover, this is a bijection: for any second-order-calibrated $(p^\theta_{Y|X}, \hat{\Sigma}^\theta)$, there is a unique first-order-calibrated pair predictor with matching marginal and pair covariance.

The pair covariance $\hat{\Sigma}^\theta_{Y_1,Y_2|X}(x) \in \mathbb{R}^{K \times K}$ is defined (Definition 3.1) as:

$\hat{\Sigma}^\theta_{Y_1,Y_2|X}(x)_{y_i, y_j} \triangleq p^\theta_{Y_1,Y_2|X}(y_i, y_j | x) - p^\theta_{Y_1|X}(y_i | x) \cdot p^\theta_{Y_2|X}(y_j | x)$

Why this equality holds: the proof (Appendix D.2) uses the decomposition of covariance as a difference of expectations:

$\text{Cov}[p_{Y|X}(y|X), p_{Y|X}(y'|X) \mid X \in [x]_\Phi] = \mathbb{E}[p_{Y|X}(y|X) \cdot p_{Y|X}(y'|X) \mid X \in [x]_\Phi] - \mathbb{E}[p_{Y|X}(y|X) \mid X \in [x]_\Phi] \cdot \mathbb{E}[p_{Y|X}(y'|X) \mid X \in [x]_\Phi]$

The first term $\mathbb{E}[p_{Y|X}(y|X) \cdot p_{Y|X}(y'|X) \mid \Phi]$ is exactly $\mathbb{E}[P(Y_1=y, Y_2=y' \mid X) \mid \Phi]$ by independence of $Y_1$ and $Y_2$ given $X$. If the pair predictor is calibrated, its predicted $p^\theta_{Y_1,Y_2|X}(y,y'|x)$ equals this expectation. The second and third terms are the marginal expectations, which equal $p^\theta_{Y_1|X}(y|x)$ and $p^\theta_{Y_2|X}(y'|x)$ if the pair predictor is calibrated. Therefore, the pair covariance $\hat{\Sigma}^\theta_{Y_1,Y_2|X}$ exactly equals the epistemic covariance of the true probabilities.

What this means operationally: you do not need to explicitly train a model to output both a mean and a covariance matrix—you simply train it to predict pairs using cross-entropy, and the covariance emerges automatically from the difference between the joint and the product of marginals. The autoregressive factorization makes this practical: the conditional term $p^\theta_{Y_2|Y_1,X}(y|y,x)$ captures how much more likely $y$ becomes when the model "cheats," and the diagonal of the pair covariance simplifies to $\hat{V}^\theta_\text{Cheat}(y|x) = p^\theta_{Y_1|X}(y|x) \cdot (p^\theta_{Y_2|Y_1,X}(y|y,x) - p^\theta_{Y_1|X}(y|x))$.

---

3.4.4 Theoretical Guarantees Under Calibration

When the pair predictor $p^\theta_{Y_1,Y_2|X}$ is perfectly calibrated, the paper proves several strong guarantees that operationalize the uncertainty estimates.

Deviation Bound (Theorem 4.2):

For any event $A$ and any response $\tilde{Y}$ (possibly random) such that $A, \tilde{Y} \perp\\!\\!\\!\perp X \mid \Phi^\theta_{Y_1,Y_2|X}(X)$:

$\mathbb{E}\left[ (p^\theta_{Y_1|X}(\tilde{Y}|X) - p_{Y|X}(\tilde{Y}|X))^2 \;\middle|\; A \right] = \mathbb{E}\left[ \hat{V}^\theta_\text{Cheat}(\tilde{Y}|X) \;\middle|\; A \right]$

and for any $\beta \in (0, 1)$:

$P\left[ \left|p^\theta_{Y_1|X}(\tilde{Y}|X) - p_{Y|X}(\tilde{Y}|X)\right| \geq \sqrt{\frac{\hat{V}^\theta_\text{Cheat}(\tilde{Y}|X)}{\beta}} \;\middle|\; A \right] \leq \beta$

What these state: The first equality says that the expected squared error between the model's prediction and the truth is exactly the expected cheat-corrected variance. This is an exact calibration-in-expectation property, not an inequality. The second is a Chebyshev-style confidence interval: with probability at least $1-\beta$, the true probability $p_{Y|X}(\tilde{Y}|X)$ lies within $\pm \sqrt{\hat{V}^\theta_\text{Cheat}/\beta}$ of the model's prediction $p^\theta_{Y_1|X}(\tilde{Y}|X)$.

The independence condition $A, \tilde{Y} \perp\\!\\!\!\perp X \mid \Phi^\theta_{Y_1,Y_2|X}(X)$ is subtle but crucial. It means the guarantee holds when conditioning on events or responses that are functions only of the model's output matrix $\Phi^\theta_{Y_1,Y_2|X}(X)$. For example, if you condition on the model reporting a specific predicted probability and variance for a specific response class, the bound holds. But it does not hold conditioned on $X$ itself—once you know $X$, the true probability is either within the interval or not, so the conditional probability is either 0 or 1.

Statistical Hallucination Bound (Theorem 4.5):

Under the same independence condition, for any decoding algorithm that produces responses $\tilde{Y}$:

$P\left[ p_{Y|X}(\tilde{Y}|X) = 0 \;\middle|\; A \right] \leq 1 - \mathbb{E}\left[ C^\theta_\text{Cheat}(\tilde{Y}|X) \;\middle|\; A \right]$

What it states: the probability that a generated response is a "statistical hallucination"—a response $y$ for which the true probability $p_{Y|X}(y|X)$ is exactly zero—is bounded above by the expected complement of the cheat-corrected epistemic confidence. A statistical hallucination is defined in the paper (Section 4.1) as a response for which $p_{Y|X}(y|x) = 0$, meaning it could never occur under the true process—for example, a false statement about a digit of $\pi$ when queried about that specific digit.

Why this bound works: the proof uses Cantelli's inequality (one-sided Chebyshev). Conditioned on the model's output, the true probability $p_{Y|X}(\tilde{Y}|X)$ is a random variable with mean $p^\theta_{Y_1|X}(\tilde{Y}|X)$ and variance $\hat{V}^\theta_\text{Cheat}(\tilde{Y}|X)$. The probability that this random variable equals zero is bounded by $1 - \mathbb{E}[Z]^2 / \mathbb{E}[Z^2]$, which simplifies to $1 - C^\theta_\text{Cheat}(\tilde{Y}|X)$ using the relationship between the first and second moments encoded in the cheat-corrected confidence.

Decoding strategies enabled by Theorem 4.5:

1. Cheat-corrected selective generation: generate $\tilde{Y}$ using any sampler, then reject (abstain) if $|1 - C^\theta_\text{Cheat}(\tilde{Y}|X)| > \beta$. This guarantees that, conditioned on not abstaining, the hallucination rate is at most $\beta$.

2. Cheat-corrected rejection sampling: repeatedly sample $\tilde{Y} \sim p^\theta_{Y_1|X}(\cdot|X)$ until $|1 - C^\theta_\text{Cheat}(\tilde{Y}|X)| < \beta$, then return $\tilde{Y}$.

3. Cheat-corrected top-1 search: find $\arg\max_y p^\theta_{Y_1|X}(y|X)$ subject to $|1 - C^\theta_\text{Cheat}(y|X)| < \beta$, or abstain if no such $y$ exists.

The paper uses the absolute value $|1 - C^\theta_\text{Cheat}|$ rather than $1 - C^\theta_\text{Cheat}$ in practice (Section 6.2) because miscalibration can cause $C^\theta_\text{Cheat} > 1$, and the absolute value is a conservative safe threshold that reduces to the original bound when the model is calibrated.

Distribution-Free Calibration Adjustment (Theorem 4.6 and Algorithm 1):

For binary $\mathcal{Y} = \\{0, 1\\}$, the paper provides an algorithm that corrects imperfectly-calibrated variance estimates using a held-out set of paired responses, without any assumptions about $p_{Y|X}$.

The input to the algorithm (Algorithm 1) is:

• A calibration set $\\{(x^{(i)}, y_1^{(i)}, y_2^{(i)})\\}_{i=1}^N$ of paired response data,
• A variance cutoff $\varepsilon > 0$ (controls the minimum variance considered, preventing division by zero),
• A tolerance $\alpha \in (0, 1)$ (controls the required confidence level),
• A predictor $p^\theta_{Y|X}$ and variance estimator $\hat{V}^\theta$ (which need not be well-calibrated).

For each calibration example $i = 1$ to $N$, the algorithm computes:

• $\hat{p}^{(i)} := p^\theta_{Y|X}(1 | x^{(i)})$, the model's predicted probability for $Y=1$,
• $\hat{v}^{(i)}_\varepsilon := \max\\{\hat{V}^\theta(1 | x^{(i)}), \varepsilon\\}$, the truncated variance estimate,
• $s^{(i)}_\varepsilon := (y_1^{(i)} - \hat{p}^{(i)}) \cdot (y_2^{(i)} - \hat{p}^{(i)}) / \hat{v}^{(i)}_\varepsilon$, a normalized product of residuals.

The key quantity $s^{(i)}_\varepsilon$ is an unbiased estimate of the normalized squared error. Its expectation (over $Y_1, Y_2 \sim p_{Y|X}(\cdot|x^{(i)})$) is:

$\mathbb{E}[s^{(i)}_\varepsilon \mid x^{(i)}] = \frac{(p_{Y|X}(1|x^{(i)}) - p^\theta_{Y|X}(1|x^{(i)}))^2}{\max\\{\hat{V}^\theta(1|x^{(i)}), \varepsilon\\}} =: D_\varepsilon(x^{(i)})$

$D_\varepsilon(x^{(i)})$ is the true normalized deviation at $x^{(i)}$. If the model were second-order calibrated, $\mathbb{E}[D_\varepsilon] \to 1$ as $\varepsilon \to 0$. The algorithm then computes a $(1-\alpha)$-confidence upper bound $\gamma^+_\varepsilon$ on $\mathbb{E}[S_\varepsilon]$ using any subroutine for bounding the mean of a bounded random variable (e.g., Hoeffding's inequality or betting-based methods from Waudby-Smith & Ramdas, 2020).

The resulting guarantee (Theorem 4.6): with probability at least $1-\alpha$ over draws of the calibration set, for a randomly sampled input $X \sim p(X)$ and any $\beta \in (0, 1)$:

$P\left[ \left| p^\theta_{Y|X}(1|X) - p_{Y|X}(1|X) \right| \geq \sqrt{\frac{\gamma^+_\varepsilon \cdot \max\\{\hat{V}^\theta(1|X), \varepsilon\\}}{\beta}} \right] \leq \beta$

What this computes: a corrected confidence interval for $p_{Y|X}$ that is wider than the calibrated version by a factor of $\sqrt{\gamma^+_\varepsilon}$, where $\gamma^+_\varepsilon$ accounts for any miscalibration in the original variance estimates. If the model is well-calibrated, $\gamma^+_\varepsilon \approx 1$ for large $N$ and small $\varepsilon$. If the model is overconfident (variance estimates too small), $\gamma^+_\varepsilon > 1$ to compensate. If the model is underconfident, the bound becomes looser but remains valid.

Why this form: the key insight is that $s^{(i)}_\varepsilon$ provides an unbiased, sample-based estimate of $D_\varepsilon(x^{(i)})$ using only the observed $Y_1, Y_2$ and the model's outputs—it does not require knowing the true $p_{Y|X}$. By constructing a confidence interval for $\mathbb{E}[S_\varepsilon] = \mathbb{E}[D_\varepsilon]$, the algorithm obtains a data-driven bound on the average normalized squared error, which can then be used to rescale the per-input variance estimates. This circumvents the impossibility result of Barber (2020) because paired data enables the estimation of the second moment of $p_{Y|X}$—something impossible with single samples where only the first moment can be identified.

Implementation details: the algorithm uses the subroutine MeanConfItvl, which can be based on Hoeffding's inequality (Proposition D.3) or on betting-based algorithms (confseq). For Hoeffding's inequality, with $N$ calibration examples:

$\gamma^+_\varepsilon = \frac{1}{N} \sum_{i=1}^N s^{(i)}_\varepsilon + \sqrt{\frac{2 \cdot (-\log \alpha)}{N \cdot \varepsilon^2}}$

The term $\sqrt{-\log \alpha / N}$ decreases as the calibration set grows, and $1/\varepsilon$ appears because $s^{(i)}_\varepsilon \in [-1/\varepsilon, 1/\varepsilon]$.

---

3.4.5 Architectural Design and Regularization

The paper develops architectural constraints to encourage the pair predictor $p^\theta_{Y_1,Y_2|X}$ to satisfy the properties that calibrated models must satisfy (Proposition E.1), reducing the gap between theory and practice.

Properties required of a calibrated pair predictor (Proposition E.1):

1. Proper probability distribution: $p^\theta_{Y_1,Y_2|X}(y_1, y_2|x) \geq 0$ for all $y_1, y_2, x$, and $\sum_{y_1, y_2} p^\theta_{Y_1,Y_2|X}(y_1, y_2|x) = 1$.

2. Symmetry: $p^\theta_{Y_1,Y_2|X}(y_1, y_2|x) = p^\theta_{Y_1,Y_2|X}(y_2, y_1|x)$, because $Y_1$ and $Y_2$ are identically distributed.

3. Positive semidefiniteness: for each $x$, the $K \times K$ matrix $\hat{P}[x]$ with entries $\hat{P}_{ij}[x] = p^\theta_{Y_1,Y_2|X}(v_i, v_j|x)$ is positive semidefinite. This is because $\hat{P}[x] = \mathbb{E}[\mathbf{p}[X] \mathbf{p}[X]^T \mid \Phi]$ for some probability vector $\mathbf{p}[X]$, and the expectation of rank-1 positive semidefinite matrices is positive semidefinite.

Architectural choices by output space type:

• Binary classification ($\mathcal{Y} = \\{0, 1\\}$): the paper parameterizes the joint using two outputs from the network: $\mu(x) = \sigma(h_\theta(x)[0])$ and $\rho(x) = \sigma(h_\theta(x)[1])$, where $\sigma$ is the logistic sigmoid and $h_\theta(x) \in \mathbb{R}^2$ is the network's penultimate layer output. The joint matrix is then constructed (Proposition E.2) as:

$\hat{P}[x] = \rho(x) \begin{bmatrix} 1 - \mu(x) & 0 \\ 0 & \mu(x) \end{bmatrix} + (1 - \rho(x)) \begin{bmatrix} (1-\mu(x))^2 & \mu(x)(1-\mu(x)) \\ \mu(x)(1-\mu(x)) & \mu(x)^2 \end{bmatrix}$

where $\mu(x)$ is the predicted marginal probability of $Y=1$, and $\rho(x)$ is the predicted Pearson correlation between $Y_1$ and $Y_2$ conditioned on $\Phi(X)$ (also called the Phi coefficient). This parameterization inherently enforces properties (1), (2), and (3) for any $\mu \in [0, 1], \rho \in [0, 1]$.

• Finite classification ($\mathcal{Y} = \\{1, \ldots, K\\}$): the paper uses a $K \times K$ symmetric softmax output layer. The network outputs $K(K+1)/2$ logits corresponding to the upper triangle of a symmetric matrix; these are reshaped into a $K \times K$ symmetric matrix by adding the transpose. The softmax is then applied over all $K^2$ entries, enforcing property (1). Symmetry (property 2) is enforced by construction. Property (3) is not strictly enforced by the architecture but is regularized: the paper computes the eigenvalues $\lambda_i(x)$ of the post-softmax matrix $\hat{P}[x]$, and adds a penalty term for negative eigenvalues:

$\mathcal{L}_{\text{regularized}}(x, y_1, y_2) = -\log p^\theta_{Y_1,Y_2|X}(y_1, y_2|x) + \alpha \sum_{i=1}^K \max\{0, -\lambda_i(x)\}^2$

where $\alpha$ is the regularization strength (set to 10.0 in the CIFAR-10H experiments). Since a calibrated model should never produce negative eigenvalues, this penalty does not change the optimal calibrated solution if one exists, but prevents overfitting from causing unreasonable negative variance estimates during training.

• Sequence modeling (exponentially large $\mathcal{Y}$): for the digits-of-$\pi$ and Frozen Lake tasks, the paper uses a standard autoregressive Transformer with no special architectural constraints beyond property (1) (enforced by the standard softmax token-level outputs). The authors note that developing architectures that enforce properties (2) and (3) for sequence models is an "exciting area for future work" (Appendix E). In practice, they pad both $Y_1$ and $Y_2$ to a constant length with a separator token <SEP> to ensure consistent positional embeddings, which reduces noise in the confidence metric since $Y_2$'s positional offsets don't vary with $Y_1$'s length.

Training hyperparameters (from experimental sections):

• CIFAR-10H (Cheat NN): Wide ResNet (depth 28, width multiplier 10), pretrained on CIFAR-10N for 50 epochs with AdamW, learning rate $1.113 \times 10^{-3}$, weight decay $4.835 \times 10^{-1}$, batch size 512. Fine-tuned on CIFAR-10H for 50 epochs with learning rate $4.265 \times 10^{-5}$, weight decay $1.865 \times 10^{-1}$. AugMix augmentation applied during training. Eigenvalue regularization coefficient $\alpha = 10.0$.

• CIFAR-10H (Cheat SNGP): Same Wide ResNet with SNGP modifications (spectral normalization, 1024 orthogonal random features, spectral-norm bound 6.0). Pretrained for 200 epochs with learning rate $1.687 \times 10^{-3}$, weight decay $4.411 \times 10^{-1}$. Fine-tuned for 30 epochs with learning rate $4.972 \times 10^{-5}$, weight decay $7.621 \times 10^{-5}$. The Gaussian process posterior covariance is NOT computed; the random features are used only as a deterministic parameterization with distance-awareness inductive biases.

• Digits of $\pi$: 6-layer pre-LayerNorm Transformer, 8 attention heads, embedding dimension 512, MLP dimension 2048. Trained for 50,000 iterations at batch size 1024, AdamW with 1,000 warmup steps, maximum learning rate $2 \times 10^{-5}$, cosine decay. Standard next-token prediction loss, masking out tokens before <SEP>.

• Frozen Lake: 12-layer pre-LayerNorm GPT-2-style Transformer, 12 attention heads, embedding dimension 768, MLP dimension 3072. Trained for 50,000 iterations at batch size 512, AdamW with 1,000 warmup steps, maximum learning rate $2 \times 10^{-5}$, cosine decay.

---

3.4.6 The Distribution-Free Calibration Pipeline (Algorithm 1)

Algorithm 1 operates on a held-out calibration set and produces a scalar multiplier $\gamma^+_\varepsilon$ that can be used to widen the cheat-corrected confidence intervals to achieve provable frequentist coverage.

Step-by-step operation:

1. Iterate over calibration examples: for each $i = 1, \ldots, N$, given $(x^{(i)}, y_1^{(i)}, y_2^{(i)})$:

   • Extract the model's prediction $\hat{p}^{(i)} = p^\theta_{Y|X}(1|x^{(i)})$.
   • Extract the truncated variance $\hat{v}^{(i)}_\varepsilon = \max\\{\hat{V}^\theta(1|x^{(i)}), \varepsilon\\}$. The $\varepsilon$ floor prevents division by zero and controls how much the bound relies on regions with near-zero predicted variance. Smaller $\varepsilon$ allows tighter bounds where the model is confident, but risks blowup if the model is miscalibrated.
   • Compute the normalized cross-residual: $s^{(i)}_\varepsilon = (y_1^{(i)} - \hat{p}^{(i)}) \cdot (y_2^{(i)} - \hat{p}^{(i)}) / \hat{v}^{(i)}_\varepsilon$. This is a single scalar per example.

2. Construct a confidence interval for $\mathbb{E}[S_\varepsilon]$: call MeanConfItvl on the collection of $s^{(i)}_\varepsilon$ values, bounded in $[-1/\varepsilon, 1/\varepsilon]$, with confidence level $\alpha$. This returns a lower and upper bound $(\gamma^-_\varepsilon, \gamma^+_\varepsilon)$ such that $P(\gamma^-_\varepsilon \leq \mathbb{E}[S_\varepsilon] \leq \gamma^+_\varepsilon) \geq 1-\alpha$. Only the upper bound $\gamma^+_\varepsilon$ is used, since the goal is to conservatively overestimate $\mathbb{E}[D_\varepsilon]$.

3. Use $\gamma^+_\varepsilon$ to rescale variance estimates at inference time: for a new input $X$, the $(1-\beta)$-confidence interval for $p_{Y|X}(1|X)$ is:

$p^\theta_{Y|X}(1|X) \pm \sqrt{\frac{\gamma^+_\varepsilon \cdot \max\\{\hat{V}^\theta(1|X), \varepsilon\\}}{\beta}}$

The subroutine MeanConfItvl: the paper provides two implementations:

• Hoeffding's inequality (Proposition D.3): simpler but more conservative. Returns $\gamma^+_\varepsilon = \bar{s}_\varepsilon + \sqrt{2 \cdot (-\log \alpha) / (N \cdot \varepsilon^2)}$ where $\bar{s}_\varepsilon$ is the sample mean of $s^{(i)}_\varepsilon$.

• Betting-based algorithm (confseq, Waudby-Smith & Ramdas, 2020): tighter bounds, especially for small $N$, but more computationally expensive. Used in the paper's 1D regression experiments (Appendix B) and shown to produce substantially narrower confidence intervals than Hoeffding.

Convergence behavior (Appendix B, Figures 14 and 15):

• As $N \to \infty$ and $\varepsilon \to 0$, if the model is second-order calibrated, $\gamma^+_\varepsilon \to 1$, and the distribution-free bound converges to the calibrated bound of Theorem 4.2.
• For miscalibrated models, $\gamma^+_\varepsilon > 1$ compensates for optimism in the variance estimates, but may be overly conservative if $\varepsilon$ is too small (leading to $S_\varepsilon$ values with large magnitude and slow convergence).
• Setting $\varepsilon$ too large effectively ignores the per-input variance estimates and produces a constant-width confidence interval based on the marginal variance of $p_{Y|X}$ across all $X$—a valid but uninformative bound.

How it circumvents Barber (2020): Barber proved that any distribution-free confidence interval for $p_{Y|X}$ constructed from single samples $(X, Y)$ must be wide enough to contain 0 or 1 with high probability. This is because a single sample can only identify the first moment of $p_{Y|X}$ conditioned on $\Phi(X)$. With paired samples $(X, Y_1, Y_2)$, the product of residuals $(Y_1 - \hat{p})(Y_2 - \hat{p})$ is an unbiased estimator of the squared deviation $(p_{Y|X} - \hat{p})^2$, which enables estimation of the second moment. The distribution-free bound therefore can be tight when the model is accurate and shrink with increased calibration data, whereas single-sample bounds fundamentally cannot.

4. Key Insights and Innovations

Innovation 1: Paired Data as an Escape Hatch from the Impossibility of Distribution-Free Epistemic Uncertainty Quantification

The paper's most fundamental conceptual move is identifying that the theoretical impossibility of distribution-free epistemic uncertainty quantification goes away when you collect two independent responses per input instead of one. This is not an incremental improvement—it is a diagnostic reframing that changes what is possible.

The field's prior state was defined by a negative result. Barber (2020) proved that, given only single $(X, Y)$ pairs, any distribution-free confidence interval for $p_{Y|X}(y|x)$ must also be a confidence interval for $Y$ itself—meaning the interval must contain 0 or 1 with high probability and cannot tightly bound the true conditional probability away from these extremes. This established a hard ceiling: without assumptions about $p_{Y|X}$, you fundamentally cannot distinguish between a model that knows the true probability and one that is guessing. Prior EUQ methods (ensembles, GPs, evidential deep learning) all implicitly worked within this limitation by making assumptions (Gaussian priors, parametric posteriors, smoothness) that could be violated in practice, as Figure 3 demonstrates.

The paper's reframing is that the impossibility is not about epistemic uncertainty per se—it is about the moment structure of the available data. Single samples $(X, Y)$ can only identify the first moment $\mathbb{E}[Y|X] = p_{Y|X}(1|X)$. To identify how far your prediction is from this expectation—which requires the second moment $\mathbb{E}[(Y - p_{Y|X}(1|X))^2|X]$—you need a second independent sample. The paired data $(X, Y_1, Y_2)$ enables estimation of the product of residuals $(Y_1 - \hat{p})(Y_2 - \hat{p})$, which is an unbiased estimator of $(p_{Y|X} - \hat{p})^2$. This is what makes distribution-free second-moment estimation possible, and it is what Algorithm 1 exploits to construct provably-correct confidence intervals without assumptions.

The significance of this goes beyond the specific method. It establishes that the key ingredient for honest epistemic uncertainty quantification is not a better prior or a more sophisticated architecture—it is data collection strategy. If you want models that know what they don't know, you need to collect multiple independent responses per query during training. This is a practical prescription (collect paired annotations, run paired simulations, query two experts) that reorients the research agenda away from purely architectural solutions toward data-centric ones.

The evidence for this claim is both theoretical (Theorem 4.6, which directly circumvents Barber's impossibility result by using paired data to construct distribution-free confidence intervals) and empirical (Section 6.1, where the cheat-corrected method achieves an ECE-2 of 0.009–0.022 on CIFAR-10H variants, compared to 0.039–0.521 for baselines that lack the paired-data signal). The connection between the theoretical escape and the practical gains is not coincidental—it is the same mechanism operating at different levels of formality.

Innovation 2: Cheating as an Operational Definition of Epistemic Uncertainty

The paper introduces a genuinely novel operational definition of epistemic uncertainty that does not rely on Bayesian posteriors, ensemble disagreement, or distributional assumptions. The core concept is that the gap between a model's marginal prediction and the true conditional distribution is exactly measured by how much the model can improve its prediction by observing an independent sample from that distribution.

This is a conceptual departure from how the field has typically thought about uncertainty. Prior EUQ methods are introspective: they examine the model's internal state (how much do ensemble members disagree? what is the posterior variance?) to estimate how much the model "believes" its prediction could be wrong. The problem, as Figure 3 makes vivid, is that when the model is misspecified, its introspections are themselves wrong—a GP with a too-smooth kernel genuinely "believes" it is certain, and reports low uncertainty accordingly.

The cheating framework is behavioral rather than introspective. It asks: "If I give you a peek at someone else's answer, can you do better?" If the answer is yes, then the model's original prediction was incomplete relative to the information available in the true process. The amount of improvement—the gap between the marginal $p^\theta_{Y_1|X}(y|x)$ and the self-conditioned $p^\theta_{Y_2|Y_1,X}(y|y,x)$—directly quantifies the epistemic gap without ever requiring the model to "know" that it's wrong. The model reveals its ignorance through its behavior, not its internal uncertainty estimates.

This reframing has several important properties that distinguish it from prior work:

• It is task-agnostic: the same operational procedure (score a response twice, compare the probabilities) works for classification, sequence generation, and sequential decision making (as demonstrated across CIFAR-10H, digits of $\pi$, and Frozen Lake) without any task-specific similarity metrics or correctness functions. This contrasts with methods like semantic uncertainty (Kuhn et al., 2022) that require defining equivalence classes over outputs, or verifier-based approaches (Cobbe et al., 2021) that require training separate scoring models.

• It separates aleatoric and epistemic uncertainty at the level of individual responses: the ratio $C^\theta_\text{Cheat}(y|x) = p^\theta_{Y_1|X}(y|x) / p^\theta_{Y_2|Y_1,X}(y|y,x)$ normalizes for how inherently unlikely $y$ is (aleatoric uncertainty), isolating whether the model is uncertain about this specific response beyond what chance alone would predict. This is a more fine-grained decomposition than methods that produce a single scalar uncertainty per input.

• It has an exact theoretical interpretation: when the model is calibrated, $C^\theta_\text{Cheat}(y|x) = 1$ if and only if $p^\theta_{Y|X}(y|x) = p_{Y|X}(y|x)$ (Proposition 4.4), and $\hat{V}^\theta_\text{Cheat}(y|x)$ is exactly the epistemic variance of $p_{Y|X}(y|X)$ across inputs the model groups together (Theorem 3.2). These are not approximations—they are identities that hold at the level of the model's grouping function.

The evidence for the effectiveness of this operational definition is most clearly visible in the difficulty-dependent results on CIFAR-10H (Table 1). When the task includes both extra classes (increased aleatoric noise) and scrambled images (increased epistemic uncertainty from underfitting), the cheat-corrected method's $\mathbb{E}[\hat{v}^\theta]$ rises from 0.052 to 0.134 (Cheat NN) or 0.054 to 0.153 (Cheat SNGP), tracking the true increase in $\mathbb{E}[(p^\theta - p)^2]$ from 0.068 to 0.154 (Cheat NN) or 0.052 to 0.150 (Cheat SNGP). The NN Ensemble, by contrast, reports $\mathbb{E}[\hat{v}^\theta] = 0.014$ in both settings, failing to detect the increased epistemic uncertainty despite its KL divergence rising from 0.15 to 0.65. The ensemble's introspective uncertainty estimate is blind to the quality of its own fit; the cheat-corrected measure is not.

This behavioral framing also explains the paper's relationship to other methods that use multiple samples. Techniques like self-consistency (Wang et al., 2022) or MBR decoding (Bertsch et al., 2023) compare multiple model-generated samples at inference time to improve outputs; they work because the model's own samples reveal patterns of agreement and disagreement. The cheat-corrected approach uses a similar logic but applies it to training-time data samples rather than inference-time model samples, enabling single-response evaluation with the same statistical power that multi-sample methods achieve only through repeated generation.

Innovation 3: Second-Order Calibration as a Formal Target That Unifies Pair Prediction and Epistemic Uncertainty

The paper introduces second-order calibration (Definition 2.3) as a principled extension of ordinary calibration that provides the formal bridge between the operational procedure (train on pairs) and the desired capability (quantify epistemic uncertainty). While the term "second-order calibration" has been used previously in different senses (Muralidharan & Najmi, 2015, for a parametric post-processing procedure), this paper gives it a precise, nonparametric definition with a direct link to pair prediction.

The definition is elegant in its simplicity: a second-order calibrated model reports, for each equivalence class of inputs that it cannot distinguish, both the average of the true probabilities and the covariance matrix of those probabilities. The diagonal entries of this covariance matrix are exactly the squared error between the model's prediction and the truth, aggregated over the equivalence class. This means a second-order calibrated model directly reports how wrong its own predictions might be, in units of squared probability.

What makes this definition powerful is not just its semantics but its operational accessibility. Theorem 3.2 establishes that second-order calibration is equivalent to first-order calibration over pairs, and the proof is a bijection—every second-order calibrated $(p^\theta_{Y|X}, \hat{\Sigma}^\theta)$ corresponds to a unique first-order calibrated pair predictor, and vice versa. This means that any technique for training calibrated models (cross-entropy minimization, temperature scaling, binning) can be directly applied to achieve second-order calibration simply by changing the target space from $\mathcal{Y}$ to $\mathcal{Y} \times \mathcal{Y}$. You do not need to design a new training objective for epistemic uncertainty—maximum likelihood on pairs naturally incentivizes it.

This formalization also clarifies the relationship to prior work in a way that the earlier literature lacked. The paper explicitly distinguishes its "second-order" (about second moments—variances and covariances of probabilities) from "second-order distributions" (about Dirichlet or Normal-Inverse-Wishart priors over simplex-valued parameters, as in Sensoy et al., 2018; Malinin & Gales, 2018). This distinction matters because the failure modes are different: second-order distribution predictors can be biased by their regularization terms (as Bengs et al., 2022, 2023 proved for evidential deep learning), whereas second-order calibration as defined here is parameterization-agnostic and judged purely by whether the reported variance matches the true squared error. The ECE-2 metric introduced in Section 6.1 operationalizes this judgment and provides a clear evaluation criterion that prior work lacked.

The evidence for the utility of this formalism is in the ECE-2 results (Table 1). The cheat-corrected models achieve ECE-2 of 0.009–0.022, compared to 0.039–0.521 for baselines. But beyond the numbers, the formalism explains why the baselines fail. Ensemble methods, for example, produce variance estimates that are first-order properties of the ensemble distribution—they reflect disagreements among ensemble members, which are themselves trained on the same data with the same inductive biases. When the ensemble as a whole underfits (as in the scrambled CIFAR-10H setting), the disagreement shrinks (to 0.014 for NN Ensemble in both settings) even though the true error grows (from 0.053 to 0.148). The ensemble is first-order calibrated in its own internal belief space, but it is not second-order calibrated with respect to the true $p_{Y|X}$ because it has no mechanism to detect that its belief space is misspecified.

The second-order calibration framework provides precise language for what was previously an intuitive critique of Bayesian and ensemble methods: they can be "subjectively calibrated" (their internal uncertainty matches their internal model of the world) while being "objectively miscalibrated" (their internal model of the world is wrong). Second-order calibration bridges this gap by requiring the uncertainty reports to reference the actual variation in the true process, not the model's beliefs about that variation.

Innovation 4: Difficulty-Aware Uncertainty That Distinguishes Underfitting from Accurate Estimation Without Out-of-Distribution Detection

A subtle but important conceptual contribution emerges from the empirical behavior of the cheat-corrected method in the 1D regression experiment (Figure 3 and the expanded Figure 18 in Appendix F). The method does not simply report higher uncertainty everywhere when the model underfits—it reports spatially localized uncertainty that concentrates where the model's predictions actually deviate from the truth.

This is not trivially achieved by existing methods. As Figure 3 shows:

• The Gaussian process reports low uncertainty everywhere, including in the underfit region near $x \approx 0$, because its smoothness prior leads it to believe the function is simple.
• Evidential deep learning reports high uncertainty everywhere, including near $x \approx 2.0$ where it actually fits well, because its regularization biases uncertainty estimates upward.
• The cheat-corrected NN reports low uncertainty where the model fits well ($|x| > 1$) and high uncertainty precisely in the region where it underfits ($x \approx 0$).

This localized behavior stems from the same mechanism that distinguishes the method from out-of-distribution detection techniques. The cheat-corrected measure responds to the covariance structure of $p_{Y|X}$ within the model's equivalence classes. In regions where the model has learned the correct average but fails to capture variation around that average, the pair covariance will be large (there are inputs with different true probabilities receiving the same prediction), and the cheat-corrected variance will detect this. This is fundamentally different from distance-aware methods like SNGP (Liu et al., 2020), which detect when an input is far from training data but cannot detect underfitting within densely sampled regions.

The practical implication is significant: it means the cheat-corrected method can identify that a model trained on abundant data for a particular region of input space is still making systematic errors in that region—a capability that is essential for detecting failures like racial or gender bias in well-sampled populations, or confounded predictions in environments where the model has plenty of data but the wrong features.

The evidence appears in both the controlled 1D setting (where the high-frequency variation near $x=0$ creates exactly this situation: dense sampling but structural underfitting) and the CIFAR-10H scrambled setting (where the model has seen many examples of the scrambled images but cannot process them effectively due to the violated convolutional inductive bias—the cheat-corrected method detects the resulting underfitting while the ensemble does not).

Innovation 5: The Confounder Detection Capability and Its Implications for Safe Decision-Making

The Frozen Lake experiment (Section 6.3, Figure 6) demonstrates a capability that goes beyond standard uncertainty quantification: the cheat-corrected method can detect when a model lacks information that is necessary for safe decision-making, and can adjust behavior accordingly without being explicitly told what information is missing. This is not just uncertainty estimation—it is a form of causal awareness that emerges from the pair-prediction training.

The setup is deliberately adversarial to naive imitation learning. The model sees the environment state $X$ but, 50% of the time, the unsafe patch location is hidden (replaced with "?" tokens). The expert demonstrations always avoid the unsafe patch (the expert knows where it is). A naive imitation learner trained to maximize likelihood on single trajectories would learn to cross the lake randomly when the patch is hidden—sometimes safely, sometimes fatally—because it cannot distinguish between the two cases and averages over them. This is the "self-delusion" problem identified by Ortega et al. (2021).

The pair-prediction model behaves differently. Because it is trained on pairs of trajectories that share the same unsafe patch location (the hidden confounder), it learns to cheat by conditioning on $Y_1$ when predicting $Y_2$. When the patch is visible, the model can predict trajectories accurately without cheating because $X$ contains all relevant information—$p^\theta_{Y_1|X}$ already matches the expert distribution, and conditioning on an observed trajectory provides no additional benefit. When the patch is hidden, the model cannot predict the exact trajectory from $X$ alone (since it doesn't know which paths are safe), but it can condition on a generated trajectory to assess its consistency—and it learns to assign low cheat-corrected confidence to any trajectory that crosses the lake, because such trajectories are only safe for some hidden patch locations and not others.

The result (Figure 6) is that the cheat-corrected rejection sampling and top-1 search strategies automatically avoid all lake-crossing trajectories when the patch is hidden, even though the model was never explicitly told which actions are unsafe. The model doesn't know the patch location, but it knows that it doesn't know, and it knows which actions depend on the missing information.

This connects to a broader principle about partial observability and misspecification that the paper articulates in Appendix C: training a calibrated pair predictor is roughly equivalent to having an optimal predictor that conditions on whatever information is shared between $Y_1$ and $Y_2$. If a hidden variable $Z$ (like the unsafe patch location) influences both expert trajectories, the pair predictor must learn to implicitly condition on $Z$ to make calibrated predictions, and this implicit conditioning reveals itself through the cheating behavior. The cheat-corrected confidence then flags actions whose safety depends on the hidden $Z$, even though $Z$ is never explicitly modeled or inferred.

This is a fundamentally different approach to safe imitation learning under confounding compared to methods that require explicit modeling of the confounder (Warrington et al., 2020) or that require on-policy data collection (Ortega et al., 2021). The pair-prediction approach requires only paired expert demonstrations at training time—a data collection requirement that may be practical in many settings. It does not require the model to represent or infer the confounder, only to detect its influence on the correlation structure of generated trajectories.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The empirical validation spans three distinct tasks, each designed to test different aspects of the method:

  • CIFAR-10H (Peterson et al., 2019): the CIFAR-10 test set relabeled by >50 independent annotators per image, producing a distribution over class labels for each of 10,000 images. The paper splits these into 3,000 for finetuning, 2,000 for validation, and 5,000 for test evaluation. CIFAR-10N (Wei et al., 2021) provides 50,000 pretraining images, each with three annotator labels. Two dataset variants are introduced: "Extra Classes" (increases aleatoric noise by splitting each of the 10 classes into 3 subclasses with Dirichlet-sampled probabilities, producing a 30-way classification) and "Scrambled" (applies a fixed permutation to center pixels, increasing epistemic uncertainty due to violated convolutional inductive biases). A combined "Extra + Scrambled" variant applies both.

  • Digits of π: a synthetic language modeling task where queries request information about specific digits of π (e.g., "Tell me about digit 0236 of pi."), with digit offsets sampled from a mixture of geometric distributions favoring early digits. Responses are generated from a hand-written probabilistic context-free grammar producing true statements about the digit's value, parity, spelling, or letter count, with multiple valid phrasings and stylistic variations. The ground-truth distribution $p_{Y|X}$ is known exactly, enabling precise measurement of whether generated samples are statistical hallucinations ($p_{Y|X}(y|x) = 0$).

  • Frozen Lake (Warrington et al., 2020): a 5×5 gridworld where agents navigate from start to goal, with the possibility of taking shortcuts across a frozen lake. In each episode, one of nine possible lake tiles is randomly designated as unsafe (instant failure if entered); expert policies (computed via entropy-regularized soft Q-learning) always avoid this tile. The model observes the grid with the unsafe patch either visible (50% of episodes) or hidden behind "?" tokens.

• Base model(s). For CIFAR-10H, all methods use a Wide ResNet backbone (Zagoruyko & Komodakis, 2016) with depth 28 and width multiplier 10. The Cheat NN variant uses standard convolutional layers, while Cheat SNGP incorporates spectral normalization and a 1024-dimensional random-feature output layer following Liu et al. (2020). For digits of π, a 6-layer pre-LayerNorm Transformer (Vaswani et al., 2017; Xiong et al., 2020) with 8 attention heads, embedding dimension 512, and MLP dimension 2048 (approximately 19M parameters) is trained from scratch. For Frozen Lake, a 12-layer GPT-2-style Transformer (Radford et al., 2019) with 12 attention heads, embedding dimension 768, and MLP dimension 3072 (approximately 85M parameters) is used. All models are trained with the standard maximum-likelihood objective on the paired data format, with no architectural modifications beyond the output layer.

• Metrics. The primary evaluation metric for CIFAR-10H is second-order expected calibration error (ECE-2): the difference between each method's reported epistemic variance $\hat{V}^\theta$ and the actual squared error $(p^\theta_{Y|X} - p_{Y|X})^2$, computed by averaging over 100 equal-probability quantile bins of predicted variance, then summing across classes. Supporting metrics include: ECE-1 (ordinary calibration error of the marginal predictions, computed identically but comparing $p^\theta_{Y|X}$ to empirical label frequencies), KL divergence between the model's marginal prediction and the empirical annotator distribution, top-1 accuracy relative to clean CIFAR-10 labels, and the raw expectations $\mathbb{E}[\hat{v}^\theta]$ and $\mathbb{E}[(p^\theta - p)^2]$. For digits of π, the primary metric is the statistical hallucination rate: the fraction of generated responses for which $p_{Y|X}(y|x) = 0$ (responses that could never be generated by the true grammar for that digit), evaluated across 120 samples per digit for offsets 1–3000. For Frozen Lake, evaluation is qualitative: visualization of whether the model's decoding strategies safely avoid lake-crossing trajectories when the unsafe patch is hidden.

• Baselines. For CIFAR-10H, five baselines are compared:

  • Naive NN: uses $p^\theta(1-p^\theta)$ as the variance estimate, treating all uncertainty as epistemic (assuming $Y$ is deterministic given $X$).
  • NN Ensemble (Lakshminarayanan et al., 2016): 8 independently-trained copies of the Wide ResNet, with empirical mean and (unbiased) variance across ensemble members as prediction and epistemic uncertainty.
  • Evidential DL (Sensoy et al., 2018): outputs Dirichlet concentration parameters $\alpha(x) = 1 + \text{softplus}(h_\theta(x))$ trained with a regularized cross-entropy loss; epistemic uncertainty is the variance of predicted probabilities under $\text{Dirichlet}(\alpha(x))$.
  • SNGP Cov. (Liu et al., 2020): spectral-normalized Wide ResNet with a 1024-dimensional random-feature Gaussian process output layer; posterior covariance is approximated via Laplace approximation after training.
  • Epinet (Osband et al., 2021): augments the Wide ResNet with an MLP head taking a random 20-dimensional "index" vector, trained to produce diverse predictions; epistemic uncertainty is the variance across 1000 sampled index vectors at test time.

  For digits of π, baselines include: Total LP (ranking by sample log-probability), Avg. Token LP (Malinin & Gales, 2020; length-normalized log-probability), and Clustered (Kuhn et al., 2022; Li et al., 2022a; grouping 120 samples into either 12 groups of 10 or one group of 120, scoring by the number of semantically-equivalent samples in the same group).

• Generation budget / compute accounting. For CIFAR-10H, all methods are trained under comparable conditions: same Wide ResNet backbone, same number of training epochs (50 for pretraining on CIFAR-10N, 30–200 for finetuning on CIFAR-10H, chosen by hyperparameter sweep), same batch size (512). The pair-prediction models process the same number of individual label samples as the baselines (two per example per batch for the cheat models versus two separate minibatch examples for single-prediction baselines), making the per-iteration cost comparable. For digits of π and Frozen Lake, pair-prediction models train on concatenated sequences ($Y_1$ followed by $Y_2$) with a <SEP> token, doubling the effective sequence length relative to single-response training, but this cost is incurred only at training time. At inference, the cheat-corrected metrics require only a single forward pass scoring the concatenated sequence $(x, y, y)$.

• Cross-validation / statistical protocol. CIFAR-10H results are averaged over eight independent training runs with different random seeds; Table 3 reports both mean and standard deviation for all metrics. Hyperparameter tuning uses a validation set (2,000 images from CIFAR-10H) distinct from the test set; the best configuration (chosen by validation KL divergence) is then retrained on the combined training + validation set before final evaluation. For the digits of π task, all 120 samples per digit are used for evaluation, with no train/test split (the model has seen all digit offsets during training but the hallucination criterion tests whether generated statements are true for each specific digit). For Frozen Lake, evaluation is qualitative with no statistical protocol reported.

Main Quantitative Results

Second-Order Calibration on CIFAR-10H

The central empirical finding for CIFAR-10H, shown in Table 1, is that the cheat-corrected variance estimates are substantially better second-order calibrated than all baselines, while maintaining comparable or superior first-order calibration and predictive accuracy.

On the original CIFAR-10H dataset, the Cheat SNGP model achieves an ECE-2 of 0.009 ± 0.002, compared to 0.039 ± 0.000 for NN Ensemble (the best non-cheat baseline) and 0.377 ± 0.001 for Evidential DL (the worst). The Cheat NN model achieves 0.018 ± 0.001. The epistemic variance predicted by the cheat models tracks the true squared error more closely: for Cheat SNGP, $\mathbb{E}[\hat{v}^\theta] = 0.054$ versus $\mathbb{E}[(p^\theta - p)^2] = 0.052$, a difference of only 0.002; for NN Ensemble, the corresponding values are 0.014 versus 0.053—the ensemble systematically underestimates epistemic uncertainty by a factor of ~3.8×. The Naive NN overestimates ($\mathbb{E}[\hat{v}^\theta] = 0.142$ vs. $\mathbb{E}[(p^\theta - p)^2] = 0.065$), while Evidential DL produces a moderate mean estimate (0.053) but with an ECE-2 of 0.377, indicating poor bin-wise calibration (it reports similar variance across all predictions despite true errors varying).

On the Extra Classes + Scrambled variant (increased aleatoric and epistemic difficulty), the results in Table 1 reveal a critical distinction: the cheat-corrected methods detect the increased epistemic uncertainty, while the ensemble does not. For Cheat SNGP, $\mathbb{E}[\hat{v}^\theta]$ rises from 0.054 to 0.153, closely tracking the increase in $\mathbb{E}[(p^\theta - p)^2]$ from 0.052 to 0.150. The NN Ensemble reports $\mathbb{E}[\hat{v}^\theta] = 0.014$ in both settings, completely blind to the degradation in its own predictions (KL divergence rises from 0.15 to 0.65). The Cheat SNGP's ECE-2 on this harder variant is 0.011 ± 0.001, nearly identical to its performance on the original dataset (0.009 ± 0.002), whereas the NN Ensemble's ECE-2 degrades from 0.039 to 0.134, and Naive NN degrades from 0.076 to 0.521. Evidential DL shows the opposite pattern: its ECE-2 remains poor in both settings (0.377 original, 0.387 harder), and its variance estimates (0.053 → 0.031) actually decrease as the model's true error increases (0.430 → 0.418), a behavior consistent with the bias identified by Bengs et al. (2022, 2023).

First-order calibration (ECE-1) and predictive accuracy are maintained across all cheat models: Cheat SNGP achieves ECE-1 of 0.022 (original) and 0.044 (harder), comparable to SNGP Cov. (0.020) and NN Ensemble (0.029, 0.032) and substantially better than Evidential DL (1.038, 0.794). Accuracy on clean CIFAR-10 labels is identical between Cheat SNGP and SNGP Cov. (94.9% on original) and slightly lower for Cheat NN (93.6%) versus Naive NN (93.9%), demonstrating that pair-prediction training does not degrade standard performance.

Table 4 shows results for the intermediate task variants (Extra Classes only and Scrambled only). On Extra Classes alone, all methods except Naive NN and Epinet maintain ECE-2 ≤ 0.054; the Cheat SNGP achieves 0.009 and SNGP Cov. achieves 0.017. On Scrambled alone, epistemic uncertainty is elevated for all methods (true $\mathbb{E}[(p^\theta - p)^2]$ ranges 0.285–0.314), but the Cheat SNGP again achieves the best ECE-2 (0.029) with variance estimates ($\mathbb{E}[\hat{v}^\theta] = 0.280$) closely matching the true error ($\mathbb{E}[(p^\theta - p)^2] = 0.286$). The NN Ensemble underestimates dramatically (0.028 vs. 0.289), and Naive NN overestimates (0.354 vs. 0.314).

Hallucination Detection on Digits of π

Figure 5 (left) validates the theoretical bound from Theorem 4.5: binned by predicted confidence $C^\theta_\text{Cheat}$, the hallucination rate (fraction of samples with $p_{Y|X}(y|x) = 0$) is generally ≤ $1 - C^\theta_\text{Cheat}$, as predicted. The paper notes that this relationship holds "usually," but identifies a miscalibration phenomenon: for some samples, $C^\theta_\text{Cheat} > 1$, which cannot occur for a calibrated model (Proposition 4.4). Samples with confidence slightly above 1 are usually correct (the model's self-conditioned probability is lower than its marginal, indicating the originally-sampled $Y_1$ was itself a low-probability mistake), but in rare cases very large values of $C^\theta_\text{Cheat}$ (approximately $10^4$ or larger) occur for malformed, out-of-distribution samples. The paper's practical recommendation is to threshold on $|1 - C^\theta_\text{Cheat}|$ rather than $1 - C^\theta_\text{Cheat}$ to handle these outliers conservatively.

Figure 5 (right) shows that ranking samples by $|1 - C^\theta_\text{Cheat}(y|x)|$ achieves a similar or lower hallucination rate than common filtering strategies when controlling the fraction of responses generated. At a response rate of approximately 0.6 (60% of all samples kept), the cheat-corrected ranking produces a hallucination rate of approximately 0.05, compared to roughly 0.08 for Clustered (k=120) and approximately 0.12 for Clustered (k=10). Total LP and Avg. Token LP plateau at substantially higher hallucination rates (roughly 0.18–0.22 at response rate 0.6). At very low response rates (0.1–0.2), all methods converge to hallucination rates below 0.02, but the cheat-corrected metric reaches this regime with fewer samples rejected—it keeps roughly 75% of samples while maintaining hallucination rate below 0.05, whereas Clustered (k=120) would need to reject approximately 60% of samples to achieve the same rate.

Figure 26 (Appendix F.3.3) explores alternative thresholding strategies for handling $C^\theta_\text{Cheat} > 1$: $1 - C^\theta_\text{Cheat}$ alone, $|1 - C^\theta_\text{Cheat}|$, $1 - \min\{1, C^\theta_\text{Cheat}\}$, and $1 - \min\{C^\theta_\text{Cheat}, 1/C^\theta_\text{Cheat}\}$. Using $1 - C^\theta_\text{Cheat}$ alone leads to high hallucination rates at strict thresholds because the only samples kept are the outliers with very large $C^\theta_\text{Cheat}$; the absolute value and other symmetric thresholds avoid this failure mode.

Figure 27 (Appendix F.3.5) shows that predicted epistemic confidence, after removing outlier samples with very large $C^\theta_\text{Cheat}$ values, closely tracks the model's actual accuracy. When aggregating over groups of 40 consecutive digit offsets (rows 3–4), the average confidence closely follows the fraction of correct samples, with both declining as digit offset increases (reflecting the geometric sampling distribution—later digits are rarer in training and thus less well-learned). For digit offsets 1–200 (the most frequent in training), average confidence is approximately 0.85 and correctness fraction approximately 0.90; by offsets 2500–3000, confidence declines to approximately 0.35 and correctness to approximately 0.25.

Confounder-Aware Decision Making in Frozen Lake

Figure 6 presents qualitative results for the two cheat-corrected decoding strategies (rejection sampling and top-1 search, both with threshold $|1 - C^\theta_\text{Cheat}| \leq 0.05$). When the unsafe patch is visible (left column), both strategies behave similarly to their non-cheat-corrected counterparts: rejection sampling produces diverse trajectories including lake-crossing paths, and top-1 search deterministically selects the shortest lake-crossing path (the highest-probability trajectory under the model's marginal $p^\theta_{Y_1|X}$). When the unsafe patch is hidden (right column), both strategies automatically avoid all lake-crossing trajectories. The cheat-corrected rejection sampling rejects any sampled path that crosses the lake (shown as dashed lines) and only accepts paths that go around the safe border. The cheat-corrected top-1 search selects a border-hugging safe path as the highest-likelihood response satisfying the confidence constraint, even though lake-crossing paths have higher marginal probability.

Additional samples shown in Figures 11–13 (Appendix A) confirm this behavior across different unsafe patch locations (bottom-left, middle-right) and for the hidden-patch case. The model assigns $C^\theta_\text{Cheat}$ values consistently above 0.95 for safe trajectories and variable but generally lower values for lake-crossing trajectories when the patch is hidden (Figure 13). In the fully-observable case (Figures 11–12), the confidence values are consistently high for all valid trajectories regardless of whether they cross the lake, confirming that the drop in confidence is specifically driven by the hidden confounder, not by any inherent property of lake-crossing actions.

The paper reports that the cheat-corrected rejection sampling with the $|1 - C^\theta_\text{Cheat}| \leq 0.05$ constraint sometimes rejects safe trajectories as well (Figures 11–12 show occasional dashed safe paths), indicating that the threshold achieves safety at some cost in false rejections—a standard precision-recall tradeoff.

Ablation Studies and Robustness Checks

Extra Classes variant (increased aleatoric noise): When the CIFAR-10H task is modified to include 30 subclasses with Dirichlet-sampled label noise (Table 4), the cheat-corrected models (Cheat NN: ECE-2 = 0.010, Cheat SNGP: ECE-2 = 0.009) and the NN Ensemble (ECE-2 = 0.020) all maintain good second-order calibration. This demonstrates that the aleatoric noise injection does not impair the epistemic uncertainty estimates—the models correctly recognize that the stochasticity comes from the label process rather than from underfitting. Naive NN's ECE-2 rises to 0.540, as expected since its variance estimator conflates aleatoric and epistemic uncertainty.

Scrambled variant (increased epistemic uncertainty from misspecification): When center pixels are permuted (Table 4), the true squared error $\mathbb{E}[(p^\theta - p)^2]$ increases substantially for all methods (0.285–0.314 vs. 0.052–0.071 on original). Cheat SNGP's variance estimates rise to match ($\mathbb{E}[\hat{v}^\theta] = 0.280$ vs. $\mathbb{E}[(p^\theta - p)^2] = 0.286$), while the NN Ensemble's estimates remain collapsed ($\mathbb{E}[\hat{v}^\theta] = 0.028$ vs. $\mathbb{E}[(p^\theta - p)^2] = 0.289$). This is the paper's strongest evidence that ensemble-based epistemic uncertainty fails under misspecification, even when individual ensemble members are well-trained: the ensemble disagreement disappears because all members converge to the same wrong solution, a failure mode that the cheat-corrected method avoids because it draws its uncertainty signal from the data (via the paired response structure) rather than from model disagreement.

Extra Classes + Scrambled combined: As reported in the main results, Cheat SNGP maintains ECE-2 of 0.011, nearly identical to its original-dataset performance, while NN Ensemble degrades to 0.134.

Eigenvalue regularization for pair predictors: The paper reports that pair prediction models on CIFAR-10H "occasionally overfit on the small dataset and produced negative $\hat{V}^\theta_\text{Cheat}$ estimates due to miscalibration" (Section 6.1). A penalty of $\alpha \sum_{i=1}^K \max\{0, -\lambda_i(x)\}^2$ with $\alpha = 10.0$ is added to the loss for negative eigenvalues of the post-softmax joint probability matrix $\hat{P}[x]$. No ablation of $\alpha$ is reported, but the strong performance of Cheat SNGP (which achieves better calibration without this regularization, relying instead on the distance-awareness inductive biases of the SNGP architecture) suggests that the regularization is effective but that spectral normalization provides an alternative path to preventing negative variance estimates.

SNGP backbone vs. standard backbone: Across all CIFAR-10H variants, the Cheat SNGP model consistently outperforms Cheat NN in ECE-2 (0.009 vs. 0.018 original; 0.011 vs. 0.022 harder; 0.009 vs. 0.010 Extra Classes; 0.029 vs. 0.056 Scrambled). The paper attributes this to the SNGP architecture's distance-awareness inductive biases (Liu et al., 2020) improving first-order calibration, which in turn improves second-order calibration when training on pairs.

Hoeffding vs. confseq for distribution-free bounds: For the 1D regression distribution-free adjustment (Appendix B, Figures 14–15), the confseq algorithm (Waudby-Smith & Ramdas, 2020) produces substantially tighter upper bounds on $\mathbb{E}[D_\varepsilon]$ than Hoeffding's inequality. With a calibration set of $10^6$ examples and $\varepsilon = 0.02^2$, confseq converges to $\gamma^+_\varepsilon \approx 1.2$, while Hoeffding requires approximately $10^9$ examples to achieve the same bound. However, the confseq bounds are more computationally expensive and exhibit discrete jumps due to the finite hypothesis set. The paper recommends confseq for calibration sets of moderate size.

Variance threshold $\varepsilon$ in Algorithm 1: As $\varepsilon \to 0.001^2$, the bound blows up ($\gamma^+_\varepsilon \gg 10$) because the model is imperfectly calibrated, so the normalized score $s^{(i)}_\varepsilon$ takes extreme values (bounded by $\pm 1/\varepsilon$) and the confidence interval on its mean converges slowly. As $\varepsilon \to 0.5^2$, the bound becomes constant-width everywhere, ignoring the per-input variance estimates and using only the marginal variance of $p_{Y|X}$ across all $X$. The paper notes that this tradeoff is fundamental: smaller $\varepsilon$ allows the bound to be tighter where the model is confident but requires better calibration and larger calibration sets.

Alternative confidence scoring for $C^\theta_\text{Cheat} > 1$: Figure 26 (Appendix F.3.3) shows that four strategies for handling out-of-range confidence values produce qualitatively similar hallucination-rate vs. response-rate curves, with $|1 - C^\theta_\text{Cheat}|$ and $1 - \min\{C^\theta_\text{Cheat}, 1/C^\theta_\text{Cheat}\}$ producing slightly better results at high response rates than $1 - \min\{1, C^\theta_\text{Cheat}\}$ or raw $1 - C^\theta_\text{Cheat}$.

Evidential DL regularization strength $\lambda_{\max}$: Appendix F.1.2 (Figure 16) shows that the reported epistemic variance of the Evidential DL method is highly sensitive to the maximum KL regularization strength, with no value of $\lambda_{\max}$ producing estimates that accurately track underfitting. This negative result reinforces the paper's argument that second-order calibration is not incentivized by the evidential loss.

Critical Assessment

What the Experiments Demonstrate

The CIFAR-10H experiments demonstrate a clear and consistent result: for image classification with human annotator label noise, the cheat-corrected variance estimates achieve substantially better second-order calibration than five representative baselines spanning different uncertainty quantification paradigms, while maintaining comparable first-order calibration and accuracy. The effect is robust across eight training seeds (Table 3) and across four dataset variants (original, Extra Classes, Scrambled, Extra + Scrambled). The distinguishing result is not that the cheat-corrected method always produces perfect estimates—the ECE-2 values of 0.009–0.029 are small but not zero—but rather that it is the only method whose variance estimates track the true squared error when epistemic uncertainty increases (Scrambled variants), whereas ensemble and SNGP methods systematically underestimate uncertainty under misspecification.

The digits of π experiment demonstrates that the theoretical hallucination bound (Theorem 4.5) holds approximately in practice for a sequence modeling task with a combinatorially large output space, and that the cheat-corrected confidence ranking outperforms common heuristic filtering strategies (log-probability, length-normalized log-probability, semantic clustering) at identifying hallucinated responses. The Frozen Lake experiment provides a qualitative proof of concept that the method can detect hidden confounders and enable safe decision-making even when the model has no explicit representation of the missing information.

Genuine Weaknesses and Limitations

Single model family across all experiments: The Wide ResNet and Transformer architectures used are standard, but no experiments compare across substantially different model families (e.g., convolutional vs. vision transformer for images, autoregressive vs. encoder-decoder for sequences). The method's effectiveness may depend on architectural inductive biases that affect how easily a model learns to exploit the cheating signal. For example, the Cheat SNGP variant consistently outperforms Cheat NN on CIFAR-10H, suggesting that architectural choices matter, but only one alternative backbone is tested.

Small test set for CIFAR-10H: The 5,000-image test set, while standard for CIFAR-10H evaluations, limits the precision of calibration error estimates when splitting into 100 bins (approximately 50 examples per bin when aggregating across all classes). The paper's ECE-2 estimates have standard deviations of 0.001–0.003 across eight seeds (Table 3), indicating reasonable precision, but differences of 0.01 in ECE-2 between methods (e.g., Cheat SNGP at 0.009 vs. NN Ensemble at 0.039) are larger than these error bars, supporting the claimed ranking.

No comparison to conformal prediction under paired data: While the paper's distribution-free adjustment (Algorithm 1) is positioned as circumventing Barber (2020), no comparison is made to a hypothetical conformal prediction method that also has access to paired calibration data. A conformal predictor with paired data could potentially construct prediction sets by calibrating a nonconformity score based on $(Y_1 - \hat{p})(Y_2 - \hat{p})$; whether such a method would produce tighter or looser intervals than Algorithm 1 is unknown. This is a missing baseline that would clarify whether the paper's specific estimator is optimal or merely sufficient.

The digits of π task is synthetic and fully controlled: While this enables clean measurement of statistical hallucinations, it does not demonstrate the method on real language modeling data where the true $p_{Y|X}$ is unknown and where the types of miscalibration differ (e.g., long-tail token frequency issues, factual knowledge gaps, prompt-format sensitivity). The paper does not run any experiment on a standard NLP benchmark with real text data.

No experiment on regression tasks: All experiments use discrete $\mathcal{Y}$. The paper's theoretical framework (Section 2, Definition 2.3) is presented for discrete output spaces only. Extension to continuous $\mathcal{Y}$ would require approximating or parameterizing the joint pair density, and it is unclear whether the cheat-corrected metrics have natural continuous analogs.

Frozen Lake evaluation is purely qualitative: No quantitative metric is reported for the Frozen Lake experiment—there is no measurement of safe trajectory rate, false rejection rate, or comparison to alternative safe imitation learning methods (e.g., Warrington et al., 2020; Ortega et al., 2021). The qualitative demonstration in Figure 6 shows that the method can detect confounders, but provides no evidence about how reliably it does so across random seeds, environment configurations, or threshold choices.

Calibration set size for distribution-free bounds is not studied in context: Algorithm 1's guarantees are presented theoretically and demonstrated on the 1D synthetic regression (Appendix B), but the algorithm is not applied to CIFAR-10H, digits of π, or Frozen Lake. All three main experiments rely on the model being approximately calibrated, with no distribution-free correction. This means the reported hallucination bounds for digits of π and the safe behavior for Frozen Lake are not accompanied by any formal statistical guarantee—they are demonstrations that the method works when the model is well-calibrated, but provide no protection against miscalibration in deployment. The paper acknowledges this implicitly by developing Algorithm 1 and then not using it in the headline experiments.

The effect of paired data quantity: All CIFAR-10H experiments use the full CIFAR-10N pretraining set (50,000 images × 3 annotators) and the CIFAR-10H finetuning sets. No ablation varies the number of paired examples to determine the sample complexity of learning good cheat-corrected estimates. If paired data is expensive (e.g., requiring two human annotators per example), knowing whether 100, 1,000, or 50,000 paired examples are needed would be practically essential.

Negative variance estimates are addressed with heuristics: The eigenvalue regularization on CIFAR-10H and the absolute-value threshold on digits of π are practical patches for miscalibration, but neither is theoretically principled. The paper does not characterize how often negative variances occur, how large the regularization penalty needs to be, or whether these heuristics interact with the model's primary objective in ways that could degrade either first-order or second-order calibration.

Experiments That Would Have Strengthened the Paper

• A real language modeling benchmark (e.g., TriviaQA, Natural Questions, or a summarization task) with paired reference responses (multiple human-written answers per query) would directly demonstrate the method's applicability to the hallucination problems that motivate the work. The digits of π experiment shows the mechanism works for sequences, but does not show it works for natural language sequences with their much richer correlation structure.

• A head-to-head comparison with conformal prediction using paired calibration data, to establish whether the cheat-corrected confidence metric provides tighter prediction sets or lower hallucination rates than a conformal baseline that also exploits the paired structure.

• Ablation of paired data quantity across at least two orders of magnitude (e.g., 100 vs. 1,000 vs. 10,000 paired examples) on CIFAR-10H or a synthetic task, to establish the sample efficiency of the method.

• Quantitative Frozen Lake results reporting safe trajectory rate, false rejection rate, and comparison to the robust imitation learning method of Warrington et al. (2020) or the causal approach of Ortega et al. (2021).

• Application of Algorithm 1 to the digits of π task, to demonstrate the distribution-free bound in a high-dimensional output space and measure how much wider the corrected confidence intervals become relative to the uncalibrated cheat-corrected estimates.

6. Limitations and Trade-offs

Practical Cost of Paired Data Collection

The assumption or constraint: The method requires, at training time, two independent responses $Y_1, Y_2$ drawn from $p_{Y|X}(\cdot|X)$ for each input $X$. The paper states this requirement clearly:

"this technique fundamentally assumes that $Y_1$ and $Y_2$ are independent and identically distributed according to $p_{Y|X}(\cdot|X)$ for each $X$" (Appendix C)

and acknowledges that "paired responses may not be available for all datasets" (Section 7). Collecting paired data means querying two human annotators per example, running two independent simulations per environment, or sampling two expert trajectories per state—a 2× or greater increase in data collection cost relative to standard single-response training.

The consequence: For many existing datasets and applications, paired response data does not exist and cannot be retroactively collected. Single-annotator datasets (the vast majority of NLP and vision benchmarks) are incompatible with the method. Even when paired data could in principle be collected, the cost may be prohibitive: doubling annotator time for every example in a large-scale dataset, or requiring paired expert demonstrations in sequential decision settings where experts are scarce. The paper provides no guidance on whether interpolation between single-response and paired-response regimes is possible—for example, training partially on paired data and partially on single data, or using the method when only a subset of examples have multiple annotations.

What evidence exists in the paper: The paper does not measure the relationship between the quantity or quality of paired data and the resulting second-order calibration. All experiments use full paired datasets: CIFAR-10H has >50 annotators per image, CIFAR-10N has 3 annotators per image, the digits-of-π task generates paired responses synthetically, and Frozen Lake samples paired expert trajectories. No ablation varies the number of paired examples (e.g., 10% paired + 90% single vs. 100% paired), and no experiment uses real-world data where paired responses are noisy or inconsistently available. The method's sensitivity to violations of the i.i.d. assumption (e.g., annotators with correlated biases, simulations with shared random seeds) is not studied.

Mitigation status: Not addressed. The paper acknowledges the limitation in Section 7 and Appendix C but provides no empirical characterization of the paired-data requirement. The discussion in Appendix C does note that third-variable approaches (like Collier et al., 2022, using annotator IDs as privileged information) could potentially "explain away" some aleatoric variation without requiring strict pairwise independence, but this connection is not developed theoretically or empirically.

---

Miscalibration Causes Negative Variance Estimates and Confidence Values Exceeding 1, with Only Heuristic Fixes

The assumption or constraint: The theoretical guarantees in Theorems 4.2, 4.4, and 4.5 all assume the pair predictor $p^\theta_{Y_1,Y_2|X}$ is perfectly calibrated. The paper acknowledges that, in practice, models may not achieve this:

"We observed that our models occasionally overfit on the small dataset and produced negative $\hat{V}^\theta_\text{Cheat}$ estimates due to miscalibration" (Section 6.1)

and for the digits-of-π task:

"we observe that $C^\theta_\text{Cheat}(y|x) > 1$ for some samples, which would not occur for a well-calibrated model" (Section 6.2)

The consequence: When the model is miscalibrated, the cheat-corrected metrics lose their theoretical interpretation. $\hat{V}^\theta_\text{Cheat}$ can become negative (violating the variance interpretation), $C^\theta_\text{Cheat}$ can exceed 1 (violating the confidence normalization in Proposition 4.4), and the hallucination bound of Theorem 4.5 no longer holds. In the digits-of-π task, samples with very large $C^\theta_\text{Cheat}$ values (approximately $10^4$ or larger) are "usually malformed and out-of-distribution" (Section 6.2), meaning the confidence metric fails most severely on exactly the kind of degenerate outputs that a hallucination detector should flag. The paper's recommendation to use $|1 - C^\theta_\text{Cheat}|$ as a threshold is a heuristic that "is equivalent if the model is calibrated" but has no theoretical justification when the model is not.

This matters because the deployment scenarios that motivate the work—detecting hallucinations in language models, avoiding unsafe actions in RL—are precisely those where the model is likely to be miscalibrated due to distribution shift, out-of-distribution inputs, or capacity limitations. A user cannot know whether their model is sufficiently calibrated for the guarantees to hold without access to ground-truth $p_{Y|X}$, which defeats the purpose.

What evidence exists in the paper: The paper directly observes the problem in both the CIFAR-10H and digits-of-π experiments. On CIFAR-10H, the eigenvalue regularization with $\alpha = 10.0$ is applied to prevent negative variance, but no ablation varying $\alpha$ or measuring how often negative eigenvalues would occur without regularization is provided. On digits of π, Figure 5 (left) shows that the theoretical bound $1 - C^\theta_\text{Cheat}$ holds "usually" but not always, and the discussion of Figure 26 (Appendix F.3.3) shows that different heuristic thresholding strategies produce different hallucination-rate vs. response-rate tradeoffs. The paper does not report what fraction of samples in either experiment violate the calibrated bounds, nor does it report the magnitude of the violations.

Mitigation status: Partially addressed by two heuristics, neither of which is theoretically principled. First, the eigenvalue regularization on CIFAR-10H penalizes negative eigenvalues but does not guarantee positive semidefiniteness—it is a soft constraint whose effectiveness depends on the regularization strength $\alpha$. Second, the $|1 - C^\theta_\text{Cheat}|$ thresholding for the digits-of-π task is a practical patch that empirically reduces hallucination rates (Figure 5, right) but provides no formal guarantee. Algorithm 1 offers a distribution-free correction for binary $\mathcal{Y}$, but this requires a held-out calibration set of paired data and is not applied to any of the multi-class or sequence experiments. The paper identifies miscalibration as "an exciting area for future work" (Appendix E) but does not propose architectural improvements for sequence models.

---

No Quantitative Evaluation on Real Language Tasks or Standard NLP Benchmarks

The assumption or constraint: The paper's motivating applications focus on language model hallucination:

"Missing information can cause even well-trained models to 'hallucinate' incorrect claims" (Section 1)

and the method is positioned as applicable to "tasks with large output spaces such as sequence modeling" (Section 6.2). However, the only language experiment (digits of π) uses a synthetic context-free grammar with a small closed vocabulary and known ground-truth probabilities. No experiment uses real text data, standard NLP benchmarks, or pretrained language models.

The consequence: The paper does not demonstrate that the cheat-corrected metrics remain calibrated or practically useful when applied to natural language. Real language has properties absent from the synthetic task: extremely long-tailed token distributions, compositional semantics, factual knowledge that interacts with linguistic form, and open-ended generation where "correctness" is not well-defined. The digits-of-π task has exactly correct/incorrect answers, a vocabulary of approximately 50 tokens, and a clean separation between epistemic uncertainty (which digit is being asked about and what are its properties) and aleatoric uncertainty (which valid phrasing is selected). None of these properties hold for, say, answering open-domain questions or generating summaries. The paper provides no evidence that the method extends to these settings, and the miscalibration problems observed even on the synthetic task (negative variances, $C^\theta_\text{Cheat} > 1$) are likely to be substantially worse on real language.

What evidence exists in the paper: Only the synthetic digits-of-π experiment. The paper's language modeling architecture (a 19M-parameter Transformer trained from scratch on synthetic data) is orders of magnitude smaller than deployed LMs and was not pretrained on natural text. There is no experiment where a pretrained LM is fine-tuned on paired natural language data (e.g., multiple reference summaries, multiple human answers to the same question). The Frozen Lake experiment uses tokenized gridworld trajectories, not natural language.

Mitigation status: Not addressed. The paper states optimism in Section 7: "We are optimistic that our procedure will scale up to this use case, and are eager to explore this direction in future work." No experiments support this optimism, and the scaling challenges (maintaining calibration over $|\mathcal{Y}| = \text{vocabulary size}^{\text{sequence length}}$ with an autoregressive model) are not discussed.

---

Single Model Family and Dataset for Classification Experiments

The assumption or constraint: All CIFAR-10H experiments use a single model architecture family (Wide ResNet, depth 28, width multiplier 10, with or without SNGP modifications) and a single dataset (CIFAR-10/CIFAR-10H/CIFAR-10N). The paper states:

"We believe this model is representative" (regarding the digits-of-π Transformer, Section 6.2)

but provides no equivalent claim for the CIFAR-10H experiments, and no experiments vary the backbone architecture.

The consequence: It is unknown whether the cheat-corrected method's strong second-order calibration depends on properties of the Wide ResNet architecture or the CIFAR-10 image domain. For example, the Cheat SNGP variant consistently outperforms Cheat NN across all CIFAR-10H variants (ECE-2: 0.009 vs. 0.018 original, 0.011 vs. 0.022 harder), demonstrating that architectural choices within the same family affect second-order calibration. Whether the method would work with vision transformers, MLP-Mixers, or other modern architectures—and whether the eigenvalue regularization would still be needed—is untested. Similarly, CIFAR-10 images are low-resolution (32×32) with centered objects on simple backgrounds; whether the method extends to higher-resolution, more complex image distributions (ImageNet, medical imaging, satellite imagery) is unknown.

What evidence exists in the paper: The only architecture comparison is Cheat NN vs. Cheat SNGP, both variants of the same Wide ResNet backbone. The digits-of-π and Frozen Lake experiments use Transformers with different scales (19M and 85M parameters), showing that the method works across model sizes, but these are not classification tasks and do not compare architectural choices for pair prediction. No vision transformer or non-convolutional architecture is tested. The paper does not report computational overhead comparisons between pair-prediction training and single-prediction training for the same architecture, though the per-iteration cost is noted to be comparable since pair-prediction models process two labels per example versus two separate minibatch examples for baselines.

Mitigation status: Not addressed. No claims are made about architectural generality, and the paper does not discuss this as a limitation. The strong performance of Cheat SNGP relative to Cheat NN suggests that architecture matters, but the paper treats this as a positive finding (SNGP's distance-awareness helps) rather than as evidence that the method may be sensitive to architectural choices.

---

The Frozen Lake Experiment is Qualitative with No Quantitative Safety Metrics or Comparisons

The assumption or constraint: The Frozen Lake experiment is described as "a proof of concept" (Section 6.3). The evaluation consists of visualizations in Figure 6 and Appendix A showing that the cheat-corrected decoding strategies avoid lake-crossing trajectories when the unsafe patch is hidden. No quantitative metrics are reported.

The consequence: The paper cannot substantiate how reliably the method detects confounders and avoids unsafe actions. Key practical questions are unanswered: What is the false positive rate (safe trajectories incorrectly rejected)? What is the false negative rate (unsafe trajectories incorrectly accepted)? How does performance vary with the confidence threshold $\beta$? How does the method compare to existing safe imitation learning approaches (e.g., Warrington et al., 2020; Ortega et al., 2021) in terms of safety rate, task completion rate, or computational cost? Without these measurements, the Frozen Lake experiment demonstrates possibility but does not establish practical utility.

What evidence exists in the paper: Figure 6 shows a single example environment configuration (unsafe patch in the bottom-left, hidden and visible). Figures 11–13 show additional configurations (unsafe patch in the middle-right, hidden case) and qualitatively confirm the pattern. The paper notes that the rejection sampling strategy "does occasionally reject safe paths" (Figure 11 caption), indicating false rejections, but no rate is given. The top-1 search strategy is reported with 6400 samples per decision, a computationally expensive approach whose cost is not quantified. No baseline method (e.g., naive imitation learning, robust imitation learning, explicit confounder modeling) is implemented or compared in the Frozen Lake setting.

Mitigation status: Minimally addressed. The experiment is explicitly labeled a "proof of concept," which limits the strength of the claims but does not remedy the absence of quantitative evidence. The paper does not discuss the lack of baselines or quantitative metrics as a limitation. Future work is not specifically directed at strengthening this evaluation.

---

Distribution-Free Guarantees Are Not Demonstrated on Any Task Beyond Synthetic 1D Regression

The assumption or constraint: Algorithm 1 and Theorem 4.6 provide the paper's only formal statistical guarantee that does not assume perfect calibration. This algorithm is restricted to binary $\mathcal{Y} = \\{0, 1\\}$ and requires a held-out calibration set of paired responses. The paper acknowledges:

"For simplicity we assume $\mathcal{Y} = \\{0, 1\\}$" (Section 4.2)

The consequence: The distribution-free confidence intervals—which are the paper's answer to "what if my model isn't perfectly calibrated?"—are not available for any of the main experiments. CIFAR-10H uses 10 or 30 classes; digits of $\pi$ and Frozen Lake use sequence outputs. The method as deployed in these experiments assumes calibration without the safety net of Algorithm 1. A practitioner who wants provable guarantees for a multi-class or sequence task receives no guidance from the paper on how to extend the algorithm.

Furthermore, even for binary tasks, Algorithm 1 requires the user to choose $\varepsilon$ (the variance floor) and $\alpha$ (the confidence level for the bound on $\mathbb{E}[D_\varepsilon]$), and the resulting bound's tightness depends sensitively on these choices and on the calibration set size $N$. The 1D regression experiments (Appendix B, Figures 14–15) show that $\gamma^+_\varepsilon$ can blow up (exceeding 10 or 100) when $\varepsilon$ is set too small relative to the calibration set size and the model's degree of miscalibration. The paper provides no systematic guidance for choosing $\varepsilon$ in practice.

What evidence exists in the paper: The distribution-free algorithm is demonstrated only on the 1D binary regression toy problem (Appendix B, Figures 14–15), where the true $p_{Y|X}$ is known and can be used to verify the bounds. The algorithm is not applied to CIFAR-10H (multi-class), digits of $\pi$ (sequences), or Frozen Lake (sequences). The paper does not report the distribution-free bounds for any real dataset. The 1D results show that confseq produces tighter bounds than Hoeffding but still requires calibration sets of $10^5$–$10^7$ examples to achieve $\gamma^+_\varepsilon \approx 1$ for a well-calibrated model. The convergence rate and practical feasibility for real tasks are not characterized.

Mitigation status: The existence of Algorithm 1 partially mitigates the concern about miscalibration for the binary case, but the restriction to binary $\mathcal{Y}$ and the absence of experimental validation on non-synthetic data leaves a significant gap. The paper does not discuss extending the algorithm to multi-class or sequence settings, nor does it provide practical heuristics for choosing $\varepsilon$ when the model's degree of calibration is unknown (which is the deployment scenario the algorithm is designed for).

7. Implications and Future Directions

How This Work Changes the Landscape

This paper introduces a data-centric reframing of epistemic uncertainty quantification that shifts the field's attention from architectural solutions toward data collection strategy. The central conceptual move—that the impossibility of distribution-free epistemic uncertainty estimation vanishes when you collect paired responses instead of single responses—is not an incremental improvement but a diagnostic insight that changes the terms of the problem.

Before this work, the prevailing approaches to epistemic uncertainty fell into two camps, both of which the paper problematizes. The first camp—Bayesian methods, ensembles, and related techniques—attempts to estimate epistemic uncertainty by examining the model's internal state: posterior variance, ensemble disagreement, or variance over stochastic forward passes. Figure 3 shows the fundamental fragility of this approach: when the model is misspecified (as it always is in practice, especially in regions of input space that are densely sampled but structurally complex), the model's introspections are themselves wrong. A Gaussian process with a too-smooth kernel genuinely "believes" the function is simple and reports low uncertainty in precisely the region where its predictions are most inaccurate. An ensemble converges to consistent but wrong predictions and reports near-zero disagreement. These are not edge cases—they occur with large training sets and standard architectures, as the paper's 1D regression, CIFAR-10H scrambled (Table 4: NN Ensemble $\mathbb{E}[\hat{v}^\theta] = 0.028$ vs. true $\mathbb{E}[(p^\theta - p)^2] = 0.289$), and Frozen Lake experiments all demonstrate.

The second camp—conformal prediction and distribution-free methods—provides formal guarantees but, as Barber (2020) proved, faces a fundamental limitation: with single samples $(X, Y)$, you can only identify the first moment of $p_{Y|X}$, and any distribution-free confidence interval must be wide enough to cover 0 or 1 with high probability. This prevents tight estimation of epistemic uncertainty without assumptions.

The paper's reframing is that neither camp identified the correct bottleneck. The bottleneck is not better priors, more sophisticated posteriors, or cleverer calibration algorithms—it is the moment structure of the available data. Single samples provide one moment; paired samples provide two. Two moments are necessary and sufficient to estimate the squared deviation between a model's prediction and the truth, which is exactly what epistemic uncertainty aims to quantify. By demonstrating this theoretically (Theorem 4.6 circumvents Barber's impossibility using the product-of-residuals estimator $S_\varepsilon = (Y_1 - \hat{p})(Y_2 - \hat{p}) / \hat{v}_\varepsilon$) and empirically (the cheat-corrected method achieves second-order calibration where all single-sample baselines fail), the paper establishes that honest epistemic uncertainty quantification is achievable without distributional assumptions—provided you collect paired training data.

This reorients the research agenda in several concrete ways:

• Architectural innovation for uncertainty quantification becomes less central. If the key signal for epistemic uncertainty comes from the data (via paired responses) rather than from the model's internal representation, then efforts to design better Bayesian approximations, more expressive posterior parameterizations, or more sophisticated ensemble schemes are addressing a secondary problem. The primary problem is getting the paired signal into the training objective. The paper's results bear this out: the Cheat NN (a standard Wide ResNet with no uncertainty-specific architectural modifications beyond a symmetric softmax output head) achieves ECE-2 of 0.018 on original CIFAR-10H, while the NN Ensemble (8 copies of the same backbone) achieves 0.039 despite being far more computationally expensive and supposedly designed for uncertainty quantification. Adding SNGP (distance-awareness inductive biases) further improves Cheat SNGP to ECE-2 0.009, but the baseline SNGP Cov. without paired training achieves only 0.048. Architecture helps, but the paired data signal is the dominant factor.

• Data collection for ML systems should prioritize multiple independent annotations per example over single annotations on more examples. This is a practical engineering prescription with budget implications. If you have a fixed annotation budget, the paper suggests that collecting paired labels on half as many examples may produce not just better uncertainty estimates but also more reliable downstream systems (as the Frozen Lake safe navigation results suggest). The CIFAR-10H experiments support this: the model trained on paired data identifies underfitting that single-label ensembles miss, even when the total number of individual labels processed is the same.

• The distinction between aleatoric and epistemic uncertainty becomes operational rather than definitional. Prior work often defines the distinction in terms of hypothetical limiting behavior (aleatoric is what remains with infinite data; epistemic is what disappears). The paper provides an operational test: a model's uncertainty about a specific response $y$ is epistemic to the extent that observing an independent draw from the true process would change the model's prediction for a second draw. This operational definition is computable from the model's own outputs ($C^\theta_\text{Cheat}(y|x) = p^\theta_{Y_1|X}(y|x) / p^\theta_{Y_2|Y_1,X}(y|y,x)$) and has a clean calibration-theoretic interpretation (Proposition 4.4).

The paper also reconciles a tension in the uncertainty quantification literature. Evidential deep learning methods (Sensoy et al., 2018) claim to separate epistemic and aleatoric uncertainty by predicting a distribution over output distributions, but Bengs et al. (2022, 2023) proved that the evidential loss does not incentivize faithful uncertainty reporting. The paper's results align with Bengs et al.'s critique—Evidential DL achieves the worst ECE-2 (0.377) on CIFAR-10H and its uncertainty estimates are biased (underconfident on the Extra Classes variant, failing to increase when epistemic uncertainty actually rises under scrambling). The cheat-corrected approach resolves this by abandoning the "distribution over distributions" formalism entirely in favor of a second-moment approach grounded in paired data, providing a constructive alternative that does not suffer from the identified bias.

Finally, the paper validates a behavioral approach to model evaluation that may generalize beyond uncertainty quantification. The cheating test—"can the model improve its prediction by observing an independent sample?"—requires no ground-truth labels at inference time, no task-specific similarity metrics, and no assumptions about the data-generating process. This pattern of using a model's own autoregressive behavior as a diagnostic signal could extend to other properties we want models to report: whether they are extrapolating beyond their training distribution, whether their reasoning chains are causally coherent, or whether they are sensitive to irrelevant features.

Follow-Up Research This Work Enables

Scaling to real language modeling benchmarks with paired human annotations. The digits-of-π experiment demonstrates the mechanism on a synthetic language task with ~50 vocabulary tokens and known ground-truth probabilities. The critical follow-up is to test whether cheat-corrected metrics remain calibrated and useful when applied to real natural language data. Concretely: fine-tune a pretrained language model (e.g., 7B-parameter scale) on a dataset with multiple human-written responses per query—candidate datasets include ELI5 (multiple Reddit answers per question), the SummEval benchmark (multiple expert summaries per document), or dialogue datasets where multiple valid responses exist for each context. Measure (a) whether $C^\theta_\text{Cheat}$ correlates with factual correctness on a held-out test set where ground-truth answer validity is known (analogous to the digits-of-π hallucination detection but for real facts), (b) whether the $|1 - C^\theta_\text{Cheat}| \leq \beta$ threshold provides meaningful hallucination rate control at various $\beta$, and (c) how often $C^\theta_\text{Cheat} > 1$ occurs on natural text (the paper observed this on synthetic data and attributed it to miscalibration; real text with long-tailed token distributions may exacerbate it). A negative result (cheat-corrected metrics provide no better hallucination detection than log-probability on real data) would substantially constrain the method's claimed applicability to language models and motivate investigation into why the synthetic-to-real gap matters.

Extending Algorithm 1 to multi-class and sequence outputs. Theorem 4.6 and Algorithm 1 provide distribution-free confidence intervals for $p_{Y|X}$ only for binary $\mathcal{Y} = \{0, 1\}$. This is a significant practical limitation—the CIFAR-10H experiments use 10 or 30 classes, and the language/RL experiments use exponentially large sequence spaces. A natural extension is to construct distribution-free bounds for multi-class settings by applying Algorithm 1 separately to each class: for each $y \in \mathcal{Y}$, treat the problem as binary classification $Y' = \mathbb{1}[Y = y]$, train a separate pair predictor (or share representations across classes), and calibrate each independently. The challenge is that the resulting per-class intervals must be combined while maintaining a joint coverage guarantee (e.g., simultaneous coverage across all classes with probability $1-\alpha$). A strong follow-up would derive a Bonferroni-like correction or a more sophisticated multiple-testing adjustment, characterize the resulting confidence intervals on CIFAR-10H (where the true $p_{Y|X}$ can be approximated from >50 annotator labels), and compare the width of the distribution-free intervals to the un-adjusted cheat-corrected intervals. For sequence outputs, a different approach is likely needed—perhaps constructing prediction sets over sequences rather than pointwise probability intervals—and connecting to the conformal prediction literature on structured outputs.

Ablation study on the quantity and quality of paired data. The paper provides no characterization of how many paired examples are needed to achieve good second-order calibration, nor how the method degrades when paired data is scarce or noisy. A practically essential follow-up: on CIFAR-10H, train Cheat NN models with varying numbers of paired fine-tuning examples (10, 50, 100, 500, 1000, 5000) drawn from CIFAR-10H, keeping the CIFAR-10N pretraining fixed but varying whether it uses single or paired labels. Measure ECE-2, $\mathbb{E}[\hat{v}^\theta]$, and $\mathbb{E}[(p^\theta - p)^2]$ as a function of paired data quantity. A complementary direction: test robustness to violations of the i.i.d. assumption in the paired data. What happens if annotators have correlated biases (simulate this by making $Y_2$ a noisy copy of $Y_1$ with correlation $\rho$ rather than truly independent)? At what correlation does the cheat-corrected variance become unreliable? This would establish practical guidelines for when paired data collection protocols (e.g., two annotators from the same team vs. two independent contractors) are sufficient.

Combining cheat-corrected training with test-time compute scaling for safer decoding. The paper's Theorem 4.5 establishes that any decoding strategy which only depends on $X$ through $\Phi^\theta_{Y_1,Y_2|X}(X)$ will have a statistical hallucination rate bounded by $1 - \mathbb{E}[C^\theta_\text{Cheat}]$ when the model is calibrated. The experiments demonstrate this for simple strategies (filtering, rejection sampling, constrained top-1 search). A natural follow-up asks: can the cheat-corrected confidence be integrated into more sophisticated decoding strategies that actively optimize the confidence-accuracy tradeoff? For example, use $C^\theta_\text{Cheat}$ as a reward signal in a search procedure (beam search, best-of-N, or tree search) that simultaneously maximizes output quality (according to the model's marginal probability) while satisfying a confidence constraint. This would connect to the test-time compute scaling literature and could produce a "safe decoding" framework where the user specifies a hallucination risk tolerance and the search procedure adaptively allocates compute to respect it—directly addressing the safety concerns that motivate the work. The Frozen Lake experiment provides a preliminary demonstration (top-1 search with a confidence constraint), but a systematic study across tasks and search budgets would establish whether the approach scales.

Diagnosing and mitigating the causes of $C^\theta_\text{Cheat} > 1$ in autoregressive models. The paper observes that, in the digits-of-π experiment, the model sometimes produces $C^\theta_\text{Cheat}(y|x) > 1$—a violation of the calibrated behavior guaranteed by Proposition 4.4—and that these violations are associated with malformed or out-of-distribution samples. Understanding why this occurs in autoregressive models is important for diagnosing when the method's guarantees break down. The paper speculates that the issue stems from the model generating an incorrect $Y_1$ but a more correct $Y_2$ when conditioned on $Y_1$—behavior that is rational from a likelihood-maximization perspective (the model learns that $Y_2$ can correct $Y_1$'s mistakes because training data sometimes contains inconsistent pairs) but violates the symmetry and positive semidefiniteness assumptions required for the theory. A diagnostic study could: (1) measure the frequency and magnitude of $C^\theta_\text{Cheat} > 1$ across different model scales, training durations, and data distributions; (2) analyze whether these violations concentrate on specific types of inputs or outputs; (3) test whether architectural constraints that enforce symmetry (e.g., scoring $(y_1, y_2)$ and $(y_2, y_1)$ identically in the output layer if $\mathcal{Y}$ were tractable) reduce the violations; and (4) develop a correction procedure that post-processes the autoregressive scores to restore approximate calibration, similar to temperature scaling for first-order calibration.

Cheat-corrected metrics as a reward signal for RL fine-tuning of language models. The paper demonstrates that $C^\theta_\text{Cheat}$ can detect hallucinations without requiring external verifiers or task-specific correctness signals (unlike Cobbe et al., 2021, which trains a separate verifier, or Kuhn et al., 2022, which requires semantic equivalence metrics). This raises the possibility of using $C^\theta_\text{Cheat}$ as a reward signal for fine-tuning language models to reduce their hallucination rate via reinforcement learning. In this framework, the model would be trained to maximize a combined objective: a standard language modeling loss plus a reward proportional to $C^\theta_\text{Cheat}(y|x)$ for its generated outputs, encouraging it to favor responses for which it has high epistemic confidence. The challenge is that $C^\theta_\text{Cheat}$ is computed from the same model being fine-tuned, creating a risk of reward hacking (the model could learn to simply increase $C^\theta_\text{Cheat}$ without improving actual correctness). A careful study would need to demonstrate that optimizing against $C^\theta_\text{Cheat}$ improves factual accuracy (measured by an independent oracle) rather than merely inflating the cheat-corrected confidence. The Frozen Lake result—where cheat-corrected decoding produces safe behavior without any explicit safety reward—provides suggestive evidence that the signal may be robust enough for this purpose, but a controlled RL experiment would be needed to confirm it.

Practical Applications and Downstream Use Cases

Selective generation with bounded hallucination rates for fact-seeking language model deployments. If an organization deploys a language model to answer user questions (e.g., customer support, medical information, legal guidance) and cannot afford incorrect answers on certain query types, the cheat-corrected selective filtering strategy from Section 4.1 provides a direct mechanism: generate a candidate response using any decoder, score it with $|1 - C^\theta_\text{Cheat}(y|x)|$, and either return it (if the score is below a threshold $\beta$) or escalate to a human operator (if above the threshold). The digits-of-π results (Figure 5, right) show that at a response rate of 0.6, this strategy achieves a hallucination rate of approximately 0.05, substantially better than clustering-based methods (0.08–0.12) and log-probability baselines (0.18–0.22). For a real deployment, training would require a dataset of queries with at least two independent human-written responses per query—a data collection cost that may be amortized over many inference queries, especially in high-stakes domains where the cost of a single incorrect answer is high. The method requires no task-specific correctness metric, no separate verifier model, and no changes to the decoding architecture beyond scoring each candidate once under the pair predictor.

Human-annotation-based uncertainty quantification for medical image classification. Medical imaging tasks (radiology, pathology, dermatology) frequently involve substantial inter-annotator disagreement due to genuine diagnostic ambiguity (aleatoric uncertainty) and differences in annotator expertise. The CIFAR-10H experiments (Table 1) provide a direct analogue: images with >50 annotator labels per image, where the goal is to estimate the distribution of human diagnoses. The Cheat SNGP model achieves ECE-2 of 0.009 on this task while maintaining standard accuracy (94.9%), demonstrating that pair-prediction training can produce calibrated epistemic uncertainty estimates from human annotator data without requiring the model to know which annotators are "correct." In deployment, a medical imaging system trained on paired diagnoses would not only classify images but also report per-image epistemic confidence—distinguishing between images where diagnosticians consistently agree (high confidence) and images where the model's prediction is an average over genuinely ambiguous or differentially-diagnosed cases (low confidence). The key practical requirement is that each training image receives at least two independent annotator labels (drawn from the intended deployment population of diagnosticians); existing multi-reader studies in medical imaging often already collect this data, making the method retroactively applicable to many existing datasets.

Safe offline imitation learning from paired expert demonstrations. The Frozen Lake experiment (Section 6.3, Figure 6) demonstrates that a model trained on paired expert trajectories can automatically detect and avoid actions whose safety depends on unobserved confounders, without requiring explicit modeling of the confounders or on-policy data collection. This has practical implications for autonomous systems where expert demonstrations contain implicit knowledge about hidden state variables: for example, autonomous driving demonstrations where the human driver reacts to road conditions not fully captured by sensors (ice patches, aggressive nearby drivers, obscured pedestrians), or robotic manipulation demonstrations where the expert adjusts their strategy based on object properties not visible to the robot's cameras. By training on paired demonstrations from the same hidden state (two trajectories driven under the same road conditions, two manipulation attempts on objects with the same hidden properties), the model learns to assign low $C^\theta_\text{Cheat}$ to actions that would be unsafe if the hidden state were unfavorable. The cheat-corrected rejection sampling strategy then automatically filters these actions at deployment time, producing behavior that is conservative in the face of missing information. Compared to alternative approaches—explicit Bayesian filtering over hidden states (computationally expensive), robust RL (requires online interaction), or causal confounder modeling (requires expert knowledge of the causal graph)—the pair-prediction approach requires only paired expert data at training time and single-step scoring at inference time, making it potentially practical for complex real-world imitation learning settings.

When to Prefer This Method

The paper explicitly positions the cheat-corrected pair-prediction approach against two families of alternatives: architecture-based epistemic uncertainty methods (ensembles, Bayesian neural networks, SNGP, Epinets, evidential deep learning) and distribution-free calibration methods (conformal prediction, calibrated classification). The tradeoffs are articulated clearly enough to support a conditional recommendation framework.

Prefer the cheat-corrected pair-prediction method when:

• You can collect (or already have) at least two independent responses per training input from the true conditional process $p_{Y|X}$. This is the hard prerequisite. Without paired data, the method cannot be applied; with paired data, it provides guarantees that single-sample methods cannot (Theorem 4.6 vs. Barber, 2020). The paper demonstrates effectiveness with as few as 3 annotators per example (CIFAR-10N pretraining) and >50 annotators per example (CIFAR-10H finetuning), but does not characterize the minimum number of annotations needed—in practice, pilot experiments would be needed to determine whether a specific paired dataset is sufficient.

• The model may be misspecified relative to $p_{Y|X}$, and you need uncertainty estimates that remain valid under misspecification. The CIFAR-10H scrambled experiments (Table 4) provide the critical evidence: when the model's inductive biases are violated (scrambled pixels breaking the convolutional prior), the NN Ensemble reports $\mathbb{E}[\hat{v}^\theta] = 0.028$ while the true $\mathbb{E}[(p^\theta - p)^2] = 0.289$—a 10× underestimation of epistemic uncertainty. The Cheat SNGP reports $\mathbb{E}[\hat{v}^\theta] = 0.280$ vs. true 0.286. If your deployment may involve distribution shift, capacity limitations, or model misspecification, ensemble and Bayesian methods may be dangerously overconfident, while the paired-data signal remains informative.

• You need a task-agnostic epistemic uncertainty measure that does not require defining correctness or semantic equivalence for your output space. The hallucination detection experiments on digits of π (Figure 5, right) show the cheat-corrected confidence outperforming clustering-based methods that require task-specific semantic equivalence checks. For tasks where defining when two outputs "mean the same thing" is itself difficult or contested (creative generation, open-ended dialogue, scientific reasoning), task-agnostic uncertainty quantification is essential.

• You are willing to accept heuristic handling of miscalibration (the $|1 - C^\theta_\text{Cheat}|$ threshold, eigenvalue regularization) rather than formal distribution-free guarantees, or your task is binary and you can apply Algorithm 1. The paper's main experiments do not use Algorithm 1, relying instead on approximate calibration. If formal statistical guarantees are non-negotiable, the current method only provides them for binary outputs with a held-out paired calibration set.

Prefer architecture-based uncertainty methods (ensembles, Bayesian neural networks, SNGP) when:

• Paired data is unavailable or impractical to collect, and you are willing to accept that uncertainty estimates may be overconfident under misspecification. The paper shows that these methods can achieve reasonable first-order calibration and accuracy (NN Ensemble ECE-1 0.029, accuracy 94.9% on CIFAR-10H), and their epistemic uncertainty estimates may be adequate when the model is well-specified and training data is abundant. However, the CIFAR-10H scrambled results demonstrate that they systematically underestimate epistemic uncertainty when the model underfits—a failure mode that is silent (the ensemble reports low variance precisely when it is most wrong).

• Computational constraints favor training multiple small models over modifying the data collection pipeline. Ensembles require $K$ forward passes at inference time and $K$ training runs, which may be cheaper than collecting $2\times$ annotations for an entire dataset. This is an economic tradeoff, not a statistical one—the paper provides no cost comparison.

Prefer conformal prediction or other distribution-free calibration methods when:

• You only have single responses per input and cannot modify the training data, but you do have a held-out calibration set and a well-defined nonconformity score. Conformal methods provide frequentist coverage guarantees without paired training data, at the cost of producing prediction sets rather than pointwise probability intervals, and with the limitation that (per Barber, 2020) the intervals must be wide enough to cover 0 or 1 with high probability for binary problems.
• Your primary concern is first-order calibration (matching predicted probabilities to empirical frequencies) rather than second-order calibration (estimating per-input gaps between $p^\theta_{Y|X}$ and $p_{Y|X}$). The paper's ECE-1 results (Table 1) show that several baselines achieve first-order calibration comparable to the cheat-corrected method (SNGP Cov. ECE-1 0.020, Cheat SNGP ECE-1 0.022). If you only need the model's confidence scores to be reliable on average, rather than per-input, single-sample methods may suffice. The distinguishing value of second-order calibration is when you need to make per-input decisions (e.g., "should I trust this specific response?") rather than population-level decisions ("what fraction of my responses will be correct?").