84Why Language Models Hallucinate

Adam Tauman Kalai, Ofir Nachum, Santosh S. Vempala and Edwin Zhang, arXiv preprint 2509.04664, September 2025

Linked to 17 chapters: supports 10 · contradicts 3 · mechanism 4 · same claim 5 · pairing 3

Asked for Adam Kalai's birthday, with the instruction to answer only if it knew, an open-source model of six hundred billion parameters returned three different dates on three attempts. None was right; the true date is in autumn. Kalai, Nachum, Vempala and Zhang treat that behaviour as ordinary rather than mysterious, and give it two causes, one at each stage of how such systems are made. Pretraining produces errors because fitting a distribution over text is at least as hard as deciding, for each candidate output, whether it is valid, and that decision is impossible for facts the training data never settled. Post-training fails to remove them because the tests that rank models award one point for a correct answer and none for an admission of ignorance, so a model that guesses whenever it is unsure outscores an identical model that says it does not know. The first cause is a theorem. The second is a fact about how the field keeps score, and it is where the paper's proposal lands: not another hallucination benchmark, but a confidence threshold written into the instructions of the benchmarks that already decide the leaderboards. The abstract states the diagnosis in a clause — models are "optimized to be good test-takers".

Pretraining errors

A base model is an estimate of the distribution its training text was drawn from. Proving that such an estimate must generate falsehoods is harder than it looks, because some models generate none. A model that answers everything with "I don't know" never says anything false, and neither does one that recites passages from a corpus assumed to be clean. Both fail at the estimation they were trained for, and the authors need a bound that covers the models which succeed at it.

The bound comes from a reduction to binary classification. They define a problem called Is-It-Valid: shown a string, say whether it is a valid output or an error. Its data are half real training examples, labelled valid, and half errors drawn uniformly at random, labelled error. Any language model can be read as a classifier for that problem by thresholding its own probabilities, calling a response valid when the model gives it more than one chance in the number of possible errors. Generation is the harder of the two tasks, since producing a valid response implicitly settles the validity question for every candidate it passed over. The theorem makes this precise in the direction that matters. The generative error rate is at least twice the misclassification rate of the induced classifier, less two corrections. One is the ratio of valid responses to erroneous ones, small wherever there are many ways to be wrong: for a birthday in day-month form there are 364 wrong answers against one right. The other is a calibration term.

That calibration term is the gap between the probability mass the model puts above the threshold and the mass the training distribution puts there. The authors show it equals the size of the derivative of the cross-entropy loss under a rescaling of the above-threshold probabilities. If the gap were large, rescaling would lower the loss and the model would not be sitting at a minimum. Any model family able to represent such a rescaling will therefore have a small gap once trained. Calibration is not a virtue added to a base model; it is what minimising cross-entropy yields. The paper reprints the GPT-4 calibration histograms to show it, from the system card: before reinforcement learning the model's confidence on four-way multiple choice tracks its accuracy, and afterwards it does not.

The conclusion is narrower and harder than the one usually heard. Hallucination is not inevitable for language systems in general. A program that answers a fixed list of questions from a database, computes well-formed arithmetic, and otherwise abstains never hallucinates. What the bound shows is that a model which never errs cannot be calibrated. Nothing in the argument depends on next-word prediction or on transformers; it would apply to any procedure fitted to the distribution of language, which is why the authors insist their subject is not autocomplete.

Error factors for base models

Because generative error inherits the difficulty of a classification problem, the settled understanding of why classifiers fail becomes a catalogue of why models hallucinate. The paper's opening figure draws three cases with the same apparatus: labelled points and a classifier trying to separate them.

