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

AI summary

Overview

Research area: Machine learning theory — information-theoretic explanations of large language model hallucination, connecting LLM factuality to the rate-distortion theory of approximate membership data structures (Bloom-type filters).

Technical level: Advanced. The paper assumes comfort with KL divergence, rate-distortion theory, convex optimization over probability measures, variational calculus, and KKT conditions.

One-sentence scope: The paper proves that hallucination on unstructured "random facts" is not a failure of training or data but the information-theoretically optimal behavior of any finite-memory system, and that this same theorem recovers and sharpens classical space lower bounds for Bloom-type filters.

What This Paper Is About

Large language models frequently produce confident but false statements about "random facts" — unstructured details like phone numbers or biographical information that cannot be inferred unless seen during training. The authors ask why, even under idealized conditions (optimal training, perfect data, a "closed world" with finitely many known facts, and unlimited permission to abstain), models should still hallucinate rather than simply forgetting or saying "I don't know." They formalize memorizing such facts as a membership testing problem — the same abstraction that underlies Bloom filters — and derive an exact memory-versus-error trade-off for it.

Key Contributions

1. A rate-distortion theorem for membership testing. In the sparse limit where |K|/|U| → 0, the minimum memory budget per key is exactly n · KL(μ_K ‖ μ_N) + o(n) bits, where μ_K and μ_N are the score distributions on keys and non-keys that satisfy the error constraints while minimizing KL divergence. The theorem has both a lower-bound direction and a matching achievability direction.

2. Hallucination as the optimal mode of error. Under log-loss / cross-entropy evaluation of confidence scores, the unique loss-minimizing strategy is to assign high confidence to all facts while simultaneously assigning that same high confidence to a nonzero fraction of non-facts. Neither systematic forgetting nor uniform uncertainty is optimal — hallucination is.

3. A thresholding result via two-sided filters. Any LLM decision mechanism based on score thresholding — whether scores come from generative probabilities or from a probability-estimation output — is subject to the memory-error trade-off of two-sided filters (which permit both false positives and false negatives). Unlike the probability-estimation result, this applies to all thresholding classifiers and does not assume optimality.

4. Recovery and sharpening of classical filter bounds. The same theorem recovers existing space lower bounds (Carter et al., 1978; Pagh and Rodler, 2001; Hurley and Waldvogel, 2007; Li et al., 2023a) as special cases, and pins down an additive constant per key that Pagh and Rodler (2001) left as an unspecified Θ(1) gap for two-sided filters. A hash-based two-sided filter is also shown to achieve the lower bound up to o(n) bits of overhead.

Main Findings

• The exact memory-error frontier. For error metrics d^K and d^N and error rates ε_K, ε_N, the asymptotic per-key memory budget satisfies lim inf B(M_j)/n_j ≥ min KL(μ_K ‖ μ_N) over μ_K in C_K(ε_K) and μ_N in C_N(ε_N), and this bound is achievable by some sequence of testers.

• Optimal outputs converge to specific distributions. If the KL minimizer is unique, any asymptotically optimal family of testers must have μ_K(M_j) → μ_K* and μ_N(M_j) → μ_N* in Wasserstein-1 distance.

• Log-loss optimal solution (Theorem 4.1). In the regime ε_K > 0, ε_N > 0, and e^{−ε_K} + e^{−ε_N} > 1, the unique minimizers are μ_K* = δ_{x*} and μ_N* = (1 − q*)δ_0 + qδ_{x}, where x* = e^{−ε_K} and q* = ε_N / (−ln(1 − x*)). The resulting memory bound simplifies to KL(μ_K* ‖ μ_N*) = log(1/q*).

• The hallucination rate is set by memory alone. The hallucination probability q* on non-facts is determined solely by the memory capacity dedicated to storing random facts, independent of how the two error types are traded off against each other.

• Thresholding cannot remove hallucinations. Because non-facts must place an atom at the same score x* used for facts, any threshold that accepts a fact also accepts the hallucinating non-facts, and any threshold that rejects any hallucination also rejects every fact.

