Skip to content

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

🕒 Published (v1): 2026-07-01 00:00 UTC · Source: HuggingFace · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Classic cache policies (LRU, LFU, ARC) systematically underperform even naive FIFO on LLM agent retrieval buffers because semantic workloads violate the temporal-locality and frequency-concentration assumptions those policies depend on. SOLAR addresses this with a learning-augmented framework combining regret-gated admission control and Bayesian Thompson-sampling eviction, achieving a provably constant competitive ratio \(\leq 3\) and 5–75% relative improvement over FIFO at tight cache sizes.

Problem

LLM agent memory systems store experience in retrieval buffers that are managed by cache replacement policies inherited from classical computer architecture (LRU, LFU, ARC). These policies assume: (1) binary hits via exact ID match, (2) temporal or frequency locality in access patterns, and (3) static item utility. None of these hold for semantic memory: hit quality is continuous (cosine similarity), items match by embedding proximity rather than identity, and relevance drifts as conversation topics shift. The result is that classical heuristics perform worse than FIFO—yet no principled alternative with theoretical guarantees existed.

Method

SOLAR (Semantic Online Learning-Augmented Replacement) formalizes the problem as an online semantic cache replacement problem with switching costs, minimizing:

\[\text{COST}(\pi, T) = \sum_{t=1}^{T} \ell_t(S_t^\pi) + \lambda \cdot N^\pi\]

where \(\ell_t \in [0,1]\) is 1 minus the token-level F1 of the response, and \(\lambda N^\pi\) penalizes cache modifications.

Admission (when to modify): A cumulative regret accumulator \(c\) tracks running miss cost \(\delta_t = 1 - \text{qual}_t\). A modification fires only when \(c \geq \tau\), where the threshold adapts via exponential moving average \(\tau_{t+1} = (1-\alpha)\tau_t + \alpha\delta_t\). This limits modifications to ~17% of steps.

Eviction (what to replace): Each cached item \(i\) maintains a Beta posterior \(\mu_i \sim \text{Beta}(\alpha_i, \beta_i)\), updated by: positive retrieval events (\(\alpha_i \mathrel{+}= 1\)) and temporal decay when not retrieved (\(\beta_i \mathrel{+}= 0.05\)). At eviction time, Thompson sampling draws \(\tilde{v}_i \sim \text{Beta}(\alpha_i, \beta_i)\), adds a novelty bonus \(b_i = \gamma/(1 + \text{age}(i)/\Delta_\text{nov})\), and evicts \(i^* = \arg\min_i (\tilde{v}_i + b_i)\). New items initialize at \(\text{Beta}(1,1)\) (uniform prior).

Key Contributions

  • Formal definition of the online semantic cache replacement problem with switching costs, bridging online algorithm theory to LLM memory management.
  • Empirical discovery and root-cause analysis of the systematic failure of LRU/LFU/ARC on semantic workloads across two real benchmarks and controlled synthetics.
  • Proof that SOLAR achieves competitive ratio \(\leq 3\) (universal constant, independent of \(K\) and \(T\)), versus \(\Omega(K)\) for FIFO.
  • Proof of eviction regret \(O(\sqrt{KT \log T})\), matching the information-theoretic lower bound \(\Omega(\sqrt{KT})\) up to logarithmic factors.
  • Demonstration that retrieval quality follows an inverted-U relationship with pool size, establishing that capacity constraints in semantic memory stem from retrieval noise (embedding confusion from near-duplicates), not storage limits.

Results

  • 5–75% relative F1 improvement over FIFO at tight cache sizes (\(K \in \{10, 20, 50\}\)) on LoCoMo and DialSim from MemoryBench-Full.
  • Combined SOLAR exceeds sum of individual components: +0.014 F1 over FIFO at \(K=50\), vs. +0.003 (eviction alone) + +0.007 (admission alone) = +0.010 (superadditive).
  • A-MAC (LLM-call-based admission, 2644 ms/decision) achieves F1=0.583 on LoCoMo admission; SOLAR matches or exceeds with no LLM calls and ~17% modification rate.
  • Synthetic cycling workload: FIFO drops to exactly 0% hit rate; SOLAR maintains near-optimal performance.
  • Pool-size experiment (5000 items): retrieval quality peaks at ~1000 items, then degrades as pool grows.
  • Phase transition observed at the working-set boundary: SOLAR wins decisively when \(K <\) effective working-set size, converges to FIFO above it.

Limitations

  • Evaluated on only two real-world datasets (LoCoMo, DialSim); broader coverage across more agent task types is undemonstrated.
  • The competitive ratio \(\leq 3\) assumes the offline optimal also incurs switching costs; behavior relative to an unconstrained oracle is not characterized.
  • Temporal decay rate (\(\beta_i \mathrel{+}= 0.05\)) and novelty bonus parameters (\(\gamma\), \(\Delta_\text{nov}\)) require tuning; sensitivity analysis is limited.
  • The paper is truncated before the full complexity analysis and experimental section; some reported numbers (e.g., DialSim breakdown per \(K\)) may be incomplete.
  • Assumes implicit retrieval feedback (top-\(k\) membership) as the only signal; agents where retrieval rank is not observable cannot directly apply the posterior update.

Relevance to Agentic AI / LLM Agents

This paper directly targets a core infrastructure component of long-running LLM agents: the experience retrieval buffer that functions as external long-term memory. It demonstrates that blindly inheriting classical systems-software heuristics into agent architectures introduces systematic performance regressions, and provides both the theoretical framework and a practical algorithm to address it. The work is directly applicable to any agent system using embedding-based retrieval (RAG-style memory, tool-use logs, skill libraries), and the finding that retrieval noise—not storage—limits useful cache size challenges common architectural assumptions about "bigger memory is better." The learning-from-implicit-feedback paradigm (no LLM calls, no training) also sets a practical efficiency baseline for future agent memory research.