The hard case is a fact with no pattern behind it. The authors define it formally: for each prompt one correct answer is drawn uniformly at random from a set of candidates, and an abstention is available. A birthday is the example. Whether a base model gets such a fact right depends on nothing but whether the training data happened to record it, and how often. Their bound is the singleton rate, the fraction of training facts that appear exactly once. The estimator behind it is Alan Turing's: the share of a sample that occurs exactly once estimates the probability mass of everything the sample missed. Their theorem says the error rate after pretraining is at least the singleton rate, less a term that shrinks as the number of wrong answers grows, a term that shrinks with the square root of the training size, and the calibration gap. A matching upper bound is achieved by an efficient calibrated algorithm, so the singleton rate is a floor that can be met, not a loose one. The reading is concrete. If a fifth of the birthdays in a corpus appear exactly once, a base model should get at least a fifth of birthday questions wrong. Einstein's birthday appears many times and models rarely miss it; the birthday recorded once in an obituary is a throw of a 365-sided die.

The second case is a model too weak for the concept. Agnostic learning supplies the term: if the best classifier available in a family still misclassifies, generation in that family must err at least as much, and for a plain multiple-choice question the bound is close to twice that best error. The illustration is a trigram model, which predicts each word from the two before it. Given a sentence ending "lost it and was completely out of", and the same sentence begun with a different pronoun, a two-word window cannot reach that pronoun, so no trigram model can tell "her mind" from "his mind", and on an even mixture of the two prompts it errs at least half the time. The modern version is letter counting. Asked how many Ds are in DEEPSEEK, DeepSeek-V3 answered 2 or 3 across ten trials, and other assistants returned numbers as large as 6 and 7. The reasoning model R1 spells the word out letter by letter and gets 1. Same data, better model: the difficulty is that a prompt reaches the model as tokens, D/EEP/SEE/K, rather than as characters.

Three further sources follow. Computational hardness, which the appendix makes exact with a cipher: if no efficient algorithm can distinguish a true decryption from a false one, a calibrated model asked to decrypt must err at nearly the maximum rate, whatever else it can do. Distribution shift, for prompts unlike anything in training, such as asking which is heavier, a pound of feathers or a pound of lead. And the oldest source of all, that corpora contain falsehoods and base models repeat them. This last is the one post-training genuinely fixes: conspiracy theories and common misconceptions are among the things InstructGPT-style training from human feedback removes.

How evaluations reinforce hallucination

Post-training is meant to turn an autocomplete into an assistant that does not assert what it does not know. The authors argue that the attempt is fighting the scoreboard.

Call a grader binary if its scores are only 0 and 1 and every abstention scores 0. A test-taker knows the question, the space of responses and the shape of the rubric, but not the answer, and so holds some belief about which responses are right. For every such belief, the authors observe, no abstention is among the highest-scoring responses. The proof is a line of union bound. Under binary grading, abstention is not usually worse than guessing; it is always worse.

From this follows the comparison that gives the paper its force. Let Model A signal uncertainty accurately and never assert a falsehood, and let Model B be the same model with each abstention replaced by its best guess. B outscores A on every binary benchmark. Nothing about B is better. The scoring cannot tell a wrong answer from a refusal to invent one, and so it pays for the invention.

The problem is therefore not a shortage of hallucination evaluations but an abundance of misaligned ones. The authors went through the evaluations featured on the boards the field actually reads: the flagship capabilities leaderboard of HELM, the Open LLM Leaderboard, SWE-bench and Humanity's Last Exam.

Nine of the ten give nothing for an abstention. The tenth, WildBench, grades real user conversations on a ten-point rubric in which a response that is fair but carries factual errors lands at five or six, while one that does not help the user lands at three or four, so an admission of ignorance can score below a fabrication. Several of the ten are graded by language models, which sometimes mark a confident wrong answer correct, and that pays for bluffing too. Humanity's Last Exam does report a calibration error alongside accuracy, but the authors show it measures something else: a model that answered every question wrong while reporting no confidence would score as perfectly calibrated.

