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

ai-safetyhallucinationfabricationcorrelated-errorscalibrationnlp-evaluation

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.