KV Cache Eviction: Keep Reusable Prefixes

KV cache eviction is a policy for protecting reusable computation under memory pressure, not a contest to maximize raw hit rate. This guide compares leaf-LRU and priority-aware LRU on one immutable trace while active references, ancestry, tenant scope, avoided prefill, miss latency, and rollback remain explicit.

KV cache eviction starts with reusable work

KV cache eviction should preserve the blocks that are expensive and likely to be reused, not merely celebrate a high cache-hit percentage. A hit on four tokens and a hit on four thousand tokens count equally in a naive dashboard, although their avoided prefill work and effect on time to first token are radically different. The decision is therefore which inactive prefix blocks to reclaim when memory is full while active requests, tenant boundaries, and latency objectives remain protected.

Start with one immutable request trace. Each event names a tenant, model revision, adapter, tokenized prefix, arrival time, active reference interval, and measured or estimated prefill cost. Replay that exact trace through leaf-LRU and a priority-aware LRU. If the policies see different requests, capacity, or clocks, the comparison says nothing about KV cache eviction.

The vLLM prefix-caching design explains hash-addressed blocks and the conditions required for safe prefix reuse. That mechanism is the foundation, not an eviction recommendation for every workload. A useful result reports avoided prefill tokens, miss latency, occupied blocks, eviction reasons, and fairness by tenant beside hit rate.

This guide builds that receipt. It separates lossless prefix-block reclamation from lossy attention-cache token eviction, protects active references, keeps ancestry valid, scopes identity correctly, and makes the cost of every policy visible before production behavior changes.

Define identity before ranking blocks

A prefix is reusable only when every input that can change its KV values agrees. At minimum, key identity by model and tokenizer revision, adapter or LoRA identity, token IDs, multimodal input fingerprints, and any cache-salt or tenant scope required by the threat model. Do not hash decoded text: distinct tokenization can render the same-looking string into different computation.

Build a radix-style ancestry ledger. A child block is reusable only after its parent chain matches, so eviction candidates are usually inactive leaves. Removing a parent while retaining descendants creates dangling entries that appear resident but can never be reached safely. KV cache eviction must either remove a valid leaf or atomically remove the entire dependent subtree.

Use cryptographic-quality hashes when isolation or adversarial collision risk matters, and store enough metadata to reject cross-model or cross-adapter matches. The cache key is part of the security boundary. A shared tenant pool may improve reuse, but it also changes timing and information-leak risk; make that choice explicit rather than inheriting it from a global map.

The companion guide to prompt-caching metrics explains why saved input work belongs beside nominal hits. For this policy, record matched depth, saved tokens, avoided prefill milliseconds, parent chain, last access, tenant scope, priority, and expiry. These fields let an operator distinguish a cheap accidental hit from a reusable system prompt that genuinely protects latency.

Keep active references outside the candidate set

The first invariant is simple: an active block is not an eviction candidate. Maintain a reference count or ownership set for every resident block and update it at request admission, prefix attachment, completion, cancellation, and failure cleanup. An exception path that forgets to release a reference leaks memory; one that releases early can corrupt a live decode.

Construct candidates only from inactive leaves. When a request finishes, walk its chain and expose newly inactive leaves, but never assume the entire chain is free: another request may share an ancestor. After every mutation, assert that referenced nodes remain resident, each resident child has a resident parent, block usage does not exceed capacity, and accounting equals the actual resident set.

This is lossless KV cache eviction. The system discards recomputable prefix state and pays prefill again on a later miss. It is not an attention-quality technique that removes tokens from a live sequence. Mixing those two meanings produces dangerous claims: a prefix-cache miss changes latency and compute, while lossy attention eviction may change generated output.

Request preemption is related but separate. The preemption, recompute, and swap comparison covers how active work can yield resources under overload. Here active references remain pinned. If capacity cannot admit a request after all safe inactive leaves are reclaimed, admission control or a declared preemption path must decide what happens next.

Compare leaf-LRU with priority-aware LRU

Leaf-LRU evicts the least recently used inactive leaf, then repeats as ancestors become leaves. It is deterministic, cheap to explain, and often a strong baseline. It can still discard a large shared prefix seconds before a burst reuses it, because recency treats every block as equal and has no vocabulary for known business cycles or recomputation cost.

Priority-aware LRU adds a bounded hint. Rank eligible leaves first by whether an unexpired priority protects them, then by declared priority, reuse cost, and recency, with a stable final tie break. Expiry matters: permanent high priority turns a cache into manual pinning and can starve ordinary tenants. A priority hint is not a prediction of future reuse; it is an operator-authored preference that must earn its memory.

The RadixAttention paper describes reuse through a radix tree and cache-aware scheduling in SGLang. That evidence motivates structural prefix accounting, but the local simulator is deliberately smaller. It compares two transparent candidate rankings over a synthetic trace rather than reproducing a production scheduler.

For fair KV cache eviction, feed both policies the same ordered events and capacity. Export every candidate set, selected victim, ranking fields, and resulting resident roots. A surprising choice should be explainable from one row. If it requires reading mutable global state that is absent from the receipt, the policy is too opaque to debug during pressure.

Measure saved prefill and miss latency

