Abstract
The increasing adoption of large language models (LLMs) with extended context windows necessitates efficient Key-Value Cache (KVC) management to optimize inference performance. Inference workloads like Retrieval-Augmented Generation (RAG) and agents exhibit high cache reusability, making efficient caching critical to reducing redundancy and improving speed. We analyze real-world KVC access patterns using publicly available traces and evaluate commercial key-value stores like Redis and state-of-the-art RDMA-based systems (CHIME and Sherman) for KVC metadata management. Our work demonstrates the lack of tailored storage solutions for KVC prefilling, underscores the need for an efficient distributed caching system with optimized metadata management for LLM workloads, and provides insights into designing improved KVC management systems for scalable, low-latency inference.
Introduction
During LLM inference, the attention mechanism utilizes a Key-Value Cache (KVC) to store previously computed token representations. This mechanism is vital for preventing redundant calculations, especially as context windows expand in Retrieval-Augmented Generation (RAG) and agentic workflows. However, the resulting explosion in KVC size poses significant management challenges. To minimize Time to First Token (TTFT), modern serving engines employ prefix prefilling, which involves caching frequently used prompt prefixes. Retrieving these cached blocks requires a metadata manager—a database mapping token hashes to physical memory addresses. This study investigates whether traditional key-value stores are adequate for the unique demands of LLM KVC metadata management.
Analysis of KVC Access Patterns
To understand the requirements of KVC metadata management, we analyzed production traces from Mooncake’s LLM applications, covering "conversation," "tool&agent," and "synthetic" workloads. Our analysis revealed two critical characteristics:
- High Reusability: Over 75% of requests demonstrate a KVC block hit rate exceeding 50%. Temporal locality is particularly strong for initial system prompts and the most recently generated tokens.
- Mixed Access Patterns: KVC access within a single request is predominantly sequential, with an average of 86.8% contiguous blocks. This pattern favors range queries. However, the remaining accesses are highly random, creating a "sequential + random" hybrid workload that challenges traditional KV stores optimized for only one access type.
Benchmarking Distributed Key-Value Stores
We evaluated the performance of three systems—Redis (a popular commercial KV store) and two RDMA-based distributed stores, CHIME and Sherman—using a custom benchmark simulating KVC metadata operations (32-byte keys, 8-byte values).
Performance Bottlenecks
Our results indicate that traditional systems like Redis are ill-suited for microsecond-scale GPU operations. Redis exhibited p99 latencies exceeding 0.1 ms. Given that GPU TTFT can be as low as 0.44 ms, such metadata lookup overhead represents a significant performance penalty.
While RDMA-based systems like CHIME and Sherman offer much lower latency, they are not perfectly tuned for LLM workloads. Sherman, optimized for write-heavy tasks, and CHIME, which struggles with sequential chunk access, both showed high variability in p99 latency during range queries. Specifically, Sherman outperformed CHIME by 10.3% on range queries, while CHIME was 5.5% faster for search latency.
Conclusion and Future Directions
Current key-value stores lack the architectural alignment necessary for efficient LLM KVC management. As optimizations like chunked prefilling further reduce data transfer times, metadata lookup latency will become the primary bottleneck.
Future work involves developing a purpose-built hierarchical KVC caching system. Key features will include a reuse-optimized metadata cache, a workload-aware index structure to balance sequential and random lookups, and hotness-aware data placement. We also intend to release a specialized KVC benchmark to better evaluate future LLM storage solutions.
Summary updated