---
title: "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"
type: "claim"
status: "seedling"
writer_model: "claude-sonnet-5"
source_url: "https://arxiv.org/pdf/2311.14648"
source_sha: "a481ef538d58b39f023db1795b2b1fa29f41cb10076a9a5ef4078220988e2f91"
source_title: "Calibrated Language Models Must Hallucinate"
source_author: "Adam Tauman Kalai, Santosh S. Vempala"
source_date: "2023-11-24"
source_venue: "Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024); arXiv preprint cs.CL 2311.14648 (v3, 2024-03-20)"
source_quote: "There is no statistical reason that LMs should hallucinate on systematic facts."
source_quote_2: "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"
source_quote_3: "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."
source_tier: 1
independent_roots: 1
provenance: "Promotion from 10-inbox/raw/2026-11-02-this-weeks-ai-safety-capture-found-llm-errors.md, 2026-11-03 (headless)"
origin: "batch"
derived_from: "10-inbox/raw/2026-11-02-this-weeks-ai-safety-capture-found-llm-errors.md"
date_created: "2026-11-03T00:00:00.000Z"
tags: ["ai-safety","hallucination","fabrication","calibration","nlp-evaluation"]
audit_status: "capture-verified (quote and sha recorded at capture time, 2026-11-02) | 2026-11-04 cross-model audit (auditor claude-fable-5, writer claude-sonnet-5): CORRECTED one body sentence — 'generalizes Dawid's 1982 forecaster-calibration notion from token-level probability statements' implied Dawid's notion was token-level; per the paper itself, Dawid (1982) introduced forecaster calibration and it was prior LM work that applied calibration at the token level. All three quotes re-verified verbatim against the capture-time archive and a fresh fetch of the live arXiv PDF (sha256 unchanged, a481ef53…). Claim unaffected."
seek_code_commit: "d40ee39"
quote_sweep: "PASS 2026-11-04 — source_quote verbatim (normalized) in the capture-time archive (sha256 a481ef538d58…), same-night model-free sweep"
verified_verbatim: "2026-11-04 — source_quote matched verbatim (normalized) against a direct fetch of source_url by seek_verify (no model involved)"
---


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 [[entity-a-philip-dawid|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]].

> [!note] Seek's commentary: This is the half of the question the theorem
> directly answers — a *rate* theory, not a *regime* theory. Reading "rate" as a
> proxy for "regime" (whether an error converges or diverges across model runs)
> is the inferential leap the two sibling notes below work out rather than
> assume. — Seek