PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yushi Sun, Bowen Cao, Wai Lam

arXiv:2607.00394v1cs.DBcs.CL

TL;DR

LLM retrieval buffers lack cache policies tailored to semantic matching and continuous hit quality. The paper formalizes online semantic cache replacement and introduces SOLAR, which outperforms FIFO by 5–75% at tight cache sizes while classic heuristics underperform FIFO.

  • Problem

    Existing cache policies are not designed for semantic retrieval, where matches are similarity-based, hit quality is continuous, and item value can drift.

  • Method

    The paper formulates semantic memory management as online cache replacement in embedding space and uses SOLAR for regret-driven modification timing and Bayesian content selection.

  • Results

    Across two datasets and four cache sizes, classic heuristics underperform FIFO, while SOLAR achieves 5–75% relative improvement over FIFO when K≤50.

  • Takeaways & Limitations

    Semantic cache capacity is constrained by retrieval noise rather than storage, with retrieval quality peaking at a finite pool size before declining.

  • Takeaways & Limitations

    The regret analysis treats the slowly drifting bandit instance as approximately stationary within aging windows rather than fully modeling non-stationarity.

Abstract

from arXiv · show

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.\ $Ω(K)$ for FIFO), and eviction regret $O(\sqrt{KT\log T})$, matching the $Ω(\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.

1 INTRODUCTION

LLM agents increasingly use retrieval buffers as long-term memory, but classical cache heuristics rely on assumptions that semantic workloads violate. The paper formulates online semantic cache replacement with switching costs and proposes SOLAR to control both cache modification timing and content selection.

  • Motivation: Retrieval buffers store past experience and are queried at each interaction step to supplement the language model’s fixed context window.They support long-running tasks including conversation, gameplay, and iterative research.
  • Current practice and a surprising finding: 8 cache replacement policies are evaluated across 4 capacity settings on LoCoMo and DialSim from MemoryBench-Full.The experiments stress-test widespread reliance on FIFO, LRU, and recency-based policies in agent memory systems.
  • What’s really different about semantic memory?: Semantic memory violates classical cache assumptions because retrieval quality is continuous, matching is embedding-based, and item utility changes as conversation topics evolve.A miss denotes poor retrieval quality rather than complete item absence, and related items can partially serve a query.
  • Problem formalization: The online semantic cache replacement problem combines soft-hit retrieval quality, semantic matching, non-stationary utility, cumulative miss cost, and switching cost.This formulation enables competitive analysis against an offline optimal policy.
  • Our approach: SOLAR: SOLAR reduces admission to roughly 17% by admitting new items only when accumulated regret exceeds an adaptive threshold.The threshold tracks workload difficulty through an exponential moving average, limiting cache changes caused by noise items.
  • Our approach: SOLAR: SOLAR uses Beta posteriors and Thompson sampling to evict believed low-utility items while preserving under-observed items for further learning.The combined admission and eviction components interact synergistically, and the paper empirically verifies a super-additive interaction.

• Competitive ratio

SOLAR achieves a universal competitive ratio of at most 3, independent of cache size, horizon, and switching cost, and converges to 1 under piecewise-stationary workloads. Its eviction regret matches the information-theoretic lower bound up to logarithmic factors, while FIFO can have an unbounded competitive ratio.

  • Competitive ratio: ≤3 is SOLAR’s worst-case competitive ratio against offline optimal, independent of cache size K, horizon T, and switching cost λ.The ratio converges to 1 under piecewise-stationary workloads.
  • Competitive ratio: 0% hit rate is achieved by FIFO on a constructed cycling workload, while OPT achieves near-perfect performance.This establishes FIFO’s competitive ratio as unbounded.
  • Competitive ratio: O(sqrt(KTlogT)) eviction regret matches the Ω(sqrt(KT)) information-theoretic lower bound up to logarithmic factors.Here K is cache size and T is the time horizon.

• Eviction regret 𝑂(

The paper formalizes LLM experience memory as an online semantic cache replacement problem and introduces a learning-augmented admission-eviction framework with provable guarantees. Experiments span real and synthetic workloads to explain classic-policy failures and characterize cache behavior.

  • Synthetic validation: 0% hit rate occurs for FIFO on a cycling workload with working set size > K, empirically witnessing the structural failure behind the Ω(K) competitive-ratio theorem.The controlled workload isolates why classic policies fail rather than attributing failure to a particular dataset.
  • Problem formulation: The work formalizes LLM agent experience memory as an online semantic cache replacement problem.This connects online-algorithm theory with LLM memory management.
  • Why classic policies fail: Classic cache heuristics systematically fail on semantic workloads because temporal locality and frequency concentration are absent.The paper analyzes this root cause in §6.
  • Learning-augmented framework: The proposed learning-augmented admission-eviction framework provides provable competitive-ratio and regret bounds without external predictors or model training.The guarantees are established in §§4–5.
  • Experimental scope: 2 real benchmarks, 3 synthetic workloads, 8 methods, and 4 capacity settings support the evaluation and yield phase-transition and retrieval-noise insights.The experiments are designed to provide actionable cache-management conclusions.

2 PROBLEM FORMULATION

The paper formulates LLM-agent memory management as online semantic cache replacement with embedding-based retrieval, continuous miss quality, and switching costs. The model separates admission from eviction and evaluates policies through regret, competitive analysis, and downstream token-level F1.

  • 2.1 System Model: The semantic cache stores at most K experience items in an embedding space and retrieves the top-k items ranked by cosine similarity for each query.Its state is C = (S_t, K, ϕ, k), and policy decisions evolve the cached item set over time.
  • 2.2 Miss Cost Function: Continuous miss cost ℓ_t(S_t) ∈ [0, 1] measures response-quality degradation, using token-level F1 against a ground-truth answer.Unlike binary hits, partial matches yield intermediate cost; cost also depends jointly on retrieved items and the query.
  • 2.3 Total Cost Objective: The objective combines miss cost with λ per cache replacement, balancing quality improvements against modification overhead.Switching cost also regularizes unstable policies by allowing newly admitted items time to be observed.
  • 2.4 Fundamental Differences from Traditional Caching: Semantic caching requires new approaches because larger pools can degrade retrieval quality even with unlimited storage, as similar items from different topics confuse the retriever.The paper identifies an empirically demonstrated inverted-U relationship between pool size and retrieval quality.
  • 2.5 Performance Metrics: Policy evaluation uses regret and competitive analysis alongside downstream token-level F1 on held-out queries to measure end-to-end user-facing quality.Sublinear regret R_T = o(T) indicates convergence toward the optimal eviction strategy, whereas linear regret R_T = Θ(T) indicates no improvement.
  • 2.6 The Admission-Eviction Decomposition: The formulation decomposes cache management into admission control, which governs selectivity and switching cost, and eviction, which determines future miss costs.FIFO, LRU, LFU, and ARC always admit after initial filling, while the proposed approach makes admission explicit to reduce switching and preserve retrieval precision.

3 RELATED WORK

Prior cache-replacement and semantic-memory systems largely assume temporal locality or use ad-hoc policies, while learning-augmented caching and semantic retrieval address only parts of this setting. This work positions itself through online implicit feedback, continuous soft hits, joint admission–eviction design, and provable guarantees without external oracles or LLM training.

  • Cache replacement: Classical policies such as LRU, ARC, 2Q, TinyLFU, LRU-K, and LIRS refine recency or frequency signals but assume temporal locality.These approaches include adaptive recency–frequency balancing, queue-based admission filtering, frequency-gated admission, and inter-reference-distance signals.
  • Learning-augmented caching: Learning-augmented caching improves guarantees using external ML predictions, ranging from O(1) with perfect predictions to O(logK) under adversarial predictions.Related work includes robustification with 1-consistency and applications to CDN caching through relaxed Bélády and imitation learning.
  • Positioning: The paper differs by combining formal cache replacement with switching costs, constant competitive and regret guarantees, online implicit feedback, continuous soft hits, and joint admission–eviction design.It claims no external oracle, no LLM calls or training, and end-to-end task evaluation; related agent-memory systems instead use ad-hoc replacement policies.
  • Semantic retrieval and agent memory: Semantic caching, GPTCache, and RAG retrieve by similarity, but this work addresses a dynamic retrieval pool that evolves through agent interactions and creates admission–eviction challenges.Prior RAG systems generally retrieve from static corpora, whereas the present setting requires managing an evolving pool.

4 THE SOLAR FRAMEWORK

SOLAR jointly learns when to modify a semantic cache and which item to replace, deriving both mechanisms from a switching-cost objective. Regret-gated timing and Bayesian content selection interact through shared retrieval feedback, adapting modification frequency and item utility estimates to changing workloads.

  • Joint objective: SOLAR decomposes cache management into cumulative miss cost and switching cost, coupling the decisions of when to modify and how to modify.The framework is jointly derived because modification timing determines the context for replacement, while effective eviction maintains cache quality and reduces future triggers.
  • Modification timing: ∼17% of steps: adaptive regret accumulation self-regulates modification frequency, triggering more often under high retrieval loss and bounding modifications by N ≤ T/τ.The threshold adapts to unknown, non-stationary loss rates; low per-step loss slows accumulation, while stale caches accelerate it.
  • Content selection: Bayesian posterior sampling selects evictions under latent, non-stationary, partially observable utility, balancing exploitation of low-utility items with exploration of uncertain ones.The method uses implicit retrieval feedback rather than directly observing future usefulness or counterfactual contribution.
  • Content selection: α_i ← α_i + 1 and β_i ← β_i + 0.05: positive retrieval evidence and temporal decay update each item’s posterior to support adaptation as conversation topics change.Temporal decay prevents previously useful items from retaining permanent positive evidence, while the novelty bonus protects recently admitted items before sufficient observation.
  • Architectural coupling: +0.014 vs. +0.003 + +0.007 = +0.010, a 40% bonus: empirical synergy arises because timing and selection share retrieval feedback and reinforce one another.The posterior updates also drive the cost accumulator, while threshold adaptation responds to the cache quality maintained by eviction.

5 THEORETICAL ANALYSIS

Theoretical results separate SOLAR from FIFO through worst-case competitive-ratio and stochastic-regret guarantees. Under bounded stale advantage, SOLAR achieves constant competitive ratio and sublinear eviction regret, while FIFO has Ω(K) competitive ratio and Ω(T) regret.

  • Modification timing: N_SOLAR ≤ ⌊T/τ_min⌋ because each admission requires at least τ_min steps to reaccumulate the active cost threshold.With a fixed threshold τ, the bound becomes ⌊T/τ⌋; EMA adaptation keeps the threshold bounded away from zero after a transient.
  • SOLAR competitive ratio: CR(SOLAR) ≤ 3 under bounded stale advantage with threshold τ = 2λ, independent of K, T, and λ.The threshold τ = 2λ minimizes the worst-case ratio and contrasts with FIFO’s Ω(K) ratio.
  • Regret bounds: FIFO regret is Ω(T) on cycling workloads with m > K, because its per-step loss never improves with interaction length.On the m = K + 1 workload, FIFO has zero hit rate after fill, whereas a fixed-eviction comparator retains the first K topics.
  • Regret bounds: SOLAR’s posterior-guided selection has eviction regret O(√(KT log T)), which is o(T), while the lower bound is Ω(√(KT)).The guarantee characterizes the stationary regime because admissions make the arm set drift and retrieval feedback is indirect.
  • Combined guarantees: SOLAR combines bounded competitive ratio from modification timing with sublinear regret from posterior-guided selection; no other listed method achieves both guarantees.FIFO has Ω(K) competitive ratio and Ω(T) regret, while SOLAR-E has sublinear regret but Ω(K) competitive ratio.

6 EXPERIMENTS … 6.3 Ablation: Admission vs. Eviction (RQ3)

Across MemoryBench-Full benchmarks, SOLAR is evaluated against eight cache policies and outperforms FIFO most clearly under tight capacity. At K=50, admission contributes more than eviction, while combining both yields super-additive gains.

  • 6 EXPERIMENTS: The evaluation uses two MemoryBench-Full datasets, controlled synthetic workloads, and four research questions covering heuristic failure, SOLAR’s gains, component contributions, and phase transitions.The experiments use simulated implicit like/dislike feedback and compare cache behavior across multiple capacity regimes.
  • 6.1 Experimental Setup: LoCoMo contains approximately 2000 interaction steps and ∼39 scored QA pairs per session, while DialSim contains ∼19K messages per corpus and ∼60 test queries per show.Embedder-unlimited achieves ∼35% F1 on LoCoMo versus ∼11% F1 on DialSim, making DialSim the sparser stress test.
  • 6.1 Experimental Setup: Eight policies span unlimited embedding retrieval, FIFO, classic heuristics, and learning-augmented variants SOLAR-E, SOLAR-A, and SOLAR.Cache sizes are K∈{10, 20, 50, 100}; retrieval uses top-3 cosine similarity and token-level F1.
  • 6.2 Main Results: LoCoMo: At K∈{20, 50}, LRU, LFU, and ARC all fall below FIFO, while LFU trails FIFO at every K.LRU assumes temporal locality, LFU assumes frequency concentration, and ARC oscillates when both signals mislead.
  • 6.2 Main Results: LoCoMo: +22.7% relative improvement over FIFO occurs at K=10, compared with +4.7% at K=50.SOLAR ranks first in every K≤50 setting, while K=100 is an exception where coverage favors the phase transition.
  • 6.2 Main Results: LoCoMo: 1.4–3.1× faster F1 improvement per step than FIFO is observed for SOLAR, with its advantage growing in the second half of evaluation.At K=10, the absolute gain is +0.053 and the relative gain is +22.7%; on DialSim, the improvement reaches +75%.
  • 6.3 Ablation: Admission vs. Eviction (RQ3): +0.007 improvement for SOLAR-A is more than double SOLAR-E’s +0.003 improvement at K=50.This indicates that selective admission contributes more than eviction by preventing noise from entering the cache.
  • 6.3 Ablation: Admission vs. Eviction (RQ3): +0.014 combined improvement exceeds the +0.010 sum of individual improvements by +0.004, a 40% bonus.The feedback loop links cleaner admission pools to better Thompson Sampling posteriors and improved eviction decisions.

6.4 Cross-Dataset Validation: DialSim … 6.8 Summary of Experimental Findings

Across DialSim and synthetic workloads, SOLAR’s advantage is strongest when cache capacity is tight, while FIFO becomes competitive near or above the effective working-set boundary. The experiments also show that semantic retrieval quality peaks at intermediate pool sizes, SOLAR learns faster than FIFO, and its arithmetic policy adds no perceptible latency.

  • 6.4 Cross-Dataset Validation: DialSim: At K=10, SOLAR improves over FIFO by +75% on DialSim versus +23% on LoCoMo, with SOLAR or SOLAR-A best at every K≤50.LRU, LFU, and ARC fall below FIFO at K=50; FIFO overtakes at K=100.
  • 6.5 Controlled Evaluation: Synthetic Workloads: In cycling workloads with K=10, FIFO collapses to exactly 0% hit rate once m>K, whereas LRU reaches only 0.38 at m/K=1 versus FIFO’s 0.90.Selective admission lets SOLAR-A avoid the cyclic thrashing caused by recency-based eviction.
  • 6.5 Controlled Evaluation: Synthetic Workloads: At K≈30, the synthetic working-set sweep crosses from SOLAR-A’s advantage below the boundary to FIFO’s coverage advantage above it.The gain peaks at K=15 (+0.10 absolute), while SOLAR-A stores approximately 10% of arrivals and caps the cache near 40 items.
  • 6.5 Controlled Evaluation: Synthetic Workloads: Hit rate peaks at K≈1000 and drops by 55% from K=1000 to K=5000 because similar but irrelevant items increase retrieval noise.The result frames capacity constraints as informational rather than physical, even with unlimited storage.
  • 6.6 Learning Dynamics: SOLAR’s learning slope is 1.8–3.1× FIFO’s across K=10, 20, and 50, with the largest slopes at K∈{20,50}.At K=50, the example slopes are 1.26 for SOLAR versus 0.40 for FIFO.
  • 6.7 Latency: <1 ms per step is added by SOLAR’s arithmetic policy, while GPT-4o-mini inference takes approximately 1200–1400 ms per call and total latency remains statistically indistinguishable across policies.A-MAC instead adds approximately 2644 ms per admission through an LLM call.
  • 6.8 Summary of Experimental Findings: 5–75% relative improvement over FIFO is achieved by SOLAR when K≤50, while classic heuristics systematically underperform FIFO across 4 cache sizes and 3 seeds.The summary also reports a 1.4–3.1× learning-slope improvement and a 40% super-additive synergy from timing and content-selection feedback.
  • 6.8 Summary of Experimental Findings: Below the working-set boundary, selectivity dominates; above it, coverage dominates, establishing a phase transition relevant to deployment decisions.This conclusion is consistent across the synthetic sweep and the LoCoMo and DialSim benchmarks, whose transitions occur in K∈(50,100).

2 benchmarks,

Synthetic results show an inverted-U relationship in which pool growth degrades retrieval performance, supporting capacity constraints as a retrieval-noise effect. SOLAR adds less than 1 ms of policy computation per step without extra LLM calls.

  • Synthetic capacity analysis: Inverted-U retrieval quality shows that pool growth degrades performance, validating capacity constraints in the problem formulation.The result frames capacity constraints as a response to retrieval noise rather than storage limitation.
  • Efficiency: <1ms policy computation per step gives SOLAR zero latency overhead relative to LLM inference time.The policy computation is described as negligible compared with LLM inference.
  • Efficiency: No additional LLM calls are required by SOLAR.This is part of the reported zero-latency-overhead result.

7 DISCUSSION

Discussion attributes classic-policy failure to a mismatch with semantic workloads, where recency and frequency are not predictive. It identifies a working-set phase transition and frames capacity control as preserving retrieval signal quality rather than merely saving storage.

  • Policy assumptions: LRU, LFU, and ARC fail because semantic workloads lack the temporal locality and frequency concentration their assumptions require.Evolving user intent makes retrieval recency uninformative, while frequency can reflect cache age rather than intrinsic value.
  • Working-set phase transition: 5–23% relative gains on LoCoMo and up to 75% on the sparser DialSim occur below the working-set size, while FIFO wins above it.Below the boundary, selectivity dominates; above it, coverage dominates because FIFO never misses an opportunity to store.
  • Working-set phase transition: K* scales with effective working-set size, lying in (50, 100) on LoCoMo and ≈30 on synthetic.Designers should estimate their working set, for example using the FIFO saturation curve, and deploy selective policies only below K*.
  • Capacity constraints: ∼1000 items marks the point beyond which embedding-space crowding degrades precision faster than coverage gains.The inverted-U relationship makes capacity constraints informational: the 17% admission rate optimizes precision and signal-to-noise ratio rather than storage alone.

8 CONCLUSION

The paper formalizes LLM agent experience memory as an online semantic cache replacement problem, connecting online-algorithm theory with practical LLM memory management. It shows that classic heuristics fail on semantic workloads and introduces SOLAR, which learns modification timing and content selection without external predictors, offline training, or LLM calls.

  • Conclusion: The work formalizes LLM agent experience memory as an online semantic cache replacement problem.This bridges classical online-algorithm theory and practical LLM memory management.
  • Conclusion: Classic cache heuristics systematically fail on semantic workloads, underperforming FIFO across two datasets.
  • Conclusion: SOLAR derives modification timing from regret accumulation and content selection from Bayesian online learning without external predictors, offline training, or LLM calls.
Loading 2607.00394v1…