LLM KV Cache Eviction: Protect Latency Under Memory Pressure

An overloaded LLM server often runs out of memory before it runs out of math. Every active sequence holds key and value tensors for its previous tokens. Without an explicit LLM KV cache eviction policy, one long conversation can crowd out dozens of short requests and turn stable latency into a queue.

This tutorial builds the policy as a control system: measure pressure, classify cache blocks, choose victims, and verify that the cure does not create more recomputation than it saves.

Prerequisites

You should know basic transformer inference and have metrics for GPU memory, request state and token counts. The examples use Python-like pseudocode because vLLM, TensorRT-LLM and custom runtimes expose different hooks.

Before changing policy, record p50, p95 and p99 time-to-first-token, inter-token latency, cache hit rate, preemption count and tokens recomputed. A lower memory watermark is not a win if p99 latency doubles.

Step 1: calculate the real cache budget

Reserve memory for model weights, activations, CUDA graphs and a safety margin. The remainder is your usable KV budget.

usable_bytes = total_vram - weights - runtime_reserve - safety_margin
high_watermark = int(usable_bytes * 0.92)
low_watermark = int(usable_bytes * 0.82)

Use two thresholds. Eviction begins at the high watermark and stops below the low watermark. This hysteresis prevents the scheduler from evicting one block on every allocation.

Expected result: normal traffic stays below the high watermark; bursts cause one bounded cleanup cycle instead of continuous churn.

Step 2: track blocks, not whole conversations

Paged-attention runtimes divide KV data into blocks. Track each block’s bytes, last access, owning request, recomputation cost and whether it is shared by prefix caching.

class CacheBlock:
    bytes: int
    last_used_ms: int
    owner: str
    tokens: int
    shared_refs: int
    priority: int

Whole-sequence eviction is simple but wasteful. A 100,000-token chat may have a cold middle, a reusable system prefix and a hot recent window. Block metadata gives the scheduler options.

Step 3: score eviction candidates

Pure least-recently-used behavior is a reasonable baseline, but production workloads need cost awareness. Shared prefixes and expensive-to-recompute blocks should be harder to evict.

def victim_score(block, now_ms):
    age = now_ms - block.last_used_ms
    reuse_penalty = 4_000 * block.shared_refs
    recompute_penalty = 2 * block.tokens
    priority_penalty = 10_000 * block.priority
    return age - reuse_penalty - recompute_penalty - priority_penalty

Evict the highest scores until memory falls below the low watermark. Keep priority coarse—perhaps zero for batch, one for interactive and two for protected system work. Too many tiers make capacity planning opaque.

Step 4: decide what preemption means

When an active request loses cache, you can recompute tokens later, swap blocks to CPU memory, or reject lower-priority work. Each option shifts cost.

• Recomputation avoids transfer overhead but consumes GPU time.
• CPU swap preserves work but can be limited by PCIe bandwidth and host memory.
• Admission control protects existing requests but produces explicit errors.

A sensible default is recomputation for short batch prompts, host swap for moderately sized paused requests, and admission control when both GPU and host watermarks are exceeded.

Step 5: protect the decoding set

Requests emitting tokens now are latency-sensitive. Prefer evicting queued or paused sequences before active decoders. Do not make the rule absolute: one runaway decoder with a huge context still needs a cap.

if request.state == "DECODING":
    block.priority += 1
if request.context_tokens > tenant_limit:
    block.priority -= 1

Per-tenant limits prevent a single customer from consuming the shared cache. Charge reserved cache bytes to the same quota system used for tokens or concurrent requests.

Step 6: test with adversarial traffic

Replay at least four shapes: many short chats, a few maximum-context requests, mixed batch and interactive traffic, and repeated shared prefixes. Increase arrival rate until the system crosses both watermarks.

Success means:

• no out-of-memory crashes;
• bounded preemption per minute;
• interactive p99 within the service objective;
• recomputed tokens remain an understood fraction of throughput;
• one tenant cannot starve others.

Common mistakes

Evicting shared prefixes too early

A prefix with many references may look old while still saving large amounts of prefill work. Count references and recent downstream hits.

Measuring only cache hit rate

A high hit rate can coexist with bad tail latency if large requests monopolize memory. Pair hit rate with bytes, recomputation and latency by request class.

Waiting for allocation failure

Emergency cleanup is already late. Start at a high watermark and keep a reserve for kernels and temporary buffers.

Ignoring cancellation

Disconnected clients and timed-out jobs must release blocks quickly. A cancellation leak looks exactly like organic memory pressure.

A practical starting policy

Start with paged blocks, high/low watermarks, LRU scoring, protection for active decoding and shared prefixes, and hard per-tenant context limits. Add swapping only after measuring transfer cost on your hardware.

The takeaway is simple: KV cache is a scheduled resource, not leftover memory. Treating eviction as an explicit policy turns overload from a GPU crash into a predictable tradeoff you can monitor and improve.