MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation

Ali Noshad, Zishan Zheng, Yinjun Wu · 2026

Read MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation by Ali Noshad, Zishan Zheng, Yinjun Wu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24914.txt.

Introduction

Ali Noshad leads MVR-cache, a semantic cache for language models cutting cost and wait time. It spots when a new prompt matches one already answered. Current caches lean on crude similarity scores, capping hit rates. MVR-cache splits prompts with a learned segmentation model, then compares pieces with fine-grained multi-vector retrieval. Its training goal comes from theory tying the objective to cache hits under strict correctness rules. Reinforcement learning handles the non-differentiable optimization, and hit rates rise by up to about a third.

Catalog record

CREATORAli Noshad, Zishan Zheng, Yinjun Wu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68413
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.24914

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation Ali Noshad, Zishan Zheng, Yinjun Wu Abstract 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 1 Introduction Semantic caching has emerged as an effective mechanism for reducing the latency and computational cost of large language model (LLM) inference ( 32 ; 23 ) . Traditional caches based on exact string matches fail to exploit the underlying semantic 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 ( 2 ; 7 ) . Production examples include Azure semantic caching option for LLM APIs 1 1 1 https://learn.microsoft.com/en-us/azure/api-management/azure-openai-enable-semantic-caching , and LiteLLM caching system 2 2 2 https://docs.litellm.ai/docs/proxy/caching 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 ( 7 ; 12 ; 2 ) 1 1 footnotemark: 1 2 2 footnotemark: 2 compare such similarity scores against a global threshold to decide the cache’s reuse, while the recently proposed vCache method ( 23 ) 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. For instance, we draw a prompt, x , from the SemCacheClassification dataset ( 23 ) in Figure 1 , which is a positive review of an adult crime drama. In a standard cosine similarity lookup, this prompt returns x_{1} as the nearest neighbor. While x_{1} 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 x_{1} compared to x , resulting in a cache miss despite their high topical similarity. Figure 1 : A motivating example from the SemCacheClassification dataset ( 23 ) . Using a single embedding per prompt, a new query x about whether an adult crime drama review is friendly finds its nearest neighbor ( x_{1} ) 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, x_{2} . By embedding these segments, the segmentation-aware MaxSim score of x_{2} to x exceeds that of other cached prompts, thus allowing the reuse of the cached response of x_{2} for a cache hit. 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 ( 11 ) , MVR decomposes both queries and documents into fine-grained 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 ( 11 ) 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 ( 14 ) has shown this to be suboptimal, demonstrating that optimized segmentation is key to unlocking MVR’s full potential. 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 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 x_{2} 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. 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) ( 4 ) task, where we design a reward function directly informed by our theoretical objective, enabling effective gradient-based learning of the segmentation model. 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, MVR-cache 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

Read the complete text