Exact token-ID prefix matching

Every practical difficulty in getting a cache hit rate up is a consequence of what the lookup key is. It is the sequence of token IDs the tokenizer produced — integers such as [2028, 32006, 1057, ...] — and the walk that finds a match begins at the first of them. A serving engine hashes the first block of tokens, hashes the second block together with the first block's hash, and continues until it reaches a hash that is not resident; everything before that point skips prefill, everything after it is computed fresh. There is no mechanism for finding a shared span in the middle of two sequences, because the identity of block n incorporates every block before it, and a block whose content matches but whose predecessor does not is a different block.

The takeaway's claim about two 10,000-token prompts is worth working through, because it is the estimate people most often get wrong. Suppose two prompts differ somewhere in their first hundred tokens and are then identical for the next eight thousand. The walk hashes prompt A's first block and finds nothing resident under that hash, because prompt B's first block hashed differently, so it stops there. Every later block in prompt A carries prompt A's first block's hash inside its own identity, so none of them can match anything stored under prompt B either, however identical their sixteen tokens happen to be. Eight thousand tokens of genuinely shared content yield zero shared blocks.

It is fair to ask why an engine could not locate that shared span in the middle and reuse it anyway, and the answer is not that nobody has got round to it. The tensors in those blocks are not the tensors the second prompt needs. A key halfway down the shared region was computed from every token ahead of it, so if any of the first hundred differed, the stored key belongs to a different sequence, and serving it would produce a different answer while reporting a hit. Middle-span reuse is not a missing feature. It is arithmetically unavailable, and the only route around it is to make the two prompts agree from the front.

This chapter is about the gap between those integers and the string a human reads, because that gap is where hit rates are lost. A prompt is assembled from templates, serialised schemas, interpolated values and provider-supplied wrappers, and several of those can change the integers while leaving the rendered text visually identical — or leave the text entirely alone and change the integers underneath it. You will get a diagnostic that compares token IDs rather than strings, a catalogue of what typically moves the shared boundary and how far, a fingerprint to log so the boundary is observed rather than reasoned about, and the arithmetic that turns a measured shared prefix into a percentage of input cost.

The gap begins with what a tokenizer is. A model does not read characters; it reads integers drawn from a fixed vocabulary of a few tens of thousands of entries, and a tokenizer is the function that turns a string into that sequence of integers. It does not work word by word. The vocabulary is built by starting from single characters and repeatedly merging whichever pair occurs most often across a large body of text, thousands of times over, so the entries that survive are whatever fragments turned out to be frequent — whole common words, common prefixes and suffixes, and single characters for everything rare. Encoding a string means applying those learned merges in the order they were learned. The way a given word splits is therefore not a decision made per prompt but a consequence of statistics gathered once, over text you have never seen.

Two properties of that procedure cause most of what follows. Whitespace belongs to a token rather than separating one from the next, so " support" with its leading space and "support" without one are two different vocabulary entries carrying two different integers, and a stray space does not so much add a token as replace one. And the merges apply greedily to the string as it actually stands, so changing a character early can change how the characters after it group, which means one edited byte can shift the integers for a stretch of text that byte was never part of. Neither property is visible in rendered text, and both of them move the lookup key.

The mental model that fits#

The closest familiar analogue is the Docker layer cache. Layers hash on content and on the layer beneath, so a COPY . . early in a Dockerfile invalidates every RUN after it no matter how unchanged those commands are, and everyone learns to put COPY package.json before COPY . .. A prompt is a Dockerfile whose layers are 16-token blocks, and the same discipline applies for the same reason: stable things first, volatile things last, and a change anywhere invalidates everything downstream of it.

The analogy also predicts the shape of the loss correctly, which is why it is worth carrying. Nobody expects a Dockerfile to reuse a layer "partially" because most of the file is unchanged; the reuse ends at the first difference. A prompt behaves the same way and people expect it not to, which is where confidently wrong cost estimates come from.

Two places where the picture stops holding are worth marking now, because both are where somebody leaning on it will be misled. A Dockerfile's layers are declared by its author, so the boundaries sit exactly where the instructions sit, and moving a COPY line is a decision made in a file anyone can read. A prompt's blocks fall every sixteen tokens regardless of where its sentences are, so the boundary that decides your hit rate can land in the middle of a word and nobody chose it. The second break is worse. A Docker build is invalidated only by editing the file, whereas a prompt's integers can change while the string stays exactly as it was, because the tokenizer or the chat template moved underneath it. The shape of the loss transfers precisely; the idea that you can find the cause by reading your own source does not.

