Pith. sign in

REVIEW 2 major objections 4 minor 16 references

A rate-distortion theorem shows that, with finite memory, the optimal membership tester assigns high confidence to some non-facts, making hallucination the cheapest error mode.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 05:52 UTC pith:COUQ6OIQ

load-bearing objection The one-time-pad counterexample is real: Theorem 3.1 is false as stated because shared randomness is free under Definition 2.1, but the KL-minimization core and filter connections survive and deserve a reworked version. the 2 major comments →

arxiv 2602.00906 v7 pith:COUQ6OIQ submitted 2026-01-31 cs.LG cs.AIcs.CLcs.DScs.ITmath.IT

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

Anxin Guo , Jingwei Li This is my paper
classification cs.LG cs.AIcs.CLcs.DScs.ITmath.IT MSC 94A1768P0568T07
keywords hallucinationmembership testingrate-distortionKL divergencemutual informationBloom filtersparse regimememory capacity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper claims that high-confidence hallucinations on unstructured random facts are the information-theoretically optimal error pattern for a capacity-limited model, not a failure of training or data. It models fact storage as membership testing in a sparse universe and proves a rate-distortion theorem: the minimal memory per fact needed to hit given error rates is the minimum KL divergence between the score distributions on facts and non-facts. Under log-loss the unique optimum is a 'hallucination channel' where all facts and a fraction q* of non-facts receive the same high-confidence score, so no threshold can separate them. The same theorem recovers and sharpens known space lower bounds for Bloom-type filters. A sympathetic reader would care because it reframes hallucination mitigation: finite capacity makes a small hallucination rate the cheapest way to answer, and eliminating it costs unbounded memory unless the model also forgets facts.

Core claim

Core discovery: a rate-distortion theorem for membership testing. When |K|/|U| tends to zero, storing n keys with error (epsK, epsN) costs n * KL(muK || muN) + o(n) bits, where muK and muN are the score distributions on facts/non-facts minimizing KL. The bound is achievable. Under log-loss, the unique optimum is mu*_K = delta_{x*}, mu*_N = (1-q*)delta_0 + q*delta_{x*}, with x* = e^{-epsK}, q* = epsN / -ln(1-x*). So the optimal tester recalls all facts and assigns the same high confidence to a q* fraction of non-facts. Hallucination probability q* is set by the memory budget: KL = log(1/q*). Zero false positives is infinitely expensive unless rejecting all facts; thresholding cannot separate

What carries the argument

The key machinery is the rate-distortion function R_p(epsK, epsN) = min F_p(muK, muN) over feasible score distributions, where F_p = I(X; X_hat)/p measures the mutual information between a random Bernoulli fact indicator X and the tester's output X_hat, normalized per key. In the sparse limit p -> 0, this function converges to the KL divergence KL(muK || muN) (Theorem 3.1). The 'hallucination channel' - mu*_K = delta_{x*}, mu*_N = (1-q*)delta_0 + q*delta_{x*} - is derived via variational calculus and a KKT support condition, and it carries the argument: the optimal error mode places an atom of non-facts at the exact fact score, making them indistinguishable by any downstream procedure.

Load-bearing premise

The conclusion rests on the premise that a real LLM's effective memory for unstructured random facts is small and fixed; the paper's Appendix A gives heuristic reasons (regularization and structured knowledge crowding out random facts), but the experiments never measure the actual mutual information between weights and facts - if models can allocate unbounded effective capacity to random facts, hallucination need not be the optimal strategy.

What would settle it

