Technical Summary: Polynomial Context-Truncation Sensitivity in Autoregressive Language Models

1. Problem Statement

The paper addresses the theoretical limits of online KV (Key-Value) cache compression in autoregressive language models (LLMs). As context lengths grow, the linear growth of the KV cache becomes a primary bottleneck for inference. While numerous empirical compression schemes exist (e.g., heavy-hitter eviction, sliding windows, attention sinks, quantization), there is a lack of quantitative theoretical bounds on what is achievable for the online compression problem.

The core question is: How much memory (window size) is required to maintain a specific level of distortion (accuracy) in the next-token distribution when compressing the context?

Classical information theory often assumes geometric mixing (or $\rho$-mixing), where the influence of distant past tokens decays exponentially ($C\rho^w$). Under this assumption, a window size of $O(\log(1/\epsilon))$ suffices for $\epsilon$-accuracy. However, this assumption is not derived from the language modeling setup and may not hold for trained LLMs.

2. Methodology and Framework

2.1 Sequential Wyner–Ziv Formulation

The authors formulate KV cache compression as a sequential Wyner–Ziv source coding problem.

• Source: The sequence of tokens $X_{1:t-1}$ generated by the model.
• Encoder: A causal online encoder $\phi_t$ that maps past tokens to a compressed code $\hat{C}_t$.
• Decoder Side Information: The next-step query vector $Q_t$ (computed by the uncompressed model) serves as side information at the decoder.
• Goal: Reconstruct the next-token distribution $\tilde{p}_t$ from $(\hat{C}_{\le t}, Q_t)$ such that the expected KL divergence $E[D_{KL}(p_t \| \tilde{p}_t)]$ is minimized for a given rate.

2.2 Empirical Characterization of Truncation Sensitivity

Instead of assuming geometric mixing, the authors empirically measure the truncation sensitivity of trained models. They define the sensitivity $d_{TV}^w$ as the Total Variation (TV) distance between the full-context next-token distribution and the distribution conditioned only on the most recent $w$ tokens:
$$d_{TV}^w := TV(p_\theta(\cdot | X_{1:t-1}), p_\theta(\cdot | X_{t-w:t-1}))$$

Key Empirical Finding: Across four models (Qwen2.5-0.5B/1.5B/3B, SmolLM2-1.7B) and two domains (Natural Language, Code), the decay of $d_{TV}^w$ follows a power law rather than an exponential decay:
$$d_{TV}^w \propto w^{-\alpha}$$

• Measured exponents: $\alpha_{\text{nat}} \approx 0.44$ (Natural Language) and $\alpha_{\text{code}} \approx 0.38$ (Code).
• Power-law fits significantly outperform exponential fits in extrapolation (log-RMSE improvement of 2–2.5$\times$).
• This property is verified to be free of positional-encoding artifacts via a position-preserving ablation.

3. Key Contributions and Theoretical Results

Based on the empirical observation of $\alpha$-polynomial truncation sensitivity, the paper develops an information-theoretic framework with the following core results:

C1: Sequential Wyner–Ziv Converse (Lower Bound)

The authors establish a fundamental lower bound on the rate required to achieve a target distortion $D$. For any causal online scheme:
$$\liminf_{n \to \infty} E[R_n] \ge R^\star(D)$$
This bound holds without assuming specific mixing conditions, relying only on the structure of the sequential Wyner–Ziv problem.

C2: Window Scaling for Suffix-Only Policies

The paper characterizes the memory requirements for suffix-only policies (schemes where the reconstruction depends only on the most recent $w$ tokens, e.g., sliding windows).

• Upper Bound: A sliding-window scheme achieves TV distortion $\epsilon$ with window size $w = O(\epsilon^{-1/\alpha})$.
• Lower Bound (Converse): Under an additional "two-sided Bayes-risk" condition (Definition 4.4), any suffix-only policy requires $w = \Omega(\epsilon^{-1/\alpha})$.
• Result: The per-token memory requirement for suffix-only policies is tight: $\Theta(\epsilon^{-1/\alpha})$.
  • Contrast with Geometric Mixing: Under geometric mixing, $w = O(\log(1/\epsilon))$. With $\alpha \approx 0.5$, the window size scales polynomially (e.g., $w \sim 10^2$ for $\epsilon=0.01$), explaining why deployed schemes require much larger windows than geometric mixing would predict.

