Predictable Compression Failures: Why Language Models Actually Hallucinate

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, E_π[(Y Γ_π(X))], which admits a Kolmogorov-complexity interpretation up to additive constants, rather than the permutation-invariant description length (Y 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) 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+bln n (Qwen2-7B b ≈ 0.377, Llama-3.1-8B b ≈ 0.147); permutation mixtures improve ground-truth likelihood/accuracy; and randomized dose-response shows hallucinations drop by ~ 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.