When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers
2026-07-01 • Databases
DatabasesComputation and Language
AI summaryⓘ
The authors study how large language model agents manage memory buffers that store past experiences, focusing on when and what to replace to keep retrieval effective. They show that traditional methods like LRU and LFU perform worse than a simple first-in-first-out (FIFO) approach for these semantic tasks. To improve this, they propose SOLAR, a new learning-based method that smartly decides when and what to update, offering better performance and strong theoretical guarantees. Their experiments confirm SOLAR's advantage, especially when memory is limited, and they also find that bigger memory pools can sometimes hurt retrieval quality due to noise rather than just storage limits.
LLM agentssemantic cache replacementretrieval bufferLRULFUFIFOonline learningBayesian learningcompetitive ratioregret bounds
Authors
Yushi Sun, Bowen Cao, Wai Lam
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.