Source-linked AI summary
Calibrated Language Models Must Hallucinate
Adam Tauman Kalai, Santosh S. Vempala
TL;DR
Language-model hallucinations pose serious risks, and the paper asks whether some hallucinations are statistically unavoidable rather than caused only by bad data or architecture. It defines generative calibration and proves lower bounds showing that arbitrary facts seen once in training induce hallucination, while recurring or systematic facts need not. The authors conclude that mitigating these cases requires distinguishing this statistical source from other causes and recognizing important scope and measurement limits.
Problem
Language models often produce plausible falsehoods, motivating the question of whether hallucinations persist even with accurate training data and capable architectures.
Method
The paper defines semantic calibration for generative models and analyzes calibrated predictors over arbitrary factoids using missing mass and Good-Turing estimation.
Results
Hallucination is lower-bounded near the fraction of arbitrary facts appearing exactly once in training, with the bound adjusted for miscalibration and distributional regularity.
Takeaways & Limitations
Pretraining need not inherently cause hallucination for repeatedly observed references or systematic facts, while post-training may mitigate arbitrary-fact hallucinations.
Takeaways & Limitations
The analysis covers only one statistical source of hallucination, uses a computationally difficult semantic calibration notion, and relies on assumptions that may fail for overlapping or partly systematic facts.
Abstract
from arXiv · showhide
Recent language models generate false but plausible-sounding text with surprising frequency. Such "hallucinations" are an obstacle to the usability of language-based AI systems and can harm people who rely upon their outputs. This work shows that there is an inherent statistical lower-bound on the rate that pretrained language models hallucinate certain types of facts, having nothing to do with the transformer LM architecture or data quality. For "arbitrary" facts whose veracity cannot be determined from the training data, we show that hallucinations must occur at a certain rate for language models that satisfy a statistical calibration condition appropriate for generative language models. Specifically, if the maximum probability of any fact is bounded, we show that the probability of generating a hallucination is close to the fraction of facts that occur exactly once in the training data (a "Good-Turing" estimate), even assuming ideal training data without errors. One conclusion is that models pretrained to be sufficiently good predictors (i.e., calibrated) may require post-training to mitigate hallucinations on the type of arbitrary facts that tend to appear once in the training set. However, our analysis also suggests that there is no statistical reason that pretraining will lead to hallucination on facts that tend to appear more than once in the training data (like references to publications such as articles and books, whose hallucinations have been particularly notable and problematic) or on systematic facts (like arithmetic calculations). Therefore, different architectures and learning algorithms may mitigate these latter types of hallucinations.
1 Introduction
The paper argues that calibrated language models can hallucinate arbitrary facts even with perfect training data, because predictive accuracy imposes a statistical lower bound tied to facts seen only once.
- Motivation: Language models can generate plausible but false information, creating serious risks in legal, healthcare, and other applications.Reported examples include hallucinated legal cases and concerns about life-threatening healthcare errors.
- Setting: The paper studies arbitrary 5W facts and references whose truth cannot be determined systematically when absent from training data.The analysis assumes ideal, factually correct i.i.d. training data and unconditional generation.
- Method: The authors generalize calibration from token probabilities to semantic facts because a fact can have exponentially many natural-language descriptions.Token-level calibration alone may be uninformative when multiple descriptions express the same fact.
- Results: The Good-Turing missing-mass estimate is the fraction of facts appearing exactly once in training, called the MonoFacts estimator here.This estimator approximates the probability that future facts were unobserved during training.
- Interpretation: The analysis predicts high hallucination for frequently unique facts but no inherent statistical necessity for references that usually recur in training.It also leaves room for other causes, including model capacity, and notes that unique facts can persist even in very large corpora.
2 Related work
Related work attributes hallucinations to data problems, modeling choices, and knowledge failures, while this paper isolates a statistical cause under idealized conditions.
- Open- vs. closed-domain hallucinations: The paper differs from closed-domain hallucination studies because it analyzes open-domain generation rather than fidelity to a supplied source document.Closed-domain work examines fabricated facts absent from a provided document in tasks such as translation or summarization.
- Honesty vs. factuality: Factuality and honesty are distinct concepts, although they coincide in the paper’s ideal world with consistent ground truth and factual training data.Under those assumptions, bounds on non-factuality also bound untruthful generation.
- Hypotheses for why LMs hallucinate: Prior research proposes false or outdated training data as major sources of hallucination, but this paper argues they are not the only causes.The paper distinguishes imitative falsehoods from missing or temporally outdated information.
- Hypotheses for why LMs hallucinate: Next-token training is statistically equivalent to document likelihood, so token-by-token training alone does not explain hallucination as a fundamental statistical effect.Architectural or computational limitations may still matter in practice, but the objectives represent the same document distribution.
- Related explanations: Other research shows that language models may detect their own hallucinations, which is compatible with hallucination arising despite predictive optimization.The paper frames detection methods as consistent with an ideal model still hallucinating when optimized for predictive accuracy.
3 Mathematical Preliminaries
The paper extends calibration from token probabilities to semantic fact distributions, defining miscalibration through probability bins and coarsenings relative to a true distribution.
- Generative calibration: Semantic-level calibration models probabilities over facts rather than individual tokens, addressing the many descriptions that can express one fact.The paper argues token-level calibration is not particularly meaningful for factual generation because facts have multiple natural-language descriptions.
- Miscalibration: Misb(g, p) measures how accurately g’s probabilities match future examples from p using adaptive bins.The measure is zero exactly when g is calibrated to p, regardless of the number of bins.
- Calibration definition: A distribution g is calibrated to p when g equals a partition-based coarsening of p.The paper notes that both g = p and the uniform distribution are calibrated under this definition.
- Miscalibration: Adaptive bins have roughly equal generation probability mass, while alternative strategies can use equal-width log-probability intervals.The framework permits multiple binning strategies, including fixed-width approaches discussed in the appendix.
- Advantages and limitations: Semantic calibration is conceptually natural but may be difficult to measure experimentally outside settings with canonical fact descriptions.The paper identifies synthetic settings as potentially easier for validation because facts can have canonical descriptions.
4 The model and guarantees
The model represents documents as independently sampled fact-bearing examples and studies arbitrary factoids under idealized sparsity, regularity, and one-fact-per-document assumptions.
- Model: The model samples n documents independently from a stationary language distribution and maps each document to one factoid.A special empty fact permits documents containing no facts, while multiple documents may describe the same factoid.
- Factoid assumptions: Arbitrary factoids are plausible information whose truth cannot be inferred systematically from observed training facts.Systematic facts such as mathematical inequalities are excluded from the factoid universe.
- Factoid assumptions: The ideal training-data assumption makes every observed fact genuine and gives each fact nonzero probability under the language distribution.The authors state these simplifications can be removed without changing the results, at the cost of additional notation.
- Factoid assumptions: Sparsity assumes there are many more plausible hallucinations than true facts, as with detailed paper citations.The fact universe is chosen so the true-fact set is exponentially smaller than the hallucination set.
- Regularity: Regularity limits how concentrated unobserved fact probabilities can be, with semi-regularity relaxing equal-likelihood assumptions.The framework separately defines regular facts and regular probabilities, then combines them into regular world distributions.
- Examples: A permuted power-law world provides a regular example, including uniform and Zipfian fact distributions.The construction randomly selects the fact set and assigns probabilities through a random ordering with power-law weights.
- Examples: The W5 example introduces anti-correlations, while predictable eaters can make the regularity parameter prohibitively large.The authors note that learned patterns may then reduce hallucination frequency for such predictable cases.
5 Guarantees
The guarantees relate hallucination to missing facts and the monofact Good-Turing estimate, with corrections for miscalibration, sparsity, regularity, and finite sample size.
- 5.1 Missing facts: The missing-fact rate p(U) is the pretraining probability of facts unobserved in the training data.It is the fact-level analogue of missing mass in sampling theory.
- 5.1 Missing facts: The monofact estimate d_MF counts the fraction of facts appearing exactly once in training data.Classical Good-Turing results make this estimate close to p(U) with high probability, up to a ˜O(1/n) error.
- 5.2 Guarantees: Semi-regular assumptions yield weaker guarantees, while the displayed bound is meaningful when sparsity s is much larger than log n.The paper provides an alternative bound using semi-regularity when that sparsity condition does not hold.
- 5.3 Multiple fact types: The analysis extends to k distinct fact types by applying the corresponding bounds to each type with a union bound.Each type receives its own monofact estimate and miscalibration rate.
- 5.2 Analysis approach: The proof strategy rewrites the theorem through total variation, concentration, and Good-Turing bounds.The theorem also supports multiple binning strategies whose partitions depend on g but not p.
6 Proof of Theorem 1
The proof establishes the theorem by comparing unobserved true facts with generated mass through total variation and decomposing the resulting positive-part bound.
- Theorem proof: The proof sets q to the partition coarsening p and uses H ⊆ U to relate hallucination and unobserved-fact sets.This yields an inequality involving p(U), q(U), and generated mass on F ∩ U.
- Theorem proof: A positive-part inequality bounds the target expression by missing true mass plus generated probability assigned to unobserved facts that are in F.The argument uses monotonicity of (a)+ under order preservation.
7 Upper bounds on hallucination rate
The paper constructs a calibrated language model whose hallucination rate is close to the Good-Turing estimate of missing facts, showing that substantially stronger general lower bounds are impossible.
- For any world distribution, a calibrated algorithm can hallucinate at a rate near the missing-facts rate.This establishes that the lower bound is close to attainable, not merely an artifact of the proof.
- The algorithm computes the monofact rate from observed and unobserved factoids, then assigns different probabilities to memorized and unseen facts.It samples a factoid from the resulting distribution and outputs a corresponding document.
- By construction, the generated fact distribution equals the target distribution induced by the algorithm.The paper states this as g = f ◦ DLM.
- The proof reduces the relevant discrepancy to the difference between missing mass and the monofact estimator.The Good-Turing estimator controls this difference with high probability.
8 Proofs of Corollaries
The corollaries follow by combining concentration bounds with Markov’s inequality and structural relations between observed, unobserved, factual, and hallucinated fact sets.
- Markov’s inequality converts an expectation bound into a high-probability bound for the relevant nonnegative error quantity.The proof applies it after defining the variable involving missing mass and hallucination-related terms.
- The proof combines the preceding bound with Corollary 6 and a union bound to obtain the stated corollaries.The text explicitly invokes δ-splitting before concluding the results.
- For regular fact distributions, the posterior satisfies the required regularity properties with probability 1.The argument then uses set containments and the earlier equations to establish Corollary 1.
- The proof of Corollary 2 additionally uses that the number of observed factoids is at most n.
9 Conclusions, limitations, and future work
The paper argues that predictive pretraining can produce hallucinations even under idealized conditions, while limiting the claim to a statistical source of hallucination and identifying directions for mitigation.
- Conclusions: Predictive pretraining can lead to hallucination even with perfectly factual data, disjoint facts, one fact per document, and no hallucination-inducing prompt.The theory is intended to demystify how detailed knowledge and unsupported fabrications can coexist.
- Conclusions: Hallucination is expected to be higher for fact types with high monofact rates, whereas references to books or articles may require other explanations.The paper mentions model capacity as one possible alternative explanation for problematic reference hallucinations.
- Limitations: The work studies only one statistical source of hallucination, and its calibration notion is computationally intractable to evaluate for many models.
- Limitations: The analysis may not apply when facts overlap, contain mild systematic structure, or multiple facts appear in a document.The paper notes that real-world complexity could reduce the minimal hallucination rates predicted by the idealized setting.
- Future work: Future work could distinguish systematic from arbitrary facts to reduce hallucination while preserving useful mathematical generation.
A Good-Turing estimator bounds
The appendix defines missing mass and the Good-Turing estimator, develops concentration bounds for them, and discusses how prompts can either eliminate or worsen hallucination.
- A Good-Turing estimator bounds: The appendix derives distribution-free concentration and finite-sample bounds for missing mass and Good-Turing estimates.These results are stated for arbitrary sets and distributions and rely on previously established concentration inequalities.
- A Good-Turing estimator bounds: Missing mass is the probability assigned by a distribution to elements absent from an i.i.d. training sample.The appendix denotes it as MD(s) := D(S \ {s1, s2, ..., sn}).
- A Good-Turing estimator bounds: The Good-Turing estimator is the fraction of sample elements that appear exactly once.The appendix states that expected missing mass and expected unique-element mass are very close.
- B.1 Hallucination with Prompts: Prompt distributions materially affect hallucination: complete-document prompts can make it unnecessary, while adversarial out-of-distribution prompts can make it severe.The unconditional analysis corresponds to zero-length prompts.
B.2 KL-divergence and log-loss
The paper contrasts calibration with KL-divergence and log-loss as ways to analyze hallucination. KL-divergence can remain near-optimal even when hallucinations are suppressed, whereas calibration can be achieved statistically without guaranteeing predictive accuracy.
- Accuracy and hallucination: Not all language models hallucinate; models that avoid memorization or output a constant can avoid hallucinations but perform poorly on held-out log-likelihood.This motivates analyzing whether good log-loss performance necessarily entails hallucination.
- KL-divergence and log-loss: The paper proposes analyzing hallucination through training-distribution log-loss or equivalently KL-divergence from the training distribution.The KL expression measures how far model log-loss is from the entropy of the training distribution.
- KL-divergence and log-loss: A model that outputs yay with probability 99% and samples another model with probability 1% hallucinates with probability below 1%, while increasing log-loss by at most log 100 bits.The increase is described as small relative to document entropy, especially for longer documents.
- Calibration versus KL-divergence: Calibration may be statistically achievable with near-zero miscalibration, unlike KL-divergence, which cannot generally be expected to approach zero.The paper gives uniformly random factoid generation as an example of achieving calibration while ignoring computational costs.
- Open question: The paper leaves open whether hallucination rates can be quantified using accuracy alone rather than calibration.It points to work showing that statistical models must memorize training data for accuracy purposes.
B.3 Alternative calibration definitions
This section presents alternative calibration definitions based on probability bins, including fixed-width and generative formulations. It relates generative calibration error to the paper's earlier miscalibration measure and extends the analysis through corresponding lemmas and corollaries.
- Alternative calibration definitions: Fixed-width calibration bins partition outcomes by equal-width intervals in probability space rather than by statistical distance.The construction uses Bz for exact probability values and BI for outcomes whose probabilities fall in an interval.
- Alternative calibration definitions: Log-probability binning uses ε to control multiplicative bin width, with smaller ε producing narrower bins.The definition includes limiting cases ε = 0 and ε = 1 for the binning construction.
- Proof structure: The corollary's proof follows the earlier corollary's proof while substituting pB(g, ε) for Vb(g).This substitution transfers the prior analysis to the alternative calibration definition.
- Generative calibration error: The generative calibration error definition provides an alternative to total variation as a measure of miscalibration.The text states that total variation could serve as a definition of miscalibration with a corresponding corollary.
- Generative calibration error: At ε = 0, generative calibration error equals the paper's earlier infinite-bin miscalibration measure.The equality is stated as GCE0(g, p) = Mis∞(g, p).
- Proof of the binning relation: The binning proof treats each bucket as an interval and uses the fact that a weighted average remains within that interval.This establishes the needed relation between the original probabilities and their binned averages.