Prefix Caching

Many requests share the same opening tokens: a long system prompt, a few-shot template, a common document. Prefix caching computes the KV Cache for that shared prefix once and reuses it across every request that starts the same way, skipping redundant prefill.

The idea

The KV of a token depends only on the tokens before it. So the KV for a shared prefix is identical across requests and can be computed once, stored, and reused.

How it works

• Hash the prefix (often block by block) and key the cached KV blocks by that hash.
• A new request whose prefix matches reuses those blocks and only prefills the tokens after the shared part.
• Built on Paged Attention: shared blocks are pointed to by multiple sequences via copy-on-write, so no data is duplicated.
• Also see SGLang’s RadixAttention for a different implementation.

Payoff

• Cuts prefill compute and time to first token (see Inference Metrics) for workloads with heavy prompt reuse.
• Biggest wins: shared system prompts, few-shot prompts, multi-turn chat (each turn reuses the whole prior conversation), and RAG with repeated context.

Limits

Only an exact prefix match helps: a single differing earlier token invalidates everything after it. Cached blocks also consume memory, so they are evicted under pressure, usually least-recently-used.

BLOCK = 16
 
def block_hashes(tokens):
    """Chained hash per full block - have the identity be these tokens and all the tokens before it"""
    hs, parent = [], 0
    for i in range(len(tokens) // BLOCK):
        parent = hash((parent, tuple(tokens[i*BLOCK: (i+1) * BLOCK])))
 
        hs.append(parent)
    return hs
 
 
class PrefixCache:
    def __init__(self, num_blocks):
        self.free = list(range(num_blocks))
        self.cached = {} # map block hash to physical block id
 
    def allocate(self, tokens):
        hashes = block_hashes(tokens)
        tables, n_hit = [], 0
 
        # reuse longest contiguous run of already computed blocks
        for h in hashes:
            if h not in self.cached:
                break
            table.append(self.cached[h])
            n_hit +=1
 
        
        # fresh blocks for everything after that
        n_blocks = (len(tokens) // BLOCK)
 
        for i in range(n_hit, n_blocks): # i = logical block index, starting after the hits 
	        bid = self.free.pop() # grab any free physical block 
	        table.append(bid) # logical i -> physical bid
            if i < len(hashes): # only full blocks shareable
                self.cached[hashes[i]] = bid
        
        return table, n_hit * BLOCK