Mis-keyed and stale cache entries

Every other failure in this topic announces itself. A cold cache shows up as latency, a saturated pool shows up as preemptions, a byte-unstable prompt assembler shows up as a hit rate that will not rise. This one shows up as a customer complaint, days later, about an answer that was fluent and wrong. From every operational angle a mis-keyed prefix hit is a perfectly healthy request — no exception, no 500, no timeout, no degraded health check, no anomaly in latency or token counts. It is faster than a miss.

This chapter is about the two ways a key goes wrong, how to establish after the fact that a cache was implicated at all, and how to construct a key and a lifecycle log that make the next occurrence a five-minute diagnosis. It ends on invalidation, which on this kind of store is not a command you issue but an arrangement you make in advance — there is no flush endpoint, and the only lever is to change the bytes the lookup depends on.

Why this failure has no signal#

Consider what a mis-keyed hit looks like in a conventional cache. Ask Redis for order:8812 and get order 4471 back, and the object arrives with the wrong ID in it, a customer reference that does not match the session, and foreign keys that resolve to the wrong rows. Something downstream — a serializer, an authorisation check, a template that renders {{ order.id }} — trips over the inconsistency, usually within milliseconds and usually loudly. The wrong value is structurally detectable because the consumer expects a shape and the shape carries identity.

A prefix cache serves key and value tensors into the attention mechanism of a language model, and the consumer of those tensors is a system whose entire competence is producing fluent continuations of whatever context it is given. Hand it another tenant's policy and it will reason correctly and write well about that policy, with no capacity to notice which one it was supposed to be reasoning about. There is no shape to violate. The output is prose, the prose is well-formed, and the only detector that could catch it is a human who happens to know both policies. The corollary is that "we would have noticed" is not true.

It is worth walking why the output arrives coherent rather than corrupt, because "served the wrong cache entry" ordinarily implies garbage and here it does not. The tensors are not damaged. They are the correct key and value tensors for a real prefix, computed by this model at this precision, and every one of them is consistent with the others. Attention therefore behaves exactly as designed: the query for each new token scores against keys that are well-formed, produces a sensible distribution over them, and mixes values that are well-formed too. From inside the computation nothing whatever is unusual. The only defect is that the prefix those tensors encode is a different prefix from the one the request carried, and nothing in the architecture holds a representation of which prefix was supposed to be there. There is no field to compare, so there is no comparison that could fail.

The two shapes of a wrong key#

Neither of them is a bug in the cache implementation.

Both shapes arise in the same place, so it is worth saying what that place is. An engine's automatic prefix caching keys on token IDs and needs no help from anybody, but it holds blocks only for as long as its own pool allows and loses all of them when the process restarts. Teams that want reuse to outlast that build a store of their own: after a prefill they copy the key and value tensors out of device memory into host RAM or onto disk, filed under a key the application chooses, and on a later request they copy a matching entry back in instead of prefilling. That copy is where the danger enters. At the moment of writing the file, the identity of an entry stops being derived from the tokens and becomes whatever string somebody typed.

The first is a key that omits a dimension the tokens do not carry. Engine-level automatic prefix caching hashes token IDs, so two requests with identical tokens legitimately share blocks — that is the mechanism working. Trouble starts when a team builds its own prefix store on top, saving and restoring KV to host memory under an application-chosen key, and chooses something like f"{template_name}:{model}". Two tenants both using template support_v7 map to the same key, and whichever tenant filled it first supplies the resident blocks. The tenant identity was in the rendered text the template produced, but not in the key that indexed the result.

Nothing in that diagram is an error path.

The second shape is an entry that was never invalidated. A key of f"support:{template_version}" is fine until someone edits the template's wording without bumping the version — a copy fix, a tightened instruction, a tool description reworded in a config push. The new text is rendered, the old blocks are found under the unchanged key, and the model runs against instructions that were deleted last Thursday. The same shape appears with document sets: a key derived from a collection ID rather than a digest of its contents keeps serving the pre-reindex documents indefinitely.

Diagnosing one#

The first move is to establish that the cache is implicated at all, by regenerating the same request with reuse disabled and diffing the two outputs at temperature 0.

def bypass_diff(request, engine):
    cached   = engine.generate(request, temperature=0.0)
    uncached = engine.generate(request, temperature=0.0, prefix_cache=False)
    return {
        "match": cached.text == uncached.text,
        "cached_key": cached.debug["prefix_key"],
        "cached_blocks": cached.debug["blocks_reused"],
        "first_divergence": next(
            (i for i, (a, b) in enumerate(zip(cached.token_ids, uncached.token_ids))
             if a != b),
            None,
        ),
    }

