What should an AI agent forget? Recency isn't enough — and neither is a self-tuning cache

An agent's memory is finite. When it fills up, something has to go, and the eviction rule — what to forget — quietly decides whether the agent keeps the memory it will actually need. We measured the classic rules and a two-tier store on three workloads. Two of the three things we could have led with turn out to be textbook — but the last one is worth your time. Minimal, fully-reproducible simulation (runnable probe).

Three rules, three regimes

Hold a fixed-capacity store; drive it with three access patterns and measure the served hit-rate (the fraction of future access-weight — each access scaled by its importance — that lands on a still-kept memory):

• temporal locality — a drifting working set (recent things are needed soon).
• rare-but-critical — a few items accessed seldom but each worth a lot.
• poison flood — a real working set buried under a stream of unique junk.

Every access-pattern rule owns at most locality and dies on the rest. Recency (LRU) tracks a drifting working set but is wiped to zero by a flood — the junk is always "most recent". Crucially, ARC — the state-of-the-art self-tuning cache (Megiddo & Modha 2003; it adapts the recency/frequency balance online and ships in ZFS and IBM storage) — scores about 0.12 / 0.00 on rare-critical and the flood, no better than plain LRU. It can't help: it infers importance from reuse, and a rarely-read-but-critical item (or a working set buried under a flood wider than the cache) never produces the reuse signal ARC needs. Only value survives those two regimes — and value needs a signal the access pattern doesn't contain. That no single online rule wins everywhere is itself textbook: Sleator & Tarjan (1985) proved every online rule is at best k-competitive; Belady (1966) showed the true optimum needs the future.

A blend, or a tier — both are old ideas

There are two classic ways to combine value with recency, and both predate agent memory by decades. The first is a single blended score — value discounted by a recency-decay clock, the GreedyDual-Size / GDSF family of cost-aware caching (Cao & Irani 1997; Cherkasova 1998). It does not rescue the flood: every junk eviction pumps the aging clock, so the very decay that handles a drifting working set ages the real memories out under attack. Aging-for-drift and no-aging-for-robustness are in direct tension inside one number.

The second way is a two-tier store — and it's segmented caching

Split the budget: a small value-protected tier (top items by value, immune to recency and to the flood) plus a recency-aged tier for everything else. This is the well-worn segmented-cache pattern — SLRU (Karedla 1994), 2Q (Johnson & Shasha 1994), LRU-K (O'Neil 1993) and ARC (2003) — with one change: admission to the protected tier is by an exogenous value, not by observed reuse. At a protected fraction of 30% it matches the best single rule across all three regimes at once:

The protected tier keeps the rare-critical and flood-targeted memories; the recency-aged tier serves the drifting working set. Two honest caveats. This is not free universality: at a 15% protected fraction it fails rare-critical (0.44) and the flood (0.42), so the protected fraction is a tuning knob, not a constant — and on rare-critical the tier is 0.64 vs value's 0.65, a small regression within noise. And ARC already self-tunes exactly this recency/frequency split that we fix by hand, so the tier's only real advantage over ARC is the value signal, not the two-tier structure. The regime-dependence dissolves — but into an old idea and a tuned knob.

It's the value signal, not the tier

Strip it down: value-admission — single or tiered — beats every access-pattern policy here for one reason. It can see a memory's importance directly, decoupled from how often the memory is touched. Does that require knowing the future? No. Re-run with a strictly write-time estimator — the running maximum importance observed each time a memory is used, zero before it is ever seen — and the numbers barely move (0.81 / 0.64 / 0.57). An agent realistically has that signal (a criticality tag, a high-stakes-use flag); a cache policy, by construction, does not. It degrades gracefully, too: with a badly noisy importance estimate the value tier still beats ARC by more than 2×. The lever is having an importance signal at all, not calibrating it perfectly.

If you build agent memory

Value-aware eviction isn't new — it's cost-aware caching (GreedyDual-Size, 1997). The agent-specific lesson from the ARC baseline is sharper: don't assume a "smart" self-tuning cache protects your rare-but-critical memories — it can't see importance the access pattern doesn't reveal. Admit on an observed importance signal. If you tier, treat the protected fraction as a knob, and know a single value-weighted score may match it; the case for an explicit bounded protected tier is strongest under adversarial value (a poisoned importance signal), where bounded capacity caps the damage. And note most production systems (Mem0, Letta, Zep) decay or consolidate rather than hard-evict — Mem0 already recommends "LRU with a salience floor," which is this idea. (This is the change we shipped into our open memory core.)

The falsifierEach access-pattern rule had to win at most locality and lose the rest — it did, ARC included (0.80 on locality; 0.12 / 0.00 on rare-critical and the flood). Value-admission had to recover the regimes they lose — it did (0.64 / 0.57), with a write-time-observable signal, not an oracle. And the tuned two-tier had to match the best single rule across all three — it did at a 30% protected fraction (with a small rare-critical regression, 0.64 vs 0.65), but not at 15%, so the win is a tuned knob, not free.

FAQ

What is the best memory-eviction policy for an AI agent? No single online rule is universal - that is a theorem (Sleator-Tarjan 1985), not a finding. Access-pattern rules (LRU, LFU, and even the self-tuning ARC cache) each handle a drifting working set but score about 0.12 on rare-but-critical items and 0.00 under a poison flood, because they infer importance from reuse. Admitting on an exogenous value signal recovers those regimes (0.64/0.57). A value-protected + recency-aged two-tier store (the segmented-cache pattern, SLRU/ARC) matches the best single rule across all three - but only at a tuned protected fraction of about 30%.

Why does recency (LRU) collapse under a memory poison flood? Because injected junk is always the most recent thing, so a pure recency rule keeps the flood and evicts the real memories - it drops to 0.00 exactly when it is attacked. A self-tuning cache like ARC also collapses here when the flood is wider than the cache, because the working set never generates the reuse signal ARC needs.

Does a smarter, self-tuning cache like ARC solve it? No. ARC (Megiddo-Modha 2003) adaptively balances recency and frequency and is excellent on access-pattern workloads, but it has no exogenous value signal - so on our probe it scores the same ~0.12 on rare-critical and 0.00 under the flood as plain LRU. The missing ingredient is importance, not adaptivity.

Why not just keep the highest-value memories? Value-only eviction protects rare-critical and flood-targeted items (0.65 / 0.57) but starves a drifting working set (0.22 on locality) by clinging to stale high-value memories. Pairing it with a recency-aged tier covers both - that is the two-tier store, which is textbook segmented caching (SLRU/2Q/ARC) with admission by exogenous value rather than by observed reuse.

What does a two-tier memory store mean in practice? Split the store: a value-protected tier that recency pressure cannot evict, plus a recency-aged tier for the working set. The protected tier survives floods; the aged tier tracks drift. This is segmented caching (SLRU, ARC); the only change for agent memory is that admission is by an observed importance signal rather than by reuse.

Related research

• The same hidden law in four AI-memory mechanisms
• Can corroboration stop AI-agent memory poisoning?
• Does long context kill RAG? We measured it