A Measure-Theoretic Account of Semantic Caching: When Approximate Reuse Is Provably Safe

1 Introduction

The cheapest token is the one a system never generates. Of the several caching layers that sit between an application and a language model, the semantic cache is the one that promises the most and risks the most. It stores past prompts alongside the model responses they produced, embeds each incoming prompt, retrieves the nearest cached prompt by vector similarity, and, when the similarity clears a threshold, returns the stored response without calling the model at all ^[1]. When the incoming prompt is a genuine near-duplicate of a cached one, this is close to free money: the answer is served in milliseconds at the cost of an embedding lookup rather than a multi-second generation. The published systems report exactly this appeal, and the practitioner literature quotes production hit rates in the twenty to forty-five percent range on suitable traffic ^[5], each hit a saved generation.

The risk is structural and it is easy to miss. Every other caching layer in the stack is lossless. An exact-match prompt cache or a prefix cache returns the model output for an identical or identically-prefixed input, and a key-value cache reuses the model's own attention state; in each case the served answer is exactly what the model would have computed, so there is nothing to be wrong about ^[4]. The semantic cache is different in kind, because it substitutes a response that was computed for a different prompt. When the substitution is valid the two prompts share an answer and the reuse is invisible and correct. When it is not, the cache commits what we will call a false reuse: it serves an answer to a question the user did not ask, fluent and confident and wrong, returned with a success status and no flag anywhere in the request path. A hit-rate dashboard cannot see it, because from the dashboard's point of view a false reuse is a hit like any other; latency looks healthy and the cost graph looks better than ever while a fraction of users receive the wrong answer. Figure 1 places the false reuse in the request path.

flowchart TD
    Q[Incoming prompt q] --> EX{Exact or prefix hit?}
    EX -- yes --> LL[Lossless reuse, no error risk]
    EX -- no --> EMB[Embed q, nearest anchor a*]
    EMB --> TH{similarity s >= tau?}
    TH -- no --> GEN[Cache miss, call the model]
    TH -- yes --> SAFE{q in safe set of a*?}
    SAFE -- yes --> OK[Safe reuse, correct answer]
    SAFE -- no --> BAD[FALSE REUSE, wrong answer, 200 OK]
    GEN --> STORE[Store q and response as new anchor]

How large is the false-reuse branch in practice? The honest answer from the deployment literature is: larger than teams expect, and set by a knob they choose by feel. A widely-circulated production write-up reports a false-positive rate near one percent when the threshold is tuned to the boundary and a hit rate far below the ninety-five percent that vendor marketing implies ^[5]. A second practitioner study is blunter: to reach a hit rate above the roughly thirty percent break-even, semantic caches operate near a cosine similarity of 0.93 to 0.95, and in that band three to seven percent of cache hits return the wrong answer to the user, so that a support bot serving ten thousand queries a day at thirty percent hit rate ships on the order of ninety to two hundred wrong cached responses daily; a well-tuned cache holds the false-positive rate below two percent while an untuned one on broad chat traffic can reach ten to fifteen percent ^[6]. These two sources, gathered independently, agree on the shape of the problem: the error rate is a single-digit percentage that is real, invisible, and entirely a function of where a human set one threshold.

That last point is the gap this paper addresses. The state of the practice is a scalar dial, a global cosine threshold, turned until the hit rate looks good, with the error rate as an uncontrolled side effect that the team discovers later if at all. The most rigorous system in the published record, vCache, makes the diagnosis explicit: existing caches “use the same static similarity threshold across all requests, [and] static thresholds do not give formal correctness guarantees, result in unexpected error rates, and lead to suboptimal cache hit rates” ^[2]. vCache's response is an online-learned, per-prompt threshold with a user-specified error bound, and it reports up to 12.5 times higher cache hit and 26 times lower error than static and fine-tuned baselines, with a Pareto point at 61 percent cost savings and a false-reuse rate below 1.3 percent ^[2]. That such a system exists and works is the empirical fact this paper explains. What has been missing is the theory underneath it: a precise statement of what safety means for a semantic cache, of when reuse provably cannot change the answer, of what fundamentally limits how safe a similarity threshold can be, and of how to certify a chosen error rate with a proof rather than a hope.

We supply that theory. We treat the query stream as a probability measure on a metric space, the true answer as a partition of that space into cells within which the stored response is interchangeable, and the cache as a covering of the space by similarity balls around a finite set of anchors. In this language the reuse decision is a selective predictor in the sense of Chow's reject option ^[12], the false-reuse rate is its selective risk, and the questions a deployment cares about become theorems. We carry the derivations out.

It is worth being explicit about why the right lens is measure theory rather than, say, a classification-accuracy analysis of the matcher. A semantic cache does not classify prompts in isolation; it makes a reuse decision whose consequences are integrated over the traffic distribution, and the quantity a deployment is accountable for, the fraction of served answers that are wrong, is a measure of a set (the queries that hit and land outside a safe region) against the query distribution. Accuracy of the matcher on a balanced benchmark says little about that measure, because the measure is dominated by where the traffic actually concentrates and by the geometry of the answer boundaries the traffic crosses. Casting the problem measure-theoretically also makes the impossibility result of Section 4 expressible at all: the statement that no threshold can beat a floor is a statement about the measure of a collision set surviving into the hit set at every threshold, which has no natural expression in the language of a single confusion matrix. The move is the same one that turned selective classification from a heuristic into a theory, and the same one conformal prediction makes when it trades pointwise correctness for a controlled measure of error, and we lean on both bodies of work throughout.

The economic stakes are large enough to justify the rigor. Inference is the dominant recurring cost of a deployed language-model application, a generated answer costs a multi-second model call while a cache hit costs an embedding lookup, and at a realistic thirty percent hit rate the semantic layer removes nearly a third of generation spend. That is precisely why the layer is deployed despite its hazard, and precisely why the hazard deserves a principled treatment rather than a heuristic dial: a cost lever that a team is strongly incentivized to lean on, whose failure mode is silent and whose error rate is set by one hand-tuned number, is exactly the kind of component where an uncontrolled risk accumulates unnoticed until it surfaces as a support incident or a compliance finding. The contribution of this paper is to make the lever safe to pull as hard as its economics invite, by replacing the hand-tuned number with a calibrated, per-anchor, certified threshold and by saying exactly what that certification can and cannot promise.

A word on method and honesty. This is a paper of definitions, theorems, and analytical models, not of experiments. We ran none. Every empirical number that appears is attributed in the sentence that uses it to a published source with a working reference, and the load-bearing numbers (the production false-reuse rates, the vCache Pareto point, the PAWS collision evidence) are cross-confirmed across independent sources. Every figure that draws a curve is either an analytical model, whose assumptions its caption states, or a replot of numbers from a named study, whose caption names it. The remainder of the paper is organized as the contributions list: Section 2 sets the background, Section 3 builds the measure-theoretic model, Section 4 gives the exact-safety and impossibility results, Section 5 the separability law, Section 6 the certificate and the per-anchor result, Section 7 the economics, and Sections 8 through 11 discuss, qualify, and apply the theory.

2 Background and Related Work

2.1 A taxonomy of caching, and which layer is lossy

It is worth being precise about which caching layers carry correctness risk, because the answer is exactly one of them. An exact-match response cache keys on the literal prompt and returns a stored response only for an identical request; it is trivially correct. A prefix or prompt cache, offered by the major providers, reuses the computation over a shared prefix of the input so that a long system prompt is not reprocessed on every call; the provider guarantees the reused computation is bit-identical to recomputation, so the answer is unchanged ^[4]. A key-value cache stores the attention keys and values of tokens already processed so that autoregressive decoding does not recompute them; again the reuse is of the model's own state and is lossless. All three return what the model would have returned. The semantic cache is the sole exception: it returns a response computed for a similar but different prompt, and that substitution is the entire subject of this paper. The architectural implication, which we develop in Section 8, is that the lossless layers should be exhausted first and the lossy layer applied only to the residual traffic of near-duplicate but non-identical queries.

The correctness contracts differ in a way worth stating precisely, because it determines where a proof is even needed. Lossless reuse satisfies a strong equality: the served response equals the response the model would have produced for this exact input, so its error is identically zero by construction and no calibration or statistical bound applies or is required. Semantic reuse satisfies at best an approximate relation: the response was correct for a neighbor, and its correctness for the present query is a probabilistic event whose rate is exactly the object this paper bounds. The distinction is not academic. It says a team should never spend a statistical safety budget on the lossless layers (there is nothing to certify) and must spend one on the semantic layer (there is nothing else protecting it), and it explains why the systems that added rigor added it to the semantic layer specifically and left the lossless layers untouched ^[3], ^[2].

2.2 Semantic-cache systems and the threshold problem

