Search papers, labs, and topics across Lattice.
This paper addresses the inefficiencies of traditional cache management policies in semantic retrieval buffers used by LLM agents, formalizing the problem as an online semantic cache replacement issue with switching costs. Through experiments on two datasets, it is shown that classic heuristics like LRU and LFU consistently underperform compared to a naive FIFO baseline due to their inability to leverage temporal locality and frequency concentration. The proposed SOLAR framework, which utilizes regret accumulation for modification timing and Bayesian online learning for content selection, achieves significant improvements in retrieval performance, demonstrating a constant competitive ratio and matching theoretical lower bounds.
Classic cache policies like LRU and LFU fail in semantic retrieval, while the new SOLAR framework achieves up to 75% improvement over FIFO by leveraging learning-augmented strategies.
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.\ $\Omega(K)$ for FIFO), and eviction regret $O(\sqrt{KT\log T})$, matching the $\Omega(\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.
