Cache Eviction

Least-Recently-Used (LRU) is the most prevalent cache eviction policy. It removes the key-value pairs for tokens that have not been accessed for the longest period. This policy operates on the temporal locality principle, assuming recently used tokens are more likely to be needed again.

• Mechanism: Each cache entry has an associated timestamp or is moved to the front of a list upon access. When eviction is triggered, the oldest entry is discarded.
• KV Cache Application: In autoregressive decoding, the model attends to all previous tokens. LRU effectively prioritizes keeping tokens from more recent parts of the conversation or document, which often have higher relevance for predicting the next token.
• Advantage: Simple to implement and effective for many conversational and document completion workloads.
• Limitation: Can perform poorly if the working set is larger than the cache and access patterns lack strong recency bias.

First-In-First-Out (FIFO) evicts the oldest cached entries based on insertion time, regardless of how recently they were accessed. It treats the cache as a circular queue.

• Mechanism: New entries are added to the tail of the queue. When the cache is full, the entry at the head (the first one inserted) is removed.
• KV Cache Application: In a long, continuous stream of tokens, FIFO provides a deterministic, rolling window over the most recent context. It is computationally cheaper than LRU as it requires no tracking of access recency.
• Use Case: Suitable for streaming applications where the model must maintain a fixed, sliding context window (e.g., real-time transcription, infinite streaming chat).
• Drawback: It can evict frequently accessed, important tokens if they were loaded early in the sequence, potentially harming coherence in long conversations.

Least-Frequently-Used (LFU) evicts the tokens whose key-value pairs have been accessed the least number of times. It prioritizes retention based on historical popularity.

• Mechanism: Maintains a counter for each cache entry that increments on every attention access. The entry with the smallest count is evicted.
• KV Cache Application: In theory, this could protect important, recurring concepts or entities mentioned throughout a long document. However, it is rarely used in pure form for KV caches due to a critical flaw: it can become poisoned by tokens that were accessed frequently early on but are no longer relevant, blocking space for newer, more immediately useful tokens.
• Variants: Aging LFU periodically reduces counts to address the 'staleness' problem, making it more adaptive.
• Consideration: The overhead of maintaining and comparing frequency counters for every token in a large cache is often prohibitive for high-throughput inference.

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

• Mechanism: Uses a pseudo-random number generator to select a cache block or page for eviction.
• KV Cache Application: Its primary virtue is implementation simplicity and speed. In systems like vLLM with PagedAttention, where the cache is divided into fixed-size blocks, random eviction at the block level can be efficient.
• Performance: Surprisingly, its average-case performance can be competitive with more complex policies, especially when the access pattern is unpredictable or the cache is large. It avoids the worst-case scenarios of FIFO or LRU when faced with adversarial access patterns.
• Drawback: Performance is non-deterministic and can occasionally evict critical, high-utility tokens, leading to variable latency.

Size-aware eviction policies consider the memory footprint of cached entries, not just their access pattern. The goal is to maximize the utility of freed memory.

• Mechanism: When eviction is needed, the policy evaluates candidates based on a cost-benefit metric, such as (access recency or frequency) / (size in bytes). It may evict a single large, less-useful entry instead of several smaller, more useful ones.
• KV Cache Application: Highly relevant for PagedAttention and KV cache compression techniques. Different attention heads or layers may have key-value tensors of varying precision (e.g., FP16 vs. INT8) or sparsity, leading to variable-sized cache blocks.
• Example: A policy might choose to evict a full-precision (FP16) KV block from a less critical layer before evicting a quantized (INT8) block from a more critical layer.
• Benefit: Enables more granular and efficient use of the total cache budget, potentially allowing for longer effective context windows.

Modern inference systems often employ hybrid or adaptive eviction policies that switch strategies based on runtime workload characteristics.

• Mechanism: A monitoring subsystem tracks metrics like cache hit rate, batch composition, and sequence length distribution. A controller can then select or blend policies.
• Examples:
  • LRU-K: Uses the time of the K-th-to-last access, which is more robust than pure LRU against sporadic bursts of accesses.
  • Adaptive Replacement Cache (ARC): Dynamically balances between recency (LRU) and frequency (LFU) by maintaining two adaptive lists. It self-tunes to the workload.
  • Workload-Aware: A system might use FIFO for very long streaming sessions but default to LRU for shorter, interactive chats.
• KV Cache Application: In a continuous batching environment with heterogeneous requests (e.g., short API calls mixed with long document summarization), an adaptive policy can optimize global throughput and latency by applying the most suitable eviction logic to different request types or cache partitions.

The Least-Recently-Used (LRU) policy evicts the cached key-value tensors for the tokens that have not been accessed for the longest time. This is based on the temporal locality principle—recently used tokens are likely to be needed again soon.

