KVSET: LRU-Stack-Distanzen für das Sizing von LLM-Prefix-Caches

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: Die Autoren berichten den ersten Open-Source-Online-Analysator für dieses seitengranulare LLM-Prefix-Cache-Problem — und das Timing ist kein Zufall. Agentische Workloads mit wiederholten Präfixen machen die Kapazitätsplanung relevant; OpenCost verfolgt zudem Inferenzkosten pro Modell und berücksichtigt Cache-Hit-Ersparnisse⁴.

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. Ohne Speicherzugriffskosten modelliert das KVSET-Paper den Prefill-Durchsatz als T = T₀ / (1 − r) mit KV-Cache-Hit-Rate r: Die idealisierte Formel ergibt 4x bei r=0,75 und 10x bei r=0,90, wenn Speicherzugriffskosten vernachlässigbar sind¹. Der tatsächliche Durchsatz muss gemessen werden. (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. Im 24.000-Request-Trace des KVSET-Papers erhalten ~1 TiB die theoretische Hit-Rate jedes einzelnen Requests für 95 % der Requests, ~5 TiB für 99 %; diese Prozentsätze bezeichnen Request-Coverage und keine globale Token-Hit-Rate, 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: Der Toy-Trace liefert bei Kapazität 8 eine Hit-Rate von 0,74 und bei Kapazität 6 von 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¹. Das ist ein anderes Ziel als die globale Seiten-Hit-Rate im Toy: Coverage ist der Anteil der Requests, deren jeweils theoretische Hit-Rate erhalten bleibt. 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.

Das Toy-Working-Set (8) bleibt unter der Zahl der jemals berührten Seiten (13). Im separaten 24.000-Request-Trace des Papers konvergierte die benötigte Kapazität für 99,9 % Request-Coverage innerhalb des Beobachtungsfensters nicht¹. Daraus folgt nicht, dass einmalig berührte Seiten die Ursache sind.

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¹. Für eine Nicht-LRU-Policy ist die LRU-Kurve eine Vergleichsbasis, keine garantierte Ober- oder Untergrenze. Eine Policy kann LRU auf einem Trace übertreffen und auf einem anderen unterliegen; für das Sizing muss der Trace unter der tatsächlich eingesetzten Policy getestet werden.

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 LRU-Anforderung für den beobachteten Trace und die genannte Ziel-Hit-Rate beziehungsweise Request-Coverage gelesen, liefert es eine belastbare Basis; andere Eviction-Policies und künftige Workloads müssen gesondert geprüft werden.

Fußnoten