MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Ali Noshad 1 Zishan Zheng 2 Yinjun Wu 1
arXiv:2605.24914v1 [cs.IR] 24 May 2026
Abstract
similarity between different, but conceptually equivalent, prompts—requiring redundant model invocations. To address this limitation, semantic caches can serve paraphrased or semantically related queries by embedding prompts into a semantic vector space and reusing responses based on similarity, substantially increasing the cache hit rate, i.e., the ratio of reusing the cache’s response, and thus improving system efficiency (Bang, 2023; Dasgupta et al., 2024). Production examples include Azure semantic caching option for LLM APIs 1 , and LiteLLM caching system 2
To reduce LLM costs and latency, semantic caching systems must accurately identify when a new prompt matches a cached one. Current methods often rely on simplistic similarity measures, which limit their effectiveness. We introduce MVR-cache, a novel semantic caching approach that significantly improves retrieval accuracy by integrating Multi-Vector Retrieval (MVR). MVR-cache is built upon a learnable segmentation model that intelligently splits prompts, enabling fine-grained similarity comparisons via MaxSim. We derive the model’s training objective from a rigorous theoretical analysis. This can ensure that optimizing this objective directly maximizes cache hits under strict correctness constraints. To solve the resulting non-differentiable combinatorial optimization problem, we leverage a reinforcement learning-based training strategy with the theoretically grounded objectives as the reward. Experimental results on established benchmarks across diverse tasks confirm that in comparison to the state-of-the-art, MVR-cache consistently increases the cache hit rates by up to 37% while maintaining the same correctness guarantees. MVR-cache is available at https:// github.com/PKU-SDS-lab/MVR-Cache
Existing semantic caching methods primarily focus on how to design reasonable cache policies to determine when to reuse the cache or not, based on the similarity scores between incoming prompts and their nearest neighbors in the cache. For instance, the static policy approaches (Dasgupta et al., 2024; Li et al., 2024; Bang, 2023)1 2 compare such similarity scores against a global threshold to decide the cache’s reuse, while the recently proposed vCache method (Schroeder et al., 2025) employs dynamically learned, prompt-specific thresholds to provably guarantee correct response. Only when such similarity scores are high enough, the cached response of the nearest neighbors is reused. However, the similarity measures used in these methods are all simple ones, such as cosine similarity between the prompts’ embeddings, which may not accurately capture the subtle semantic differences in prompts, particularly for those semantically complex ones. Consequently, semantically dissimilar prompts may be incorrectly matched, degrading the cache hit rate.
1. Introduction
For instance, we draw a prompt, x, from the SemCacheClassification dataset (Schroeder et al., 2025) in Figure 1, which is a positive review of an adult crime drama. In a standard cosine similarity lookup, this prompt returns x1 as the nearest neighbor. While x1 is also a review for the same type of drama—sharing salient keywords like “crime” that define their primary topic—it contains negative comments. This subtle semantic difference leads to a divergent LLM response for x1 compared to x, resulting in a cache miss despite their high topical similarity.
Semantic caching has emerged as an effective mechanism for reducing the latency and computational cost of large language model (LLM) inference (Xiong et al., 2024; Schroeder et al., 2025). Traditional caches based on exact string matches fail to exploit the underlying semantic 1 School of Computer Science, Peking University, Beijing, China 2 School of Information, Renmin University of China, Beijing, China. Correspondence to: Yinjun Wu <[email protected]>.
1
https://learn.microsoft.com/en-us/azure/ api-management/azure-openai-enable-semantic-caching 2 https://docs.litellm.ai/docs/proxy/caching
Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s).
1
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
cached prompts is made instantly online, and (2) the ability to produce a variable number of segments per prompt, which is fundamental to the flexible nature of MVR where the vector count per sample varies. However, two critical challenges arise for effective training over this model. First, the cache hit rate is a discrete and non-differentiable metric, which thus cannot serve as the training objective for the segmentation model. Instead, we propose a surrogate objective, which aims to align the segmentation-aware MaxSim score of a new prompt to its nearest neighbor in the cache with identical LLM responses. As a consequence, for the example in Figure 1, the MaxSim score between x and its real nearest neighbor x2 could become higher than others. A rigorous theoretical analysis reveals that optimizing this objective guarantees maximizing the vCache cache hit rate without violating the correctness constraints.
Figure 1. A motivating example from the SemCacheClassification dataset (Schroeder et al., 2025). Using a single embedding per prompt, a new query x about whether an adult crime drama review is friendly finds its nearest neighbor (x1 ) via cosine similarity. However, their LLM responses differ, thus causing a cache miss. In contrast, MVR-cache learns to segment prompts, particularly extracting the sentences with positive comments as individual segments (highlighted with purple boxes) for x and its real nearest neighbor, x2 . By embedding these segments, the segmentationaware MaxSim score of x2 to x exceeds that of other cached prompts, thus allowing the reuse of the cached response of x2 for a cache hit.
In addition, due to the discrete nature of segmentation decisions, the output space of the segmentation model is large and complex, which is a combinatorial space of all possible segmentation points on each prompt. Hence, optimizing the above objective remains non-differentiable. To overcome this, we frame the problem of training the segmentation model as a reinforcement learning for combinatorial optimization (RL4CO) (Berto et al., 2023) task, where we design a reward function directly informed by our theoretical objective, enabling effective gradient-based learning of the segmentation model.
To address this issue, we propose to employ Multi-Vector Retrieval (MVR) to facilitate the retrieval of the real nearest neighbor for a new prompt. Originally proposed for information retrieval by ColBERT (Khattab & Zaharia, 2020), MVR decomposes both queries and documents into finegrained pieces and encodes each piece into one embedding, thus producing multi-vector representations for queries and documents. The query-document similarity is then computed using the MaxSim score: for each query vector, its maximum similarity with any document vector is identified, and these scores are aggregated. As revealed by ColBert (Khattab & Zaharia, 2020) and its follow-up works, MVR provides a nuanced matching mechanism that excels at capturing partial matches, thereby enhancing retrieval accuracy. However, its performance hinges critically on the strategy used to segment text since the multi-vector representations are produced by embedding each of these segments. While ColBERT’s default approach uses single-token embeddings, recent work (Liu et al., 2025) has shown this to be suboptimal, demonstrating that optimized segmentation is key to unlocking MVR’s full potential.
We further perform extensive experiments on a variety of benchmark datasets, covering diverse tasks such as classification, search and open-ended generation. The results demonstrate that in comparison to the state-of-the-art, MVRcache can consistently increase the cache hit rate by up to 25% while respecting the correctness guarantees. Our contributions are summarized as follows: • MVR-cache, a method that learns an efficient, lightweight segmentation model to segment prompts to facilitate multi-vector retrieval (MVR) to identify the real nearest neighbors in the cache for a new prompt. • A rigorous theoretical analysis that formalizes a training objective, proving that optimizing it is equivalent to maximizing cache hit rate under correctness guarantees. • A reinforcement learning (RL) solution to train this segmentation model by framing it as a combinatorial optimization problem. • Extensive experiments on a variety of benchmark datasets covering diverse tasks demonstrate the effectiveness of MVR-cache.
We therefore propose a novel prompt segmentation method, MVR-cache, for semantic cache, which aims to maximize the cache hit rate while strictly adhering to user-specified error guarantees. MVR-cache begins with the development of a lightweight segmentation model designed with two essential properties: (1) minimal model capacity to ensure efficiency so that the decision of whether to exploit the 2
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
where the minimization is over (t′ , γ ′ ) within a (1 − ϵ) confidence region of (t̂, γ̂). This formulation guarantees, under mild assumptions, the probability of a correct response (via cache or LLM) is at least 1 − δ for any user-defined error rate δ (see (Schroeder et al., 2025) for derivation).
2. Preliminaries 2.1. Semantic Caching Let x1 , . . . , xn be prompts sequentially inserted into a semantic cache. For each xi , mainstream solutions like vCache (Schroeder et al., 2025) store three items: its embedding E(xi ) ∈ Rd , its LLM-generated response r(xi ) = LLM(xi ), and associated metadata O(xi ). O(xi ) is a sequence of pairs, where each pair links xi to a later prompt xj that identified xi as its nearest neighbor. Formally: O(xi ) = {(s(xj ), c(xj ))|nn(xj ) = xi }n j=i+1 ,
2.3. Multi-Vector Retrieval As noted in Section 1, cosine similarity between full-prompt embeddings may not reflect true semantic similarity, leading to suboptimal cache hit rates.
(1)
in which nn(xj ) denotes the nearest neighbor of xj among {x1 , x2 , . . . , xj−1 }, s(xi ) is defined as the similarity score between xj and nn(xj ), and a Boolean label c(xj ) indicating whether the true response r(xj ) matches the cached response r(nn(xj )).
To address this issue, we employ multi-vector retrieval (MVR) (Khattab & Zaharia, 2020), which represents each text sequence with a set of embedding vectors rather than a single vector. Specifically, let a cached prompt xj and a new prompt x be represented by sequences of embeddings (1) (2) {E(x(1) ), E(x(2) ), . . . } and {E(xj ), E(xj ), . . . }. Their similarity is then measured by the following MaxSim score:
The goal of performing semantic caching is to reduce LLM inference costs by reusing cached responses for new, sufficiently similar prompts. The core of this approach is to develop a caching policy that decides, for each new query, whether to exploit (reuse a cached response) or explore (invoke the LLM).
MaxSim(x, xj ) =
To achieve the above goal, vCache (Schroeder et al., 2025) proposes a stochastic caching policy based on the similarity of one new prompt, x, to its nearest neighbor in the cache, s(x). This policy aims to maximize the cache hit rate while ensuring that the probability of returning the correct response is provably high enough. Due to the dependency of this policy on s(x), vCache begins by modeling the conditional correctness probability that the LLM response of a new prompt, x, matches that of its nearest neighbor given s(x) using the following sigmoid formula: 1 . 1 + e−γ(s−t)
X
t,γ
ℓBCE (L(si ; t, γ), ci ),
x x(2)
(2)
(3)
Specifically, to compensate for potential overfitting of the parameters (t̂, γ̂) in Equation (3), which could lead to an overestimate of Pr c(x) = 1 | s(x) , τ is conservatively estimated as: (1 − δ) − α , 1−α
with α = (1 − ϵ) L s; t′ , γ ′ ,
x1 0.01 0.05
(1)
x2 0.83 0.80
(1)
x3 0.02 0.01
In Multi-Vector Retrieval (MVR), the effectiveness of MaxSim scores depends critically on the strategy used to decompose text into segments. While existing methods like ColBERT (Khattab & Zaharia, 2020) generate embeddings at the token level, this overly fine-grained approach can impair retrieval performance. To address this, (Liu et al., 2025) introduces a method that dynamically decomposes text into coarser, semantically meaningful segments. This approach uniquely leverages retrieval performance as an optimization signal to iteratively refine the decomposition process.
in which, ℓBCE represents the binary cross-entropy loss. These two estimated parameters are then incorporated into Equation (2) to estimate the correctness probability for each new prompt x. This probability is then utilized to dynamically determine the exploration probability, τ , which governs when to bypass the cache and query the LLM directly.
t ,γ
(5)
For each x(t) from x, we identify its most similar vector (1) (2) (3) among [x1 , x1 , x1 ] and highlight its similarity to x(t) using red color, which is the same as the highest similarity score at each row. These scores are then plugged into Equation (5), yielding the final MaxSim score MaxSim(x, x1 ) = 0.83 + 0.80 = 1.63
(si ,ci )∈O(nn(x))
τ = min ′ ′
(s)
maxs sim(E(x(t) ), E(xj )).
(1)
(1)
In the above formula, t ∈ [0, 1] and γ > 0. These two parameters are dependent on specific cached prompts, and estimated via maximum likelihood estimation (MLE) using all the metadata of the nearest neighbor of x, O(nn(x)): (t̂, γ̂) = arg min
t
Intuitively speaking, MaxSim(x, xj ) first selects the most (s) similar vector, E(xj ), from xj for each E(x(t) ), and then aggregates this similarity across all t. Example 2.1. Suppose one cached prompt x1 is represented (1) (2) (3) by three vectors, [x1 , x1 , x1 ] while the new prompt x is associated with two vectors, [x(1) , x(2) ], we compute the pairwise similarity scores between each vector from x1 and each vector from x as follows:
2.2. Caching policy in vCache
Pr c(x) = 1 | s(x) = L(s(x); t, γ) =
X
Problem definition Building on this insight, we adapt the strategy of (Liu et al., 2025) to semantic caching. Our method automatically decomposes both cached and new prompts, then uses a segmentation-aware MaxSim score to more reliably retrieve the real nearest neighbors. The
(4)
3
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
multi-vector representation for each cached prompt xi and each new prompt x:
ultimate goal is to maximize the cache hit rate while maintaining the correctness guarantees.
(1)
3. MVR-cache
(E(x(1) ), E(x(2) ), · · · ) = Emb(SEG(x; Θ(x)))
3.1. General inference process
These multi-vector representations can then be incorporated into Equation (5) to compute the MaxSim score between each xi and x. However, the MaxSim score is inherently asymmetric, which poses a critical issue in semantic caching. Returning to Example 2.1, MaxSim(x1 , x) is computed by aggregating the highest score at each column, resulting in a score of 0.89, which is only roughly half of MaxSim(x, x1 ). In semantic caching, a cache hit should reflect mutual semantic similarity between the new and cached prompts. A high MaxSim score, which is unidirectional, however, can only guarantee partial matching between prompts-specifically, that each segment of the new prompt is similar to some segment of the cached prompt, but not necessarily vice versa. Hence, we propose to average the two normalized unidirectional MaxSim scores as the Segmentation-aware MaxSim score for semantic caching:
The overall inference process of MVR-cache is visualized in Figure 2, which is described in detail below. Prompt segmentation and embedding Given an arbitrary text sequence x—including both incoming new prompts and cached prompts—MVR-cache first identifies a set of candidate split positions, e.g., punctuation boundaries. These split positions are denoted by Px = {p1 , p2 , . . . , pi , . . . }. A segmentation model Θ then selects a subset of these positions to split the sequence. Formally, the model outputs an ordered list of split indices: → Θ(x) = − p = [pi1 , . . . , pim−1 ], 1 ≤ i1 < · · · < im−1 < |Px |,
Using these indices, x is partitioned into m contiguous subsequences, (x(1) , . . . , x(m) ), such that each x(t) consists of tokens from position (pit ) + 1 to position (pit+1 ) in x, with the conventions pi0 = 0 and pim = |x|.
SMaxSimΘ (xi , xj ) (7) 1 1 MaxSim(xi , xj ) + MaxSim(xj , xi ) := 0.5 × |xi | |xj |
where |xi | and |xj | denote the number of segments in each prompt, and normalization ensures scale invariance across prompts of different lengths. It is parameterized by Θ since it relies on the segmentation produced by the model Θ. This symmetric measure better captures bidirectional semantic relevance, making it more suitable for cache hit determination. Using SMaxSimΘ , the nearest neighbor for a new prompt x is identified as
(t)
Each x is then embedded using a shared encoder E(·), producing m vectors, (E(x(1) ), E(x(2) ), . . . , E(x(m) )) as the multi-vector representation for x. The overall segmentation and embedding process can be summarized as follows: SEG(x; Θ(x)) = (x(1) , . . . , x(m) ) Emb((x(1) , . . . , x(m) )) = (E(x(1) ), . . . , E(x(m) ))
(2)
(E(xi ), E(xi ), · · · ) = Emb(SEG(xi ; Θ(xi )))
(6)
sΘ (x) = SMaxSimΘ (x, nnΘ (x)) nnΘ (x) = argmaxxj SMaxSimΘ (x, xj ).
Example 3.1. For instance, Px could be defined as an ordered sequence of positions where punctuation marks appear in x. For the following prompt x, Px =[6, 14, 28] since the comma occurs at the token position 6 and 14, and a period occurs at the token position 28. The period at the final position may also be treated as a special “<stop>” token.
In the above formula, sΘ (x) and nnΘ (x) are parameterized by Θ due to its reliance on the segmentation model, Θ. During the inference phase, nnΘ (x) can be quickly retrieved using indexes constructed for multi-vector retrieval, e.g., x = ‘‘Summarize Section 3, list three PLAID (Santhanam et al., 2022). The corresponding simlimitations, and format as bullet points.’’ ilarity score, sΘ (x), is then passed to the vCache module described in Section 2.2 (Equations (2)–(4)) to determine Given P(x), a segmentation model Θ may output a subset of these positions to indicate where the prompt should be the exploration probability τ for prompt x. Note that acdivided. For instance, Θ might output [14], indicating that cording to Equation (3), t̂ and γ̂ also implicitly depend on the second comma at position 14 is used to split x into two Θ, which are thus dynamically updated during the training sub-subsequences: process as Θ evolves (see Section 3.4). x(1) = ‘‘Summarize Section 3, list three limitations,’’ x
(2)
3.2. Segmentation model design
= ‘‘and format as bullet points.’’
Lightweight and Variable-Size Segmentation Model. The segmentation model Θ is a critical component for ensuring segmentation quality and the quality of subsequent multivector representations. Ideally, Θ should possess two key properties. First, it must be sufficiently lightweight—ideally, much smaller than the underlying LLM—to enable real-time segmentation of new prompts during online inference. If Θ were comparable in size to the LLM, processing each
Note that Px is prompt-dependent, which has variable sizes between different prompts. Similarly, the output of Θ is a variable-length subset of Px . Segmentation-aware MaxSim score The above segmentation-and-embedding procedure can generate a 4
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 2. Overview of the inference process for MVR-cache. Given a new prompt x, the segmentation model Θ first identifies candidate split positions (e.g., at punctuation marks) to yield multiple text segments. Each segment is encoded by the embedding model E to produce a multi-vector representation for x. This representation is compared to cached entries using the segmentation-aware MaxSim score (SMaxSim) to retrieve the nearest neighbor nn(x) and its similarity score. Finally, the vCache module uses nn(x) and its SMaxSim score to determine whether to utilize the cached prompt.
Θ4 uses d1 and the pointer states hi to compute a probability distribution over all potential split positions. However, unlike the standard pointer network which considers all input indices, our candidate split positions are a restricted subset Px of [1, . . . , L]. We therefore mask invalid positions by assigning them zero probability. The attention mechanism for this step is formulated as: u1j = v ⊤ tanh(W1 hj + W2 d1 ), j ∈ [1, 2, . . . , L] X a1j = softmax(u1j ) · I(j ∈ Px ), d′1 = a1j hj
(8)
j
Figure 3. Model architecture for prompt segmentation. This segmentation model encodes input prompt tokens using a BERT encoder (Θ1 ). A projection MLP (Θ2 ) transforms the token embeddings, which are then processed by a decoder LSTM (Θ3 ). Finally, an attention layer (Θ4 ) computes the probability distribution over candidate split positions to predict segment boundaries.
where v, W1 , and W2 are learnable parameters in the attention layer. Hence, Θ4 = (v, W1 , W2 ). The position j with the highest probability a1j is selected as the first segmentation boundary. Overall, the segmentation model consists of one Bert encoder (Θ1 ), one MLP layer (Θ2 ), one single-layer LSTM (Θ3 ) and one simple attention layer (Θ4 ). In our implementation, Θ only takes around 500-600 MB GPU memory in total, which is much smaller than the capacity of typical LLMs.
prompt would incur near-LLM-level computational overhead, negating the acceleration benefits of caching. Second, Θ must accommodate variable-length inputs and outputs, as both the prompt and the number of segments are dynamic. To fulfill these requirements, we design a lightweight model based on the pointer network architecture (Vinyals et al., 2015), which naturally handles sequences of variable sizes (see Figure 3). Given an input prompt x of length L, our model first encodes x using a BERT encoder Θ1 to obtain token embeddings (e1 , . . . , eL ). A single-layer MLP encoder Θ2 then transforms each ei into a pointer state hi for i = 1, . . . , L. These states are aggregated into an initial hidden state d1 via a single-layer LSTM Θ3 :
Recurrent selections of the split positions To select subsequent boundaries, this process proceeds recurrently. The attention output d′i is fed back into the LSTM, Θ3 , to update the context state for the next step: d2 = LSTMΘ3 ([h1 , h2 , . . . , hL , d′1 ]).
(9)
We then compute a new distribution by replacing d1 with d2 in Equation 8. To prevent reselection, all candidate positions up to and including the previously chosen index are masked. This recurrent selection continues until the termination token (<stop>) is predicted.
d1 = LSTMΘ3 ([h1 , h2 , . . . , hL ]).
The resulting d1 represents the entire prompt context. Following the pointer network mechanism, an attention layer 5
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
3.3. Theoretical insights for the training objectives
two critical training challenges: 1) Combinatorial Optimization: the search space consists of all possible combinations of split indices in Px , which grows exponentially with the prompt length; 2) Non-Differentiability: the output of Θ—a discrete set of indices—does not carry gradients, preventing the direct use of gradient-based optimization.
Recall that our goal is to maximize cache hit rate while preserving vCache’s correctness guarantee through appropriate prompt segmentation. To this end, we adapt the segmentation-aware MaxSim score, SMaxSimΘ , by training the segmentation model to minimize the MLE loss in Equation (3). This aligns the similarity scores SMaxSimΘ (xi , xj ) with the binary label indicating whether xi and xj yield equivalent LLM responses.
To overcome these challenges, we frame the problem as a Reinforcement Learning for Combinatorial Optimization (RL4CO) task (Berto et al., 2023) and model Θ as a stochastic policy πΘ .
However, as mentioned in Section 3.1, a complication arises because the optimal t and γ implicitly depend on Θ, thus leading to a complex dependency of the final cache hit rate on Θ. Nevertheless, we can formally show that under the following assumptions, optimizing the MLE loss maximizes the hit rate while maintaining the correctness guarantee.
Problem Formulation as RL4CO In the RL4CO formulation, an input prompt x represents the state. The action to take from this state is a candidate segmentation, defined by − a sampled subset of split indices → p from the candidate set Px . The segmentation model Θ serves as the policy, defin− ing a probability distribution πΘ (→ p | x) over all possible segmentations (actions) conditioned on the input prompt.
Assumption 3.1 (Conditional distribution of similarity scores). The similarity score s(x), conditioned on the annotation label c, follows a normal distribution: Pr(s | c) ∼ N (µc , σ 2 ), where µc differs between different classes, c (could be either 0 or 1).
Reward Design and Optimization Objective For each training step, we randomly sample a prompt xi and consider all prompts xj where nnΘ (xj ) = xi . We then sample seg−→ mentations: − p→ xi ∼ πΘ (p | xi ) and pxj ∼ πΘ (p | xj ) for xi and each xj . Using these segmentations, we compute the segment-aware similarity SMaxSimΘ (xi , xj ) and the corresponding Binary Cross-Entropy (BCE) loss. The reward is the negative sum of these losses:
Assumption 3.2 (Balanced class prior). The class distribution is balanced: Pr(c = 1) = Pr(c = 0) = 0.5. Theorem 3.3. Under Assumptions 3.1 and 3.2, optimizing the prompt segmentation model to minimize Equation (3) maximizes the cache hit rate under an arbitrary user-specified error bound δ.
Reward =
X
−ℓBCE (L(SMaxSimΘ (xi , xj ); ti , γi ), cj )
nnΘ (xj )=xi
In practice, the balanced-class assumption (3.2) often does not hold. We therefore employ a class rebalanced version of Equation (3). The following lemma extends our guarantee to this setting.
We optimize Θ with REINFORCE (Williams, 2004) by maximizing the following expected reward:
Lemma 3.4. Under Assumption 3.1 alone, minimizing the class-rebalanced version of Equation (3) increases the cache hit rate under the same error bound δ.
The expectation is approximated via Monte Carlo sampling (Sutton & Barto, 2005) from the policy πΘ .
max Ep−−x→i ∼πΘ (·|xi ),p−−x→j ∼πΘ (·|xj ), for all nn(xj )=xi Reward . Θ
(10)
Jointly Optimizing ti and τi As discussed in Section 3.1, the values of ti and τi used in the reward depend implicitly on the current segmentation policy Θ. Therefore, at each training step, we temporarily freeze Θ and update ti and τi by solving the maximum likelihood estimation in Equation (3) over xi and its current set of nearest neighbors.
We defer the full proofs of Theorem 3.3 and Lemma 3.4 to Appendix A. We include some empirical results in Appendix D that can justify Assumption 3.1 on real datasets. 3.4. Offline Training of the Segmentation Policy Following the above theoretical analysis, the training objective is to minimize the following MLE loss over all training prompts xi and their associated nearest neighbors xj : X
X
i
nnΘ (xj )=xi
Training Efficiency Considerations While the segmentations for xi and its neighbors xj are generated online at each training step, the nearest neighbor mapping nnΘ (·) itself is also dependent on Θ. Ideally, updating Θ would require recalculating this mapping for the entire cache at every step, as segmentations for all cached prompts would change. However, performing this full-neighbor recalculation online in every iteration is prohibitively expensive. To resolve this efficiency bottleneck, we keep the nearest neighbor mapping fixed at each training step and only update it
ℓBCE (L(SMaxSimΘ (xi , xj ); ti , γi ), cj )
where nnΘ (xi ) denotes the cached prompt most similar to xi under the segment-aware similarity measure SMaxSimΘ . Optimizing this objective requires adapting the segmentation model Θ to select an optimal set of split indices from the candidate set Px for any prompt x. However, this poses 6
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Algorithm 1 Training Θ via offline RL
Datasets We evaluate MVR-cache and baseline methods on the following four datasets, covering a variety of tasks.
Input: A training set of prompts with ground-truth LLM responses T ; The policy model πθ (· | x) for t = 1 to T do Sample a prompt xi from T , determine all xj ’s in T satisfying nn(xj ) = xi → Sample segmentation − p from πΘ (·|x) for each x = xi and xj ’s satisfying nn(xj ) = xi Perform inference on xi and each xj Compute SMaxSimΘ (xi , xj ) between xi and each xj . Update Θ by optimizing Equation (10) with REINFORCE Update ti and γi by solving Equation (3) for xi if t%K == 0 then Segment all prompts in T using Θ and update the set of prompts taking xi as the nearest neighbor end if end for
• SemCacheSearchQueries: a subset of 150K prompts from the ORCAS dataset (Craswell et al., 2020) for the web search task. • SemCacheClassification: a benchmark containing 45K short prompts for classification, collected from three diverse ecommerce text classification dataset (Talmor et al., 2019; Ni et al., 2019).1 • PromptBench: PromptBench (Zhu et al., 2023) provides a framework to comprehensively evaluate the robustness of LLMs by perturbing prompts. We follow (Zhu et al., 2023) to perturb each prompt of the SQUAD-V2 (Rajpurkar et al., 2018) dataset in different manners such that perturbed prompts can ideally have the same LLM responses to the original ones. We follow (Schroeder et al., 2025) to determine the equivalence of the LLM responses between prompts. This finally yields 38K prompts for the question answering task. • QNLI: is another question answering benchmark (Wang et al., 2018). We follow the same procedure as above to perturb prompts and generate labels, which results in 29K prompts.
periodically—once every K steps—where K is a hyperparameter. This strategy decouples the costly neighbor search from the frequent policy updates, achieving an effective balance between model performance and computational cost. Training data. Following (Schroeder et al., 2025), we assume access to ground-truth LLM responses for all training prompts. The label cj for a pair of prompts (xi , xj ) is determined via exact string matching of their corresponding LLM responses.
While the first two datasets have been used to evaluate vCache (Schroeder et al., 2025), they consist primarily of short prompts that do not reflect more complex, emerging scenarios—such as multi-turn conversations or reasoning tasks with lengthy, semantically rich prompts. To address this, we include the PromptBench and QNLI datasets, which capture these previously overlooked settings.
4. Experiments 4.1. Experimental setup Baseline We compare MVR-cache against the state-ofthe-art semantic caching method vCache(Schroeder et al., 2025), which provides a correctness guarantee on its caching policy. In addition, we attempt to incorporate the two representative segmentation methods used in MVR, ColBert(Khattab & Zaharia, 2020) and POQD(Liu et al., 2025), into vCache. The details of adapting these two methods to vCache are provided in Appendix B. Detailed configurations of MVR-cache are provided in Appendix B.
Unlike prior systems such as vCache, our approach involves offline training of a segmentation model. Accordingly, we split each dataset into training, validation, and test subsets. The model is trained on the training split, with the validation split used for model selection. Notably, the training split is intentionally limited—containing only 3K prompts per dataset—to reflect the practical constraints of obtaining labeled data for this task. Indeed, according to the ablation studies in Appendix D, a training set of 3K is sufficient to train the segmentation model. To ensure fair comparison with baseline methods like vCache, all approaches are evaluated on the same set of test prompts.
Prompt-insertion protocols We evaluate semantic caching under two prompt-insertion protocols. Our default setting follows the standard vCache protocol (Schroeder et al., 2025), which we denote as cache-on-miss only: an incoming prompt is inserted into the cache only when it results in a cache miss, while prompts served by cache hits are not inserted. This protocol is used for all main cache hit rate, error rate, and latency results. We also evaluate a always-cache protocol, where every incoming prompt is inserted into the cache regardless of whether it is a hit or miss. This setting keeps the cache contents identical across methods and isolates the effect of retrieval quality from differences in cache growth.
Embedding models and LLMs Throughout the experiments, the BGE model (Chen et al., 2024) is configured as the default embedding model to embed prompt segments, while GPT-4o-mini (Hurst et al., 2024) is employed to generate the ground-truth response for each prompt. 1
https://www.kaggle.com/datasets/saurabhshahane/ ecommerce-text-classification
7
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 4. The cumulative cache hit rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.01
Figure 5. The cumulative error rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.01
Metrics We report the following metrics: 1) cache hit rate, defined as the ratio of the prompt that exploits the cache to the total number of prompts; 2) error rate, calculated as the ratio of false positive cache hits to the total number of new prompts; 3) latency, which measures the overall inference time, including the segmentation time, embedding time, retrieval time, and LLM invocation time (if cache miss).
results of SemCacheSearchQueries dataset on always-cache protocol). MVR-cache reduces the end-to-end inference time. Although MVR-cache introduces additional computation from prompt segmentation and multi-vector retrieval, it achieves higher cache hit rates, which reduces costly LLM invocations and accelerates end-to-end inference. As shown in Table 1 (under the default cache-on-miss only protocol), MVR-cache reduces the inference overhead by up to 6% under the same error bound, while its algorithmic overhead excluding LLM calls remains small compared with the dominant LLM inference cost. In contrast, POQD incurs substantially higher latency because it requires an additional LLM to segment each prompt, making it less suitable for time-sensitive semantic caching.
4.2. Experimental results Due to space limits, we report results for δ = 0.01; the results for other δ’s are in Appendix D. MVR-cache achieves higher cache hit rates under the same error bound We follow (Schroeder et al., 2025) to plot the curve of the cumulative cache hit rate as the number of incoming prompts increases, which is shown in Figure 4. We also examine the real error rate in this setting. As reported in Figure 5, the error rate of all methods, including MVR-cache, gradually increases to a stable value below the user-specified δ, indicating that MVR-cache respects the correctness guarantees.
MVR-cache generalizes across different datasets Unlike vCache, which is a training-free method, MVR-cache requires performing additional training to obtain one segmentation model for prompt segmentation, which is conducted per dataset in the above experiments. However, we additionally evaluate the generalizability of the segmentation model trained on the PromptBench dataset to the QNLI dataset, which is reported in Figure 6. This figure surprisingly reveals that our segmentation model still outperforms all baseline methods in terms of the cache hit rate, even in the out-of-the-distribution setting.
The similar performance pattern indeed occurs under the always-cache protocol. As shown in Figures 7 and 20 (see Appendix D), MVR-cache maintains much higher cache hit rates while keeping the error rate below the user-specified bound under this protocol. Figure 7 suggests that MVRcache can consistently achieve higher cache hit rates than all baseline methods, where the gains are up to 37% (see the 8
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation Table 1. Cumulative end-to-end inference latency (minutes). Values in parentheses denote algorithm running time excluding LLM calls. SemCacheClassification
SemCacheSearchQueries
PromptBench
QNLI
vCache ColBert POQD
408.49 (23.21) 501.46 (25.84) 971.51 (492.92)
6361.52 (69.77) 6521.89 (130.00) 6990.08 (628.33)
1870.57 (19.58) 2294.38 (150.32) 2945.20 (959.60)
1536.00 (14.10) 1626.37 (39.28) 2648.80 (1048.48)
MVR-cache
383.32 (34.14)
6345.61 (111.26)
1866.58 (27.49)
1504.43 (17.62)
Figure 6. Generalization of the segmentation model trained on PromptBench to QNLI.
Figure 7. Cumulative cache hit rate e VS increasing number of incoming prompts under the always-cache protocol with δ = 0.01.
Training-label cost MVR-cache uses labeled prompt pairs for offline training, collecting ground-truth LLM responses for 3K prompts per dataset this introduces a onetime labeling cost. This one-time cost is outweighed by downstream benefits: on SemCacheClassification, MVRcache increases cache hits by 9% over vCache, saving roughly 4.1K LLM calls, already exceeding the traininglabel cost. Appendix D.3 shows that increasing the training set yields minimal additional gains, indicating data-efficient segmentation. We also evaluate a weak-supervision variant that uses GPT-4o-mini as a proxy labeler for GPT-4 outputs and queries GPT-4 only when proxy confidence is low. On SemCacheClassification, this avoids 80.4% of GPT-4 label calls while maintaining 97.1% agreement on proxy-labeled samples, suggesting that labeling cost can be substantially reduced without changing the training framework.
tuning and instead rely on prompt similarity. These include static threshold policies (Dasgupta et al., 2024; Bang, 2023) 1 2 and adaptive approaches like vCache (Schroeder et al., 2025), which learns prompt-specific thresholds online with correctness guarantees. In contrast, our work is the first to enhance cache hit rates by improving the similarity measure itself, integrating multi-vector retrieval (MVR) and MaxSim. Multi-Vector Retrieval Multi-vector retrieval (MVR) overcomes the representational limitations of single-vector dense retrieval by encoding queries and documents as sets of vectors, scored via the MaxSim operator from ColBERT (Khattab & Zaharia, 2020). While subsequent work has primarily focused on improving the efficiency of MVR systems (Santhanam et al., 2021; 2022; Gao et al., 2021; Li et al., 2022), recent research (Liu et al., 2025) demonstrates the critical impact of query segmentation granularity on performance and introduces an adaptive segmentation strategy guided by retrieval accuracy. Diverging from this approach—which uses heuristic document segmentation—our method (MVR-cache) jointly optimizes the segmentation of both new queries and cached documents. Additional query reformulation work is discussed in Appendix C.1.
Additional experimental results. Further analyses, including ablations on the embedding model, training set size, and a detailed per-prompt online overhead breakdown, are provided in Appendix D.
5. Related work Semantic Caching Current efforts to improve semantic cache hit rates largely focus on optimizing caching policies through similarity measures between prompts. While some works fine-tune embedding models to align prompts and responses (Zhu et al., 2024; ZHANG et al., 2023), these approaches lack generalizability to closed-source models and are susceptible to distribution shifts (Hajipour et al., 2022). Hence, the state-of-the-art methods avoid model
6. Conclusion We present MVR-cache that integrates MVR with a learnable segmentation model. We derive a training objective that maximize hit rates while preserving correctness guarantees and formulate segmentation as a reinforcement learning for the combinatorial optimization problem.
9
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Acknowledgements
Gao, L., Dai, Z., and Callan, J. Coil: Revisit exact lexical match in information retrieval with contextualized inverted list. In North American Chapter of the Association for Computational Linguistics, pp. 3030–3042. Association for Computational Linguistics, 2021. doi: 10.18653/V1/2021.NAACL-MAIN.241.
This work is supported by “The Fundamental Research Funds for the Central Universities, Peking University”.
Impact Statement This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Hajipour, H., Yu, N., Staicu, C.-A., and Fritz, M. Simscood: Systematic analysis of out-of-distribution generalization in fine-tuned source code models. In NAACL-HLT, pp. 1400–1416, 2022. doi: 10.18653/v1/2024.findings-naacl. 90.
References
Hurst, O. A., Lerer, A., Goucher, A. P., Perelman, A., Ramesh, A., Clark, A., Ostrow, A., Welihinda, A., Hayes, A., Radford, A., et al. Gpt-4o system card. arXiv preprint arXiv:2410.21276, 2024.
Azad, H. K. and Deepak, A. Query expansion techniques for information retrieval: a survey. Information Processing & Management, 56(5):1698–1735, 2017. doi: 10.1016/j. ipm.2019.05.009.
Khattab, O. and Zaharia, M. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 39–48, 2020. doi: 10.1145/3397271.3401075.
Bang, F. Gptcache: An open-source semantic cache for llm applications enabling faster answers and cost savings. In NLPOSS, pp. 212–218. Empirical Methods in Natural Language Processing, 2023. doi: 10.18653/v1/2023. nlposs-1.24.
Li, J., Xu, C., Wang, F., Riedemann, I. M. v., Zhang, C., and Liu, J. Scalm: Towards semantic caching for automated chat services with large language models. In International Workshop on Quality of Service, pp. 1–10. IEEE, IEEE, 2024. doi: 10.1109/IWQoS61813.2024.10682957.
Bergman, S., Ji, Z., Kermarrec, A.-M., Petrescu, D., Pires, R., Randl, M., and Vos, M. d. Leveraging approximate caching for faster retrieval-augmented generation. In EuroMLSys, pp. 66–73. ACM, 2025. doi: 10.1145/3721146.3721941. Berto, F., Hua, C., Park, J., Kim, M., Kim, H.-S., Son, J., Ye, H., Kim, H., Kim, J., and Park, J. RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark. In Knowledge Discovery and Data Mining, 2023. doi: 10.1145/3711896.3737433. URL https: //github.com/ai4co/rl4co.
Li, M., Lin, S.-C., Oguz, B., Ghoshal, A., Lin, J., Mehdad, Y., Yih, W.-t., and Chen, X. Citadel: Conditional token interaction via dynamic lexical routing for efficient and effective multi-vector retrieval. In Annual Meeting of the Association for Computational Linguistics, pp. 11891– 11907, 2022. doi: 10.48550/arXiv.2211.10411.
Chen, J., Xiao, S., Zhang, P., Luo, K., Lian, D., and Liu, Z. Bge m3-embedding: Multi-lingual, multifunctionality, multi-granularity text embeddings through self-knowledge distillation. Annual Meeting of the Association for Computational Linguistics, 4(5):2318–2335, 2024. doi: 10.18653/v1/2024.findings-acl.137.
Liu, Y., Li, J., Wu, Y., and Chen, Z. Poqd: Performanceoriented query decomposer for multi-vector retrieval. In International Conference on Machine Learning, 2025. doi: 10.48550/arXiv.2505.19189. Luo, C., Lakshman, V., Shrivastava, A., Cao, T., Nag, S., Goutam, R., Lu, H., Song, Y., and Yin, B. Rose: Robust caches for amazon product search. In The Web Conference, pp. 89–93. ACM, 2022. doi: 10.1145/3487553. 3524213.
Craswell, N., Campos, D., Mitra, B., Yilmaz, E., and Billerbeck, B. Orcas: 18 million clicked query-document pairs for analyzing search. In International Conference on Information and Knowledge Management, pp. 2983–2989. ACM, 2020. doi: 10.1145/3340531.3412779.
Malkov, Y. A. and Yashunin, D. A. 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, 2016. doi: 10.1109/TPAMI.2018.2889473.
Dasgupta, S., Wagh, A., Parsai, L., Gupta, B., Vudata, G., Sangal, S., Majumdar, S., Rajesh, H., Banerjee, K., and Chatterjee, A. wallmartcache: A distributed, multi-tenant and enhanced semantic caching system for llms. In International Conference on Pattern Recognition, pp. 232–248. Springer, 2024. doi: 10.1007/978-3-031-78183-4 15.
Ni, J., Li, J., and McAuley, J. Justifying recommendations using distantly-labeled reviews and fine-grained aspects. 10
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
In Conference on Empirical Methods in Natural Language Processing, pp. 188–197. Association for Computational Linguistics, 2019. doi: 10.18653/v1/D19-1018.
Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S. Glue: A multi-task benchmark and analysis platform for natural language understanding. In BlackboxNLP@EMNLP, pp. 353–355. Association for Computational Linguistics, 2018. doi: 10.18653/v1/W18-5446.
Qian, H. and Dou, Z. Explicit query rewriting for conversational dense retrieval. In Conference on Empirical Methods in Natural Language Processing, pp. 4725–4737. Association for Computational Linguistics, 2022. doi: 10.18653/v1/2022.emnlp-main.311.
Wang, L., Yang, N., Huang, X., Jiao, B., Yang, L., Jiang, D., Majumder, R., and Wei, F. Text embeddings by weaklysupervised contrastive pre-training. arXiv.org, 2022. Wang, X., Macdonald, C., and Ounis, I. Deep reinforced query reformulation for information retrieval. arXiv.org, 2020.
Rajpurkar, P., Jia, R., and Liang, P. Know what you don’t know: Unanswerable questions for squad. In Annual Meeting of the Association for Computational Linguistics, pp. 784–789. Association for Computational Linguistics, 2018. doi: 10.18653/v1/P18-2124.
Williams, R. J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machinemediated learning, 8(3):229–256, 2004. doi: 10.1023/A: 1022672621406.
Ren, Q., Dunham, M. H., and Kumar, V. Semantic caching and query processing. IEEE transactions on knowledge and data engineering, 15(1):192–210, 2003. doi: 10. 1109/TKDE.2003.1161590.
Xiong, H., Bian, J., Li, Y., Li, X., Du, M., Wang, S., Yin, D., and Helal, S. When search engine services meet large language models: visions and challenges. IEEE Transactions on Services Computing, 17(6):4558–4577, 2024. doi: 10.1109/TSC.2024.3451185.
Santhanam, K., Khattab, O., Saad-Falcon, J., Potts, C., and Zaharia, M. Colbertv2: Effective and efficient retrieval via lightweight late interaction. In North American Chapter of the Association for Computational Linguistics, pp. 3715–3734, 2021. doi: 10.18653/v1/2022.naacl-main. 272.
ZHANG, Q., Xu, L., Fang, J., Tang, Q., Wu, Y. N., Tighe, J., and Xing, Y. Threshold-consistent margin loss for openworld deep metric learning. In International Conference on Learning Representations, 2023.
Santhanam, K., Khattab, O., Potts, C., and Zaharia, M. Plaid: an efficient engine for late interaction retrieval. In International Conference on Information and Knowledge Management, pp. 1747–1756, 2022. doi: 10.1145/ 3511808.3557325.
Zhu, H., Zhu, B., and Jiao, J. Efficient prompt caching via embedding similarity. arXiv.org, 2024. doi: 10.48550/ arXiv.2402.01173. Zhu, K., Zhao, Q., Chen, H., Wang, J., and Xie, X. Promptbench: A unified library for evaluation of large language models. arXiv.org, 25(254):1–22, 2023. doi: 10.48550/arXiv.2312.07910.
Schroeder, L. G., Desai, A., Cuadron, A., Chu, K., Liu, S., Zhao, M., Krusche, S., Kemper, A., Zaharia, M., and Gonzalez, J. vcache: Verified semantic prompt caching. arXiv preprint arXiv:2502.03771, 2025. Sutton, R. S. and Barto, A. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 2005. doi: 10.1109/TNN.1998.712192. Talmor, A., Herzig, J., Lourie, N., and Berant, J. Commonsenseqa: A question answering challenge targeting commonsense knowledge. In North American Chapter of the Association for Computational Linguistics, pp. 4149– 4158, 2019. doi: 10.18653/v1/N19-1421. Tu, Y., Su, W., Zhou, Y., Liu, Y., Lin, F., Liu, Q., and Ai, Q. Generalized pseudo-relevance feedback. In Proceedings of the ACM Web Conference 2026, pp. 1876–1886, 2025. doi: 10.1145/3774904.3792078. Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. Neural Information Processing Systems, 28, 2015. 11
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
A. Proof A.1. Preliminary for the Proof Definition A.1 (Two similarity metrics). Let svcache be the similarity score between one prompt and its nearest neighbor in the cache store using the conventional SVR-based cosine similarity score, svcache (·). Likewise, let sMVR-cache be the similarity score under the learned similarity metric snew (·) in MVR-cache. Both are assumed to be random variables in [0, 1]. We write sm for m ∈ {vcache, MVR-cache}. Definition A.2 (Class-conditional probability distribution). Assume each sm admits class-conditional densities on [0, 1]: f1 (s) := f (s | C = 1),
f0 (s) := fm (s | C = 0),
and corresponding CDFs f1 , f0 . The marginal density is the mixture p(s) := f (s) = πf1 (s) + (1 − π)f0 (s), where π = Pr(C = 1). Definition A.3. The population-level MLE loss is defined as: MLE(P0 , P1 ) = E[BCELoss(L(s; t, γ), c)] =
1 1 EP1 log(1 + e−γ(s−t) ) + EP0 log(1 + eγ(s−t) ) . 2 2
Assumption A.4 (Balanced distribution assumption). We further assume that π = Pr(C = 1) = Pr(C = 0) = 0.5, Assumption A.5 (Equal-variance location model; correct specification). For each method m ∈ {vcache, MVR-cache}, we assume that the similarity score conditioned on the label c (which is equal to 0 or 1), s(x) | (C = c), follows Gaussian distribution: s(x) | (C = 1) ∼ P1 = N (µ1 , σ 2 ),
s(x) | (C = 0) ∼ P0 = N (µ0 , σ 2 ),
where sm (x) denotes the similarity score between a prompt x and its nearest neighbor from the cache store using either vcache or MVR-cache, µc is the mean of the Gaussian distribution, dependent on the method m and the annotation label, c. We further assume an identical standard deviation of these normal distributions across different c and m. Hence, fc (c = 0 or 1) defined in Definition A.2 denotes the density function of a Gaussian distribution, i.e.: 1 (s − µc )2 exp(− ) (11) 2σ 2 2πσ Lemma A.6 (Closed-form posterior and logistic parameters). Under Assumption A.5, the correctness probability defined in Equation (2), η(s) := Pr(C = 1 | S = s) is rewritten as follows: 1 η(s) = , (12) 1 + exp{−γ(s − t)} with fc (s) = f (s|C = c) = √
γ=
µ1 − µ0 , σ2
t=
µ1 + µ0 . 2
Proof. By Bayes’ rule, η(s) Pr(C = 1 | s) Pr(s | C = 1) Pr(C = 1) f1 (s) = = = . 1 − η(s) Pr(C = 0 | s) Pr(s | C = 0) Pr(C = 0) f0 (s) 12
(13)
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Taking logs and substituting fc with Equation (11), yielding f1 (s) η(s) = log log 1 − η(s) f0 (s) (s − µ1 )2 − (s − µ0 )2 =− 2σ 2 2 (s − 2sµ1 + µ21 ) − (s2 − 2sµ0 + µ20 ) =− 2σ 2 µ21 − µ20 µ1 − µ0 s− = σ2 2σ 2 µ1 − µ0 µ1 + µ0 = s − . σ2 2
(14)
η(s) Furthermore, according to the definition of η(s) in Equation (12), log 1−η(s) is further derived as:
log
η(s) 1 = log = γ(s − t) 1 − η(s) exp{−γ(s − t)}
0 . By comparing the above formula against Equation (14), we can obtain γ := (µ1 − µ0 )/σ 2 and thus t = µ1 +µ 2
A.2. Proof of Theorem 3.3 Theorem A.7. Let ∆ := µ1 − µ0 . Under the above assumptions, the population-level MLE loss, MLE(P0 , P1 ) satisfies: 1. MLE(P0 , P1 ) depends on (P0 , P1 ) only through ∆. 2. MLE(P0 , P1 ) is strictly decreasing in ∆ for 0 < ∆ < 1. 3. Consequently, the global minimum of MLE(P0 , P1 ) over all feasible (P0 , P1 ) is attained at µ1 = 1,
µ0 = 0.
Proof. Step 1: Explicit form of the risk Since the class prior is balanced, the population risk can be written as MLE(P0 , P1 ) =
1 1 EP log(1 + e−γ(s−t) ) + EP0 log(1 + eγ(s−t) ) . 2 1 2
Substituting γ = ∆/σ 2 and t = (µ1 + µ0 )/2, we obtain 1 ∆ µ1 + µ0 1 ∆ µ1 + µ0 MLE(P0 , P1 ) = EP1 log 1 + exp − 2 s − + EP0 log 1 + exp 2 s − . 2 σ 2 2 σ 2 Step 2: Translation invariance. Define the centered variable u := s −
µ1 + µ0 . 2
Then
∆ ∆ , E[u | y = 0] = − . 2 2 Under equal variance and bounded support, the distributions of u | y = 1 and u | y = 0 are translations of each other. Therefore, the joint law of u depends on (P0 , P1 ) only through ∆. Hence, E[u | y = 1] =
MLE(P0 , P1 ) = MLE(∆), which proves statement (1). 13
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Step 3: Derivative with respect to ∆. Differentiating under the expectation (justified by bounded support and smoothness), " " # # u u dMLE 1 1 + 2 EP0 . = − 2 EP1 d∆ 2σ 2σ 1 + exp σ∆2 u 1 + exp − σ∆2 u d
Using the symmetry u | y = 0 = −u | y = 1, this simplifies to " # dMLE u 1 . = − 2 EP1 d∆ σ 1 + exp σ∆2 u Step 4: Sign of the derivative. Under P1 , the random variable u has strictly positive mean ∆/2 and bounded support. The function u g(u) = 1 + exp σ∆2 u has strictly positive expectation for ∆ > 0. Therefore, dMLE <0 d∆
for all ∆ ∈ (0, 1),
which proves statement (2). Step 5: Optimality under bounded scores. Since s ∈ [0, 1], we have 0 ≤ µ0 ≤ µ1 ≤ 1
⇒
0 ≤ ∆ ≤ 1.
Because MLE(∆) is strictly decreasing on [0, 1], its minimum is attained at ∆ = 1, i.e., µ1 = 1,
µ0 = 0.
This proves statement (3). Theorem A.7 indicates that adapting the similarity score s by minimizing the population-level MLE loss can push µ1 and µ0 to 1 and 0, respectively, thus maximizing the gap between these two variables, which is equivalent to maximizing γ. Plus, the following lemma suggests the stability of the value of t throughout training: Lemma A.8 (Midpoint Stability). Under the above assumptions, the value of t is invariant under the gradient flow of the following logistic loss: ℓ(s, y) = −y log g(s) − (1 − y) log(1 − g(s)), in which, g(s) = σ(γ(s − t)) If each score s is updated via ṡ = −
∂ℓ = −γ(g(s) − y), ∂s
then ṫ = 0, Proof. The logistic loss for a sample (s, y) is ℓ(s, y) = −y log g(s) − (1 − y) log(1 − g(s)), with gradient ∂ℓ = γ(g(s) − y). ∂s 14
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
The dynamics of the class means are: µ̇1 = E[ṡ | y = 1] = −γ E[g(s) − 1 | y = 1] = γ E[1 − g(s) | y = 1], µ̇0 = E[ṡ | y = 0] = −γ E[g(s) − 0 | y = 0] = −γ E[g(s) | y = 0]. Thus the midpoint evolves according to ṫ =
µ̇1 + µ̇0 γ = (E[1 − g(s) | y = 1] − E[g(s) | y = 0]) . 2 2
Since f1 and f0 are the density function of two normal distributions of the same variance while t is the mid point of the means of these two normal distributions, then f1 (t + δ) = f0 (t − δ). Plus, based on the definition of the function g(·), g(t + δ) = 1 − g(t − δ) holds. Hence, we have Z Z E[1 − g(s) | y = 1] = (1 − g(t + δ)) f1 (t + δ) dδ = g(t − δ) f0 (t − δ) dδ = E[g(s) | y = 0]. Hence, ṁ =
γ (E[g(s) | y = 0] − E[g(s) | y = 0]) = 0. 2
At the same time, the inter-class separation evolves as d (µ1 − µ0 ) = µ̇1 − µ̇0 = γ (E[1 − g(s) | y = 1] + E[g(s) | y = 0]) > 0, dτ which is strictly positive as long as µ1 < 1 and µ0 > 0. Therefore, t is stable while the separation grows monotonically. The above analysis suggests that minimizing the MLE loss can maximize µ1 , minimize µ0 , maximize γ, and maintain the value of t. Hence, for those samples with positive labels, L(s; t, γ) increases, and τ defined in Equation (4) decreases, thus decreasing the exploration probability and increasing the cache hit rate while the same error bound τ remains fixed. A.3. Proof of Lemma 3.4 In the case of the imbalanced class distribution, we can then consider the following class-balanced version of the MLE loss: X 1 X 1 X [ · log(1 + e−γ(s−t) ) + log(1 + eγ(s−t) )], π 1 − π y=1 y=0 i in which the class prior π = Pr(c = 1) could be estimated by the ratio of the positive samples in the training set. The corresponding population-level MLE loss is thus derived as: 1 1 MLE(P0 , P1 ) = E[BCELoss(L(s; t, γ), c)] = Pr(c = 1) EP1 · log(1 + e−γ(s−t) ) + Pr(c = 0) EP0 · log(1 + eγ(s−t) ) π 1−π −γ(s−t) γ(s−t) = EP1 log(1 + e ) + EP0 log(1 + e ) This indicates that the population-level MLE loss remains the same. Hence, we can follow the same proof of Theorem 3.3 to prove Lemma 3.4.
B. Additional experimental setup B.1. Additional details for baseline methods We provide the details of adapting ColBert and POQD to vCache as follows, which both use the symmetric MaxSim score as the similarity measure as MVR-cache: 15
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
• ColBert(Khattab & Zaharia, 2020): As a pioneering MVR method, it decomposes text into individual tokens and embeds each separately. We adapt it for vCache by encoding tokens from cached and new prompts to produce sequences of embeddings. • POQD(Liu et al., 2025): A state-of-the-art MVR segmentation method that fine-tunes the prompt prefix for a generalpurpose LLM to segment queries. For documents in storage, POQD applies heuristic decomposition (e.g., splitting into sentences). Accordingly, we segment cached prompts by sentences, while segmenting incoming prompts using POQD, where fine-tuning is performed using the same training set as MVR-cache. B.2. Configurations for MVR-cache Throughout the experiments, the candidate split positions Px are defined as the indices of all punctuation marks in the prompt x. To enable efficient retrieval during inference, we use a two-stage retrieval pipeline. We first construct an HNSW index (Malkov & Yashunin, 2016) on the single-vector representations of cached prompts and retrieve the Top-20 nearestneighbor candidates. We then rerank these candidates using the learned segmentation-aware MaxSim score SMaxSimΘ to select the final nearest neighbor. Thus, MVR-cache uses single-vector retrieval only as a coarse candidate generator and does not require the single-vector Top-1 result to be correct, as long as the correct neighbor is included in the Top-20 candidates. We validate this design on PromptBench: this two-stage retrieval pipeline achieves a nearest-neighbor recall of 0.179, which is close to 0.183 from a full MVR scan over the entire cache, while avoiding the substantially higher overhead of exhaustive multi-vector retrieval. This small gap indicates that Top-20 single-vector retrieval preserves most relevant candidates, and the MVR reranker can correct many single-vector Top-1 errors. While recent methods such as PLAID (Santhanam et al., 2022) enable efficient retrieval directly over multi-vector data, our preliminary tests show that they introduce substantial computational overhead and do not meet our real-time inference requirements.
C. Additional Discussion C.1. Additional Related Work on Query Reformulation A related line of retrieval work improves matching quality through query expansion (QE) and pseudo-relevance feedback (PRF), which reformulate the original query using related or feedback-derived terms (Azad & Deepak, 2017; Tu et al., 2025). These methods offer a different latency–quality trade-off from embedding-based approaches: they can improve recall with relatively low overhead, but primarily rely on lexical reformulation rather than learned semantic matching. Recent work further extends this direction with learning-based query reformulation, including reinforcement-learning methods (Wang et al., 2020) and neural rewriting for conversational search (Qian & Dou, 2022). Similar ideas also appear in semantic and approximate caching systems (Ren et al., 2003; Bergman et al., 2025), including ROSE (Luo et al., 2022), which improves cache robustness to misspellings and approximate matches through rewriting. Our method is related in spirit to query reformulation, but differs in both objective and mechanism. Instead of generating rewritten queries, MVR-cache learns a variable-number segmentation of each prompt and matches the resulting segments to cached prompts using a learned segmentation-aware similarity function. This allows the cache to compare prompts at a finer semantic granularity without replacing the original prompt with a rewritten textual form. C.2. Limitations and Future Work MVR-cache currently segments prompts as linear text sequences. This design applies directly to multi-turn conversations by concatenating the system prompt, dialogue history, and current user query before segmentation. Extending the method to multimodal inputs requires new decomposition mechanisms, such as region-level units for images or temporal units for audio, and is left for future work.
D. Additional experimental results We include the experimental results with varied values of δ in this section.
16
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 8. The cumulative cache hit rate VS increasing number of incoming prompts with δ = 0.02
Figure 9. The cumulative error rate VS increasing number of incoming prompts with δ = 0.02
D.1. Cache hit and error rate under varied δ We further report the cache hit and error rate by varying δ among {0.015, 0.02, 0.03, 0.05, 0.07, 0.08}. These results are included in Figure 8-19, which suggest that consistent performance gains of MVR-cache in comparison to the baseline methods. D.2. Online overhead breakdown Table 2 reports the average per-prompt latency breakdown. This table complements Table 1: Table 1 reports cumulative end-to-end latency, while Table 2 decomposes the per-prompt cost into segmentation, embedding, retrieval/reranking, and one LLM call. All values are reported in milliseconds. As shown in Table 2, the online non-LLM overhead of MVR-cache is small compared with the latency of a single LLM call. The main additional cost comes from the lightweight segmentation step, while retrieval/reranking remains below 0.4 ms per prompt. Therefore, even for infrequent queries where this overhead cannot be amortized over many cache hits, LLM inference remains the dominant cost.
Figure 10. The cumulative cache hit rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.03
17
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 11. The cumulative error rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.03
Figure 12. The cumulative cache hit rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.05
Figure 13. The cumulative error rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.05
Figure 14. The cumulative cache hit rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.07
18
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 15. The cumulative error rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.07
Figure 16. The cumulative cache hit rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.08
Figure 17. The cumulative error rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.08
Figure 18. The cumulative cache hit rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.015
19
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 19. The cumulative error rate VS increasing number of incoming prompts under the cache-on-miss protocol with δ = 0.015
Figure 20. Cumulative error rate e VS increasing number of incoming prompts under the always-cache protocol with δ = 0.01.
D.3. Ablation studies We further perform ablation studies for MVR-cache using the promptbench dataset with the error bound δ = 0.01. First of all, in Figure 21, we compare the effect of MVR-cache using varied embedding models including the default BGE model, GTE Large model (Wang et al., 2022) and E5-large (Wang et al., 2022), which suggest that there is almost no performance difference for MVR-cache between different embedding models. In addition, we also vary the number of training samples for training the segmentation model. As Figure 22 shows, regardless of the training set sizes, MVR-cache ends up with almost the same performance. This thus indicates that a training set with 3K training samples is sufficient to obtain a reasonable segmentation model. In the main experiments, we use punctuation marks as candidate split positions. To test whether this design choice limits the segmentation policy, we compare it with three alternative candidate sets on PromptBench while keeping the rest of the MVR-cache pipeline fixed: keyword-level boundaries, token-level boundaries, and sentence-level boundaries. Keyword-level boundaries include punctuation marks and selected keywords such as “and” and “or”; token-level boundaries
Figure 21. Ablation on embedding models
20
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 22. Ablation on the training set size
Figure 23. Comparison of using the symmetric MaxSim score and the vanilla MaxSim score
21
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation Table 2. Average per-prompt latency breakdown. All values are in milliseconds. The non-LLM total excludes the LLM call.
Dataset
Method
Seg.
Emb.
Ret./rerank
Non-LLM total
LLM call
SemCacheCls.
MVR-cache vCache
23.00 –
32.00 25.00
0.35 0.20
55.35 25.20
1234.60 1234.60
SemCacheSQ
MVR-cache vCache
28.00 –
32.00 23.00
0.35 0.20
60.35 23.20
3004.20 3004.20
PromptBench
MVR-cache vCache
22.00 –
32.00 25.00
0.35 0.30
54.35 25.30
3352.00 3352.00
QNLI
MVR-cache vCache
23.00 –
32.00 20.00
0.35 0.30
55.35 20.30
4273.00 4273.00
Figure 24. Sensitivity analysis of candidate split positions on PromptBench. We report the cumulative cache hit rate as the number of incoming prompts increases.
include punctuation marks and spaces; sentence-level boundaries include punctuation marks excluding commas; and punctuation-level boundaries correspond to our default setting. Figure 24 shows the cumulative cache hit rate as the number of incoming prompts increases. The curves are highly similar across all candidate sets, indicating that giving the policy a larger set of possible split positions does not lead to a meaningful improvement. In particular, punctuation-level splitting remains competitive with, and slightly better than, the larger candidate sets in the final cache hit rate. This suggests that punctuation marks already provide a compact and effective search space for prompt segmentation in our setting. We also report the number of segments selected by the learned policy in Table 3. The average segment count is close to one for short search queries and increases for longer question-answering prompts. This shows that the policy does not use a fixed segmentation length, but adapts the number of segments to the input structure. In the end, we also replace the symmetric MaxSim score, i.e., SMaxSim, used in MVR-cache with the vanilla MaxSim score, which is unidirectional. The results are reported in Figure 23, which reveals a slight performance gain if the symmetric MaxSim score is used. D.4. Qualitative Example on Long-Context Prompts We further examine whether MVR-cache remains effective for very long prompts. Long-context inputs are challenging for semantic caching because a single-vector representation can dilute local semantic details. A long prompt may contain many repeated or related sub-questions, and the information that determines response equivalence may appear only in specific parts of the input. As a result, single-vector retrieval may retrieve a broadly related but response-inequivalent nearest neighbor. 22
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation Table 3. Statistics of the number of segments selected by MVR-cache.
DATASET
M IN
M AX
M EAN
S EM C ACHE S EARCH Q UERIES S EM C ACHE C LASSIFICATION QNLI P ROMPT B ENCH
1 1 1 1
4 93 149 262
1.01 2.64 5.31 7.67
Table 4. A qualitative long-context example. The incoming prompt is about the CASA 1000 electricity transmission project. MVR-cache retrieves a response-equivalent CASA 1000 prompt and produces a cache hit, while vCache retrieves a response-inequivalent prompt about solar hot water systems and misses the cache.
Incoming prompt excerpt “Describe the project named CASA 1000. What is the intended purpose of the CASA 1000 project? . . . CASA 1000 will transmit 1000 MW of surplus electricity from Tajikistan to Pakistan with power transit through Afghanistan. . . . Further clarify the role and involvement of Tajikistan, Pakistan, and Afghanistan. . . . Describe potential risks, timeline, budget, revenue sharing, and regional impacts.” Method
Retrieved nearest-neighbor prompt excerpt
Result
vCache
“Explain in detail the capacity of a solar hot water system . . . including global installations as of 2007, approximately 154 thermal gigawatt (GWth). . . . What does this capacity represent in terms of the number of homes, hospitals, or businesses that can be supported? . . . Describe the geographical distribution of these installations and the average system size.”
Miss
MVR-cache
“The CASA 1000 project promotes regional energy security through regional cooperation. . . . Explain how regional cooperation on energy projects like CASA 1000 enhances regional energy security. . . . Describe the planned project objectives, participating countries, infrastructure deployment, risks, and regional economic implications.”
Hit
Table 4 shows a representative example. The incoming prompt contains around 10K tokens and consists of many subquestions about the CASA 1000 electricity transmission project. To make the example readable, we show only representative excerpts from the incoming prompt and the retrieved nearest-neighbor prompts, omitting repeated sub-questions with ellipses. The difference comes from how the two methods represent the long prompt. vCache compresses the entire prompt into one embedding. In this example, the retrieved prompt is broadly energy-related, but it concerns solar hot water capacity rather than the CASA 1000 project. Since the two prompts require different LLM responses, vCache misses the cache. In contrast, MVR-cache decomposes the long prompt into multiple segments and compares them with cached prompts using SMaxSimΘ . The learned segments preserve specific local semantics, such as the project goal, the participating countries, implementation risks, and regional impacts. These segment-level matches allow MVR-cache to retrieve a nearest neighbor from the same response-equivalence set and produce a correct cache hit. This example illustrates why variable-length segmentation is useful for long-context prompts: the relevant matching evidence may be distributed across several local spans and can be obscured by a single global representation. D.5. Empirically validate Assumption 3.1 Recall that our theoretical results rely on Assumption 3.1, which states that the class-conditional distributions of the learned segmentation-aware similarity scores approximately follow normal distributions. To empirically validate this assumption, we evaluate the learned SMaxSimΘ scores on all four datasets. Specifically, for each dataset, we randomly sample prompts and compute their similarity scores against their retrieved nearest-neighbor prompts, then group the scores according to their corresponding labels. As shown in Figures 25 - 28, the resulting class-conditional score distributions are approximately normal across all datasets, providing empirical support for Assumption 3.1. For the additional assumption used in Theorem 3.3, i.e., Assumption 3.2, we acknowledge that it may be strong in practice. To address this, Lemma 3.4 shows that under Assumption 3.1 alone, minimizing the class-rebalanced objective still improves the cache hit rate under the same error bound. Therefore, since Assumption 3.1 is empirically supported across all four datasets, the theoretical implication of Lemma 3.4 remains meaningful. 23
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 25. Empirically validate Assumption 3.1 on SemCacheSearchClassification dataset
Figure 26. Empirically validate Assumption 3.1 on SemCacheSearchQueries dataset
Figure 27. Empirically validate Assumption 3.1 on PromptBench dataset
24
MVR-cache : Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
Figure 28. Empirically validate Assumption 3.1 on QNLI dataset
25