Cache Eviction

The Least-Recently-Used (LRU) algorithm evicts the cached key-value pairs for the tokens that were accessed farthest in the past. It operates on the principle that recently used context is more likely to be needed again for coherent continuation.

• Implementation: Typically uses a doubly-linked list and a hash map for O(1) access and eviction.
• Impact on LLMs: Effective for maintaining local coherence in dialogue but can discard critical long-range dependencies from the beginning of a document.
• Example: In a 4k context window, if the 1,000th token hasn't been attended to in many generation steps, its KV cache is a prime candidate for eviction.

The First-In-First-Out (FIFO) policy evicts cached tokens in the order they were computed, regardless of recent usage. It treats the KV cache as a simple circular buffer.

• Mechanism: The oldest key-value pairs are overwritten first as new tokens are generated.
• Trade-off: Extremely simple and low-overhead but can be highly disruptive, as it may evict foundational context (e.g., system prompts or core document premises) needed for the entire session.
• Use Case: Sometimes used in high-throughput, streaming inference where absolute minimal management overhead is required.

The Least-Frequently-Used (LFU) algorithm evicts the key-value pairs for tokens that have been referenced the least number of times during the generation session.

• How it works: Maintains a frequency counter for each cached position. The token with the smallest count is evicted.
• LLM Consideration: Can preserve foundational tokens that are repeatedly attended to (e.g., a character's name in a story) but may retain stale, high-frequency tokens that are no longer relevant.
• Challenge: Requires additional metadata (frequency counts) and can suffer from 'cache pollution' where an initially high-frequency token becomes obsolete.

Attention-score-based eviction uses the model's own attention mechanism to decide what to keep. It evicts tokens whose key vectors received the lowest aggregate attention scores from recent queries.

• Rationale: Directly targets semantic relevance; tokens that the model itself "ignores" are safe to remove.
• Process: Computes a rolling sum of attention scores for each cached key. Periodically evicts tokens below a threshold.
• Advantage: More semantically informed than LRU/FIFO. Can help preserve narratively important but temporally distant context.
• Overhead: Requires tracking or sampling attention distributions, adding computational cost.

Random eviction selects cached tokens for removal uniformly at random. It is a stochastic, non-deterministic policy.

• Characteristics: Zero management overhead and can be surprisingly effective in large caches due to statistical dispersion.
• Drawback: Unpredictable; may occasionally evict critical context, leading to sudden coherence breaks or factual errors in generation.
• Application: Rarely used as a primary policy in production LLM serving but serves as an important baseline in cache performance research.

Modern systems often employ hybrid or size-aware policies that combine multiple signals for intelligent eviction.

• Examples:
  • LRU-K: Evicts based on the time of the K-th-to-last reference, better resisting one-time spikes.
  • Adaptive Replacement Cache (ARC): Dynamically balances between recency (LRU) and frequency (LFU) lines.
  • Model-Aware Policies: Integrate token importance scores from the model's logits or intermediate activations.
• LLM-Specific Design: The optimal policy often depends on the task—LRU for chat, attention-based for long-document QA—leading to runtime-switchable eviction strategies.

The Least-Recently-Used (LRU) algorithm evicts the cached data that has not been accessed for the longest time. It's based on the principle of temporal locality.

• Mechanism: Tracks access timestamps or maintains an ordered list. The oldest entry is discarded first.
• KV Cache Application: When the GPU memory allocated for the Key-Value cache is full, the attention states for the tokens generated earliest in the sequence are typically evicted.
• Pro: Simple and effective for many access patterns.
• Con: Can perform poorly if older context is suddenly needed again, potentially harming coherence in very long generations.

The First-In-First-Out (FIFO) policy evicts cached data in the order it was added, regardless of how recently it was used.

• Mechanism: Operates like a queue. New entries are added to the tail; the entry at the head is removed when eviction is required.
• System Context: Often used in streaming or pipeline buffers where data has a strict chronological lifespan.
• Pro: Extremely low overhead, no need to track access frequency.
• Con: Can evict frequently used, critical data simply because it was loaded earlier, leading to poor cache hit rates.

The Least-Frequently-Used (LFU) algorithm evicts the cached data with the smallest number of accesses over a recent period.

• Mechanism: Maintains a counter for each cache entry that increments on every access. The entry with the smallest count is evicted.
• Consideration for LLMs: While less common for pure KV cache eviction, variants are relevant for semantic cache systems that store frequent query-embedding pairs. It prioritizes retaining commonly referenced context patterns.
• Pro: Excellent for stable, repetitive access patterns.
• Con: Can become biased, where once-popular but now stale data occupies cache, and it requires more metadata (counters).

Random Replacement (RR) selects a victim cache entry at random when eviction is necessary.

• Mechanism: Uses a pseudo-random number generator to pick an index within the cache to evict.
• System Context: Used in high-performance computing and some CPU caches due to its simplicity and lack of state overhead.
• Pro: Zero metadata overhead and fast decision time. Avoids pathological worst-case scenarios of deterministic policies.
• Con: Performance is unpredictable and generally lower on average than LRU or LFU for most workloads. Not typically used for KV cache management where coherence is critical.

In transformer inference, KV Cache eviction is directly tied to GPU memory limits. The cache stores (Key, Value) matrices for previous tokens to avoid recomputation.

• Trigger: Eviction occurs when the pre-allocated cache memory is exhausted during the generation of a long output sequence.
• Typical Policy: A form of LRU applied to sequence positions. The earliest tokens in the sequence (often from the initial prompt or early generation) are evicted first, as their attention influence typically decays.
• Impact: Evicting essential context can cause the model to "forget" early instructions or narrative details, leading to coherence breakdown or task failure. This necessitates context management strategies like summarization or selective retention.

An admission policy determines whether new data is inserted into the cache at all, working in tandem with the eviction policy.

• Always Admit: Every new piece of data (e.g., new token's KV states) is written to cache, forcing an eviction. This is standard for streaming KV caches.
• Probabilistic Admission: New data is only cached with a certain probability (e.g., TinyLFU). This filters out one-hit wonders, items accessed only once, preserving cache space for more valuable entries.
• Size-Aware Admission: Considers the size of the new item versus the size of potential victims. A large item might not be cached if it would evict many smaller, potentially more useful items.
• Context: In LLM systems, admission is usually "always admit" for the KV cache, but these policies are highly relevant for higher-level semantic or document caches built atop the model.

The KV cache is the transformer mechanism that cache eviction policies manage. During autoregressive generation, a model computes and stores key (K) and value (V) vectors for each previous token. This cache prevents redundant computation on each new generation step, dramatically speeding up inference. The cache's size grows linearly with sequence length, consuming GPU memory. When this memory is full, a cache eviction algorithm (like LRU) determines which cached vectors to discard to make room for new tokens.

The context window is the fixed-size, contiguous block of tokens a transformer model can process in a single forward pass. It represents the model's total working memory. The KV cache is a performance optimization for generating text within this window. Cache eviction becomes necessary when a long-generation task's sequence length approaches or exceeds the practical memory limits for the KV cache, even if within the theoretical context window. Managing the cache is thus essential for fully utilizing the available context.

Context compression is a proactive strategy to reduce token footprint before hitting hard memory limits. Techniques include:

• Summarization: Condensing long passages.
• Selective Pruning: Removing tokens deemed less important.
• Token Merging: Combining semantically similar tokens. While cache eviction reactively discards cached computations, compression aims to preserve the semantic utility of information within the context window in a more compact form, potentially delaying or reducing the need for eviction.

Sliding window attention is an architectural approach to long contexts that inherently limits cache size. In this sparse attention pattern, each token can only attend to a fixed number of preceding tokens within a local window (e.g., 4096). Tokens outside this window are inaccessible. This design means the KV cache only needs to store vectors for the most recent W tokens, where W is the window size. Eviction of the oldest tokens is therefore built into the architecture, happening automatically as the window slides, rather than being a separate policy decision.

Incremental encoding is the process that relies on a maintained KV cache. It refers to processing a streaming input where new tokens are appended, and their key-value vectors are added to the existing cache without re-computing the entire sequence from scratch. This enables low-latency interactions. Cache eviction is the necessary counterpart to incremental encoding for long sessions; without eviction, the cache would grow unbounded. Efficient systems combine incremental encoding with a smart eviction policy to balance speed and memory use over long dialogues or documents.

Dynamic context refers to systems where the effective context window or retained information adapts at runtime. A system implementing sophisticated cache eviction is a form of dynamic context management. Instead of a simple fixed window, it can use policies to prioritize which parts of a long history (e.g., the most recent exchanges, system instructions, or highly attended tokens) to keep in the active KV cache. This moves beyond a static limit towards an intelligent, task-aware allocation of the finite memory resource, optimizing for both performance and task relevance.