Use a genuine engine-level bypass if one exists — a per-request flag, a separate pool, or simply omitting the cache_control breakpoint on a hosted API. The tempting shortcut of prepending a random salt to force a miss is worth knowing about and worth distrusting: it does force a miss, but it also changes the token IDs, so the two runs are no longer the same computation and small differences are expected rather than diagnostic. A salted run tells you the model behaves differently on a slightly different prompt, which you already knew.

When the diff shows two materially different answers, the cache is confirmed and the question becomes which entry was served and where it came from. That question is answerable only if the events were logged with the key attached:

12:04:01 cache.create  key=9f3c1a…  tenant=northwind  template=v7  tokens=8992  ttl=300s
12:04:44 cache.hit     key=9f3c1a…  tenant=northwind  reused=8992
12:09:12 cache.hit     key=9f3c1a…  tenant=northwind  reused=8992
14:20:09 cache.hit     key=9f3c1a…  tenant=contoso    reused=8992

That last line ends an investigation in one reading. The same key fingerprint served two different tenants, so the key does not separate tenants, so the key is wrong. Without the tenant field on the event, the same four lines say nothing at all and the team spends a week on prompt evaluations looking for a fabricated answer that never happened.

Building the key path so it can be audited#

The rule that produces a correct key is not "hash the prompt". It is: anything that changes what the tokens mean, or who is entitled to see them, belongs in the key — including things that do not change the tokens. Model weights, tokenizer vocabulary, and tenant boundary all satisfy that description and none of them appears in the rendered text.

from dataclasses import dataclass, asdict
import hashlib, json

@dataclass(frozen=True)
class PrefixKey:
    model_id: str            # claude-opus-5, or a local checkpoint name
    weights_digest: str      # short sha of the served weights
    kv_dtype: str            # bf16 / fp8 — different tensors, same tokens
    tokenizer_id: str        # vocabulary version
    template_id: str
    template_digest: str     # sha of the rendered template, not its name
    tool_schema_digest: str  # sha of the canonically serialised tool list
    tenant_id: str           # isolation boundary, invisible in the tokens
    token_ids_digest: str    # sha of the actual prefix token IDs

    def fingerprint(self) -> str:
        blob = json.dumps(asdict(self), sort_keys=True, separators=(",", ":"))
        return hashlib.sha256(blob.encode()).hexdigest()[:16]

Digests rather than names is the load-bearing choice. template_digest cannot go stale the way template_version can, because it is derived from the content that will actually be sent rather than from a number a human remembers to increment. The same argument applies to the tool list and to a retrieved document set: key on what the bytes are, never on what someone called them.

In its general form the difference is between a key that is computed and a key that is asserted. A digest is a function of the bytes, so it changes whenever the bytes change, and there is no state of the world in which the content has moved and the digest has not. A version number is a claim somebody made about the content at the moment they last thought about it, so it can be true and then quietly stop being true with nothing happening in between. Every mis-keyed entry in this chapter lives in that gap. A key path is safe exactly when there is no way to change what a request means without also changing the key, and a name is precisely a way to do that.

Then log the four lifecycle events — create, hit, expire, invalidate — each carrying fingerprint() and the fields that would let you reconstruct why. Retain them for longer than your TTL by a wide margin; a gap of days between cause and detection is normal here, and an entry's creation event is useless if it aged out of the log two days before anyone asked.

For the tenant case specifically, a canary closes the loop cheaply. Embed a tenant-specific marker in the cached prefix — a line reading Account reference: NW-4471 — and require the model to echo it in a structured field of every response. A mismatch between the echoed reference and the request's tenant is a hard, machine-checkable assertion on an otherwise unverifiable output, and it fires on the first bad request rather than the thousandth.

The canary works by manufacturing the one thing this failure otherwise lacks: a piece of the output whose correct value is known before the response arrives. Nothing about a policy answer can be checked automatically, because nobody wrote down what the right sentence would have been. An account reference can be, because the request already knows which tenant it belongs to. Placing that reference inside the cached region makes it part of what a wrong entry carries, so a wrong entry comes back echoing the wrong tenant's reference, and comparing two short strings settles a question that a paragraph of prose could not. The general move — add one decidable field to an output that is otherwise entirely undecidable — recurs throughout the topic on hallucination.

Invalidation is something you do, not something that happens#

There is no flush command. A hosted API exposes no way to evict an entry, and a self-hosted engine's only blunt instrument is a restart, which takes every other tenant's warm blocks with it. Invalidation in practice means arranging for the lookup to stop matching — changing the key, or changing the bytes the key is derived from.

