CoChat
Sign Up
Cited by 91Topic ModelingNatural Language Processing TechniquesAdversarial Robustness in Machine Learning

Calibrated Language Models Must Hallucinate

Open access
Kalai, Adam Tauman, Vempala, Santosh S.·2024·Proceedings of the 56th Annual ACM Symposium on Theory of Computing
DOI 10.1145/3618260.3649777
Open this paper in CoChat — free accountOpen PDF

Abstract

Recent language models generate false but plausible-sounding text with surprising frequency. Such “hallucinations” are an obstacle to the usability of language-based AI systems and can harm people who rely upon their outputs. This work shows that there is an inherent statistical lower-bound on the rate that pretrained language models hallucinate certain types of facts, having nothing to do with the transformer LM architecture or data quality. For “arbitrary” facts whose veracity cannot be determined from the training data, we show that hallucinations must occur at a certain rate for language models that satisfy a statistical calibration condition appropriate for generative language models. Specifically, if the maximum probability of any fact is bounded, we show that the probability of generating a hallucination is close to the fraction of facts that occur exactly once in the training data (a “Good-Turing” estimate), even assuming ideal training data without errors. One conclusion is that models pretrained to be sufficiently good predictors (i.e., calibrated) may require post-training to mitigate hallucinations on the type of arbitrary facts that tend to appear once in the training set. However, 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 (like references to publications such as articles and books, whose hallucinations have been particularly notable and problematic) or on systematic facts (like arithmetic calculations). Therefore, different architectures and learning algorithms may mitigate these latter types of hallucinations.

Integrity signals

Registry

Crossref · 10.1145/3618260.3649777

Cites

39 of 39 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

