pith. sign in

arxiv: 2607.01520 · v1 · pith:QVY37H2Snew · submitted 2026-07-01 · 💻 cs.LG

The risk of KV cache compression

Lukas Haverbeck , Carmen Amo Alonso , Andres Felipe Posada-Moreno , Sebastian Trimpe , Marco Pavone This is my paper

Pith reviewed 2026-07-03 20:51 UTC · model grok-4.3

classification 💻 cs.LG
keywords KV cache compressionminimax risktransformer inferencecausal maskinglong sequencesattention mechanismsprefill decoding
0
0 comments X

The pith

The minimax risk of KV cache compression is governed by the intrinsic compressibility of the cache.

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

The paper characterizes the minimax risk of replacing a full KV cache with a compact summary in transformer models. It shows that accurate compression is possible precisely when the cache possesses sufficient intrinsic compressibility, and derives design principles that achieve this optimal risk under causal masking. These principles translate directly into algorithms for the prefill and autoregressive decoding stages. A sympathetic reader would care because the work replaces empirical trial-and-error with theoretical guidance for making long-sequence inference cheaper without sacrificing accuracy.

Core claim

We characterize the minimax risk of KV cache compression in terms of the intrinsic compressibility of a cache, revealing when and how accurate compression is possible. These results yield novel design principles for KV cache compression under causal masking that map efficiently to prefill and autoregressive decoding while achieving minimax-optimal risk. We instantiate these principles in a practical algorithm and report promising performance on LongBench in targeted experiments.

What carries the argument

The minimax risk of KV cache compression expressed as a function of the intrinsic compressibility of the cache.

Load-bearing premise

That the intrinsic compressibility of a given KV cache can be identified or bounded in a way that directly informs practical algorithm design and that the theoretical results transfer to real prefill and autoregressive decoding.

What would settle it

A concrete KV cache and compression scheme following the derived design principles whose observed risk exceeds the minimax bound predicted from the cache's measured compressibility.

Figures

Figures reproduced from arXiv: 2607.01520 by Andres Felipe Posada-Moreno, Carmen Amo Alonso, Lukas Haverbeck, Marco Pavone, Sebastian Trimpe.

Figure 1
Figure 1. Figure 1: Illustration of our approach. Left: We view the token sequence as a measure P over key– value pairs (k, v) ∈ X , which we map to their response profiles ΓP (k, v) ∈ Hν. Right: Compressing P amounts to a sparse reweighting of tokens, which moves the barycenter of the response profiles. The size of this displacement depends on the retained tokens and their assigned weights, and controls the attention error i… view at source ↗
read the original abstract

Transformer inference on long sequences is expensive because softmax attention repeatedly reads from a large KV cache. The prevalent approach to this bottleneck is KV cache compression, which replaces the full cache with a compact summary. Despite its practical importance, the design of such summaries is largely driven by empirical experimentation. On the theoretical side, existing results show that KV cache compression can be impossible in the worst case, but offer little systematic guidance for designing algorithms in regimes where accurate compression is possible. We bridge this gap by characterizing the minimax risk of KV cache compression in terms of the intrinsic compressibility of a cache, revealing when and how accurate compression is possible. These results yield novel design principles for KV cache compression under causal masking that map efficiently to prefill and autoregressive decoding while achieving minimax-optimal risk. We instantiate these principles in a practical algorithm and report promising performance on LongBench in targeted experiments. Overall, our results provide a principled avenue for practical KV cache compression with theoretical guarantees.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims to characterize the minimax risk of KV cache compression in terms of the intrinsic compressibility of a given cache. This characterization is used to derive novel design principles for compression under causal masking; the principles are asserted to map efficiently to prefill and autoregressive decoding phases while attaining minimax-optimal risk. The principles are instantiated in a practical algorithm whose performance is reported as promising on LongBench.

Significance. If the central characterization and the transfer to causal-masking design principles hold with the claimed optimality, the work supplies the first systematic theoretical guidance for when and how KV cache compression can be accurate, moving the field beyond purely empirical heuristics. The explicit linkage of minimax risk to intrinsic compressibility and the attempt to produce practical, optimality-preserving algorithms constitute the primary contribution.

major comments (2)
  1. [Design principles section (following the minimax characterization)] The central claim that the derived design principles achieve minimax-optimal risk under causal masking rests on an unstated identification procedure for the intrinsic compressibility of a concrete KV cache. No explicit construction or bound is supplied showing how this quantity is computed from attention scores or sequence statistics, nor how the resulting principles avoid approximation gaps when instantiated (see the skeptic note on transfer assumptions).
  2. [Experimental evaluation] Table or figure reporting LongBench results: the experiments are described only as 'promising' and contain no verification that the practical algorithm meets or approaches the derived minimax risk bound for the tested caches. This leaves open whether optimality is retained or whether a weaker empirical criterion is satisfied.
minor comments (1)
  1. Notation for the compressibility measure and the minimax risk functional could be introduced with a short table of symbols to aid readability for readers outside the immediate sub-area.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive review. The comments identify key areas where the manuscript can be strengthened by clarifying the practical computation of intrinsic compressibility and by better linking experiments to the theoretical bounds. We address each major comment below and indicate the corresponding revisions.

