KVSET: The Oldest Trick in Cache Analysis Just Solved LLM Prefix-Cache Sizing

A September 2026 paper from Kingsoft Cloud, KVSET, makes a claim that sounds like a new lever but is really the return of a very old one: the KV-cache working set — the minimum cache capacity that achieves a target hit rate — can be measured online, from a single pass over the request stream, instead of simulated capacity-by-capacity¹². The machinery is Mattson's stack-distance algorithm, published in 1970 in the IBM Systems Journal for sizing virtual-memory hierarchies, plus a Fenwick tree to make the per-access bookkeeping cheap¹³.

That framing matters for how you read the paper. Nothing in the core algorithm is new: stack-distance analysis has been the standard tool for cache- and memory-hierarchy sizing for five decades, with later work (Counter Stacks, Cuki) reducing its overhead, as the paper's own related-work section states plainly¹. What is new is the target: nobody had pointed this exact, page-granular analysis at LLM prefix caches and shipped an open-source online analyzer for it — and the timing is not accidental. The capacity question became binding only when agentic workloads turned prefix-cache hit rate into the dominant term on the serving bill, as our agent-fleet cost guide decomposed and OpenCost's inference-cost tracking now measures per model⁴⁵.

This guide decomposes what the algorithm actually does, runs it end to end on a toy agentic trace with the classic verification (one-pass curve vs naive simulation at every capacity), extracts the working set, and then states the two caveats the paper is honest about but a Twitter-length summary will lose: the numbers are exact only under LRU eviction, and the trace is only today's trace.

1. What the problem actually is

Prefix caching reuses the attention key-value states of an identical prefix instead of recomputing prefill — the mechanism in our KV cache explained and vLLM vs SGLang comparisons, and the tier it lives on in agentic inference KV tiering. Agent loops are the ideal customer: every tool call re-sends the entire conversation so far plus one new item, so the re-read fraction of a long agent run is enormous⁵.

The throughput payoff is not linear. The KVSET paper renders it as prefill throughput T = T₀ / (1 − r), where r is the KV-cache hit rate: at r=0.75 prefill runs 4× faster than cold, at r=0.90 already 10×¹. (Check the shape yourself: 1/(1−0.75)=4, 1/(1−0.9)=10 — the generic cost form fresh_work + re_reads × discount from the fleet guide, with the discount going to zero.)

But capacity is finite, and every retained token costs real bytes. The scale: a Llama-3.1-70B-class GQA model carries roughly 320 KiB of BF16/FP16 KV state per token, so one 32K-token request is ~10 GiB, and one hundred concurrent requests approach 1 TiB of aggregate KV state⁶ — a subset of the working-set accounting in our KV cache glossary. The KVSET paper's own 24,000-request production coding-agent trace needs ~1 TiB of storage to preserve the theoretical hit rate of 95% of requests, ~5 TiB for 99%, and at 99.9% coverage the requirement does not converge at all within the observed trace¹.

So the question is not "is a big cache good" — it is "how many GiB buy which hit rate, and where do the marginal returns die." Answering that by deployment means standing up physical cache pools at many sizes. Answering it by conventional simulation means replaying the whole trace once per candidate capacity — dozens of replays for a precise answer, which is exactly the overhead that makes the analysis offline-only¹. The paper cites kvcache-simulator as the existing tool in exactly this simulate-per-budget shape¹.

2. The old trick: stack distance in one pass

Here is the entire classical idea, decomposed to what it actually computes.

Maintain the LRU stack: the pages currently in the system, ordered by recency of last access, most recent on top. On every access to a page, its stack distance d is its position in that stack (1 = most recently used) at the moment of the access. Then push the page to the top.

The single theorem that makes everything work: an LRU cache of capacity C serves that access as a hit exactly when d ≤ C. One distance, computed once, decides the hit/miss outcome simultaneously for every capacity. Sweep the trace once, collect one distance per access, and the hit-rate-vs-capacity curve for the entire capacity axis falls out of a histogram. N candidate caches no longer cost N simulations; they cost one pass and a counter. The working set for a target hit rate is then just the smallest capacity whose cumulative hit rate clears the target.

