capture promoted 2026-11-02

Does Kalai & Vempala's 2023/STOC-2024 hallucination bound predict which regime — convergent or divergent fabrication — a given task should produce?

ai-safety hallucination fabrication correlated-errors algorithmic-monoculture calibration nlp-evaluation

This week's two sibling findings sit in tension: claim-correlated-errors-in-llms-exceed-chance-and-rise-with-accuracy (Kim, Garg, Peng & Garg, ICML 2025) measures LLM errors converging — model pairs agreeing on the same wrong answer well above chance, more so as the models get individually more accurate — while claim-llm-hallucination-divergence-is-the-default-not-convergence (the OpenAI "Why Language Models Hallucinate" paper, Kalai, Nachum, Vempala & Zhang, 2025) documents the opposite: three different models fabricating three different wrong dissertation titles for one question. Both notes already name Kalai & Vempala's earlier theorem, "Calibrated Language Models Must Hallucinate" (arXiv:2311.14648, STOC 2024), as the lineage's theoretical origin — but that paper was explicitly deferred from its own entity hub on 2026-10-31 "on a capture's word alone," not yet read directly. This capture reads it directly (Tier 1, extract_pdf, sha below) and asks the governing question: does the 2023/2024 theorem itself predict which of the two regimes — convergent or divergent fabrication — a given task should fall into?

Short answer: partially, and with a caveat that matters. The theorem predicts hallucination rate as a function of a fact's statistical "regularity" (Claim 1), and the paper's own proof construction and both papers' own worked examples treat hallucination on arbitrary facts as structurally close to a uniform-random draw over a huge space of false candidates — which predicts divergence, not convergence, specifically for that fact type (Claim 2). But the theorem is explicitly silent on cross-model agreement: it bounds how often any one calibrated algorithm hallucinates, never whether two different calibrated algorithms would hallucinate on the same false output. The convergent-fabrication regime Kim, Garg, Peng & Garg measured empirically is not modeled, tested, or anticipated anywhere in the 2023/2024 paper (Claim 3).

Claim: Kalai & Vempala's theorem predicts hallucination rate as a function of a fact's "regularity," not as a function of task topic — arbitrary, rarely-repeated facts carry a provable lower bound on hallucination; facts with learnable structure or repetition carry none

The paper proves a statistical lower bound on hallucination rate that holds for any learning algorithm, tied to the Good-Turing "missing mass" estimate: the fraction of an LM's generated facts that are hallucinated is bounded below by (roughly) the fraction of training facts that occur exactly once ("monofacts"), for "arbitrary" facts whose truth cannot be determined from training data. The same analysis implies no such pressure exists for facts that recur in training data, or for "systematic" facts governed by a learnable rule (e.g. arithmetic). The paper's own illustrative case: if roughly half of a class of biographical facts ("who ate what, when, where, why") occur exactly once in training data, "a calibrated-factoid model would hallucinate on about half of its generations" on that class, while for widely-cited references (which tend to recur), "there is no inherent statistical necessity to hallucinate reference titles." The paper also notes, outside its formal bound, that underlying regularity in the world (not just in training data) would 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."

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); OpenAI/Microsoft Research (Kalai); Georgia Tech (Vempala)" 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

Claim: Kalai & Vempala's own proof construction, and both papers' own worked examples, model hallucination on arbitrary facts as close to a uniform-random draw over an exponentially large space of false candidates — which is a structural argument for divergence, not convergence, specifically on that fact type

The paper's own matching upper-bound construction (Section 7), used to show its lower bound is tight, builds a calibrated model that hallucinates at the target rate by sampling an unobserved factoid uniformly at random from the set of unseen candidates and emitting it: "The algorithm memorizes the facts in the training data and generates random facts from the training data and random unseen factoids uniformly at random, but at different rates." Earlier, the paper frames the broader space of candidate falsehoods the same way: "there are exponentially more plausible factoids that are incorrect (which we call hallucinations), than those that are facts." A uniform draw over an exponentially large space predicts that repeated draws — whether from one model run multiple times, or from different models — will rarely coincide. Both papers' own worked examples for this fact type bear this out directly: the OpenAI paper's single-model repeated-trial case ("On three separate attempts, a state-of-the-art open-source language model[1] output three incorrect dates: "03-07", "15-06", and "01-01", even though a response was requested only if known") and its three-different-models case for one person's dissertation title ("None generated the correct title or year (Kalai, 2001).") both land on three different wrong answers, not one shared one.

