A reference librarian who has worked the desk for twenty years does not walk to the archive every time someone asks a question. When one patron asks “what year was the Treaty of Versailles signed” and, an hour later, another asks “when did they sign the Treaty of Versailles”, the librarian recognizes these are the same question wearing different words and answers the second one from memory in five seconds. A librarian with a perfect memory but no ability to recognize paraphrase treats them as unrelated lookups and makes the same twenty-minute trip twice. Every high-traffic LLM product has this exact problem, multiplied across hundreds of thousands of conversations that rephrase a much smaller number of actual questions.

A customer support copilot answering “how do I reset my password” and “I forgot my password, what do I do” is asking the underlying model to do the same reasoning work twice and paying twice for it. A code assistant that gets asked to “write a function that reverses a linked list” and, minutes later, “implement linked list reversal in Python” sends both prompts through a full forward pass on a model that costs real money per token, even though the second answer is, for all practical purposes, identical to the first. At 2 million completions a day with an average prompt of 800 tokens and a 300-token completion, a platform like this is paying for full inference on a large fraction of requests that are near-duplicates of something it already answered minutes or hours earlier.

The naive fix, an exact-match cache keyed by the literal prompt string, catches almost none of this. Two semantically identical prompts rarely share the same bytes: different capitalization, a reordered clause, a synonym, an extra “please”, and the hash changes completely, so the cache misses on exactly the traffic it exists to catch. The opposite naive fix, treating any two prompts with a high embedding similarity as interchangeable, is worse in a different way: it will happily serve a cached refund policy answer for a question about a different product’s refund policy, or a cached code snippet targeting Python 3.8 for a question that specified Python 3.12, because “close in vector space” is not the same thing as “safe to answer identically.” A cache that raises the hit rate at the cost of silently wrong answers has not saved money, it has shipped a quality regression that nobody notices until a customer complains.

The forces in tension are cost against correctness, and recall against precision. We need to solve for a similarity threshold that is tuned per use case rather than applied globally, an embedding-based lookup that can find a semantically equivalent prompt in milliseconds against millions of cached entries, a staleness policy that expires answers before the world changes underneath them, and a way to measure, in dollars, whether the cache is actually paying for the infrastructure it costs to run.

Requirements and Constraints

Functional Requirements

• Compute an embedding for every incoming prompt and use that vector, not the raw string, as the cache lookup key
• Perform a k-nearest-neighbor search against a vector index partitioned by use case to find semantically similar previously answered prompts
• Apply a similarity threshold decision engine that only returns a cached response when the best match clears a use-case-specific bar, and otherwise forwards the request to the live model
• Store the model’s response alongside the originating prompt embedding, the model name and version, and the generation parameters (temperature, top_p, max_tokens) that produced it, since a cached answer is only valid for the parameters that generated it
• Expire or invalidate cache entries based on staleness rules: a time-to-live, an explicit invalidation trigger when underlying source data changes, or a rollover when the origin model version changes
• Delegate the static, repeated portions of a prompt, system instructions, few-shot examples, tool schemas, to the LLM provider’s native prefix caching mechanism, even on a full semantic cache miss
• Continuously sample served cache hits for quality, comparing the cached response’s relevance against the new prompt, and feed low-quality samples back into threshold tuning
• Track and report cost savings attributable to the cache: hit count multiplied by the average per-request inference cost that hit avoided, net of the cache’s own infrastructure cost

Non-Functional Requirements

• Scale: 2,000,000 LLM requests/day (about 25 requests/sec sustained, up to 200 requests/sec at peak), average prompt length 800 tokens, average completion length 300 tokens, across roughly a dozen distinct use-case partitions
• Latency: a cache hit must resolve in p99 under 80ms, end to end; a cache miss must add no more than 15ms of embedding and lookup overhead on top of the live model call
• Hit rate: a blended semantic cache hit rate of 35% to 45% across all use cases, with high-repetition partitions like support macros and onboarding FAQs exceeding 70%
• Quality: fewer than 0.5% of served cache hits flagged as materially incorrect by continuous quality sampling, whether via an LLM-as-judge pass or human spot review
• Availability: 99.95% for the cache path; any failure in the embedding service, the vector index, or the decision engine must fail open to a live model call rather than block or error the request
• Cost: reduce aggregate inference spend by at least 30% at the target hit rate, after subtracting the embedding generation and vector index infrastructure cost
• Freshness: cached entries for time-sensitive use cases (pricing, inventory, live status) default to a 15-minute TTL; static-knowledge use cases (product documentation, code idioms) default to a 24-hour TTL

Constraints and Assumptions

• We are not building the LLM itself; the underlying model is treated as a metered, black-box API billed per input and output token
• We assume every application sends its prompts through a shared gateway rather than calling the model provider directly, since the cache has to sit in the request path to do anything
• We are not building the embedding model; we assume access to an off-the-shelf small embedding model, chosen for low latency over maximum retrieval quality
• We are not building an automated reinforcement-learning loop that tunes thresholds on its own; threshold tuning is a periodic, human-reviewed offline process informed by the quality sampling pipeline
• We assume prompts may contain personally identifiable information, so cache storage must support entry-level deletion for compliance requests, though a full data-retention and redaction system is out of scope for this design
• Provider-side prefix caching mechanics (how the provider stores and matches a cached prefix internally) are treated as an external capability we integrate with, not something we implement ourselves

