1 Introduction↩︎

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 [1], [2]. The gap widens further in long-lived, agent-style deployments such as multi-turn assistants, persistent reasoning loops [3], and repository-scale coding agents [4], [5], where the effective context grows toward an unbounded stream. Sparse attention methods [6]–[8] 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 [9]–[14] 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 the \(K\) highest-scoring tokens by deterministic top-\(K\) selection. We argue, however, that eviction 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-\(K\) is 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-\(K\) misses tokens whose importance fluctuates. Per-step importance scores in KV caches are noisy and time-varying. Attention in modern LLMs is heavy-tailed [7], [9]: 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). A token important to query \(t\) may look marginal at \(t\!+\!1\) and important again at \(t\!+\!10\). Top-\(K\), 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.

Reservoir sampling is the streaming-algorithms answer to this setting. Weighted reservoir sampling [15], [16] 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-\(K\) evicts 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 propose Nexus 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 the \(K\) retained tokens with inclusion probability proportional to this walk-augmented weight, replacing the deterministic top-\(K\) selection 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-\(K\) misses, and the reservoir recovers the marginal-rank tokens that any deterministic top-\(K\) erodes. Theoretically, Nexus’s long-run token survival decays as a product of per-step inclusion probabilities (a mean over steps), where deterministic top-\(K\)’s collapses to zero on the first below-cutoff step (details in App. 8). The contributions are:

• We identify a fundamental limitation of deterministic-top-\(K\) KV 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 propose Nexus 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-\(K\)’s is a min over steps, and empirically demonstrate at \(20\%\) density that Nexus Sampling stays within \(\sim\)​1 point of dense attention on LongBench while outperforming top-\(K\) baselines on retrieval-heavy long-context tasks, with up to \(10\times\) smaller per-sequence cache memory than dense FlashAttention-2.

2 Nexus Sampling↩︎

