Skip to content
AI360XpertBeta

Prefix Caching

When every request opens with the same instructions, you should compute that opening once and reuse it. Prefix caching stores those key and value blocks a single time and shares them across requests.

Two requests share one copy of an 8-token prefix in physical blocks 10 and 11, then diverge into private blocks 12 and 13, so the prefix is computed once
Two requests share one copy of an 8-token prefix in physical blocks 10 and 11, then diverge into private blocks 12 and 13, so the prefix is computed once

Why Does This Exist?

You ship one assistant to many people at once. Every request carries the same opening: who the assistant is, how it must format answers, a couple of examples. Without sharing, each request runs prefill over that same opening and stores its own copy of the keys and values. You pay for identical work again and again, and time to first token grows because nothing new can start until prefill finishes. That is the waste this page removes.

Prefix caching computes the shared opening once, keeps one copy of its blocks, and points every request with the same opening at that copy. The requests still diverge after the opening, but the long shared part is never recomputed. That is the whole trick.

A KV cache is the file of past keys and values that lets decoding reuse work instead of replaying it; the full story is in KV cache. This page is about sharing one such file across requests. The block machinery underneath lives in paged attention, and what you should put in the shared opening lives in system prompts.

Think of It Like This

The print shop master copy

You run a print shop. Every customer wants the same 8 page safety manual plus 2 or 3 pages of their own form at the end. The slow way is to photocopy all 10 or 11 pages fresh for each person while they wait. The fast way is to run the 8 shared pages once, stack the copies by the counter, then print only each person's short tail and staple it to a shared stack. You did the long job once. Each order still leaves with a complete document.

It maps cleanly. The shared stack is the cached prefix blocks. The short tail is the private suffix block. Stapling is the block table that says your document is shared pages plus your pages.

Where it stops: paper stacks are independent once stapled. Here the shared pages stay shared live, with a count of who points at them. If the shop shreds the stack to free the counter, the next customer pays for the long job again. And if one customer rewrites page 1, nobody else can use that stack, because sharing starts at page 1 and any early change breaks the whole match.

How It Actually Works

A request is a token string. Write SS for the length of the shared opening in tokens, UU for the length of your request's unique tail, and N=S+UN = S + U for the total length. Write BB for the block size, the fixed number of token slots per block. In plain words: SS is how much you share, UU is how much is yours alone, BB is the tray size everything is stored in, and NN is the full prompt you sent.

Shared blocks, private tails

With B=4B = 4, an S=8S = 8 opening fills exactly ⌈S/B⌉=2\lceil S/B \rceil = 2 blocks. The ceiling brackets mean round up. Those two physical blocks are marked read only and given a count of how many requests point at them. Your request's block table is a small list that says logical block 0 lives in physical block 10 and logical block 1 lives in physical block 11. When a second request arrives with the same opening, its table simply lists 10 and 11 again. No copy. Two tables, one trunk.

The moment your text stops matching, the engine stops sharing. Your next logical block gets a fresh private physical block that only you can write. From there on you append normally while still reading the shared trunk. Think of it as copy on write: shared pages stay untouched and new pages are yours.

How the engine finds the match

Matching is positional and exact, from token 0. The engine keeps cached prefixes in a radix tree keyed by token ids, not by raw characters, so it can walk a new request token by token and stop at the longest prefix it has already stored. Each tree node maps to one physical block through a hash of its token slice. When memory fills, the least recently used blocks are evicted, shared or not, and the next request that needs them recomputes.

That is the trade. You spend a little bookkeeping on hashes and the tree to save a lot of prefill work and memory. It pays when a few heavy prefixes serve most of your traffic. It does not pay when every request opens differently, because then the tree rarely hits and you carry the bookkeeping for nothing. So do not use one shared cache across dozens of personas or across prompts whose retrieved documents shuffle order on each call.

The whole trick assumes the shared tokens are identical and in the same order from the very first position. If that assumption fails at position 0, nothing later can match, even if the rest looks the same to you.

