Semantic Caching

Three different caches

DefinitionThree tiers of caching, doing three different jobs

	Exact	Prefix (KV)	Semantic
Key	hash of the full request	the literal token prefix	embedding of the query
Stored	the response	attention keys and values	the response
Saves	the entire generation	prefill for the shared prefix	the entire generation
Lives	anywhere (Redis)	on the GPU that holds it	a vector index
Can be wrong	no	no	yes
Typical hit rate	low (1–10%)	high with shared system prompts	workload-dependent

Exact and prefix caching are transparent: a hit returns exactly what a miss would have. Semantic caching is not — it returns the answer to a different question that was judged similar enough. That single difference is why it needs a cost model and the other two do not.

Does it pay?

PropositionThe expected cost of a semantic cache

Let $h$ be the fraction of requests answered from the cache, $q$ the fraction of those that are wrong answers, $c_{\text{miss}}$ the cost of generating, $c_{\text{hit}}$ the cost of a lookup, and $C_{\text{wrong}}$ the cost of serving a wrong answer. Then

$$\E[\text{cost}] \;=\; h\bigl(c_{\text{hit}} + q\,C_{\text{wrong}}\bigr) \;+\; (1-h)\,\bigl(c_{\text{hit}} + c_{\text{miss}}\bigr),$$

and the cache is worth deploying exactly when

$$h\,c_{\text{miss}} \;>\; h\,q\,C_{\text{wrong}} + c_{\text{hit}}, \qquad\text{i.e.}\qquad q \;<\; \frac{c_{\text{miss}}}{C_{\text{wrong}}} - \frac{c_{\text{hit}}}{h\,C_{\text{wrong}}} .$$

ProofReveal

The threshold

PropositionLowering the threshold trades precision for recall monotonically

Let the cache return the nearest stored entry when its cosine similarity exceeds $\tau$. Both the hit rate $h(\tau)$ and the false-hit rate $h(\tau)\,q(\tau)$ are non-increasing in $\tau$. Hence no change of $\tau$ can reduce false hits and increase hits simultaneously: the only way to improve both is to change the embedding, not the threshold.

ProofReveal

A reference implementation

class SemanticCache:
    def __init__(self, index, embedder, threshold=0.93, ttl=3600):
        self.index, self.embed, self.tau, self.ttl = index, embedder, threshold, ttl

    def _key(self, req) -> str:
        # Everything that changes the answer must be in the namespace, not the vector.
        return hashlib.sha256(json.dumps({
            "model": req.model,
            "system": req.system,            # a different system prompt is a different cache
            "tools": sorted(t.name for t in req.tools),
            "tenant": req.tenant,            # never share across tenants
            "config": req.config_hash,
        }, sort_keys=True).encode()).hexdigest()

    async def lookup(self, req):
        if not cacheable(req):
            return None
        v = await self.embed(normalise(req.query))
        hit = await self.index.nearest(namespace=self._key(req), vector=v, k=1)
        if hit is None or hit.score < self.tau:
            return None
        if hit.age > self.ttl:
            await self.index.delete(hit.id)
            return None
        metrics.incr("semcache.hit", score=hit.score)
        return hit.payload

    async def store(self, req, response):
        if not cacheable(req) or response.stop_reason != "end_turn":
            return                            # never cache a truncated or errored generation
        v = await self.embed(normalise(req.query))
        await self.index.upsert(namespace=self._key(req), vector=v, payload=response)

What must never be cached

HeuristicWhat must never be cached

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

A request is unsafe to serve from a similarity match when any of the following hold:

• Personalised — the answer depends on who is asking ("what is my balance?"). The query text may be identical across users and the answers are not.
• Time-sensitive — the answer depends on now ("is the service up?", "what did we ship this week?"). A TTL bounds the damage but does not remove it.
• Side-effecting — the request causes a tool call that does something. Serving a cached "I've cancelled your order" without cancelling anything is a serious failure mode.
• Authorisation-dependent — the answer depends on the caller's permissions. Caching across principals leaks data upward.
• Non-deterministic by design — brainstorming, creative writing, sampling with high temperature, where returning the same answer twice defeats the purpose.

The practical form is a cacheable(req) predicate consulted before both lookup and store, with the default being not cacheable and an explicit allowlist of intents that are.

Measuring it honestly

A semantic cache needs two numbers that ordinary caches do not:

1. Hit rate — easy, a counter.
2. False-hit rate — hard, because a false hit looks exactly like a hit. Obtaining it requires deliberately sampling a small fraction of hits, generating the true answer anyway, and comparing. That shadow generation costs a few percent of the savings and is the only way to know the rate rather than assume it.

if hit is not None and random.random() < SHADOW_RATE:      # e.g. 0.02
    asyncio.create_task(shadow_compare(req, hit))          # off the response path