KV-Surgeon: A Compensation-Aware Approach to KV-Cache Compression

Title

KV-Surgeon: A Compensation-Aware Approach to KV-Cache Compression

Meta Description

KV-Surgeon introduces a compensation-aware offline KV-cache compression method that jointly optimizes eviction and compensation decisions via a quadratic surrogate model, surpassing state-of-the-art methods on multiple long-context benchmarks and significantly advancing the cost-accuracy Pareto frontier.

Article Content

Offline compression of the key-value cache (KV-cache) is an effective way to reduce the fixed context cost of repeated queries: build a smaller cache once, then reuse it many times. The core challenge of compression is deciding which cache entries to evict and which to keep. Existing methods evaluate each eviction candidate independently while holding the rest of the cache fixed. However, the softmax re-normalization in the attention operation couples these decisions nonlinearly: evicting one entry changes the attention weights of all remaining entries.

To address this, researchers propose KV-Surgeon, which uses calibration data to account for interactions among entries in a tractable way. The method derives a quadratic surrogate model with a closed-form expression that jointly makes optimal greedy eviction decisions and performs compensation among the remaining entries. Experiments show that on the QuALITY, LongHealth, and Long Code Arena datasets, for dense models and mixture-of-experts models ranging from 4 billion to 30 billion parameters, KV-Surgeon significantly advances the cost-accuracy Pareto frontier at every evaluated compression ratio.

The Challenge of Compression and the Limitations of Existing Methods

The goal of KV-cache compression is to reduce the memory and compute overhead of the cache as much as possible without significantly degrading model performance. Traditional methods typically evaluate the importance of each cache entry in isolation, assuming that evicting an entry does not affect the role of other entries. But the softmax normalization in the attention mechanism ties all entries together: after an entry is evicted, the attention scores of the remaining entries are re-normalized, thereby changing the model's behavior. This nonlinear coupling makes it difficult for independent evaluation methods to make globally optimal eviction decisions.

According to the paper, KV-Surgeon captures this interaction effect through calibration data, transforming the problem into a quadratic optimization problem so that eviction and compensation can be considered simultaneously.

KV-cache is the mechanism in Transformer autoregressive inference that stores the Key and Value vectors of historical tokens, avoiding recomputation of the entire context each time a new token is generated. For repeated queries over a fixed long context (such as long documents or codebases), this cache can be built offline and reused, thereby amortizing the prefill cost. However, the cache size grows linearly with context length, and memory footprint and memory access bandwidth become bottlenecks, making compression necessary.

Softmax re-normalization refers to the fact that the denominator in the attention weights ( \mathrm{softmax}(qK^\top/\sqrt{d}) ) is the sum of exponentials over all unmasked entries. When some entries are evicted (masked), the denominator becomes smaller, and the attention weight of each remaining entry increases proportionally—this is "re-normalization." It means eviction decisions are not independent: removing one entry changes the weight distribution of all the others, producing nonlinear coupling, which is precisely the root cause of the failure of independent scoring methods.

KV-Surgeon's Core Method: Quadratic Surrogate and Compensation Mechanism

The core innovation of KV-Surgeon is to construct a quadratic surrogate model that approximates how attention weights change after entries are evicted. This surrogate model allows closed-form solution of the optimal greedy eviction policy while also adjusting (compensating) the attention weights among the retained entries to offset the effect of eviction.

Specifically, the method first uses calibration data to compute an interaction matrix among entries, then gradually selects entries to evict via a greedy algorithm, with each step accounting for compensation adjustments among the remaining entries. This joint optimization approach significantly outperforms independent scoring methods.

Quadratic surrogate model means approximating the effect of an eviction set on the attention output with a quadratic form. Since the denominator of softmax re-normalization is the sum of exponentials over the remaining entries, interaction terms naturally arise when multiple entries are evicted, and the objective function can be written as a quadratic form in terms of eviction indicator variables; within a greedy framework, each step only requires a closed-form comparison on the quadratic form to select the currently optimal single eviction, thereby avoiding combinatorial explosion.

Greedy eviction and compensation means evicting only one entry per step but allowing attention weights on the remaining entries to be adjusted (i.e., compensation) to minimize perturbation of the output distribution on the calibration data. The compensation term can be computed directly from the closed-form solution of the surrogate model without additional forward passes, so the computational cost is far lower than exhaustive or iterative optimization.

Experimental Results: Advancing the Pareto Frontier

The researchers evaluated KV-Surgeon on three long-context benchmarks: QuALITY (long-document question answering), LongHealth (long medical text understanding), and Long Code Arena (code understanding). The tested models include dense models and mixture-of-experts models, with parameter sizes from 4B to 30B.

Key results include: at a 50x compression ratio, KV-Surgeon improves question-answering accuracy by up to 4 percentage points over the current state-of-the-art attention matching method (Zweiger et al., 2026) at comparable cost. In addition, the authors propose a faster variant whose cost is only 40% of attention matching but which still surpasses state-of-the-art methods. These results show that KV-Surgeon achieves substantial improvements in the cost-accuracy trade-off.

Significance and Outlook

The proposal of KV-Surgeon offers a new perspective for offline KV-cache compression: by accounting for interactions among entries and a compensation mechanism, cache space can be utilized more efficiently. This is of significant value for application scenarios that require repeated queries over a fixed context (such as long-document question answering and retrieval-augmented generation over codebases). Possible future directions include further reducing calibration overhead and extending to online compression scenarios.

One-line Summary

KV-Surgeon jointly optimizes KV-cache eviction and compensation with a quadratic surrogate model, advancing the cost-accuracy Pareto frontier.

Paragraph Summary

Offline compression of the key-value cache (KV-cache) can reduce the cost of repeated queries over a fixed context, but the core challenge of compression is deciding which cache entries to evict. Existing methods evaluate each candidate entry independently, ignoring the nonlinear coupling introduced by attention softmax re-normalization: evicting one entry changes the attention weights of all remaining entries. KV-Surgeon uses calibration data to build a quadratic surrogate model and jointly makes optimal greedy eviction decisions in closed form, with compensation adjustments among the remaining entries. On QuALITY, LongHealth, and Long Code Arena, for dense and mixture-of-experts models from 4B to 30B, the method significantly advances the cost-accuracy Pareto frontier at every evaluated compression ratio; at 50x compression, question-answering accuracy improves by up to 4 percentage points over attention matching methods, and a faster variant at only 40% of the cost still surpasses state-of-the-art methods.