vCache: Verified Semantic Prompt Caching
Authors: Luis Gaspar Schroeder
Aditya Desai
Alejandro Cuadron
Kyle Chu
Shu Liu
Mark Zhao
Stephan Krusche
Alfons Kemper
Matei Zaharia
Joseph E. Gonzalez
Venue: ICLR 2026 Poster (2026)
Keywords: Semantic Prompt Cache
Caching
LLM
Guarantees
Embedding Threshold
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: First reliable, interpretable semantic prompt caching approach with user-specified error-rate bounds, achieving up to 26× gains over state-of-the-art baselines.

Abstract: Semantic caches return cached responses for semantically similar prompts to reduce LLM inference latency and cost. They embed cached prompts and store them alongside their response in a vector database. Embedding similarity metrics assign a numerical score to quantify the similarity between a request and its nearest neighbor prompt from the cache. Existing systems use the same static similarity threshold across all requests to determine whether two prompts can share similar responses. However, we observe that static thresholds do not give formal correctness guarantees, result in unexpected error rates, and lead to suboptimal cache hit rates. This paper proposes vCache, the first verified semantic cache with user-defined error rate guarantees for predictable performance. It employs an online learning algorithm to estimate an optimal threshold for each cached prompt, enabling reliable cache responses without additional training. Our experiments show that vCache consistently meets the specified error bounds while outperforming state-of-the-art static-threshold and fine-tuned embedding baselines with up to 12.5$\times$ higher cache hit and 26$\times$ lower error rates. We release the vCache implementation and four benchmarks to support future research.