read point-by-point responses

  1. Referee: [Design principles section (following the minimax characterization)] The central claim that the derived design principles achieve minimax-optimal risk under causal masking rests on an unstated identification procedure for the intrinsic compressibility of a concrete KV cache. No explicit construction or bound is supplied showing how this quantity is computed from attention scores or sequence statistics, nor how the resulting principles avoid approximation gaps when instantiated (see the skeptic note on transfer assumptions).

    Authors: We agree that an explicit procedure for identifying or estimating intrinsic compressibility from attention scores or sequence statistics is not provided in the current manuscript. The characterization is stated in terms of this abstract quantity, and the design principles follow from it, but we did not include a concrete identification method or analysis of approximation gaps under causal masking. We will add a new subsection in the design principles section that discusses estimation approaches (e.g., via attention score thresholding or sequence statistics) and explicitly addresses transfer assumptions and potential gaps between the theoretical quantity and its practical instantiation. revision: yes

  2. Referee: [Experimental evaluation] Table or figure reporting LongBench results: the experiments are described only as 'promising' and contain no verification that the practical algorithm meets or approaches the derived minimax risk bound for the tested caches. This leaves open whether optimality is retained or whether a weaker empirical criterion is satisfied.

    Authors: The LongBench experiments demonstrate practical utility rather than direct numerical verification against the minimax bound, as exact computation of the information-theoretic minimax risk for real-world caches is intractable. We acknowledge that this leaves the optimality claim partially unverified in the empirical setting. We will revise the experimental section to include a dedicated discussion of the relationship between observed performance and the theoretical bound, add synthetic experiments where the bound can be computed exactly, and qualify the claims accordingly. revision: partial

Circularity Check

0 steps flagged

No circularity: theoretical characterization stands independently of inputs

full rationale

The provided abstract and description present a theoretical characterization of minimax risk for KV cache compression expressed in terms of intrinsic compressibility, followed by derivation of design principles. No equations, fitting procedures, self-citations, or reductions to inputs by construction are visible. The mapping to prefill/autoregressive decoding is stated as a consequence of the characterization rather than a redefinition of the same quantity. This is the common case of a self-contained theoretical contribution with no detectable circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the central claim rests on the unelaborated notion of 'intrinsic compressibility' whose operational definition is not visible.

