mlsanityData to 14 Oct 2026

Polynomial Context-Truncation Sensitivity in Autoregressive Language Models: Sequential Wyner-Ziv Bounds for KV Cache Compression

arXiv 2605.25085 ↗First posted 24 May 2026cs.IT cs.AI cs.LGcited by 0

On the map: Efficient LLM inference and serving → KV cache optimization

Abstract (arXiv)

We study the rate-distortion limits of online KV cache compression in autoregressive language models, formulating it as sequential Wyner-Ziv source coding on the filtration induced by the model, with the next-step query as decoder side information. Empirically, across four models spanning two families and 0.5-3B parameters, we find that the next-token distribution's sensitivity to context truncation decays polynomially rather than geometrically: a power law improves on an exponential fit by an order of magnitude in extrapolation, the fitted exponent is recovered independently from a sink-plus-recent KL measurement, and the decay is verified to be free of positional-encoding artifacts by a position-preserving ablation. Under a corresponding polynomial truncation-sensitivity assumption, our main result characterizes the per-token memory requirement of suffix-only cache policies: a sliding-window scheme attains distortion varepsilon with window w = O(varepsilon-1/α), and -- under an additional two-sided Bayes-risk condition -- a converse shows w = Omega(varepsilon-1/α) is necessary within this policy class, so the scaling is Theta(varepsilon-1/α) for suffix-only policies. Whether recurrent or propagating cache summaries can beat this scaling is left open. An explicit block-Markov scheme achieves the upper bound; its rate-of-convergence exponent matches the converse under additional forward-decay and regularity hypotheses (not implied by truncation sensitivity alone), and differs by a factor of two otherwise. Empirically, the polynomial law predicts the degradation curves of concrete cache policies: recency-based eviction (sliding, sink-plus-recent) suppresses distortion by roughly two orders of magnitude over random retention at equal budget, with a power-law decay in the budget.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 23 of its 61 references that are in the map. First posted on arXiv 24 May 2026.

Builds on

23 of 61 references.

Closest ancestors · 7

Same direction, newest first

  1. 2024Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference16 Jul
  2. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference16 Jun
  3. 2024PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling4 Jun
  4. 2024SnapKV: LLM Knows What You are Looking for Before Generation22 Apr
  5. 2024GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM8 Mar
  6. 2023Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs3 Oct
  7. 2023Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time26 May

Other references · 16

  1. 2017Attention Is All You Needcited by 60,361
  2. 2024The Llama 3 Herd of Modelscited by 14,715
  3. 2020Scaling Laws for Neural Language Modelscited by 6,586
  4. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  5. 2023GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpointscited by 1,346
  6. 2020Transformer Feed-Forward Layers Are Key-Value Memoriescited by 1,336
  7. 2024DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Modelcited by 1,135
  8. 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 717
  9. 2024KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cachecited by 637
  10. 2021Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depthcited by 419
  11. 2025SmolLM2: When Smol Goes Big -- Data-Centric Training of a Small Language Modelcited by 335
  12. 2021The Intrinsic Dimension of Images and Its Impact on Learningcited by 315
4 more
  1. 2019Intrinsic dimension of data representations in deep neural networkscited by 282
  2. 2020The Lipschitz Constant of Self-Attentioncited by 174
  3. 2023A mathematical perspective on Transformerscited by 164
  4. 2021Lipschitz Normalization for Self-Attention Layers with Application to Graph Neural Networkscited by 39

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024More Tokens, Lower Precision: Towards the Optimal Token-Precision Trade-off in KV Cache Compression
  2. 2025H1B-KV: Hybrid One-Bit Caches for Memory-Efficient Large Language Model Inference
  3. 2026KV-CoRE: Benchmarking Data-Dependent Low-Rank Compressibility of KV-Caches in LLMs
  4. 2026A JoLT for the KV cache: Near-Lossless KV Cache Compression via Joint Rank-bit Allocation
  5. 2024ZigZagkv: Dynamic KV Cache Compression for Long-context Modeling based on Layer Uncertainty
  6. 2026RDKV: Rate-Distortion Bit Allocation for Joint Eviction and Quantization of the KV Cache
  7. 2025Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores
  8. 2025PackKV: Reducing KV Cache Memory Footprint through LLM-Aware Lossy Compression