Source-linked AI summary
The KV Cache Working Set: Online Capacity Planning for LLM Inference Systems
Luchang Li, Shuaishuai Wang, Zhao Ruan, Dongfang Li, Bozhao Gong
TL;DR
LLM cache provisioning must balance expensive retention of historical KV states against preserving useful prefix hits. KVSET estimates capacity needs online using stack distances rather than separate simulations for many cache sizes, and its predicted hit rates closely match deployed-cache measurements.
Problem
Retaining all historical KV states can require impractically large storage, while repeated simulation across cache sizes is costly and difficult to integrate into online serving.
Source: §1 · p. 2Method
KVSET uses the Mattson stack algorithm and Fenwick-tree stack-distance computation to estimate LRU hit rates across capacities from a single replay and find target capacity.
Source: §1 · p. 3, §2 · pp. 3–4Results
KVSET's predicted hit rates closely match measurements from deployed caches across capacities.
Source: §3 · p. 4Takeaways & Limitations
For the evaluated workload, approximately 5 TiB suffices at 99% coverage and approximately 1 TiB at 95%, illustrating a storage-performance trade-off.
Source: §3 · p. 6KVSET currently applies only to caches using LRU eviction and to full-attention KV states; extending beyond these remains future work.
Source: §5 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
Prefix caching can improve LLM serving by reusing KV states, but retaining too much history is expensive and sizing a cache for a target hit rate is difficult. KVSET addresses this with online capacity analysis that avoids replaying the workload separately for many cache sizes.
1 Introduction
- Repeated prefix reuse avoids redundant prefill computation, and prefill throughput rises sharply at high KV cache hit rates rather than scaling linearly.Figure 1 estimates throughput from the zero-hit throughput using Equation 1.Source: §1 · pp. 1–2, Figure 1 · p. 2
- Retaining every historical KV state can require an impractically large storage pool, while capacity-by-capacity simulation imposes substantial compute and latency overhead.The repeated replay required by existing approaches makes real-time integration with online serving systems difficult.Source: §1 · p. 2
- KVSET uses the Mattson stack algorithm to estimate hit rates across multiple capacities in one pass and identifies the minimum capacity meeting a target hit rate.The framework targets page-granular LRU prefix caches and supports online request processing and offline trace replay.Source: §1 · p. 3
2 Method
KVSET uses the LRU stack property to assess page hits at arbitrary cache capacities. A Fenwick tree helps compute each access's stack distance, allowing hit-rate curves and target-capacity estimates without separate cache replays.
2 Method
- Under LRU, a page is retained at capacity C when its stack distance is smaller than C; KVSET uses this property to characterize eviction across capacities.The Mattson stack algorithm derives hit or miss outcomes from stack distance.Source: §2 · p. 3, Figure 2 · p. 4
- KVSET records each page's most recent access position and uses a Fenwick tree to count distinct pages accessed more recently, yielding stack distance.This computes the distance without maintaining a separate cache instance for each capacity.Source: §2 · p. 3
- A single replay yields hit-rate outcomes across capacities, and the maximum LRU depth among the prefix pages needed for the target hit rate gives the minimum capacity.The illustration shows that capacity 1 suffices when two pages are expected to hit, while three expected hits require capacity 2.Source: §2 · p. 4, Figure 2 · p. 4
3 Evaluation
KVSET's predicted hit rates closely match measurements from deployed caches. Production-trace analysis also shows that required capacity depends on the coverage target, with storage needs and marginal hit-rate gains varying as capacity grows.
Capacity Estimation Accuracy
- KVSET's predicted hit rates closely match deployed-cache measurements across capacities.The comparison uses a 10,000-request internal production coding-agent trace and physical cache pools configured for SGLang.Source: §3 · p. 4, Figure 3 · p. 5
- Hit rate increases rapidly in the low-capacity regime, but marginal improvement diminishes substantially beyond a certain capacity.The paper identifies a trade-off between storage cost and the throughput improvement enabled by a higher hit rate.Source: §3 · p. 5
Online KV Cache Capacity Analysis
- Across a 24,000-request production trace, cumulative capacity for retaining all historical KV states increases monotonically as requests arrive.The curves drop near 21,000 requests because the number of concurrently active users decreases.Source: §3 · p. 5, Figure 4 · p. 6
- At 99% coverage, approximately 5 TiB is sufficient for this workload; at 95% coverage, required capacity decreases to approximately 1 TiB.The paper suggests approximately 1 TiB of CPU memory and 5 TiB of disk for a two-tier configuration targeting 95% and 99% request coverage, respectively.Source: §3 · p. 6
4 Related Work
KVSET builds on cache stack-distance analysis but applies it to page-granular LLM prefix caches and request-level hit-rate targets. Its provisioning focus complements systems that optimize runtime cache behavior.
Cache working-set and miss-ratio analysis
- Prior work derives LRU hit and miss ratios across capacities, while KVSET targets exact, page-granular analysis of LLM prefix caches and request-level hit-rate targets.It converts token-prefix reuse into a KV-page reference stream and reports capacity for retaining a target fraction of theoretically reusable prefixes.Source: §4 · p. 7
KV cache systems and workload studies
- Unlike tools that replay traces across memory budgets, KVSET maintains one reuse-distance state to estimate many LRU capacities as requests arrive.The related-work discussion distinguishes this provisioning analysis from prior work on serving architecture, workload characterization, and policy design.Source: §4 · p. 7
Agentic-workload KV management
- KVSET asks how much storage is needed for a specified fraction of requests to retain a target fraction of their theoretically reusable prefix, complementing runtime optimizations.The paper identifies DRAM and SSD tier sizing as an application alongside agentic-workload cache scheduling, eviction, and prefix-reuse work.Source: §4 · p. 7
5 Conclusion
KVSET estimates the capacity needed to meet a target hit rate, and its estimates closely match deployed-cache measurements on production coding-agent traces. In the evaluated workload, 99.9% coverage did not converge within the observed trace, and the analyzer is limited to LRU caches and full-attention KV states.
5 Conclusion
- Approximately 1 TiB and 5 TiB preserved theoretical hit rates of 95% and 99% of requests, while 99.9% coverage did not converge in the observed trace.Source: §5 · p. 7
- KVSET combines Mattson stack analysis and a Fenwick tree to estimate multiple-capacity hit rates in one replay and infer minimum capacity for a target hit rate.Source: §5 · p. 7
- Its estimates closely matched deployed-cache measurements on production coding-agent traces, supporting capacity analysis without deploying or separately simulating every cache size.Source: §5 · p. 7
- KVSET estimates capacity only for LRU caches and full-attention KV states; extending analysis beyond these remains future work.Source: §5 · pp. 7–8