High-Level Architecture

The system has six major components: the Cache Gateway, the Embedding Service, the Semantic Similarity Index, the Cache Decision Engine, the Response Store, and the Prefix Cache Manager, sitting in front of the Origin LLM Provider and feeding a Cost and Metrics Pipeline.

Every request from a client application arrives at the Cache Gateway, the single ingress point that every LLM call passes through before it reaches a model. The gateway hands the prompt to the Embedding Service, which converts it into a fixed-length vector, and that vector becomes the actual cache key: two prompts that mean the same thing land near each other in vector space even when their text differs completely. The gateway then queries the Semantic Similarity Index, an approximate nearest-neighbor index partitioned by use case, to retrieve the closest previously cached prompts and their similarity scores. The Cache Decision Engine evaluates those candidates against a use-case-specific threshold and either returns a cached response straight from the Response Store, a cache hit, or forwards the request to the Origin LLM Provider, a cache miss. On a miss, the Prefix Cache Manager still attaches any provider-side cached prefix (the system prompt, few-shot examples) to shave latency and cost off the live call even though the full response could not be served from cache. Every hit and miss, along with the tokens and dollars each one represents, flows into the Cost and Metrics Pipeline.

The six components divide cleanly along a fast, always-on read path (Gateway, Embedding Service, Similarity Index, Decision Engine, Response Store) and a slower write path that only runs on a miss (Origin Provider call, then a write back into the Response Store and index). That split is what keeps the cache from ever becoming slower than not having one.

Component Deep Dives

The Embedding Service

This component’s job is to turn a raw prompt into a vector such that two prompts with the same meaning end up close together, regardless of surface wording.

The tempting shortcut is to embed the entire prompt exactly as received, including boilerplate the application always prepends: a system instruction, a conversation history, formatting directions. That inflates every prompt’s vector with the same repeated signal, so two genuinely different user questions that share the same boilerplate can end up looking artificially similar, dragging false-positive matches above threshold. The Embedding Service instead extracts the semantically meaningful span of the prompt, typically the user’s actual question or instruction, before embedding it, and embeds boilerplate separately only if a use case specifically needs to distinguish “same question, different system context.”

# Embedding service: extracts the semantically meaningful span of a prompt
# and produces a fixed-length vector used as the cache lookup key
from dataclasses import dataclass
import hashlib
import re

STOP_PREFIXES = (
    "system:", "context:", "conversation history:", "instructions:",
)

@dataclass
class EmbeddingResult:
    vector: list
    prompt_hash: str
    normalized_text: str

def extract_semantic_span(raw_prompt: str) -> str:
    # Drop boilerplate lines the application always injects, keep the
    # user-authored content that actually varies between requests
    lines = raw_prompt.strip().splitlines()
    kept = [
        line for line in lines
        if not any(line.strip().lower().startswith(p) for p in STOP_PREFIXES)
    ]
    text = " ".join(kept).strip()
    # Collapse whitespace and casing differences that don't change meaning
    text = re.sub(r"\s+", " ", text).lower()
    return text

def embed_prompt(raw_prompt: str, embedding_model) -> EmbeddingResult:
    normalized = extract_semantic_span(raw_prompt)
    vector = embedding_model.encode(normalized)  # e.g. a 1536-dim vector
    prompt_hash = hashlib.sha256(normalized.encode("utf-8")).hexdigest()
    return EmbeddingResult(vector=vector, prompt_hash=prompt_hash, normalized_text=normalized)

prompt_hash is not the cache key, the vector is, but it is still useful: an exact-match fast path checks the hash first and skips the vector search entirely when two requests are byte-identical after normalization, which is common for scripted or templated traffic and is cheaper than any ANN lookup. The analogy here is a mail sorting facility that reads a postal code before doing full address matching, the coarse check resolves the easy majority of cases before the expensive one runs at all.

The Semantic Similarity Index

This component’s job is to find, in milliseconds, the handful of previously cached prompts whose vectors are closest to an incoming prompt’s vector, out of a corpus that can grow into the millions.

The natural first instinct is to run one shared index across all use cases, since it is simpler to operate. That fails for two reasons: a single global threshold cannot serve both a support FAQ partition, where correctness matters enormously and the acceptable similarity bar is high, and a casual chit-chat partition, where a looser bar is fine and a tighter one would tank the hit rate for no quality benefit. It also means a burst of traffic in one partition, a product launch flooding the code-assistant partition with near-duplicate questions, degrades lookup latency for every other partition sharing the same index. The index is instead partitioned by use case, each partition with its own embedding space, its own threshold, and its own retention policy.

# Approximate nearest-neighbor search against a per-partition HNSW index,
# using hnswlib-style semantics: fast, recall-tunable, memory-resident
import hnswlib
import numpy as np

