KVSET: Der älteste Trick der Cache-Analyse löst gerade das Prefix-Cache-Sizing für LLMs

Ein Paper von Kingsoft Cloud aus dem September 2026 — KVSET — macht eine Aussage, die nach einem neuen Hebel klingt, in Wahrheit aber die Rückkehr eines sehr alten ist: das KV-Cache-Working-Set — die minimale Cache-Kapazität, die eine Ziel-Hit-Rate erreicht — lässt sich online messen, in einem einzigen Durchlauf über den Request-Strom, statt Kapazität für Kapazität zu simulieren¹². Die Maschinerie ist Mattsons Stack-Distanz-Algorithmus, 1970 im IBM Systems Journal zum Sizing virtueller Speicherhierarchien veröffentlicht, plus einem Fenwick-Baum, der die Buchhaltung pro Zugriff billig macht¹³.

Diese Einordnung entscheidet darüber, wie man das Paper liest. Nichts am Kern-Algorithmus ist neu: Stack-Distanz-Analyse ist seit fünf Jahrzehnten das Standardwerkzeug zum Sizing von Cache- und Speicherhierarchien, spätere Arbeiten (Counter Stacks, Cuki) haben ihren Overhead gesenkt — so steht es ungeschönt im Related-Work-Abschnitt des Papers¹. Neu ist das Ziel: Diese exakte, seitengranulare Analyse hatte bisher niemand auf LLM-Prefix-Caches gerichtet und als Open-Source-Online-Analysator ausgeliefert — und das Timing ist kein Zufall. Die Kapazitätsfrage wurde erst bindend, als agentische Workloads die Prefix-Cache-Hit-Rate zum dominierenden Posten auf der Serving-Rechnung machten — genau die Zerlegung in unserem Agenten-Flotten-Kostenguide, die OpenCosts Inference-Cost-Tracking inzwischen pro Modell misst⁴⁵.

Dieser Guide zerlegt, was der Algorithmus tatsächlich tut, führt ihn komplett auf einem toy-agentischen Trace aus — inklusive der klassischen Verifikation (Ein-Pass-Kurve gegen naive Simulation bei jeder Kapazität) —, extrahiert das Working Set und benennt dann die zwei Caveats, zu denen das Paper ehrlich ist, die aber jede Zusammenfassung in Tweet-Länge verliert: Die Zahlen gelten exakt nur unter LRU-Eviction, und der Trace ist nur der Trace von heute.

1. Was das Problem eigentlich ist

Prefix-Caching verwendet die Attention-Key-Value-Zustände eines identischen Präfixes wieder, statt Prefill neu zu rechnen — der Mechanismus aus unserem KV-Cache-Grundlagen-Guide und dem vLLM-vs-SGLang-Vergleich, sowie die Ebene, auf der er lebt, im agentischen Inferenz-KV-Tiering. Agenten-Loops sind der Idealkunde: Jeder Tool-Call sendet die gesamte bisherige Konversation plus genau ein neues Element, deshalb ist der Neu-Lese-Anteil eines langen Agenten-Laufs gewaltig⁵.

Der Durchsatz-Gewinn ist nicht linear. Das KVSET-Paper fasst ihn als Prefill-Durchsatz T = T₀ / (1 − r) mit KV-Cache-Hit-Rate r: Bei r=0,75 läuft Prefill 4x so schnell wie kalt, bei r=0,90 bereits 10x¹. (Die Form selbst nachprüfbar: 1/(1−0,75)=4, 1/(1−0,9)=10 — dieselbe Kostenform fresh_work + re_reads x Rabatt aus dem Flotten-Guide, mit dem Rabatt gegen null.)

Aber Kapazität ist endlich, und jedes gehaltene Token kostet echte Bytes. Die Größenordnung: Ein GQA-Modell der Llama-3.1-70B-Klasse trägt grob 320 KiB BF16/FP16-KV-Zustand pro Token, ein 32K-Token-Request also ~10 GiB, und hundert gleichzeitige Requests nähern sich 1 TiB aggregiertem KV-Zustand⁶ — eine Teilmenge der Working-Set-Rechnung in unserem KV-Cache-Glossar. Der Produktions-Trace des KVSET-Papers selbst — 24.000 Requests aus einem internen Coding-Agenten-Dienst — braucht ~1 TiB Speicher, um die theoretische Hit-Rate von 95 % der Requests zu erhalten, ~5 TiB für 99 %, und bei 99,9 % Coverage konvergiert die Anforderung innerhalb des beobachteten Traces gar nicht¹.