• Binary decision solution (Theorem 4.3). In the regime ε_K, ε_N ≥ 0 and ε_K + ε_N < 1, the minimizers are μ_K* = Bern(1 − ε_K) and μ_N* = Bern(ε_N). A first-order refinement for small p = n/u gives a correction term of p/(2 ln 2) · χ²(Bern(1 − ε_K) ‖ Bern(ε_N)).

• There is no hallucination-free regime. Driving false positives to zero means ε_N → 0, but then KL(Bern(1 − ε_K) ‖ δ_0) = ∞ for every ε_K < 1. Zero false-positive rate is compatible only with rejecting everything (ε_K = 1) or with unbounded memory. The authors state this also proves no "reverse Bloom filter" can tolerate false negatives but not false positives.

• Post-processing only moves along the frontier. Reducing ε_N by being conservative necessarily increases either the memory budget or ε_K (more forgetting or over-refusal), formalizing the precision-recall / over-refusal trade-off observed empirically.

• Empirical validation. The predicted tendency is verified in two complementary settings: small transformers trained from scratch on synthetic random strings (Section 4.3), and LoRA-tuned pretrained LLMs on both synthetic IDs and real-world ISBNs (Sections 4.3 and E.1). Figure 1 shows output distributions on facts versus non-facts (log-scale y-axis) across different values of λ_F for a model with 15145 parameters (1 per fact), with blue stems marking the predicted memory-optimal atoms for non-facts under the same empirical loss values.

• Why effective memory is small. Appendix A offers two explanations: (i) modern networks are encouraged to minimize pure memorization through regularization and MDL/PAC-Bayes viewpoints, and (ii) structured knowledge (language, reasoning) and random facts compete for a finite memory budget, with the former taking precedence during learning because of its greater impact on the training objective.

• Shape of the frontier matters. The marginal memory cost of eliminating the final few errors is prohibitively high, so training objectives that optimize aggregate loss rather than perfect precision naturally tolerate those residual errors.

Methodology in Plain English

The authors abstract away from the details of any particular model and treat factuality judgment as a membership testing problem. A universe U of plausible statements is fixed; the set of known facts is a key set K ⊆ U of size n drawn uniformly at random. A "membership tester" consists of two algorithms: Init, which takes K and produces a memory state W (model parameters or data-structure contents), and Query, which takes an item i and the memory state and returns a confidence score x̂_i in [0,1]. The memory budget is defined as B(M) = I(W; K), the mutual information between the memory state and the key set, which also lower-bounds the bits of storage since I(W; K) ≤ H(W).

Two families of error metrics are considered. For filters and binary decisions, the false-negative metric is d^K(x̂) = 1 − x̂ and the false-positive metric is d^N(x̂) = x̂. For LLM confidence estimation, log-loss is used: d^K(x̂) = −ln x̂ for facts and d^N(x̂) = −ln(1 − x̂) for non-facts.

The analysis assumes permutation-invariance (the query distribution depends only on whether the queried item is a key or a non-key), which the authors note is without loss of generality for the lower bounds because any tester can be symmetrized with a uniformly random permutation.

The key analytical object is F_p(μ_K, μ_N) = I(X; X̂)/p, where X ~ Bern(p) with p = n/u, and X̂ is drawn from μ_K conditioned on X = 1 and from μ_N conditioned on X = 0. This serves as a finite-p proxy for the per-key memory cost. A non-asymptotic lower bound shows B(M)/n ≥ F_p(μ_K, μ_N) − log(8n)/(2n). The function F_p is shown to be jointly lower semi-continuous, continuous and differentiable in p, and to converge to KL(μ_K ‖ μ_N) as p → 0. The rate-distortion function R_p(ε_K, ε_N) is then defined as the minimum of F_p over the feasible regions C_K(ε_K) and C_N(ε_N), giving the bound B(M)/n ≥ R_p(ε_K, ε_N) − log(8n)/(2n), with a matching achievability lemma showing existence of a tester within δ of R_p.

