PaperlayerView exact revision on arXiv

Source-linked AI summary

Hallucination is Inevitable: An Innate Limitation of Large Language Models

Ziwei Xu, Sanjay Jain, Mohan Kankanhalli

arXiv:2401.11817v2cs.CLcs.AIcs.LG

TL;DR

LLM hallucination is difficult to eliminate because correctness is hard to formalize in the real world. The paper defines a computable formal world and uses learning-theoretic results to show that hallucination is inevitable for computable LLMs, with implications for mitigation and safe deployment.

  • Problem

    Hallucination produces plausible but factually incorrect or nonsensical information, while formally defining real-world correctness remains difficult.

  • Method

    The paper defines hallucination as inconsistency between a computable LLM and a computable ground truth function, then applies learning-theory results in a formal world.

  • Results

    The paper shows that hallucination is inevitable for computable LLMs and therefore cannot be eliminated in real-world LLMs, independently of implementation details.

  • Takeaways & Limitations

    Because hallucination is inevitable, the paper emphasizes rigorous study of LLM safety and discusses mitigators and deployment implications.

  • Takeaways & Limitations

    The analysis does not cover hallucinations on problems within LLMs’ computational capabilities and assumes a deterministic ground truth function.

Abstract

from arXiv · show

Hallucination has been widely recognized to be a significant drawback for large language models (LLMs). There have been many works that attempt to reduce the extent of hallucination. These efforts have mostly been empirical so far, which cannot answer the fundamental question whether it can be completely eliminated. In this paper, we formalize the problem and show that it is impossible to eliminate hallucination in LLMs. Specifically, we define a formal world where hallucination is defined as inconsistencies between a computable LLM and a computable ground truth function. By employing results from learning theory, we show that LLMs cannot learn all the computable functions and will therefore inevitably hallucinate if used as general problem solvers. Since the formal world is a part of the real world which is much more complicated, hallucinations are also inevitable for real world LLMs. Furthermore, for real world LLMs constrained by provable time complexity, we describe the hallucination-prone tasks and empirically validate our claims. Finally, using the formal world framework, we discuss the possible mechanisms and efficacies of existing hallucination mitigators as well as the practical implications on the safe deployment of LLMs.

1 Introduction

Prior hallucination research has mainly been empirical, leaving unresolved whether hallucination can be completely eliminated. This paper formalizes hallucination and argues that it is inevitable for computable LLMs.

  • Hallucination occurs when LLMs generate plausible but factually incorrect or nonsensical information.
  • Existing work has identified potential causes across data collection, training, and inference, and has proposed metrics, benchmarks, and mitigation methods.
  • Empirical research cannot determine whether hallucination can be completely eliminated because it cannot test every possible input.
  • The paper defines a formal world in which hallucination is an inconsistency between a computable LLM and a computable ground truth function.
  • Its contributions include proving inevitability for computable LLMs, discussing mitigators and deployment, and empirically validating hallucination-prone problems.

2 Definitions

The paper models trained LLMs as computable functions that learn from ground-truth input-output samples and are evaluated against unseen inputs. Hallucination is defined as persistent disagreement with the ground truth across training states.

  • 2.1 Large Language Model: The formal framework represents strings over a finite alphabet and treats an LLM after training as a total computable function.
  • 2.1 Large Language Model: LLM states h[i] represent successive training stages, and the training process and resulting states are assumed uniformly computable.
  • 2.1 Large Language Model: P-property LLMs form computably enumerable subsets of total computable functions, such as models constrained to polynomial-time computation.
  • 2.2 A Formal World and Hallucination: A formal world G_f contains every input string s paired with its sole correct output f(s), while training samples T provide selected pairs from that world.
  • 2.2 A Formal World and Hallucination: An LLM hallucinates with respect to f when every training state has at least one input on which h[i](s) differs from f(s).
  • 2.2 A Formal World and Hallucination: The fundamental question asks whether a fixed training procedure can eventually produce a state matching any computable ground-truth function on every input.
  • 2.3 Training an LLM: The framework trains an LLM iteratively on a stream of ground-truth samples, checks it after stopping criteria, and then deploys the final trained state.
  • 2.3 Training an LLM: Because the formal LLMs are more powerful than real-world counterparts, inevitability in the formal setting is used to infer inevitability for real-world LLMs.

