KV Cache Eviction and Streaming Attention: Mathematical Foundations, Attention Sink Mechanics, Heavy Hitter Oracles (H2O), and Bounded-Memory Generation

In autoregressive transformer generation, memory consumption and serving throughput are dominated by the Key-Value (KV) cache. For long-context generation and continuous multi-turn dialogue, the linear growth of the KV cache with sequence length imposes an unsustainable memory footprint and saturates high-bandwidth GPU memory channels.

Standard sliding-window attention fails catastrophically when applied naively to pretrained models, causing immediate perplexity explosion once input sequences exceed the window boundary. Recent developments in attention dynamics, specifically the discovery of attention sinks in StreamingLLM (Xiao et al., 2023) and dynamic importance tracking in H2O: Heavy-Hitter Oracle (Zhang et al., 2023), provide mathematical frameworks for bounded-memory generation without fine-tuning.

1. The KV Cache Memory Bottleneck in Autoregressive Generation

During autoregressive decoding, generating token $x_{T+1}$ requires computing attention against all previous tokens $x_1, \dots, x_T$. To avoid recomputing Key and Value projections at every generation step, inference engines cache previous key and value vectors in high-bandwidth memory (HBM).

Memory Footprint Scaling

For a model with $L$ layers, hidden dimension $d$, $n_{\text{kv\_heads}}$ key-value heads, head dimension $d_k = d / n_{\text{heads}}$, sequence length $T$, batch size $B$, and numerical precision of $b$ bytes (e.g., 2 bytes for FP16/BF16), the total memory required by the KV cache is:

$$M_{\text{KV}} = 2 \times B \times T \times L \times n_{\text{kv\_heads}} \times d_k \times b$$

+-----------------------------------------------------------------------------+
|                     KV CACHE MEMORY CONSUMPTION SCALING                     |
+-------------------+---------------------+-----------------+-----------------+
| Model             | Context Length (T)  | Batch Size (B)  | KV Cache Memory |
+-------------------+---------------------+-----------------+-----------------+
| Llama 3 8B (BF16) | 8,192 tokens        | 1               | 1.07 GB         |
| Llama 3 8B (BF16) | 128,000 tokens      | 1               | 16.78 GB        |
| Llama 3 8B (BF16) | 128,000 tokens      | 16              | 268.43 GB       |
| Llama 3 70B(BF16) | 128,000 tokens      | 1               | 41.94 GB        |
| Llama 3 70B(BF16) | 128,000 tokens      | 16              | 671.09 GB       |
+-------------------+---------------------+-----------------+-----------------+

Memory Bandwidth Bound During Decoding

Autoregressive decoding generates tokens one by one. For each token generated, the model must read all stored KV vectors across all layers from GPU HBM into SRAM:

$$\text{Bytes Read per Token} = 2 \times B \times T \times L \times n_{\text{kv\_heads}} \times d_k \times b$$

While matrix multiplication during the prefill phase is compute-bound, single-token generation during the decode phase is memory-bandwidth-bound. As $T$ scales into tens or hundreds of thousands of tokens, reading the KV cache saturates GPU memory bandwidth, driving per-token decoding latency upward and collapsing batch concurrency.

2. The Failure of Naive Sliding-Window Attention

An intuitive approach to bounding KV cache memory is sliding-window attention: retaining only the most recent $W$ tokens in the KV cache and discarding tokens with index $t < T - W + 1$.

Naive Sliding Window (Window Size W = 4):
Step 1: [T1] [T2] [T3] [T4]          -> Perplexity Normal
Step 2: [T2] [T3] [T4] [T5] (Evict T1)-> Perplexity Explodes (PPL -> 10^3+)

When a standard pretrained causal transformer encounters naive sliding-window truncation, model perplexity immediately explodes (often exceeding $10^3$ or producing degenerate repetitions) as soon as the very first token ($x_1$) is evicted from the cache.

Recomputing the KV states across a sliding window over the entire prompt restores performance but requires $\mathcal{O}(W \cdot T)$ quadratic computation, eliminating the throughput advantages of caching.

3. Mathematical Foundations of the Attention Sink Phenomenon

The catastrophic failure of naive window attention was explained by Xiao et al. (2023) through the identification of attention sinks.

Softmax Normalization Dynamics

Standard scaled dot-product attention computes attention weights $\alpha_{i, j}$ for query $q_i$ at position $i$ over keys $k_1, \dots, k_i$:

$$\alpha_{i, j} = \frac{\exp\left(\frac{q_i^\top k_j}{\sqrt{d_k}}\right)}{\sum_{m=1}^i \exp\left(\frac{q_i^\top k_m}{\sqrt{d_k}}\right)}$$

