Prefix Caching

The problem: redoing work you've already done

Every time a request arrives, the prefill phase → Ch.06 processes its input tokens — computing Key and Value vectors for each one and writing them to the KV cache → Ch.03. This is expensive. But what if two consecutive requests share the exact same first 2,000 tokens — a system prompt, say? Without prefix caching, you'd pay the full prefill cost twice, writing identical data into the cache twice. That's pure waste.

Prefix caching is especially powerful in real deployments because shared content is extremely common. Every request in a chatbot shares the same system prompt. Every request in a RAG pipeline shares the same retrieved documents. Every turn in a multi-turn conversation shares all the prior turns. Across thousands of requests per second, the compute savings are enormous.

How prefix caching works — three building blocks

Prefix caching is built on top of PagedAttention's block structure → Ch.04. Because the KV cache is already divided into fixed-size blocks, and because each block holds exactly block_size tokens, it's natural to ask: "have I already computed the KV data for these exact tokens?" The answer is a hash lookup.

Building block 1 — Hash functions: turning content into a fingerprint

A hash function is a mathematical recipe that takes any input — a block of tokens, a document, a file — and produces a short, fixed-length string called a hash or fingerprint. Two critical properties make hashes useful for caching:

nano-vLLM uses a specific hash function called xxhash — chosen because it's extremely fast (computing a hash takes microseconds, far less than the prefill time it might save) and produces a 64-bit integer output that is compact enough to use as a dictionary key.

Building block 2 — The hash-to-block map

The block manager → Ch.04 maintains a Python dictionary: hash_to_block. The key is the xxhash of a block's token content. The value is the physical block ID where those tokens' KV data already lives in the cache. When a new request arrives, the block manager hashes each of its first N blocks and checks this dictionary. If the hash is found, that's a cache hit — the KV data already exists and can be reused instantly. If not, that's a cache miss — prefill must compute that block fresh.

Building block 3 — Reference counting for shared blocks

When a block is shared between multiple requests via the cache, we can't just free it when one request finishes — other requests might still need it. The block manager uses a reference count (already introduced in Ch.04 → Ch.04 for copy-on-write) — an integer tracking how many requests are pointing to a block. The block is only returned to the free list when its reference count drops to zero. Until then, it stays in the cache, ready to serve future cache hits.

What happens when a request arrives — the full algorithm

When the block manager's allocate_with_prefix() is called for a new sequence, it runs through the request's token blocks one by one from the start, checking for cache hits before allocating any new blocks.

See prefix caching in action — send multiple requests

The simulation below shows how the hash-to-block map fills up as requests arrive. Each request is divided into blocks. Green blocks are cache hits (reused instantly). Cyan blocks are cache misses (must run prefill). Yellow blocks are unique to this request. Watch how the second and third requests with the same system prompt pay progressively less prefill cost.

When prefix caching wins — and by how much

The savings from prefix caching depend on one thing: how many tokens are shared between requests. Here are the scenarios where it matters most.

LRU eviction — keeping the most useful blocks alive

LRU (Least Recently Used) is a simple but effective eviction strategy. The idea: if a block hasn't been accessed recently, it's unlikely to be accessed soon. Evict the block that was last used the longest time ago. For prefix caching, this means a system prompt that's being actively used stays in the cache. A system prompt from a conversation that ended an hour ago gets evicted first. The cache naturally prioritises the content that's most likely to produce hits.

The prefix cache in code

Prefix caching lives in core/block_manager.py → Ch.02. The key addition over basic PagedAttention → Ch.04 is the hash_to_block dictionary and the hash-check loop inside allocation.

import xxhash

def allocate_with_prefix(self, seq: Sequence) -> bool:
    seq.block_table = []
    seq.num_cached_tokens = 0  # how many tokens we can skip in prefill

    # How many FULL blocks does this sequence have?
    # Only full blocks are eligible for prefix caching.
    num_full_blocks = len(seq.tokens) // self.block_size

    # ── PHASE 1: check for prefix cache hits ──────────────────
    for i in range(num_full_blocks):
        # Extract the token IDs for this block
        start = i * self.block_size
        block_tokens = seq.tokens[start : start + self.block_size]

        # Hash the token content → fingerprint for this block
        # bytes() converts the list of ints to a byte string for hashing
        h = xxhash.xxh64(bytes(block_tokens)).hexdigest()

        if h in self.hash_to_block:
            # ✓ CACHE HIT — this block's KV data already exists
            blk = self.hash_to_block[h]
            self.ref_counts[blk] += 1    # one more request using this block
            seq.block_table.append(blk)
            seq.num_cached_tokens += self.block_size
        else:
            # ✗ CACHE MISS — stop checking prefix; allocate fresh from here
            break

    # ── PHASE 2: allocate fresh blocks for the miss region ────
    remaining_tokens = len(seq.tokens) - seq.num_cached_tokens
    blocks_needed = math.ceil(remaining_tokens / self.block_size)

    if len(self.free_blocks) < blocks_needed:
        return False  # signal OOM to scheduler

    for _ in range(blocks_needed):
        blk = self.free_blocks.pop()
        self.ref_counts[blk] = 1
        seq.block_table.append(blk)

    return True

def register_prefix(self, seq: Sequence) -> None:
    # After prefill writes KV data to the new blocks,
    # register their hashes so future requests can hit them.
    num_full_blocks = len(seq.tokens) // self.block_size

    for i in range(seq.num_cached_tokens // self.block_size, num_full_blocks):
        # Only register blocks that were freshly computed (not already cached)
        start = i * self.block_size
        block_tokens = seq.tokens[start : start + self.block_size]
        h = xxhash.xxh64(bytes(block_tokens)).hexdigest()

        blk = seq.block_table[i]
        self.hash_to_block[h] = blk   # register: this hash lives at this block
        # ref_count stays at 1 — owned by this sequence for now
        # If another request hits this hash later, ref_count will increment

What prefix caching enables at scale

Things beginners get wrong about prefix caching

Quiz

Three questions on prefix caching. Wrong answers explain exactly where the reasoning broke down.

What you now know