Least Recently Used (LRU)

LRU operates on a simple, temporal heuristic: the item that has not been accessed for the longest time is evicted first. This assumes that recently used data is more likely to be needed again in the near future, a principle known as temporal locality. When the cache reaches capacity, the algorithm identifies and removes the 'coldest' entry to make space for a new item.

• Example: In a chat agent's conversation history cache, the opening message of a long session would be evicted before the user's most recent query.

Efficient LRU requires data structures that support fast access, update, and ordering. The canonical implementation combines a hash map (or dictionary) for O(1) key lookups with a doubly linked list to maintain access order.

• Hash Map: Maps keys to nodes in the linked list.
• Doubly Linked List: The head represents the Most Recently Used (MRU) item. The tail represents the Least Recently Used (LRU) item, ready for eviction.
• On Access: A retrieved item is moved to the head of the list (an O(1) operation).
• On Insertion: A new item is added to the head. If at capacity, the tail node is evicted.

A properly implemented LRU cache aims for O(1) time complexity for both get (read) and put (insert/update) operations. This efficiency is critical for high-throughput systems like API gateways or vector database query caches.

• Advantage: Excellent performance under stable, locality-heavy workloads.
• Overhead: Requires maintaining two data structures, leading to higher memory overhead per entry compared to simpler policies like FIFO.
• Latency: The constant-time operations ensure predictable performance, which is essential for real-time agentic systems.

LRU performs poorly under scan or one-time access patterns. If a workload involves sequentially reading a large dataset that exceeds cache size, LRU will evict the entire existing 'working set' to accommodate the scan, causing a cache pollution effect.

• Example: An agent performing a full-table database scan for analytics will flush the cache of frequently accessed user profiles.
• Contrast with LFU: The Least Frequently Used (LFU) algorithm is more resilient to scans, as one-time scan entries have a low frequency count and are evicted quickly.

Several algorithms extend or modify classic LRU to address its limitations:

• LRU-K: Tracks the times of the last K references to an item, evicting based on the K-th-to-last access time. This better distinguishes between frequently and infrequently accessed items.
• 2Q (Two Queues): Uses two queues: an A1 queue (FIFO) for items seen once and an Am queue (LRU) for items seen multiple times. This effectively filters out one-time scans.
• Adaptive Replacement Cache (ARC): Dynamically balances between LRU and LFU by maintaining both recent and frequent entry lists, adapting to the workload.

In autonomous agents, LRU is a key policy for managing finite context windows and episodic memory buffers.

• Context Window Management: An LLM-powered agent with a limited token context can use LRU to retain the most recent user instructions and system outputs, eviding older interactions to stay within limits.
• Tool Call Result Cache: Results from expensive API calls (e.g., database queries, weather APIs) can be cached with an LRU policy, ensuring the most recently fetched data is readily available for subsequent reasoning steps.
• Session State: For multi-turn conversations, LRU can manage which pieces of historical state are kept in fast-access memory versus persisted to slower vector stores.

A cache eviction policy is a predetermined algorithm that determines which items to remove from a cache when it reaches its capacity limit. LRU is one specific policy among many, each with different trade-offs between hit rate, computational overhead, and access pattern assumptions. Other key policies include:

• First-In-First-Out (FIFO): Evicts the oldest item by insertion time.
• Random Replacement (RR): Selects a random item for eviction.
• Most Recently Used (MRU): Evicts the most recently accessed item, useful for certain scanning patterns. The choice of policy directly impacts system latency and throughput.

Least Frequently Used (LFU) is a cache eviction algorithm that removes the item with the lowest count of access requests. Unlike LRU, which cares about recency, LFU prioritizes frequency. It is effective for workloads with highly popular, stable items but can suffer from cache pollution where once-frequent but now stale items block new entries. Modern variants like Aging LFU incorporate time decay to mitigate this. In agentic systems, LFU might be used for long-term memory caches storing frequently referenced domain knowledge.

Adaptive Replacement Cache (ARC) is a self-tuning, patented eviction policy that dynamically balances between recency (LRU) and frequency (LFU). It maintains two adaptive lists: T1 for recent entries and T2 for frequent entries. By observing which list contributes more hits, ARC adjusts its size to optimize for the observed workload. This makes it highly effective for unknown or shifting access patterns, a common scenario in agentic workflows where an agent's focus may change between tasks. It provides superior hit rates compared to static policies but with higher memory overhead for metadata.

Time-To-Live (TTL) is a mechanism that sets an expiration timestamp on cached data, network packets, or session state. When the TTL expires, the item is considered stale and is evicted or must be refreshed. TTL is often used in conjunction with LRU to provide a two-layer eviction strategy: LRU manages capacity-based eviction, while TLL handles time-based staleness. This is critical in agentic memory for ensuring context relevance; for example, a cached API response or a temporary user session token would have a defined TLL to prevent the use of outdated information.

The working set model is a principle in memory management that defines the subset of total pages or cache entries a process actively needs within a specific time interval (the working set window) to operate efficiently without excessive page faults. LRU is a practical implementation heuristic for approximating the working set. If the cache size is at least as large as the working set, performance is optimal. For autonomous agents, understanding the working set of its active context—the chunks of memory, tools, and facts needed for the current task—is key to sizing memory caches correctly and minimizing retrieval latency.

A write-back cache is a storage optimization technique where data modifications are written only to the cache initially. The update to the slower, backing store (like a database or disk) is deferred until the cache block is evicted. This dramatically improves write performance but introduces complexity: the cache must track dirty bits for modified blocks and ensure writes are persisted on eviction to prevent data loss. In agentic systems, a write-back strategy might be used for a fast, in-memory experience buffer, with batched writes to a persistent vector store, where LRU could trigger the flush of dirty evicted memories.