LLMs Will Always Hallucinate, and We Need to Live With This

Sourav Banerjee; Ayushi Agarwal; Saloni Singla

Source-linked AI summary

LLMs Will Always Hallucinate, and We Need to Live With This

Sourav Banerjee, Ayushi Agarwal, Saloni Singla

arXiv:2409.05746v1Sep 9, 2024stat.MLcs.LG

TL;DR

The paper examines whether hallucinations can be fully eliminated from increasingly consequential LLM applications. Using computational theory and undecidability arguments, it concludes that structural hallucinations remain inevitable across the LLM process. The paper therefore challenges claims that architectural, data, or fact-checking improvements can remove them completely.

Problem
As LLMs become influential in fields such as healthcare and education, hallucinations remain an intrinsic challenge requiring critical examination of model limitations.
Method
The paper uses computational theory and arguments about undecidable problems, extending its analysis beyond Turing machines to oracle Turing machines.
Results
The paper concludes that structural hallucinations cannot be fully eliminated, and reports verifying this conclusion with a single prompt.
Takeaways & Limitations
Faithful explanations can help users understand generation processes and spot hallucinations, but hallucinations remain an intrinsic feature of LLM generation.
Takeaways & Limitations
The analysis extends its undecidability claims to three problems on oracle machines: the Halting, Emptiness, and Acceptance Problems.

Abstract

from arXiv · show

As Large Language Models become more ubiquitous across domains, it becomes important to examine their inherent limitations critically. This work argues that hallucinations in language models are not just occasional errors but an inevitable feature of these systems. We demonstrate that hallucinations stem from the fundamental mathematical and logical structure of LLMs. It is, therefore, impossible to eliminate them through architectural improvements, dataset enhancements, or fact-checking mechanisms. Our analysis draws on computational theory and Godel's First Incompleteness Theorem, which references the undecidability of problems like the Halting, Emptiness, and Acceptance Problems. We demonstrate that every stage of the LLM process-from training data compilation to fact retrieval, intent classification, and text generation-will have a non-zero probability of producing hallucinations. This work introduces the concept of Structural Hallucination as an intrinsic nature of these systems. By establishing the mathematical certainty of hallucinations, we challenge the prevailing notion that they can be fully mitigated.

1.1 Background

LLMs generate text by predicting likely linguistic patterns rather than understanding language or truth. Their apparent intelligence comes from mimicking thought products through next-token prediction.

LLMs are increasingly used in fields such as healthcare and education, while hallucinations remain an intrinsic challenge.
LLMs address the question of which word is likely to come next given a sequence of words.
A transformer-like language model represents a token sequence and computes conditional probabilities for the next token.
Despite apparently intelligent behavior, the model has learned to mimic products of thought rather than think or possess a concept of truth.

1.2 Architectures of Large Language Model Generation

LLM generation architectures convert tokens into position-aware representations, use attention or alternative sequence models to process them, and produce probabilistic transitions. The section also introduces Mamba and KANs as architectural alternatives.

Tokens may be words, word parts, or characters, with special tokens marking sequence boundaries such as BOS and EOS.
Absolute positional encoding adds semantic and positional vectors so the model can distinguish word order.
Self-attention uses query, key, and value vectors, computes attention from query-key dot products, and returns a weighted value sum.
Relative positional encoding represents distances between words, while RoPE combines positional information through rotations.
Mamba: Mamba uses data-dependent gating and matrices to provide efficient sequential processing with linear-time complexity for long contexts.
KANs: KANs approximate multivariate functions through compositions of single-variable functions and use learnable edge activations instead of fixed node activations.

1.3 Transfer Learning

Transfer learning adapts pretrained models to specific data, while PEFT reduces the number of trainable parameters. RAG supplements model inputs with retrieved information to support more factually grounded outputs.

Transfer learning aligns pretrained model parameters with specific data to improve task performance.
PEFT: PEFT updates fewer parameters than traditional fine-tuning, reducing computational costs while helping models adapt to tasks.
PEFT: Adapters add small trainable modules, whereas BitFit updates bias terms and a task-specific classification layer.
PEFT: LoRA keeps pretrained weights frozen and represents dense-layer updates with low-rank matrices A and B.
PEFT: For a d×m weight matrix, LoRA reduces parameters from d × m to (d × r) + (r × m), with r << min(d, m).
RAG: RAG retrieves relevant documents, combines them with the input, and generates output from the augmented context.

1.4 Hallucinations in LLMs: What They Are and How They Happen

LLM hallucinations are false, fabricated, or context-inconsistent outputs that can arise through factual errors, misinterpretation, incomplete retrieval, and fabrication. These failures can create serious societal, legal, health, trust, and bias-related consequences.

