Why Language Models Hallucinate

TL;DR

Kalai, Nachum, Vempala, and Zhang (OpenAI + Georgia Tech) reframe LLM hallucination as a predictable consequence of two factors: a statistical pretraining objective that, like binary classification, must err on inherently unlearnable facts, and a post-training/evaluation regime that scores models on 0-1 accuracy and therefore rewards guessing over abstaining. The pretraining analysis introduces an “Is-It-Valid” reduction proving that generative error rate is lower-bounded by twice the binary misclassification rate on a valid-vs-error mixture, with a tight bound for arbitrary facts: the post-pretraining hallucination rate is at least the singleton rate (the fraction of facts appearing exactly once in training data). The post-training analysis argues the field’s “epidemic” is not a missing hallucination benchmark but the grading scheme of the dominant non-hallucination benchmarks — and proposes adding explicit confidence thresholds to existing leaderboards (e.g. “answer only if >75% confident; wrong answers penalized 3×”) so calibrated abstention is no longer a losing strategy.

Key claims

Generative error rate is lower-bounded by ~2× the Is-It-Valid (IIV) binary-classification error rate on a 50/50 mix of valid samples and uniformly random errors, established by thresholding the base model’s probability at $1/|\mathcal{E}|$ [Theorem 1, §3.2].
For “arbitrary facts” (single correct answer per prompt, no learnable pattern, like the lead birthday example), the hallucination rate after pretraining is lower-bounded by the singleton rate — the fraction of training prompts that appear exactly once with a non-abstention answer [Theorem 2, §3.3.1].
The cross-entropy pretraining objective itself drives calibration: $\delta$ (the calibration term in the bound) equals the magnitude of the loss derivative with respect to a rescaling of $\mathcal{E}$ vs $\mathcal{V}$ probabilities, so at a local minimum $\delta$ is small for any model class expressive enough to approximate that rescaling [§3.1, Calibration discussion].
Empirically, base models are well-calibrated; post-trained models often are not, because RL/RLHF objectives deviate from cross-entropy [Fig. 2, §3.1, Hallucinations are inevitable only for base models].
Trigram models necessarily hallucinate at rate ≥1/2 on coherent-sentence prompts because the optimal-in-class agnostic error is high — a clean illustration that poor model families produce errors via the same IIV mechanism [Corollary 2, §3.3.2].
Letter-counting failures (“count the Ds in DEEPSEEK” → 2/3/6/7) are a poor-model instance of the same IIV bound: reasoning models like DeepSeek-R1 that spell the token out solve it because they fix the model family, not because they fix the objective [§3.3.2].
The persistence of hallucinations after post-training is socio-technical: of nine influential primary benchmarks surveyed (GPQA, MMLU-Pro, SWE-bench, HLE, MATH, IFEval, BBH, WildBench, MMMU-Pro), all but WildBench use binary 0-1 grading that gives a strictly higher expected score to a model that always guesses when uncertain over one that abstains [§4, Table on benchmark grading].
The proposed fix is not yet another hallucination-specific benchmark but modifying the primary benchmarks: include explicit confidence-target instructions in the prompt (e.g. “Answer only if you are >t confident; correct answer +1, wrong answer −t/(1−t), IDK 0”) so that abstaining is the score-maximizing strategy under uncertainty [§4, Behavioral calibration].
“Behavioral calibration” is operationalized as: a model’s stated confidence on each output should predict its accuracy across the threshold range; this can be evaluated post-hoc on any existing dataset without needing a new dataset [§4].
Hallucinations are not inevitable in principle: a system that answers a fixed Q&A database + calculator and outputs IDK otherwise has zero hallucination rate, but achieves it by being uncalibrated (large $\delta$ ) — the bound is on calibrated models [§3.1, Hallucinations are inevitable only for base models].
The IIV reduction generalizes the Kalai-Vempala 2024 “missing-mass” hallucination result to include prompts, IDK responses, and bounded-cardinality answer sets, and recovers the singleton-rate bound as the no-pattern special case [§3.3.1, Theorem 2].

Method