• Implementation: Requires tracking an access timestamp for each cached block or page.
• Overhead: Introduces metadata management but is highly effective for conversational workloads where recent dialogue is most relevant.
• Example: In a chatbot session, early introductory tokens may be evicted before more recent query and response tokens.

The First-In-First-Out (FIFO) policy evicts cached entries in the order they were created, regardless of how recently they were accessed. It operates like a simple queue.

• Implementation: Low overhead, requiring only a queue structure to manage eviction order.
• Use Case: Effective for streaming workloads where context has a strong sequential dependency and the model primarily attends to the most recent tokens.
• Limitation: Can perform poorly if early tokens remain important throughout the sequence, leading to unnecessary cache misses.

This policy uses the model's own attention scores as a heuristic for importance. Tokens with lower aggregate attention scores over recent decoding steps are considered less critical and are candidates for eviction.

• Implementation: Requires computing or estimating a rolling sum of attention weights directed at each cached token.
• Advantage: Aligns eviction decisions with the model's intrinsic reasoning; tends to preserve semantically important context.
• Challenge: Adds computational overhead to track scores, though this can be approximated efficiently.

In systems like vLLM, eviction operates at the block level rather than the token level due to the PagedAttention memory layout. The KV cache is managed in fixed-size blocks (e.g., 16 tokens).

• Granularity: Evicting an entire block is more efficient than tracking individual tokens, reducing metadata overhead.
• Policy Application: LRU or FIFO is applied to these blocks. A block is evicted only when all its tokens are eligible for removal.
• Benefit: Enables efficient memory sharing and zero fragmentation, which is foundational for high-throughput continuous batching.

Selecting an eviction policy involves a direct trade-off between memory savings and computational penalty.

• Cache Miss Penalty: Evicting a token that is later needed forces a recomputation of its key and value states during a subsequent decode step, which is expensive.
• Policy Overhead: More sophisticated policies (e.g., attention-based) have higher management overhead but may yield better cache hit rates.
• System Tuning: The optimal policy depends on workload patterns: conversational, document analysis, or long-context streaming.

Eviction must be coordinated with continuous batching schedulers. As new requests enter the batch and existing sequences complete generation, the global KV cache pressure changes dynamically.

• Dynamic Pressure: The scheduler must monitor aggregate cache usage across all concurrent sequences.
• Eviction Trigger: Eviction is triggered when total allocated cache nears physical capacity, not on a per-request basis.
• Orchestration: Systems like vLLM and TensorRT-LLM tie block-level eviction to their block manager, ensuring efficient memory reuse across the entire batch.

PagedAttention is the memory management algorithm that makes efficient cache eviction possible. It organizes the KV cache into non-contiguous, fixed-size blocks (pages). This structure allows the system to:

• Evict and allocate pages independently for different sequences in a batch.
• Eliminate internal memory fragmentation, a common cause of wasted cache capacity.
• Enable advanced features like memory sharing for identical prompt prefixes across requests. It is the foundational technology behind high-throughput inference engines like vLLM.

KV Cache Compression is a complementary strategy to eviction for managing cache size. While eviction removes entries, compression reduces the size of the entries that remain. Key techniques include:

• Quantization: Storing cache tensors in lower precision (e.g., FP8, INT4).
• Pruning: Removing attention heads or tokens deemed less important.
• Selective Caching: Only storing KV pairs for a subset of layers. These methods increase effective cache capacity, allowing longer contexts or larger batches before eviction is triggered.

Cache-Aware Scheduling is an orchestration strategy that groups inference requests to optimize cache utilization and minimize eviction overhead. A scheduler implementing this policy will:

• Batch requests with similar context lengths to reduce padding waste.
• Prioritize requests that can reuse cached prompts (e.g., from a common system prompt).
• Schedule sequences to promote temporal locality, keeping "hot" data in cache. This reduces the frequency of evictions and the performance penalty of cache misses.

A Memory-Bound Regime describes the performance state of an inference system where throughput and latency are limited by memory bandwidth, not compute. This is critically relevant to cache eviction because:

• The primary job of the GPU during the decode phase is to read the KV cache.
• Inefficient eviction policies that cause frequent, non-sequential memory access exacerbate this bottleneck.
• The goal of cache management is to keep the working set of active tokens within the high-bandwidth memory to avoid stalling the compute units.

Unified Virtual Memory is a hardware/software architecture (e.g., CUDA UVM) that enables techniques like KV Cache Offloading, which is a form of strategic, large-scale eviction to slower memory. UVM allows:

• The GPU to access a single virtual address space spanning GPU and CPU RAM.
• "Cold" portions of the KV cache to be transparently paged out to host memory.
• Systems to handle context windows far exceeding GPU memory capacity, though with a latency penalty for cache misses that require retrieval from CPU.