Die Frage ist also nicht „ist ein großer Cache gut", sondern „wie viele GiB kaufen welche Hit-Rate, und wo sterben die Grenzerträge." Per Deployment beantwortet heißt das: physische Cache-Pools in vielen Größen aufstellen. Per klassischer Simulation: den kompletten Trace einmal pro Kandidaten-Kapazität abspielen — Dutzende Replays für eine präzise Antwort, exakt der Overhead, der solche Analysen offline-only macht und den das Papier als Stand der Technik zitiert (kvcache-simulator)¹.

2. Der alte Trick: Stack-Distanz in einem Durchlauf

Hier ist die gesamte klassische Idee, zerlegt auf das, was sie wirklich berechnet.

Halte den LRU-Stack: die aktuell im System befindlichen Seiten, geordnet nach Rezenz des letzten Zugriffs, der jüngste oben. Bei jedem Zugriff auf eine Seite ist ihre Stack-Distanz d ihre Position in genau diesem Stack (1 = zuletzt verwendet) zum Zeitpunkt des Zugriffs. Danach wandert die Seite nach oben.

Der eine Satz, der alles trägt: Ein LRU-Cache der Kapazität C bedient diesen Zugriff exakt dann als Hit, wenn d ≤ C gilt. Eine Distanz, einmal berechnet, entscheidet den Hit/Miss-Ausgang gleichzeitig für jede Kapazität. Einmal über den Trace kehren, eine Distanz pro Zugriff einsammeln — und die ganze Hit-Rate-gegen-Kapazität-Kurve fällt aus einem Histogramm. N Kandidaten-Caches kosten nicht mehr N Simulationen, sondern einen Durchlauf und einen Zähler. Das Working Set für eine Ziel-Hit-Rate ist dann schlicht die kleinste Kapazität, deren kumulierte Hit-Rate das Ziel erreicht.

Auf einen seitengranularen KV-Cache überträgt sich das sauber: Token-Präfix-Wiederverwendung wird in einen Strom von KV-Seiten-Referenzen übersetzt — die Setzung des Papers: LRU-Eviction, Seitengranularität, das, was laut Paper die Mainstream-Engines und KV-Speichersysteme übernehmen¹. Pro Zugriff braucht KVSET die Zahl „wie viele verschiedene Seiten wurden jünger berührt als diese" — der Zähler ist die Tiefe — und ein Fenwick-Baum liefert ihn in O(log n), statt den Stack zu Fuß abzulaufen¹. Das ist die gesamte Modernisierung: Der Algorithmus ist von 1970, die Datenstruktur von 1994, und erst die Kombination macht die Online-Analyse pro Request billig genug für Produktions-Traffic.

Zwei historische Credits, weil sie häufig verstümmelt werden: Die Stack-Distanz-Methode ist Mattson, Gecsei, Slutz und Traiger, 1970, „Evaluation techniques for storage hierarchies", IBM Systems Journal 9(2) — nicht ein Paper von 1981 oder 1983 zum Copy-Back, wie es in den Zusammenfassungen von KVSET herumgeistert³. Die gestraffte LRU-Stack-Processing-Formulierung ist Bennett und Kruskal, 1975⁷.

3. Der Algorithmus, ausgeführt und verifiziert

Alles Folgende ist echtes, lauffähiges Python — die Toy-Version genau dessen, was KVSET tut, minus der Fenwick-Baum-Optimierung. Der Trace imitiert die agentische Form: ein gemeinsames System-Präfix (S0–S2), das in jedem Turn neu gelesen wird, eine wachsende Konversationshistorie (P1, P2, ...) und jeweils eine frische Tool-Ergebnis-Seite (T1, T2, ...), die genau einmal berührt wird. „Seiten" sind die Einheit, die Ihre Hierarchie sieht — KV-Seiten, Cache-Zeilen, Objekte; der Algorithmus ist gleichgültig.