GPTCache introduced the open-source template that most deployments follow: embed the prompt, search a vector store for the nearest cached prompt, optionally re-rank the top candidates with a cross-encoder, and return the stored response when an embedding-distance threshold is met ^[1]. Its design choice, a single distance threshold, is the one every later analysis returns to. MeanCache improves the matching model with federated fine-tuning and embedding compression, reporting roughly seventeen percent higher F-score and twenty percent higher precision than GPTCache along with an eighty-three percent storage reduction, and it states the operational priority plainly: precision matters more than recall, because each false hit hands the user a wrong answer and forces a re-query ^[3]. Follow-on work pushes the same lever, fine-tuning smaller domain-specific embedding models to sharpen the safe-versus-unsafe boundary ^[30]. vCache is the first system to attach a formal guarantee, replacing the global threshold with an online-learned per-prompt threshold calibrated to a user-specified error rate, and demonstrating that the static-threshold regime is not merely suboptimal but uncertifiable ^[2]. Our Sections 5 and 6 are, in effect, the analysis that says why this progression was inevitable: the quantity that binds is score separability and local geometry, and only a calibrated, per-anchor rule can control it.

Read as a sequence, the systems record traces the exact contour the theory predicts. GPTCache establishes the template and the single global threshold, the simplest approximation to Chow's rule, and pays for the simplicity with an uncontrolled error rate ^[1]. MeanCache improves the score, raising separability, and reports the gain as higher precision, which is the frontier of Section 5 moving toward the origin ^[3]. The domain-specific-embedding follow-on presses the same separability lever with fine-tuned encoders ^[30]. vCache then attacks the remaining gap, the heterogeneity of local geometry, with a per-prompt threshold and a formal error bound, which is the per-anchor certificate of Section 6 realized online ^[2]. Each step moved the lever the theory identifies as binding at that point, and none moved the generator, which the theory says is not the constraint. That the field arrived at per-anchor certification empirically, without the measure-theoretic account, speaks well of the engineering; that the account explains why nothing else could have worked is the contribution this paper adds.

2.3 Similarity is not equivalence

The premise of a semantic cache is that embedding similarity is a usable proxy for answer equivalence. The premise is sound on average and treacherous at the boundary, and the reasons are well documented. Sentence-embedding models such as Sentence-BERT are trained so that cosine similarity tracks human similarity judgments on semantic-textual-similarity data ^[7], and the MTEB benchmark shows the best models do this well across many tasks ^[8]. But “well on average” is not “faithfully at the decision boundary,” and two structural facts guarantee a gap. First, the geometry: contextual embedding spaces are strongly anisotropic. Ethayarajh measured that arbitrary word representations in models like BERT and GPT-2 have an average cosine similarity near 0.99, so the usable dynamic range of the cosine score is a thin sliver near the top rather than the full interval ^[10], a degeneration Gao and colleagues traced to the training objective driving representations into a narrow cone ^[11]. When everything is similar to everything, thresholding similarity is thresholding noise. Second, the linguistics: meaning can flip with lexical overlap near total. The PAWS dataset was built precisely to expose this, with 108,463 sentence pairs of high lexical overlap where a word swap reverses meaning (“flights from New York to Florida” versus “flights from Florida to New York”); models that scored well on ordinary paraphrase data collapsed below forty percent accuracy on PAWS before targeted training ^[9]. These near-collinear-but-not-equivalent pairs are the collisions that Section 4 shows impose a floor no threshold can escape.

The two structural facts compound rather than merely coexist, and the compounding is what makes the boundary treacherous rather than merely imperfect. Anisotropy squeezes the entire similarity distribution into a thin band near the top, so the safe and unsafe densities of Section 5 are pushed together and their overlap grows; the paraphrase collisions then populate the region of that overlap where the score is highest, which is exactly the region a threshold trusts most. The result is that the most confident reuses, the ones at cosine nearest one, are not uniformly the safest, because a fraction of them are collisions the geometry cannot separate. This inverts the intuition a threshold encodes, that higher similarity is monotonically safer, and it is the microscopic origin of the macroscopic impossibility in Section 4.3. It also explains an otherwise puzzling operational report, that the false-positive rate is worst not in the middle of the threshold range but at its boundary where similarity is just above the cutoff ^[5]: those boundary hits are disproportionately the near-collisions the score cannot resolve.

2.4 The reuse decision is a reject option

A cache that answers on a hit and defers to the model on a miss is a selective predictor. The formalism is old and clean: Chow analyzed the optimum tradeoff between error and reject rate for a classifier allowed to abstain ^[12], and the modern selective-classification literature develops the risk-coverage curve that trades the fraction of inputs answered against the error among them ^[13]. The cache miss is the reject, the false reuse is the error among the accepted, and the hit rate is the coverage. This is not an analogy we decorate the paper with; it is the object, and it lets us import the Bayes-risk and reject-tradeoff results wholesale ^[14]. What the classical theory does not supply is a finite-sample, distribution-free way to set the operating point so that the error among the accepted is provably bounded, which is where conformal methods enter.

One classical result from this literature deserves to be carried forward explicitly, because it fixes what an optimal cache would do if it knew the truth. Chow's rule says the Bayes-optimal reject option abstains exactly when the posterior probability of error on an input exceeds the cost ratio of an error to a rejection ^[12], ^[14]. Translated to a cache, the optimal policy is to reuse when the probability that the stored answer is unsafe for this query is below a cost-determined level, and to defer otherwise. This is a statement about the true conditional error, not about similarity, and it is the target that every practical rule approximates. A similarity threshold is the crude approximation that assumes the conditional error is a monotone function of a single scalar; a per-anchor threshold is a better approximation that lets the mapping from similarity to error vary by neighborhood; and a calibrated entailment-plus-similarity fusion is a better one still. Reading the whole design space as successive approximations to Chow's rule is what organizes Sections 5 through 7, and it is why the cost model of Section 7 recovers a cost-ratio threshold that echoes Chow's exactly.

2.5 Conformal prediction and risk control

Conformal prediction turns a calibration set into a distribution-free finite-sample guarantee, assuming only exchangeability ^[15], ^[16], ^[17]. The variant we need controls not coverage but the expectation of a bounded loss: risk-controlling prediction sets choose a threshold so a monotone risk is bounded with high probability ^[18], learn-then-test recasts calibration as multiple hypothesis testing over a family of candidate thresholds ^[19], and conformal risk control extends the split-conformal guarantee to any monotone bounded loss and recovers ordinary conformal prediction as a special case ^[20]. The theoretical foundations are surveyed in ^[26]. Two limits of this machinery are load-bearing for our honesty section: the guarantee is marginal, and exact conditional coverage is impossible distribution-free with finite data ^[22], ^[23]; and it rests on exchangeability, which drift breaks, repairable under known covariate shift by reweighting ^[21] and otherwise only by re-calibration ^[28]. The finite-sample slack we quote is Hoeffding's ^[24], tightened where it matters by betting-style confidence bounds ^[25]. Our contribution is not a new conformal method; it is the reduction of semantic cache safety to a risk-control problem, plus the measure-theoretic results (containment, collision floor, separability law, per-anchor optimality) that say what that risk control can and cannot buy.

3 The Reuse Model: A Measure-Theoretic Setup

We now build the object the rest of the paper reasons about. The construction is deliberately spare: a measure space of queries, a notion of when reuse is acceptable, and a cache as a covering. Everything downstream, the exact-safety condition, the impossibility, the certificate, is a property of this object.

3.1 Queries, answers, and the safe set

The safe indicator is the honest primitive. It is a judgment, human or automated, of whether one prompt's answer serves another, and Section 9 treats its fallibility as a first-class threat. In the cleanest special case there is a ground-truth answer function and $S(q,a)=1$ iff $q$ and $a$ share it; then $\sim$, defined by $q\sim a\iff S(q,a)=1$, is an equivalence relation and its classes partition $\mathcal{Q}$ into answer cells within which any stored response is interchangeable. In general $S$ need not be symmetric or transitive (a detailed answer may serve a vaguer question but not conversely), so we work with the safe sets $R_a$ directly and note where the partition picture is an idealization. Figure 2 shows the picture: answer cells tile the query space, anchors sit inside them, and a cache hit covers a similarity ball that may or may not stay within a cell.

A concrete instance grounds the abstraction. Take a customer-support assistant whose query space is the set of English support questions, with $d$ a semantic distance under which paraphrases are near and topic changes are far. The anchor “how do I reset my password” has a wide safe set: “I forgot my password, what now”, “can you help me change my password”, and dozens of rephrasings all accept the same stored answer, so $R_a$ is a large region and reuse inside it is nearly always safe. The anchor “what is my current account balance” has a safe set that is nearly a point: it is unsafe for a different account, a different date, or a different currency, even though those queries are lexically almost identical and embed close by. The two anchors live in the same cache under the same global threshold, and the entire difficulty of semantic caching is that one threshold cannot be right for both. This example is the intuition behind the per-anchor result of Section 6, and it is why the safe-set formulation, rather than a single global notion of similarity strictness, is the correct primitive.

flowchart LR
    subgraph CellA["answer cell A"]
      a1((anchor a1)) --- ballA["ball in cell: only safe reuse"]
    end
    subgraph CellB["answer cell B"]
      a2((anchor a2)) --- ballB["ball crosses boundary"]
    end
    ballB -.->|sliver outside cell| FR["false reuse mass"]
    style CellA fill:#0a0a0a,stroke:#6ab04c
    style CellB fill:#0a0a0a,stroke:#c0504d

3.2 The cache, the hit region, and the estimands