Train a family of transformers on n random facts with controlled capacity (e.g., 1, 2, 4, 8 bits per fact) and measure the achievable (epsK, epsN) pairs. The theorem predicts the empirical frontier must lie at or above KL(mu*_K || mu*_N) with the hallucination atom at x* = e^{-epsK}. A specific falsifying observation would be a model that, with fewer than n * log(1/epsN) bits, achieves zero false positives while recalling all facts - or a learned non-fact score distribution that is spread rather than atomic and allows a threshold to remove hallucinations without hurting recall at the same memo

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Zero false positives is only compatible with the trivial regime that rejects all facts (epsK = 1) or with an unbounded memory budget; a 'reverse Bloom filter' that eliminates hallucinations without forgetting does not exist.
  • Optimal score distributions place hallucinations at the same confidence as facts, so any threshold that accepts a fact also accepts the hallucinated non-facts - thresholding cannot separate them.
  • Post-processing for factual accuracy (abstention, verification, thresholding) only moves a system along the memory-error frontier; it cannot cross it.
  • Retrieval-augmented generation is effective because non-parametric memory removes the memory-budget constraint, so the rate-distortion cost no longer applies.
  • For two-sided filters, the optimal per-key memory is KL(Bern(1-epsK) || Bern(epsN)), which recovers previous lower bounds and settles the previously open additive constant.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the effective-memory premise holds for real LLMs, the theorem predicts a quantitative law: the hallucination rate q on random facts should decay as 2^{-(effective bits per fact)}. Measuring I(W;K) directly - for instance via memorization probes at controlled model sizes - could test this.
  • The same analysis implies that training pressure toward 'always factual' or 'always helpful' should push models along the frontier into higher hallucination rates, not lower; the authors' reweighting experiments already hint at this, and it could be tested at production scale.
  • The atomic non-fact distribution suggests a testable corollary: confidence-calibration methods that claim to separate hallucinations from facts are either operating with more effective capacity than the theorem's regime or are not actually dealing with unstructured random facts.
  • The binary-decision result reframes over-refusal as the mirror cost of low hallucination; abstention-based mitigations should be evaluated against this frontier rather than treated as absolute cures.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper models LLM factuality as a membership-testing problem: a key set K drawn from a large universe U, a memory state W produced by Init, and confidence scores produced by Query. The main result (Theorem 3.1) claims that, in the sparse regime |K|/|U|→0, any tester meeting error constraints (εK,εN) needs at least min KL(µK∥µN)+o(1) bits per key, with matching achievability; Theorem 3.2 adds convergence of optimal score distributions, and Theorem 3.3 gives a first-order finite-universe correction. The paper then solves the KL-minimization for log-loss (Theorem 4.1), showing the optimal non-fact distribution has an atom at the fact score, which the authors interpret as information-theoretically optimal hallucination. A binary-decision variant recovers and sharpens Bloom-filter lower bounds, including a hash-based two-sided filter construction. Empirical experiments on synthetic Transformers are used to support the predicted hallucination channel.

Significance. If the main theorem is correct, the paper provides a clean rate-distortion characterization of membership testing and a provocative explanation for high-confidence hallucinations under optimal lossy compression. It also recovers known filter bounds and settles the additive constant for two-sided filters. The proofs are detailed and the variational solution in Theorem 4.1 is internally consistent. However, the central lower bound is false as stated because the paper allows free shared randomness while measuring memory only by I(W;K). The empirical validation is also partly circular and does not measure the information budget, so the LLM interpretation rests on an unverified premise. The mathematical framework is promising, but the definitional flaw must be fixed before the main claim can be accepted.

major comments (2)
  1. [§2 (Def. 2.1), Lemma 3.4, §B.1] The definition of membership tester includes shared randomness R, but the memory budget B(M)=I(W;K) does not count R. This is not a harmless convention: take R to be a uniformly random permutation of U, set W=R(K), and let Query return 1 iff R(i)∈W. Then I(W;K)=0 because R⊥K and W is marginally uniform, yet the tester has zero FPR and zero FNR. This directly violates Theorem 3.1. The proof of Lemma 3.4 applies data processing along K→W→X̂, but the actual chain is K→(W,R)→X̂, and I(K;W) does not upper-bound I(K;X̂). The same issue affects the symmetrization in Remark 2.2. The fix is to define B(M)=I(W;K|R), or to require R to be part of W / deterministic. With B(M)=I(W;K|R), the DPI step becomes I(K;X̂)≤I(K;W,R)=I(K;W|R), and the rest of the proof goes through. This is essential and must be corrected in the main text, not only in an appendix.
  2. [§4.3 and Appendix A] The empirical validation is partly circular: the 'theoretical optimum' atoms in Figures 1–3 are computed by plugging the observed losses (εK,εN) from the same trained model into the optimizer, so agreement with the empirical distributions is a consistency check, not an independent prediction of hallucination rates from model capacity. Moreover, the paper never measures B(M)=I(W;K) for the trained models; parameter count is used as a proxy, and Appendix A's argument that the effective memory budget for random facts is small is heuristic. Since the central LLM conclusion depends on the premise that real LLMs are near-optimal membership testers in the small-budget regime, this premise remains unverified. The authors should either measure an information-theoretic budget or clearly reframe the experiments as illustrative rather than confirmatory.
