Prefix Caching and Shared Residency

Requests to a language model are rarely independent. A system prompt of several thousand tokens is identical across every request from the same application. A document being summarised is processed once per question asked about it. A multi-turn conversation re-sends the entire history with each new user message. In all three cases the leading tokens of the sequence are byte-identical, and the keys and values computed for them are byte-identical too, because attention over a prefix depends only on the prefix.

Recomputing those keys and values per request is pure waste, and the waste scales with the prefix length. Prefix caching removes it by keeping the computed blocks and letting a new sequence point at them instead of recomputing. The mechanism is content addressing over block boundaries, and its constraints come from the fact that a block’s cache depends on everything before it.

Why a block’s cache depends on its position

A token’s key is a linear projection of its hidden state, and its hidden state at layer $\ell$ is a function of all preceding tokens through the attention at every layer up to $\ell$. This is why prefix caching works at all: identical prefixes produce identical caches. It is also why suffix caching does not: a block’s contents depend on the prefix, so two sequences that share a suffix but differ in their prefix have different caches for that suffix.

The dependency chain is per position and cumulative. Position 100’s cache at layer 5 depends on positions 0 through 100. If two sequences agree on positions 0 through 100, they agree on the cache for those positions at every layer. If they agree on 0 through 99 and diverge at 100, they agree on the cache for 0 through 99 and diverge from 100 onward.

This makes the natural unit of sharing the prefix, and the natural unit of granularity the block. A block covering positions $[kP, (k+1)P)$ has a cache determined by positions $0$ through $(k+1)P - 1$, which is the block itself plus everything before it. So a block’s identity is a function of its own tokens and the identity of the block before it.

Chaining hashes across blocks

The standard scheme hashes each block’s tokens together with the hash of the preceding block, producing a chain. Block 0’s key is a hash of its token ids. Block 1’s key is a hash of block 0’s key concatenated with block 1’s token ids. And so on. Two sequences that share a prefix of $n$ blocks produce the same keys for all $n$ blocks, regardless of what follows.

def prefix_keys(token_ids, block_size, seed=b"kv"):
    keys, prev = [], seed
    for start in range(0, len(token_ids) - block_size + 1, block_size):
        chunk = token_ids[start:start + block_size]
        prev = hashlib.sha256(prev + b"|" + bytes(str(chunk), "ascii")).digest()
        keys.append(prev)             # identity of this block given its prefix
    return keys

Only full blocks are hashed. A trailing partial block cannot be shared safely, because a second sequence with the same partial tokens may continue differently, and the block would then need copy-on-write for every position rather than every block. Restricting sharing to full blocks keeps the copy-on-write unit aligned with the allocation unit.

The hash chain has a property worth noting: the cost of computing it is linear in the number of blocks, not in the number of tokens, because each block’s hash is over a fixed-size chunk. For a 10,000-token prompt with 16-token blocks that is 625 hashes of 16 integers each, which is negligible beside the prefill it might save.

A collision in the chain means two different prefixes map to the same key and one sequence receives another’s cache. With a 256-bit hash the probability is negligible for any realistic number of blocks, but the consequence is silent wrong output rather than a crash. Implementations that cannot tolerate even that risk compare the stored tokens on a hit, at the cost of keeping the tokens alongside the blocks.

The lookup and its granularity

A new request arrives with its full token sequence. The scheduler computes the chain of keys and probes the cache index for the longest matching run from block 0. The probe stops at the first miss, because a miss at block $k$ makes every later block’s key unpredictable without recomputation: block $k+1$‘s key includes block $k$‘s, and the cached block $k$ may belong to a different sequence.

The match length determines the work saved. If $m$ blocks hit, the request skips $mP$ tokens of prefill, and its cache blocks for those positions are shared with reference count increments rather than allocated and written. The remaining $T - mP$ tokens are prefilled normally, with attention over the shared prefix as well as the new tokens.