3 Hallucination is Inevitable for LLMs

Using diagonalization and learning-theoretic results, the paper shows that computable LLMs inevitably hallucinate for some computable ground-truth functions, sometimes on infinitely many inputs. This yields a negative answer to whether hallucination can be eliminated, including for real-world LLMs under the paper’s formal assumptions.

  • 3.1 Computably Enumerable LLMs will Hallucinate: Diagonalization constructs a computable ground-truth function that contradicts the outputs of every state in any computably enumerable set of LLMs.The proof enumerates LLM states and defines ground truth values to differ from diagonal outputs.
  • 3.1 Computably Enumerable LLMs will Hallucinate: Every LLM state in a computably enumerable set can be forced to hallucinate on infinitely many inputs.For each input, the constructed ground truth differs from the outputs of a growing set of LLMs, so each enumerated LLM eventually disagrees on all later inputs.
  • 3.2 Any Computable LLM will Hallucinate: The result extends from computably enumerable sets to any total computable LLM: some computable ground-truth function makes every training state hallucinate.An individual computable LLM forms a computably enumerable singleton set, allowing Theorems 1 and 2 to apply.
  • 3.2 Any Computable LLM will Hallucinate: A computable linear ordering provides a concrete hallucination-prone example, covering abstractions such as rankings, chronology, and alphabetical sorting.The theorem constructs an ordering on which the LLM hallucinates after training on comparisons among earlier elements.
  • 3.2 Any Computable LLM will Hallucinate: The paper concludes that no computable LLM can eliminate hallucination, and this conclusion is independent of architecture, training procedure, and prompts under the formal definitions.The corollary also indicates that LLM-based mitigation methods, including prompt-based chain-of-thought, cannot eliminate hallucination.

4 Discussion

The discussion identifies tasks that exceed a given LLM set’s computational capabilities as hallucination-prone and examines why common mitigators cannot guarantee elimination. It draws practical safety boundaries around autonomous LLM use.

  • 4.1 Identifying Hallucination-Prone Problems: Hallucination-prone problems are those whose computable ground-truth functions cannot be learned by the given set of LLMs.The paper proposes identifying such problems by finding ground-truth functions that all models in the set fail to learn.
  • 4.1 Identifying Hallucination-Prone Problems: Listed examples include combinatorial listing, Presburger arithmetic, Subset Sum, and entailment problems in propositional and first-order logic.The listed tasks span exponential-time, co-NP-complete, and undecidable problems.
  • 4.1 Identifying Hallucination-Prone Problems: Mathematical and logic-reasoning answers from real-world LLMs should be subject to proper scrutiny.The paper illustrates this concern empirically through the combinatorial list problem and learning all computable linear orders.
  • 4.2 Existing and Possible Hallucination Mitigators: Increasing parameters, training data, or ensemble size cannot eliminate hallucination when the ground-truth function lies beyond the LLMs’ computational class.For polynomial-time LLMs, larger models may address polynomial-time functions but not exponential-time functions; ensembles remain bounded by the same theorem.
  • 4.2 Existing and Possible Hallucination Mitigators: Prompting can mitigate hallucination for specific tasks but cannot eliminate it merely by changing prompts.The discussion places Chain of Thoughts, Reflections, and Verification within in-context learning.
  • 4.2 Existing and Possible Hallucination Mitigators: Guardrails and fences can explicitly constrain model behavior, while knowledge-enhanced LLMs provide information beyond input-output training samples; both approaches face real-world scalability questions.Guardrails and fences align outputs with values or restrict critical automation, whereas knowledge-enhanced systems use retrieval and symbolic reasoning.
  • 4.3 Practical Implications: Without external aids or human control, LLMs cannot be used automatically in safety-critical decision-making.The paper identifies guardrails, fences, knowledge bases, and human involvement as relevant external controls.
  • 4.4 Limitations: The formal analysis does not cover hallucinations on problems within LLMs’ computational capabilities and assumes deterministic ground-truth functions.The empirical study also uses existing LLMs without further fine-tuning.