That absence is structural rather than a gap in the API surface. An entry is not a row anybody can address; it is a set of blocks inside one process's memory pool on one machine, indexed by a hash the engine computed and never handed out. A hosted provider runs many such processes across many machines, so an eviction request would have to name an entry the caller has no identifier for, on a node the caller cannot select, in a fleet whose membership changes underneath them. The only lever available at any layer is therefore the one that decides whether a lookup matches, and that lever is the token IDs. Invalidation here has the same shape as the accident in chapter 5 because it is the same mechanism, turned around and used deliberately.

The lever is a version marker at the very front of the prefix. It is the identical mechanism to chapter 5's date line, used on purpose: a handful of tokens at position zero that make everything behind them unreachable. PROMPT-EPOCH 14 at the top of the system block, bumped by a config value, gives you a fleet-wide invalidation that takes effect on the next request with no restart and no coordination. The difference between this and the accident is entirely the change rate — once a quarter when something goes wrong, rather than once a request — and having it available turns "we think stale instructions are being served" from a several-hour investigation into a one-line change you can make while the investigation continues.

Two invalidations that people expect to be automatic are not. A model alias that moves does not change any string in your key: requesting support-model-prod before and after that alias is repointed to a new fine-tune gives byte-identical keys over genuinely different weights, and the tensors from the old model are arithmetically unrelated to what the new one would produce. Pin the revision, or resolve the alias at startup and put the resolved digest in the key. A document reindex does not change a collection name: a key built from corpus="policies" keeps matching after the underlying documents are replaced, and the model keeps answering from the version that was current at fill time. Key on a digest of the concatenated document IDs and their revisions, so the reindex changes the key as a side effect of doing its job. Names are stable across content changes, which is precisely what makes them unusable as cache keys.

Hallucination, shared blocks and the timing side channel#

This is not hallucination, and treating it as such sends the fix in exactly the wrong direction. The model did not fabricate a sixty-day policy; it read one, accurately, from a context it was given. Prompt engineering will not help, a stricter instruction will not help, and a grounding evaluation that checks answers against retrieved sources will not help if the retrieved sources are the ones that came with the wrong entry. This is an input-integrity failure with a data-plane cause, and it is fixed in the key.

The misdiagnosis is tempting for a reason worth stating, which is that every observable feature of the two failures matches. Both produce a fluent, well-formatted paragraph asserting something untrue about a policy. Both pass a response validator. Both are reported by a customer days later, and neither leaves a trace anywhere in the request path. The single distinguishing feature cannot be seen in the output at all: whether the false claim was present in the model's context or absent from it. That is exactly what the bypass diff establishes, and it is why running it before anything else is worth the ten minutes. It separates a problem fixed in a cache key from a problem fixed by supplying and checking evidence, and the two classes share no remedies at all.

It is also not an argument against sharing blocks across tenants when the tokens genuinely are identical. Two tenants sending byte-identical prompts to the same model get byte-identical K and V, and serving them the same blocks is exactly correct — nothing of either tenant's leaks, because there is nothing distinct to leak. The residual concern there is not correctness but observability: an attacker who can time requests can probe whether a particular prefix is already resident and learn that somebody on the deployment is using it, which is a genuine side channel and the reason regulated deployments partition the pool by tenant even where correctness does not require it.

That probe works because the property making a hit valuable is the same property making it observable. A hit skips prefill, prefill is most of a cold time to first token on a long prompt, and time to first token is something any client can measure to the millisecond. So somebody who can guess a candidate prefix — a competitor's system prompt, a particular customer's document set — can send it, time the first token, and read residency off the clock. Nothing was returned to them that they had not supplied themselves. What leaked is a single bit about whether somebody else on the deployment is sending the same bytes, through a channel that exists precisely because the optimisation works.

A cache key, then, is a claim about what makes two requests interchangeable, and a mis-keyed hit is that claim being false in a system with no way to notice. Because the consumer of the tensors is a language model, the wrong entry produces the one output shape nothing can validate: fluent, formatted, confident prose. The defences are all structural and all cheap relative to the incident — put every dimension that changes meaning or entitlement into the key, derive each of those dimensions from a digest rather than a name, log create, hit, expire and invalidate against the resulting fingerprint, keep the log longer than the detection lag, and carry an epoch marker you can bump when you need reachability to stop.

None of that is a reason to distrust the hit rate you measure. Once the key path is auditable, the numbers coming out of it are trustworthy — which makes it worth looking at what they actually say. They will not say 100%, they will not say anything close to it on most workloads, and the gap between the hit rate a cost model assumes and the one a service observes is where six-figure forecasts go wrong.