We introduce Nexus Sampling, a KV cache eviction method that runs alongside decoding: at every eviction step \(t\) (whenever the budget is hit during the decoding stream), Nexus produces the retention set \(S_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 \(\mathbf{w}^{(t)}\) that reflects indirect importance. The reservoir step then draws the \(K\) retained blocks with inclusion probability proportional to \(\mathbf{w}^{(t)}\) under the weighted-without-replacement law, replacing the deterministic top-\(K\) selection 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.1 Preliminaries and Notation↩︎

Streaming view. We treat KV cache eviction as a streaming problem over the steps of inference. At each step \(t\), the LLM ingests one new query \(q_t \in \mathbb{R}^{1 \times D}\) (a prompt token during prefill or a decoded token during decode), attends over the current cache \(K_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 subset \(S_t \subseteq \{1,\dots,T_t\}\) of \(B\) positions is retained, the rest are dropped, and inference continues with \(K_{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 step \(t\) are not recoverable at any step \(t' > t\).

Block granularity. We work at the granularity of key blocks rather than individual tokens, amortizing the per-decision cost over \(b\) tokens (\(b=32\)); blocks are indexed by \(j \in \{1,\dots,N_k\}\) with \(N_k = \lceil T_k / b \rceil\) where \(T_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 [13], [14] we score blocks against a length-\(W\) observation window of recent queries \(\mathbf{Q} \in \mathbb{R}^{W \times D}\) on head-averaged representations. The per-block base score \(\mathbf{a} \in \mathbb{R}^{N_k}\) is the row average of \(\widehat{\mathbf{S}} = \operatorname{rownorm}(\operatorname{BlockSum}_b(\operatorname{softmax}(\mathbf{Q}\mathbf{K}^\top / \sqrt{D})))\): \[\mathbf{a} = \tfrac{1}{W} \textstyle\sum_{w=1}^{W} \widehat{\mathbf{S}}_{w,\cdot},\quad \textstyle\sum_j a_j = 1, \label{eq:base-score}\tag{1}\]

Notation. Throughout the rest of the section we use \(W\) for the observation-window length, \(\widehat{\mathbf{S}} \in \mathbb{R}^{W \times N_k}\) for the per-row block distribution, \(\mathbf{a} \in \mathbb{R}^{N_k}\) for the base score (Eq. 1 ), \(\mathbf{c} \in \mathbb{R}^{N_k}\) for the walk state, \(\mathbf{w} \in \mathbb{R}^{N_k}\) for the combined sampling weight, \(B\) for the total retained-block budget, and \(n\) for the reservoir averaging count. A full notation table appears in App. 8.1.

2.2 Nexus Scoring↩︎

Nexus scoring assigns each block a two-term Nexus score \[s_j = a_j + \lambda\,\tilde{c}_j, \label{eq:nexus-score}\tag{2}\] that captures both the direct importance \(a_j\) of block \(j\) (how much the recent queries attend to it) and an indirect importance \(\tilde{c}_j\) that measures how strongly block \(j\) acts 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: \(a_j\) scores blocks the current query has reason to look at; \(\tilde{c}_j\) scores blocks the current query has reason to remember, by virtue of their role in the recent context. The mixing weight \(\lambda \geq 0\) balances the two terms.

Both terms are computed from the same per-query rows of \(\widehat{\mathbf{S}}\). Denote the rows by \(\mathbf{a}^{(q)} \in \mathbb{R}^{N_k}\), so \(\mathbf{a}^{(q)} = \widehat{\mathbf{S}}_{q,\cdot}\) is the block distribution of window query \(q\). The direct importance is the uniform row-average, \[\mathbf{a} \;=\; \tfrac{1}{W} \textstyle\sum_{q=1}^{W} \mathbf{a}^{(q)}, \label{eq:direct}\tag{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 for \(H\) steps; at each step we plug in a fresh window query row \(\mathbf{a}^{(q)}\) and update \[\mathbf{C} \;\leftarrow\; \mathbf{C} + \gamma_q\,\mathbf{a}^{(q)},\qquad \gamma_q = 1 + \langle \mathbf{a}^{(q)},\,\mathbf{C}\rangle, \label{eq:walk}\tag{4}\] from which \(\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, \[w_j = s_j + \varepsilon_{\text{tie}}\,r_j,\quad r_j = j/(N_k - 1), \label{eq:combined}\tag{5}\] with \(r_j\) a linear ramp from \(0\) (oldest block) to \(1\) (newest), and \(\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.3 Weighted Reservoir Block Selection↩︎

Given the per-block weight \(\mathbf{w} \in \mathbb{R}^{N_k}\) from §2.2, the reservoir step decides which \(K\) of the \(N_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 for \(B_{\text{forced}}\) slots of the total budget \(B\), leaving \(K = B - B_{\text{forced}}\) slots for the reservoir step below.

\(n\)-averaged reservoir priority. For every remaining candidate block \(j\), we draw \(n\) independent uniform variates \(u_j^{(1)},\dots,u_j^{(n)} \sim \mathcal{U}(0,1)\) and form the \(n\)-averaged reservoir priority \[\pi_j = \frac{1}{n}\sum_{i=1}^{n} \bigl(u_j^{(i)}\bigr)^{1/w_j}. \label{eq:ares}\tag{6}\] We then keep the top \(K\) candidates by \(\pi_j\).

3 Why 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 the \(K\) surviving tokens are picked by deterministic top-\(K\). 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). 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-\(K\) erases subtly important tokens at the cutoff; the reservoir preserves them. A streaming eviction policy is applied at every step, and under deterministic top-\(K\) a token at rank \(K\!+\!1\) is dropped with the same finality as a token at rank \(10^6\), so a token survives the first \(e\) steps 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 [16] 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 \[p_j^{(e)} \;=\; \prod_{e' \leq e} \Pr\!\bigl(j \in \mathrm{top}\text{-}K\text{ by }\pi^{(e')}\bigr)\] stays bounded away from zero whenever \(w_j^{(e')}\) does (§2.3; Lemma 1). 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 [7], [9] rather than in the head. Even a perfect selection rule cannot recover such a token from this score, because sampling (or top-\(K\)) proportional to a weight that does not see the structural signal samples from the wrong distribution. The bridge term \(\tilde{c}_j\) in the Nexus score (§2.2) 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 1). 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-\(K\) the 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 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.

4 Theoretical Guarantees↩︎

The arguments of §3 have formal counterparts. The reservoir’s long-run survival decays as a product over eviction steps where deterministic top-\(K\)’s collapses to zero on the first below-cutoff step (Lemma 1), the walk provably amplifies hub tokens above the uniform window average (Theorem 1), and the two together yield an end-to-end bound on per-step eviction quality (Proposition 2). Proofs and supporting lemmas are deferred to App. 8.

Lemma 1 formalizes the min-vs-product contrast from §3: deterministic top-\(K\) converts 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 1 formalizes the bridge-recovery claim of §3: the walk does not merely denoise the direct score, it injects a block-dependent term proportional to the hub score \(h_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. 8.2), 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 1. Lemma 1 and Theorem 1 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. Let \(z_j \geq 0\) denote the utility that block \(j\) would contribute to future attention if it remained in cache (e.g., its future block-attention mass over a short horizon).

Proposition 2 separates the two sources of approximation: the reservoir step (Lemma 1) 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 1) is designed to improve over the direct score \(\mathbf{a}\).

5 Experiments↩︎

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

5.1 Setup↩︎

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 [17], spanning single- and multi-document QA, summarization, to few-shot tasks; and (ii) RULER [18], 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 against SnapKV [13] and PyramidKV [11] in the prefill-only setting and against H2O [9] and MorphKV [14] in the prefill + decode setting, with Full Attention as an upper-reference. We additionally report Ada-KV variants (Ada-SnapKV, Ada-PyramidKV), which layer the head-adaptive budget allocation of [12] on top of each score; see Appendix 10 for the isolated comparison. All methods are at \(20\%\) density (80% eviction).

Implementation details. We implement Nexus Sampling on top of HuggingFace Transformers, with block-wise eviction at block size \(b = 32\) and dense attention on the retained cache served by FlashAttention-2 kernels [19]. Observation window \(W = 16\); walk depth \(H = 3\); mixing weight \(\lambda = 0.5\); tie-break magnitude \(\varepsilon_{\text{tie}} = 10^{-6}\); reservoir averaging \(n = 5\). Because the reservoir step is stochastic, all reported numbers use a fixed random seed; the \(n=5\) priority averaging (Eq. 6 ) further suppresses per-seed variation, which we find negligible relative to the gaps in Tables 1–2. All experiments run on a single NVIDIA H200 (143 GB) with greedy decoding.

5.2 LongBench Results↩︎

2.3pt

Table 1 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 1) 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-\(K\) baselines (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-\(K\) drops once its score dips below the cutoff and that reservoir sampling instead keeps alive at a controlled rate.

5.3 RULER Across Context Lengths↩︎

3pt

Table 2 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 \(\sim\)​3 points on Llama-3.1-8B on average, while SnapKV loses \(15\)–\(25\) points; on the smaller Llama-3.2-1B the gap to SnapKV widens further (\(60.58\) vs.\(38.41\) on average). In prefill + decode, the same pattern is amplified: H2O and MorphKV both sit \(\sim\)​20 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 \(\sim\)​1.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.81\) vs.H2O \(36.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-\(K\) silently erodes the relevant tokens while reservoir sampling does not.

5.4 Agentic 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 on \(50\) tasks sampled from SWE-bench [5]. Concretely, we use DeepSWE-Preview [20], trained on top of Qwen3-32B within the R2E-Gym environment [21]. 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.

6pt

Table ¿tbl:tab:agentic? 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 from \(7\)/\(6\) to \(1\)/\(1\) once their evicted tokens can no longer be recovered, the failure mode an irreversible deterministic top-\(K\) verdict induces, whereas Nexus Sampling remains stable at \(8\) and matches the best baseline. In the hardest Prefill + Decode \(\cdot\) True eviction setting, Nexus Sampling stays competitive at 8, one task behind MorphKV and ahead of H2O.

5.5 Ablations↩︎

Nexus Sampling is robust to its hyperparameters: across walk depth \(H\), mixing weight \(\lambda\), observation window \(W\), block size \(b\), and density (Figure 3), the defaults of §5.1 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 by \(H = 3\) and is indistinguishable from \(H = 5\), matching the rank-1 propagation analysis of §4: a few walk steps are enough to surface bridge tokens, and additional iterations only resharpen what is already there, so \(H\) does not need per-task tuning. Second, accuracy is essentially flat from \(20\%\) to \(80\%\) density on all three tasks, confirming the aggressive setting we report in §5.2–5.3 loses no accuracy headroom; this is the empirical signature of the marginal-mass argument of §3, where reservoir sampling preserves subtly important tokens that deterministic top-\(K\) would erode rather than collapsing on the first below-cutoff step. Details discussion appears in App. 9.

5.6 Inference 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 length \(T_p = 8\text{K}\), batch size 1, against dense FlashAttention-2 [19] and the baselines from Tables 1–2.

2pt

Decode throughput. Table 3 reports decode-time throughput and per-step latency across decode lengths \(D \in \{4\text{K}, 8\text{K}, 16\text{K}\}\). Nexus Sampling delivers \(1.22\)–\(1.30\times\) throughput and \(15\)–\(23\%\) lower per-step latency over dense FlashAttention-2, beating both SnapKV and MorphKV at every \(D\).

6pt

Per-sequence memory. Table 4 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 saves \(5.0\text{--}10.0\times\) over dense FlashAttention-2, with the saving growing with \(D\) because the dense cache scales as \(T_p + D\) while Nexus pins the working cache at a constant \(20\%\) density of \(T_p\); at \(D = 32\text{K}\) this \(10\times\) reduction translates into a comparable factor in achievable batch size on the same GPU.

6 Related Work↩︎

We situate Nexus Sampling within the broader landscape of KV cache compression and reservoir sampling. KV cache eviction methods (StreamingLLM [10], H2O [9], SnapKV [13], PyramidKV [11], Ada-KV [12], and MorphKV [14]) all reduce to different scoring strategies fed into the same deterministic top-\(K\) selection rule, leaving them vulnerable to the irreversible-verdict failure mode discussed in §3. Nexus Sampling is orthogonal to KV cache selection (sparse attention) methods such as Quest [6], BLASST [8], and Sketch-and-Walk [7], 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 [15], [16], [22]. See Appendix 11 for a detailed discussion of each method and its relationship to our approach.

7 Conclusion↩︎

We presented Nexus Sampling, a training-free KV cache eviction method that pairs an iterative walk surfacing bridge tokens with weighted reservoir sampling, replacing the deterministic top-\(K\) selection 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, at \(80\%\) KV cache eviction, Nexus Sampling matches dense attention within \(\sim\)​1 point on LongBench while outperforming top-\(K\) baselines on retrieval-heavy long-context tasks, with up to \(10\times\) smaller 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.

8 Theoretical Analysis↩︎

This appendix gives full proofs for the three statements of §4 (Lemma 1, Theorem 1, and Proposition 2), together with several supporting statements that we develop only here: reservoir unbiasedness (Lemma 2), \(n\)-averaged concentration (Lemma 3), window noise reduction (Lemma 4), and the walk decomposition that underlies Theorem 1 (Lemma 5). Main-text statements are restated verbatim (or in a slightly expanded form when convenient for the proof); appendix-only statements are presented in full.

8.1 Notation↩︎

8.2 Reservoir Sampling: Unbiasedness and Concentration↩︎

The statement above is intentionally phrased in terms of inclusion probabilities \(p_j\) rather than the simplified formula \(K w_j/\sum_{j'}w_{j'}\). For fixed-size weighted sampling without replacement, the exact marginal \(p_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.

Because \(w_j/(w_j+1)\) is strictly increasing in \(w_j\), the deterministic limit induces the same ordering as top-\(K\) by \(w_j\) directly. The averaging count \(n\) is therefore a single-knob interpolation between unbiased sampling (Lemma 2) and deterministic top-\(K\) (\(n \to \infty\)), with no other change to the pipeline.

8.3 Streaming Marginal-Mass Survival↩︎

Lemma 1 (Min over steps vs.product over steps; restated). Consider a sequence of eviction steps \(e = 1,\dots,E\) with per-step weights \(w_j^{(e)} > 0\) and a fixed retention budget \(K\) at every step. Let \(S_j^{\text{top-}K}(E)\) and \(S_j^{\text{res}}(E)\) denote the long-run survival probability of block \(j\) under deterministic top-\(K\) and reservoir sampling respectively. Then \(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 has \(w_j^{(e)} < w_{(K)}^{(e)}\); while \(S_j^{\text{res}}(E) = \prod_{e=1}^E q_j^{(e)}\) with \(q_j^{(e)} \in (0,1]\) strictly positive whenever \(w_j^{(e)} > 0\).

This is the precise sense in which the reservoir step is the right primitive for the streaming-budget regime: deterministic top-\(K\) converts 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.

8.4 Window Averaging as Noise Reduction↩︎

The bound is the standard \(1/\sqrt{W}\) noise-reduction rate, with the \(N_k\)-dimensional union bound contributing only a \(\log N_k\) factor. The implication for the reservoir step is that a modest window length (\(W \approx 16\)–\(32\)) suffices to bring the per-block noise floor on the reservoir’s input weights below the typical scale of meaningful per-block weight differences.

8.5 Eviction Quality Under Approximate Future Utility↩︎

We restate Proposition 2 of §4 in its full three-part form (the main-text statement combines parts 1 and 2 into a single bound) and prove it. Let \(z_j \geq 0\) denote the utility that block \(j\) would contribute to future attention if it remained in cache; this can be instantiated as future block-attention mass, or as a value-norm-weighted utility \(z_j=\sum_{\tau} \alpha_{\tau j}\|V_j\|\) over a short future horizon.

Proposition 2 (restated and extended). Fix one cache-update event and let \(I_j\) be the reservoir-sampling inclusion indicator with inclusion probability \(p_j=\Pr(I_j=1)\). For any deterministic future-utility vector \(\mathbf{z}\):

1. The Horvitz–Thompson retained-utility estimator \[\widehat{Z}_{\mathrm{HT}}=\sum_{j=1}^{N_k}\frac{I_j z_j}{p_j}\] is unbiased for the full-cache utility \(Z=\sum_j z_j\).

2. If \(p_j\geq p_{\min}>0\) and \(0\leq z_j\leq Z_{\max}\), then with probability at least \(1-\delta\), \[|\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{K N_k}{\delta p_{\min}}}.\]

3. If the Nexus weight approximates future utility as \(\| \mathbf{w}-\mathbf{z}\|_\infty\leq\eta\), then the expected evicted utility \(L=\sum_j(1-I_j)z_j\) satisfies \[\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 .\]

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 4 reduces estimation noise in direct utility, while Theorem 1 raises the weight of hub blocks whose future utility is indirect rather than visible in one-hop attention.

8.6 Multi-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 1.

The first term is the unwalked window aggregate (essentially \(W \mathbf{a}\) if all window rows are used). The second term is the genuinely multi-hop contribution: each \(\mathbf{M}_q\) is a rank-1 affinity matrix encoding which block pairs query \(q\) connects, and \(\mathbf{M}_q\,\mathbf{C}^{(q-1)}\) aggregates the accumulated walk under that affinity structure. The depth \(H\) controls the highest-order hop captured; as in [7], small \(H\) (e.g., \(H = 3\)) suffices in practice because effective composed attention depth in transformer stacks is empirically shallow.

8.6.1 Hub Amplification (Main Theorem)↩︎

We first record the i.i.d.stationarity assumption and the formal definition of a hub block, then restate Theorem 1 with the full intermediate quantities and prove it.

Theorem 1 (restated and extended). Under Assumption 1, the Nexus walk (Eq. 4 ) with \(H\) steps satisfies \[\mathbb{E}[C_j^{(H)}] \;=\; B_H\,a_{\star,j} \;+\; D_H\,h_j \;+\; O(H\,\|\boldsymbol{\Sigma}\|_F^2), \label{eq:hub}\tag{7}\] where \(B_H = \sum_{q=1}^H \mathbb{E}[\gamma_q] \geq H\) is a block-independent amplification factor, \(D_H = \sum_{q=1}^{H-1} B_q \geq H(H-1)/2\) is the cumulative covariance-boost coefficient, and the \(O(\cdot)\) term captures second-order covariance interactions. Since \(\sum_j h_j = 0\) (Lemma 5), \(L_1\)-normalization gives \[\begin{align} \mathbb{E}[\tilde{c}_j^{(H)}] &\;=\; a_{\star,j} + \tfrac{D_H}{B_H}\,h_j + O(\|\boldsymbol{\Sigma}\|_F^2); \\ &\text{in particular,}\quad \mathbb{E}[\tilde{c}_j^{(H)}] \;\gtrless\; a_{\star,j} \;\Longleftrightarrow\; h_j \;\gtrless\; 0. \end{align}\] Furthermore, hub blocks have strictly higher expected sampling weight \(\mathbb{E}[w_j]\); by the monotonicity of inclusion probability in \(w_j\) (Lemma 2), their expected inclusion probability \(\mathbb{E}[p_j]\) is strictly higher than the window average \(\mathbf{a}\) alone would predict.

Remark. Assumption 1 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.

9 Detailed Ablations↩︎

This appendix expands §5.5, walking through each panel of Figure 3. All settings match §5.1: Llama-3.1-8B at \(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 depth \(H\). \(H = 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 \geq 1\) adds 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 \in \{2, 3\}\) captures the bulk of the gain and \(H = 5\) is essentially indistinguishable from \(H = 3\), matching the rank-1 propagation analysis of App. 8: 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 to \(H = 3\), which keeps the bridge-token benefit while leaving the per-step cost negligible relative to dense attention.

Mixing weight \(\lambda\). \(\lambda = 0\) closes most of the gap to Nexus but stays consistently below \(\lambda > 0\) on 2WikiMQA, confirming that the bridge term contributes signal beyond what direct attention already captures. \(\lambda = 1.0\) overweights 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 \(\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 \(\lambda = 0.5\) throughout.

Observation window \(W\). Small windows (\(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 \(\sim\)​5–10 points at \(W = 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 = 16\) is 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 [13], [14].

Block size \(b\). \(b \in \{16, 32, 64\}\) are within noise of one another, while \(b \geq 128\) degrades 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 small \(b\) is 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 to \(b = 32\), which is the smallest block size that lets the kernel achieve full memory-bandwidth utilization on the H200.

Density. Accuracy is essentially flat from \(20\%\) to \(80\%\) density on all three tasks, confirming that the aggressive \(20\%\) setting we report in §5.2–5.3 does not give up accuracy headroom to less aggressive configurations. This is the empirical signature of the marginal-mass argument of §3: under reservoir sampling, even tight budgets retain the subtly important tokens that deterministic top-\(K\) would 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.

10 Comparison with Head-Adaptive Budget Allocation (Ada-KV)↩︎

Ada-KV [12] 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.

Table 6 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.

2.3pt

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 7 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.

3pt

11 Extended 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 step \(t\) can be re-selected at step \(t+1\). Nexus Sampling and all baselines we compare against in §5 are eviction methods; while representative sparse attention methods include Quest [6], BLASST [8], Sketch-and-Walk [7], and SOCKET [23]. A third axis is lossless compression, e.g., FAFO [24], 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-\(K\) selection rule, and have been comprehensively benchmarked across long-context tasks alongside other compression families by [25]. StreamingLLM [10] hard-codes a sink-plus-recency retention rule, motivated by the attention-sink phenomenon they identify at the first few absolute positions. H2O [9] retains heavy hitter tokens by ranking on cumulative attention over the generation so far, formulating eviction as a dynamic submodular problem. SnapKV [13] 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 [11] 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 [12] 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 [14] 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-\(K\) at each step, and is therefore subject to the irreversible-verdict failure mode of §3 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 to [22] and [15]; [16] extended the scheme to weighted-without-replacement sampling via the priority \(u_j^{1/w_j}\), which is exactly the per-step primitive Nexus uses. We instantiate this rule as an eviction primitive and add the \(n\)-fold averaged variant of §2.3, which interpolates between unbiased (\(n=1\)) and effectively deterministic (\(n \to \infty\)) retention with a single knob, recovering the existing deterministic-top-\(K\) template as a limit case.

Connection to Sketch-and-Walk. [7] 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 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.

References↩︎

---

1. Equal contribution. Contact: el72@rice.edu and zhaozhuo.xu@workato.com.↩︎