S07Memory & KV Cache·263 lines

Prefix Caching

Shared system prompts, few-shot examples and multi-turn chats mean most prefill tokens have been computed before. Hash the blocks and reuse them.

block hashing
radix tree
LRU eviction
reference counting
cache hit rate

Motivation

The problem

Look at what a real chat server receives. A 1,500-token system prompt, a few thousand tokens of few-shot examples or retrieved documents, then forty tokens of user question. The next request is identical except for the last forty tokens. So is the one after that.

Multi-turn conversation is worse, or better, depending on your point of view. Turn five of a conversation resends turns one through four verbatim. Every one of those tokens was prefilled seconds ago, and the engine throws all of it away and computes it again.

Prefill is compute-bound, so this is not a small tax. On a chat workload with a large system prompt, redundant prefill can be the majority of all GPU work the server performs.

Core idea

The solution

S06 already gave us shareable blocks; what was missing was a reason to point two requests at the same one. Prefix caching supplies it: give each block an identity derived from its contents, and look that identity up before computing anything.

The identity has to include position, or a block of tokens appearing at a different offset would falsely match. The standard trick is a chained hash: a block's hash covers its own tokens and its parent's hash.

hash-based prefix reusepython

def match_prefix(self, token_ids, block_size):
    """Return the physical blocks we can reuse, and where prefill must start."""
    reused, parent_hash = [], None

    for start in range(0, len(token_ids) - block_size + 1, block_size):
        block = tuple(token_ids[start : start + block_size])
        h = hash((parent_hash, block))       # chained: position is baked in

        node = self.cache.get(h)
        if node is None:
            break                            # first miss ends the shared prefix
        node.last_used = self.clock
        node.ref_count += 1
        reused.append(node.physical_block)
        parent_hash = h

    return reused, len(reused) * block_size   # prefill starts here

Only full blocks are cacheable

A partially-filled trailing block cannot be hashed, because the request is about to append more tokens and change its contents. Prefix cache hits therefore always land on a block boundary, and a smaller block size gives finer-grained sharing at a higher cost.

Mechanics

How it works

Diagramhash chaining and the radix tree

Requests sharing a prefix converge on the same nodes. The tree is a view of which block tables happen to overlap, rather than a data structure of its own.

Eviction is where the subtlety lives

The cache is finite, so blocks must be evicted. A naive LRU is wrong in two ways.

Never evict a node that has cached children. The children's hashes were computed from this node. Drop the parent and the children become unreachable garbage occupying memory. Evict leaves only.
Never evict a block a running request is using. Reference counting handles this: a block with refcount > 0 is pinned, and only becomes eligible when the last request using it finishes.

The result behaves like an LRU over the frontier of the tree. That protects the shared system prompt for free: it is always an interior node with many children, so it is never a candidate.

Radix trees and the SGLang variant

vLLM implements this as a flat hash map from block hash to block, with the tree structure implicit in the parent pointers. SGLang makes it explicit with RadixAttention: a radix tree keyed on token sequences, where edges carry variable-length token runs rather than fixed blocks.

The explicit tree matches at token granularity rather than block granularity. For short shared prefixes that matters, and the eviction policy becomes literal leaf-LRU on a tree. The cost is a more complex structure to keep consistent with the allocator.

Explore

Try it

Six requests sharing a system prompt, cycling repeatedly: roughly what a chat endpoint sees. Run it and watch the second pass, where the tree stops growing and the log turns green.

Simulatorprefix cache with LRU evictionrun twice through the traffic, then shrink capacity

block size4cache capacity (blocks)24

step 0 / 24

prefix hit rate: 0%
tokens reused: 0
tokens prefilled: 0
evictions: 0

radix tree · 0/24 blocks cached

empty — press run

Each node is one cached block. Depth is position in the prompt, so a shared system prompt appears once at the root and every request hangs off it. Green nodes have been reused.

request log

