Priority Decay vs LRU Eviction for AI Memory

How LRU Eviction Works

LRU eviction is borrowed from cache management in operating systems and databases. Every memory records the timestamp of its most recent access. When the store reaches capacity, the memory with the oldest last-access timestamp is removed to make space for new entries. If multiple memories are tied, they are typically removed in creation order.

LRU's strength is simplicity. It requires a single timestamp per memory, no complex scoring calculations, and a straightforward eviction decision. It works well for caches where recent access is a strong predictor of future access, because items you used recently are statistically likely to be used again soon.

For AI memory, LRU has several problems. The most significant is that it treats all accesses equally. A foundational architectural decision that was established a year ago and has not been directly queried since then has a very old last-access timestamp, even though it is critical context for dozens of related memories. Under LRU, this memory would be evicted before a trivial observation made yesterday, simply because the observation was stored more recently.

LRU also ignores confidence and corroboration. A memory corroborated by five independent sources and a memory stored from a single ambiguous conversation have the same eviction priority if their last-access timestamps are similar. The well-corroborated memory is far more likely to be accurate and useful, but LRU cannot make that distinction.

How Priority Decay Works

Priority decay computes a composite score for each memory that incorporates multiple signals: how recently and how frequently the memory was accessed (base-level activation from ACT-R), how well-corroborated it is (confidence score), and how connected it is in the knowledge graph (entity centrality). Memories with the lowest composite scores are evicted first.

The key advantage is that priority decay makes nuanced decisions. A foundational memory with high confidence, many entity connections, and a moderate access history scores much higher than a recent, uncorroborated observation, even if the observation was accessed more recently. The system keeps the memory that is more likely to be useful for future queries, not just the one that was used most recently.

Priority decay also handles the frequency dimension that LRU ignores entirely. A memory accessed once per week for the past six months has very different value than a memory accessed once yesterday. Under LRU, the weekly-accessed memory might be evicted during a brief lull in access. Under priority decay, its accumulated activation from dozens of spaced accesses gives it a high score that protects it from eviction.

Side-by-Side Comparison

Consider a memory store at capacity with these five entries, where one must be evicted to make space:

Memory A: architectural decision, accessed 15 times over 6 months, last access 3 weeks ago, confidence 9.0, connected to 12 entities. Memory B: debugging note, accessed once, stored yesterday, confidence 5.0, connected to 2 entities. Memory C: API endpoint reference, accessed 8 times over 2 months, last access 1 week ago, confidence 7.0, connected to 5 entities. Memory D: casual preference mention, accessed once, stored 2 months ago, confidence 4.0, connected to 1 entity. Memory E: team process note, accessed 3 times over 1 month, last access 2 weeks ago, confidence 6.0, connected to 4 entities.

LRU evicts Memory A because it has the oldest last-access timestamp (3 weeks ago). This is the worst possible choice, because Memory A is the most established, most connected, and most valuable entry in the store. Memory D, the casual preference mention with low confidence and minimal connections, would be the best eviction candidate.

Priority decay evicts Memory D because it scores lowest on the composite of activation, confidence, and centrality. Single access, low confidence, minimal entity connections, and an aging access timestamp all contribute to the lowest score. This is the correct decision because Memory D contributes the least value to the store.

LFU as a Middle Ground

LFU (Least Frequently Used) eviction addresses one of LRU's weaknesses by tracking access count rather than just the most recent access. Under LFU, a memory accessed once is evicted before a memory accessed ten times, regardless of when the accesses occurred. This is an improvement over LRU for AI memory because frequency correlates with importance.

However, LFU has its own weakness: it has no recency bias. A memory accessed 20 times two years ago but never since then keeps its high count forever. It will not be evicted even if the information it contains is completely outdated. LFU also ignores confidence and graph connectivity, just like LRU.

ACT-R's base-level learning equation, which powers the activation component of priority decay, naturally combines recency and frequency by weighting each access by its age. Recent accesses contribute more to activation than old accesses, and more accesses contribute more than fewer accesses. This handles both the recency problem of LFU and the frequency problem of LRU in a single, mathematically principled model.

Implementation Complexity

LRU requires one timestamp per memory and a simple sort to find the eviction candidate. It can be implemented in a few lines of code with negligible computational overhead.

Priority decay requires access history (list of timestamps), confidence scores, entity connection counts, and a scoring function that combines these signals. The scoring function involves logarithmic and power-law calculations and a weighted combination. This is more complex to implement and requires more metadata per memory.

In practice, the additional complexity is modest. The priority score can be precomputed and updated incrementally whenever a memory is accessed, so the eviction decision itself is just a comparison of precomputed values. The storage overhead of maintaining access histories is small relative to the content and embedding storage of each memory. For any production AI memory system, the quality improvement from priority decay easily justifies the implementation cost.

When LRU Is Sufficient

LRU is appropriate for caches where the only goal is to keep frequently accessed items fast, and where all items are equally valid. A vector search cache that stores recent query results can use LRU effectively because every cached result was correct when it was stored and the only question is whether it is likely to be queried again.

For persistent AI memory where some entries are more important, more reliable, or more connected than others, LRU is not sufficient. The retention decision should account for the quality and structural importance of each memory, not just when it was last accessed. Priority decay, as implemented in Adaptive Recall through ACT-R cognitive scoring, provides this multi-dimensional assessment.

TTL-Based Eviction

A third strategy worth mentioning is TTL (Time To Live) based eviction, where every memory has a fixed expiration time set at creation. After the TTL expires, the memory is removed regardless of whether it has been accessed or how important it is. TTL is common in session stores and temporary caches, but it is a poor fit for AI memory because the lifespan of useful knowledge varies enormously. An architectural decision might be relevant for years while a debugging observation is relevant for hours. A fixed TTL cannot accommodate both without being either too aggressive (removing valuable long-term knowledge) or too lenient (retaining transient noise).

Priority decay handles this naturally because the decay rate is modulated by importance. High-importance memories decay slowly and persist for a long time. Low-importance memories decay quickly and are evicted soon. The effective TTL emerges from the interaction of the decay model and the importance score, producing different retention durations for different memories without requiring manual TTL configuration.