Hallucinations are plausible-sounding but incorrect outputs that may range from subtle inaccuracies to entirely fictional assertions.
Factual inaccuracies: Factual inaccuracies misrepresent existing information, such as reporting an incorrect patient measurement.
Misinterpretation: Misinterpretation occurs when models misunderstand corpus intent or user prompts, including ambiguous terms such as “lead.”
Retrieval failures: The needle-in-a-haystack problem describes failures to retrieve specific information, producing omissions or mixtures of accurate and inaccurate facts.
Fabrications: Fabrications are invented statements without supporting training data or actual retrieval.
Consequences: Hallucinations can spread misinformation, create legal and ethical risks, harm public health, erode trust, and amplify bias.

1.5 Identification of LLM Hallucination and Mitigation Strategies

The section reviews strategies for identifying or mitigating hallucinations across LLM generation stages, while emphasizing that these techniques cannot eliminate hallucinations entirely.

Chain-of-Thought prompting makes reasoning explicit and can reduce logical errors, but models may still produce factually incorrect reasoning chains.
Self-consistency generates multiple Chain-of-Thought paths and selects the most consistent answer because hallucinations or errors are expected to vary more.
Uncertainty quantification uses class-probability distributions and related stability measures to identify potential hallucinations, but it does not prevent confidently wrong outputs.
Faithfulness explanations, including Shapley values, help users assess whether explanations reflect model reasoning and identify how features or data contribute to predictions.
The reviewed approaches target training, intent classification, retrieval, output generation, and post-generation checking, yet hallucinations remain ineliminable across these stages.

2 All Hallucinations are Structural Hallucinations

The paper defines structural hallucinations as inherent to the mathematical and logical structure of LLMs. It argues that incomplete data, nondeterministic retrieval and classification, and undecidable generation behavior make hallucinations unavoidable.

2 All Hallucinations are Structural Hallucinations: Structural hallucinations are presented as an inherent part of the mathematical and logical structure of any LLM.
2 All Hallucinations are Structural Hallucinations: Each stage of LLM generation carries a non-zero probability of structural hallucination, regardless of model sophistication or training-data size.
2 All Hallucinations are Structural Hallucinations: Training data cannot be complete because human knowledge is vast and continually changing, leaving the model without 100% a priori knowledge.
2 All Hallucinations are Structural Hallucinations: Even complete data would not guarantee correct retrieval or intent classification, because LLMs cannot perform either operation with probability 1.
2 All Hallucinations are Structural Hallucinations: Undecidable halting behavior means an LLM cannot know exactly where generation will stop and may produce any token sequence.
2 All Hallucinations are Structural Hallucinations: These limitations allow LLMs to produce inconsistent, contradictory, self-referential, or paradoxical statements that cannot be fully eliminated.
2 All Hallucinations are Structural Hallucinations: The computational argument uses reductions from known undecidable problems to conclude that the target problem has no Turing-machine decider.

3 Hallucination is Inevitable: Claims and Proofs

The paper argues that hallucinations are inevitable because training data cannot be complete and retrieval cannot be perfectly reliable. It supports these claims through undecidability-based proofs for data completeness and needle-in-a-haystack retrieval.

Training data: No training dataset can contain all true facts, so increasing dataset size cannot eliminate structural hallucinations.The paper frames this as Assertion 1 and argues that every finite database remains incomplete.
Training data: The proof considers whether a Gödel-like statement about facts outside the training database is true or false.In either case, the generation is treated as hallucinating: if false, it is an incorrect generation; if true, it is unverifiable from the database.
Training data: When a true fact lies outside the database, no statement in that database can verify the generated claim.The paper therefore characterizes the output as an unverifiable hallucination.
Information retrieval: Even complete training data would not guarantee deterministic retrieval of the correct information.The paper studies retrieval as a needle-in-a-haystack problem and asserts that it is undecidable.
Information retrieval: Assuming needle-in-a-haystack retrieval were decidable would yield a decider for the undecidable Acceptance Problem.The contradiction is used to conclude that an LLM cannot know in advance whether it will select the intended needle.

Contradiction:

The paper extends its undecidability argument from retrieval to intent classification. It concludes that models cannot completely solve intent classification because doing so would make needle-in-a-haystack retrieval decidable.

Intent classification: Intent classification is presented as an undecidable problem that can never be completely solved.The paper connects this limitation to ambiguity in prompts, contexts, and knowledge systems.
Reduction: The proof reduces the needle-in-a-haystack problem to intent classification.It assumes an intent-classification decider and constructs a decider for retrieval.
Reduction: Because needle-in-a-haystack retrieval is undecidable, the assumed intent-classification decider cannot exist.The contradiction establishes the paper’s claim about intent classification.
Implication: The resulting communication problem is that the model cannot know whether it correctly understood the prompt, context, or database knowledge.This conclusion is stated as the practical implication of the reduction.

3.4 Hallucinations are Inevitable During Generation

The paper argues that hallucinations remain inevitable during generation because LLMs cannot predict their own halting behavior or complete output. This uncertainty leaves generation impossible to check perfectly in advance.