C3: Explicit Achievability Scheme

The authors propose an explicit block-Markov random-coding scheme that achieves the theoretical bounds.

• Window Size: $w_n = \lceil n^{1/(\alpha+1)} \rceil$.
• Convergence: The scheme achieves distortion within $O(n^{-\alpha/(\alpha+1)})$ of the target.
• Rate Convergence:
  • In expectation, the rate converges with exponent $\alpha/(\alpha+1)$.
  • In high probability, the exponent is $\alpha/(2(\alpha+1))$ without further assumptions.
  • Under additional hypotheses (forward covariance decay, additive tilted-information), the high-probability exponent matches the converse ($\alpha/(\alpha+1)$).

C4: Sink-Plus-Recent Eviction Implication

The paper analyzes the popular "sink-plus-recent" eviction strategy (retaining attention sinks + recent tokens).

• Result: Under $\alpha$-polynomial sensitivity, the KL distortion gap decays as $O(k^{-2\alpha})$, where $k$ is the budget.
• Mechanism: The exponent doubling ($2\alpha$ instead of $\alpha$) arises from a local quadratic relationship between KL divergence and TV distance ($KL \le C \cdot TV^2$) in the bounded-floor regime, not from Pinsker's inequality.
• Empirical Validation: Measured KL exponents ($\alpha_{KL} \approx 1.04$ for Natural, $0.74$ for Code) are approximately twice the TV exponents ($0.44$ and $0.38$), confirming the theoretical prediction.

4. Empirical Results

The paper validates the framework on Qwen2.5 (0.5B, 1.5B, 3B) and SmolLM2 (1.7B):

1. Polynomial Decay: Power-law fits for TV decay are superior to exponential fits across all models and domains.
2. Exponent Consistency: The ratio $\alpha_{KL} / \alpha_{TV}$ consistently brackets the predicted factor of 2 (ratios observed: 1.93 to 2.38).
3. Policy Degradation: Recency-based policies (sliding window, sink-plus-recent) suppress distortion by roughly two orders of magnitude compared to random token retention at equal budget.
4. Domain Differences: Natural language exhibits faster truncation sensitivity decay ($\alpha \approx 0.44$) than code ($\alpha \approx 0.38$), suggesting code retains long-range structural dependencies (scopes, imports) more strongly.
5. Robustness: The power law holds up to window sizes of $w=8192$, well beyond the typical 4k deployment range, and is robust to positional encoding artifacts.

5. Significance and Claims

The paper claims the following significance:

• Theoretical Foundation: It provides the first quantitative rate-distortion characterization for KV cache compression based on the empirically observed polynomial truncation sensitivity of LLMs, replacing the unverified geometric mixing assumption.
• Explaining Empirical Practices: The polynomial scaling law ($\Theta(\epsilon^{-1/\alpha})$) explains why deployed systems (e.g., Mistral with $w=4096$, StreamingLLM) require windows significantly larger than geometric mixing would suggest.
• Optimality of Suffix-Only Policies: It establishes that for the class of suffix-only policies, the memory scaling is tight. Whether more complex recurrent or propagating summaries can beat this scaling remains an open problem.
• Validation of "Sink-Plus-Recent": It provides a theoretical justification for the performance of sink-plus-recent eviction, linking the observed $k^{-2\alpha}$ decay to the underlying polynomial sensitivity and the local quadratic KL-TV relation.

Limitations Acknowledged by the Authors:

• The analysis is restricted to models $\le 3B$ parameters due to computational constraints; larger models (7B–8B) are left for future work.
• The "two-sided Bayes-risk" condition and forward-decay hypotheses required for tight high-probability bounds are not implied by truncation sensitivity alone and are treated as additional assumptions.
• The framework assumes standard Transformer architectures; state-space models (e.g., Mamba) are not analyzed.
• The paper does not claim to derive the exponent $\alpha$ from architectural parameters, but rather measures it empirically.

In summary, the paper argues that polynomial context-truncation sensitivity is a fundamental property of trained LLMs that dictates the memory-rate trade-off, necessitating polynomially scaling windows for high-accuracy compression and providing a theoretical basis for the efficacy of recency-based eviction strategies.