Prefix caching with hash dedup

In production, most requests to an LLM share a system prompt. A customer service chatbot might prepend 500 tokens of instructions to every user message. A coding assistant might include 1000 tokens of context. If you are serving 100 concurrent requests that all share the same 500-token system prompt, you are storing 100 copies of the same KV cache data and computing it 100 times. That is 99 copies and 99 prefill passes too many.

Prefix caching solves this by deduplicating shared prefixes across requests. The idea is borrowed from content-addressed storage (think Git or IPFS): hash the token content of each KV cache block, and if two blocks have the same hash, they contain the same data and can share the same physical memory.

How it connects to the block allocator

In yesterday's block allocator, each request has its own block table mapping logical positions to physical blocks. Prefix caching adds a twist: blocks that correspond to shared prefixes can point to the same physical block from multiple block tables. We add reference counting so a shared block is only freed when all requests that reference it are done.

from dataclasses import dataclass, field
from typing import Dict, List, Optional, Tuple
import hashlib

@dataclass
class PrefixCacheBlock:
    block_id: int
    token_hash: str         # Hash of the token IDs in this block
    ref_count: int = 1      # Number of requests sharing this block
    is_full: bool = False   # Whether the block has all BLOCK_SIZE tokens

@dataclass
class PrefixCachingAllocator:
    num_blocks: int
    block_size: int
    free_blocks: List[int] = field(default_factory=list)
    # Hash table: token_hash -> PrefixCacheBlock
    hash_table: Dict[str, PrefixCacheBlock] = field(default_factory=dict)
    # Per-request block tables
    block_tables: Dict[str, List[PrefixCacheBlock]] = field(default_factory=dict)

    def __post_init__(self):
        self.free_blocks = list(range(self.num_blocks - 1, -1, -1))

    def _hash_tokens(self, token_ids: List[int], prefix_hash: str = "") -> str:
        """Compute a hash for a block of tokens, chained with the prefix hash.
        
        Chaining is critical: the KV values at position N depend on ALL
        preceding tokens, not just the tokens in this block. Two blocks with
        identical tokens but different prefixes produce different KV values.
        """
        content = f"{prefix_hash}:{','.join(str(t) for t in token_ids)}"
        return hashlib.sha256(content.encode()).hexdigest()[:16]

The chained hashing trick

This is the subtlety that makes or breaks prefix caching. You cannot just hash each block's tokens independently. The KV cache at any position depends on all previous tokens due to causal attention. Block 3 of a sequence with prefix "A B C" contains different KV values than block 3 of a sequence with prefix "X Y Z," even if block 3 itself contains the same tokens in both cases.

The solution is to chain hashes: each block's hash includes the hash of all preceding blocks. This is exactly how Git commits work. The hash of block N is:

hash(block_N) = SHA256(hash(block_{N-1}) + tokens_in_block_N)

Two blocks match (and can share physical memory) only if they contain the same tokens and are preceded by the same token sequence. This is precisely the condition under which their KV cache values are identical.

Allocating with deduplication

When a new request arrives, we hash its tokens block by block. For each block, we check the hash table. If a matching block exists and it is still in GPU memory, we increment its reference count and reuse it. If not, we allocate a new physical block and insert it into the hash table.

def allocate_with_prefix(self, request_id: str, 
                          token_ids: List[int]) -> Tuple[int, int]:
    """Allocate blocks for a request, reusing cached prefix blocks.
    
    Returns (num_cached, num_new): how many blocks were reused vs allocated.
    """
    self.block_tables[request_id] = []
    num_cached = 0
    num_new = 0
    prefix_hash = ""

    for i in range(0, len(token_ids), self.block_size):
        block_tokens = token_ids[i:i + self.block_size]
        is_full = len(block_tokens) == self.block_size

        if is_full:
            token_hash = self._hash_tokens(block_tokens, prefix_hash)

            if token_hash in self.hash_table:
                # Cache hit: reuse existing block
                cached_block = self.hash_table[token_hash]
                cached_block.ref_count += 1
                self.block_tables[request_id].append(cached_block)
                prefix_hash = token_hash
                num_cached += 1
                continue

        # Cache miss: allocate new block
        if not self.free_blocks:
            self._evict_unreferenced()
        block_id = self.free_blocks.pop()
        token_hash = self._hash_tokens(
            block_tokens, prefix_hash
        ) if is_full else ""

        new_block = PrefixCacheBlock(
            block_id=block_id, 
            token_hash=token_hash,
            is_full=is_full
        )
        if is_full and token_hash:
            self.hash_table[token_hash] = new_block
        self.block_tables[request_id].append(new_block)
        prefix_hash = token_hash if is_full else prefix_hash
        num_new += 1

    return num_cached, num_new

