Predictable Compression Failures: Order Sensitivity and Information Budgeting for Evidence-Grounded Binary Adjudication

Ahmed Karim; Leon Chlon; Maggie Chlon; MarcAntonio Awada

REVIEW 4 major objections 5 minor 12 references

Predictable Compression Failures: Order Sensitivity and Information Budgeting for Evidence-Grounded Binary Adjudication

T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read Transformers are Bayesian in expectation but order-sensitive in realization, making hallucination a predictable compression failure.

desk verdict Useful abstention toolkit; the Bayesian-in-expectation story is not proven for standard transformers. read the letter →

arxiv 2509.11208 v3 pith:TQXWJUBR submitted 2025-09-14 stat.ML cs.LG

Leon Chlon , Ahmed Karim , Maggie Chlon , MarcAntonio Awada This is my paper · ORCID

classification stat.MLcs.LG MSC 68T0768Q3062B1094A17

keywords hallucinationpermutationinvarianceinformationbudgetcompressioncross-entropyabstentiontransformerinterpretabilitycalibration

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper argues that transformers trained with next-token prediction minimize expected conditional description length averaged over evidence orderings, not the permutation-invariant loss that Bayesian symmetry would require. That distinction explains why models can look well-calibrated on average yet flip their answers when evidence chunks are reordered. The authors derive a bound showing order-induced prediction deviations grow logarithmically with context length, and an information-theoretic lower bound (the Expectation-level Decompression Law) showing how much evidence information is needed to reach a target reliability for rare events. They build these into a decision rule that abstains when the measured information budget falls short, and report that a fixed threshold achieves near-zero hallucination at about 24% abstention on a held-out audit. A sympathetic reader would care because the framework turns hallucination from an unpredictable failure into a quantity that can be computed before generation.

What carries the argument

The Quantified Martingale Violation (QMV) bound is the first pillar: it converts adjacent-rank positional sensitivity into an expected-absolute-deviation bound using a logistic Lipschitz lemma and a harmonic-distance identity, yielding the O(log n) law. The second pillar is the Expectation-level Decompression Law (EDFL), which applies convexity of KL divergence plus data processing to Bernoulli predicates, giving a closed-form lower bound on the information budget needed for reliability. The third is the Information Sufficiency Ratio (ISR), the ratio of the measured information budget to the bits-to-trust target; the gate ISR≥1 triggers answering, otherwise abstention. The theory also includ

What would settle it

Compute, on held-out items, both the measured expected KL budget Eπ KL(P∥Sπ) and the EDFL lower bound KL(Ber(p)∥Ber(q̄)); if a nontrivial fraction of items satisfy the reverse inequality at the claimed reliability, the law is falsified. Alternatively, train a standard transformer on exchangeable data and check whether the dispersion slope b exceeds the O(log n) prediction (e.g., super-logarithmic growth) or whether permutation mixtures fail to improve ground-truth cross-entropy.

Watch

Extended reading notes

Core claim

The central claim is that the apparent paradox of LLMs being both Bayesian and permutation-violating is resolved by recognizing the training objective: models minimize Eπ[ℓ(Y|Γπ(X))], the cross-entropy averaged over all orderings of the evidence, rather than the permutation-invariant ℓ(Y|X). As a result the predictive distribution is a uniform mixture over permutations, which is exchangeable in expectation but not in any fixed realization. The paper proves a Quantified Martingale Violation bound showing that, under bounded total variation of logit changes under adjacent swaps, the expected absolute residual grows as O(log n) in the harmonic regime. It then proves the Expectation-level Decomp

Load-bearing premise

The paper assumes that standard next-token training actually drives the model toward minimizing expected conditional description length averaged over evidence orderings; if gradient descent does not converge to that permutation-mixture optimum, the expectation-realization gap is not explained by the theory.

Editorial extensions

If this is right