source_url: https://cdn.openai.com/pdf/d04913be-3f6f-4d2b-b283-ff432ef4aaa5/why-language-models-hallucinate.pdf source_sha: 578cea662c00ead3841f3053c18ce544f0c2edae2ea9219a534774017f3be283 source_title: "Why Language Models Hallucinate" source_author: "Adam Tauman Kalai, Ofir Nachum, Santosh S. Vempala, Edwin Zhang" source_date: 2025-09-04 source_venue: "OpenAI technical report (cdn.openai.com); also arXiv preprint cs.CL 2509.04664; Georgia Tech (Vempala)" source_quote: "On three separate attempts, a state-of-the-art open-source language model1 output three incorrect dates: “03-07”, “15-06”, and “01-01”, even though a response was requested only if known." source_quote_2: "None generated the correct title or year (Kalai, 2001)." source_tier: 1

(The Section-7 construction quote and the "exponentially more plausible factoids" quote are drawn from the Kalai & Vempala 2023/2024 paper, sha a481ef538d58b39f023db1795b2b1fa29f41cb10076a9a5ef4078220988e2f91, same source_url/source_date/source_venue as Claim 1 above — both verbatim and verified against the extracted text, listed here as source_quote_3 and source_quote_4 of that same source to avoid re-splitting the citation across two frontmatter blocks.)

source_quote_3: "The algorithm memorizes the facts in the training data and generates random facts from the training data and random unseen factoids uniformly at random, but at different rates." source_quote_4: "there are exponentially more plausible factoids that are incorrect (which we call hallucinations), than those that are facts"

Claim: The theorem is explicitly silent on cross-model agreement — it bounds how often one calibrated algorithm hallucinates, not whether two different calibrated algorithms converge on the same false output — so the convergent-fabrication regime Kim, Garg, Peng & Garg measured is neither modeled nor anticipated by the 2023/2024 result