Hit rate is a count, not a cost model. Weight each match by tokens or profiled prefill time actually skipped. A long shared prefix can justify several blocks even with modest request frequency; thousands of tiny hits may save less compute. Report both so a workload change cannot hide behind one flattering ratio.

Measure time to first token separately for hits and misses, sliced by prompt length, tenant, model, and concurrency. Cache lookup, hashing, block allocation, and scheduler contention can consume part of the theoretical saving. Use the LLM serving goodput SLO to keep deadline-qualified completions visible: a policy that raises aggregate throughput while one tenant misses its TTFT objective is not automatically successful.

Memory is the counterweight. Record occupied blocks over time, churn, bytes reclaimed, failed admissions, and recomputation caused by prior evictions. Normalize saved work per resident byte and per eviction. Then inspect distributions and worst slices rather than collapsing everything into an unexplained score.

KV cache eviction also needs a counterfactual. The fixed-trace lab calculates the alternate policy from identical events so differences are attributable to ranking, not traffic. In production, shadow replay or sampled trace simulation can provide the same discipline without letting an experimental policy control live memory. Synthetic results are a hypothesis for a real trace, never proof that priority-aware LRU wins.

Protect fairness and tenant isolation

A global cache rewards whichever tenant produces the most reusable or recently accessed prefixes, which may be acceptable for a single product and unacceptable for a multi-tenant service. Declare whether capacity is global, partitioned, quota-based, or borrowable. Show occupancy, saved prefill, misses, evictions, and admission failures per scope.

Priority must not become an undeclared billing tier. Cap its range, require expiry, and define how equal priorities interleave across tenants. One practical policy ranks within a tenant quota, then permits borrowing from genuinely idle capacity. Another reserves a minimum share and applies weighted fairness above it. Test an adversarial trace where one tenant floods unique prefixes while another repeats a valuable prefix.

The TensorRT-LLM KV cache documentation documents features and controls in a specific runtime. Treat those controls as deployment evidence to revalidate against the installed version, not as a portable semantic promise. Runtime behavior, block size, events, and metrics belong in the release receipt.

Security review should include timing leakage, cache-salt strategy, purge behavior, adapter isolation, and observability access. Never export raw prompts in a troubleshooting artifact. The lab uses synthetic labels and hashes only. Production traces should preserve structural facts while redacting content, because a perfect KV cache eviction study is not worth turning customer prompts into analytics payloads.

Turn the trace into a release gate

Define success before replay. Hard gates can include zero active-reference eviction, zero broken ancestry, zero cross-scope reuse, bounded memory, and no regression beyond a declared p95 TTFT or fairness threshold. Optimization objectives can then compare avoided prefill time, recompute cost, churn, and admission success among policies that pass every invariant.

Do not average away bursts. Evaluate steady repetition, synchronized fan-out from a shared system prompt, tenant flood, priority expiry, model revision rollover, adapter churn, and cancellation. Include a cold trace where no reuse exists; extra ranking logic should not create unbounded overhead when the cache cannot help.

The LLM inference roofline helps interpret why saved prefill work changes with hardware and sequence shape. Tokens avoided are stable trace evidence, but milliseconds avoided depend on kernels, batching, bandwidth, and accelerator. Publish both, and label modeled time separately from observed time.

Release KV cache eviction behind a reversible configuration. Record policy version, capacity, block size, priority rules, expiry clock, scope, trace hash, simulator hash, runtime build, and comparison thresholds. Roll out by tenant or replica, watch miss latency and memory pressure, and retain the baseline route. An eviction policy is operational control logic; its rollback should not depend on rebuilding model weights or draining the entire fleet.

Ship a bounded policy receipt

The local lab uses a fixed synthetic sequence of arrivals, releases, and prefix references. It makes an LLM prefix cache, prefix cache eviction, prioritized LRU, and KV cache reuse visible in one deliberately small system. It constructs scoped block chains, pins active references, admits within a small capacity, and replays leaf-LRU and priority-aware LRU from the same immutable event list. JSON captures configuration, events, invariants, resident state, and summary metrics; CSV exposes the decision ledger for independent analysis.

Its truth boundary is deliberately narrow. The simulator does not execute a model, allocate GPU memory, predict future reuse, benchmark a serving engine, or recommend one universal policy. Its modeled prefill costs only make policy consequences inspectable. Replace them with profiled costs and a redacted trace from the intended stack before rollout.

Review the receipt after runtime upgrades, block-size changes, model or adapter revisions, tenant-policy changes, or a shift in prompt distribution. A policy can regress when prefix shapes change even if its implementation stays fixed. Keep old traces so a new policy is compared against historical incidents as well as recent traffic.

That is the durable KV cache eviction decision: preserve valid active state, rank only safe inactive leaves, value avoided work rather than raw hits, enforce scope and fairness, and prove the choice on one identical trace. The interactive lab supplies the method. Production telemetry supplies the policy. Neither should pretend to supply the other.

Runnable local artifact — The lab is an educational deterministic simulator with modeled prefill costs; it is not a serving-engine benchmark, GPU-memory allocator, future-reuse predictor, or universal policy recommendation.

Replay one immutable scoped-prefix trace, pin active references, preserve ancestry, compare safe leaf rankings, and export every victim and modeled consequence.