5 Related Works

Related work classifies hallucination, studies causes across data, training, and inference, and develops measurement, retrieval, prompting, and data-focused mitigation approaches.

  • 5 Related Works: Recent surveys provide extensive reviews of hallucination, while this paper relates its analysis to PAC learnability and online learnability.The latter relationship is discussed in the appendix.
  • 5 Related Works: Hallucination is commonly divided into intrinsic cases that contradict the input and extrinsic cases that cannot be verified from it.The literature also introduces faithfulness hallucination and terms such as factual mirage and silver lining.
  • 5 Related Works: Reported causes span poor-quality, misleading, biased, or outdated data, long-tailed knowledge, and deficiencies in model architecture or training strategy.The paper frames hallucination as arising across data, training, and inference stages.
  • 5 Related Works: Mitigation work includes fact-focused datasets, automatic data cleaning, retrieval augmentation, and prompting methods such as Chain-of-Thought and Tree-of-Thought.These methods target data quality, knowledge gaps, knowledge recall, or reasoning.

6 Conclusion

The conclusion states that hallucination is inevitable for computable LLMs under the paper’s formal framework and extends this conclusion to real-world LLMs. It emphasizes urgent safety research and deployment implications.

  • 6 Conclusion: The paper defines hallucination as inconsistency between a computable LLM and a computable ground-truth function.This formal world makes precise discussion possible despite the difficulty of defining real-world semantics.
  • 6 Conclusion: Learning-theoretic results show that computable LLMs inevitably hallucinate when the ground-truth function is any computable function.The conclusion extends the formal result to real-world LLMs because the formal world is part of the real world.
  • 6 Conclusion: The paper discusses hallucination mitigators and the practical implications of its theoretical results for real-world LLM deployment.It emphasizes rigorous LLM safety study as critical and urgent.

B Implementation of Large Language Models

LLMs model token-string probabilities autoregressively and commonly complete prompts by maximizing the likelihood of a full string. Their implementation and training combine Transformer architectures with several training paradigms.

  • B Implementation of Large Language Models: LLMs assign each token a likelihood conditioned on all preceding tokens in the string.This defines the autoregressive string model used in the paper’s formulation.
  • B Implementation of Large Language Models: Prompt completion generates a complete string from a partial string by maximizing the likelihood of the full sequence.The partial string is the prompt.
  • B Implementation of Large Language Models: Completion proceeds iteratively one token at a time and stops after a fixed number of iterations or when a stopping token appears.The stopping condition can therefore be iteration-based or token-based.
  • B Implementation of Large Language Models: State-of-the-art LLMs generally use multilayer Transformer networks equipped with attention mechanisms.The paper describes typical models as having billions of parameters and training corpora containing trillions of tokens.
  • B Implementation of Large Language Models: Training commonly combines unsupervised pretraining, supervised fine-tuning, and reinforcement learning from human feedback.These procedures respectively target general completion, task-specific samples, and societal value alignment.

C Empirical Study: Can LLMs List Them All?

The study tests whether LLMs can enumerate every fixed-length string, finding that all models eventually fail as task size grows, even when answers fit comfortably within context windows.

  • Results: Model parameter count and context size do not significantly affect performance on this task; the tested models are described as equally poor.The paper presents the task as an empirical validation of polynomial-time LLM limitations.
  • Task and evaluation: The experiment asks LLMs to list all strings of length m over specified alphabets, using three random seeds per task.Success requires one run to contain all and only valid strings; duplicate entries are permitted.
  • Models: The evaluation covers Llama 2, Llama 3, and GPT model families, including 70-billion-parameter Llama variants.The tested models have context windows of at least 4096 tokens.
  • Results: All tested LLMs eventually failed on L(m, {a, b}) and L(m, {a, b, c}) as m increased.Table C2 records success with ✓ and failure with ✗, including an alphabet-sensitive exception for gpt-4-turbo-2024-04-09.
  • Results: The answer for L(7, {a, b}) contains 128 strings and is approximately 896 characters, yet remains much shorter than the tested context windows.This indicates that context length alone does not explain the observed failures.