The core technical move is a reduction from generation to binary classification. Define the Is-It-Valid problem: given a prompt $x$ and a candidate response $r$ , output 1 iff $r$ is a valid response to $x$ . The training distribution for IIV is a 50/50 mix of (a) real prompt-response pairs from the pretraining data, all labeled valid, and (b) prompt-uniformly-random-error pairs, all labeled invalid. Given any base model $\hat p$ , threshold its probability at $\tau = 1/|\mathcal{E}|$ (the uniform-error probability) to produce an IIV classifier: predict “valid” iff $\hat p(r \mid x) > \tau$ . Theorem 1 shows the generative error rate (probability $\hat p$ samples an $r \in \mathcal{E}$ ) is at least $2 \cdot \text{err}_{IIV} - \delta - |\mathcal{V}|/|\mathcal{E}|$ , where $\delta$ is a calibration slack that derivative analysis shows is small under cross-entropy training. For the Arbitrary Facts model (one correct answer per prompt, drawn uniformly at random), the singleton-rate bound follows from connecting the IIV error to Turing’s missing-mass estimator.

For post-training, the analysis is a game-theoretic decomposition rather than a theorem: under a binary 0-1 grading scheme that scores correct=1, wrong=0, IDK=0, the strictly dominant strategy when posterior confidence $p < 1$ is to guess (expected score $p > 0$ ). The fix is a graded scoring rule with an explicit confidence threshold $t$ : correct=1, wrong= $-t/(1-t)$ , IDK=0; this makes abstention strictly optimal whenever true confidence is below $t$ , restoring incentive compatibility. The paper recommends modifying existing benchmarks (MMLU-Pro, GPQA, etc.) by injecting the threshold $t$ into the prompt and the loss into the scorer, rather than adding new hallucination-specific evaluations.

Results

There are no headline benchmark numbers — this is a theory paper. The empirical anchors are: (1) DeepSeek-V3, Meta-AI, and Claude 3.7 Sonnet all hallucinate Adam Kalai’s birthday with three different wrong dates across 3 trials [§1]; (2) the same three models, plus Llama-4-Scout-17B, hallucinate three distinct dissertation titles, years, and institutions for Kalai’s PhD, none correct [§1, Footnote 4]; (3) the letter-counting prompt “How many Ds in DEEPSEEK” returns 2–7 across ten DeepSeek-V3 trials [§1]; (4) base models are empirically calibrated, post-trained models often are not [Fig. 2]; (5) of nine major primary benchmarks surveyed, eight use binary 0-1 grading that disincentivizes abstention [§4 benchmark table].

Why it’s interesting

This is the cleanest filed framing for what hallucination is statistically rather than mechanistically — and it directly answers will’s slack question about whether the LLM concept of hallucination maps onto Luma’s video/world-model concerns. The answer the paper gives is: hallucination = generation of plausible-but-invalid outputs under a calibrated density-estimation objective on a domain with epistemic uncertainty (singletons). That definition transfers cleanly to omni/Vespa/Ray/Mach: any generative model fit by maximum-likelihood (cross-entropy or its flow-matching cousin) on multi-modal data with long-tail singletons will produce confidently-wrong outputs in those tail regions, and the IIV reduction is essentially modality-agnostic. The post-training half of the argument also has direct relevance: most filed video/T2I benchmarks (RULER-Bench: Probing Rule-based Reasoning Abilities of Next-level Video Generation Models for Vision Foundation Intelligence, Towards World Simulator: Crafting Physical Commonsense-Based Benchmark for Video Generation (PhyGenBench), R2I-Bench: Benchmarking Reasoning-Driven Text-to-Image Generation) are 0-1 scored against a single correct rule/physics outcome and so reward “confident wrong” over “abstain” by the same mechanism. The paper complements Audio Hallucination Attacks: Probing the Reliability of Large Audio Language Models (AHA) which gives an empirical attack suite on the symptom of audio hallucination, and arXiv clarifies penalty for uncorrected LLM hallucinations: 1-year ban + peer-review requirement which addresses the publishing-hygiene side of LLM-generated falsehoods, by providing the underlying mathematical model. The connection to Qwen3.7-Max: The Agent Frontier (Qwen) is particularly sharp: that filed paper reports Qwen3.7-Max having the lowest hallucination rate among frontier models while AA-Omniscience separately shows raw accuracy down with abstention up vs Qwen3.6 — exactly the abstention-vs-accuracy frontier this paper predicts will dominate once benchmarks stop penalizing IDK.