PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xi Wang, Shijia Xu, Rongfeng Guo

arXiv:2609.12111v1cs.CL

TL;DR

Closed-book factual error is often framed as missing coverage, although observed facts can also be recalled incorrectly when stored under finite memory. The paper models this distinction with a rate-distortion bound and tests its predicted signatures in simulations and controlled fact-injection probes. The results support a separable account of lossy recall, not a complete theory of hallucination.

  • Problem

    Missing coverage is a common explanation for factual errors, but facts that were observed may also be recalled incorrectly when memory stores them lossily.

    Source: §1 · p. 1

  • Method

    The paper models unstructured factual recall as compression of observed labels under finite memory and analyzes the resulting coverage and distortion errors.

    Source: §3 · p. 3

  • Results

    Increasing independent fact load under fixed effective memory raises observed-query error, while increasing adapter rank shifts the transition and unseen entities remain near chance.

    Source: §4.5 · p. 8

  • Takeaways & Limitations

    Observed-query error provides a direct diagnostic for lossy factual recall, while unseen-entity error diagnoses missing coverage.

    Source: §5 · p. 8, §4.5 · p. 8

    The model assumes a maximally unstructured random source and uses an abstract effective-memory budget; the probes use synthetic fact injection and do not cover every source of open-domain hallucination.

    Source: Limitations · p. 9

Abstract

from arXiv · show

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}\delta^\star\!\left(\frac{B}{M}\right) + \left(1-\frac{M}{N}\right)\left(1-\frac{1}{K}\right)$, where $\delta^\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.

1 Introduction

Closed-book factual error can arise not only from missing facts, but also from lossy recall of facts that were observed. The paper formalizes this coverage–compression trade-off and studies its predicted signatures with simulations and controlled fact-injection probes.

1 Introduction

  • A fact may be recalled incorrectly even after observation, because finite memory can store its value only in a lossy code.The paper distinguishes this failure of recall under compression from a failure of exposure.Source: §1 · p. 1
  • The model uses a uniformly random query-to-answer mapping, removing semantic regularity so correct prediction must come from stored information.It considers N queries, K answers, M observed pairs, at most B memory bits, and test queries answered without retrieval.Source: §1 · p. 1
  • The lower bound separates distortion on observed facts from guessing error on unobserved queries, with nonzero observed-fact error when B/M < log2 K.When B/M ≥ log2 K, observed facts can be stored losslessly and the bound reduces to the unseen-query floor.Source: §1 · p. 2
  • Structure can reduce the number of independent facts that must be stored, while long-context organization poses an analogous competition for limited effective attention.Selective allocation can yield diminishing returns; compression overload arises when many observed facts share a fixed effective representation and B/M falls.Source: §1 · p. 2
  • Theory-implied simulations instantiate the distortion-rate envelope, while language-model probes vary independent fact load and effective trainable memory.Observed-query, unobserved-query, and full-space errors measure lossy recall, missing coverage, and their mixture, respectively.Source: §1 · p. 2
  • The paper’s contributions are a rate-distortion lower bound and a diagnostic framework for measurable signatures in simulations and controlled fact-injection probes.Its claim is limited: compression is a separable mechanism, not a complete theory of hallucination.Source: §1 · pp. 2–3

2 Problem Setting

The problem setting isolates unstructured factual recall: a learner stores labels for a sampled subset of queries under a finite memory budget and answers test queries without retrieval.

2 Problem Setting

  • The ground-truth mapping is uniformly random, making the query labels independent uniform K-ary symbols without semantic, logical, or distributional shortcuts.This is a null model for unstructured factual memory, not a claim that real knowledge is random.Source: §2 · p. 3
  • The learner observes a uniformly sampled training set S of M queries and their labels, then encodes the observed information in a memory state of at most 2^B possibilities.At test time, it answers a query without retrieval and may use randomized encoders and decoders.Source: §2 · p. 3
  • Under free addressing, the decoder may condition on the training index set and query identity, while B is charged only for stored answer information.This convention favors the learner; storing query identities would require an additional address cost.Source: §2 · p. 3
  • Expected full-space error is measured under a uniform test-query distribution, and training coverage does not guarantee effective memory coverage.A fact may be present in the training set yet still be recalled incorrectly.Source: §2 · p. 3

3 Coverage–Compression Theory