pith-pipeline@v0.9.1-grok · 5702 in / 1073 out tokens · 17790 ms · 2026-07-03T20:51:52.556883+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 2 internal anchors

  1. [1]

    Keyformer: KV cache reduction through key tokens selection for efficient generative inference.Proceedings of Machine Learning and Systems, 6:114–127, 2024

    Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant J Nair, Ilya Soloveychik, and Purushotham Kamath. Keyformer: KV cache reduction through key tokens selection for efficient generative inference.Proceedings of Machine Learning and Systems, 6:114–127, 2024

    work page 2024

  2. [2]

    Support basis: Fast attention beyond bounded entries

    Maryam Aliakbarpour, Vladimir Braverman, Junze Yin, and Haochen Zhang. Support basis: Fast attention beyond bounded entries. InProceedings of the 29th International Conference on Artificial Intelligence and Statistics, 2026

    work page 2026

  3. [3]

    Fast attention requires bounded entries.Advances in Neural Information Processing Systems, 36:63117–63135, 2023

    Josh Alman and Zhao Song. Fast attention requires bounded entries.Advances in Neural Information Processing Systems, 36:63117–63135, 2023

    work page 2023

  4. [4]

    Effective gene expression prediction from sequence by integrating long-range interactions

    Žiga Avsec, Vikram Agarwal, Daniel Visentin, Joseph R Ledsam, Agnieszka Grabska- Barwinska, Kyle R Taylor, Yannis Assael, John Jumper, Pushmeet Kohli, and David R Kelley. Effective gene expression prediction from sequence by integrating long-range interactions. Nature Methods, 18(10):1196–1203, 2021

    work page 2021

  5. [5]

    wav2vec 2.0: A frame- work for self-supervised learning of speech representations.Advances in Neural Information Processing Systems, 33:12449–12460, 2020

    Alexei Baevski, Henry Zhou, Abdelrahman Mohamed, and Michael Auli. wav2vec 2.0: A frame- work for self-supervised learning of speech representations.Advances in Neural Information Processing Systems, 33:12449–12460, 2020

    work page 2020

  6. [6]

    LongBench v2: Towards deeper understanding and reason- ing on realistic long-context multitasks

    Yushi Bai, Shangqing Tu, Jiajie Zhang, Hao Peng, Xiaozhi Wang, Xin Lv, Shulin Cao, Jiazheng Xu, Lei Hou, Yuxiao Dong, et al. LongBench v2: Towards deeper understanding and reason- ing on realistic long-context multitasks. InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3639–3664, 2025

    work page 2025

  7. [7]

    On a generalization of iterated and randomized rounding.Theory of Computing, 20(6):1–23, 2024

    Nikhil Bansal. On a generalization of iterated and randomized rounding.Theory of Computing, 20(6):1–23, 2024

    work page 2024

  8. [8]

    Language models are few-shot learners.Advances in Neural Information Processing Systems, 33:1877–1901, 2020

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners.Advances in Neural Information Processing Systems, 33:1877–1901, 2020

    work page 1901

  9. [9]

    Martin Burger, Samira Kabri, Yury Korolev, Tim Roith, and Lukas Weigand. Analysis of mean-field models arising from self-attention dynamics in transformer architectures with layer normalization.Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 383(2298), 2025

    work page 2025

  10. [10]

    PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling

    Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Yucheng Li, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Junjie Hu, et al. PyramidKV: Dynamic KV cache compression based on pyramidal information funneling.arXiv preprint arXiv:2406.02069, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  11. [11]

    Low-rank thinning

    Annabelle Michael Carrell, Albert Gong, Abhishek Shetty, Raaz Dwivedi, and Lester Mackey. Low-rank thinning. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste- Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors,Proceed- ings of the 42nd International Conference on Machine Learning, volume 267 ofProceed- ings of Machine Le...

    work page 2025

  12. [12]

    Super-samples from kernel herding

    Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding. InProceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, pages 109–116, 2010

    work page 2010

  13. [13]

    Transformer-xl: Attentive language models beyond a fixed-length context

    Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. InProceedings of the 57th annual meeting of the association for computational linguistics, pages 2978–2988, 2019

    work page 2019

  14. [14]

    BERT: Pre-training of deep bidirectional transformers for language understanding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. InProceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers), pages 4171–4186, 2019. 11

    work page 2019

  15. [15]

    A mathematical perspective on transformers.Bulletin of the American Mathematical Society, 62(3):427–479, 2025

    Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. A mathematical perspective on transformers.Bulletin of the American Mathematical Society, 62(3):427–479, 2025

    work page 2025

  16. [16]

    Compression barriers for autoregressive transformers

    Themistoklis Haris and Krzysztof Onak. Compression barriers for autoregressive transformers. arXiv preprint arXiv:2502.15955, 2025

    work page arXiv 2025

  17. [17]

    Revisiting frank-wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. InInterna- tional conference on machine learning, pages 427–435. PMLR, 2013

    work page 2013

  18. [18]

    Stream- ing attention approximation via discrepancy theory.arXiv preprint arXiv:2502.07861, 2025

    Ekaterina Kochetkova, Kshiteej Sheth, Insu Han, Amir Zandieh, and Michael Kapralov. Stream- ing attention approximation via discrepancy theory.arXiv preprint arXiv:2502.07861, 2025

    work page arXiv 2025

  19. [19]

    SnapKV: LLM knows what you are looking for before generation.Advances in Neural Information Processing Systems, 37:22947–22970, 2024

    Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. SnapKV: LLM knows what you are looking for before generation.Advances in Neural Information Processing Systems, 37:22947–22970, 2024

    work page 2024

  20. [20]

    ScissorHands: Exploiting the persistence of importance hypothesis for LLM KV cache compression at test time.Advances in Neural Information Processing Systems, 36:52342–52364, 2023

    Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. ScissorHands: Exploiting the persistence of importance hypothesis for LLM KV cache compression at test time.Advances in Neural Information Processing Systems, 36:52342–52364, 2023

    work page 2023

  21. [21]

    YaRN: Efficient context window extension of large language models

    Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. YaRN: Efficient context window extension of large language models. In B. Kim, Y . Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y . Sun, editors,International Conference on Learning Representations, volume 2024, pages 31932–31951, 2024. URL https://proceedings.iclr.cc/paper_files/ paper/202...

    work page 2024

  22. [22]

    Alexander Rives, Joshua Meier, Tom Sercu, Siddharth Goyal, Zeming Lin, Jason Liu, Demi Guo, Myle Ott, C Lawrence Zitnick, Jerry Ma, et al. Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences.Proceedings of the National Academy of Sciences, 118(15):e2016239118, 2021

    work page 2021

  23. [23]

    Attention is all you need.Advances in Neural Information Processing Systems, 30, 2017

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need.Advances in Neural Information Processing Systems, 30, 2017

    work page 2017

  24. [24]

    Efficient streaming language models with attention sinks

    Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In B. Kim, Y . Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y . Sun, editors,International Conference on Learning Representations, volume 2024, pages 21875–21895, 2024. URL https://proceedings.iclr.cc/paper_files/ paper/2024/fi...

    work page 2024

  25. [25]

    Qwen3 Technical Report

    An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report.arXiv preprint arXiv:2505.09388, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  26. [26]

    SubGen: Token generation in sublinear time and memory.arXiv preprint arXiv:2402.06082, 2024

    Amir Zandieh, Insu Han, Vahab Mirrokni, and Amin Karbasi. SubGen: Token generation in sublinear time and memory.arXiv preprint arXiv:2402.06082, 2024

    work page arXiv 2024

  27. [27]

    alive set

    Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2O: Heavy-hitter oracle for efficient generative inference of large language models.Advances in Neural Information Processing Systems, 36:34661–34710, 2023. 12 Appendix Contents A Sparse barycenter balancing in H...

    work page 2023