When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers
Summary
Proposes SOLAR, a learning-augmented framework for semantic cache replacement in LLM agents, outperforming classical heuristics by using regret-based modification timing and Bayesian online learning. Achieves constant competitive ratio and significant improvements over FIFO.
View Cached Full Text
Cached at: 07/09/26, 07:55 AM
Paper page - When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers
Source: https://huggingface.co/papers/2607.00394
Abstract
Research addresses cache management for LLM agents by formalizing semantic cache replacement as an online problem with switching costs, proposing SOLAR—a learning-augmented framework that outperforms traditional heuristics through regret-based modification timing and Bayesian content selection.
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 anonline semantic cache replacementproblem withswitching costs, where items are matched byembedding similarityand 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 fromregret accumulation(achieving sim17\% modification rate) and content selection fromBayesian online learningoverimplicit retrieval feedback. We prove SOLAR achieves a constantcompetitive ratioleq 3, independent of cache size and horizon (vs.\ Ω(K) for FIFO), andeviction regretO(KTlog T), matching the Ω(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 theworking set boundary. Synthetic experiments with 5000-item pools further reveal an inverted-U relationship between pool size andretrieval quality, justifying capacity constraints as a retrieval noise phenomenon rather than a storage limitation.
View arXiv pageView PDFAdd to collection
Get this paper in your agent:
hf papers read 2607\.00394
Don’t have the latest CLI?curl \-LsSf https://hf\.co/cli/install\.sh \| bash
Models citing this paper0
No model linking this paper
Cite arxiv.org/abs/2607.00394 in a model README.md to link it from this page.
Datasets citing this paper0
No dataset linking this paper
Cite arxiv.org/abs/2607.00394 in a dataset README.md to link it from this page.
Spaces citing this paper0
No Space linking this paper
Cite arxiv.org/abs/2607.00394 in a Space README.md to link it from this page.
Collections including this paper0
No Collection including this paper
Add this paper to acollectionto link it from this page.
Similar Articles
Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches
A new semantic-adaptive eviction policy for LLM prefix caches that learns token reuse patterns across different token types, achieving 1.4x-2.7x TTFT improvement over existing policies.
Semantic Cache Distillation: Efficient State Transfer via Reuse and Selective Patching
This paper proposes Semantic Cache Distillation (SCD), a loss-constrained framework that replaces raw KV cache transmission with compact semantic codes, achieving up to 2.65x TTFT speedup while keeping generation quality within 5% F1 of the oracle.
Learning What to Remember: Observability-Safe Memory Retention via Constrained Optimization for Long-Horizon Language Agents
This paper formulates memory retention for long-horizon language agents as a constrained stochastic optimization problem, introducing OSL-MR, a framework that enforces observability-safe learning with a Mixed-Score heuristic. Experiments show consistent improvements over existing heuristic baselines under tight memory budgets.
Meta-Cognitive Memory Policy Optimization for Long-Horizon LLM Agents
Introduces Belief Entropy and Metacognitive Memory Policy Optimization (MMPO) to improve memory quality in long-horizon LLM agents, outperforming existing methods and maintaining performance over long contexts.
Selective Memory Retention for Long-Horizon LLM Agents
This paper presents TraceRetain, a lightweight framework for bounded external memory in frozen LLM agents, demonstrating that selective retention differentiates from cache heuristics primarily when memory streams contain noise, offering task-success and efficiency benefits.