When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers

• URL: http://arxiv.org/abs/2607.00394v1
• Date: Wed, 01 Jul 2026 03:38:42 GMT
• Title: When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers
• Abstract summary: LLM agents increasingly rely on retrieval buffers to store and reuse past experience.<n>We formalize this as an online semantic cache replacement problem with switching costs.<n>We propose SOLAR, a learning-augmented framework that derives modification timing from regret accumulation.
• Score: 43.46514805933049
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: LLM agents increasingly rely on retrieval buffers to store and reuse past experience, yet the cache management policies governing these buffers remain largely ad-hoc. We formalize this as an online semantic cache replacement problem with switching costs, where items are matched by embedding similarity and hit quality is continuous rather than binary. Through experiments on two datasets from MemoryBench-Full (LoCoMo, DialSim) with 8 replacement policies, we reveal a surprising finding: classic heuristics (LRU, LFU) \emph{consistently underperform} the naive FIFO baseline on semantic workloads, due to the absence of temporal locality and frequency concentration. We propose SOLAR, a learning-augmented framework that derives modification timing from regret accumulation (achieving $\sim$17\% modification rate) and content selection from Bayesian online learning over implicit retrieval feedback. We prove SOLAR achieves a constant competitive ratio $\leq 3$, independent of cache size and horizon (vs.\ $Ω(K)$ for FIFO), and eviction regret $O(\sqrt{KT\log T})$, matching the $Ω(\sqrt{KT})$ lower bound up to logarithmic factors. Experiments demonstrate 5--75\% relative improvement over FIFO at tight cache sizes, with a clearly characterized phase transition at the working set boundary. Synthetic experiments with 5000-item pools further reveal an inverted-U relationship between pool size and retrieval quality, justifying capacity constraints as a retrieval noise phenomenon rather than a storage limitation.

Related papers

• Continuous Semantic Caching for Low-Cost LLM Serving [29.887977985331972]
  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.<n>Existing caching frameworks have proposed to decide which query responses to cache by assuming a finite, known universe of discrete queries.<n>We establish the first rigorous theoretical framework for semantic LLM response caching in continuous query space under uncertainty.
  arXiv  Detail & Related papers  (2026-04-21T21:56:43Z)
• LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference [87.57291812372848]
  We treat optimal cache selection as a knapsack problem and employ an accumulation-based strategy to balance computational overhead and cache updates.<n>We prove that the regret of our algorithm achieves an $O(sqrtMNT)$ bound, improving the coefficient of $sqrtMN$ compared to the $O(MNsqrtT)$ in Berkeley.<n>We also provide a problem-dependent bound, which was absent in previous works.
  arXiv  Detail & Related papers  (2025-09-19T01:39:08Z)
• Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation [54.61034867177997]
  Caching inference responses allows them to be retrieved without another forward pass through the Large Language Models.<n>Traditional exact-match caching overlooks the semantic similarity between queries, leading to unnecessary recomputation.<n>We present a principled, learning-based framework for semantic cache eviction under unknown query and cost distributions.
  arXiv  Detail & Related papers  (2025-08-11T06:53:27Z)
• Lookahead Q-Cache: Achieving More Consistent KV Cache Eviction via Pseudo Query [48.52389201779425]
  KV cache memory usage grows substantially with longer text sequences.<n>Existing KV cache eviction methods prune tokens using prefilling-stage attention scores.<n>Lookahead Q-Cache generates low-cost pseudo lookahead queries to better approximate the true decoding-stage queries.
  arXiv  Detail & Related papers  (2025-05-24T10:34:38Z)
• CacheFocus: Dynamic Cache Re-Positioning for Efficient Retrieval-Augmented Generation [6.544043376474944]
  Large Language Models (LLMs) excel across a variety of language tasks yet are constrained by limited input lengths and high computational costs.<n>Existing approachestextemdash partially alleviate these issues but often require additional training or suffer from performance degradation with longer inputs.<n>We introduce textbftextitCacheFocus, a method that enhances length normalization and reduces inference latency without any further training.
  arXiv  Detail & Related papers  (2025-02-16T12:33:16Z)
• Training-Free Exponential Context Extension via Cascading KV Cache [49.608367376911694]
  We introduce a novel mechanism that leverages cascading sub-cache buffers to selectively retain the most relevant tokens.<n>Our method reduces prefill stage latency by a factor of 6.8 when compared to flash attention on 1M tokens.
  arXiv  Detail & Related papers  (2024-06-24T03:59:17Z)
• MeanCache: User-Centric Semantic Caching for LLM Web Services [8.350378532274405]
  Caching is a natural solution to reduce inference costs on repeated queries.<n>This paper introduces MeanCache, a user-centric semantic cache for LLM-based services.<n>MeanCache identifies semantically similar queries to determine cache hit or miss.
  arXiv  Detail & Related papers  (2024-03-05T06:23:50Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  We propose a novel caching paradigm, that we named approximate-key caching. While approximate cache hits alleviate DL inference workload and increase the system throughput, they however introduce an approximation error. We analytically model our caching system performance for classic LRU and ideal caches, we perform a trace-driven evaluation of the expected performance, and we compare the benefits of our proposed approach with the state-of-the-art similarity caching.
  arXiv  Detail & Related papers  (2021-12-13T13:49:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.