Diff the integers, not the strings#

Once you accept that the key is token IDs, the debugging tool follows. When two prompts should be sharing a prefix and are not, encode both and find the first index where they part.

from transformers import AutoTokenizer

tok = AutoTokenizer.from_pretrained("meta-llama/Meta-Llama-3-8B-Instruct")

def first_divergence(a: str, b: str, window: int = 3):
    ia, ib = tok.encode(a), tok.encode(b)
    n = min(len(ia), len(ib))
    i = next((k for k in range(n) if ia[k] != ib[k]), n)
    lo = max(0, i - window)
    return {
        "shared_tokens": i,
        "shared_fraction": round(i / max(len(ia), len(ib)), 4),
        "a_context": [(t, repr(tok.decode([t]))) for t in ia[lo : i + window]],
        "b_context": [(t, repr(tok.decode([t]))) for t in ib[lo : i + window]],
    }

Run it on two prompts that "look the same" and it prints the seam:

shared_tokens: 4
shared_fraction: 0.0005
a_context: [(2675,"'You'"), (527," ' are'"), (264," ' a'"), (11470," ' support'"), (8479," ' agent'")]
b_context: [(2675,"'You'"), (527," ' are'"), (264," ' a'"), (11470," ' support'"), (13307," ' assistant'")]

The repr on the decoded pieces is doing real work there. Without it, a trailing space, a non-breaking space, a \r\n where the other side has \n, and a zero-width joiner all render as nothing at all in terminal output, and you spend an hour convinced the two strings are equal because your eyes say so. With it, the space is visible as ' ' inside quotes and the argument ends.

Here is what typically moves the seam, and where it lands.

The last row is the only benign one, and the difference between it and the row above is entirely about position. A varying value at the end costs you nothing; the same value 200 tokens in costs you everything after it.

The changes that reach token zero#

Most of that table degrades the hit rate. Three entries destroy it outright, because they move the very first token, and they are worth separating because none of them originates in your prompt.

A tokenizer change rewrites the integers under an unchanged string. Vocabularies are built by fitting merge rules to a body of text, and a new release with different merges can split a word your prompt opens with into different pieces — "You are a support assistant" encoding as [2675, 527, 264, 11470, 18328] under one vocabulary and [2675, 527, 264, 1862, 18328] under another. The text you wrote did not change, the model may not even have changed, and every cached block is unreachable. This arrives through a transitive dependency bump more often than through a deliberate decision, which is exactly why the tokenizer identity belongs in the fingerprint you log rather than in a comment.

A chat template change does the same thing from the other direction. What a hosted model receives is not your system string; it is your string wrapped in the role markers and turn delimiters the model was trained on, and the template that produces that wrapper ships with the model rather than with your code. A provider adding a single token to the opening of the system turn shifts everything after it. You cannot see this in your own prompt at all, and it is one of the reasons a model revision — even one advertised as behaviour-compatible — is treated as a full cache invalidation.

An injected message is the one you control and the one most likely to be added on purpose. A safety preamble, a locale banner, an experiment header, a "you are running in the EU region" line placed above the system block: each is a small, well-intentioned addition ahead of everything stable. The mitigation is not to refuse such additions but to give them a fixed place after the stable region, and to treat "does this go before or after the breakpoint" — the marker in the request that declares where the cacheable region ends — as a required question in code review for anything that touches prompt assembly.

The unifying rule is that the prefix has an owner and a change budget. Decide which region of the prompt is allowed to vary per request, put a comment on the boundary, and route every new piece of context to the correct side of it. Teams that skip this step do not end up with a broken prompt; they end up with a prompt that is 94% stable, varies in three places spread through the first two thousand tokens, and reuses nothing.

Instrument the boundary instead of reasoning about it#

A prompt assembler can be correct in the sense its author meant and still produce a different byte sequence on each machine that runs it, which is not diagnosable by reading the code. What catches that in an afternoon is a hash of the rendered prefix, emitted with every request.

import hashlib

def prefix_fingerprint(prefix_text: str, tokenizer_name: str, model: str) -> str:
    ids = tok.encode(prefix_text)
    payload = f"{model}|{tokenizer_name}|" + ",".join(map(str, ids))
    return hashlib.sha256(payload.encode()).hexdigest()[:16]