Because the softmax function enforces a strict sum-to-one constraint:

$$\sum_{j=1}^i \alpha_{i, j} = 1$$

every layer must distribute a total probability mass of 1 across all visible positions $j \le i$.

The Numerical Sink Hypothesis

In autoregressive language modeling, not all query tokens require semantic context from preceding tokens (e.g., punctuation, syntactic connectors, or transitions). However, because the softmax denominator cannot be zero, the model must assign the remaining unneeded probability mass to some token position.

Because the initial token $x_1$ (and immediate successors $x_2, \dots, x_4$) is visible to every single token across the entire causal attention mask, early training iterations condition the model to use the initial tokens as an implicit numerical sink:

$$\alpha_{i, 1} \gg 0 \quad \forall i \gg 1$$

Empirical measurements across LLaMA, Falcon, MPT, and Mistral architectures reveal that even when the initial tokens carry zero semantic relevance to the current query, attention heads consistently allocate between 30% and 80% of their total attention mass to the first 1 to 4 tokens across middle and deeper layers.

Attention Distribution Across Context Positions:
Position:      [x1]    [x2]    ...    [x_{T-3}]  [x_{T-2}]  [x_{T-1}]  [x_T]
Attn Score:   0.52    0.18           0.04       0.06       0.08       0.12
Role:        [-- Attention Sink --]  [------- Semantic Local Window -------]

When naive window eviction discards $x_1$, the denominator of the softmax function loses its primary stabilizing mass:

$$\sum_{m=T-W+1}^i \exp\left(\frac{q_i^\top k_m}{\sqrt{d_k}}\right) \ll \sum_{m=1}^i \exp\left(\frac{q_i^\top k_m}{\sqrt{d_k}}\right)$$

This forces arbitrary and erratic redistribution of large probability masses across the remaining local tokens, destroying the calibrated variance of the hidden representations and causing immediate perplexity collapse.

4. StreamingLLM: Retaining Sinks for Infinite Decoding

StreamingLLM (Xiao et al., 2023) exploits the attention sink phenomenon to achieve stable, bounded-memory generation over arbitrary sequence lengths without fine-tuning.

+-----------------------------------------------------------------------------+
|                     STREAMINGLLM KV CACHE REORGANIZATION                    |
+-----------------------------------------------------------------------------+
| Logical Sequence:   [x1] [x2] [x3] [x4] ... [x_{T-3}] [x_{T-2}] [x_{T-1}] [x_T] |
|                                                                             |
| Retained Cache:    |-- Sinks (K=4) --|     |--- Rolling Window (W=1020) ---|
| Memory Layout:     [K1,V1] [K2,V2] [K3,V3] [K4,V4] | [K_{T-3},V_{T-3}] ... [K_T,V_T]|
| Evicted Slots:     Tokens between index K and T-W are discarded from HBM     |
+-----------------------------------------------------------------------------+

Cache Structure Formulation

StreamingLLM partitions the KV cache into two fixed-size buffers:

1. Sink Tokens ($S_{\text{sink}}$): The first $K$ tokens (typically $K = 4$).
2. Rolling Window Tokens ($S_{\text{window}}$): The most recent $W$ tokens (e.g., $W = 1020$ or $2044$).

The total cached token set at step $T$ is defined as:

$$\mathcal{C}_T = \{1, 2, \dots, K\} \cup \{T - W + 1, T - W + 2, \dots, T\}$$

The total cache capacity remains strictly constant:

$$|\mathcal{C}_T| = K + W \quad \forall T \ge K + W$$

Positional Embedding Re-indexing

When using Rotary Position Embeddings (RoPE) or ALiBi, assigning absolute positional indices directly to the truncated cache causes distributional shifts because relative distance gaps appear between position $K$ and position $T - W + 1$.

StreamingLLM resolves this by assigning logical continuous positions to the cached tokens rather than their original absolute positions in the text stream:

$$p(j) = \begin{cases} j & \text{if } j \le K \\ K + (j - (T - W + 1)) + 1 & \text{if } j > K \end{cases}$$

This ensures that the attention mechanism perceives a contiguous sequence of length $K + W$, matching the positional distribution encountered during pretraining.

Complexity Characteristics

Under StreamingLLM:

• KV Cache Memory: $\mathcal{O}(K + W)$, strictly independent of total generated sequence length $T$.
• Per-Token Generation Latency: $\mathcal{O}(K + W)$, strictly constant.
• Sequence Length Horizon: Validated up to 4,000,000+ continuous tokens with stable language modeling perplexity.

5. Heavy Hitter Oracle (H2O): Dynamic Accumulated Score Eviction