For a page-granular KV cache this maps cleanly: convert token-prefix reuse into a stream of KV page references (the paper's setting — LRU eviction, page granularity, which it notes is what mainstream engines and KV-storage systems adopt)¹. For each access, KVSET needs "how many distinct pages were touched more recently than this one" — that count is the depth — and a Fenwick tree computes it in O(log n) instead of walking the stack¹. That is the whole modernization: the algorithm is 1970, the data structure 1994, and the combination is what makes online, per-request analysis cheap enough to run alongside production traffic.

Two historical credits, because they are frequently mangled: the stack-distance method is Mattson, Gecsei, Slutz and Traiger, 1970, "Evaluation techniques for storage hierarchies," IBM Systems Journal 9(2) — not a 1981 or 1983 copy-back paper, which is the citation drifting around social-media summaries of KVSET³. The streamlined LRU-stack-processing formulation is Bennett and Kruskal, 1975⁷.

3. The algorithm, run and verified

Everything below is real, runnable Python — the toy version of exactly what KVSET does, minus the Fenwick-tree optimization. The trace mimics the agentic shape: a shared system prefix (S0–S2) re-read every turn, a growing conversation history (P1, P2, ...), and one fresh tool-result page (T1, T2, ...) that is touched once and never reused. Pages are the unit your hierarchy sizes — KV pages, cache lines, objects; the algorithm does not care.

def mattson_hit_rates(trace, max_cap):
    """Mattson-stack pass: ONE sweep over the trace yields the LRU hit
    rate at EVERY capacity C. The stack distance d of an access is its
    position in the recency stack (1 = most recent) just before the
    access; a capacity-C cache hits exactly when d <= C."""
    stack, dists = [], []
    for x in trace:
        d = stack.index(x) + 1 if x in stack else max_cap + 1  # miss everywhere
        if x in stack:
            stack.remove(x)
        stack.insert(0, x)
        dists.append(d)
    return {C: sum(1 for d in dists if d <= C) / len(trace)
            for C in range(1, max_cap + 1)}
 
def naive_hit_rate(trace, cap):
    """Baseline: a separate LRU simulation per capacity."""
    cache, hits = [], 0
    for x in trace:
        if x in cache:
            hits += 1
            cache.remove(x); cache.insert(0, x)
        else:
            cache.insert(0, x)
            if len(cache) > cap:
                cache.pop()
    return hits / len(trace)
 
def working_set(curve, target):
    for C, h in curve.items():
        if h >= target:
            return C
    return None
 
# Toy agentic-loop trace, 5 turns. Each turn re-reads the shared system
# prefix S0..S2 plus the whole conversation history P1..Pk, then touches
# one fresh tool-result page T_i. Pages are the unit the hierarchy sizes:
# KV pages, cache lines, whatever.
trace, history = [], []
for i in range(1, 6):
    history += ['S0', 'S1', 'S2', 'P1'] if i == 1 else [f'P{i}']
    trace += ['S0', 'S1', 'S2'] + history + [f'T{i}']
# -> S0 S1 S2 S0 S1 S2 P1 T1  S0 S1 S2 S0 S1 S2 P1 P2 T2 ...
 
target = 0.70
curve = mattson_hit_rates(trace, 8)
print('capacity  Mattson  naive   identical')
identical = True
for C in range(1, 9):
    n = naive_hit_rate(trace, C)
    same = abs(n - curve[C]) < 1e-12
    identical &= same
    print(f'{C}         {curve[C]:.2f}    {n:.2f}    {same}')
print(f'curves identical at every capacity: {identical}')
# capacity  Mattson  naive   identical
# 1         0.00    0.00    True
# 2         0.00    0.00    True
# 3         0.30    0.30    True
# 4         0.30    0.30    True
# 5         0.38    0.38    True
# 6         0.48    0.48    True
# 7         0.60    0.60    True
# 8         0.74    0.74    True
# curves identical at every capacity: True
 
ws = working_set(curve, target)
print(f'min capacity for hit rate >= {target}: {ws}')
# min capacity for hit rate >= 0.7: 8

Three things to read off this output, because they are the paper's entire argument in miniature:

• The one-pass curve is exact, not approximate. Every capacity column from the Mattson pass matches the naive simulation to the last digit — that is the classic verification, and here it is reproduced (by us, on a toy trace; you are reading simulation output, not the paper's Figure 3). The paper's corresponding evidence is production validation: predicted hit rates from its single pass closely match measurements from physically deployed Mooncake-backed cache pools on SGLang¹.
• The staircase is the cost structure. Capacity 3→4 buys nothing here (0.30 → 0.30) because the growing history pages all have distance > 4; capacity 7→8 buys +0.14. The hit rate is not a smooth function of capacity — it is a staircase whose steps are set by the trace's reuse structure. This is why "assume 75%" is a category error: the same trace that yields 0.74 at capacity 8 yields 0.48 at capacity 6.
• The working set is a target, not an intrinsic number. "The" working set only exists once you fix the hit-rate target. One target above, 0.70, gives 8; the paper's production trace gives ~1 TiB at 95% request coverage and ~5 TiB at 99%¹. Change the target, change the answer — which is precisely the explicit performance-cost trade-off the tool is supposed to surface instead of hiding inside a "just over-provision" reflex.

And the toy's shape warning: the toy working set (8) is smaller than the total unique pages ever touched (13), and in a real trace the fraction of pages that ever hit again goes down as the trace grows — the paper's non-convergence at 99.9% coverage is what a coverage-frontier looks like when you refuse to evict even the once-touched tail¹.

4. The caveats, stated the way the paper states them

The authors are unusually direct about the limits, so honor them verbatim rather than routing around them:

LRU-exact, not a sizing oracle. The one-pass theorem holds for LRU eviction, full stop — the paper says "KVSET currently applies only to caches that use LRU eviction" and flags anything beyond as future work¹. The only reason this is acceptable in practice is that vLLM, Mooncake and the mainstream KV-storage systems do use LRU, per the paper¹. But that is exactly how the output reads under policies that evict better than pure LRU: what you are guaranteed is that an LRU-managed pool needs exactly the reported capacity, and any engine with foresight — SGLang-style radix scheduling, prefix-aware eviction, UNISON-class schedulers chasing Bélády MIN — can in principle hold the same hit rate in less, by evicting never-reused pages earlier than LRU would. Against such a policy the reported capacity is therefore an upper bound on what it needs, and the hit-rate curve a lower bound on what it achieves — a budget guard rail, not a floor.

The trace is today's trace. A working set extracted from this month's coding-agent traffic is a statement about this month's reuse structure. The paper's own Figure 4 shows the requirement evolving with request count, and sagging when concurrency drops around request 21,000¹ — capacity demand is an observed property of the workload's current shape, not a constant of nature. Agent harnesses change their compaction policy, max-steps, tool breadth; slowly none of the old prefixes repeat and yesterday's working set is stale⁵. The fleets that this measure is for are exactly the fleets whose behavior shifts under them — the same reason the fleet guide gates every optimization behind measured hit rates rather than assumptions. Online analysis, that re-runs as the stream grows, is the honest half-answer; the tool supports it, so use it online rather than as a one-time sizing number¹.

Full attention only. KVSET currently measures the full-attention component of a model; for hybrid architectures (linear attention, sliding windows, Mamba states) the authors recommend estimating the full-attention layers' requirement separately and reserving additional memory by model-specific ratio¹. A hybrid model, or a per-layer-KV-dtype configuration, cannot be sized by one number from this tool.

5. Why now: the constraint got real

The tool wave around KV measurement in the second half of 2026 is a product announcement, not an academic coincidence:

• OpenCost 1.121.0 (announced August 5, 2026 on the CNCF blog) added first-of-a-kind Kubernetes inference cost tracking, demonstrated on a proof-of-concept cluster of 109 GPUs and 30 deployed models: it consumes vLLM's token-throughput and processing-time metrics, splits allocation-based from usage-based cost per model, prices cache-hit savings into usage-based per-token costs, and publishes everything as Prometheus metrics plus REST API⁴.
• The KV-management survey (arXiv:2607.02574) audits current KV evaluations and names seven missing KV-specific measurements — working-set sizing is exactly the kind of measurement it calls for — which is the precise gap KVSET fills⁶.
• KVSET itself is the first open-source online capacity analyzer the authors are aware of, and the code supports both online request processing and offline trace replay¹².

Put together: costs are now measured per cache-hit line item, the hit-rate-vs-capacity curve is identified as a missing primitive, and the classical algorithm that measures it was already sitting in the 1970 literature³ — needing only to be pointed at the new object.

6. Verdict

KVSET earns its place not by novelty but by honesty: it takes a 56-year-old measurement tool, ports it to the object that is now the binding constraint in serving cost, validates it against physical deployments, and publishes the open-source analyzer¹². It is a capacity-vs-hit-rate measurement tool with a checkable claim, not another benchmark entry. Under its own stated bounds — LRU only, full attention only, today's trace only, and no convergence guarantee at extreme coverage — it closes exactly the gap our fleet-cost guide flagged: the hit rate h in the cost multiplier 1 − 0.9 × h stops being a guess and becomes a number you can measure per workload, per target⁵.

The failure mode to watch for is not in the tool but around it: quoting the working-set number without its target ("the working set is 1 TiB" is meaningless without "at 95% coverage"), or porting it to a non-LRU engine, or freezing it after one calibration day. Treat it as the exact LRU requirement from a live measurement loop — an upper bound under policies that evict better than LRU — and it is the missing half of cache-hit-rate elasticity.

Footnotes