Order-induced dispersion in binary adjudication should scale as a+b log n across model families, with the slope constant capturing architecture-specific positional sensitivity.
Uniform permutation mixtures are near-optimal in cross-entropy, so averaging predictions over reorderings improves ground-truth likelihood without learning new weights.
Randomized variation in the number of supporting evidence chunks should causally move hallucination rates by roughly 0.13 per additional nat of information budget.
A pre-specified ISR=1 abstention rule can hold hallucination to near-zero at moderate abstention rates, making the threshold an ex-ante operating point rather than a tuned hyperparameter.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the minimization-over-orderings premise holds for standard transformers, the same EDFL bound should apply to any verifiable binary predicate (unit tests, rubric checks), not just support/refute; that would give a generic safety layer for structured generation.
The O(log n) law suggests that position-sensitivity will grow only slowly with context length, but the constant b may differ by pretraining objective; comparing b across next-token vs. permutation-robust training objectives would test whether the law is universal or architecture-specific.
A training-time regularizer that penalizes the variance of logits across permutations is proposed; a natural extension is to test whether this regularizer improves the calibration of the ISR gate on long-context tasks.
The paper leans on binary adjudication because the bounds are tightest there; extending EDFL to multi-class via one-vs-rest is mentioned but not evaluated, leaving open whether the same information-budget thresholds transfer.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

You should know: the paper gives a practical, pre-generation abstention rule for binary adjudication and a clean O(log n) bound on permutation dispersion under a harmonic positional-sensitivity assumption. The empirical effort is real. But the headline explanation — that standard transformers minimize expected description length over orderings, making them 'Bayesian in expectation' — is not established by the theorems, and the validation is weaker than it first appears.

What's genuinely new: the QMV bound with explicit constants, the EDFL specialization to Bernoulli events, and the B2T/RoH/ISR planners. The authors are unusually transparent: the ISR=1 threshold is fixed in advance, the audit is pre-specified, and they acknowledge the binary-only scope. The 3,059-item dispersion study and the randomized dose-response are real measurements, and the code/data are pinned.

Where it frays: the central premise is assumed. Theorem 3 shows that an ensemble-within-the-network with tied weights and an averaging head can realize the permutation mixture. That's a non-standard architecture, and Theorem 4 takes the infimum over that convex hull, not over the parameter class of an ordinary decoder. Nothing shows that next-token training of a standard transformer converges to the order-averaged I-projection. Without that, the 'Bayesian in expectation' claim is conditional on a closure that isn't demonstrated. The O(log n) prediction is tested by fitting a slope and intercept; that can't distinguish logarithmic from other monotone curves. The Jensen-gap experiment confirms Jensen's inequality — a mathematical certainty — rather than a model-specific prediction, so it tells you little about whether the architecture actually minimizes the averaged objective. The audit's reference distribution P for the information budget isn't specified, and there are no baseline detectors, though the authors explicitly say they're doing calibration, not benchmarking — fair enough.

The paper is honestly written and the limitations are stated. But the load-bearing claim needs either a training experiment or a clear reframing as a property of a specific closed model family. For a reading group, it's a good sparring partner; I'd send it to peer review with major revision expected.

Referee Report

4 major / 5 minor

Summary. The paper argues that transformers with positional encodings minimize expected conditional description length over orderings, E_π[ℓ(Y|Γ_π(X))], rather than the permutation-invariant ℓ(Y|X), making them 'Bayesian in expectation, not in realization.' It derives a Quantified Martingale Violation (QMV) bound claiming O(log n) permutation-induced dispersion, an Expectation-level Decompression Law (EDFL) for Bernoulli predicates, and operational planners (B2T, RoH, ISR) for answer/abstain decisions. Experiments on 3,059 evidence-grounded QA items report logarithmic dispersion, positive Jensen gains from permutation mixtures, a causal dose-response of hallucination to information budget, and a pre-specified audit in which an analytically fixed ISR=1 gate yields near-0% hallucination with ~24% abstention.

Significance. The intended contribution is substantial: a quantitative, information-theoretic account of why order-sensitive models can appear Bayesian on average yet fail on fixed inputs, together with deployable abstention rules. The EDFL lower bound and the QMV upper bound, where proved, are clean and potentially useful. The pre-specified audit is a genuine strength, as is the use of external observables (ground-truth likelihood, accuracy, hallucination rates) rather than the proposed metrics themselves for validation. However, the central explanatory claim — that standard transformers minimize the order-averaged objective — is not established, and the operational gate appears to rely on reversing a necessary-condition inequality. If these gaps can be repaired, the framework would be an important step; as it stands, the paper offers a set of interesting bounds and empirical regularities rather than the resolution claimed in the abstract.

major comments (4)

