The cost of a KV cache miss is not the cost of a cache lookup failure. It is the cost of a full prefill recompute for the evicted token sequence. On Llama-3 8B with a 4K-token context, that is roughly 400-500 ms of prefill latency on an A100 node, depending on current batch occupancy. That cost applies every time you evict a block that a live request later needs. Eviction policy selection is therefore not a minor optimization. It directly determines what fraction of your prefill compute budget gets burned on redundant work.
We have been running side-by-side evaluations of three eviction policies inside Inferact's scheduler: LRU (least recently used), prefix-aware (which weights shared prompt prefixes to avoid eviction), and an adaptive policy that we built and have been tuning over the last several months. This post shares what we found, including the part where the adaptive policy behaved worse than LRU under a specific concurrency condition we had not anticipated.
How KV Cache Pages Work in PagedAttention
Quick context for readers who have not worked directly with vLLM-style PagedAttention implementations: the KV cache is divided into fixed-size blocks (pages), each holding the key and value tensors for a fixed number of tokens. vLLM defaults to a block size of 16 tokens. Each sequence's KV state is stored in a sequence of these pages, which can be non-contiguous in physical GPU memory. When the cache fills, the scheduler must decide which blocks to evict to make room for new sequences.
The critical property that makes this interesting is prefix sharing. If 50 concurrent requests all start with the same 2K-token system prompt, the KV cache can store one copy of those 2K tokens' K/V tensors and share it across all 50 sequences. Evicting that shared prefix block invalidates the cached state for all 50 sequences simultaneously. An eviction policy that does not account for reference counts on shared blocks will make eviction decisions that look cheap in isolation but are catastrophically expensive when you count downstream prefill recompute.
LRU Baseline
LRU is the default in many inference frameworks and serves as our baseline. The policy is simple: when the cache is full, evict the block whose most recent access timestamp is oldest. It does not consider whether a block is shared across multiple sequences or whether the block holds tokens that are computationally expensive to recompute (long context vs short context).
In our internal benchmarks on a workload with a high system-prompt sharing rate (approximately 65 percent of requests sharing a common 1800-token system prompt), LRU performed poorly for a predictable reason: once the cache pressure is sufficient to start evicting blocks, LRU frequently evicts the shared prefix block because the last access to that specific block was many steps ago even though it remains in active use by many in-flight sequences. The result is a cascading prefill storm. We measured LRU producing 3-6x higher prefill compute per unit time compared to prefix-aware under this workload pattern in our testing.
LRU performs acceptably when the workload has low system-prompt sharing rates and short context lengths. If most of your requests are independent, short, and do not share prefixes, LRU is fine and simpler to implement than the alternatives.
Prefix-Aware Eviction
Prefix-aware eviction weights blocks by their reference count and by their position in the prefix tree. The basic rule: never evict a block with a reference count above 1 unless no single-reference blocks exist. Among single-reference blocks, prefer evicting blocks at the leaves of the prefix tree (the most recently generated tokens of sequences that are close to completion) over blocks at the roots (shared prefixes).
This policy significantly reduces the cost of eviction in high-sharing-rate workloads. In our tests, at 65 percent system-prompt sharing on 1800-token prompts, prefix-aware reduced prefill recompute cost by roughly 73 percent compared to LRU at the same cache utilization level. The tail TTFT improvement was even larger because the cascade effect of LRU disappears when the shared prefix block is protected.
Prefix-aware has one weakness: it requires maintaining a reference count per block and a prefix tree data structure that maps token hash sequences to block IDs. The overhead is low, but it is non-zero, and the data structure must be consistent across concurrent eviction and allocation operations. We found a subtle race condition in our initial prefix-aware implementation where two concurrent allocation requests could both see a block as evictable during the window between the reference count decrement and the actual eviction operation. Fixing this required a short critical section around the eviction decision, which adds a small but measurable scheduling latency under extremely high concurrency (above 300 concurrent sequences on our test hardware).
The Adaptive Policy
The adaptive policy we built attempts to estimate the future access probability of each block based on observed request patterns and adjust eviction priority accordingly. The intuition: a block that holds tokens from a system prompt used by 80 percent of recent requests has a much higher future access probability than a block holding the middle of a unique long document. Evicting the high-probability block is more expensive in expectation than evicting the low-probability one, even if the reference count is currently identical.
We maintain a rolling histogram of token prefix hashes observed over the last 5 minutes, weighted by request count. Blocks whose prefix hash falls in the top decile of the frequency distribution get a survival bonus that effectively raises their eviction threshold. Blocks in the bottom quintile are treated as evictable even if recently accessed.
In moderate-concurrency testing (up to 150 concurrent sequences), adaptive outperformed both LRU and prefix-aware on throughput-focused metrics. Under workloads with a clear hot prefix (the 65 percent sharing scenario), adaptive preserved the prefix more aggressively than prefix-aware because it could also anticipate future requests, not just protect currently referenced blocks.
Where Adaptive Broke Down
The unexpected failure appeared at high concurrency, specifically above 250 concurrent sequences with a burst arrival pattern. The frequency histogram that drives the survival bonus is computed over a 5-minute window. During a sudden traffic spike where the incoming request distribution shifted (a new batch of requests arrived with a different system prompt), the histogram was stale. The adaptive policy continued protecting the old hot prefix while the new hot prefix had no protection and immediately began getting evicted as new sequences filled the cache.
The result was worse than LRU under this condition. LRU evicts randomly with respect to prefix semantics, which means it occasionally evicts the old hot prefix and preserves the new one purely by accident. The adaptive policy, by contrast, specifically protected the wrong prefix because its signal was lagged.
We have two partial mitigations in place. First, we reduced the histogram window from 5 minutes to 90 seconds, which reduces the lag at the cost of less statistical stability in the frequency estimates. Second, we added a decay factor that reduces the survival bonus for blocks that have not been accessed in the last 60 seconds regardless of their historical frequency. Neither fix is fully satisfying. The histogram window tuning is a compromise that depends on your traffic pattern, and the access-time decay partially collapses adaptive back toward LRU in steady-state low-traffic periods.
Summary of Results
From our internal benchmarks on the workloads described above, the ordering we observe is:
On high-sharing-rate workloads with stable traffic patterns, adaptive performs best followed closely by prefix-aware. The gap between them is in the range of 8-15 percent on throughput metrics. LRU is substantially worse, by 40-70 percent on prefill recompute cost.
On low-sharing-rate workloads (independent requests, diverse prompts), all three policies perform similarly. Prefix-aware has slight overhead from maintaining the prefix tree; adaptive has slight overhead from the histogram. For purely independent workloads, LRU is the simplest choice with minimal downside.
On bursty workloads with distribution shift, prefix-aware is more reliable than adaptive. The prefix tree is reactive, tracking current reference counts accurately, while the adaptive histogram introduces a lag that can cause active misprioritization during transitions.
What We Would Change
If we were redesigning from scratch, we would not treat the adaptive policy as a drop-in replacement for prefix-aware. Instead, we would use prefix-aware as the base policy and layer the frequency histogram signal on top only for the tie-breaking case where multiple single-reference, leaf-position blocks are candidates for eviction. This avoids the situation where the stale histogram overrides the accurate reference count signal on shared prefix blocks.
We are also looking at online learning approaches for the frequency estimate, specifically a recency-weighted exponential moving average per prefix hash rather than a fixed-window histogram. This would reduce the step-change problem during distribution shifts. That work is not production-ready yet, but the early internal results look more stable than the current histogram approach.