Freeing and eviction with reference counts

When a request finishes, we decrement the reference count on all its blocks. Blocks with a reference count of zero are not immediately freed; instead, they stay in the hash table as "cached but unreferenced" blocks. If a future request shares the same prefix, it can reuse them without recomputation. They are only truly freed when memory pressure requires it.

def free_request(self, request_id: str):
    """Release a request's claim on its blocks."""
    if request_id not in self.block_tables:
        return
    for block in self.block_tables[request_id]:
        block.ref_count -= 1
        # Don't free immediately; keep in hash table for future reuse
    del self.block_tables[request_id]

def _evict_unreferenced(self):
    """Free cached blocks with zero references (LRU order)."""
    to_remove = []
    for token_hash, block in self.hash_table.items():
        if block.ref_count == 0:
            self.free_blocks.append(block.block_id)
            to_remove.append(token_hash)
            if len(self.free_blocks) >= self.block_size:
                break  # freed enough
    for h in to_remove:
        del self.hash_table[h]
    if not self.free_blocks:
        raise MemoryError("Cannot evict: all blocks are actively referenced")

The savings in practice

Consider a real scenario: 200 concurrent chat requests, all sharing a 512-token system prompt, each with a 256-token user message and generating up to 512 tokens.

Without prefix caching, total KV cache tokens: 200 * (512 + 256 + 512) = 256,000 tokens.

With prefix caching, the 512-token system prompt is stored once (32 blocks at block size 16). Total tokens: 512 (shared) + 200 * (256 + 512) = 154,112 tokens. That is a 40% memory reduction just from deduplicating the system prompt.

But the bigger win is compute. Without prefix caching, every request prefills the 512-token system prompt independently. With it, only the first request computes the KV cache for the system prompt; all subsequent requests skip straight to their unique suffix. For a 7B model, prefilling 512 tokens takes roughly 15ms on an H100. Saving 199 prefills is about 3 seconds of GPU time.

When prefix caching breaks down

Prefix caching only helps when requests share prefixes. If every request has a unique prompt, the hash table fills up with entries that never match, and the overhead of hashing and lookup is pure waste. In practice, three patterns trigger high cache hit rates:

• Shared system prompts: the most common case. Chat APIs prepend the same instructions to every request.
• Multi-turn conversations: each turn shares the entire history of previous turns as a prefix.
• Few-shot prompting: many requests include the same set of examples before the actual query.

Prefix caching is the LLM equivalent of page sharing in operating systems. The same virtual addresses in different processes can map to the same physical page when the content is identical. Content-addressed hashing is the mechanism that detects the match without comparing the actual data.

Connection to radix attention

SGLang takes this further with radix attention, which uses a radix tree (trie) to track all cached prefixes. The radix tree allows efficient longest-prefix matching: given a new prompt, find the longest cached prefix in O(n) time where n is the prompt length. This is more flexible than the block-hash approach because it handles arbitrary shared prefixes, not just block-aligned ones.

But the block-hash approach has its own advantages: it is simpler to implement, integrates cleanly with the block allocator, and the per-block granularity is fine enough for most production workloads where the shared prefix is much longer than one block.

Tomorrow I am moving to the parallelism dimension: simulating tensor parallelism to understand how model weights and activations are split across multiple GPUs.