# Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing

arXiv: https://arxiv.org/abs/2602.00906 · HTML: https://mlsanity.com/paper/2602.00906/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 84 references that are in the map.
- First posted on arXiv 31 Jan 2026.

## Builds on (most cited first, 30 of 52)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [Contrastive Decoding: Open-ended Text Generation as Optimization](https://mlsanity.com/paper/2210.15097/) (2022)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Documenting Large Webtext Corpora: A Case Study on the Colossal Clean Crawled Corpus](https://mlsanity.com/paper/2104.08758/) (2021)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Grammar Variational Autoencoder](https://mlsanity.com/paper/1703.01925/) (2017)
- [Physics of Language Models: Part 3.1, Knowledge Storage and Extraction](https://mlsanity.com/paper/2309.14316/) (2023)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Why Language Models Hallucinate](https://mlsanity.com/paper/2509.04664/) (2025)
- [Emergence of Invariance and Disentanglement in Deep Representations](https://mlsanity.com/paper/1706.01350/) (2017)
- [Factuality Enhanced Language Models for Open-Ended Text Generation](https://mlsanity.com/paper/2206.04624/) (2022)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Physics of Language Models: Part 3.3, Knowledge Capacity Scaling Laws](https://mlsanity.com/paper/2404.05405/) (2024)
- [Know Your Limits: A Survey of Abstention in Large Language Models](https://mlsanity.com/paper/2407.18418/) (2024)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [Calibrated Language Models Must Hallucinate](https://mlsanity.com/paper/2311.14648/) (2023)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Recurrent Neural Network Grammars](https://mlsanity.com/paper/1602.07776/) (2016)
- [The Art of Saying No: Contextual Noncompliance in Language Models](https://mlsanity.com/paper/2407.12043/) (2024)

## Built on by (most cited first, 2 of 2)

- [Abstain-R1: Calibrated Abstention and Post-Refusal Clarification via Verifiable RL](https://mlsanity.com/paper/2604.17073/) (2026)
- [Context Compaction Theory](https://mlsanity.com/paper/2608.01326/) (2026)

## Abstract (arXiv)

Large language models often hallucinate with high confidence on "random facts" that lack inferable patterns. We formalize the memorization of such facts as a membership testing problem, unifying the discrete error metrics of Bloom filters with the continuous log-loss of LLMs. By analyzing this problem in the regime where facts are sparse in the universe of plausible claims, we establish a rate-distortion theorem: the optimal memory efficiency is characterized by the minimum KL divergence between score distributions on facts and non-facts. This theoretical framework provides a distinctive explanation for hallucination under an idealized setting: even with optimal training, perfect data, and a simplified ``closed world'' setting, the information-theoretically optimal strategy under limited capacity is not to abstain or forget, but to assign high confidence to some non-facts, resulting in hallucination. We validate this theory empirically on both synthetic and real-world data, showing that hallucinations persist as a natural consequence of lossy compression. The same theorem recovers and sharpens classical space lower bounds for Bloom-type filters, pinning down an additive constant left open for two-sided filters.