KV cache working set capacity planning

KV cache working set capacity planning asks how much reusable state a workload needs, not how much state it has ever created.

The useful output is a capacity-to-hit-rate curve. For each cache size, estimate the prefix hit rate or request coverage that the workload would retain under the actual eviction policy.

Then choose a point on that curve and convert its pages into bytes. Total history, maximum context length, and current active tokens answer different capacity questions.

KV cache working set capacity planning

The KVSET paper defines the KV cache working set as the minimum cache capacity required to reach a target hit rate.

That definition has two parts. The workload supplies a stream of reusable KV pages. The operator supplies the service target, such as preserving 95% of theoretically reusable prefix pages.

The resulting capacity is smaller than the cumulative KV written over the trace when old pages stop being useful.

It can be larger than the active decode footprint because completed requests may leave prefixes worth reusing.

Track those pools separately. Active-request KV is required for current decoding. Prefix-cache KV is retained for possible future requests.

Fanout's KV cache memory formula gives bytes per token. Working-set analysis decides how many reusable tokens or pages deserve capacity.

Reuse distance gives the LRU curve

KVSET targets page-granular caches using least recently used eviction. Under LRU, one page's fate depends on its stack distance.

Stack distance is the number of distinct pages accessed more recently than that page. A cache of C pages contains the page when its distance is below C.

That test works for every candidate capacity. There is no need to replay a separate simulated cache for 10,000 pages, 20,000 pages, and every other size.

KVSET uses the Mattson stack algorithm and a Fenwick tree to calculate those distances efficiently. One request stream produces the full capacity-to-hit-rate curve.

The paper's implementation supports online processing and offline trace replay. Its scope matters: the estimate is exact for the modeled LRU page stream, not for every replacement policy.

The vLLM prefix-caching design also works in full blocks and evicts cached blocks from an LRU free queue.

That makes stack-distance analysis a natural fit, provided the trace uses the same block identity and cache scope as the serving deployment.

Work a seven-access example

Take the page-reference stream A, B, C, A, D, B, A. The first A, B, and C accesses are cold.

When A appears again, B and C have been accessed more recently. A has stack distance two, so it needs a capacity of at least three pages to hit.

When B appears again, C, A, and D are more recent. B has stack distance three and needs at least four pages.

The final A again has distance two. A three-page cache therefore hits the two repeated A accesses but misses the repeated B.

A four-page cache hits all three repeated accesses. The curve moves from two hits out of seven at capacity three to three out of seven at capacity four.

Real prefix requests contain ordered page chains. The engine reuses the longest valid prefix and stops at the first missing full block.

The trace must preserve that request structure. Counting popular pages without their prefix order can overstate useful reuse.

Fanout's prefix match unit guide explains why logical match boundaries and physical blocks also need to stay separate.

Choose hit rate and request coverage separately

An aggregate page hit rate weights long requests more heavily because they reference more pages.

Request coverage asks a different question: what fraction of requests retain a chosen share of their theoretical prefix hit?

KVSET reports capacity for a coverage target. A request's theoretical hit rate is the reuse available with unlimited cache capacity.

Suppose one long coding-agent request can reuse 10,000 pages while nine short requests can reuse 100 pages each.

Losing half of the long request removes 5,000 page hits but affects one request. Losing every short request removes 900 page hits but affects nine requests.

Neither metric is wrong. Page hit rate tracks avoided page work. Request coverage protects how widely the benefit is distributed.

Record both before choosing capacity. Also record reused tokens and avoided prefill time because equal page counts can have different compute value at different prefix depths.

The recent prefix-cache trace study found that miss cost grows with block depth and that two policies with equal hit ratios can save different amounts of prefill computation.

Convert pages into storage bytes

Let C be the selected page capacity, P the tokens per page, and B the physical KV bytes per token for the stored model shard and cache dtype.

The logical cache payload is C times P times B.

If C is 100,000 pages, P is 16 tokens, and B is 60 KiB per token, the payload is 96,000,000 KiB, or about 91.6 GiB.

The 60 KiB figure is the FP8 configuration in the KVSET evaluation. It is not a general constant.

Add allocator metadata, block tables, transport buffers, indexes, and operational reserve outside that payload.

