Cache Eviction

Least Recently Used (LRU) evicts the data that has not been accessed for the longest time. It operates on the principle that recently used information is more likely to be needed again.

• Mechanism: Typically implemented with a doubly linked list and a hash map. When data is accessed, it's moved to the front (most recent). The tail of the list holds the least recently used item for eviction.
• Use Case: Highly effective for conversational agents where the most recent user query and the model's immediate prior response are critical for coherence.
• Drawback: Can be inefficient if older context becomes relevant again later in a long session, leading to cache thrashing.

First-In-First-Out (FIFO) evicts the oldest entry in the cache, regardless of how often or recently it has been used. It's a simple queue-based policy.

• Mechanism: New entries are added to the back of a queue. When eviction is required, the entry at the front (oldest) is removed.
• Use Case: Useful for streaming data or logging scenarios where historical order is the primary concern, or when access patterns are completely uniform.
• Drawback: Often performs poorly in practice because it may evict frequently accessed, valuable context simply because it was loaded early.

Least Frequently Used (LFU) evicts the item that has been used the least number of times. It prioritizes retention based on historical popularity.

• Mechanism: Maintains a counter for each cache entry that increments on every access. The entry with the smallest count is evicted.
• Use Case: Can be effective for agents with repetitive tasks where certain foundational context (e.g., system prompts, core instructions) is referenced constantly.
• Drawback: Prone to cache pollution. An item accessed many times in the distant past may persist indefinitely, blocking newer, potentially more relevant context. Requires more overhead to track frequencies.

Random Replacement (RR) selects a candidate entry for eviction at random. It is a stateless, low-overhead policy.

• Mechanism: On eviction, a pseudo-random number generator selects an index in the cache to remove.
• Use Case: Provides a simple baseline. Its performance can be surprisingly competitive when access patterns are unpredictable or when the overhead of tracking recency/frequency is prohibitive.
• Drawback: Unpredictable and can evict critical, hot context by chance, leading to performance volatility. Not suitable for deterministic or high-performance agentic systems.

Time-To-Live (TTL) Expiration is not a capacity-driven policy but a time-based one. Each cache entry has a timestamp and is evicted once a predefined lifespan expires.

• Mechanism: A background process or a check on access scans for entries whose (creation_time + TTL) < current_time.
• Use Case: Essential for ensuring context freshness. Critical in multi-agent systems where cached state (e.g., sensor data, market prices) becomes stale and misleading after a certain period.
• Drawback: Does not directly address capacity limits. Often used in conjunction with another policy (e.g., LRU-TTL) where entries are evicted due to expiry or capacity pressure.

Modern systems often use adaptive or hybrid policies that combine strategies or adjust behavior based on runtime workload characteristics.

• Examples:
  • LRU-K: Considers the time of the K-th-to-last access, better resisting one-hit wonders that pollute a standard LFU cache.
  • 2Q (Two Queues): Uses two queues: an LRU queue for items accessed once and a main LRU queue for items accessed multiple times, improving hit rates.
  • ARC (Adaptive Replacement Cache): Dynamically balances between recency (LRU) and frequency (LFU) by maintaining both lists and adapting their size based on misses.
• Use Case: Complex, long-running autonomous agents with shifting context needs, where no single static policy is optimal.

The KV Cache is a transformer optimization that stores pre-computed key and value tensors for previously generated tokens during autoregressive inference. This cache eliminates redundant computation for the attention mechanism, dramatically speeding up sequential token generation. Its size is directly proportional to the context length, making efficient cache eviction essential for managing long sequences without exhausting GPU memory.

• Purpose: Accelerates generation by caching attention layer outputs.
• Memory Footprint: Grows with batch size, sequence length, and model dimensions.
• Eviction Trigger: When the cache exceeds available memory or a predefined token limit, an eviction policy must decide which cached tensors to discard.

A context eviction policy is a deterministic rule set that selects which entries to remove from a cache when capacity is reached. It is the algorithmic core of the cache eviction process. Common policies include:

• Least Recently Used (LRU): Discards the item that hasn't been accessed for the longest time. Effective for conversational agents where recent turns are most relevant.
• First-In-First-Out (FIFO): Removes the oldest item in the cache, regardless of usage. Simple but can evict critical, frequently accessed context.
• Least Frequently Used (LFU): Evicts the item with the fewest accesses. Can be problematic if early, important context is never re-accessed.
• Random Replacement: Randomly selects an item for eviction. Low overhead but unpredictable. The choice of policy directly impacts an agent's ability to retain pertinent operational state.

Context window saturation occurs when a model's fixed token limit is fully utilized, preventing the injection of new tokens without first removing existing ones. This is the primary condition that triggers cache eviction. In agentic workflows, saturation forces a trade-off:

• Information Loss: Evicting context may discard critical instructions, historical facts, or intermediate reasoning steps.
• Performance Degradation: Models can "forget" early context, leading to incoherent or contradictory outputs.
• Management Overhead: Requires systems to monitor token counts and execute eviction or compression routines automatically. Saturation is an engineering constraint that defines the working memory boundary for any single inference call.

StreamingLLM is a framework that enables language models trained with a finite context window to process infinite-length text streams without fine-tuning. It achieves this by leveraging attention sinks—the observation that initial tokens receive disproportionately high attention scores—and maintaining a fixed-size sliding window cache of recent tokens.

• Mechanism: Keeps the first few tokens (the attention sink) and the most recent N tokens in the KV Cache, evicting the middle tokens.
• Eviction Implication: Implements a hybrid eviction policy: absolute retention of sink tokens and FIFO eviction for the recent token window.
• Use Case: Essential for long-running chatbots, log processing, and real-time transcription where context far exceeds the native window.

Context caching is the broader strategy of storing and reusing previously computed context—such as KV Cache states, summarized dialogue history, or retrieved document chunks—across multiple inference calls or user sessions. Cache eviction is the cleanup mechanism for this strategy.

• Objective: Reduce latency and computational cost by avoiding redundant processing of static or repeated context.
• Examples: Caching system prompts, frequently accessed knowledge base snippets, or the state of a multi-step planning process.
• Challenge: Requires invalidation logic (eviction) to ensure cached data does not become stale or incorrectly applied to new queries.

Sliding window attention is an efficient attention mechanism where a transformer model only attends to a fixed-size window of the most recent tokens. This creates a built-in, implicit cache eviction policy: as new tokens are added, tokens that fall outside the window are automatically excluded from attention calculations.

• Memory Efficiency: Provides a constant, predictable memory cost (O(window_size)) for sequences of arbitrary length.
• Eviction Behavior: Implements a strict FIFO eviction from the attention scope; older tokens are "forgotten" by the model's attention heads.
• Trade-off: While efficient, it limits the model's ability to draw connections between distant parts of a very long sequence.