💻 computer science

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

This paper introduces SOLAR, a learning-augmented framework that outperforms classic cache heuristics and achieves a constant competitive ratio for semantic retrieval buffers by addressing their unique lack of temporal locality and continuous hit quality through regret-based timing and Bayesian content selection.

Original authors: Yushi Sun, Bowen Cao, Wai Lam

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yushi Sun, Bowen Cao, Wai Lam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The Overwhelmed Librarian

Imagine an AI assistant (like a smart personal assistant) that has a "memory bank." Every time you talk to it, it saves a note about what you said. To answer your next question, it looks through these notes to find the most helpful ones.

However, this memory bank has a size limit. It can't hold everything forever. So, when the bank gets full, the AI has to decide: "Which note should I throw away to make room for the new one?"

For years, engineers used the same old rules (like "throw away the oldest note" or "throw away the one nobody has looked at recently") to manage this memory. The authors of this paper discovered something surprising: These old rules are actually making the AI dumber.

The Problem: Why the Old Rules Fail

The paper argues that the old rules were designed for computer hard drives, not for human conversations. Here is why they fail in the AI world:

The "Recency" Trap (LRU): The old rule says, "If I haven't looked at this note in a while, it's useless."
- The Reality: In a conversation, you might talk about "cats" for a while, then switch to "cars" for an hour, and then suddenly ask about "cats" again. The old rule would have thrown away the cat notes because they were "old," leaving the AI confused when you asked about them again.
The "Popularity" Trap (LFU): The old rule says, "If a note has been looked at a lot, keep it forever."
- The Reality: In a long conversation, early topics get looked at a lot simply because they've been around longer. The AI ends up hoarding old, irrelevant facts about your morning coffee while forgetting the important details of your current project.

The Result: When the researchers tested these old rules, the AI performed worse than if they had just used the simplest possible rule: "Throw away the oldest note, no matter what." (This is called FIFO).

The Solution: SOLAR (The Smart Librarian)

The authors created a new system called SOLAR. Instead of blindly following rules, SOLAR acts like a smart librarian who learns from experience. It makes two key decisions:

1. When to Swap (The "Regret" Gate)

Most systems swap notes constantly, even when the current notes are fine. This is wasteful.

SOLAR's Approach: It waits. It keeps a mental tally of how "bad" the current answers are. If the AI starts giving bad answers because it's missing information, the "regret" score goes up. Only when the regret gets high enough does SOLAR decide, "Okay, we need to change something."
The Analogy: Imagine you are driving a car. You don't change the radio station every 10 seconds. You only change it when the current song is so bad that you start regretting listening to it. SOLAR waits for that moment of regret before acting.

2. What to Swap (The "Gambler's" Choice)

Once SOLAR decides to swap, it has to pick which note to throw out.

SOLAR's Approach: It doesn't just guess. It treats every note like a slot machine. It keeps a "confidence score" for each note based on how often it helped.
- If a note hasn't been used in a while, its confidence score slowly drops (it "forgets" old things).
- If a note is new, it gets a "bonus" so it doesn't get thrown out before it has a chance to prove itself.
- SOLAR uses a mathematical trick (Bayesian learning) to pick the note that is most likely to be useless, while keeping the ones that might still be valuable.

The Surprising Discoveries

The paper ran many experiments and found three major things:

Old Rules are Broken: On real conversation data, the classic "smart" rules (LRU, LFU) were consistently worse than the "dumb" rule (FIFO).
SOLAR Wins Big: When the memory bank is small (which is common in real apps), SOLAR improved the AI's answers by 5% to 75% compared to the old methods.
More Memory Isn't Always Better: This is the most counter-intuitive finding. The researchers found that if you let the memory bank get too huge (thousands of notes), the AI actually gets worse.
- The Analogy: Imagine trying to find a specific needle in a haystack. If the haystack is small, it's easy. If the haystack is the size of a mountain, you can't find the needle because there are too many "fake needles" (similar but irrelevant notes) confusing you.
- Conclusion: The limit on memory isn't about running out of storage space; it's about avoiding "noise" that confuses the AI.

The Bottom Line

The paper proves that managing an AI's memory is different from managing a computer's hard drive. You can't just use old rules.

SOLAR is a new system that:

Waits until it's really necessary to make a change.
Uses math to guess which memories are truly useless.
Keeps the memory bank small and clean to avoid confusion.

The result is an AI that remembers the right things at the right time, without needing expensive extra computing power or complex training. It's a smarter way to help an AI remember what matters.

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

1. Problem Formulation

The paper addresses the management of retrieval buffers (long-term memory) in Large Language Model (LLM) agents. Unlike traditional database buffer pools or web caches, these buffers store "experience items" (e.g., conversation turns, tool results) that are retrieved via embedding similarity rather than exact ID matching.

The authors formalize this as an online semantic cache replacement problem with switching costs, characterized by three fundamental departures from classical caching theory:

Soft Hits (Continuous Utility): Retrieval quality is continuous ( $[0, 1]$ ) based on semantic similarity, not binary. A "miss" implies poor retrieval quality, not necessarily the absence of an item.
Semantic Matching: Items are matched by embedding similarity. A cached item can partially serve queries from related topics, meaning exact recency or frequency does not guarantee future utility.
Non-Stationary Utility: Item value drifts as conversation topics evolve. An item relevant at turn 50 may be irrelevant at turn 200.

The objective is to minimize the total cost, defined as the sum of cumulative miss cost (retrieval quality loss) and switching cost (penalties for modifying the cache state, such as re-indexing).

