Continuous Semantic Caching for Low-Cost LLM Serving

Baran Atalar, Xutong Liu, Jinhang Zuo, Siwei Wang, Wei Chen, Carlee Joe-WongarXiv 2026 · arXiv

TL;DR

Serving Large Language Models (LLMs) is incredibly expensive, but caching responses to semantically similar queries can dramatically reduce costs. This paper introduces the first rigorous theoretical framework for semantic caching in an infinite, continuous query space. By combining dynamic discretization ($\epsilon$-nets) with Kernel Ridge Regression, the authors deliver algorithms that significantly cut down LLM latency and compute costs with provable performance guarantees.

What Problem Does This Paper Address?

While LLMs like ChatGPT are wildly popular, they suffer from high inference latencies and massive computational costs. To mitigate this, systems use semantic caching—storing query-response pairs so that if a user asks something semantically close to a previous query, the system can return the cached answer instead of running a costly new LLM inference pass.

However, existing caching frameworks operate under a major flaw: they assume a finite, known universe of discrete queries. In reality, user prompts are practically infinite and vary continuously. When queries are mapped into continuous embedding spaces, traditional caching algorithms break down. They struggle to estimate query arrival probabilities and execution costs for previously unseen prompts, and they face a "reverse feedback" problem: when a query is served from the cache, the system never learns what it would have actually cost to run on the LLM.

Methods

The authors bridge the gap between discrete optimization and continuous representation spaces by introducing a novel geometric and machine learning approach:

  1. Continuous-to-Discrete Reduction via $\epsilon$-Nets: To make optimization over an infinite space tractable, the system dynamically partitions the continuous embedding space into Voronoi regions using an $\epsilon$-net. The cache is then designed by selecting at most one representative query per region.
  2. Kernel Ridge Regression (KRR): Because cost feedback is sparse (only observed when the LLM is actually invoked), the framework uses KRR in a Reproducing Kernel Hilbert Space (RKHS). This allows the system to generalize partial feedback and quantify estimation uncertainty across continuous semantic neighborhoods.

Using these tools, the authors design algorithms for three settings:

  • Oracle Setting: A Reverse Greedy algorithm that provides provable approximation guarantees when costs and arrival distributions are known.
  • Offline Setting (CUCB-SC-Cont): A pessimistic learning algorithm that utilizes historical deployment logs to build the $\epsilon$-net and estimate costs.
  • Online Adaptive Setting (CLCB-SC-LS-Cont): An online algorithm that dynamically constructs the $\epsilon$-net on the fly from incoming queries. It uses adaptive thresholds to balance exploration and exploitation while minimizing "switching costs" (the overhead of updating the cache).
Figure 1: Continuous semantic caching system for low-cost LLM serving, showing query arrivals, service from the cache or LLM, and cache updates.

Datasets

The framework was evaluated on two distinct benchmarks:

  • Synthetic Benchmark: A collection of 50 natural language prompts spanning diverse domains, where continuous space was simulated by adding Gaussian noise to the prompt embeddings.
  • Real-World Benchmark (NQ + TriviaQA): A combined dataset of 5,000 real-world queries (2,500 from Natural Questions and 2,500 from TriviaQA). Queries were mapped to a 384-dimensional vector space using sentence-transformers, and a highly non-uniform, bursty stream was simulated using a log-normal popularity distribution.

Key Insights and Ideas

  • The Power of Continuous Generalization: Unlike discrete models that estimate parameters for each query independently, this framework leverages kernel similarity. Observing the cost of one query reduces the uncertainty for all nearby queries in the continuous space.
  • Real-World Queries Naturally Cluster: In a worst-case scenario, optimizing over a continuous space would lead to an exponential explosion of regret. However, the authors justify a "Cluster-Based Arrival Distribution" assumption by showing that real-world user queries naturally concentrate into dense semantic neighborhoods rather than spreading uniformly.
  • Sublinear Regret in Infinite Spaces: The authors successfully prove that their online adaptive algorithm achieves a sublinear regret bound ($\tilde{O}(\sqrt{T})$) against an optimal continuous oracle, effectively matching the theoretical efficiency of discrete models despite operating in an infinite action space.

Key Results

  • Offline Superiority: In the offline setting, CUCB-SC-Cont achieved the lowest suboptimality gap, demonstrating up to a 73.32% improvement over prior discrete methods when historical data was sparse.
  • Online Regret Reduction: In online streams, the CLCB-SC-LS-Cont algorithm outperformed all baselines, yielding a 72.41% reduction in final average regret on synthetic data and a 43.14% reduction on the bursty real-world dataset compared to standard discrete semantic caching.
  • Maintained Efficiency: Despite the added complexity of KRR and dynamic $\epsilon$-net adjustments, the online algorithm maintained a processing latency nearly identical to heuristic baselines, proving its viability for production environments.

Limitations and Future Work

While this work lays a solid theoretical foundation, the authors note a few areas for improvement. First, the current framework relies on a pre-defined distance metric and kernel function, which might need manual tuning for different embedding models. Second, future work includes establishing formal lower bounds for the continuous semantic caching problem and developing even finer mathematical characterizations of realistic query distributions to further optimize caching strategies.

Summary updated

Abstract

As Large Language Models (LLMs) become increasingly popular, caching responses so that they can be reused by users with semantically similar queries has become a vital strategy for reducing inference costs and latency. Existing caching frameworks have proposed to decide which query responses to cache by assuming a finite, known universe of discrete queries and learning their serving costs and arrival probabilities. As LLMs' pool of users and queries expands, however, such an assumption becomes increasingly untenable: real-world LLM queries reside in an infinite, continuous embedding space. In this paper, we establish the first rigorous theoretical framework for semantic LLM response caching in continuous query space under uncertainty. To bridge the gap between discrete optimization and continuous representation spaces, we introduce dynamic $ε$-net discretization coupled with Kernel Ridge Regression. This design enables the system to formally quantify estimation uncertainty and generalize partial feedback on LLM query costs across continuous semantic query neighborhoods. We develop both offline learning and online adaptive algorithms optimized to reduce switching costs incurred by changing the cached responses. We prove that our online algorithm achieves a sublinear regret bound against an optimal continuous oracle, which reduces to existing bounds for discrete query models. Extensive empirical evaluations demonstrate that our framework approximates the continuous optimal cache well while also reducing computational and switching overhead compared to existing methods.
BibTeX
@misc{atalar2026continuous,
  author = {Baran Atalar and Xutong Liu and Jinhang Zuo and Siwei Wang and Wei Chen and Carlee Joe-Wong},
  title = {{Continuous Semantic Caching for Low-Cost LLM Serving}},
  year = {2026},
  eprint = {2604.20021},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.20021},
}

Loading related content...

Figure