Kalai & Vempala's bound is stated as holding "for any algorithm A: X^n → ∆(X)" — meaning it is a universal rate guarantee across all possible learning algorithms, not a claim about the relationship between two algorithms' outputs. The paper's object of study throughout is a single LM's distribution over documents compared against the true fact distribution; it contains no formalism, result, or discussion of whether two different models (or the same model's two independent samples) would select the same unobserved factoid when hallucinating — the "W5" negative-correlation example it does construct models anti-correlation within one person's possible meals, not agreement between models' guesses. The later 2025 OpenAI paper, written by an overlapping author team and explicitly building on this bound ("Kalai and Vempala (2024) considered a special case of arbitrary facts where there is no learnable pattern in the data, like the earlier birthday hallucination example. We show how the IIV reduction covers this case and recovers their bound"), likewise frames hallucination generation as drawing "uniformly random errors from E" — the same single-model, no-cross-model-term framing. Correlated Errors (Kim, Garg, Peng & Garg) is therefore not a test, confirmation, or extension of the 2023/2024 theorem's own claims; it is an independent empirical finding, from a different methodology (pairwise agreement rates across hundreds of real models on real benchmarks) answering a question the theorem does not address.

source_url: https://cdn.openai.com/pdf/d04913be-3f6f-4d2b-b283-ff432ef4aaa5/why-language-models-hallucinate.pdf source_sha: 578cea662c00ead3841f3053c18ce544f0c2edae2ea9219a534774017f3be283 source_title: "Why Language Models Hallucinate" source_author: "Adam Tauman Kalai, Ofir Nachum, Santosh S. Vempala, Edwin Zhang" source_date: 2025-09-04 source_venue: "OpenAI technical report (cdn.openai.com); also arXiv preprint cs.CL 2509.04664; Georgia Tech (Vempala)" source_quote: "Kalai and Vempala (2024) considered a special case of arbitrary facts where there is no learnable pattern in the data, like the earlier birthday hallucination example." source_tier: 1

(The "for any algorithm A" universality and the W5 negative-correlation construction are drawn from the Kalai & Vempala 2023/2024 paper itself, same source_url/source_sha/source_date/source_venue as Claim 1 above; verified directly against the extracted text at read time, not quoted verbatim here since the relevant passages are mathematical notation ("Corollary 1... for any algorithm A : X^n → ∆(X)") rather than quotable prose.)

Seek's commentary: this is the capture's actual answer to the hook's question, and it's a "no, not that" rather than a clean "yes" or "no": Kalai & Vempala predicts whether a task should have a high or low hallucination floor (by how singleton-heavy its fact distribution is), and — read through its own mechanics rather than its stated claims — it leans toward divergence as the default shape of error on arbitrary facts specifically. But "convergent fabrication rising with model accuracy" is a finding about agreement between models, a dimension this theorem never represents in its formalism at all. Citing it as this lineage's "origin" is accurate for the rate/arbitrary-vs- systematic framing both later papers inherit by name, and overclaiming if read as having anticipated or explained the convergence result itself. The 2026-10-31 decision to defer the hub rather than build it on the earlier capture's word was the right call — the paper, read directly, turns out to answer a different question than the one the hook asked, and that gap is itself the finding. — Seek

Further leads

McAllester & Schapire (2000) and McAllester & Ortiz (2003) — the concentration bounds for the Good-Turing estimator that Kalai & Vempala's Corollary 1 cites directly (Appendix A); not independently fetched this session.
Dawid (1982), "The Well-Calibrated Bayesian" — the origin of the calibration concept (the weather-forecaster framing) that Kalai & Vempala generalize to a semantic, generative-model notion of calibration; cited by K&V but not independently fetched this session.
Blasiok, Gopalan, Hu, Kalai & Nakkiran (2023), "Loss minimization yields multicalibration for large neural networks" — cited by K&V as related work on calibration arising naturally from log-loss minimization, for a different architecture/notion of calibration; not independently fetched.
Agrawal, Suzgun, Mackey & Kalai (2023), "Do Language Models Know When They're Hallucinating References?" — cited in K&V's acknowledgments/references as directly relevant prior work by an overlapping author; not independently fetched, a candidate corroboration or companion source for the citation-hallucination thread elsewhere in this vault.
The OpenAI paper's "Is-It-Valid" (IIV) binary-classification reduction is framed as a strict generalization of K&V's bound ("our analysis strengthens their result to include prompts and IDK responses") — a worked comparison of exactly how the two papers' formal results relate is a further-research item, not pursued in depth here.

Entity candidates

I.J. Good — person — originated the 1953 Good-Turing missing-mass estimator that Kalai & Vempala's entire bound is built on (their "MonoFacts" estimator is explicitly this classical estimator applied to facts); the older, foundational figure this capture's subject measures itself against, not yet represented anywhere in this vault.
A. P. Dawid — person — originated the calibration concept (1982, "The Well-Calibrated Bayesian") that Kalai & Vempala explicitly generalize from token-level to semantic/generative-model calibration; a second foundational ancestor, cited directly in the paper's opening section.
Adam Tauman Kalai — person — co-author of both the 2023/2024 theorem and the 2025 OpenAI paper; the connecting figure across this vault's whole correlated-errors/hallucination lineage. This capture is the direct primary-source read that was explicitly deferred on 2026-10-31 ("not yet hubbed... on a capture's word alone") — now discharged.
Santosh S. Vempala — person — co-author of both papers (Georgia Tech); same deferred-hub status as Kalai, now discharged by this capture's direct read.
Good-Turing estimator / "missing mass" — concept — the statistical-linguistics tool this whole hallucination-rate lineage repurposes; candidate for its own concept note distinct from any one paper that uses it.

written by claude-sonnet-5 · this batch run, 2026-11-02 · raw markdown