Name two production KV-cache eviction policies and what each prioritizes

Short answer·Medium·4.0 · 0·~3 min·Asked atNotion Swiggy·Relevant atAi4bharat Anthropic Cerebras NVIDIA

Attempt it

When generation pushes the KV cache past its memory budget at long context, the server must evict cache entries to keep going. Name two production grade eviction policies, describe what each keeps and what each drops, and note the bookkeeping cost of each.

Free · 2 AI evals / day

When a long generation pushes the KV cache past available memory, the server must drop some cached K, V entries to keep generating. Two production policies dominate: **1. Sliding-window eviction**, keep the most recent W tokens; drop anything older. Bookkeeping is essentially free (a circular buffer or moving pointer). The cost: anything older than W is gone, so long-range references die. This is implicit in models trained with sliding-window attention like Mistral 7B and is the simplest fallback for stretched context. **2. Heavy-hitter eviction (H2O)**, score each cached token by how much attention weight it has received historically. Keep the top-k highest-scored tokens plus a recent local window; drop the rest. Bookkeeping requires per-token running scores updated each step. The win: better quality preservation at the same cache budget because semantically important tokens (entities, topic anchors) survive. Production often blends these. **StreamingLLM** keeps a few 'attention sink' tokens at the very start of the sequence (because of attention-sink phenomena where the first few positions absorb disproportionate weight, dropping them collapses the softmax) plus a recent window. The trade-off is quality vs bookkeeping cost: sliding-window is cheap, heavy-hitter is smarter, hybrids try to get both.

Two policies cover most production deployments. **Sliding-window eviction.** Keep only the last W tokens of K, V; drop the oldest as new tokens are added. Implementation is a circular buffer or a moving start-pointer, essentiallyzero bookkeeping cost. The quality cost is that anything beyond W is unreachable for the rest of the generation. Used implicitly by Mistral 7B's sliding-window attention and as the default fallback in vLLM and SGLang for context-bounded serving. **Heavy-hitter eviction (H2O style).** Track per-token attention weight accumulated over recent decode steps. At eviction time, keep the top-k highest-scored tokens plus a small local window of the most recent tokens; drop the rest. Bookkeeping is a per-token running score updated every step. The quality win is substantial: semantically important tokens (entities, topic anchors, structural markers) survive eviction even when they are far back in the sequence, while uninformative filler is dropped. **Hybrids in production.** **StreamingLLM** is the canonical example: keep the first few 'attention sink' tokens permanently (they absorb disproportionate softmax mass and dropping them destabilizes the distribution) plus a recent window. **Adaptive KV eviction** in some 2025-2026 serving stacks combines heavy-hitter scoring with chunked drops to reduce per-step overhead. The practical choice is a quality vs bookkeeping trade. Use sliding-window when you need cheap and predictable; use heavy-hitter when long-range references matter and quality at extreme context is the binding constraint.

TL;DR

Two production policies: sliding-window (keep last W, free bookkeeping) and heavy-hitter (keep tokens with highest accumulated attention weight, per-token score tracking).

Memory aid

Easy to grasp

Picture a chef's prep station that can only hold 20 ingredients at a time. As new ingredients come in, old ones have to go. The simple rule is 'whatever has been sitting longest, throw it out',that is sliding-window. The smarter rule is 'whatever the recipes keep reaching for, keep it; whatever has been ignored, throw it out',that is heavy-hitter. The smarter rule needs the chef to keep a tally of how often each ingredient gets used, but it preserves the important stuff better. Production kitchens often blend the two: always keep a few staples like salt at the start, and otherwise rotate the recent and the popular.

Key concepts

KV cache Sliding window attention H2O eviction Attention sink StreamingLLM

Concept explanation~2 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

KV cache eviction is one of the most important and least-discussed long-context serving topics. The KV cache grows linearly with sequence length, and at 1M-token contexts a single request can blow through the entire GPU memory budget for the model. Eviction policies decide which past tokens' K, V to keep and which to drop, and the choice has direct quality and throughput implications. Sliding-window is the cheapest and most-deployed; H2O-style heavy-hitter is the smartest and most quality-preserving; StreamingLLM is the production-favored hybrid.

This deep dive walks each policy in detail, explains the attention-sink phenomenon that makes the first few tokens un-evictable, surveys the orthogonal optimization of KV quantization, and closes with a decision guide for picking the right policy in 2026.

Why eviction is necessary

The KV cache stores key and value tensors for every past token at every transformer layer. For a typical decoder-only model with L layers, H heads, d_head per head, sequence length T, and batch size B at FP16:

\text{bytes} = 2 \cdot L \cdot H \cdot d_h \cdot T \cdot B \cdot 2

The first factor of 2 is for K and V; the second is for FP16.

Concrete numbers

For a Llama 3 8B class model (32 layers, 32 query heads with GQA reducing to 8 KV heads, d_head = 128) at T = 100,000 tokens and B = 1:

code

bytes = 2 * 32 * 8 * 128 * 100_000 * 1 * 2 = 13.1 GB

For a single 1M-token request: 131 GB. That exceeds the memory of any single GPU. With batch size > 1, the situation compounds linearly in batch.

The eviction question

Eviction is the question: at the moment the KV cache cannot grow further, which entries do we drop? The answer determines both how much memory we save and how much quality we keep.

What eviction is not

Not KV quantization: that reduces per-token bytes; eviction reduces token count.
Not architectural KV compression like MLA: that changes the model's KV structure; eviction operates at serving time on an unchanged model.
Not sliding-window attention: that is an architectural training-time choice; sliding-window eviction is a serving-time analog.

Eviction is a serving-time policy on top of a model whose architecture is fixed. The model does not know its KV is being trimmed.

Sliding-window eviction in detail

Heavy-hitter eviction (H2O) in detail

Attention sinks and the StreamingLLM hybrid

Decision guide and the orthogonal optimizations

Situations where this technique stops working.

2–4 min · Everything important, quickly.

Real products, models, and research that use this idea.

Mistral 7B: sliding-window attention with W = 4096 is the architectural form of sliding-window eviction.
H2O (NeurIPS 2023): the canonical heavy-hitter eviction paper; showed near-lossless quality at 20% cache size on long-context QA benchmarks.

What an interviewer would ask next. Try answering before peeking at the approach.

QWhy does dropping the first few tokens collapse the attention distribution in long generations?

The attention-sink phenomenon: softmax always sums to 1, so some 'pressure release' position must absorb excess weight when no other position is a great match. The first tokens become this sink because they are visible from every later position and tend to absorb 10-30% of total attention mass regardless of content. Dropping them forces that mass to redistribute onto semantically wrong tokens and the distribution becomes noisy.

2 more follow-ups an interviewer would ask next. Sign in to reveal them.

Red flags & common mistakes

The phrases that signal junior thinking. Click to expand.

Most common mistake

Treating KV cache eviction as a pure capacity problem with one right answer. Quality varies by eviction policy because not all cached tokens are equally useful for future generation.

60 second bullets to scan on the way to the call.

Describe how sliding-window eviction decides which KV entries to drop
Describe the heavy-hitter / H2O scoring rule and what it retains

Primary sources. Browse if you want the original framing.