PaperlayerView exact revision on arXiv

Source-linked AI summary

Why Language Models Hallucinate

Adam Tauman Kalai, Ofir Nachum, Santosh S. Vempala, Edwin Zhang

arXiv:2509.04664v1cs.CL

TL;DR

Language models hallucinate by producing plausible falsehoods, and these errors persist because training and evaluation procedures favor guessing over uncertainty. The paper analyzes hallucinations through binary classification and argues that revising existing benchmark scoring can mitigate them.

  • Problem

    Hallucinations remain plausible, overconfident falsehoods that diminish language models’ utility and trustworthiness.

  • Method

    The paper analyzes hallucinations using computational learning theory, connecting generative errors to binary classification across pretraining and post-training.

  • Results

    The paper shows that even error-free pretraining can generate errors, while mainstream binary evaluations reward guessing and penalize uncertainty.

  • Takeaways & Limitations

    Modifying existing evaluations to reward appropriate uncertainty could realign incentives and support hallucination mitigation.

  • Takeaways & Limitations

    The formalism does not distinguish different error magnitudes or degrees of uncertainty, and correct/incorrect/IDK categories remain incomplete.

Abstract

from arXiv · show

Like students facing hard exam questions, large language models sometimes guess when uncertain, producing plausible yet incorrect statements instead of admitting uncertainty. Such "hallucinations" persist even in state-of-the-art systems and undermine trust. We argue that language models hallucinate because the training and evaluation procedures reward guessing over acknowledging uncertainty, and we analyze the statistical causes of hallucinations in the modern training pipeline. Hallucinations need not be mysterious -- they originate simply as errors in binary classification. If incorrect statements cannot be distinguished from facts, then hallucinations in pretrained language models will arise through natural statistical pressures. We then argue that hallucinations persist due to the way most evaluations are graded -- language models are optimized to be good test-takers, and guessing when uncertain improves test performance. This "epidemic" of penalizing uncertain responses can only be addressed through a socio-technical mitigation: modifying the scoring of existing benchmarks that are misaligned but dominate leaderboards, rather than introducing additional hallucination evaluations. This change may steer the field toward more trustworthy AI systems.

1 Introduction

The paper explains hallucinations as statistically expected errors arising during pretraining and persisting because post-training evaluations reward guessing over uncertainty. It connects generation to binary classification and argues that modifying mainstream evaluations could improve alignment.

  • Hallucinations are plausible falsehoods that remain in state-of-the-art language models and reduce their utility and trustworthiness.
  • The analysis models hallucinations as errors over arbitrary plausible strings, using computational learning theory and a prompt-aware formalism.
  • 1.1 Errors caused by pretraining: Even error-free pretraining data can produce errors because the statistical objective optimized during pretraining leads language models to generate them.
  • 1.1 Errors caused by pretraining: The Is-It-Valid reduction connects generative error rates to binary-classification mistakes, with generative error rate ≳2 · IIV misclassification rate.
  • 1.1 Errors caused by pretraining: The reduction covers arbitrary facts, including birthday facts, and strengthens prior bounds by incorporating prompts and IDK responses.
  • 1.2 Why hallucinations survive post-training: Post-training can preserve overconfident hallucinations because prevailing binary evaluations penalize uncertainty and abstention, rewarding models that guess when unsure.
  • 1.2 Why hallucinations survive post-training: The paper proposes adjusting numerous primary evaluations so that uncertain responses are not penalized, rather than relying only on additional hallucination benchmarks.

2 Related work

Related work studies hallucination causes, mitigation methods, evaluation benchmarks, and uncertainty communication. The paper positions its supervised-to-unsupervised reduction as novel while extending prior theoretical work to prompts, uncertainty, and post-training.

  • The paper identifies its reduction from supervised binary classification to unsupervised density estimation or self-supervised learning as novel to the authors’ knowledge.
  • Prior studies attribute hallucinations to factors including overconfidence, decoding randomness, long-tailed samples, misleading alignment training, and spurious correlations.
  • Kalai and Vempala’s theory is presented as a special case, while this paper adds uncertainty expressions, prompts, supervised-learning connections, and post-training modifications.
  • Existing mitigation approaches include RLHF, RLAIF, DPO, fine-tuning, and methods using predictive signals about factual accuracy or uncertainty.
  • Recent work includes hallucination benchmarks and leaderboards, but relatively little research has examined barriers to their adoption.
  • Research also explores graded uncertainty language and pragmatics to improve how language models communicate information.

3 Pretraining Errors

