The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination
Xi Wang, Shijia Xu, Rongfeng Guo
cs.CL
Quick verdict
Clean rate-distortion lower bound separating coverage vs compression error in closed-book recall; sound, modestly novel, empirics only qualitative.
Summary
The paper analyzes closed-book factual hallucination with a coverage–compression model. In a null model where the ground-truth mapping over N queries and K answers is uniformly random, a learner observes M facts and compresses them into B bits; Theorem 3.1 proves E ≥ (M/N)δ*(B/M) + (1 − M/N)(1 − 1/K), where δ* is the inverse rate-distortion function of a uniform K-ary source under zero-one loss. The proof conditions on the training set, bounds memory information via the data-processing inequality, and applies the classical Hamming rate-distortion converse; a tightness proposition shows the bound is asymptotically achievable under free addressing, and an address-charged variant tightens it. Corollaries cover selective memory (saturation, not degradation), forced-compression overload, and deductive closure reducing effective load; the envelope is instantiated numerically (Tables 2–5). Controlled fact-injection probes LoRA-tune Qwen3-8B/32B, Qwen3-30B-A3B, and DeepSeek-R1-Distill-Qwen-32B on K=10 synthetic facts (M up to 28,672, three seeds). At fixed rank, observed-query error rises with load (Qwen3-8B rank 16: 0.032 to 0.862 across M=512 to 28,672), higher rank delays the transition, unseen entities stay near the 0.9 chance level, and structured facts delay overload (0.563 vs 0.866 at 28,672). Limitations: LoRA rank is only a qualitative capacity proxy never quantitatively fitted to B; the long-context analogue is unquantified; no code release is stated.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 2
● low 3
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Closed-book factual error decomposes into a coverage floor on unobserved queries plus a compression-distortion floor on observed facts: E ≥ (M/N)δ*(B/M) + (1 − M/N)(1 − 1/K) (Theorem 3.1).
- Under free addressing the bound is asymptotically tight, i.e., it is the rate-distortion envelope of the random-source model rather than a loose lower bound (Proposition 3.2).
- Observed-query error under fixed effective memory is a direct diagnostic of lossy recall and rises with fact load, while increasing LoRA rank shifts the transition later (Figures 2–3, Tables 11–12).
- Structure in the form of deductive closure reduces the number of independent labels that must be stored and delays overload (Proposition A.2, Table 14).
- Finite memory alone predicts saturation under selective allocation, not degradation; U-shaped full-space curves require extra mechanisms such as forced uniform allocation or interference (Section 3, A.3).
Strengths
Sound, self-contained theory built on a correct classical core
Theorem 3.1's proof (Appendix A.2) is a clean conditioning-on-S plus data-processing argument yielding I(X_S; X̂_S|S) ≤ B and the standard uniform K-ary Hamming converse R_K(D) = log2 K − h2(D) − D log2(K−1); Proposition 3.2 establishes asymptotic tightness under free addressing, so the bound is an envelope rather than a loose floor.
Diagnostically useful decomposition, validated at signature level
Separating observed-query error from unseen-entity error is the practical contribution: Table 11 shows Qwen3-8B rank 16 rising from 0.032 (M=512) to 0.862 (M=28,672) while Table 13's unseen-entity split stays at 0.889–0.902 against the analytic 0.9 chance level for K=10, matching the two-source structure.
Honest scoping and explicit conventions
Structure prediction quantitatively supported
Audit-ready experimental bookkeeping
Weaknesses
Theory–experiment link is purely qualitative
Limited novelty relative to classical results
Training-duration confound not ablated
Thin statistics for the comparisons being made
Internal inconsistency and unquantified long-context section
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper builds a coverage–compression model of closed-book factual recall and proves Theorem 3.1: for a uniformly random ground-truth mapping over N queries and K answers, a learner that observes M facts and stores at most B bits satisfies E ≥ (M/N)δ*(B/M) + (1 − M/N)(1 − 1/K), where δ* inverts the standard uniform K-ary rate-distortion function R_K(D) = log2 K − h2(D) − D log2(K−1) under zero-one loss. The framing example — 160 bits store only about 48 independent K=10 facts — anchors the capacity intuition. The claim set is deliberately narrow: an information-theoretic account of one separable failure mode (lossy recall of observed facts), not a theory of hallucination at large. Ancillary results: asymptotic tightness under free addressing (Prop. 3.2), an address-charged variant subtracting a log2-binomial address cost, corollaries on selective memory (saturation, not degradation), forced-compression overload, deductive closure (Prop. A.2), and abstention (Eq. 13).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the main result of The Cost of Compression (arXiv 2609.12111)?
It proves a lower bound on closed-book factual error: with N possible questions, K possible answers, M observed facts, and B bits of memory, expected error is at least (M/N)δ*(B/M) + (1 − M/N)(1 − 1/K), where δ* is the rate-distortion error curve of a uniform K-ary source. The first term is recall error on seen facts caused by lossy compression; the second is unavoidable guessing error on unseen facts.
Does the paper show that large language models actually obey this rate-distortion bound?
Not quantitatively. The model probes use LoRA rank as a stand-in for memory and test only qualitative signatures: observed-fact error rises with fact load at fixed rank, higher rank delays the failure point, unseen entities stay near chance, and structured facts delay overload. No effective bit budget B is fitted to any model.
Which models were used in the fact-injection experiments?
Qwen3-8B (LoRA rank sweep 4/16/64), Qwen3-32B, Qwen3-30B-A3B (MoE), and DeepSeek-R1-Distill-Qwen-32B, all LoRA-tuned on up to 28,672 synthetic entity-label facts with K=10 answer values, evaluated over three seeds. Kimi-K2-Instruct and GLM-5 appear only in a qualitative long-context analogue.
Is code or data available for this paper?
The extracted text does not state any code or data release. The appendix does document seeds, hyperparameters, hardware (8×A100-80GB), and answer normalization in enough detail to attempt a reimplementation, and the theory tables are reproducible by simple numerical inversion of the rate-distortion function.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figure image content is absent from the text extraction; assessments of Figures 1–6 rely on their captions alone.
- Figure 1's embedded OCR text is garbled (several symbols render as placeholder glyphs), but the caption and body text carry the same content, so no conclusion in this review rests on the garbled portion.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.