The Cost of Compression: Rate-Distortion Limits Behind Factual Hallucination
Rate-distortion theory proves some LLM hallucinations are an inevitable cost of lossy memory compression.
This paper offers a new lens on factual hallucination in language models: errors don't only stem from unseen knowledge, but also from compression distortion of facts that were seen but imperfectly stored. The authors build a coverage–compression framework that splits the error lower bound into two independent terms — compression distortion and coverage gap — using the inverse rate-distortion function for a uniform K-ary source to precisely characterize the former. When the bit budget $B$ is fixed and the number of facts $M$ grows, distortion inevitably rises, explaining at an information-theoretic level why more data doesn't always linearly improve accuracy. Controlled fact-injection experiments on modern LLMs confirm this signal, and the framework provides theoretical grounding for practices like RAG, abstention, and selective memory.
Hallucination Isn't Just "Never Learned" — It Can Also Be "Imperfectly Remembered"
Factual hallucination in large language models has long been framed as a coverage problem: the model answers incorrectly because the relevant fact was never in its internal memory to begin with. This explanation is intuitive and common, but it overlooks a subtler source of error.
A new paper on arXiv, The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination, argues that even when a fact has been "seen" by the model, limited memory capacity may force it to be stored only approximately. In other words, the model didn't fail to learn the fact — it learned it, then had it distorted through compression. This is a separable, quantifiable failure mode, and the authors derive an information-theoretic lower bound for it.
The Coverage–Compression Model: Decomposing Hallucination into Two Parts
The paper constructs a minimal yet analytically tractable framework called the coverage–compression model. It abstracts the closed-book question-answering task as follows:
- There are $N$ possible queries in total
- Each query has $K$ possible answers
- The learner observes $M$ training facts
- These facts are compressed into at most $B$ bits
- At test time, the model answers a uniformly sampled query without any retrieval
Under the assumption that the true mapping is uniformly random, the authors prove the following lower bound on error rate:
$$\mathcal{E} \geq \frac{M}{N}\delta^\star!\left(\frac{B}{M}\right) + \left(1-\frac{M}{N}\right)\left(1-\frac{1}{K}\right)$$
The elegance of this inequality lies in how cleanly it decomposes error into two terms.
Term 1: Compression Distortion on Observed Facts
$\frac{M}{N}\delta^\star(B/M)$ captures the error from facts the model has seen but cannot store accurately due to memory constraints. Here, $\delta^\star(r)$ is the inverse rate-distortion function for a uniform $K$-ary source under zero-one loss. It precisely quantifies how much distortion is unavoidable when you have only $B/M$ bits to store each fact. This is the core contribution of applying rate-distortion theory to hallucination analysis — even with perfect training data, insufficient bits inevitably cause "memory corruption."
Term 2: Coverage Gap on Unobserved Facts
$(1-\frac{M}{N})(1-\frac{1}{K})$ corresponds to the traditional coverage problem: facts that never appeared during training. The model can only guess at these, with a $1/K$ chance of being correct, contributing an error rate of $(1-1/K)$, weighted by the fraction of uncovered queries $(1-M/N)$.
This decomposition draws a clear line — for the first time — between "never learned" and "learned but imperfectly recalled."
What Can Be Inferred from a Lower Bound
The authors emphasize that this bound provides a compact lens through which to reason about a range of real-world engineering techniques and phenomena:
- Selective memory: A model can deliberately avoid storing low-frequency facts, reserving limited bits for high-value information
- Forced compression: When $B$ is fixed and $M$ grows, each fact receives fewer bits and distortion increases — explaining why "feeding more data" doesn't linearly improve accuracy
- Structure: Real-world facts are not uniformly random; exploiting structure can reduce effective storage cost
- Retrieval: External retrieval effectively bypasses the internal compression bottleneck, lifting the constraint imposed by $B$
- Abstention: Choosing to say "I don't know" avoids confidently wrong answers caused by compression distortion
- Long-context organization: How information is organized in the context window to reduce effective memory load
From another angle, this lower bound gives model designers a diagnostic tool: when accuracy plateaus, is the bottleneck insufficient coverage (need more data or retrieval), or compression distortion (need more capacity or better structure)?
From Theory to Experiment: Fact-Injection Probes
The paper doesn't stop at pure theory. The authors validate the theoretical predictions through two types of experiments.
The first is theory-implied simulations, which directly test whether the shape of the lower bound matches predictions under controlled assumptions.
The second is more practically grounded — controlled fact-injection probes on modern language models. The researchers systematically vary two quantities: fact load (i.e., $M$) and effective trainable memory (i.e., $B$). By observing how error rates change with these variables, they confirm that compression distortion is indeed a distinct, observable failure mode — independent of coverage.
This Is Not a Complete Theory of Hallucination
The authors are careful to scope their claims: this is not a complete theory of hallucination. Real-world hallucination is complex, involving training dynamics, prompting, reasoning chains, alignment objectives, and many other factors. This paper isolates and addresses just one clearly delineated mechanism — lossy recall of observed facts under limited memory.
But it is precisely this isolation that gives the work its value. It reduces a vague, sprawling problem into a sub-problem with an information-theoretic lower bound that is measurable and amenable to formal reasoning. For researchers and engineers who care about model reliability, understanding that "compression itself carries an irreducible error cost" may reshape how they weigh tradeoffs among scaling, retrieval augmentation, and abstention strategies.
Implications for Practice
If compression distortion is indeed an independent source of hallucination, then simply stacking more parameters or more data may not be the optimal solution. In this framework, retrieval-augmented generation (RAG) has a cleaner explanation for its effectiveness: it externalizes fact storage, fundamentally sidestepping the rate-distortion limit of the internal bit budget. For scenarios that must rely on parametric memory, exploiting structure among facts, prioritizing bits for high-value facts, and proactively abstaining under uncertainty all become theoretically grounded strategies for reducing error.
The deeper significance of this paper may be this: it invites us to stop treating hallucination as a vague "model defect" and instead view it as a cost that can be precisely accounted for using information theory.
Related articles
CCPS Sampling: Preserving Reasoning Diversity to Boost LLM Performance Without Fine-Tuning
A new arXiv paper proposes CCPS, which boosts LLM reasoning accuracy without any training by preserving reasoning diversity via Chopthin resampling and semantic majority selection — achieving up to 10.6pp absolute gains.
MIT Spinout Transforms Plastic Waste into High-Resilience Building Materials
MIT spinout Atlas Building Composites converts plastic waste into resilient structural components for buildings and infrastructure, pioneering a high-value recycling pathway.
Repair Before Reinforce: Context-Augmented Knowledge Graph Reasoning Tackles Multi-Hop QA
New arXiv paper proposes a context-augmented KG reasoning framework using a "Repair Before Reinforce" strategy to improve LLM multi-hop QA. Validated on Gastroparesis and Diabetes KGs with Qwen3-14B, achieving 100% single-hop accuracy after repair.