In plain words: Learning theory shows no language model can master every rule that could be computed, so it will sometimes contradict the true answer. Because real-world models face the same limit plus time limits, hallucination can be reduced but never fully removed.
Abstract · Hallucination is Inevitable: An Innate Limitation of Large Language Models
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.
Ziwei Xu, Sanjay Jain, Mohan Kankanhalli
arXiv:2401.11817 · cs.CL, cs.AI, cs.LG · submitted Jan 22, 2024 · updated Feb 13, 2025
abstract · pdf · html
I think this is a clever point and an interesting philosophical question (about math, computer science, and language), but I think people are mostly trying to apply this using our commonsense notions of "LLM hallucination" rather than the formal notion they use in this paper, and I don't see an obvious connection, since commonsense hallucinations (eg inventing chapters of a novel when asked to produce summaries, inventing specific details when asked) don't seem to be NP-complete problems but rather are hallucinatory for some other interesting reason. (I apologize if I have not captured the paper correctly and would welcome correction on that, I read it quickly)
The statement that the formal world (the world of math and logic and formal grammars) is a subset of the "real" world (or perhaps, the world of natural language) is really interesting to me as well. Most humans can't solve formal logic problems and parse formal grammars but don't suffer from a (strong) hallucination effect, and can work in natural language in great proficiency. Is hallucination inevitable in humans since we also can't solve certain NP-complete problems? We have finite lifespans, after all, so even with the capabilities we might never complete a certain problem.