From Exact Hits to Close Enough: Semantic Caching for LLM Embeddings Dvir David Biton, Roy Friedman Abstract The rapid adoption of large language models (LLMs) has created demand for faster responses and lower costs. Semantic caching, reusing semantically similar requests via their embeddings, addresses this need but breaks classic cache assumptions and raises new challenges. In this paper, we explore offline policies for semantic caching, proving that implementing an optimal offline policy is NP-hard, and propose several polynomial-time heuristics. We also present online semantic aware cache policies that combine recency, frequency, and locality. Evaluations on diverse datasets show that while frequency based policies are strong baselines, our novel variant improves semantic accuracy. Our findings reveal effective strategies for current systems and highlight substantial headroom for future innovation. All code is open source. 1 Introduction Modern large language models (LLMs) rely on embedding methods to encode the semantic meaning of user queries into high-dimensional vectors. These embeddings enable efficient comparison of queries, making them a cornerstone of natural language processing tasks, such as question answering and semantic search. LLMs have gained wide adoption in the last few years although they suffer from high computational cost, as well as significant consumption of energy, memory, storage, and communication bandwidth. Caching is a known technique to alleviate such limitations, and has been applied successfully in a variety of domains. Recently there have been several attempts to apply caching to LLMs ( 3 ; 16 ; 37 ) . By encoding each query into an embedding and comparing it against cached embeddings, semantically similar requests are detected, which enables the system to return the previously computed answer, avoiding redundant inference and reducing overall latency and compute cost. Most of these works adopt a naïve or ad-hoc approach to managing the cache, i.e., for deciding which embeddings should be inserted into the cache, and once the cache is full, which should be evicted to make room for new ones. This is despite evidence from other domains that clever cache management can significantly improve caching benefits ( 31 ; 34 ; 12 ) . In particular, it is known that different workloads may yield significantly different hit rates depending on the cache management policy chosen. This has led to a plethora of cache management policies ( 19 ; 27 ; 1 ) as well as to various adaptive schemes and learning based schemes. However, a universally optimal cache management policy remains an open research challenge. Since semantically similar queries can be answered by the same response, despite the fact that syntactically they are not exactly the same, most LLM caching solutions rely on semantic caching , in which a query is considered a hit if the cache already includes the reply to some query such that the embedding vectors of both queries are “close enough” under some metric such as L2 norm or cosine similarity. The impact of this shift from exact match caching to semantic caching on the vast knowledge about caching and cache replacement policies is not clear a priori. Hence, in this work we take a systematic approach to studying LLM cache management and, in particular, what changes, if any, are needed when moving from exact matches to semantic caching. 1.1 Related Work Recent works, such as GPTCache ( 3 ) , have demonstrated the benefits of applying caching to LLM inference. GPTCache can be integrated with multiple embedding models, vector stores and cache management schemes. It supports LRU, LFU, FIFO, and Random by default. MeanCache is another recent cache for LLMs ( 16 ) , which applies lighter models than GPTCache. The work utilizes LRU as cache replacement, at least by default. For most of the workloads we have experimented with in this work, LRU is not a good cache management policy. GPTSemCache also applies caching to avoid repeated LLM API invocations ( 35 ) . They report a reduction in API calls by up to 68.8% across various query categories, with cache hit rates ranging from 61.6% to 68.8%, while achieving high accuracy. GPTSemCache relies on Redis to store cached data without any hard cache size limit, and therefore does not consider any replacement strategy. vCache ( 38 ) employs an online learning algorithm to estimate an optimal threshold for each cached prompt similarity bound. They assume an infinite cache size, rendering the replacement policy irrelevant. When the cache size matters, our work becomes complementary to vCache and can be integrated with it. Similarly, InstCache ( 45 ) and GenerativeCache ( 21 ) are additional LLM caching mechanisms that assume an infinite cache and therefore do not apply any replacement policy. The work of ( 44 ) studied how to minimize the cost of a cache based LLM system by learning the expected cost of various queries processing time, and integrating it with the Least Expected Cost policy and the Greedy Dual-Size with Frequency (GDSF) replacement algorithm. They assume an oracle that clusters semantically similar queries into equivalence groups, thereby ignoring the issue of having multiple cached vectors that can be considered a hit for the same query. In that sense, their work can be compared to our ClusterLFU and CRVB policies, which we have shown to be often suboptimal. RAGCache ( 24 ) caches RAG contents. It applies a novel prefix-aware Greedy-Dual-Size-Frequency replacement policy, and compares it to GDSF, LRU and LFU. Proximity ( 8 ) is another RAG cache project. The focus in Proximity is reducing the cache search time, which is obtained by dividing the cache into independent buckets, or sets, and applying a mapping mechanism like locality-sensitive hashing (LSH) that ensures that semantically similar vectors are placed in the same bucket. Then each bucket can be managed using its own policy. Currently, Proximity supports LRU and FIFO. Our work is therefore complementing to ( 8 ) , and our results can be applied for better selection of the replacement policies of the buckets of Proximity. Let us note that caching high-dimensional vectors for similarity search is not exclusive to NLP. It is also used in many applications such as recommender systems, reverse image search, and biological sequence analysis. 1.2 Summary of Contributions We show that the optimal clairvoyant caching algorithm, also known as Belady’s OPT or MIN, is no longer optimal in the context of semantic caching, and that computing the corresponding clairvoyant solution, which we term VOPT, is NP-hard. To address this, we propose and analyze three polynomial-time clairvoyant heuristics: Clustered Relaxed Vector Belady (CRVB), Volume Greedy Relaxed Vector Belady (FGRVB), and Time Greedy Relaxed Vector Belady (RGRVB). We compare these clairvoyant approaches against a broad range of established online cache management policies, adapted for semantic caching, across nine publicly available workloads. Our results show that frequency-based algorithms generally outperform other online approaches, with our novel SphereLFU achieving the highest accuracy. Also, in most workloads, the clairvoyant algorithms significantly outperform online policies, suggesting substantial remaining opportunities for innovation. 2 Preliminaries 2.1 Semantic Caching A semantic (vector) cache C is parameterized by ( i ) Dim - the dimensionality of each vector, ( ii ) N - the maximum number of vectors the cache can store, and ( iii ) D_{\text{thresh}} - a distance threshold. A stored vector within this distance from a request is considered a cache hit . Each stored vector is a tuple of Dim floats. In our evaluation, all vectors are L2-normalized to have unit magnitude, although this is not strictly required. The cache exposes two basic methods: Query: Given a vector V and an integer M , return the M or less vectors that are closest to V , restricted to those within a distance smaller than D_{\text{thresh}} . Update: Given a vector V, the cache is requested to store V. If the cache already contains N vectors, inserting the new vector requires evicting one of the stored vectors from the cache. The cache’s management policy decides which vectors are stored and evicted. For efficiency reasons, our cache implementation supports batches, i.e., querying for multiple vectors using a single request and caching multiple vectors with a single request. 2.2 Embedding Embedding methods aim to project high-dimensional textual data into vector representations that preserve semantic relationships. Sentence-BERT (SBERT) ( 36 ) is a widely used model of this kind, which offers a balanced tradeoff between semantic clustering quality and runtime efficiency. In our experiments, we normalize the embeddings so that their magnitude equals 1, and specifically use the all-MiniLM-L6-v2 variant, which produces 384-dimensional vectors. 2.3 Embeddings Similarity Embedding similarity is commonly measured using cosine similarity, with L2 distance serving as a closely related alternative ( 11 ) . In this work, we compute similarity using L2 distance. Our embeddings are normalized to have a magnitude of 1, therefore cosine similarity and L2 distance become equivalent up to a monotonic transformation, and the choice between them has no effect on the nearest neighbor results. For normalized embeddings, the L2 distance directly reflects angular similarity. Identical embeddings have distance 0 , while completely opposite embeddings have distance 2 . A distance of \sqrt{2} corresponds to orthogonal vectors, i.e., unrelated vectors. Distances between 0 and \sqrt{2} indicate increasing alignment: for example, an euclidean distance of 0.5 corresponds to a cosine similarity of about 0.875, meaning the vectors are close but not identical. Conversely, distances beyond \sqrt{2} indicate increasing opposition, with values approaching 2 representing strong dissimilarity. In this work, we utilized three normalized L2 distance thresholds ( D_{thresh} ): 0.5, 0.7, and 0.9, which correspond to cosine similarity scores of approximately 0.88, 0.75, and 0.60, respectively. While similarity thresholds are data dependent, we selected these values based on established benchmarks: 0.88 targets strict near-duplicate detection, 0.75 serves as a balanced baseline for semantic equivalence, and 0.60 functions as a high-recall filter for broader topical relevance ( 36 ; 10 ) . 3 Theoretical Analysis 3.1 OPT OPT, also called Belady’s optimal or MIN, is the clairvoyant cache policy that, upon a miss with a full cache, evicts the resident item whose next request occurs farthest into the future ( 6 ) . This rule provably minimizes total misses for any fixed capacity on a given finite request trace. Classic exchange-argument proofs show that any deviation cannot improve the miss count. Because it requires perfect future knowledge, OPT is not implementable online, but it serves as an oracle upper bound for evaluation and as a target for online policies. Computing OPT for a cache sized N and a known in advance trace of length n requires O(nlogN) . OPT defines the achievable frontier against which real policies are compared. As stated before, in semantic caching, a hit occurs if the requested vector lies within D_{\text{thresh}} of a cached vector. This heuristic breaks OPT’s optimality: consider a workload with two disjoint regions of requests, one dense and popular and the other sparse and unpopular. An OPT policy translated directly would fill the cache with vectors from the dense region, although only a handful are needed to cover that region. On the other hand, the sparse region will suffer unnecessary misses. This means we must redefine an optimal algorithm for semantic caching. 3.2 VOPT We define VOPT as an offline policy that achieves the maximum hit rate for a given semantic cache and workload. Different policies may achieve the maximum hit rate, and we would consider all of them to be an instance of VOPT. Theorem 3.1 (Hardness of Computing VOPT) . Let D_{\text{thresh}}>0 and let k be the cache capacity. Given a request sequence of vectors, computing VOPT is NP-hard. Proof. We reduce from the Maximum Coverage Problem (MCP). In MCP, we are given sets S_{1},\dots,S_{m} over a ground set U=\{e_{1},\dots,e_{n}\} and an integer k . The goal is to choose at most k of the sets whose union covers the largest number of elements ( 20 ) . Requests. We construct vectors u_{S} (sets) and v_{e} (elements) in \mathbb{R}^{m+n} in polynomial time (see Appendix C ). For distinct sets S,S^{\prime} and elements e,e^{\prime} : 1. d(u_{S},u_{S^{\prime}})>D_{\text{thresh}} and d(v_{e},v_{e^{\prime}})>D_{\text{thresh}} . 2. d(u_{S},v_{e})\leq D_{\text{thresh}}\iff e\in S . Request sequence. We define a two-phase request sequence: • Phase 1: Request all set vectors v_{S_{1}},\dots,v_{S_{m}} . All requests are misses, but the policy may keep up to k set vectors after Phase 1. • Phase 2: Request all element vectors v_{e_{1}},\dots,v_{e_{n}} . A request to v_{e_{i}} is a hit iff some cached v_{S_{j}} corresponds to a set containing e_{i} . Correctness. The number of hits in Phase 2 equals the number of elements in the union of the k sets associated with the cached set vectors. Thus, an optimal VOPT policy chooses the same k sets that achieve optimal maximum coverage. Since MCP is NP-hard, so is computing VOPT. ∎ Corollary 3.2 (Inapproximability of VOPT) . Unless \mathrm{P}=\mathrm{NP} , no polynomial-time algorithm can approximate VOPT’s hit ratio within a factor better than (1-1/e) . Proof. The reduction in Theorem 3.1 is approximation-preserving: the optimal number of Phase 2 hits equals the maximum coverage value of the MCP instance. MCP is known to be NP-hard to approximate to within a factor better than (1-1/e) ( 20 ) . Thus, any algorithm approximating VOPT more closely would imply an algorithm approximating MCP more closely, contradicting known hardness results. ∎ Theorem 3.3 (Well-Definedness and Computational Infeasibility of VOPT) . For any request sequence and threshold distance D_{\text{thresh}} , VOPT is well-defined: an optimal selection of up to k cached vectors that maximizes semantic hits always exists. However, computing VOPT requires solving an NP-hard optimization problem and is therefore computationally infeasible for realistic workloads. Proof. Well-definedness follows from the fact that the request sequence is finite and there are finitely many subsets of size at most k that the cache may contain. Each such subset induces a unique number of semantic hits, and an optimal choice exists. ∎ Corollary 3.4 (Approximability of the Static Formulation) . Consider the static variant of the problem where the cache contents S ( |S|\leq k ) are selected and inserted prior to processing the request sequence and remain fixed. In this setting, the objective function is monotone submodular, and a greedy selection strategy achieves an approximation ratio of (1-1/e)\approx 0.632 . The reduction from the Maximum Coverage Problem (MCP) in Theorem 3.1 reveals a fundamental structural property: if the cache admits no evictions (i.e., the content is static), the problem of maximizing hits is mathematically equivalent to MCP. The objective function of MCP exhibits diminishing returns, a property formally known as submodularity. It is known ( 32 ) that for such problems, iteratively selecting the element that covers the most uncovered items yields the optimal (1-1/e) approximation. However, this strict theoretical guarantee does not extend to the general (dynamic) semantic caching problem. In dynamic settings, an eviction decision at time t constrains the feasible cache states at time t+1 , creating temporal dependencies that break the submodularity of the global objective function. Nevertheless, the static relaxation serves as the theoretical foundation for our offline heuristics. By treating the dynamic problem as a sequence of local maximum coverage problems, where we attempt to maximize the number of future hits covered by the current cache state, we leverage the strong performance of greedy strategies on submodular functions, even in the absence of worst-case guarantees. 3.3 VOPT heuristics We propose 3 heuristics of VOPT. In our measurements, as reported below, we have found that different ones obtain slightly higher or lower hit rate based on the workload and cache size. Obviously, since these are offline schemes, meant to establish an upper bound on the best attainable performance, and they are computationally efficient, one can simply implement all three and take the best one at any given data point. 3.3.1 Clustered Relaxed Vector Belady As mentioned before, the challenge in adapting OPT to semantic caches is that multiple cached vectors may cover the same future requests, leading to coverage redundancy. One method to utilize our clairvoyant knowledge of all requests is to divide them into semantically identical clusters, where the maximum distance between two vectors in the same cluster is D_{\text{thresh}} . To create the clusters, we first construct a graph G in which each node represents one embedding vector. An edge is added between two nodes if their embeddings are semantically identical, i.e., if their distance is below the threshold D_{\text{thresh}} . Since any cluster of semantically identical embeddings corresponds to a clique in G , the task of minimizing the number of clusters reduces to finding the Minimum Clique Cover (MCC). This problem is NP-hard, and can be solved by coloring the complement graph of G , denoted \overline{G} ( 15 ) . A useful heuristic is greedy coloring with DSATUR, which strikes a balance between accuracy and runtime. However, we found that for this use case, the complement graph is too large and dense for the coloring method to be practical. Instead, we adopt a simple greedy approach: iteratively extracting maximal cliques. While this method yields lower quality partitions, it produces sufficiently good results in significantly lower runtime, particularly when the graph is sparse as in our case. After clustering, the problem reduces to classic caching with exact matching, where each embedding is represented by its cluster ID. In this setting, OPT is provably the optimal policy and thus achieves the highest possible hit rate among policies that rely solely on clusters. If embeddings form true equivalence classes, i.e., if the similarity relation is transitive ( d(v_{i},v_{j})\leq D_{\text{thresh}}\land d(v_{i},v_{k})\leq D_{\text{thresh}}\;\Rightarrow\;d(v_{j},v_{k})\leq D_{\text{thresh}} ), then clustering perfectly captures semantic identity, and CRVB yields optimal results. A further consequence of this property is that finding the Minimum Clique Cover becomes trivial, since each connected component is a clique. In practice, we encountered cases where a vector v_{i} is semantically equivalent to both v_{j} and v_{k} , but v_{j} and v_{k} are not equivalent. Thus, CRVB is not optimal in the general case, and is used as a baseline oracle. 3.3.2 Frequency Greedy Relaxed Vector Belady FGRVB attempts to approximate the optimal policy by focusing on the quantity of future hits. This approach is motivated directly by the reduction to MCP. Although we cannot guarantee the (1-1/e) bound in the dynamic setting, FGRVB implements the greedy heuristic for submodular maximization as an online eviction policy. FGRVB ranks cached embeddings by their marginal contribution to the total number of future hits. On a cache miss, FGRVB counts the number of future unique hits attributed to the missed request, i.e., hits that are only covered by said embeddings. It replaces the cached item with the least unique covered future hits, given that it covers fewer hits compared to the missed item. Let R_{t:}=(r_{t},r_{t+1},\dots) be the sequence of all future requests. For a cached vector v , we define its volume score as the cardinality of the subset of future requests it covers: \text{Vol}(v)=|\{r_{i}\in R_{t:}:d(v,r_{i})i\,\}, where d(\cdot,\cdot) denotes the embedding distance. For each embedding vector r_{i} at time t (the index of the last request made to the cache), we define \text{NextCover}(r_{i},t)=\min\{\,j\;:\;j>t,\;r_{j}\in\text{cover}(r_{i})\,\}, with \text{NextCover}(r_{i},t)=\infty if no such j exists. The cache cover is then \text{CacheCover}(C,t)=\{\,\text{NextCover}(r_{j},t)\;\mid\;r_{j}\in C\,\}. While the cache is not yet full, every embedding vector is admitted. After the cache reaches capacity, a new embedding r_{i} is accepted only if its next cover is not already served: \text{NextCover}(r_{i},t)\notin\text{CacheCover}(C,t). If admitted, r_{i} replaces the embedding vector whose next hit lies furthest in the future. We consider the next hit rather than all future hits; while embeddings may cover requests far ahead, by the time those requests occur the cache has changed enough to make such predictions unreliable. Also, empirically, focusing on the next hit yields better results. (a) ELI5 (b) WildChat (c) NaturalQuestions (d) HotPotQA (e) TriviaQA (f) Quora (g) MsMarco (h) MMLU (i) StackOverflow Figure 1 : Hit rate as a function of cache size - note log scale on the Y-axis (a) ELI5 (b) WildChat (c) NaturalQuestions (d) HotPotQA (e) TriviaQA (f) Quora (g) MsMarco (h) MMLU (i) StackOverflow Figure 2 : Mean hit distance as a function of cache size - note log scale on the Y-axis 4 Online Cache Management Policies In this work, we have explored immediate adaptations to semantic caching of several known caching policies including LRU ( 19 ) , LFU ( 27 ) , LFUDA ( 1 ) , LRU-K ( 33 ) , ARC ( 31 ) , and RAP ( 7 ) . That is, whenever there is a hit, we update the metadata of the top item that is returned by the cache for the respective query according to the respective policy. In addition, we experimented with several alternative ideas of how to better address the fact that in semantic caching, there may be multiple vectors that could potentially serve as a hit, i.e., are within the threshold distance from the queried vector. Since in our experiment LFU based policies seems to generally perform better than other approaches, we focus in this paper on LFU variations. To that end, we have designed SphereLFU, MissLFU, ClusterLFU, ClusterLRU, DistanceLFU, Surprisal, and SurprisalLFU. For lack of space, we refer the reader to Appendix B for additional information about these policies. Of these, SphereLFU is particularly notable for achieving the highest semantic accuracy. Unlike discrete frequency counters, SphereLFU employs a probabilistic credit assignment mechanism, where usage ’mass’ is distributed among neighboring cached vectors based on a similarity kernel ( Section B.2.1 ). In that sense, it is trying act as an online approximation of FGRVB. We have explored ML based policies, based on LRB ( 40 ) , but found that results were much worse than other methods we explored. This is due to the fact that the workloads were not long enough to enable the complex learning mechanism of LRB to converge, especially with the more complex nature of non-exact matching. 5 Experiments In this section, we evaluate the performance of our proposed semantic caching policies against standard baselines and offline oracles. We utilize the nine datasets described in Section 5.1 , processing the first 100K entries of each (91K for NaturalQuestions). Based on the properties observed in our vector analysis and on Section 2.3 , we set the semantic threshold distance D_{\text{thresh}}=0.9 for all reported experiments. We selected the threshold such that the hit rate is within a useful range for all datasets, at least 10%, although the trends are similar for other thresholds. In Appendix E , we present results for the smaller normalized L2 distance thresholds of 0.7 and 0.5. In addition, the complete unprocessed data is available online ( 9 ) . 5.1 Datasets The nine real-world datasets we employed in our evaluation include MsMarco ( 2 ) , WildChat ( 43 ) , ELI ( 14 ) , Natural Questions (NQ) ( 28 ) , StackOverflow queries (SO) ( 17 ) , Quora ( 22 ) , MMLU ( 18 ) , TriviaQA ( 26 ) , and HotPot QA ( 42 ) . They span chats, conversational reformulations, community Q&A, web search, open-domain QA, and broad consumer questions. We have obtained the datasets from Hugging Face and processed them into a unified format, utilizing relevant data from each for specific purposes detailed below. Our canonical datasets can be generated with a script that is included in our open-source project online. We only embed queries from the datasets, and not responses. An analysis of these datasets’ characteristics appears in Appendix A . Our evaluation has revealed that they have the following properties: they rarely carry ordering signal, mostly affected by frequency and follow a specific distribution. It is of interest that when plotting the point density for the embeddings and looking at the number of neighbors of distance 0 is a concentration parameter determining the sharpness of the kernel. Soft Frequency Updates. Upon receiving a query q , we identify the set \mathcal{M}(q) of cached embeddings within the threshold distance D_{\text{thresh}} . We calculate a responsibility score r_{i}(q) for each neighbor i\in\mathcal{M}(q) , representing the probability that vector i generated query q : r_{i}(q)=\frac{(c_{i}+\alpha)\exp\!\left(-\frac{\kappa}{2}d_{i}^{2}\right)}{\sum_{j\in\mathcal{M}(q)}(c_{j}+\alpha)\exp\!\left(-\frac{\kappa}{2}d_{j}^{2}\right)} where d_{i}=d(q,e_{i}) , c_{i} is the current accumulated frequency of embedding i , and \alpha>0 is a smoothing constant. The counters are then updated by distributing exactly one unit of mass: c_{i}\leftarrow c_{i}+r_{i}(q). Unlike heuristic LFU counters, c_{i} here represents a sufficient statistic for the mixture weight \pi_{i}=\Pr[Z=i] , converging to the true usage density under stationary conditions. Distribution Shift and Decay. To handle non-stationary workloads where topic popularity shifts over time, we apply a multiplicative decay factor \gamma\in(0,1) during updates: c_{i}\leftarrow\gamma c_{i}+r_{i}(q). This effectively creates an exponentially weighted moving average of the density. For computational efficiency, rather than decaying every counter on every step, we implement this lazily or by periodically rescaling all global counters by a fixed factor (e.g., halving all counters every N requests). Efficiency. Unlike our other LFU variants that perform a k -NN search to update a single metadata entry, SphereLFU employs a range query to identify all vectors within the semantic threshold. While this theoretically allows for an update of the entire cache, the high-dimensional embedding space is characterized by extreme sparsity. In practice, the number of neighbors within D_{\text{thresh}} is consistently low, fewer than 10. If the neighbor count were to increase significantly, it would indicate that D_{\text{thresh}} is likely set too high. In scenarios where strict latency bounds are required, computational complexity can be capped by restricting soft-frequency updates to the top k nearest neighbors. This approximation preserves the most significant portion of the probability mass while maintaining a guaranteed O(k) update time. B.2.2 MissLFU Similar to LFU, but only inserts an embedding vector into the cache if there are no stored semantically identical vectors in the cache. The intuition here is that if a vector is close enough to an existing vector in the cache, there is already a (semantic) hit, so there is no point inserting the new vector. Hence, we prefer to keep embedding vectors that may otherwise not have a cached semantically close representative. B.2.3 ClusterLFU This policy groups vectors into clusters using a greedy online clustering algorithm (although other clustering algorithms can be used as well). It then applies LFU at the cluster level rather than for individual vectors. Each cluster maintains a single LFU counter representing the aggregate access frequency of its members. When an eviction is required, the least frequently used cluster is selected, and a random vector from that cluster is removed. By aggregating counters at the cluster level, this approach reduces metadata overhead and exploits semantic similarity among vectors, allowing the cache to favor groups of related embeddings that are accessed frequently. B.2.4 ClusterLRU Similar to ClusterLFU, this policy operates at the cluster level using the same greedy online clustering method. Instead of tracking frequency, it maintains the most recent access time for each cluster, based on the latest access to any of its members. Upon eviction, the least recently used cluster is selected, and a random vector from that cluster is removed. This aggregation reduces the need to maintain per-vector recency data, making it more efficient for large vector caches while still capturing temporal locality patterns. B.2.5 DistanceLFU This policy adjusts LFU counting based on vector similarity to incoming queries. If the closest stored embedding to a query is at distance d (with D_{\text{thresh}} being the maximum distance threshold to be considered a hit), the corresponding counter is incremented by: \Delta=1-\frac{d}{D_{\text{thresh}}}~~. This weighting increases the counter proportionally to how close is the match, allowing the cache to prioritize embeddings that better match recent queries. B.2.6 Surprisal This policy evicts the sentence with the maximum surprisal. Surprisal is calculated using the word frequencies library in python, which is based on multiple data sources and includes the top 100 million most popular words. A floor value is given to missing words. The Surprisal calculation is done on the raw text string, and not on the embedding iteself. In this paper, we’ve used Surprisal for efficiency reasons - as it is fast to calculate in a ”bag of words” method. Yet, it is natural to utilize the perplexity of the embedding, or other metrics that can be derived from an LLM processing the query for more accurate metric. B.2.7 SurprisalLFU This policy leverages linguistic surprisal to guide eviction decisions. Surprisal measures how unexpected a sentence is, with higher values indicating lower probability of occurrence. Perplexity is a metric closely related to surprisal, and is defined as the inverse probability of the sequence normalized by its length. Direct computation of perplexity from an LLM is computationally expensive for online caching. Instead, a more efficient metric can be obtained using a precomputed dictionary of token probabilities or frequency statistics from a large corpus. The surprisal of a sentence can be estimated as: \text{Surprisal}(s)=-\sum_{w\in s}\log p(w) where p(w) is the probability of token w under the reference distribution. Upon eviction, the item with the highest surprisal value out of all items with the minimal LFU counter is removed from the cache. This approach prioritizes retaining semantically common vectors that are more likely to contribute to future hits, while discarding outliers that are unlikely to be requested again. This is particularly useful, as we found that caches often accumulate a long tail of items with nearly identical counters. Appendix C Vector Construction To reduce the Maximum Coverage Problem (MCP) to the VOPT problem, we construct a geometric embedding that translates set membership into Euclidean distance. Let the MCP instance consist of a universe of elements U=\{e_{1},\dots,e_{n}\} and a collection of sets \mathcal{S}=\{S_{1},\dots,S_{m}\} . Let K_{\max}=\max_{j}|S_{j}| be the size of the largest set. When K_{\max}=1 , the problem is trivial. Without loss of generality, we assume K_{\max}>1 . We define a high-dimensional Euclidean space \mathbb{R}^{n+m} with orthonormal basis vectors: • \{\mathbf{u}_{1},\dots,\mathbf{u}_{n}\} corresponding to the n elements. • \{\mathbf{w}_{1},\dots,\mathbf{w}_{m}\} corresponding to the m sets. We construct the vectors using scaling parameters \alpha,\beta,\gamma>0 . For each element e_{i}\in U , we define the element vector : v_{e_{i}}=\alpha\cdot\mathbf{u}_{i} (2) For each set S_{j}\in\mathcal{S} , we define the set vector as a weighted combination of its members and a unique identifier: v_{S_{j}}=\sum_{e_{k}\in S_{j}}(\beta\cdot\mathbf{u}_{k})+(\gamma\cdot\mathbf{w}_{j}) (3) For the reduction to hold, the embedding must satisfy four conditions relative to the cache threshold D_{\text{thresh}} : 1. Element Separation: Distinct elements must not cover each other. 2. Set Separation: Distinct sets must not cover each other. 3. Membership Coverage: A set must cover its member elements. 4. Non-Membership Separation: A set must not cover non-member elements. These conditions correspond to the following system of inequalities regarding the squared Euclidean distance: \displaystyle\|v_{e_{i}}-v_{e_{\ell}}\|^{2}=2\alpha^{2} \displaystyle>D_{\text{thresh}}^{2}\quad\forall i\neq\ell (4) \displaystyle\|v_{S_{j}}-v_{S_{\ell}}\|^{2}\geq 2\gamma^{2} \displaystyle>D_{\text{thresh}}^{2}\quad\forall j\neq\ell (5) \displaystyle\|v_{S_{j}}-v_{e_{i}}\|^{2}\leq D_{\text{thresh}}^{2} \displaystyle\iff e_{i}\in S_{j} (6) Expanding the distance for a set S_{j} and an element e_{i} , we distinguish two cases: • Case 1 ( e_{i}\in S_{j} ): The distance is minimized due to the shared component \beta : (\alpha-\beta)^{2}+(|S_{j}|-1)\beta^{2}+\gamma^{2}\leq D_{\text{thresh}}^{2} (7) • Case 2 ( e_{i}\notin S_{j} ): The components are orthogonal, maximizing distance: \alpha^{2}+|S_{j}|\beta^{2}+\gamma^{2}>D_{\text{thresh}}^{2} (8) We now prove that valid parameters \alpha,\beta,\gamma always exist. We set \beta such that the set vector ”leans” towards its members relative to the element scale: \beta=\frac{\alpha}{K_{\max}} (9) We analyze the constraints for the ”worst-case” scenario (a set of maximum size K_{\max} ). Substituting \beta , the squared distance for a member element becomes: \text{Dist}^{2}_{\text{in}}=\alpha^{2}\left(1-\frac{1}{K_{\max}}\right)+\gamma^{2} (10) To satisfy all conditions, we must find \alpha and \gamma such that: \displaystyle 2\alpha^{2} \displaystyle>D_{\text{thresh}}^{2} (11) \displaystyle 2\gamma^{2} \displaystyle>D_{\text{thresh}}^{2} (12) \displaystyle\alpha^{2}\left(1-\frac{1}{K_{\max}}\right)+\gamma^{2} \displaystyle\leq D_{\text{thresh}}^{2} (13) From ( 13 ), we derive an upper bound for \gamma^{2} : \gamma^{2}\leq D_{\text{thresh}}^{2}-\alpha^{2}\left(\frac{K_{\max}-1}{K_{\max}}\right) (14) To simultaneously satisfy ( 12 ), this upper bound must strictly exceed D_{\text{thresh}}^{2}/2 : D_{\text{thresh}}^{2}-\alpha^{2}\left(\frac{K_{\max}-1}{K_{\max}}\right)>\frac{D_{\text{thresh}}^{2}}{2} (15) Rearranging for \alpha^{2} , we obtain the existence condition: \alpha^{2}<\frac{D_{\text{thresh}}^{2}}{2}\cdot\left(\frac{K_{\max}}{K_{\max}-1}\right) (16) Since K_{\max}\geq 2 implies \frac{K_{\max}}{K_{\max}-1}>1 , there exists a non-empty open interval for \alpha^{2} : \frac{D_{\text{thresh}}^{2}}{2}<\alpha^{2}<\frac{D_{\text{thresh}}^{2}}{2}\left(\frac{K_{\max}}{K_{\max}-1}\right) (17) By choosing any \alpha^{2} within this interval and setting \gamma^{2} sufficiently close to (but greater than) D_{\text{thresh}}^{2}/2 , all strict inequalities are satisfied. This guarantees that a valid embedding exists for any MCP instance. ∎ (a) ELI5 (b) WildChat (c) NaturalQuestions (d) HotPotQA (e) TriviaQA (f) Quora (g) MsMarco (h) MMLU (i) StackOverflow Figure 4 : Throughput as a function of cache size - note log scale on the Y-axis Appendix D Throughput Analysis In Figure 4 we evaluate the system throughput by measuring the average operations per second (OPS) for the combined query and update cycle across the entire request stream. Since semantic caching inherently requires identifying similar vectors to determine hits, we treat the nearest neighbor (NN) search and the subsequent cache policy logic as an atomic operation. Our profiling, as reported in Figure 4 , indicates that the runtime is primarily dominated by the NN search latency, which is common to all semantic policies. Consequently, throughput remains consistent across different strategies, with all policies operating within the same order of magnitude. This suggests that the computational overhead introduced by the complex bookkeeping of policies like SphereLFU is negligible compared to the cost of the underlying vector retrieval. To ensure scalability for larger cache sizes, we employed optimized implementations for all baselines. Notably, the offline clairvoyant policies (CRVB, FGRVB, RGRVB) achieve high throughput despite their algorithmic complexity. This is achieved by pre-computing a global pairwise distance matrix during initialization, effectively offloading the expensive distance calculations from the critical path of the evaluation. FGRVB has the lowest throughput, which is caused by its implementation requiring a complex computation of the marginal gain for each vector per update. Appendix E Additional Experiments We provide supplemental evaluations for varying distance thresholds, specifically D_{\text{thresh}}=0.5 and 0.7 (corresponding to cosine similarities of 0.88 and 0.76 , respectively). These more conservative thresholds naturally result in fewer semantic hits per query. This shift diminishes the advantage of SphereLFU, which relies on a high density of neighboring vectors to effectively distribute soft-frequency updates. Conversely, SurprisalLFU exhibits relative robustness at lower thresholds. when most cached items share a baseline frequency of 1, its linguistic surprisal metric provides a more intelligent tie-breaking mechanism for eviction compared to random or recency-based selection. (a) ELI5 (b) WildChat (c) NaturalQuestions (d) HotPotQA (e) TriviaQA (f) Quora (g) MsMarco (h) MMLU (i) StackOverflow Figure 5 : Hit rate at D_{\text{thresh}}=0.5 as a function of cache size - note log scale on the Y-axis (a) ELI5 (b) WildChat (c) NaturalQuestions (d) HotPotQA (e) TriviaQA (f) Quora (g) MsMarco (h) MMLU (i) StackOverflow Figure 6 : Mean hit distance at D_{\text{thresh}}=0.5 Distance as a function of cache size - note log scale on the Y-axis (a) ELI5 (b) WildChat (c) NaturalQuestions (d) HotPotQA (e) TriviaQA (f) Quora (g) MsMarco (h) MMLU (i) StackOverflow Figure 7 : Hit rate at D_{\text{thresh}}=0.7 as a function of cache size - note log scale on the Y-axis (a) ELI5 (b) WildChat (c) NaturalQuestions (d) HotPotQA (e) TriviaQA (f) Quora (g) MsMarco (h) MMLU (i) StackOverflow Figure 8 : Mean hit distance at D_{\text{thresh}}=0.7 Distance as a function of cache size - note log scale on the Y-axis