A cache is a finite set of anchors $C=\{a_1,\dots ,a_m\}$ with stored responses, together with a similarity $s:\mathcal{Q}\times \mathcal{Q}\to \mathbb{R}$ (in practice the cosine of embeddings) and a threshold $\tau$. A query $q$ is routed to its nearest anchor $a^{\ast }(q)=\arg {\max }_{a\in C}s(q,a)$, and the cache hits when $s(q,a^{\ast }(q))\ge \tau$, returning $r_{a^{\ast }(q)}$; otherwise it misses and the model is called. Three quantities describe its behavior. The hit rate is the mass that the cache answers, $H(\tau )=\mu \{q:s(q,a^{\ast }(q))\ge \tau \}$. The false-reuse rate is the probability that an answered query was answered wrongly,

where $E(\tau )$ is the unconditional served-wrong rate, the fraction of all traffic that receives a false reuse. Equation 1 is a definition, but the factorization it records is the first useful fact: the harm a cache does decomposes into how often it answers ($H$) times how often an answer is wrong ($\rho$), and a deployment can care about either factor or their product depending on whether its budget is bounded by deferrals or by wrong answers. In the selective-prediction language of Section 2.4, $\rho$ is the selective risk and $H$ the coverage; the whole paper is about controlling $\rho$ while keeping $H$ as large as the score allows.

The three quantities are worth keeping distinct because deployments confuse them and the confusion is consequential. A hit-rate dashboard reports $H$ and calls it success, but $H$ alone is maximized by never missing, which is achieved by reusing on everything, which maximizes $\rho$ too. A cost report may track the served-wrong rate $E$ and find it comfortably small even while $\rho$ is alarming, because $E=\rho H$ can be held down by a low hit rate that masks a high per-hit error. The quantity a user experiences is $\rho$, the chance that an answer they received is wrong, and it is the one a naive dashboard never shows because it is conditional on the cache having answered, which requires knowing which served answers were cache hits and whether each was safe. This is why the certificate of Section 6 targets $\rho$ specifically: it is both the user's exposure and the quantity no free telemetry reveals. A deployment that monitors only $H$ and $E$ can watch both look healthy while $\rho$ climbs, which is precisely the silent-degradation mode the introduction warned about.

3.3 Safety as containment

When does the cache commit no false reuse at all? Exactly when every hit lands in a safe set. Write the hit region of anchor $a$ as $H_a(\tau )=\{q:a^{\ast }(q)=a,s(q,a)\ge \tau \}$, the set of queries routed to $a$ that clear the threshold. Then the cache is lossless (zero false reuse) if and only if

Equation 2 is the containment condition, and it is worth reading slowly because it is the measure-theoretic heart of the paper. It says safety is not a property of similarity being high; it is a property of the hit region being subordinate to the answer structure. A very high threshold that still admits one query on the wrong side of an answer boundary is unsafe; a generous threshold whose entire ball sits in the interior of a cell is safe. This is a non-interference statement in the sense used in secure information flow: the stored answer must not be exposed to any query it does not correctly serve. It also makes clear why a single global $\tau$ is the wrong control variable, a point we prove in Section 6: containment is a local condition on each $H_a$, and different anchors need different thresholds to satisfy it.

The containment condition also clarifies what the nearest-neighbor rule buys and costs. Routing each query to its single most similar anchor makes the hit regions $H_a(\tau )$ a partition of the hit set (each query is served by exactly one anchor), which is what lets Equation 3 sum cleanly over anchors. But nearest-neighbor routing is not free of failure modes: a query can be closest to an anchor whose answer is wrong for it while a farther anchor would have been safe, a routing error distinct from a threshold error. In the safe-set language this is the event that $a^{\ast }(q)$ is unsafe though some other $a$ with $s(q,a)\ge \tau$ is safe. A cache that considered the top-$k$ anchors and re-ranked them, as GPTCache's cross-encoder stage does ^[1], can recover some of these, which is why re-ranking improves precision without changing the threshold. Our analysis treats the composed route-then-threshold map as the object $s$, folding the re-ranker into the score, so the containment and certificate results apply whether or not a re-ranker is present; the re-ranker's effect shows up as a better separability in Section 5.

3.4 The boundary-measure formula

Real caches are not lossless, so we need the size of the violation, not just its presence or absence. Summing the mass of each hit region that falls outside its safe set gives the served-wrong rate exactly:

Equation 3 localizes the harm to boundary mass: the false-reuse rate is the measure of queries that are similar enough to an anchor to be served by it yet lie across an answer boundary from it. Two consequences follow immediately and organize the next two sections. First, if the answer cells are large relative to the hit balls, the boundary mass is small and reuse is nearly free; the operative geometric quantity is the measure of a thin shell around cell boundaries, which is where the answer changes but the similarity does not. This is the deterministic story of Section 4.1. Second, the whole formula presumes the cache can see the boundary through the similarity $s$, and it cannot see it perfectly, because $s$ is an embedding surrogate for the true distance $d$. The mismatch between the ball $\{s\ge \tau \}$ and the true neighborhood $\{d\le r\}$ is what makes the boundary mass irreducible below a floor, the story of Section 4.2 and 4.3.

4 When Reuse Cannot Change the Answer

4.1 The answer-stability radius

Start with the cleanest possible guarantee, one that holds for every query rather than on average, and see exactly what it requires. Suppose the correct answer is locally constant: there is a radius $r_0>0$ such that any two queries within semantic distance $r_0$ share an answer. Formally, assume the answer function is constant on every ball of radius $r_0$. Then any hit confined to that radius of its anchor is safe, and we have a deterministic zero-error guarantee.

Equation 4 is the ideal the rest of the section measures reality against. It says that if the world has an answer-stability radius and the cache can translate that radius into a similarity threshold, reuse inside the radius is provably lossless, no calibration and no probability required. The answer-stability radius is a real and useful notion: for a factual lookup the cell around “what is the capital of France” is wide, absorbing enormous paraphrase variation, whereas around a numerical or temporal query (“revenue in Q3” versus “Q4”) it is razor-thin, which is exactly why numeric and entity-bearing prompts are where semantic caches misfire. The catch is the clause “the cache can translate that radius into a threshold.” The cache does not measure $d$; it measures $s$. The next two subsections are about the price of that substitution.

The answer-stability radius is also the cleanest way to see why some query classes are intrinsically cache-friendly and others intrinsically cache-hostile, a distinction a deployment can exploit before writing a line of calibration code. Where the answer depends on the prompt through a continuous, slowly-varying map (a definitional question, a how-to, a stable fact), the stability radius is large and the boundary mass of Equation 3 is small, so even a permissive threshold is safe and the cache pays off. Where the answer depends on a discrete or high-precision feature of the prompt (an identifier, a number, a date, a negation, a unit), the stability radius collapses toward zero because an arbitrarily small semantic change flips the answer, and no threshold short of exact match is safe. This is the same structure PAWS exploits adversarially ^[9]: word order and entity swaps are precisely the discrete features that collapse the stability radius while barely moving the embedding. The operational reading is to route high-precision query classes away from the semantic cache entirely (to the lossless layer or a fresh generation) and reserve it for the classes whose stability radius is comfortably positive, a routing decision that Sections 6 and 10 make part of the deployment recipe.

4.2 The similarity-to-equivalence gap

The embedding similarity $s$ is a surrogate for the semantic distance $d$, and a surrogate distorts. Model the distortion by two-sided (bi-Lipschitz) bounds relating embedding distance $d_e$ to semantic distance $d$ on the support of the traffic:

The distortion constant $\kappa =c_2/c_1$ is the object that matters. A threshold on $d_e$ that is guaranteed to stay within semantic radius $r_0$ must use the pessimistic side of Equation 5: to be sure $d\le r_0$ one needs $d_e\le c_1{r}_0$, so the usable safe radius in embedding space shrinks by $c_1$, and the fraction of the true safe ball the cache can actually certify shrinks like ${\kappa }^{-\dim }$. Anisotropy is exactly the regime where $\kappa$ is large. When arbitrary pairs already sit at cosine 0.99 ^[10], the score compresses genuine semantic differences into a sliver near the top of its range, so a small change in true distance maps to a tiny change in similarity and the distortion $\kappa$ is severe. The representation degeneration that produces this geometry is a property of the training objective, not of any one prompt ^[11], which is why whitening or isotropy repair, not threshold tuning, is the intervention that moves $\kappa$. Figure 3 shows the safe-versus-unsafe similarity distributions the distortion produces at a hit.

It is worth carrying the shrinkage through to a number a practitioner would feel. Suppose the true safe ball around an anchor occupies a semantic radius $r_0$ and the traffic near the anchor has local intrinsic dimension $d_{\text{loc}}$. Under the isotropic ideal ($\kappa =1$) the cache can certify the whole ball, capturing a hit mass proportional to $r_0^{d_{\text{loc}}}$. Under a distortion $\kappa$ it can only certify the inscribed embedding ball of radius $r_0/\kappa$, capturing a mass proportional to $(r_0/\kappa {)}^{d_{\text{loc}}}={\kappa }^{-d_{\text{loc}}}{r}_0^{d_{\text{loc}}}$. The certifiable hit mass therefore falls by a factor ${\kappa }^{d_{\text{loc}}}$, which is exponential in the local dimension. A distortion of $\kappa =1.5$ in a ten-dimensional local neighborhood costs a factor of $1.5^{10}\approx 58$, turning a would-be sixty percent hit rate into roughly one percent. This is the quantitative reason anisotropy is not a cosmetic nuisance but a first-order determinant of whether a semantic cache is economically viable at all, and it is why the systems literature keeps returning to better embeddings and re-rankers rather than to cleverer thresholds ^[3], ^[30].

