Kv cache working set estimation improves large language model efficiency
The KV Cache Working Set: Online Capacity Planning for LLM Inference Systems
Distributed, Parallel, and Cluster Computing
Summary
Large language models (LLMs) are often used in conversations where previous context is repeated. To avoid redoing work, systems keep a cache of key-value states from earlier parts of the conversation. But keeping too much cached data is costly, while too little hurts performance. The authors designed KVSET, a tool that estimates how much cache is really needed by analyzing requests efficiently. This helps design systems with better balance between speed and cost.
What this means in practice
- •For llm infrastructure teams: Determine the minimal cache size needed to maintain desired response speeds and reduce redundant computation in large language model deployments.
- •For cloud service operators: Optimize server resource allocation for conversational AI services by estimating cache needs dynamically using real workload traces.
Authors
Luchang Li, Shuaishuai Wang, Zhao Ruan, Dongfang Li, Bozhao Gong
Abstract
Prefix caching is critical for efficient large language model (LLM) serving, particularly for agentic workloads that repeatedly invoke the model with a growing conversation and tool-use history. By reusing the key-value (KV) states of previously processed prefixes, prefix caching avoids redundant prefill computation. Its effectiveness, however, depends on retaining a sufficiently large set of KV cache states. Provisioning enough cache to preserve all historical KV states is prohibitively expensive and often unnecessary, whereas insufficient capacity can substantially degrade the cache hit rate. Determining the KV cache working set, defined as the minimum cache capacity required to achieve a target hit rate, is therefore essential for efficient cache provisioning and system design. We present KVSET, an online analyzer that estimates the KV cache working set of LLM serving workloads. KVSET uses the Mattson stack algorithm to efficiently estimate cache hit rates across a wide range of cache capacities. For each KV cache page, KVSET computes its LRU stack distance and compares it with the page number of each candidate capacity. This comparison determines whether the page would be a hit at each capacity without independently simulating every capacity configuration. KVSET therefore substantially reduces the computational and memory overhead of conventional capacity-by-capacity simulation and makes online working-set analysis practical. KVSET further determines the minimum cache capacity based on the maximum LRU depth among the prefix pages required to achieve the target hit rate. We validate KVSET using traces collected from production LLM workloads and show that its estimates closely match measurements from real cache deployments. The open-source implementation supports both online request processing and offline trace replay.