class PartitionedSimilarityIndex:
    def __init__(self, dim: int = 1536):
        self.dim = dim
        self.indexes = {}       # partition -> hnswlib.Index
        self.entry_ids = {}     # partition -> {internal_id: cache_entry_id}

    def create_partition(self, partition: str, max_elements: int = 2_000_000):
        index = hnswlib.Index(space="cosine", dim=self.dim)
        index.init_index(max_elements=max_elements, ef_construction=200, M=16)
        index.set_ef(64)  # query-time recall/latency tradeoff
        self.indexes[partition] = index
        self.entry_ids[partition] = {}

    def add(self, partition: str, internal_id: int, vector: np.ndarray, cache_entry_id: int):
        self.indexes[partition].add_items(vector, internal_id)
        self.entry_ids[partition][internal_id] = cache_entry_id

    def search(self, partition: str, query_vector: np.ndarray, k: int = 5) -> list:
        index = self.indexes[partition]
        labels, distances = index.knn_query(query_vector, k=k)
        results = []
        for internal_id, dist in zip(labels[0], distances[0]):
            cosine_similarity = 1.0 - dist
            results.append({
                "cache_entry_id": self.entry_ids[partition][internal_id],
                "similarity": float(cosine_similarity),
            })
        return sorted(results, key=lambda r: r["similarity"], reverse=True)

M and ef_construction trade index build time and memory against recall, and ef at query time trades a few hundred microseconds of extra search against a better chance of finding the true nearest neighbor rather than a merely close one. At a few hundred thousand entries per partition, an HNSW graph answers a k-nearest-neighbor query in single-digit milliseconds, which is what makes the sub-80ms hit-path latency budget achievable at all; a linear scan comparing the query vector against every cached entry would blow that budget once a partition passes a few thousand entries.

The Cache Decision Engine

This component’s job is to look at the top candidate matches from the similarity index and decide, in a way that is both fast and defensible, whether serving a cached response is safe.

A smart engineer’s first instinct is to pick a single similarity threshold, say 0.90 cosine similarity, and apply it everywhere. This is precisely the cache hit rate versus quality tradeoff in miniature: raise the threshold and the cache becomes safer but answers fewer requests from cache, since fewer pairs of prompts clear the bar; lower it and the hit rate climbs but so does the chance of serving an answer to a question that was subtly different from the one that was actually asked. There is no single correct threshold, only a threshold appropriate to how expensive a wrong answer is for that specific use case.

# Cache decision engine: applies a per-partition similarity threshold with
# a safety margin, and never trusts a single ambiguous top match
from dataclasses import dataclass

@dataclass
class CacheDecision:
    action: str            # "hit", "miss", "ambiguous_miss"
    entry_id: int | None
    similarity: float | None
    reason: str

PARTITION_THRESHOLDS = {
    "support_faq":       {"threshold": 0.93, "margin": 0.02},
    "onboarding":        {"threshold": 0.91, "margin": 0.02},
    "code_assistant":    {"threshold": 0.97, "margin": 0.01},
    "summarization":     {"threshold": 0.88, "margin": 0.03},
    "general_chat":      {"threshold": 0.85, "margin": 0.04},
}

def decide(partition: str, candidates: list, model_params: dict, cached_params_by_entry: dict) -> CacheDecision:
    config = PARTITION_THRESHOLDS[partition]
    threshold, margin = config["threshold"], config["margin"]

    if not candidates:
        return CacheDecision("miss", None, None, "no_candidates")

    best = candidates[0]
    if best["similarity"] < threshold:
        return CacheDecision("miss", None, best["similarity"], "below_threshold")

    # Guard against a near-tie: if the top-2 candidates are within `margin`
    # of each other but point to materially different cached answers, the
    # match is ambiguous and it is safer to fall through to a live call
    if len(candidates) > 1:
        second = candidates[1]
        if (best["similarity"] - second["similarity"]) < margin:
            if cached_params_by_entry.get(best["entry_id"]) != cached_params_by_entry.get(second["entry_id"]):
                return CacheDecision("ambiguous_miss", None, best["similarity"], "top2_disagree_near_tie")

    cached_params = cached_params_by_entry.get(best["entry_id"], {})
    if cached_params.get("model") != model_params.get("model"):
        return CacheDecision("miss", None, best["similarity"], "model_version_mismatch")
    if abs(cached_params.get("temperature", 0) - model_params.get("temperature", 0)) > 0.01:
        return CacheDecision("miss", None, best["similarity"], "generation_params_mismatch")

    return CacheDecision("hit", best["entry_id"], best["similarity"], "above_threshold")

code_assistant runs at 0.97 because a single flipped keyword argument or a different target language produces code that compiles but does the wrong thing, a failure mode much more expensive than an occasional cache miss. general_chat runs at 0.85 because a slightly imperfect conversational answer is a minor annoyance, not a correctness bug, so it is worth accepting more false-positive hits to capture more of the redundant traffic. The model_version_mismatch and generation_params_mismatch checks exist because a cached response generated at temperature=0.2 under an older model version is not a valid substitute for a request asking for temperature=0.9 under the current one, even if the prompts are semantically identical.

The Response Store and Staleness Manager

This component’s job is to hold the cached response itself and to make sure a cached answer stops being served once it is no longer trustworthy.