Worked example: 8 shared tokens in blocks of 4

Take S=8S = 8, B=4B = 4, request A with U=3U = 3 and request B with U=2U = 2. Then N=11N = 11 for A and N=10N = 10 for B.

Blocks needed are ⌈N/B⌉\lceil N/B \rceil. For A that is ⌈11/4⌉=3\lceil 11/4 \rceil = 3. For B it is ⌈10/4⌉=3\lceil 10/4 \rceil = 3. The shared part alone needs ⌈8/4⌉=2\lceil 8/4 \rceil = 2 blocks.

Give those two blocks physical ids 10 and 11 and mark them shared with a count of 2. A's tail of 3 tokens needs one private block, id 12, which ends holding 3 tokens with 1 slot free. B's tail of 2 tokens needs one private block, id 13, holding 2 tokens with 2 slots free. The tables are A=[10,11,12]A = [10, 11, 12] and B=[10,11,13]B = [10, 11, 13], exactly as drawn above.

Prefix work without reuse is 8+8=168 + 8 = 16 token prefills. With reuse it is 88 once, so you save 88 on two requests. Scale that up: 100 requests with the same 8 token opening need 800800 prefix token prefills without sharing and 88 with it, saving 792792. The saving grows with request count while the stored prefix stays at 2 blocks.

Code

This snippet models the only data structure that matters: the table that maps each request's logical blocks to shared or private physical blocks. It uses the same numbers as the worked example.

def blocks_needed(total_tokens: int, block_size: int) -> int:    return (total_tokens + block_size - 1) // block_size

def build_table(shared: list[int], private: int) -> list[int]:    return [*shared, private]

shared_blocks: list[int] = [10, 11]alice_table = build_table(shared_blocks, 12)bob_table = build_table(shared_blocks, 13)
print(blocks_needed(11, 4))  # -> 3print(blocks_needed(10, 4))  # -> 3print(alice_table)  # -> [10, 11, 12]print(bob_table)  # -> [10, 11, 13]

Both tables point at 10 and 11 for the shared trunk and diverge only in the last entry. That shared first part is the entire saving.

Watch Out For

A changing token at the front wipes out the whole match

Your prompts look nearly identical but the hit rate sits near zero and time to first token never drops. You will swear the cache is broken. It is not.

The cause is usually one dynamic value near the front: a timestamp, a user id, or retrieved documents pasted in a fresh order each call. Because matching starts at token 0, a difference at position 1 poisons every position after it, even when positions 5 through 500 are identical.

Put static instructions first and push every dynamic value to the end. Freeze the order of examples and documents. Then verify with exact token ids, not with your eyes, that two requests truly share their first tokens.

Too many prefixes churn the cache

Hits start high in testing, then collapse under real load and latency swings from request to request. The shared blocks you counted on keep disappearing.

The cause is cardinality. Fifty personas or fifty document orders mean fifty heavy prefixes fighting for the same memory, so the least recently used policy evicts each one before it can be reused. You recompute almost as often as without the cache.

Keep the number of hot prefixes small and stable. Pin the one or two openings that serve most traffic, measure the hit rate as hits over total lookups, and do not expect a win for requests whose openings are unique by design.

The Quick Version

  • Prefix caching stores one shared opening's key and value blocks a single time and points every matching request at that copy.
  • Prefix caching matches positionally and exactly from token 0 in blocks of size B, so one early changed token breaks the whole match.
  • With 8 shared tokens and blocks of 4, two blocks are stored once while tables like [10, 11, 12] and [10, 11, 13] diverge only in the private tail.
  • Prefix caching trades a little hash and tree bookkeeping for much less prefill work and memory, and the trade pays when a few heavy prefixes serve most traffic.
  • Prefix caching rewards static text first and dynamic text last, frozen document order, and a watched hit rate, because a cold or churned cache recomputes.