Gen AI

Prefix Caching

Instead of recomputing the attention states for a massive system prompt every time a new user connects, compute it once, store it, and let every concurrent request share those exact same memory blocks.

Why Does This Exist?

In production AI applications, you rarely send just a user's raw question to the model. You prepend it with a massive system prompt—often containing thousands of tokens of instructions, few-shot examples, JSON schemas, or retrieved RAG documents.

If your app has 1,000 concurrent users, the standard inference pipeline will take that 2,000-token system prompt, process it through the transformer, and compute its KV cache 1,000 separate times. This burns massive amounts of GPU compute (Time to First Token latency) and duplicates the exact same data 1,000 times in GPU memory. Prefix caching intercepts this waste. It recognizes when multiple requests start with the exact same sequence of tokens, computes the KV cache for that sequence just once, and allows every request to share that identical memory.

Think of It Like This

A teacher reading the same syllabus to 50 students individually

Imagine a professor who requires every student to schedule a one-on-one meeting on the first day of class. The professor spends the first 20 minutes of every single meeting reading the exact same syllabus aloud, before finally asking the student, "Do you have any questions?"

This wastes the professor's time and energy. The optimized approach is to gather all 50 students in a lecture hall, read the syllabus out loud exactly once, and then break off into 50 parallel rooms to answer their individual questions. The lecture is the shared prefix; the individual questions are the unique user queries.

How It Actually Works

Driven by Paged Attention

Prefix caching is practically impossible if a system allocates memory in massive, contiguous chunks. It relies entirely on the architecture of paged attention.

When Request A arrives with a massive system prompt, the inference engine computes the KV cache and stores it across several physical memory blocks (e.g., blocks 10, 11, and 12). When Request B arrives a moment later with the exact same system prompt, the engine's hashing system recognizes the identical text. Instead of recomputing, the engine simply creates a block table for Request B and points its first few entries directly to physical blocks 10, 11, and 12.

Branching at the divergence point

The shared physical blocks are marked as "read-only" with a reference counter (tracking that 2 requests are using them).

Once the prompt transitions from the shared system instructions to the unique user query, the requests diverge. The engine allocates a fresh, private memory block (e.g., block 13) for Request A's unique query, and a different private block (block 14) for Request B. From that point forward, the generation loop continues normally, with each request appending data to its own private blocks while continuing to read from the shared trunk.

Tree-based hashing

To make this fast, inference engines use a Radix tree (or prefix tree) to hash and store the token sequences. When a new request arrives, the engine walks down the tree, matching token by token, until it finds the longest matching prefix that already exists in the cache. This means that even if two prompts aren't 100% identical, if they share the first 500 tokens, those 500 tokens will still be matched and shared automatically.

Show Me the Code

This script demonstrates the logical routing of prefix caching. Notice how both requests map their initial logical blocks to the exact same physical memory IDs.

1import hashlib2
3class PrefixCacheEngine:4    def __init__(self):5        # Maps a hash of a token sequence to a physical block ID6        self.block_registry: dict[str, int] = {}7        self.next_physical_block = 08        9    def hash_sequence(self, tokens: list[str]) -> str:10        return hashlib.md5("".join(tokens).encode()).hexdigest()11
12    def get_or_compute_block(self, block_tokens: list[str]) -> int:13        seq_hash = self.hash_sequence(block_tokens)14        15        if seq_hash in self.block_registry:16            print(f"CACHE HIT! Reusing Physical Block {self.block_registry[seq_hash]}")17            return self.block_registry[seq_hash]18            19        print(f"CACHE MISS. Computing and storing in Physical Block {self.next_physical_block}")20        self.block_registry[seq_hash] = self.next_physical_block21        self.next_physical_block += 122        return self.next_physical_block - 123
24engine = PrefixCacheEngine()25
26system_prompt = ["You", "are", "a", "helpful", "bot"]27
28print("--- Request A (Alice) ---")29alice_table = []30alice_table.append(engine.get_or_compute_block(system_prompt))  # Cache Miss31alice_table.append(engine.get_or_compute_block(["Hi", "there!"])) # Cache Miss32
33print("\n--- Request B (Bob) ---")34bob_table = []35bob_table.append(engine.get_or_compute_block(system_prompt))    # Cache HIT!36bob_table.append(engine.get_or_compute_block(["How", "are", "you?"])) # Cache Miss37
38print(f"\nAlice's Block Table: {alice_table}")39print(f"Bob's Block Table:   {bob_table}")40
41# -> Alice's Block Table: [0, 1]42# -> Bob's Block Table:   [0, 2]

Bob's request skipped the expensive computation for block 0, sharing it perfectly with Alice, while maintaining his own unique block 2 for his specific question.

Watch Out For

Dynamic elements destroying the prefix

Prefix matching is strictly positional, starting from the very first token. If you inject a dynamic variable—like a timestamp, a unique user ID, or a randomly sorted list of retrieved documents—at the beginning of your system prompt, the engine will see a completely different sequence of tokens starting at token 1. The cache will miss entirely. To leverage prefix caching, always put static, shared instructions at the top of your prompt, and push user-specific dynamic data to the very bottom.

Cache eviction policies

Shared physical blocks aren't kept forever; GPU memory is limited. When memory fills up, the engine will evict the least recently used blocks. If you have 50 different "personas" (50 different system prompts) and users request them randomly, the engine might constantly evict and recompute them, neutralizing the benefit. Prefix caching shines brightest when a vast majority of traffic flows through a small handful of heavy, identical prefixes.

The Quick Version

Prefix caching intercepts multiple API requests that start with the exact same text (like a system prompt).
It computes the heavy KV cache for that shared text only once, storing it in physical memory.
Using Paged Attention, it points the block tables of all concurrent requests to that single shared memory location.
This drastically reduces Time to First Token (TTFT) and saves massive amounts of GPU memory.
To benefit, developers must ensure their prompts are identical from token 0, pushing all dynamic/user-specific variables to the end of the prompt.