# Efficient Prompt Caching via Embedding Similarity

arXiv: https://arxiv.org/abs/2402.01173 · HTML: https://mlsanity.com/paper/2402.01173/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 43 references that are in the map.
- First posted on arXiv 2 Feb 2024.

## Builds on (most cited first, 26 of 26)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [Atlas: Few-shot Learning with Retrieval Augmented Language Models](https://mlsanity.com/paper/2208.03299/) (2022)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Capabilities of GPT-4 on Medical Challenge Problems](https://mlsanity.com/paper/2303.13375/) (2023)
- [Carbon Emissions and Large Neural Network Training](https://mlsanity.com/paper/2104.10350/) (2021)
- [Pre-training Tasks for Embedding-based Large-scale Retrieval](https://mlsanity.com/paper/2002.03932/) (2020)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Training Language Models with Memory Augmentation](https://mlsanity.com/paper/2205.12674/) (2022)
- [The Cost of Training NLP Models: A Concise Overview](https://mlsanity.com/paper/2004.08900/) (2020)
- [Improving Neural Language Models with a Continuous Cache](https://mlsanity.com/paper/1612.04426/) (2016)
- [Nonparametric Masked Language Modeling](https://mlsanity.com/paper/2212.01349/) (2022)
- [Unbounded cache model for online language modeling with open vocabulary](https://mlsanity.com/paper/1711.02604/) (2017)
- [On Optimal Caching and Model Multiplexing for Large Model Inference](https://mlsanity.com/paper/2306.02003/) (2023)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Evaluating Embedding APIs for Information Retrieval](https://mlsanity.com/paper/2305.06300/) (2023)
- [Regret-Optimal Online Caching for Adversarial and Stochastic Arrivals](https://mlsanity.com/paper/2211.16051/) (2022)
- [Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrability](https://mlsanity.com/paper/2302.03770/) (2023)
- [Learning to Cache and Caching to Learn: Regret Analysis of Caching Algorithms](https://mlsanity.com/paper/2004.00472/) (2020)
- [Provably Efficient Reinforcement Learning via Surprise Bound](https://mlsanity.com/paper/2302.11634/) (2023)

## Built on by (most cited first, 9 of 9)

- [Dipper: Diversity in Prompts for Producing Large Language Model Ensembles in Reasoning tasks](https://mlsanity.com/paper/2412.15238/) (2024)
- [vCache: Verified Semantic Prompt Caching](https://mlsanity.com/paper/2502.03771/) (2025)
- [A Generative Caching System for Large Language Models](https://mlsanity.com/paper/2503.17603/) (2025)
- [TVCACHE: A Stateful Tool-Value Cache for Post-Training LLM Agents](https://mlsanity.com/paper/2602.10986/) (2026)
- [Asynchronous Verified Semantic Caching for Tiered LLM Architectures](https://mlsanity.com/paper/2602.13165/) (2026)
- [The Structural Safety Generalization Problem](https://mlsanity.com/paper/2504.09712/) (2025)
- [LLMBridge: Reducing Costs to Access LLMs in a Prompt-Centric Internet](https://mlsanity.com/paper/2410.11857/) (2024)
- [ODIA: Oriented Distillation for Inline Acceleration of LLM-based Function Calling](https://mlsanity.com/paper/2507.08877/) (2025)
- [MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation](https://mlsanity.com/paper/2605.24914/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have achieved huge success in numerous natural language process (NLP) tasks. However, it faces the challenge of significant resource consumption during inference. In this paper, we aim to improve the inference efficiency of LLMs by prompt caching, i.e., if the current prompt can be answered by the same response of a previous prompt, one can directly utilize that previous response without calling the LLM. Specifically, we focus on the prediction accuracy of prompt caching for single-round question-answering tasks via embedding similarity. The existing embeddings of prompts mostly focus on whether two prompts are semantically similar, which is not necessarily equivalent to whether the same response can answer them. Therefore, we propose a distillation-based method to fine-tune the existing embeddings for better caching prediction. Theoretically, we provide finite-sample guarantees for the convergence of our method under different types of loss functions. Empirically, we carefully construct a hard dataset based on Kwiatkowski et al. (2019) where the existing embedding model (Wang et al., 2022) only achieves an AUC of 0.51. We then fine-tune the above embedding model, which significantly improves the AUC of caching prediction from 0.51 to 0.81. We also conduct simulations demonstrating that our trained models achieve better caching efficiency than the previous embedding model.