KV Cache Reuse and Prefix Caching, in depth: hash chains versus radix trees, prompt layouts that earn hits, cache-aware routing across a fleet, and isolation

What reuse buys, and the number to watch

Prefill for N prompt tokens on a dense model of P parameters costs roughly 2 × P × N floating-point operations plus an attention term that grows with N squared. A prefix hit of C tokens removes the work for those C tokens; the N − C suffix tokens still attend to all N positions, and decode is unchanged. Reuse therefore buys lower time to first token and spare tensor-core time. It costs HBM: every block held for a future hit is one a running sequence cannot use (see KV cache sizing).

The number to track is the token hit rate: cached prompt tokens divided by total prompt tokens, measured over a window. A request hit rate (the share of requests that hit at all) flatters you, because a request that reuses 16 tokens of a 20,000-token prompt counts as a hit and saves almost nothing. vLLM's counters vllm:prefix_cache_queries and vllm:prefix_cache_hits record queried tokens and cached tokens, so their ratio is the token hit rate. Prometheus clients usually expose counters with a _total suffix:

sum by (instance) (rate(vllm:prefix_cache_hits_total[5m]))
  /
sum by (instance) (rate(vllm:prefix_cache_queries_total[5m]))

Check the exact names on your version's /metrics output before alerting on them.

Two index designs: hash chains and radix trees

Every engine with prefix reuse needs an index that answers one question fast: given this prompt, how many leading tokens already have keys and values in GPU memory, and where? Two designs dominate.

Hash chains. vLLM gives each full fixed-size block an identity: a hash of the parent block's hash, the block's token ids and extra keys such as a LoRA adapter id, multimodal input hashes and an optional cache salt. Equal hashes therefore mean equal prefixes from position zero. Lookup walks the prompt block by block and stops at the first miss; the index is a flat dictionary, and freed blocks keep their hash in an LRU queue until evicted. The cost is granularity: only full blocks are cached.

Radix trees. SGLang's RadixAttention keeps a radix tree whose edges are runs of tokens and whose nodes point at KV storage. Inserting a prompt that diverges from an existing edge splits the edge at the divergence point. Matching is token-granular, so two prompts sharing 1,003 tokens reuse 1,003, and the tree shape makes branching workloads explicit: one system prompt, several tool schemas beneath it, many user turns beneath each. Eviction removes unreferenced leaves in LRU order, which naturally keeps shared trunks alive longer than the private tails hanging off them.

The difference matters less than it looks: a 16-token block wastes at most 15 tokens per request. What both share matters more. A hit requires a match from the first token, because the keys at position 500 depend on every earlier token; a middle segment whose prefix differs cannot be reused safely.

Prompt layouts that earn hits

Since reuse is prefix-only, the order of content inside a prompt decides the hit rate more than any engine flag. The rule is simple: most stable first, most variable last. In practice that is system instructions, then tool or function schemas, then long shared context such as a document or few-shot examples, then conversation history, then the new user message. Each layer should change less often than the one after it.

The misses that hurt are invisible. A timestamp or request id in the system prompt makes every prompt unique from token one. Tool schemas serialised without fixed key order change tokens for the same tools. Retrieval returning the same chunks in a different order shares nothing past the first chunk. A template that rewrites earlier turns invalidates cached history. Build the prompt deterministically and test that it is stable:

import hashlib, json

def render(system, tools, doc_chunks, history, user_msg):
    chunks = sorted(doc_chunks, key=lambda c: c["id"])     # stable, not by score
    parts = [
        system,                                            # changes per deploy
        json.dumps(tools, sort_keys=True, separators=(",", ":")),  # stable bytes
        "\n\n".join(c["text"] for c in chunks),
        *[f"{m['role']}: {m['content']}" for m in history],  # append-only
        f"user: {user_msg}",
    ]
    return "\n\n".join(parts)

def prefix_fingerprint(prompt, tokenizer, n_tokens=2048):
    ids = tokenizer.encode(prompt)[:n_tokens]
    return hashlib.sha256(json.dumps(ids).encode()).hexdigest()[:16]

# CI test: two requests that differ only in the user message must share
# the first 2,048 tokens exactly.
def test_prefix_is_stable(tokenizer):
    a = render(SYSTEM, TOOLS, CHUNKS, [], "What is the refund window?")
    b = render(SYSTEM, TOOLS, CHUNKS, [], "Who signs the contract?")
    assert prefix_fingerprint(a, tokenizer) == prefix_fingerprint(b, tokenizer)

Sorting chunks by id rather than relevance may cost a little answer quality on some models; measure before choosing. Fingerprint token ids, not characters, because a tokenizer can merge characters across the stable-to-variable boundary; ending the stable part on a newline keeps that boundary fixed.

From one replica to a fleet: cache-aware routing

