Source-linked AI summary
Trust the Mass: Forced Weights in KV-Cache Eviction
Jack Shi, Jerry Gu
TL;DR
The paper asks whether eviction quality comes from selecting better subsets when deployed operators force attention weights, and whether published comparisons measure memory fairly. It enumerates forced-weight subsets, audits evaluation pipelines, and introduces ContourKV, finding that selection is near-optimal while budget enforcement materially changes results. At matched memory, ContourKV wins 93 of 160 comparisons against KVzip, loses 22, and ties Compactor.
Problem
Eviction methods keep subsets and renormalize weights, but the paper investigates how much improvement selection can provide and what published comparisons actually measure.
Method
The paper enumerates exact best subsets on 168,192 attention rows, audits bytes and query information in the shared evaluation pipeline, and deploys the training-free ContourKV allocator.
Results
Keeping the largest weights is near-optimal, while enforcing a nominal budget on one fixed selection costs 14.1 to 62.2 benchmark points; ContourKV wins 93 of 160 comparisons against KVzip and loses 22.
Takeaways & Limitations
Eviction comparisons should enforce budgets and measure physical memory, because query-agnostic masks can leave the full cache resident.
Takeaways & Limitations
The paper has not shown that a rule acting before the question arrives can reach the value-side residual.
Abstract
from arXiv · showhide
Every deployed sparse-attention or KV-cache-eviction rule keeps a subset of the keys, discards the rest, and renormalizes the attention weights over the kept set. Enumerating the exact best subset under that constraint on $168{,}192$ attention rows from five models shows that keeping the largest weights is already near-optimal, since the best subset closes only a median $2$ to $5\%$ of the remaining gap to full attention. If selection closes this little, published margins between eviction methods must come from elsewhere, so we measure the bytes each method holds. In the shared evaluation pipeline, the strongest query-agnostic methods hold the full cache because their per-head selections are stored as masks, and only ragged per-head storage frees that memory. Enforcing a nominal budget on one fixed selection costs $14$ to $62$ benchmark points. We trace an $87.6$-point retrieval margin to rankings computed while the question is visible. ContourKV, a training-free allocator built from the dropped-mass statistic, wins $93$ of $160$ paired comparisons against that state of the art and loses $22$ at the byte count of the budget-enforcing baselines, and it ties the strongest of them.
1 Introduction
The paper argues that forced-weight selection is already near-optimal, so eviction-method comparisons must account for memory, query information, and compute. It introduces ContourKV and physically enforces budgets to measure deployed performance fairly.
- Selection ceiling: 168,192 attention rows from five models show that the largest-weight keys are already near-optimal under forced weights.The exact best subset closes only a small fraction of the remaining gap to dense attention.
- Selection ceiling: The best subset closes a median 2 to 5% of the remaining gap to the dense output, while a cheap swap rule recovers that median in full.The dropped weight predicts the exceptions.
- Evaluation accounting: Query-agnostic methods can retain the full cache when per-head selections are stored as masks over a non-shrinking cache.Their published quality can therefore reflect selection quality at full memory rather than memory reduction.
- Evaluation accounting: Enforcing a nominal budget on one fixed selection costs 14.1 to 62.2 benchmark points.The paper separates margins into memory, query information, and compute.
- ContourKV: ContourKV wins 93 of 160 comparisons against KVzip while losing 22, and ties Compactor at matched memory.It is training-free, reuses existing importance scores, and enforces its budget physically before results are read.
- Scope: The paper’s contribution is measurement and accounting, with the gap to the dense output especially relevant when one compressed cache serves multiple later queries.This setting corresponds to multi-turn use, where decode continues appending to the cache.
2 Operator and Frozen-Head Measurements
The paper formalizes forced-weight subset selection for attention, measures its ceiling and frozen-head costs, and uses dropped mass to identify where better allocation can help. Across models and budgets, top-mass selection is usually near-optimal, while forced-weight penalties and deployment storage explain larger practical differences.
- 2.1 Operator: Forced-weight attention renormalizes the original weights over a kept subset, unlike free-weight approximation, which re-solves weights on retained values.The paper defines ES(s) for forced weights and EF(s) for re-solved weights, with ES(s) ≥ EF(s).
- 2.1 Operator: ES(s)=0 decision is NP-complete even in one dimension with uniform masses and s=N/2.The result rules out polynomial-time multiplicative approximation unless P=NP.
- 2.2 Enumeration: At s=8, shared frozen-head group voting costs a median 1.06× to 1.22× each row’s own top-mass error as group size grows from 2 to 6.Against each row’s own ESpool, the corresponding medians are 1.14× to 1.38×.
- 2.2 Enumeration: 168,192 attention rows across five models show that top-mass selection closes a median 2.1% to 4.7% of the remaining top-mass-to-dense gap.The balancing selector recovers a median 1.00 of the closable gap within the audited candidate set.
- 2.2 Enumeration: Forced-weight penalty rises with budget: on the reference family, median π increases from 1.07 to 1.79 and the 99th percentile from 2.2 to 6.8 as s grows from 4 to 32.After renormalization, geometric selection also performs worse than top-mass.
- 2.3 Prediction: Dropped mass predicts difficult instances at AUC 0.76 to 0.85 on four headline families and 0.76 to 0.89 across ten arms.The statistic is one-pass O(Nd), tracks ESpool at Spearman 0.84 to 0.98 on the reference family, and costs 0.002× to 0.03× a dense attention layer.
- 2.3 Prediction: Replacing top-mass with balancing only in flat cells lowers held-out continuation cross-entropy by 0.122 to 0.243 nats on five of eight families at s=8.This targeted switch captures 88% to 98% of all-cell balancing’s improvement.
3 Related Work
Prior work studies subset approximation, eviction scoring, and memory infrastructure, but commonly reweights retained points or leaves physical storage and optimality gaps unspecified. This paper positions forced-weight analysis and byte-level auditing as the missing diagnostic connection.
- 3 Related Work: Classical subset approximation, coresets, and optimal design re-solve or reweight the retained points, whereas eviction renormalizes the original attention weights.The paper identifies forced weights as the distinction separating its problem from these lines of work.
- 3 Related Work: Value-aware eviction scores rank decisions at decode time but do not certify how close the retained set is to an optimum.Retained mass can stop a budget or allocate one across heads without stating the resulting set’s optimality gap.
- 3 Related Work: Ragged paging addresses storage constraints, while the paper measures the nominal-to-physical memory gap per method class.ContourKV reuses prior methods’ importance scores and replaces only their allocator.
4 Deployment
Deployment results show that measured memory and budget enforcement materially affect eviction comparisons, while retrieval margins can arise from question-visible ranking. ContourKV performs competitively when compared at matched byte counts.
- ContourKV: ContourKV uses a shared importance threshold across heads and layers, retaining a recency floor while allocating extra entries where dropped mass predicts residual selection gains.Its score is instantiated with KVzip’s context-reconstruction score, so the methods differ in allocation.
- Benchmark results: 14.1 to 62.2 benchmark points are lost when a nominal budget is enforced on one fixed selection.The average LongBench loss at s = 32 is 14.1 points, rising to 62.2 on RULER at s = 128.
- Benchmark results: 93 of 160 paired conditions favor ContourKV over KVzip, while 22 favor KVzip at the budget-enforcing baselines’ byte count.Without enforcement, ContourKV wins 146 of 157 conditions, but that comparison allows KVzip to hold the full cache.
- Benchmark results: ContourKV ties Compactor at matched memory, consistent with the small attainable gap between near-optimal subset selections.Reallocating memory by the window score nearly ties SnapKV, finishing 0.13 points below it over 154 conditions.
- Retrieval: 88.2 and 87.6 retrieval points are lost when rankings use document rows or eviction moves to the document boundary, respectively.The two losses differ by only 0.6 points, while the allocation contributes none of the measured margin; the relevant ranking runs over question rows.
- Measurement: Comparisons require enforced budgets and measured memory because the strongest query-agnostic methods can retain the full cache under mask-based per-head storage.Only ragged per-head storage frees that memory in the shared pipeline.
A Proofs
This appendix section states that its purpose is to prove Lemma 2.1 and Proposition 2.1.
- The appendix aims to prove Lemma 2.1 and Proposition 2.1 stated in Section 2.
A.1 Identities
The appendix develops identities and bounds for subset approximation, then records limitations of forced-weight selection and its error-based predictors.
- Identities: The weighted mean decomposes into kept-set and complement means, yielding an identity for the distance between the full and kept-set means.The proof uses the law of total expectation: µ = p(A)mA + ¯p(A)mAc.
- Identities: The single-key case recovers the per-decision eviction-error bound by setting the complement mean to the dropped key.This connects the general identity to prior single-key analyses.
- Bounds: EF(d + 1) = 0 is attainable in the worst case, with minimizers given by hull extreme points independent of the masses.
- Bounds: EF(s) ≤ σ/√s ≤ D/√s, giving a free-weight approximation bound that follows from averaging and bounded support.Padding the selected set to exactly s points preserves the bound.
- Limitations: A small dropped mass does not guarantee instance-level near-optimality because the two errors in κ can both be small and the denominator can shrink faster.Dropped-mass prediction is therefore statistical rather than deterministic.
- Optimization: Forced-weight error is not submodular or supermodular, so the appendix uses restricted candidate enumeration and upper-bounding selectors.The candidate pool combines the top-mass set with keys having largest single-key error.
A.2 Hardness
The hardness appendix reduces ZEROES from balanced partitioning and shows that approximating the optimum within a multiplicative factor would decide an NP-complete problem. Empirically, exhaustive and certified searches find that better subsets close only a small fraction of the top-mass-to-dense gap.
- Hardness proof: Balanced partitioning is reduced to ZEROES by encoding integers as one-dimensional key locations with uniform masses and budget m/2.The construction preserves whether an equal balanced split exists.
- Hardness proof: For balanced subsets, the excess score is either zero or at least 2m^-2, creating a discrete gap used in the reduction.
- Hardness proof: ZEROES lies in NP because a verifier checks subset cardinality and tests the exact zero-gap condition using polynomial-bit arithmetic.
- Hardness proof: Any polynomial-factor estimate of ES(s) would distinguish zero from positive instances and therefore imply P=NP.Constructed instances have ES(s)=0 or ES(s)≥2N^-2, enabling a threshold test.
- Certification and experiments: Across the empirical evaluation, the estimated closable share remains small, while balancing reaches the candidate-set optimum after one to two swaps.The evaluation uses exhaustive enumeration, solver checks, and multiple model families and budgets.
B.4 Sensitivity of Certification
Certification remains stable when solver-discovered improvements replace the pooled enumeration argmin. Distribution-free bounds and audited-family results keep the estimated closable share small across budgets.
- Certification substitution: Replacing ESpool argmins with solver improvements changes the paired median closable share by at most +0.0063 at s=32.The corresponding median balancing ratio changes by only 3×10^-7.
- Certification substitution: Wilson-95 bounds cap the population median closable-share distribution at 0.108 at s=32, even counting unsolved instances as improved.
- Budget sensitivity: Across deployed budgets, per-budget 95% intervals for the median closable share stay within [0.017, 0.051].
- Reference tables: At s=32, the geometric ratio ranges from 1.3 to 2.6, whereas the leverage ratio ranges from 7 to 32 across families.
B.6 Other Details
Budget reallocation can worsen reconstruction error because flat cells have little closable error, while dropped mass better identifies difficult instances than prior absolute bounds. Swap-based balancing is inexpensive at decode but costly as a prefill mask.
- Allocation: Reallocating budget increases pooled reconstruction error by +0.044 to +1.032 at unit budget 8 under balancing.The deltas are measured against uniform allocation at matched total budget.
- Prediction: Prior absolute bounds classify difficult instances worse than dropped mass alone, with AUC ranges 0.58 to 0.87 and 0.58 to 0.86 versus 0.76 to 0.89.
- Prediction: The diameter and variance refinements rank top-mass error strongly but correlate less with the remaining gap, while dropped mass reaches 0.48 to 0.73.
- Cost: One balancing swap round costs about 2% of a row’s QK^T computation at N=4,096, with a median of one to two swaps.As a prefill mask, the same round is launch-bound at 20× to 114× a dense layer.
C Selector Details
Deployed selector comparisons depend on whether evaluation uses cache-faithful masks and on the bytes physically retained. Query-agnostic masks can preserve dense-cache memory, while reconstruction scoring adds substantial compute cost.
- Selector quality: At s=8, deployed selectors are 1.4 to 2.1 times ESpool, compared with 1.02 to 1.03 for top-mass on sharper families.
- Held-out loss: Quest has the lowest held-out loss increase at s=8, while StreamingLLM has the highest; per-query loss does not exceed cache-faithful loss when both exist.
- Evaluation caveat: Baseline all-true masks ignore which positions survived eviction, so their absolute levels differ from per-layer cache-faithful comparisons.
- Memory: KVzip retains the full dense cache, 28 to 1078 times SnapKV’s bytes, while unenforced ContourKV retains 3.5% to 84%.
- Compute cost: ContourKV reconstruction scoring costs 8.7 to 13.6 times a dense context prefill, versus 1.03 to 1.13 times for SnapKV and CompressKV.
D.3 Per-condition results
ContourKV generally outperforms the compared methods, but its deficits concentrate in specific settings, especially low-budget RULER and layer allocation. CompressKV remains close overall yet loses most clearly where allocation is active.
- RULER and retrieval: 10.4 to 76.4 points: ContourKV’s margins over KVzip at RULER s = 128 are positive across all fourteen model-length cells.Every interval excludes zero.
- RULER and retrieval: −7.3 and −6.6 points: ContourKV’s only significant losses against any opponent occur on LongBench repobench-p for Llama-3.1-8B at both budgets.
- RULER and retrieval: 16 of 22 losses to KVzip occur at RULER s = 32, where KVzip scores 12.6 to 17.6 and SnapKV scores 3.6 to 5.5 from the full cache.
- Allocation effects: 13.55 and 10.75 points: the window-scored per-layer variant falls below Compactor and the uniform run, respectively, at RULER s = 128.
- Allocation effects: −0.85 points: CompressKV’s budget-enforced aggregate record against ContourKV is 7/47/26, with its RULER s = 128 block at 0/0/8 and −9.39.
E Reconstruction Boundary
The reconstruction experiments test whether balancing gains come from ranking the right cells or merely increasing set size. Results show substantial dependence on model and allocation, while curvature-based predictions closely match measured gain shares.
- Learned scoring: At most 5%: the prefill probe recovers only this share of decode-time loss reduction against a fixed 25% target.
- Cell selection: 94% versus 66%: on Qwen2.5-1.5B, the map recovers more all-cell gain than a random set, but two thirds of its gain comes from set size alone.
- Cell selection: 77% versus 15%: on Qwen3-1.7B, the random set outperforms the map, and no tested cell ranking beats random selection.
- Cell selection: 55/15/31%: across the three Qwen3 scales, the map retains these fractions of the all-cell gain.
- Curvature analysis: 0.86 to 0.95 versus 0.88 to 0.98: the second-order curvature prediction matches measured shares of the loss gain.The conversion constant is the loss change per unit of flat-cell reconstruction reduction.