Least Recently Used (LRU)

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.

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.