🤖 machine learning

Trust the Mass: Forced Weights in KV-Cache Eviction

This paper argues that the performance gains of existing KV-cache eviction methods often stem from implicit memory budget advantages rather than superior selection strategies, and introduces ContourKV, a training-free allocator based on "dropped-mass" statistics that achieves state-of-the-art results while strictly enforcing memory constraints.

Original authors: Jack Shi, Jerry Gu

Published 2026-08-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jack Shi, Jerry Gu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Large language models, the engines behind modern artificial intelligence, rely on a vast internal memory to hold the context of a conversation as they generate text. As a model reads a long document or a multi-turn chat, it stores a representation of every word it has seen so far. This storage, known as the key-value cache, acts like a working notebook that allows the model to recall earlier details when forming new sentences. However, as conversations grow longer, this notebook can become so large that it overwhelms the computer's memory, slowing down the system or causing it to crash. To keep these models running smoothly, engineers have developed rules to delete older or less important entries from this notebook, keeping only a subset of the data to save space. The central challenge has always been deciding which pieces of information to discard without losing the ability to understand the text.

A team of researchers at Stanford University has taken a fresh look at this problem, challenging the assumption that complex, custom-built rules are necessary to make these deletions effectively. They investigated whether the most straightforward approach—simply keeping the entries that the model currently considers most important and discarding the rest—was already nearly as good as any sophisticated method could possibly be. By testing this idea across five different large language models and analyzing hundreds of thousands of specific instances of how the models process information, they found that the simple strategy of keeping the strongest signals is already remarkably close to the theoretical best possible outcome. Their measurements showed that even the most perfect, mathematically ideal way of choosing which items to keep would only improve the result by a tiny margin, typically closing just two to five percent of the remaining gap between the compressed version and the full, uncompressed memory.

The researchers discovered that the perceived advantages of many existing methods in the field were not actually due to better selection of information. Instead, these methods were often holding onto more data than they claimed. In the standard testing pipelines used by the community, some advanced techniques stored their choices as a list of instructions over a full, unshrunk memory block, rather than physically removing the data. This meant they were effectively keeping the entire notebook while pretending to save space. When the researchers forced these methods to actually delete data and stick to a strict memory limit, their performance dropped significantly, sometimes by as much as sixty points on standard benchmarks. This revealed that the real differentiator was not the cleverness of the selection rule, but the physical amount of memory the system was allowed to use.

To address this, the team introduced a new, free-to-use method called ContourKV. This approach does not require any additional training or complex calculations. Instead, it uses a simple, physical rule to decide how much memory to keep in different parts of the system, ensuring that the memory budget is actually enforced. When tested against the leading methods in the field, ContourKV won the majority of comparisons while using the same strict memory limits. It performed just as well as the strongest existing methods that also enforced their own memory limits, confirming that the gap between different approaches is far smaller than previously thought. The study suggests that the future of efficient long-context processing lies less in inventing complex new selection algorithms and more in building systems that can physically manage memory storage more flexibly, allowing different parts of the model to hold different amounts of data as needed.

The work also highlighted a critical flaw in how some of these systems are evaluated. In many cases, the ranking of which information to keep was calculated while the model was still reading the question or the prompt, giving it an unfair advantage. When the researchers re-ran the tests so that the decision to delete information had to be made before the question was fully visible, the performance of the best methods dropped dramatically. This finding underscores that the true test of a memory-saving rule is its ability to work without peeking at the future, a condition that many current methods fail to meet when the memory is strictly limited. The researchers concluded that the most effective path forward is to focus on physical memory management and to ensure that comparisons between methods are fair, measuring the actual bytes stored rather than the theoretical potential of the selection rules.

Technical Summary: Trust the Mass: Forced Weights in KV-Cache Eviction

Problem Statement

Large Language Models (LLMs) rely on the Key-Value (KV) cache to store past token representations, which dominates memory usage during long-context inference. To manage this, deployed systems employ sparse-attention or KV-cache-eviction rules that retain a subset of keys, discard the rest, and renormalize the attention weights over the kept set.

The core problem addressed is the gap between the performance of these deployed methods and the theoretical optimum. While previous literature compares eviction methods based on benchmark scores, this paper questions what these scores actually measure. Specifically, it investigates whether the performance differences between methods stem from superior subset selection or from artifacts in how memory is allocated and measured. The authors focus on the constraint of forced weights: once a subset of keys is chosen, the attention weights are fixed (renormalized) rather than re-optimized. The paper asks: How much can the subset selection alone improve the output once the weights are forced?

Methodology

1. Theoretical Analysis and Enumeration

The authors formalize the eviction problem as finding a subset $A$ of size $s$ that minimizes the error $e_s(A) = \|\mu - m_A\|$ , where $\mu$ is the dense attention output and $m_A$ is the output under forced weights.

Hardness: They prove that deciding if the error can be zero ( $ES(s)=0$ ) is NP-complete, even for 1D data with uniform masses.
Enumeration: To quantify the "selection ceiling," the authors enumerate the exact best subset over a restricted candidate set (top-mass keys plus keys with largest single-key error) across 168,192 attention rows from five models (Qwen, Llama, OLMo, Gemma).
Balancing Selector: They introduce a "balancing selector" (a greedy swap rule) that starts with the top-mass set and iteratively swaps keys to minimize error. This serves as an upper bound on what any selection rule can achieve under forced weights.

