Forget Without Compromise: Nexus Sampling for Streaming KV-Cache Eviction Under Fixed Budgets

# Nexus Sampling for Streaming KV-Cache Eviction Under Fixed Budgets
Source: [https://arxiv.org/html/2606.23961](https://arxiv.org/html/2606.23961)
## Forget Without Compromise: Nexus Sampling for Streaming KV\-Cache Eviction Under Fixed Budgets

Duc DuongEqual contribution\. Contact:el72@rice\.eduandzhaozhuo\.xu@workato\.com\.Department of Computer Science, Grinnell CollegeJianwen XieLambda, IncAnshumali ShrivastavaDepartment of Computer Science, Rice UniversityZhaozhuo XuWorkato

###### Abstract

Long\-context and agentic LLM workloads push the KV cache past any fixed memory budget, forcing the inference stack to permanently*evict*tokens at every step of a continuous\-inference stream\. Existing methods all share the same template, a per\-step direct\-attention score followed by*deterministic top\-KK*selection, which converts a single below\-cutoff step into an irreversible verdict and permanently erases any subtly important token that direct attention cannot single out from noise\. To address this challenge, we proposeNexus Sampling, a training\-free eviction method that pairs*Nexus scoring*, an iterative walk over direct attention that surfaces bridge tokens, with*weighted reservoir sampling*, which retains tokens with inclusion probability in place of deterministic top\-KK\. Theoretically, we show that Nexus Sampling dominates deterministic top\-KKin long\-run survival of subtly important tokens\. Empirically, at80%80\\%KV cache eviction, Nexus Sampling matches dense attention within∼\\sim1 point on LongBench while outperforming top\-KKbaselines on retrieval\-heavy tasks, with up to10×10\\timessmaller per\-sequence cache memory\.

## 1Introduction

GPU memory imposes a hard ceiling on what an LLM inference stack can hold during long\-context generation, yet the Key\-Value \(KV\) cache grows linearly with context length and quickly exceeds this budget\[[19](https://arxiv.org/html/2606.23961#bib.bib20),[5](https://arxiv.org/html/2606.23961#bib.bib17)\]\. The gap widens further in long\-lived, agent\-style deployments such as multi\-turn assistants, persistent reasoning loops\[[18](https://arxiv.org/html/2606.23961#bib.bib21)\], and repository\-scale coding agents\[[1](https://arxiv.org/html/2606.23961#bib.bib22),[12](https://arxiv.org/html/2606.23961#bib.bib23)\], where the effective context grows toward an unbounded stream\. Sparse attention methods\[[20](https://arxiv.org/html/2606.23961#bib.bib6),[14](https://arxiv.org/html/2606.23961#bib.bib24),[24](https://arxiv.org/html/2606.23961#bib.bib9)\]address this efficiency problem partially by*reading*a still\-full cache more efficiently\. But once the cache no longer fits in memory, reading it efficiently is not enough: the inference stack must permanently*evict*tokens\. A growing body of work\[[25](https://arxiv.org/html/2606.23961#bib.bib5),[22](https://arxiv.org/html/2606.23961#bib.bib7),[3](https://arxiv.org/html/2606.23961#bib.bib10),[8](https://arxiv.org/html/2606.23961#bib.bib11),[16](https://arxiv.org/html/2606.23961#bib.bib12),[9](https://arxiv.org/html/2606.23961#bib.bib13)\]performs this*KV cache eviction*, retaining the tokens that score highest under the current \(or recent\) queries’ attention and dropping the rest\. Existing methods all share the same per\-step design as sparse attention: at every eviction step, they retain theKKhighest\-scoring tokens by*deterministic top\-KK*selection\. We argue, however, thateviction is fundamentally different from sparse attention:while sparse attention performs a one\-time read of a still\-full cache, eviction is a*streaming, fixed\-budget*problem in which tokens arrive continuously, evictions are irreversible, and the policy must repeatedly decide what to retain against future queries it has not yet seen\. Under this view, per\-step deterministic top\-KKis a suboptimal primitive: it treats each step in isolation and inherently confuses transient marginality with permanent unimportance, so a token whose score is only intermittently above the cutoff is dropped on the first marginal step, even though its long\-run average importance across steps may be high\.

Deterministic top\-KKmisses tokens whose importance fluctuates\.Per\-step importance scores in KV caches are noisy and time\-varying\. Attention in modern LLMs is heavy\-tailed\[[25](https://arxiv.org/html/2606.23961#bib.bib5),[14](https://arxiv.org/html/2606.23961#bib.bib24)\]: a small head of tokens holds most of the attention mass, while the rest of the cache sits at near\-uniform low scores where the relative ranking between tokens is dominated by noise \(Figure[1](https://arxiv.org/html/2606.23961#S1.F1)\)\. A token important to queryttmay look marginal att\+1t\\\!\+\\\!1and important again att\+10t\\\!\+\\\!10\. Top\-KK, however, treats each of these per\-step scores as a final verdict: a token that lands below the cutoff at any single step is dropped with the same finality as a token deep in the tail, regardless of how close its score was to the cutoff\. A long context produces many such verdicts, and the per\-step errors compound\. The result is*monotone marginal erosion*: every token whose score is only intermittently above the cutoff is silently and permanently lost\.

![Refer to caption](https://arxiv.org/html/2606.23961v1/attention_distribution.png)Figure 1:Attention scores are heavy\-tailed:∼\\sim80% of cumulative mass concentrates on the first∼\\sim15% of token positions \(black curve\), with a small head of high\-score tokens \(top\-left cluster\) and a long, noisy tail of marginal\-score tokens \(bottom band\) where deterministic top\-KKeviction is forced to choose between near\-identical scores\.Reservoir sampling is the streaming\-algorithms answer to this setting\.Weighted reservoir sampling\[[21](https://arxiv.org/html/2606.23961#bib.bib14),[7](https://arxiv.org/html/2606.23961#bib.bib15)\]retains each token with probability proportional to its current score, so that a token’s long\-run survival across many steps tracks its*average importance across steps*rather than collapsing on the first step where its score happens to land below the cutoff\. We believe this is the right candidate of selection primitive for KV cache eviction, but it inherits the calibration of the score it samples against\. The direct\-attention magnitude used by existing methods is, however, locally myopic: it counts only what the current query attends to, and misses what we call*bridge tokens*\- tokens that no single recent query attends to strongly, but that hold together a strongly\-connected cluster of mutually\-attended tokens across the context, such that removing one would sever the cluster’s internal connections\. Bridges are a canonical instance of marginal\-rank tokens: deterministic top\-KKevicts them at every step, even though the clusters they hold together may be highly important\. We therefore lift the reservoir’s input weight from this direct\-attention score to a*Nexus score*that surfaces bridges before any selection happens\.

We proposeNexus Sampling, a training\-free KV cache eviction method built around two new mechanisms that together address both failure modes identified above, applied uniformly across prefill and decode\. Upstream,*Nexus scoring*passes the direct\-attention score through a short iterative walk recurrence that surfaces bridge tokens before any selection happens\. Downstream,*weighted reservoir sampling*draws theKKretained tokens with inclusion probability proportional to this walk\-augmented weight, replacing the deterministic top\-KKselection step that every prior eviction method shares\. Each fix recovers a category of importance the existing template cannot see: the walk recovers bridges that direct\-attention top\-KKmisses, and the reservoir recovers the marginal\-rank tokens that any deterministic top\-KKerodes\. Theoretically, Nexus’s long\-run token survival decays as a product of per\-step inclusion probabilities \(a mean over steps\), where deterministic top\-KK’s collapses to zero on the first below\-cutoff step \(details in App\.[A](https://arxiv.org/html/2606.23961#A1)\)\. The contributions are:

- •We identify a fundamental limitation of deterministic\-top\-KKKV cache eviction: it converts transient marginality into permanent loss, producing*monotone marginal erosion*in the streaming, fixed\-budget regime that is inherent to KV cache eviction\.
- •We proposeNexus Sampling, a training\-free KV cache eviction method that applies uniformly to prefill and decode, combining weighted reservoir sampling with a*Nexus score*that surfaces*bridge tokens*, tokens anchoring strongly\-connected clusters of mutually\-attended tokens across the window\.
- •We establish theoretical guarantees showing that reservoir sampling’s long\-run token survival is a*product over steps*where deterministic top\-KK’s is a*min over steps*, and empirically demonstrate at20%20\\%density that Nexus Sampling stays within∼\\sim1 point of dense attention on LongBench while outperforming top\-KKbaselines on retrieval\-heavy long\-context tasks, with up to10×10\\timessmaller per\-sequence cache memory than dense FlashAttention\-2\.

We introduceNexus Sampling, a KV cache eviction method that runs alongside decoding: at every eviction steptt\(whenever the budget is hit during the decoding stream\), Nexus produces the retention setStS\_\{t\}via two components applied in sequence:*Nexus scoring*followed by*weighted reservoir selection*\. Nexus scoring passes the per\-block attention score through a short iterative walk recurrence that surfaces*bridge tokens*, tokens anchoring strongly\-connected clusters of mutually\-attended tokens, and yields a per\-block sampling weight𝐰\(t\)\\mathbf\{w\}^\{\(t\)\}that reflects indirect importance\. The reservoir step then draws theKKretained blocks with inclusion probability proportional to𝐰\(t\)\\mathbf\{w\}^\{\(t\)\}under the weighted\-without\-replacement law, replacing the deterministic top\-KKselection that every prior eviction method shares\. The name reflects the two roles each component plays at every step in the stream: Nexus scoring identifies the*nexus*blocks that hold a cluster together, and the reservoir*samples*from the resulting weights so that every positive\-weight block keeps positive inclusion probability rather than being deterministically condemned the first time it lands at the marginal rank\.

### 2\.1Preliminaries and Notation

Streaming view\.We treat KV cache eviction as a streaming problem over the steps of inference\. At each steptt, the LLM ingests one new queryqt∈ℝ1×Dq\_\{t\}\\in\\mathbb\{R\}^\{1\\times D\}\(a prompt token during prefill or a decoded token during decode\), attends over the current cacheKt,VtK\_\{t\},V\_\{t\}, and appends one new \(key, value\) pair, after which the cache may exceed the memory budget\. An*eviction step*occurs whenever the budget is hit: a subsetSt⊆\{1,…,Tt\}S\_\{t\}\\subseteq\\\{1,\\dots,T\_\{t\}\\\}ofBBpositions is retained, the rest are dropped, and inference continues withKSt,VStK\_\{S\_\{t\}\},V\_\{S\_\{t\}\}\. Eviction is therefore relevant in both phases: a long prompt can trigger a one\-shot eviction at the end of prefill, while a long generation produces a long stream of eviction steps throughout decode\. In both cases, eviction is irreversible: positions evicted at stepttare not recoverable at any stept′\>tt^\{\\prime\}\>t\.

Block granularity\.We work at the granularity of*key blocks*rather than individual tokens, amortizing the per\-decision cost overbbtokens \(b=32b=32\); blocks are indexed byj∈\{1,…,Nk\}j\\in\\\{1,\\dots,N\_\{k\}\\\}withNk=⌈Tk/b⌉N\_\{k\}=\\lceil T\_\{k\}/b\\rceilwhereTkT\_\{k\}is the number of cached keys\.

Per\-block base score\.Single\-query attention is noisy and dominated by the immediate token, so following standard practice\[[16](https://arxiv.org/html/2606.23961#bib.bib12),[9](https://arxiv.org/html/2606.23961#bib.bib13)\]we score blocks against a length\-WW*observation window*of recent queries𝐐∈ℝW×D\\mathbf\{Q\}\\in\\mathbb\{R\}^\{W\\times D\}on head\-averaged representations\. The per\-block*base score*𝐚∈ℝNk\\mathbf\{a\}\\in\\mathbb\{R\}^\{N\_\{k\}\}is the row average of𝐒^=rownorm⁡\(BlockSumb⁡\(softmax⁡\(𝐐𝐊⊤/D\)\)\)\\widehat\{\\mathbf\{S\}\}=\\operatorname\{rownorm\}\(\\operatorname\{BlockSum\}\_\{b\}\(\\operatorname\{softmax\}\(\\mathbf\{Q\}\\mathbf\{K\}^\{\\top\}/\\sqrt\{D\}\)\)\):

𝐚=1W​∑w=1W𝐒^w,⋅,∑jaj=1,\\mathbf\{a\}=\\tfrac\{1\}\{W\}\\textstyle\\sum\_\{w=1\}^\{W\}\\widehat\{\\mathbf\{S\}\}\_\{w,\\cdot\},\\quad\\textstyle\\sum\_\{j\}a\_\{j\}=1,\(1\)
Notation\.Throughout the rest of the section we useWWfor the observation\-window length,𝐒^∈ℝW×Nk\\widehat\{\\mathbf\{S\}\}\\in\\mathbb\{R\}^\{W\\times N\_\{k\}\}for the per\-row block distribution,𝐚∈ℝNk\\mathbf\{a\}\\in\\mathbb\{R\}^\{N\_\{k\}\}for the base score \(Eq\.[1](https://arxiv.org/html/2606.23961#S2.E1)\),𝐜∈ℝNk\\mathbf\{c\}\\in\\mathbb\{R\}^\{N\_\{k\}\}for the walk state,𝐰∈ℝNk\\mathbf\{w\}\\in\\mathbb\{R\}^\{N\_\{k\}\}for the combined sampling weight,BBfor the total retained\-block budget, andnnfor the reservoir averaging count\. A full notation table appears in App\.[A\.1](https://arxiv.org/html/2606.23961#A1.SS1)\.

![Refer to caption](https://arxiv.org/html/2606.23961v1/nexus_sampling.png)Figure 2:Overview of Nexus Sampling at one eviction step\.*Nexus scoring*\(top\) combines a direct importance term \(windowed per\-query attention\) with a bridge term obtained by an iterative walk over the same query rows\.*Streaming reservoir sampling*\(bottom\) then draws the retained blocks with inclusion probability proportional to the resulting weight, replacing the deterministic top\-KKused by every prior eviction method\.
### 2\.2Nexus Scoring

Nexus scoring assigns each block a two\-term*Nexus score*

sj=aj\+λ​c~j,s\_\{j\}=a\_\{j\}\+\\lambda\\,\\tilde\{c\}\_\{j\},\(2\)that captures both the*direct*importanceaja\_\{j\}of blockjj\(how much the recent queries attend to it\) and an*indirect*importancec~j\\tilde\{c\}\_\{j\}that measures how strongly blockjjacts as a*bridge token*, i\.e\., how strongly it anchors a cluster of mutually\-attended tokens across the window even when no single recent query attends to it strongly\. The two terms cover complementary failure modes of a single\-query attention score:aja\_\{j\}scores blocks the current query has reason to look at;c~j\\tilde\{c\}\_\{j\}scores blocks the current query has reason to*remember*, by virtue of their role in the recent context\. The mixing weightλ≥0\\lambda\\geq 0balances the two terms\.

Both terms are computed from the same per\-query rows of𝐒^\\widehat\{\\mathbf\{S\}\}\. Denote the rows by𝐚\(q\)∈ℝNk\\mathbf\{a\}^\{\(q\)\}\\in\\mathbb\{R\}^\{N\_\{k\}\}, so𝐚\(q\)=𝐒^q,⋅\\mathbf\{a\}^\{\(q\)\}=\\widehat\{\\mathbf\{S\}\}\_\{q,\\cdot\}is the block distribution of window queryqq\. The*direct*importance is the uniform row\-average,

𝐚=1W​∑q=1W𝐚\(q\),\\mathbf\{a\}\\;=\\;\\tfrac\{1\}\{W\}\\textstyle\\sum\_\{q=1\}^\{W\}\\mathbf\{a\}^\{\(q\)\},\(3\)which treats each window query as an equal vote\. The*bridge*score, by contrast, aggregates the same rows through an alignment\-weighted iterative walk\. Starting from𝐂=𝟎\\mathbf\{C\}=\\mathbf\{0\}, the walk runs forHHsteps; at each step we plug in a fresh window query row𝐚\(q\)\\mathbf\{a\}^\{\(q\)\}and update

𝐂←𝐂\+γq​𝐚\(q\),γq=1\+⟨𝐚\(q\),𝐂⟩,\\mathbf\{C\}\\;\\leftarrow\\;\\mathbf\{C\}\+\\gamma\_\{q\}\\,\\mathbf\{a\}^\{\(q\)\},\\qquad\\gamma\_\{q\}=1\+\\langle\\mathbf\{a\}^\{\(q\)\},\\,\\mathbf\{C\}\\rangle,\(4\)from which𝐜~=𝐂/‖𝐂‖1\\tilde\{\\mathbf\{c\}\}=\\mathbf\{C\}/\\\|\\mathbf\{C\}\\\|\_\{1\}\. The per\-block weight fed to the reservoir is the Nexus score plus a small recency tie\-break,

wj=sj\+εtie​rj,rj=j/\(Nk−1\),w\_\{j\}=s\_\{j\}\+\\varepsilon\_\{\\text\{tie\}\}\\,r\_\{j\},\\quad r\_\{j\}=j/\(N\_\{k\}\-1\),\(5\)withrjr\_\{j\}a linear ramp from0\(oldest block\) to11\(newest\), andεtie\\varepsilon\_\{\\text\{tie\}\}small enough that it does not flip any real signal but large enough to deterministically break ties in favor of more\-recent blocks\.

### 2\.3Weighted Reservoir Block Selection

Given the per\-block weight𝐰∈ℝNk\\mathbf\{w\}\\in\\mathbb\{R\}^\{N\_\{k\}\}from §[2\.2](https://arxiv.org/html/2606.23961#S2.SS2), the reservoir step decides whichKKof theNkN\_\{k\}blocks survive the eviction step\. The choice of selection rule here, not the choice of weight, is what distinguishes Nexus Sampling from every prior eviction method\. Following standard practice, we retain the attention\-sink block and a small recency window unconditionally; these account forBforcedB\_\{\\text\{forced\}\}slots of the total budgetBB, leavingK=B−BforcedK=B\-B\_\{\\text\{forced\}\}slots for the reservoir step below\.

nn\-averaged reservoir priority\.For every remaining candidate blockjj, we drawnnindependent uniform variatesuj\(1\),…,uj\(n\)∼𝒰​\(0,1\)u\_\{j\}^\{\(1\)\},\\dots,u\_\{j\}^\{\(n\)\}\\sim\\mathcal\{U\}\(0,1\)and form the*nn\-averaged reservoir priority*

πj=1n​∑i=1n\(uj\(i\)\)1/wj\.\\pi\_\{j\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\bigl\(u\_\{j\}^\{\(i\)\}\\bigr\)^\{1/w\_\{j\}\}\.\(6\)We then keep the topKKcandidates byπj\\pi\_\{j\}\.

## 3Why Nexus Sampling for KV Cache Eviction?

Every existing eviction method makes two implicit choices: that a token’s importance is read off from*direct*per\-step attention, and that theKKsurviving tokens are picked by*deterministic top\-KK*\. Both choices are defensible for a one\-shot prefill against a still\-dense cache, but both might break in the streaming, fixed\-budget regime that defines KV cache eviction \(§[2](https://arxiv.org/html/2606.23961#S2)\)\. Nexus Sampling replaces them with two components, Nexus scoring and weighted reservoir selection, each addressing a failure mode that the other cannot reach on its own\.

Deterministic top\-KKerases subtly important tokens at the cutoff; the reservoir preserves them\.A streaming eviction policy is applied at every step, and under deterministic top\-KKa token at rankK\+1K\\\!\+\\\!1is dropped with the same finality as a token at rank10610^\{6\}, so a token survives the firsteesteps only if its weight clears the cutoff at*every*step\. Long\-run survival is thus a min over steps and collapses to zero on the first below\-cutoff step, permanently erasing any token whose per\-step weight sits just below the cutoff, even if it is subtly important on average and would be relevant later in the stream\. Weighted reservoir sampling\[[7](https://arxiv.org/html/2606.23961#bib.bib15)\]replaces this min with a product: per\-step inclusion probability is monotone in the weight and strictly positive whenever the weight is, so long\-run survival

pj\(e\)=∏e′≤ePr⁡\(j∈top​\-​K​by​π\(e′\)\)p\_\{j\}^\{\(e\)\}\\;=\\;\\prod\_\{e^\{\\prime\}\\leq e\}\\Pr\\\!\\bigl\(j\\in\\mathrm\{top\}\\text\{\-\}K\\text\{ by \}\\pi^\{\(e^\{\\prime\}\)\}\\bigr\)stays bounded away from zero wheneverwj\(e′\)w\_\{j\}^\{\(e^\{\\prime\}\)\}does \(§[2\.3](https://arxiv.org/html/2606.23961#S2.SS3); Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1)\)\. The reservoir thus fixes the*selection rule*: it converts transient marginality into a controlled per\-step probability rather than an irreversible verdict, and exactly the subtly important tokens the deterministic rule would erase are the ones it keeps at a controlled non\-zero rate\.

Direct attention misses bridge tokens; Nexus scoring lifts them\.*Bridge tokens*are a canonical instance of the subtly important tokens above: tokens that no single recent query attends to*strongly*, but that sit at the intersection of many mutually\-attended tokens in the window and structurally hold their cluster together\. The direct score𝐚\\mathbf\{a\}is a uniform average of per\-query distributions and does not reward this structural role: a bridge typically picks up moderate mass from many queries but rarely a peak from any one, so it lands in the noisy mid\-band of the heavy\-tailed score distribution\[[25](https://arxiv.org/html/2606.23961#bib.bib5),[14](https://arxiv.org/html/2606.23961#bib.bib24)\]rather than in the head\. Even a perfect selection rule cannot recover such a token from this score, because sampling \(or top\-KK\) proportional to a weight that does not see the structural signal samples from the wrong distribution\. The bridge termc~j\\tilde\{c\}\_\{j\}in the Nexus score \(§[2\.2](https://arxiv.org/html/2606.23961#S2.SS2)\) is built precisely to extract this higher\-order signal: an iterative walk over the same per\-query rows compounds mass on tokens that successive queries*agree on*, amplifying exactly the cluster\-anchoring positions a uniform average flattens out, which we formalize as*hub amplification*\(Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)\)\. The walk thus fixes the*weight construction*: it ensures the input to selection already reflects indirect importance, so the reservoir’s preservation guarantee applies to bridges rather than to a wrong notion of importance\.

Both fixes are needed, and they compose\.The two components are not redundant; each guards against a failure mode the other cannot\. The reservoir alone cannot save bridge tokens: if they are not lifted into the head of the weight, sampling proportional to weight samples from the wrong distribution\. The walk alone cannot save subtly important tokens that still sit at the cutoff after scoring: a comprehensive per\-step weight is still terminated by deterministic top\-KKthe first time it lands below the cutoff\. Bridge tokens are recovered upstream in the weight; near\-cutoff subtly important tokens are recovered downstream in the selection; together they remove both of the implicit assumptions above\. The empirical picture in §[5](https://arxiv.org/html/2606.23961#S5)matches: existing methods do well when the score has a clear head and the relevant tokens are stably top\-ranked, and existing methods degrade on multi\-hop retrieval, long summarization, and tasks whose answer depends on subtly important tokens that the recent query does not directly attend to\.

## 4Theoretical Guarantees

The arguments of §[3](https://arxiv.org/html/2606.23961#S3)have formal counterparts\. The reservoir’s long\-run survival decays as a*product*over eviction steps where deterministic top\-KK’s collapses to zero on the first below\-cutoff step \(Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1)\), the walk*provably amplifies*hub tokens above the uniform window average \(Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)\), and the two together yield an end\-to\-end bound on per\-step eviction quality \(Proposition[4\.3](https://arxiv.org/html/2606.23961#S4.Thmtheorem3)\)\. Proofs and supporting lemmas are deferred to App\.[A](https://arxiv.org/html/2606.23961#A1)\.

###### Lemma 4\.1\(Min over steps vs\. product over steps\)\.

Consider a sequence of eviction stepse=1,…,Ee=1,\\dots,Ewith per\-step weightswj\(e\)\>0w\_\{j\}^\{\(e\)\}\>0at every step, and letw\(K\)\(e\)w\_\{\(K\)\}^\{\(e\)\}denote theKK\-th largest weight at stepee\. Then the long\-run survival probabilities of blockjjunder deterministic top\-KKand weighted reservoir sampling satisfy

Sjtop\-​K​\(E\)\\displaystyle S\_\{j\}^\{\\text\{top\-\}K\}\(E\)=∏e=1E𝟏​\[wj\(e\)≥w\(K\)\(e\)\],\\displaystyle\\;=\\;\\textstyle\\prod\_\{e=1\}^\{E\}\\mathbf\{1\}\\\!\\bigl\[w\_\{j\}^\{\(e\)\}\\geq w\_\{\(K\)\}^\{\(e\)\}\\bigr\],Sjres​\(E\)\\displaystyle S\_\{j\}^\{\\text\{res\}\}\(E\)=∏e=1Eqj\(e\),\\displaystyle\\;=\\;\\textstyle\\prod\_\{e=1\}^\{E\}q\_\{j\}^\{\(e\)\},whereqj\(e\)∈\(0,1\]q\_\{j\}^\{\(e\)\}\\in\(0,1\]is strictly positive wheneverwj\(e\)\>0w\_\{j\}^\{\(e\)\}\>0\. The first product collapses to zero as soon as any single step haswj\(e\)<w\(K\)\(e\)w\_\{j\}^\{\(e\)\}<w\_\{\(K\)\}^\{\(e\)\}; the second stays bounded away from zero as long aswj\(e\)w\_\{j\}^\{\(e\)\}does\.

Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1)formalizes the min\-vs\-product contrast from §[3](https://arxiv.org/html/2606.23961#S3): deterministic top\-KKconverts a single below\-cutoff step into an irreversible verdict, while reservoir sampling decays survival only as the product of per\-step inclusion probabilities, exactly the property that lets subtly important tokens at the cutoff have a chance to persist across a long stream\.

###### Theorem 4\.2\(Hub amplification\)\.

Assume theHHwalk\-step rows𝐚\(1\),…,𝐚\(H\)\\mathbf\{a\}^\{\(1\)\},\\dots,\\mathbf\{a\}^\{\(H\)\}are i\.i\.d\. with mean𝐚⋆\\mathbf\{a\}\_\{\\star\}and covariance𝚺\\bm\{\\Sigma\}, and define the*hub score*hj=𝚺j⊤​𝐚⋆h\_\{j\}=\\bm\{\\Sigma\}\_\{j\}^\{\\top\}\\mathbf\{a\}\_\{\\star\}\. The walk recurrence \([4](https://arxiv.org/html/2606.23961#S2.E4)\) satisfies

𝔼​\[c~j\(H\)\]=a⋆,j\+DHBH​hj\+O​\(‖𝚺‖F2\),\\mathbb\{E\}\[\\tilde\{c\}\_\{j\}^\{\(H\)\}\]\\;=\\;a\_\{\\star,j\}\\;\+\\;\\tfrac\{D\_\{H\}\}\{B\_\{H\}\}\\,h\_\{j\}\\;\+\\;O\(\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\),withBH≥HB\_\{H\}\\geq HandDH≥H​\(H−1\)/2D\_\{H\}\\geq H\(H\-1\)/2both block\-independent\. In particular,𝔼​\[c~j\(H\)\]≷a⋆,j⇔hj≷0\\mathbb\{E\}\[\\tilde\{c\}\_\{j\}^\{\(H\)\}\]\\gtrless a\_\{\\star,j\}\\iff h\_\{j\}\\gtrless 0: hub blocks are amplified above the unwalked score and peripheral blocks are attenuated\.

Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)formalizes the bridge\-recovery claim of §[3](https://arxiv.org/html/2606.23961#S3): the walk does not merely denoise the direct score, it injects a block\-dependent term proportional to the hub scorehjh\_\{j\}, which is exactly the higher\-order signal a uniform average𝐚\\mathbf\{a\}over per\-query rows cannot recover\. Because reservoir inclusion is monotone in the sampling weight \(App\.[A\.2](https://arxiv.org/html/2606.23961#A1.SS2)\), the hub amplification carries through to the selection step: bridge\-like tokens that the direct score𝐚\\mathbf\{a\}leaves in the noisy mid\-band are lifted into the head of the Nexus score, and the reservoir then keeps them at the controlled non\-zero rate of Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1)\. Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1)and Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)are component\-level guarantees on selection and scoring; we close the loop by combining them into an end\-to\-end bound on the retained\-utility error of one eviction step\. Letzj≥0z\_\{j\}\\geq 0denote the utility that blockjjwould contribute to future attention if it remained in cache \(e\.g\., its future block\-attention mass over a short horizon\)\.

###### Proposition 4\.3\(Eviction\-quality bound\)\.

Fix one eviction step and letIjI\_\{j\}be the reservoir inclusion indicator withpj=Pr⁡\(Ij=1\)p\_\{j\}=\\Pr\(I\_\{j\}=1\)\. The Horvitz–Thompson estimatorZ^HT=∑jIj​zj/pj\\widehat\{Z\}\_\{\\mathrm\{HT\}\}=\\sum\_\{j\}I\_\{j\}z\_\{j\}/p\_\{j\}is unbiased forZ=∑jzjZ=\\sum\_\{j\}z\_\{j\}, and ifpj≥pmin\>0p\_\{j\}\\geq p\_\{\\min\}\>0and0≤zj≤Zmax0\\leq z\_\{j\}\\leq Z\_\{\\max\}, then with probability≥1−δ\\geq 1\-\\delta,

\|Z^HT−Z\|≤Zmax​K​Nk/\(δ​pmin\)\.\|\\widehat\{Z\}\_\{\\mathrm\{HT\}\}\-Z\|\\;\\leq\\;Z\_\{\\max\}\\sqrt\{KN\_\{k\}/\(\\delta\\,p\_\{\\min\}\)\}\.Moreover, if the Nexus weight approximates future utility as‖𝐰−𝐳‖∞≤η\\\|\\mathbf\{w\}\-\\mathbf\{z\}\\\|\_\{\\infty\}\\leq\\eta, then the expected evicted utilityL=∑j\(1−Ij\)​zjL=\\sum\_\{j\}\(1\-I\_\{j\}\)z\_\{j\}satisfies

\|𝔼​\[L\]−∑j\(1−pj\)​wj\|≤η​Nk\.\\bigl\|\\mathbb\{E\}\[L\]\-\\textstyle\\sum\_\{j\}\(1\-p\_\{j\}\)w\_\{j\}\\bigr\|\\leq\\eta N\_\{k\}\.

Proposition[4\.3](https://arxiv.org/html/2606.23961#S4.Thmtheorem3)separates the two sources of approximation: the reservoir step \(Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1)\) contributes no systematic bias once inclusion probabilities are accounted for, so the remaining error is controlled by how well the Nexus weight𝐰\\mathbf\{w\}tracks the future utility𝐳\\mathbf\{z\}, which is precisely what the walk \(Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)\) is designed to improve over the direct score𝐚\\mathbf\{a\}\.

## 5Experiments

We evaluate Nexus Sampling on two long\-context benchmarks under two eviction regimes, comparing against competitive baselines in each regime\.

### 5\.1Setup

Models\.We evaluate three long\-context instruction\-tuned models at different scales: Llama\-3\.1\-8B\-Instruct, Llama\-3\.2\-1B\-Instruct, and Qwen3\-8B, all supporting context lengths up to 128K tokens, with the default chat template for each model\.Benchmarks\.We evaluate on two complementary long\-context benchmarks: \(i\)LongBench\[[2](https://arxiv.org/html/2606.23961#bib.bib1)\], spanning single\- and multi\-document QA, summarization, to few\-shot tasks; and \(ii\)RULER\[[10](https://arxiv.org/html/2606.23961#bib.bib2)\], a synthetic diagnostic stressing retrieval and position\-sensitive reasoning over very long contexts \(4K–64K tokens\)\. On RULER we report average accuracy across the 13\-task suite at each context length\.Baselines\.We compare Nexus Sampling againstSnapKV\[[16](https://arxiv.org/html/2606.23961#bib.bib12)\]andPyramidKV\[[3](https://arxiv.org/html/2606.23961#bib.bib10)\]in the prefill\-only setting and againstH2O\[[25](https://arxiv.org/html/2606.23961#bib.bib5)\]andMorphKV\[[9](https://arxiv.org/html/2606.23961#bib.bib13)\]in the prefill \+ decode setting, withFull Attentionas an upper\-reference\. We additionally report Ada\-KV variants \(Ada\-SnapKV, Ada\-PyramidKV\), which layer the head\-adaptive budget allocation ofFenget al\.\[[8](https://arxiv.org/html/2606.23961#bib.bib11)\]on top of each score; see Appendix[C](https://arxiv.org/html/2606.23961#A3)for the isolated comparison\. All methods are at20%20\\%density \(80% eviction\)\.

Implementation details\.We implement Nexus Sampling on top of HuggingFace Transformers, with block\-wise eviction at block sizeb=32b=32and dense attention on the retained cache served by FlashAttention\-2 kernels\[[6](https://arxiv.org/html/2606.23961#bib.bib18)\]\. Observation windowW=16W=16; walk depthH=3H=3; mixing weightλ=0\.5\\lambda=0\.5; tie\-break magnitudeεtie=10−6\\varepsilon\_\{\\text\{tie\}\}=10^\{\-6\}; reservoir averagingn=5n=5\. Because the reservoir step is stochastic, all reported numbers use a fixed random seed; then=5n=5priority averaging \(Eq\.[6](https://arxiv.org/html/2606.23961#S2.E6)\) further suppresses per\-seed variation, which we find negligible relative to the gaps in Tables[1](https://arxiv.org/html/2606.23961#S5.T1)–[2](https://arxiv.org/html/2606.23961#S5.T2)\. All experiments run on a single NVIDIA H200 \(143 GB\) with greedy decoding\.

### 5\.2LongBench Results

Table 1:LongBench accuracy at 80% KV cache eviction \(B/Nk=0\.20B/N\_\{k\}=0\.20, i\.e\.,*Density = 20%*\) across three models and 16 tasks\.*Prefill*blocks evict only during the prefill phase \(baselines: SnapKV, PyramidKV\);*Prefill \+ Decode*blocks evict throughout the entire inference stream \(baselines: H2O, MorphKV\)\.Boldmarks the leading method per row across the eviction methods \(Full Attention shown for reference\)\.ModelMethodDensityWIKIGOVHPQALCCMNewsMFQAMUSNQACOUNTRetr\.QASQMSREPOSamSTRECTRIVAvg\.*Prefill\-only eviction\.*Llama\-3\.1\-8BFull Attention100%47\.7534\.7056\.9655\.2026\.7656\.1632\.7729\.919\.6699\.5045\.0625\.3947\.8043\.2773\.0092\.1448\.50SnapKV20%47\.1728\.6958\.6155\.4223\.1955\.4431\.5330\.2810\.2599\.5040\.0324\.6048\.7542\.1768\.5091\.4347\.22PyramidKV20%47\.9628\.0757\.3353\.4622\.3756\.1132\.9730\.4910\.3399\.5042\.3624\.9047\.0242\.5371\.0091\.6847\.38Nexus Sampling20%48\.8230\.0758\.0354\.6222\.6557\.8332\.6829\.2410\.0099\.0043\.4725\.2447\.8742\.9373\.0092\.6648\.01Llama\-3\.2\-1BFull Attention100%31\.2329\.6535\.4729\.8325\.8843\.3518\.4520\.403\.674\.5016\.3521\.8436\.0439\.7761\.5078\.5431\.03SnapKV20%30\.4522\.9235\.4830\.7519\.6139\.0417\.1521\.583\.675\.0015\.0621\.1835\.8637\.4058\.0079\.3129\.53PyramidKV20%28\.4020\.2734\.8928\.6216\.9239\.9116\.1919\.633\.005\.0014\.4720\.8035\.1337\.3758\.0078\.4528\.57Nexus Sampling20%31\.8624\.5834\.5230\.7920\.9141\.8717\.5320\.755\.675\.0015\.3021\.7436\.2337\.7158\.5079\.9530\.18Qwen3\-8BFull Attention100%42\.6233\.5857\.9457\.3924\.8252\.9434\.3327\.644\.50100\.0047\.9123\.8556\.6744\.1771\.5090\.7148\.16SnapKV20%42\.3828\.7656\.9458\.0720\.2952\.7633\.9227\.966\.00100\.0043\.5523\.1756\.6043\.9066\.5090\.7146\.97PyramidKV20%39\.5626\.8755\.2555\.2418\.4448\.4831\.7826\.026\.50100\.0036\.6122\.2953\.2943\.4068\.0090\.5545\.14Nexus Sampling20%42\.4931\.7357\.6856\.9322\.1152\.5233\.7327\.445\.0099\.5043\.7223\.8956\.2343\.8571\.0091\.3647\.45*Prefill \+ decode eviction\.*Llama\-3\.1\-8BFull Attention100%47\.7534\.7056\.9655\.2026\.7656\.1632\.7729\.919\.6699\.5045\.0625\.3947\.8043\.2773\.0092\.1448\.50H2O20%48\.5228\.0556\.9752\.6722\.1753\.2432\.1429\.878\.9699\.0038\.7824\.4245\.8843\.3773\.0091\.6546\.79MorphKV20%48\.3028\.4157\.1554\.6323\.1754\.1430\.0930\.3510\.1299\.5038\.9624\.2647\.7642\.5152\.5092\.3645\.89Nexus Sampling20%48\.0629\.4457\.6153\.7422\.1556\.7832\.3730\.8910\.0099\.0041\.1625\.2346\.6442\.7570\.0092\.6247\.40Llama\-3\.2\-1BFull Attention100%31\.2329\.6535\.4729\.8325\.8843\.3518\.4520\.403\.674\.5016\.3521\.8436\.0439\.7761\.5078\.5431\.03H2O20%30\.8023\.3835\.4528\.6221\.0039\.6617\.6320\.652\.674\.5014\.6221\.1634\.6038\.9261\.5078\.5029\.60MorphKV20%28\.8923\.5833\.6428\.6921\.5134\.9516\.7819\.563\.174\.5014\.5021\.1735\.1236\.7747\.0079\.5028\.08Nexus Sampling20%30\.9724\.6334\.4130\.4620\.8141\.1617\.6221\.594\.645\.0015\.1821\.0137\.4838\.7362\.0078\.8830\.29Qwen3\-8BFull Attention100%42\.6233\.5857\.9457\.3924\.8252\.9434\.3327\.644\.50100\.0047\.9123\.8556\.6744\.1771\.5090\.7148\.16H2O20%42\.0829\.6057\.8355\.1919\.5051\.7633\.7328\.183\.50100\.0043\.7223\.2855\.1044\.8171\.5090\.7146\.91MorphKV20%40\.1529\.4455\.9657\.3620\.8850\.6631\.5127\.264\.50100\.0040\.4523\.0156\.3243\.6453\.5090\.8045\.34Nexus Sampling20%42\.3830\.8059\.2156\.7920\.6052\.1734\.1126\.965\.00100\.0043\.9523\.3156\.2943\.1070\.0091\.3647\.25

Table[1](https://arxiv.org/html/2606.23961#S5.T1)reports per\-task LongBench accuracy at 80% eviction\. In the*prefill\-only*regime, Nexus Sampling matches or exceeds SnapKV and PyramidKV on the average across all three models, recovering most of the gap to Full Attention\. In the*prefill \+ decode*regime, where eviction errors compound across decoding steps and the reservoir’s product\-over\-steps guarantee \(Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1)\) is structurally relevant, Nexus Sampling wins the average against baselines\. The gain on MultiFieldQA\-en \(MFQA\) is especially indicative of the marginal\-erosion failure mode: in the prefill \+ decode regime Nexus Sampling tops both deterministic top\-KKbaselines \(Llama\-3\.1\-8B: 56\.78 vs\. H2O 53\.24 and MorphKV 54\.14\) and matches Full Attention \(56\.16\)\. MFQA answers often hinge on a span the recent query does not strongly attend to, a subtly important token that deterministic top\-KKdrops once its score dips below the cutoff and that reservoir sampling instead keeps alive at a controlled rate\.

### 5\.3RULER Across Context Lengths

Table 2:RULER accuracy \(%\) across 4K–64K context lengths at 80% KV cache eviction\.*Prefill*blocks evict only during prefill;*Prefill \+ Decode*blocks evict throughout the entire inference stream\.Boldmarks the leading eviction method per row \(Full Attention shown for reference\)\. Qwen3\-8B supports a maximum context length of 32K, so its 64K column cannot be evaluated and is reported as “–”\.ModelMethodDensity4K8K16K32K64KAvg\.*Prefill\-only eviction\.*Llama\-3\.1\-8BFull Attention100%96\.1595\.9195\.4391\.3586\.3093\.03SnapKV20%82\.6968\.5173\.864\.4273\.3272\.55PyramidKV20%75\.0083\.6586\.3086\.3081\.9782\.64Nexus Sampling20%89\.4288\.4694\.2388\.4689\.1889\.95Llama\-3\.2\-1BFull Attention100%76\.6870\.6765\.3864\.6660\.3467\.55SnapKV20%45\.4342\.5537\.0237\.0230\.0538\.41PyramidKV20%41\.1145\.9143\.5146\.8841\.5943\.80Nexus Sampling20%58\.8961\.7856\.9763\.7061\.5460\.58Qwen3\-8BFull Attention100%97\.6095\.4388\.4692\.79–93\.57SnapKV20%70\.4967\.0173\.6179\.17–72\.57PyramidKV20%61\.5461\.0665\.1465\.38–63\.28Nexus Sampling20%77\.1683\.4180\.2982\.45–80\.83*Prefill \+ decode eviction\.*Llama\-3\.1\-8BFull Attention100%96\.1595\.9195\.4391\.3586\.3093\.03H2O20%68\.0368\.9977\.4074\.5269\.2371\.63MorphKV20%84\.6265\.3866\.8361\.3068\.2769\.28Nexus Sampling20%91\.3591\.3594\.4789\.1884\.8690\.24Llama\-3\.2\-1BFull Attention100%76\.6870\.6765\.3864\.6660\.3467\.55H2O20%36\.0633\.6535\.3440\.1537\.2636\.49MorphKV20%22\.8417\.3115\.3918\.7512\.9817\.45Nexus Sampling20%58\.8959\.1359\.1462\.9858\.8959\.81Qwen3\-8BFull Attention100%97\.6095\.4388\.4692\.79–93\.57H2O20%66\.8371\.8874\.0470\.19–70\.74MorphKV20%67\.3162\.5061\.3057\.45–62\.14Nexus Sampling20%73\.5681\.4977\.1684\.14–79\.09

Table[2](https://arxiv.org/html/2606.23961#S5.T2)reports RULER accuracy across 4K–64K context lengths\. Note that Qwen3\-8B supports a maximum context length of 32K, so we cannot evaluate it at 64K and its average is taken over the 4K–32K lengths\. Nexus Sampling is the leading eviction method in nearly every cell, with margins that grow with context length\. In*prefill\-only*, Nexus matches Full Attention within∼\\sim3 points on Llama\-3\.1\-8B on average, while SnapKV loses1515–2525points; on the smaller Llama\-3\.2\-1B the gap to SnapKV widens further \(60\.5860\.58vs\.38\.4138\.41on average\)\. In*prefill \+ decode*, the same pattern is amplified: H2O and MorphKV both sit∼\\sim20 points below Nexus at every length \(avg 71\.63 and 69\.28 vs\. Nexus 90\.24\), with MorphKV degrading further as the stream lengthens, while Nexus Sampling stays within∼\\sim1\.5 points of Full Attention on Llama\-3\.1\-8B at 64K, and on Llama\-3\.2\-1B, Nexus almost doubles the next\-best baseline \(59\.8159\.81vs\. H2O36\.4936\.49\)\. This is the empirical signature of the min\-vs\-product survival argument: on retrieval\-heavy synthetic tasks where every step’s decisions matter, deterministic top\-KKsilently erodes the relevant tokens while reservoir sampling does not\.

### 5\.4Agentic Coding

We further evaluate Nexus Sampling on an agentic coding benchmark, where the model operates as a multi\-turn coding agent over a long, growing interaction trace and is scored by*Resolved/Pass@1*on5050tasks sampled from SWE\-bench\[[12](https://arxiv.org/html/2606.23961#bib.bib23)\]\. Concretely, we use DeepSWE\-Preview\[[17](https://arxiv.org/html/2606.23961#bib.bib4)\], trained on top of Qwen3\-32B within the R2E\-Gym environment\[[11](https://arxiv.org/html/2606.23961#bib.bib3)\]\. This setting stresses eviction in two orthogonal ways\. First, we vary the*scoring scope*: in*Prefill\-only*the cache is compressed once during prefill, while in*Prefill \+ Decode*eviction runs throughout the entire generation stream\. Second, and more importantly, we vary the*eviction protocol*\. Under*Full context every turn*, the entire history is re\-prefilled at each agent turn and compression is re\-applied from scratch, so the cache is only an inference\-time approximation of full attention and evicted tokens can re\-enter on later turns; eviction is always conditioned on the current turn’s query, so it is effectively a*single\-turn*problem of deciding what is relevant to the question being answered*right now*, with full access to the history each time\. Under*True eviction*, the cache persists across turns and evicted tokens are gone permanently, making it a genuinely*multi\-turn*problem: the method must commit to keeping or discarding a token*before*knowing which later turn will need it, so it must retain information whose relevance only surfaces several turns later\. Mistakes are irreversible and compound over the agent’s lifetime\.

Table 3:Agentic coding accuracy \(*Resolved/Pass@1*over5050tasks\) at20%20\\%KV density \(80% eviction\)\.*Full context every turn*re\-prefills and re\-compresses the entire history at every agent turn \(evicted tokens can return\);*True eviction*carries a persistent cache across turns \(evicted tokens are gone for good\)\.Boldmarks the leading eviction method per block \(Dense shown for reference\)\.ScopeProtocolMethodKV densityResolved/Pass@1Prefill\-onlyFull contextevery turnDense100%12 \(24%\)SnapKV20%8 \(16%\)PyramidKV20%7 \(14%\)AdaSnapKV20%6 \(12%\)AdaPyramidKV20%6 \(12%\)Nexus Sampling20%9 \(18%\)TrueevictionDense100%12 \(24%\)SnapKV20%8 \(16%\)PyramidKV20%1 \(2%\)AdaSnapKV20%8 \(16%\)AdaPyramidKV20%1 \(2%\)Nexus Sampling20%8 \(16%\)Prefill \+ DecodeFull contextevery turnDense100%12 \(24%\)H2O20%1 \(2%\)MorphKV20%6 \(12%\)Nexus Sampling20%7 \(14%\)TrueevictionDense100%12 \(24%\)H2O20%4 \(8%\)MorphKV20%9 \(18%\)Nexus Sampling20%8 \(16%\)Table[3](https://arxiv.org/html/2606.23961#S5.T3)reports the results\. Under*Full context every turn*, Nexus Sampling leads all eviction baselines in both scoring scopes, confirming that the Nexus score is a stronger selection signal than direct attention even when no token is permanently lost\. The protocol shift to*True eviction*is where the structural differences surface: PyramidKV and AdaPyramidKV collapse from77/66to11/11once their evicted tokens can no longer be recovered, the failure mode an irreversible deterministic top\-KKverdict induces, whereas Nexus Sampling remains stable at88and matches the best baseline\. In the hardest*Prefill \+ Decode⋅\\cdotTrue eviction*setting, Nexus Sampling stays competitive at 8, one task behind MorphKV and ahead of H2O\.

### 5\.5Ablations

![Refer to caption](https://arxiv.org/html/2606.23961v1/all_ablations.png)Figure 3:Ablations of the five Nexus knobs on Llama\-3\.1\-8B at20%20\\%density, evaluated on three multi\-hop QA tasks \(HotpotQA, 2WikiMQA, MultiFieldQA\-en\)\.Nexus Sampling is robust to its hyperparameters: across walk depthHH, mixing weightλ\\lambda, observation windowWW, block sizebb, and density \(Figure[3](https://arxiv.org/html/2606.23961#S5.F3)\), the defaults of §[5\.1](https://arxiv.org/html/2606.23961#S5.SS1)sit inside a flat region on Llama\-3\.1\-8B across three multi\-hop QA tasks \(HotpotQA, 2WikiMQA, MultiFieldQA\-en\)\. First, the walk\-depth sweep saturates byH=3H=3and is indistinguishable fromH=5H=5, matching the rank\-1 propagation analysis of §[4](https://arxiv.org/html/2606.23961#S4): a few walk steps are enough to surface bridge tokens, and additional iterations only resharpen what is already there, soHHdoes not need per\-task tuning\. Second, accuracy is essentially flat from20%20\\%to80%80\\%density on all three tasks, confirming the aggressive setting we report in §[5\.2](https://arxiv.org/html/2606.23961#S5.SS2)–[5\.3](https://arxiv.org/html/2606.23961#S5.SS3)loses no accuracy headroom; this is the empirical signature of the marginal\-mass argument of §[3](https://arxiv.org/html/2606.23961#S3), where reservoir sampling preserves subtly important tokens that deterministic top\-KKwould erode rather than collapsing on the first below\-cutoff step\. Details discussion appears in App\.[B](https://arxiv.org/html/2606.23961#A2)\.

### 5\.6Inference Efficiency

We measure the two efficiency axes that long\-context eviction must improve under a fixed memory budget: decode throughput and steady\-state per\-sequence memory\. All runs use Llama\-3\.1\-8B\-Instruct in bf16 on a single H200 \(143 GB\), prefill lengthTp=8​KT\_\{p\}=8\\text\{K\}, batch size 1, against dense FlashAttention\-2\[[6](https://arxiv.org/html/2606.23961#bib.bib18)\]and the baselines from Tables[1](https://arxiv.org/html/2606.23961#S5.T1)–[2](https://arxiv.org/html/2606.23961#S5.T2)\.

Table 4:Decode throughput \(tokens/s\) and per\-step latency \(ms\) atTp=8​KT\_\{p\}=8\\text\{K\}prefill, batch size 1, on Llama\-3\.1\-8B\-Instruct \(H200, bf16\)\. Higher is better for throughput; lower is better for per\-step latency\.Boldmarks the best value per row\.DecodeDDMetricDenseSnapKVMorphKVNexusSampling4KThroughput \(tok/s,↑\\uparrow\)35\.140\.231\.445\.5Per\-step \(ms,↓\\downarrow\)28\.5324\.8531\.8422\.008KThroughput \(tok/s,↑\\uparrow\)35\.034\.229\.245\.2Per\-step \(ms,↓\\downarrow\)28\.5529\.2734\.2722\.1216KThroughput \(tok/s,↑\\uparrow\)36\.035\.032\.843\.8Per\-step \(ms,↓\\downarrow\)27\.8128\.5530\.4922\.83

Decode throughput\.Table[4](https://arxiv.org/html/2606.23961#S5.T4)reports decode\-time throughput and per\-step latency across decode lengthsD∈\{4​K,8​K,16​K\}D\\in\\\{4\\text\{K\},8\\text\{K\},16\\text\{K\}\\\}\. Nexus Sampling delivers1\.221\.22–1\.30×1\.30\\timesthroughput and1515–23%23\\%lower per\-step latency over dense FlashAttention\-2, beating both SnapKV and MorphKV at everyDD\.

Table 5:Steady\-state per\-sequence decode memory \(mempost−memafter\_load\\text\{mem\}\_\{\\text\{post\}\}\-\\text\{mem\}\_\{\\text\{after\\\_load\}\}, model weights excluded\) on Llama\-3\.1\-8B\-Instruct \(bf16, H200, batch size 1\) atTp=8​KT\_\{p\}=8\\text\{K\}\. Nexus Sampling pins the cache at a constant≈\\approx1638\-token budget regardless of decode length, so its decode memory is essentially flat inDD, while dense FlashAttention\-2 grows linearly\.Boldmarks the lower memory footprint per row\.DecodeDDDense FA\-2Nexus SamplingSaving4K1\.5 GiB0\.3 GiB5\.0×5\.0\\times8K2\.0 GiB0\.3 GiB6\.7×6\.7\\times16K3\.0 GiB0\.4 GiB7\.5×7\.5\\times32K5\.0 GiB0\.5 GiB10\.0×10\.0\\timesPer\-sequence memory\.Table[5](https://arxiv.org/html/2606.23961#S5.T5)reports the steady\-state per\-sequence decode memory \(GPU memory each sequence holds during decoding excluding model weights, which determines how many concurrent sequences fit under a fixed GPU budget\)\. Nexus Sampling saves5\.0–10\.0×5\.0\\text\{\-\-\}10\.0\\timesover dense FlashAttention\-2, with the saving growing withDDbecause the dense cache scales asTp\+DT\_\{p\}\+Dwhile Nexus pins the working cache at a constant20%20\\%density ofTpT\_\{p\}; atD=32​KD=32\\text\{K\}this10×10\\timesreduction translates into a comparable factor in achievable batch size on the same GPU\.

## 6Related Work

We situate Nexus Sampling within the broader landscape of KV cache compression and reservoir sampling\. KV cache eviction methods \(StreamingLLM\[[22](https://arxiv.org/html/2606.23961#bib.bib7)\],H2O\[[25](https://arxiv.org/html/2606.23961#bib.bib5)\],SnapKV\[[16](https://arxiv.org/html/2606.23961#bib.bib12)\],PyramidKV\[[3](https://arxiv.org/html/2606.23961#bib.bib10)\],Ada\-KV\[[8](https://arxiv.org/html/2606.23961#bib.bib11)\], andMorphKV\[[9](https://arxiv.org/html/2606.23961#bib.bib13)\]\) all reduce to different scoring strategies fed into the same deterministic top\-KKselection rule, leaving them vulnerable to the irreversible\-verdict failure mode discussed in §[3](https://arxiv.org/html/2606.23961#S3)\. Nexus Sampling is orthogonal to KV cache*selection*\(sparse attention\) methods such asQuest\[[20](https://arxiv.org/html/2606.23961#bib.bib6)\],BLASST\[[24](https://arxiv.org/html/2606.23961#bib.bib9)\], andSketch\-and\-Walk\[[14](https://arxiv.org/html/2606.23961#bib.bib24)\], and can be composed with them: eviction decides which tokens stay resident in the cache, and sparse attention then decides which of the surviving tokens to read at each step, so the two stack naturally as a memory\-side and a compute\-side compression on the same cache\. Nexus Sampling also connects to classical weighted reservoir sampling\[[4](https://arxiv.org/html/2606.23961#bib.bib16),[21](https://arxiv.org/html/2606.23961#bib.bib14),[7](https://arxiv.org/html/2606.23961#bib.bib15)\]\. See Appendix[D](https://arxiv.org/html/2606.23961#A4)for a detailed discussion of each method and its relationship to our approach\.

## 7Conclusion

We presentedNexus Sampling, a training\-free KV cache eviction method that pairs an iterative walk surfacing bridge tokens with weighted reservoir sampling, replacing the deterministic top\-KKselection that every prior eviction method shares\. Theoretically, the walk provably amplifies hub tokens above any uniform window average, and the reservoir’s long\-run survival decays as a product over eviction steps rather than collapsing on the first below\-cutoff step\. Empirically, at80%80\\%KV cache eviction, Nexus Sampling matches dense attention within∼\\sim1 point on LongBench while outperforming top\-KKbaselines on retrieval\-heavy long\-context tasks, with up to10×10\\timessmaller per\-sequence cache memory than dense FlashAttention\-2\.

Implications for agentic context\.As LLM workloads shift from one\-shot prompts toward long\-running agents, eviction moves from a one\-time cost to a continuous, lifetime\-shaping decision\. We expect that in this regime the algorithmic question of*what selection primitive to use*eclipses the question of*what scoring function to use*: existing methods already produce reasonable per\-token weights, but only a primitive that preserves marginal mass across a long stream of eviction steps, like the reservoir step at the core of Nexus Sampling, is structurally matched to a streaming\-budget setting\.

## References

- \[1\]Anthropic\(2025\)Claude Sonnet 4\.5\.Note:Anthropic model releaseCited by:[§1](https://arxiv.org/html/2606.23961#S1.p1.3)\.
- \[2\]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\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(ACL\),Cited by:[§5\.1](https://arxiv.org/html/2606.23961#S5.SS1.p1.1)\.
- \[3\]Z\. Cai, Y\. Zhang, B\. Gao, Y\. Liu, Y\. Li, T\. Liu, K\. Lu, W\. Xiong, Y\. Dong, J\. Hu, and W\. Xiao\(2025\)PyramidKV: dynamic KV cache compression based on pyramidal information funneling\.InConference on Language Modeling \(COLM\),Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p2.2),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§5\.1](https://arxiv.org/html/2606.23961#S5.SS1.p1.1),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[4\]M\.\-T\. Chao\(1982\)A general purpose unequal probability sampling plan\.Biometrika69\(3\),pp\. 653–656\.Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p3.5),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[5\]T\. Dao, D\. Y\. Fu, S\. Ermon, A\. Rudra, and C\. Ré\(2022\)FlashAttention: fast and memory\-efficient exact attention with IO\-awareness\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2606.23961#S1.p1.3)\.
- \[6\]T\. Dao\(2024\)FlashAttention\-2: faster attention with better parallelism and work partitioning\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§5\.1](https://arxiv.org/html/2606.23961#S5.SS1.p2.7),[§5\.6](https://arxiv.org/html/2606.23961#S5.SS6.p1.1)\.
- \[7\]P\. S\. Efraimidis and P\. G\. Spirakis\(2006\)Weighted random sampling with a reservoir\.Information Processing Letters97\(5\),pp\. 181–185\.Cited by:[§A\.2](https://arxiv.org/html/2606.23961#A1.SS2.1.p1.11),[Lemma A\.1](https://arxiv.org/html/2606.23961#A1.Thmtheorem1),[Appendix D](https://arxiv.org/html/2606.23961#A4.p3.5),[§1](https://arxiv.org/html/2606.23961#S1.p3.1),[§3](https://arxiv.org/html/2606.23961#S3.p2.5),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[8\]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\),Cited by:[Table 7](https://arxiv.org/html/2606.23961#A3.T7),[Table 8](https://arxiv.org/html/2606.23961#A3.T8),[Appendix C](https://arxiv.org/html/2606.23961#A3.p1.1),[Appendix D](https://arxiv.org/html/2606.23961#A4.p2.2),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§5\.1](https://arxiv.org/html/2606.23961#S5.SS1.p1.1),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[9\]R\. Ghadia, A\. Kumar, G\. Jain, P\. Nair, and P\. Das\(2025\)Dialogue without limits: constant\-sized KV caches for extended responses in LLMs\.InInternational Conference on Machine Learning \(ICML\),Cited by:[Appendix B](https://arxiv.org/html/2606.23961#A2.p4.5),[Appendix D](https://arxiv.org/html/2606.23961#A4.p2.2),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§2\.1](https://arxiv.org/html/2606.23961#S2.SS1.p3.4),[§5\.1](https://arxiv.org/html/2606.23961#S5.SS1.p1.1),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[10\]C\. 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?\.InConference on Language Modeling \(COLM\),Cited by:[§5\.1](https://arxiv.org/html/2606.23961#S5.SS1.p1.1)\.
- \[11\]N\. Jain, J\. Singh, M\. Shetty, L\. Zheng, K\. Sen, and I\. Stoica\(2025\)R2E\-Gym: procedural environments and hybrid verifiers for scaling open\-weights SWE agents\.arXiv preprint arXiv:2504\.07164\.Cited by:[§5\.4](https://arxiv.org/html/2606.23961#S5.SS4.p1.1)\.
- \[12\]C\. E\. Jimenez, J\. Yang, A\. Wettig, S\. Yao, K\. Pei, O\. Press, and K\. Narasimhan\(2024\)SWE\-bench: can language models resolve real\-world GitHub issues?\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§5\.4](https://arxiv.org/html/2606.23961#S5.SS4.p1.1)\.
- \[13\]S\. Joshi, A\. Chowdhury, W\. Bellinger, A\. Kanakamedala, E\. Singh, H\. A\. D\. Le, A\. Desai, and A\. Shrivastava\(2026\)SOCKET: SOft collision kernel Estimator for sparse attention\.arXiv preprint arXiv:2602\.06283\.Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p1.2)\.
- \[14\]H\. A\. D\. Le, S\. Joshi, Z\. Yang, Z\. Xu, and A\. Shrivastava\(2026\)Scout before you attend: sketch\-and\-walk sparse attention for efficient LLM inference\.arXiv preprint arXiv:2602\.07397\.Cited by:[§A\.6](https://arxiv.org/html/2606.23961#A1.SS6.p2.7),[Appendix D](https://arxiv.org/html/2606.23961#A4.p1.2),[Appendix D](https://arxiv.org/html/2606.23961#A4.p4.1),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§1](https://arxiv.org/html/2606.23961#S1.p2.5),[§3](https://arxiv.org/html/2606.23961#S3.p3.3),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[15\]H\. A\. D\. Le, S\. Zhong, Y\. Lu, Y\. Dou, J\. Yuan, Y\. Chuang, X\. Fan, G\. Wang, Y\. Chen, and X\. Hu\(2026\)FAFO: lossy KV cache compression for lossless inference acceleration via draftless fumble decoding\.OpenReview preprint\.Note:[https://openreview\.net/forum?id=oSk9tP5Mgs](https://openreview.net/forum?id=oSk9tP5Mgs)Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p1.2)\.
- \[16\]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\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix B](https://arxiv.org/html/2606.23961#A2.p4.5),[Appendix D](https://arxiv.org/html/2606.23961#A4.p2.2),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§2\.1](https://arxiv.org/html/2606.23961#S2.SS1.p3.4),[§5\.1](https://arxiv.org/html/2606.23961#S5.SS1.p1.1),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[17\]M\. Luo, N\. Jain, J\. Singh, S\. Tan, A\. Patel, Q\. Wu, E\. Ariyak, C\. Cai, A\. Cuadron, T\. Zhang, I\. Stoica, and K\. Sen\(2025\)DeepSWE: training a fully open\-sourced, state\-of\-the\-art coding agent by scaling rl\.Note:Notion BlogAgentica and Together AICited by:[§5\.4](https://arxiv.org/html/2606.23961#S5.SS4.p1.1)\.
- \[18\]OpenAI\(2024\)OpenAI o1 system card\.Note:Technical report, OpenAICited by:[§1](https://arxiv.org/html/2606.23961#S1.p1.3)\.
- \[19\]R\. Pope, S\. Douglas, A\. Chowdhery, J\. Devlin, J\. Bradbury, A\. Levskaya, J\. Heek, K\. Xiao, S\. Agrawal, and J\. Dean\(2023\)Efficiently scaling transformer inference\.InProceedings of Machine Learning and Systems \(MLSys\),Cited by:[§1](https://arxiv.org/html/2606.23961#S1.p1.3)\.
- \[20\]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\),Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p1.2),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[21\]J\. S\. Vitter\(1985\)Random sampling with a reservoir\.ACM Transactions on Mathematical Software11\(1\),pp\. 37–57\.Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p3.5),[§1](https://arxiv.org/html/2606.23961#S1.p3.1),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[22\]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\),Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p2.2),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[23\]J\. Yuan, H\. Liu, S\. Zhong, Y\. Chuang, S\. Li, G\. Wang, D\. Le, H\. Jin, V\. Chaudhary, Z\. Xu, Z\. Liu, and X\. Hu\(2024\)KV cache compression, but what must we give in return? A comprehensive benchmark of long context capable approaches\.InFindings of the Association for Computational Linguistics: EMNLP 2024,pp\. 4623–4648\.Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p2.2)\.
- \[24\]J\. Yuan, C\. Shinn, K\. Xu, J\. Cui, G\. Klimiashvili, G\. Xiao, P\. Zheng, B\. Li, Y\. Zhou, Z\. Ye, W\. You, T\. Zheng, D\. Brown, P\. Wang, M\. Hoehnerbach, R\. Cai, J\. Demouth, J\. D\. Owens, X\. Hu, S\. Han, T\. Liu, and H\. Mao\(2025\)BLASST: dynamic BLocked attention sparsity via softmax thresholding\.arXiv preprint arXiv:2512\.12087\.Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p1.2),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.
- \[25\]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\)H2O: heavy\-hitter oracle for efficient generative inference of large language models\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix D](https://arxiv.org/html/2606.23961#A4.p2.2),[§1](https://arxiv.org/html/2606.23961#S1.p1.3),[§1](https://arxiv.org/html/2606.23961#S1.p2.5),[§3](https://arxiv.org/html/2606.23961#S3.p3.3),[§5\.1](https://arxiv.org/html/2606.23961#S5.SS1.p1.1),[§6](https://arxiv.org/html/2606.23961#S6.p1.1)\.

## Appendix ATheoretical Analysis

This appendix gives full proofs for the three statements of §[4](https://arxiv.org/html/2606.23961#S4)\(Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1), Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2), and Proposition[4\.3](https://arxiv.org/html/2606.23961#S4.Thmtheorem3)\), together with several supporting statements that we develop only here: reservoir unbiasedness \(Lemma[A\.1](https://arxiv.org/html/2606.23961#A1.Thmtheorem1)\),nn\-averaged concentration \(Lemma[A\.2](https://arxiv.org/html/2606.23961#A1.Thmtheorem2)\), window noise reduction \(Lemma[A\.3](https://arxiv.org/html/2606.23961#A1.Thmtheorem3)\), and the walk decomposition that underlies Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)\(Lemma[A\.4](https://arxiv.org/html/2606.23961#A1.Thmtheorem4)\)\. Main\-text statements are restated verbatim \(or in a slightly expanded form when convenient for the proof\); appendix\-only statements are presented in full\.

### A\.1Notation

SymbolMeaningWWobservation window length \(recent query tokens\)𝐐∈ℝW×D\\mathbf\{Q\}\\in\\mathbb\{R\}^\{W\\times D\}trailingWWquery rows, head\-averaged𝐊∈ℝTk×D\\mathbf\{K\}\\in\\mathbb\{R\}^\{T\_\{k\}\\times D\}full key cache, head\-averagedbbtokens per key blockNk=⌈Tk/b⌉N\_\{k\}=\\lceil T\_\{k\}/b\\rceilnumber of key blocks, indexed byjj𝐏∈ℝW×Tk\\mathbf\{P\}\\in\\mathbb\{R\}^\{W\\times T\_\{k\}\}token\-level attention matrix over the observation window𝐌∈ℝW×Nk\\mathbf\{M\}\\in\\mathbb\{R\}^\{W\\times N\_\{k\}\}block\-aggregated attention;Mw,j=∑t=\(j−1\)​b\+1j​bPw,tM\_\{w,j\}=\\sum\_\{t=\(j\-1\)b\+1\}^\{jb\}P\_\{w,t\}𝐒^∈ℝW×Nk\\hat\{\\mathbf\{S\}\}\\in\\mathbb\{R\}^\{W\\times N\_\{k\}\}row\-normalized block attention;S^w,j=Mw,j/∑j′Mw,j′\\hat\{S\}\_\{w,j\}=M\_\{w,j\}/\\sum\_\{j^\{\\prime\}\}M\_\{w,j^\{\\prime\}\}𝐚\(q\)=𝐒^q,⋅\\mathbf\{a\}^\{\(q\)\}=\\hat\{\\mathbf\{S\}\}\_\{q,\\cdot\}attention distribution of query rowqq𝐚⋆=𝔼​\[𝐚\(q\)\]\\mathbf\{a\}\_\{\\star\}=\\mathbb\{E\}\[\\mathbf\{a\}^\{\(q\)\}\]population mean block\-attention distribution𝚺\\bm\{\\Sigma\}covariance matrix;Σj​k=Cov⁡\(S^q,j,S^q,k\)\\Sigma\_\{jk\}=\\operatorname\{Cov\}\(\\hat\{S\}\_\{q,j\},\\hat\{S\}\_\{q,k\}\)𝐂∈ℝNk\\mathbf\{C\}\\in\\mathbb\{R\}^\{N\_\{k\}\}hub score accumulator from the multi\-hop walkγq=1\+⟨𝐚\(q\),𝐂⟩\\gamma\_\{q\}=1\+\\langle\\mathbf\{a\}^\{\(q\)\},\\mathbf\{C\}\\rangleper\-step amplification factorhj=𝚺j⊤​𝐚⋆h\_\{j\}=\\bm\{\\Sigma\}\_\{j\}^\{\\top\}\\mathbf\{a\}\_\{\\star\}hub score of blockjj;𝚺j\\bm\{\\Sigma\}\_\{j\}is thejj\-th column of𝚺\\bm\{\\Sigma\}wjw\_\{j\}combined sampling weight \(Eq\.[5](https://arxiv.org/html/2606.23961#S2.E5)\)πj\\pi\_\{j\}reservoir priority of blockjj\(Eq\.[6](https://arxiv.org/html/2606.23961#S2.E6)\)nnreservoir averaging countKKblock retention budget after forced blocks are removedeecache\-update event index in the streaming analysisTable 6:Notation used in §[2](https://arxiv.org/html/2606.23961#S2)and Appendix[A](https://arxiv.org/html/2606.23961#A1)\.
### A\.2Reservoir Sampling: Unbiasedness and Concentration

###### Lemma A\.1\(Reservoir unbiasedness,n=1n=1;[7](https://arxiv.org/html/2606.23961#bib.bib15)\)\.

Letπj=uj1/wj\\pi\_\{j\}=u\_\{j\}^\{1/w\_\{j\}\}withuj∼𝒰​\(0,1\)u\_\{j\}\\sim\\mathcal\{U\}\(0,1\)independent, and letIj=𝟏​\{j∈𝒮\}I\_\{j\}=\\mathbf\{1\}\\\{j\\in\\mathcal\{S\}\\\}indicate whether blockjjbelongs to the top\-KKpriority set\. The selected set𝒮\\mathcal\{S\}is a probability\-proportional\-to\-size sample without replacement\. In particularpj=Pr⁡\(Ij=1\)\>0p\_\{j\}=\\Pr\(I\_\{j\}=1\)\>0wheneverwj\>0w\_\{j\}\>0,pjp\_\{j\}is monotone inwjw\_\{j\}, and for any deterministic utility vector𝐳\\mathbf\{z\},

Z^HT=∑j=1NkIj​zjpjsatisfies𝔼​\[Z^HT\]=∑j=1Nkzj\.\\widehat\{Z\}\_\{\\mathrm\{HT\}\}=\\sum\_\{j=1\}^\{N\_\{k\}\}\\frac\{I\_\{j\}z\_\{j\}\}\{p\_\{j\}\}\\quad\\text\{satisfies\}\\quad\\mathbb\{E\}\[\\widehat\{Z\}\_\{\\mathrm\{HT\}\}\]=\\sum\_\{j=1\}^\{N\_\{k\}\}z\_\{j\}\.

###### Proof\.

The priority rule ofEfraimidis and Spirakis \[[7](https://arxiv.org/html/2606.23961#bib.bib15)\]is equivalent to drawing independent exponential clocksEj=−log⁡\(uj\)/wjE\_\{j\}=\-\\log\(u\_\{j\}\)/w\_\{j\}with rateswjw\_\{j\}and taking the firstKKarrivals\. This is the standard probability\-proportional\-to\-size without\-replacement law\. Positivity follows because a positive\-rate exponential clock can arrive among the firstKKwith non\-zero probability; monotonicity follows by coupling two clocks with the sameuju\_\{j\}, sinceuj1/wju\_\{j\}^\{1/w\_\{j\}\}increases withwjw\_\{j\}\(equivalently,−log⁡\(uj\)/wj\-\\log\(u\_\{j\}\)/w\_\{j\}decreases withwjw\_\{j\}\)\. The Horvitz–Thompson identity is immediate:𝔼​\[Ij​zj/pj\]=zj\\mathbb\{E\}\[I\_\{j\}z\_\{j\}/p\_\{j\}\]=z\_\{j\}for eachjj, and summing over blocks gives the claim\. ∎

The statement above is intentionally phrased in terms of inclusion probabilitiespjp\_\{j\}rather than the simplified formulaK​wj/∑j′wj′Kw\_\{j\}/\\sum\_\{j^\{\\prime\}\}w\_\{j^\{\\prime\}\}\. For fixed\-size weighted sampling without replacement, the exact marginalpjp\_\{j\}has no universal linear closed form for all weights and budgets; what Nexus needs is the weaker but correct fact that positive\-weight blocks have positive, monotone inclusion probability and admit unbiased retained\-mass estimation\.

###### Lemma A\.2\(nn\-averaged concentration\)\.

Letπj\(n\)=1n​∑i=1n\(uj\(i\)\)1/wj\\pi\_\{j\}^\{\(n\)\}=\\tfrac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\(u\_\{j\}^\{\(i\)\}\)^\{1/w\_\{j\}\}withuj\(i\)∼𝒰​\(0,1\)u\_\{j\}^\{\(i\)\}\\sim\\mathcal\{U\}\(0,1\)independent\. Then𝔼​\[πj\(n\)\]=wj/\(wj\+1\)\\mathbb\{E\}\[\\pi\_\{j\}^\{\(n\)\}\]=w\_\{j\}/\(w\_\{j\}\+1\)andVar​\(πj\(n\)\)→0\\mathrm\{Var\}\(\\pi\_\{j\}^\{\(n\)\}\)\\to 0at rate1/n1/nasn→∞n\\to\\infty\. If the weightswjw\_\{j\}are distinct \(as guaranteed in practice by the recency tie\-breakεtie​rj\\varepsilon\_\{\\mathrm\{tie\}\}\\,r\_\{j\}\), the rank of blockjjunderπj\(n\)\\pi\_\{j\}^\{\(n\)\}converges almost surely to the rank underwj/\(wj\+1\)w\_\{j\}/\(w\_\{j\}\+1\)asn→∞n\\to\\infty\.

###### Proof\.

Foru∼𝒰​\(0,1\)u\\sim\\mathcal\{U\}\(0,1\), the random variableX=u1/wX=u^\{1/w\}has CDFFX​\(x\)=Pr⁡\(u≤xw\)=xwF\_\{X\}\(x\)=\\Pr\(u\\leq x^\{w\}\)=x^\{w\}on\[0,1\]\[0,1\], densityfX​\(x\)=w​xw−1f\_\{X\}\(x\)=wx^\{w\-1\}, and moments𝔼​\[Xk\]=w/\(w\+k\)\\mathbb\{E\}\[X^\{k\}\]=w/\(w\+k\)\. Hence𝔼​\[X\]=w/\(w\+1\)\\mathbb\{E\}\[X\]=w/\(w\+1\)andVar​\(X\)=w/\(w\+2\)−\(w/\(w\+1\)\)2=w/\[\(w\+1\)2​\(w\+2\)\]\\mathrm\{Var\}\(X\)=w/\(w\+2\)\-\(w/\(w\+1\)\)^\{2\}=w/\[\(w\+1\)^\{2\}\(w\+2\)\]\. Averagingnni\.i\.d\. copies gives𝔼​\[πj\(n\)\]=wj/\(wj\+1\)\\mathbb\{E\}\[\\pi\_\{j\}^\{\(n\)\}\]=w\_\{j\}/\(w\_\{j\}\+1\)andVar​\(πj\(n\)\)=wj/\[n​\(wj\+1\)2​\(wj\+2\)\]=O​\(1/n\)\\mathrm\{Var\}\(\\pi\_\{j\}^\{\(n\)\}\)=w\_\{j\}/\[n\(w\_\{j\}\+1\)^\{2\}\(w\_\{j\}\+2\)\]=O\(1/n\)\. By the strong law of large numbers,πj\(n\)→a\.s\.wj/\(wj\+1\)\\pi\_\{j\}^\{\(n\)\}\\xrightarrow\{a\.s\.\}w\_\{j\}/\(w\_\{j\}\+1\), and the monotonicity ofw/\(w\+1\)w/\(w\+1\)inwwensures that the rank underπj\(n\)\\pi\_\{j\}^\{\(n\)\}converges a\.s\. to the rank underwj/\(wj\+1\)w\_\{j\}/\(w\_\{j\}\+1\)\. ∎

Becausewj/\(wj\+1\)w\_\{j\}/\(w\_\{j\}\+1\)is strictly increasing inwjw\_\{j\}, the deterministic limit induces the same ordering as top\-KKbywjw\_\{j\}directly\. The averaging countnnis therefore a*single\-knob*interpolation between unbiased sampling \(Lemma[A\.1](https://arxiv.org/html/2606.23961#A1.Thmtheorem1)\) and deterministic top\-KK\(n→∞n\\to\\infty\), with no other change to the pipeline\.

### A\.3Streaming Marginal\-Mass Survival

Lemma[4\.1](https://arxiv.org/html/2606.23961#S4.Thmtheorem1)\(Min over steps vs\. product over steps; restated\)\.*Consider a sequence of eviction stepse=1,…,Ee=1,\\dots,Ewith per\-step weightswj\(e\)\>0w\_\{j\}^\{\(e\)\}\>0and a fixed retention budgetKKat every step\. LetSj*top\-*​K​\(E\)S\_\{j\}^\{\\text\{top\-\}K\}\(E\)andSj*res*​\(E\)S\_\{j\}^\{\\text\{res\}\}\(E\)denote the long\-run survival probability of blockjjunder deterministic top\-KKand reservoir sampling respectively\. ThenSj*top\-*​K​\(E\)=∏e=1E𝟏​\{wj\(e\)≥w\(K\)\(e\)\}S\_\{j\}^\{\\text\{top\-\}K\}\(E\)=\\prod\_\{e=1\}^\{E\}\\mathbf\{1\}\\\{w\_\{j\}^\{\(e\)\}\\geq w\_\{\(K\)\}^\{\(e\)\}\\\}, which collapses to zero as soon as any single step haswj\(e\)<w\(K\)\(e\)w\_\{j\}^\{\(e\)\}<w\_\{\(K\)\}^\{\(e\)\}; whileSj*res*​\(E\)=∏e=1Eqj\(e\)S\_\{j\}^\{\\text\{res\}\}\(E\)=\\prod\_\{e=1\}^\{E\}q\_\{j\}^\{\(e\)\}withqj\(e\)∈\(0,1\]q\_\{j\}^\{\(e\)\}\\in\(0,1\]strictly positive wheneverwj\(e\)\>0w\_\{j\}^\{\(e\)\}\>0\.*

###### Proof\.

Under deterministic top\-KK, blockjjsurvives stepeeiffwj\(e\)≥w\(K\)\(e\)w\_\{j\}^\{\(e\)\}\\geq w\_\{\(K\)\}^\{\(e\)\}\. Survival of allEEsteps is therefore the indicator∏e=1E𝟏​\{wj\(e\)≥w\(K\)\(e\)\}\\prod\_\{e=1\}^\{E\}\\mathbf\{1\}\\\{w\_\{j\}^\{\(e\)\}\\geq w\_\{\(K\)\}^\{\(e\)\}\\\}, which is zero whenever a single step falls below the cutoff\. Under reservoir sampling, Lemma[A\.1](https://arxiv.org/html/2606.23961#A1.Thmtheorem1)gives a positive per\-step inclusion probabilityqj\(e\)q\_\{j\}^\{\(e\)\}wheneverwj\(e\)\>0w\_\{j\}^\{\(e\)\}\>0\. With independent priority draws at different eviction steps, the survival probability is∏eqj\(e\)\\prod\_\{e\}q\_\{j\}^\{\(e\)\}, which is strictly positive whenever everyqj\(e\)q\_\{j\}^\{\(e\)\}is\. ∎

This is the precise sense in which the reservoir step is the*right*primitive for the streaming\-budget regime: deterministic top\-KKconverts a single marginal\-rank misjudgment into permanent, irrecoverable loss \(the block is gone from the cache and cannot re\-enter\), while reservoir sampling assigns strictly positive inclusion probability at every event, so the long\-run survival probability remains bounded away from zero as long as the block’s per\-event weight is positive\.

### A\.4Window Averaging as Noise Reduction

###### Lemma A\.3\(Window noise reduction\)\.

If each row𝐚\(q\)=𝛍\+𝛏q\\mathbf\{a\}^\{\(q\)\}=\\bm\{\\mu\}\+\\bm\{\\xi\}\_\{q\}with𝔼​\[𝛏q\]=𝟎\\mathbb\{E\}\[\\bm\{\\xi\}\_\{q\}\]=\\mathbf\{0\}and per\-coordinate variance≤ν2\\leq\\nu^\{2\}, then with probability≥1−δ\\geq 1\-\\delta,

‖𝐚−𝝁‖∞≤ν​2​log⁡\(2​Nk/δ\)/W\.\\\|\\mathbf\{a\}\-\\bm\{\\mu\}\\\|\_\{\\infty\}\\leq\\nu\\sqrt\{2\\log\(2N\_\{k\}/\\delta\)/W\}\.

###### Proof\.

By construction𝐚−𝝁=\(1/W\)​∑q𝝃q\\mathbf\{a\}\-\\bm\{\\mu\}=\(1/W\)\\sum\_\{q\}\\bm\{\\xi\}\_\{q\}, an average ofWWindependent zero\-mean coordinate\-wise sub\-Gaussian random vectors\. For any blockjj, Hoeffding’s inequality \(applied to bounded coordinates of𝝃q\\bm\{\\xi\}\_\{q\}on\[−1,1\]\[\-1,1\]\) gives

Pr⁡\(\|\(𝐚−𝝁\)j\|≥t\)≤2​exp⁡\(−W​t2/\(2​ν2\)\)\.\\Pr\\\!\\bigl\(\|\\,\(\\mathbf\{a\}\-\\bm\{\\mu\}\)\_\{j\}\\,\|\\geq t\\bigr\)\\leq 2\\exp\(\-Wt^\{2\}/\(2\\nu^\{2\}\)\)\.Taking a union bound over theNkN\_\{k\}block coordinates and solving forttat confidence1−δ1\-\\deltayields the claim\. ∎

The bound is the standard1/W1/\\sqrt\{W\}noise\-reduction rate, with theNkN\_\{k\}\-dimensional union bound contributing only alog⁡Nk\\log N\_\{k\}factor\. The implication for the reservoir step is that a modest window length \(W≈16W\\approx 16–3232\) suffices to bring the per\-block noise floor on the reservoir’s input weights below the typical scale of meaningful per\-block weight differences\.

### A\.5Eviction Quality Under Approximate Future Utility

We restate Proposition[4\.3](https://arxiv.org/html/2606.23961#S4.Thmtheorem3)of §[4](https://arxiv.org/html/2606.23961#S4)in its full three\-part form \(the main\-text statement combines parts 1 and 2 into a single bound\) and prove it\. Letzj≥0z\_\{j\}\\geq 0denote the utility that blockjjwould contribute to future attention if it remained in cache; this can be instantiated as future block\-attention mass, or as a value\-norm\-weighted utilityzj=∑τατ​j​‖Vj‖z\_\{j\}=\\sum\_\{\\tau\}\\alpha\_\{\\tau j\}\\\|V\_\{j\}\\\|over a short future horizon\.

Proposition[4\.3](https://arxiv.org/html/2606.23961#S4.Thmtheorem3)\(restated and extended\)\.*Fix one cache\-update event and letIjI\_\{j\}be the reservoir\-sampling inclusion indicator with inclusion probabilitypj=Pr⁡\(Ij=1\)p\_\{j\}=\\Pr\(I\_\{j\}=1\)\. For any deterministic future\-utility vector𝐳\\mathbf\{z\}:*

1. 1\.*The Horvitz–Thompson retained\-utility estimator* Z^HT=∑j=1NkIj​zjpj\\widehat\{Z\}\_\{\\mathrm\{HT\}\}=\\sum\_\{j=1\}^\{N\_\{k\}\}\\frac\{I\_\{j\}z\_\{j\}\}\{p\_\{j\}\}*is unbiased for the full\-cache utilityZ=∑jzjZ=\\sum\_\{j\}z\_\{j\}\.*
2. 2\.*Ifpj≥pmin\>0p\_\{j\}\\geq p\_\{\\min\}\>0and0≤zj≤Zmax0\\leq z\_\{j\}\\leq Z\_\{\\max\}, then with probability at least1−δ1\-\\delta,* \|Z^HT−Z\|≤Kδ​∑j=1Nkzj2pj≤Zmax​K​Nkδ​pmin\.\|\\widehat\{Z\}\_\{\\mathrm\{HT\}\}\-Z\|\\leq\\sqrt\{\\frac\{K\}\{\\delta\}\\sum\_\{j=1\}^\{N\_\{k\}\}\\frac\{z\_\{j\}^\{2\}\}\{p\_\{j\}\}\}\\leq Z\_\{\\max\}\\sqrt\{\\frac\{KN\_\{k\}\}\{\\delta p\_\{\\min\}\}\}\.
3. 3\.*If the Nexus weight approximates future utility as‖𝐰−𝐳‖∞≤η\\\|\\mathbf\{w\}\-\\mathbf\{z\}\\\|\_\{\\infty\}\\leq\\eta, then the expected evicted utilityL=∑j\(1−Ij\)​zjL=\\sum\_\{j\}\(1\-I\_\{j\}\)z\_\{j\}satisfies* \|𝔼​\[L\]−∑j=1Nk\(1−pj\)​wj\|≤η​∑j=1Nk\(1−pj\)≤η​Nk\.\\left\|\\mathbb\{E\}\[L\]\-\\sum\_\{j=1\}^\{N\_\{k\}\}\(1\-p\_\{j\}\)w\_\{j\}\\right\|\\leq\\eta\\sum\_\{j=1\}^\{N\_\{k\}\}\(1\-p\_\{j\}\)\\leq\\eta N\_\{k\}\.

###### Proof\.

The first claim is the Horvitz–Thompson identity already used in Lemma[A\.1](https://arxiv.org/html/2606.23961#A1.Thmtheorem1)\. For the second claim, letAj=Ij​zj/pjA\_\{j\}=I\_\{j\}z\_\{j\}/p\_\{j\}\. Because exactlyKKblocks are retained,\(∑jAj\)2≤K​∑jAj2\(\\sum\_\{j\}A\_\{j\}\)^\{2\}\\leq K\\sum\_\{j\}A\_\{j\}^\{2\}\. Therefore

𝔼​\[Z^HT2\]≤K​∑j𝔼​\[Ij​zj2pj2\]=K​∑jzj2pj\.\\mathbb\{E\}\[\\widehat\{Z\}\_\{\\mathrm\{HT\}\}^\{2\}\]\\leq K\\sum\_\{j\}\\mathbb\{E\}\\\!\\left\[\\frac\{I\_\{j\}z\_\{j\}^\{2\}\}\{p\_\{j\}^\{2\}\}\\right\]=K\\sum\_\{j\}\\frac\{z\_\{j\}^\{2\}\}\{p\_\{j\}\}\.SinceVar⁡\(Z^HT\)≤𝔼​\[Z^HT2\]\\operatorname\{Var\}\(\\widehat\{Z\}\_\{\\mathrm\{HT\}\}\)\\leq\\mathbb\{E\}\[\\widehat\{Z\}\_\{\\mathrm\{HT\}\}^\{2\}\], Chebyshev’s inequality yields the stated bound\. The final inequality follows fromzj2≤Zmax2z\_\{j\}^\{2\}\\leq Z\_\{\\max\}^\{2\}andpj≥pminp\_\{j\}\\geq p\_\{\\min\}\. For the third claim,

𝔼​\[L\]=∑j\(1−pj\)​zj,\\mathbb\{E\}\[L\]=\\sum\_\{j\}\(1\-p\_\{j\}\)z\_\{j\},and subtracting∑j\(1−pj\)​wj\\sum\_\{j\}\(1\-p\_\{j\}\)w\_\{j\}gives\|∑j\(1−pj\)​\(zj−wj\)\|≤η​∑j\(1−pj\)\\left\|\\sum\_\{j\}\(1\-p\_\{j\}\)\(z\_\{j\}\-w\_\{j\}\)\\right\|\\leq\\eta\\sum\_\{j\}\(1\-p\_\{j\}\)\. ∎

The proposition separates the two sources of approximation\. The reservoir step contributes no systematic bias once inclusion probabilities are accounted for; the remaining eviction error is controlled by how well the score𝐰\\mathbf\{w\}predicts future utility\. This is where the observation window and walk matter: Lemma[A\.3](https://arxiv.org/html/2606.23961#A1.Thmtheorem3)reduces estimation noise in direct utility, while Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)raises the weight of hub blocks whose future utility is indirect rather than visible in one\-hop attention\.

### A\.6Multi\-Hop Walk: Decomposition and Hub Amplification

This subsection states a rank\-1 decomposition of the walk recurrence that underlies the hub\-amplification argument, then proves Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)\.

###### Lemma A\.4\(Walk decomposition and hub\-score zero\-sum\)\.

Let𝐌q=𝐚\(q\)​\(𝐚\(q\)\)⊤∈ℝNk×Nk\\mathbf\{M\}\_\{q\}=\\mathbf\{a\}^\{\(q\)\}\(\\mathbf\{a\}^\{\(q\)\}\)^\{\\top\}\\in\\mathbb\{R\}^\{N\_\{k\}\\times N\_\{k\}\}be the rank\-1 per\-query block\-affinity matrix\. The walk recurrence \([4](https://arxiv.org/html/2606.23961#S2.E4)\) satisfies the exact identity

𝐂\(H\)\\displaystyle\\mathbf\{C\}^\{\(H\)\}=\(∑q=1H𝐚\(q\)\)\\displaystyle\\;=\\;\\Bigl\(\\textstyle\\sum\_\{q=1\}^\{H\}\\mathbf\{a\}^\{\(q\)\}\\Bigr\)\+\(∑q=1H𝐌q​𝐂\(q−1\)\)\.\\displaystyle\\quad\+\\;\\Bigl\(\\textstyle\\sum\_\{q=1\}^\{H\}\\mathbf\{M\}\_\{q\}\\,\\mathbf\{C\}^\{\(q\-1\)\}\\Bigr\)\.Furthermore,∑jhj=0\\sum\_\{j\}h\_\{j\}=0, i\.e\., the hub scores sum to zero\.

###### Proof\.

For each stepqq, the update increment is

γq​𝐚\(q\)\\displaystyle\\gamma\_\{q\}\\,\\mathbf\{a\}^\{\(q\)\}=\(1\+⟨𝐚\(q\),𝐂\(q−1\)⟩\)​𝐚\(q\)\\displaystyle=\\bigl\(1\+\\langle\\mathbf\{a\}^\{\(q\)\},\\mathbf\{C\}^\{\(q\-1\)\}\\rangle\\bigr\)\\,\\mathbf\{a\}^\{\(q\)\}=𝐚\(q\)\+\(𝐚\(q\)⊤​𝐂\(q−1\)\)​𝐚\(q\)\\displaystyle=\\mathbf\{a\}^\{\(q\)\}\+\\bigl\(\\mathbf\{a\}^\{\(q\)\\top\}\\mathbf\{C\}^\{\(q\-1\)\}\\bigr\)\\,\\mathbf\{a\}^\{\(q\)\}=𝐚\(q\)\+𝐌q​𝐂\(q−1\),\\displaystyle=\\mathbf\{a\}^\{\(q\)\}\+\\mathbf\{M\}\_\{q\}\\,\\mathbf\{C\}^\{\(q\-1\)\},an exact equality with no residual\. Summing𝐂\(q\)=𝐂\(q−1\)\+𝐚\(q\)\+𝐌q​𝐂\(q−1\)\\mathbf\{C\}^\{\(q\)\}=\\mathbf\{C\}^\{\(q\-1\)\}\+\\mathbf\{a\}^\{\(q\)\}\+\\mathbf\{M\}\_\{q\}\\,\\mathbf\{C\}^\{\(q\-1\)\}fromq=1q=1toHHwith𝐂\(0\)=𝟎\\mathbf\{C\}^\{\(0\)\}=\\mathbf\{0\}yields the stated identity\. For the hub\-sum claim: since∑jaj\(q\)=1\\sum\_\{j\}a\_\{j\}^\{\(q\)\}=1a\.s\., we have∑jξq,j=0\\sum\_\{j\}\\xi\_\{q,j\}=0a\.s\., so∑jΣj​k=𝔼​\[∑jξq,j​ξq,k\]=0\\sum\_\{j\}\\Sigma\_\{jk\}=\\mathbb\{E\}\[\\sum\_\{j\}\\xi\_\{q,j\}\\,\\xi\_\{q,k\}\]=0for everykk, giving𝟏⊤​𝚺=𝟎⊤\\bm\{1\}^\{\\top\}\\bm\{\\Sigma\}=\\mathbf\{0\}^\{\\top\}and∑jhj=𝟏⊤​𝚺​𝐚⋆=0\\sum\_\{j\}h\_\{j\}=\\bm\{1\}^\{\\top\}\\bm\{\\Sigma\}\\,\\mathbf\{a\}\_\{\\star\}=0\. ∎

The first term is the unwalked window aggregate \(essentiallyW​𝐚W\\mathbf\{a\}if all window rows are used\)\. The second term is the genuinely multi\-hop contribution: each𝐌q\\mathbf\{M\}\_\{q\}is a rank\-1 affinity matrix encoding which block pairs queryqqconnects, and𝐌q​𝐂\(q−1\)\\mathbf\{M\}\_\{q\}\\,\\mathbf\{C\}^\{\(q\-1\)\}aggregates the accumulated walk under that affinity structure\. The depthHHcontrols the highest\-order hop captured; as inLeet al\.\[[14](https://arxiv.org/html/2606.23961#bib.bib24)\], smallHH\(e\.g\.,H=3H=3\) suffices in practice because effective composed attention depth in transformer stacks is empirically shallow\.

#### A\.6\.1Hub Amplification \(Main Theorem\)

We first record the i\.i\.d\. stationarity assumption and the formal definition of a hub block, then restate Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)with the full intermediate quantities and prove it\.

###### Assumption A\.5\(i\.i\.d\. stationarity\)\.

TheHHwalk\-step attention distributions𝐚\(1\),…,𝐚\(H\)\\mathbf\{a\}^\{\(1\)\},\\dots,\\mathbf\{a\}^\{\(H\)\}\(i\.e\., theHHquery rows consumed by the recurrence \([4](https://arxiv.org/html/2606.23961#S2.E4)\)\) are drawn i\.i\.d\. from a fixed distribution with mean𝐚⋆\\mathbf\{a\}\_\{\\star\}and covariance matrix𝚺\\bm\{\\Sigma\}\.

###### Definition A\.6\(Hub block\)\.

Blockjjis a*hub block*ifhj=𝚺j⊤​𝐚⋆\>0h\_\{j\}=\\bm\{\\Sigma\}\_\{j\}^\{\\top\}\\mathbf\{a\}\_\{\\star\}\>0, i\.e\., queries that give high attention to blockjjtend to also give high attention to other frequently attended blocks\. Blockjjis*peripheral*ifhj≤0h\_\{j\}\\leq 0\.

Theorem[4\.2](https://arxiv.org/html/2606.23961#S4.Thmtheorem2)\(restated and extended\)\.*Under Assumption[A\.5](https://arxiv.org/html/2606.23961#A1.Thmtheorem5), the Nexus walk \(Eq\.[4](https://arxiv.org/html/2606.23961#S2.E4)\) withHHsteps satisfies*

𝔼​\[Cj\(H\)\]=BH​a⋆,j\+DH​hj\+O​\(H​‖𝚺‖F2\),\\mathbb\{E\}\[C\_\{j\}^\{\(H\)\}\]\\;=\\;B\_\{H\}\\,a\_\{\\star,j\}\\;\+\\;D\_\{H\}\\,h\_\{j\}\\;\+\\;O\(H\\,\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\),\(7\)*whereBH=∑q=1H𝔼​\[γq\]≥HB\_\{H\}=\\sum\_\{q=1\}^\{H\}\\mathbb\{E\}\[\\gamma\_\{q\}\]\\geq His a block\-independent amplification factor,DH=∑q=1H−1Bq≥H​\(H−1\)/2D\_\{H\}=\\sum\_\{q=1\}^\{H\-1\}B\_\{q\}\\geq H\(H\-1\)/2is the cumulative covariance\-boost coefficient, and theO​\(⋅\)O\(\\cdot\)term captures second\-order covariance interactions\. Since∑jhj=0\\sum\_\{j\}h\_\{j\}=0\(Lemma[A\.4](https://arxiv.org/html/2606.23961#A1.Thmtheorem4)\),L1L\_\{1\}\-normalization gives*

𝔼​\[c~j\(H\)\]\\displaystyle\\mathbb\{E\}\[\\tilde\{c\}\_\{j\}^\{\(H\)\}\]=a⋆,j\+DHBH​hj\+O​\(‖𝚺‖F2\);\\displaystyle\\;=\\;a\_\{\\star,j\}\+\\tfrac\{D\_\{H\}\}\{B\_\{H\}\}\\,h\_\{j\}\+O\(\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\);in particular,𝔼​\[c~j\(H\)\]≷a⋆,j⟺hj≷0\.\\displaystyle\\text\{in particular,\}\\quad\\mathbb\{E\}\[\\tilde\{c\}\_\{j\}^\{\(H\)\}\]\\;\\gtrless\\;a\_\{\\star,j\}\\;\\Longleftrightarrow\\;h\_\{j\}\\;\\gtrless\\;0\.*Furthermore, hub blocks have strictly higher expected sampling weight𝔼​\[wj\]\\mathbb\{E\}\[w\_\{j\}\]; by the monotonicity of inclusion probability inwjw\_\{j\}\(Lemma[A\.1](https://arxiv.org/html/2606.23961#A1.Thmtheorem1)\), their expected inclusion probability𝔼​\[pj\]\\mathbb\{E\}\[p\_\{j\}\]is strictly higher than the window average𝐚\\mathbf\{a\}alone would predict\.*

###### Proof\.

Step 1: Unrolling the recurrence\.The walk \(Eq\.[4](https://arxiv.org/html/2606.23961#S2.E4)\) gives𝐂\(H\)=∑q=1Hγq​𝐚\(q\)\\mathbf\{C\}^\{\(H\)\}=\\sum\_\{q=1\}^\{H\}\\gamma\_\{q\}\\,\\mathbf\{a\}^\{\(q\)\}, whereγq=1\+⟨𝐚\(q\),𝐂\(q−1\)⟩\\gamma\_\{q\}=1\+\\langle\\mathbf\{a\}^\{\(q\)\},\\mathbf\{C\}^\{\(q\-1\)\}\\rangleandγ1=1\\gamma\_\{1\}=1\. Taking expectations entry\-wise:

𝔼​\[Cj\(H\)\]\\displaystyle\\mathbb\{E\}\[C\_\{j\}^\{\(H\)\}\]=∑q=1H𝔼​\[γq​aj\(q\)\]\\displaystyle=\\sum\_\{q=1\}^\{H\}\\mathbb\{E\}\[\\gamma\_\{q\}\\,a\_\{j\}^\{\(q\)\}\]=∑q=1H\(𝔼​\[γq\]​a⋆,j\+Cov⁡\(γq,aj\(q\)\)\)\.\\displaystyle=\\sum\_\{q=1\}^\{H\}\\Bigl\(\\mathbb\{E\}\[\\gamma\_\{q\}\]\\,a\_\{\\star,j\}\+\\operatorname\{Cov\}\(\\gamma\_\{q\},\\,a\_\{j\}^\{\(q\)\}\)\\Bigr\)\.\(8\)
Step 2: Block\-independence of the amplification sum\.Under Assumption[A\.5](https://arxiv.org/html/2606.23961#A1.Thmtheorem5),𝐚\(q\)\\mathbf\{a\}^\{\(q\)\}is independent of𝐂\(q−1\)\\mathbf\{C\}^\{\(q\-1\)\}, so

𝔼​\[γq\]=1\+⟨𝐚⋆,𝔼​\[𝐂\(q−1\)\]⟩\.\\mathbb\{E\}\[\\gamma\_\{q\}\]=1\+\\langle\\mathbf\{a\}\_\{\\star\},\\,\\mathbb\{E\}\[\\mathbf\{C\}^\{\(q\-1\)\}\]\\rangle\.This depends only on𝐚⋆\\mathbf\{a\}\_\{\\star\}and𝚺\\bm\{\\Sigma\}through𝔼​\[𝐂\(q−1\)\]\\mathbb\{E\}\[\\mathbf\{C\}^\{\(q\-1\)\}\], and crucially*not*on block indexjj\. DefiningBH=∑q=1H𝔼​\[γq\]B\_\{H\}=\\sum\_\{q=1\}^\{H\}\\mathbb\{E\}\[\\gamma\_\{q\}\], the first term in \([8](https://arxiv.org/html/2606.23961#A1.E8)\) contributesBH​a⋆,jB\_\{H\}\\,a\_\{\\star,j\}uniformly across all blocks\.

Step 3: Covariance boost\.Forq≥2q\\geq 2, by the independence of𝐚\(q\)\\mathbf\{a\}^\{\(q\)\}from𝐂\(q−1\)\\mathbf\{C\}^\{\(q\-1\)\}\(Assumption[A\.5](https://arxiv.org/html/2606.23961#A1.Thmtheorem5)\):

Cov⁡\(γq,aj\(q\)\)\\displaystyle\\operatorname\{Cov\}\(\\gamma\_\{q\},\\,a\_\{j\}^\{\(q\)\}\)=Cov⁡\(⟨𝐚\(q\),𝐂\(q−1\)⟩,aj\(q\)\)\\displaystyle=\\operatorname\{Cov\}\\\!\\bigl\(\\langle\\mathbf\{a\}^\{\(q\)\},\\mathbf\{C\}^\{\(q\-1\)\}\\rangle,\\;a\_\{j\}^\{\(q\)\}\\bigr\)=𝔼​\[𝐂\(q−1\)\]⊤​𝚺j,\\displaystyle=\\mathbb\{E\}\[\\mathbf\{C\}^\{\(q\-1\)\}\]^\{\\top\}\\bm\{\\Sigma\}\_\{j\},where𝚺j\\bm\{\\Sigma\}\_\{j\}is thejj\-th column of𝚺=𝔼​\[𝐚\(q\)​𝐚\(q\)⊤\]−𝐚⋆​𝐚⋆⊤\\bm\{\\Sigma\}=\\mathbb\{E\}\[\\mathbf\{a\}^\{\(q\)\}\\mathbf\{a\}^\{\(q\)\\top\}\]\-\\mathbf\{a\}\_\{\\star\}\\mathbf\{a\}\_\{\\star\}^\{\\top\}\. \(The equality follows by conditioning on𝐂\(q−1\)\\mathbf\{C\}^\{\(q\-1\)\}and using𝔼​\[𝐚\(q\)​\(𝐚\(q\)\)⊤\]=𝚺\+𝐚⋆​𝐚⋆⊤\\mathbb\{E\}\[\\mathbf\{a\}^\{\(q\)\}\(\\mathbf\{a\}^\{\(q\)\}\)^\{\\top\}\]=\\bm\{\\Sigma\}\+\\mathbf\{a\}\_\{\\star\}\\mathbf\{a\}\_\{\\star\}^\{\\top\}\.\) We now compute𝔼​\[𝐂\(q−1\)\]\\mathbb\{E\}\[\\mathbf\{C\}^\{\(q\-1\)\}\]by induction\. The base case is𝔼​\[𝐂\(1\)\]=𝐚⋆=B1​𝐚⋆\\mathbb\{E\}\[\\mathbf\{C\}^\{\(1\)\}\]=\\mathbf\{a\}\_\{\\star\}=B\_\{1\}\\,\\mathbf\{a\}\_\{\\star\}sinceγ1=1\\gamma\_\{1\}=1\. At each step,𝔼​\[𝐂\(q\)\]=𝔼​\[𝐂\(q−1\)\]\+𝔼​\[γq\]​𝐚⋆\+O​\(‖𝚺‖\)\\mathbb\{E\}\[\\mathbf\{C\}^\{\(q\)\}\]=\\mathbb\{E\}\[\\mathbf\{C\}^\{\(q\-1\)\}\]\+\\mathbb\{E\}\[\\gamma\_\{q\}\]\\,\\mathbf\{a\}\_\{\\star\}\+O\(\\\|\\bm\{\\Sigma\}\\\|\), giving

𝔼​\[𝐂\(q−1\)\]\\displaystyle\\mathbb\{E\}\[\\mathbf\{C\}^\{\(q\-1\)\}\]=Bq−1​𝐚⋆\+O​\(‖𝚺‖\),\\displaystyle=B\_\{q\-1\}\\,\\mathbf\{a\}\_\{\\star\}\+O\(\\\|\\bm\{\\Sigma\}\\\|\),Bq−1\\displaystyle B\_\{q\-1\}=∑q′=1q−1𝔼​\[γq′\]\.\\displaystyle=\\textstyle\\sum\_\{q^\{\\prime\}=1\}^\{q\-1\}\\mathbb\{E\}\[\\gamma\_\{q^\{\\prime\}\}\]\.Substituting:

Cov⁡\(γq,aj\(q\)\)=Bq−1​hj\+O​\(‖𝚺‖F2\)\.\\operatorname\{Cov\}\(\\gamma\_\{q\},\\,a\_\{j\}^\{\(q\)\}\)=B\_\{q\-1\}\\,h\_\{j\}\+O\(\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\)\.Summing overq=2,…,Hq=2,\\dots,Hand settingDH=∑q=1H−1BqD\_\{H\}=\\sum\_\{q=1\}^\{H\-1\}B\_\{q\}:

∑q=2HCov⁡\(γq,aj\(q\)\)=DH​hj\+O​\(H​‖𝚺‖F2\)\.\\sum\_\{q=2\}^\{H\}\\operatorname\{Cov\}\(\\gamma\_\{q\},\\,a\_\{j\}^\{\(q\)\}\)=D\_\{H\}\\,h\_\{j\}\+O\(H\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\)\.Combining with Step 2 gives Eq\. \([7](https://arxiv.org/html/2606.23961#A1.E7)\)\. NoteDH≥∑q=1H−1q=H​\(H−1\)/2D\_\{H\}\\geq\\sum\_\{q=1\}^\{H\-1\}q=H\(H\-1\)/2sinceBq≥qB\_\{q\}\\geq q\.

Step 4: Directional consequence\.By Lemma[A\.4](https://arxiv.org/html/2606.23961#A1.Thmtheorem4),∑jhj=0\\sum\_\{j\}h\_\{j\}=0\. Therefore theL1L\_\{1\}\-norm of𝔼​\[𝐂\(H\)\]\\mathbb\{E\}\[\\mathbf\{C\}^\{\(H\)\}\]satisfies

∑j𝔼​\[Cj\(H\)\]\\displaystyle\\textstyle\\sum\_\{j\}\\mathbb\{E\}\[C\_\{j\}^\{\(H\)\}\]=BH​∑ja⋆,j⏟=1\+DH​∑jhj⏟=0\\displaystyle=B\_\{H\}\\underbrace\{\\textstyle\\sum\_\{j\}a\_\{\\star,j\}\}\_\{=\\,1\}\+D\_\{H\}\\underbrace\{\\textstyle\\sum\_\{j\}h\_\{j\}\}\_\{=\\,0\}\+O​\(H​‖𝚺‖F2\)\\displaystyle\+O\(H\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\)=BH\+O​\(H​‖𝚺‖F2\)\.\\displaystyle=B\_\{H\}\+O\(H\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\)\.Dividing Eq\. \([7](https://arxiv.org/html/2606.23961#A1.E7)\) entry\-wise by this norm:

𝔼​\[c~j\(H\)\]\\displaystyle\\mathbb\{E\}\[\\tilde\{c\}\_\{j\}^\{\(H\)\}\]=BH​a⋆,j\+DH​hjBH\+O​\(‖𝚺‖F2\)\\displaystyle=\\frac\{B\_\{H\}\\,a\_\{\\star,j\}\+D\_\{H\}\\,h\_\{j\}\}\{B\_\{H\}\}\+O\(\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\)=a⋆,j\+DHBH​hj\+O​\(‖𝚺‖F2\)\.\\displaystyle=a\_\{\\star,j\}\+\\tfrac\{D\_\{H\}\}\{B\_\{H\}\}\\,h\_\{j\}\+O\(\\\|\\bm\{\\Sigma\}\\\|\_\{F\}^\{2\}\)\.SinceDH/BH\>0D\_\{H\}/B\_\{H\}\>0, we have𝔼​\[c~j\(H\)\]≷a⋆,j\\mathbb\{E\}\[\\tilde\{c\}\_\{j\}^\{\(H\)\}\]\\gtrless a\_\{\\star,j\}if and only ifhj≷0h\_\{j\}\\gtrless 0\.

Step 5: Hub retention\.By Lemma[A\.1](https://arxiv.org/html/2606.23961#A1.Thmtheorem1), the inclusion probabilitypj​\(𝐰\)=Pr⁡\(Ij=1∣𝐰\)p\_\{j\}\(\\mathbf\{w\}\)=\\Pr\(I\_\{j\}=1\\mid\\mathbf\{w\}\)is increasing inwjw\_\{j\}with all other weights fixed\. The realized weightwj=Cj\(H\)w\_\{j\}=C\_\{j\}^\{\(H\)\}is random; taking expectations over𝐰\\mathbf\{w\}gives𝔼​\[pj\]=𝔼𝐰​\[pj​\(𝐰\)\]\\mathbb\{E\}\[p\_\{j\}\]=\\mathbb\{E\}\_\{\\mathbf\{w\}\}\[p\_\{j\}\(\\mathbf\{w\}\)\]\. Hub blocks satisfy𝔼​\[wj\]=𝔼​\[Cj\(H\)\]\>a⋆,j\\mathbb\{E\}\[w\_\{j\}\]=\\mathbb\{E\}\[C\_\{j\}^\{\(H\)\}\]\>a\_\{\\star,j\}after normalization \(Step 4\), while peripheral blocks have𝔼​\[wj\]<a⋆,j\\mathbb\{E\}\[w\_\{j\}\]<a\_\{\\star,j\}\. Becausepj​\(𝐰\)p\_\{j\}\(\\mathbf\{w\}\)is increasing inwjw\_\{j\}, a shift in the distribution ofwjw\_\{j\}toward larger values \(higher mean\) raises𝔼​\[pj\]\\mathbb\{E\}\[p\_\{j\}\]via the law of total expectation\. Consequently, the expected inclusion probability of hub blocks strictly exceeds what the unwalked window scoreaja\_\{j\}would predict\. ∎

Remark\.Assumption[A\.5](https://arxiv.org/html/2606.23961#A1.Thmtheorem5)requires i\.i\.d\. query rows, which is an idealization: consecutive tokens within a document are correlated\. In practice the window acts as a local mixing device; the theorem should be read as characterizing the*tendency*of the walk to amplify cross\-query consensus blocks rather than as an exact finite\-sample guarantee\.

## Appendix BDetailed Ablations

This appendix expands §[5\.5](https://arxiv.org/html/2606.23961#S5.SS5), walking through each panel of Figure[3](https://arxiv.org/html/2606.23961#S5.F3)\. All settings match §[5\.1](https://arxiv.org/html/2606.23961#S5.SS1): Llama\-3\.1\-8B at20%20\\%density, evaluated on three multi\-hop QA tasks \(HotpotQA, 2WikiMQA, MultiFieldQA\-en\)\. We selected this slice deliberately: multi\-hop QA stresses the two failure modes Nexus Sampling is designed to address \(bridge tokens and irreversible eviction\), so any knob that mattered should move the numbers here before showing up on broader benchmarks\.

Walk depthHH\.H=0H=0\(no walk\) is already strong because the windowed direct score𝐚\\mathbf\{a\}alone is informative; this is the regime every direct\-attention baseline already operates in, which is why those baselines are competitive on retrieval tasks where a single bridge hop suffices\.H≥1H\\geq 1adds a small but consistent improvement on 2WikiMQA, the most multi\-hop\-sensitive of the three tasks: each additional walk step lets a token inherit influence from a neighbor one further hop away from the current query, and 2WikiMQA is precisely the dataset where the answer\-supporting token is reached through such an intermediate\.H∈\{2,3\}H\\in\\\{2,3\\\}captures the bulk of the gain andH=5H=5is essentially indistinguishable fromH=3H=3, matching the rank\-1 propagation analysis of App\.[A](https://arxiv.org/html/2606.23961#A1): after a few steps the walk converges toward the principal direction of the attention operator and additional iterations only resharpen what is already there\. We therefore default toH=3H=3, which keeps the bridge\-token benefit while leaving the per\-step cost negligible relative to dense attention\.

Mixing weightλ\\lambda\.λ=0\\lambda=0closes most of the gap to Nexus but stays consistently belowλ\>0\\lambda\>0on 2WikiMQA, confirming that the bridge term contributes signal beyond what direct attention already captures\.λ=1\.0\\lambda=1\.0overweights the bridge term and slightly hurts HotpotQA, where the answer is often a single hop away and the direct score is the cleaner signal; mixing the two terms is what makes the score robust across multi\-hop structures of different depth\. The safe operating range isλ∈\[0\.25,0\.5\]\\lambda\\in\[0\.25,0\.5\]across all three datasets, and within that range the surface is flat, so the choice does not require per\-task tuning; we default toλ=0\.5\\lambda=0\.5throughout\.

Observation windowWW\.Small windows \(W∈\{8,16,32\}W\\in\\\{8,16,32\\\}\) track full attention closely\. Larger windows degrade sharply on tasks that need short\-range responsiveness: MultiFieldQA\-en and 2WikiMQA both drop∼\\sim5–10 points atW=256W=256, because the per\-query distribution gets diluted across queries that are no longer relevant to the current decoding step\. This is a familiar effect from streaming attention\-scoring methods: averaging the score over too long a window turns the per\-step decision into a stale running mean and erases the locality the model relies on\.W=16W=16is a sweet spot, small enough to remain responsive yet large enough to absorb single\-step noise, and matches the window sizes reported by recent eviction work\[[16](https://arxiv.org/html/2606.23961#bib.bib12),[9](https://arxiv.org/html/2606.23961#bib.bib13)\]\.

Block sizebb\.b∈\{16,32,64\}b\\in\\\{16,32,64\\\}are within noise of one another, whileb≥128b\\geq 128degrades sharply\. The mechanism is straightforward: too\-coarse blocks aggregate over too many tokens at once, hiding the single\-token signal that the per\-block attention distribution needs to resolve\. The flat region at smallbbis what makes block\-wise eviction practical at all: it lets implementations align the eviction granularity with the hardware\-friendly block sizes already used by FlashAttention kernels without paying an accuracy tax\. We default tob=32b=32, which is the smallest block size that lets the kernel achieve full memory\-bandwidth utilization on the H200\.

Density\.Accuracy is essentially flat from20%20\\%to80%80\\%density on all three tasks, confirming that the aggressive20%20\\%setting we report in §[5\.2](https://arxiv.org/html/2606.23961#S5.SS2)–[5\.3](https://arxiv.org/html/2606.23961#S5.SS3)does not give up accuracy headroom to less aggressive configurations\. This is the empirical signature of the marginal\-mass argument of §[3](https://arxiv.org/html/2606.23961#S3): under reservoir sampling, even tight budgets retain the subtly important tokens that deterministic top\-KKwould erode, and the long\-run survival probability decays gracefully with the budget rather than collapsing on the first below\-cutoff step\. Practically, this means the relevant question at deployment time is not “how much can we shrink the cache before accuracy breaks?” but “how much memory headroom does the workload need for other purposes?”, which is the regime modern agentic deployments actually operate in\.

## Appendix CComparison with Head\-Adaptive Budget Allocation \(Ada\-KV\)

Ada\-KV\[[8](https://arxiv.org/html/2606.23961#bib.bib11)\]is*orthogonal*to Nexus Sampling: rather than proposing a new token\-importance score, it redistributes a fixed layer\-wide budget*across attention heads*so that heads with more concentrated attention keep more tokens\. It can therefore be layered on top of any scoring rule, including SnapKV \(yielding Ada\-SnapKV\) or, in principle, Nexus Sampling itself\. Because this head\-budget allocation is a separate axis from the scoring contribution we study in the main paper, we report Ada\-SnapKV separately here rather than mixing it into Table[1](https://arxiv.org/html/2606.23961#S5.T1)\.

Table[7](https://arxiv.org/html/2606.23961#A3.T7)compares Ada\-SnapKV against SnapKV and Nexus Sampling in the prefill\-only regime, with Full Attention shown for reference\. Ada\-SnapKV improves over plain SnapKV on average, as expected from its better budget allocation, but Nexus Sampling remains competitive on the average across all three models using a uniform per\-head budget, indicating that the scoring contribution we introduce is complementary to the head\-adaptive allocation of Ada\-KV\.

Table 7:Prefill\-only LongBench accuracy at20%20\\%density, isolating the orthogonal head\-adaptive budget allocation of Ada\-KV\[[8](https://arxiv.org/html/2606.23961#bib.bib11)\]\. Ada\-SnapKV applies the Ada\-KV allocation on top of the SnapKV score; Nexus Sampling uses a uniform per\-head budget\.Boldmarks the leading method per row across the eviction methods \(Full Attention shown for reference\)\.ModelMethodDensityWIKIGOVHPQALCCMNewsMFQAMUSNQACOUNTRetr\.QASQMSREPOSamSTRECTRIVAvg\.Llama\-3\.1\-8BFull Attention100%47\.7534\.7056\.9655\.2026\.7656\.1632\.7729\.919\.6699\.5045\.0625\.3947\.8043\.2773\.0092\.1448\.50SnapKV20%47\.1728\.6958\.6155\.4223\.1955\.4431\.5330\.2810\.2599\.5040\.0324\.6048\.7542\.1768\.5091\.4347\.22Ada\-SnapKV20%48\.4229\.3457\.9055\.0522\.8256\.3232\.9330\.4210\.0899\.5043\.7325\.1547\.8942\.2072\.0092\.3647\.88Nexus Sampling20%48\.8230\.0758\.0354\.6222\.6557\.8332\.6829\.2410\.0099\.0043\.4725\.2447\.8742\.9373\.0092\.6648\.01Llama\-3\.2\-1BFull Attention100%31\.2329\.6535\.4729\.8325\.8843\.3518\.4520\.403\.674\.5016\.3521\.8436\.0439\.7761\.5078\.5431\.03SnapKV20%30\.4522\.9235\.4830\.7519\.6139\.0417\.1521\.583\.675\.0015\.0621\.1835\.8637\.4058\.0079\.3129\.53Ada\-SnapKV20%28\.5824\.0035\.7829\.7520\.5940\.8218\.2420\.872\.644\.5015\.8821\.5236\.2537\.4761\.0079\.1529\.82Nexus Sampling20%31\.8624\.5834\.5230\.7920\.9141\.8717\.5320\.755\.675\.0015\.3021\.7436\.2337\.7158\.5079\.9530\.18Qwen3\-8BFull Attention100%42\.6233\.5857\.9457\.3924\.8252\.9434\.3327\.644\.50100\.0047\.9123\.8556\.6744\.1771\.5090\.7148\.16SnapKV20%42\.3828\.7656\.9458\.0720\.2952\.7633\.9227\.966\.00100\.0043\.5523\.1756\.6043\.9066\.5090\.7146\.97Ada\-SnapKV20%42\.2530\.6657\.7357\.3620\.5752\.1234\.2827\.835\.50100\.0045\.2723\.9056\.9543\.2170\.5090\.7147\.43Nexus Sampling20%42\.4931\.7357\.6856\.9322\.1152\.5233\.7327\.445\.0099\.5043\.7223\.8956\.2343\.8571\.0091\.3647\.45

When the same head\-adaptive allocation is applied on RULER, the picture is consistent: it lifts every scoring rule, and Nexus Sampling under the Ada\-KV allocation \(Ada\-Nexus Sampling\) remains the leading method on the average across all three models, confirming that our scoring contribution composes with the orthogonal budget\-allocation axis\. Table[8](https://arxiv.org/html/2606.23961#A3.T8)reports the prefill\-only RULER results with the Ada\-KV allocation; for Qwen3\-8B we additionally report results without the chat template, since RULER’s synthetic prompts are sensitive to the template wrapping\.

Table 8:Prefill\-only RULER accuracy \(%\) across 4K–64K context lengths at20%20\\%density with the orthogonal Ada\-KV\[[8](https://arxiv.org/html/2606.23961#bib.bib11)\]head\-adaptive budget allocation applied to each scoring rule\.Boldmarks the leading method per row across the eviction methods \(Full Attention shown for reference\)\.ModelMethodDensity4K8K16K32K64KAvg\.Llama\-3\.1\-8BFull Attention100%96\.1595\.9195\.4391\.3586\.3093\.03Ada\-SnapKV20%82\.2189\.1894\.2392\.7983\.8988\.46Ada\-PyramidKV20%84\.8689\.1891\.8387\.2681\.9787\.02Ada\-Nexus Sampling20%85\.8091\.3094\.0088\.7084\.6088\.88Llama\-3\.2\-1BFull Attention100%76\.6870\.6765\.3864\.6660\.3467\.55Ada\-SnapKV20%57\.6954\.3350\.0051\.6844\.7151\.68Ada\-PyramidKV20%56\.9752\.6443\.9949\.5238\.4648\.32Ada\-Nexus Sampling20%57\.4552\.8852\.6456\.4950\.7254\.04Qwen3\-8BFull Attention100%97\.6095\.4388\.4692\.79–93\.57Ada\-SnapKV20%73\.5673\.8079\.5777\.41–76\.09Ada\-PyramidKV20%65\.3866\.1169\.9574\.28–68\.93Ada\-Nexus Sampling20%75\.4881\.4983\.4184\.38–81\.19*Qwen3\-8B without chat template\.*Qwen3\-8BFull Attention100%97\.6095\.4388\.4692\.79–93\.57Ada\-SnapKV20%81\.7389\.6688\.7090\.38–87\.62Ada\-PyramidKV20%81\.7386\.7885\.1088\.94–85\.64

## Appendix DExtended Related Work

KV cache eviction vs\. KV cache selection\.Long\-context LLM inference is bottlenecked by both the compute and the memory footprint of the KV cache, and two complementary lines of work try to address these axes\.*KV cache eviction*permanently discards tokens under a fixed memory budget, addressing memory and compute simultaneously; an evicted token is irrecoverable\.*KV cache selection*, often called*sparse attention*or query\-aware sparsity, keeps the full cache and only chooses which tokens to attend to per query, targeting compute alone; missed tokens at stepttcan be re\-selected at stept\+1t\+1\. Nexus Sampling and all baselines we compare against in §[5](https://arxiv.org/html/2606.23961#S5)are eviction methods; while representative sparse attention methods includeQuest\[[20](https://arxiv.org/html/2606.23961#bib.bib6)\],BLASST\[[24](https://arxiv.org/html/2606.23961#bib.bib9)\],Sketch\-and\-Walk\[[14](https://arxiv.org/html/2606.23961#bib.bib24)\], andSOCKET\[[13](https://arxiv.org/html/2606.23961#bib.bib26)\]\. A third axis is*lossless*compression, e\.g\.,FAFO\[[15](https://arxiv.org/html/2606.23961#bib.bib25)\], which drafts off a lossy compressed cache and verifies in parallel against the full cache to recover bitwise\-identical generation\. Nexus Sampling is orthogonal to both: any selection method can be applied on top of the surviving cache after eviction has run, and lossless schemes like FAFO still need an underlying retention policy when the full cache no longer fits\.

KV cache eviction\.Existing eviction methods are best understood as different choices of the*score*fed to a shared deterministic top\-KKselection rule, and have been comprehensively benchmarked across long\-context tasks alongside other compression families byYuanet al\.\[[23](https://arxiv.org/html/2606.23961#bib.bib27)\]\.StreamingLLM\[[22](https://arxiv.org/html/2606.23961#bib.bib7)\]hard\-codes a sink\-plus\-recency retention rule, motivated by the attention\-sink phenomenon they identify at the first few absolute positions\.H2O\[[25](https://arxiv.org/html/2606.23961#bib.bib5)\]retains*heavy hitter*tokens by ranking on cumulative attention over the generation so far, formulating eviction as a dynamic submodular problem\.SnapKV\[[16](https://arxiv.org/html/2606.23961#bib.bib12)\]computes the score against an observation window of the most recent prompt tokens, which it shows are sufficient to identify the important positions for upcoming decode steps\.PyramidKV\[[3](https://arxiv.org/html/2606.23961#bib.bib10)\]introduces a layer\-wise budget allocation that retains more tokens in lower layers and fewer in higher ones, motivated by the pyramidal information\-funneling pattern of attention\.Ada\-KV\[[8](https://arxiv.org/html/2606.23961#bib.bib11)\]adapts the budget across heads instead of layers, exploiting the empirical observation that different heads concentrate their attention on different scales of the cache\.MorphKV\[[9](https://arxiv.org/html/2606.23961#bib.bib13)\]maintains a constant\-size cache by correlation\-aware ranking against recent tokens, iteratively refining the retained set with lightweight updates\. Despite the diversity of scoring strategies, every method above commits to the surviving tokens by deterministic top\-KKat each step, and is therefore subject to the irreversible\-verdict failure mode of §[3](https://arxiv.org/html/2606.23961#S3)regardless of how good its score is\. Nexus Sampling is the first eviction method, to our knowledge, to replace the selection primitive itself rather than refine the score only\.

Reservoir sampling\.Classical reservoir sampling for streaming uniform sampling traces toChao \[[4](https://arxiv.org/html/2606.23961#bib.bib16)\]andVitter \[[21](https://arxiv.org/html/2606.23961#bib.bib14)\];Efraimidis and Spirakis \[[7](https://arxiv.org/html/2606.23961#bib.bib15)\]extended the scheme to weighted\-without\-replacement sampling via the priorityuj1/wju\_\{j\}^\{1/w\_\{j\}\}, which is exactly the per\-step primitive Nexus uses\. We instantiate this rule as an eviction primitive and add thenn\-fold averaged variant of §[2\.3](https://arxiv.org/html/2606.23961#S2.SS3), which interpolates between unbiased \(n=1n=1\) and effectively deterministic \(n→∞n\\to\\infty\) retention with a single knob, recovering the existing deterministic\-top\-KKtemplate as a limit case\.

Connection to Sketch\-and\-Walk\.Leet al\.\[[14](https://arxiv.org/html/2606.23961#bib.bib24)\]introduce a multi\-hop walk for sparse*attention*over a full cache, propagating block importance*across layers*by composing per\-layer block\-attention matrices through an iterative recurrence\. The Nexus walk of §[2\.2](https://arxiv.org/html/2606.23961#S2.SS2)is structurally analogous but operates on an orthogonal dimension: it propagates importance*across tokens*, using the per\-window per\-query distribution to expose bridge tokens that no single recent query attends to strongly\. The two are therefore complementary rather than competing, addressing two stages of the same pipeline: Sketch\-and\-Walk reduces the cost of reading from a still\-full cache, while Nexus Sampling decides which tokens survive into that cache\.