The theory separates error on observed facts, caused by lossy reconstruction, from guessing error on unobserved queries. Under a random-source model with free addressing, it lower-bounds recall error by combining these two sources.

3 Coverage–Compression Theory

  • Conditioned on the observed queries, their independent uniform K-ary labels form a source that memory compresses and the decoder reconstructs coordinate by coordinate.The relevant distortion is factual recall error.Source: §3 · pp. 3–4
  • Theorem 3.1 combines rate-distortion error on observed facts with guessing error on unobserved queries to lower-bound total error.A uniformly drawn query is observed with probability M/N; otherwise its label is independent of memory and can only be guessed.Source: §3 · pp. 3–4
  • When B/M ≥ log2 K, observed facts can be stored losslessly; below that rate, observed facts have a nonzero recall-error floor.Even perfect recall leaves the error floor from unobserved queries.Source: §3 · pp. 3–4
  • Under free addressing, the bound is achievable up to finite-blocklength effects as M grows with B/M approaching a fixed rate.Standard rate-distortion codes attain observed-fact distortion δ⋆(r)+o(1), while unobserved queries are answered by random guessing.Source: §3 · p. 4
  • The main theorem assumes free addressing; explicitly encoding query identities adds address cost and tightens the effective memory constraint.The address-charged variant is presented as a conservative analogue.Source: §3 · p. 4
  • With selective allocation, more observations need not hurt an optimal learner; the predicted pattern is saturation or diminishing returns.The feasible set grows with M.Source: §3 · pp. 4–5
  • Compression overload requires all observed facts to share one fixed effective representation; a U-shaped full-space error curve is not universal.It requires additional mechanisms such as forced uniform allocation, interference, or an evaluation distribution concentrated on competing facts.Source: §3 · p. 5
  • In the structured-fact model, one independent base fact can support multiple surface queries, reducing how many independent facts must be compressed.The model assigns each base label to a block of c derived queries through known one-to-one transformations.Source: §3 · p. 5

4 Empirical Signatures of Coverage–Compression

Theory-implied simulations and controlled fact-injection probes test whether coverage and compression produce separable error signatures. Across the probes, greater independent fact load under fixed effective memory raises observed-fact error, while more memory or structure shifts overload; the long-context result is only a qualitative analogue.

4.1 Setup and diagnostics

  • The probes distinguish observed-query error as a compression diagnostic, unobserved-query error as a coverage diagnostic, and full-space error as their mixture.Synthetic independent facts and held-out query forms make coverage and fact load known by construction; LoRA rank is a proxy for effective trainable memory, not the theoretical bit budget B.Source: §4.1 · p. 5

4.2 Theory-implied envelope

  • Theory-implied sweeps instantiate the rate-distortion envelope rather than measure language-model performance.They make explicit how missing coverage and per-fact distortion can move differently as fact load changes at fixed memory.Source: §4.2 · p. 6
  • The envelope predicts that increasing fact load at fixed memory can lower missing-coverage error while raising observed-fact error, even when full-space error improves.Increasing memory moves the system along the distortion-rate curve, and structure increases query coverage per independent stored fact.Source: §4.2 · p. 6

4.3 Capacity-controlled fact injection

  • At fixed adapter rank, observed-fact fidelity degrades as independent injected facts grow, while higher rank delays the high-error transition across tested models.The model probes support the predicted diagnostic direction, not exact numerical agreement with the ideal rate-distortion curve.Source: §4.3 · p. 6, Figure 2 · p. 6, Figure 3 · p. 7

4.4 Robustness and structure

  • Unseen entities stay near chance, while seen-query error rises with fact load; paraphrased and relation-rephrased queries degrade earlier than direct queries.The seen-relation split excludes ambiguous inverse queries, and unseen-entity error is near 0.9 for K = 10.Source: §4.4 · p. 7, Figure 4 · p. 7
  • With the same surface-query count, sharing fewer independent base facts delays overload relative to assigning an independent label to every query.The result illustrates the role of structure in this framework, not a claim that all reasoning reduces to deductive closure.Source: §4.4 · p. 7, Figure 5 · p. 8

4.5 Long-context analogue and summary

  • In the long-context probe, error grows with in-context fact count for non-literal middle-position retrieval, but this is a qualitative analogue, not a direct test of the parametric-memory theorem.The probe concerns facts present in the prompt and does not estimate Bctx or quantitatively test Theorem 3.1.Source: Figure 6 · p. 8, §4.5 · p. 8