4.3 The collision floor: an impossibility result

The distortion of Section 4.2 shrinks the safe radius but, taken alone, still permits a high-enough threshold to be safe. The genuinely fatal obstacle is different: collisions, pairs of queries that the embedding places at maximal similarity but whose answers differ. If such pairs carry positive measure, no threshold can be both safe and useful, because they survive into the hit set at every threshold. Let ${\kappa }_c$ denote the mass of unsafe pairs that remain at the very top of the similarity range and $\lambda$ the mass of safe pairs there. Then the false-reuse rate is bounded below uniformly in $\tau$:

Equation 6 is an impossibility theorem for similarity thresholding. It says that once a positive mass of non-equivalent pairs is indistinguishable from equivalent ones under the score, there is a floor on the false-reuse rate that tightening the threshold cannot cross; pushing $\tau$ to the maximum drives the hit rate to zero while the conditional error plateaus at the floor. The proof is immediate from Equation 1: as $\tau$ rises, both the safe and unsafe hit masses are dominated by their top-of-range components $\lambda$ and ${\kappa }_c$, and the ratio tends to the stated floor rather than to zero. The empirical reality of ${\kappa }_c>0$ is not in doubt: PAWS was constructed to populate exactly this corner, sentence pairs of near-total lexical overlap and opposite meaning on which similarity models scored below forty percent before targeted training ^[9], and the numeric and word-order sensitivities it probes are pervasive in real query streams. Figure 4 replots the PAWS and anisotropy numbers that make the floor concrete, and Figure 5 plots the floor itself as a function of collision mass.

The proof deserves to be spelled out because its structure is what makes the result unavoidable rather than incidental. Fix any threshold $\tau$ and split the unsafe hit mass into a resolvable part, whose similarity distribution is separated from the safe one and whose tail beyond $\tau$ vanishes as $\tau$ rises, and a collision part of mass ${\kappa }_c$ whose similarity distribution coincides with the safe one and whose tail beyond $\tau$ therefore tracks the safe tail. As $\tau \to s_{\max }$, the resolvable unsafe tail and most of the safe tail both shrink, but the collision tail and the safe tail shrink at the same rate because they share a distribution, so their ratio tends to a constant. The false-reuse rate of Equation 1 is that collision mass over the collision-plus-safe mass in the limit, which is the stated floor ${\kappa }_c/({\kappa }_c+\lambda )$. No step of the argument used the form of the safe density, only that the collisions are, by definition, indistinguishable from safe reuses under the score. The lesson is that the floor is a property of the score's inability to separate a specific set of pairs, and it can be lowered only by a different score or an additional signal, never by moving a cutoff along the same score. Figure 5 shows the floor is already material at modest collision fractions: at a five percent collision rate and a thirty percent base rate the floor sits near two percent, which is the same order as the tuned production false-reuse rates reported in the field ^[6], suggesting deployed caches are operating close to their embeddings' floors.

4.4 The two obstacles combine multiplicatively

Sections 4.2 and 4.3 name two distinct obstacles, and it is worth being explicit that they are genuinely different and combine rather than being two names for one thing. The distortion of Section 4.2 is a geometric tax: even a perfectly faithful embedding that separated every non-equivalent pair would still, if anisotropic, compress the usable range and shrink the certifiable safe ball, costing hit rate at a fixed safety target. The collision floor of Section 4.3 is an information obstacle in the strict sense: it is present whenever the embedding maps some non-equivalent pairs to indistinguishable positions, so no downstream processing of the score can recover the lost distinction, a data-processing constraint in the information-theoretic sense ^[29], and it caps the safety target itself rather than merely raising its price. A cache can suffer either without the other. An isotropic embedding with a few unavoidable collisions has no distortion tax but a positive floor; a faithful but anisotropic embedding has a distortion tax but, if it never truly collides non-equivalent pairs, a floor of zero reachable only in the limit of vanishing hit rate. Most real embeddings suffer both, and the combined effect is that the achievable safety-coverage frontier of Figure 7 both sits above zero (the floor) and is pushed away from the origin (the distortion). That is the two-fold reason a hand-tuned threshold on a raw cosine cannot be trusted to deliver a stated error rate, and the reason the constructive Sections 6 and 7 pair a certified threshold with an explicit account of what the score's geometry allows.

The distinction also predicts which interventions help which obstacle, which matters because they are not interchangeable and a team can waste effort on the wrong one. Isotropy repair (whitening, contrastive fine-tuning of the embedding, dimension standardization) attacks the distortion tax: it stretches the compressed cosine range back out so a unit of true semantic distance maps to a larger, more usable change in similarity, lowering $\kappa$ and recovering certifiable hit mass. It does little for the collision floor, because two genuinely indistinguishable pairs remain indistinguishable after a global linear stretch. Escaping the floor requires either a representation that actually separates the colliding pairs (a stronger or task-adapted encoder, or a cross-encoder that reads both prompts jointly rather than embedding them independently) or a second signal that reads the feature the embedding drops (an entailment check that notices the swapped entity, a lightweight verification that the stored answer is consistent with the new query). A team that responds to a high floor with whitening, or to a high distortion with an entailment check, will find the intervention does not move the number it was chosen to move, and the two-obstacle decomposition is what tells it which lever to pull.

5 The Separability Law and the Safety-Coverage Frontier

5.1 A two-density model of the hit

Above the collision floor, the achievable tradeoff between safety and hit rate is governed by how well the score separates safe from unsafe reuses. We make this quantitative with a two-density model. Condition on a query reaching its nearest anchor; let $p$ be the fraction of such candidate reuses that are unsafe (the base rate), and model the similarity at the hit as drawn from $f_1$ when the reuse is safe and $f_0$ when it is unsafe, with safe reuses stochastically more similar. Writing $\bar{F}$ for a right tail, the false-reuse rate at threshold $\tau$ is

Equation 7 is the false-discovery form of the selective risk: the numerator is the unsafe mass admitted, the denominator the total mass admitted. It makes the roles of the two ingredients explicit. The base rate $p$ scales the numerator, but the shape of the tradeoff, how fast $\rho$ falls as the threshold rises, is set entirely by the ratio of tails ${\bar{F}}_0/{\bar{F}}_1$, which is a property of separation, not of prevalence.

To read the law off the equation, specialize to the Gaussian instance that the figures use: safe similarity $\sim \mathcal{N}(d^{\prime },1)$ and unsafe similarity $\sim \mathcal{N}(0,1)$, so the separability $d^{\prime }$ is the standardized gap between the two means. Then ${\bar{F}}_0(\tau )=\bar{\Phi }(\tau )$ and ${\bar{F}}_1(\tau )=\bar{\Phi }(\tau -d^{\prime })$, and the false-reuse rate of Equation 7 is a logistic-like function of $\tau$ whose steepness is controlled by $d^{\prime }$. Working a representative point: at $d^{\prime }=2$, a base rate $p=0.3$, and a threshold one standard deviation above the unsafe mean, the unsafe tail is $\bar{\Phi }(1)\approx 0.159$ and the safe tail is $\bar{\Phi }(-1)\approx 0.841$, giving a false-reuse rate near $0.3\cdot 0.159/(0.3\cdot 0.159+0.7\cdot 0.841)\approx 0.075$ at a hit rate near $0.3\cdot 0.159+0.7\cdot 0.841\approx 0.64$. Push the separability to $d^{\prime }=3$ and the same seven-percent target is reached at a much higher hit rate, because the unsafe tail has moved further under the threshold while the safe tail barely moves. This is the arithmetic behind Figure 7: each unit of separability is worth more hit rate at a fixed safety target than any reduction in the base rate, and the two are not interchangeable.

5.2 Monotonicity and the frontier

For the threshold to behave, higher similarity must mean lower risk. This is exactly a monotone-likelihood-ratio (MLR) condition on the two densities.

Equation 8 is proved by differentiating Equation 7: the sign of ${\rho }^{\prime }$ is the sign of $f_1(\tau ){\bar{F}}_0(\tau )-f_0(\tau ){\bar{F}}_1(\tau )$, which is nonpositive exactly under MLR. When MLR holds, raising the threshold buys safety and costs hit rate monotonically, and the operating points $(H(\tau ),\rho (\tau ))$ trace a well-behaved frontier as $\tau$ sweeps. When it fails, and it can, if the unsafe similarity distribution is bimodal because collisions pile up at the top, raising the threshold past the collision mode can increase risk, a pathology that a global threshold sweep will not reveal and that motivates the per-anchor treatment of Section 6. Figure 6 shows $\rho$ and $H$ against the threshold under MLR, and Figure 7 the induced safety-coverage frontier for several separations.

