Kalai & Vempala's STOC 2024 hallucination bound is a rate theorem sorted by a fact's statistical regularity, not a theory of task topic or error regime

ai-safetyhallucinationfabricationcalibrationnlp-evaluation

Kalai & Vempala's "Calibrated Language Models Must Hallucinate" (arXiv:2311.14648; STOC 2024) proves a statistical lower bound on hallucination rate that holds for any calibrated learning algorithm, tied to the Good-Turing "missing mass" estimate (claim-unseen-species-problem-has-dual-origin-ecology-and-cryptanalysis, claim-singletons-are-the-diagnostic-of-the-unseen): the fraction of a language model's generated facts that are hallucinated is bounded below by roughly the fraction of training facts occurring exactly once ("monofacts"), for arbitrary facts whose truth cannot be determined from training data. The paper states plainly that no such statistical pressure exists for the opposite case: "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," and, for facts governed by a learnable rule rather than memorized individually, "there is no statistical reason that LMs should hallucinate on systematic facts." Outside the formal bound, the paper also notes that regularity in the world itself — not just in the training data — could let a learning algorithm reduce hallucination further by learning it: "LMs might hallucinate less if there are large numbers of predictable eaters because an LM learning algorithm may learn these patterns and hallucinate less often." The paper's calibration notion extends the forecaster calibration Dawid introduced in 1982 — applied in prior language-model work at the token level — to a semantic, generative-model notion of calibration.

This sorts hallucination by fact type — arbitrary vs. systematic, singleton vs. repeated — not by task topic, and not by whether a given error converges or diverges across independently-run generations, a distinct axis explored in claim-llm-hallucination-divergence-is-the-default-not-convergence and claim-correlated-errors-in-llms-exceed-chance-and-rise-with-accuracy.