Predictable Compression Failures Why Language Models Actually Hallucinate
Leon Chlon, Ahmed Karim, Maggie Chlon · 2025
Read Predictable Compression Failures Why Language Models Actually Hallucinate by Leon Chlon, Ahmed Karim, Maggie Chlon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11208.txt.
Introduction
Leon Chlon and three co-authors study a quiet failure mode of transformer models in this 2025 machine learning paper. A model may decide yes or no from a set of evidence passages. Shuffling the passage order can change its answer. The evidence itself stays the same.
The authors model this order sensitivity mathematically. They derive bounds on how much answers scatter under shuffling. They also build decision tools from the theory. One tool is a sufficiency gate. The model answers only when evidence carries enough information. Otherwise it abstains. The team tested thousands of grounded questions from public datasets. In a held-out audit, the gate kept wrong answers near zero. It declined roughly a quarter of the questions.
Catalog record
| CREATOR | Leon Chlon, Ahmed Karim, Maggie Chlon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-11208
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Predictable Compression Failures Why Language Models Actually Hallucinate Leon Chlon, Ahmed Karim, Maggie Chlon Abstract Large language models perform near-Bayesian inference yet violate permutation invariance on exchangeable data. We resolve this by showing transformers minimize expected conditional description length (cross-entropy) over orderings, 𝔼 π [ ℓ ( Y ∣ Γ π ( X ) ) ] \mathbb{E}_{\pi}[\ell(Y\!\mid\!\Gamma_{\pi}(X))] , which admits a Kolmogorov-complexity interpretation up to additive constants, rather than the permutation-invariant description length ℓ ( Y ∣ X ) \ell(Y\!\mid\!X) . This makes them Bayesian in expectation, not in realization . We derive (i) a Quantified Martingale Violation bound showing order-induced deviations scale as O ( log n ) O(\log n) with constants; (ii) the Expectation-level Decompression Law linking information budgets to reliability for Bernoulli predicates; and (iii) deployable planners (B2T/RoH/ISR) for answer/abstain decisions. Empirically, permutation dispersion follows a + b ln n a+b\ln n (Qwen2-7B b ≈ 0.377 b\approx 0.377 , Llama-3.1-8B b ≈ 0.147 b\approx 0.147 ); permutation mixtures improve ground-truth likelihood/accuracy; and randomized dose-response shows hallucinations drop by ∼ \sim 0.13 per additional nat. A pre-specified audit with a fixed ISR=1.0 achieves near-0% hallucinations via calibrated refusal at 24% abstention. The framework turns hallucinations into predictable compression failures and enables principled information budgeting. 1 Introduction Large language models (LLMs) exhibit a fundamental paradox: they demonstrate remarkable in-context learning capabilities consistent with Bayesian inference Xie et al. 2022 , Zhang et al. 2023 , Bai et al. 2023 , yet systematically violate the permutation invariance that characterizes Bayesian predictive distributions on exchangeable data Falck et al. 2024 . For truly exchangeable sequences where p(x_{1},\ldots,x_{n})=p(x_{\pi(1)},\ldots,x_{\pi(n)}) , Bayesian inference yields predictive distributions satisfying \mathbb{E}[f(X_{n+1})|X_{1},\ldots,X_{n}]=\mathbb{E}[f(X_{n+1})|X_{\pi(1)},\ldots,X_{\pi(n)}] for any permutation \pi . The violation of this property indicates a mismatch between transformer architectures and exchangeability assumptions, yet transformers achieve near-optimal statistical performance across diverse tasks. How can models be simultaneously Bayesian and non-Bayesian? We validate theory using observables not defined by our metrics: ground-truth likelihood/accuracy under permutation mixtures, the log-scaling of permutation-induced dispersion, and randomized dose-response of hallucination to information budgets (see Appendix B for full non-circular validation principle). 1.1 Our Contributions We resolve this paradox through three interconnected theoretical and empirical contributions: 1. Theoretical Resolution: Conditional Complexity Minimization. We show that transformers with positional encodings minimize expected conditional description length (cross-entropy), \mathbb{E}_{\pi}[\ell(Y|\Gamma_{\pi}(X))] , rather than the permutation-invariant \ell(Y|X) . This admits a Kolmogorov-complexity interpretation up to additive constants. This fundamental distinction explains why transformers are “Bayesian in expectation, not in realization”: they achieve entropy-level compression and calibration when averaged over orderings but systematically deviate for fixed input sequences. Our Quantified Martingale Violation theorem (Theorem 1 ) provides an explicit O(\log n) upper bound with constants for these deviations under harmonic positional decay. 2. Compression Failure Framework: From Theory to Hallucination. Building on recent connections between compression and learning Delétang et al. 2023 , Kalai and Vempala 2024 , we develop the Expectation-level Decompression Law (EDFL, Theorem 5 ) that quantifies precisely how much information \bar{\Delta} is required to lift an event’s probability from prior mass \bar{q} to posterior mass p . Unlike existing work that treats compression as binary success/failure, EDFL provides exact bounds: for fixed p=1-\varepsilon , achieving reliability 1-\varepsilon for rare events ( q\ll 1 ) requires \bar{\Delta}\geq(1-\varepsilon)\log\frac{1}{\bar{q}}+O(\bar{q}) nats. This transforms hallucination from an unpredictable failure mode into a quantifiable consequence of information insufficiency. 3. Operational Deployment Tools. We bridge theory and practice through three metrics derived from EDFL: • Bits-to-Trust (B2T) : Information needed for target reliability h^{*} • Risk-of-Hallucination (RoH) : Achievable error given information budget • Information Sufficiency Ratio (ISR) : Ratio determining abstention decisions These planners align with the pre-specified ISR boundary in frontier model audits, enabling practitioners to predict hallucination risk before generation and manage it through information budgeting. 1.2 Empirical Validation We validate our framework through three complementary experiments: Empirical (Primary, non-circular). (i) Permutation mixtures improve ground-truth likelihood/accuracy (mixture Jensen gain). (ii) Permutation dispersion follows a+b\ln n with b\approx 0.377 across 3,059 items. (iii) Randomized dose-response shows \approx 0.13 fewer hallucinations per nat. Deployment (Secondary, calibration only). A pre-specified ISR boundary ( =1.0 ) exhibits 96.2% boundary alignment; this is reported as a calibration check rather than as primary validation. Ground-truth permutation analysis establishes that permutation-induced dispersion precisely follows O(\log n) across models. Causal dose-response studies establish that information content, not just prompt length, determines hallucination rates. Pre-specified permutation audits on 528 held-out QA tasks prevent post-hoc selection bias. Our work synthesizes multiple research streams. While Xie et al. 2022 established Bayesian interpretations, Falck et al. 2024 documented permutation invariance violations, and Farquhar et al. 2024 developed detection methods, no prior work explained how these phenomena coexist or provided predictive frameworks. By showing positional processing creates an inherent gap between average-case and worst-case behavior through a positional Jensen inequality, we provide the missing theoretical foundation. Rather than treating hallucinations as inevitable Kalai and Vempala 2024 or relying on post-hoc detection Farquhar et al. 2024 , practitioners can now predict and prevent failures through principled information management. 2 Related Work Bayesian interpretations, MDL, and positional encodings. A large body of work ties transformers to Bayesian inference: in-context learning as implicit Bayes Xie et al. 2022 , approximate Bayesian model averaging Zhang et al. 2023 , near-optimal predictive power Bai et al. 2023 , and full Bayesian inference comparable to MCMC Reuter et al. 2024 . However, Falck et al. 2024 show that LLMs violate permutation invariance. The compression-learning connection has deep roots in Minimum Description Length (MDL) Grünwald 2007 , with Delétang et al. 2023 establishing equivalence between language modeling and compression. Positional encodings fundamentally alter behavior. Liu et al. 2024 documented systematic “lost-in-the-middle” effects. Our O(\log n) bounds with explicit constants provide finer characterization connecting to compression failure. Hallucination detection vs prevention. Farquhar et al. 2024 introduced semantic entropy for detection, achieving AUROC 0.790 by clustering semantically equivalent responses. Kalai and Vempala 2024 proved calibrated models must hallucinate at rates approximated by Good-Turing estimation. Multiple 2024 papers adopted “LLMs as lossy compression” perspectives Su et al. 2024 , Vasilatos et al. 2024 , but without formal frameworks. While these works provide detection methods or prove inevitability, our EDFL offers the first predictive theory linking compression failure to hallucination with preventive measures through information budgeting. 3 Theory: Order-Sensitive Information-Theoretic Guarantees We formalize how positional processing creates systematic deviations from Bayesian behavior while maintaining average-case optimality. 3.1 Setup and Notation Let X=(x_{1},\ldots,x_{n}) be a sequence with sufficient statistic T(X) for predicting target Y . Let \pi denote a permutation of chunk indices \{1,\ldots,n\} , \Gamma_{\pi} a content-preserving reordering map where \Gamma_{\pi}(X)=(x_{\pi(1)},\ldots,x_{\pi(n)}) , and S_{\pi}(\cdot)=\Pr(\cdot|\Gamma_{\pi}(X)) the model’s predictive distribution given permuted input. Define q_{\pi}(x)=\mathbb{E}[f(X_{n+1})|\Gamma_{\pi}(x)] as the prediction under permutation \pi and \bar{q}(x)=\mathbb{E}_{\pi}[q_{\pi}(x)] as the average prediction over permutations. All expectations over \pi are conditional on fixed item x . We assume P\ll S_{\pi} for all \pi (absolute continuity), smoothing zero-probability tokens with \varepsilon=10^{-9} in practice. We write E_{\text{pair}}:=\mathbb{E}_{\pi,\pi^{\prime}}|q_{\pi}(x)-q_{\pi^{\prime}}(x)| for the expected pairwise absolute difference across independent permutations. All information quantities (KL divergences, information budgets, Jensen gaps) are reported in nats unless otherwise noted. 3.2 Quantified Martingale Violations Definition 1 (Permutation-induced residual) . For the Answer/Refusal indicator f and position-aware