---
id: "20261102-0215-this-weeks-ai-safety"
title: "Does Kalai & Vempala's 2023/STOC-2024 hallucination bound predict which regime — convergent or divergent fabrication — a given task should produce?"
type: "capture"
status: "promoted"
origin: "batch"
writer_model: "claude-sonnet-5"
date_created: "2026-11-02T00:00:00.000Z"
provenance: "this batch run, 2026-11-02"
derived_from: []
tags: ["ai-safety","hallucination","fabrication","correlated-errors","algorithmic-monoculture","calibration","nlp-evaluation"]
seek_code_commit: "d40ee39"
promoted_to: ["30-notes/claim-kalai-vempala-2023-hallucination-bound-is-a-rate-theorem-sorted-by-fact-regularity.md","30-notes/claim-kalai-vempala-2023-construction-models-arbitrary-fact-hallucination-as-uniform-random-draw.md","30-notes/claim-kalai-vempala-2023-theorem-is-silent-on-cross-model-hallucination-agreement.md","40-entities/entity-adam-tauman-kalai.md (new hub, discharges the 2026-10-31 deferral)","40-entities/entity-santosh-vempala.md (new hub, discharges the 2026-10-31 deferral)","40-entities/entity-i-j-good.md (new hub — recurrence across 3 prior claim-notes plus this one cleared the bar)","40-entities/entity-good-turing-estimator.md (new concept hub — recurs across 3 prior claim-notes plus this one)","40-entities/entity-a-philip-dawid.md (existing hub, additive dated line: 1982 calibration-concept ancestry)"]
promoted: "2026-11-03T00:00:00.000Z"
not_promoted: ["McAllester & Schapire (2000) / McAllester & Ortiz (2003) Good-Turing concentration-bound citations — not independently fetched this session, lead only, no kept claim rests on them","Dawid (1982) 'The Well-Calibrated Bayesian' as its own claim-note — the capture names it but does not quote it directly; folded into entity-a-philip-dawid.md's dated additive line instead of a separate 30-notes/ claim","Blasiok, Gopalan, Hu, Kalai & Nakkiran (2023) on multicalibration — cited as related work in K&V's references, not independently fetched, lead only","Agrawal, Suzgun, Mackey & Kalai (2023), 'Do Language Models Know When They're Hallucinating References?' — cited in K&V's acknowledgments, not independently fetched, candidate corroboration lead for the citation-hallucination thread elsewhere in the vault, not pursued this session","A worked formal comparison of exactly how the OpenAI paper's IIV reduction relates to K&V's bound — flagged by the capture as a further-research item, not pursued in depth here; no kept claim rests on the comparison itself","No new 50-questions/ entry routed: none of the three kept claims carries a blocking [unverified-*] flag — all three quotes are Tier 1, fetched directly with sha at capture time, and the two non-prose passages (universality clause, W5 construction) were verified directly against the extracted text rather than quoted, per the quote-shape rule for mathematical notation"]
---


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

> [!note] Seek's commentary: This is the half of the question the theorem
> directly answers — it is a *rate* theory, sorted by fact type (arbitrary
> vs. systematic, singleton vs. repeated), not a *regime* theory sorted by
> convergent vs. divergent error. Reading "rate" as a proxy for "regime"
> is the inferential leap the rest of this capture tries to pin down
> rather than assume. — Seek

## 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"

> [!note] Seek's commentary: This is the closest the primary source comes
> to predicting a *regime*, and it only does so by implication: nothing in
> the paper says "arbitrary facts → divergent fabrication," but the
> mechanics of its own model (uniform sampling over an exponentially large
> hallucination space) have that as a direct consequence, and both
> papers' own illustrative tables happen to show exactly that outcome. I
> am being careful to mark this as my own reading of the model's
> mechanics, not a claim either paper states in these words — see
> [[claim-llm-hallucination-divergence-is-the-default-not-convergence]]'s
> own commentary, which flags the identical inferential gap independently.
> — Seek

## 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.)

> [!note] 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.