KV Cache Eviction Trade-offs: Why Higher Hit Rates Spike Tail Latency

When GPU HBM fills up, there are only two options: reject incoming requests or evict existing cached KV blocks. The former is an availability problem; the latter is a recomputation cost problem. Eviction is the policy that decides what to discard in this situation, and many teams default to LRU without much thought.

There are cases where LRU hits its limits in LLM serving. In prefix-sharing environments, "least recently used" frequently diverges from "least costly to discard." And the paradox emerges: the harder you try to boost hit rates by holding off on eviction, the more p99 TTFT spikes in the opposite direction.

When Eviction Kicks In

The memory footprint of a KV cache is larger than it looks when you work through the numbers. In FP16, the KV cache size per token is:

2 × num_layers × num_kv_heads × head_dim × 2 bytes

For LLaMA-3 70B (80 layers, 8 GQA KV heads, head_dim 128), that's roughly 0.32 MB per token. A single 64K-context request occupies about 20 GB of cache. On an A100 80GB, model weights already consume 35–40 GB, so just two 64K requests push KV cache space to its limit. In practice, eviction starts much earlier than that — dozens of shorter-context requests running concurrently drain the HBM headroom fast.

In vLLM, when vllm:gpu_cache_usage_perc stays above 90% while vllm:num_requests_waiting remains nonzero, that's a signal that eviction is directly contributing to latency.

Recomputation Cost Compounds Quadratically

Evicted KV blocks must be recomputed the next time a request needs that prefix. If this cost were linear, eviction policy wouldn't matter as much as it does. The problem is that prefill is superlinear.

Transformer prefill FLOPs break down into two main parts. The linear projection portion (Q, K, V, and output projections) scales with sequence length L, but the attention computation per layer is:

(1/2) × 4 × L² × (num_heads × head_dim)

If context length grows 4× from 4K to 16K, the attention cost alone increases 16×. From 4K to 64K, it's 256×. Total prefill cost lands somewhere in between, but the quadratic term dominates as context grows longer. This scaling doesn't change with FlashAttention — FlashAttention optimizes memory access patterns, but the FLOPs complexity remains O(L²).

In a 64K-context serving system, a poorly designed eviction policy means a single cache miss can translate into a several-second TTFT penalty. You build up cache to improve p50 TTFT, but when a cache miss hits, that request's TTFT can spike by an order of magnitude or more.

Policy Comparison: LRU, Prefix-Aware LRU, and Radix Tree

Basic LRU

Evicts the block least recently accessed. Simple to implement and works well for general cache workloads. The problem in LLM serving is prefix sharing. If a system prompt prefix shared across many requests gets evicted simply because it hasn't been accessed recently, every subsequent request must recompute that prefix. The most reused blocks disappear first — the exact opposite of what you want.

vLLM Prefix-Aware LRU

vLLM reverses the order in which blocks are added to the eviction queue when a request completes. Blocks for a finished request are enqueued in reverse order — suffix first. This encodes the observation that later blocks in a sequence are less likely to be reused. When multiple blocks share the same last-access timestamp, the one belonging to the longest prefix chain — the deepest leaf node in the tree — is evicted first.

The vLLM documentation explicitly states that this behavior produces the same outcome as SGLang's RadixAttention policy for full-attention models.

SGLang Radix Tree Eviction (Leaf-LRU)

Zheng et al. (arXiv:2312.07104)'s RadixAttention manages the KV cache as a radix tree. The tree structure lives on the CPU while actual KV tensors are stored in a GPU paged layout; on eviction, the LRU leaf node is discarded first.

A leaf node is one with no children — a node that no other request shares as a prefix. A system prompt prefix shared by ten requests becomes a deep internal node in the tree, while the tail (suffix) of a single session remains a leaf. Under memory pressure, leaves are always evicted first. Whether a block is shared is automatically factored into the eviction decision — not just when it was last accessed.

A simplified version of the logic:

def evict(tree, required_blocks):
    freed = 0
    while freed < required_blocks:
        # 현재 사용 중이지 않은(ref_count == 0) 리프 노드 중 가장 오래된 것
        candidates = [n for n in tree.leaf_nodes() if n.ref_count == 0]
        if not candidates:
            break
        node = min(candidates, key=lambda n: n.last_access_time)
        tree.remove(node)
        free_blocks(node.kv_blocks)
        freed += node.num_blocks

In LMSYS blog benchmarks, RadixAttention achieved up to 5× higher throughput compared to the same setup without it.

LFU and Cost-Aware Policies

LFU (Least Frequently Used) evicts blocks with the lowest access frequency. Newly arriving prefixes naturally have low frequency counts, putting them at a disadvantage early on. The vLLM community proposed a freq × compute_cost retention scoring approach via RFC #23641, but it was closed due to unclear gains relative to implementation complexity.

Why Higher Hit Rates Lead to Longer Tail Latency

Holding off on eviction raises hit rates and reduces p50 TTFT. But p99 TTFT can move in the opposite direction.

Here's the mechanism. Retaining more stale blocks in the cache shrinks the free block pool. When a burst of requests arrives in this state, the scheduler can't allocate KV blocks for new requests, forcing it to either preempt existing requests or queue the new ones. At that moment, some requests see their TTFT spike sharply. The result is a classic distribution: low p50, high p99.

The numbers reported in the T-LRU RFC illustrate this relationship concretely. T-LRU reduced P95 TTFT by up to 27.4% compared to baseline LRU, closing 25–79% of the performance gap relative to the clairvoyant offline optimum. T-LRU uses a dual-queue design: blocks that won't cause a TTFT SLO violation (TEL-safe) are evicted first; blocks that would (TEL-unsafe) are preserved. Rather than maximizing hit rate, it constrains tail latency by adjusting eviction aggressiveness accordingly.

Tuning this tradeoff without a defined SLO is essentially impossible. You need a target like "p99 TTFT < 2 seconds" before you can decide how aggressively to evict. In practice, it's common to optimize for hit rate alone and only discover the p99 problem after the fact.

Choosing a Policy Based on Request Patterns

The higher the proportion of shared prefixes, the more effective Radix Tree-based eviction becomes. In PGDSF research, prefix-aware policies achieved 1.06–1.62× higher hit rates than basic LRU under identical traffic. Conversely, for workloads like open-ended Q&A with no prefix sharing, the choice of eviction policy barely affects hit rate at all.

Applying hit rate measurements or policy tuning from one workload directly to another can actually hurt performance. An aggressive eviction configuration tuned for 80% RAG traffic, when deployed in an environment with a mix of open-ended requests, ends up conserving evictions unnecessarily — shrinking the free block pool without any shared prefix to protect.

Diagnosing Eviction in Production

Prometheus metrics exposed by vLLM that are directly useful for eviction diagnosis:

# KV cache utilization. Above 90% indicates eviction pressure.
vllm:gpu_cache_usage_perc

# Cumulative preemption count. Use rate() to monitor eviction frequency in real time.
vllm:num_preemptions_total

# GPU / CPU prefix cache hit rates
vllm:gpu_prefix_cache_hit_rate
vllm:cpu_prefix_cache_hit_rate

The point where gpu_cache_usage_perc exceeds 90% while the num_preemptions_total rate also climbs is the window where eviction is directly driving latency. Without watching both metrics together, it's hard to diagnose why p99 is bad despite a high hit rate.

If hit rate is high but preemption rate is also rising, you either need to increase eviction aggressiveness to free up the block pool, or redefine eviction priority around your SLO targets. Doing neither means leaving hit rate and tail latency on a collision course indefinitely.