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.
Figures & tables
Figure 1: Ceiling across 10 arms. Per family and budget, the reconstruction residual is normalized so that top-mass sits at 1 and dense at 0 . The block is the remainder ESpool/es(As⋆) that cannot be closed by any candidate subset, and the cap above it is the share c^ that a subset can close. The mark is the balancing selector’s residual, which sits at the floor in every cell. Since ESpool≥ES , the cap is a lower bound. Whiskers are cluster-bootstrap 95% intervals.
median balancing closure
s=4
8
16
32
64
128
256
Qwen2.5-1.5B
0.001
0.023
0.032
0.032
0.044
0.047
0.041
OLMo-2-1B
0.134
0.144
0.124
0.091
0.126
0.127
0.105
pooled
0.032
0.057
0.058
0.050
0.075
0.077
0.061
median dropped mass
0.38
0.28
0.20
0.13
0.08
0.04
0.02
gap, share of its s=8 value
—
1
—
—
0.28/0.34
0.16/0.21
0.08/0.12
Table 1: Native budget: the median share of the top-mass-to-dense gap closed by the balancing subset, which is a lower bound on c , in one convention across all budgets (the vertical rule marks the enumeration boundary). The share holds at its small-budget level through s=256 while the gap it applies to, capped by the dropped mass (last row, pooled), collapses. Balancing beats top-mass by at least 10% on 21 to 30% of Qwen2.5-1.5B rows and 47 to 59% of OLMo-2 rows across budgets. The last row gives the remaining gap at the deployed budgets as a share of its s=8 value on the native-budget records of the two audited families (Qwen2.5-1.5B/OLMo-2-1B, § 2.4 ).
Figure 2: The map. Per cell, the left panel shows the median dropped mass at s=8 and the right panel shows the median κ^ from the same records. Cell-level AUC is 0.82 to 0.94 , and balancing closes the cells whose median κ^ reaches 1.11 . Since κ^≤κ , those cells are certain.
content type
AUC(mˉs) span
share
English prose
0.78 to 0.85
26 to 30%
source code
floor of the span, 0.71
33 to 37%
French text
0.81 to 0.86
20 to 23%
Table 2: Content diversity on the reference family ( 72,576 instances). “share” is the fraction of instances with κ^>1.11 , and the AUC replicates across all three content types. The headroom itself is content-dependent, and code carries the most (median κ to 1.06 ), which is consistent with flatter attention leaving a larger tail. Input-level 95% intervals are about ±5 percentage points on the share and ±0.01 to ±0.035 on the AUC.
Opponent
Holds
Not enforced (W/T/L)
Enforced (W/T/L)
KVzip
full cache
146/9/2
93/45/22
ExpectedAttention
full cache
142/15/0
61/80/19
FastKVzip
full cache
74/3/0
57/23/0
SnapKV
budget
137/19/1
56/91/13
Compactor
budget
136/20/1
24/96/40
KVzap
budget
76/2/1
38/28/14
Table 3: Benchmark record: win/tie/loss for ContourKV against each opponent over paired conditions, without and with its budget enforced.
Opponent
W/T/L
Opponent
W/T/L
SnapKV
23/23/2
KVzip
27/21/0
PyramidKV
23/23/2
Ada-KV
27/17/4
TOVA
25/23/0
ExpectedAttention
27/21/0
StreamingLLM
23/24/1
H2O
12/6/0 ( 18 )
KNorm
27/21/0
KVzap
11/8/0 ( 19 )
KeyDiff
21/26/1
FastKVzip
8/16/2 ( 26 )
Table 4: Retrieval: win/tie/loss for the window-scored ContourKV with its budget enforced against each compared method over document-paired conditions, with 48 per opponent unless noted in parentheses.
Re-run
Change in hit rate
Memory
ranking restricted to document rows
−88.2[−90.0,−86.4]
1.02×
eviction moved to the document boundary
−87.6[−89.0,−86.3]
1.43×
difference of the two rows
+0.6
Table 5: The condition decomposition of § 4 , on eight document-paired Llama-3.1-8B cells at s∈{64,128} . Changes are hit-rate points against the unmodified run, and memory is relative to the run compressed before the question.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Family
QK-norm
AUC(mˉs)
edge/int [95%]
ρdepth
ρ(Φ,ESpool)
medκ^bal
Qwen2.5-1.5B
no
0.83
1.89[1.51,2.29]
0.80
0.91
1.00
Llama-3.2-1B
no
0.80
1.98[1.72,2.26]
0.67
0.95
1.00
Qwen3-1.7B
yes
0.85
1.21[0.98,1.47]
0.94
0.98
1.00
OLMo-2-1B
yes
0.76
0.74[0.62,0.87]
0.51
0.80
1.00
Qwen3-0.6B
yes
0.85
1.31[1.04,1.60]
0.92
0.98
1.00
Qwen3-4B
yes
0.76
1.26[1.16,1.37]
0.64
0.97
1.00
Appendix
Table 6: The ten-arm panel consists of the four headline families, four widening families, and two scale arms. AUC(mˉs) is at s=8 (document-cluster 95% intervals within ±0.008 , and the Qwen2.5-7B row is budget-pooled); “edge/int” is the rate of κ^>1.11 at the network edges over the interior rate, with head-cluster intervals; ρdepth rank-correlates the per-layer profiles of dropped mass and of the κ^>1.11 rate; ρ(Φ,ESpool) is the pooled Spearman correlation of Φ with ESpool ; κ^bal is the balancing selector’s median gap (intervals [1.00,1.00] ; the statistic is discrete, § 2.2 ). † gemma-2-2b replaces QK-norm with soft-capping and 4,096 -token interleaved windows. gemma-3-1b-pt is QK-normalized with 512 -token windows.
s
improved
Wilson- 95fhi
median
cap at fhi
cap, unsolved improved
4
0/237
0.016
0.018
0.022
0.027
8
2/234
0.031
0.040
0.047
0.057
16
8/234
0.066
0.047
0.064
0.073
32
36/234
0.206
0.046
0.108
0.119
Appendix
Table 7: Certification substitution at a glance. “improved” counts manifest instances where the solver beat ESpool by more than 1% ; fhi is the Wilson- 95 upper bound on that rate; “median” is the per-budget closable-share median over the four audited families’ full record sets ( 186,240 instances per budget); the caps are the distribution-free worst-case medians after substitution, at fhi and with the 21 unsolved instances also counted as improved. The corresponding caps on the median κ^bal are 1.00 everywhere.
s
medκ
p99κ
share
es(As⋆)es(Asgeo)
es(As⋆)es(Aslev)
medπ
p99π
ρ(Φ,ESpool)
4
1.003
2.28
23.5%
1.40
6.8
1.07
2.18
0.84
8
1.025
2.27
25.9%
1.73
9.7
1.16
2.90
0.92
16
1.034
2.15
26.5%
1.96
13.8
1.39
4.27
0.96
32
1.033
1.91
23.6%
2.06
20.3
1.79
6.75
0.98
Appendix
Table 8: The per-budget reference profile for the family Qwen2.5-1.5B, with 6,048 instances per budget. “share” is the fraction with ES≤0.9es(As⋆) . The geometric column is the Frank–Wolfe support padded to size s with top-mass keys, and the padding only helps it under the operator. The leverage column is the ridge-leverage subset. All quantities are restricted to the candidate set, one-sided in the direction stated above. Across families the geometric ratio runs 1.3 to 2.6 and the leverage ratio 7 to 32 at s=32 .
Figure 3: The left panel shows the ROC of dropped mass as a predictor of each rule’s excess label at s=8 on the reference family, and the right panel shows the same AUC pooled per family with 95% intervals. The grey band is the AUC range of § 2.3 and the dashed line is chance, and the row labeled “certificate” scores mˉs itself.
Figure 4: Change in held-out cross-entropy against top-mass at s=8 when balancing only the labeled cells. The percentages give each set’s fraction of the gain from balancing all cells.
KV-cache compression is often justified by attention maps with a few large weights. This is incomplete: large weights may not contain most of the mass, omitted values can cancel, and preserving the attention output may not preserve the task. We separate these questions. Global score gaps -- not threshold counts -- determine how many tokens are needed to retain a target mass. For a realized row, the weighted sum of omitted values is the exact missing statistic. A controlled retrieval--aggregation model explains when truncation helps and when it hurts. These results motivate CertKV, a training-free compressor that reserves one tail-summary slot per head and allocates the rest by value dispersion. Under matched budgets, CertKV is top-two in seven of nine LongBench-v2 settings, remains in the leading compressed tier on 128K RULER, and realizes a ten-fold cache budget in a packed Llama prototype. Compressibility depends on the mass, values, future queries, and task -- not on a sparse-looking map alone.
Chiwun Yang, Xiaoyu Li
City University of Hong Kong · University of New South Wales
Serving long-context autoregressive language models is constrained by the key-value (KV) cache. Most dynamic eviction methods score token importance per query head and choose tokens independently. This fits poorly with grouped-query attention (GQA), where several query heads share one physical KV buffer: divergent per-head selections force the serving engine to retain the union of their choices - inflating the cache by up to the group ratio r - while arithmetic mean pooling dilutes the specialized retrieval heads that carry factual recall. We introduce Page-EntroKV, a formal framework for KV-cache eviction operating at the granularity GQA serving actually allocates. Heads within each physical group are pooled by weights derived from sink-isolated collision (Renyi-2) entropy - one inner product per head, computed once at prefill with no calibration - so sink heads cannot masquerade as retrieval heads. Pooled scores are projected onto PagedAttention page frames, and eviction executes at the hardware tuple (layer, group, page). We formalize the union overhead ratio (UOR) and intra-group disagreement, prove an exact identity linking them for two-head groups alongside two-sided bounds at every group ratio, prove strict budget preservation and a finite-context needle-retention bound that arithmetic mean pooling provably violates, and give exact per-layer page accounting. On a pilot architecture (Qwen2.5-1.5B-Instruct, r=6), head-independent replay over 2,240 group measurements yields union overhead up to 4.75x at a 2% budget, while Page-EntroKV holds UOR exactly 1.000; sink isolation removes a 13x sink masquerade; needle recall is 100% versus 0% for mean pooling at a 20% budget; retained cardinality is exact for every page size; and QA and code tasks remain solvable at 20% retention.
Inbasekaran S
Department of Computer Science and Engineering SRM Institute of Science and Technology, India
Long-context decoding is increasingly constrained by key--value (KV) cache memory and bandwidth. Existing fixed-budget compression methods typically separate retention from compensation, while a retention ranking specifies neither discarded attention mass nor the direction of induced output error. We start from an exact factorization: eviction error equals evicted attention mass times the directional gap between the evicted centroid and retained output, highlighting the importance of set-level coverage in retention and mass-preserving memory writing. We introduce CORE COverage Calibration and Evicted-Mass REdistribution for KV Cache, which distills an offline allocation combining query utility and log-determinant coverage into a lightweight cache-aware indexer. At inference, one calibrated distribution drives both channels: its Top-B ordering retains complementary KV states, while its excluded allocation mass and conditional weights parameterize latent-memory writes without a separate write-weight predictor or online log-determinant evaluation. Our analysis provides a four-term pre-compensation error certificate, characterizes non-additive coverage interactions, and establishes mass-independent write stability with hierarchical bounds through recurrent and query-adaptive normalization. Across three backbones, CORE exceeds the strongest RULER baseline by up to 3.78 points at 90% compression; LongBench and repeated-eviction evaluations further demonstrate strong effectiveness and decoding efficiency.
Shuxin Liu, Qing Liu, Yi Du +1
Hangzhou Institute for Advanced Study, University of Chinese Academy of Sciences