Semantic Caching: Beyond Exact Matches

Exact-match caching for LLM responses works for roughly 3% of real-world traffic. We measured it across the AllRoutes fleet for a month: of the requests that were eligible for caching at all (deterministic, low temperature, no tools), only 3.1% had a byte-identical previous request within the last 24 hours.

The reason is obvious once you look at production prompt distributions. Users phrase the same question fifteen different ways. RAG systems prepend slightly different context windows depending on which documents the retriever surfaced. Agent loops embed timestamps and request IDs into the prompt. None of these requests are identical, but most of them have identical answers.

Semantic caching closes that gap. Done right, it lifts cache hit rate from 3% to roughly 30% on typical traffic, with precision high enough that the cache rarely returns a wrong answer. Done wrong, it returns plausible-sounding but factually incorrect responses to questions the user did not ask. This post is about doing it right.

The two-tier design

The AllRoutes cache is two tiers, and the order matters:

1. Exact-match tier. A normalized hash of (model, messages, params) keyed in Redis with a TTL. Looks up in roughly 200 microseconds. Catches the easy 3%. Free.
2. Semantic tier. An HNSW vector index over embeddings of recent prompts, queried with cosine similarity, gated by a similarity threshold and a domain-specific judge. Catches another 25-30% of traffic. Costs an embedding call (~$0.0001) per query but the embedding cost is dwarfed by the LLM cost it saves.

The exact tier runs first because it is essentially free and removes the need to run the embedding lookup on most popular requests.

The hard part: false positives

Naive cosine similarity returns false positives constantly. "What was Q3 2024 revenue?" and "What was Q4 2024 revenue?" embed to vectors with cosine similarity around 0.97, but they are different questions with different answers. Returning the cached Q3 answer to the Q4 question is the worst possible failure mode for a cache: silent, plausible, and wrong.

We use three guards:

1. Adaptive thresholds

A single global similarity threshold does not work. The right threshold depends on the embedding model, the prompt length, and the workload. We measured optimal thresholds per workload empirically and store them in the cache config. For most workloads on text-embedding-3-large, the threshold lands between 0.94 and 0.97. Below that, false positive rate spikes. Above that, hit rate collapses.

2. Critical-token verification

The biggest source of false positives is named entities and numbers. "Tokyo" and "Toronto" embed to similar-but-not-identical vectors. "2024" and "2025" likewise. We extract critical tokens from both the candidate prompt and the cached prompt — proper nouns, numbers, dates, currency amounts, code identifiers — using a small NER pass, and require an exact set match on the critical tokens before declaring a hit.

This catches the Q3-vs-Q4 case cheaply. The NER call adds about 8ms p50 to the cache lookup, which is acceptable given the alternative is a full LLM call.

3. Optional judge pass

For high-stakes workloads (anything tagged safety: strict), we run an LLM-as-judge on the candidate hit before serving it. The judge sees both prompts and the cached response, and answers "is the cached response a correct answer to the new prompt?" Adds about 200ms and a few cents in judge tokens, but cuts false positive rate to under 0.5%.

Most callers do not need the judge tier. The first two guards alone get false-positive rate under 5% on workloads we have measured.

Architecture details

The vector index is HNSW, sharded by tenant. Each shard holds at most 500k vectors before we evict the LRU 20%. We use 1024-dimensional embeddings from text-embedding-3-large because the precision boost over the 256-dim variant is worth the storage cost — semantic cache misses are essentially free, but false positives are expensive.

# Pseudocode for the cache lookup path
def lookup(req: Request) -> Optional[Response]:
    exact = redis.get(exact_key(req))
    if exact:
        return exact

    embedding = embed(req.canonical_prompt())
    candidates = hnsw.query(embedding, k=5, tenant=req.tenant)

    for cand in candidates:
        if cand.similarity < threshold(req.workload):
            break  # candidates are sorted by similarity desc

        if not critical_tokens_match(req, cand):
            continue

        if req.workload.safety == "strict":
            if not judge_says_match(req, cand):
                continue

        return cand.response

    return None

A hit returns the cached response with a X-AllRoutes-Cache: semantic-hit header and a similarity score. Callers can opt out per-request with Cache-Control: no-cache if they need a fresh generation.

What we observed in production

After three months of running this in production across the AllRoutes fleet:

• Hit rate. Median 28% across customers, p10 12%, p90 47%. The big variance comes from workload type. RAG-heavy workloads cache poorly because retrieval surface area is huge. Customer-support and FAQ workloads cache exceptionally well.
• False positive rate. Median 1.8% as measured by post-hoc judging on a sample. This is comfortably below the bar for most use cases, including our own dogfood.
• Latency. Cache hit p50 is 12ms, p95 28ms. That includes the embedding call. A cache miss adds about 18ms to the request before the LLM call starts, which is the cost we pay for trying.
• Cost. On workloads with 25%+ hit rate, the net spend after embedding cost drops by 22-30%. Compounds nicely with cost-optimized routing.

What does not work

A few things we tried that did not pan out:

• Embedding the response too. We tried verifying hits by re-embedding the cached response and checking that it answered the new question. Too noisy. The judge tier does this better when you actually need it.
• Bloom filter pre-pass. Cute but the Redis exact-match lookup is already fast enough that the pre-pass adds latency without saving much.
• Cross-tenant cache. Privacy nightmare. We tried this for a public-knowledge subset and the engineering complexity of getting tenant isolation right was not worth the marginal hit-rate boost.

Configuring it

Semantic caching is on by default with sensible thresholds. To tune it:

client.chat.completions.create(
    model="gpt-4o",
    messages=[...],
    extra_body={
        "cache": {
            "mode": "semantic",
            "similarity_threshold": 0.95,
            "safety": "strict",  # enables the judge tier
            "ttl_seconds": 3600,
        }
    },
)

If your traffic pattern looks like a lot of paraphrased questions about the same underlying knowledge — and it probably does, more than you think — the caching docs walk through end-to-end setup.