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

As LLMs process increasingly long contexts, the Key-Value (KV) cache often exceeds available GPU memory, necessitating permanent token eviction during inference. Existing methods typically use deterministic top-K selection based on direct attention scores. The authors argue that this approach is fundamentally flawed for streaming, as it treats transiently marginal tokens as permanently unimportant, leading to the irreversible loss of information that may be critical for future queries.

The authors introduce Nexus Sampling, a training-free eviction method consisting of two primary components:

1. Nexus Scoring: Instead of relying solely on direct attention, this mechanism uses an iterative walk over recent query-attention rows. This process surfaces "bridge tokens"—tokens that anchor strongly-connected clusters of information across the context, even if they do not receive high attention from any single query.
2. Weighted Reservoir Sampling: This replaces the deterministic top-K selection. By assigning tokens an inclusion probability proportional to their Nexus score, the method ensures that tokens with marginal importance have a non-zero probability of survival, preventing the "monotone marginal erosion" seen in deterministic approaches.

Theoretically, the authors demonstrate that while deterministic top-K survival collapses to zero as soon as a token's score falls below a threshold, Nexus Sampling allows survival probability to decay as a product of per-step inclusion probabilities, keeping subtly important tokens alive longer. Empirically, at 80% cache eviction, Nexus Sampling maintains performance within 1 point of dense attention on the LongBench benchmark and outperforms existing baselines on retrieval-heavy tasks, all while requiring up to 10x less memory per sequence.