5 Discussion and Conclusion

Closed-book factual error can reflect either missing coverage or lossy recall of observed facts. The discussion uses this distinction to interpret diagnostics and interventions, while limiting the claim to a separable mechanism rather than a complete theory of hallucination.

5 Discussion and Conclusion

  • Unseen-entity error diagnoses missing coverage, while observed-query error diagnoses lossy recall of injected facts.The bound distinguishes queries without effective coverage from observed facts stored with insufficient fidelity.Source: §5 · p. 8
  • The bound is a limit on unstructured factual memorization, not a complete theory of hallucination.It identifies a capacity scale rather than an optimal dataset size; more observations need not hurt an optimal learner, though forced sharing or interference can degrade fidelity.Source: §5 · p. 8
  • Retrieval shifts factual burden from parametric memory to retrieval and verification, while abstention avoids queries outside reliable coverage.Structure and reasoning reduce the number of independent facts to store; long-context organization addresses competition for limited effective attention or context capacity.Source: §5 · p. 8
  • At fixed adapter rank, more injected independent facts raise observed-query error; increasing rank shifts the transition, unseen entities stay near chance, and structure delays overload.The controlled probes support a diagnostic interpretation, not exact numerical identification with the idealized rate-distortion curve.Source: §5 · p. 8

Limitations

The theory and empirical probes use deliberately restricted models of factual memory. Their conclusions therefore do not cover all properties of natural knowledge or all sources of open-domain hallucination.

Limitations

  • The uniform random mapping omits semantic, logical, temporal, and distributional redundancy in real knowledge.The bit budget is an abstract effective-memory measure rather than a direct parameter-count law; LoRA rank serves only as a controlled capacity proxy.Source: Limitations · p. 9
  • The empirical study uses controlled synthetic fact injection rather than naturally occurring factual knowledge.It does not cover every source of open-domain hallucination, including conflicting evidence, outdated knowledge, decoding behavior, calibration failure, or instruction-following pressure.Source: Limitations · p. 9

A Technical Details and Proofs

The appendix supplies omitted derivations, memory-accounting conventions, tightness details, and allocation variants. Its rate-distortion preliminaries explain how addressing assumptions and tolerated reconstruction errors affect the memory accounting.

A Technical Details and Proofs

A.1 Memory Accounting and Rate-Distortion Preliminaries

  • Under free addressing, query identities are available to the decoder and the budget counts stored answer information, not addresses.Encoding which queries are stored would require an additional address cost, so free addressing favors the learner.Source: §A.1 · p. 11
  • Allowing distortion reduces the bits needed per fact by letting a reconstructed sequence represent nearby true sequences.The counting argument chooses error positions and alternative labels to estimate how many true sequences lie near a reconstruction.Source: §A.1 · p. 11

A.2 Coverage, Compression, and Tightness

The appendix derives a lower bound by combining distortion on observed facts with guessing error on unseen queries, and describes when that envelope is tight. It then contrasts selective storage with forced compression as the number of observations grows.

A.2 Coverage, Compression, and Tightness

  • A test query is unseen with probability (N − M)/N, so even perfect answers on observed queries leave a full-space error floor.Source: §A.2 · p. 11
  • The bound combines observed-query distortion δ⋆(B/M) with unseen-query guessing error 1 − 1/K, weighted by their query probabilities.For an unseen query, its label is independent of observed labels; the theorem applies to any learner with memory budget B.Source: §A.2 · pp. 11–12
  • Under free addressing, the lower bound is tight up to finite-blocklength effects as block rate-distortion codes approach the observed-fact distortion.The decoder reconstructs observed answers from the code and guesses uniformly on unseen queries.Source: §A.2 · p. 12

A.3 Allocation Regimes

  • With selective memory, expected error is non-increasing as observations grow, so finite memory alone does not mean more data hurts an optimal learner.The lossless endpoint is approximately B/log2 K unstructured K-ary facts under free addressing.Source: §A.3 · p. 12
  • With forced shared compression, more observations reduce unseen-query error but can raise observed-fact distortion as the per-fact rate B/M falls.A U-shaped full-space curve is not implied by finite memory alone; it requires an additional mechanism such as forced uniform allocation or interference.Source: §A.3 · p. 12

A.4 Structure and Abstention