21 of 28 cited sources checked · 6 supported · 1 flagged · accuracy not yet measured

  • Findingreasoning

    Under a regularity assumption, for any algorithm, with probability at least 99% over training sets, the hallucination rate is at least the monofact estimate minus miscalibration minus 300 times the ratio of facts to possible hallucinations minus 7 divided by the square root of n.

    “In particular, under a “regularity” assumption on the factoid distribution, our simplest bound (Corollary 1) implies that, for any algorithm, with probability ≥ 99% over training sets, the Hallucination rate is at least 𝑀𝐹 -Miscalibration - 300|Facts| |Possible hallucinations| - 7 √ 𝑛 ,”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [14] 14. Katja Filippova. 2020. Controlled Hallucinations: Learning to Generate Faithfully from Noisy Data. http://arxiv.org/abs/2010.05873 arXiv:2010.05873 [cs]. source

      Section 3 describes per-example hallucination scores, and Section 6 reports an empirical reduction in hallucinations; neither gives a lower bound for every algorithm. Searches for the regularity assumption, monofact estimate, miscalibration, Corollary 1, and the stated constants found no matching result in our copy. Page numbers were not available. (LLM, conf=0.77)

      Experimental — accuracy not yet measured
    • The authors state this as an assumption: No single factoid is very likely; under perfect regularity, after observing training data, all unobserved factoids are equally likely to appear as facts in the language distribution.
  • Findingreasoning

    If the maximum probability of any fact is bounded, the chance of generating a hallucination is close to the fraction of facts that occur exactly once in training data, even with ideal error-free training data.

    “Specifically, if the maximum probability of any fact is bounded, we show that the probability of generating a hallucination is close to the fraction of facts that occur exactly once in the training data (a “Good-Turing” estimate), even assuming ideal training data without errors.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [14] 14. Katja Filippova. 2020. Controlled Hallucinations: Learning to Generate Faithfully from Noisy Data. http://arxiv.org/abs/2010.05873 arXiv:2010.05873 [cs]. source

      The Introduction and Section 3 describe detecting and controlling hallucinations associated with noisy training data. Searches for Good–Turing, facts occurring exactly once, bounded fact probabilities, and error-free training data found no passage stating the claimed probability relationship. (LLM, conf=0.76)

      Experimental — accuracy not yet measured
    • The authors state this as an assumption: No single factoid is very likely; under perfect regularity, after observing training data, all unobserved factoids are equally likely to appear as facts in the language distribution.
  • Premisecitation

    The Good-Turing estimator is within order square root of 1 over n of the missing mass with high probability for any distribution p.

    “The Good-Turing estimator was shown to be within |𝑝 (𝑈 ) -𝑀𝐹 | = Õ ( √︁ 1/𝑛) of the missing mass, with high probability [22,23], for any distribution 𝑝.”
    Quote in the paperSubstantial claim1 of 2 sources checked
    • cites [22] 22. Joshua Maynez, Shashi Narayan, Bernd Bohnet, and Ryan McDonald. 2020. On Faithfulness and Factuality in Abstractive Summarization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (Eds.). Association for Compu- tational Linguistics, Online, 1906-1919. https://doi.org/10.18653/v1/2020.acl- main.173 source

      The cited paper’s sections on model hyperparameters, hallucination results, and entailment discuss abstractive summarization, not estimation of missing mass. Searches for “Good-Turing estimator” and “missing mass” found no passage addressing the claimed high-probability √(1/n) bound. (LLM, conf=0.78)

      Experimental — accuracy not yet measured
    • cites [23] 23. David McAllester and Robert E Schapire. 2000. On the Convergence Rate of Good-Turing Estimators.

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Premisecitation

    Simple post-hoc probability modification procedures can calibrate any uncalibrated predictor and simultaneously increase its accuracy under metrics such as cross-entropy.

    “Simple post-hoc probability modification procedures can calibrate any uncalibrated predictor and simultaneously increase its accuracy under metrics such as cross-entropy [see, e.g., 7, 8].”
    Quote in the paperSubstantial claim1 of 2 sources checked
    • cites [7] 7. Mark Braverman, Xinyi Chen, Sham Kakade, Karthik Narasimhan, Cyril Zhang, and Yi Zhang. 2020. Calibration, Entropy Rates, and Memory in Language Models. In Proceedings of the 37th International Conference on Machine Learning. source

      Section 4.2 (p. 6) describes calibrating a language model while improving its perplexity, and Algorithm 2 (p. 8) fits a modified model by minimizing cross-entropy. The paper does not establish that these procedures calibrate any uncalibrated predictor: its results concern specified discrepancies in language models and are subject to stated assumptions. (LLM, conf=0.86)

      Experimental — accuracy not yet measured
    • cites [8] 8. PMLR, 1089-1099. https://proceedings.mlr.press/v119/braverman20a.html ISSN: 2640-3498.

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Findingreasoning

    More generally, the bound holds with probability at least 1 minus delta, with the constant 60 replaced by a term inversely proportional to delta and proportional to a regularity term on the factoid distribution.

    “More generally, the bound holds with probability ≥ 1 -𝛿 where the constant 60 can be replaced by a term which is inversely proportional to 𝛿 and proportional to a regularity term on the distribution of factoids.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: No single factoid is very likely; under perfect regularity, after observing training data, all unobserved factoids are equally likely to appear as facts in the language distribution.
  • Classified as probably not a substantial claim. 32
  • May combine two claims. 18
  • The quote only partly states this claim. 1

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Language models know when they are hallucinating.

    “Another line of work that sheds light on the nature of hallucinations shows that LMs know when they’re hallucinating [1,3,18,20].”
    Quote in the paperNot a substantial claim4 of 4 sources checked
    • cites [1] 1. Ayush Agrawal, Mirac Suzgun, Lester Mackey, and Adam Tauman Kalai. 2023. Do Language Models Know When They're Hallucinating References? http: //arxiv.org/abs/2305.18248 arXiv:2305.18248 [cs]. source

      The Introduction describes testing whether LMs can recognize their own hallucinated references. The Conclusions report that self-detection methods are only partially reliable and leave their generalizability to other kinds of hallucination open. Thus, the paper supports a narrower finding than the unqualified claim that LMs know when they are hallucinating. Page numbers are not provided in our copy. (LLM, conf=0.88)

      Experimental — accuracy not yet measured
    • cites [3] 3. Amos Azaria and Tom Mitchell. 2023. The Internal State of an LLM Knows When its Lying. https://doi.org/10.48550/arXiv.2304.13734 arXiv:2304.13734 [cs]. source

      The Introduction (page unavailable) says the study demonstrates that an LLM might “know” when a statement it has just generated is false. But the paper distinguishes detecting false statements from detecting hallucinations as defined in work on source-dependent tasks. The citing sentence states a broader, unqualified conclusion about language models and hallucination than this source supports. (LLM, conf=0.88)

      Experimental — accuracy not yet measured
    • cites [18] 18. Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. 2021. How Can We Know When Language Models Know? On the Calibration of Language Models for Question Answering. Transactions of the Association for Computational Linguistics 9 (Sept. 2021), 962-977. https://doi.org/10.1162/tacl_a_00407 source

      The Introduction says the models’ confidence estimates correspond poorly to whether their answers are correct. The Background on Calibration gives examples of wrong answers assigned very high probability, and the Implementation Details say models tend to be overconfident about cases they do not know. The paper therefore does not show that language models know when they are hallucinating; it studies methods to improve their calibration. (LLM, conf=0.89)

      Checked by a reasoning model — may be wrong.

      Experimental — accuracy not yet measured
    • cites [20] 20. Stephanie Lin, Jacob Hilton, and Owain Evans. 2022. TruthfulQA: Measuring How Models Mimic Human Falsehoods. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Smaranda Mure- san, Preslav Nakov, and Aline Villavicencio (Eds.). Association for Computational Linguistics, Dublin, Ireland, 3214-3252. https://doi.org/10.18653/v1/2022.acl- long.229 source

      The Introduction (p. 1) and Results (p. 6) show that models generate false answers, but do not establish that they recognize their own false answers. The GPT-judge passage (Appendix B.1, p. 19) describes a separately trained model evaluating answers, not a model knowing when it is hallucinating. I searched for recognition of false answers and confidence in generated answers. (LLM, conf=0.72)

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Many studies focus on hallucination with respect to a specific source document given to a language model, such as in translation or summarization.

    “Interestingly, many studies focus on hallucination with respect to a specific source document that is given to an LM, such as in translation [35] or summarization [21].”
    Quote in the paperNot a substantial claim2 of 2 sources checked
    • cites [35] 35. Karen Weise and Cade Metz. 2023. When A.I. Chatbots Hallucinate. The New York Times (May 2023). https://www.nytimes.com/2023/05/01/business/ai-chatbots- hallucination.html source

      The Related Work section names prior hallucination studies in machine translation and abstractive summarization, supporting the examples. It does not say that many studies focus on hallucination relative to a specific source document given to a language model; the Limitations section says this paper studies question answering, not summarization. (LLM, conf=0.75)

      Experimental — accuracy not yet measured
    • cites [21] 21. Potsawee Manakul, Adian Liusie, and Mark J. F. Gales. 2023. SelfCheckGPT: Zero- Resource Black-Box Hallucination Detection for Generative Large Language Models. http://arxiv.org/abs/2303.08896 arXiv:2303.08896 [cs]. source

      Section 2.1 says hallucination has been studied in summarization, supporting that example of the broader research area. But SelfCheckGPT does not study hallucination relative to a source document given to the model: Section 6 describes generating Wikipedia-style passages from a concept prompt, and the Introduction describes its focus as general LLM responses. The paper therefore does not itself exemplify the source-document-focused studies suggested by the citation placement. (LLM, conf=0.84)

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    A cited study reports a greater reduction in closed-domain hallucinations than in open-domain ones.

    “Consistent with this, [27] reports a greater reduction in closed-domain hallucinations over open-domain ones.”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [27] 27. Jeremy Nixon, Mike Dusenberry, Ghassen Jerfel, Timothy Nguyen, Jeremiah Liu, Linchuan Zhang, and Dustin Tran. 2020. Measuring Calibration in Deep Learning. https://doi.org/10.48550/arXiv.1904.01685 arXiv:1904.01685 [cs, stat]. source

      The Abstract (p. 1) describes a study of calibration measures, and §5.3 (pp. 6–7) compares their sensitivity to binning choices. Searches for closed-domain and open-domain hallucinations found no passage reporting a reduction in either, so our copy does not address the attributed comparison. (LLM, conf=0.78)

      Experimental — accuracy not yet measured

  • May combine two claims.

    Premisecitation

    Post-training alignment was used to reduce hallucination but was also found to reduce calibration.

    “Post-training alignment was applied to reduce hallucination (among other factors) but was also found to reduce calibration [27].”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [27] 27. Jeremy Nixon, Mike Dusenberry, Ghassen Jerfel, Timothy Nguyen, Jeremiah Liu, Linchuan Zhang, and Dustin Tran. 2020. Measuring Calibration in Deep Learning. https://doi.org/10.48550/arXiv.1904.01685 arXiv:1904.01685 [cs, stat]. source

      The Introduction (p. 2) describes a study of calibration measures, and §2.3 (p. 3) discusses post-processing classifier outputs for recalibration. Searches for post-training alignment, hallucination, and reduced calibration found no passage addressing the claimed trade-off. (LLM, conf=0.76)

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation

    The concept of calibration was introduced by Dawid and has been extensively studied in statistics, machine learning, and specifically for language models.

    “As discussed in the introduction, the concept of calibration was introduced by Dawid [10] and has been extensively studied in statistics and machine learning and even specifically for LMs [7,17,38] and other related fields of deep learning and generative AI [21,28].”
    Quote in the paperNot a substantial claim5 of 6 sources checked
    • cites Dawid [10]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [7] 7. Mark Braverman, Xinyi Chen, Sham Kakade, Karthik Narasimhan, Cyril Zhang, and Yi Zhang. 2020. Calibration, Entropy Rates, and Memory in Language Models. In Proceedings of the 37th International Conference on Machine Learning. source
    • cites [17] 17. Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. 2023. Survey of Hallucination in Natural Language Generation. Comput. Surveys 55, 12 (Dec. 2023), 1-38. https://doi.org/10.1145/3571730 source
    • cites [38] 38. Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, Longyue Wang, Anh Tuan Luu, Wei Bi, Freda Shi, and Shuming Shi. 2023. Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models. http://arxiv.org/abs/2309.01219 arXiv:2309.01219 [cs]. source
    • cites [21] 21. Potsawee Manakul, Adian Liusie, and Mark J. F. Gales. 2023. SelfCheckGPT: Zero- Resource Black-Box Hallucination Detection for Generative Large Language Models. http://arxiv.org/abs/2303.08896 arXiv:2303.08896 [cs]. source

      The Introduction and §2.2 discuss uncertainty metrics for generated language, and §8 describes the paper's hallucination-detection method for large language models. This supports citing the paper as related work in generative AI, but our copy does not show it studying calibration or address the claim about calibration's history and breadth of study. (LLM, conf=0.78)

      Experimental — accuracy not yet measured
    • cites [28] 28. OpenAI. 2023. GPT-4 Technical Report. http://arxiv.org/abs/2303.08774 arXiv:2303.08774 [cs]. source

  • The quote only partly states this claim.

    Interpretationcitation

    Post-training reduces hallucination rates at the cost of increasing calibration error, as suggested by the model and shown in GPT-4 calibration curves.

    “As suggested by our model, post-training reduces hallucination rates at the cost of increasing calibration error.Note that calibration here is on a multiple-choice test rather than generative calibration which we study.”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [27] 27. Jeremy Nixon, Mike Dusenberry, Ghassen Jerfel, Timothy Nguyen, Jeremiah Liu, Linchuan Zhang, and Dustin Tran. 2020. Measuring Calibration in Deep Learning. https://doi.org/10.48550/arXiv.1904.01685 arXiv:1904.01685 [cs, stat]. source

      Section 5.4 (pp. 7–8) examines how calibration metrics rank recalibration methods; Section 2.3 (p. 3) describes post-processing classifiers to calibrate their predictions. Our copy does not address hallucination rates, GPT-4 calibration curves, or the claimed trade-off from post-training (searched: post-training, hallucination, GPT-4, multiple-choice). (LLM, conf=0.77)

      Experimental — accuracy not yet measured

  • May combine two claims.

    Premisecitation

    For any distribution and n≥1, the missing mass exceeds its mean by ε with probability at most e^{-ε^2 n}, and falls below its mean by ε with probability at most e^{-1.92 ε^2 n}.

    “Pr 𝑠∼D 𝑛 [𝑀 D (𝑠) ≥ 𝑀 𝑛 D + 𝜀] ≤ 𝑒 -𝜀 2 𝑛 (11 ) Pr 𝑠∼D 𝑛 [𝑀 D (𝑠) ≤ 𝑀 𝑛 D -𝜀] ≤ 𝑒 -1.92𝜀 2 𝑛(12)”
    Quote in the paperSubstantial claim1 of 2 sources checked
    • cites McAllester and Ortiz [23] 23. David McAllester and Robert E Schapire. 2000. On the Convergence Rate of Good-Turing Estimators.

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites Berend and Kontorovich [4] 4. Daniel Berend and Aryeh Kontorovich. 2013. On the concentration of the missing mass. Electronic Communications in Probability 18, none (Jan. 2013), 1-7. https: //doi.org/10.1214/ECP.v18-2359 Publisher: Institute of Mathematical Statistics and Bernoulli Society. source

  • Classified as probably not a substantial claim.

    Premisecitation

    In the first stage of pretraining, common today, the generative language model is optimized for predictive text performance.

    “Notably in the first stage of pretraining, common today, the generative LM is optimized for predictive text performance [9,27].”
    Quote in the paperSubstantial claim2 of 2 sources checked
    • cites [9] 9. Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, and Pree- tum Nakkiran. 2023. Loss minimization yields multicalibration for large neural networks. https://doi.org/10.48550/arXiv.2304.09424 arXiv:2304.09424 [cs, stat]. source
    • cites [27] 27. Jeremy Nixon, Mike Dusenberry, Ghassen Jerfel, Timothy Nguyen, Jeremiah Liu, Linchuan Zhang, and Dustin Tran. 2020. Measuring Calibration in Deep Learning. https://doi.org/10.48550/arXiv.1904.01685 arXiv:1904.01685 [cs, stat]. source

      The Introduction (p. 1) discusses calibrated prediction probabilities, and the other retrieved passages concern classifier calibration. Searches for generative language models, pretraining, and next-token prediction found no passage addressing whether a generative LM is optimized for predictive text performance in its first stage of pretraining. (LLM, conf=0.76)

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Findingnone given

    The adaptive binning definition gives zero miscalibration exactly when g is calibrated to p regardless of the number of bins, whereas other definitions give zero miscalibration whenever there is a single bin.

    “One nice property of the above adaptive binning is that Mis 𝑏 (𝑔, 𝑝) = 0 iff 𝑔 is calibrated to 𝑝, regardless of 𝑏, whereas other definitions give 0 miscalibration whenever there is a single bin.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingreasoning

    For any set, distribution, n≥1, and δ∈(0,1], with probability at least 1−δ the absolute difference between missing mass and the Good-Turing estimator is at most 1/n + 2.42 sqrt(ln(4/δ)/n); and missing mass is at least the Good-Turing estimator minus 1/n minus 2.14 sqrt(ln(2/δ)/n).

    “Pr 𝑠∼D 𝑛 |𝑀 D (𝑠) -𝐺𝑇 (𝑠)| ≤ 1 𝑛 + 2.42 √︂ ln(4/𝛿) 𝑛 ≥ 1 -𝛿. (15 ) Pr 𝑠∼D 𝑛 𝑀 D (𝑠) ≥ 𝐺𝑇 (𝑠) - 1 𝑛 -2.14 √︂ ln(2/𝛿) 𝑛 ≥ 1 -𝛿. (16 )”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning

    For any set, distribution, and n≥1, with probability at least 1−δ the absolute difference between missing mass and the Good-Turing estimator is at most 3 sqrt(ln(4/δ)/n); and for δ≤1/3, missing mass is at least the Good-Turing estimator minus sqrt(6 ln(2/δ)/n).

    “∀𝛿 ∈ (0, 1] Pr 𝑠∼D 𝑛 |𝑀 D (𝑠) -𝐺𝑇 (𝑠)| ≤ 3 √︂ ln(4/𝛿) 𝑛 ≥ 1 -𝛿. (17 ) ∀𝛿 ∈ (0, 1/3] Pr 𝑠∼D 𝑛 𝑀 D (𝑠) ≥ 𝐺𝑇 (𝑠) - √︂ 6 ln(2/𝛿) 𝑛 ≥ 1 -𝛿.(18)”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning

    For the constructed algorithm, for any δ and λ in [0,1], any world distribution, and n≥1, with probability at least 1−δ the hallucination rate is at most the monofact rate and the infinite-bin miscalibration is at most 3 sqrt(ln(4/δ)/n).

    “For any 𝛿, 𝜆 ∈ [0, 1], 𝐷 world , 𝑛 ≥ 1, Pr x train ∼D train 𝑔(𝐻 ) ≤ 𝑀𝐹 and Mis ∞ (𝑔, 𝑝) ≤ 3 √︂ ln(4/𝛿) 𝑛 ≥ 1 -𝛿”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning

    The one-bin miscalibration equals total variation to the uniform distribution, which shows that miscalibration is not monotonic in the number of bins because one bin is minimal for the uniform distribution while infinitely many bins minimize miscalibration for a calibrated distribution.

    “Note that Mis 1 (𝑔, 𝑝) = ∥𝑔 -𝑢 ∥ TV is the total variation to the uniform distribution, which shows that Mis 𝑏 (𝑔, 𝑝) is not monotonic in 𝑏 because 𝑏 = 1 is the minimum for 𝑔 = 𝑢 (regardless of 𝑝) while 𝑏 = ∞ minimizes Mis 𝑏 (𝑝, 𝑝) = 0 for 𝑔 = 𝑝.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingcitation

    For any distribution and n≥1, the Good-Turing estimator exceeds its mean by sqrt(2 ln(1/δ)/n) with probability at most δ, and falls below its mean by that amount with probability at most δ.

    “Pr 𝑠∼D 𝑛 𝐺𝑇 D (𝑠) ≥ 𝐺𝑇 𝑛 D + √︂ 2 ln 1/𝛿 𝑛 ≤ 𝛿 (13 ) Pr 𝑠∼D 𝑛 𝐺𝑇 D (𝑠) ≤ 𝐺𝑇 𝑛 D - √︂ 2 ln 1/𝛿 𝑛 ≤ 𝛿(14)”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Evans et al. point out a difference between factuality and truthfulness, or honesty.

    “Evans et al. [12] points out that there is a difference between factuality and truthfulness (i.e., honesty).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Evans et al. [12]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S2 (checkable), S4 (based).

    Interpretationreasoning

    Even an ideal super-intelligent model should hallucinate if its goal is predictive accuracy.

    “This is consistent with our work in the sense that one would expect even an ideal “super-intelligent” model should hallucinate if its goal is predictive accuracy.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Premisenone given

    The parameters of both types of language models are typically pretrained to maximize likelihood on a corpus, equivalently minimizing KL divergence between the model and the training data distribution.

    “Despite this tension between factuality and predictive accuracy, the parameters of both types of LMs are typically trained or “pretrained” to maximize likelihood on a corpus, or equivalently to minimize the “KL divergence”, a strong statistical discrepancy metric between the LM and the distribution of data on which it was trained.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing). May combine two claims.

    Interpretationreasoning

    There is no clear statistical argument for why closed-domain hallucinations must occur, since they can be avoided by filtering if they are verifiable from the source text and generation.

    “There is no clear statistical argument for why closed-domain hallucinations must occur, since if one can verify such hallucinations from the source text and generation one can avoid them by filtering out generations with such mistakes.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning

    There is an inherent statistical lower bound on how often pretrained language models hallucinate certain facts, and this bound is independent of transformer architecture and data quality.

    “This work shows that there is an inherent statistical lower-bound on the rate that pretrained language models hallucinate certain types of facts, having nothing to do with the transformer LM architecture or data quality.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Premisenone given

    Calibration is meaningful because a calibrated predictor's probabilities can be read as accurate confidences, and it is statistically achievable.

    “Calibration is both meaningful, since a calibrated predictor’s probabilities are interpretable as accurate confidences, and statistically achievable. 2”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Premisenone given

    In Zipfian and other power-law distributions, a constant fraction of entities often appear exactly once even as datasets scale.

    “And in other contexts, such as Zipfian and other power-law distributions, it is often observed that a constant fraction of entities appear exactly once, even as the datasets scale.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Language models fabricate facts not present in a source document even when instructed to use only information present in the source.

    “There, LMs are also found to fabricate facts not present in the source document even when instructed to use only information present in the source.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Significant efforts are made in constructing language model corpora to remove duplicates.

    “First, it is worth noting that significant efforts are made, in constructing LM corpora, to remove duplicates [see, e.g.29].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [see, e.g.29]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Premisenone given

    Hallucination can also be due to an adversarial or out-of-distribution prompt, a textual prefix that establishes context for the language model to complete.

    “Hallucination can also be due to an adversarial or out-of-distribution prompt: a textual prefix provided for the LM to complete which establishes context.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    The equivalence between next-token prediction and document generation holds only if computational costs are disregarded.

    “The equivalence between next-token-prediction and document generation holds only if one disregards computational costs.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Premisenone given

    Many real-world facts are systematic rather than arbitrary.

    “Of course, many real-world facts are systematic, not arbitrary.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisereasoning

    Any language model can be used either to generate text or to predict the next token in naturally occurring text conditioned on previous tokens, though prediction and generation have different desiderata.

    “This mathematically trivial equivalence 1 has a profound implication: any LM can be used either to generate text or predict the next token in naturally occurring text conditioned on the previous tokens, though prediction and generation have different desiderata.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    For any world distribution, there exists an algorithm that is calibrated and whose hallucination rate is close to the missing-facts rate (the Good-Turing estimate), showing that a substantially better lower bound is impossible.

    “In this section, we argue that a significantly better lower-bound is not possible by showing that for any 𝐷 world , there is a algorithm that is calibrated and hallucinates at a rate near the missing facts rate, equivalent its Good-Turing estimate.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Interpretationreasoning

    Correcting hallucinated references may be possible by modifying the pretraining pipeline without post-training, though this would not address other arbitrary facts where monofacts are common.

    “Furthermore, correcting for hallucinated references may be doable by modifying the pre-training pipeline without post-training, though this will not address other types of arbitrary facts where the monofacts are common, as in our 5W example.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisenone given

    Various techniques may identify language model hallucinations from the model itself, using internal weights, token probabilities, or additional questions.

    “Various techniques may be used to identify LM hallucinations purely from the LM itself, either the internal weights, its token probabilities, or by querying it with additional questions.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationreasoning

    Hallucinated references may arise from other issues such as model capacity, given the large number of facts a language model encounters in training.

    “Therefore, these may arise from other issues such as model capacity, when one considers the shear number of facts including references and others that an LM encounters in training.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Interpretationreasoning

    A disadvantage of semantic-level calibration is that measuring calibration rates may be intractable, so experimental validation may be easier in synthetic settings where facts have canonical descriptions.

    “This is also a disadvantage, however, because it means that it may be intractable to measure calibration rates, and thus experimental validation may be easier in synthetic settings where facts have canonical descriptions.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.

    Interpretationreasoning

    The regularity parameter will be prohibitively large if there are predictable eaters, and language models might hallucinate less if there are many predictable eaters because a learning algorithm may learn those patterns.

    “However the regularity parameter 𝑟 will be prohibitively large if there are predictable eaters, and indeed 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.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Interpretationreasoning

    The monofact rate can illuminate the rates at which calibrated language models must hallucinate for different kinds of facts.

    “The monofact rate may shed light on the rates at which calibrated LMs must hallucinate for different types of facts.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Adaptive binning has been used in supervised classification.

    “Adaptive binning has been used in supervised classification [e.g., 26].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [e.g., 26]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Premisenone given

    The regularity constant is 1 for symmetric distributions and other simple distributions.

    “This constant is 1 for symmetric distributions and other types of simple distributions.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.

    Premisenone given

    Real-world distributions are non-stationary and dynamic, and real-world training data contains duplicates and is not independent and identically distributed.

    “Of course, real-world distributions are non-stationary and dynamic, and realworld training data contains duplicates and is not i.i.d.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given

    The term involving the ratio of the number of arbitrary facts to similar false pieces of information is exponentially small for many types of information.

    “We also have a term involving the ratio of the number of arbitrary facts to similar pieces of information that are false, which is exponentially small for many types of information.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: There are many fewer facts than hallucinations; specifically, with probability 1 over the world distribution, the number of facts is at most e to the minus s times the number of hallucinations.

  • Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing).

    Interpretationreasoning

    The paper's lower bound can shed light on the different rates at which different types of facts should be hallucinated.

    “Moreover, it gives a lower-bound on the rate of hallucination, which can shed light on the different rates at which different types of facts should be hallucinated.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    Compared with the simplified setting, hallucination may be even more likely when the language model is prompted with contexts drawn from a different distribution than the training data.

    “Again, compared to our simplified setting, hallucination may be even more likely in the more realistic case where the LM is prompted with contexts that come from a different distribution than the training data.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Premisenone given

    An advantage of semantic-level calibration is that it naturally models the exponentially many ways to describe any given fact, unlike token-level calibration models.

    “An advantage of semantic-level calibration is that it naturally models the exponentially many ways there are to describe any given fact, unlike token-level calibration models.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationreasoning

    If the probability of hallucination is small, then hallucinations will be rare.

    “However, if this probability is small, then hallucinations will be rare.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    The final 7 over square root of n term is small for the large training set sizes used in today's language models.

    “The final 7/ √ 𝑛 term is small for the large training set sizes 𝑛 used in today’s LM.”
    Quote in the paperNot a substantial claim