no requests yet

Green is prefill you did not have to do. On the second pass through the traffic the system prompt is free for every request. That cuts time-to-first-token directly, not only GPU cost.

what this does to TTFT

no prefix cache

with prefix cache

Prefill is compute-bound, so skipping it is a near-linear latency win. Production chat traffic with a large shared system prompt routinely reports 60–90% hit rates. vLLM and SGLang both ship it on by default.

Now drag capacity down to 8 blocks. Evictions start and the hit rate drops. KV cache capacity and prefix cache capacity are one budget: every block spent holding history for a possible future request is a block unavailable to a running one.

Build it

Implementation

code/s07_prefix_caching.py (excerpt)python

def evict(self, n_needed: int):
    """LRU over evictable leaves only."""
    has_cached_child = {node.parent_hash for node in self.cache.values()}

    candidates = [
        node
        for h, node in self.cache.items()
        if node.ref_count == 0            # not pinned by a running request
        and h not in has_cached_child     # not a prefix of something cached
    ]
    candidates.sort(key=lambda n: n.last_used)

    for node in candidates[:n_needed]:
        self.free_blocks.append(node.physical_block)
        del self.cache[node.hash]

Hash collisions are a correctness bug, not a performance bug

If two different token sequences hash to the same value, one request silently reads another's KV cache. The output is fluent and wrong, and nothing logs an error. Production engines use a 64-bit or wider hash and, in the more paranoid configurations, store the token IDs alongside the hash and compare them on a hit. If you are building this for real, store the tokens and compare.

Prefix caching leaks information across requests

A cache hit is faster than a miss, and that timing difference is observable. An attacker who can time requests learns whether a particular prefix is already cached, and on a multi-tenant server that reveals what other users have sent. Engines that care about this scope the cache per tenant or per API key; if you serve multiple customers from one instance, this is not optional.

Run it locally

Builds a chained-hash prefix cache over the S06 block manager, replays a synthetic chat workload with a shared system prompt and multi-turn conversations, and reports hit rate, prefill tokens saved, and eviction behaviour as capacity shrinks.

$ python code/s07_prefix_caching.py

Expect: A block hit rate around 80% on the chat workload, roughly 78% of prefill tokens reused, and a capacity sweep showing how leaf-only LRU protects the shared prefix.

Only NumPy is required — setup instructions.

Production notes

In production

vLLM — enable_prefix_caching, on by default in v1. Uses chained block hashes over the same block pool as PagedAttention.
SGLang — RadixAttention; the cache is the allocator, with token-granular matching.
Anthropic and OpenAI APIs — surface this as prompt caching: Anthropic lets you place explicit cache_control breakpoints, while OpenAI caches automatically for prompts of 1,024 tokens or more; both discount cached tokens. The API-level feature is this mechanism with a price attached.
quant.cpp — serialises the compressed KV cache to a .kv file so a session resumes with zero re-processing. That is the single-user version of the same idea.

Exercises

1
Add token-ID comparison on cache hits and construct a deliberate collision to prove your check catches it.
2
Implement a two-tier cache: GPU blocks backed by a CPU-memory second tier. Measure whether the PCIe transfer is cheaper than recomputing prefill. The answer depends on prompt length; finding the crossover is the point.
3
Implement cache-aware routing: with two engine replicas, send each request to the replica most likely to already hold its prefix. Measure the hit-rate improvement over round-robin.

Continue

What's next

We have made the cache small, shareable and reusable. The last memory lever is to make every number in it smaller. S08 covers quantization: INT8 and INT4 weights, group-wise scales, GGUF K-quants, and the KV cache compression that buys long context on consumer hardware.

Check yourself

Questions

Answer before you look. A wrong answer tells you more than a right one, because the explanation points at the part of the chapter to reread.

Check yourselfQuestion 1 of 6

Why does a block's hash include its parent block's hash rather than just its own tokens?

Score 0/6