Low-Rank KV Cache Compression in LLMs: A Second-Order Output Metric and Its Limits

The key–value (KV) cache makes autoregressive decoding in large language models fast, but it grows with the length of the context. At long context it becomes the main drain on a GPU’s memory, both in how much it has to store and in how fast it can be read. Compressing the keys and values with a low-rank projection is a cheap, training-free way to shrink it. The trouble is that existing methods help only a little at the compression ratios people actually use, and the targets they optimize are mostly heuristics. This thesis builds a second-order account of attention-aware low-rank KV compression and uses it to show both what these methods can do and where they break down.

Our approach builds on a fundamental premise: the model reads the attention output, not the key vectors. From this we derive a closed-form metric, the output-Fisher metric, that scores each key direction by how much compressing it would change the output. The score is the product of two things: how strongly a query attends to the key, and how distinctive the value it reads is after the output projection. This metric extends the first-order, logit-matching objective of KQ-SVD to the output. It gives an optimal rank-r key basis in closed form, as a whitened generalized eigenproblem, and it adds nothing to the cost of inference.

We then show that this metric is the diagonal of the true attention-output Hessian. The off-diagonal blocks are couplings the metric drops: across tokens, across keys and values, and across layers. We measure all three in closed form. Each is large when you look at the distortion, but under aggressive compression each barely moves the loss.  Instead, we find that dynamic
rank allocation is the primary driver of loss reduction. Spending a global rank budget by water-filling the end-to-end loss-Fisher spectrum pushes the usable compression frontier further out, beats the strongest published allocator at the same budget, and carries over to grouped-query attention.

Finally, we find the largest error the second-order metric throws away at high compression: the third-order curvature of the softmax. It grows steadily as compression increases. We show it is irreducibly non-quadratic, so no metric can capture it, not even a curvature-corrected one. Together these results mark a hard limit on metric-based low-rank attention compression. They also explain, through a decoupling of output distortion from the loss that recurs throughout the work, why the returns on finer metrics shrink exactly where compression is needed most.

Committee: Ali Jannesari (major professor), Yang Li and Mengdi Huai