Prefix Caching and Prompt Reuse in Large-Scale Inference

What is actually being cached

During prefill the model computes a key and a value vector for every token at every layer. Those tensors depend only on the token and everything before it, so two requests that share their first N tokens produce identical keys and values for those N positions. Caching them turns a repeated prefill into a memory lookup, leaving only the new suffix to compute.

The size of that state is what makes the design interesting. Per token it is 2 x layers x KV heads x head dimension x bytes per element. For a model with 32 layers, 8 KV heads under grouped-query attention, head dimension 128 and 16-bit values, that is 2 x 32 x 8 x 128 x 2 = 131,072 bytes, or 128 KiB per token. A 4,000-token shared system prompt and tool schema therefore occupies about 500 MiB of accelerator memory per resident copy. Prefix caching is a capacity decision as much as a latency optimization: every cached block is memory that is not available for running sequences.

The payoff side of the ledger is just as concrete. Consider an agent endpoint where every request carries that 4,000-token prefix followed by about 500 tokens of conversation and new input. Without reuse the server prefills 4,500 tokens per request; with a warm cache it prefills roughly 500, a ninefold reduction in prefill work for that route. Because time to first token on long prompts is dominated by prefill, the user-visible latency improvement is of the same order, and the freed compute goes to decoding other requests. One resident copy of the prefix, shared by every concurrent request that uses it, costs the same 500 MiB whether ten or a thousand requests reference it, which is why reuse gets more valuable as traffic concentrates.

Block hashing versus radix trees

Engines with paged KV caches, such as vLLM, divide each sequence into fixed-size blocks of tokens and identify a full block by a hash of the block's tokens chained to the hash of the previous block. Because each hash covers the entire history up to that block, equal hashes mean equal prefixes, and a lookup walks the new prompt block by block until the first miss. Extra inputs that change the KV contents, such as a LoRA adapter identity or image features, are folded into the hash. Only full blocks are shareable, so the reusable length is rounded down to a block boundary.

import hashlib

BLOCK = 16

def block_hashes(token_ids, extra=b""):
    """Chained hashes for every full block; equal hash => equal full prefix."""
    hashes, parent = [], hashlib.sha256(extra).digest()
    full = len(token_ids) - len(token_ids) % BLOCK
    for start in range(0, full, BLOCK):
        block = token_ids[start:start + BLOCK]
        h = hashlib.sha256(parent + repr(block).encode()).digest()
        hashes.append(h)
        parent = h
    return hashes

def cached_prefix_len(token_ids, table, extra=b""):
    n = 0
    for h in block_hashes(token_ids, extra):
        if h not in table:
            break
        n += BLOCK
    return n

SGLang's RadixAttention stores the same information as a radix tree keyed by token sequences. Each edge holds a run of tokens and the KV cache for them, shared prefixes share tree nodes, and eviction removes least recently used leaves. The tree matches at token granularity and makes multi-branch reuse natural, for example many sampled continuations of one prompt, or conversations that fork. Hash tables are simpler to make concurrent and distribute; trees give finer-grained matching and a natural structure for scheduling requests that share prefixes together. Either way the observable contract is the same: a longest-prefix match that returns a number of reusable tokens and pins the matched blocks while the request runs.

Designing prompts for reuse

The cache can only reuse what is byte-identical at the token level from the very first token, so prompt layout determines hit rate more than any engine setting. Put the most stable content first: system instructions, tool definitions, policy text and long reference documents. Put volatile content last: retrieved passages that change per query, the user's message, and anything derived from the current request. A single dynamic token near the start invalidates everything after it.

• Do not put timestamps, request ids or user names in the system prompt; pass them in a late message or as metadata.
• Serialize tool schemas and JSON deterministically, with stable key order and whitespace; a reordered dictionary is a cache miss.
• Sort or pin the order of retrieved documents where quality allows, so that repeated queries over the same corpus share longer prefixes.
• Keep chat templates versioned; a template change silently shifts every token after the first special marker.
• Watch tokenizer boundaries: two strings that differ only after the cut point can still tokenize differently at the join, so the shared prefix is measured in tokens, not characters.

Hosted model APIs expose the same economics as prompt caching, either through explicit cache breakpoints in the request or through automatic prefix matching above a minimum length, and usually bill cached input tokens at a discount. The layout rules are identical, which is convenient: a prompt engineered for your own engine's prefix cache is also engineered for a provider's.

Routing requests to their cache