43 of 43

  • The authors state this as an assumption.

    Each document contains at most one factoid.

    “One-per-doc: First, we assume that there is at most one factoid per document by defining a surjective function 𝑓 : 𝑋 ↠ 𝑌 which extracts a single factoid with each document”

  • The authors state this as an assumption.

    Training data consists solely of facts, and every fact has nonzero probability of being described under the language distribution.

    “Good-training-data: Second, we assume that the set of facts 𝐹 := supp(𝑝) ∪ {⊥} where supp(𝑝) = {𝑦 ∈ 𝑌 | 𝑝 (𝑦) > 0} = 𝑓 (supp(𝐷 𝐿 )), i.e., the training data consists solely of facts and every fact has non-zero probability of being described under 𝐷 𝐿 .”

  • The authors state this as an assumption.

    There are many fewer facts than hallucinations; specifically, with probability 1 over the world distribution, the number of facts is at most e to the minus s times the number of hallucinations.

    “Assumption 1 (𝑠-Sparse facts). There are many fewer facts than hallucinations.Specifically, there exists 𝑠 ∈ R such that, with probability 1 over 𝐷 𝐿 ∼ 𝐷 world : |𝐹 | ≤ 𝑒 -𝑠 |𝐻 |.”

  • The authors state this as an assumption.

    No single factoid is very likely; under perfect regularity, after observing training data, all unobserved factoids are equally likely to appear as facts in the language distribution.

    “Finally, and most importantly, we assume that no single factoid is very likely.Specifically, perfect regularity requires that after observing the training data, all unobserved factoids are equally likely to appear as facts in the language distribution”

  • The authors state this as an assumption.

    The world is static and does not change, and training data are independent and identically distributed without factual errors.

    “This model requires a static world that does not change.Of course, real-world distributions are non-stationary and dynamic, and realworld training data contains duplicates and is not i.i.d.However, our lower bounds imply hallucination even in this ideal static setting.”

  • The authors state this as an assumption.

    Factoids are arbitrary, so given the facts observed in training data one cannot infer any likely facts among the unobserved factoids.

    “Their arbitrary nature means that, given the facts observed in training data, one cannot infer any likely facts among the unobserved factoids.”

  • The authors state this as an assumption.

    There is a large but finite set of factoids, meaning arbitrary plausible pieces of information that could be true facts or false hallucinations as determined by a world distribution.

    “We assume there is a large but finite set 𝑌 of “factoids” by which we mean arbitrary plausible pieces of information, each of which could be true (facts) or false (hallucinations), as determined by some world distribution.”

  • The authors state this as an assumption.

    The correctness of arbitrary factoids not contained in the training data cannot be determined.

    “If the correctness of arbitrary factoids not contained in the training cannot be determined, the missing fact rate can provide a lowerbound on the rate of hallucination.”

  • The authors state this as an assumption.

    The idealized setting holds: training data is perfectly factual, there is no blur between facts and hallucinations, each document contains at most one fact, and no prompt encourages hallucination.

    “even in an ideal world where the training data is perfectly factual, there is no blur between facts and hallucinations, each document contains at most one fact, and there is not even a prompt that would encourage hallucination.”

  • The authors state this as an assumption.

    The world distribution is regular, with 1-regular facts and 1-regular probabilities.

    “For a regular 𝐷 world , because it has 1regular-facts and 1-regular-probabilities, with probability 1 the posterior satisfies:”

  • The authors state this as an assumption.

    The world distribution is s-sparse and has r-regular facts and r-regular probabilities.

    “Fix any 𝛿 ∈ [0, 1], 𝑏, 𝑛 ∈ N, 𝑟, 𝑠 ∈ R and any 𝑠sparse 𝐷 world with 𝑟 -regular-facts and 𝑟 -regular-probabilities.”
