What is prefix-cache eviction, and how does cache memory pressure affect LLM inference performance?

Prefix-cache eviction removes previously stored, reusable KV-cache blocks when an LLM serving engine needs their memory for new or active requests. Prefix caching speeds up repeated prompt prefill, but GPU KV memory is finite: the scheduler must balance retaining reusable prefixes against serving current generations.

1. How does eviction work?

• A completed request can leave behind cached KV blocks available for reuse. They may have zero active references while still containing reusable data.
• In vLLM's block-cache design, when another request needs capacity, a reusable block with reference count zero can be reclaimed. Cached blocks are selected from an LRU-style free queue rather than arbitrarily deleting KV state currently required by an executing request.
• A block still needed by active requests cannot simply be discarded as an ordinary idle cache entry.
• Removing a cached block's hash association means a future request can no longer reuse that block; if it needs those tokens, the server must recompute their attention states.
• Some older descriptions additionally explain preferring deeper prefix blocks on recency ties. Follow the running engine version's documented policy rather than assuming every implementation is identical.

2. Beginner-friendly numerical example

Imagine a simplified pool of 12 equal-sized KV blocks:

• Active requests hold 7 blocks.
• Completed requests left 5 reusable prefix blocks; none are currently referenced by an active request.
• A newly admitted request needs 3 new blocks. If no genuinely unused blocks remain, the engine can evict 3 idle cached blocks to make room while keeping the 7 active blocks and 2 surviving reusable blocks.
• Suppose the evicted blocks represented 48 common prompt tokens (16 tokens/block). A later request may need to recompute those 48 tokens, rather than getting an immediate cache hit.

The numbers are illustrative. Real KV managers may handle allocation, partial blocks and overlapping prefix matches differently.

3. How does this affect latency and throughput?

1. More cache hits: repeated long prompts skip eligible prefill computations, often lowering time to first token (TTFT).
2. More eviction: cache-hit probability falls; previously cached prefix tokens are prefetched and computed again, increasing GPU work and potentially TTFT.
3. High active KV occupancy: many concurrent requests or long contexts can leave too few blocks to admit more requests. Queueing and tail latency rise even if unused accelerator arithmetic capacity remains.
4. Insufficient active capacity: when the serving engine cannot allocate KV blocks required by running sequences, it may use request preemption and recomputation. This is distinct from evicting unreferenced prefix-cache entries.
5. Excessive retention: using memory to keep cache entries can be counterproductive if it displaces capacity needed by active requests; a correct allocator can reclaim eligible idle cache blocks on demand.

4. Prefix-cache eviction versus request preemption

• Idle prefix-cache eviction: drop a reusable block that no running request needs; future matching prompts become misses. Current execution correctness is preserved.
• Request preemption: pause or reschedule an active request because the KV budget cannot support it. Depending on the engine, some state may need to be recomputed when resumed. This directly hurts request latency.

Do not equate cache eviction counts with active-request failures or OOM events. Eviction of idle data can be routine, healthy operation.

5. What should production engineers monitor?

• Prefix-cache queries and hits, and changes in hit rate across repeated prompt workloads.
• KV-cache usage, active and waiting request counts, and cache-block residence/idle-to-eviction times.
• p50/p95/p99 TTFT, prefill throughput, time between output tokens and overall SLO-compliant goodput.
• Long-context traffic, prompt-sharing distributions, preemptions and available headroom.

For example, vLLM exposes counters such as vllm:prefix_cache_queries and vllm:prefix_cache_hits, a usage gauge vllm:kv_cache_usage_perc, and sampled eviction/residence metrics in supported versions.

6. Practical optimization checklist

1. Measure first: distinguish expected cache misses (unique prompts) from lost reuse caused by evictions.
2. Make shared prompts prefix-identical whenever appropriate; place stable system instructions and shared context before variable user content.
3. Avoid excessive concurrency or unbounded long contexts when active KV cache pressure causes queueing and preemption.
4. Tune KV memory allocation and scheduler limits under realistic load; reduce competing memory use or scale replicas when justified.
5. Assess locality and tenant boundaries: route recurring prefixes to compatible cache pools only where security and workload isolation permit.
6. Benchmark tradeoffs: compare cache-hit rate, memory occupancy, p95 TTFT and completed requests per second, not hit rate alone.

Interview-ready answer

“Prefix-cache eviction reclaims KV blocks from completed requests when memory is needed. An LRU-like policy can evict zero-reference cached blocks without interrupting active requests, but future matching prefixes must be recomputed. At high KV pressure, admission delays or active-request preemption may also hurt latency. I'd monitor hits, block residency, KV usage, waiting requests and p95 TTFT, then tune cache capacity and concurrency around real workload reuse.”

Sources: vLLM Prefix Caching Design; vLLM Metrics Reference.