The obvious approach, cache forever until an operator manually clears an entry, works until the first time the world changes underneath a cached answer: a pricing page updates, a product is discontinued, a policy changes, and the cache keeps confidently serving the old answer because nothing ever told it to stop. Staleness management has to be a first-class mechanism, not an afterthought, with three independent triggers: a default time-to-live per partition, an explicit invalidation signal when an upstream data source changes, and a version rollover whenever the origin model itself changes, since a response generated by a retired model version is not a valid stand-in for the current one even if the prompt is identical.

# Staleness manager: three independent expiry triggers, any one of which
# retires a cache entry regardless of the others
from datetime import datetime, timedelta, timezone

PARTITION_TTL_SECONDS = {
    "pricing":          900,      # 15 minutes, changes frequently
    "inventory_status":  900,
    "support_faq":       86400,   # 24 hours, changes rarely
    "code_assistant":    86400,
    "general_chat":      21600,   # 6 hours
}

def compute_expiry(partition: str, created_at: datetime) -> datetime:
    ttl = PARTITION_TTL_SECONDS.get(partition, 3600)
    return created_at + timedelta(seconds=ttl)

def is_expired(entry: dict, now: datetime = None) -> bool:
    now = now or datetime.now(timezone.utc)
    if entry.get("invalidated_at") is not None:
        return True
    if now >= entry["expires_at"]:
        return True
    return False

def invalidate_by_source_change(store, partition: str, affected_prompt_hashes: list):
    # Called by an upstream webhook (e.g. a pricing table update) to force
    # immediate invalidation ahead of the entry's natural TTL
    now = datetime.now(timezone.utc)
    for prompt_hash in affected_prompt_hashes:
        store.mark_invalidated(partition, prompt_hash, invalidated_at=now)

def invalidate_by_model_rollover(store, partition: str, retired_model: str):
    # Called whenever a model version is deprecated; every entry generated
    # by that model is no longer a valid stand-in for a live request
    now = datetime.now(timezone.utc)
    store.mark_invalidated_where(partition, model_name=retired_model, invalidated_at=now)

A 900-second TTL on the pricing partition accepts that an entry might serve a price that is up to fifteen minutes stale, an acceptable tradeoff for that use case, while support_faq can safely run at 24 hours because policy documentation changes on the order of days or weeks, not minutes. The explicit invalidation path exists because TTL alone cannot react to an unscheduled change, a price cut announced an hour into a 15-minute window still needs the old entries gone immediately, not merely eventually.

The Prefix Cache Manager

This component’s job is to make sure that even on a full semantic cache miss, the static, repeated portion of a prompt does not get reprocessed by the origin model from scratch every single time.

It is tempting to think semantic caching alone is sufficient, but a large fraction of every prompt in a typical application is not the user’s question at all, it is a system instruction, a set of few-shot examples, and a tool schema that are identical across thousands of requests and can run into the thousands of tokens on their own. Reprocessing that fixed prefix on every single call, even ones the semantic cache correctly identifies as novel, wastes both latency and money on tokens that never change. Prefix caching operates one layer below semantic caching: it caches the model’s internal key-value state for a shared prefix so the provider does not recompute attention over those tokens on every call, regardless of whether the rest of the prompt is new.

# Prefix cache manager: registers a stable prompt prefix with the provider's
# native prefix caching mechanism and reuses it across many distinct requests
import hashlib

SYSTEM_PREFIX = """You are a support assistant for Acme Cloud.
Follow these rules: ... (few-shot examples, tool schema, ~2400 tokens) ..."""

def prefix_hash(prefix_text: str) -> str:
    return hashlib.sha256(prefix_text.encode("utf-8")).hexdigest()

def build_request_with_prefix_cache(user_prompt: str, partition: str, client) -> dict:
    # cache_control marks the boundary: everything up to and including this
    # block is eligible for the provider's prefix cache; only the user
    # turn after it needs to be freshly attended to
    return client.messages.create(
        model="claude-sonnet-4-5",
        system=[
            {
                "type": "text",
                "text": SYSTEM_PREFIX,
                "cache_control": {"type": "ephemeral"},
            }
        ],
        messages=[{"role": "user", "content": user_prompt}],
        max_tokens=1024,
    )

def should_register_prefix(prefix_text: str, min_tokens: int = 1024) -> bool:
    # Providers typically only cache prefixes above a minimum token count,
    # caching a 40-token system prompt costs more in bookkeeping than it saves
    approx_tokens = len(prefix_text) // 4
    return approx_tokens >= min_tokens

The 1024-token floor in should_register_prefix mirrors a real constraint most providers apply: below a certain prefix length, the write-then-read overhead of maintaining a cached prefix exceeds what reprocessing those few tokens would have cost anyway. Prefix caching and semantic caching are complementary, not redundant: semantic caching decides whether the whole response can be reused, prefix caching decides whether the shared setup cost of a request that could not be reused still has to be paid in full.

Data Model

The durable state splits into use-case partition configuration, the cache entries themselves with their embeddings, the provider-side prefix registry, and a continuous quality sampling log.

