Trust the Mass: Forced Weights in KV-Cache Eviction

# Trust the Mass: Forced Weights in KV-Cache Eviction
Source: [https://arxiv.org/html/2608.25230](https://arxiv.org/html/2608.25230)
###### Abstract

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 on168,192168\{,\}192attention rows from five models shows that keeping the largest weights is already near\-optimal, since the best subset closes only a median22to5%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 costs1414to6262benchmark points\. We trace an87\.687\.6\-point retrieval margin to rankings computed while the question is visible\. ContourKV, a training\-free allocator built from the dropped\-mass statistic, wins9393of160160paired comparisons against that state of the art and loses2222at the byte count of the budget\-enforcing baselines, and it ties the strongest of them\.

## 1Introduction

The KV cache stores a key and a value vector for every past token at every attention head and dominates serving memory at long context, so deployed systems shrink it by evicting entries\. Every deployed eviction or sparse\-attention rule keeps a subset of the keys and renormalizes the softmax weights over it, then returns the renormalized average in place of the dense attention output, so the methods differ only in how the subset is chosen \(\[[22](https://arxiv.org/html/2608.25230#bib.bib30),[41](https://arxiv.org/html/2608.25230#bib.bib15),[20](https://arxiv.org/html/2608.25230#bib.bib19),[5](https://arxiv.org/html/2608.25230#bib.bib6)\]\)\. Classical subset approximation re\-solves the weights on the points that it keeps and selects by geometry \(\[[6](https://arxiv.org/html/2608.25230#bib.bib38),[18](https://arxiv.org/html/2608.25230#bib.bib10),[9](https://arxiv.org/html/2608.25230#bib.bib13),[21](https://arxiv.org/html/2608.25230#bib.bib3)\]\)\. Evictionforcesthe weights\. We quantify the maximum gain any kept set can achieve once the weights are forced, and we identify what published comparisons between eviction methods actually measure\.

We enumerated the exact best subset under forced weights on168,192168\{,\}192attention rows from five models, which revealed that keeping the largest weights is already near\-optimal\. The best subset improves on it by a median22to5%5\\%of the gap to the dense output, and a cheap swap rule recovers that median in full\. The weight that selection drops predicts the exceptions \(§[2](https://arxiv.org/html/2608.25230#S2)\)\. If selection closes this little, the margins published between eviction methods must come from elsewhere\. Thus, we run them on the field’s own evaluation pipeline and read the bytes that each one holds\. The margins decompose into memory, query information and compute\. The strongest methods that compress without seeing the question select per attention head, and the pipeline stores that selection as a mask over a non\-shrinking cache, so their published quality is selection quality at full memory \(§[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px2)\)\. Therefore, we find that enforcing a nominal budget on one fixed selection costs14\.114\.1to62\.262\.2benchmark points \(§[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px4)\), and an87\.687\.6\-point retrieval margin traces to rankings computed while the question is visible \(§[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px5)\)\.

We deploy ContourKV, our allocation rule\. It wins9393of160160comparisons against KVzip \(\[[20](https://arxiv.org/html/2608.25230#bib.bib19)\]\), the leading method in that class, while losing2222, with its budget enforced against KVzip’s full cache \(memory ratios in App\.[D](https://arxiv.org/html/2608.25230#A4)\)\. At matched memory it ties Compactor \(\[[5](https://arxiv.org/html/2608.25230#bib.bib6)\]\), the strongest baseline that enforces its own budget\. This tie confirms the measurement at deployment scale \(§[2\.2](https://arxiv.org/html/2608.25230#S2.SS2.SSS0.Px2)\), since two rules near the subset optimum cannot separate when selection closes only a few percent of the remaining gap\. ContourKV is training\-free and borrows the compared methods’ own importance scores, and its budget is enforced physically before any result is read\.

Our contribution is the measurement and the accounting \(positioning in §[3](https://arxiv.org/html/2608.25230#S3)\), and it does not depend on ContourKV winning\. Our object is the gap to the dense output—the only quantity a compressor can optimize before the query\. We note that optimizing the gap is ideal only when one cache is reused\. This is the multi\-turn case, where a single compressed cache serves every later query while decode keeps appending to it\. Storage that lets each head hold a different number of entries is being built for that cache \(\[[19](https://arxiv.org/html/2608.25230#bib.bib34)\]\)\. Downstream loss is separate \(App\.[E](https://arxiv.org/html/2608.25230#A5)\)\.

## 2Operator and Frozen\-Head Measurements

### 2\.1Operator

Full details and proofs are in Appendix[A](https://arxiv.org/html/2608.25230#A1)\.

###### Definition 2\.1\(Terminology\)\.

Aninstanceis a strictly positive probability vectorppon\[N\]=\{1,…,N\}\[N\]=\\\{1,\\dots,N\\\}with pointsv1,…,vN∈ℝdv\_\{1\},\\dots,v\_\{N\}\\in\\mathbb\{R\}^\{d\}and meanμ=∑jpj​vj\\mu=\\sum\_\{j\}p\_\{j\}v\_\{j\}\. A nonemptykept setA⊆\[N\]A\\subseteq\[N\]hasp⁡\(A\)=∑j∈Apjp\(A\)=\\sum\_\{j\\in A\}p\_\{j\}, wherepjp\_\{j\}is themassof the keyjj, and it has dropped massp¯​\(A\)=1−p​\(A\)\\bar\{p\}\(A\)=1\-p\(A\)andmA=∑j∈A\(pj/p⁡\(A\)\)​vjm\_\{A\}=\\sum\_\{j\\in A\}\(p\_\{j\}/p\(A\)\)v\_\{j\}\. The top\-mass setAs⋆A\_\{s\}^\{\\star\}is a size\-ssset of largest masses andD=maxj⁡‖vj−μ‖D=\\max\_\{j\}\\\|v\_\{j\}\-\\mu\\\|\.

At an attention head,ppis one query row,vjv\_\{j\}are the values,μ\\muis the dense output, andmAm\_\{A\}is what any deployed sparse operator returns\. We callm¯s=p¯​\(As⋆\)\\bar\{m\}\_\{s\}=\\bar\{p\}\(A\_\{s\}^\{\\star\}\)the least achievable dropped mass\. For\|A\|=s\|A\|=s, letef⁡\(A\)=dist⁡\(μ,conv⁡\{vj:j∈A\}\)\\mathrm\{ef\}\(A\)=\\mathrm\{dist\}\(\\mu,\\mathrm\{conv\}\\\{v\_\{j\}:j\\in A\\\}\)be the error under re\-solved weights andes⁡\(A\)=‖μ−mA‖\\mathrm\{es\}\(A\)=\\\|\\mu\-m\_\{A\}\\\|the error under forced weights\. Their minima over\|A\|=s\|A\|=sareEF⁡\(s\)\\mathrm\{EF\}\(s\)andES⁡\(s\)\\mathrm\{ES\}\(s\), andκ⁡\(s\)=es⁡\(As⋆\)/ES⁡\(s\)≥1\\kappa\(s\)=\\mathrm\{es\}\(A\_\{s\}^\{\\star\}\)/\\mathrm\{ES\}\(s\)\\geq 1\.

###### Lemma 2\.1\.

For0<p⁡\(A\)<10<p\(A\)<1,

es⁡\(A\)=p¯​\(A\)​‖mAc−mA‖=‖gA‖p⁡\(A\),gA:=∑j∈Apj​\(vj−μ\),\\mathrm\{es\}\(A\)\\;=\\;\\bar\{p\}\(A\)\\,\\\|m\_\{A^\{c\}\}\-m\_\{A\}\\\|\\;=\\;\\frac\{\\\|g\_\{A\}\\\|\}\{p\(A\)\},\\qquad g\_\{A\}:=\\sum\_\{j\\in A\}p\_\{j\}\(v\_\{j\}\-\\mu\),andpj​\(vj−μ\)p\_\{j\}\(v\_\{j\}\-\\mu\)sums to00across alljj\. Furthermore, for everyAA,es⁡\(A\)≥ef⁡\(A\)\\mathrm\{es\}\(A\)\\geq\\mathrm\{ef\}\(A\), thusES⁡\(s\)≥EF⁡\(s\)\\mathrm\{ES\}\(s\)\\geq\\mathrm\{EF\}\(s\)\. It also holds thates⁡\(As⋆\)≤2​D​m¯s\\mathrm\{es\}\(A\_\{s\}^\{\\star\}\)\\leq 2D\\bar\{m\}\_\{s\}\.

The factorization and the last bound are known \(\[[34](https://arxiv.org/html/2608.25230#bib.bib36),[31](https://arxiv.org/html/2608.25230#bib.bib32),[13](https://arxiv.org/html/2608.25230#bib.bib4),[11](https://arxiv.org/html/2608.25230#bib.bib8)\]\), although no prior bound addresses our object, the gap to the best subset\. The problem is solved for free weights; in particular,EF⁡\(s\)≤D/s\\mathrm\{EF\}\(s\)\\leq D/\\sqrt\{s\}and geometric minimizers that do not depend onpp\(App\.[A](https://arxiv.org/html/2608.25230#A1)\)\. However, free and forced weights differ in value and argmin \(Ex\.[2\.2](https://arxiv.org/html/2608.25230#S2.Thmtheorem2)\), and that difference increases with budget \(App\.[B\.3](https://arxiv.org/html/2608.25230#A2.SS3)\)\.

###### Example 2\.2\(Free and forced weights\)\.

Letd=1d=1,v=\(−1,1,5\)v=\(\-1,1,5\),p=\(0\.45,0\.45,0\.10\)p=\(0\.45,0\.45,0\.10\),s=2s=2\. Then, we getEF⁡\(2\)=0\\mathrm\{EF\}\(2\)=0andES⁡\(2\)=922\\mathrm\{ES\}\(2\)=\\tfrac\{9\}\{22\}, attained by\{1,3\}\\\{1,3\\\}\. The top\-mass set\{1,2\}\\\{1,2\\\}gives12\\tfrac\{1\}\{2\}, a factor119\\tfrac\{11\}\{9\}above the optimum\.

###### Proposition 2\.1\(Computational Hardness\)\.

DecidingES⁡\(s\)=0\\mathrm\{ES\}\(s\)=0isNP\-complete, even atd=1d=1with uniform masses, integer points ands=N/2s=N/2\. UnlessP==NP, no polynomial\-time estimate ofES⁡\(s\)\\mathrm\{ES\}\(s\)within any multiplicative factor exists, and none within additive error<N−2<N^\{\-2\}on the reduction class \(App\.[A](https://arxiv.org/html/2608.25230#A1)\)\.

The objective is not submodular \(Ex\.[A\.2](https://arxiv.org/html/2608.25230#A1.Thmtheorem2)\), andES⁡\(s\)\\mathrm\{ES\}\(s\)is a nonconvex combinatorial minimization, so we enumerate over a restricted candidate set and use a cheap subset whose error upper\-boundsES⁡\(s\)\\mathrm\{ES\}\(s\)at any budget\. A selector maps an instance and a budget to a size\-sskept set \(top\-mass is the deployed one\) and thebalancing selectoris the greedy alternative that starts atA=As⋆A=A\_\{s\}^\{\\star\}and repeatedly takes the swap of one kept key for one dropped key that most decreaseses⁡\(A\)\\mathrm\{es\}\(A\), stopping when no decrease exists\. Balancing reads the dense outputμ\\mu, so it runs at decode time \(where the value\-aware criteria of\[[13](https://arxiv.org/html/2608.25230#bib.bib4),[14](https://arxiv.org/html/2608.25230#bib.bib39)\]also apply\) or as a prefill teacher\. Note that we use it only to measure how much of the gap a better kept set can still close—ContourKV itself does not use it \(§[4](https://arxiv.org/html/2608.25230#S4)\)\.

Even though each query row is its own instance, deployment fixes one kept set per KV head and applies it to the*group*of query rows that share that head and to all future rows\. Since every row could have kept the shared set itself, the best per\-row subset can only do better, so the per\-row optimum lower\-bounds every shared rule’s error\. One group vote, which keeps thesskeys of largest mass summed over the group’s rows, costs each row a median1\.06×1\.06\\timesto1\.22×1\.22\\timesits own top\-mass error ats=8s=8, and the cost rises monotonically with group size:1\.06×1\.06\\times,1\.12×1\.12\\times,1\.17×1\.17\\times, and1\.22×1\.22\\timesat sizes22,44,55, and66\. Against each row’s ownESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}the medians run1\.14×1\.14\\timesto1\.38×1\.38\\times\. The vote degrades7676to90%90\\%of rows against their own top\-mass sets and improves77to10%10\\%, where the improved rows are those whose own top\-mass keeps a key that the group vote drops\. The multi\-head family has group size11, so the vote reproduces each row’s own top\-mass selection exactly\.

### 2\.2Enumeration

###### Definition 2\.2\.

Thecandidate setof an instance is the top\-mass set together with the keys of largest single\-key errorpj​‖vj−μ‖p\_\{j\}\\\|v\_\{j\}\-\\mu\\\|, andESpool​\(s\)\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}\(s\)is the exact minimum ofes\\mathrm\{es\}over the size\-sssubsets of the candidate set, soESpool≥ES⁡\(s\)\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}\\geq\\mathrm\{ES\}\(s\)and the derived estimates are lower bounds\. Writeκ^=es⁡\(As⋆\)/ESpool\\hat\{\\kappa\}=\\mathrm\{es\}\(A\_\{s\}^\{\\star\}\)/\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}, and writec=1−ES⁡\(s\)/es⁡\(As⋆\)c=1\-\\mathrm\{ES\}\(s\)/\\mathrm\{es\}\(A\_\{s\}^\{\\star\}\)for the fraction of the gap that a subset can close, with estimatec^\\hat\{c\}usingESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}\. LetAbalA\_\{\\mathrm\{bal\}\}be the set that the balancing selector returns\. A \(layer, head\) pair, called acell, isflatwhen its median dropped mass ats=8s=8exceeds0\.250\.25\.

![Refer to caption](https://arxiv.org/html/2608.25230v1/figures/b9_ceiling_sym.png)Figure 1:Ceiling across 10 arms\.Per family and budget, the reconstruction residual is normalized so that top\-mass sits at11and dense at00\. The block is the remainderESpool/es⁡\(As⋆\)\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}/\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)that cannot be closed by any candidate subset, and the cap above it is the sharec^\\hat\{c\}that a subset can close\. The mark is the balancing selector’s residual, which sits at the floor in every cell\. SinceESpool≥ES\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}\\geq\\mathrm\{ES\}, the cap is a lower bound\. Whiskers are cluster\-bootstrap95%95\\%intervals\.Here, an instance is a sampled query row of a frozen attention head\. Four families \(Qwen2\.5\-1\.5B, our reference family, Llama\-3\.2\-1B, OLMo\-2\-1B, Qwen3\-1\.7B\), with six rows sampled per head at every layer over three documents, give111,744111\{,\}744instances ats∈\{4,8,16,32\}s\\in\\\{4,8,16,32\\\}\. We also ran a 7B arm at16,38416\{,\}384tokens \(adding56,44856\{,\}448\), and test five further arms under the same protocol\. This brings the panel to ten models over five lineages and0\.60\.6B to1414B\. We computeESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}by exhaustive enumeration and certify it with cap\-widening sweeps and an exact solver, which leave the medianc^\\hat\{c\}under0\.120\.12at every budget \(protocol and certification in App\.[B](https://arxiv.org/html/2608.25230#A2)\)\. A25×25\\timeslarger enumeration cap at the worst budget cases=32s=32, from2⋅1052\\cdot 10^\{5\}to5⋅1065\\cdot 10^\{6\}subsets and four to six keys beyondAs⋆A^\{\\star\}\_\{s\}, moves the median gap by under1%1\\%, and on the depth\-spanning head subset of that sweep the fraction withκ^\>1\.11\\hat\{\\kappa\}\>1\.11rises from35\.6%35\.6\\%to37\.8%37\.8\\%and then to38\.7%38\.7\\%, with diminishing increments\. A solver confirmed theESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}argmin globally optimal on37%37\\%of solved instances and found a materially better subset on4\.9%4\.9\\%\(every improvement tightensES\\mathrm\{ES\}\)\.

#### Penalty\.

We discover that the cost of forced weights grows with the budget\. The ratioπ⁡\(s\)=ES⁡\(s\)/EF⁡\(s\)≥1\\pi\(s\)=\\mathrm\{ES\}\(s\)/\\mathrm\{EF\}\(s\)\\geq 1analyzes forced weights against the free\-weight optimum\. On the reference family, the medianπ\\pirises from1\.071\.07to1\.791\.79and its9999th percentile from2\.22\.2to6\.86\.8asssrises from44to3232\(App\.[B\.3](https://arxiv.org/html/2608.25230#A2.SS3)\)\. Once the weights are renormalized, geometric selection also does worse than top\-mass \(Table[8](https://arxiv.org/html/2608.25230#A2.T8)\)\.

#### Selection ceiling\.

We find a medianc^\\hat\{c\}of0\.0210\.021to0\.0470\.047over eight families and all budgets, with per\-budget95%95\\%intervals inside\[0\.017,0\.051\]\[0\.017,0\.051\], rising to0\.2000\.200to0\.2540\.254on the instances withκ^\>1\.11\\hat\{\\kappa\}\>1\.11\. The share is measured against the top\-mass\-to\-dense gapes⁡\(As⋆\)\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\), since we recoverμ\\muwhen every key is kept, and it is small because large gaps are uncommon \(κ^≤1\.5\\hat\{\\kappa\}\\leq 1\.5on8989to90%90\\%of instances,κ^≤2\\hat\{\\kappa\}\\leq 2on97%97\\%ats∈\{4,8\}s\\in\\\{4,8\\\}, App\.[B](https://arxiv.org/html/2608.25230#A2)\)\. Top\-mass attainsESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}outright on39%39\\%of instances ats=4s=4and21%21\\%ats=8s=8\. We show that the balancing selector reaches this bound, recovering a median1\.001\.00of the closable gap in every family and budget \(\[1\.00,1\.00\]\[1\.00,1\.00\], Figure[1](https://arxiv.org/html/2608.25230#S2.F1)\)\. Per\-family coverage atκ^≤1\.5\\hat\{\\kappa\}\\leq 1\.5ands=4s=4spans0\.750\.75\(OLMo\-2\) to0\.950\.95\(Qwen3\-0\.6B\), and every family clears0\.910\.91atκ^≤2\\hat\{\\kappa\}\\leq 2\. Where covered, the medianκ^\\hat\{\\kappa\}is1\.001\.00to1\.031\.03and the9090th percentile is1\.141\.14to1\.281\.28; sinceκ^\\hat\{\\kappa\}is restricted to the candidate set, these are upper estimates\. We cannot search exactly at the deployeds=64s=64to256256\(Prop\.[2\.1](https://arxiv.org/html/2608.25230#S2.Thmproposition1)\), but no selector gains more thanes⁡\(As⋆\)≤2​D​m¯s\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)\\leq 2D\\bar\{m\}\_\{s\}\(Lemma[2\.1](https://arxiv.org/html/2608.25230#S2.Thmtheorem1)\), and this cap falls to a median2828to34%34\\%of itss=8s=8value ats=64s=64and88to12%12\\%ats=256s=256\. The balancing subset stays feasible and closes0\.040\.04to0\.130\.13of the gap acrosss=64s=64to256256on the two audited families, at or above itss=32s=32level, so this share lower\-boundscc\(Table[1](https://arxiv.org/html/2608.25230#S2.T1), App\.[B\.4](https://arxiv.org/html/2608.25230#A2.SS4)\)\. Thuses⁡\(As⋆\)\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)decreases withsswhile the closable fraction stays level\.

Table 1:Native budget: the median share of the top\-mass\-to\-dense gap closed by the balancing subset, which is a lower bound oncc, in one convention across all budgets \(the vertical rule marks the enumeration boundary\)\. The share holds at its small\-budget level throughs=256s=256while the gap it applies to, capped by the dropped mass \(last row, pooled\), collapses\. Balancing beats top\-mass by at least10%10\\%on2121to30%30\\%of Qwen2\.5\-1\.5B rows and4747to59%59\\%of OLMo\-2 rows across budgets\. The last row gives the remaining gap at the deployed budgets as a share of itss=8s=8value on the native\-budget records of the two audited families \(Qwen2\.5\-1\.5B/OLMo\-2\-1B, §[2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1)\)\.

### 2\.3Prediction

![Refer to caption](https://arxiv.org/html/2608.25230v1/figures/b3_map_sym.png)Figure 2:The map\.Per cell, the left panel shows the median dropped mass ats=8s=8and the right panel shows the medianκ^\\hat\{\\kappa\}from the same records\. Cell\-level AUC is0\.820\.82to0\.940\.94, and balancing closes the cells whose medianκ^\\hat\{\\kappa\}reaches1\.111\.11\. Sinceκ^≤κ\\hat\{\\kappa\}\\leq\\kappa, those cells are certain\.#### Dropped mass certificate\.

We find thatm¯s\\bar\{m\}\_\{s\}exclusively predicts whether an instance hases⁡\(As⋆\)\>0\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)\>0andκ^\>1\.11\\hat\{\\kappa\}\>1\.11, at AUC0\.760\.76to0\.850\.85on the four headline families and0\.760\.76to0\.890\.89across the ten arms\. We tested anO⁡\(N​d2\)O\(Nd^\{2\}\)spectral alternative; it performs at chance\. The published absolute bounds rankes⁡\(As⋆\)\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)at Spearman up to0\.980\.98but fall to0\.210\.21to0\.700\.70againstκ^\\hat\{\\kappa\}\(\[[34](https://arxiv.org/html/2608.25230#bib.bib36)\]\)\. The prediction replicates across content types and retrieval contexts \(Table[2](https://arxiv.org/html/2608.25230#S2.T2), App\.[B\.5](https://arxiv.org/html/2608.25230#A2.SS5)\)\. We find thatΦ=‖gAs⋆‖\\Phi=\\\|g\_\{A^\{\\star\}\_\{s\}\}\\\|of Lemma[2\.1](https://arxiv.org/html/2608.25230#S2.Thmtheorem1)is a one\-passO⁡\(N​d\)O\(Nd\)statistic and tracksESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}at Spearman0\.840\.84to0\.980\.98across budgets on the reference family and0\.800\.80to0\.980\.98pooled per family \(Tables[8](https://arxiv.org/html/2608.25230#A2.T8)and[6](https://arxiv.org/html/2608.25230#A2.T6)\)\. The mechanism follows from §[2](https://arxiv.org/html/2608.25230#S2), since a row with smallm¯s\\bar\{m\}\_\{s\}caps the selector’s gain at2​D​m¯s2D\\bar\{m\}\_\{s\}while a row with largem¯s\\bar\{m\}\_\{s\}leaves termspj​\(vj−μ\)p\_\{j\}\(v\_\{j\}\-\\mu\)that a swap cancels\. Per cell,m¯s\\bar\{m\}\_\{s\}gives the map of Figure[2](https://arxiv.org/html/2608.25230#S2.F2), and flat\-cell location is architectural, set by query\-key normalization and windowing \(per\-family edge\-to\-interior ratios in Table[6](https://arxiv.org/html/2608.25230#A2.T6)\), so we deploym¯s\\bar\{m\}\_\{s\}, since a hard\-coded edge rule fails on the query\-key normalized and windowed models\. On an H100, computingm¯s\\bar\{m\}\_\{s\}is anO⁡\(s\)O\(s\)increment on work that top\-mass selection already does, at0\.002×0\.002\\timesto0\.03×0\.03\\timesa dense attention layer acrossN=2,048N=2\{,\}048to16,38416\{,\}384\(0\.120\.12ms per layer atN=16,384N=16\{,\}384\)\.

Table 2:Content diversity on the reference family \(72,57672\{,\}576instances\)\. “share” is the fraction of instances withκ^\>1\.11\\hat\{\\kappa\}\>1\.11, and the AUC replicates across all three content types\. The headroom itself is content\-dependent, and code carries the most \(medianκ\\kappato1\.061\.06\), which is consistent with flatter attention leaving a larger tail\. Input\-level95%95\\%intervals are about±5\\pm 5percentage points on the share and±0\.01\\pm 0\.01to±0\.035\\pm 0\.035on the AUC\.
#### Task\-structured contexts\.

We registered every bound before any capture, and all of them hold on contexts built to concentrate retrieval\. The pooledc^\\hat\{c\}stays at0\.0160\.016to0\.0420\.042per budget \(registered ceiling0\.090\.09\), and the9090th percentile headroom ratio of retrieval\-critical rows against background is0\.830\.83to0\.970\.97\(ceiling22\)\. The case that needs value\-aware selection occurs on1\.87%1\.87\\%of retrieval rows ats=8s=8\(ceiling5%5\\%\), and the prediction transfers at AUC0\.750\.75to0\.800\.80\(floor0\.700\.70\)\. We test on planted needles\[[28](https://arxiv.org/html/2608.25230#bib.bib24)\], multi\-hop variable chains, and long\-document QA, assembled in token space so that needle positions are exact, with retrieval rows at least20%20\\%of instances\. The map’s cell labels \(flat and non\-flat\) hold across these contexts \(label agreement0\.900\.90to0\.930\.93, order correlation\+0\.94\+0\.94to\+0\.97\+0\.97\)\.

### 2\.4Audit

#### Deployed selectors and loss\.

The deployed selectors SnapKV, H2O, Quest and StreamingLLM sit well above the optimum at small budgets, at a median1\.41\.4to2\.12\.1timesESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}ats=8s=8against1\.021\.02to1\.031\.03for top\-mass on the three sharper families, while TOVA’s keep set is top\-mass itself \(\[[22](https://arxiv.org/html/2608.25230#bib.bib30),[41](https://arxiv.org/html/2608.25230#bib.bib15),[29](https://arxiv.org/html/2608.25230#bib.bib35),[33](https://arxiv.org/html/2608.25230#bib.bib26),[38](https://arxiv.org/html/2608.25230#bib.bib33)\]\)\. SnapKV’s error holds at1\.81\.8to2\.22\.2times the same\-budget top\-mass error through the deployed budgets;m¯s\\bar\{m\}\_\{s\}ranks each rule’s excess at Spearman0\.700\.70to0\.840\.84without query\-key normalization \(App\.[C](https://arxiv.org/html/2608.25230#A3)\)\.

Switching only the flat cells to balancing lowers held\-out continuation cross\-entropy ats=8s=8by0\.1220\.122to0\.2430\.243nats on five of the eight families \(four lineages,11B to77B, every interval below zero\)\. We measure loss in the model forward at matched budget, where each head’s attention is replaced with the restricted operatormAm\_\{A\}, and the same code reproduces the unmodified model up to floating\-point error\. The switch captures8888to98%98\\%of what all\-cell balancing achieves, and on Qwen2\.5\-7B at16,38416\{,\}384tokens the gap doubles while the same switch recovers63%63\\%of it\. Keeping each rule on non\-flat cells while switching the flat cells to balancing recovers0\.510\.51to0\.930\.93of its gap to all\-cell balancing on all nine \(selector, family\) pairs, with each paired95%95\\%interval below zero\. We discover that on the three Qwen3 scales, the map selects the wrong cells and keeps5555/1515/31%31\\%of the all\-cell gain, so it supports cell\-level conversion only, which must be measured per family\. A rank\-1616scorer trained on the query and key projections to reproduce the balancing swaps \(\[[36](https://arxiv.org/html/2608.25230#bib.bib23)\]\) recovers at most5%5\\%of the decode\-time loss reduction against a25%25\\%bar fixed in advance, because the gain sits in the value\-side residualgAg\_\{A\}, which lies outside those projections \(App\.[E](https://arxiv.org/html/2608.25230#A5)\)\. Also, the constant that converts a reconstruction gain into a loss gain varies by four orders of magnitude across families; it is smallest where reconstruction gain is largest, and it is not predicted by dropped mass \(App\.[E](https://arxiv.org/html/2608.25230#A5)\)\.

## 3Related Work

We claim that forced weights separate this problem from prior work\. Approximating a mean by a few of its points is classical\. Additionally, every near\-optimal answer re\-solves the weights on the points that it keeps\. Renormalization removes that freedom, since it only rescales the original weights\. Resampling keeps the largest weights, which is optimal only for value\-agnostic unbiased objectives \(\[[6](https://arxiv.org/html/2608.25230#bib.bib38),[8](https://arxiv.org/html/2608.25230#bib.bib12)\]\)\. Optimal design relaxes the subset to a re\-solved design measure \(\[[18](https://arxiv.org/html/2608.25230#bib.bib10)\]\)\. Coresets and recombination reweight whatever they retain \(\[[9](https://arxiv.org/html/2608.25230#bib.bib13),[26](https://arxiv.org/html/2608.25230#bib.bib27),[2](https://arxiv.org/html/2608.25230#bib.bib5)\]\)\. The attention\-discrepancy line applies vector balancing, with re\-solved weights in\[[21](https://arxiv.org/html/2608.25230#bib.bib3)\]and one uniform rescaling of the kept weights in\[[23](https://arxiv.org/html/2608.25230#bib.bib2)\]\. None of them answers which subset is best when the weights are fixed\.

In the eviction literature the objects differ in another way\. Value\-aware scores rank one decision at decode time and do not certify the set that remains \(\[[13](https://arxiv.org/html/2608.25230#bib.bib4),[14](https://arxiv.org/html/2608.25230#bib.bib39),[11](https://arxiv.org/html/2608.25230#bib.bib8)\]\), and leverage selection builds sets that already contain the high\-mass keys \(\[[17](https://arxiv.org/html/2608.25230#bib.bib20)\]\)\. Retained mass is deployed practice, which stops a budget \(\[[24](https://arxiv.org/html/2608.25230#bib.bib37)\]\) and allocates one across heads \(\[[10](https://arxiv.org/html/2608.25230#bib.bib1)\]\) without stating how far the resulting set sits from the optimum\. We supply that statement\. The nearest concurrent diagnostic works per block, so it certifies nothing per head \(\[[40](https://arxiv.org/html/2608.25230#bib.bib41)\]\)\.

On the systems side, ragged paging is being built for the storage constraint that we measure \(\[[19](https://arxiv.org/html/2608.25230#bib.bib34)\]\), and the nominal\-to\-physical memory gap is posed as an infrastructure problem \(\[[27](https://arxiv.org/html/2608.25230#bib.bib22)\]\), which we measure per method class\. The deployed compressors are audited, in particular the reconstruction\-scored class \(\[[20](https://arxiv.org/html/2608.25230#bib.bib19)\]\), the observation\-window class \(\[[22](https://arxiv.org/html/2608.25230#bib.bib30)\]\), and the strongest budget\-enforcing baseline \(\[[5](https://arxiv.org/html/2608.25230#bib.bib6)\]\)\. ContourKV reuses their importance scores with only the allocator replaced\.

## 4Deployment

#### ContourKV\.

The allocator uses one importance scorerrand one thresholdτ\\taushared by every layer and head, so the budget flows to the cells where dropped mass predicts that selection can still improve \(§[2\.3](https://arxiv.org/html/2608.25230#S2.SS3.SSS0.Px1)\)\. Each cell keeps a recency floorFFof the last3232positions plus\{j∉F:rj≥τ\}\\\{j\\notin F:r\_\{j\}\\geq\\tau\\\}, whereτ\\tauis set so that the cache averagesssentries per cell, so flat cells retain more\. We instantiaterrwith KVzip’s context\-reconstruction score \(\[[20](https://arxiv.org/html/2608.25230#bib.bib19)\]\), so the two methods differ only in the allocation, and with SnapKV’s observation\-window score \(\[[22](https://arxiv.org/html/2608.25230#bib.bib30)\]\), which needs no second pass\. Both versions are training\-free\.

#### Setup and measured memory\.

We run Llama\-3\.1\-8B\-Instruct, Qwen2\.5\-7B\-Instruct, Qwen3\-8B and Qwen3\-14B at4,0964\{,\}096to32,76832\{,\}768tokens on RULER \(\[[15](https://arxiv.org/html/2608.25230#bib.bib29)\]\) and LongBench \(\[[1](https://arxiv.org/html/2608.25230#bib.bib21)\]\), through NVIDIA’s official kvpress pipeline and its method implementations whenever they exist \(\[[7](https://arxiv.org/html/2608.25230#bib.bib18)\]\)\. The fourteen library baselines span nine uniform\-selection and five per\-head methods, with H2O added in our harness, all at the same per\-head budgetss\(roster below\)\. In the needle runs, the nine uniform\-selection methods shrink the cache to0\.240\.24to4\.3%4\.3\\%of full size, while the five per\-head methods, including KVzip, hold all of it at every length and budget, because the pipeline stores each layer’s cache as one tensor with equal slots per head and applies the selection as a mask \(their own implementations free it with ragged per\-head storage,\[[19](https://arxiv.org/html/2608.25230#bib.bib34)\]\)\. ContourKV evicts physically in both modes and holds0\.150\.15to5\.3%5\.3\\%of the cache enforced \(0\.60\.6to1\.51\.5times SnapKV’s bytes\) and4\.04\.0to96%96\\%without\. Since the benchmark setting records no bytes of its own, we replayed its contexts through the same code at the same commit \(prefill only,603603measurements per model\), without touching a score\. On the replayed benchmark documents, SnapKV and Compactor hold0\.090\.09to3\.6%3\.6\\%of the full cache while KVzip holds all of it at all5656conditions \(ratios in App\.[D](https://arxiv.org/html/2608.25230#A4)\), and enforcement caps every ContourKV head at SnapKV’s count\.

#### Compared methods\.

The compared methods are SnapKV \(\[[22](https://arxiv.org/html/2608.25230#bib.bib30)\]\), PyramidKV \(\[[4](https://arxiv.org/html/2608.25230#bib.bib25)\]\), TOVA \(\[[29](https://arxiv.org/html/2608.25230#bib.bib35)\]\), StreamingLLM \(\[[38](https://arxiv.org/html/2608.25230#bib.bib33)\]\), CriticalKV \(\[[11](https://arxiv.org/html/2608.25230#bib.bib8)\]\), Compactor \(\[[5](https://arxiv.org/html/2608.25230#bib.bib6)\]\), KVzip \(\[[20](https://arxiv.org/html/2608.25230#bib.bib19)\]\), Ada\-KV \(\[[10](https://arxiv.org/html/2608.25230#bib.bib1)\]\), ExpectedAttention \(\[[7](https://arxiv.org/html/2608.25230#bib.bib18)\]\), DuoAttention \(\[[37](https://arxiv.org/html/2608.25230#bib.bib11)\]\), and four methods shipped with the library, KNorm, KeyDiff, KVzap and FastKVzip\. Selection is uniform when every head in a layer keeps the same number of entries, and it is per head when the counts differ\. Our harness deletes per head instead, and in the benchmark setting enforcement caps each head before scoring\. The unenforced row frees memory but over\-keeps to each layer’s widest cell, so only the two enforced rows free it fully\.

KNorm prunes by key norm, KeyDiff evicts the keys closest to the layer’s mean key direction, and KVzap is a learned per\-layer scorer shipped with the library\. CompressKV is evaluated separately \(§[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px4)\)\. We configured every method to keep the same fraction of the cache,0\.10\.1to3\.4%3\.4\\%across the grid, so the methods differ only in which keys they keep\. We exclude IndexMem \(\[[39](https://arxiv.org/html/2608.25230#bib.bib16)\]\), which releases neither code nor weights, and DBTrimKV \(\[[3](https://arxiv.org/html/2608.25230#bib.bib9)\]\), whose retention gates require training and whose released checkpoints do not cover any of our four models\.

Table 3:Benchmark record: win/tie/loss for ContourKV against each opponent over paired conditions, without and with its budget enforced\.
#### Benchmark results\.

Without enforcement \(the reconstruction score\), ContourKV beats KVzip in146146of157157paired conditions and loses22, with LongBench margins of18\.118\.1to30\.330\.3points, while holding3\.53\.5to84%84\\%of the cache \(full W/T/L grid in Table[3](https://arxiv.org/html/2608.25230#S4.T3)\)\. Enforcing the budget on one fixed selection, with the ranking unchanged, lowers the score in140140of157157paired conditions and does not raise it in any—by14\.114\.1points on average on LongBenchs=32s=32, up to62\.262\.2on RULERs=128s=128\. With the budget enforced, ContourKV still beats KVzip in9393of160160conditions and loses2222at the budget\-enforcing baselines’ byte count \(sixteen at RULERs=32s=32, where KVzip’s full cache leads every budget\-enforcing method\)\. The advantage against SnapKV sits at RULERs=128s=128\(\+10\.8\+10\.8points\)\. We note that this comes from the score, since the window\-scored version ties SnapKV at equal memory and the reconstruction score costs8\.78\.7to13\.613\.6times a dense prefill \(App\.[D](https://arxiv.org/html/2608.25230#A4)\)\.

The Compactor tie \(24/96/4024/96/40\) is predicted by §[2\.2](https://arxiv.org/html/2608.25230#S2.SS2.SSS0.Px2), since both sit near the subset optimum and selection closes only a few percent of the remaining gap\. We can confirm this by reallocating the same total memory across cells by the window score \(4/133/174/133/17,0\.130\.13points below SnapKV over154154conditions\)\. The reconstruction\-scored variant was withheld when its answer\-span coverage collapsed at matched memory \(App\.[D](https://arxiv.org/html/2608.25230#A4)\)\.

CompressKV \(\[[25](https://arxiv.org/html/2608.25230#bib.bib7)\]\) is the one extreme\-compression challenger with released code\. Our port reproduces the official implementation’s selection bitwise on all328328test cases, and the one unavoidable question\-time code\-path difference moves bfloat16 scores by at most1\.22×10−41\.22\\times 10^\{\-4\}\. It matches SnapKV at matched memory \(\+0\.89\+0\.89,6060of8080tied\) at1\.031\.03to1\.131\.13times a dense prefill\. On RULERs=128s=128it trails enforced ContourKV by9\.399\.39points, in a query\-agnostic setting that is not measured by its published scores \(App\.[D](https://arxiv.org/html/2608.25230#A4)\)\.

Table 4:Retrieval: win/tie/loss for the window\-scored ContourKV with its budget enforced against each compared method over document\-paired conditions, with4848per opponent unless noted in parentheses\.Table 5:The condition decomposition of §[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px5), on eight document\-paired Llama\-3\.1\-8B cells ats∈\{64,128\}s\\in\\\{64,128\\\}\. Changes are hit\-rate points against the unmodified run, and memory is relative to the run compressed before the question\.
#### Retrieval\.

Separation appears froms=64s=64and is widest ats=128s=128on three of four models, at0\.370\.37to1\.001\.00against SnapKV’s0\.000\.00to0\.110\.11\. Ats=32s=32neither method recovers the planted fact; the fourth model, Qwen3\-14B, fails on both for reasons specific to that lineage \(per\-model records in App\.[D](https://arxiv.org/html/2608.25230#A4)\)\. Over the4848conditions the tally against SnapKV is23/23/223/23/2, and the ordering holds against the other fourteen methods at comparable bytes \(0\.820\.82times SnapKV’s ats=64s=64and1\.171\.17ats=128s=128, Table[4](https://arxiv.org/html/2608.25230#S4.T4)\)\. The kept set is chosen without reading the question, while the ranking behind it runs over question rows, because the harness evicts after the question enters the cache\. We re\-ran eight matched Llama\-3\.1\-8B conditions to price that: restricting the ranking to document rows costs88\.288\.2points of hit rate and moving eviction to the document boundary costs87\.687\.6, which is the same to within0\.60\.6points, and the allocation contributes none of it \(Table[5](https://arxiv.org/html/2608.25230#S4.T5)\)\. Although it holds1\.431\.43times the memory, the re\-run that evicts at the document boundary finishes only2\.62\.6points above the run compressed before the question, so the fall is not a memory effect\. The re\-run restricted to document rows does evict four to six of the question’s thirty\-nine rows, but that is far too few to account for an8888\-point drop\. We report the condition rather than correct for it, and it arises only where decode\-time eviction meets prefill compression, so the benchmark results are unaffected\.

#### Discussion\.

Because selection’s ceiling is this low, comparisons between eviction methods need enforced budgets and measured memory\. We have not yet shown that a rule that acts before the question arrives can reach the value\-side residual\.

## References

- \[1\]Y\. Bai, X\. Lv, J\. Zhang, H\. Lyu, J\. Tang, Z\. Huang, Z\. Du, X\. Liu, A\. Zeng, L\. Hou, Y\. Dong, J\. Tang, and J\. Li\(2024\)LongBench: a bilingual, multitask benchmark for long context understanding\.InAssociation for Computational Linguistics \(ACL\),Note:arXiv:2308\.14508Cited by:[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px2.p1.1)\.
- \[2\]S\. Barman\(2014\)Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory’s theorem\.Note:arXiv:1406\.2296External Links:1406\.2296Cited by:[§A\.1](https://arxiv.org/html/2608.25230#A1.SS1.p3.1.1),[§3](https://arxiv.org/html/2608.25230#S3.p1.1)\.
- \[3\]N\. Bui, H\. T\. Nguyen, A\. Cohan, and R\. Ying\(2026\)Make each token count: towards improving long\-context performance with KV cache eviction\.Note:arXiv:2605\.09649External Links:2605\.09649Cited by:[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p3.1)\.
- \[4\]Z\. Cai, Y\. Zhang, B\. Gao, Y\. Liu, Y\. Li, T\. Liu, K\. Lu, W\. Xiong, Y\. Dong, J\. Hu, and W\. Xiao\(2024\)PyramidKV: dynamic KV cache compression based on pyramidal information funneling\.Note:arXiv:2406\.02069External Links:2406\.02069Cited by:[§B\.6](https://arxiv.org/html/2608.25230#A2.SS6.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[5\]V\. Chari and B\. V\. Durme\(2025\)Compactor: calibrated query\-agnostic KV cache compression with approximate leverage scores\.Note:arXiv:2507\.08143External Links:2507\.08143Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p1.1),[§1](https://arxiv.org/html/2608.25230#S1.p3.1),[§3](https://arxiv.org/html/2608.25230#S3.p3.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[6\]E\. Cohen, N\. Duffield, H\. Kaplan, C\. Lund, and M\. Thorup\(2008\)Stream sampling for variance\-optimal estimation of subset sums\.Note:arXiv:0803\.0473External Links:0803\.0473Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p1.1),[§3](https://arxiv.org/html/2608.25230#S3.p1.1)\.
- \[7\]A\. Devoto, M\. Jeblick, and S\. Jégou\(2025\)Expected attention: KV cache compression by estimating attention from future queries distribution\.Note:arXiv:2510\.00636\. Library:[https://github\.com/NVIDIA/kvpress](https://github.com/NVIDIA/kvpress)External Links:2510\.00636Cited by:[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[8\]P\. Fearnhead and P\. Clifford\(2003\)On\-line inference for hidden Markov models via particle filters\.Journal of the Royal Statistical Society, Series B\.Cited by:[§3](https://arxiv.org/html/2608.25230#S3.p1.1)\.
- \[9\]D\. Feldman and M\. Langberg\(2011\)A unified framework for approximating and clustering data\.InSymposium on Theory of Computing \(STOC\),Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p1.1),[§3](https://arxiv.org/html/2608.25230#S3.p1.1)\.
- \[10\]Y\. Feng, J\. Lv, Y\. Cao, X\. Xie, and S\. K\. Zhou\(2025\)Ada\-KV: optimizing KV cache eviction by adaptive budget allocation for efficient LLM inference\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Note:arXiv:2407\.11550Cited by:[§B\.6](https://arxiv.org/html/2608.25230#A2.SS6.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2608.25230#S3.p2.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[11\]Y\. Feng, J\. Lv, H\. Guo, Y\. Cao, S\. K\. Zhou, and X\. Xie\(2026\)CriticalKV: optimizing KV cache eviction from an output perturbation perspective\.InInternational Conference on Machine Learning \(ICML\),Note:arXiv:2502\.03805Cited by:[§A\.1](https://arxiv.org/html/2608.25230#A1.SS1.p2.1.1),[§2\.1](https://arxiv.org/html/2608.25230#S2.SS1.p3.1),[§3](https://arxiv.org/html/2608.25230#S3.p2.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[12\]M\. R\. Garey and D\. S\. Johnson\(1979\)Computers and intractability: a guide to the theory of NP\-completeness\.W\. H\. Freeman\.Cited by:[§A\.2](https://arxiv.org/html/2608.25230#A1.SS2.p1.1)\.
- \[13\]R\. Goel, J\. Park, M\. Gagrani, D\. Jones, M\. Morse, H\. Langston, M\. Lee, and C\. Lott\(2025\)CAOTE: KV cache selection for LLMs via attention output error\-based token eviction\.Note:arXiv:2504\.14051External Links:2504\.14051Cited by:[§A\.1](https://arxiv.org/html/2608.25230#A1.SS1.p2.1.1),[§2\.1](https://arxiv.org/html/2608.25230#S2.SS1.p3.1),[§2\.1](https://arxiv.org/html/2608.25230#S2.SS1.p4.1),[§3](https://arxiv.org/html/2608.25230#S3.p2.1)\.
- \[14\]Z\. Guo, H\. Kamigaito, and T\. Watanabe\(2024\)Attention score is not all you need for token importance indicator in KV cache reduction: value also matters\.InEmpirical Methods in Natural Language Processing \(EMNLP\),Note:arXiv:2406\.12335Cited by:[§2\.1](https://arxiv.org/html/2608.25230#S2.SS1.p4.1),[§3](https://arxiv.org/html/2608.25230#S3.p2.1)\.
- \[15\]C\.\-P\. Hsieh, S\. Sun, S\. Kriman, S\. Acharya, D\. Rekesh, F\. Jia, Y\. Zhang, and B\. Ginsburg\(2024\)RULER: what’s the real context size of your long\-context language models?\.InFirst Conference on Language Modeling \(COLM\),Note:arXiv:2404\.06654Cited by:[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px2.p1.1)\.
- \[16\]M\. Jaggi\(2013\)Revisiting Frank\-Wolfe: projection\-free sparse convex optimization\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§B\.3](https://arxiv.org/html/2608.25230#A2.SS3.p1.1)\.
- \[17\]R\. Kannan, C\. Bhattacharyya, P\. Kacham, and D\. P\. Woodruff\(2024\)LevAttention: time, space, and streaming efficient algorithm for heavy attentions\.Note:arXiv:2410\.05462External Links:2410\.05462Cited by:[§3](https://arxiv.org/html/2608.25230#S3.p2.1)\.
- \[18\]J\. Kiefer and J\. Wolfowitz\(1960\)The equivalence of two extremum problems\.Canadian Journal of Mathematics12\.Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p1.1),[§3](https://arxiv.org/html/2608.25230#S3.p1.1)\.
- \[19\]H\. Kim, M\. Kim, H\. Kim, and J\. Choi\(2026\)Tangram: unlocking non\-uniform KV cache compression for efficient multi\-turn LLM serving\.Note:arXiv:2606\.06302External Links:2606\.06302Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p4.1),[§3](https://arxiv.org/html/2608.25230#S3.p3.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px2.p1.1)\.
- \[20\]J\.\-H\. Kim, J\. Kim, S\. Kwon, J\. W\. Lee, S\. Yun, and H\. O\. Song\(2025\)KVzip: query\-agnostic KV cache compression with context reconstruction\.Note:arXiv:2505\.23416External Links:2505\.23416Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p1.1),[§1](https://arxiv.org/html/2608.25230#S1.p3.1),[§3](https://arxiv.org/html/2608.25230#S3.p3.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[21\]E\. Kochetkova, K\. Sheth, I\. Han, A\. Zandieh, and M\. Kapralov\(2025\)Streaming attention approximation via discrepancy theory\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Note:arXiv:2502\.07861Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p1.1),[§3](https://arxiv.org/html/2608.25230#S3.p1.1)\.
- \[22\]Y\. Li, Y\. Huang, B\. Yang, B\. Venkitesh, A\. Locatelli, H\. Ye, T\. Cai, P\. Lewis, and D\. Chen\(2024\)SnapKV: LLM knows what you are looking for before generation\.Note:arXiv:2404\.14469External Links:2404\.14469Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p1.1),[§2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2608.25230#S3.p3.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[23\]E\. Liberty, A\. Andoni, and E\. Kleiner\(2026\)Nearly optimal attention coresets\.Note:arXiv:2605\.05602External Links:2605\.05602Cited by:[§3](https://arxiv.org/html/2608.25230#S3.p1.1)\.
- \[24\]C\. Lin, J\. Tang, S\. Yang, H\. Wang, T\. Tang, B\. Tian, I\. Stoica, S\. Han, and M\. Gao\(2025\)Twilight: adaptive attention sparsity with hierarchical Top\-pppruning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Note:arXiv:2502\.02770Cited by:[§3](https://arxiv.org/html/2608.25230#S3.p2.1)\.
- \[25\]X\. Lin, J\. Wang, O\. Kondrateva, Y\. Shi, B\. Li, and G\. L\. Zhang\(2025\)CompressKV: semantic retrieval heads know what tokens are not important before generation\.Note:arXiv:2508\.02401External Links:2508\.02401Cited by:[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px4.p3.1)\.
- \[26\]C\. Litterer and T\. Lyons\(2012\)High order recombination and an application to cubature on Wiener space\.Annals of Applied Probability22\(4\)\.Cited by:[§3](https://arxiv.org/html/2608.25230#S3.p1.1)\.
- \[27\]W\. Mao, Y\. Chen, W\. Huang, S\. Yang, L\. Wang, and S\. Han\(2026\)KV cache compression and its infra problems\.Note:NVIDIA Research Efficient AI blog,[https://research\.nvidia\.com/labs/eai/blogs/kv\-cache\-compression\-and\-its\-infra\-problems/](https://research.nvidia.com/labs/eai/blogs/kv-cache-compression-and-its-infra-problems/)Cited by:[§3](https://arxiv.org/html/2608.25230#S3.p3.1)\.
- \[28\]A\. Mohtashami and M\. Jaggi\(2023\)Landmark attention: random\-access infinite context length for transformers\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Note:arXiv:2305\.16300Cited by:[§2\.3](https://arxiv.org/html/2608.25230#S2.SS3.SSS0.Px2.p1.1)\.
- \[29\]M\. Oren, M\. Hassid, N\. Yarden, Y\. Adi, and R\. Schwartz\(2024\)Transformers are multi\-state RNNs\.InEmpirical Methods in Natural Language Processing \(EMNLP\),Note:arXiv:2401\.06104Cited by:[§2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[30\]R\. T\. Rockafellar\(1970\)Convex analysis\.Princeton University Press\.Cited by:[§A\.1](https://arxiv.org/html/2608.25230#A1.SS1.p3.1.1)\.
- \[31\]Z\. Shen, J\. Lu, L\. Gui, J\. Li, Y\. He, D\. Yin, and X\. Sun\(2025\)SSA: sparse sparse attention by aligning full and sparse attention outputs in feature space\.Note:arXiv:2511\.20102External Links:2511\.20102Cited by:[§2\.1](https://arxiv.org/html/2608.25230#S2.SS1.p3.1)\.
- \[32\]S\. Sun, A\. Canziani, Y\. LeCun, and J\. Zhu\(2026\)The spike, the sparse and the sink: anatomy of massive activations and attention sinks\.Note:arXiv:2603\.05498External Links:2603\.05498Cited by:[§B\.3](https://arxiv.org/html/2608.25230#A2.SS3.p1.1)\.
- \[33\]J\. Tang, Y\. Zhao, K\. Zhu, G\. Xiao, B\. Kasikci, and S\. Han\(2024\)Quest: query\-aware sparsity for efficient long\-context LLM inference\.InInternational Conference on Machine Learning \(ICML\),Note:arXiv:2406\.10774Cited by:[§2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1.p1.1)\.
- \[34\]G\. Tzachristas, L\. Deng, I\. Tzachristas, G\. Zhang, and R\. Chen\(2025\)A mathematical theory of Top\-kksparse attention via total variation distance\.Note:arXiv:2512\.07647External Links:2512\.07647Cited by:[§B\.6](https://arxiv.org/html/2608.25230#A2.SS6.SSS0.Px2.p1.1),[§2\.1](https://arxiv.org/html/2608.25230#S2.SS1.p3.1),[§2\.3](https://arxiv.org/html/2608.25230#S2.SS3.SSS0.Px1.p1.1)\.
- \[35\]R\. Vershynin\(2018\)High\-dimensional probability: an introduction with applications in data science\.Cambridge University Press\.Cited by:[§A\.1](https://arxiv.org/html/2608.25230#A1.SS1.p3.1.1)\.
- \[36\]H\. Wang, H\. Razanajato, Z\. Zhang, Y\. Yuan, and H\. Liu\(2026\)How much dense attention is necessary? oracle\-guided sparse prefill for full/GQA layers in hybrid long\-context models\.Note:arXiv:2606\.07703External Links:2606\.07703Cited by:[Appendix E](https://arxiv.org/html/2608.25230#A5.p1.1),[§2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1.p2.1)\.
- \[37\]G\. Xiao, J\. Tang, J\. Zuo, J\. Guo, S\. Yang, H\. Tang, Y\. Fu, and S\. Han\(2025\)DuoAttention: efficient long\-context LLM inference with retrieval and streaming heads\.InInternational Conference on Learning Representations \(ICLR\),Note:arXiv:2410\.10819Cited by:[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[38\]G\. Xiao, Y\. Tian, B\. Chen, S\. Han, and M\. Lewis\(2024\)Efficient streaming language models with attention sinks\.InInternational Conference on Learning Representations \(ICLR\),Note:arXiv:2309\.17453Cited by:[§2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p2.1)\.
- \[39\]X\. Yang, H\. Gu, B\. Xu, L\. Li, B\. Liu, J\. Liu, Q\. Zhu, Y\. Guo, and S\. Han\(2026\)IndexMem: learned KV\-cache eviction with latent memory for long\-context LLM inference\.InInternational Conference on Machine Learning \(ICML\),Note:arXiv:2605\.25475Cited by:[§4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px3.p3.1)\.
- \[40\]R\. Zhang, H\. Liang, D\. Chang, L\. Hu, F\. Kong, H\. Yin, and Y\. Li\(2026\)When does value\-aware KV eviction help? a fixed\-contract diagnostic for non\-monotone cache compression\.Note:arXiv:2605\.08234External Links:2605\.08234Cited by:[§3](https://arxiv.org/html/2608.25230#S3.p2.1)\.
- \[41\]Z\. Zhang, Y\. Sheng, T\. Zhou, T\. Chen, L\. Zheng, R\. Cai, Z\. Song, Y\. Tian, C\. Ré, C\. Barrett, Z\. Wang, and B\. Chen\(2023\)H2\{\}\_\{2\}O: heavy\-hitter oracle for efficient generative inference of large language models\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Note:arXiv:2306\.14048Cited by:[§1](https://arxiv.org/html/2608.25230#S1.p1.1),[§2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1.p1.1)\.

## Appendix AProofs

In this appendix, our goal is to prove Lemma[2\.1](https://arxiv.org/html/2608.25230#S2.Thmtheorem1)and Proposition[2\.1](https://arxiv.org/html/2608.25230#S2.Thmproposition1)\(stated in §[2](https://arxiv.org/html/2608.25230#S2)\)\.

### A\.1Identities

###### Proof of Lemma[2\.1](https://arxiv.org/html/2608.25230#S2.Thmtheorem1)\.

Use the law of total expectation to writeμ=p⁡\(A\)​mA\+p¯​\(A\)​mAc\\mu=p\(A\)m\_\{A\}\+\\bar\{p\}\(A\)m\_\{A^\{c\}\}, so thatμ−mA=p¯​\(A\)​\(mAc−mA\)\\mu\-m\_\{A\}=\\bar\{p\}\(A\)\(m\_\{A^\{c\}\}\-m\_\{A\}\)\. Taking norms yields the first identity\. For the second form, we have

mA−μ=\(p⁡\(A\)\)−1​∑j∈Apj​\(vj−μ\)=gAp⁡\(A\)\.m\_\{A\}\-\\mu=\(p\(A\)\)^\{\-1\}\\sum\_\{j\\in A\}p\_\{j\}\(v\_\{j\}\-\\mu\)=\\frac\{g\_\{A\}\}\{p\(A\)\}\.We know thatpj​\(vj−μ\)p\_\{j\}\(v\_\{j\}\-\\mu\)sums to 0 across alljjsince their expanded form isμ−μ=0\\mu\-\\mu=0\. Additionally, by definition of convex combination,

‖μ−mA‖≥dist⁡\(μ,conv⁡\{vj:j∈A\}\),\\\|\\mu\-m\_\{A\}\\\|\\geq\\mathrm\{dist\}\(\\mu,\\mathrm\{conv\}\\\{v\_\{j\}:j\\in A\\\}\),so we getes⁡\(A\)≥ef⁡\(A\)\\mathrm\{es\}\(A\)\\geq\\mathrm\{ef\}\(A\)\. Minimizing does not change this relation\. For the boundes⁡\(As⋆\)≤2​D​m¯s\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)\\leq 2D\\bar\{m\}\_\{s\}, note that bothmAm\_\{A\}andmAcm\_\{A^\{c\}\}are convex combinations ofvjv\_\{j\}and lie inB¯​\(μ,D\)\\bar\{B\}\(\\mu,D\), so their distance is at most2​D2D\. Applying the first form atAs⋆A^\{\\star\}\_\{s\}completes the bound\. ∎

###### Remark\.

We can recover the per\-decision eviction error of[Goel et al\. \[13\]](https://arxiv.org/html/2608.25230#bib.bib4),[Feng et al\. \[11\]](https://arxiv.org/html/2608.25230#bib.bib8)using the single\-key case\. That is, for a single dropped keyjjwe havemAc=vjm\_\{A^\{c\}\}=v\_\{j\}, and we use the first form to solve fores⁡\(A\)\\mathrm\{es\}\(A\)\. ∎

###### Proposition A\.1\.

Working inℓ2\\ell\_\{2\}, we have

EF⁡\(s\)≤σ/s≤D/s,σ2=∑jpj​‖vj−μ‖2\.\\mathrm\{EF\}\(s\)\\leq\\sigma/\\sqrt\{s\}\\leq D/\\sqrt\{s\},\\,\\,\\sigma^\{2\}=\\sum\_\{j\}p\_\{j\}\\\|v\_\{j\}\-\\mu\\\|^\{2\}\.In the worst case, this inequality is tight withEF⁡\(d\+1\)=0\\mathrm\{EF\}\(d\+1\)=0\. The minimizers are extreme points of the hull that do not depend on the masses\.

###### Proof\.

By exact Carathéodory\[[30](https://arxiv.org/html/2608.25230#bib.bib28)\],μ=𝔼⁡\[X\]\\mu=\\mathbb\{E\}\[X\]for a randomXXsupported on the points\. Averagingssindependent copies gives𝔼​‖μ−X¯s‖2=σ2/s≤D2/s\\mathbb\{E\}\\left\\lVert\\mu\-\\bar\{X\}\_\{s\}\\right\\rVert^\{2\}=\\sigma^\{2\}/s\\leq D^\{2\}/s, so at least one of thesscopies has an average withinσ/s\\sigma/\\sqrt\{s\}ofμ\\mu, using at mostssdistinct points\. Padding the set to exactlysspoints only expands the hull, soEF⁡\(s\)≤σ/s\\mathrm\{EF\}\(s\)\\leq\\sigma/\\sqrt\{s\}\. Tightness is classical\[[2](https://arxiv.org/html/2608.25230#bib.bib5),[35](https://arxiv.org/html/2608.25230#bib.bib40)\]\. Exactness ats=d\+1s=d\+1is Carathéodory\. ∎

###### Example A\.1\(Smallm¯s\\bar\{m\}\_\{s\}does not boundκ\\kappa\)\.

A small dropped mass does not make the top\-mass set near\-optimal on a given instance, becauseκ=es⁡\(As⋆\)/ES⁡\(s\)\\kappa=\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)/\\mathrm\{ES\}\(s\)is a ratio of two errors that can both be small, and the denominator can shrink faster\. A dropped\-mass prediction ofκ\\kappacan therefore only be statistical, which is what §[2\.3](https://arxiv.org/html/2608.25230#S2.SS3.SSS0.Px1)measures\.

###### Example A\.2\(Not submodular\)\.

Letd=1d=1,v=\(0,1,2,3\)v=\(0,1,2,3\), andp=\(14,14,14,14\)p=\(\\tfrac\{1\}\{4\},\\tfrac\{1\}\{4\},\\tfrac\{1\}\{4\},\\tfrac\{1\}\{4\}\), soμ=32\\mu=\\tfrac\{3\}\{2\}, and write kept sets by their points\. Adding the key at00to\{2\}\\\{2\\\}leaveses\\mathrm\{es\}at12\\tfrac\{1\}\{2\}while adding it to the superset\{1,2\}\\\{1,2\\\}raiseses\\mathrm\{es\}from00to12\\tfrac\{1\}\{2\}, so the increment grows on the superset andes\\mathrm\{es\}is not submodular\. Adding the same key to\{1\}\\\{1\\\}raiseses\\mathrm\{es\}from12\\tfrac\{1\}\{2\}to11while adding it to the superset\{1,3\}\\\{1,3\\\}lowerses\\mathrm\{es\}from12\\tfrac\{1\}\{2\}to16\\tfrac\{1\}\{6\}, so the increment shrinks andes\\mathrm\{es\}is not supermodular\.

### A\.2Hardness

Our argument follows by a reduction from thePartitionproblem, which isNP\-complete\[[12](https://arxiv.org/html/2608.25230#bib.bib14)\]: given nonnegative integersu1,…,unu\_\{1\},\\dots,u\_\{n\}, decide whether some subsetS⊆\[n\]S\\subseteq\[n\]satisfies∑i∈Sui=∑i∉Sui\\sum\_\{i\\in S\}u\_\{i\}=\\sum\_\{i\\notin S\}u\_\{i\}\. We reduce in two steps\. We first pass to the balanced variant,BalancedPartition: given an evenmmandw∈ℤ≥0mw\\in\\mathbb\{Z\}\_\{\\geq 0\}^\{\\,m\}, decide whether someAAwith\|A\|=m/2\\left\\lvert A\\right\\rvert=m/2splits the sum equally\. We then encodeBalancedPartitionintoZeroES: given a rational instance of our problem, decide whetherES⁡\(s\)=0\\mathrm\{ES\}\(s\)=0\. Instances are rational throughout, withpj∈ℚ∩\(0,1\)p\_\{j\}\\in\\mathbb\{Q\}\\cap\(0,1\)andvj∈ℚdv\_\{j\}\\in\\mathbb\{Q\}^\{d\}in binary encoding, and by Lemma[2\.1](https://arxiv.org/html/2608.25230#S2.Thmtheorem1),ES⁡\(s\)=0\\mathrm\{ES\}\(s\)=0holds exactly when some size\-sssubset hasgA=0g\_\{A\}=0\. We also use one elementary fact: over the rationals,

∑i∈Yxi=∑i∈X∖Yxi⟺∑i∈Yxi=12∑i∈Xxi\.\\sum\_\{i\\in Y\}x\_\{i\}=\\sum\_\{i\\in X\\setminus Y\}x\_\{i\}\\quad\\Longleftrightarrow\\quad\\sum\_\{i\\in Y\}x\_\{i\}=\\tfrac\{1\}\{2\}\\sum\_\{i\\in X\}x\_\{i\}\.
###### Lemma A\.3\(Zero\-padding encodes exact cardinality\)\.

Map aPartitioninstance\(n,u\)\(n,u\)to theBalancedPartitioninstance\(2​n,w\)\(2n,w\)withwi=uiw\_\{i\}=u\_\{i\}fori≤ni\\leq nandwi=0w\_\{i\}=0otherwise\. The map is polynomial\-time, and\(n,u\)\(n,u\)admits an equal split exactly when\(2​n,w\)\(2n,w\)admits a balanced one\.

###### Proof\.

WriteU=∑i≤nuiU=\\sum\_\{i\\leq n\}u\_\{i\}\. First suppose someS⊆\[n\]S\\subseteq\[n\]splits theuu\-sum equally, with\|S\|=k\\left\\lvert S\\right\\rvert=k\. By\(‡\)\(\\ddagger\)it has∑i∈Sui=U/2\\sum\_\{i\\in S\}u\_\{i\}=U/2, soA=S∪\{n\+1,…,2​n−k\}A=S\\cup\\\{n\+1,\\dots,2n\-k\\\}has\|A\|=n=m/2\\left\\lvert A\\right\\rvert=n=m/2andww\-sumU/2U/2, and\(2​n,w\)\(2n,w\)admits a balanced equal split\. Conversely, suppose someAAwith\|A\|=n\\left\\lvert A\\right\\rvert=nsplits theww\-sum equally\. Then∑i∈Awi=U/2\\sum\_\{i\\in A\}w\_\{i\}=U/2, and since the padded coordinates carry weight zero,S=A∩\[n\]S=A\\cap\[n\]splits theuu\-sum equally by\(‡\)\(\\ddagger\)\. ∎

Note thatBalancedPartitionlies inNP, since a verifier checks\|A\|=m/2\\left\\lvert A\\right\\rvert=m/2and that∑i∈Awi\\sum\_\{i\\in A\}w\_\{i\}equals half the total, so it isNP\-complete\. Given aBalancedPartitioninstance\(m,w\)\(m,w\), we construct an instance of our problem in the following way: place themmintegers on the line, one key atvi=wiv\_\{i\}=w\_\{i\}withd=1d=1, then give every key the same mass1/m1/mand set the budget tos=m/2s=m/2\. Formally,

σ⁡\(m,w\)=\(N,d,p,v,s\)=\(m,1,\(1m,…,1m\),w,m2\),\\sigma\(m,w\)=\(N,d,p,v,s\)=\\big\(m,\\,1,\\,\(\\tfrac\{1\}\{m\},\\dots,\\tfrac\{1\}\{m\}\),\\,w,\\,\\tfrac\{m\}\{2\}\\big\),a polynomial\-time map\.

###### Lemma A\.4\.

WithW=∑iwiW=\\sum\_\{i\}w\_\{i\}, the instanceσ⁡\(m,w\)\\sigma\(m,w\)hasμ=W/m\\mu=W/mand, for everyA⊆\[m\]A\\subseteq\[m\],

gA=1m2​\(m​∑i∈Awi−\|A\|​W\)\.g\_\{A\}=\\tfrac\{1\}\{m^\{2\}\}\\big\(m\\sum\_\{i\\in A\}w\_\{i\}\-\\left\\lvert A\\right\\rvert\\,W\\big\)\.At\|A\|=m/2\\left\\lvert A\\right\\rvert=m/2,gA=0g\_\{A\}=0exactly when∑i∈Awi=∑i∉Awi\\sum\_\{i\\in A\}w\_\{i\}=\\sum\_\{i\\notin A\}w\_\{i\}\.

###### Proof\.

We expandgA=∑i∈A1m​\(wi−Wm\)g\_\{A\}=\\sum\_\{i\\in A\}\\tfrac\{1\}\{m\}\(w\_\{i\}\-\\tfrac\{W\}\{m\}\)\. At\|A\|=m/2\\left\\lvert A\\right\\rvert=m/2we factor outmmand apply\(‡\)\(\\ddagger\)\. ∎

###### Lemma A\.5\.

For every instanceσ⁡\(m,w\)\\sigma\(m,w\)and everyAAwith\|A\|=m/2\\left\\lvert A\\right\\rvert=m/2, we havem2​gA∈ℤm^\{2\}g\_\{A\}\\in\\mathbb\{Z\}, sogA=0g\_\{A\}=0or\|gA\|≥m−2\\left\\lvert g\_\{A\}\\right\\rvert\\geq m^\{\-2\}\. Also,p⁡\(A\)=12p\(A\)=\\tfrac\{1\}\{2\}, soes⁡\(A\)=2​\|gA\|\\mathrm\{es\}\(A\)=2\\left\\lvert g\_\{A\}\\right\\rvert\. HenceES⁡\(N/2\)∈\{0\}∪\[2​N−2,∞\)\\mathrm\{ES\}\(N/2\)\\in\\\{0\\\}\\cup\[2N^\{\-2\},\\infty\)on every constructed instance\.

###### Proof\.

Sincewwhas integer entries,m2​gA=m​∑i∈Awi−\|A\|​Wm^\{2\}g\_\{A\}=m\\sum\_\{i\\in A\}w\_\{i\}\-\\left\\lvert A\\right\\rvert\\,Wis an integer for everyAAwith\|A\|=m/2\\left\\lvert A\\right\\rvert=m/2, sogA=0g\_\{A\}=0or\|gA\|≥m−2\\left\\lvert g\_\{A\}\\right\\rvert\\geq m^\{\-2\}\. Sincep⁡\(A\)=\|A\|/m=12p\(A\)=\\left\\lvert A\\right\\rvert/m=\\tfrac\{1\}\{2\}, Lemma[2\.1](https://arxiv.org/html/2608.25230#S2.Thmtheorem1)gives

es⁡\(A\)=\|gA\|/p⁡\(A\)=2​\|gA\|\\mathrm\{es\}\(A\)=\\left\\lvert g\_\{A\}\\right\\rvert/p\(A\)=2\\left\\lvert g\_\{A\}\\right\\rvertso eaches⁡\(A\)\\mathrm\{es\}\(A\)is00or≥2​m−2\\geq 2m^\{\-2\}\. Then,ES⁡\(m/2\)\\mathrm\{ES\}\(m/2\)is the minimum of these, so it lies in\{0\}∪\[2​N−2,∞\)\\\{0\\\}\\cup\[2N^\{\-2\},\\infty\)withN=mN=m\. ∎

###### Proof of Proposition[2\.1](https://arxiv.org/html/2608.25230#S2.Thmproposition1)\.

Given a subsetAA, a verifier checks\|A\|=s\\left\\lvert A\\right\\rvert=sand testsgA=0g\_\{A\}=0in exact rational arithmetic\. Clearing denominators turns the test intoddcomparisons of integers with zero, and these integers have bit\-length polynomial in the input size\. An instance withES⁡\(s\)=0\\mathrm\{ES\}\(s\)=0has such a subset, soZeroESlies inNP\.

Next,BalancedPartitionisNP\-complete \(Lemma[A\.3](https://arxiv.org/html/2608.25230#A1.Thmtheorem3)\), andσ\\sigmareduces it toZeroES\. IfAAis a balanced equal split, thengA=0g\_\{A\}=0by Lemma[A\.4](https://arxiv.org/html/2608.25230#A1.Thmtheorem4), soes⁡\(A\)=0\\mathrm\{es\}\(A\)=0andES⁡\(m/2\)=0\\mathrm\{ES\}\(m/2\)=0\. Conversely, ifES⁡\(m/2\)=0\\mathrm\{ES\}\(m/2\)=0, the minimum is attained, so some size\-m/2m/2subset hasgA=0g\_\{A\}=0, and by Lemma[A\.4](https://arxiv.org/html/2608.25230#A1.Thmtheorem4)that subset splits the sum equally\. Every constructed instance hasd=1d=1, uniform masses, integer points ands=N/2s=N/2\.

Now suppose an estimateE^\\widehat\{E\}satisfiesES⁡\(s\)≤E^≤f⁡\(I\)⋅ES⁡\(s\)\\mathrm\{ES\}\(s\)\\leq\\widehat\{E\}\\leq f\(I\)\\cdot\\mathrm\{ES\}\(s\)for some functionf≥1f\\geq 1\. WhenES⁡\(s\)=0\\mathrm\{ES\}\(s\)=0this forcesE^=0\\widehat\{E\}=0, and whenES⁡\(s\)\>0\\mathrm\{ES\}\(s\)\>0it forcesE^\>0\\widehat\{E\}\>0\. Accepting exactly whenE^=0\\widehat\{E\}=0therefore decidesZeroES\(ffis never evaluated\)\. Next suppose\|E^−ES⁡\(s\)\|<N−2\\left\\lvert\\widehat\{E\}\-\\mathrm\{ES\}\(s\)\\right\\rvert<N^\{\-2\}on the constructed instances\. ThereES⁡\(s\)\\mathrm\{ES\}\(s\)is either00or at least2​N−22N^\{\-2\}\(Lemma[A\.5](https://arxiv.org/html/2608.25230#A1.Thmtheorem5)\), soE^<N−2\\widehat\{E\}<N^\{\-2\}in the first case andE^\>N−2\\widehat\{E\}\>N^\{\-2\}in the second\. Accepting exactly whenE^<N−2\\widehat\{E\}<N^\{\-2\}therefore decidesZeroES\. In both cases a polynomial\-time estimate decides anNP\-complete problem, soP==NPfollows\. ∎

## Appendix BPer\-head Layer

This appendix deals with the approximation behind §[2](https://arxiv.org/html/2608.25230#S2)\. We boundESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}’s distance aboveES\\mathrm\{ES\}two ways\. A sweep of the enumeration cap admits more candidate keys and measures how much the gap changes, and an exact solver either confirms theESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}argmin or finds a better subset\. We keep track of these derived statistics:κ^bal=es⁡\(Abal\)/ESpool\\hat\{\\kappa\}\_\{\\mathrm\{bal\}\}=\\mathrm\{es\}\(A\_\{\\mathrm\{bal\}\}\)/\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}, which understates the balancing selector’s distance above the optimum because the candidate set restricts the search, andΦ=‖gAs⋆‖\\Phi=\\\|g\_\{A^\{\\star\}\_\{s\}\}\\\|of Lemma[2\.1](https://arxiv.org/html/2608.25230#S2.Thmtheorem1), which is a one\-passO⁡\(N​d\)O\(Nd\)statistic\.

### B\.1Setup

Each sampled row’s output sits within10−510^\{\-5\}of the model’s own dense forward in float32 expectation; the capture stops if any row disagrees by more than4×10−34\\times 10^\{\-3\}\. Models load in bfloat16 with eager attention, and we capture the per\-head fields\(P,V,K\)\(P,V,K\)in float32 and run all enumeration arithmetic in float64\. Prose inputs are non\-overlapping wikitext\-103 test chunks\.

The first three documents of every re\-captured family reproduce the committed records bitwise, and that slice \(111,744111\{,\}744instances\) is the primary set\. One instance is one sampled query row, lettingp=P\[i,:i\+1\]p=P\[i,\{:\}i\{\+\}1\]andv=V\[:i\+1\]v=V\[\{:\}i\{\+\}1\]\. We use budgetss∈\{4,8,16,32\}s\\in\\\{4,8,16,32\\\}, six rows per head, every layer, and twenty4,0964\{,\}096\-token documents for each headline family, Qwen2\.5\-1\.5B \(28×1228\\times 12layers×\{\}\\times\{\}heads\), Llama\-3\.2\-1B \(16×3216\\times 32\), OLMo\-2\-1B \(16×1616\\times 16\) and Qwen3\-1\.7B \(28×1628\\times 16\)\. The corpus is tokenized once\.

We further test six more arms to bring the total to ten\. Qwen3\-0\.6B, Qwen3\-4B, gemma\-2\-2b and gemma\-3\-1b\-pt run under the same protocol, and the gemma pair is captured with its deployed attention geometry \(Table[6](https://arxiv.org/html/2608.25230#A2.T6)\), so captured rows are the model’s own windowed softmax\. The scale runs cover Qwen2\.5\-7B at16,38416\{,\}384tokens \(56,44856\{,\}448instances\) through a row\-streamed capture that bit\-matches the eager path, and Qwen3\-14B at4,0964\{,\}096tokens through the same path with a validating five\-shard merge\. The content run uses prose, code and French sources \(72,57672\{,\}576instances\)\.

Table 6:The ten\-arm panel consists of the four headline families, four widening families, and two scale arms\.AUC⁡\(m¯s\)\\mathrm\{AUC\}\(\\bar\{m\}\_\{s\}\)is ats=8s=8\(document\-cluster95%95\\%intervals within±0\.008\\pm 0\.008, and the Qwen2\.5\-7B row is budget\-pooled\); “edge/int” is the rate ofκ^\>1\.11\\hat\{\\kappa\}\>1\.11at the network edges over the interior rate, with head\-cluster intervals;ρdepth\\rho\_\{\\mathrm\{depth\}\}rank\-correlates the per\-layer profiles of dropped mass and of theκ^\>1\.11\\hat\{\\kappa\}\>1\.11rate;ρ⁡\(Φ,ESpool\)\\rho\(\\Phi,\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}\)is the pooled Spearman correlation ofΦ\\PhiwithESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\};κ^bal\\hat\{\\kappa\}\_\{\\mathrm\{bal\}\}is the balancing selector’s median gap \(intervals\[1\.00,1\.00\]\[1\.00,1\.00\]; the statistic is discrete, §[2\.2](https://arxiv.org/html/2608.25230#S2.SS2.SSS0.Px2)\)\.†gemma\-2\-2b replaces QK\-norm with soft\-capping and4,0964\{,\}096\-token interleaved windows\. gemma\-3\-1b\-pt is QK\-normalized with512512\-token windows\.
### B\.2Enumeration

We note thatESpool≥ES\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}\\geq\\mathrm\{ES\}on every instance, so every gap is a lower bound, thus there are no false positives\. We evaluateES⁡\(s\)\\mathrm\{ES\}\(s\)by exhaustive enumeration over the candidate set of Definition[2\.2](https://arxiv.org/html/2608.25230#S2.Thmdefinition2)\(24/12/6/424/12/6/4keys beyondAs⋆A^\{\\star\}\_\{s\}ats=4/8/16/32s=4/8/16/32\)\. A key of small mass and small deviation moves neitherp⁡\(A\)p\(A\)normAm\_\{A\}, so it cannot loweres\\mathrm\{es\}\.

We formulateES⁡\(s\)≤τ\\mathrm\{ES\}\(s\)\\leq\\tauas a mixed\-integer second\-order\-cone feasibility problem and solve it by bisection with theESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}argmin as warm start \(SCIP,120120s per solve\), on a960960\-instance manifest sampled evenly across family, budget and dropped\-mass decile\. The improvements concentrate ats≥16s\\geq 16, with the largest at75%75\\%, and2121unsolved instances hit memory limits\.

Per instance, we find thatκ^≤1\.5\\hat\{\\kappa\}\\leq 1\.5on8989to90%90\\%of instances andκ^≤2\\hat\{\\kappa\}\\leq 2on97%97\\%, over the eight\-family grid ats∈\{4,8\}s\\in\\\{4,8\\\}\.

### B\.3Penalty

The estimateπ^=ESpool/EFFW\\hat\{\\pi\}=\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}/\\mathrm\{EF\}\_\{\\mathrm\{FW\}\}ofπ⁡\(s\)\\pi\(s\), whereEFFW\\mathrm\{EF\}\_\{\\mathrm\{FW\}\}is the Frank–Wolfe\[[16](https://arxiv.org/html/2608.25230#bib.bib17)\]estimate ofEF⁡\(s\)\\mathrm\{EF\}\(s\), has unsigned bias because its numerator and denominator are both over\-estimates\. The median ofπ^\\hat\{\\pi\}rises withm¯s​s\\bar\{m\}\_\{s\}\\sqrt\{s\}in every family\. The same statistic separates the instances withκ^\>1\.11\\hat\{\\kappa\}\>1\.11from the rest, since the rank correlation of𝟏\{κ^\>1\.11\}\\mathbf\{1\}\\\{\\hat\{\\kappa\}\>1\.11\\\}withm¯s\\bar\{m\}\_\{s\}is0\.420\.42to0\.460\.46in every family while its correlation withDDis weak and its sign is unstable across families\. One family carries massive\-activation outliers \(\[[32](https://arxiv.org/html/2608.25230#bib.bib31)\]\) that we measure at radiusD≈500D\\approx 500at its deep layers, but those layers havem¯s≈0\.07\\bar\{m\}\_\{s\}\\approx 0\.07and almost no instances withκ^\>1\.11\\hat\{\\kappa\}\>1\.11\.

LetAsgeoA^\{\\mathrm\{geo\}\}\_\{s\}be a minimizer ofef\\mathrm\{ef\}, computed by Frank–Wolfe and padded to sizesswith top\-mass keys, and letAslevA^\{\\mathrm\{lev\}\}\_\{s\}be thesskeys of largest ridge leveragekj⊤​\(K⊤​K\+λ​I\)−1​kjk\_\{j\}^\{\\top\}\(K^\{\\top\}K\+\\lambda I\)^\{\-1\}k\_\{j\}\. The median ofes⁡\(Asgeo\)/es⁡\(As⋆\)\\mathrm\{es\}\(A^\{\\mathrm\{geo\}\}\_\{s\}\)/\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)rises to2\.062\.06with budget and the median ofes⁡\(Aslev\)/es⁡\(As⋆\)\\mathrm\{es\}\(A^\{\\mathrm\{lev\}\}\_\{s\}\)/\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)rises to20\.320\.3\(Table[8](https://arxiv.org/html/2608.25230#A2.T8)\)\. The balancing selector achievesESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}at the median in every family and budget after a median of11to22swaps\. Swap costs are in the Cost paragraph below\.

### B\.4Sensitivity of Certification

Substituting the solver’s subset for theESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}argmin where improvement exists, then recomputing every statistic paired, moves the paired manifest medianc^\\hat\{c\}by at most\+0\.0063\+0\.0063\(ats=32s=32, from0\.0510\.051to0\.0570\.057\) and the medianκ^bal\\hat\{\\kappa\}\_\{\\mathrm\{bal\}\}by3×10−73\\times 10^\{\-7\}\. Because the balancing selector and the exhaustive search draw from the same candidate set, a subset outside it could beat both\. Thus, the solver searched the full key set and found4646improvements \(0/2/8/360/2/8/36by budget\)\. The median improvement is3\.8%3\.8\\%and the largest is75%75\\%\(Table[7](https://arxiv.org/html/2608.25230#A2.T7)\)\. After substitution, the fraction of instances where the found optimum beats balancing materially \(by more than1%1\\%\) rises from1\.31\.3to5\.1%5\.1\\%ats=32s=32and stays below5%5\\%elsewhere\. Because raising at most a fractionffof a sample moves its median no higher than the old\(0\.5\+f\)\(0\.5\{\+\}f\)\-quantile, the Wilson\-9595bound on each improvement rate caps the population median distribution\-free \(at most0\.1080\.108ats=32s=32\)\. The balancing median cannot move becauseκ^bal=1\\hat\{\\kappa\}\_\{\\mathrm\{bal\}\}=1exactly on87\.087\.0to94\.0%94\.0\\%of instances per budget and the worst \(family, budget\) cell has margin\+0\.17\+0\.17\. The last column of the table counts the unsolved instances as improved\.

Table 7:Certification substitution at a glance\. “improved” counts manifest instances where the solver beatESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}by more than1%1\\%;fhif\_\{\\mathrm\{hi\}\}is the Wilson\-9595upper bound on that rate; “median” is the per\-budget closable\-share median over the four audited families’ full record sets \(186,240186\{,\}240instances per budget\); the caps are the distribution\-free worst\-case medians after substitution, atfhif\_\{\\mathrm\{hi\}\}and with the2121unsolved instances also counted as improved\. The corresponding caps on the medianκ^bal\\hat\{\\kappa\}\_\{\\mathrm\{bal\}\}are1\.001\.00everywhere\.Per\-budget95%95\\%intervals on the medianc^\\hat\{c\}sit inside\[0\.017,0\.051\]\[0\.017,0\.051\]\. The fraction of the top\-mass\-to\-dense gap that a better kept set can still remove holds at its small\-budget level throughs=256s=256, even as the dropped mass falls roughly tenfold \(median\)\. At the deployed budgets the per\-family medians are0\.040\.04to0\.130\.13, and the balancing subset beats top\-mass by at least10%10\\%on2828to58%58\\%of rows\. Exact enumeration cannot reveal this since it stops ats=32s=32\. The anchor \(the balancing\-subset bound\) still applies, because whatever the balancing subset closes,1−esbal/es⁡\(As⋆\)1\-\\mathrm\{es\}\_\{\\mathrm\{bal\}\}/\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\), can also be closed by the best subset\. Table[1](https://arxiv.org/html/2608.25230#S2.T1)analyzes the bound froms=4s=4to256256on the two audited families\.

### B\.5Reference tables

Table 8:The per\-budget reference profile for the family Qwen2\.5\-1\.5B, with6,0486\{,\}048instances per budget\. “share” is the fraction withES≤0\.9​es​\(As⋆\)\\mathrm\{ES\}\\leq 0\.9\\,\\mathrm\{es\}\(A^\{\\star\}\_\{s\}\)\. The geometric column is the Frank–Wolfe support padded to sizesswith 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 runs1\.31\.3to2\.62\.6and the leverage ratio77to3232ats=32s=32\.
### B\.6Other Details

#### The allocation panel\.

Re\-allocating budget by the map raises pooled reconstruction error in every family, withΔ​es\\Delta\\mathrm\{es\}of\+0\.044\+0\.044\(Llama\-3\.2\-1B\),\+0\.144\+0\.144\(OLMo\-2\),\+0\.255\+0\.255\(Qwen2\.5\-1\.5B\) and\+1\.032\+1\.032\(Qwen3\-1\.7B\) at unit budget88under the balancing selector\. Cell\-cluster intervals exclude zero, and the sign holds at unit budget1616and under top\-mass selection\. The deltas are against uniform at matched total budget, with mass\-greedy\[[10](https://arxiv.org/html/2608.25230#bib.bib1)\]and pyramid\-shaped\[[4](https://arxiv.org/html/2608.25230#bib.bib25)\]allocators in the same panel\. A flat cell’s closable part is small \(§[2\.2](https://arxiv.org/html/2608.25230#S2.SS2.SSS0.Px2)\), so extra budget there buys little\.

#### Absolute forms\.

Both prior\-art bounds classify the label𝟏\{κ^\>1\.11\}\\mathbf\{1\}\\\{\\hat\{\\kappa\}\>1\.11\\\}worse thanm¯s\\bar\{m\}\_\{s\}alone in every family \(AUC0\.580\.58to0\.870\.87and0\.580\.58to0\.860\.86against0\.760\.76to0\.890\.89\)\. The diameter form2​D​m¯s2D\\bar\{m\}\_\{s\}and the variance refinementm¯s/\(1−m¯s\)​σ\\sqrt\{\\bar\{m\}\_\{s\}/\(1\-\\bar\{m\}\_\{s\}\)\}\\,\\sigma\[[34](https://arxiv.org/html/2608.25230#bib.bib36)\]rank the top\-mass set’s own error at Spearman0\.630\.63to0\.950\.95and0\.890\.89to0\.980\.98but fall to0\.230\.23to0\.700\.70and0\.210\.21to0\.680\.68against the gap \(barem¯s\\bar\{m\}\_\{s\}reaches0\.480\.48to0\.730\.73\)\. The family ordering ats=8s=8holds over the central margins of theκ^≥1\.00\\hat\{\\kappa\}\\geq 1\.00to1\.431\.43sweep \(Kendallτ=\+1\.0\\tau=\+1\.0\), and relabeling against the certified optima leaves per\-family AUCs at0\.720\.72to0\.870\.87, with wide intervals that overlap the committed spans\.

#### Cost\.

One balancing swap round \(192192drop\-add pairs atΘ⁡\(d\)\\Theta\(d\)\) costs about2%2\\%of the row’sQ​K⊤QK^\{\\top\}atN=4,096N=4\{,\}096, with a median of 1 to 2 swaps over the111,744111\{,\}744committed records\. The rule deploys at decode, whereμ\\muis the step’s already\-computed output and the swap is one incremental row\. As a batch prefill mask, one balancing swap round is launch\-bound at20×20\\timesto114×114\\timesa dense layer and would further needμ\\mu\(oneP​VPVmatmul,0\.31×0\.31\\timesto0\.43×0\.43\\timesdense\)\. The map costs one offline dense forward over sixteen documents and amortizes across serving\.

## Appendix CSelector Details

We score each rule’s kept set against the enumerated optimumESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}on the same111,744111\{,\}744instances as §[2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1), joined row by row to the recorded runs\. SnapKV runs with windowmax⁡\(1,min⁡\(32,s/2\)\)\\max\(1,\\min\(32,s/2\)\)and kernel77with max pooling, H2O with accumulated mass and recencys/2s/2, Quest with pages ofmax⁡\(2,s/4\)\\max\(2,s/4\)and a page\-1616configuration ats≥16s\\geq 16, and StreamingLLM withmin⁡\(4,s/2\)\\min\(4,s/2\)sinks plus recency\. TOVA’s per\-query keep set is identical to top\-mass, and this identity is checked at runtime, so we do not score it separately\. Budgets are accounted in two ways: per\-query, where a rule re\-chooses its set at every query, and cache\-faithful, where one evicted cache serves all queries, so the per\-query reading is never above the cache\-faithful one\.

![Refer to caption](https://arxiv.org/html/2608.25230v1/figures/c8_method_headroom.png)Figure 3:The left panel shows the ROC of dropped mass as a predictor of each rule’s excess label ats=8s=8on the reference family, and the right panel shows the same AUC pooled per family with95%95\\%intervals\. The grey band is the AUC range of §[2\.3](https://arxiv.org/html/2608.25230#S2.SS3.SSS0.Px1)and the dashed line is chance, and the row labeled “certificate” scoresm¯s\\bar\{m\}\_\{s\}itself\.#### Small budgets\.

Ats=8s=8the four scored rules sit at a median1\.41\.4to2\.12\.1timesESpool\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}against1\.021\.02to1\.031\.03for top\-mass on the three sharper families\. Top\-mass exceeds1\.11​ESpool1\.11\\,\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}on as few as19%19\\%of instances, while each deployed rule exceeds it on7575to99%99\\%of instances ats≤32s\\leq 32, so the label𝟏\{esmethod\>1\.11ESpool\}\\mathbf\{1\}\\\{\\mathrm\{es\}\_\{\\mathrm\{method\}\}\>1\.11\\,\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}\\\}is almost always11and its AUC, pooled across families, is0\.490\.49to0\.640\.64for mass rules and a positional control alike \(Fig\.[3](https://arxiv.org/html/2608.25230#A3.F3)\)\. At the deployed budgets the label is11on fewer instances, andm¯s\\bar\{m\}\_\{s\}predicts it, since three of the four mass\-based selectors clear AUC0\.700\.70ats=128s=128and all four clear it ats=256s=256on the reference family\. Ranking each rule’s excessesmethod/ESpool\\mathrm\{es\}\_\{\\mathrm\{method\}\}/\\mathrm\{ES\}\_\{\\mathrm\{pool\}\}bym¯s\\bar\{m\}\_\{s\}reaches Spearman0\.700\.70to0\.840\.84on the families without query\-key normalization and0\.360\.36to0\.610\.61on the two with it\. SnapKV’s error holds at1\.81\.8to2\.22\.2times the same\-budget top\-mass error through the deployed budgets\. Cache\-faithful accounting raises every rule’s median excess, to about3\.03\.0for the sequential rules and4\.24\.2for the frozen\-set SnapKV reading ats=8s=8\. Quest is evaluated below the page sizes that it was designed for \(22to88keys per page ats≤32s\\leq 32\)\. Ats∈\{64,128,256\}s\\in\\\{64,128,256\\\}exact enumeration is infeasible, so the references are top\-mass and the balancing subset, and OLMo\-2\-1B reaches AUC0\.700\.70only ats=256s=256, which is one budget later than the reference family\.

#### Held\-out loss\.

Ats=8s=8Quest increases it the least and StreamingLLM increases it the most\. Per\-query loss stays at or below cache\-faithful loss \(whenever both readings exist\)\. On Qwen3\-1\.7B the flat\-cell switch recovers0\.180\.18to0\.650\.65of the gap to all\-cell balancing, which is consistent with §[2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1)on the same family\.

## Appendix DDeployment Details

### D\.1Compared methods

The baselines ran with one all\-true mask over the compressed cache and ignored which positions remained after eviction\. The per\-layer forms mask according to the positions actually kept\. We mark every comparison that crosses the two, and the absolute levels in the baseline tables are affected\.

### D\.2Costs and uncertainty

The byte figures of §[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px2)come from per\-layer memory records in our harness\. In the replay, SnapKV and Compactor each hold between0\.090\.09and3\.6%3\.6\\%of the dense cache with identical byte counts, while KVzip holds all of it at every condition, which is2828to10781078times SnapKV’s bytes\. ContourKV without enforcement holds3\.53\.5to84%84\\%of the dense cache, or2020to9696times the budget\-enforcing methods’ bytes and a median of43\.943\.9times SnapKV’s, since the unenforced mode over\-keeps to each layer’s widest cell at1111to8585times its nominal budget\.

SnapKV and our CompressKV reimplementation each cost1\.031\.03to1\.131\.13times a dense context prefill, while ContourKV’s reconstruction score costs8\.78\.7to13\.613\.6times \(7\.7447\.744seconds against0\.6050\.605on Llama\-3\.1\-8B\), although its own method class reports22to33times for itself\.

All intervals come from one estimator, a cluster bootstrap over documents withB=1000B=1000and95%95\\%percentile intervals\. When both methods were measured in the same batch we take paired per\-document differences, and otherwise we resample the two samples independently\. Neither the resampling nor the averaging ever crosses from the benchmark setting into the retrieval one\. We treat any margin below0\.050\.05points as too small to interpret, though we still count it toward the totals by its sign\.

### D\.3Per\-condition results

ContourKV’s margins over KVzip at RULERs=128s=128run10\.410\.4to76\.476\.4points across the fourteen model and length cells, and every interval excludes zero\. ContourKV’s only losses with intervals excluding zero, against any opponent, are LongBench repobench\-p on Llama\-3\.1\-8B at both budgets \(−7\.3\-7\.3and−6\.6\-6\.6points\)\. With the budget enforced, sixteen of the twenty\-two losses to KVzip sit at RULERs=32s=32, where KVzip scores12\.612\.6to17\.617\.6from the full cache and SnapKV scores3\.63\.6to5\.55\.5\.

#### Equal\-memory allocation and retrieval\.

At RULERs=128s=128the window\-scored per\-layer variant falls13\.5513\.55points below Compactor and10\.7510\.75points below the uniform run\. In the retrieval runs, thes=64s=64record against SnapKV is7/7/17/7/1and every advantage in the4848\-condition tally falls ats≥64s\\geq 64, and the window\-scored version holds0\.820\.82times SnapKV’s bytes ats=64s=64and1\.171\.17times ats=128s=128\. The reconstruction score concentrates the budget so strongly that padding each layer’s block to its widest head consumes up to seven eighths of the memory at grouped\-query width88, and we stopped that variant when its answer\-span coverage fell5\.45\.4to31\.631\.6points below the uniform run, as the rule that we had fixed in advance required\. Qwen3\-14B fails retrieval under both the window\-scored version and SnapKV for reasons specific to that lineage\.

Our CompressKV reimplementation selects identical entries to the official implementation on all328328test cases\. Its complete record covers8080cells at exactly matched memory on Llama\-3\.1\-8B and Qwen2\.5\-7B, which are the two models that its authors provide calibration for\. It is7/47/267/47/26against ContourKV with the budget enforced \(−0\.85\-0\.85points in aggregate\), with the RULERs=128s=128block at0/0/80/0/8and−9\.39\-9\.39\. It is13/60/713/60/7against SnapKV at\+0\.89\+0\.89,15/55/1015/55/10against the per\-layer variant of §[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px4)at\+0\.79\+0\.79\[\+0\.24,\+1\.38\]\[\+0\.24,\+1\.38\], which is its one favorable comparison and is concentrated on Llama\-3\.1\-8B, and11/36/3311/36/33against Compactor, where it trails by4\.964\.96at RULERs=32s=32\(ContourKV’s own aggregate against Compactor runs−1\.9\-1\.9to\+0\.7\+0\.7\)\. Its layer allocation does not vary ats=32s=32\(a uniform3232entries per layer\) and varies ats=128s=128\(5454to169169per layer on Llama\-3\.1\-8B and6363to174174on Qwen2\.5\-7B\), so thes=32s=32comparison tests its scoring alone ands=128s=128adds its allocation, where the deficit is largest\.

## Appendix EReconstruction Boundary

The prefill probe of §[2\.4](https://arxiv.org/html/2608.25230#S2.SS4.SSS0.Px1)is a rank\-1616scorer trained on the query and key projections of Qwen2\.5\-1\.5B and Llama\-3\.2\-1B to reproduce the balancing swaps \(\[[36](https://arxiv.org/html/2608.25230#bib.bib23)\]\), and it recovers at most5%5\\%of the decode\-time loss reduction against a25%25\\%bar fixed in advance\. It is zero\-initialized, so an untrained probe selects identically to top\-mass, and it was trained on4848documents disjoint from evaluation, where the mixing weight between the probe and the top\-mass score was calibrated on half of the held\-out documents and checked on the other half\. Its held\-out swap recall is0\.330\.33and0\.390\.39, and when deployed it moves held\-out cross\-entropy ats=8s=8by\+0\.010\+0\.010and−0\.006\-0\.006, where balancing in the same run moves it by−0\.119\-0\.119and−0\.118\-0\.118\.

To test whether the map picks the right cells, we switched the same number of cells at random instead\. On Qwen2\.5\-1\.5B the map recovers94%94\\%of the all\-cell gain and the random set recovers66%66\\%, so two thirds of the map’s gain comes from set size alone; on Qwen3\-1\.7B the random set recovers77%77\\%and the map recovers15%15\\%, and no ranking of cells that we tried beat the random set \(Fig\.[4](https://arxiv.org/html/2608.25230#A5.F4)\)\. Across the three Qwen3 scales the map keeps5555/1515/31%31\\%of the all\-cell gain\. Both configurations sit far from the dense output, so the difference between their cross\-entropies is second order and is set by the local curvature\. At deployment scale, the reconstruction\-ranked per\-layer batch was withheld when its answer\-span coverage collapsed at matched memory \(§[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px4)\), and the reconstruction\-scored state of the art loses when scored at its measured bytes \(§[4](https://arxiv.org/html/2608.25230#S4.SS0.SSS0.Px2)\)\.

![Refer to caption](https://arxiv.org/html/2608.25230v1/figures/t13c_redirect_paper.png)Figure 4:Change in held\-out cross\-entropy against top\-mass ats=8s=8when balancing only the labeled cells\. The percentages give each set’s fraction of the gain from balancing all cells\.We measured the local curvature directly, from loss gradients and Hessian\-vector products at each head’s output\-projection input\. The second\-order prediction built from it matches the measured shares of the loss gain \(0\.860\.86to0\.950\.95against0\.880\.88to0\.980\.98\), and the conversion constant is the loss change per unit of flat\-cell reconstruction reduction\.