The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination

• URL: http://arxiv.org/abs/2609.12111v1
• Date: Thu, 10 Sep 2026 18:37:44 GMT
• Title: The Cost of Compression: A Rate-Distortion Limit on Factual Hallucination
• Abstract summary: Factual hallucination in closed-book question answering is often treated as a coverage problem.<n>We study this effect through a simple coverage--compression model of factual recall.<n>We study the predicted signatures with theory-implied simulations and controlled fact-injection probes in modern language models.
• Score: 5.158280959759542
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Factual hallucination in closed-book question answering is often treated as a coverage problem: a model fails because the relevant fact is absent from its internal memory. This view misses a second source of error. Even when a fact has been observed, finite memory may force it to be stored only approximately. We study this effect through a simple coverage--compression model of factual recall. We consider an unstructured question-answering task with $N$ possible queries and $K$ possible answers. A learner observes $M$ training facts, compresses them into at most $B$ bits, and answers uniformly drawn test queries without retrieval. For a uniformly random ground-truth mapping, we prove $\mathcal{E} \geq \frac{M}{N}δ^\star\!\left(\frac{B}{M}\right) + \left(1-\frac{M}{N}\right)\left(1-\frac{1}{K}\right)$, where $δ^\star(r)$ is the inverse rate-distortion function of a uniform $K$-ary source under zero-one loss. The two terms separate compression distortion on observed facts from missing coverage on unobserved facts. The bound gives a compact way to reason about selective memory, forced compression, structure, retrieval, abstention, and long-context organization. We study the predicted signatures with theory-implied simulations and controlled fact-injection probes in modern language models that vary fact load and effective trainable memory. The result is not a complete theory of hallucination, but an information-theoretic account of a separable failure mode: lossy recall of observed facts under finite memory.

Related papers

• REIN: Bridging the Gap between Reasoning and Reliability via Reflection and Abstention Alignment [35.47736821237044]
  Large reasoning models (LRMs) are prone to hallucination, which undermines their reliability and poses challenges for safe deployment.<n>We propose REIN, an alignment framework that trains LRMs to produce a structured reasoning sequence.<n>REIN introduces a reward mechanism that encourages explicit abstention when none of the sampled reasoning chains yields a correct answer.
  arXiv  Detail & Related papers  (2026-08-08T05:37:13Z)
• Reclaim Evaluation: A Lossy Memory Is Worse Than an Empty One [0.0]
  A language model's memory can be worse than no memory at all.<n>A memory that keeps a wrong conclusion but drops the work behind it makes the model emit the stale value as a confident answer.
  arXiv  Detail & Related papers  (2026-06-24T06:24:53Z)
• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing [3.4782736103257323]
  Large language models often hallucinate with high confidence on "random facts"<n>We formalize memorization of such facts as a membership testing problem.<n>We show that hallucinations persist as a natural consequence of lossy compression.
  arXiv  Detail & Related papers  (2026-01-31T21:18:28Z)
• Bias-Class Discrimination of Universal QRAM Boolean Memories [0.0]
  Given query access to a quantum memory, we ask: what can be inferred about the bias class of $f$ using coherent, addressable queries?<n>We show that for exact-weight bias classes, the induced single-query ensemble state on the address register has a two-eigenspace structure that yields closed-form expressions for the single-copy Helstrom-equivalent measurement and success probability.<n>This goes beyond the perfect-discrimination case of Deutsch-Jozsa and complements exact-identification settings such as Bernstein-Vazirani.
  arXiv  Detail & Related papers  (2025-12-19T12:14:18Z)
• LLMs Can Get "Brain Rot"! [68.08198331505695]
  Continual exposure to junk web text induces lasting cognitive decline in large language models (LLMs)<n>We run controlled experiments on real Twitter/X corpora, constructing junk and reversely controlled datasets.<n>Results provide significant, multi-perspective evidence that data quality is a causal driver of LLM capability decay.
  arXiv  Detail & Related papers  (2025-10-15T13:28:49Z)
• Are Hallucinations Bad Estimations? [19.11290014868759]
  We show that even loss-minimizing optimal estimators still hallucinate.<n>This reframes hallucination as structural misalignment between loss minimization and human-acceptable outputs.
  arXiv  Detail & Related papers  (2025-09-25T19:39:09Z)
• The Law of Knowledge Overshadowing: Towards Understanding, Predicting, and Preventing LLM Hallucination [85.18584652829799]
  We introduce a novel framework to quantify factual hallucinations by modeling knowledge overshadowing.<n>We propose a new decoding strategy CoDa, to mitigate hallucinations, which notably enhance model factuality on Overshadow (27.9%), MemoTrap (13.1%) and NQ-Swap (18.3%)
  arXiv  Detail & Related papers  (2025-02-22T08:36:06Z)
• Trust Me, I'm Wrong: LLMs Hallucinate with Certainty Despite Knowing the Answer [51.7407540261676]
  We investigate a distinct type of hallucination, where a model can consistently answer a question correctly, but a seemingly trivial perturbation causes it to produce a hallucinated response with high certainty.<n>This phenomenon is particularly concerning in high-stakes domains such as medicine or law, where model certainty is often used as a proxy for reliability.<n>We show that CHOKE examples are consistent across prompts, occur in different models and datasets, and are fundamentally distinct from other hallucinations.
  arXiv  Detail & Related papers  (2025-02-18T15:46:31Z)
• On Large Language Models' Hallucination with Regard to Known Facts [74.96789694959894]
  Large language models are successful in answering factoid questions but are also prone to hallucination. We investigate the phenomenon of LLMs possessing correct answer knowledge yet still hallucinating from the perspective of inference dynamics. Our study shed light on understanding the reasons for LLMs' hallucinations on their known facts, and more importantly, on accurately predicting when they are hallucinating.
  arXiv  Detail & Related papers  (2024-03-29T06:48:30Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.