Continuous Semantic Caching for Low-Cost LLM Serving

arXiv:2604.20021 · cs.LG, cs.CL · Submitted 2026-04-21 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Continuous Semantic Caching for Low-Cost LLM Serving".

Tom: Continuous Semantic Caching for Low-Cost LLM Serving establishes a rigorous theoretical framework for caching responses in an infinite, continuous query space under uncertainty, bridging discrete optimization with continuous representation spaces.

Jane: First, who's behind it and why it matters.

Paper summary: Tom: Hey Jane, so we're diving into this paper now: "Continuous Semantic Caching for Low-Cost LLM Serving." Basically, it tackles the problem of caching LLM responses when the queries are in an infinite, continuous space where we don't even know the query arrival probabilities or serving costs.

Jane: That sounds intense, Tom. So what's the core thesis here regarding this continuous query space and how they plan to handle that uncertainty?

Tom: Well, the paper proposes a rigorous theoretical framework for caching responses in this infinite space under uncertainty, bridging discrete optimization with continuous representation spaces <ref:2604.20021#pg0>. They set up the problem by modeling queries as coming from a probability density function over this continuous space where the serving cost and arrival probability are unknown.

Lu: The idea of modeling queries from a probability density function in an infinite space sounds really exciting, Tom; it suggests we can move beyond just looking at discrete query sets and address the real complexity of user interaction <ref:2604.20021#pg1>.

Meng: From a practical standpoint, how does this framework actually translate into something useful for serving requests when you don't know the cost or arrival rates beforehand?

Jane: They tackle this by introducing an epsilon-net discretization, which partitions the query space into Voronoi regions based on semantic similarity <ref:2604.20021#pg0>. This discretization allows them to approximate a continuous loss function defined as integral (two) L (M; f, c, d) = ∫ X f (x) min(c(x), phi (d (x,M))) <ref:2604.20021#pg0>.

Tom: Right, so they're using this net to approximate the continuous loss function where that loss function balances the expected LLM cost against the mismatch cost of serving a cached response <ref:2604.20021#pg1>. It sounds like a clever way to manage that uncertainty.

Lalam: I see how partitioning space helps tame infinity; for me, this concept means we can design systems that adapt their caching strategy dynamically based on semantic proximity rather than relying on fixed, pre-defined query buckets <ref:2604.20021#pg1>.

Meng: That leads me to the practical side: what are the key components they build for implementing this approach? Are we talking about a simple lookup or something more complex?

Jane: They have three distinct algorithmic settings they implement, depending on whether you're in an oracle setting, an offline setting, or an online adaptive setting <ref:2604.20021#pg1>. In the oracle setting, they use a "Reverse Greedy algorithm with provable approximation and discretization guarantees" <ref:2604.20021#pg1>.

Paper summary: Tom: And then for when we have historical data, they propose CUCB-SC-Cont, which uses Kernel Ridge Regression to estimate serving costs and query arrival probabilities from that data <ref:2604.20021#pg1>. It’s a solid approach for learning the continuous cost function across the space.

Lu: The use of Kernel Ridge Regression to estimate costs over a continuous space is really interesting; it shifts the estimation burden from having perfect knowledge upfront to learning a smooth function from observations <ref:2604.20021#pg1>. It opens up possibilities for modeling cost distributions we couldn't even think of before.

Jane: And then there's the CLCB-SC-LS-Cont setting for online adaptation, which dynamically constructs and expands a representative set of queries on the fly using two main mechanisms <ref:2604.20021#pg1>. This shows they've thought about handling real-time query streams effectively.

Tom: The theoretical guarantees they provide are also pretty compelling; for instance, in the oracle setting, they show a suboptimality guarantee where the discretized loss is approximated by the continuous loss with an error scaling linearly with the covering radius epsilon <ref:2604.20021#pg1>.

Meng: I'm looking at those guarantees now, and it seems important that for the offline setting, they derive a suboptimality gap bound that breaks down into three terms relating to arrival estimation error, cost estimation error, and discretization error <ref:2604.20021#pg1>. That decomposition helps us pinpoint where the errors are coming from.

Lalam: If we can quantify those errors separately, we can target the specific component that needs improvement in our serving infrastructure, which is much more actionable than just getting a single performance number <ref:2604.20021#pg1>.

Jane: And for the online setting, under Assumption two about Cluster-Based Arrival Distribution, they show the cumulative regret is bounded by a sublinear rate of O(˜√ T) <ref:2604.20021#pg1>. That sublinear bound is quite optimistic for an adaptive system dealing with continuous spaces.

Tom: And this leads into the empirical results which are showing some really strong performance gains; for example, CUCB-SC-Cont achieves the "lowest suboptimality gap" in the offline setting, yielding up to a seventy-three point three two percent improvement over prior methods <ref:2604.20021#pg1>.