The paper analyzes pretraining hallucinations as statistically expected generation errors, even with error-free data, by reducing validity generation to binary classification. It derives lower bounds for several settings and connects calibration, data sparsity, and model limitations to those errors.

  • Model trade-offs: A model that avoids errors by always answering IDK or memorizing training data fails at useful density estimation, while matching the true distribution requires prohibitively large data.The paper argues that well-trained base models nevertheless generate certain errors.
  • Reduction to classification: The analysis reduces valid-output generation to binary classification, allowing computational learning theory to characterize generative error mechanisms.The base model is treated as an IIV classifier by thresholding its probability at 1/|E|.
  • Scope: The framework applies to general density estimation and does not depend on next-word prediction or Transformer architectures.It covers reasoning and search-and-retrieval language models as well as prompted and unprompted settings.
  • Arbitrary facts: For inherently unlearnable facts, all calibrated base models must incur errors; the bound recovers a hallucination rate at least equal to the fraction of facts appearing once in training.If 20% of birthday facts appear exactly once, the analysis expects at least 20% hallucination on those facts.
  • Poor models: For pure multiple-choice settings, any trigram model has generation error rate at least 1/2, while larger n-gram models require exponentially more data as n grows.The bound follows from Theorem 3 with C = 2 and opt(G) = 1/2 for trigram models.

4 Post-training and hallucination

Post-training aims to reduce confident falsehoods, but binary evaluations reward guessing and penalize uncertainty, reinforcing hallucination. The paper therefore advocates explicit confidence targets and modifying influential existing benchmarks.

  • Post-training should shift models away from autocomplete behavior so they avoid confident falsehoods except when appropriate, such as fiction.
  • How evaluations reinforce hallucination: Binary grading awards no credit for uncertainty and makes abstaining strictly sub-optimal, so overconfident best guesses maximize expected test performance.
  • How evaluations reinforce hallucination: The vast majority of popular evaluations use binary grading, while additional hallucination evaluations may be overwhelmed by mainstream benchmarks that penalize uncertainty.
  • Explicit confidence targets: Evaluations should state explicit confidence targets and assign penalties for mistakes while giving zero points for “I don’t know” responses.
  • Explicit confidence targets: Confidence thresholds such as t = 0.5, 0.75, or 0.9 make answering optimal only when the model’s confidence exceeds the specified threshold.The corresponding mistake penalties are 1, 2, and 9 points, respectively.
  • Explicit confidence targets: The proposal incorporates confidence targets into established evaluations, rather than relying only on bespoke hallucination benchmarks with implicit penalties.

5 Discussion and limitations

The framework simplifies hallucination into a statistical model and therefore has explicit scope boundaries. It focuses on plausible falsehoods, single factual questions, prompt-visible context, and top-level uncertainty decisions.

  • The framework prioritizes selected aspects of hallucination because its multifaceted nature requires simplifying assumptions.
  • Plausibility and nonsense: By considering only plausible strings, the analysis excludes nonsensical outputs, although the theorem can be extended to include them under modified definitions.
  • Open-ended generations: The examples emphasize single factual questions, while open-ended generations require defining errors within responses and may warrant graded hallucination severity.
  • Search (and reasoning) are not panaceas: Search and retrieval do not remove the binary-grading incentive to guess when retrieval fails, and may not address miscalculations or intrinsic hallucinations.
  • Latent context: Errors dependent on context outside the prompt and response, such as ambiguity about phones versus land lines, fall outside the formalism.
  • A false trichotomy: The correct/incorrect/IDK categories do not represent different error magnitudes or uncertainty levels, though explicit confidence targets provide a practical modification.
  • Beyond IDK: The paper focuses on the top-level decision of what to say rather than richer uncertainty signals such as hedging, omitted details, questions, or probabilistic confidence.

6 Conclusions

The paper traces hallucinations from pretraining errors to their persistence through post-training, arguing that mainstream evaluations often reward hallucinatory behavior.

  • Pretraining errors parallel misclassifications in supervised learning and arise naturally from cross-entropy minimization.
  • The paper presents hallucinations as a phenomenon spanning the modern training pipeline, from pretraining through post-training.
  • The analysis argues that mainstream evaluations reward hallucinatory behavior rather than appropriate expressions of uncertainty.The authors propose modifying mainstream evaluations to realign incentives.

A Proof of the main theorem

The proof partitions hallucination and misclassification rates around a probability threshold, then bounds contributions above and below that threshold.

  • The proof partitions hallucination and misclassification rates into above-threshold and below-threshold components.
  • Above the threshold, each relevant misclassification contributes no more than µ(c)/2K to misclassification error while contributing at least µ(c)/K to hallucinations.
  • Below the threshold, the proof uses the number of valid responses per query and the probability bound ˆp(r | c) ≤1/K to control valid-response mass.

B Arbitrary-facts analysis

The appendix develops missing-mass estimates with abstentions and combines concentration arguments with a lower-bound analysis for arbitrary factual errors.

  • The analysis uses union bounds, Hoeffding bounds, McDiarmid’s inequality, and prior Good-Turing guarantees to establish concentration results.
  • The appendix extends the Good-Turing missing-mass framework to training data containing an abstention response IDK.
  • A key proof step treats correct answers for unseen queries as selected after the algorithm fixes its output, enabling an expectation calculation and concentration bound.
  • The appendix constructs a calibrated algorithm that memorizes observed answers and abstains with the correct probability for unseen queries.

C Poor-model analysis

