The risk of KV cache compression
For practitioners of transformer inference, this work provides theoretical guarantees and design principles for KV cache compression, bridging a gap between empirical experimentation and worst-case impossibility results.
This paper characterizes the minimax risk of KV cache compression, revealing when accurate compression is possible and yielding design principles that achieve minimax-optimal risk. The principles are instantiated in a practical algorithm with promising performance on LongBench.
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.