Hallucination is Inevitable: An Innate Limitation of Large Language Models

The paper asks a question that benchmark studies cannot answer: can hallucination in large language models be eliminated entirely? Measuring error rates on test sets can show that a technique helps, but no finite test can show that errors are gone for every possible input.

To make the question precise, the authors define a formal world. Inputs are finite strings over a fixed alphabet. The correct answer to each input is given by a ground truth function f that a computer can calculate. A language model is any computable function from strings to strings that is updated as it sees training pairs (s, f(s)). A model hallucinates with respect to f if, at every stage of training, there is some input where its output differs from f.

With those definitions, the authors adapt a classic argument from computability theory. List every model state, list every input, and build f so that its answer on input i differs from what state i outputs on input i. Every state is then wrong on at least one input, and a stronger construction makes each one wrong on infinitely many inputs. Because a single model is a list of one, the result covers any computable model: for each one there exists a computable task it cannot get fully right. The authors argue that since the formal world is part of the real world, hallucination cannot be eliminated in real systems either.

The paper then lists problem classes that are hard for models with polynomial running time (SAT, subset sum, Presburger arithmetic), discusses which mitigations could escape the theorems (retrieval and external tools can, because they add information beyond training pairs), and reports two small experiments in which current models fail to list all strings of a given length and fail to reason about an unfamiliar ordering relation.

Design as if errors are permanent. The practical message is the one customers most need to hear before a launch. No model release, prompt or fine-tune will make an open-ended assistant error-free, so the system around the model has to catch, contain and correct mistakes. That means verification steps, citations a user can check, human review where the cost of an error is high, and a clear path for reporting problems.

Know the limits of the proof. The theorem shows that for every model there exists some computable task it fails. It does not say your task is that task, and it does not give an error rate. The ground truth in the proof is built from the model it defeats. When someone cites this paper to argue that a contract-extraction system "will always hallucinate at some rate", the honest reply is that the paper supports the first half (some error will exist somewhere) and says nothing about the rate or where errors fall.

External information changes the picture. The authors note that retrieval, tools and knowledge bases give the model information beyond its training pairs, so their theorems do not apply in the same way. This is the strongest practical argument in the paper for grounding: the model is not asked to compute or remember what a database lookup, a calculator or a search can supply.

Refusal is part of the design. The paper observes that a model that never answers never hallucinates. Its own Definition 4 counts a refusal as a wrong output, which our experiment shows. In production you want the second view: abstention reported as its own outcome, with coverage and accuracy measured separately.

Watch the experiments, not just the theorems. The listing failures happen on answers of about a thousand characters, far from any context limit. Simple, mechanical tasks can fail for reasons unrelated to computational hardness, which is a reason to give such tasks to code.