Reproduce “The risk of KV cache compression” on OpenResearch

About this paper

Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno, Sebastian Trimpe, Marco Pavone

A theoretical framework for KV cache compression in Transformers is introduced, formalizing it as a sparse measure approximation and characterizing its minimax risk. This work provides sharp bounds distinguishing query-aware and query-agnostic compression, informing algorithms that achieve 95% KV cache reduction on Qwen3-32B while maintaining accuracy comparable to uncompressed baselines on long-context benchmarks.

Key insights

• The intrinsic compressibility of a KV cache can be characterized by the spectral decay of its covariance operator, which captures the geometry of query-visible variation.
• Query-aware compression (with knowledge of future queries) achieves error rates proportional to the spectral tail of the covariance operator, offering a significant advantage over query-agnostic methods.
• Minimax lower bounds confirm a sharp separation between query-aware and query-agnostic compression, illustrating the inherent cost of uncertainty about future query distributions.

Summary by alphaXiv.