传统缓存策略在语义检索中失效,新方法通过学习提升缓存效率。
When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers

- 基于后悔累积和贝叶斯在线学习,动态调整缓存内容与更新时机
- 实验显示比先进缓存策略提升5%至75%,且在小缓存下表现更优
- 适合需要高效利用历史经验的LLM智能体系统
大语言模型智能体日益依赖检索缓冲区存储和复用过往经验,但其缓存管理策略仍多为随意设定。本文将此问题形式化为具有切换成本的在线语义缓存替换问题,其中项目通过嵌入相似度匹配,命中质量为连续值而非二值。在MemoryBench-Full的两个数据集(LoCoMo、DialSim)上,对8种替换策略的实验发现:经典启发式方法(如LRU、LFU)在语义工作负载下始终劣于朴素的FIFO基线,原因在于缺乏时间局部性和频率集中性。为此提出SOLAR,一种学习增强框架,通过后悔累积确定修改时机(约17%修改率),并基于隐式检索反馈的贝叶斯在线学习进行内容选择。理论证明SOLAR具有不依赖缓存大小和时间跨度的常数竞争比(≤3),优于FIFO的Ω(K);其淘汰后悔为O(√KT log T),逼近Ω(√KT)的下界。实验表明,在紧致缓存尺寸下,相对FIFO提升5%–75%,且在工作集边界处出现清晰相变。在5000项池的合成实验中进一步揭示池大小与检索质量呈倒U型关系,支持容量限制作为检索噪声现象而非存储瓶颈。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。