Prefix matching in prompt caching

A prompt is assembled from blocks — a policy, a set of tool schemas, some retrieved documents, the user's turn — and topic 4.14 is about which order they go in. Two mechanisms pull on that order from opposite ends. The first is prompt caching, also called prefix caching. A provider stores the processed form of the tokens at the front of a request — the internal state the model builds while reading them — in a short-lived entry, so a later request that begins with the identical tokens skips that work: populating the entry costs around 1.25× the base input rate on the common hosted pricing shape, and reading it back costs about a tenth. It exists because production prompts repeat themselves at scale. You meet it in the usage object on every response, where cache_creation_input_tokens counts tokens written into a new entry and cache_read_input_tokens counts tokens served from one that already existed, and the cache hit rate on a dashboard is the share of input arriving by the second route. Entries idle out after a TTL, or time to live, of about five minutes on most providers, refreshed on each read.

Which tokens qualify is decided by prefix matching, and the second mechanism is position bias, which topic 1.12 measured directly: a model does not attend evenly across a long input, so a rule sitting deep inside ten thousand tokens of context is followed less reliably than the same sentence placed at the opening of the prompt or, for instructions especially, at the very end. Ordering a prompt is a decision with a price on both sides, and the two prices land on different budgets — one on an invoice, the other on whatever the model was supposed to be reliable about. This chapter is about the caching side, because it is the side that fails in a way that is neither gradual nor proportional to the change that caused it.

Cacheability is not a property of a block#

A support agent at Northwind carries 9,000 tokens of policy and tool schemas, byte-identical on every one of its 120,000 daily calls. When those 9,000 tokens moved from the front of the prompt to the bottom, behind the user's question and three retrieved knowledge-base chunks, none of them changed. The cache stopped seeing them anyway.

The intuition that makes a move like that look free is that each block in a prompt carries its own cacheability, the way each file in a build carries its own hash. The policy block is stable, so it is cacheable; the retrieved chunks are volatile, so they are not; therefore the volatile material can be moved anywhere without touching the discount on the stable material. Topic 2.15 established why that model is wrong: a prompt cache entry is keyed on a hash chain walked forward from position zero, so two requests match for as long as their serialized bytes agree and stop matching at the first token that differs. There is no mechanism that skips over a volatile region and resumes matching afterwards, because the hash of everything downstream depends on everything upstream.

The hash chain is the bookkeeping, and it is worth going one layer under it to the thing being booked, because that is where the misconception actually lives. What the entry stores is not the tokens. It is the model's internal state after having read tokens zero through i — the representation each of those positions has been given once every earlier position has been taken into account. Every position's representation therefore depends on every position before it. Change token forty and the state at token forty-one is a different state, and so is the state at every position after it, all the way to the end. So the stored state for the 9,000-token policy block is only reusable by a request whose first 9,000 tokens are the same 9,000 tokens: not the same content in a different place, and not the same content behind something else. Put a different first token in front and the state you cached was computed for a sequence that no longer exists. The chain hash is just the cheap way to check that before doing the expensive work of finding out.

That is why there is no "resume" to build. Resuming would mean holding a state computed for tokens after the divergence and reusing it behind different tokens before the divergence, and there is no such state — the one you stored already has the old prefix baked into it. The absence is not a gap somebody could close in a later release; there is nothing there to expose.

With the question at position zero, essentially no two requests in the day's traffic agree on their first token, so the match fails immediately and the 9,000 stable tokens behind the divergence point are unreachable. They are still stable. They are simply no longer part of any prefix that two requests share. The 4% residual came from duplicate submissions and a handful of canned questions that support macros send verbatim.

# before the deploy — the 9,000-token block is a shared prefix
blocks = [
    policy_and_tools,          # 9,000 tok, byte-identical on every request
    retrieved_chunks(query),   # ~1,000 tok, different on every request
    user_turn(query),          #   ~200 tok, different on every request
]

# after the deploy — the same tokens, nothing shared from position zero
blocks = [
    user_turn(query),          #   ~200 tok
    retrieved_chunks(query),   # ~1,000 tok
    policy_and_tools,          # 9,000 tok, still stable, now unreachable
]

The usage counters said it plainly, and nobody read them for six days:

before:  cache_creation=0      cache_read=9000   input=1203
after:   cache_creation=10187  cache_read=0      input=13

The write counter is the part worth pausing on. The cache did not switch itself off; it kept doing exactly what it was asked, which was to create a new entry for a prefix that would never be requested again. Every request paid the write premium on 10,187 tokens to populate an entry that expired unread.

Where the first difference lands decides what survives#

The match runs forward and halts once, so two requests share everything ahead of their first differing token and nothing behind it. The number that determines what a layout is worth is therefore the offset of the first difference rather than the count of differences or their size. One character changed at token 40 costs more than a thousand tokens rewritten at token 9,000, because the first forfeits every token that follows it and the second forfeits only itself.

Because the halt is a single point rather than a filter, the interesting cases are the ones where the first difference sits neither at position zero nor at the boundary you intended. The same company's billing assistant is one of those. Its prompt opens with 1,900 tokens of shared preamble — the product description, the response format and the refusal rules — then a two-line tenant header of the form Tenant: Fenwick Ltd (plan: enterprise, region: eu-west-1), then 7,100 tokens of policy that is byte-identical for every tenant, then the retrieved documents and the turn. The header is 22 tokens and it moved the first difference from token 9,000 to token 1,900, which put the 7,100 tokens behind it on the wrong side of the halt.

That surface serves about 2,000 tenants at roughly 60 requests a day each, spread over a ten-hour window, so a given tenant's requests arrive about ten minutes apart against a five-minute entry lifetime. The per-tenant segment is therefore written cold almost every time it is used, and the only prefix doing any work is the 1,900 tokens in front of the header.

Moving those 22 tokens down the prompt, so the tenant header sits with the retrieved documents rather than ahead of the policy, takes the surface from the second row of that table to the third — $3,230 a day down to $1,576, which is the $1,654 a day those 22 tokens were costing — and changes nothing a reader of the prompt would notice. It is worth stating what did not change to get that saving: not one token was deleted, not one was added, and the tenant header is still in the prompt and still says the same thing. The entire effect is that 7,100 tokens moved from behind the first difference to in front of it. The salvage does need a breakpoint at the new boundary — the explicit cache_control marker that tells the provider how far along the prompt the cacheable segment runs — because a provider that caches up to an explicit marker will only give you the segment you asked for; a marker left at the end of the preamble caps reuse at 1,900 tokens no matter how much invariant material follows it.

What the two orderings actually cost#

Take the common hosted pricing shape of $3 per million input tokens, a write charged at 1.25× the base rate and a read at 0.1×, and express everything in effective tokens so two layouts can be compared on one axis.

An effective token is a real token multiplied by whatever rate it was billed at, so a token read from cache at 0.1× counts as a tenth of a token and one written at 1.25× counts as one and a quarter. The point of the conversion is that a layout with a high hit rate and a layout with none can then be compared as two numbers on one axis instead of as two hit rates and two token counts.

Under the support agent's original layout, 78% of requests read the 9,000-token prefix at 0.1× and pay full rate on the 1,200-token tail. Nine thousand at a tenth is 900; the tail is charged as itself; so those requests are 900 + 1,200 = 2,100 effective tokens. The other 22% find no warm entry, so they write the prefix at 1.25×, which is 9,000 times one and a quarter, or 11,250, plus the same 1,200 tail: 12,450. Neither of those is the number you are billed on average — that comes from weighting each by how often it happens, 78% of 2,100 plus 22% of 12,450, which is 4,377 effective tokens per request. Under the reordered layout there is no shared prefix at all, so all 10,200 tokens are written at 1.25× — 12,750 effective — with a 4% sliver reading at 0.1×, giving 12,281.

Divide the second by the first and input spend went up by a factor of 2.8, and the sentence worth pausing on is that this is worse than simply turning caching off. Work out the third layout to see why. With no cache at all there is no premium and no discount, so 10,200 tokens are billed at 1.0×, which is 10,200 effective, or $3,672 a day — and 10,200 effective tokens is less than the 12,281 the reordered layout produces. The layout that produced a 4% hit rate therefore cost about $750 a day more than not caching at all, and every cent of that difference is the quarter-rate premium on entries that were written and never read. That is the specific pathology of a broken prefix. A cache that misses is not a cache that does nothing, because a miss still writes, and a write costs more than not caching — so the mechanism does not degrade gracefully towards neutral, it crosses it and keeps going. "The cache will still match on whatever stays stable" is an expensive sentence for exactly this reason: there was nothing stable left in front, so what the cache did instead was buy an entry a day's worth of times and throw all of them away.

The compliance column is real too. Instructions placed after the material they govern were followed more reliably here, which is what topic 1.12's placement probes showed on this same prompt family. Both facts hold at once, and the two goals are pulling on the same lever from opposite ends: reuse wants the invariant material at the front, and compliance wants the governing rules at the back, and there is exactly one front and one back.

The divergences nobody wrote on purpose#

The 78% is not a ceiling either, and finding out why is the same exercise applied to material that no product decision ever touched. Hit rate on that surface is an average over six application pods sharing one cache, and a per-pod breakdown showed five of them at 94% and one at 3%. The divergent pod had reloaded its tool registry during a rolling deploy and was serializing the nine schemas in a different order, which put the first difference at token 340 for every request it handled. Twenty thousand requests a day were writing entries that the other five pods could not read, and the aggregate hid it completely.

Check that the aggregate really can hide it, because this is the part that decides whether a dashboard is worth looking at. One pod in six carries a sixth of the 120,000 daily requests, which is the twenty thousand above. Five sixths of the traffic hits at 94%, one sixth hits at 3%, and five sixths of 94 plus one sixth of 3 is a little over 78 — the number on the panel. So a pod in complete failure moved the headline figure by about sixteen points, and a headline figure of 78% is exactly what a healthy surface with a little cold-start churn also looks like. Nothing about 78 says which of those two it is. The diagnostic property is not the average's value but its variance: a real hit rate is a rate every pod shares, because they are all sending the same prefix, so any spread across pods means they are not sending the same prefix and the interesting question is why.

Two more turned up in the same audit. A threshold in the policy was rendered as 0.7 on pods running one YAML library and 0.70 on pods running another, and a policy file edited on a Windows workstation carried \r\n line endings for two days after the merge. Neither is visible in a diff that a human reads, both moved the first difference under token 400, and both are the kind of thing that only ever shows up as a cache metric.

The reason those two count as differences at all is that the comparison happens on the serialized bytes, not on anything a program would call the value. 0.7 and 0.70 are the same number and they are different strings, so they tokenize differently and the match halts between them. A line ending is not part of the policy in any sense a reviewer would recognise and it is part of the byte sequence, so the same applies. Anything upstream of serialization that can produce two byte sequences from one meaning — float formatting, dictionary iteration order, locale-dependent date rendering, a trailing newline — is a mechanism for silently ending the prefix, and none of them will ever look like a bug in the prompt.

def canonical_system_block(registry, config):
    """Anything that reaches the prefix is serialized deterministically."""
    tools = [registry[name] for name in sorted(registry)]      # not dict order
    return json.dumps(
        {"tools": tools, "thresholds": {k: f"{v:.2f}" for k, v in config.items()}},
        sort_keys=True,
        separators=(",", ":"),
        ensure_ascii=True,
    ).replace("\r\n", "\n")

The general rule that falls out is that everything ahead of the breakpoint has to be produced by a function of committed data, with no dependence on process state, dict iteration order, locale, or the machine that last edited the file. That is a stronger property than "stable", and it is worth stating as a property of the assembler rather than as a habit, because the failure is silent by construction: the prompt is correct, the answers are correct, and the only symptom is a number on a billing page.

The middle is the problem, not the front#

None of this says that caching works less well at the front of a prompt. The front is the only place caching works. The conflict exists because caching requires the front, and position bias makes the front the region where a rule is least likely to survive contact with 10,000 tokens of intervening context.

Nor is there a general law that instructions must go last. The evidence that "Lost in the Middle" put on the record is about the middle: recall of a fact degrades as it moves away from either edge and recovers at both. A rule at token 200 of a 10,200-token prompt is at an edge, and on many prompts it is followed perfectly well. The support agent's 4.1% violation rate came from rules buried at token 6,800 of a 9,000-token policy — the middle of the prompt in every sense — and moving the whole block to the end fixed those rules by moving them to the other edge. That distinction matters because it opens repairs that do not require moving the block at all, which is where this topic ends up.

And it is not a problem that better cache configuration solves. There is no breakpoint, no cache tier and no TTL setting that makes a suffix reusable when the bytes in front of it differ on every request. The lever is the order of the content, which means the decision belongs to whoever assembles the prompt rather than to whoever configures the client.

Cacheability, then, is not a label you can attach to a block and carry around with it. It is a statement about where the first difference between two requests falls, and every token behind that point is charged at full rate no matter how many months it has gone unedited. A layout is cacheable or it is not; the blocks inside it have no independent standing, which is why moving one small volatile thing forward can cost more than the entire block it displaced.

That leaves the ordering question genuinely open rather than settled in favour of stable-first. The layout that survives the cost argument keeps the 9,000-token block at the front, and the next chapter asks what that costs on the other axis, because keeping it there is a decision with a price, and stating the price is what separates a chosen ordering from an inherited one.