The MLR condition is not a technical convenience; it is the precise assumption under which “raise the threshold to be safer” is sound advice, and naming it exposes exactly when the advice fails. MLR holds for the Gaussian and for most log-concave pairs where the safe distribution is a clean shift of the unsafe one, and there the false-reuse rate is a monotone decreasing function of the threshold with no local reversals, so a one-dimensional search for the threshold meeting a target is well-posed and a calibrated cutoff is the right instrument. MLR fails exactly in the collision regime of Section 4.3, where the unsafe similarity distribution inherits a second mode at the top of the range from the collisions; there the likelihood ratio $f_0/f_1$ is non-monotone, the false-reuse rate can rise as the threshold enters the collision mode, and a naive sweep can select a threshold that is worse than a lower one. The diagnostic is to plot $\rho (\tau )$ over the full range rather than assuming monotonicity, and the fix is either to remove the second mode (a better score) or to abandon the single threshold for a rule that treats the collision mode separately, which per-anchor calibration does implicitly by giving the collision-prone anchors their own, necessarily stricter, thresholds.

5.3 Why separability, not base rate, sets the cost of safety

The separability law is the practical payoff of the two-density model, and it cuts against a natural intuition. One expects that a cache on low-hallucination traffic (small $p$) is easy to make safe and a cache on messy traffic (large $p$) is hard. Equation 7 says the binding quantity is instead the separation between $f_0$ and $f_1$. Reducing the base rate rescales the frontier vertically but leaves its shape, and therefore the hit-rate cost of reaching a given target, largely intact; improving the separability $d^{\prime }$ pulls the entire frontier toward the origin, buying hit rate at every target (Figure 7). The consequence for where to invest is direct and matches the systems record: MeanCache and its successors improved caches by sharpening the matching model, the separability, rather than by touching the generator ^[3], ^[30], and vCache's gains came from learning where each anchor's boundary sits, again a separability-and-geometry move rather than a base-rate move ^[2]. The highest-leverage dollar in a semantic cache is spent on the score, not on the model behind it.

The separability law also reframes what a similarity threshold is doing. Practitioners speak of the threshold as a knob on strictness, and quote starting points like 0.8, 0.92, or 0.97 as though the number carried meaning across systems ^[6]. The two-density model says the number is meaningless in isolation: a cosine of 0.92 is highly safe under a well-separated, isotropized score and dangerously permissive under a degenerate one, because the same nominal cosine corresponds to different positions on the safe and unsafe densities. This is why a threshold tuned on one embedding does not transfer to another and why the “dangerous zone” that one practitioner study identifies between 0.88 and 0.94 ^[6] is a property of a particular embedding's geometry rather than a universal constant. The quantity that does transfer is the standardized separability $d^{\prime }$, the gap between the two densities measured in their own spread, and a discipline that reported $d^{\prime }$ alongside the threshold would let a target be set once and carried across embedding upgrades, which raw cosine cannot.

The law has a sharp corollary for how safety scales as a cache grows. As anchors accumulate, the nearest-neighbor similarity of an arbitrary query rises, because there are more anchors to be near, so the hit rate climbs; but the safe fraction among those closer matches does not rise in step, because the new anchors bring new boundaries as well as new interiors. In the two-density picture, adding anchors shifts both the safe and unsafe similarity distributions rightward together, and Equation 7 shows the false-reuse rate depends on their separation, which the shift leaves unchanged. This is why a larger cache is not automatically a safer cache at a fixed threshold, and why the common practice of growing the cache and holding the threshold constant lets the false-reuse rate drift upward as the hit rate improves, a slow degradation that reads as success on a hit-rate dashboard. The certificate must be re-checked as the cache grows, not only as the traffic drifts, and the per-anchor rule of Section 6 handles this gracefully because each new anchor arrives with its own calibrated threshold rather than inheriting a global one tuned for a smaller cache.

5.4 Reading the frontier for a target

The frontier of Figure 7 is not only a diagnostic; it is the object a team reads to decide feasibility before spending a labeling budget. Given a target false-reuse rate and a required hit rate, the pair is a point in the frontier's plane, and the question is whether the achievable frontier for the team's score passes below and to the right of it. Estimating the frontier is cheap relative to full calibration: a small pilot of labeled hits at a few thresholds traces the two similarity densities well enough to fit the separability and place the frontier, and the placement answers the feasibility question at once. If the target point sits above the frontier, no threshold reaches it and the team must improve the score or add an orthogonal signal (Section 4.3); if it sits comfortably below, the certificate of Section 6 will reach it and the only remaining question is the calibration budget. Running this feasibility read first is what prevents the most common and most expensive failure of a cache deployment, which is to label a large calibration set and discover only at the certification step that the target was never reachable with the score in hand. The order matters because the feasibility read costs a pilot and the calibration costs a campaign.

The frontier also exposes a subtlety about how to compare two candidate embeddings or re-rankers. The right comparison is not which scores higher on a matching benchmark but which frontier dominates at the team's operating target, and the two can disagree: an embedding with higher average matching accuracy can have a worse frontier near a stringent target if its errors concentrate as high-confidence collisions rather than as diffuse low-similarity misses. A benchmark that reports a single accuracy or F-score averages over the operating point that matters and can rank the embeddings backwards for the purpose of a safe cache, exactly the metric hazard that aggregate embedding-benchmark scores invite ^[8]. The discipline that follows is to evaluate candidate scores by their frontier at the intended target, not by a summary statistic, and it is another instance of the general lesson that a cache is characterized by a pair of numbers at an operating point, not by one number averaged over all of them.

6 A Distribution-Free Safety Certificate

6.1 Calibrating the threshold with a proof

The frontier of Section 5 tells you the tradeoff; it does not tell you which threshold hits a target false-reuse rate, and a hand-picked threshold certifies nothing. We now calibrate the threshold so the false-reuse rate is provably bounded. Draw a calibration set of $n$ labeled hits, queries that clear a candidate threshold, each labeled safe or unsafe by the same judge that defines $S$. Because $\rho (\tau )$ is monotone in $\tau$ under MLR (Equation 8), the risk-controlling prediction-set construction applies: choose the smallest threshold whose upper confidence bound on the empirical risk is at most $\alpha$. With a Hoeffding bound this is

where ${\hat{\rho }}_n$ is the empirical false-reuse rate on the calibration hits. Equation 9 is the paper's central constructive promise: a distribution-free, finite-sample certificate that the deployed cache's false-reuse rate is at most $\alpha$ with confidence $1-\delta$, assuming only that calibration and deployment traffic are exchangeable and that safety is judged the same way in both ^[18], ^[19], ^[20]. It assumes nothing about the embedding, the model, or the query distribution. The betting-style confidence bounds of ^[25] tighten the slack term when the calibration budget is small, and learn-then-test extends the construction to jointly control a second risk (say a maximum abstention) through its multiple-testing view ^[19]. This is exactly the guarantee vCache targets with its online estimator ^[2]; Equation 9 is the offline, distribution-free version and the reason such a guarantee is attainable at all.

The construction deserves to be unpacked, because its validity rests on a specific and checkable structure. The risk-controlling prediction-set recipe treats the candidate thresholds as a nested family: as $\tau$ increases the hit set shrinks and, under MLR, the risk decreases, so the empirical risk ${\hat{\rho }}_n(\tau )$ is a monotone function of the single parameter being calibrated. Monotonicity is what lets a single upper confidence bound, evaluated along the family, control the risk with no multiplicity penalty: one picks the smallest $\tau$ whose bound clears the target, and the high-probability guarantee follows from the pointwise concentration of ${\hat{\rho }}_n$ around $\rho$ at that $\tau$ ^[18]. When monotonicity is not assumed, the learn-then-test view instead treats each candidate threshold as a hypothesis and applies a family-wise-error-controlling procedure, which is the correct tool when a second risk is controlled jointly or when the collision regime breaks MLR ^[19]. Conformal risk control gives the in-expectation counterpart, bounding the mean risk rather than bounding it with high probability, and is the natural choice when the cache re-calibrates continuously so that the expectation is what accumulates ^[20]. The three are not competitors but a menu indexed by how often one calibrates and how many risks one controls, and the deployment recipe of Section 10 says which to reach for.

A subtlety in applying the certificate to a cache, absent from the generic conformal setting, is that the calibration unit is a hit, and hits are generated by the same threshold being calibrated. The clean way to handle this is to label calibration queries at the most permissive threshold under consideration, so that every query that could hit at any candidate threshold is labeled, and then evaluate ${\hat{\rho }}_n(\tau )$ on the subset that hits at each $\tau$. This keeps the calibration sample valid across the whole threshold family and avoids the circularity of labeling only what the current threshold admits. It also makes concrete why only labeled hits count toward the effective sample size of Section 6.3: a calibration query that never hits at any candidate threshold carries no information about the selective risk and does not reduce the slack.

6.2 A global threshold is provably suboptimal

Equation 9 calibrates a threshold, but which threshold: one global $\hat{\tau }$ for the whole cache, or one ${\hat{\tau }}_a$ per anchor? The containment condition of Equation 2 already hinted that safety is local. We now show the global rule is strictly worse. Suppose anchors fall into groups with different local separability $d_a^{\prime }$ (equivalently, different safe radii: some anchors sit deep in a cell, others near a boundary). A per-anchor rule sets each ${\hat{\tau }}_a$ to meet $\alpha$ locally and answers as much as each neighborhood safely allows. A global rule must pick one threshold conservative enough for the aggregate, so it over-refuses the easy anchors and, to hold the average, under-protects none only by leaving hit rate on the table. The hit-rate gap is a Jensen penalty in the heterogeneity of local geometry:

