# Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 28 of its 42 references that are in the map.
- First posted on arXiv 11 Aug 2025.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

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

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models](https://mlsanity.com/paper/2211.10438/) (2022)
- [LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale](https://mlsanity.com/paper/2208.07339/) (2022)
- [FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU](https://mlsanity.com/paper/2303.06865/) (2023)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Prompt Cache: Modular Attention Reuse for Low-Latency Inference](https://mlsanity.com/paper/2311.04934/) (2023)
- [From Words to Watts: Benchmarking the Energy Costs of Large Language Model Inference](https://mlsanity.com/paper/2310.03003/) (2023)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023)
- [Mobile Edge Intelligence for Large Language Models: A Contemporary Survey](https://mlsanity.com/paper/2407.18921/) (2024)
- [SpotServe: Serving Generative Large Language Models on Preemptible Instances](https://mlsanity.com/paper/2311.15566/) (2023)
- [ServerlessLLM: Low-Latency Serverless Inference for Large Language Models](https://mlsanity.com/paper/2401.14351/) (2024)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Survey of Vector Database Management Systems](https://mlsanity.com/paper/2310.14021/) (2023)
- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [SCALM: Towards Semantic Caching for Automated Chat Services with Large Language Models](https://mlsanity.com/paper/2406.00025/) (2024)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Multinomial Logit Bandit with Low Switching Cost](https://mlsanity.com/paper/2007.04876/) (2020)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Cache me if you Can: an Online Cost-aware Teacher-Student framework to Reduce the Calls to Large Language Models](https://mlsanity.com/paper/2310.13395/) (2023)
- [Similarity Caching: Theory and Algorithms](https://mlsanity.com/paper/1912.03888/) (2019)
- [A Unified Online-Offline Framework for Co-Branding Campaign Recommendations](https://mlsanity.com/paper/2505.22254/) (2025)

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

- [HARBOR: Automated Harness Optimization](https://mlsanity.com/paper/2604.20938/) (2026)
- [Scaling the Long Video Understanding of Multimodal Large Language Models via Visual Memory Mechanism](https://mlsanity.com/paper/2603.29252/) (2026)
- [Prompt Injection Mitigation with Agentic AI, Nested Learning, and AI Sustainability via Semantic Caching](https://mlsanity.com/paper/2601.13186/) (2026)
- [MemBoost: A Memory-Boosted Framework for Cost-Aware LLM Inference](https://mlsanity.com/paper/2603.26557/) (2026)
- [Hallucination Mitigation with Agentic AI, Nested Learning, and AI Sustainability via Semantic Caching](https://mlsanity.com/paper/2605.29055/) (2026)
- [Closing the Operational Gap in Semantic Caching](https://mlsanity.com/paper/2606.19719/) (2026)
- [Semantic Caching and Intent-Driven Context Optimization for Multi-Agent Natural Language to Code Systems](https://mlsanity.com/paper/2601.11687/) (2026)
- [POLAR: Online Learning for LoRA Adapter Caching and Routing in Edge LLM Serving](https://mlsanity.com/paper/2604.16583/) (2026)
- [Continuous Semantic Caching for Low-Cost LLM Serving](https://mlsanity.com/paper/2604.20021/) (2026)
- [FinCacheServe: Dependency-Consistent Answer Reuse for Cost-Efficient RAG Serving over Mutable Enterprise Documents](https://mlsanity.com/paper/2607.26076/) (2026)
- [PHOENIX: Fine-Tuned SLM-Powered Autonomous Satellite Lifetime Extension via Predictive Self-Healing and Multi-Agent AI Recovery](https://mlsanity.com/paper/2608.07126/) (2026)
- [Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders](https://mlsanity.com/paper/2608.20280/) (2026)
- [Semantic Views: Certified Reuse of LLM Labels Across Semantic Queries](https://mlsanity.com/paper/2610.12768/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) are revolutionizing how users interact with information systems, yet their high inference cost poses serious scalability and sustainability challenges. Caching inference responses, allowing them to be retrieved without another forward pass through the LLM, has emerged as one possible solution. Traditional exact-match caching, however, overlooks the semantic similarity between queries, leading to unnecessary recomputation. Semantic caching addresses this by retrieving responses based on semantic similarity, but introduces a fundamentally different cache eviction problem: one must account for mismatch costs between incoming queries and cached responses. Moreover, key system parameters, such as query arrival probabilities and serving costs, are often unknown and must be learned over time. Existing semantic caching methods are largely ad-hoc, lacking theoretical foundations and unable to adapt to real-world uncertainty. In this paper, we present a principled, learning-based framework for semantic cache eviction under unknown query and cost distributions. We formulate both offline optimization and online learning variants of the problem, and develop provably efficient algorithms with state-of-the-art guarantees. We also evaluate our framework on a synthetic dataset, showing that our proposed algorithms perform matching or superior performance compared with baselines.