While StreamingLLM maintains a static combination of initial sinks and recent tokens, it discards all intermediate semantic tokens, regardless of their intrinsic importance.

H2O: Heavy-Hitter Oracle (Zhang et al., 2023) introduces dynamic importance-based KV cache eviction by observing that attention scores across sequence generation follow a heavy-tailed power-law distribution.

+-----------------------------------------------------------------------------+
|                     HEAVY-HITTER ATTENTION ACCUMULATION                     |
+-----------------------------------------------------------------------------+
| Prompt / Generated Stream:                                                  |
| [Sink] ... [Punctuation] ... [Key Entity] ... [Common Word] ... [Recent]     |
|   ||              |               ||                |              ||       |
| High Mass     Low Mass        High Mass         Low Mass       High Mass    |
| (Retained)    (Evicted)       (Retained H2)     (Evicted)      (Local W)    |
+-----------------------------------------------------------------------------+

Mathematical Formulation of Cumulative Attention

For any key vector $k_j$ stored at position $j$, its cumulative attention score $\mathcal{S}_j^{(T)}$ at time step $T$ across all attention heads $h \in \{1, \dots, H\}$ is defined as:

$$\mathcal{S}_j^{(T)} = \sum_{t=j+1}^T \sum_{h=1}^H \alpha_{t, j}^{(h)}$$

Tokens with high cumulative scores $\mathcal{S}_j$ are designated as Heavy Hitters ($\text{H}_2$). These tokens correspond to critical anchor points: named entities, structural markers, numerical values, and initial sinks.

Dynamic Eviction Policy

Given a total KV cache budget $B$, H2O allocates the budget among three components:

1. Sinks / Initial Tokens: $B_{\text{sink}}$
2. Dynamic Heavy Hitters: $B_{\text{heavy}}$
3. Local Sliding Window: $B_{\text{local}}$

where $B = B_{\text{sink}} + B_{\text{heavy}} + B_{\text{local}}$.

At each decode step $T+1$:

1. Compute attention weights $\alpha_{T+1, j}$ for all currently cached positions $j \in \mathcal{C}_T$.
2. Update cumulative scores:

$$\mathcal{S}_j^{(T+1)} = \mathcal{S}_j^{(T)} + \sum_{h=1}^H \alpha_{T+1, j}^{(h)}$$

1. Append the newest token $T+1$ to the local window buffer.
2. If $|\mathcal{C}_{T+1}| > B$, evict the token $j^*$ from outside the local window and sink buffers that minimizes cumulative attention:

$$j^* = \arg\min_{j \in \mathcal{C}_{T+1} \setminus (S_{\text{sink}} \cup S_{\text{local}})} \mathcal{S}_j^{(T+1)}$$

Theoretical Error Bounds

Zhang et al. proved that under bounded attention variance, greedy eviction based on cumulative attention scores $\mathcal{S}_j$ approximates the combinatorial optimal subset of KV vectors with bounded matrix approximation error:

$$\|A - \tilde{A}_{\text{H2O}}\|_F \le \frac{1}{\sqrt{B_{\text{heavy}}}} \sum_{j \notin \text{H}_2} \mathcal{S}_j$$

Empirical results demonstrate that H2O can evict up to 80% of the KV cache (retaining only 20% of tokens) with negligible degradation across reasoning and generation benchmarks.

6. Advanced Selective Eviction: SnapKV and Scissorhands

Recent research has refined selective KV cache eviction by optimizing prompt-phase pre-filtering and head-specific sparsity.

SnapKV: Prompt Observation Windows

SnapKV (Li et al., 2024) addresses the compute overhead of continuously updating cumulative attention scores during generation.

SnapKV posits that the importance of prompt KV states is established during the prefill phase. By analyzing an observation window $L_{\text{obs}}$ (the final 16 to 32 tokens of the prompt), SnapKV identifies spatial attention clusters:

Prefill Prompt: [Tokens 1 .............................. T - L_obs] [Observation Window L_obs]
                                                                            |
                                                    Compute Attention Clustered Pooling
                                                                            v
Selected Prompt KV: [Sinks] + [Top Clustered Feature Vectors] ---------> Frozen Cache

1. Compute attention maps for tokens in the observation window against all prior prompt positions:

$$\mathbf{M}_{i, j} = \alpha_{T - L_{\text{obs}} + i, \, j} \quad \text{for } i \in [1, L_{\text{obs}}], \, j \in [1, T - L_{\text{obs}}]$$

1. Apply 1D max-pooling with kernel size $k$ across the positional dimension to preserve contextual clusters:

$$\mathbf{P}_j = \max_{m \in [0, k-1]} \sum_{i=1}^{L_{\text{obs}}} \mathbf{M}_{i, \, j+m}$$