Claims thus far: The paper summarizes three limits: incomplete training data, imperfect retrieval, and imperfect intent classification.It then argues that improving these stages still cannot prevent hallucinations during generation.
LLM halting: The Halting Problem for LLMs is undecidable, so transformer-based LLMs cannot know in advance how many tokens they will generate.The argument reduces the classical Turing-machine Halting Problem to halting for LLMs.
Generation uncertainty: LLM generation has uncertainty about both the next token and the total number of generated tokens.The paper assigns a non-zero probability to infinite generation and states that the sequence between BOS and EOS is unknowable a priori.
Generation uncertainty: A predictor for complete LLM outputs would fail on a self-referential construction that forces opposite halting behavior.This contradiction is used to rule out a general generation-prediction algorithm.
Implication: Because an LLM cannot predict its generation, it cannot check the accuracy or correctness of that output before producing it.The paper presents this as a consequence of generation unknowability.
Structural hallucinations: Self-contradictory and paradoxical statements would count as hallucinations when generated because they lack definitive truth values.The paper states that infinitely many such statements can be constructed and may occur with non-zero probability.

3.5 Fact Checking Mechanisms are Inherently Insufficient

The paper argues that fact-checking cannot completely eliminate hallucinations because no finite fact-checking and modification procedure can guarantee agreement with an ideal response for every input. It supports this claim by reducing such a procedure to the undecidable Acceptance Problem.

Fact-checking limits: The paper argues that fact-checking is incomplete in a finite number of steps.It frames this as the claim that hallucinations cannot be completely eliminated by checking every generated statement.
Proof setup: The proposed fact checker modifies an LLM output iteratively toward an ideal response using a character-edit distance.The construction models the fact checker as a Turing Machine and uses Levenshtein distance to measure agreement.
Contradiction: If finite modification always reached the ideal response, the procedure could decide the Acceptance Problem.The paper constructs a decider from the assumed universal correction procedure.
Conclusion: Because the Acceptance Problem is undecidable, no fact-checking algorithm can modify all hallucinations into non-hallucinatory responses.This is the paper’s formal conclusion about post-generation correction.

4 Illustration

The illustration uses a self-referential prompt to show that LLMs diverge from an expected infinite response and fail across training, retrieval, intent classification, generation, and fact-checking stages.

4.2 The Expected Response: The prompt asks the model to generate a five-word sentence while repeatedly inserting countdown phrases until no more sentences can be added.The expected response would begin at infinity, making the instruction structurally problematic for left-to-right generation.
4.2 The Expected Response: Each tested LLM deviated significantly from the expected response, with |A(w) −B(w)| significantly greater than 0.The paper presents responses from multiple popular LLMs as evidence of this deviation.
4.3–4.4 Failure Analysis: The authors attribute the failures to incomplete training coverage, inaccurate retrieval, and incorrect interpretation of the instruction.The model cannot be trained for tasks requiring prediction of its own behavior, retrieves five-word sentences imperfectly, and fails to classify the prompt’s intent.
4.4 Reasoning: Because an LLM cannot determine where generation should begin or halt, it has a non-zero probability of producing arbitrary content.The paper links this uncertainty to the apparently random material generated in response to the prompt.
4.5 Discussion: Fact-checking cannot completely eliminate hallucinations because the checking mechanism is itself an LLM subject to the same generation limitations.The paper therefore concludes that the single prompt verifies the proposed reasons structural hallucinations cannot be fully eliminated.

5 Concluding Remarks

The concluding section extends the paper’s undecidability arguments beyond ordinary Turing machines and presents structural hallucinations as an ineliminable property of LLMs. It also frames responsible use, mitigation research, and safety work as continuing priorities.

5.1 These Limitations Extend Beyond Turing Machines: The authors argue that undecidability results extend to oracle machines because the Halting Problem remains undecidable for machines equivalent to the oracle itself.An oracle may decide whether a Turing machine halts on an input, but not generally whether an equivalent machine will halt.
5.1 These Limitations Extend Beyond Turing Machines: Assuming an Emptiness decider would permit construction of a Halting decider, producing a contradiction; the Acceptance Problem is likewise shown undecidable on oracles.The reduction modifies an oracle to accept only a target string before applying the Emptiness decider.
5.2 The Unknown and the Unknowable — The Verdict: The paper’s established result is that proofs based on Halting undecidability and Gödel’s First Incompleteness Theorem establish hallucination inevitability at every generation stage.This conclusion is presented as a formal definition and proof-based account of structural hallucinations.
5.2 The Unknown and the Unknowable — The Verdict: The authors state that understanding structural hallucinations is vital for responsible use by researchers and laypeople.They emphasize awareness of risks and the use of common sense and domain knowledge when interpreting model outputs.
5.3 Future Work: The paper identifies future work on identifying and mitigating structural hallucinations, benchmarking them, specializing models, improving AI literacy, and developing safety measures.Additional proposed directions include access across the digital divide, protections for children and vulnerable entities, and regulation.