[Section 3.3, Theorems 3–4] The paper's central premise — that standard transformers minimize E_π[ℓ(Y|Γ_π(X))] over orderings — is not derived. Theorem 3 constructs a tied-weight multi-branch ensemble with a linear averaging head and shows only that this non-standard architecture can realize permutation mixtures. Theorem 4 takes the infimum over the convex hull of such mixtures, not over the parameter class of an ordinary decoder-only transformer. No training theorem shows that gradient-based next-token training converges to the order-averaged I-projection, and no training experiment tests the premise. Without this, the claim that hallucinations are predictable compression failures lacks its stated mechanism. The authors should either prove the minimization claim under explicit assumptions, or reframe the contribution as a conditional framework and validate the premise empirically.
[Section 3.2, Theorem 1] Theorem 1, the general QMV bound under Assumption 1, is stated without proof. Appendix A.2 proves only Theorem 2, which relies on the stronger Assumption 2. Since Theorem 1 is the foundational result behind the O(log n) scaling claim, a proof (or a precise proof sketch with all steps) is required. In particular, the step from coordinate total variation to the expectation over pairs of random permutations needs justification; the constant 1/4 and the handling of the sum of coordinate variations are not self-evident.
[Appendix A.1, Lemma 3] Lemma 3 states E[HD] = H_n - 3/2 + O(1/n), but a direct calculation for D=|U-V| with U,V i.i.d. uniform on {1,...,n} gives E[H_D] = H_n - 3/2 + (H_n + 1/2)/n - 1/n^2 = H_n - 3/2 + O((log n)/n). The stated O(1/n) is therefore incorrect. This does not change the leading log n behavior in Theorem 2, but the claimed 'explicit constants' and o(1) term need correction. Please also define HD/H_D explicitly, as the notation is ambiguous.
[Section 3.4 and Box 1 (B2T/RoH/ISR)] EDFL as stated is a lower bound: for any event A with posterior mass p and prior mass \bar q, the expected budget satisfies \bar\Delta \ge KL(Ber(p)||Ber(\bar q)). This is a necessary condition on the budget needed for a given reliability level. The operational planners, however, treat the inequality as if exceeding the lower bound were sufficient: ISR ≥ 1 is used as a license to answer, and Box 2 reports a 'maximum achievable success' at a given budget. No theorem establishes that a model whose budget exceeds KL(Ber(p)||Ber(\bar q)) can actually achieve reliability p; the I-projection P* is a constructed distribution, not the model's predictive distribution. The audit results may still be a useful calibration check, but they do not follow from EDFL alone. Please either provide a sufficiency guarantee under additional assumptions or explicitly downgrade the planners to heuristics.

minor comments (5)

[Appendix A.6] The statement K_U(y|Γ_π(x)) = L_θ(y|Γ_π(x)) + O(1) is not the coding theorem. The coding theorem relates Kolmogorov complexity to a universal prefix code, not to the log-loss of an arbitrary trained model. This section needs substantial qualification or removal.
[Appendix D] The text says 'content is held fixed across dose arms' but the design varies the number of support vs. non-support chunks. Please clarify what is held fixed (question, evidence pool, prompt length) and discuss the potential direct effect of dose on answerability, which the IV strategy does not automatically exclude.
[Appendix A.1] The notation E[HD] is undefined; it should be E[H_D] where H_D = ∑_{t=1}^{D} 1/t. The current text is confusing.
[Throughout] Model names are inconsistent: 'Qwen2-7B' vs 'Qwen-2-7B-Instruct', 'Llama-3.1-8B' vs 'Llama-3.1-8B-Instruct'. Please standardize.
[Table 1, Section 4.1.1] The claim that a fitted line a + b ln n 'confirms Theorem 1' is overstrong: Theorem 1 gives an upper bound, not an equality, and the Llama R² of 0.515 leaves substantial unexplained variance. Please soften the language and report the comparison of the fitted slope to the theoretical constant rather than only the fit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: core derivations are deductive and empirical validations use external observables.

full rationale