log.info(
    "llm.request",
    extra={
        "prefix_fp": prefix_fingerprint(system_block, tok.name_or_path, MODEL),
        "prefix_tokens": len(tok.encode(system_block)),
        "cache_read_tokens": usage["cache_read_input_tokens"],
        "cache_write_tokens": usage["cache_creation_input_tokens"],
    },
)

Then graph the distinct count of prefix_fp per five-minute window. A healthy deployment shows one value, or a small number if you genuinely run several prompt variants. Anything more is a cardinality you can count and explain — the A/B flag someone added last week, the template edit that shipped in a config push, the tokenizer upgrade that arrived with a library bump. Fold the model ID and tokenizer name into the fingerprint as shown, because a prefix that is byte-identical but tokenized by a different vocabulary is a different key to the cache and should be a different key to you.

For the same reason, make the assembler byte-stable rather than trusting it to be. json.dumps(schema, sort_keys=True, separators=(",", ":")) for every serialised object, an explicitly sorted tool list, no set iteration anywhere in the path, and no locale- or timezone-dependent formatting. These are one-line changes and each of them is the difference between a hit rate of 0.8 and a hit rate of 0.07.

From reusable fraction to money saved#

Chapter 3 gave the price shape: reads at 0.1× base input, writes at 1.25× for a five-minute entry. Turning a shared-prefix measurement into a cost figure is then direct. Let P be the number of tokens in the shared prefix and S the suffix that varies per request. A steady-state hit bills 0.1·P + S where an uncached request bills P + S, so the fraction of input cost you keep is:

saved = 0.9 · P / (P + S)

The 0.9 in that numerator is where the discount lives, and it is worth deriving rather than remembering. What you save is the difference between the two bills, (P + S) − (0.1·P + S). The S term appears on both sides with the same coefficient, so it cancels — which is the arithmetic form of the fact that the suffix is billed identically whether caching is on or off. What survives the cancellation is P − 0.1·P, which is 0.9·P. Dividing that saving by the uncached bill of P + S gives the formula as written, and the two terms left in the denominator are precisely why the answer turns on the ratio of prefix to suffix rather than on the size of either one.

For an 8,000-token system block and a 60-token message, that is 0.9 × 8000/8060 = 89%. Move one thing — put a 40-token retrieved snippet before the system block instead of after — and the shared prefix drops from 8,000 to whatever precedes the snippet, which is zero, so the saving is zero. The formula has no term for "how much of the content is repeated"; it only has a term for how much of the content is repeated at the front, in order, byte for byte. A prompt with a great deal of repeated material and an unstable opening saves nothing. A prompt with a modest stable opening and wildly varying content after it saves in proportion to that opening.

Similarity, normalisation and byte-stability#

A prefix cache is not a similarity cache, and this is the belief most worth uprooting because it is intuitive, it sounds like how caches ought to work, and it produces confidently wrong estimates. Nothing compares embeddings, nothing computes an edit distance, nothing recognises that two tool schemas describe the same tools in a different order. "Similar" has no meaning to a mechanism that hashes integers in sequence from position zero. There are systems that cache on semantic similarity — they answer a new question with a stored response when the question is close enough to an old one — and they are a different technique with a different failure mode, namely returning an answer to a question the user did not ask.

It is also not normalising. No layer strips your trailing whitespace, collapses your newlines, sorts your JSON keys, or canonicalises your Unicode before hashing. If you want those properties, you implement them in the assembler; the cache will faithfully treat "Instructions:" and "Instructions: " as different worlds.

And byte-stability alone is not sufficient. An assembler can be perfectly deterministic, produce exactly one fingerprint across the whole fleet, and still deliver a hit rate of zero, because determinism says nothing about where in the prompt the varying content sits.

What a prefix cache offers, then, is narrower than it first appears and entirely predictable once stated: reuse of the longest run of leading token IDs that two requests have in common, with the identity of every block chained to the one before it. That single property generates the whole chapter — why a stray space near the top costs everything behind it, why a tokenizer bump you did not authorise can zero your hit rate, why the Docker layer discipline transfers exactly, and why the saving formula depends on the length of the common prefix rather than on the volume of repeated material.

It also explains why the most expensive prompt-assembly bug is the one that deterministically puts a varying value at the very top of every prompt. Today's date is the canonical example, and it is worth working through in full, because the same eight tokens that cost an entire cache by accident are also the only reliable way to invalidate one on purpose.