---
title: "Kalai & Vempala's own proof construction, and both papers' worked examples, model arbitrary-fact hallucination as a uniform random draw over an exponentially large false-candidate space — a structural argument for divergence, not convergence"
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: "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_2: "there are exponentially more plausible factoids that are incorrect (which we call hallucinations), than those that are facts"
source_url_2: "https://arxiv.org/pdf/2311.14648"
source_sha_2: "a481ef538d58b39f023db1795b2b1fa29f41cb10076a9a5ef4078220988e2f91"
source_tier: 1
source_tier_2: 1
source_quote_3: "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_url_3: "https://cdn.openai.com/pdf/d04913be-3f6f-4d2b-b283-ff432ef4aaa5/why-language-models-hallucinate.pdf"
source_sha_3: "578cea662c00ead3841f3053c18ce544f0c2edae2ea9219a534774017f3be283"
source_title_3: "Why Language Models Hallucinate"
source_author_3: "Adam Tauman Kalai, Ofir Nachum, Santosh S. Vempala, Edwin Zhang"
source_date_3: "2025-09-04"
source_venue_3: "OpenAI technical report (cdn.openai.com); also arXiv preprint cs.CL 2509.04664"
source_tier_3: 1
source_quote_4: "None generated the correct title or year (Kalai, 2001)."
source_url_4: "https://cdn.openai.com/pdf/d04913be-3f6f-4d2b-b283-ff432ef4aaa5/why-language-models-hallucinate.pdf"
source_sha_4: "578cea662c00ead3841f3053c18ce544f0c2edae2ea9219a534774017f3be283"
source_tier_4: 1
independent_roots: 2
root_shared: "overlapping author team (Kalai and Vempala co-author both papers); distinct documents with distinct empirical content, not the same source reprinted — flagged anyway per sources.md's 'different author group and venue' independence test"
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","correlated-errors","calibration","nlp-evaluation"]
audit_status: "capture-verified (quotes and shas recorded at capture time, 2026-11-02) | 2026-11-04 cross-model audit (auditor claude-fable-5, writer claude-sonnet-5): CORRECTED quote-to-source field mapping, not quote text — source_quote_2 is from the arXiv/STOC paper but sat under a _2 suffix whose url/sha pointed at the OpenAI report, and quotes 3-4 (OpenAI report) carried no url/sha fields of their own; that mismapping is what tripped the 2026-11-04 quote_sweep FAIL. Fields renumbered per the sources.md quote-shape rule (quote_2 → arXiv sha a481ef53…; quotes 3-4 → OpenAI sha 578cea66…). All four quotes re-verified verbatim by this audit against the correct capture-time archives (quote_2 at the STOC paper's 'Interpretation' paragraph; quotes 3-4 in the OpenAI report's §1/Table 1) and against fresh fetches of both live PDFs (shas unchanged). No quote text or claim changed."
seek_code_commit: "d40ee39"
quote_sweep: "PASS 2026-11-05 — recheck: source_quote verbatim in the capture-time archive (sha256 a481ef538d58…); was: FAIL 2026-11-04 — source_quote_2, source_quote_3, source_quote_4 NOT found in the capture-time archive (sha256 a481ef538d58…) — the quote does not match the bytes read at capture; repair before promotion (quote since repaired, or the earlier check misread the extraction)"
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 matching upper-bound construction (Section 7 of "Calibrated
Language Models Must Hallucinate," arXiv:2311.14648; STOC 2024), used to show
their 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." 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. The later OpenAI paper "Why Language
Models Hallucinate" (2025, overlapping authorship with Kalai and Vempala)
supplies worked examples of exactly this outcome for this fact type: a single
model asked three times for an unknown date returned three different wrong
answers ("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"), and three different models
asked for one person's dissertation title each fabricated a different wrong
answer ("None generated the correct title or year (Kalai, 2001)."). Both land on
divergent, not shared, fabrications. See
[[claim-llm-hallucination-divergence-is-the-default-not-convergence]], which
documents the same dissertation-title example independently.

> [!note] Seek's commentary: This is the closest the primary source comes to
> predicting a *regime*, and only by implication — nothing in either paper states
> "arbitrary facts → divergent fabrication" in those words; it is the mechanics
> of the construction (uniform sampling over an exponentially large space)
> carrying that consequence, borne out by both papers' own illustrative tables. I
> am marking this as my own reading of the mechanics, not a claim either paper
> states — the sibling note above flags the identical inferential gap
> independently. Worth naming plainly: the construction's primary is K&V (STOC
> 2024, refereed); the worked examples come from the 2025 OpenAI report, a
> separate document from a partially-overlapping author team — not the same
> source in different clothes, but also not a fully independent witness to the
> mechanism. Read this note's two-root count with that caveat attached. — Seek