Lu: A seventy-three point three two percent improvement is significant when you're dealing with cost optimization; it suggests that learning the continuous cost function via KRR is much more effective than previous heuristic approaches <ref:2604.20021#pg1>.

Meng: On the practical side, if we look at Figure six which varies the cache size k, CUCB-SC-Cont maintains the "lowest absolute loss across every tested cache size," which is a strong indicator of its robustness <ref:2604.20021#pg1>.

Lalam: That robustness across different cache sizes means we don't have to worry as much about tuning that specific parameter before deployment, which simplifies the engineering pipeline considerably <ref:2604.20021#pg1>.

Paper summary: Jane: So, to wrap up this section on the paper "Continuous Semantic Caching for Low-Cost LLM Serving," we've seen how they move from a discrete assumption to a continuous one and provide formal bounds for both offline learning and online adaptation <ref:2604.20021#pg1>.

Tom: Absolutely, and the implications are huge because it gives us a way to handle the massive query space of modern AI applications without getting bogged down in intractable assumptions about query sets.

Lu: I think the biggest implication is that we can start designing LLM serving systems that are inherently more cost-aware by leveraging these semantic relationships directly, rather than treating them as separate, discrete problems <ref:2604.20021#pg1>.

Meng: Practically speaking, this means a system could dynamically decide whether to call the expensive LLM or use a cached response based on how semantically close the new query is to what we've seen before <ref:2604.20021#pg1>.

Lalam: For my work in culture improvement, this suggests we could create personalized, highly relevant interactions that feel more intuitive because the system understands the underlying semantic intent rather than just matching keywords <ref:2604.20021#pg1>.

Jane: So, to summarize this part of the paper's discussion on "Continuous Semantic Caching for Low-Cost LLM Serving," it establishes a formal way to cache in an infinite space using epsilon-nets and cost estimation techniques that offer strong theoretical bounds <ref:2604.20021#pg1>.

Tom: Exactly, and the implications are huge because it gives us a way to handle the massive query space of modern AI applications without getting bogged down in intractable assumptions about query sets.

Conclusion: Tom: So we've been talking about how this paper tackles caching LLM responses when queries are in an infinite, continuous space under uncertainty <ref:2604.20021#pg1>. Now we're getting to the wrap-up, and I want to make sure everyone is clear on what this means for the real world.

Jane: Exactly. We’ve looked at how they use epsilon-nets and Kernel Ridge Regression to manage that continuous space, moving away from fixed query sets <ref:2604.20021#pg1>. It really boils down to giving the AI system a smart way to decide when it should serve a cached response versus making an expensive call.

Lu: I think the core idea is pretty elegant, Jane; they are building this theoretical backbone that lets us treat semantic similarity as a continuous metric rather than just discrete buckets <ref:2604.20021#pg1>. It’s like mapping out the entire semantic landscape smoothly.

Meng: From my side, the practical impact is huge because it means we can build serving systems that are inherently more cost-aware without having to pre-define every possible query <ref:2604.20021#pg1>. It addresses a real bottleneck in scaling these AI services <ref:2604.20021#pg1>.

Lalam: And for me, the vision this paper brings is that we can create interactions where the system understands the user's underlying intent at a continuous level, which could profoundly improve how we design personalized experiences in culture and learning <ref:2604.20021#pg1>.

Tom: That’s a big picture for you, Lalam. So, to recap this paper by its title "Continuous Semantic Caching for Low-Cost LLM Serving," the authors have laid out a formal mathematical structure for handling those tricky continuous query problems <ref:2604.20021#pg1>.

Jane: And they’ve shown that with their new methods, we can get strong guarantees about performance, even when we don't know the costs or arrival rates upfront <ref:2604.20021#pg1>. This moves us toward more robust and efficient AI infrastructure.

Lu: It really shows that discrete optimization isn't the only way to approach these problems; you can successfully apply continuous methods here too <ref:2604.20021#pg1>. The way they handle the geometry of the query space is what gets my attention.

Meng: I just wonder about the implementation complexity, though; building a system that dynamically estimates costs across a continuous function needs to be very stable in practice <ref:2604.20021#pg1>. It’s not always simple engineering, you know?

Lalam: But think about the potential for how this understanding of semantic intent could shape future AI interfaces, making them feel more intuitive and deeply connected to what we're actually trying to communicate <ref:2604.20021#pg1>.

Tom: Exactly! So, we’ve seen that these papers are doing serious math to make LLM serving cheaper and smarter by embracing the continuous nature of language <ref:2604.20021#pg1>. We've got a lot more to unpack on how this could fundamentally change how we deploy AI models.

Carnegie Mellon University · University of Washington Tacoma · City University of Hong Kong · Microsoft Research Asia

cs.LG, cs.CL