A prefix cache is local to a replica's memory. With round-robin load balancing across N replicas, the chance that a request lands on the replica holding its prefix is roughly 1/N, and every replica ends up caching the same popular prefixes independently. Cache-aware routing fixes this by sending requests with the same prefix to the same replica. The simplest version hashes a leading span of the prompt, for example the first few blocks or an explicit session or prompt-template key, and uses consistent hashing to pick a replica.

Pure affinity creates hot spots, because prefix popularity is heavily skewed. A viral system prompt would pin a large share of traffic to one replica. The standard remedy is bounded-load consistent hashing: route to the preferred replica unless its load exceeds a multiple of the mean, and otherwise walk the ring to the next candidate. More advanced routers score each replica by the estimated number of cached tokens it holds for this request minus a penalty for its queue depth, which requires replicas to publish summaries of their cache contents.

import bisect, hashlib

class BoundedPrefixRouter:
    def __init__(self, replicas, vnodes=64, slack=1.25):
        self.ring = sorted((self._h(f"{r}#{i}"), r) for r in replicas for i in range(vnodes))
        self.keys = [k for k, _ in self.ring]
        self.load = {r: 0 for r in replicas}
        self.slack = slack

    @staticmethod
    def _h(s):
        return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")

    def pick(self, prefix_key):
        cap = self.slack * (sum(self.load.values()) + 1) / len(self.load)
        i = bisect.bisect(self.keys, self._h(prefix_key)) % len(self.ring)
        for step in range(len(self.ring)):
            replica = self.ring[(i + step) % len(self.ring)][1]
            if self.load[replica] + 1 <= cap:
                self.load[replica] += 1
                return replica
        return min(self.load, key=self.load.get)

    def done(self, replica):
        self.load[replica] -= 1

Eviction, offload and lifetime

Cached blocks are only freeable when no running request references them, so engines keep a reference count per block and place blocks with a zero count on an eviction list, usually least recently used. Under memory pressure, running sequences always win: the cache is opportunistic and shrinks to make room for active work. That means hit rates fall exactly when the server is busiest, which is worth knowing when interpreting dashboards. A cache that looks excellent at night and poor at peak is often behaving correctly.

Offload tiers extend the cache below accelerator memory. Evicted blocks can be copied to host DRAM or local SSD and brought back on a hit, which is worthwhile when the transfer is cheaper than recomputing the prefill. For long prefixes on large models it often is; for short prefixes the transfer overhead and bookkeeping can exceed the saving. External KV stores shared across replicas push this further, allowing a prefix computed on one node to be fetched by another, but they introduce network cost, consistency questions and a larger security boundary.

Lifetime also has a correctness dimension. KV contents depend on the exact weights, the quantization scheme, any adapter, the tokenizer and the positional encoding configuration. An in-process cache is naturally cleared when the engine restarts with new weights. A persistent or shared cache is not, so its keys must include a model fingerprint, adapter id and tokenizer version, and a deploy must invalidate or partition the old entries. Reusing KV from a different model version does not fail loudly; it produces subtly wrong outputs.

Isolation and side channels

A shared prefix cache leaks information through timing. A request whose prefix is cached returns its first token faster, so a tenant who can guess a candidate prompt, such as another customer's system prompt or a document they might have uploaded, can submit it and observe time to first token to learn whether someone else recently sent it. On a multi-tenant endpoint this is a real confidentiality issue, not a theoretical one.

The fix is to scope reuse to a trust boundary. Mix a per-tenant secret into the root of the block hash chain so identical prompts from different tenants map to different cache entries; some engines expose exactly this as a per-request cache salt. Shared public prefixes, such as a platform-wide system prompt, can be deliberately placed in a common scope. Isolation costs hit rate, so decide the boundary explicitly and document it rather than inheriting whatever the engine default happens to be.

Measuring it

Report hit rate in tokens, not requests: the fraction of prompt tokens served from cache across all requests. A request-level hit rate counts a one-block match on a 30,000-token prompt as a success. Break the token hit rate down by route, prompt template and tenant, and pair it with prefill tokens computed per second, time to first token for hits versus misses, eviction rate, offload transfer time and the share of KV memory occupied by cached versus running blocks.

The most useful experiment is a replay of real traffic with caching disabled, enabled, and enabled with cache-aware routing, measuring time to first token percentiles and total GPU-seconds of prefill. That separates the gain from caching itself from the gain from routing, and it usually shows that prompt layout fixes deliver more than any engine flag.