2. Key Finding: The Failure of Classic Heuristics

Through comprehensive experiments on two datasets from MemoryBench-Full (LoCoMo and DialSim) using 8 replacement policies, the authors reveal a counter-intuitive phenomenon: classic heuristics (LRU, LFU, ARC) consistently underperform the naive FIFO baseline on semantic workloads.

LRU Failure: Recency of retrieval is not predictive of future utility in diverse conversations; "dormant but valuable" items are evicted prematurely.
LFU Failure: Frequency accumulation favors items from early, potentially obsolete topics, turning the cache into a "museum of obsolete-but-popular items."
Theoretical Proof: The authors prove that FIFO has an unbounded competitive ratio ( $\Omega(K)$ ) in this setting. In a cyclic workload where the working set size exceeds cache capacity, FIFO achieves exactly 0% hit rate, whereas classic LRU achieves a ratio of $K$ in traditional paging but fails similarly here due to the lack of temporal locality.

3. Methodology: The SOLAR Framework

The authors propose SOLAR (Semantic Online Learning-Augmented Replacement), a framework that decouples cache management into two coupled decisions: When to modify and What to put in.

A. Regret-Gated Modification Timing (Admission Control)

Instead of always admitting new items (as classic policies do), SOLAR gates admission based on accumulated regret.

Mechanism: A new item enters the cache only when the cumulative cost of not having it (miss cost) exceeds an adaptive threshold $\tau$ .
Adaptation: The threshold $\tau$ tracks workload difficulty via an exponential moving average (EMA) of the miss cost.
Effect: This reduces the modification rate to approximately 17%, ensuring the cache is only modified when demonstrably inadequate, thereby preserving the "switching budget" for high-value updates.

B. Bayesian Online Content Selection (Eviction)

When admission is triggered and the cache is full, SOLAR must select an item to evict under uncertainty.

Mechanism: It maintains a Beta posterior distribution ( $\alpha_i, \beta_i$ ) for the utility of each cached item, updated via implicit retrieval feedback (whether the item was retrieved in the top- $k$ ).
Eviction Strategy: The system uses Thompson Sampling to select the item with the lowest sampled utility.
Non-Stationarity Handling: A temporal decay mechanism increases the $\beta$ parameter for items not retrieved over time, allowing the posterior to drift toward low utility, preventing "permanent" retention of obsolete items.
Novelty Bonus: A bonus term prevents the premature eviction of recently admitted items before sufficient observation.

C. Synergy

The two components interact synergistically. Selective admission ensures the cache contains high-value items, providing cleaner feedback signals for the Bayesian posteriors. In turn, better eviction decisions preserve high-quality items, reinforcing the value of selective admission. Empirically, the combined effect exceeds the sum of individual components by ~40%.

4. Theoretical Guarantees

The paper provides rigorous theoretical bounds for SOLAR:

Competitive Ratio: SOLAR achieves a constant competitive ratio $\le 3$ against an offline optimal policy, independent of cache size ( $K$ ), time horizon ( $T$ ), and switching cost ( $\lambda$ ). This contrasts sharply with FIFO's unbounded ratio.
Regret Bounds: The eviction regret is bounded by $O(\sqrt{KT \log T})$ , matching the information-theoretic lower bound ( $\Omega(\sqrt{KT})$ ) up to logarithmic factors.
Convergence: Under piecewise-stationary workloads, the competitive ratio converges to 1 as $T \to \infty$ .

5. Experimental Results

Experiments were conducted on two real-world benchmarks (LoCoMo, DialSim) and three synthetic workloads.

Performance Gains: SOLAR achieves 5–75% relative improvement over FIFO at tight cache sizes ( $K \le 50$ ). The improvement is most pronounced in low-signal environments (DialSim, ~4% hit rate), where selective admission maintains a higher signal-to-noise ratio.
Learning Dynamics: SOLAR's performance improves continuously over time, with a learning slope (F1 improvement per step) 1.4–3.1× faster than FIFO.
Ablation: The admission control component contributes more to performance gains than the eviction component alone, highlighting the importance of filtering noise at the entry point.
Phase Transition: A clear boundary exists at the working set size. Below this size, selectivity (SOLAR) dominates; above it, raw coverage (FIFO) becomes sufficient.
Retrieval Noise: Synthetic experiments with pools up to 5,000 items reveal an inverted-U relationship between pool size and retrieval quality. Performance peaks around 1,000 items and degrades thereafter due to embedding-space confusion (near-duplicates). This justifies capacity constraints as an informational necessity (retrieval noise) rather than a physical storage limitation.

6. Significance and Claims

The paper claims to be the first to:

Formalize LLM agent memory as an online semantic cache replacement problem with switching costs, bridging online algorithm theory and LLM management.
Demonstrate the systematic failure of decades-old cache heuristics (LRU, LFU, ARC) on semantic workloads due to the absence of temporal locality and frequency concentration.
Propose a learning-augmented framework (SOLAR) with provable competitive ratio and regret bounds that requires no external predictors, offline training, or LLM calls for decision-making.
Establish that capacity constraints in semantic memory are driven by retrieval noise (embedding confusion) rather than storage limits, providing a theoretical basis for admission control even in systems with unlimited storage.

The authors emphasize that SOLAR adds <1ms of overhead per step (negligible compared to LLM inference latency) and achieves these gains without the computational cost of LLM-based admission decisions used in other recent works.