A good hit rate on one replica does not imply one across a fleet. Round robin over R replicas sends each prefix to every replica. For one prefix shared by all traffic that is fine: each replica computes it once. For many distinct prefixes (per document, tenant or conversation) it multiplies the working set by R, and each replica sees only 1/R of the reuses that would keep a prefix warm.

Cache-aware routing fixes this by sending a request to the replica most likely to hold its prefix. Three approaches are in use, in increasing order of accuracy and cost:

• Prefix-hash affinity. Hash the first K tokens (or a document or conversation id) and route with consistent hashing. It is stateless, cheap and deterministic, but blind to load and to what the replica actually evicted.
• Approximate prefix trees in the router. SGLang's router keeps an approximate radix tree per worker of the text it routed there, and sends a request to the longest-matching worker when the match rate exceeds a cache threshold. When load is imbalanced by both an absolute and a relative margin, it falls back to load balancing. The tree is a guess: it does not know what the engine evicted.
• Event-driven KV indexes. NVIDIA Dynamo's KV-aware router consumes events engines publish when blocks are stored or evicted, so its index tracks real cache contents, and weighs overlap against load. The price is an event stream to operate.

Every cache-aware policy must handle hot prefixes. If one document takes 30 percent of traffic, pure affinity melts one replica. The answer is bounded load: route by affinity until a replica exceeds its share by a margin, then spill to the next candidate, which computes the prefix once and then hits too. Hot prefixes end up replicated as widely as their load needs; cold ones live on one replica:

def choose(replicas, prompt_ids, k=1024, overload=1.25):
    key = hash(tuple(prompt_ids[:k]))
    ring = consistent_ring_order(replicas, key)      # stable preference list
    mean_load = sum(r.queued_tokens for r in replicas) / len(replicas)
    for r in ring:                                    # affinity first
        if r.queued_tokens <= overload * mean_load:
            return r                                  # warm or soon warm
    return min(replicas, key=lambda r: r.queued_tokens)  # everyone busy

Worked example: a contract library on eight replicas

A team serves questions over a library of 2,000 contracts, each about 6,000 tokens, on eight replicas of an 8-billion-parameter model with grouped-query attention. In 16-bit precision that model's keys and values take 2 × 32 layers × 8 KV heads × 128 dimensions × 2 bytes = 128 KiB per token, so one contract's prefix occupies about 750 MiB. Each replica has roughly 40 GiB of KV pool, and running requests pin about 15 GiB of it, which leaves about 25 GiB, or some 33 contracts, for idle cached prefixes.

Traffic is skewed: the 250 most active contracts receive 80 percent of questions. Under round robin, each replica receives questions about all 250 hot contracts but can keep only 33 of them, so a question hits only if the same replica saw the same contract recently enough. With the hot set eight times larger than each cache, most hot questions miss and every miss prefills 6,000 tokens.

Under prefix affinity each replica owns about 31 of the hot contracts. That set fits in its 33-contract budget, so hot questions mostly hit and prefill only the 60 to 100 tokens of the question. The fleet now holds about 264 distinct contracts instead of the same 33 eight times. Prefill for hot traffic drops by close to two orders of magnitude. The numbers are illustrative; the shape is general: when the hot set is larger than one replica's cache and smaller than the fleet's, routing is worth more than any engine tuning.

Isolation and side channels

A shared prefix cache is shared state, and shared state leaks. A request whose prefix is cached returns its first token measurably faster than one that is not. An attacker who can send requests to the same engine as a victim can, in principle, guess a prefix, time the response and learn whether someone else recently sent it. Published research has demonstrated timing attacks of this kind against shared prompt caches, so treat the risk as real for multi-tenant deployments.

vLLM supports per-request salting: a cache_salt field in the request is injected into the hash of the first block, so only requests carrying the same salt can reuse each other's blocks. Use one salt per trust group, usually per tenant. That costs cross-tenant sharing of a common system prompt; if the shared part is genuinely public (your own product prompt, not customer data) the loss is modest, because each tenant warms its own copy once. Routing by tenant gives a second layer: tenants who never share a replica cannot probe each other's cache at all.

A correctness corollary: anything that changes keys and values must be in the cache key, including adapter, multimodal inputs and model revision. A restart clears GPU memory, but an offload tier on CPU or disk (see KV cache on disk) must key on model identity too.

Failure modes

Trade-offs

What to do next

1. Graph token hit rate per replica from your engine's counters, after confirming the metric names on /metrics.
2. Add a CI test that two prompts differing only in the user message share the same leading token fingerprint.
3. Audit the prompt for timestamps, request ids, unsorted JSON and relevance-ordered chunks in the stable part.
4. Estimate your hot working set in tokens and compare it with one replica's idle KV budget and the fleet's.
5. If the hot set exceeds one replica, replace round robin with prefix affinity plus a load bound, then compare hit rate and p95 time to first token.
6. Decide your trust groups and set a cache salt per tenant if tenants share engines.
7. Re-read paged KV cache architecture to see how shared blocks are reference counted underneath.