E5.2 · LESSON 2 OF 6

Hash-based lookup

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

THE IDEA

Finding cached blocks by hash

Systems look up cached blocks by a key. A good key for block i is a hash of the previous block's key plus the model identity plus this block's tokens. Chaining the previous key means identical tokens after a different beginning get a different key, as they should. Including the model (and any adapter or setting that changes the computed state) keeps one model's cache from being used for another. Only full blocks are hashed.

value of the first block's tokens1block size4

model:

block	tokens	key = hash(previous key, model, tokens)	same as the reference prompt?
1	1 1 1 1	cb7d17	yes
2	7 7 7 7	de3df1	yes

11 tokens → 2 full blocks; the last 3 token(s) are not hashed yet The second block holds the same tokens (7 7 7 7) in every row, but its key changes when the FIRST block or the MODEL changes. (the hash here is a small demo function; the exercise uses sha256)

Change the first block or the model: the second block keeps the same tokens, yet its key changes.

Predict first. Why include ancestry or preceding context in a block's identity?

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

Reason about block keys by hand, then build chained hashes and a hit-counting lookup.

value of the first block's tokens1block size4

model:

block	tokens	key = hash(previous key, model, tokens)	same as the reference prompt?
1	1 1 1 1	cb7d17	yes
2	7 7 7 7	de3df1	yes

full blocks in 70 tokens, block 16 same second-block key after different first blocks? leading blocks hit (match, match, differ)

To do: A 70-token prompt with blocks of 16: how many FULL blocks get a hash?
To do: Two prompts have an identical SECOND block of tokens but different first blocks. If each block's hash includes the previous block's hash, will the two second-block hashes be equal? Type yes or no
To do: The cache holds hashes of the first 3 blocks of an earlier prompt. A new prompt matches blocks 1 and 2, then differs in block 3. How many leading blocks are a hit?

Part 2. Do it in code

block_hashes(tokens, block, model="m1"): split tokens into FULL blocks only. The key of block i is sha256 of the text f"{previous_key}|{model}|{block_tokens}" where previous_key is "root" for the first block and block_tokens is the tuple of its token ids. Return the list of hex digests.
leading_hits(cache, hashes): the number of leading hashes that are in the set `cache`; stop at the first miss.
store(cache, hashes): add the hashes to the set and return how many were new.
lookup_and_store(cache, tokens, block, model="m1"): hash the prompt, count leading hits, store the rest, and return (hit_blocks, new_blocks).

import hashlib

def block_hashes(tokens, block, model="m1"):
    pass

def leading_hits(cache, hashes):
    pass

def store(cache, hashes):
    pass

def lookup_and_store(cache, tokens, block, model="m1"):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Why include ancestry or preceding context in block identity?

ABlocks never depend on earlier tokens.BIt makes the stored hash shorter.CThe same token block can produce different states after different prefixes, so identical tokens must not share a key.

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.