minor comments (4)
  1. [Abstract] The abstract states the theory is validated on 'both synthetic and real-world data', but the experiments in Section 4.3 use only synthetic data. Please make the abstract consistent.
  2. [Remark 4.2 / Appendix D.1] Remark 4.2 refers to 'Theorem D.1', but the corresponding statement in Appendix D.1 is labeled 'Lemma D.1'. Please unify the numbering.
  3. [Table 1 / Figures 1–4] All experiments use a single seed (42) and no variance estimates. Since Figures 1–4 compare empirical histograms to theoretical atoms, error bars or multiple seeds would strengthen the quantitative comparison.
  4. [§4.2, 'No non-trivial hallucination-free regime'] The sentence 'KL(Bern(1−εK)∥δ0)=∞' is correct, but the phrasing 'for every εK<1' might be misread as including εK=1. Consider clarifying that the degenerate εK=1 (reject all) is the only zero-FPR case with finite budget.

Circularity Check

0 steps flagged

No significant circularity: the rate-distortion theorem is a self-contained derivation; the empirical 'predicted atoms' are conditional checks with independent shape content.

full rationale

The main theorem chain (Lemma 3.4 -> Rp -> Theorem 3.1/3.2/3.3 -> Theorem 4.1/4.3) is derived from data-processing and variational arguments in the paper itself, and it is checked against external filter bounds (Carter et al.; Pagh and Rodler), so the core result is not equivalent to its inputs. Theorem 4.1's closed form (x*=e^{-εK}, q*=εN/(-ln(1-x*))) is a genuine optimization result; the synthetic experiments then measure (εK, εN) from a trained transformer and compare the empirical output distribution with the optimizer. This is a conditional prediction, not a fitted quantity renamed as prediction: the two-atom shape and the shared high-confidence atom are not forced by the observed loss values alone, so the validation has independent content, albeit weak. Appendix A's argument that effective memory for random facts is small is heuristic and cites external work (Feldman; Pan et al.); it is load-bearing for the LLM conclusion but is neither self-citational nor definitionally circular. I do not count the separate correctness flaw noted in the skeptic brief — Definition 2.1 admits shared randomness R while B(M)=I(W;K) ignores R, so a one-time-pad tester achieves B=0 with zero error and refutes Theorem 3.1 as stated — as circularity; it is a mathematical error in the proof's Markov-chain step, not a reduction of the conclusion to the premises.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

The mathematical theorems are self-contained given standard information theory (type covering, convex duality, envelope theorem). The burden is in the domain assumptions: the closed world, uniform random sparsity, and especially the unverified claim that real LLMs operate as membership testers with a small information budget for random facts. No free parameters are needed in the derivation; the empirical section uses measured losses as constraints rather than fitting the theorem's constants.

axioms (6)
  • domain assumption Closed-world assumption: all true facts are in K and all unseen potential facts are treated as non-facts at evaluation time.
    Invoked in §1; reduces LLM factuality to finite membership testing. In an open world with unknown true facts, the lower-bound story and the meaning of hallucination change.
  • domain assumption Key set K is a uniformly random n-subset of a finite universe U, with n/u→0.
    Theorem 3.1 and the hallucination analysis assume this sparse random-facts regime; real-world facts are not uniform random elements of a fixed universe.
  • standard math It suffices to study permutation-invariant membership testers.
    Remark 2.2 gives a symmetrization argument showing lower bounds transfer to all testers; standard in data-structure lower bounds.
  • standard math Error metrics dK,dN are nonnegative, LSC, perfect scores have zero error, and some c has finite error under both.
    Assumption 2.4; covers log-loss and FNR/FPR filters. The theorems rely on this for compactness/LSC arguments.
  • domain assumption An LLM can be modeled as a membership tester with memory budget I(W;K): Init=training, Query=inference, and scores estimate membership.
    §4's bridge from filters to LLMs. This is a modeling choice, not a proven property of trained transformers.
  • domain assumption The effective memory budget for random facts is small (regularization limits I(W;Z) and structured knowledge crowds out K).
    Appendix A argues via PAC-Bayes/MDL and a mutual-information decomposition, but the argument is heuristic; experiments use parameter count as a proxy and never measure I(W;K).

