Why is LRU the default so often?

LRU needs little metadata and no long-term belief about popularity. A timestamp or linked-list position per KV block is enough, and many production workloads reuse prompts soon after first use. That makes it a strong baseline. It is still fragile when traffic contains scans of unique prompts or abrupt shifts in tenant behaviour.

Is LFU better than LRU for KV cache eviction?

It depends on whether popularity is stable. LFU can protect a repeatedly used prefix from being displaced by one-off prompts, which helps under skewed, steady traffic. But raw LFU remembers old popularity too strongly. Without ageing, a once-hot prefix can occupy GPU memory long after it stops being useful.

What makes KV-cache eviction different from ordinary cache eviction?

The cached item is tensor memory tied to model execution, not just an application object. Its value depends on prefix length, recomputation cost, active sequence references, batching pressure, and GPU memory bandwidth. Evicting the wrong block can trigger prefill work that competes with latency-sensitive decode, so the policy is part of serving scheduling.

Eviction

Eviction is the rule an inference server uses to choose which KV-cache blocks to remove when GPU memory reserved for cached tokens is full. It ranks cached pages by signals such as recency, hit count, prefix position, tenant priority, or recomputation cost, then frees the least valuable blocks so new requests can proceed.

Eviction is necessary because KV cache is valuable but finite. Reused prefixes, system prompts, RAG templates, and agent scaffolds can save expensive prefill work, yet every retained token consumes HBM that could hold active sequences or larger batches. Once cached KV becomes shared across requests, the server must decide what to keep without knowing the future. The ideal policy would keep the blocks with the highest future reuse value per byte, but production systems only see past accesses.

In practice, the cached object is usually a page or block of key and value tensors, not a whole prompt string. Page-based systems keep metadata beside each block, such as last access time, hit count, hash, reference count, and sometimes tree position. LRU evicts the block least recently used. LFU evicts the block with the fewest hits, often with ageing. Hybrid policies combine recency, frequency, size, prefix depth, and estimated recomputation cost into a score.

LRU is common because it is simple, cheap, and often matches real traffic, where reuse is clustered in time. Its weakness is scan pollution: a wave of unique large prompts can push out useful prefixes. LFU protects stable hot prefixes, but can become sticky when yesterday’s popular prompt stops mattering. Hybrids are more expressive, but require tuning and extra metadata. The honest answer is workload-dependent, and KV eviction remains active systems research rather than settled practice.

Engineers meet eviction in prefix caching, paged KV allocators, radix-tree prefix stores, and inference schedulers in systems such as vLLM, SGLang, TensorRT-LLM, NVIDIA Dynamo, and llm-d. It shows up as latency spikes after cache misses, low hit rates despite high memory use, page-pool churn, or unfairness between tenants. It also interacts with batching, privacy boundaries, speculative decoding, disaggregated prefill and decode, and the exact GPU memory budget.

Go deeper

Inference EngineeringEvictionCompare KV cache eviction policies: LRU, LFU, and hybrid strategies. Explain why LRU is the dominant default and also fragile under changing traffic. Recognise that this is live research, not settled practice.Open the lesson

Common questions

Why is LRU the default so often?: LRU needs little metadata and no long-term belief about popularity. A timestamp or linked-list position per KV block is enough, and many production workloads reuse prompts soon after first use. That makes it a strong baseline. It is still fragile when traffic contains scans of unique prompts or abrupt shifts in tenant behaviour.
Is LFU better than LRU for KV cache eviction?: It depends on whether popularity is stable. LFU can protect a repeatedly used prefix from being displaced by one-off prompts, which helps under skewed, steady traffic. But raw LFU remembers old popularity too strongly. Without ageing, a once-hot prefix can occupy GPU memory long after it stops being useful.
What makes KV-cache eviction different from ordinary cache eviction?: The cached item is tensor memory tied to model execution, not just an application object. Its value depends on prefix length, recomputation cost, active sequence references, batching pressure, and GPU memory bandwidth. Evicting the wrong block can trigger prefill work that competes with latency-sensitive decode, so the policy is part of serving scheduling.

Every term