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.
Alex: Welcome to another episode of ResearchPod. Today, we're discussing a study on how artificial intelligence agents manage their long-term memory.
Sam: So this paper is basically asking why our current AI assistants are so bad at remembering things from past conversations?
Alex: Exactly. The core problem is that the systems used to decide what an AI "keeps in mind" rely on outdated rules that were never designed for how modern AI actually works.
Sam: And the argument is that these rules are actively making the memory worse?
Alex: Yes. To understand why, picture a librarian with a tiny desk. The desk only has room for, say, ten books at a time. The librarian has to constantly decide which books to keep out for quick reference and which to put back on the shelves. That desk is what computer scientists call a "cache"—a small, fast storage space for the things you're most likely to need right now.
Sam: Okay, so the librarian keeps swapping books in and out as the user asks for different things. What are they doing wrong?
Alex: They're using old-school rules like "First-In-First-Out"—just toss out the oldest book regardless of how useful it still is. Or "Least Recently Used"—if you haven't looked at a book in a while, it goes back on the shelf. These rules made sense for older computer systems, but the study shows they fail badly for AI memory.
Sam: Why? What's different about AI memory?
Alex: Here's the key distinction. Traditional computer memory works like a filing cabinet—you look up an exact file by its label. But AI memory works more like a library organised by ideas. If you ask about "dogs," the system doesn't just pull up files labelled "dogs." It pulls up anything related in meaning—pets, training, veterinary care. That kind of meaning-based storage is called a "semantic cache."
Sam: So if I talk about dogs, the AI should keep related books about pets nearby, even if I haven't mentioned those specific books yet.
Alex: Precisely. And that changes everything. Because the AI is constantly updating its understanding of the conversation, the value of what's on that desk keeps shifting. Old rules assume that if you haven't looked at a book recently, you probably won't need it again. But in a long conversation, a topic you discussed an hour ago might suddenly become relevant again.
Sam: So throwing something away just because it hasn't come up for a while is a real mistake in this context.
Alex: It is. And the authors found something worth paying attention to: these classic rules actually perform worse than just picking items to remove at random. When your smart system does worse than a coin flip, that's a sign the underlying assumptions are broken.
Sam: So what's the alternative?
Alex: The researchers propose a new system called SOLAR. It has two distinct jobs: deciding when to reorganise the desk, and deciding which book to swap out when it does.
Sam: How does it decide when to reorganise?
Alex: It uses something called "regret-gated admission." Think of it like a pain threshold. The system tracks what the researchers call the "miss cost"—essentially, how much the AI is struggling to answer well because it doesn't have the right information to hand. It only clears and resets the desk when that struggle reaches a certain level. Below that threshold, it leaves things alone.
Sam: So it's not constantly shuffling things around. It waits until there's a clear reason to act.
Alex: Exactly. That prevents a problem called "thrashing"—where a system wastes all its energy constantly swapping things in and out, never settling long enough to actually be useful.
Sam: And the second part? How does it choose which book to swap?
Alex: This is where it gets interesting. It uses a technique called "Thompson sampling." Rather than following a fixed rule, the system maintains a running estimate—a probabilistic hunch—about how valuable each item in the cache is likely to be. Every time an item helps the AI answer a question well, that hunch gets updated. Items that consistently prove useful get protected. Items that rarely help are more likely to be swapped out.
Sam: So it's learning from its own track record.
Alex: Exactly. And it balances that track record against the possibility that a newer, untested item might turn out to be even more valuable. It's a self-correcting loop that gets better as the conversation goes on.
Sam: There's something else I wanted to ask about. The paper mentions a point where adding more memory actually starts to hurt. How does that work?
Alex: Right—this is one of the more counterintuitive findings. You'd assume that a bigger desk is always better. But beyond a certain size, the cache becomes crowded with items that are similar to what you need but not quite right. When the AI searches for relevant information, all that near-miss content creates noise that makes it harder to find the actual signal. The researchers call this "retrieval noise," and it produces what they describe as a phase transition—a specific point where performance stops improving and starts declining.
Sam: So the lesson isn't just "build a bigger cache." It's "build a smarter one."
Alex: That's precisely the takeaway. The authors suggest that system designers should estimate the size of their "working set"—the realistic range of topics a conversation is likely to cover—and size the cache accordingly. Beyond that, selective policies like SOLAR matter far more than raw capacity.
Sam: It's a bit like the difference between alphabetising a bookshelf and organising a library by the ideas inside the books. Once the library gets big enough, the organisation system matters more than the building size.
Alex: That's a good way to put it. And it points to something broader: memory management for AI isn't a solved problem that we can hand off to rules designed for a different era. It requires systems that treat memory as a learning problem—one that adapts as the conversation evolves.
Sam: So SOLAR is less like a filing system and more like a thoughtful colleague who's paying attention to what's actually been useful.
Alex: That's the ambition. Whether it scales to the most complex real-world deployments is still an open question, but as a framework for thinking about semantic memory management, the evidence in this paper suggests it's a meaningful step forward. Thanks for listening to ResearchPod.