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.