D.1 Theoretical Results

The theoretical results construct computable orderings that force any computable LLM to err on local and global questions, while experiments show corresponding reasoning failures.

  • Local ordering questions: For every computable LLM, there exists a computable ordering on which it hallucinates when answering whether s2n+1 < s2n after finite training.The construction defines the ordering to contradict the model’s answer at each stage.
  • Local ordering questions: The construction remains computable because each stage defines the ordering for finitely many new pairs using the computable LLM’s output.Increasing n corresponds to providing more training samples to the model.
  • Global ordering questions: A computable ordering can also force infinitely many errors on the global question of whether the ordering is isomorphic to N or Z.The theorem states that this occurs for infinitely many training stages.
  • Theoretical implication: Together, Theorem 4 and Theorem D1 show hallucinations on both local and global linear-order properties regardless of the number of training samples.The paper frames these results as applying to computable LLMs in a controlled world.
  • Empirical study: In the empirical ω(m) task, all LLMs failed; ω1 errors involved transitivity, while ω2 answers were often inconsistent in opposite directions.The evaluation used paired statements and allowed “unknown” for ω2 when appropriate.

E Identifying Limits on LLMs’ Capabilities

The paper bounds which computable functions can be learned without hallucination, while also identifying a class of functions that some LLMs can learn from finite examples.

  • Upper bound: The set of ground-truth functions on which a computable LLM can become hallucination-free after finite training is contained in a computably enumerable set of total computable functions.This is stated as Theorem E2.
  • Upper bound: The proof enumerates all finite training sets and associates each with a total computable function induced by the trained LLM.It establishes containment first, then shows the containing set is computably enumerable.
  • Practical boundary: The paper notes that undecidable real-world problems, such as deciding whether a program halts, cannot be solved by LLMs under this framework.The limitation follows because such problems are not computable.
  • Learnable functions: Some computable functions are learnable: for every computably enumerable set of total computable functions, some LLM can become hallucination-free on each member after at most k samples.This is the result stated in Theorem E3.
  • Learnable functions: The nth-character task R(m, n) is reported as learnable by some, but not all, LLMs.In the experiment, all models performed well for R(∗, 1) after five examples and testing on five new strings.

F In Defence of LLMs and Hallucination

The paper frames LLM use as a precision–efficiency trade-off: hallucinations may be acceptable in high-volume settings, reducible but not eliminable, and potentially useful creatively.

  • Deployment trade-offs: LLM use involves a trade-off between precision and efficiency shaped by the application.The paper describes speed and large-scale information processing as benefits that can make occasional inaccuracies acceptable.
  • Future mitigation: Hallucination severity may be controlled and reduced for many applications, although complete elimination remains impossible.The paper connects this expectation to continuing advances in models, data, training, and error correction.
  • Creative applications: In art, literature, and design, unpredictable or nonsensical outputs may inspire unique perspectives, innovation, and creativity.The paper therefore does not treat hallucination as entirely detrimental in these settings.

G.1 PAC Unlearnability does not answer Question 1

The paper distinguishes practical PAC-style learnability limits from the stronger question of whether hallucination can ever be eliminated, showing that conventional online unlearnability does not answer it.

  • There is no O-time algorithm that finds an LLM with hallucination rate at most ϵ across all formal worlds and input distributions with probability 1−δ.
  • No computably enumerable set of LLMs is hallucination-free in every formal world, regardless of time-complexity and error-rate assumptions.
  • Statement 1 concerns practical learnability under bounded complexity and error assumptions, whereas Statement 2 addresses learnability without those assumptions.
  • Infinite Littlestone dimension does not imply inevitable hallucination: an LLM can learn functions that differ from zero on only finitely many inputs.
  • The discussion leaves open which real-world problems LLMs can solve without hallucination and how external knowledge or reasoning tools might detect and correct errors.
Loading 2401.11817v2…