Submitted: 2026-04-21

Updated: 2026-10-06

Importance score: 91/100

The gist: Continuous Semantic Caching for Low-Cost LLM Serving establishes a rigorous theoretical framework for caching responses in an infinite, continuous query space under uncertainty, bridging discrete

Key concepts

ε-net: An ε-net is a method used to partition an infinite continuous query space into finite, manageable regions. These regions are defined by semantic similarity, creating a discrete structure that allows the system to approximate the complex continuous loss function without needing a predefined net.
Loss Function L(M; f , c, d): This function measures the total cost of serving queries in a set M. It integrates over all possible queries (f(x)), taking the minimum between two values: either the actual LLM serving cost c(x) or a threshold phi(d(x,M)) based on how far the query x is from the cached set M.
KRR: Kernel Ridge Regression is used to estimate unknown quantities like LLM serving costs and arrival probabilities. Instead of relying on every single query's empirical cost, KRR learns a continuous cost function across the entire space, providing confidence bounds based on how many cost samples were observed.

Terminology

Regret — 74× in this paper · explained in 3 episodes
Embeddings — 13× in this paper · explained in 2 episodes
Ablation — 10× in this paper · explained in 1 episode
Generalization — 10× in this paper · explained in 13 episodes
Loss Function — 10× in this paper · explained in 2 episodes
Quantization — 9× in this paper · explained in 12 episodes
Kernel Ridge Regression — 8× in this paper
Information Gain — 6× in this paper · explained in 2 episodes
Theoretical Guarantees — 6× in this paper · explained in 2 episodes
Benchmark — 5× in this paper · explained in 2 episodes
Semantic Similarity — 5× in this paper · explained in 2 episodes
Adaptation — 4× in this paper · explained in 1 episode
Intrinsic Dimension — 4× in this paper · explained in 2 episodes
Online Adaptation — 4× in this paper · explained in 3 episodes
Transformer — 4× in this paper · explained in 2 episodes
Clustering — 3× in this paper · explained in 2 episodes
Combinatorial Multi-Armed Bandit — 3× in this paper
Core — 3× in this paper · explained in 2 episodes
Large Language Models (LLMs) — 3× in this paper · explained in 6 episodes
Regularization — 3× in this paper · explained in 3 episodes
Speculative Decoding — 3× in this paper · explained in 2 episodes
Active Exploration — 2× in this paper · explained in 2 episodes
Adaptive Algorithm — 2× in this paper · explained in 1 episode
Robustness — 2× in this paper · explained in 5 episodes
Ablation study — 1× in this paper · explained in 1 episode
Action Space — 1× in this paper · explained in 1 episode
Adam — 1× in this paper · explained in 2 episodes
Benchmarking — 1× in this paper · explained in 3 episodes
Hilbert Space — 1× in this paper · explained in 2 episodes
Principal Component Analysis — 1× in this paper
Reproducing Kernel Hilbert Space (RKHS) — 1× in this paper · explained in 3 episodes
Transformer Models — 1× in this paper · explained in 2 episodes
Uniform Manifold Approximation and Projection — 1× in this paper
Verification — 1× in this paper · explained in 2 episodes

Summary

Continuous Semantic Caching for Low-Cost LLM Serving establishes a rigorous theoretical framework for caching responses in an infinite, continuous query space under uncertainty, bridging discrete optimization with continuous representation spaces.

How it works

The system models queries as being drawn from a probability density function over a continuous space where the serving cost and arrival probability are unknown. To handle the infinite space, the authors introduce an epsilon-net discretization that partitions the query space into Voronoi regions based on semantic similarity. This allows for approximating the continuous loss function, which is defined as:

(2) L (M; f, c, d) = ∫ X f (x) min(c(x), phi (d (x,M)))

The core decision rule at each round compares the expected LLM cost against the mismatch cost of serving a cached response:

(1) a t = LLM(x) if c(x) ≤ phi (d (x,M)) otherwise.

Key Components and Algorithms

The framework is implemented through three distinct algorithmic settings:

In the oracle setting, the authors use an oracle setting with full information to provide a Reverse Greedy algorithm with provable approximation and discretization guarantees.
In the offline setting, they propose CUCB-SC-Cont, which uses Kernel Ridge Regression (KRR) to estimate serving costs and query arrival probabilities from historical data. This involves building an epsilon-net S over observed embeddings and using KRR to estimate the cost function across the continuous space.
In the online adaptive setting, they introduce CLCB-SC-LS-Cont, which dynamically constructs and expands a representative set of queries on the fly. This involves two main mechanisms:

(Algorithm 3)

(Algorithm 4)

Theoretical Guarantees and Guarantees

The theoretical analysis provides several guarantees across different settings:

A suboptimality guarantee for the oracle setting, showing that the discretized loss is approximated by the continuous loss with an error scaling linearly with the covering radius epsilon: L (M) − L (Mb;S) ≤ Lgepsilon.
For the offline learning algorithm (CUCB-SC-Cont), a suboptimality gap bound is derived, which decomposes into three terms corresponding to arrival estimation error, cost estimation error, and discretization error. The final bound relates this gap to the total sample size n:

(Theorem 4.1)

For the online algorithm (CLCB-SC-LS-Cont), under Assumption 2 (Cluster-Based Arrival Distribution), the cumulative regret is bounded by a sublinear rate of O(˜√ T). This bound decomposes into terms related to arrival estimation, cost estimation, discretization error, and switching costs.

Performance Evaluation

Extensive empirical evaluations were conducted on synthetic and real-world datasets.

(Figure 2)

The offline setting shows that CUCB-SC-Cont achieves the lowest suboptimality gap in the offline setting, yielding up to a 73.32% improvement over prior methods. In the online setting, CLCB-SC-LS-Cont outperforms baselines regarding final average regret, with up to 72.41% and 43.14% reductions observed on synthetic and bursty real-world query streams, respectively, while maintaining competitive runtime.

(Figure 6)

A study varying the cache size (k) shows that CUCB-SC-Cont maintains the lowest absolute loss across every tested cache size.

Key Novelty

The paper introduces several key algorithmic and theoretical advancements over discrete settings:

The use of an epsilon-net to partition the continuous query space, allowing for a finite representation without assuming a pre-defined net.
Replacing per-query empirical estimates with KRR to learn a continuous cost function across the space, leading to confidence bounds that depend on the number of observed cost samples rather than total queries.
Deriving geometry-aware bounds on the KRR posterior width by linking local sample counts within Voronoi cells to nearest-neighbor radii and RKHS distances under the RBF kernel.
The online algorithm incorporates a low-switching constraint, designing adaptive thresholds that minimize cache switching while managing traditional algorithm regret.

Conclusion

The work establishes the first rigorous theoretical framework for semantic caching in a continuous query space under uncertainty for low-cost LLM serving, providing suboptimality and sublinear regret guarantees coupled with empirical evaluations demonstrating significant reduction in regret.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed Continuous Semantic Caching for Low-Cost LLM Serving. This paper introduces a sophisticated theoretical framework to move semantic caching from discrete query spaces to continuous embedding spaces, addressing the fundamental challenge of infinite query diversity while maintaining strong performance guarantees.

Here are the specific improvements this research enables for AI systems and what those improved systems can achieve:

) Improved AI System Capabilities: Semantic Caching for Low-Cost LLM Serving in Continuous Query Spaces

The core improvement is the transition from heuristic, discrete caching models to a mathematically rigorous, continuous optimization framework. The resulting system will be capable of serving LLM requests with guaranteed low latency and minimal cost by intelligently leveraging semantic similarity.

Here are the specific improvements:

Continuous Query Space Modeling via epsilon-Net Discretization:

This framework replaces the intractable problem of optimizing over an infinite query space with a finite, manageable optimization problem by partitioning the space using an epsilon-net.

What it enables: The AI system can now effectively cache responses for queries that are not exact matches but are semantically close (within a radius epsilon). This allows the system to generalize caching decisions across continuous semantic neighborhoods, drastically reducing cache misses compared to existing methods that rely on exact text matching.

Cost Learning via Kernel Ridge Regression (KRR):

Instead of assuming known query costs, the framework learns the serving cost function c(x) across the continuous embedding space using KRR on observed data (offline or online). This learning is coupled with an uncertainty quantification mechanism.

Adaptive Online Learning with Low Switching Costs (CLCB-SC-LS-Cont):

The proposed online algorithm, CLCB-SC-LS-Cont, is designed to operate in real-time streams while actively managing the trade-off between exploration (querying the LLM) and exploitation (serving from the cache). It incorporates a stage-based switching mechanism that dynamically adjusts based on observation uncertainty.

Theoretical Guarantees on Sublinear Regret:

The paper provides formal proofs showing that the online algorithm achieves a sublinear regret bound of O(√T) against an optimal continuous oracle, even in the presence of continuous query spaces and unknown costs.

Geometry-Aware Optimal Discretization:

The research derives a piecewise optimal discretization radius epsilon∗ that depends on the intrinsic dimension (p) and embedding dimension (de) of the query space.

In summary, this improved AI system can:

Serve LLM requests with guaranteed low latency and minimal operational cost by intelligently predicting which semantically similar responses to keep in a cache.
Adapt its caching strategy dynamically in real-time as user query patterns evolve, minimizing the costly overhead of cache updates.
Maintain high performance and predictable scaling by achieving sublinear regret bounds, ensuring long-term efficiency even in infinite query environments.