E5.1 · LESSON 1 OF 6

Reusable prefixes

Identify reusable prompt prefixes, calculate saved prefill work and distinguish token savings from hit rates.

THE IDEA

Only an exact beginning can be reused

Many prompts start with the same material: a system prompt, a shared document, a long conversation so far. The cached keys and values of that part are identical across requests, so the server can reuse them and skip that prefill work. The condition is strict: the tokenized beginning must be identical, including template markers and anything else that affects the computation. A token's cached state depends on everything before it, so a match in the middle or at the end is useless.

prompt A (token ids) prompt B

12349

12379

cache block size2

identical start: 3 tokens (green) → reusable in whole blocks of 2: 2 tokens Only the beginning can be reused: the cached state of a token depends on everything before it.

Compare the exact token ids, including template markers: text that looks the same can tokenize differently, and the same question at the end of two different prompts reuses nothing.

Edit the two token lists. Green is the reusable beginning.

Predict first. Can two prompts share cache only because they end with the same question?

Chapter context

Prefix caching reuses compatible KV state for a repeated beginning of a prompt. A repeated suffix alone is not enough, because causal hidden states depend on the preceding context.

TRY IT YOURSELF

Part 1. Do it hands-on

Find shared starts by hand, then write prefix matching with block alignment.

prompt A (token ids) prompt B

12349

12379

cache block size2

identical start: 3 tokens (green) → reusable in whole blocks of 2: 2 tokens Only the beginning can be reused: the cached state of a token depends on everything before it.

Compare the exact token ids, including template markers: text that looks the same can tokenize differently, and the same question at the end of two different prompts reuses nothing.

shared start of A=[1,2,3,4,9], B=[1,2,3,7,9] shared start of A and C=[5,2,3,4,9] reusable tokens of 40 shared, block 16

To do: Token sequences A = [1, 2, 3, 4, 9] and B = [1, 2, 3, 7, 9]. How many tokens at the START are identical?
To do: A and C = [5, 2, 3, 4, 9] end with the same four tokens [2, 3, 4, 9]. How many start tokens can be reused?
To do: Two prompts share their first 40 tokens. Cache blocks hold 16 tokens and only whole blocks are reused. How many tokens are reusable?

Part 2. Do it in code

common_prefix_len(a, b): the number of equal tokens at the start of the two lists.
reusable_tokens(cached, new): the longest common prefix between `new` and ANY of the cached sequences (a list of lists); 0 if the cache is empty.
reusable_aligned(cached, new, block): like reusable_tokens, but only whole blocks count: round the result down to a multiple of block. block must be at least 1 (ValueError).
best_match(cached, new): the index of the cached sequence with the longest common prefix (the first one on ties), or None if nothing matches at all.

def common_prefix_len(a, b):
    pass

def reusable_tokens(cached, new):
    pass

def reusable_aligned(cached, new, block):
    pass

def best_match(cached, new):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can two prompts share cache only because they end with the same question?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

A simple saved-token estimate is

S=H\,P,

where H is the number of hits reusing P prefix tokens. If all R requests contain P prefix and U unique tokens, the baseline prompt work is $R(P+U)$ and the nominal fraction saved is $HP/[R(P+U)]$ . This models token work, not directly wall-clock speed.

Worked example

One hundred requests each contain a 500-token common prefix and a 300-token unique suffix. Eighty hits reuse the entire prefix. Saved prefill tokens are 80×500=40,000 out of 100×800=80,000 baseline tokens: 50% token work saved despite an 80% request hit rate. Cache lookup and new-output generation still take work.

Reference code

The following example uses the Python standard library and does not call a remote service.

requests,hits,prefix,unique=100,80,500,300
saved=hits*prefix
baseline=requests*(prefix+unique)
assert saved == 40000 and baseline == 80000
assert saved/baseline == .5
assert hits/requests == .8

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Textual similarity is not cache identity. A common suffix is not a common causal prefix. Hit rates need definitions and do not directly translate into end-to-end speedups.