What is being evicted from a KV cache?

Usually not a complete prompt string. Serving systems commonly manage KV memory as pages or blocks of key and value tensors. When the memory budget is exceeded, the eviction policy chooses which inactive cached blocks to discard, while preserving blocks still referenced by active sequences.

Why is LRU the usual default for KV cache eviction?

LRU matches a common production pattern: if a prefix is reused, it is often reused soon. It is also simple to maintain in page-based KV allocators because each block only needs a last-access signal or list position. That makes it attractive before workload-specific popularity statistics are trustworthy.

Why is KV cache eviction still an active research problem?

The value of keeping a KV block depends on reuse probability, recomputation cost, prefix sharing, batching, active decode pressure, tenant policy, and hardware memory behaviour. A policy that works for one traffic mix can fail after a product launch, scan workload, privacy constraint, or serving-stack change.

The KV Cache

03.11 · Concept

Eviction

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

No video curated for this lesson yet

This lesson is written, ordered and part of the path - the video slot is the only thing still open. We are working through Inference Engineering lesson by lesson; 93 of 94 have their video so far.

The written notes below cover this idea in full - you lose nothing by reading instead of watching.

KV cache eviction decides which resident KV tensor blocks are discarded when memory is full. LRU is common because reuse is often clustered and metadata is cheap, but it fails under scans and traffic shifts. LFU and hybrids can protect stable hot prefixes, yet add stickiness, tuning, and operational complexity.

What this lesson answers

why is LRU common for KV cache eviction
when does LFU beat LRU for prefix caching
how do hybrid KV eviction policies rank blocks

Notes

KV cache eviction is the admission/removal rule used when the serving system’s token-resident KV blocks exceed the memory budget: for cached object $i$ with size $s_{i}$ bytes and future reuse value $v_{i}$ , the offline optimum would evict the set minimizing lost value under $\sum_{i} s_{i} \leq C$ , but production systems use online approximations because future requests are unknown.

References

Common questions

What is being evicted from a KV cache?: Usually not a complete prompt string. Serving systems commonly manage KV memory as pages or blocks of key and value tensors. When the memory budget is exceeded, the eviction policy chooses which inactive cached blocks to discard, while preserving blocks still referenced by active sequences.
Why is LRU the usual default for KV cache eviction?: LRU matches a common production pattern: if a prefix is reused, it is often reused soon. It is also simple to maintain in page-based KV allocators because each block only needs a last-access signal or list position. That makes it attractive before workload-specific popularity statistics are trustworthy.
Why is KV cache eviction still an active research problem?: The value of keeping a KV block depends on reuse probability, recomputation cost, prefix sharing, batching, active decode pressure, tenant policy, and hardware memory behaviour. A policy that works for one traffic mix can fail after a product launch, scan workload, privacy constraint, or serving-stack change.

Short definition: what is Eviction?

03.10 · The KV CacheHit Rate 04.01 · The BatchOne Request at a Time