Summary (Overview)

• Key finding 1: Enumerating the exact best subset under forced weights (where attention weights are renormalized over kept keys) on 168,192 attention rows from five models shows that keeping the largest weights (top-mass selection) is already near-optimal. The best subset closes only a median 2–5% of the remaining gap to full attention.
• Key finding 2: Published margins between eviction methods largely come from memory accounting artifacts, not selection quality. The strongest query-agnostic methods (e.g., KVzip) hold the full cache because per-head selections are stored as masks over non-shrinking tensors in the evaluation pipeline.
• Key finding 3: Enforcing a nominal budget on one fixed selection costs 14.1 to 62.2 benchmark points, and an 87.6-point retrieval margin traces to rankings computed while the question is visible (a test-set contamination issue).
• Key finding 4: ContourKV, a training-free allocator built from the dropped-mass statistic, wins 93 of 160 paired comparisons against KVzip (losing 22) at the byte count of budget-enforcing baselines, and ties Compactor, the strongest budget-enforcing baseline.
• Key finding 5: The balancing selector (a greedy swap rule) recovers a median 1.00 of the closable gap in every family and budget, confirming that selection quality is near-saturated at top-mass.

---

Introduction and Theoretical Foundation

Every deployed sparse-attention or KV-cache-eviction rule operates by:

1. Keeping a subset of keys
2. Discarding the rest
3. Renormalizing attention weights over the kept set

This "forced weights" constraint distinguishes the problem from classical subset approximation, which re-solves weights on kept points (e.g., coresets, optimal design, recombination). The paper asks a fundamental question: What is the maximum gain any kept set can achieve once weights are forced?

Key definitions:

• An instance is a strictly positive probability vector $p$ on $[N] = \{1, \ldots, N\}$ with points $v_1, \ldots, v_N \in \mathbb{R}^d$ and mean $\mu = \sum_j p_j v_j$
• A kept set $A \subseteq [N]$ has mass $p(A) = \sum_{j \in A} p_j$, dropped mass $\bar{p}(A) = 1 - p(A)$, and forced-weight mean $m_A = \sum_{j \in A} (p_j / p(A)) v_j$
• The top-mass set $A_s^\star$ is the size-$s$ set of largest masses
• $\bar{m}_s = \bar{p}(A_s^\star)$ is the least achievable dropped mass

Central lemma (Lemma 2.1):

$$\operatorname{es}(A) = \bar{p}(A) \| m_{A^c} - m_A \| = \frac{\|g_A\|}{p(A)}, \quad g_A := \sum_{j \in A} p_j (v_j - \mu)$$

where $\operatorname{es}(A)$ is the forced-weight error and $\operatorname{ef}(A)$ is the free-weight (re-solved) error. The bound $\operatorname{es}(A_s^\star) \leq 2D\bar{m}_s$ holds with $D = \max_j \|v_j - \mu\|$.

Computational hardness (Proposition 2.1): Deciding whether $\operatorname{ES}(s) = 0$ is NP-complete, even at $d = 1$ with uniform masses, integer points, and $s = N/2$. No polynomial-time estimate within any multiplicative factor exists (unless P = NP), nor within additive error $< N^{-2}$.

---

Methodology

Enumeration Protocol

• Instances: Sampled query rows from frozen attention heads across ten model arms (Qwen2.5-1.5B, Llama-3.2-1B, OLMo-2-1B, Qwen3-1.7B as headline families; plus Qwen3-0.6B/4B, gemma-2-2b, gemma-3-1b-pt, Qwen2.5-7B at 16K, Qwen3-14B)
• Budgets: $s \in \{4, 8, 16, 32\}$ for exact enumeration (111,744 instances), extending to $s = 256$ via the balancing selector
• Candidate set: Top-mass set plus keys of largest single-key error $p_j\|v_j - \mu\|$
• Certification: Cap-widening sweeps (25× larger enumeration) and an exact mixed-integer solver (SCIP)

The Balancing Selector

A greedy alternative that:

1. Starts at $A = A_s^\star$ (top-mass set)
2. Repeatedly takes the swap of one kept key for one dropped key that most decreases $\operatorname{es}(A)$
3. Stops when no decrease exists

Uses the dense output $\mu$, so it runs at decode time or as a prefill teacher—used only to measure the closable gap, not in ContourKV itself.

ContourKV Allocator

• Uses one importance score $r$ and one threshold $\tau$ shared by every layer and head
• Each cell keeps a recency floor $F$ of the last 32 positions plus $\{j \notin F : r_j \geq \tau\}$
• $\tau$ is set so the cache averages $s$ entries per cell (flat cells retain more)
• Instantiations: KVzip's context-reconstruction score and SnapKV's observation-window score (both training-free)

Evaluation Pipeline

• Benchmarks: RULER and LongBench on Llama-3.1-8B-Instruct, Qwen2.5-7B-Instruct, Qwen3-8B, Qwen3-14B at 4,096–32,768 tokens
• Pipeline: NVIDIA's official kvpress pipeline with its method implementations
• Memory measurement: Replayed benchmark contexts through the same code at the same commit (prefill only, 603 measurements per model)