This is why they call the problem socio-technical rather than technical. A better hallucination test changes nothing while the boards people read still reward guessing, and the 2025 AI Index observes that hallucination benchmarks "have struggled to gain traction within the AI community". The diagnosis has the shape the sycophancy paper found for flattery, where the raters were people who preferred agreement and the model learned to agree; here the raters are grading scripts that prefer an answer, and the model learns to produce one. And as the mirage paper argued about abilities that seem to appear all at once, the metric rather than the model decides which behaviour shows up.

Explicit confidence targets

Human examinations have met the same problem and some have solved it by stating the penalty. India's JEE, NEET and GATE deduct marks for wrong answers, as have the American Mathematics Competitions and, in earlier years, the SAT, AP and GRE. The rule appears in the instructions, so a candidate can work out the confidence above which guessing pays.

The proposal is to do the same to machine benchmarks. Append to each question a line saying that an answer should be given only above some stated confidence, that a mistake costs a stated penalty, that a correct answer earns one point and that "I don't know" earns none. Set the penalty at the odds implied by the threshold, and the expected score favours answering exactly when the probability of being right exceeds it. The natural settings are a threshold of a half with a penalty of one, three-quarters with a penalty of two, and nine-tenths with a penalty of nine. A threshold of zero is today's grading, stated honestly: guess anyway.

Two details separate the scheme from earlier penalty proposals. The threshold is written into the instruction rather than hidden in the scoring, because a hidden penalty makes grading contestable and leaves model builders without a common target; with it stated, one model can be best at every threshold, whereas an unstated penalty forces a trade-off under which no single model is best. And the targets belong inside mainstream evaluations already in use, SWE-bench among them, rather than in bespoke hallucination tests that the mass of ordinary benchmarks would drown out.

What the scheme asks for is behavioural rather than numeric. The authors call it behavioural calibration: the model need not emit a probability, only give the most useful response it is confident enough to stand behind, and abstain when it has none. It can be audited by comparing accuracy and error across thresholds, and it sidesteps the difficulty that a correct answer can be phrased in many ways.

Where the analysis stops

The authors list what their account omits, and the list is worth reading as part of the argument. It considers only plausible strings and sets nonsense aside. It treats a response containing one falsehood as an error, which flattens the degrees of wrongness in an open-ended task such as writing a biography. Retrieval and reasoning reduce hallucination but do not repair the incentive, since binary grading still rewards a guess when the search returns nothing. Errors that turn on context outside the exchange, such as a question about phones that was meant to be about land lines, fall outside a definition reading only prompt and response. The three categories of correct, incorrect and abstain are themselves coarse, and the authors concede as much, offering a false trichotomy because it beats a false dichotomy. Abstention is the blunt end of a range of ways to signal uncertainty that also includes hedging, omitting a detail and asking a question; a stated numeric confidence handles these badly, since a model announcing one chance in 365 that a birthday falls on 7 March is calibrated and useless.

Since 2025

The paper was read widely because its second half named something anyone in the field could check in an afternoon, and that half has held up. The boards it surveyed still report accuracy as their primary number, and an abstention still earns nothing on them, which is the socio-technical difficulty the authors identified rather than a refutation of it. The first half is more contested. It generalises the authors' own 2024 result that calibrated models must hallucinate, extending it to prompts and to abstentions, and what it delivers is a lower bound in a worst case: knowing that a base model must err on a fifth of the facts its corpus recorded once says little about the error rate of a deployed model that has been post-trained and given a search tool. The singleton-rate prediction is testable, and the empirical work testing it began almost immediately. The evidence offered that base models are calibrated, meanwhile, is a single reprinted figure from one system card.

The proposal has drawn the objection that a stated threshold is one more thing to optimise against, and that a model tuned to the announced penalty will abstain on questions it could have answered, trading a falsehood for an unhelpful silence. The authors half-concede it by treating the threshold as arbitrary by design, something to be stated rather than got right. What survives either way is the observation underneath, which is not about language models at all: a scoring rule that gives no credit for saying "I don't know" will select, from any population of candidates, the ones most willing to make something up.