The paper's central derivations are not circular. The QMV bound (Theorems 1–2) follows from Assumptions 1–2 via symmetrization, the logistic Lipschitz lemma, and a harmonic-distance identity; it does not assume the O(log n) conclusion. EDFL (Theorem 5) is a direct consequence of Jensen's inequality and the data-processing inequality for KL divergence, with no fitted parameters or hidden re-use of the target result. The B2T/RoH/ISR planners are algebraic transformations of the EDFL lower bound, and the ISR=1 threshold is fixed analytically before the audit, not tuned on the held-out data. The empirical validations (mixture Jensen gain on ground-truth labels, a+b ln n dispersion scaling, randomized dose-response) are observables not defined by the planners, as the paper explicitly states in Appendix B.1 and Appendix G; the reported 3.8% boundary misalignment would be impossible under a tautological metric. The main weakness is that the thesis that standard transformers minimize Eπ[ℓ(Y|Γπ(X))] is not proven from the next-token objective: Theorem 3 provides only a conditional construction using a non-standard tied-weight averaging head, and Theorem 4's infimum is taken over the convex hull of permutation mixtures, not the standard decoder parameter class. This is a load-bearing but unsupported premise—a correctness/validity risk, not circularity. No equation in the paper reduces a prediction to its input, and no fitted parameter is relabeled as a prediction. Therefore, under the strict circularity criteria, the paper contains no significant circular step.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central theory rests on structural assumptions about model behavior (local rank stability, additive positional logits) and on an unproved premise that standard training minimizes the permutation-averaged loss. The empirical dispersion law is fitted, not predicted with constants, and the audit requires a reference distribution P that is not specified for deployment. No new physical or ontological entities are introduced; B2T/RoH/ISR are derived metrics, not postulated entities.

free parameters (4)

log-dispersion slope b = Qwen2-7B: 0.377 [0.319,0.435]; Llama-3.1-8B: 0.147 [0.109,0.184]
Fitted to mean absolute residual vs ln n over 3,059 items; theory gives O(log n) form but no constant, so the empirical confirmation is a two-parameter fit.
log-dispersion intercept a = not reported explicitly
Fitted intercept in the a + b ln n model; carries the constant offset not predicted by theory.
clipping budget B = 6.0 nats
Chosen by hand before the audit; sensitivity checked over 4, 6, 8 nats; not derived from theory.
number of permutations m = 6 (audit), 12/16 (dispersion experiments)
Chosen for compute; sensitivity analysis shows robustness; acts as a hyperparameter in the gate.

assumptions (6)

standard math Jensen's inequality and KL convexity
Used for EDFL Theorem 5 and for the Jensen gap positivity.
standard math Data processing inequality for KL divergence
Used to reduce KL(P||Sbar) to KL(Ber(p)||Ber(qbar)).
domain assumption Assumption 1: local rank stability with bounded total variation
Bounds coordinate-wise adjacent increments of logit(q_pi); not verified on real model logits.
ad hoc to paper Assumption 2: first-order positional sensitivity logit(q_pi)=a(x)+sum w_i psi(pos)
Assumed to make the O(log n) bound explicit; not tested on the models used in the experiments.
ad hoc to paper Architectural closure / I-projection realizability
Theorem 3 constructs an averaging-head ensemble, but standard transformers are not shown to contain it, and the claim that transformers minimize E_pi depends on this.
ad hoc to paper Reference distribution P for the budget estimator
The audit computes Delta using a reference P that is not specified for deployment; if P is the gold label, the gate is not deployable as described.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Predictable Compression Failures: Order Sensitivity and Information Budgeting for Evidence-Grounded Binary Adjudication." pith.science (2026). https://pith.science/paper/TQXWJUBR

@misc{pith2026250911208,
  author       = {Pith},
  title        = {Pith review of: Predictable Compression Failures: Order Sensitivity and Information Budgeting for Evidence-Grounded Binary Adjudication},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TQXWJUBR}},
  note         = {Machine review of arXiv:2509.11208}
}

abstract

Transformers used for evidence-grounded binary adjudication (e.g., support/refute, yes/no, or verifier-backed pass/fail decisions) can be sensitive to the order in which exchangeable evidence is presented, producing dispersion across permutations and unreliable attempted answers under a verifier-relative Bernoulli predicate. We treat evidence order as a nuisance variable and formalize an expectation-realization gap: next-token training can minimize expected conditional description length over orderings while a fixed ordering remains position-sensitive. Our Quantified Martingale Violation (QMV) bound predicts the dispersion induced by adjacent-rank positional sensitivity, with $O(\log n)$ growth in the harmonic regime; our Expectation-level Decompression Law (EDFL) specializes a KL convexity/data-processing bound to Bernoulli predicates, yielding Bits-to-Trust (B2T), Risk-of-Hallucination (RoH), and an Information Sufficiency Ratio (ISR) gate for answer/abstain decisions. On 3,059 grounded items from FEVER, HotpotQA, NQ-Open, PopQA, and Controls, we observe logarithmic dispersion and positive Jensen gains from uniform permutation mixtures. In one pre-specified held-out audit (528 items), the analytically fixed ISR$=1$ gate attains 0.0-0.7% hallucination with 20.6-27.9% abstention (95% CIs), supporting the operating point without claiming universal calibration across all model families or unrestricted generation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 3 linked inside Pith

