New Research Characterizes KV Cache Compression Risks

Transformer models face a significant bottleneck during inference with long sequences due to the large Key-Value (KV) cache, which is repeatedly accessed by softmax attention. KV cache compression, which replaces the full cache with a compact summary, is a common practical solution, but its design has largely been empirical. This research aims to provide a theoretical foundation for KV cache compression. The paper quantifies the minimax risk of KV cache compression, linking it to the intrinsic compressibility of the cache itself. This theoretical framework clarifies when and how accurate compression is feasible. Based on these insights, the authors derive new design principles specifically for KV cache compression under causal masking, which are efficient for both prefill and autoregressive decoding and achieve minimax-optimal risk. These principles are then instantiated into a practical algorithm, which demonstrates promising performance on the LongBench benchmark in targeted experiments. The overall contribution is a principled approach to practical KV cache compression, backed by theoretical guarantees, moving beyond purely empirical methods.