2. Measurement of Memory and Budgets

The paper identifies a critical flaw in existing evaluations: many state-of-the-art methods (e.g., KVzip, ExpectedAttention) claim to compress the cache but, in standard evaluation pipelines, store the full cache and apply selection via masks. This means they hold the full memory footprint while claiming compression.

Physical Enforcement: The authors enforce a strict, physical memory budget where the cache size is actually reduced (ragged storage), rather than just masked.
Audit: They re-evaluate existing methods (SnapKV, Compactor, KVzip, etc.) under these physically enforced budgets to separate the effects of "selection quality" from "memory holding."

3. ContourKV

The authors propose ContourKV, a training-free allocation rule.

Mechanism: It uses a "dropped mass" statistic ( $\bar{m}_s$ ) to predict which attention heads (cells) have a large gap between the top-mass selection and the dense output.
Allocation: It directs the fixed budget to these "flat" cells where selection can still improve the output, while keeping a recency floor in all cells. It reuses importance scores from existing methods (e.g., KVzip's reconstruction score or SnapKV's observation window) but replaces the allocation logic.

Key Contributions

Near-Optimality of Top-Mass Selection: Through exhaustive enumeration, the authors demonstrate that keeping the largest attention weights (top-mass) is already near-optimal under forced weights. The best possible subset improves upon the top-mass set by only a median of 2% to 5% of the remaining gap to the dense output.
The "Selection Ceiling": They establish that the fraction of the gap a better subset can close is small and predictable. The "dropped mass" (the sum of weights of discarded keys) is a strong predictor (AUC 0.76–0.89) of whether a specific attention row will benefit from complex selection over simple top-mass.
Memory vs. Selection Accounting: The paper reveals that published performance margins between eviction methods often stem from memory differences rather than selection quality. Methods that do not physically evict (holding the full cache via masks) outperform those that strictly enforce a budget.
Query-Agnostic vs. Query-Aware: The authors trace an 87.6-point retrieval margin to rankings computed while the question is visible (query-aware). When selection is strictly query-agnostic (before the question is seen), the performance gap narrows significantly.
ContourKV: A new allocator that achieves state-of-the-art results by physically enforcing budgets and intelligently distributing them based on the dropped-mass statistic, without requiring training.

Results

Theoretical Findings

Gap Closure: Across eight model families and various budgets ( $s=4$ to $32$), the median share of the gap closed by the optimal subset is 0.021 to 0.047.
Penalty of Forced Weights: The ratio of error under forced weights to free weights ( $\pi(s)$ ) increases with budget, rising from 1.07 to 1.79 as $s$ goes from 4 to 32.
Predictability: The dropped mass statistic exclusively predicts whether an instance has a significant gap ( $\hat{\kappa} > 1.11$ ).

Empirical Benchmarks

ContourKV vs. KVzip: In 160 paired comparisons, ContourKV (with budget enforced) wins 93, ties 22, and loses 22 against KVzip (which holds the full cache). When ContourKV's budget is enforced to match KVzip's byte count, it still wins 93 times.
Cost of Budget Enforcement: Enforcing a nominal budget on a single fixed selection (without adaptive allocation) costs 14.1 to 62.2 benchmark points on LongBench and RULER.
Retrieval Performance: In retrieval tasks, ContourKV (window-scored, budget enforced) beats SnapKV in 23 of 48 conditions and ties in 23, with a win rate of 0.37 to 1.00 against SnapKV's 0.00 to 0.11 at $s=128$ .
Comparison to Compactor: ContourKV ties Compactor (the strongest budget-enforcing baseline) in 96 of 160 comparisons. The authors attribute this tie to the fact that both methods operate near the subset optimum, where the remaining gap is too small to separate them.

Significance and Claims

The paper claims its primary contribution is measurement and accounting, not necessarily the superiority of ContourKV itself.

Reframing the Problem: The authors argue that optimizing the gap to the dense output is the only quantity a compressor can optimize before the query arrives. They show that this gap is largely irreducible by selection alone once the weights are forced.
Infrastructure vs. Algorithm: The paper posits that the "margins" seen in literature often reflect infrastructure differences (e.g., ragged vs. uniform storage, full cache vs. evicted cache) rather than algorithmic superiority in subset selection.
Modest Optimism: The authors are modest about the potential for further gains. They note that since the "selection ceiling" is so low (2-5%), two rules that are near the subset optimum cannot be easily separated. They also note that optimizing the gap is ideal only in multi-turn scenarios where a single compressed cache serves multiple queries; for single-turn tasks, the value of such optimization is separate.
Future Direction: The paper suggests that future improvements may lie in ragged paging (allowing different heads to hold different numbers of entries) and in understanding the "value-side residual" that selection cannot capture, rather than in finding better subset selection heuristics.

In summary, the paper argues that the community has been overestimating the power of subset selection in KV-cache eviction. The dominant factor in performance is often the physical memory budget and whether the method truly evicts data, rather than the sophistication of the selection rule. ContourKV serves as a proof-of-concept that a simple, training-free allocator, when paired with strict memory enforcement and intelligent budget distribution, can match or exceed state-of-the-art methods.