1. Retain top-$K$ indices based on $\mathbf{P}_j$ and freeze the compressed prompt KV cache for all subsequent decoding steps.

Scissorhands: The Persistence of Importance

Scissorhands (Liu et al., 2023) formalized the Persistence of Importance Hypothesis: if a token does not receive substantial attention within a critical window $\delta$ after its generation, it is statistically improbable to ever receive high attention in subsequent steps. This enables early one-way pruning without maintaining global accumulators.

7. Architectural Comparison of KV Eviction Methods

+----------------------------------------------------------------------------------------------------+
|                         KV CACHE EVICTION AND STREAMING METHODS                                    |
+-------------------+----------------+--------------------+---------------------+--------------------+
| Method            | Cache Budget   | Eviction Criterion | Update Overhead     | Long-Context Scope |
+-------------------+----------------+--------------------+---------------------+--------------------+
| Dense Full Cache  | O(T) (Linear)  | None (Retain all)  | None                | Exact Recall       |
| Naive Window      | O(W) (Fixed)   | Oldest First       | None                | Fails (PPL Explodes|
| StreamingLLM      | O(K + W)       | Static (Keep Sink) | O(1) pointer shifts | Infinite Streaming |
| H2O               | O(K + H + W)   | Lowest Cumulative  | O(B) score sum/step | Summarization/Gen  |
| Scissorhands      | O(B)           | Persistence Window | O(B) tracking       | Reasoning/QA       |
| SnapKV            | O(K + C + W)   | Prefill Obs Window | Zero decode overhead| Long Document QA   |
+-------------------+----------------+--------------------+---------------------+--------------------+

8. Systems Engineering and Serving Infrastructure

Integrating KV cache eviction into high-throughput inference engines (e.g., vLLM, SGLang, and TensorRT-LLM) requires specialized memory management.

+-----------------------------------------------------------------------------+
|               PAGEDATTENTION WITH LOGICAL EVICTION BLOCKS                   |
+-----------------------------------------------------------------------------+
| Logical Sequence:   [Block 0 (Sink)] -> [Block 12 (H2)] -> [Block 45 (Local)]|
|                            |                    |                   |       |
| Physical HBM Pages: [Page Frame 0x1A]   [Page Frame 0x8F]   [Page Frame 0x3C]|
| Free Page Pool:     [Page Frame 0x2B] <- (Returned upon block eviction)     |
+-----------------------------------------------------------------------------+

Integration with PagedAttention

In modern serving engines using PagedAttention (Kwon et al., 2023), physical KV memory is allocated in non-contiguous fixed-size blocks (typically 16 or 32 tokens per page).

Token-level eviction policies (like exact H2O) introduce intra-block fragmentation. Serving engines implement two architectural adaptations:

1. Block-Level Eviction: Eviction scores are aggregated across all tokens in a physical page:

$$\mathcal{S}_{\text{block}} = \sum_{j \in \text{Block}} \mathcal{S}_j$$ When memory limits are reached, entire physical blocks are returned to the free-page pool without memory copy overhead.

1. Dynamic In-Place Compaction: Retained heavy-hitter tokens are compacted into dedicated persistent pages during scheduled memory compaction cycles.

Trade-offs: Streaming vs Long-Context Retrieval

KV cache eviction is not a universal replacement for dense long-context attention:

1. Streaming Generation vs Needle Retrieval:

• For multi-turn conversational agents, autonomous agent loops, and streaming summarization, eviction techniques (StreamingLLM, H2O) provide up to $4\times\text{--}10\times$ throughput improvements with zero quality degradation.
• For specific single-token retrieval tasks across large contexts (e.g., Needle-In-A-Haystack benchmarks), non-retained intermediate tokens cannot be recalled unless backed by an external retrieval (RAG) system or hierarchical index.

1. Hardware Bandwidth vs Compute Limits:

• By capping KV memory at a fixed size $B \ll T$, memory bandwidth utilization drops from $\mathcal{O}(T)$ to $\mathcal{O}(B)$ per token.
• Decoding throughput scales proportionally, enabling larger batch sizes ($B_{\text{batch}}$) and lower inter-token latency (ITL).

Sources

• Efficient Streaming Language Models with Attention Sinks (Xiao et al., 2023)
• H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models (Zhang et al., 2023)
• Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time (Liu et al., 2023)
• SnapKV: LLM Knows What You Are Looking for Before Generation (Li et al., 2024)
• LM-Infinite: Zero-Shot Extreme Length Generalization for Large Language Models (Han et al., 2023)
• PagedAttention: Efficient Memory Management for Large Language Model Serving with vLLM (Kwon et al., 2023)