pith-pipeline@v1.3.0-alltime-deepseek · 35722 in / 21579 out tokens · 224139 ms · 2026-08-03T05:52:18.976204+00:00 · methodology

0 comments
read the original 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.

Figures

Figures reproduced from arXiv: 2602.00906 by Anxin Guo, Jingwei Li.

Figure 1
Figure 1. Figure 1: Output distributions on facts vs. non-facts ( [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Effect of different weight λF on fact. Each color represents a different model size. The amount of information per key decreases with λF for each model size. et al., 2024). Theorem 4.3 is agnostic to how xˆ is produced. Whether the decision is derived from a calibrated probability, a raw logit, a log-likelihood ratio, or a multi-stage verification chain that outputs a scalar score, the final thresholded ma… view at source ↗
Figure 3
Figure 3. Figure 3: Output distributions with 15145 facts and 8767 parameters. [PITH_FULL_IMAGE:figures/full_fig_p044_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Output distributions with 15145 facts and 33085 parameters. [PITH_FULL_IMAGE:figures/full_fig_p044_4.png] view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 1 linked inside Pith

  1. [1]

    2.F p(µK, µN )is continuous inp

    The function(p, µK, µN )7→F p(µK, µN )is jointly lower semi-continuous. 2.F p(µK, µN )is continuous inp. 3.F p is differentiable inpwith ∂ ∂p Fp(µK, µN ) =− KL(µN ∥pµK +(1−p)µN ) p2 wheneverp >0. Proof.We prove the three properties using the following identity: I(X; ˆX) = KL(P X, ˆX ∥PX ⊗P ˆX ) =E X∼Bern(p) KL(P ˆX|X ∥P ˆX ) =pKL(µ K∥µp) + (1−p)KL(µ N ∥µp...

  2. [2]

    We only need to verify continuity atp = 0

    Continuity inp.For fixed µK, µN, and p >0, Fp is clearly continuous as a composition of continuous functions. We only need to verify continuity atp = 0. Standard results in information theory have shown that the KL divergence vanishes sublinearly when the two distributions are close, see e.g. Proposition 2.20 in (Polyanskiy and Wu, 2025): ∂ ∂p KL(µN ∥µp) ...

    2025

  3. [3]

    Fredrik Hellstr"om, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky

    URLhttps://arxiv.org/abs/2507.22915. Fredrik Hellstr"om, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky. Generalization bounds: Perspectives from information theory and pac-bayes.Foundations and Trends in Machine Learning, 18(1):1–223, 2025. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. I...

    Pith/arXiv arXiv 2025

  4. [6]

    First, observe that the map( p, µK, µN ) 7→µ p = pµK + (1 −p )µN is continuous from the product topology to the weak-* topology

    Joint Lower Semi-Continuity.For any sequence( pn, µK,n, µN,n) → (p, µK, µN ), we show that lim infF pn ≥F p. First, observe that the map( p, µK, µN ) 7→µ p = pµK + (1 −p )µN is continuous from the product topology to the weak-* topology. Since KL divergence is jointly lower semi-continuous (LSC) with respect to the weak-* topology, it is immediate thatFp(...

  5. [8]

    For p∈ (0, 1), let ν := µK + µN and write fK := dµK dν , fN := dµN dν , so that the mixtureµp =pµ K + (1−p)µ N has density mp := dµp dν =pf K + (1−p)f N

    Differentiability in p.Fix µK, µN. For p∈ (0, 1), let ν := µK + µN and write fK := dµK dν , fN := dµN dν , so that the mixtureµp =pµ K + (1−p)µ N has density mp := dµp dν =pf K + (1−p)f N . Using (2), we can write I(p) :=I(X; ˆX) =p Z fK log fK mp dν+ (1−p) Z fN log fN mp dν. We first show thatI ′(p) = KL(µK∥µp) −KL (µN ∥µp). For convenience, we assume th...

    2011

  6. [9]

    , uin the sequencesx u andy u

    Let ˆPX,Y (x′, y′|xu, yu)be the joint empirical distribution ofxi and yi for i = 1, . . . , uin the sequencesx u andy u. Then, ˆPX,Y (x′, y′|xu, yu)−P X (x′)PY|X (y′|x′) ≤γ

  7. [10]

    WheneverP Y|X (y′|x′) = 0, ˆPX,Y (x′, y′|xu, yu) = 0. It follows from uniform continuity that, for sufficiently smallγ, all P ∗ Y|X -typical sequences yu under condition xu will have the empirical distribution of(xi, yi)close to P ∗ X,Y, and thus satisfy(4) and (5) for the desired choice ofδ. By Lemma 2.13 in Csiszár and Körner (2011), there exist sequenc...

    2011

  8. [11]

    Then µ∗ N = δ0

    If the minimum is uniquely atx = 0. Then µ∗ N = δ0. This implies C∗ = 0 λK = 0(since λK >1). This leads toJ(µ ∗ N ) =∞, which is not optimal

  9. [12]

    Then µ∗ N = δx∗

    If the minimum is uniquely atx∗. Then µ∗ N = δx∗. This implies µ∗ K = µ∗ N and KL = 0, a contradiction. We conclude thatµ∗ N is a two-point distribution: µ∗ N = (1−q ∗)δ0 +q ∗δx∗. We can now determineµ∗ K using the relative density in(7): because dµ∗ K dµ∗ N (0) = 0λK = 0, it follows that it is a point massµ∗ K =δ x∗. Now we use the tight constraints to d...

  10. [13]

    Constraint onµ ∗ K:E µ∗ K [−lnX] =ε K =⇒ −ln(x∗) =ε K =⇒x ∗ =e −εK

  11. [14]

    (1−q ∗)(−ln 1) +q ∗(−ln(1−x ∗)) =ε N =⇒q ∗ = εN −ln(1−x ∗)

    Constraint onµ ∗ N:E µ∗ N [−ln(1−X)] =ε N. (1−q ∗)(−ln 1) +q ∗(−ln(1−x ∗)) =ε N =⇒q ∗ = εN −ln(1−x ∗) . The conditione −εK +e −εN >1ensures thatε N <−ln(1−e −εK ), so0< q ∗ <1. Step 4: verifying KKT conditions.Note that we calculate C∗ = Eµ∗ N [X λK ] = q∗(x∗)λK (since λK >1). Condition 1:g(x ∗) = 0. g(x∗) =− (x∗)λK C∗ −λ N ln(1−x ∗) =− 1 q∗ −λ N ln(1−x ∗...

  12. [15]

    (Constraints preserved)E ¯µK [1− ˆX] =E µK [1− ˆX]andE ¯µN [ ˆX] =E µN [ ˆX]

  13. [16]

    Consequently, in the definition ofRp(εK, εN )we may restrict toˆx∈ {0,1}, and the optimal output distributions are Bernoulli

    (Objective non-increasing) For everyp∈(0,1), Fp(¯µK,¯µN )≤F p(µK, µN ). Consequently, in the definition ofRp(εK, εN )we may restrict toˆx∈ {0,1}, and the optimal output distributions are Bernoulli. Proof sketch.The first part follows from linearity: underT, the binary outputY∈ {0, 1} satisfies E[Y| ˆX = t] = t, hence E[Y ] = E[ ˆX]and E[1 −Y ] = E[1 − ˆX]...

    2009

  14. [2001]

    world state

    doi: 10.1007/3-540-44676-1\_25. URLhttps://doi.org/10.1007/3-540-44676-1_25. Zhixuan Pan, Shaowen Wang, and Jian Li. Understanding LLM behaviors via compression: Data generation, knowledge acquisition and scaling laws.CoRR, abs/2504.09597, 2025. doi: 10.48550/ ARXIV.2504.09597. URLhttps://doi.org/10.48550/arXiv.2504.09597. 20 Michal Perelkiewicz and Rafal...

    doi:10.48550/arxiv.2504.09597 2025

  15. [2021]

    URLhttps://doi.org/10.1145/3442188.3445922

    doi: 10.1145/3442188.3445922. URLhttps://doi.org/10.1145/3442188.3445922. Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors.Commun. ACM, 13(7): 422–426, 1970. doi: 10.1145/362686.362692. URLhttps://doi.org/10.1145/362686.362692. Avrim Blum and John Langford. Pac-mdl bounds. InLearning Theory and Kernel Machines: 16th Annual Confe...

    arXiv 1970

  16. [2025]

    Zeyuan Allen-Zhu and Yuanzhi Li

    URLhttps://arxiv.org/abs/2510.06265. Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 3.1, knowledge storage and extraction. InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URLhttps://openreview.net/forum?id= 5x788rqbcj. Zeyuan Allen-Zhu and Yuanzhi Li. Physic...

    arXiv 2024