Published as a conference paper at ICLR 2026
VCACHE: VERIFIED SEMANTIC PROMPT CACHING
Luis Gaspar Schroeder Shu Liu'
Aditya Desai" Stephan Krusche²
Alejandro Cuadron 1.3
Kyle Chu Matei Zaharia'
Mark Zhao
Alfons Kemper
Joseph E. Gonzalez*
University of California, Berkeley "Stanford University
Technical University of Munich
ETH Zurich
ABSTRACT
Semantic caches return cached responses for semantically similar prompts to re- duce LLM inference latency and cost. They embed cached prompts and store them alongside their response in vector database, Embedding similarity metrics assign numerical score to quantify the similarity between request and its nearest neighbor prompt from the cache. Existing systems use the same static similarity threshold across all requests to determine whether two prompts can share similar re- sponses. However, we observe that static thresholds do not give formal correctness guarantees, result in unexpected error rates, and lead to suboptimal cache hit rates. This paper proposes vCache, the first verified semantic cache with user-defined error rate guarantees for predictable performance. It employs an online learning al- gorithm to estimate an optimal threshold for each cached prompt, enabling reliable cache responses without additional training. Our experiments show that vCache consistently meets the specified error bounds while outperforming state-of-the-art static-threshole and fine-tuned embedding baselines with up to 12.5x higher cache hit and 26x lower error rates. We release the vCache implementation and four benchmarks to support future research.
INTRODUCTION
Large language models (LLMs)) power applications ranging from conversational assistants to search engines and code generation, but their widespread use limited by the high computational cost and inference latency (Zhao et al., 2023; Xiong et al., 2024; Achiam et al., 2023). Each new prompt requires multiple expensive forward passes through the model, which makes deployments costly and slow (Kwon et al., 2023). Prompt caching offers natural way to mitigate this issue: if a prompt has already been answered, the system can return the cached response instead of performing another inference. Traditional exact string- string-match caching reduces cost by returning responses for repeated prompts, but it fails whenever the same intent is expressed in different words (Zhu et al., 2024). For example, a cache that already answered "Which city is Canada's is capital?" should also return the same response when later asked "What is the capital of Canada?". Semantic caching addresses this limitation by retrieving responses for prompts that are semantically similar, even if their lexical form differs, and reduces inference latency by up to 100x (Bang, 2023). Semantic caches are effective in single-turn interactions with short to medium context, such as web search queries or classification tasks, where requests reappear in paraphrased forms but map to the same underlying response (Liu et al., 2024b; Wang et al., 2024). this paper, we study the reliability of semantic caches in returning correct responses for semantically similar prompts.
Semantic caches operate as follows. The cache embeds every prompt request into a vector (xx) E & and retrieves the semantically most similar prompt rz(z)) alongside its response r r(nn(z)), from a vector database (Pan et al., 2024). The cache measures similarity (c.g., cosine similarity) between two embeddings using s(x) sim (E)),, E(y)) E [0, 1). If no sufficiently similar prompt is found, an LLM generates a response and adds the embedded prompt along with the response to the vector database in the cache.
To determine whether a new prompt is sufficiently close to an existing prompt in the cache, state- of-the-art semantic caches rely on user-selected threshold E [0, 1] (Bang, 2023; Li et al., 2024;

---

Published as a conference paper at ICLR 2026
Dasgupta et al., 2025; Razi et al., 2024; Sudarsan & MasayaNiihimmai, 2024). If s(z) 2 t. the system performs exploitation (cache hit) by returning the cached response r(nn(2)). Otherwise, performs exploration (cache miss) by querying the model for a new response r(x)). The cache adds (()) to the vector database, stores r(z in its metadata, and returns r(z)).
However, selecting an appropriate threshold is nontrivial. If the threshold i is set too low, the system may treat unrelated prompts as similar, resulting in cache hits where the retrieved response r r(nn(z)) differs from the correct output r(z). These false positives reduce response quality and compromise cache reliability. If / is too high, the system may forgo correct cache hit opportunities and invoke the model unnecessarily (Rekabsaz et al., 2017).
Existing systems use the same static similarity threshold across all requests, Users either use predefined threshold (c.g., 0.8) or determine one by testing multiple values upfront (Dasgupta et al., 2025; Li et al., 2024; Dan Lepow, 2025; Razi et al., 2024; lit, 2025; Bang, 2023). This approach assumes that similarity correlates uniformly with correctness across all prompts and their embeddings. However, two prompts may be close in embedding space yet require different responses. Figure 3 illustrates that correct and incorrect cache hits have highly overlapping similarity distributions, suggesting that fixed thresholds are either unreliable or must be set extremely high to avoid errors, making them suboptimal. Another significant limitation of existing semantic caches is the lack of error-rate guarantees. While the latency benefits of caching appealing, the risk of returning incorrect responses can outweigh those advantages. For widespread adoption, semantic caches must adhere to user-defined error rate tolerances.
We propose vCache, the first verified semantic cache with theoretical correctness guarantees. vCache learns a separate threshold (Figure 1) for each embedding in the cache, capturing the threshold variability observed in Figure 3. It requires no upfront training, is agnostic to the underlying embedding model, and dynamically adapts its thresholds to the data distribution it encounters. As a consequence, vCache is robust to out-of-distriburt semantic caching 1) learns thresholds in an online manner and 2) guarantees their correctness.
inputs. To our knowledge, no prior work in
We adopt a probabilistic framework to bound the error rate conditioned on a learned per-embedding threshold. When deploying vCache, the user specifies a maximum error rate bound and the system maximizes the cache hit rate subject to this correctness constraint (Figure 2). Let vCache(2) (z) denote the response returned by vCache. Let r denote the exploration probability- value monotonically decreasing in the likelihood of being correct-and calibrated such that the overall error rate remains below the user-specs eser-specified bound (Section 4). The decision rule modeling the probability of being correct for whether to exploit the cached response or explore an LLM inference is given by:
(m(n(()) Uniform(0, 1) T,
vCache(x)
[LM(x)
otherwise.
An illustrative overview of the vCache workflow and system architecture is provided in Appendix B.
We evaluate the effectiveness of vCache in terms of correctness guarantees and overall performance. To assess generalizability, we compare vCache across three embedding models, two LLMs, and five datasets. We find that vCache consistently meets the error-rate bounds and outperforms static threshold baselines, even when using fine-tuned embeddings. Specifically, it achieves up to 12.5x higher cache hit rates and reduces error rates by up to 26x. Our main contributions
follows:
1. We propose vCache, the first predictable semantic cache that enforces a user-defined correctness guarantee by bounding the error rate.
2. We introduce an online threshold learning algorithm that requires no prior supervised training, adapts to the observed data distribution, and is agnostic to the choice of embedding model. dynamic thresholds improve decision quality. By
3. We demonstrate that embedding-speciiee learning separate threshold per cached embedding, vCache achieves equal or better performance compared to both static thresholding and fine-tuned embeddings.
We introduce four benchmarks, derived from five real-world datasets, that capture common semantic cache use cases: classification tasks, search queries, and open-ended prompt distributions.
5. We release the CCache implementation' and four benchmarks" to support future research.
/t htwp://ttwbbcooooccceeeeeeee /vCcche
hhttps://huggingffe htt.:/acc..ccc/aaaae co/vCache
2

---

Published as a conference paper at ICLR 2026
Existing Cache Decision Boundary
Embedding 42 (Using 6-0.01)
1.0
Exp oration Probability
Probabi By curve
P1
0.8
ity curve
Bn
R2
0.87
Truee
P4
0.92
Hilt
P
Hit
0.4
Correct observations (clx]
0.2
incorrect observations (cOx]
VCache Decision Boundary
0.0
0.6
Embedding 128 [Using 6-0.01)
P
Expleration Probability
1.0
Ry,
Truee
True
0.8
t'
0.78
Hit
P
6.6
Figure 1: The static threshold in existing mantic caches enforces naive decision bound- aries, resulting in either low cache hit high error rates. vCache's s embedding-spedd dynamic thresholds learn decision boundaries to guarantee user-defined maximum error rate. Gradient shading reflects decreasing confidence in correctness as similarity to the cached embedding decreases.
0.2
0.0
0.2
0.
0.6
0.8
1.0
Similarity (s)
and
Figure 2: Exploration probability for emb1 and
Observations are perfectly separable. Bottom: Observations are overlapping. vCache selects the optimal f and adjusts the exploration probability based on the user-defined 8 0.01.
emb128. Top:
RELATED WORK
Existing semantic caches, such as GPTCache (Bang, 2023) and industry variants (Razi et al., 2024; Dan Lepow, 2025; lit, 2025: Dasgupta al., 2025; Li al., 2024), use a global similarity threshold to make cache hit decisions. This assumes uniform correlation between similarity and correctness across all prompts and embeddings. However, illustrated Figure 3, similarity distributions vary widely, making fixed thresholds unreliable. Further details are provided in Appendix F.9.
Semantic Cache Optimization.
The threshold dilemma illustrated in Figure can be addressed via two approaches: optimizing the embedding space or learning more effective thresholding strategies.
Embedding Fine-tuning: Zhu et al. (2024) propose a distillation- based method that fine-tunes embeddings for semantic caching, improving alignment between semantically equivalent prompts and their responses. A related challenge arises in image retrieval, where systems must determine whether nearest neighbor corresponds to the correct target class. Zhang al. (2023a) address this by introducing the Threshold- Conoslst-nnnsstttt Margin loss, which enforces tighter intra-class cohesion and clearer inter-class separation by selectively penalizing negative pairs. However, they require supervised training, are limited to open-source embedding models, and can fail to generalize to out-of- distribution data inference time (Hajipour al., 2024). vCache's online learning algorithm does require training, is model-agnostic, and generalizes to out-of-distribun
data (see Appendix H.
Threshold Optimization: Threshold optimization learns a decision boundary over existing embeddings without modifying the embedding model itself (Zhang et al., 2023b). To our knowledge, no prior work in semantic caching learns thresholds online inference time. Yet, shown in Figure 3, the optimal similarity threshold varies significantly across embeddings, motivating embedding-speciff and online threshold estimation. Related ideas have been explored incremental learning. For example, Rudd et al. (2017) propose the Extreme Value Machine (EVM), which models class boundaries using extreme value theory to support generalization to unseen categories. However, these methods do guarantee user-defined error rates. In contrast, introduce the first online algorithm that estimates per-embedding thresholds for semantic caches while satisfying a user-detined error bound.
Semantic Cache Guarantees. Even with high-quality embeddings and presumably carefully tuned threshold, semantic caches remain inherently approximate. Unless a threshold 1.0 used (effectively restricting cache hits to exact prompt matches), there is always risk of returning incorrect responses (Razi et al., 2024; Jim Allen Wallace, 2024). Despite this, existing semantic caching systems rely fixed thresholds decide whether return cached response (Dasgupta
3

---

Published as a conference paper at ICLR 2026
et al., 2025; Li al., 2024; Dan Lepow, 2025; Razi et al., 2024; lit, 2025; Bang, 2023). As result, they offer no formal guarantees on accuracy or error rates, making it difficult to justify their reliability in production environments. To address this, propose vCache, the first semantic caching system that combines competitive performance with user-defined correctness guarantee.
3 OVERVIEW OF SEMANTIC CACHING
Let {21, f .2,..., In J be the set all prompts inserted into the cache, in that order. Note that this set excludes prompts for which cache hit found and served. Let D denote all the data stored in the cache. For each prompt z inserted into the cache, we store its vector embedding (x) E IR the true response r(x) = LLM(aa produced by the LLM, and optional additional metadata (z)). Given Exx), the cache retrieves the most similar prompt from the vector database with an approximate nearest neighbor search (Arya et al., 1998), where
nn (r) = arg max sim sim (E((), E()).
(2)
yEC
In vCache, for a prompt Ze, the metadata (z;;) stores similarity and response match information for all future prompts zj (with > i) such that nn(x)) z₁. The exact workings of vCache are presented in Algorithm The sets DD and O can be represented as follows:
D = (E(z)), r(x)), O(z,)) }"
O(x,) = (s(zz). dxz))) nn((z)) = 2 }"
(3)
j=it1
where s(x) E [0 is the similarity between x and its nearest neighbor nn(x) and c(x) indicates if the cached response of nn(x), r(nn(z)). matches the true response r(z).
c(x) {
if (fr(n)))) r(x:)
s(x) = ((((E()),
(4)
otherwise.
Algorithm. Given a prompt, say x, we first compute the embedding Exx) and find its nearest neighbor nn(x). The caching policy P then determines whether we should use the cached response for this prompt (exploit) or run the LLM inference (explore). In case we decide to exploit, r(un(z))
returned. Otherwise, we run rax) LLM(x), compute s(x) and c(x). update the observations (z)(()) and add x to the database D using,
((n((x) (nn())) ((())
D DDD ((E()),
(5)
The key challenge lies in designing decision policy P(...), as it directly impacts both the cache hit rate and the overall error rate.
Policy of existing systems (P (s(x))). In existing semantic caching systems, the decision function is implemented as a fixed threshold rule. Given a user-defined threshold 4, the cache exploits if sxx) 2 t by returning the cached response r[nn(z)). Otherwise, it explores by invoking the model for a response. As discussed in Section 2, this approach lacks formal guarantees and does not adapt to variation in similarity value distributions.
Policy of vCache (PyCache (s(x), (nn(x))) 8)). vCache replaces static thresholding with an embedding speccifc decision function that respects a user-defined error bound 8. If the function returns exploit, the cache is sufficiently confident and outputs the eached response r(nn(x) (Algorithm 1, 1.5). Otherwise, it returns explore by inferring the LLM. Section provides further details.
Scope of definitions. All quantities such as nn(r), s(x). and e(x), are evaluated at a fixed (but arbitrary) point in time. Since the analysis is performed online, these definitions apply consistently across time steps. Policy discussion always refers to a specific embedding in the cache, with all parameters and estimates interpreted conditional on
For ease of reference, a glossary of all symbols and functions is provided in Appendix A.
4 VCACHE
Given a user-defined maximum error rate 6, vCache maximizes the cache hit rate while ensuring the probability of correctness remains above - 5. Instead of relying on an unreliable static threshold
4

---

Published as a conference paper at ICLR 2026
20
KDF (c(x) = 0 at s(x))
Algorithm 1 vCache Workflow
15
Density
KDF (c(x) 1 at s(x))
1: ((r)
10
Mean (miss): 0.84
2: y + un(xr
5
Mean (hit): 0.85
3: s(x) t simm(e E(y)
4: Pr, Oly), exploit then
0.0
0.2
0.4
0.6
0.8
1.0
Similarity Values
5: return r(y)
100
6:
else
Mean (f): 0.88
Frequency
75
7:
7(x) (LM(x)
8:
cxx) = 1(r(x) = r(y))
50
9:
+ ((<()).(()))
25
10:
if' (<() then
+ ((E(z),
0.0
0.2
0.4 0.6 0.8
1.0
Optimal Threshold Values
12: end if
return r(x)
Figure 3: Results from 45k samples in the Sem- CacheClassification benchmark. Motivates the need for dynamic, sumbedding-specifii thresholds. Top: Similarity values of correct and incorrect ex- plorations exhibit highly overlapping distributions. Bottom: Optimal per-embedding thresholds vary substantially, indicating that single threshold can suffice across embeddings (see Appendix F.9).
14:
end if
vCache workflow for deciding whether to ex- ploit cached response (cache hit) explore an LLM inference (cache miss). The decision relies on the PvCache policy (Section 4) and guarantees user-defined error rate bound 5.
fine-tuned embeddings, vCache models probability distributions make cache hit miss decisions. The distributions are specific to each embedding in the cache and model the probability of correct cache hits for given similarity value. To remain dataset agnostic and avoid costly offline training, vCache estimates these distributions online by selectively generating labels for uncertain similarity values. Since generating label requires an LLM inference, equivalent in cost not using a cache, vCache minimizes such inferences. We refer to such inferences as explore and classify them as cache miss. For given prompt x. the cached response r(nn(z)) considered uncertain when the observations O(nn(z)) do not provide sufficient evidence to determine whether the cached response correct (c(z) = 1). In contrast, O (nn(x:) provides sufficient evidence, vCache proceeds with exploit by returning the cached response r (nn(zz) without an LLM inference. The rest of this section formalizes these ideas and provides a detailed explanation the vCache policy, PvCache
4.1 USER GUARANTEE
One of the key features of vCache is that it takes user-defined maximum error rate, 6, and ensures that the overall performance the cache remains within this error bound. Let vCache(x) denote the response returned by vCache, regardless of whether the decision was to explore or exploit. Then, an eтror rate guarantee
implics:
Definition 4.1 gueer-guarantee). An error-rate guarantee of for vCache implies that the marginal probability of vCache returning the correct answer, given any arbitrary prompt F, is lower bounded by (1 -8)) 8). In other words,
Pr(vCache(z) = r(x)) ( 5).
To achieve the eиrоr guarantee, vCache probabilistically decides when to explore and when to exploit. Let Prexplore (x DD) be the probability that, given a prompt x and having accumulated data D, vCache decides to explore. Then, can decompose the probability that vCache is correct as,
Pr(vCache(r==<(2) Pr(explore|22 D) (1 Pr(explore|r, D)) Pr(((() D). (7)
This expression reflects two disjoint events. First, vCache decides to explore with probability Pr(explore) D), and in this case, the output vCache(z) is same LLM(xr by design. In the second case, the vCache decides to exploit with probability (1 Pr(explore/jr D)) and in this case, the probability of vCache being correct is represented as Pr(c(x) = ||r, D) using notation from the
5

---

Published as a conference paper at ICLR 2026
previous section. To ensure enror guarantees are maintained, should have,
Pr(cxplore|z; D) 2 (1 - 8) Pr(c(x) = =1 D) = Tnn(a)(s(x))
(8)
1 1 Pr(c(x) = 1[
To meet the guarantees. vCache models the Pr(c(z) 1|,, D). This inequality provides an actionable constraint: if the estimated probability of correctness from the cache is high, the system may exploit; if the estimate is low, the system must explore. As long as Pr(explorejz; D) is larger the guarantees are achieved. Notation of is chosen to emphasize that it is function over similarities and is specific to each embedding in the cache.
than the Tnn(x) (s(z)), (s(())
Since vCache can only estimate Pr(c(z) 1 x, D) based on a limited number of samples, it accounts for the uncertainty in the estimation by considering the confidence band of Pr(c(z) = 1 x, D). The modeling details and the vCache policy are presented in the following subsection.
4.2 VCACHE MODELING
vCache imposes a sigmoid parametric model on the relationship between similarity and correctness. Specifically, for an arbitrary prompt x, the probability of correct cache hit is defined
1
Pr(e(x) = 1 |z. D) ((s(x),))) 1+e 1+
where ((x) E [0, 1] is the similarity of x with its near neighbour. L. E [0, 1] is an embedding--ppecifie decision boundary parameter, and y > 0 is a parameter controlling the steepness of the function. The sigmoid form is well-suited for this task: it induces a smooth and monotonic relationship between similarity and correctness probability and enables efficient maximun-likelihood estimation (MLE) of the threshold t from labeled data (justification in Appendix E). By fitting a continuous likelihood function rather than enforcing a hard threshold, vCache generalizes better from limited observations.
The MLE estimates for the parameters, say Emn(s) and Inn(a), using all the meta-data Oun(a) solves the binary cross entropy loss,
( (og(((( ((1-c)
Eun(a); Fmn(x) arg min (.s,)EE0 6,7
(a-e))-oo((1 log(1 L L(s,t,, (1,,
(10)
Note that these parameters belong to a specific embedding in the cache (specifically nn(x)).
Since these estimates are based on limited number of samples, estimating the true Pr(c(z)=1|z, D). and thus the correct [nn(z) (s(x:) is not possible. To ensure we still achieve guarantees, vCache, instead computes a upper bound, say f for (s(x)) using pessimistic values for 7 from the
(1 - c) confidence band for these points for some c E (0, 1). Let these estimates be t'(c), We compute i using,
(1 (1-
i == min cE(0,1)
2 [=)())(((z)).
(11)
The details of why f 2 Tna(ze)
and how to obtain confidence bands for 1 and are explained in Appendix C. Once have F. we have to ensure that the probability of exploration is above this value (see Eq 8) ). This is achieved by sampling uniform random variable ~ Uniform (0, 1). If u < f, the vCache explores, i.c. runs the LLM model obtain the correct response. Otherwise, exploits the cache by returning r(nn(z)). This randomized policy ensures that, in expectation, the system explores sufficiently often to meet the correctness guarantee while maximizing cache usage when reliability is high. The exact algorithm of how explore and exploit decisions are made is presented in Algorithm 2. Figure 2 illustrates the vCache modeling, where each subplot shows one cached embedding. Green and red points indicate correct and incorrect responses to observed similarities. The yellow dashed curve is the sigmoid model, with threshold obtained by MLE. The blue dashed curve represents the sigmoid fit based on confidence bounds, with threshold t' selected to meet the user-defined error bound 8. The dark green curve T(s) denotes the exploration probability, where for given similarity 8, vCache explores with probability r(s) and exploits the cache otherwise.
(s(x)) [=
4.3 VCACHE ALGORITHM
To summarize, the final vCache algorithm works as follows. First, for each incoming prompt æ, retrieves its nearest cached embedding y nn(x) and fits a logistic decision boundary i(y) using

---

VCache Fine-tuned embedding (Zhu et al., 2024): Same vCache, but fine-tuned Published as a conference paper at ICLR 2026
Algorithm 2 vCache Policy P PoCacha (s (nn(())), 5)
1: function (((x)) (1n())))
1: function G,(s, f, 9, 6, c)
2: i t arg min LogisticLosss(, 7: ()
, t 1- 9,
3:
b ie solve Eq 10
3:
a t (1 ( L(x,
4:
T < m (z, 6,),
(1 - 6)
4: T
5:
u (niform(0, 1)
1- a
6:
if и S T then
return
return explore 8: else
7:
6: end function
9: return exploit
10: end if
11:
end function
all labeled examples observed for y. then computes the 7 using Eq by iterating over different values of confidence e. Then we use uniform random variable u ~ Uniform(O, 1] and explore if S and exploit otherwise.
vCache makes two assumptions. First, the data DD received by the cache is independently and identically drawn from the underlying distribution. Second, the true probability of correctness of response match given similarity, i.e. Pr(c(x) = 1 (D,,)) .) is well represented by the sigmoid family of functions (Eq 9).. Under these assumptions, the vCache policy can provide user-defined error-rate guarantees, as summarized in the following theorem.
Theorem 4.1. Let ô (0, 1) be the user-provided maximum error tolerance. Let D, [ nu be the set of prompts seen by vCache at an arbitrary point in time. Then under the assumptions that prompts D are drawn i.idd. from underlying distribution and sigmoid family of functions (defined in Eq 9) correctly model the true likelihood of correctness for each embedding, the probability of correct response from VCache for any arbitrary prompt x, executed an online manner in accordance with Algorithm 2, is guaranteed to be greator than - 5. i.e.
Pr(vCache(2) (z) = r()) 2 11--886 8)V2,
(12)
5 EVALUATION
For our experiments, use three popular embedding models (GteLargeENv1-5 (Zhang et al., 2024), E5-large-v2 (Wang et al., 2022), and OpenAl text-embedding---smmi (ope, 2025)), and two LLMs (Llama-3-8B-instruue (Dubey al., 2024) and GPT-4o-mini (gpt, 2024)), representing both high- quality proprietary models and efficient open alternatives. We use the HNSW vector database (Malkov & Yashunin, 2018) with cosine similarity, standard metric for comparing vector embeddings in semantic caching systems (Bang, 2023; Li et al., 2024; Dasgupta et al., 2025). All experiments are conducted on a machine running Ubuntu 24.04.2 LTS, with an Intel Xeon Platinum 8570 CPU and an NVIDIA Blackwell with 192 GB of memory.
Metrics. We measure the following metrics. (1) Error Rate: (Lower is better) defined as F//n. where FP is the number of false positives and is the total number of prompts. (2) Cache hit rate: (Higher better) defined as (TP FP)/n where TP and FP are true positives and false positives, respectively. Together. TP and FP measure the total cache hits. We also show ROC curves Hoo et al. (2017). For the non-deterministic evaluation of vCache (Algorithm 2, Line 5), we compute 95% confidence intervals using Wallis binomial confidence bounds and contingency tests Wallis (2013).
Baselines. We use the following Cache-settings in our experiments
GPTCache (zilliztech): SOTA using static threshold for all embeddings (Parameter: threshold). GPTCache + Fine-tuned embedding: Changing the embedding model in GPTCache. Embedding data and method provided by Zhu et al. (2024) (Parameter: threshold). yCache: This is our proposed method (Parameter: error-rate bound 6).
models are fine-tuned
embedding model (Parameter: error-rate bound 8).
We implement additional baselines for ablations and show the results in Appendix F.8.
7

---

Published as a conference paper at ICLR 2026
GPTCache
VCache Fine-tuned Embedding
VCache
Fine-tuned Embedding
8.0
Target
(%)
Actual Error
Error Rate (%)
30
4.0
2
20
2.0
Cache
10
0
20000
40000
60000
20000 40000 60000
E5-large-v2 embedding model, OpenAl GPT-4o mini LLM, SemCachelmAAena benchmark
Error Rate (%)
8.00
Target
2.0
5.0.7
Cache Rate (%)
15
6.00
Actual Error
Error Rate (%)
1.5
10
4.00
2.00
0.00
100
8.0 2.00
0.5
Values
50000 100000 150000
50000 100000 150000
Sample Size
Sample Size
GteLargeENvi embedding model, Llama 3.1-8B LLM, SemCaahhSearchCuuriiss benchmark
8.0
7.0
Target
2.5
Cache Hit Rate (%)
6.0
Actual Error
Error Rate (9)
2.0
5.0
20
4.0
1.5
8-0015
3.0
2.0
10
0.0
1.00
0.5
6
0.0
Values
20000
40000
0
20000
40000
Sample Size
Sample Size
Seebbedng model, Llama 3.1-8B LLM, SemsaahhClassfiiation benchmark
8.00
Error Rate (%)
7.00
Target
2.0
Cache Hit Rate (%)
330
6.00
Actual Error
4.00
5.00
Error Rate
1.5
6-0015
3.00
1.0
2.00
1.00
0.5
10
0.00
0.0
Values
Sample Size
60000
20000
Sample Size
40000
60000
OpenAl text-emmeedding---mmlll model, OpenAl GPT 4.1-nano LLM, SemCacheLMMAenn benchmark
8.00
Fror Rate (
7.00
6 Target
a
5.00
6.00
Actual Error
Error Rate (%)
6 0.03
15
4.00
3.00
Cache Hit
10
2.00
1.00
0.00
10000
20000 Sample Size
10000 20000 Sample Size
6 Values
GtelargeENvi embedding model, Llama 3.1-8B LLM, SemCacheCombo benchmark
Figure 4: vCache meets the user-defined maximum error rate bound 8 with steadily increasing cache hit rates (vCache learning). GPTCache shows increasing error and hit rates, illustrating the unreliability of static thresholds. Static baselines use fixed thresholds. See Figure for threshold vs. Pareto comparison.
8

---

Published as a conference paper at ICLR 2026
GPTCache
VCache Fine tuned Embedding
Random Classifier No Cache
VCache
Fine tuned Embedding
1.0
100
Cache Hit Rate (%)
1::77
80
6-002
Error Rate (%)
6-001
5:000
40
6:00
20
0.00
0.25
0.50
0.75
1.00
3
E5-large-v2 embedding model, OpenAl GPT-4o mini LLM, SemCachelmArena benchmark
1.0
330
0 8
Error Rate (%)
TPR
0.6
20
0.006
w
1-:005
0.4
Cache
10
0.00
0,25
0.50
0.75
2
0.20
FPR
Error Rate (%)
Average Latency (sec)
GteLangeENv1 embedding model, Liama 3.1-88 LLM, SemCacheSearchhuerie benchmark
50
Cache Hit (%)
10007
40
Error Rate (%6]
30
11-8976
20
1-2507
kw007
14:59
10
0.175
0,200 0.225 0,250
FPR
Error Rate (%)
Average Latency (sec)
GrelargeENVi model, Liama 3.1-8B LLM, SemCacheClassfication benchmark
100
Cache Hit Rate (%)
.33
92
Error Rate (%)
m
TPR
40
0.2
20
0.00
0.25
0.50
0.75
1.00
2.5
4
FPR
Error Rate (%)
Average Latency (sec)
OpenAl text-embeddiing 3-small model, OpenAl GPT 4.1-nano LLM, SemCacheLMArenn benchmark
Cache Hit Rate (%))
Error Rate (%6)
TPR
90
20
3
10
5-
01
0.00
0.25
0.50
0.75
1.00
2
4
1.15
1.20
1.25
FPR
Error Rate (%6)
Average Latency (sec)
GteLargeENvi embedding model, Llama 3.1-8B LLM, SemCacheCombo benchmark
Figure 5: Pareto comparison across range of thresholds and d values. Each point represents full run on all samples of a dataset.
Datasets. To the best of our knowledge, realistic open-source benchmark currently exists for evaluating semantic caches. We introduce and open-source four diverse benchmarks designed to reflect common caching scenarios. Appendix H provides the complete dataset and benchmark cards.

---

Published as a conference paper at ICLR 2026
SemCacheLMMArnnt Randomly sampled subset of 60,000 queries from the LM-Arena human preference dataset (Chiang et al., 2024), containing open-ended, and user- seer-generated prompts. Benchmark of 45,000 prompts derived from three classification datasets (Saurabh Shahane, 2023; Talmor et al., 2018; Ni et al., 2019).
Sem BemCCachSSearchhuerreee Random subset of 150,000 web-search queries (Craswell et al., 2020).
SemCacheCommbo: 27, 27,500-prompl benchmark combining SemCCcheSearchhuerie and distinct LemCacheLMAArnn queries to model partial workloads with no cache hits.
VCache respects user-defined error-rate requirements. We evaluate whether vCache satisfies the user-defined error rate bound 5 while maintaining competitive performance. As shown in Figure vCache consistently meets the maximum error rate across d values, with actual error remaining below the specified bound, The small gap between maximum error rate and observed error stems from the conservative t' estimation, which ensures robustness and can be further refined. Notably, as the error rate stabilizes, vCache continues to increase its cache hit rate, demonstrating effective learning over time. In contrast, GPTCache baselines exhibit increasing error rates with sample size, reflecting the inherent limitations of fixed thresholds despite improving hit rates.
Dynamic and ambedding-spechie thresholds are superior to static thresholds. We evaluate whether semantic caches benefit from dynamic, threshold. To this end, compare vCache with static-threshold baselines by systematically varying threshold values for GPTCache and the maximum error rate (6) for vCache across feasible range. Each point in Figure represents a complete evaluation direct Pareto comparison between vCache and static-threshold configurations. vCache achieves better ROC curves, higher cache-hit rates at a given error rate, and lower average latency. On LenCacheLMArena, it achieves up to 26x lower error, 12.5x higher hit rates, and reduced latency. SemCCahheCassifictton vCache outperforms all baselines for error bounds above 1.5%, where static methods either violate constraints or underutilize the cache. For bounds below 1.5%, vCache is more conservative, reflecting its strategy of prioritizing correctness by increasing exploration under uncertainty. We note that GPTCache erro rates have not fully converged and exhibit an upward trend (Figure 4), suggesting the reported results likely overstate GPTCache performance.
sereeeddinn--pcccfff thresholds over a single static
the benchmark dataset, enabling
Convergence, Sigmoid, Latency, vLLM, and Additional Baselines. We report additional exper- iments on the convergence speed (Appendix D), aggregate empirical correctness probability (Ap- pendix E), computation (Appendix F.4), embedding generation (Appendix F.5), logistic regression (Appendix F6), vLLM inference (Appendix F.7), and extended baseline evaluations (Appendix F.8).
6 LIMITATIONS
There are two main limitations of vCache. First, for responses longer than a few words, string matching is insufficient and vCache uses LLMMaa---juudee (Zheng et al., 2023a) to assess response equivalence (Algorithm 1, L8), requiring an additional LLM inference. However, this can be executed asynchronously outside the critical path, not impacting latency (see vCache implementation). Since the output is a single token (e.g., "yes" or "no"), the overhead is minimal (Leviathan et al., 2023). In LenCacheLMArens and Sem SenCCacheSaachhuueriie,, response equivalence is assessed with LLM-as- a-judge, whereas reliably under evaluation regimes (Figure 4). Second, vCache relies on i.i.d. data and a sigmoid function family to represent the probability of correctness. If these assumptions are violated, the analysis may not hold. Nonetheless, both assumptions natural and appear model most use cases well, as supported by our experimental results (Appendix E).
CemCacheClassffiatte
it is determined by string matching. vCache performs
7 CONCLUSION
We introduced vCache, semantic cache that provides correctness guarantees by learning an optimal similarity threshold for each cached embedding online. This approach addresses the limitations of static thresholds and embedding fine-tuning in the semantic caching domain, ensuring that the error rate remains below user- sperisped bound. Our experiments demonstrate that vCache consistently satisfies this guarantce while outperforming existing methods w.r.t error and cache hit rates. These results suggest that reliable, interpretable caching for I.LMs is both practical and deployable.
10

---

Published as a conference paper at ICLR 2026
8 ACKNOWLEDGMENT
The authors thank Sebastien Gautier--ean-Iacques Beurnier and Siavash Ameli for their invaluable contributions. This research is partly supported by gifts from Accenture, Amazon, AMD, Anyscale, Broadcom, Google, IBM, Intel, Intesa Sanpaolo, Lambda, Lightspeed, Mibura, NVIDIA, Samsung SDS, and SAP.
ETHICS STATEMENT
This work contributes to the advancement of machine learning by improving the efficiency of large language model (LLM) inference. By reducing both computational cost and latency, our approach makes LLM-based systems more accessible to organizations and individuals with limited computational resources, thereby lowering the barrier to adoption. addition, by decreasing the frequency of full LLM invocations, method reduces overall compute demand and, consequently, the environmental impact associated with training and operating large-scale AI infrastructure.
10 REPRODUCIBILITY STATEMENT
We have taken several steps to ensure reproducibility our work. The full implementation of vCache, including all algorithms and experiments, is publicly available in GitHub repository The four semantic caching benchmarks introduced in this paper are released on HuggingFace' and Appendix H describes their construction and preprocessing in detail. All experimental settings, including hardware, software, and model configurations, are specified in Section Theoretical assumptions and complete proofs of correctness guarantees provided in Appendix C. Together, these resources ensure that our results can be verified and extended by future work.
REFERENCES
gpt, 2024. URL http://pp....ooo///////////o///a dccientiinte ligence/ [Accessed 11-11-2024).
Cache LLM Responses, 11 2025. URL ULL/ttpp://ooc...teelmaaaaa ng. [Accessed 02-05-2025).
(ext-embbediing---mmaeee 2025. URL https::/pllttoomn text-rebeeddig--33 11. [Accessed 11-11-2025].
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint ar 2xxv:23033.87774 2023.
Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), -99-999, 1998.
Fu Bang. Gpteache: An open-soures semantic cache for Ilm applications enabling faster answers and s of the 3rd Workshop for Natural Language Processing Open Source Software (NLP-OSS 20233), pp. 212-218, 2023.
cost savings. In Proceedings
Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Banghua Zhu, Hao Zhang, Michael Jordan, Joseph E Gonzalez, et al. Chatbot arena: An open platform for evaluating Ilms by human preference. In Forty-first International Conference Machine Learning, 2024.
Nick Craswell, Daniel Campos, Bhaskar Mitra, Emine Yilmaz, and Bodo Billerbeck. Orcas: 18 million clicked query duccmeeo pairs for analyzing search. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 2983-2989, 2020.
"https://githhee httt:::://githbb...c///aaeeeeeee http:///aacceeepooeeeeeeeeeeee /vCCche hittps:/huggingee anae colcco//vvvc/ vcache

---

Published as a conference paper at ICLR 2026
Robby Millsap Dan Lepow, Arie Heinrich. Enable semantic eaching for Azure OpenAI APIs in Azure API Management, 01 2025. URL https://Learr www.eeim.iiieeee microsoft. com/ en- /sz ure / app-maaangemeeteeeeaaaeeeeeeeeee htwp:///wwe....eeoooooooaaaaaaaa 22-01-2025].
[Accessed
Soumik Dasgupta, Anurag Wagh, Lalitdutt Parsai, Binay Gupta, Geet Vudata, Shally Sangal, Sohom Majumdar, Hema Rajesh, Kunal Banerjee, and Anirban Chatterjee. wallmartcache: A distributed, multi-tenant and enhanced semantic caching system for llms. In International Conference on Pattern Recognition, pp. 232 248. Springer, 2025.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.211 17782 2024.
Kai Franz, Samuel Arch, Denis Hirn, Torsten Grust, Todd C. Mowry, and Andrew Pavlo. Dear user-defined functions, inlining isn't working out so great for us. let's try batching to make our relationship work. sincerely, sql. In Conference on Innovative Data Systems Research, 2024. URL https: / api. semant wesccccclaaae org/Corpur
266738256.
Hossein Hajipour, Ning Yu,
Staicu, and Mario Fritz. SimSCOOD: System- atic analysis of out-of-distribution generalization in fine-tuned source code models. In Kevin Duh, Helena Gomez, and Steven Bethard (eds.), Findings of the Association for Computa- Mexico City, Mexico, June 2024. Associ- ation for Computational Linguistics. doi: 10. 10.18653/v1/2024 htt.:///w//22....nnnggg.... findings- naacll9.. URL org/2024 f findings naacl. 90/.
fional Linguisties: NAACL 2024, pp. 1406-1416,
https: https://aclantthlllee
Zhe Hui Hoo, Jane Candlish, and Dawn Teare. What is an roc curve?, 2017.
Jim Allen Wallace. Semantic caching for faster, smarter LLM apps, 7 2024. URL https: semantic-cadhe caching/. [Accessed 05-04-2025).
//redis. wwtpii//llllliiee http://ttttt---s--it---a-aaa-ee-
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pp. 611-626, 2023.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274-19286. PMLR, 2023.
Jaaxing Li, Chi Xu, Feng Wang, Isaac M von Riedemann, Cong Zhang, and Jiangehuan Liu. Scalm: Towards semantic caching for automated chat services with large language models. arXiv preprint arXiv:2406. 240.0025000000055... 2024.
Lin Liu, Jiajun Meng, and Yongliang Yang. Lim technologies and information search. Journal of Economy and Technology, 2:269-277. 2024a.
Shu Liu, Asim Biswal, Audrey Cheng, Xiangxi Mo, Shiyi Cao, Joseph E Gonzalez, Ion Stoica, and Matei Zaharia. Optimizing Ilm queries in relational workloads. arXiv preprint arXiv:2403.05821, 2024b.
Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4))824-836, 2018
Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly-labeled reviews and fine-grained aspects. In Proceedings of the 2019 conference empirical methods in natural languuge processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP)) pp. 197, 2019.
James Jie Pan, Jianguo Wang, and Guoliang Li. Survey vector database management systems. The VLDB Journal, 13951155511 2024.
12

---

Published as a conference paper at ICLR 2026
Kamran Razi, Anila Joshi, Sungmin Hong, and Yash Shah. Build read-through semantic cache with Amazon OpenSearch Serverless and Amazon Bedrock, 11 2024. URL https://wwa amaz on he-wi wwt.aarrrmazzoo--eeeeeerrr--eee 17-01-2025].
cac amazon- aand-amazoo-beerrokeee bedrock/. [Accessed
Navid Rekabsaz, Mihai Lupu, and Allan Hanbury. Exploration of threshold for similarity based on uncertainty in word embedding. In Advances in Information Retrieval: 39th European Conference on IR Research, ECIR 2017, Aberdeen, UK, April 8-13, 2017, Proceedings 39, pp. 396-409. Springer, 2017.
Ethan M Rudd, Lalit P Jain, Walter J Scheirer, and Terrance E Boult. The extreme value machine. IEEE transactions on pattern analysis and machine intelligence, 40(3):762-768, 2017.
Saurabh Shahane. Ecommerce text classification, 10 2023. URL htts:/// www.wwww........... [Accessed
om. /t///aaa.......oooo. datastts httpe/////aaaaaaaaaaaaaa//eeeeee wttp://reeeeeeetteeeassasseeaeae
12-11-2024).
Tomshapland Sudarsan and MasayaNishimaki, Optimize azure openai applications with semantic caching, Apr 2024. URL
mi micoosoft.......m
architectureblog wwtiii/e//oiiiieeiieeeeeeeeeeeee azure openai cetpdd-pppppiaiiiio with semanti 4-caching/4416866) [Accessed 12-11-2024).
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsenseqq:: A question answering challenge targeting commonsense knowledge. arXiv preprint arXiv:1811.0099 2018.
Sean Wallis. Binomial confidence intervals and contingency tests: Mathematical fundamentals and the evaluation of alternative methods. Journal of Quantitative Linguistics, 20(3):178 208, 2013. doi: 10. 10.0000099296674.211379999999999
Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei. Text embeddings by weakly- suakll-se contrastive pre-training. arXiv preprint arXiv:22122.03533, 2022.
Liang Wang, Nan Yang, Xiaolong Huang, Linjun Yang, Rangan Majumder, and Furu Wei. Large search model: Redefining search stack in the era of llms. In ACM SIGIR Forum, volume 57, pp. 1-16. ACM New York, NY, USA, 2024.
Haoyi Xiong, Jiang Bian, Yuchen Li, Xuhong Li, Mengnan Du Shuaiqiang Wang, Dawei Yin, and Sumi Helal. When search engine services meet large language models: visions and challenges. IEEE Transactions on Services Computing, 2024.
Qin Zhang, Linghan Xu, Qingming Tang, Jun Fang, Ying Nian Wu, Joe Tighe, and Yifan Xing. Threshold-consistent margin loss for open-world deep metric learning. arXiv preprint arX1v:2307.04047, 2023a.
Qinghua Zhang, Chengying Wu, Shuyin Xia, Fan Zhao, Man Gao, Yunlong Cheng, and Guoyin Wang. Incremental learning based on granular ball rough sets for classification in dynamic mixed-type decision system. IEEE Transactions on Knowledge and Data Engineering, 35(9)99319-9322 2023b.
Xin Zhang, Yanzhao Zhang, Dingkun Long, Wen Xie, Ziqi Dai, Jialong Tang, Huan Lin, Baosong Yang, Pengjun Xie, Fei Huang, et al. mgte: Generalized long-context text representation and reranking models for multilingual text retrieval. arXiv preprint arXiv:2407. 2024.
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. A survey of large language models. arXiv preprint arXiv:2303. 18223, 1(2), 2023.
Lianmin Zheng, Win Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging Ilm-as-a a--ud-----ude with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36:46595 2023a.
13

---

Published as a conference paper at ICLR 2026
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, lon Stoica, Joseph E Gonzalez, et al. Efficiently programming large language models using sglang. arXiv e-prints, pp. arXiv-2312, 2023b.
Hanlin Zhu, Banghua Zhu, and Jiantao Jiao, Efficient prompt caching via embedding similarity. arXiv preprint arXiv:2402.01113, 2024.
zilliztech. GPTCache: A Library for Creating Semantic Cache for LLM Queries. URL https: //github. com/ zilliztech GPTCache. [Accessed 23-01-2025).
14

---

Published as a conference paper at ICLR 2026
A NOTATION GLOSSARY
For clarity, we summarize the key symbols and functions used throughout the paper in Table The glossary covers cache contents, decision policies, probability functions, and modeling parameters. Each entry is accompanied by a short explanation and, where applicable, references to the defining equations, algorithms, or sections.
Table 1: glossary of notations used in the paper and their explanations
Notation
Explanation
r(z)
Response produced by the LLM for prompt
(xx
Vector embedding of prompt sr.
un(x)
Current nearest neighbor of æ in the cache; may change as the cache grows (see Equation 2).
s(x)
Similarity between prompt x and nn(x) (see Equation 4).
dx))
Correctness: rifr(nn())) = r(x), else (see Equation 4). Cache contents: (E(x;), r(z,), (zx)) (see Equation 3). Metadata for cached prompt .r; all observed (((r)),,((;)) with nn( 2i (see Equation 3).
D
O(ri)
P ((p(aahe(((x1))
Static-threshold policy used by existing systems.
P Pocacte ((n(z))), 8)
vCache policy using embedding-specie modeling under user- defined error bound (Section 4).
User-defined maximum eтror tolerance (see Section 4.1).
Pr(vCache(s) = r(x))
Probability that vCache returns the correct response (see Equa- tion 8).
(s(())
Required exploration probability to satisfy the guarantee (see Equa- tion 8).
Upper bound used for exploration probability (see Equation 11), Random draw used to realize the exploration decision (see Algo- rithm 2).
Uniform(O. (0,
((s())tt,)
Sigmoid likelihood modeling Pr(c(z) tion 9).
D) (see Equa-
1,7
True threshold (t) and slope (7) parameters of L (see Equation 9). MLE estimates of t and y based on O(n(2z) (see Equation 10). Conservative estimates of the logistic parameters 4,7, selected from the confidence band of the MLE estimates. These values are used compute and ensure that vCache respects the user-defined enror bound (see Equation 11).
15

---

Published as a conference paper at ICLR 2026
B VCACHE SEMANTIC CACHE ARCHITECTURE
Figure illustrates the vCache architecture. When a new prompt gets processed, it is first embedded into vector representation and queried against the vector database retrieve the nearest cached prompt. The similarity score and metadata of the retrieved embedding are passed to the similarity evaluator, which compares the correctness estimate against the user-defined error bound å (see vCache decision policy in Section 4.2), If the policy returns exploit, the cached response is retrieved from the response store and served immediately. the policy returns explore, the system performs an LLM inference to generate the true response, determines the correctness of the cached response with respect the newly generated one, updates the metadata of the nearest neighbor, adds the new embedding to the vector database, adds the generated response the response store, and returns it to the user (see Algorithm 1). the vector database, the green balls represent the confidence bounds specific to the currently processed prompt. Larger balls indicate lower thresholds (more conservative exploitation). In comparison, smaller balls correspond to higher thresholds (more conservative exploration).
Reburn Responsc
Error Bound: 1%
User
Cache
Recsive Prompt Request
Embedding Generator
Retrieve Similar Embedding
M
Vector Databuse
Response Store
ID
Ciccee Zesparte
Thè in iigtet
Toimplenet cless
Is Hit?
Similarity
Evaluator
a stayy
Miss?
Inference Server
Add Lobel Firbesiding
Add LLM Responae
Figure 6: Workflow of the vCache architecture. Prompts embedded, nearest neighbors retrieved, and the decision policy selects between exploiting a cached response or exploring via an LLM inference while ensuring the user-defined error bound 8.
16

---

Published as a conference paper at ICLR 2026
C VCACHE MODELING PROOF
We provide the proof for Theorem 4.1 in this section.
Recall we use the following notation in the paper,
x prompt under consideration
D data inserted into the cache
(s)))) minimum probability of exploration associated with embedding nn(x)
similarity value s(x)
Pr. 1
Computing the exact probability Pr(c(z) 1 D, is expensive, we derive simpler upper bound. If we have an upper bound, then computing an upper bound for Tan(x) (s(x)) is straightforward.
Lemma C.1 (Upper-Bounding r). if Pr((((()) = D x) 2 then,
Tun(a)
(un(a)(s(z)) (s(x)) < 1
Proof. Rewrite r to isolate the unknown probability:
(on(w)(((z)) (1 8) -r(cc())11[,,z)
1 Pr(e(z)=1[D,4)
(13)
5
Pr(c(x)=1(Dpx)
Next, suppose have known lower bound
(e(c(x)=1120) a.
Then
1 Pr(c(x)=
= = D,z) < 1 1-a;
and since 8 > 0, it follows that
2
(14)
Pr Prp(P (c(c(z) D)
1 1-a
Hence, to guarantee the exploration probability meets т, suffices to ensure
Prexplore (I, D.)) 2 +' = 5
Tnn(z)(((x)),
(15)
1
Lemma C.2 Hlower-Bounding the MLE estimates computed as,
Probability). Given let fan(e) and Am)(r) be
( (og(C(((())))) ((--c) log(1 - C(s,t,
Eun(a); Pau(z) arg min E (s,c)EO
(16)
Let t" and 7t be the true parameters such that L(s(x), (is(x))t,77))) ) is the true probability of correct cache hits. Consider an arbitrary 10. Let t be such that,
Pr(t" +' <T)CE
(17)
Then,
Pr(c(x) 11D, x)) 2 ()(()())
(18)
17

---

Published as a conference paper at ICLR 2026
Proof. By the law of total probability:
Pr([()== 1(D,
Pr(t" > +11"" <)²) P
<)))
+ +Pr(-(l" > >1'17" <T))
Pr((d) 51,7"
(19)
Pr(-(1' > >''l"*
(1 -) Pr((e(z) = ",,,t""s',"
(1 (1-c) Pr(c(x) =1 D. t' st,n" 27).
(1-6) c)
Pr(t" =t, 7/1 s 7 Pr(c(x) a, = 3))dddy
{ Pr(l" ,,, 7/1 11,7 x')dtdr))
(1- e)
inf 1S0,72
Pr(c(x) 1|2, xz,
(1 e) inf
Pr(c(x) = z,t)
= (1 ))
inf
((x,t,))
(1 c) C(x,t/,,
(20)
since, L(x, 7) < C(x, 12, 7), Vx. t1 >
to and ((r,t,m) < C(I,t, Vz. < <2
Combining these results lets us set
a = (1-6) ((x,lin)
(e)
(21)
and then use 7'. To find the best r' closest to the actual lower bound of exploration probability, we search for the minimum over the entire range e 10,1) Thus,
5
7' min cE(0.1)
1- (1- ((s
(22)
Confidence Bound Optimal Threshold To find t', 7 from the estimated i, 9, the confidence intervals by assuming a uniform prior on t and 7* Since, under uniform prior the distributions of Pr(t*(f) and Pr(t,t") are the same,
Pr(t")f) Pr(fft))P( Pr((t)
Pr(1)
(23)
Pr((1)0) Pr(()())
Pr(t*)f) Pr(î)t))
Thus we can obtain n using CDF (I"",,
In our experiments, we only use confidence intervals for ł, i.e., we use the t' parameter to adjust the likelihood. We estimate and use the point estimate y for 7-
D CONVERGENCE SPEED ESTIMATION
For each cached prompt y nn(x), vCache fits the sigmoid model L(s(x), (,7) the meta-data Ozy). Under the standard regularity assumptions for logistic regression, the MLE (fy, fy) converges
18

---

Published as a conference paper at ICLR 2026
1.0
1.0
Probability Correctiess
observations
Probability of Correctiess
observations
0.8
0.6
0.6
0.2
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4 Similarity
0.6
0.8
1.0
Similarity (s)
Figure Empirical probability of correctness as function of similarity 8 for the two cached embeddings with the largest numbers of labeled observations (42 and 33) in SemBenchmarkLmmAree with soxt-embeddinng---oe --mall and GPT-4. -nano. We estimate Pr(c = 8, nn(x)) using a ID k-NN smoother with k = In both cases the curve is monotone and approximately sigmoidal in s, supporting the per-embedding sigmoid model [(s(x), i, 7) in Eq. 9.
to the true ambedding-speeiine parameters (fy:7y) Tyy the usual parametric rate O(1/ (T1/ where By denotes the number of explored queries whose nearest neighbor is y. Any embedding-specine threshold derived from this model (e.g., the similarity at which Pr(c(x)
I, D) exceeds 1 5, or the required exploration probability Tna(=) (s(z))) is smooth function of (ly, 7/) and therefore inherits the same (11/ convergence rate via the delta method. Intuitively, as vCache collects more labels for given neighbor, the decision boundary t and the corresponding policy R(Caeb(s((r)) (nn()))), 5) stabilize at this standard parametric speed.
E EMPIRICAL JUSTIFFCATII OF THE SIGMOID MODEL
We model, for each cached embedding nn(x), the probability Pr(c(x) = x. D) function of similarity s(x) using the logistic family. We require the following structural properties from [(s(a), 1) monotonicity in similarity, 2) boundedness in [0, 1J. and 3) low-dimensional parameterization so that we can obtain tight confidence bands for (t,r) from the relatively small observation sets Onn(z). The logistic sigmoid is canonical choice satisfying these properties and allows efficient MIEE
To empirically
configuration with eext-embedding---smee and GPT-4.1-nano We randomly select and evaluation run and for each cached embedding we collect all observed pairs (s(z), c(x)) E Onn(a)) where s(x) the similarity between and nn(z) and c(x) E {0. 1} indicates whether returning the cached response was correct. Figure 7 shows. for the two embeddings with the largest numbers of labeled observations (42 and 33, respectively). a 1D k--N estimate (k 5) of Pr(c=
validate this choice, we analyze the SemBenchnarkk.m
8, nn(x)) ) as function of similarity 8. Both curves are monotone and exhibit S-shaped transition from low to high correctness as similarity increases, which is the behavior that Eq. 9 is designed to capture for each nn(xx) and then feed into (=x))) and f in Eq. 9 and Eq. 11.
Figure shows an aggregate view across all cached embeddings in the same configuration. We all (s(z), ((()) pairs by similarity and plot the empirical correctness probability Pr(c = 1 s) per bin. The resulting curve is again monotone and clearly S-shaped, with low correctness at small similarity, rapid increase in mid-range similarity region, and saturation near at high similarity.
ADDITIONAL ACCURACY, LATENCY, AND BASELINE EVALUATIONS
F.I SUMCACHHISEARCHQUERRISS BENCHMARK
We discuss the SemCachhSearchQuerree benchmark, focusing understanding the limitations of Static-treshole caching. We highlight why fixed thresholds fail to maintain reliable error guarantees scale and how vache addresses this issue through dynamic, embedding-specifff thresholding.
19

---

Published as a conference paper at ICLR 2026
Probabiltty of correctnesss
0.4
0.2
0.0
0.0
0.2
0.4
0.6 0.8 1.0
Similarity
Figure 8: Aggregate empirical correctness probability as a function of similarity s over all cached embeddings in SemBenchnarkLmAAee
with cext-embedding---smme (s(z), c(x)) pairs by similarity and plot the fraction correct reuse decisions per bin. The resulting curve monotone and clearly S-shaped, with low correctness at low similarity, a sharp increase in a mid-similarity region, and saturation at high similarity, which matches the qualitative behavior modeled by the sigmoid family in Eq. 9.
and GPT-4.I-nano. We bin all
vCache respects user-defined error-rate requirements We evaluate whether vCache satisfies the user-defined error rate while maintaining competitive performance. As shown in Figure 4, vCache consistently remains below the specified error bound across all tested 8 values. Moreover, the error rate stabilizes, vCache continues to improve its cache hit rate (Figure 4, right). In contrast, GPTCache exhibits increasing error rates as the sample size grows, despite improved hit rates. This trend reflects fundamental limitation of static thresholds: maintaining bounded error rate requires continuously increasing the threshold. Over time, no static threshold below 1.0 may suffice satisfy strict error constraint, making such systems difficult to tune and unreliable at scale.
Dynamic and embedding-speciffi thresholds are superior to static thresholds We evaluate whether dynamic, embedding-speccfff thresholds yield better long-term performance than static thresholding. To this end, we compare vCache against GPTCache by varying static similarity thresholds and vCache's maximum error rate bound 8. Each point Figure 5 reflects a complete evaluation over the SemCCchhSearrhhuuerie benchmark, enabling direct Pareto comparison. Static- threshold configurations achieve lower cache hit rates and higher error rates than vCache under equivalent evaluation settings. As shown in Figure 4, GPTCache has an increasing error rate as the sample size grows because the threshold remains fixed (both cache hit rate and error rate rise together). As result, the GPTCache curve in the middle plot (cache hit vs. error rate) is expected to shift up and to the right, while the curve the right plot (error rate vs. latency) shifts up and to the left. This trend suggests that static threshold below 1.0 maintain bounded error as prompt diversity increases (see the threshold of 0.99, which yields an error rate of 1.7% after 150k samples). In contrast, vCache learns its threshold online and per embedding, allowing enforce the етrоr constraint while gradually improving cache hit rate.
F.2 SEMCACHECOMBO BENCIIMARK
VCache respects user-defined error-rate requirements on SemCacheCombo Figure 4 evaluates whether vCache satisfies the user-defined error rate on the SemCacheCombo benchmark. Across all tested values, the realized error of vCache remains below the requested bound, confirming that the learned thresholds reliably enforce the target еттоr rate. As more samples are processed, vCache maintains its empirical error while steadily increasing cache hit rate, indicating ongoing learning from additional data. In contrast, GPTCache with a fixed similarity threshold of 0.83 exhibits growth in both error rate and hit rate the sample size increases.
20

---

Published as a conference paper at ICLR 2026
Computation Latency in Seconds
Regression Line Stoope55.335eeee
Latency (sec)
0.0020
0.0015
0
5000
10000
15000
20000
25000
30000
35000
40000
Sample Size
Figure 9: Empirical latency computing T in Algorithm as a function of sample size. The fitted regression line (slope = 5.5 x 10 10-19) shows that the cost is effectively constant, adding at most 1.5 ms (< 0.0015 s) per update.
Dynamic, embedding-speciific thresholds yield better trade-off's than static thresholds on Sem- CacheCombo Figure 5 summarizes the resulting trade-off's by varying vCache's error bound d and GPTCache's 's static similarity threshold. Each point corresponds to a full evaluation on Sem- CacheCombo, enabling direct Pareto comparison. vCache traces strictly better frontier: it achieves higher cache hit rates at the same error level, and lower error for comparable hit rates and latency. For example, vCache attains up to 12.5x higher cache hit rates than the best static-threshold configuration while still satisfying the user-defined error bound. At matched average latency, vCache consistently delivers lower error than GPTCache. These results show that dynamic, bebedddingsppciiin thresholds provide superior accuracy-efficiency trade-offs to static thresholds.
F.3 SEMCACHELMARENT WITH OPENAI EMBEDDINGS
vCache respects user-defined error-rate requirements on SemCacheLMMAren Figure 4 evalu- ates whether vCache satisfies the user-defined error rate on the SemCacheLLMArent benchmark. Across all tested 8 values, the realized error rate of vCache remains below the user-defined target, confirming that the learned thresholds enforce the desired bound. As the sample size grows, vCache further reduces its empirical error while steadily increasing cache hit rate, indicating that it continues to learn from additional data. In contrast, GPTCache with a fixed similarity threshold of 0.98 exhibits growth in both error rate and hit rate more prompts arrive. Figure outlines Pareto comparison across all feasible thresholds.
Dynamic, embedding-speciffe thresholds yield better trade-offs than static thresholds Figure summarizes the overall accuracy-effiiinncy trade-offs SemCacheLMAreena by varying vCache's 's error bound and GPTCache's static similarity threshold. Each point represents a complete evaluation run, enabling direct Pareto comparison. vCache traces substantially higher cache hit rates at the same error level and much lower error for comparable hit rates and latency. For example, vCache reaches a cache hit rate of 57% while keeping the error rate below 0.5%, whereas GPTCache requires an cader-of-magnitude higher error to obtain similar hit rates. At matched latency, vCache achieves up 26x lower error than the best static configuration. These outcomes demonstrate that dynamic. embedding-speree thresholds are better suited than static thresholds for maintaining strict error guarantees while exploiting semantic redundancy.
strietly better frontier: it achieves
F.4 T COMPUTATION OVERHEAD
Figure reports the latency of computing (Algorithm 1) on the SemCacheLMArem benchmark as function of the current sample size. Each point corresponds to one update step, and the solid red line is a linear regression fit. The points form a tight horizontal band and the regression slope is effectively zero (== 5.5 10 10 sec per sample), indicating that be computed in constant time. Across all sample sizes, the latency remains below 1.5 ms, indicating that the overhead of computing is negligible.
21

---

Published as a conference paper at ICLR 2026
Embedding Computation Latency Distribution
0.016
Latency (seconds)
0.014
0.010
0.008
0.006
GTE
GTE
E5 Large v2
Liama 88
ES Large v2
Figure 10: Embedding computation latency distributions across models, shown as 95th percentile whisker plots. GTE_FT GteLargeENv1-5 (Zhang et al., 2024) fine-tuned (Zhu et al., 2024). E5 Large v2 FT E5-large-v? v2 (Wang et al., 2022) fine-tuned (Zhu al., 2024).
F.5 EMBEDDING GENERATION OVERHEAD
Semantic caches incur additional latency due to embedding computation, which must be evaluated in relation to the cost of LLM inference. To quantify this overhead, we compare the embedding latencies of four models the inference latency of Llama 3.
All experiments are conducted on a system with an Intel Xeon Platinum 8570 CPU and an NVIDIA Blackwell GPU with 192 GB of memory. The results show that embedding computation is signifi- cantly faster than model inference, confirming its applicability in caching pipelines.
F.6 LOGISTIC REGRESSION LATENCY OVERHEAD
Since vCache performs threshold estimation online for every request, the efficiency of logistic regression directly impacts scalability. In experiments, yielding an average latency of 0.0017 seconds on the SemBenchmark ensures that online modeling does not introduce noticeable overhead and can scale to large caches.
sklearn.linear -odee model on CPU,
Its negligible latency
F.7 VCACHE IN COMBINATION WITH VLLM
vCache is orthogonal to inference optimization systems, semantic prompt caching reuses responses for semantically similar prompts rather than accelerating inference itself. When cache miss occurs, vCache directly benefits from systems such vL..M (Kwon al., 2023) SGLang (Zheng et al., 2023b), which reduce model latency. To validate this, we hosted I.LMMa 3.1 70B with vL.LM on two NVIDIA Blackwell GPUs and compared inference latency with and without vCache. For vCache, we additionally ran the GteLargeENv 1_5 embedding model on the same machine. Evaluation was conducted on 45k samples from the SemCCaheCCassificatio benchmark.
Table 2: A comparison of overall runtime, latency, cache hit rate, and enror rate with and without vCache under different error tolerances
Overall Duration
Avg. LLM Inference Latency
Avg. Emb. Latency
Cache Hit Rate
Error
Baseline
Config
Rate
vLLM
240 min
0.32 sec
0.0%
0.0%
8 = 0.01
214 min
0.32 sec
0.018 sec
18.1%
0.4%
VLLM
8 0.02
170 min
0.32 sec
0.018 sec
35.5%
1.2%
+ vCache
5 = 0.03
160 min
0.32 sec
0.018 sec
40.2%
1.4%
22

---

Published as a conference paper at ICLR 2026
Despite the additional embedding overhead, vCache substantially reduces end-to-end latency by avoiding repeated LLM inferences. This demonstrates that vCache is complementary to inference optimization systems such vLLM.
F.8 ADDITIONAL. BASELINE EVALUATIONS
vCache is the first adaptive, probabilistic, and Bayesian method for semantic caching. The most competitive alternatives are static threshold methods, which we extend with several additional baselines for completeness. The landscape of approaches can be ordered from naive advanced as follows:
GS:
Global and Static threshold (i.e., GPTCache).
GD:
Global and Dynamic threshold (vCache with global threshold).
LS:
Per-embedding (Local) and Static threshold.
LD: Per-embedding (Local) and Dynamic threshold:
LD1: Logistic regression compute the threshold (f).
LD2: Logistic regression sigmoid fit to model correctness probability.
LD3:
Logistic regression sigmoid fit with confidence intervals and guarantees (vCache).
We implement all baselines and perform ablations the E5-1arge-v2 embedding model, OpenAl GPT-4o 4o mini LLM, and the SemCache Lmårena benchmark. For non-adaptive baselines (LD) and LD2), we select the threshold or values that produced error rates closest their observed performance. Results are shown in Table 3.
Table 3: A comparison of error rate, cache hit rate, and qualitative observations across baselines
Threshold/ Delta
Error Rate
Cache hit Rate
Baseline
Comments and Observations
0.99
2.5%
37%
No guarantee and worst trade-off.
GS
0.98
4.1%
53%
0.97
5.2%
67%
0.02
1.3%
14%
Due to the large overlap between incorrect and correct samples given similarity (see 3), the optimal threshold converges to 1.0, yielding low cache hits.
GD
0.03
2.5%
26%
0.05
4.3%
45%
LS
Impossible to compute threshold for every embedding priori.
LD1
2.6%
70%
No guarantees and no error-rate fine-tuning.
LD2
2.1%
68%
No guarantees and error-rate fine-tuning.
0.02
0.5%
41%
Guarantees and beats both SOTA and GD baselines.
LD3
0.03
1.1%
46%
0.05
2.0%
54%
This ablation underlines that (1) semantic caches benefit from embedding-specific thresholds, and (2) probabilistic modeling is required to satisfy user-defined eтror bounds and ensure predictability. Notably, only vCache provides guarantees. The importance of guarantees cannot be overstated, in practice, the absence of correctness guarantees has been primary reason for the failure of semantic caching deployments in industry.
23

---

Published as a conference paper at ICLR 2026
F.9 THRESHOLD DILEMMA
To analyze the relationship between similarity scores s(x) and cache correctness c(x). we conduct an experiment on the 45,000 entries of the SemCuchhClassifeation benchmark using an error tolerance of 8 = 0.02 (2%). For each cached embedding 2,, we record the observations (xx)) and the empirically estimated optimal threshold f...
In the top plot of Figure 3, we separate observations into two sets: one where c(x) = (correct cache hit) and another where c(x) = 0 (incorrect hit). We plot the kernel density functions (KDF), also known as kernel density estimations (KDE), to visualize the distribution of correct and incorrect observations. The result shows that correct and incorrect observations are nearly indistinguishable in similarity space, with substantial overlap and similar means (0.84 vs. 0.85). This illustrates that one single similarity threshold is not reliable decision boundary.
The bottom plot shows a histogram of the optimal threshold values computed per embedding. The thresholds span range, from 0.71 to 1.0, indicating that no single similarity threshold suffice across embeddings. A threshold set too low increases the risk of incorrect cache hits; a threshold set too high limits cache hits. Together, these results motivate the need for embedding-speciin and dynamically learned thresholds to ensure interpretable and reliable performance.
G HYPERPARAMETES GUIDANCE
VCache is designed to be simple to configure, with the error rate bound ò as its primary hyperparameter. We recommend setting this bound based the desired trade-off between accuracy and cost. For high-accuracy applications (e.g., customer support or safety-critical systems), a conservative value such as 0.5% can be appropriate. For use cases with higher tolerance for occasional errors and stronger cost or latency constraints (e.g.. search or summarization), values around 2-3% may be reasonable. Ultimately, the choice depends on petficaaioo-speciife requirements.
H BENCHMARK CREATION
To the best of our knowledge, no open-sourss benchmarks currently exist for evaluating the perfor- mance and applicability of semantic caching systems. To address this gap, we construct and release four diverse benchmarks each designed reflect a distinct real-world use case: classification tasks, conversational chatbots, and search engines. This section describes the motivation and construction process behind each benchmark.
H.1 SENCACHHCLASSSHICATIO BENCHMARK
The SemCache SemCaacheCusssfictton benchmark is designed to evaluate semantic caching in structured classification settings, such as those found in modern database environments (Liu et al., 2024b). Several database systems, including Databricks, Snowflake, and AWS, have introduced LLM-based extensions to SQL via beer--efined Functions (UDFs), enabling capabilities beyond traditional SQL semantics (Liu et al., 2024b). However, LLMM-based UDFs are inherently non-deterministic, execute row by row, and pose integration challenges for parallelization and query optimization (Franz al., 2024). When table rows contain semantically similar values, semantic caching can reduce the frequency of LLM invocations, thereby improving both latency and cost. This benchmark captures such use cases, where slight variations in phrasing should require repeated inference.
The benchmark consists of 45,000 short-form prompts with fixed output label space. Each example follows a prompt-response format, where the prompt expresses a classification query and the ex- pected response is one-word label. The benchmark combines three diverse classification datasets: CA (Talmor et al., 2018), Ecommerce Categorization (Saurabh Shahane, 2023), and Amazon Instant Video Review (Ni et al., 2019). This dataset composition models out-of out-of-distribution data because the three sources differ significantly in domain, style, and vocabulary, forcing semantic caching methods to generalize beyond a single homogeneous dataset. Sample prompts and response
24

---

Published as a conference paper at ICLR 2026
formats from each dataset are shown below, and Table 4 summarizes label distributions across the benchmark.
A sample entry from the Ecommerce Categorization (Saurabh Shahane, 2023) dataset:
"prompt": "Which category does the text belong to? Text: <text >",
Noutput_formati "Answer with 'Books', 'Electronics', Household', or 'Clothing Accessories' only"
A sample entry from the Commonsense QA Talmor et al. (2018) dataset:
"prompt": "What is the main subject of the following question? Question: <question>",
turtputfformat". "Answer with only one of the words of this set [' d'poople,, 'potato', ' 'competing', 'snake', 'lizard', x 'ood" car', 'water', 'student', 'crab', 'children', 'killing', animals', 'ficus', 'horse', 'fox', 'cat', 'weasel', 'shark', person', 'human']
sample entry from the Amazon Instant Video Review Ni et (2019) dataset:
"prompt": "Is this review friendly? Review: <review>", "output_format": "Answer with 'yes' or 'no' only"
The benchmark enables controlled evaluation of semantic caching strategies, especially in cases where small changes in input phrasing must still map to the same output class. Its fixed label format makes it particularly useful for evaluating systems like vCache, which rely correctness guarantees under threshold uncertainty. Table 4 summarizes the label distributions for the three subtasks the SemCCacheClasification benchmark.
25

---

Published as a conference paper at ICLR 2026
Number Classes
300
200
100
10
15
Number of Entries per Class
Figure 11: Distribution of class sizes in the SemCacheLMMArena benchmark. Each class corresponds to unique user prompt and contains 2-24 semantically similar variants.
Response
Count
Response
Count
Response
Count
person
2,806
Books
6,000
yes
10,000
people
625
Clothing 6,000
no
10,000
human
400
Electronics
6,000
competing
272
Household
2,000
(c) Amazon Instant Video.
animals
225
food
202
(b) Ecommerce.
car
125
water
100
student
79
children
32
killing
27
horse
24
lizard
13
potato
13
fox
11
cat
10
ficus
10
weasel
8
shark
8
crab 7
snake
(a) Commonsense QA.
Table 4: Response distribution across three datasets that form the SemnCacheClassfication benchmark.
H.2 SEMCACHELMARENA BENCHMARK
The SemCacheLLMArena benchmark designed evaluate semantic caching in chatbot environments, where users may issue semantically similar prompts with different phrasing. In such settings, caches must generalize across diverse surface forms while maintaining response correctness. This benchmark addresses these challenges by grouping semantically similar user inputs and testing whether caching systems can accurately reuse responses.
To construct the benchmark, we use the LM-Arena human preference dataset (Zheng et al., 2023a), which contains 100,000 real-world user queries. We randomly sample 3,500 distinct prompts, each of which defines a class. For each class, we generate between and 23 semantically similar variants using GPT-4. CPPT-4.Inaame -nano, resulting in a total of 60,000 prompts. A class ID assigned to each prompt to evaluate caching correctness: a cache hit is considered correct if the retrieved response belongs the same class as the query. Figure 11 shows the distribution of class sizes (number of prompts belonging to class), confirming broad variability in prompt paraphrasing. To support model-agnosta evaluation. we generate responses for all prompts using GPT-4. 1PTT-41--amm I-nano and GPT-4o-minn mini. The corresponding response length distributions are shown in Figure 12.
26

---

Published as a conference paper at ICLR 2026
GPT-4.1-nano
GPT-4o-mini
290.46
4000
3000
Median: 237.50
Median: 228.00
Frequency
3000
Frequency
Count
Count
2000
2000
1000
1000
0
200
400
600
800
1000
200
400
600
800
1000
Response Length (words)
Response Length (words)
Figure 12: Response length histogram for GPT-4.1-nan and GPT--4-mini on the Mem benchmark. Median and mean lengths are shown for each model.
H.3 SEMCACHISEEARCHQUUREES BENCHMARK
The SernCachhSSearchuuerree benchmark is designed to evaluate semantic caching in open-domain search applications. Large-scale search engines, such Google, increasingly rely on LLMs to generate direct answers to natural language queries (Liu et al., 2024a; Wang et al., 2024). While this improves experience, it introduces significant latency and cost, particularly the scale of millions of daily queries. Many queries issued to search engines are paraphrased variations of earlier inputs, making semantic caching a natural fit for reducing redundant LLM inference in this setting.
The benchmark is constructed from a filtered subset of the ORCAS dataset (Craswell et al., 2020), containing real-world search engine queries. We begin by sampling 500,000 queries and embedding each using the geeelargeee--1... embedding model (Zhang et al.. 2024). We then apply k-means clustering to group similar queries and retain the largest clusters, resulting in 150,000 entries. Within each cluster, we apply union-find algorithm guided by an I.M--based judge (GPTT-.1-nano)) to determine whether query pairs yield the same response. Sub-clusters identified this step define the equivalence classes used for caching evaluation. Figure 13 summarizes the benchmark properties, including class size distribution, frequent query terms, and statistics on the number of queries per class.
H.4 SEMCACHECOMBO BENCHMARK
We introduce the SemCacheCombo benchmark to evaluate semantic caching in workloads that contain both reusable responses and unique, non-reusable responses. The dataset is constructed by combining two sources into single sequence of 27,500 prompts. First, we take the SemCacheL.MA benchmark and select one representative prompt from each of its 3,500 semantic classes. Because each prompt represents different cluster, these 3,500 queries are pairwise semantically distinct and should not share reusable response. From the perspective of semantic cache, every SemCachel.MA Arena prompt is therefore expected to result in cache miss; any cache hit on this subset is, by definition, an incorrect reuse. Second, we append 24,000 prompts from the SemCacheClassificaton benchmark. Correct cache hits may only occur within this set of prompts. Next, randomly shuffle all 27,500 prompts.
27

---

Published as a conference paper at ICLR 2026
Distribution of Class Sizes
Top 20 Most Common Words in Queries
2500
2000
1500
Frequency
10000
Number of
7500
500
2500
downlchh bank
onlig
crede
Pree
Kinee
change
baterein
Querles
Words
Top Largest
80
11148
106187
Number Querites
60
7038
98639 (65, 1%11
5a954 159
80
170
6813 (4.5%)
20
queries: 150000
unique set
10
15
20
Set with muitiple querles: (20.3%)
Class Rank
Largest class quaries
Figure 13: Descriptive statistics for the SemCCacheSearchuueries benchmark. Top left: Most classes contain exactly two queries. Top right: The word best appears 16,000 of the 150,000 queries. Bottom left: The largest class contains 90 semantically equivalent queries. Bottom right: 59.3% of all classes contain more than eight queries, indicating substantial intra-class variability.
28


Reviews:
[{"review_id": "ZH52wsqNxp", "reviewer": "Reviewer_5kcm", "summary": "This paper proposes vCache, a semantic LLM caching method that guarantees a user-defined error rate, based on the previous work of GPTCache, a semantic LLM caching method to optimize LLM cost and latency. This work contributes to the domain of LLM caching by introducing per-embedding dynamic threshold, which was improved from the static threshold of GPTCache.", "questions": "•\tWere comparative experiments conducted with different embedding models? An analysis of the relationship between the performance of the embedding model and the performance gains from vCache would better substantiate the \"Model-Agnostic\" claim. Beyond the GteLarge and E5-large models presented, were experiments with other BERT models—such as multilingual variants or those employing improved techniques—considered?\n•\tWhen a new embedding is added to the cache, how many observations are required for vCache to learn a stable threshold? I am curious about the analysis of performance degradation during the initial learning phase (the cold-start problem).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThis study algorithmically improves from the existing threshold-based retrieval methods such as GPTCache using a novel approach. It theoretically guarantees a desired error rate and demonstrates improved performance across several metrics by introducing a verified semantic cache.\n2.\tAs an online learning algorithm, the proposed method achieves strong results without fine-tuning the embedding model, thus requiring no additional training.\n3.\tTo validate the effectiveness of the proposed methodology and foster future research, the authors have constructed and publicly released three new benchmark datasets (SemCacheClassification, SemCacheLMArena, and SemCacheSearchQueries) that reflect real-world caching scenarios.", "weaknesses": "1.\tSince vCache is still a semantic caching technique, there is an insufficient evaluation of its effectiveness concerning the capability and performance across the underlying embedding model (e.g., BERT). A comparative analysis using various embedding models is needed to substantiate the \"Model-Agnostic\" claim, which currently lacks sufficient analysis.\n2.\tWhile the paper discusses the trade-off between accuracy and cost, the benchmark results show a trade-off between Cache Hit Rate and Error Rate when compared to GPTCache. For instance, in Appendix D.5, the best-case for GPTCache (GS) shows a 5.2% error rate with a 67% hit rate, whereas vCache (LD3) achieves a 2.0% error rate with a 54% hit rate. Although vCache has the distinct advantage of reliably guaranteeing a user-defined error rate (e.g., 2.0%), the lack of in-depth analysis on this trade-off makes it difficult to conclude its superiority across all scenarios. Combined with Weakness 1, this property raises questions about whether the improvement of vCache against GPTCache is marginal or not.\n3.\tAs mentioned in the limitations section, the evaluation relies on an LLM-as-a-judge for benchmarks except SemCacheClassification, which has a clearly defined correctness criterion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BpYLamEbbs", "reviewer": "Reviewer_yfEW", "summary": "The paper proposes vCache, a novel semantic caching system for LLMs that provides user-defined error rate guarantees while learning embedding-specific thresholds online. The key innovation is replacing static global thresholds with dynamic, per-embedding thresholds estimated through an online learning algorithm that models the probability of correctness using sigmoid functions. The method is evaluated on three benchmarks across different embedding models and LLMs, demonstrating superior performance compared to static threshold baselines.", "questions": "Thank you for your submission. I appreciate the motivation behind providing formal correctness guarantees for semantic caching systems, which is indeed a significant limitation of existing approaches. The experimental validation across multiple benchmarks and the introduction of new evaluation datasets are valuable contributions. However, several aspects of the paper require clarification and the technical approach raises some concerns:\n\n- The sigmoid modeling assumption (Equation 9) is quite strong but not well justified. Why should the relationship between similarity and correctness follow a sigmoid specifically? Have you experimented with other parametric families or non-parametric approaches?\n- The confidence band computation for parameters t and γ (mentioned in Section 4.2 and relegated to Appendix C) is crucial for the guarantees but insufficiently explained in the main text. How sensitive are the guarantees to the choice of confidence level ε?\n- Algorithm 2 shows that τ is computed by minimizing over ε ∈ [0,1], but this seems computationally expensive for online inference. What is the actual computational overhead of this optimization step?\n- The paper claims vCache \"consistently meets the specified error bounds\" but Figure 4 shows the actual error rate is noticeably below the specified δ. This suggests the method might be overly conservative, potentially sacrificing cache hit rate for unnecessary safety margins. Can you quantify this conservatism?\n- The comparison with GPTCache is somewhat unfair since GPTCache doesn't attempt to provide error guarantees. A more relevant baseline would be other adaptive thresholding methods from the retrieval literature adapted to this setting.\n- The evaluation focuses on relatively simple benchmarks (classification, search queries). How does vCache perform on more complex scenarios like multi-turn conversations or reasoning tasks where semantic similarity becomes more nuanced?\n- The i.i.d. assumption for incoming prompts is quite restrictive in practice. Real-world query distributions often exhibit temporal correlations, user-specific patterns, and concept drift. How robust is vCache to violations of this assumption?\n- Figure 3's motivation is compelling, but the connection to the proposed solution could be clearer. It shows the problem but doesn't intuitively explain why sigmoid modeling would solve it.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper addresses a practical challenge of the semantic prompt caching \n- The proposed method is well-motivated", "weaknesses": "- The writing is a bit repetitive and could be streamlined", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wZtCJsq6kt", "reviewer": "Reviewer_e1XS", "summary": "This paper proposes vCache, a caching system that optimizes GPT-Cache and dynamically returned the cached responses subjected to the pre-defined error rate. Compared to the previous works that relies on a static threshold for all incoming queries and all cached responses, this paper adopts online learning to estimate a threshold for each cached response. To help evaluate the performance of GPT-cache style caching systems, the author generates three benchmarks to help evaluate the performance. Abundant empirical experiments on different models show the effectiveness of this method.", "questions": "- For creating the dataset SemCacheLMArena, how to ensure the sampled prompts are not really distinct? \n- Where do you define? I guess it's time per response?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper tackles on an important topic of GPT-cache and provides unique perspectiives on how to optimize this problem. Static threshold is a fundmental problem that prevents GPT-cache for better selecting cached responses.\n- The evaluation is holistic and abundant. The author also presents large-scale benchmarks for helping research in this field.\n- Author also presents good theoretical guarantees for showing the effectiveness of this method,", "weaknesses": "- Dataset Generation neglects no match scenario. I checked the appendix about how the data is generated. For instance, for the SemCacheLMArena, 1 to 23 similar prompts will be generated. In reality, there could be many prompts where no similar answer in the cache can be fetched directly. I would suggest adding many prompts where no similar one variants are included should be helpful.\n- Though the experiments regarding error rate is abundant, more analysis of latencies and throughputs should be added.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cNO1vGEK2T", "reviewer": "Reviewer_sFQ7", "summary": "This paper proposes using dynamic thresholds for different prompts in semantic caching, thereby providing an error rate guarantee. Based on a sigmoid parametric model and observed samples, the proposed online learning algorithm continually estimates the optimal thresholds for cached prompts. Experimental results demonstrate its effectiveness in controlling error rates.", "questions": "See weaknesses", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is well structured and easy to follow.\n- Guaranteed error rate is a crucial issue for semantic caching, and the proposed online-learning-based dynamic threshold method provides a reasonable solution.", "weaknesses": "- Although vCache can guarantee the error rate of the semantic cache, it heavily relies on the observation of correctness (Algorithm 1, Line 8). In the experimental section, the authors propose using exact matching for short prompts and LLM inference for long prompts to determine correctness. The additional LLM inference introduces extra cost for the semantic cache, which undermines its practical value. Moreover, the LLM could make mistakes in judgment, making the guarantee unreliable.\n- Why is the actual error rate in Figure 4 much lower than $\\delta$? According to the guarantee, they should not differ by such a large margin.\n- Despite the controlled error rate, the risk of private data leakage still exists, which limits its practical adoption in industry.\n- Since LMArena contains many testing prompts, the high hit rate shown in Figure 4 might result from these testing cases. Can the authors provide details about the hit prompts for the three benchmarks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)