Automatic prefix caching

With PagedAttention, KV lives in fixed-size blocks. Automatic prefix caching (APC) hashes the token contents of each block, and typically a hash chain from the parent block, so identical token spans map to the same cache entry.

When a new request arrives, the engine walks its tokens block by block, looks up hashes in a global map, reuses physical KV blocks on a hit, and prefills only the remaining suffix. No application change is required if prompts naturally share prefixes.

The big idea

Think of a content-addressed disk. Two files with the same first 4 KB share one block. The next 4 KB gets its own block only if it differs.

The picture breaks at alignment. Hashing is by blocks. A shared span shorter than a block, or split across a boundary, may not hit. Long shared prefixes shine.

Walking through a lookup

1. Walk the new request's token sequence block by block.
2. Look up each hash in the global cache map.
3. On hit, reuse physical KV blocks and bump reference counts, instead of computing prefill for that span.
4. On miss, run prefill for the remaining suffix and insert new blocks.

Invisible hashing is why "we did not implement caching" can still show cache hits in vLLM metrics once APC is enabled. Treat those metrics as a product signal. If hit rate is near zero, prompts are probably too unique in the first blocks. Fix serialization before buying more GPUs.

Caveats:

• Token identity matters. Paraphrased system prompts with the same meaning miss.
• Block alignment. Very short shared prefixes may not fill a block.
• Memory. Cached blocks occupy GPU RAM until eviction. They compete with active KV.

Common mistakes

• Ignoring hit-rate metrics. APC can be on and still miss if the first blocks differ.
• Assuming meaning is enough. The hash is over tokens, not paraphrases.
• Forgetting cached blocks cost HBM. They steal room from the live batch.

Check yourself

1. Two prompts share 50 tokens and the block size is 16 tokens. About how much can hit? Answer: three full blocks (48 tokens). The leftover 2 tokens do not fill a block.
2. Why can APC show hits when the product never called a cache API? Answer: the engine hashes blocks itself. Shared prefixes collide without an application change.

Key takeaways

• APC content-addresses paged KV blocks by token hashes.
• Hits reuse physical blocks. Misses prefill the suffix.
• Alignment and token identity decide whether a prefix hits.
• Cached blocks compete with live KV for GPU memory.

Further learning

SGLang stores the same idea as a tree: RadixAttention. Woosuk Kwon's talk covers the paging foundation: