Prompt Caching Is a Byte-Determinism Problem: What I Learned Building a Cache-Stabilizer

The standard advice about prompt caching is correct and almost useless. Yes: put the stable stuff at the front, put the changing stuff at the end, mark the boundary, and later calls that share the prefix cost a fraction of the normal rate. Every provider's docs say this. I said it too, in an earlier version of this post.

Then I spent a few months building Headroom, a local-first context-compression layer that sits between agents and the LLM, and one piece of it — the part that keeps provider caches actually hitting — turned out to be much less about "structure your prompt" and much more about a single unglamorous property: byte-determinism. The prompt can be structured perfectly and still miss the cache on every call because one invisible token near the front keeps changing. This post is about that failure mode, and the surprisingly sharp corner I cut myself on trying to fix it.

Why the same prompt keeps missing the cache

A cache hit is a prefix match. The provider can reuse the work it did reading your prompt only up to the first token that differs from a previous call. That's the whole mechanism, and it's stricter than people expect: the match is on exact bytes, not on meaning. Two prompts that a human would call "the same" — one with today's date, one with yesterday's — share a prefix only up to the character where the date diverges. Everything after that point recomputes at full price.

So the real enemy of caching isn't length, it's variation in the wrong place. A 20,000-token system prompt that's byte-identical across a session caches beautifully. A 2,000-token one with a timestamp on line 3 caches almost nothing, because line 3 busts every token behind it. The usual suspects that sneak into the front of a prompt:

• A generated timestamp or "today is {date}" line injected into the system prompt.
• A per-session UUID, request ID, or trace ID rendered into the instructions.
• A tool list assembled from a dict that comes out in a different order each process start.
• A JSON schema whose keys serialize in insertion order, so two logically identical schemas produce different bytes.

The economics make this expensive to get wrong, and they differ per provider. Reading Headroom's own model of it: Anthropic's cache_control blocks give a 90% read discount but charge a 25% write premium and expire after five minutes of inactivity; OpenAI's automatic prefix caching is a 50% discount but needs a byte-identical prefix of at least 1,024 tokens; Google's CachedContent API is a 75% discount but only above a 32,768-token minimum. A single dynamic token at the front doesn't just cost you a little — on Anthropic it means you pay the 25% write premium on every call and never collect the 90% read discount. You are strictly worse off than if you'd never enabled caching.

The cache key is the bytes. Change one byte in the prefix and the hit rate for everything behind it drops to zero — quietly, with no error, on a bill you only read at the end of the month.

The fix I built, then deleted

The obvious move — the one I actually shipped first — is to fix the prompt for the user. Detect the dynamic content (the date, the UUID), strip it out of the system prompt, and re-append it somewhere at the tail where it won't poison the prefix. The prompt still contains the information; it just isn't in the hot zone anymore. In Headroom this component is called the CacheAligner, and the first version rewrote the system prompt exactly like that.

I removed that path. It violated an invariant I'd written down early and then briefly talked myself out of: the cache hot zone — the system prompt — must never be mutated. The irony is total. The whole point of the feature is cache stability, and the "fix" mutates the one region whose stability you're trying to protect. The moment you rewrite a cached byte you change the cache key, which drops the hit rate to zero, which is the exact disease you were treating. On top of that, silently editing someone's system prompt is a correctness landmine — you can't know that moving their date line to the tail preserves their intent.

So the CacheAligner is now detector-only. It finds volatile content, emits one warning, and changes nothing:

if all_findings:
    counts_str = ", ".join(f"{k}={v}" for k, v in sorted(counts.items()))
    msg_text = (
        f"CacheAligner: detected volatile content in system prompt "
        f"({counts_str}); cache prefix unstable. "
        "Move dynamic values out of the system prompt to recover cache hits."
    )
    warnings.append(msg_text)
    logger.warning(msg_text)

It tells you your prefix is unstable and where. It does not try to be clever on your behalf. That's a worse demo and a better tool.

Detecting "dynamic" is harder than it looks

Here's a corner I didn't expect. To warn about volatile content you have to detect it, and the tempting way is a pile of regexes: one for ISO dates, one for UUIDs, one for JWTs. I made detection use structural parsers instead of pattern strings — defer to the standard library's uuid. UUID and datetime. fromisoformat rather than trying to spell out the grammar in a regex. The reason is a real bug, not aesthetics.

A canonical UUID is 36 characters with dashes. A 32-character dashless hex string is indistinguishable from an MD5 digest — and a UUID parser that accepts the dashless form will happily classify your content hash as a "volatile UUID" and warn you about a value that's actually perfectly stable. A false positive here trains the user to ignore the warning, which is worse than staying quiet. So the check refuses the dashless form on purpose:

def _is_uuid(token: str) -> bool:
    # Accepts only the canonical 36-char form with dashes. The 32-char
    # dashless form is indistinguishable from an MD5 hex digest and would
    # misclassify hashes; we treat that case as a hex hash instead.
    if len(token) != _UUID_CANONICAL_LEN:
        return False
    if token.count("-") != 4:
        return False
    try:
        _uuid.UUID(token)
    except (ValueError, AttributeError):
        return False
    return True

The general lesson: detectors for "is this value going to change between calls" want to be conservative, because a wrong yes and a wrong no both cost you. A wrong yes cries wolf and gets muted; a wrong no lets a real cache-buster through unflagged.

What you can safely change: everything but the text

If you can't touch the system prompt, where do you actually recover determinism? In the parts of the request that carry no semantic meaning in their ordering. The Headroom proxy sorts the tools[] array alphabetically by name, recursively sorts JSON-schema keys (while preserving genuinely ordered arrays like a oneOf), and auto-places cache breakpoints. Reordering a tool list or sorting schema keys doesn't change what you're asking the model to do; it just makes two logically identical requests serialize to the same bytes, so they land on the same cache entry.

Placing the cache breakpoints correctly has its own contract, and I learned to state it bluntly in the code because I kept getting it subtly wrong. On Anthropic, a cache_control marker sitting in the system block or the tools[] block does not raise the "frozen message count" — those fields are unconditionally part of the cache hot zone already. Only a per-message content marker bumps the freeze floor (a marker at message index i freezes through i+1). The Rust that computes this leads with the rule it's protecting:

//! Headroom's compressor must **never** modify any byte that's part
//! of that prefix — doing so changes the cache key, drops the hit
//! rate to 0, and silently torches the customer's bill.
pub fn compute_frozen_count(parsed: &Value) -> usize {
    let mut highest_message_index: Option<usize> = None;
    walk_messages(parsed, &mut highest_message_index);
    walk_system(parsed);  // logging + TTL check only — never bumps floor
    walk_tools(parsed);   // logging + TTL check only — never bumps floor
    highest_message_index.map(|i| i + 1).unwrap_or(0)
}

Beyond ordering, a few hard-won constraints from wiring this into real traffic, none of which show up in the tidy "just enable caching" version:

1. Do the auto-optimization only on pay-as-you-go auth. Headroom's automatic cache_control placement and OpenAI prompt_cache_key injection are gated to PAYG mode. On OAuth/subscription auth it forwards byte-for-byte and does nothing, because touching the request there can void scope or collide with the client's own caching. "Helpfully" optimizing the wrong auth mode is how you break someone's setup.
2. Ordering rules are the customer's call, not yours. Anthropic wants 1-hour TTL markers before 5-minute ones when both appear. Headroom emits a warning on violation and forwards the request unchanged rather than rejecting it — it's their prompt, their bill, their choice.
3. Trust the code over the docs. Headroom's own wiki and cache-optimization guide still describe the old rewrite-the-prompt behavior I deleted. If you're porting an idea from a project's docs, confirm it against the shipping code; docs drift, and a cache feature that mutates the prompt is exactly the kind of thing that gets quietly reversed.

Does any of this move real numbers? Honestly, it depends entirely on the workload, and I want to be careful not to oversell it. Across Headroom's own production telemetry (its reporting, not an independent benchmark) over 50,000+ proxy sessions in early 2026, the median request saw only about 4.8% compression — lots of short turns where there's nothing to save — while heavy tool-use sessions with big stable prefixes ran 40-80%. Cache stabilization is the same shape: on a chatty agent that reuses a large system prompt and tool schema all day, keeping that prefix byte-identical is close to free money. On a workload of one-off short prompts, it's noise. Know which one you have before you count the savings.

The takeaway

Prompt caching isn't really a prompt-engineering problem, it's a determinism problem. The prefix either produces the same bytes on every call or it doesn't, and one date, one UUID, one reordered tool list at the front is enough to turn a 90% discount into a 25% penalty. The instinct to fix it by rewriting the prompt is the trap: you'd be mutating the exact region whose stability you're trying to buy. Detect the volatile content and warn. Sort the things whose order carries no meaning. Place your breakpoints by the provider's real contract, not your mental model of it. And leave the sacred bytes alone.