Technical Summary: Predictable Compression Failures

1. Problem Statement

The paper addresses a critical reliability issue in evidence-grounded binary adjudication using Transformer models. In tasks such as support/refute classification, yes/no decisions, or verifier-backed pass/fail judgments, the model's output is often sensitive to the order in which exchangeable evidence chunks are presented.

While the evidence set is theoretically exchangeable (reordering should not change the truth value), Transformers with positional encodings produce varying probabilities ($q_\pi$) for different permutations ($\pi$) of the same evidence. This "order sensitivity" creates a dispersion in predictions, leading to unreliable answers or inconsistent abstention rates. The authors argue that next-token training minimizes expected conditional description length over orderings, allowing a model to be Bayes-optimal on average while deviating significantly from a permutation-invariant predictor at any fixed ordering. This gap between expectation (average over orderings) and realization (fixed ordering) constitutes a "predictable compression failure."

2. Methodology and Theoretical Framework

The paper formalizes this phenomenon through two primary theoretical lenses: Quantified Martingale Violations (QMV) and the Expectation-level Decompression Law (EDFL).

2.1 Quantified Martingale Violations (QMV)

The authors treat evidence order as a nuisance variable and model the dispersion induced by positional sensitivity.

• Assumption: The logit of the Bernoulli prediction exhibits local adjacent-rank sensitivity with a specific decay profile (e.g., harmonic decay where sensitivity $\propto t^{-\alpha}$).
• Theorem 1 & 2: Under these assumptions, the expected absolute dispersion ($E_\pi |R_\pi|$) is bounded by the cumulative sensitivity of the logit to rank changes.
  • If decay is harmonic ($\alpha=1$), dispersion grows as $O(\log n)$.
  • If decay is slower ($\alpha < 1$), it grows polynomially ($O(n^{1-\alpha})$).
  • If decay is faster ($\alpha > 1$), dispersion is bounded ($O(1)$).
• Proposition 2: Provides an assumption-free certificate using the Jensen-Shannon Divergence (JSD) to bound dispersion via Pinsker's inequality.

2.2 Expectation-level Decompression Law (EDFL)

EDFL translates the theoretical bounds into actionable deployment metrics for binary adjudication. It specializes a KL convexity and data-processing bound to Bernoulli predicates.

• Core Concept: It establishes the minimum information budget ($\bar{\Delta}$) required to shift a probability from a prior mass ($\bar{q}$) to a target posterior mass ($p$).
• Rare Event Scaling: For rare events, the required budget scales as $\log(1/\bar{q})$.
• Operational Planners: EDFL yields closed-form metrics:
  • Bits-to-Trust (B2T): The minimum information budget needed to trust an answer at a target reliability $p^\star = 1 - h^\star$. Calculated as $KL(Ber(p^\star) \| Ber(q_{lo}))$, where $q_{lo}$ is the conservative lower bound of the permutation mixture.
  • Risk-of-Hallucination (RoH): The residual risk implied by the measured budget.
  • Information Sufficiency Ratio (ISR): The ratio of available budget to required budget ($\bar{\Delta} / B2T$).

2.3 Deployment Mechanism

The authors propose a fixed ISR gating rule (Algorithm 1):

• Decision Rule: Answer if $ISR \ge 1$; otherwise, abstain or acquire more evidence.
• Implementation: This involves sampling $m$ permutations of the evidence, computing the model's probability for each, calculating the average budget $\bar{\Delta}$ (via KL divergence), and comparing it against the B2T threshold.
• Reference Distribution: The method requires a reference distribution $P_{ref}$ for the predicate $g$. This can be instantiated via deterministic oracles (e.g., database lookups, unit tests), gold labels in evaluation, or calibrated verifiers.

3. Key Contributions

1. Quantified Order Sensitivity: The paper proves a QMV bound showing that permutation-induced dispersion follows an $O(\log n)$ scaling under harmonic positional sensitivity, providing explicit constants for this growth.
2. EDFL as an Actionable Specialization: It derives the Expectation-level Decompression Law, converting abstract convexity bounds into closed-form planners (B2T, RoH, ISR) and a fixed, auditable $ISR=1$ decision boundary.
3. Deployable Answer/Abstain Interface: The authors define a practical procedure (Algorithm 1) that uses permutation mixtures to estimate information sufficiency, allowing models to reject answers when the information budget is insufficient to guarantee a target reliability.

4. Empirical Validation

The theory was validated across 3,059 grounded items from FEVER, HotpotQA, NQ-Open, PopQA, and a custom Controls benchmark, using Qwen2-7B and Llama3.1-8B.

• Dispersion Scaling (Experiment 1):

  • Observed that mean absolute residuals follow the predicted $a + b \log n$ scaling law.
  • Qwen2-7B showed a dispersion slope ($b \approx 0.377$) significantly higher than Llama3.1-8B ($b \approx 0.147$), indicating stronger positional sensitivity.
  • Uniform permutation mixtures yielded positive Jensen gaps (improvements in cross-entropy), confirming that averaging over orderings reduces loss. The uniform mixture was found to be near-MDL optimal, with optimality gaps $< 10^{-4}$ nats/token.

• Causal Dose-Response (Experiment 2):

  • A randomized study varying the "support dose" (number of supporting evidence chunks) while holding prompt length fixed.
  • Results showed a causal link: increasing support dose decreased the information budget estimate ($\bar{\Delta}$) and reduced hallucination rates. The fitted slope indicated approximately 12.7 fewer hallucinations per additional nat of information budget.

• Held-Out Audit (Experiment 3):

  • A pre-specified audit on 528 held-out items using a Gemma-2-9B fine-tuned model.
  • Using the analytically fixed $ISR=1$ gate (without post-hoc tuning), the system achieved a hallucination rate of 0.0–0.7% with an abstention rate of 20.6–27.9% (95% CIs).
  • This demonstrates the operating point's ability to trade coverage for high reliability without universal calibration claims.

5. Significance and Claims

The paper claims to provide a falsifiable, out-of-sample operating point for evidence-grounded AI. Its significance lies in:

• Reconciling Training and Deployment: It explains why models trained to minimize cross-entropy (expectation) can still fail on specific orderings (realization) and offers a method to bridge this gap.
• Moving Beyond Calibration: Instead of relying on learned confidence thresholds that may not generalize, the ISR gate is derived analytically from information-theoretic principles (KL divergence).
• Verifiable Reliability: The framework is scoped to verifier-relative predicates. The authors explicitly state that their guarantees are relative to a reference distribution induced by a specification, deterministic tool, or calibrated verifier. They do not claim universal calibration for unrestricted generation or models without such verification primitives.

The work positions itself as a "deployment-facing" solution, offering a concrete rule (Answer if $ISR \ge 1$) that allows systems to abstain when the information budget is insufficient to support a target reliability, thereby controlling the risk of hallucination in grounded tasks.