---

Empirical Validation / Results

Selection Ceiling

• Median closable share $\hat{c}$ of 0.021 to 0.047 over eight families and all budgets (95% intervals inside [0.017, 0.051])
• $\hat{\kappa} \leq 1.5$ on 89–90% of instances; $\hat{\kappa} \leq 2$ on 97% at $s \in \{4, 8\}$
• Top-mass attains $\operatorname{ES_{pool}}$ outright on 39% of instances at $s = 4$ and 21% at $s = 8$
• At deployed budgets ($s = 64$ to 256), the gap cap $2D\bar{m}_s$ falls to 28–34% of its $s = 8$ value at $s = 64$ and 8–12% at $s = 256$

Forced vs. Free Weights Penalty

• The ratio $\pi(s) = \operatorname{ES}(s)/\operatorname{EF}(s) \geq 1$ rises from median 1.07 at $s = 4$ to 1.79 at $s = 32$ (99th percentile: 2.2 to 6.8)
• Geometric selection (Frank–Wolfe support) does worse than top-mass under forced weights (median ratio rises to 2.06 with budget)
• Ridge-leverage selection is far worse: median ratio rises to 20.3

Deployed Selector Audit

At $s = 8$ on the three sharper families:

• SnapKV, H2O, Quest, StreamingLLM sit at median 1.4–2.1× $\operatorname{ES_{pool}}$
• Top-mass sits at 1.02–1.03×
• TOVA's keep set is identical to top-mass
• SnapKV's error holds at 1.8–2.2× the same-budget top-mass error through deployed budgets

Memory Accounting Findings

Key result: The five per-head methods (including KVzip) hold all of the cache at every length and budget because the pipeline stores each layer's cache as one tensor with equal slots per head, applying the selection as a mask.

Retrieval Condition Decomposition

The 87.6-point retrieval margin traces entirely to rankings computed while the question is visible—a test-set contamination issue, not a memory effect.

---

Theoretical and Practical Implications

Theoretical Contributions

1. Forced-weight optimality gap is small: The paper establishes that top-mass selection is near-optimal under forced weights, with the exact optimum closing only 2–5% of the remaining gap to dense attention. This is a fundamental limit, not a method-specific artifact.

2. NP-hardness of exact selection: Deciding whether $\operatorname{ES}(s) = 0$ is NP-complete even in the simplest case ($d = 1$, uniform masses), establishing that no polynomial-time algorithm can certify optimality.

3. Dropped mass as a certificate: The statistic $\bar{m}_s$ (least achievable dropped mass) predicts whether an instance has $\hat{\kappa} > 1.11$ at AUC 0.76–0.85 across ten arms, while spectral alternatives perform at chance. The one-pass $O(Nd)$ statistic $\Phi = \|g_{A_s^\star}\|$ tracks $\operatorname{ES_{pool}}$ at Spearman 0.80–0.98.

Practical Implications

1. Memory accounting reform: Published comparisons between eviction methods need enforced budgets and measured memory. The nominal-to-physical memory gap (masks over non-shrinking caches) is a critical confound.

2. ContourKV's contribution: A training-free allocator that wins 93/160 comparisons against KVzip at matched budget and ties Compactor, confirming the theoretical prediction that two rules near the subset optimum cannot separate when selection closes only a few percent of the remaining gap.

3. Cell-level conversion: Switching only flat cells (those with median dropped mass > 0.25 at $s = 8$) to balancing lowers held-out cross-entropy by 0.122–0.243 nats on five of eight families, capturing 88–98% of all-cell balancing gains.

4. Limits of value-aware selection: A rank-16 scorer trained on query/key projections recovers at most 5% of the decode-time loss reduction because the gain sits in the value-side residual $g_A$, which lies outside those projections.

---

Conclusion

The paper establishes that forced-weight KV-cache eviction has a fundamental selection ceiling: keeping the largest weights is already near-optimal, and better subset selection closes only 2–5% of the remaining gap to dense attention. This finding has three major consequences:

1. Published margins between eviction methods come from memory accounting, not selection quality. The strongest query-agnostic methods hold the full cache in the shared evaluation pipeline because per-head selections are stored as masks.

2. Enforcing budgets costs benchmark points. A nominal budget on one fixed selection costs 14.1–62.2 benchmark points, and retrieval margins can be inflated by rankings computed while the question is visible.

3. ContourKV demonstrates practical allocation at matched memory. It wins 93/160 comparisons against KVzip and ties Compactor, confirming that near-optimal rules cannot separate when the selection ceiling is this low.

Future directions: The paper notes that it has not yet shown that a rule acting before the question arrives can reach the value-side residual $g_A$. The dropped-mass statistic $\bar{m}_s$ provides a cheap, one-pass certificate for identifying cells where better selection can still help, and the balancing selector offers a decode-time mechanism to capture that remaining gain. The authors emphasize that their contribution is the measurement and accounting, which does not depend on ContourKV winning.