The structured variant treats independent base facts as supporting multiple derived queries, while abstention concentrates memory on fewer answered queries at reduced coverage. The accompanying theory-implied sweeps and probe details specify how these settings are evaluated, including a long-context analogue that is not a measurement of a particular model.

A.4 Structure and Abstention

  • With closure factor c, each stored base fact supports c derived queries, propagating base-label distortion while reducing the effective memory load per surface query.The bound combines distortion on observed base facts with guessing error on queries tied to unobserved base facts.Source: §A.4 · p. 13
  • Abstention lets the learner concentrate memory on fewer answered queries, trading lower answer coverage for a coverage–accuracy trade-off.The selective variant answers a fraction 1 − γ of the query space and abstains on the remainder.Source: §A.4 · p. 13

B Theory-Implied Simulation Details

  • The theory-implied sweeps numerically invert the K-ary distortion-rate function and substitute the result into the operating curves; they are not language-model measurements.The reported sweep values use K = 10 and are rounded to three decimals.Source: B Theory-Implied Simulation Details · p. 13

B.1 Unstructured Coverage–Compression Decomposition

  • The unstructured sweep specifies coverage-only, lossless-selective, and forced-compression operating curves for N = 5,000, K = 10, and B = 160 bits.The supplied passages identify these operating curves but do not give their numerical values.Source: §B.1 · pp. 13–14

B.3 Deductive Closure

  • The deductive-closure sweep uses c = 10, with each observed base fact supporting ten derived queries in the structured operating curve.The numerical operating-curve values are not given in the supplied passages.Source: §B.3 · p. 14

B.4 Long-Context Analogue

  • The long-context analogue predicts conditional recall error for in-context facts using K = 10 and Bctx = 320 bits, rather than measuring a particular model.The paper distinguishes this analogue from a direct long-context model measurement.Source: §B.4 · p. 14

C Real-Model Probe Details

  • The controlled probes make injected facts known by construction, use a disjoint unseen-entity split, and report mean ± standard error across three seeds.The stated seeds are 3407, 2025, and 1337.Source: C Real-Model Probe Details · p. 14

C.1 Hardware, Software, and Data

The probe setup uses synthetic entity-label facts and disjoint train/test entities, then adapts models with LoRA under a common training and deterministic-decoding configuration.

C.1 Hardware, Software, and Data

  • Adaptation runs use a single node with eight NVIDIA A100-SXM4-80GB GPUs connected by NVLink.The passage also specifies the software stack, including PyTorch 2.4.x and Transformers 4.45.x.Source: §C.1 · p. 14
  • Synthetic facts are entity-label mappings with uniformly sampled labels from ten choices, and the unseen-entity pool matches the injected pool in size without train/test entity overlap.Each fact is expressed with two training templates.Source: §C.1 · p. 14

C.2 Adaptation and Decoding Configuration

  • Fact-injection probes use LoRA rank as a controlled capacity proxy, not as the theoretical bit budget, with deterministic decoding at temperature 0.0.LoRA is applied to q_proj, v_proj, and o_proj; the specified configuration also includes a maximum sequence length of 96.Source: §C.2 · p. 14

C.3 Capacity-Controlled Fact Injection Results

The reported probes show that increasing LoRA rank shifts the high-error transition to larger fact loads, while query form and structured fact organization are also examined.

C.3 Capacity-Controlled Fact Injection Results

  • Increasing LoRA rank shifts Qwen3-8B’s high-error transition to larger fact loads on seen-direct queries.The representative rank sweep compares ranks 4, 16, and 64; the supplied passages do not report the table’s individual values.Source: §C.3 · p. 14, Table 11 · p. 17
  • At fixed LoRA rank 16, the model comparison evaluates seen-direct queries, but the supplied passages do not identify a winning model.The corresponding table reports errors as mean ± standard error over three seeds.Source: §C.3 · p. 14, Table 12 · p. 18

C.4 Query-Form Robustness and Structure Results

  • For DeepSeek-R1-Distill-Qwen-32B, unseen-entity error remains near chance, while paraphrased and relation-rephrased queries degrade earlier than direct queries.The comparison is reported at LoRA rank 16.Source: §C.4 · p. 14, Table 13 · p. 18
  • The structured-versus-unstructured comparison uses closure factor c = 10, making independent base facts approximately one tenth of the surface-query count.The supplied passages identify the comparison and its setup but do not state its outcome.Source: §C.4 · p. 14, Table 14 · p. 18

Related papers

Loading 2609.12111v1…