Passing p → 0 via compactness and lower semi-continuity yields the main theorem. For the specific log-loss and binary-decision cases, the authors solve the resulting optimization over probability measures using variational calculus and verify the KKT conditions. Empirically, they train small transformers from scratch on synthetic random strings and LoRA-tune pretrained LLMs on synthetic IDs and real-world ISBNs to check that observed score distributions match the predicted structure.

Why This Matters

The paper's distinctive claim is that hallucination is not an artifact of bad data, weak training, or insufficient scale, but rather the mathematically optimal way to spend a limited memory budget on unstructured facts. This reframes hallucination mitigation from "fix the model" to "change the memory budget or the error trade-off," and it unifies two previously separate literatures — the space complexity of probabilistic filters and the statistical theory of LLM hallucination — under a single rate-distortion result.

Real-world applications:

• Retrieval-augmented generation (RAG). The paper argues its framework justifies why RAG is effective: when non-parametric memory is present, the memory budget is no longer the limiting factor.
• Factuality calibration and "know what you know" evaluation. Because the theory is stated for the log-loss used in confidence-estimation evaluations, it gives a target distribution and a lower bound for how accurate such confidence estimates can be.
• Abstention and refusal policies. The frontier result clarifies that tuning a threshold for "I don't know" trades false positives for false negatives along a fixed curve rather than escaping it, which is directly relevant to designing over-refusal-avoidance policies.
• Approximate membership data structures. The refined space lower bounds, including the closing of Pagh and Rodler's per-key constant gap and a hash-based construction matching the bound to o(n) bits, bear on the design of static filters.
• Targeted fine-tuning on long-tail facts. The analysis supports fine-tuning on unstructured random facts as a way to force the model to allocate more of its memory budget to them.

Industry relevance: the results are directly relevant to deployment decisions about retrieval architectures, threshold-based safety and abstention layers, and investment in fine-tuning versus retrieval for long-tail factual coverage. The claim that "there is no reverse Bloom filter" is a strong statement about what production factuality systems can promise.

Future Directions

• Relaxing permutation-invariance. The authors state that practical LLMs are not permutation-invariant and treat the assumption purely as an analytical tool whose lower bounds still apply. Quantifying how much non-permutation-invariant structure changes the achievable frontier is left open.
• Dynamic key sets. The paper notes that static filters only store a fixed set K and that filters supporting insertion or deletion incur an additional space cost (citing Lovett and Porat, 2010; Kuszmaul and Walzer, 2024; Kuszmaul et al., 2025). Extending the theorem to the dynamic setting is a natural next step.
• Measuring and enlarging the effective memory budget. Appendix A offers qualitative reasons why the effective budget for a family of random facts is far smaller than the parameter count. How architectural choices, regularization, and training objectives shift that effective budget — and whether it can be deliberately increased — is not resolved.
• Empirical scaling of the frontier. The validation reported covers small transformers trained from scratch on synthetic random strings, and LoRA-tuned pretrained LLMs on synthetic IDs and real-world ISBNs. Whether the predicted frontier holds at larger scale and on broader fact distributions is not reported.
• Explicit future work. The available content does not contain a dedicated future-work section, so the directions above are the open questions raised by the results rather than a list the authors enumerate.

Target Audience

This paper is aimed at machine learning theorists and information theorists working on hallucination, memorization, and generalization in LLMs; researchers in data structures and algorithms interested in space lower bounds for filters; and practitioners with a strong theoretical background who are designing factuality, abstention, or retrieval systems and want a principled account of what thresholds and memory budgets can and cannot buy. Readers without a background in rate-distortion theory, convex optimization over measures, or probabilistic data structures will find the proofs in the appendices difficult, though the theorem statements and their interpretations are stated in comparatively accessible terms.

Authors’ abstract

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.