The poor-model analysis studies binary classification of a unique correct answer and proves that thresholding model probabilities yields unavoidable error bounds.

  • When each prompt has one valid answer, errors arise if the model cannot reliably distinguish that answer from plausible alternatives.
  • The analysis converts model probabilities into a binary classifier by predicting positive when ˆp(r | c) exceeds threshold t.
  • Theorem 4 states that when |Vc| = 1, some threshold t ∈[0, 1] satisfies a bound for every p and ˆp.
  • The expected misclassification rate combines false positives from plausible alternatives with false negatives for the unique correct answer.

D Computationally intractable hallucinations

The paper uses secure encryption as a stylized example showing how computationally hard distinctions can induce hallucinations, including erroneous decryptions.

  • Encryption-based hardness: Secure encryption makes distinguishing correct from incorrect ciphertext-message pairs computationally difficult without the secret key.The reduction models prompts asking for the decryption of a ciphertext generated from a uniformly random message.
  • Reduction to hallucination: The encryption example instantiates hallucination analysis with true and incorrect ciphertext-message pairs that are indistinguishable to efficient algorithms.The target function labels a pair positive exactly when the ciphertext encrypts the proposed message.
  • Lower bound: If a classifier does not β-break encryption security, the associated language model outputs erroneous decryptions with probability at least 1 − β − 2|M|^-1 − δ.The bound follows from the stated observation for any β ∈ [0,1] and language model distribution.
  • Implication: The example connects computational hardness in supervised learning to computational hardness as a factor contributing to hallucinations.The authors present this as an illustration of how their reduction applies to computationally hard problems.

E Post-training analysis

The paper analyzes post-training as an evaluation problem in which binary grading rewards guessing rather than abstention, and surveys influential benchmarks for this property.

  • Binary grading: A binary grader assigns zero to abstentions and positive credit only to correct responses, making abstention strictly suboptimal in expected score.The proof uses the fact that some response has positive posterior probability of being correct.
  • Evaluation review: The authors review popular evaluations and leaderboards to measure how their grading treats uncertainty in language-model responses.The review focuses on influential benchmarks that shape model comparisons.
  • Evaluation review: Only one of the ten selected evaluations, WildBench, offers minimal credit for indicating uncertainty.The selected evaluations are shown in Table 2, while several are also reported in prominent model cards and reports.
  • Evaluation review: Language-model judges can incorrectly mark incorrect answers as correct, potentially encouraging hallucinations even in objective domains such as mathematics.The paper notes that this issue arises when judges assess answer equivalence or grade long responses.

F.1 HELM Capabilities Benchmark

The HELM Capabilities leaderboard and related capability evaluations largely provide no credit for abstention, so their grading can favor guessing over uncertainty reporting.

  • HELM Capabilities: HELM Capabilities is a widely used leaderboard intended to capture current thinking about general language-model capabilities.Its flagship leaderboard contains five scenarios.
  • HELM Capabilities: Four of HELM Capabilities’ five scenarios give virtually no credit for “I don’t know,” while the remaining scenario appears to reward errors less harshly than abstention.This grading pattern can encourage guessing in place of uncertainty reporting.
  • Related capability evaluations: MMLU-Pro and GPQA are graded as multiple-choice exams with no abstention option, while Omni-MATH provides no particular credit for IDK.Omni-MATH compares generated mathematical answers against ground truth despite equivalent formulations.
  • Related capability evaluations: IFEval requires instruction-following text generation without a specified abstention option, and its language-model grading may not intentionally treat IDK as adequate.The paper describes this possibility as conceivable but unlikely and unintended.
  • WildBench: WildBench uses a ten-point language-model grading rubric in which IDK may score 3–4, below a fair response with factual errors or hallucinations scoring 5–6.The paper concludes that this relative scoring may encourage guessing.
  • Open LLM Leaderboard: The Open LLM Leaderboard includes several benchmarks where IDK generally receives no credit, including MMLU-Pro, GPQA, IFEval, MATH Level 5, and MuSR.MATH Level 5 and MuSR are measured exclusively by accuracy and provide no credit for IDK.

F.3 SWE-bench and Humanity’s Last Exam

SWE-bench and Humanity’s Last Exam illustrate the dominance of accuracy-based evaluation, while HLE’s calibration metric does not directly measure hallucination.

  • SWE-bench: SWE-bench evaluates 2,294 GitHub software-engineering problems using accuracy, treating incorrect patches and uncertainty responses alike.Its grading does not distinguish an incorrect patch from a response indicating uncertainty.
  • Humanity’s Last Exam: Humanity’s Last Exam contains 2,500 questions spanning dozens of fields and uses a private test set to detect overfitting.HLE was created to address near-perfect performance by top models on many mainstream evaluations.
  • Humanity’s Last Exam: All reported HLE scores were below 30% accuracy at the time of writing, while most models had calibration error rates above 70%.HLE reports both binary accuracy and a calibration error metric.
  • Calibration limitation: HLE’s calibration error is not a proper hallucination metric because a model can hallucinate every time while reporting zero confidence and achieving zero calibration error.Post-hoc confidence estimates may still be useful, but withholding answers can be preferable in some applications.
  • Calibration limitation: Conversely, a model can avoid hallucinations yet have 100% calibration error by always giving correct answers with zero confidence.This demonstrates that calibration error and hallucination frequency can diverge in both directions.
Loading 2509.04664v1…