Search papers, labs, and topics across Lattice.
This paper introduces a theoretical framework for semantic caching of LLM responses in a continuous query space, addressing the limitations of existing discrete query caching methods. They use dynamic $\epsilon$-net discretization combined with Kernel Ridge Regression to quantify estimation uncertainty and generalize feedback across continuous semantic query neighborhoods. The proposed online algorithm achieves sublinear regret against an optimal continuous oracle, demonstrating improved caching performance and reduced overhead compared to existing methods.
LLM caching can be rigorously optimized in continuous query spaces, enabling better performance and lower overhead than discrete methods.
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 $\epsilon$-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.
