Ziwei Xu, Sanjay Jain, Mohan Kankanhalli
8 min
This paper addresses the fundamental, long-standing question of whether hallucination in Large Language Models (LLMs) is a fixable bug or an unavoidable feature. While prior research has primarily focused on empirical methods—such as retrieval-augmented generation, prompting strategies, and better data curation—these approaches have failed to eliminate hallucinations. By shifting the discussion from empirical performance to theoretical limits, the authors provide a formal framework to define hallucination as the inconsistency between an LLM and a ground truth computable function.
Using the diagonalization argument from learning theory, the authors prove that any computable LLM—regardless of its architecture, training procedure, or volume of training data—will inevitably fail to replicate all computable functions perfectly. If an LLM attempts to act as a general problem solver, there will always exist scenarios where it fails to produce the ground truth output. Since this formal world is a subset of the actual world, the authors conclude that hallucination is an inherent, unresolvable limitation of LLMs in real-world deployment.
Beyond the theoretical proof, the authors identify specific categories of problems that are particularly hallucination-prone, including combinatorial tasks, NP-complete problems (such as Boolean satisfiability), and complex logical reasoning. The study suggests that while techniques like chain-of-thought prompting or knowledge-enhanced retrieval can mitigate errors in specific, bounded contexts, they cannot eliminate the root cause of hallucination. Consequently, the authors caution against using LLMs for safety-critical decision-making without rigorous human oversight, guardrails, or external symbolic verification, as these models lack an inherent, universal mechanism to verify their own truthfulness.
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.
Sam: Success is demanding. For any computable ground-truth rule, some finite training stage must produce a model that matches it on every input. Their formal definition of persistent hallucination means that every training stage still has some input where the model disagrees.
Alex: That is stronger than the usual benchmark goal. What is the idea that makes such a universal guarantee impossible?
Sam: The key is diagonalization: constructing a rule that defeats every candidate in a list. Imagine listing the trained model states, then listing possible inputs. For the first state, define the correct answer on its assigned input to differ from its output. Repeat for each state.
Alex: Each candidate then has a question it gets wrong by construction. But the target rule must itself remain computable, or this would miss the paper’s own setup.
Sam: It remains computable because every listed state finishes its computation, and changing its answer is computable too. For an effectively listable collection of learners, the authors construct a rule defeating every listed state. A stronger construction makes each state wrong on infinitely many inputs.
Alex: Does that cover every computable model, or only collections whose members can be listed by a program?
Sam: Any individual computable learner forms a list containing just itself. Applying the construction to its training states gives the broader result. For every such learner, there is some computable target rule it cannot master perfectly. The target can differ between learners.
Alex: So the result is not that every model fails every task. It is that no learner in this setup covers all tasks without error. Can the authors make that less abstract?
Sam: They construct an ordering, like a ranking of items. After training on comparisons among earlier items, the learner predicts how a fresh pair is ordered. The construction places that pair in the opposite order, while preserving a valid ordering. Additional examples never produce complete mastery of that constructed task.
Alex: That establishes a worst case. It does not tell me how often my research assistant will invent an answer. What do the experiments contribute?
Sam: Illustration, rather than proof of inevitability. The authors test five model versions from the Llama and GPT families. One task asks them to list every string of a specified length using a small alphabet. Duplicates are permitted, but missing or invalid strings mean failure.
Alex: That sounds easy to describe but increasingly expensive to complete. How generous was the success criterion?
Sam: Each task gets three runs with different random seeds, and success in any run counts. All tested models eventually fail as the requested length grows. For strings seven characters long using a two-character alphabet, every tested model fails.
Alex: That request needs 128 distinct strings. A finite experiment cannot establish the mathematical limit, but it shows errors on a clearly specified task rather than disputed factual knowledge.
Sam: And the authors distinguish computational difficulty from intellectual difficulty. Listing every binary string requires an output that grows exponentially with length. Under their polynomial-time model assumption—runtime bounded by a fixed power of input length—complete listing eventually exceeds the available computation.
Alex: But that argument does not identify where a particular model should fail. These short-task failures could have other causes too.
Sam: The paper acknowledges that its theory does not explain errors within a model’s computational capabilities. Its experiments also use existing models without further fine-tuning, and were conducted between late 2023 and spring 2024. I would read them as demonstrations, not measurements of today’s deployment risk.
Alex: What happens to the familiar fixes? If we add more training data or ask the model to check itself, does the theorem still apply?
Sam: Within the defined setup, yes. Larger models, ensembles, and more data can expand what is learned without eliminating the universal limitation. Reasoning and verification prompts may help on particular tasks. They cannot guarantee that the model always corrects itself.
Alex: The document also discusses search, calculators, and knowledge databases. Are those simply more candidates defeated by the same argument?
Sam: The authors explicitly say their central theorem is inapplicable to the knowledge-enhanced setup they describe. External sources provide information beyond training examples and can change the workflow. They present tools and programmed constraints as potentially effective mitigators, while leaving their real-world scalability open.
Alex: Then “hallucination is inevitable” should not become “mitigation is pointless.” The relevant question is what can be made reliable for a specified job.
Sam: That is consistent with the paper. It allows error-free learning for some restricted classes of tasks. It also assumes deterministic truth and supplies no practical error-rate estimate. The authors urge external safeguards and human control for safety-critical decisions, rather than treating a general model as an infallible authority.
Alex: Who should read the full document, and where should they start if they want to evaluate that boundary themselves?
Sam: Learning researchers should start with the definitions, then the proofs in “Hallucination is Inevitable for LLMs.” Deployment researchers should read “Existing and Possible Hallucination Mitigators” alongside the limitations. For everyone else: improving a model on a task is not a guarantee that it can answer everything correctly.
Alex: Keep that distinction close when deciding what to trust.