Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Technical Summary: Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Problem Statement
Large Language Model (LLM) serving systems face significant challenges in managing Key-Value (KV) caches due to the growing size of models and context lengths, which strain limited GPU memory capacity. While prefix caching and reuse are critical for reducing redundant computation and improving throughput, existing management strategies predominantly rely on Least-Recently-Used (LRU) eviction policies. The authors argue that LRU is insufficient for the diverse and complex access patterns found in real-world LLM workloads. Specifically, LRU fails to distinguish between requests that exhibit strong temporal locality (recent access) and those that act as "hotspots" (frequent access across different users or sessions). This limitation leads to unrelated workloads flushing each other's caches, degrading hit rates and increasing latency, particularly in scenarios like document-based Question Answering (QA) and multi-turn conversations.

Methodology
To address these limitations, the paper proposes integrating the Adaptive Replacement Cache (ARC) algorithm into the vLLM serving framework. The methodology introduces a hybrid recency-frequency strategy that dynamically allocates cache space between recently accessed and frequently accessed KV blocks.

The core technical components include:

1. Dual-Queue Structure: The cache is logically split into two queues:
   • L1 (Recency Queue): Contains items accessed once (composed of physical cache $T1$ and ghost cache $B1$).
   • L2 (Frequency Queue): Contains items accessed multiple times (composed of physical cache $T2$ and ghost cache $B2$).
   • Items in the recency queue are promoted to the frequency queue upon a second hit.
2. Ghost Caching: The system utilizes "ghost caches" ($B1$ and $B2$) that store only metadata (not full KV blocks) for evicted items. These caches track the history of evictions.
   • If a request misses the main cache but hits in a ghost cache, it serves as a feedback signal. A hit in $B1$ suggests the recency queue ($T1$) is too small, while a hit in $B2$ suggests the frequency queue ($T2$) needs expansion.
3. Dynamic Partitioning: Based on ghost cache hits, the algorithm dynamically adjusts the size of the physical caches $T1$ and $T2$ while maintaining a fixed total cache size. This allows the system to adapt to workload shifts, such as the emergence of new hotspots or changes in user activity patterns.
4. Integration: The strategy operates at the KV block level (e.g., 16 tokens), aligning with the paged attention mechanism used in modern serving systems. It is designed to be parameter-free and integrates directly with the vLLM evictor module.

Key Contributions

• Adaptive Eviction Policy: The paper introduces the first application of ARC to LLM serving, moving beyond static recency-based policies to a dynamic hybrid approach.
• Workload Adaptability: The method demonstrates the ability to automatically balance cache resources between recent and frequent access patterns without manual tuning.
• Interpretability: Unlike learning-based approaches that require training predictors, this method offers clear interpretability regarding how cache space is allocated based on access history.
• Open-Source Implementation: The authors provide an open-source implementation integrated with vLLM, available for community use and further research.

Experimental Results
The authors evaluated the proposed method against the standard vLLM LRU baseline and a static two-queue variant (DBL) using two primary workload types:

1. Synthetic Document QA: Using the QuALITY and WikiQA datasets with Zipf-distributed request sampling.
   • Hit Rate: Improved by up to 10.8% (QuALITY) and 7.8% (WikiQA) compared to LRU.
   • Time to First Token (TTFT): Reduced by up to 12.6% (QuALITY) and 7.9% (WikiQA).
   • The improvements were most pronounced at smaller cache sizes where eviction decisions are more frequent.
2. Real-World Conversation: Using a trace from the Qwen-Bailian Anonymous Dataset (43,058 requests).
   • Hit Rate: Improved by 1.1%–2.1%.
   • TTFT: Reduced by 1.0%–2.0%.
   • The study noted that adaptive sizing became increasingly beneficial as cache sizes grew larger, capturing long-scale workload shifts that static policies missed.
3. Batch Inference: Experiments varying batch sizes on the QuALITY dataset showed that the relative advantage of ARC over LRU persisted and slightly increased with larger batch sizes, maintaining a 5–7% reduction in TTFT.

Significance and Claims
The paper claims that adaptive KV cache management is a practical and effective mechanism for enhancing LLM serving performance. By capturing reuse patterns beyond simple recency, the proposed method improves cache hit rates and reduces latency across diverse workloads. The authors emphasize that their approach generalizes well to batch inference and provides a foundation for future systems to handle complex, shifting access patterns without the overhead of training-based predictors. The work suggests that dynamic partitioning of cache resources is a critical step toward more efficient LLM deployment in production environments.