11 of 11

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • More careful data curation may mitigate some misinformation ingested by LLMs, though data alone cannot entirely eliminate other LLM concerns like hallucinations.

    “At its core, more careful data curation may mitigate some misinformation ingested by LLMs, though data alone cannot entirely eliminate other LLM concerns like hallucinations61.”

    From Medical large language models are vulnerable to data-poisoning attacks (2025) · cites this paper as [61]

    The ‘Why LMs hallucinate’ section identifies inaccurate training data as one possible cause, but it does not assess whether more careful curation mitigates misinformation ingested by LLMs. The Conclusions state that predictive pretraining can produce hallucinations even with perfectly factual data, supporting the claim that better data alone does not address every source of hallucination. That finding is bounded to the paper’s idealized setting and calibrated models. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • LLMs hallucinate, i.e., produce plausible-sounding but false or fallacious statements.

    “First, they hallucinate, i.e., produce plausiblesounding but false or fallacious statements (Kalai and Vempala, 2024;Maleki et al., 2024).”

    From There is no such thing as conscious artificial intelligence (2025) · cites this paper as Kalai and Vempala, 2024

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Zero miscalibration does not characterize calibration for every bin count

    Minor

    The paper says that g = p is calibrated to p. But it also states that with one bin, miscalibration is the distance from g to the uniform distribution; this is nonzero whenever g = p is nonuniform, contradicting the claimed equivalence for every bin count.

  • Dictionary citation points to a different bibliography entry

    Minor

    The introduction cites entry 25 for Merriam-Webster's definition, but entry 25 is a paper about malpractice risk; Merriam-Webster is listed as entry 26. This is part of an apparent numbering shift in the references.