-- Semantic cache schema: partitions, cache entries with vector embeddings,
-- prefix cache registry, and continuous quality sampling
CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE use_case_partitions (
    partition_id            BIGSERIAL PRIMARY KEY,
    name                      TEXT NOT NULL UNIQUE,
    embedding_model             TEXT NOT NULL,
    embedding_dims                 INTEGER NOT NULL,
    similarity_threshold               NUMERIC(4,3) NOT NULL,
    threshold_margin                       NUMERIC(4,3) NOT NULL DEFAULT 0.02,
    default_ttl_seconds                        INTEGER NOT NULL DEFAULT 86400,
    created_at                                    TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

CREATE TABLE cache_entries (
    entry_id              BIGSERIAL PRIMARY KEY,
    partition_id             BIGINT NOT NULL REFERENCES use_case_partitions(partition_id),
    prompt_hash                  CHAR(64) NOT NULL,
    prompt_embedding                 VECTOR(1536) NOT NULL,
    prompt_text                          TEXT NOT NULL,
    response_text                            TEXT NOT NULL,
    model_name                                   TEXT NOT NULL,
    model_params                                     JSONB NOT NULL,
    quality_score                                        NUMERIC(4,3),
    hit_count                                                BIGINT NOT NULL DEFAULT 0,
    created_at                                                   TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    last_hit_at                                                      TIMESTAMPTZ,
    expires_at                                                           TIMESTAMPTZ NOT NULL,
    invalidated_at                                                           TIMESTAMPTZ
);

CREATE INDEX ON cache_entries USING hnsw (prompt_embedding vector_cosine_ops)
    WHERE invalidated_at IS NULL;
CREATE INDEX ON cache_entries (partition_id, expires_at);
CREATE UNIQUE INDEX ON cache_entries (partition_id, prompt_hash) WHERE invalidated_at IS NULL;

-- Tracks which static prompt prefixes are currently warm at the provider,
-- so the gateway knows when re-registering a prefix is worthwhile
CREATE TABLE prefix_cache_registry (
    prefix_id             BIGSERIAL PRIMARY KEY,
    partition_id             BIGINT NOT NULL REFERENCES use_case_partitions(partition_id),
    prefix_hash                  CHAR(64) NOT NULL,
    token_count                      INTEGER NOT NULL,
    provider_cache_id                    TEXT,
    last_warmed_at                           TIMESTAMPTZ NOT NULL,
    expires_at                                   TIMESTAMPTZ NOT NULL,
    UNIQUE (partition_id, prefix_hash)
);

-- Continuous sample of served cache hits, reviewed for quality and used
-- to retune per-partition thresholds
CREATE TABLE quality_samples (
    sample_id              BIGSERIAL PRIMARY KEY,
    entry_id                  BIGINT NOT NULL REFERENCES cache_entries(entry_id),
    query_embedding               VECTOR(1536) NOT NULL,
    similarity_score                 NUMERIC(5,4) NOT NULL,
    judged_correct                       BOOLEAN,
    judged_by                                TEXT,
    sampled_at                                   TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

prompt_embedding is indexed with hnsw for the same reason the in-process similarity index uses HNSW: sub-linear approximate search is what keeps a lookup fast as the table grows past a few hundred thousand rows. The WHERE invalidated_at IS NULL partial index keeps expired and invalidated entries out of the hot search path entirely rather than filtering them out per query, which matters once a partition accumulates millions of historical rows most of which are no longer live candidates. Sharding follows partition_id first, since a lookup only ever searches within one use case, and each partition’s cache entries are small enough (typically a few hundred thousand to a few million rows) to stay within a single index shard without cross-partition fan-out.

Key Algorithms and Protocols

Adaptive Similarity Thresholding

A fixed threshold per partition is a reasonable starting point, but it is set once from intuition and does not react to what the quality sampling pipeline actually observes over time. Adaptive thresholding periodically recomputes each partition’s bar from labeled hit outcomes, tightening it where false-positive hits are showing up and loosening it where the cache is unnecessarily conservative.

# Recomputes a partition's similarity threshold from a window of labeled
# quality samples, finding the lowest threshold that still keeps the
# false-positive rate under a target ceiling
def recompute_threshold(samples: list, target_false_positive_rate: float = 0.005) -> float:
    # samples: [{"similarity": float, "judged_correct": bool}, ...]
    # sorted descending by similarity so we can sweep from strict to loose
    sorted_samples = sorted(samples, key=lambda s: s["similarity"], reverse=True)

    best_threshold = 1.0
    incorrect_seen = 0
    total_seen = 0
    for sample in sorted_samples:
        total_seen += 1
        if not sample["judged_correct"]:
            incorrect_seen += 1
        current_fp_rate = incorrect_seen / total_seen
        if current_fp_rate <= target_false_positive_rate:
            best_threshold = sample["similarity"]
        else:
            # Crossing the target FP rate; stop loosening further
            break
    return round(best_threshold, 3)

def apply_threshold_update(partition: str, new_threshold: float, old_threshold: float, min_samples: int, sample_count: int) -> dict:
    # Guard against noisy updates from a small sample window
    if sample_count < min_samples:
        return {"applied": False, "reason": "insufficient_samples"}
    # Guard against a single bad batch swinging the threshold too far
    max_step = 0.03
    if abs(new_threshold - old_threshold) > max_step:
        direction = 1 if new_threshold > old_threshold else -1
        new_threshold = old_threshold + (direction * max_step)
    return {"applied": True, "threshold": round(new_threshold, 3)}

Sweeping from the strictest similarity downward and stopping the moment the observed false-positive rate would exceed the target is an O(n log n) operation dominated by the initial sort, and it directly encodes the hit rate versus quality tradeoff as a single tunable knob: target_false_positive_rate set at 0.005 says explicitly “we accept roughly 1 wrong answer in 200 cache hits in exchange for whatever additional hit rate that threshold buys us.” The max_step guard exists because a threshold that swings from 0.93 to 0.80 in one update, based on one noisy batch of samples, could open the floodgates to a large volume of low-quality hits before anyone notices.

Cost Savings Attribution

A cache that nobody can prove is saving money will eventually get questioned and possibly torn out, so cost measurement has to be built in from the start rather than bolted on as a dashboard later.

# Attributes a dollar value to every cache hit, net of the cache's own
# embedding and infrastructure cost, over a reporting window
from dataclasses import dataclass

@dataclass
class CostModel:
    input_cost_per_million: float   # e.g. $3.00 per 1M input tokens
    output_cost_per_million: float  # e.g. $15.00 per 1M output tokens
    embedding_cost_per_million: float  # e.g. $0.02 per 1M embedded tokens

def avoided_cost_per_hit(avg_prompt_tokens: int, avg_completion_tokens: int, cost_model: CostModel) -> float:
    input_cost = (avg_prompt_tokens / 1_000_000) * cost_model.input_cost_per_million
    output_cost = (avg_completion_tokens / 1_000_000) * cost_model.output_cost_per_million
    return input_cost + output_cost

def net_savings_report(
    hit_count: int,
    avg_prompt_tokens: int,
    avg_completion_tokens: int,
    cost_model: CostModel,
    embedding_calls: int,
    vector_index_infra_cost: float,
) -> dict:
    gross_avoided = hit_count * avoided_cost_per_hit(avg_prompt_tokens, avg_completion_tokens, cost_model)
    embedding_spend = (embedding_calls * avg_prompt_tokens / 1_000_000) * cost_model.embedding_cost_per_million
    net_savings = gross_avoided - embedding_spend - vector_index_infra_cost
    return {
        "gross_avoided_cost": round(gross_avoided, 2),
        "embedding_spend": round(embedding_spend, 2),
        "infra_cost": round(vector_index_infra_cost, 2),
        "net_savings": round(net_savings, 2),
        "roi_multiple": round(gross_avoided / max(embedding_spend + vector_index_infra_cost, 0.01), 2),
    }

embedding_calls runs on every request, hit or miss, since the lookup has to happen before the decision is made, which is why the model subtracts embedding spend against the full request volume rather than only against hits. The roi_multiple output is the number that actually justifies the cache’s existence to anyone outside the team that built it: a cache that costs $400 a day in embedding and index infrastructure to save $4,000 a day in avoided inference calls is a 10x return, and that framing survives a budget review in a way that a raw hit-rate percentage does not.

Scaling and Performance

The system scales along three mostly independent axes: the Embedding Service, which is stateless and scales horizontally behind a load balancer since each request’s embedding computation is independent of every other; the Semantic Similarity Index, sharded by use-case partition so a burst in one partition never contends with another; and the Response Store, which is read-heavy in the same way the similarity index is, since a cache’s entire purpose is to serve far more reads than it accepts writes.

Capacity Estimation:

Given:
  - 2,000,000 requests/day, ~25 req/sec sustained, ~200 req/sec peak
  - Average prompt: 800 tokens, average completion: 300 tokens
  - Target blended hit rate: 40%
  - Embedding dimension: 1536, ~12 use-case partitions
  - Input cost: $3.00 / 1M tokens, output cost: $15.00 / 1M tokens

Without caching (baseline daily inference cost):
  Cost/request = (800/1e6 * $3.00) + (300/1e6 * $15.00) = $0.0069
  Daily cost = 2,000,000 * $0.0069 ~= $13,800/day

With a 40% cache hit rate:
  Requests served from cache: 2,000,000 * 0.40 = 800,000/day
  Gross avoided inference cost: 800,000 * $0.0069 ~= $5,520/day (~$2.0M/year)

Embedding overhead (runs on every request, hit and miss):
  Embedding calls/day: 2,000,000
  Tokens embedded/day: 2,000,000 * 800 = 1,600,000,000
  Embedding cost at $0.02/1M tokens: 1,600 * $0.02 ~= $32/day

Vector index memory footprint:
  Assume 5,000,000 cached entries resident across all partitions
  Vector storage: 5,000,000 * 1536 dims * 4 bytes ~= 30.7GB
  Plus HNSW graph overhead (~1.5x raw vectors): ~46GB total resident memory

Similarity index throughput:
  Peak lookups/sec: 200 req/sec (every request triggers one kNN search)
  A single HNSW-backed node comfortably serves 1,000-3,000 kNN queries/sec
    at this dimensionality, so 200/sec runs well within one well-provisioned
    node per partition, with headroom for the largest 2-3 partitions to be split further

Net daily savings: $5,520 (avoided inference) - $32 (embedding) - infra cost (~$150/day at this scale) ~= $5,338/day

The read-to-write ratio here is even more skewed than a typical cache, since every request triggers exactly one similarity search regardless of whether it hits or misses, while a write to the Response Store only happens on a miss. At a 40% hit rate, that is 200 reads per second against roughly 120 writes per second at peak, which is why the similarity index is provisioned for query throughput and the Response Store’s write path never becomes the bottleneck. Client-side caching of the very hottest few hundred entries, the handful of FAQ answers that get asked constantly, absorbs a meaningful share of load without touching the vector index at all.

Failure Modes and Recovery

Failure	Detection	Impact	Recovery
Embedding service outage or elevated latency	Health check and p99 latency alarm on the embedding service	Cache lookups cannot compute a query vector	Fail open: forward the request directly to the origin LLM provider, bypassing the cache entirely, until the embedding service recovers
Vector index node failure	Cluster health check, missing shard heartbeat	Lookups against the affected partition fail or time out	Fail open for that partition only; other partitions continue serving normally; rebuild the failed shard from the Response Store, which remains the source of truth
Threshold misconfigured too low after a bad adaptive update	Spike in quality-sample false-positive rate, hit rate jumping unexpectedly	Cache begins serving semantically wrong answers as confident hits	Roll back to the last known-good threshold automatically once the false-positive rate crosses a hard ceiling; adaptive updates are bounded by max_step specifically to limit blast radius
Stale entry served after an upstream data change without triggering invalidation	Quality sampling flags a factually outdated response, or a downstream customer complaint	Users receive outdated information (old price, discontinued product) presented with full confidence	Force-invalidate the affected partition immediately, shorten that partition’s TTL going forward, and audit why the source-change webhook did not fire
Model version rollover without a corresponding cache invalidation	Model name mismatch check in the decision engine, or a spike in downstream complaints about response style	New requests could be served responses generated by a retired model version	The model_version_mismatch check in the decision engine already prevents this at read time; the operational fix is ensuring the invalidation job runs automatically as part of the model deployment pipeline, not as a manual step
Hot partition overwhelms one similarity index shard	Per-partition query latency and queue depth alarms	p99 latency on that partition’s lookups breaches the 80ms SLA	Split the partition’s index across additional shards by a secondary key (e.g. tenant ID within the partition), and add client-side caching for the partition’s hottest entries

Comparison of Approaches

Approach	Latency	Complexity	Failure Mode	Best Fit
Exact-match string cache	Sub-millisecond, hash lookup only	Low	Near-zero hit rate on natural language traffic, since paraphrasing defeats it entirely	Highly templated, scripted, or API-driven traffic where the same prompt string genuinely repeats verbatim
Semantic embedding cache (this design)	Low single-digit ms for the vector search, plus embedding generation	Medium to high, requires threshold tuning and quality monitoring	A misconfigured threshold serves confidently wrong answers rather than failing loudly	Conversational and natural-language-heavy products where paraphrased duplicates are common and per-use-case tuning is feasible
Provider-side prefix caching only	Effectively free, handled inside the provider’s own infrastructure	Very low, mostly a matter of structuring prompts consistently	Only saves cost on the shared prefix; the variable part of every prompt still runs a full forward pass	Any application with a large, stable system prompt or few-shot block, as a baseline layered under any other caching strategy
Small-model routing or distillation	Full model latency for whichever model is chosen, but a smaller model is faster	High, requires training or distilling a router and monitoring quality drift	A miscalibrated router sends a request that needed the large model to a weaker one, degrading quality silently	High-volume products where a meaningful fraction of traffic is simple enough for a materially cheaper model to answer correctly
No caching, full inference on every request	Full model latency and full cost on every call	Lowest, nothing to build or operate	None specific to caching, but leaves the largest cost lever on the table	Low-volume or highly latency-insensitive workloads where the engineering cost of a cache exceeds the savings it would generate

For a conversational product at the 2-million-request-a-day scale used throughout this design, a semantic embedding cache layered on top of provider-side prefix caching is the right default. It captures savings from both genuinely redundant full requests and from the shared static portions of prompts that are not redundant, which neither approach achieves alone. Small-model routing is worth revisiting once traffic volume justifies the cost of training and maintaining a router, and it composes with semantic caching rather than replacing it, since a request the semantic cache correctly identifies as novel can still be routed to a cheaper model if it is simple enough.

Key Takeaways

• Semantic similarity is not a single global number: the right similarity threshold depends entirely on how expensive a wrong answer is for that specific use case, from 0.97 for code generation down to 0.85 for casual chat.
• The embedding is the cache key, not the prompt text: normalizing away boilerplate and dynamic values before embedding is what makes semantically identical prompts actually land close together in vector space.
• Hit rate and quality are in direct tension, and both must be measured together: a hit rate number without a corresponding quality sampling pipeline is not evidence the cache is working, it is evidence nobody has checked yet.
• Staleness needs three independent triggers, not one: a default TTL, explicit invalidation on source data changes, and invalidation on model version rollover each catch failures the other two miss.
• Cache partitioning by use case is what makes per-partition tuning possible: one partition’s traffic burst, threshold, and TTL should never affect another’s.
• Prefix caching and semantic caching solve different problems and both should always run: one decides whether a whole response can be reused, the other decides whether a request’s shared setup cost still has to be paid in full.
• Cost savings must be measured net of the cache’s own infrastructure cost: gross avoided inference spend without subtracting embedding and index costs overstates the cache’s actual value.
• A cache should always fail open: any component failure should route around the cache to a live model call, never block or error a request that would have succeeded without caching at all.

The counter-intuitive lesson is that the hardest part of this system is not finding semantically similar prompts, approximate nearest-neighbor search is a well-solved problem at this scale. It is resisting the temptation to treat “similar enough” as a fixed, universal bar, because the honest answer to “how similar is similar enough” is always “it depends what happens if you’re wrong,” and that answer is different for every use case a single caching layer ends up serving.

Frequently Asked Questions

Q: Why not just cache by an exact hash of the prompt string instead of building a whole embedding and vector search pipeline?

A: Exact-match caching catches only byte-identical prompts, and natural language traffic almost never repeats verbatim, a rephrased question, a different capitalization, or a reordered clause all produce a different hash even though the underlying question is identical. In practice an exact-match cache on conversational LLM traffic sees a hit rate close to zero, while a semantic cache on the same traffic can reach 35 to 45 percent, because it matches on meaning rather than bytes.

Q: Why not use an LLM-as-judge to verify every single cache hit before serving it, instead of relying on a similarity threshold?

A: Running a judge call on every candidate hit would add the latency and cost of a second model call to every request, which defeats the purpose of caching in the first place, the whole point is to avoid a full model round trip. Instead, the similarity threshold makes the real-time decision, and LLM-as-judge is used offline and asynchronously, on a sampled subset of served hits, to validate that the threshold is calibrated correctly and to catch drift before it becomes a widespread problem.

Q: How do you prevent the cache from serving outdated information after something changes upstream, like a price or a policy?

A: Through the staleness manager’s three triggers together: a conservative default TTL per partition, an explicit invalidation webhook that upstream systems call when source data changes, and a rollover invalidation tied to model version deprecation. The TTL alone is a safety net for changes nobody explicitly reported; the invalidation webhook is the primary mechanism for anything time-sensitive enough to matter within its TTL window.

Q: Why partition the vector index by use case instead of running one global index with metadata filtering?

A: A single global index with a filter on partition_id still means every partition’s write and query traffic contends for the same underlying index structure, so a burst in one high-traffic partition, a product launch flooding the code-assistant partition, degrades latency for every unrelated partition sharing that index. Physically separate partitions also make it straightforward to apply different thresholds, TTLs, and embedding models per use case, which a single shared index with filtering makes considerably more awkward to reason about and operate.

Q: Doesn’t storing full prompts and responses in the cache create a compliance problem if they contain personal information?

A: It can, which is why cache entries are stored with entry-level deletion support rather than being append-only and immutable the way an audit log would be. A production deployment also needs prompt redaction or tokenization for known PII patterns before storage, and a TTL short enough that data does not linger indefinitely even without an explicit deletion request, though the full redaction and retention policy design is intentionally out of scope for this system’s core caching logic.

Q: What stops the cache’s hit rate from silently degrading quality over time as more entries accumulate?

A: The adaptive thresholding algorithm and the continuous quality sampling pipeline together, not the initial threshold choice alone. Thresholds are recomputed periodically from labeled quality outcomes rather than set once and left alone, and updates are bounded by a maximum step size specifically so a single bad batch of samples cannot swing a partition’s threshold into unsafe territory before anyone notices.

Interview Questions

Q: Design the lookup path for a semantic cache that must resolve a cache hit in under 80ms end to end, including embedding generation. What would you choose for the vector index and why?

Expected depth: Discuss approximate nearest-neighbor structures like HNSW versus exact brute-force search, the latency and recall tradeoffs of ef and M parameters, partitioning the index by use case to bound blast radius and enable per-partition tuning, and why an exact-match hash check as a cheap first pass before the vector search reduces average latency for templated traffic.

Q: How would you decide the similarity threshold for a cache serving both a code-generation assistant and a casual chat product from the same platform?

Expected depth: Discuss why a single global threshold is wrong, tying the threshold to the cost of a wrong answer for each use case, the margin-based ambiguity guard for near-tied candidates, and how a continuous quality sampling and adaptive thresholding loop keeps the threshold calibrated over time rather than fixed from a one-time guess.

Q: A cache entry was generated by a model version that has since been deprecated. Walk through how your system prevents that entry from being served to a live request.

Expected depth: Discuss storing model_name and generation parameters alongside every cache entry, checking for a parameter and model match at decision time in addition to the similarity score, and the invalidation trigger that runs automatically as part of a model deployment pipeline to bulk-invalidate entries from a retired model version.

Q: How would you measure whether this caching layer is actually saving money once you account for the cost of running it?

Expected depth: Discuss computing gross avoided inference cost from hit count and average token cost, subtracting embedding generation cost which is incurred on every request regardless of hit or miss, subtracting vector index infrastructure cost, and expressing the result as a return multiple that is defensible in a cost review rather than a raw hit-rate percentage alone.

Q: The cache’s false-positive rate spikes after an automated threshold update. How would you design the system to prevent this from reaching a large share of production traffic?

Expected depth: Discuss bounding automated threshold changes with a maximum step size, requiring a minimum sample count before an update is applied, monitoring the false-positive rate from continuous quality sampling as the primary safety signal, and an automatic rollback to the last known-good threshold once the false-positive rate crosses a hard ceiling.