Granularity has a direct cost. A request whose shared prefix is 3,900 tokens with a block size of 16 matches 243 blocks and recomputes 12 tokens. A request whose shared prefix is 3,905 tokens with a block size of 256 matches 15 blocks and recomputes 65 tokens. Small blocks match more precisely; large blocks have smaller tables. The same trade as paged allocation, with an extra term: small blocks also mean more hashes and more index probes per request.

What eviction must not do

Shared blocks break the simple eviction rule that a block is free when no sequence references it. A block with a reference count of zero may still be valuable, because a future request may match it. Prefix caches therefore retain blocks after their last reference drops, and treat the pool as a two-level structure: blocks referenced by a running sequence, and blocks held only as cache.

The second category must be evictable under pressure. The usual policy is least-recently-used over the unreferenced set, with the constraint that evicting block $k$ must invalidate every cached block after it in the chain, since those blocks’ identities are defined relative to $k$. Evicting a middle block of a long shared prefix therefore invalidates the whole suffix of that prefix, which means the eviction order should be from the end of the chain backwards.

A policy that ignores the chain relationship produces a cache that appears to hold many blocks but can only serve matches up to the first hole. This is the prefix-cache analogue of a fragmented file: the blocks exist, the chain does not.

Retention also interacts with the LRU order in a non-obvious way. A long shared system prompt is referenced by every request, so its blocks are touched constantly and never evicted. A one-off long document is touched once and then sits. The pool fills with one-off documents and the LRU policy evicts them first, which is correct. The pathological case is a set of distinct long prompts arriving in rotation, each touched just often enough to stay ahead of eviction while the working set exceeds the pool. Then the cache provides no hits and consumes the whole pool, and the scheduler must cap the cache’s share of memory to keep the decode batch alive.

The interaction with scheduling

Prefix caching changes the arithmetic that admission control uses. A request that matches $m$ blocks needs $m$ blocks of residency, but those blocks are shared, so the pool’s consumption is zero for them. The effective cost of admitting such a request is the cost of its unshared suffix. A scheduler that ignores this will under-admit when the workload has heavy prefix reuse.

The reverse error is more dangerous. A scheduler that counts shared blocks as free may admit many requests that all share a prefix, then have them diverge, at which point every one needs its own copy of the divergent blocks. Copy-on-write converts one shared block into two, then three, and the pool’s free count falls in a burst. The growth allowance from admission control and the memory watermark has to cover divergence, not just token growth.

Beam search and parallel sampling make this concrete. A request that samples eight completions from one prompt shares the prompt’s blocks, and each sample allocates its own blocks as it diverges. The sharing saves the prompt’s residency eightfold, and the divergence cost is eight separate continuations. Both numbers are needed to size the admission.

There is a second scheduling benefit that is easy to overlook. Because the shared blocks are already resident, a request with a long shared prefix can begin decoding almost immediately: its unshared prefill is short, so its time-to-first-token falls to the cost of processing only the suffix. For workloads dominated by a fixed system prompt, this is a larger latency improvement than the memory saving, and it is why prefix caching is often enabled for latency reasons alone.

Limits

The cache is only useful when prefixes repeat exactly, including whitespace and any template text. A prompt template that inserts a timestamp or a request identifier near the beginning destroys every match after that point, which is why such fields belong at the end of a prompt rather than the start.

Cross-model sharing is not possible: caches are specific to the weights that produced them, so a cache populated by one model version cannot serve another. A deployment serving several models must partition the cache per model or accept that matches never cross.

Finally, the cache’s contents are derived from user input. Two tenants sharing a prefix share memory, and while the values are not directly readable through the API, the residency pattern reveals that the prefixes matched. Deployments with isolation requirements either disable cross-tenant matching or restrict it to a per-tenant namespace, at the cost of losing the sharing that made the mechanism worthwhile. The physical residency side of multi-device deployments is covered in tensor-parallel residency and interconnect pressure.