2 of 2

Cites

Flagged first, then by citations

Research works printed but not linked: 5

  1. 10.1093/biomet · DOI
  2. 10.18653/v1 · DOI
  3. 10.18653/v1 · DOI
  4. David A. McAllester and Luis E. Ortiz. 2003. Concentration Inequalities for the Missing Mass and for Histogram Rule Error. https://www.semanticscholar.org/paper/Concentration-Inequalities-for-the-Missing-Mass-and-McAllester-Ortiz/d9379f1b3542f47454da4336173596b9008f642c
  5. 10.18653/v1 · DOI

Cited by

Sorted by citations

Related

Authors
Kalai, A. T., & Vempala, S. S.
Affiliations
  • OpenAI (United States) (US)
  • Georgia Institute of Technology (US)
ORCID
Venue
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
Publisher
ACM
Published
2024-06-10
Pages
160-171
DOI
10.1145/3618260.3649777
OpenAlex
W4399521940
Cited by
91
References
16
Citations by year
2026: 36 · 2025: 38 · 2024: 17
FWCI
26.73
Type
conference paper
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
  • ACM Symposium on Theory of Computing (STOC) (publishedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Funders
NSF (National Science Foundation) (2134105)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Adversarial Robustness in Machine Learning
Keywords
hallucinations, language models, statistical calibration, lower bounds, training data

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-07.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-07.

Cited sources are checked by gpt-6-sol.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review