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)