[1]

An explanation of in-context learning as implicit bayesian inference

Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations, 2022

2022
[2]

Trained transformers learn linear models in-context

Ruiqi Zhang, Simon Spencer, Dean Wagner, et al. Trained transformers learn linear models in-context. Journal of Machine Learning Research, 2023

2023
[3]

Transformers as statisticians: Provable in-context learning with in-context algorithm selection

Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. In Neural Information Processing Systems, 2023

2023
[4]

Martingale property violations in large language models

Fabian Falck, Ziyu Zhang, Samuel Amos, et al. Martingale property violations in large language models. In International Conference on Machine Learning, 2024

2024
[5]

Language modeling is compression

Gr \'e goire Del \'e tang, Anian Ruoss, Paul-Ambroise Duquenne, et al. Language modeling is compression. arXiv preprint arXiv:2309.10668, 2023

arXiv 2023
[6]

Calibrated language models must hallucinate

Adam Tauman Kalai and Santosh S Vempala. Calibrated language models must hallucinate. arXiv preprint arXiv:2311.14648, 2024

arXiv 2024
[7]

Detecting hallucinations in large language models using semantic entropy

Sebastian Farquhar, Jannik Kossen, Lorenz Kuhn, and Yarin Gal. Detecting hallucinations in large language models using semantic entropy. Nature, 2024

2024
[8]

Bayesian transformers: Full bayesian inference comparable to mcmc

Tristan Reuter, Clemens Meiler, et al. Bayesian transformers: Full bayesian inference comparable to mcmc. arXiv preprint arXiv:2402.08354, 2024

arXiv 2024

Show all 12 references

[9]

The Minimum Description Length Principle

Peter D Gr \"u nwald. The Minimum Description Length Principle. MIT Press, 2007

2007
[10]

Lost in the middle: How language models use long contexts

Nelson F Liu, Kevin Lin, John Hewitt, et al. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 2024

2024
[11]

Language models as lossy compressors

Jiangjie Su et al. Language models as lossy compressors. In Annual Meeting of the Association for Computational Linguistics, 2024

2024
[12]

Bayesian uncertainty decomposition for hallucination detection

Emmanouil Vasilatos et al. Bayesian uncertainty decomposition for hallucination detection. In International Conference on Machine Learning, 2024

2024

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

An explanation of in-context learning as implicit bayesian inference

Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations, 2022

2022

[2] [2]

Trained transformers learn linear models in-context

Ruiqi Zhang, Simon Spencer, Dean Wagner, et al. Trained transformers learn linear models in-context. Journal of Machine Learning Research, 2023

2023

[3] [3]

Transformers as statisticians: Provable in-context learning with in-context algorithm selection

Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. In Neural Information Processing Systems, 2023

2023

[4] [4]

Martingale property violations in large language models

Fabian Falck, Ziyu Zhang, Samuel Amos, et al. Martingale property violations in large language models. In International Conference on Machine Learning, 2024

2024

[5] [5]

Language modeling is compression

Gr \'e goire Del \'e tang, Anian Ruoss, Paul-Ambroise Duquenne, et al. Language modeling is compression. arXiv preprint arXiv:2309.10668, 2023

arXiv 2023

[6] [6]

Calibrated language models must hallucinate

Adam Tauman Kalai and Santosh S Vempala. Calibrated language models must hallucinate. arXiv preprint arXiv:2311.14648, 2024

arXiv 2024

[7] [7]

Detecting hallucinations in large language models using semantic entropy

Sebastian Farquhar, Jannik Kossen, Lorenz Kuhn, and Yarin Gal. Detecting hallucinations in large language models using semantic entropy. Nature, 2024

2024

[8] [8]

Bayesian transformers: Full bayesian inference comparable to mcmc

Tristan Reuter, Clemens Meiler, et al. Bayesian transformers: Full bayesian inference comparable to mcmc. arXiv preprint arXiv:2402.08354, 2024

arXiv 2024