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

Jul 16, 2026

LLM agents depend on retrieval buffers to reuse past experience, yet buffer cache management often follows ad-hoc rules. This work formalizes the task as an online semantic cache replacement problem with switching costs, using embedding-similarity matching and continuous hit quality. Experiments on two MemoryBench-Full datasets (LoCoMo, DialSim) with eight replacement policies show classic heuristics (LRU, LFU) underperform naive FIFO for semantic workloads. The paper introduces SOLAR, a learning-augmented method that learns modification timing from regret accumulation and content selection from Bayesian online learning, with proven competitive guarantees and capacity-constrained retrieval noise behavior.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages13

Reading Time33 min

Abstract

Introduction

Retrieval buffer architecture and cache analogy

Current practice and motivation for experiments

Experimental setup and surprising findings

Method: SOLAR (learning-augmented replacement)

Theoretical analysis and guarantees

Experiments and phase transition observations

When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers Yushi Sun∗ LIGHTSPEED, Tencent Shenzhen, China [ysunbp@connect.ust.hk](ysunbp@connect.ust.hk) Bowen Cao∗ The Chinese University of Hong Kong Hong Kong, China [bwcao@link.cuhk.edu.hk](bwcao@link.cuhk.edu.hk) Wai Lam The Chinese University of Hong Kong Hong Kong, China [wlam@se.cuhk.edu.hk](wlam@se.cuhk.edu.hk) arXiv :2607 .00394v 1 [ cs .DB] 1 Jul 2026 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) 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 achievesa constant competitive ratio ≤ 3, independent of cache size and horizon (vs. Ω (􀀠) for FIFO), and eviction regret 􀀤( √︁􀀠􀀩 log􀀩 ) , matching the Ω( √􀀠􀀩) lower bound up to logarithmic factors. Experiments demonstrate 5–75% relative improvement over FIFO at tight cache sizes, with a clearly characterized phase transition atthe 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. PVLDB Reference Format: Yushi Sun, Bowen Cao, and Wai Lam. When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers. PVLDB, 14(1): XXX-XXX, 2027 . doi:XX.XX/XXX.XX 1 INTRODUCTION Large language model (LLM) agents are deployed in increasingly complex, long-running tasks: personal assistants maintaining months of conversation history [22], game-playing agents accumulating strategies over thousands of episodes [33], and research agents that iteratively refine their knowledge through tool use [23] . A common architectural pattern has emerged across these systems: the agent maintains a retrieval buffer of past experience that is queried at each ∗ Both authors contributed equally to this research. This work was done during Bowen’s internship at Tencent LIGHTSPEED. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit [https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of](https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of)[ ](https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of)[this license. For any use beyond those covered by this license](this license. For any use beyond those covered by this license), [obtain permission by](obtain permission by)[emailing info@vldb.org. Copyright](emailing info@vldb.org. Copyright) is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097 . doi:XX.XX/XXX.XX step to inform its current response. This buffer serves as the agent’s long-term memory, supplementing the fixed context window of the underlying language model. The retrieval buffer operates as follows. At each interaction step, the agent generates a new experience item: in conversational deployments this is typically a user utterance or a stated preference, while in fully agentic deployments it is more often an environment observation, a tool-invocation result, or a completed subtask trac

FAQs

What problem does the paper study about retrieval buffers in LLM agents?

It studies how to manage a semantic retrieval buffer as an online cache replacement problem, including switching costs and continuous hit quality rather than binary hits.

What surprising experimental result is reported for classic cache heuristics?

Across semantic workloads, classic heuristics like LRU and LFU consistently underperform even the naive FIFO baseline, due to missing temporal locality and frequency concentration.

How does SOLAR improve semantic cache replacement compared with FIFO and classical policies?

SOLAR learns modification timing from regret accumulation and performs content selection using Bayesian online learning over implicit retrieval feedback, achieving measurable improvement and providing competitive guarantees.

Jul 16, 2026

Upload by Lucas Martin