Hallucinations Are Not Just Missing Facts: Compression Can Distort Recall

Introduction

When a language model gives a wrong answer to a factual question, a common explanation is that the relevant fact was never learned. A new arXiv paper argues that this explanation is incomplete. A model may have encountered a fact and still fail to reproduce it accurately because its effective internal memory is finite. In that case, the problem is not only missing coverage; it is lossy recall.

Key points

• Two sources of error: The paper studies an unstructured question-answering setting with N possible queries and K possible answers. A learner observes M training facts, compresses them into at most B bits, and answers test queries without retrieval.
• Unseen facts create a guessing floor: If a test query was not among the observed facts, the learner has no direct information about its answer. Under the paper’s uniform setup, the remaining error is the error of guessing among K possible answers.
• Observed facts can also be distorted: Facts that were seen must compete for a limited representation budget. If the average number of bits available per fact is too small, the stored representation may not preserve the exact answer. The paper describes this effect with the inverse rate-distortion function for a uniform K-ary source under zero-one loss.
• A combined lower bound: The proposed bound adds compression distortion on observed facts to random-guessing error on unobserved facts. This separates two mechanisms that are often grouped together under the single label of hallucination.
• Theory-guided probes: The authors report theory-implied simulations and controlled fact-injection probes in modern language models, varying fact load and effective trainable memory. The supplied abstract does not provide detailed model-by-model results, so the main contribution here is the analytical framing rather than a specific ranking of systems.

Why it matters

The distinction between coverage and compression changes how factual reliability might be improved. More training data or retrieval can help when a fact is absent. They may not solve the problem when the fact is present but encoded imprecisely. Under a fixed memory budget, adding more facts can force the system to distribute fewer bits across each item, potentially increasing distortion in what it already knows.

The framework also raises practical design questions. Should a model selectively preserve high-value facts instead of treating all facts equally? Does a longer context truly expand usable memory, or does it merely postpone the compression problem until inference? Can retrieval turn an internal-memory limitation into an access problem? And when a model is uncertain, is abstaining safer than producing an approximate answer that sounds factual?

The result should be interpreted with care. The formal task is deliberately simple and assumes an unstructured, uniformly random mapping. Real language models exploit semantic structure, parameter sharing, context, and external tools. Those properties may substantially alter how the bound applies. The paper therefore does not claim to explain every hallucination. Its more focused contribution is to identify a separable failure mode: a model can hallucinate not only because it never stored a fact, but also because finite memory stored it inaccurately.

Source: arXiv