where $g_{\alpha }$ maps an anchor's local separability to its $\alpha$-feasible hit rate and $C_g$ is a curvature constant; the gap is zero only when every anchor has identical local geometry and grows with the variance of that geometry across the cache. Equation 10 is the theoretical content of vCache's empirical result that per-prompt thresholds beat any static global one, reported as up to 12.5 times higher hit and 26 times lower error ^[2]: the advantage is structural, a consequence of heterogeneous local boundaries, not an artifact of a particular workload. Figure 8 plots both achievable hit rates at a fixed target as the heterogeneity grows.

The mechanism behind Equation 10 is worth seeing directly. Let each anchor group have an $\alpha$-feasible hit rate $g_{\alpha }(d_a^{\prime })$, the most it can answer while holding its own false-reuse rate at the target. The per-anchor rule realizes the average of these, ${\mathbb{E}}_a[g_{\alpha }(d_a^{\prime })]$, because each anchor answers at its own feasible frontier. The global rule must choose a single threshold; to keep the aggregate false-reuse rate at $\alpha$ it is dragged toward the stricter setting that the low-separability anchors require, and it therefore answers $g_{\alpha }$ evaluated at an effective separability below the mean, losing hit rate on the high-separability anchors that could safely have answered more. Because $g_{\alpha }$ is concave in the relevant range (feasible hit rate has diminishing returns in separability once the unsafe tail is already well under the threshold), Jensen's inequality makes the average of the feasible rates exceed the feasible rate at the effective separability, and the gap is the variance term of Equation 10. The practical corollary is that the value of per-anchor calibration is largest exactly where caches are hardest, on registries mixing wide-safe-set anchors (definitions, how-tos) with razor-thin ones (balances, dates), which is most real caches.

6.3 How much calibration data

The certificate is only as tight as its slack, and the slack is set by the calibration budget. Inverting Equation 9, the number of labeled hits needed so the finite-sample penalty does not eat the margin between the achievable risk ${\rho }^{\ast }$ and the target $\alpha$ is

Equation 11 records three practical facts. First, the budget scales like the inverse square of the margin you demand, so certifying a target close to the floor is expensive. Second, only labeled hits count, so if the hit rate is $H$ you must label roughly $1/H$ times as many queries as $n$; the group form makes this explicit. Third, per-anchor or per-slice certification divides the budget across groups and pays a multiplicity term $\log (G/\delta )$, the price of the finer guarantee that Equation 10 rewards. As calibrated numbers, a few hundred labeled hits put the slack in the low single-digit points and one to two thousand bring it under a point, which is the range the conformal-LLM literature operates in ^[17]. Figure 9 plots the slack against the calibration size.

A worked budget makes the tradeoffs concrete. Suppose a team wants a certificate at target $\alpha =0.03$ and confidence $\delta =0.05$, and a pilot suggests the achievable risk at a usable hit rate is ${\rho }^{\ast }\approx 0.02$, leaving a margin of one point. Equation 11 gives $n\ge \log (20)/(2\cdot 0.01^2)\approx 15,000$ labeled hits, which at a thirty percent hit rate means labeling roughly fifty thousand queries: expensive, and a signal that a one-point margin is costly. Relaxing the target to $\alpha =0.05$ triples the margin to three points and cuts the requirement by nearly an order of magnitude, to under two thousand labeled hits. The lesson is that the last point of safety is by far the most expensive, because the budget scales with the inverse square of the margin, and a team should decide whether that point is worth its labeling cost rather than demanding it reflexively. If the team also wants the guarantee to hold separately over, say, five business-critical slices, the multiplicity term and the divided budget of Equation 11 push the total higher still, which is the quantitative price of the group-conditional guarantee that Section 9.2 names as the honest middle ground between marginal and per-query control. The betting bounds of ^[25] recover a meaningful part of this cost at small sample sizes, where the Hoeffding slack is loosest, and are the right default when labels are the binding constraint.

7 Economics: Optimal Threshold and Cache Size

7.1 The cost-optimal threshold is interior

The certificate fixes a threshold from a safety target, but a deployment may prefer to choose the target itself from costs. Price a generated answer at one unit (the model call the cache would save) and a false reuse at $c_{\text{err}}$ units (the business cost of a wrong answer served with confidence, typically far above one). Relative to always calling the model, the expected cost per query under threshold $\tau$ is

Equation 12 has an interior optimum whenever $c_{\text{err}}>1$. Lowering the threshold raises the hit rate and saves generation cost, but past a point it admits enough false reuses that their expected cost outweighs the savings; the derivative condition $C^{\prime }({\tau }^{\ast })=0$ balances the marginal generation saved against the marginal wrong-answer cost incurred. The two corner policies, answer everything ($\tau \to -\infty$) and answer nothing ($\tau \to \infty$, no cache), are both suboptimal: the first pays $c_{\text{err}}$ on every collision, the second forgoes all savings. Figure 10 plots the cost curve and its minimum for two values of $c_{\text{err}}$, and the takeaway is that the cost-optimal target false-reuse rate is not zero but the point where a marginal wrong answer costs exactly what a marginal cache hit saves.

A worked instance makes the optimum tangible and connects it to Chow's rule. Suppose a generated answer costs one unit and a wrong answer served with confidence costs $c_{\text{err}}=20$ units, reflecting a setting where a confident falsehood triggers a support escalation or a compliance review. The first-order condition $C^{\prime }({\tau }^{\ast })=0$ equates the marginal generation saved by lowering the threshold, proportional to the marginal hit mass, against the marginal expected wrong-answer cost, proportional to $c_{\text{err}}$ times the marginal unsafe hit mass. Solving, the optimal operating point admits a marginal query exactly when the conditional probability that its reuse is unsafe is below $1/c_{\text{err}}=0.05$, which is Chow's cost-ratio rule recovered from the cache economics: reuse when the chance of being wrong is below the inverse cost of being wrong. At $c_{\text{err}}=5$the tolerated marginal error rises to twenty percent and the optimum shifts to a lower, more permissive threshold, which is the shift Figure 10 shows between its two curves. The managerial reading is that the safety target is not a matter of taste but a computable consequence of two prices, and a team that cannot name $c_{\text{err}}$ has not yet decided how much a wrong answer costs it, which is the decision the threshold silently encodes regardless.

7.2 How many anchors: a covering-number bound

The other economic quantity is the size of the cache. To answer a fraction $\beta$ of the query mass by reuse at safe radius $r$, the anchors must cover that mass with balls of radius $r$, so the number of anchors is bounded below by a covering number of the traffic support. Using the metric-entropy notion of Kolmogorov and Tikhomirov ^[27], for support of effective dimension $d_{\text{eff}}$ and diameter $R$,

Equation 13 exposes the tension the whole paper circles. A larger safe radius $r$ needs exponentially fewer anchors (cheaper, smaller cache) but risks crossing answer boundaries (higher false reuse); a smaller radius is safer but demands exponentially more anchors to keep the hit rate up. The certified safe radius $r(\alpha )$ from Section 6 sets the exchange rate. Anisotropy enters here too, through $d_{\text{eff}}$: a degenerate, low-intrinsic-dimension embedding needs fewer anchors to cover but, by the same collapse, separates the answer cells worse, so the apparent covering economy is paid back as a higher collision floor. Figure 11 plots the anchor count against the safe radius for two effective dimensions.

7.3 The economics of the layered design

Putting the two economic results together with the layering of Section 2.1 yields a design whose savings and risk are both bounded and both known. Let a fraction $h_e$ of traffic be served losslessly by the exact and prefix caches, a further fraction $h_s$ served by the certified semantic layer, and the rest generated fresh. The expected per-query cost relative to always generating is $1-h_e-h_s+h_s\rho c_{\text{err}}$, where only the semantic term carries the wrong-answer cost because the lossless term is exact. The semantic layer therefore contributes net savings whenever $1-\rho c_{\text{err}}>0$, that is whenever its certified false-reuse rate is below $1/c_{\text{err}}$, which is exactly the cost-ratio threshold of Section 7.1. This is the clean statement of when the lossy layer is worth running at all: its certified error must sit below the inverse cost of an error. Below that line every semantic hit is a net gain and the certificate guarantees the line is respected; above it the layer should be made stricter (raising $h_s$ quality at the cost of $h_s$ volume) or improved at the score until the line is cleared. The layered decomposition also makes the savings auditable: a finance or governance review can read off the three fractions and the certified $\rho$ and compute both the realized savings and the bounded residual risk, which a single blended hit-rate number cannot support.

There is a second-order interaction worth naming between the two lossy parameters, the threshold and the cache size. Tightening the threshold to lower $\rho$ also lowers the semantic hit rate $h_s$, which by Equation 13 means a given anchor budget now covers a smaller certified radius and therefore a smaller mass, so the two levers push the same direction and their effects compound: a safety-driven tightening both reduces the per-hit risk and shrinks the volume of hits, and a team that budgets anchors and picks a threshold independently will double-count the volume loss. The correct joint choice sets the threshold from the cost model of Section 7.1 and then sizes the anchor budget to the certified radius that threshold implies, rather than sizing the cache first and tuning the threshold against a fixed anchor set, which is the more common but backwards order.

