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

arXiv: https://arxiv.org/abs/2607.00394 · HTML: https://mlsanity.com/paper/2607.00394/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Agent memory systems, one of 16 directions in LLM agents and tool use.
- Builds on 12 of its 43 references that are in the map.
- First posted on arXiv 1 Jul 2026.

## Placed in

- LLM agents and tool use / [Agent memory systems](https://mlsanity.com/agents/agent-memory-systems/)

## Builds on (most cited first, 12 of 12)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [MemGPT: Towards LLMs as Operating Systems](https://mlsanity.com/paper/2310.08560/) (2023)
- [Evaluating Very Long-Term Conversational Memory of LLM Agents](https://mlsanity.com/paper/2402.17753/) (2024)
- [A Survey on the Memory Mechanism of Large Language Model based Agents](https://mlsanity.com/paper/2404.13501/) (2024)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [MemoryBench: A Benchmark for Memory and Continual Learning in LLM Systems](https://mlsanity.com/paper/2510.17281/) (2025)
- [Adaptive Memory Admission Control for LLM Agents](https://mlsanity.com/paper/2603.04549/) (2026)
- [KERAG: Knowledge-Enhanced Retrieval-Augmented Generation for Advanced Question Answering](https://mlsanity.com/paper/2509.04716/) (2025)
- [Beyond Heuristics: A Decision-Theoretic Framework for Agent Memory Management](https://mlsanity.com/paper/2512.21567/) (2025)
- [Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency](https://mlsanity.com/paper/2507.16242/) (2025)

## Built on by (most cited first, 1 of 1)

- [Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders](https://mlsanity.com/paper/2608.20280/) (2026)

## Abstract (arXiv)

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) 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 ~17% modification rate) and content selection from Bayesian online learning over implicit retrieval feedback. We prove SOLAR achieves a constant competitive ratio ≤ 3, independent of cache size and horizon (vs. Omega(K) for FIFO), and eviction regret O(√KTlog T), matching the Omega(√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.