def mattson_hit_rates(trace, max_cap):
    """Mattson-Stack-Durchlauf: EIN Sweep ueber den Trace liefert die
    LRU-Hit-Rate bei JEDER Kapazitaet C. Die Stack-Distanz d eines
    Zugriffs ist seine Position im Rezenz-Stack (1 = am juengsten), unmittelbar vor dem Zugriff.
    Ein Cache der Kapazitaet C hit genau dann, wenn d <= C."""
    stack, dists = [], []
    for x in trace:
        d = stack.index(x) + 1 if x in stack else max_cap + 1  # ueberall Miss
        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: eine separate LRU-Simulation pro Kapazitaet."""
    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-agentischer Trace, 5 Turns. Jeder Turn liest das gemeinsame
# System-Praefix S0..S2 plus die komplette Historie P1..Pk neu, dann
# eine frische Tool-Ergebnis-Seite T_i.
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

Drei Dinge, die dieses Output enthält — es ist das gesamte Argument des Papiers im Miniformat:

• Die Ein-Pass-Kurve ist exakt, nicht approximativ. Jede Kapazitätsspalte des Mattson-Durchlaufs stimmt mit der naiven Simulation auf die letzte Stelle überein — das ist die klassische Verifikation, hier selbst reproduziert (Simulation auf einem Toy-Trace, nicht die Figure-3-Validierung des Papers). Das Gegenstück im Paper: Die vorhergesagten Hit-Raten des einen Durchlaufs stimmen eng mit Messungen an physisch deployten, Mooncake-backed Cache-Pools auf SGLang überein.
• Die Treppe ist die Kostenstruktur. Kapazität 3→4 kauft hier nichts (0,30 → 0,30), weil die wachsenden Historien-Seiten alle eine Distanz von mehr als 4 haben; Kapazität 7→8 kauft +0,14. Die Hit-Rate ist keine glatte Funktion der Kapazität — sie ist eine Treppe, deren Stufen die Wiederverwendungsstruktur des Traces setzt. Genau deshalb ist „nehmen wir mal 75 % an" ein Kategoriefehler: Derselbe Trace, der bei Kapazität 8 auf 0,74 kommt, liefert bei Kapazität 6 nur 0,48.
• Das Working Set ist ein Ziel, keine innere Konstante. „Das" Working Set existiert erst, sobald man die Ziel-Hit-Rate fixiert. Oben gibt 0,70 die Kapazität 8; der Produktions-Trace des Papers gibt ~1 TiB bei 95 % und ~5 TiB bei 99 % Request-Coverage¹. Ziel ändern, Antwort ändern — genau der explizite Performance-Kosten-Trade-Off, den das Werkzeug sichtbar machen soll, statt ihn im „Provisionieren wir eben großzügig"-Reflex zu verstecken.

Und die Form-Warnung des Toys: Das Toy-Working-Set (8) bleibt unter der Zahl der jemals berührten Seiten (13), und in einem echten Trace sinkt der Anteil der Seiten, die je wieder treffen, mit wachsender Trace-Länge — die Nicht-Konvergenz bei 99,9 % Coverage im Papier ist das, was eine Coverage-Frontier aussieht, wenn man sich weigert, auch den einmal berührten Schwanz zu evicten¹.

4. Die Caveats, so wie das Paper sie nennt

Die Autoren sind ungewöhnlich direkt bei den Grenzen — ehrt sie im Wortlaut, statt sie zu umkurven:

LRU-exakt, kein Sizing-Orakel. Der Ein-Pass-Satz gilt für LRU-Eviction, Punkt — das Paper sagt ausdrücklich „KVSET currently applies only to caches that use LRU eviction" und markiert alles darüber als Future Work¹. Der einzige Grund, warum das praktisch akzeptabel ist: vLLM, Mooncake und die Mainstream-KV-Speichersysteme verwenden laut Paper tatsächlich LRU¹. Aber genau deshalb ist die Ausgabe so zu lesen, wenn Policies besser evicten als pures LRU: Garantiert ist, dass ein unter LRU verwalteter Pool exakt die gemeldete Kapazität braucht; jede Engine mit Voraussicht — SGLang-artiges Radix-Scheduling, prefix-aware Eviction, UNISON-Klasse-Scheduler Richtung Bélády MIN — kann dieselbe Hit-Rate im Prinzip mit weniger halten, indem sie nie wiederverwendete Seiten früher rausschmeißt, als LRU es täte. Gegenüber einer solchen Policy ist die gemeldete Kapazität folglich eine Obergrenze dessen, was sie braucht, und die Hit-Rate-Kurve eine Untergrenze dessen, was sie erreicht — ein Budget-Geländer, kein Boden.

Der Trace ist der Trace von heute. Ein Working Set aus dem Coding-Agenten-Traffic dieses Monats ist eine Aussage über die Wiederverwendungsstruktur dieses Monats. Die Figure 4 des Papers zeigt die Anforderung mitwachsend mit der Request-Zahl — und einbrechend, als die Zahl aktiver Nutzer um Request 21.000 sinkt¹: Kapazitätsbedarf ist eine beobachtete Eigenschaft der aktuellen Form der Workload, keine Naturkonstante. Agenten-Harnesses ändern ihre Compaction-Policy, ihre Step-Budgets, ihre Tool-Breite — wenn langsam keine alten Präfixe mehr wiederkehren, ist das Working-Set von gestern Stroh. Genau die Flotten, für die diese Messung gedacht ist, sind die Flotten, deren Verhalten sich unter ihnen verschiebt — derselbe Grund, warum der Flotten-Guide jede Optimierung hinter gemessenen statt angenommenen Hit-Raten gattert⁵. Online-Analyse, die mitlaufend neu rechnet, ist die ehrliche Halbe Antwort; das Werkzeug kann sie, also betreiben Sie es online statt als einmalige Sizing-Zahl¹.

Nur Full Attention. KVSET misst derzeit die Full-Attention-Komponente eines Modells; bei hybriden Architekturen (lineare Attention, Sliding Windows, Mamba-Zustände) empfehlen die Autoren, den Bedarf der Full-Attention-Layer separat zu schätzen und zusätzliche Reserve nach modellspezifischem Verhältnis zu planen¹. Ein hybrides Modell lässt sich nicht mit einer einzigen Zahl dieses Werkzeugs dimensionieren.

5. Warum jetzt: der Engpass wurde echt

Die Werkzeug-Welle rund um KV-Messung im zweiten Halbjahr 2026 ist Produktankündigung, kein akademischer Zufall:

• OpenCost 1.121.0 (am 5. August 2026 im CNCF-Blog angekündigt) brachte erstmaliges Kubernetes-Inference-Cost-Tracking, demonstriert auf einem Proof-of-Concept-Cluster mit 109 GPUs und 30 deployten Modellen: Es verarbeitet vLLMs Token-Durchsatz- und Bearbeitungszeit-Metriken, trennt Allocation-basierte von Usage-basierten Kosten pro Modell, rechnet Cache-Hit-Ersparnisse in Usage-basierte Per-Token-Kosten ein und veröffentlicht alles als Prometheus-Metrike plus REST-API⁴.
• Das KV-Management-Survey (arXiv:2607.02574) auditiert aktuelle KV-Evaluierungen und benennt sieben fehlende KV-spezifische Messungen — Working-Set-Sizing ist exakt die Art von Messung, die es einfordert — und das ist präzise die Lücke, die KVSET füllt⁶.
• KVSET ist nach Kenntnis der Autoren der erste Open-Source-Online-Kapazitätsanalysator, und der Code unterstützt sowohl Online-Request-Verarbeitung als auch Offline-Trace-Replay¹².

Zusammengenommen: Kosten werden inzwischen pro Cache-Hit-Posten gemessen, die Hit-Rate-gegen-Kapazität-Kurve gilt als fehlendes Primitiv — und der klassische Algorithmus, der sie misst, lag bereits seit 1970 in der Literatur³ und musste nur auf das neue Objekt gerichtet werden.

6. Fazit

KVSET verdient seinen Platz nicht durch Neuheit, sondern durch Ehrlichkeit: Es nimmt ein 56 Jahre altes Messwerkzeug, portiert es auf das Objekt, das inzwischen der bindende Engpass der Serving-Kosten ist, validiert es gegen physische Deployments und veröffentlicht den Open-Source-Analysator¹². Es ist ein Messwerkzeug für Kapazität gegen Hit-Rate mit einer prüfbaren Aussage, kein weiterer Benchmark-Zirkus. Innerhalb seiner selbst genannten Grenzen — nur LRU, nur Full Attention, nur der Trace von heute, keine Konvergenz-Garantie bei extremer Coverage — schließt es exakt die Lücke, die unser Flotten-Kostenguide markiert hat: Die Hit-Rate h im Kostenmultiplikator 1 − 0,9 x h ist keine Schätzung mehr, sondern eine pro Workload und pro Ziel messbare Größe⁵.

Der Misserfolgsmodus lauert nicht im Werkzeug, sondern drumherum: das Working-Set ohne Zielgröße zu zitieren („das Working Set ist 1 TiB" ist ohne „bei 95 % Coverage" bedeutungslos), die Zahl auf eine Nicht-LRU-Engine zu portieren oder sie nach einem Kalibrationstag einzufrieren. Als exakte LRU-Anforderung aus einer laufenden Messschleife gelesen — eine Obergrenze unter Policies, die besser evicten als LRU — ist es die fehlende Hälfte der Cache-Hit-Rate-Elastizität.

Fußnoten