8 Discussion

Three of the results cut against common practice sharply enough to restate. First, the global-threshold rule is not just imperfect but provably dominated. The folk method of picking one cosine threshold (the widely-quoted “start at 0.8” or “start at 0.92 and tune” ^[6]) is a single number applied to a cache whose anchors have heterogeneous local geometry, and Equation 10 shows it leaves hit rate on the table in proportion to that heterogeneity. The correct object is a per-anchor threshold, which is precisely the design vCache arrived at empirically ^[2]. The theory says this was not a lucky engineering choice but the only rule that can be both safe and efficient.

The folk rule deserves a closer post-mortem, because its failure is instructive rather than merely wrong. “Start at 0.8 and tune” is not senseless; it encodes a real prior that near-duplicate prompts sit at high cosine and a real practice of watching the error rate and adjusting. What it lacks is a proof that the adjustment converges to a stated error rate rather than to whatever the last incident happened to punish, and a recognition that the right number differs per anchor and per embedding. The result is a threshold that is simultaneously too loose for the razor-thin anchors (where it ships false reuses) and too tight for the wide ones (where it forgoes safe savings), tuned to an average that describes neither. The measure-theoretic account replaces the tuning loop with a calibration that has a proof attached and a per-anchor resolution that matches the number to the geometry, and it explains why every attempt to fix the folk rule by finding a better global constant was doomed: there is no global constant that is right, because the quantity it approximates, the local safe radius, is not global.

Second, separability, not the base hallucination rate, sets the cost of safety (Section 5). A team worried about cache safety on messy traffic should not conclude the traffic is hopeless; it should measure the separability of its score first, because a strong score makes even a high-base-rate cache cheap to certify and a weak score makes even a low-base-rate cache expensive. This reorders the usual investment priorities: the money goes to the embedding, the re-ranker, and the labeling of the safe relation, not to the generator.

Third, some targets are simply unreachable by thresholding (Section 4.3). The collision floor is an impossibility, and a deployment that demands a false-reuse rate below its embedding's floor on its traffic is asking the threshold to do something no threshold can. The escape is an orthogonal signal, an entailment check or a verification call, which is a different mechanism and a different cost. Figure 12 replots vCache's headline result as an existence proof that, above the floor, the certified regime is real: a system that meets a user-set error bound while saving a majority of cost.

There is also a clean architectural reading. Because the semantic layer is the only lossy one (Section 2.1), a system should serve exact repeats and shared prefixes from the lossless caches first, where the savings carry no correctness risk, and route only the residual near-duplicate traffic through the calibrated semantic layer. The measure-theoretic criterion applies exactly to that residual, and its purpose is to make the one lossy layer as trustworthy as the lossless ones are by construction. This layering also bounds the blast radius of a mistaken safe-relation label: the semantic layer handles less traffic than a hit-rate-maximizing design would give it, and every query it declines falls through to a lossless path or a fresh generation.

The layering has a governance reading as well as an economic one. A certified semantic cache produces, as a byproduct of its calibration and monitoring loop, exactly the artifact a risk or compliance review asks for: a written target error rate, a dated certificate that the deployed system meets it with stated confidence, and a monitoring record of the realized rate over time. This is a stronger position than most model-quality controls can offer, because the guarantee is distribution-free and finite-sample rather than an appeal to average benchmark performance, and it names its own assumptions (exchangeability, label fidelity) so a reviewer can check them. The failure modes the paper catalogs, drift voiding the certificate, a biased labeler certifying the wrong quantity, a collision floor making a target unreachable, are precisely the questions a competent audit should ask, and a deployment that has read them can answer each with a documented control rather than a shrug. In a setting where a wrong answer carries regulatory or reputational cost, the ability to state and defend a bounded error rate is worth as much as the savings that motivated the cache.

A fourth point is methodological and cuts at how these systems are evaluated. The dominant reported metric for a semantic cache is hit rate, sometimes alongside an aggregate precision or F-score on a matching benchmark ^[3]. The results here say hit rate is the wrong headline number in isolation, for the same reason mean accuracy is the wrong headline for an agent: it averages over exactly the heterogeneity that determines safety, and it is maximized by the permissive threshold that also maximizes false reuse. A cache reporting a ninety percent hit rate has said nothing about how often it is wrong, and a benchmark F-score computed on a balanced matching set does not transfer to a skewed production stream where the safe and unsafe classes are wildly imbalanced and the boundary cases dominate the harm. The metric that travels is the certified false-reuse rate at a stated hit rate, the pair reported together, with the calibration distribution named. This is the analog for caches of reporting an accuracy with a confidence interval and a named test set, and its absence from most cache evaluations is why the field's hit-rate claims and its silent-error reports coexist without contradiction.

It is also worth stating what the theory does not claim, to keep the contribution honest. It does not claim semantic caching is unsafe; it claims the opposite, that semantic caching can be made provably safe, and gives the construction. It does not claim per-anchor thresholds or conformal calibration are inventions of ours; they are, respectively, vCache's design and the conformal literature's machinery ^[2], ^[18]. What is new is the measure-theoretic account that says why those choices are forced rather than optional: the containment condition that defines safety, the collision floor that bounds it, the separability law that prices it, and the Jensen gap that condemns the global threshold. The value of a theory here is not a new algorithm but an explanation of which algorithms can possibly work and why, which is what lets a practitioner reason about a cache they have not seen benchmarked and a researcher target the obstacles that actually bind.

9 Threats to Validity and Limitations

The results are theorems and analytical models, and their force is exactly the force of their assumptions. We state the load-bearing ones and what each buys or costs.

9.1 Exchangeability and drift

The certificate of Equation 9 assumes calibration and deployment traffic are exchangeable. Query streams drift, new products, new document types, seasonal topics, and under drift the calibrated threshold no longer certifies the target; worse, the realized false-reuse rate can rise while the hit rate stays flat, so the free dashboard signal is blind to the failure that matters. Under covariate shift with an estimable likelihood ratio, weighted conformal methods restore a valid bound at the price of a reduced effective sample size ^[21]; under unknown drift, no distribution-free method can promise the bound, and the honest posture is to monitor a rolling estimate of realized risk on freshly labeled live traffic and re-calibrate on a cadence tied to the measured drift rate ^[28]. A certificate is dated: it certifies the distribution it was calibrated on, and a cache is a store of answers to a world that keeps moving. Figure 13 shows the realized risk climbing after calibration and the re-calibration that resets it.

Drift interacts with the cache in a way that a static classifier does not face, and the interaction cuts against safety. A cache accumulates anchors over time from the traffic it has seen, so its anchor set is a lagging snapshot of a moving distribution; when the query mix shifts, the new queries are matched against anchors drawn from the old world, and the safe sets around those old anchors may no longer contain the new traffic even at high similarity. This is a distinct mechanism from ordinary covariate shift: it is not only that the calibration sample is stale but that the cache's reference points are stale, so the very geometry the certificate was computed against has moved. The practical consequence is that re-calibration alone may be insufficient under strong drift; the anchor set itself must be refreshed, evicting anchors whose neighborhoods the traffic has left and admitting anchors from the new regions, which is the cache analog of a reindex in the retrieval literature ^[28]. A monitoring loop that watches realized risk will catch the degradation, but the fix may be an eviction rather than a threshold adjustment, and a design that can only re-tune the threshold will find itself unable to recover a certificate that a stale anchor set has voided.

9.2 The guarantee is marginal, not conditional

Equation 9 bounds the false-reuse rate on average over the calibration distribution. It does not promise the bound holds for every anchor, every slice, or every individual query. This is not a gap we could close with effort: exact conditional coverage is impossible distribution-free with finite data ^[22], ^[23]. The practical middle ground is to pre-register a finite family of groups (business-critical slices, high-risk anchors) and certify within each, which Equation 11 shows costs a multiplicity term and a divided budget. A guarantee that holds uniformly over arbitrary soft subpopulations is not available, and any claim to the contrary is either assuming more than distribution-free or measuring something coarser than it states.

9.3 The certificate is only as good as the safe-relation labels

Everything is defined against the safe indicator $S$, and $S$ is a judgment. If a human panel defines it, the certificate is about human-judged safety; if an LLM judge defines it, the certificate inherits the judge's biases and error rate. A judge that misses a fraction of unsafe reuses induces a systematic gap between the certified rate and the true rate, roughly its false-negative rate on the unsafe class. The mathematics is exact given the labels, which relocates the trust onto the labels: they must be audited, versioned, and held to a standard, and periodic human audits of an automated labeler are part of the calibration hygiene, because a biased instrument yields a precise certificate of the wrong quantity.

The label-noise threat has a quantitative shape that a deployment can at least bound. If the automated judge that defines $S$ has a false-negative rate $\eta$ on genuinely unsafe reuses (it calls them safe), then the certified false-reuse rate understates the true rate by approximately $\eta$ times the true unsafe fraction among hits, because that fraction of unsafe hits is invisible to both calibration and monitoring. The certificate is then a valid bound on judge-labeled unsafety and a biased estimate of true unsafety, and the bias is one-directional: it can only make the cache look safer than it is. The honest mitigation is a two-tier labeling scheme in which an expensive high-fidelity labeler (a human panel or a stronger model) audits a random subsample of the cheap judge's labels, yielding an estimate of $\eta$ that inflates the certified rate into a corrected bound, at the cost of the audit budget. This is the same instrument-calibration discipline that any measurement pipeline needs, and its omission is the single most common way a mathematically valid certificate certifies the wrong quantity in practice.

