Least Recently Used (LRU)

LRU's core logic is simple: the item that has not been accessed for the longest time is evicted first. It assumes that recently used data is more likely to be used again in the near future (temporal locality).

• Implementation: Typically requires tracking access order, often using a doubly linked list combined with a hash map for O(1) operations.
• Contrast with LFU: Unlike Least Frequently Used (LFU), which counts total accesses, LRU cares only about the timing of the most recent access.

A canonical, efficient LRU implementation uses two data structures in tandem to achieve constant-time operations for get and put.

• Hash Map (Dictionary): Provides O(1) lookup by key to find the corresponding node in the linked list.
• Doubly Linked List: Maintains items in order of access. On any access (get or put), the touched node is moved to the head (most recent). The node at the tail is the least recently used and is evicted on capacity overflow.

This combination guarantees O(1) time complexity, which is critical for high-performance caching layers.

A significant weakness of pure LRU is its vulnerability to one-time scans or looping access patterns that pollute the cache.

• Scenario: If a process sequentially reads a dataset larger than the cache capacity, every existing item is evicted because each new item becomes the 'most recent'.
• Impact: This causes 100% cache misses for the legitimate, working-set data that follows the scan, severely degrading performance.
• Mitigation: Advanced variants like LRU-K or Adaptive Replacement Cache (ARC) were developed to be more resilient to such patterns by considering frequency alongside recency.

LRU excels under specific, predictable access patterns where its core assumption holds true.

• Strong Temporal Locality: The same data is accessed in clusters over short periods (e.g., a user repeatedly querying their own recent transactions).
• Stable Working Set: The set of 'hot' data fits within the cache capacity and changes relatively slowly.
• Common Use Cases: CPU caches, database buffer pools, and in-memory caches for web session data often use LRU or its variants due to these predictable patterns.

In the context of AI agents and tool calling, LRU can manage the cache of API responses or computed results within an agent's session.

• Caching Deterministic Calls: Ideal for caching the results of pure function calls or idempotent API requests where the same input (prompt, parameters) yields the same output.
• Managing Session Context: Used to keep the most recently accessed pieces of context, conversation history, or tool results within a limited token window or memory budget.
• Integration with Semantic Cache: Can be a component in a larger system where a semantic cache first finds a similar request, and an LRU policy manages the physical storage of those cached results.

Pure LRU's limitations led to the development of more sophisticated algorithms that retain its benefits while adding robustness.

• LRU-K: Tracks the times of the last K references to an item. Eviction is based on the K-th most recent access time. This filters out one-time accesses (noise) and better identifies truly 'hot' items.
• Adaptive Replacement Cache (ARC): Maintains two LRU lists: one for recently used items (T1) and one for frequently used items (T2). It dynamically adapts the size of these lists based on the workload, effectively balancing recency (LRU) and frequency (LFU). ARC is self-tuning and generally outperforms both LRU and LFU.

Cache eviction is the process of removing items from a cache to free up space for new entries. It is a critical function triggered when a cache reaches its capacity limit. The choice of eviction policy—such as LRU, LFU, or FIFO—directly impacts cache performance and hit ratios. In agent-side caching, intelligent eviction ensures the most valuable API responses or computed results are retained to minimize redundant calls and latency.

• Primary Goal: Maintain cache efficiency by removing less useful data.
• Trigger: Typically occurs on cache full or based on a TTL expiration.
• Agent Context: Directly influences an AI agent's ability to recall recent interactions and maintain session performance.

Cache hit ratio is the primary metric for measuring cache effectiveness, calculated as (Number of Cache Hits / Total Cache Requests) * 100. A high hit ratio indicates that the cache is successfully serving requests without accessing the slower primary data source (e.g., an external API), reducing latency and load.

• Performance Indicator: A hit ratio of 95%+ is often a target for well-tuned caches.
• Agent Impact: Directly correlates to agent responsiveness and operational cost. A low hit ratio suggests poor caching strategy or unsuitable data patterns.
• Calculation: Includes both exact-match hits and, in advanced systems like semantic caches, hits on semantically similar queries.

A semantic cache stores results based on the meaning or intent of a query, rather than relying on an exact string match of the input. This is particularly powerful for AI agents interacting with LLMs or complex APIs, where users may phrase the same request in different ways.

• How it works: Uses embedding models to convert queries into vector representations. A cache hit occurs if a new query's vector is sufficiently similar to a cached query's vector.
• Agent Benefit: Dramatically increases cache utility for natural language interactions, allowing cache hits on paraphrased or conceptually identical requests.
• Eviction Challenge: Often used alongside traditional policies like LRU, but may require specialized similarity-based eviction strategies.

Time-To-Live (TTL) is a cache policy that defines the maximum duration a cached item is considered valid before it is automatically expired. It is a time-based cache invalidation strategy crucial for data where freshness is important.

• Absolute TTL: The item expires at a fixed timestamp (e.g., created_at + 300 seconds).
• Sliding TTL: The expiration timer resets on each access, keeping frequently used items alive.
• Agent Use Case: Ideal for caching API responses where the underlying data changes periodically (e.g., stock prices, weather data). An LRU policy combined with TTL ensures the cache holds only recent and fresh data.

The cache-aside pattern is a common caching strategy where the application (or AI agent) code explicitly manages the cache. The agent checks the cache first for data; on a cache miss, it fetches data from the primary source (e.g., an API), then populates the cache for future requests.

• Workflow: 1. Read from cache. 2. If miss, read from data source. 3. Write result to cache.
• Agent Responsibility: The agent's orchestration layer handles the logic for cache lookup, external calls, and storage. This pattern offers fine-grained control but adds complexity to the agent code.
• Contrast with Read-Through: In read-through, the cache system itself handles the miss, transparently to the agent.

Adaptive Replacement Cache (ARC) is a sophisticated, self-tuning eviction algorithm that dynamically balances between recency (like LRU) and frequency (like LFU). It maintains two lists: one for recent entries and one for frequent entries, adapting their size based on the observed workload.

• Self-Optimizing: Adjusts its behavior to the actual access pattern, outperforming pure LRU for workloads with mixed or looping access patterns.
• Agent Relevance: Highly effective for AI agents whose tool-calling patterns may shift between phases of a session (e.g., exploration vs. repeated execution).
• Complexity: More computationally intensive than LRU but can yield significantly higher hit ratios for dynamic workloads.