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:
- 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.
- 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).
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-Contachieved 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-Contalgorithm 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