For example, adding a 20% planning reserve to 91.6 GiB produces about 109.9 GiB. The 20% is an example assumption, not a recommendation from the paper.

Measure the deployed overhead instead. Page count remains useful only when a page means the same token count and physical layout in the analyzer and the engine.

Tensor parallelism changes per-rank bytes. KV quantization changes B. Hybrid models add recurrent or sliding-window state that KVSET does not currently estimate.

Size each storage tier by its job

HBM must hold active execution state and the hottest reusable pages while leaving room for weights, activations, CUDA graphs, and runtime workspaces.

DRAM and SSD can extend prefix retention, but their usable capacity depends on promotion latency and delivered bandwidth.

The llm-d cache architecture separates routing, indexing, offload, and peer sharing for this reason.

A page that exists on SSD but arrives after the prefill would have finished is storage capacity without latency value for that request.

Build one curve per tier policy. HBM residency answers the fast-hit curve. HBM plus DRAM answers the curve that includes transfers meeting the TTFT budget.

The InferenceX working-set example shows the distinction in benchmark telemetry.

Its B300 run kept more of the working set in HBM, while a B200 run relied more heavily on DRAM hits. The article warns that offload can raise tail latency when it covers a structural HBM shortfall.

Adding tier capacities does not make them one equivalent cache. Weight pages by whether each tier can return them before the request's deadline.

Read the knee, not the maximum

The working-set curve usually rises quickly and then flattens. The knee is where another unit of storage buys much less hit-rate or coverage improvement.

In KVSET's coding-agent trace, about 1 TiB preserved the theoretical hit rates of 95% of requests. About 5 TiB was needed for 99% coverage.

The 99.9% target did not converge within the observed trace. Those figures belong to one workload and should not be copied into another deployment.

They show why the target must be explicit. Moving from 95% to 99% coverage cost roughly four additional TiB in that experiment.

Price the next slice of capacity against avoided prefill time, storage cost, transfer cost, and the latency class of the requests it helps.

The page-one long-context capacity guide calculates active-residency limits from bytes per token.

Working-set sizing adds reuse history to that arithmetic. Both are needed because the active pool and the retained prefix pool compete for finite memory.

Re-estimate when the workload moves

A working set is a workload property, not a model-card constant.

Agent sessions can change length, turn cadence, tool schemas, tenant mix, and routing. Each change moves page identity, reuse distance, or the replica that sees the reuse.

Replay a window long enough to include session lifetimes and traffic cycles. Also calculate shorter rolling windows so a sudden shift does not hide inside a month-long average.

The recent trace study found that prefix-cache blocks often have session-bounded lifetimes and that adjacent working sets can overlap strongly before that overlap decays.

That behavior favors recent windows, but the correct duration still depends on the product's sessions.

Keep tokenizer version, chat template, model revision, LoRA identity, cache salt, multimodal hashes, block size, routing policy, and eviction policy attached to every trace.

A capacity estimate from one identity space cannot predict hits in another.

Compare the estimated curve with canary deployments at a few capacities. The point of the analyzer is to avoid a full capacity sweep, not to skip empirical validation.

A practical capacity worksheet

Start with a request trace that records ordered prefix-page identities without storing raw prompt text.

Calculate LRU stack distance for every page reference and derive hit rate across candidate capacities.

For each request, compare the retained prefix with its unlimited-capacity prefix. Aggregate both page hit rate and request coverage.

Choose a target from the latency and cost objective. Do not default to 100% or to the largest affordable pool.

Convert the selected page count into per-rank bytes using the exact page length, KV dtype, attention-layer count, KV-head count, and parallel layout.

Add active-request residency, engine overhead, metadata, transfer buffers, and measured reserve. Keep these rows separate from reusable-prefix payload.

Map the result onto HBM, DRAM, and SSD only after measuring each tier's promotion latency and bandwidth under concurrent load.

Finally, rerun the curve after workload, routing, model, or cache-policy changes. Alert when the estimated knee moves rather than when cumulative historical bytes rise.

KV cache working set capacity planning is a target-selection problem before it is a hardware-shopping problem.

Measure reuse distance, decide whose theoretical hits the service must preserve, and buy the smallest tiered capacity that meets that target with verified latency headroom.