PaperlayerView exact revision on arXiv

Source-linked AI summary

Hallucinations are inevitable but can be made statistically negligible

Atsushi Suzuki, Yulan He, Feng Tian, Zhongyuan Wang

arXiv:2502.12187v3cs.CLcs.FLcs.LGmath.STstat.MLstat.TH

TL;DR

Computability-theoretic inevitability results leave unclear whether hallucinations on infinitely many inputs constitute a practical limitation for language models. The paper analyzes hallucinations in a discrete computability framework and develops a probabilistic result for qualified training data and suitable algorithms. With sufficient training-data quality and quantity, hallucination probability can be reduced arbitrarily close to zero even though hallucinations remain inevitable on an infinite input set.

  • Problem

    Computability-theoretic inevitability results leave unclear whether hallucinations on infinitely many inputs constitute a practical limitation for language models.

    Source: §1 · pp. 2–3, §3 · p. 7

  • Method

    The paper analyzes hallucinations in a discrete computability framework and develops a probabilistic result for qualified training data and suitable algorithms.

    Source: §1 · p. 3, §2 · pp. 5–6

  • Results

    With sufficient training-data quality and quantity, hallucination probability can be reduced arbitrarily close to zero even though hallucinations remain inevitable on an infinite input set.

    Source: §1 · p. 3, §6 · p. 13

  • Takeaways & Limitations

    Practical hallucination problems should be attributed to dataset quality or quantity and algorithms rather than to diagonal-argument inevitability itself.

    Source: §6 · p. 14

    The analysis assumes with probability 1 that each training output is acceptable, while omitting an extension involving the most frequently appearing output string.

    Source: Remark 15 (Qualified random training… · p. 9

Abstract

from arXiv · show

Hallucinations, a phenomenon where a language model (LM) generates nonfactual content, pose a significant challenge to the practical deployment of LMs. While many empirical methods have been proposed to mitigate hallucinations, recent studies established a computability-theoretic result showing that any LM will inevitably generate hallucinations on an infinite set of inputs, regardless of the quality and quantity of training datasets and the choice of the language model architecture and training and inference algorithms. Although the computability-theoretic result may seem pessimistic, its significance in practical viewpoints has remained unclear. This paper claims that those "innate" inevitability results from computability theory and diagonal argument, in principle, cannot explain practical issues of LLMs. We demonstrate this claim by presenting a positive theoretical result from a probabilistic perspective. Specifically, we prove that hallucinations can be made statistically negligible, provided that the quality and quantity of the training data are sufficient. Interestingly, our positive result coexists with the computability-theoretic result, implying that while hallucinations on an infinite set of inputs cannot be entirely eliminated, their probability can always be reduced by improving algorithms and training data. By evaluating the two seemingly contradictory results through the lens of information theory, we argue that our probability-theoretic positive result better reflects practical considerations than the computability-theoretic negative result.

1 Introduction

The paper argues that computability-theoretic inevitability results do not determine practical hallucination risk: with suitable data and algorithms, hallucinations can have arbitrarily small probability. It integrates computability theory, probability, and information theory to reassess the practical meaning of these results.

1 Introduction

  • Hallucinations complicate practical LM deployment, while prior computability results claim every LM hallucinates on infinitely many inputs regardless of architecture, algorithms, or training data.Source: §1 · pp. 2–3
  • The paper asks whether infinite-set inevitability has practical implications, noting that theoretical discussion is required because numerical simulation cannot rebut computability results.Source: §1 · p. 3
  • With sufficient training-data quality and quantity and suitable algorithms, hallucination probability can be reduced arbitrarily close to zero, even though infinite hallucination sets remain.Source: §1 · pp. 3–4
  • The framework makes no assumptions about natural-language grammar, semantics, or the ground-truth mapping.Source: §1 · p. 3
  • The paper uses information theory to argue that probability-theoretic negligibility better reflects practice than computability-theoretic inevitability.Source: §1 · pp. 3–4

1.1 Related work

  • The technical contribution is an integrated framework combining computability theory and statistical learning theory rather than novel proof techniques.Source: §1.1 · p. 4

2 Preliminaries

The preliminaries model natural language as finite strings and language models as computable maps over those strings. Hallucinations are defined formally as outputs outside an input’s acceptable-output set, with the main analysis focusing on deterministic models.

2 Preliminaries

  • The paper adopts a discrete chatbot framework in which natural-language tokens are finite strings and language models are computable maps from strings to strings.Source: §2 · p. 5
  • The analysis focuses on deterministic LMs, treating them as special cases of stochastic models and aligning the setup with the prior computability-based work.Source: §2 · p. 6
  • The authors note that choosing the best output known not to be a hallucination is a reasonable strategy when hallucination avoidance is prioritized over output diversity.Source: §2 · p. 6
  • The discussion leaves compatibility between hallucination reduction and output diversity, where stochastic LMs may help, for future work.Source: §2 · p. 6
  • The countability of finite strings and computable maps is central to the later computability-theoretic proof.Source: §2 · p. 6
  • An acceptable-output map assigns each input a nonempty set of acceptable strings, and a model hallucinates when its output lies outside that set.Source: §2 · pp. 6–7

3 Innate computability limitation of LMs

The computability-theoretic limitation states that, under a worst-case acceptable-output map, every computable language model hallucinates on infinitely many inputs. The paper presents this as mathematically strong but not itself a practical obstacle.

3 Innate computability limitation of LMs

  • For any computable LM, there exists an acceptable-output map under which the model hallucinates on infinitely many input strings.Source: §3 · p. 7
  • The negative result holds regardless of neural architecture, training and inference algorithms, or training data.Source: §3 · p. 7
  • The paper’s theorem strengthens prior results by using one acceptable-output map for all LMs and avoiding the axiom of choice.Source: §3 · p. 7
  • Although infinite hallucinations may appear fatal to practitioners, the paper argues that this theorem alone is not a practical issue.Source: §3 · p. 8

4 Hallucinations can be made statistically negligible

The paper defines hallucination risk probabilistically and proves that an appropriate trainer can make it statistically negligible under qualified, sufficiently large training data. The result holds without assuming computable ground truth or natural-language grammar, while uniform guarantees additionally require a known input-length CDF lower bound.

4 Hallucinations can be made statistically negligible

  • The framework uses discrete input-output strings, formalizes trainers and qualified random training sequences, and permits arbitrary acceptable-output maps and input distributions.Qualified data are independently sampled inputs whose outputs belong to the acceptable set with probability 1; practical trainers are computable, although the theorem does not require computability.Source: §4 · pp. 8–9
  • Statistical negligibility measures hallucination probability over inputs, rather than the number of input instances that cause hallucinations.The paper defines the target through a high-probability bound on the hallucination probability of the trained model.Source: §4 · p. 8, Remark 15 (Qualified random training… · pp. 9–10
  • The theorem does not assume grammatical or semantic structure, computable ground truth, or a computable trainer, although its positive construction is computable.This broad setting is chosen to align with the computability-based impossibility results while isolating the probabilistic claim.Source: §4 · pp. 8–9, Remark 15 (Qualified random training… · p. 10

Remark 15 (Qualified random training data sequence assumption’s strength)

  • The assumptions are substantive: outputs must be acceptable with probability 1, training data must exceed a sufficient size, and uniform guarantees require an input-length CDF lower bound.The sufficient size can be huge and is nearly optimal in the appendix, though practical assumptions could shorten it.Source: Remark 15 (Qualified random training… · pp. 9, 11, 12
  • Uniform negligibility provides a distribution-independent training-size threshold, whereas non-uniform negligibility allows the threshold to depend on the input distribution.No trainer can achieve uniform negligibility over all probability measures, but non-uniform negligibility remains achievable.Source: Remark 15 (Qualified random training… · pp. 10–11
  • Theorem 21 shows that one trainer makes hallucinations statistically negligible uniformly over input distributions with a known length-CDF lower bound, and non-uniformly over all distributions.The training data must be qualified and sufficiently long; uniform negligibility additionally requires a known lower bound on the input-length CDF.Source: Remark 15 (Qualified random training… · p. 11

5 Paradox and solution: infinite input instances causing hallucinations but with arbitrarily small probability

The computability-theoretic and probabilistic results are compatible because an infinite hallucinating set can have arbitrarily small probability. Information theory therefore treats probability, rather than cardinality alone, as the practically relevant quantity.

5.1 Why can those seemingly contradicting results coexist?

  • The two theorems do not contradict each other: hallucinations may occur on infinitely many inputs while the probability of that infinite set converges to zero.The paper illustrates this with the infinite tail set Z≥m, whose probability is (1/2)^m under a geometric distribution.Source: §5.1 · p. 12

5.2 Infinite set, but with arbitrarily small probability. Which matters in practice?

  • Information theory regards an event with arbitrarily small probability as practically negligible even when the event contains many elements.This interpretation follows the typical understanding of Shannon’s source coding theorem, where negligible information-loss risk is tolerated.Source: §5.2 · p. 13
  • The paper concludes that infinite hallucinations can be practically negligible in application domains where information theory does not create a practical issue.Thus, the probability-theoretic result is presented as more relevant to practical considerations than the computability-theoretic cardinality result.Source: §5 · p. 12, §5.2 · p. 13

6 Conclusion

The conclusion states that sufficient, high-quality data and an appropriate algorithm can make hallucinations statistically negligible. Infinite hallucinating inputs remain possible, but their probability can be reduced through better data and algorithms.

6 Conclusion

  • Sufficiently high-quality and abundant training data, combined with an appropriate algorithm, can make hallucinations statistically negligible even in the worst ground-truth and distribution setting.The conclusion frames this as an existence result about a dataset-algorithm combination.Source: §6 · p. 13
  • Although hallucinations cannot be eliminated on every infinite input set, their probability can be reduced by improving algorithms and training data.The paper therefore attributes remaining practical problems to dataset or algorithm limitations rather than diagonal-argument inevitability alone.Source: §6 · pp. 13–14

Appendix A. Proof and optimality of Theorem 21

The appendix examines why Theorem 21 needs its assumptions and argues that the required training-data size and input-length information are nearly optimal. It uses this analysis to motivate stronger assumptions reflecting natural-language structure.

Appendix A. Proof and optimality of Theorem 21

  • The appendix analyzes Theorem 21 through a trivial algorithm, then proves that its training-data and input-length assumptions are necessary in the worst case.The resulting worst-case data requirement is nearly the same as that needed by the trivial construction.Source: Appendix A · p. 15

A.1 Proof strategy for Definition 16

The proof strategy constructs the Rote Memorizer algorithm to show that, under suitable input-length and training-data conditions, hallucinations are uniformly statistically negligible. The construction also motivates why those conditions cannot simply be omitted.

A.1 Proof strategy for Definition 16

  • Rote Memorizer stores training input-output pairs below a length threshold and recalls them, while longer inputs are ignored because their probability is made small.The threshold balances coverage of short strings against the tail probability of longer inputs; the algorithm is used as a proof tool rather than prescribed for practice.Source: §A.1 · p. 15
  • Proposition 26 establishes uniform statistical negligibility for the Rote Memorizer under qualified random training data and an input-length CDF converging to one.The proposition assumes every input has at least one valid output and defines the relevant distribution class through the CDF.Source: §A.1 · pp. 15–16
  • The construction requires an input-length CDF lower bound so a threshold can exclude a low-probability long-input tail while training data covers shorter strings.Without this lower bound, the training size cannot be fixed to guarantee the needed coverage uniformly.Source: §A.1 · p. 16
  • Because the algorithm rote-memorizes all strings below the threshold, its required training-data size is naturally exponential in that threshold.The paper later shows that neither the CDF condition nor the large-data requirement can be removed by using a more sophisticated algorithm.Source: §A.1 · p. 16

A.2 The input length CDF lower bound is necessary for uniform statistical negligibility

The paper proves a no-free-lunch limitation: without an input-length CDF lower bound, no language-model trainer can guarantee uniformly negligible hallucination probability. This worst-case result is theoretically sharp but is not presented as a practical failure claim.

A.2 The input length CDF lower bound is necessary for uniform statistical negligibility

  • For any language-model trainer and finite training length, a worst-case valid-output map and input distribution can force hallucination probability above a chosen threshold with nontrivial probability.The theorem quantifies over arbitrary trainers and training lengths, establishing impossibility rather than a limitation of the Rote Memorizer alone.Source: §A.2 · pp. 16–17
  • When λH = 1/4, hallucination probability exceeds 1/4 with probability at least 1/3 − ϵ in the worst case over the output map and input distribution.The probability is over the qualified random training data sequence, while the worst case is over the underlying task and input distribution.Source: §A.2 · p. 17
  • The negative theorem is not treated as a practical issue because its lower-bound distribution is only a scalar probability distribution and contains no syntax or semantic information.The result instead demonstrates the optimality of the positive theorem under its assumptions.Source: §A.2 · p. 17

A.3 Discussion on training data size

The training-size discussion shows that exponential data can suffice for statistical negligibility, while a corresponding no-free-lunch theorem makes exponential-scale data necessary in the unrestricted setting. The appendix also constructs the computability-theoretic counterexample explicitly and explains why avoiding the axiom of choice matters for computer-related claims.

A.3 Discussion on training data size

  • Proposition 26 provides a sufficient exponential training-data size, while Theorem 29 gives a converse lower bound of exponential scale in the unrestricted setting.The authors stress that these quantities do not mean such vast datasets are necessary for practical language-model success.Source: §A.3 · pp. 17–18
  • Theorem 29 implies that practical training sizes require stronger assumptions reflecting natural-language structure rather than fully general settings.Otherwise, performance is theoretically constrained to the level achievable by the trivial rote-memorization construction.Source: §A.3 · p. 18

B.1 Proof of Theorem 8

  • The proof of Theorem 8 orders the countable sets of hypotheses and strings, constructs excluded-index sets, and uses a specific map to define an output function that defeats every language model infinitely often.The construction ensures the target map is independent of the chosen language model.Source: §B.1 · p. 18

B.2 Motivation of avoiding depending on the axiom of choice (AC)

  • The proof avoids the axiom of choice by fixing an order in advance and selecting each required index with the minimum operator.This makes the computability-theoretic result independent of arbitrary choices from infinitely many nonempty sets.Source: §B.2 · pp. 18–19

B.3 The dependency of the previous work’s proof on the AC and how we avoided it

The paper replaces the previous proof’s choice-dependent construction with an explicit ordered construction, but limits this axiom-of-choice analysis to the computability-theoretic part.

B.3 The dependency of the previous work’s proof on the AC and how we avoided it

  • The previous proof selected an element from each of infinitely many sets, a step not guaranteed without the axiom of choice.The resulting product of nonempty sets could be empty, so the required selection function would not automatically exist.Source: §B.3 · p. 19
  • This paper fixes orders on the relevant sets and constructs the selection function using the minimum operator, making the proof valid without the axiom of choice.The construction directly addresses the choice-dependence in Xu et al. (2024).Source: §B.3 · p. 19

B.4 Other parts of this paper and the AC

  • The paper does not remove axiom-of-choice dependence from its probability-theoretic results, restricting the independence claim to the purely computability-theoretic section.The authors state that fully excluding such dependence elsewhere is demanding and would not alter implications for the physical world.Source: §B.4 · pp. 19–20

Appendix C. Proof of Proposition 26

The proof bounds hallucination probability by separating short inputs from the tail of the input-length distribution and controlling the short-input error through sampled training data.

Proof of Proposition 26

  • For any ϵ_H, ϵ_T ∈ (0, 1), Proposition 26 obtains HP_µ(A(T)) < ϵ_H with probability at least 1 − ϵ_T when the training size exceeds a bound determined by the input-length tail.The bound uses an integer n̄ satisfying 1 − CDF(n̄) < 1/2 min{ϵ_H, ϵ_T}.Source: Appendix C · p. 21
  • The overall hallucination probability is decomposed into errors on inputs of length at most n and the remaining input-length tail.The tail is controlled through 1 − CDF(n), while the short-input term is handled by the training-sample coverage argument.Source: Appendix C · p. 21
  • The proof orders inputs up to length n by probability and shows that covering sufficiently probable inputs in the training sample makes the short-input hallucination probability smaller than ϵ′_H.The sampled inputs are independent, and the proof bounds the probability that the training data misses the relevant high-probability inputs.Source: Appendix C · p. 21
  • The miss probability is bounded using independence and (1 − p_j)^m ≤ exp(−m p_j), yielding an exponential decrease as training size m grows.The argument applies the inequality 1 + x ≤ exp(x) after bounding the probabilities of the relevant inputs.Source: Appendix C · pp. 21–22

Appendix D. Proof strategy for LM limitations and no-free-lunch-theorem

This appendix combines a constructive positive result with no-free-lunch arguments for algorithm-independent limitations. The positive result uses a specific algorithm, whereas the negative results require showing that high hallucination risk persists for every algorithm.

Proof strategy

  • Proposition 26 is proved constructively by exhibiting an algorithm whose hallucination probability becomes small with suitable training data, while Theorems 27 and 29 use no-free-lunch reasoning against arbitrary algorithms.The proof strategy differs because negative results must establish bad events regardless of the learner used.Source: Appendix D · pp. 23–24

General no-free-lunch theorem

  • The general no-free-lunch theorem defines hallucination probability as the 0-1 risk HP_µ,f0(h) = Pr(h(X) ≠ f0(X)) and provides lower bounds for arbitrary learning algorithms.The theorem applies to training sizes m ≤ 1/2|X| and constructs a computable ground-truth map and finite subset yielding the lower bound.Source: Appendix D · p. 23

Corollary and bounds

  • When |Y| ≥ 2, the theorem gives µ ≥ 1/4 and λ_T ≥ 1 − 4λ_H, while Corollary 35 extends the result to infinite output sets.These bounds quantify the probability over training data that hallucination risk exceeds λ_H.Source: Appendix D · p. 23

Relation to prior theory

  • Theorem 33 is a generalized no-free-lunch theorem related to Shalev-Shwartz and Ben-David (2014), with a tighter bound when |Y| ≥ 3.The appendix states that the proof technique remains essentially the same as in the cited theorem.Source: Appendix D · p. 24

General no-free-lunch theorem

  • The no-free-lunch proof averages risk over possible functions and datasets, showing that every learner performs poorly for at least one function.The high-risk probability bound then follows by applying a variant of Markov’s inequality.Source: Appendix D · pp. 25–26
Loading 2502.12187v3…