9.4 Modeling assumptions in the analytical figures

The two-density model behind Figures 3, 6, 7, 8, and 10 assumes a monotone-likelihood-ratio separation and, in the plots, two Gaussians. MLR can fail exactly where it hurts, when collisions make the unsafe similarity distribution bimodal, and there raising the threshold past the collision mode can increase risk (Section 5.2). We use the Gaussian form only to draw representative curves; the qualitative results (monotone frontier under MLR, Jensen penalty for the global rule, interior cost optimum, collision floor) do not depend on Gaussianity, only on the stated structural conditions. The covering-number bound of Equation 13 uses an effective dimension that is itself a modeling choice for a curved, non-uniform embedding manifold; the exponential scaling in dimension is robust, the constant is not.

The covering-number bound also inherits a modeling assumption that a real embedding manifold violates: it treats the traffic support as a metric set of a single effective dimension with a uniform covering density. Real query distributions are highly non-uniform, concentrating mass on a few intents and thinning into a long tail, and the answer cells vary in size across that support. A faithful cache-size estimate would integrate the local safe radius against the local traffic density rather than raising a single global radius to a single global dimension, and the honest status of Equation 13 is as an order-of-magnitude scaling law, correct in its exponential dependence on dimension and its inverse dependence on radius, approximate in its constant. We flag this rather than hide it because the temptation with a clean covering bound is to read a precise anchor count off it, and that precision is not warranted; what is warranted is the qualitative claim that halving the certified safe radius multiplies the cache size by a dimension-dependent factor, which is what makes the safety-versus-size tradeoff real.

9.5 Stochastic and non-transitive answers

Two idealizations deserve naming. We wrote the model as if $M(a)$ were a single deterministic response, but real models sample, so the “correct answer” is itself a distribution and the safe indicator should be read as acceptability of the stored response for the new query, which is what we defined and which survives stochasticity. And the safe relation need not be an equivalence relation: a detailed answer can serve a broad question and not conversely, so the partition picture of Figure 2 is an idealization and the general statements are written over safe sets $R_a$, not cells. Neither idealization weakens the containment or certificate results, which never used symmetry or transitivity; they do mean the clean answer-stability-radius story of Section 4.1 is a special case, and the honest general object is the boundary-measure formula of Equation 3.

10 Practical Implications

The theory reduces to a procedure, and the procedure is worth stating as a checklist because each step corresponds to a result the paper proved load-bearing. Figure 14 is the deployment flowchart; the steps annotate it, and Figure 15 collects the cited numbers the procedure rests on. Nothing here requires touching the model: the safe semantic cache wraps an existing stack, reads a similarity it already computes, and adds a calibration set, a per-anchor threshold, and a monitoring loop.

1. Exhaust the lossless layers first. Serve exact repeats and shared prefixes from the exact and prefix caches ^[4], where reuse carries no correctness risk, and pass only the residual near-duplicate traffic to the semantic layer (Section 8).

2. Measure separability before anything else. On a small pilot, estimate how well your similarity score separates safe from unsafe reuses (Section 5). This is cheap and it tells you immediately whether your target is even reachable, or whether you are below the collision floor and need a better embedding or a re-rank rather than a tuned threshold ^[1], ^[3].

3. Name the target and confidence. Choose the largest false-reuse rate $\alpha$ you will tolerate and a confidence $1-\delta$, and if costs are what you care about, read $\alpha$ off the cost model of Equation 12 rather than by feel.

4. Calibrate per anchor, not globally. Label a calibration set of hits and set a threshold per anchor (or per pre-registered slice) with the certificate of Equation 9; Equation 10 is why per-anchor is worth the trouble and Equation 11 sizes the labeling budget.

5. Serve, monitor, and re-calibrate. Answer on a certified hit, defer on a miss, and, crucially, monitor a rolling estimate of the realized false-reuse rate on freshly labeled live traffic, not the abstention rate, because drift raises the former while leaving the latter flat (Section 9.1). Re-calibrate on a cadence tied to the measured drift.

The monitoring step deserves emphasis because it is where deployments most often cut the corner that voids the guarantee. It is tempting to monitor the abstention rate, which is free because the system already knows how often it misses, and to treat a stable abstention rate as evidence that the certificate still holds. Section 9.1 showed this is exactly backwards: drift can raise the realized false-reuse rate while leaving the abstention rate unchanged, so the free signal is blind to the failure that matters. The monitoring that actually protects the certificate requires a trickle of freshly labeled hits, drawn from live traffic and scored by the same labeler used in calibration, on which a rolling estimate of the realized false-reuse rate is maintained. This costs labeling budget, and the honest framing is that the budget is not overhead but the price of keeping the guarantee true; a deployment unwilling to label any live traffic can calibrate once but cannot claim the certificate still holds a quarter later. The cadence should be tied to the measured rate of query-mix drift, faster for a volatile product surface and slower for a stable one, and an anytime-valid confidence sequence is the principled way to watch the rolling estimate continuously without inflating the false-alarm rate ^[25].

One deployment caution ties the recipe back to the theory. The most common way the procedure fails in practice is not a subtle statistical error but skipping step 2, the separability measurement, and discovering at step 4 that the target is unreachable at any acceptable hit rate. By then the calibration set has been labeled and the disappointment is expensive. The order of the steps is deliberate: measuring separability on a small pilot is cheap and tells the team immediately whether the target is feasible with the score they have, before any large labeling investment. A team that runs the steps in order will either confirm feasibility early or learn early that it must improve the score or add an orthogonal signal, which is the difference between a project that fails in a pilot and one that fails in production. The same discipline applies to which query classes reach the semantic layer at all: routing the high-precision classes of Section 4.1 (identifiers, numbers, dates) away from the cache before calibration removes the anchors whose safe sets are near-points and whose collisions would otherwise dominate the floor, and it is cheaper to exclude them by routing than to protect them by threshold.

flowchart TD
    T[Traffic] --> L{Exact or prefix hit?}
    L -- yes --> LL[Lossless reuse]
    L -- no --> SEP{Separable above floor?}
    SEP -- no --> FIX[Improve score or add entailment check]
    SEP -- yes --> CAL[Calibrate per-anchor threshold to alpha]
    CAL --> SRV{Certified hit?}
    SRV -- yes --> ANS[Serve cached response]
    SRV -- no --> GEN[Call the model]
    ANS --> MON[Monitor realized risk]
    MON -->|drift detected| CAL

This wraps around practices we have written about elsewhere. The similarity and entailment signals a safe cache needs are the same ones a RAG and knowledge orchestration pipeline already computes; the calibration and realized-risk monitoring loop is a natural home for LLMOps observability and tracing, which supplies the telemetry step 5 depends on; the false-reuse certificate is exactly the kind of documented, defensible control a responsible AI program can point to when asked how a system bounds its own errors; and for regulated or residency-bound deployments the same layering supports the isolation a sovereign and private AI posture requires. For the broader cost picture, the cache sits inside the AI strategy and value question of where inference spend actually goes.

11 Open Problems and Future Work

Four directions follow directly from the results. First, anytime-valid certification: the offline certificate of Equation 9 is dated, and the natural repair is a confidence sequence over realized risk so a continuous-integration monitor may peek continuously and re-calibrate without inflating its false-alarm rate ^[25]; formalizing the semantic cache as an always-valid risk controller is open. Second, learning the safe geometry, not just the threshold: vCache learns a per-anchor threshold online ^[2], but Equation 10 suggests learning the local separability directly and allocating calibration budget to the anchors near boundaries, an active-calibration problem. Third, orthogonal-signal fusion: Section 4.3 says the collision floor is escaped only by a signal independent of the embedding, and the right way to combine a similarity score with an entailment or verification score under a joint risk-control guarantee (a two-dimensional learn-then-test) is unsolved. Fourth, drift-aware safe radii: coupling the reindex-trigger and drift literature ^[28] to the certified radius so the cache shrinks its own trust as its world moves, rather than waiting for a scheduled re-calibration, would close the loop the threats section opened.

Two further directions are more speculative but follow the same logic. A measure of embedding cache-fitness would summarize, in one number computable from an embedding and a traffic sample, the collision floor and the distortion tax the embedding imposes, so an embedding could be selected for caching the way it is now selected for retrieval by a benchmark score; the frontier of Section 5.4 is the object such a measure would summarize, and reducing it to a scalar without losing the operating-point dependence is the challenge. And a compositional account of cached agent steps would extend the single-turn analysis here to the setting where a cache serves an intermediate step of a multi-step agent, in which a false reuse does not merely return a wrong answer but corrupts a downstream trajectory whose error compounds; the right object is then a certified false-reuse rate per step composed through the agent's dependency structure, a problem that connects this paper to the reliability of long-horizon execution and that no current semantic cache addresses.

Frequently Asked Questions

Glossary