Prefix-Eviction: Warum LRU für LLM-Prefix-Caching bereits beinahe optimal ist

Ein Papier von September 2026 liefert eines der gesündesten negativen Ergebnisse, die Systemforschung hervorbringt: vier Jahrzehnte Cache-Replacement-Raffinesse, ehrlich auf Produktions-Traces des LLM-Serving gemessen, bewegen die Nadel kaum über Least Recently Used hinaus¹. When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse (Liu, Yu und Yang, Harvard University, arXiv:2609.28870, cs.DC, eingereicht am 24. September 2026) untersucht Produktions-Traces aus zwei öffentlichen LLM-Inferenzdiensten — einer dominiert von agentischem Traffic, einer mit breiterer Mischung — und evaluiert 14 Eviction-Algorithmen sowohl im HBM-beschränkten (24–120 GiB pro Beschleuniger) als auch im großen Memory-Pool-Regime (0,25–12 TiB). Das Ergebnis: Trotz einer großen verbleibenden Lücke zum Offline-Optimum von Belady verbessert keiner der State-of-the-Art-Algorithmen LRU bei irgendeiner gemessenen Kapazität, und frequenzbasierte Policys helfen nicht nur nicht — sie kollabieren¹. Die Offline-Decke, die hier „Spielraum" definiert, ist Beladys Optimum von 1966, erreichbar nur durch einen Algorithmus, der die Zukunft bereits gesehen hat².

Die Erklärung ist strukturell, nicht zufällig. Prefix-Cache-Reuse wird vom regelmäßigen Takt aktiver Sitzungen dominiert: Eine Konversation oder Agent-Schleife sendet ihren angesammelten Kontext Runde um Runde erneut, in stabilem Sitzungstakt. Das macht Rezenz ungewöhnlich prädiktiv — genau die Signalklasse, die der moderne Algorithmus-Zoo (Frequenz-Skizzen, angepasste analytische Modelle, gelernte Ranker) überwinden sollte. Die Workload-Klasse, gegen die diese raffinierten rezenz-agnostischen Policys entworfen wurden — langlebige Objekte aus persistenten globalen Pools mit popularitätskorrelierten Ankunftsabständen — existiert im Prefix-Serving praktisch nicht¹.

Aber das Papier ist keine Werbung für Selbstzufriedenheit. Prefix-Caching führt echte neue harte Teile ein, die die Hit-Ratio nicht sieht: Miss-Kosten, die mit der Token-Tiefe wachsen (weil Attention gegen einen langen gecachten Kontext echte FLOPs kostet), und Sitzungs-Footprints, die so schwer-tailing sind, dass die obersten 10 % der Sitzungen 76,2 % aller KV-Bytes horten¹. Für diese konstruieren die Autoren eine Compute-Savings-Ratio, zwei Offline-Oracles (ein exaktes ILP-Optimum und eine effiziente Approximation namens BeladyCompute) und vier chirurgische Fixes, die auf Rezenz aufsetzen, statt sie zu ersetzen¹.

Dieser Guide reproduziert das Kernergebnis in einer lauffähigen sitzungsgetakteten Simulation, rechnet die Compute-Savings-Arithmetik nach, wo Misses aufhören uniform zu sein, zeigt, warum Oracle-Spielraum groß und gleichzeitig nicht realisierbar sein kann, und beziffert dann die ehrlichen Grenzen — denn ein so sauberes negatives Ergebnis lädt genau zur Überverallgemeinerung ein, gegen die es argumentiert.

1. Das Setup: zwei Organisationen, vierzehn Algorithmen, ein langweiliger Gewinner

Die Produktionsdaten¹:

• FreeInference-Trace — stark agentisch, 327,5 K Requests über 7,0 Tage, davon 34,3 % in Multi-Turn-Sitzungen, 10,5 B verarbeitete Token, 0,63 B einzigartige, durchschnittlich 32,0 K Token pro Request.
• Chutes-Trace — eine breitere Mischung aus menschlichen Multi-Turn-Konversationen, agentischen Sitzungen und Einzelschuss-API-Calls, 515,8 K Requests über 130,9 Tage, 26,1 % Multi-Turn, 9,7 B verarbeitete Token, 2,23 B einzigartige, durchschnittlich 18,7 K Token pro Request.

Die gesamte Evaluation nutzt eine 16-Token-Blockgranularität und den Qwen3-Coder-30B-Tokenizer, gekappt an dessen 256K-Token-Kontextfenster (4,3 % der Requests im FreeInference-Trace übersprungen, 0,03 % im Chutes-Trace). Der Replay läuft auf einem eigenen C++-Simulator auf Basis von libCacheSim, der die Residency-Beschränkungen realer Engines abbildet — der Prefix eines eingehenden Requests wird erst zugelassen, wenn Platz für ihn existiert — und die Hit-Ratios von nativem vLLM eng trifft, bei bis zu 160-facher Evaluationsgeschwindigkeit¹.

Das Papier untersucht beide Deploymente-Formen des modernen Prefix-Caching³ — per-Replica-HBM und den disaggregierten Memory-Pool. Die vierzehn Online-Algorithmen, gruppiert nach Designprinzip¹:

• Rezenz (Baseline): LRU.
• Quick Demotion: ARC, Sieve, S3-FIFO, S4-FIFO, LIRS.
• Analytische Modellierung: LHD.
• Frequenz: LFU, W-TinyLFU.
• Gelernt: LeCaR, LRB, 3LCache.
• Prefix-spezifisch: Workload-aware, AsymCache.

Dazu Beladys Optimum als Offline-Decke. Das Ergebnis sind drei Verhaltensgruppen. Erstens: die große Mehrheit — ARC, LHD, LeCaR, 3LCache, LRB, Workload-aware, AsymCache — performt sehr ähnlich zu oder leicht schlechter als LRU: raffinierte Designs, die schlicht die Basislinie reproduzieren. Zweitens: die Quick-Demotion-Familie (S3-FIFO, S4-FIFO, Sieve, LIRS) ist hochgradig trace-abhängig: marginale Gewinne auf manchen Workloads, Regressionen um mehrere Punkte auf anderen. Drittens: LFU und W-TinyLFU kollabieren vollständig und hinken weit hinterher¹. Derweil thront Beladys Oracle weit über dem besten Online-Algorithmus: Es gibt echten Spielraum, und kein aktuelles „fancy" Mechanismus erreicht ihn.

Das Papier erweitert den Vergleich auf sechs externe Workloads — vier Qwen-Bailian-Traces plus AgentX — und die Rezenz-Schlussfolgerung bleibt stabil; nur die Kapazität, bei der LRU gleichzieht, ist workload-abhängig. Auf Qwen To-B erreichen S3-FIFO und ARC z. B. 0,491 bei 24 GiB gegen LRU's 0,403, aber LRU zieht bis 1 TiB auf jedem Trace gleich, innerhalb von 0,4 Punkten des besten Online-Algorithmus¹.

2. Warum Rezenz gewinnt: Sitzungstakt

Die Workload-Charakterisierung des Papiers ist der intellektuelle Kern. Prefix-Blöcke sind keine Objekte aus einem persistenten Pool; sie akkumulieren sich dynamisch durch Konversationen und Tool-Ausführungen, und das ändert alles. Fünf gemessene Eigenschaften auf dem FreeInference-Trace¹:

• Lebensdauer ist kurz und sitzungsbeschränkt. One-Hit-Objekte machen 53,0 %–55,7 % der Blöcke in allen drei verglichenen Workloads aus (Prefix-Cache, Web, Block). Multi-Turn-Sitzungen sind kurzlebig — Median 55 s, 90. Perzentil 14 Minuten, 99. Perzentil rund 4 Stunden. Der Cache hat keinen persistenten Kern: Benachbarte Zeitfenster teilen über 30 % ihrer Objekte, aber die Überschneidung zerfällt gegen null jenseits eines Zwei-Stunden-Abstands.
• Reuse-Intervalle sind kurz mit niedriger Varianz. Der mediane Intra-Sitzungs-Abstand beträgt 8,2 s, und 99,7 % aller Lücken fallen unter ein 22-Minuten-Reuse-Fenster. Die Enden existieren (99. Perzentil 1.000 s für System-Prompts, 562 s für Multi-Turn-History, im Extremfall Tage), aber die überwältigende Masse des Reuse ist unmittelbar.
• Frequenz verfolgt Sitzungsfortschritt, nicht Popularität. Multi-Turn-Blöcke stellen 37,6 % der distincten Blöcke, generieren aber 70,2 % aller Zugriffe; Single-Turn-Prompts sind 57,8 % der einzigartigen Blöcke, aber nur 11,4 % der Zugriffe, wobei 84,9 % nie wieder berührt werden. Entscheidend: Das Reuse-Intervall ist flach über alle Frequenz-Bins — Zugriffe kommen im stabilen, sequenziellen Takt ihrer Sitzung an, sodass akkumulierte Frequenz fast nichts über den Zeitpunkt des nächsten Zugriffs aussagt.
• Miss-Kosten sind positionsabhängig. Zwei Requests, die beide 8K Token berechnen: Der zweite muss zusätzlich gegen 64 K gecachte Token davor attendieren; das gemessene TTFT steigt von 166 ms auf 966 ms und der Rechenaufwand von 71,1 auf 493,3 TFLOP.
• Sitzungs-Footprints sind schwer-tailing. Die obersten 10 % der Sitzungen halten 76,2 % aller KV-Bytes; die obersten 1 % allein 20,3 %.

Rezenz gewinnt nicht, weil LRU clever wäre, sondern weil der Workload ihm die Antwort direkt übergibt: Innerhalb einer Sitzung kommt der nächste Zugriff auf einen Block direkt nach dem letzten; über Sitzungen hinweg geben tote Sitzungen ihre Blöcke frei und verteidigen sie nicht mehr. Frequenz trägt ein verführerisches Signal — hohe Zähler markieren aktive Sitzungen —, aber diese Aktivität ist in Rezenz bereits sichtbar, weshalb Frequenz-basiertes Ranking scheitert, während Frequenz als Zulassungsfilter dennoch helfen kann (Abschnitt 6)¹.

3. Zelle 1: Das Ergebnis in sechzig Zeilen

Die Simulation unten baut die strukturelle Situation von null auf: 150 Sitzungen, die jeweils ihren wachsenden Prefix in regelmäßigem Sitzungstakt erneut senden, plus geteilte System-Prompt-Blöcke. Sie replays denselben Zugriffsstrom durch LRU, pures LFU (die quintessentielle rezenz-agnostische Policy) und Beladys Optimum. Weil der Reuse des Workloads durch Sitzungstakt konzentriert ist, gewinnt LRU dort, wo das Frequenz-Oracle nicht mithalten kann, bei jeder gemessenen Kapazität (nur Standardbibliothek, Seed fixiert):

import random
from collections import OrderedDict, defaultdict
import heapq
 
random.seed(20260925)
 
# Session-paced prefix-reuse workload:
#   * a small set of shared system-prompt blocks (hit by every request)
#   * N sessions whose turns arrive at a REGULAR per-session pace
#   * each turn re-touches the whole accumulated prefix and appends new blocks
S_SYS = 30                            # shared system-prompt blocks
accesses = []                         # (time, block_id)
 
for s in range(150):
    sess = 1000 + s
    pacing = random.uniform(6.0, 12.0)          # regular turn gap (seconds)
    onehit = random.random() < 0.45             # single-turn session
    turns = 1 if onehit else min(2 + int(random.expovariate(1/6)), 30)
    t0 = random.uniform(0, 3600)
    grow = random.choice([24, 32, 40])           # new blocks per turn
    for turn in range(1, turns + 1):
        t = t0 + turn * pacing + random.gauss(0, pacing * 0.05)
        depth = S_SYS + turn * grow             # prefix length at this turn
        for b in range(depth):
            accesses.append((t, b if b < S_SYS else sess * 100000 + (b - S_SYS)))
accesses.sort(key=lambda a: a[0])
print("accesses:", len(accesses))
 
def replay_lru(cap):
    cache = OrderedDict(); hits = total = 0
    for t, b in accesses:
        total += 1
        if b in cache:
            hits += 1; cache.move_to_end(b)
        else:
            if len(cache) >= cap:
                cache.popitem(last=False)       # evict least recently used
            cache[b] = t
    return hits / total
 
def replay_lfu(cap):
    # pure LFU with lazy min-heap: evict the least frequently used block
    cnt = {}; heap = []; seq = 0; hits = total = 0
    for t, b in accesses:
        total += 1
        if b in cnt:
            hits += 1; cnt[b] += 1; seq += 1
            heapq.heappush(heap, (cnt[b], seq, b))
        else:
            if len(cnt) >= cap:
                while heap:                      # skip stale heap entries
                    c, _, v = heapq.heappop(heap)
                    if v in cnt and cnt[v] == c:
                        del cnt[v]; break
            cnt[b] = 1; seq += 1
            heapq.heappush(heap, (1, seq, b))
    return hits / total
 
def replay_belady(cap):
    # offline optimum: evict the block whose NEXT access is farthest away
    fut = defaultdict(list)
    for i, (t, b) in enumerate(accesses):
        fut[b].append(i)
    ptr = defaultdict(int)                       # accesses seen per block
    cache = set(); heap = []; hits = total = 0
    INF = 10**9
    for i, (t, b) in enumerate(accesses):
        total += 1
        if b in cache:
            hits += 1
        else:
            if len(cache) >= cap:
                while heap:                      # max-heap (negated key)
                    nkey, pid, v = heapq.heappop(heap)
                    if v in cache and pid == ptr[v]:
                        cache.remove(v); break
            cache.add(b)
        ptr[b] += 1
        na = fut[b][ptr[b]] if ptr[b] < len(fut[b]) else INF
        heapq.heappush(heap, (-na, ptr[b], b))
    return hits / total
 
print()
print("capacity |   LRU     LFU   BELADY")
for cap in (600, 1500, 6000):
    print(f"{cap:8d} | {replay_lru(cap):.3f}  {replay_lfu(cap):.3f}  {replay_belady(cap):.3f}")

Ausgabe eines echten Laufs (Python 3, Seed 20260925):

accesses: 129708
 
capacity |   LRU     LFU   BELADY
     600 | 0.576  0.164  0.754
    1500 | 0.827  0.195  0.844
    6000 | 0.845  0.369  0.845

Jede Signatur von Figur 2 des Papiers reproduziert sich. LFU — die Policy-Familie, die die traditionelle Cache-Literatur als die ehrliche Alternative zu LRU behandelt — wird nicht nur geschlagen, sie kollabiert (0,164–0,369 gegen LRU's 0,576–0,845), weil sie one-hit-lastige und tote Frequenz-Blöcke resident hält, während sie genau die kürzlich berührten Blöcke getakteter Sitzungen evicted, die gleich zurückkommen werden. LRU folgt der Offline-Decke eng, und bei 6.000 Blöcken Kapazität hat sich die Lücke zu Belady auf 0,000 geschlossen — das Papier misst dieselbe Konvergenz, mit LRU innerhalb von 0,4 Punkten des besten Online-Algorithmus bis 1 TiB auf jedem Trace. Beachte auch: Die Form der LRU-Belady-Lücke entspricht den Traces — am breitesten, wo die Kapazität knapp ist, strukturell schrumpfend, je mehr der Working Set hineinpasst.

Dieses Spielzeug lässt echte Komplikationen bewusst weg — Sequenzlängen-Kappungen, Engine-Zulassungsbeschränkungen, Cross-Session-Sharing von Blockinhalten — weshalb der LRU/LFU-Kontrast hier schärfer ausfällt als in den Produktions-Traces. Die Richtung ist der Punkt, nicht die Magnituden.

4. Hit-Ratio ist die falsche Währung: die Compute-Savings-Ratio

Der erste konstruktive Beitrag des Papiers behebt ein Metrik-Problem. Zwei Policys mit derselben Hit-Ratio können wild unterschiedliche Prefill-Kosten verursachen, weil das Neuberechnen eines Blocks tief im Prompt teurer ist als eines nahe dem Anfang — jeder ungecachte Token attendiert gegen alle gecachten Token davor, sodass die Recompute-Kosten eines Blocks mit seiner Tiefe in Full-Attention-Layern wächst¹.

Der Fix: die Compute-Savings-Ratio, die jeden Cache-Hit mit den Rechenkosten wiegt, die er vermeidet. In diesem Framing ist die traditionelle Hit-Ratio exakt der Spezialfall eines konstanten Kostenmodells, in dem jeder Block dieselben Kosten hat. Das Papier instanziiert das Kostenmodell auf zwei Arten: ein gemessenes Profil der FLOPs pro Block auf Qwen3-Coder-30B und ein idealisiertes lineares Modell (Appendix C), in dem die Recompute-Kosten eines Blocks proportional zu seiner Tiefe sind — der Grenzwert, in dem Full Attention strikt dominiert. Jede Schlussfolgerung gilt unter beiden, mit etwas breiteren Margen unter dem linearen Modell, weil dessen per-block-Kostenspreizung größer ist¹.

Die Konsequenz tiefenabhängiger Kosten ist schlichte Arithmetik. Unter dem linearen Modell kostet ein Block bei Tiefe d grob proportional zu (d plus Konstante). Blöcke nahe dem Prompt-Anfang sind billig neu zu berechnen; Blöcke bei Tiefe 4.096 kosten auf die Größenordnung von 250-mal mehr. Eine Cache-Policy, die einen flachen Block evicted, um einen tiefen zu schützen, kauft dieselbe Hit-Anzahl mit deutlich mehr gespartem Rechen. Die zwei Offline-Oracles machen das präzise¹:

• Oracle 1 (ILP-Optimum): der Cache-Prozess als Integer Linear Program, Reuse-Intervalle als Variablen, Kapazität als Constraint — eine exakte, aber rechenkostenintensive Offline-Schranke für die Compute-Savings-Ratio.
• Oracle 2 (BeladyCompute): die effiziente Approximation, inspiriert von BeladySize. Für jeden Block i berechnet sie Score(i) = ComputeIntensity(i) × TimeUntilNextAccess(i) und evicted den Block mit dem höchsten Score. Sie folgt dem ILP-Optimum auf dem FreeInference-Trace eng — 1,03 Punkte darunter bei 24 GiB, 0,41 Punkte bei 48 GiB, 0,08 Punkte bei 96 GiB.

Das Online-Gegenstück, das das Papier aus dieser Einsicht baut, ist RandomCompute: zufällig eine Teilmenge gecachter Blöcke sampeln und den Block mit den niedrigsten ComputeIntensity geteilt durch TimeSinceLastAccess evicted — billige, flache, lange inaktive Blöcke gehen zuerst. Auf dem FreeInference-Trace bei knappem 24 GiB unter dem gemessenen Qwen3-Coder-30B-Kostenmodell erreicht RandomCompute eine Compute-Savings-Ratio von 0,638 — 10,4 Punkte über LRU und 2,9 Punkte über dem hit-optimalen Belady-Oracle; es opfert bewusst Hit-Anzahl, um mehr teure Rechenzeit zu sparen¹. Unter dem linearen Modell weiten sich die Margen auf 12,2 Punkte über LRU, und die zwei Offline-Oracles trennen sich ebenso: BeladyCompute erreicht 0,745 gegen Standard-Beladys 0,599¹.

Die nächste Zelle reproduziert die Metrik-Mechanik auf dem sitzungsgetakteten Workload aus Abschnitt 3, mit angehängten Tiefen und dem linearen Kostenmodell, endend mit der Kostenasymmetrie-Tabelle pro Block:

import random
from collections import OrderedDict, defaultdict
import heapq
 
random.seed(20260925)
 
# Same session-paced workload as cell 1, but each block carries its depth
# (position in the prompt), which sets its recompute cost.
S_SYS = 30
requests = []                                   # (t, [(block, depth), ...])
for s in range(150):
    sess = 1000 + s
    pacing = random.uniform(6.0, 12.0)
    onehit = random.random() < 0.45
    turns = 1 if onehit else min(2 + int(random.expovariate(1/6)), 40)
    t0 = random.uniform(0, 3600)
    grow = random.choice([24, 32, 40])
    for turn in range(1, turns + 1):
        t = t0 + turn * pacing + random.gauss(0, pacing * 0.05)
        depth_total = S_SYS + turn * grow
        requests.append((t, [(b if b < S_SYS else sess * 100000 + (b - S_SYS), b)
                              for b in range(depth_total)]))
requests.sort(key=lambda r: r[0])
 
# Linear miss-cost model (paper Appendix C): recomputing a block costs
# compute proportional to its depth -- every uncached token attends to all
# cached tokens before it. Hit ratio is the special case cost == const.
def cost(depth):
    return depth + 16                           # abstract FLOP units per block
 
flat = [(t, b) for t, bl in requests for b, d in bl]
fut = defaultdict(list)
for i, (t, b) in enumerate(flat):
    fut[b].append(i)
INF = 10**9
 
def replay(cap, policy):
    cache = set(); heap = []
    lru_l = OrderedDict()                       # block -> (depth, last time)
    ptr = defaultdict(int)
    hits = total = 0; recompute = 0.0; nocache = 0.0
    for t, bl in requests:
        for b, d in bl:                         # account + admit
            total += 1
            nocache += cost(d)
            if b in cache:
                hits += 1
            else:
                recompute += cost(d)
                if len(cache) >= cap:
                    if policy == "lru":
                        victim = next(iter(lru_l)); del lru_l[victim]
                    elif policy == "randomcompute":
                        # RandomCompute (paper Sec. 5.2): sample, evict the
                        # block with the LOWEST ComputeIntensity/TimeSinceAccess
                        sample = random.sample(list(lru_l), min(16, len(lru_l)))
                        scored = [(cost(lru_l[v][0]) / max(t - lru_l[v][1], 1e-9), v)
                                  for v in sample]
                        victim = min(scored)[1]; del lru_l[victim]
                    else:                       # offline oracles (lazy max-heap)
                        victim = None
                        while heap:
                            key, pid, v = heapq.heappop(heap)
                            if v in cache and pid == ptr[v]:
                                victim = v; break
                        if victim is None:
                            victim = next(iter(lru_l))
                        del lru_l[victim]
                    cache.remove(victim)
                cache.add(b)
            lru_l[b] = (d, t); lru_l.move_to_end(b)
        for b, d in bl:                         # refresh oracle bookkeeping
            ptr[b] += 1
            na = fut[b][ptr[b]] if ptr[b] < len(fut[b]) else INF
            if policy == "belady":              # evict max TimeUntilNextAccess
                heapq.heappush(heap, (-na, ptr[b], b))
            elif policy == "beladycompute":     # evict max Cost x TimeUntilNext
                heapq.heappush(heap, (-cost(d) * na, ptr[b], b))
    return hits, total, recompute, nocache
 
def run(cap, policy):
    h, tot, rc, nc = replay(cap, policy)
    return h / tot, 1 - rc / nc
 
CAP = 700
print("capacity", CAP, "blocks | linear cost model (block cost = depth + 16 units)")
print("policy            |  hit ratio   compute-savings ratio")
for name, pol in (("LRU", "lru"),
                  ("RandomCompute", "randomcompute"),
                  ("Belady (hit-opt)", "belady"),
                  ("BeladyCompute", "beladycompute")):
    hr, csr = run(CAP, pol)
    print(f"{name:17s} |   {hr:.3f}          {csr:.3f}")
 
print()
print("block recompute cost vs depth (linear model):")
for d in (0, 256, 1024, 4096):
    print(f"  depth {d:5d}: {cost(d):6.0f} units  ({cost(d) / cost(0):4.0f}x depth-0 block)")

Ausgabe eines echten Laufs (Python 3, Seed 20260925):

capacity 700 blocks | linear cost model (block cost = depth + 16 units)
policy            |  hit ratio   compute-savings ratio
LRU               |   0.566          0.312
RandomCompute     |   0.586          0.343
Belady (hit-opt)  |   0.652          0.388
BeladyCompute     |   0.644          0.375
 
block recompute cost vs depth (linear model):
  depth     0:     16 units  (   1x depth-0 block)
  depth   256:    272 units  (  17x depth-0 block)
  depth  1024:   1040 units  (  65x depth-0 block)
  depth  4096:   4112 units  ( 257x depth-0 block)

Drei Lesarten. Erstens der Währungs-Gap: Bei so kleinen Tiefen (die Prompts des Spielzeugs enden um die 1.200 Blöcke) liegt die Compute-Savings-Ratio bereits überall deutlich unter der Hit-Ratio — die Misses, die überleben, sind unverhältnismäßig die tiefen, teuren, weil so viele mehr flache Blöcke um dieselbe Kapazität konkurrieren. Auf den Produktions-Traces, mit Requests von durchschnittlich 32 K Token bis 256 K, ist diese Dekorrelation die Motivation des Papiers für die Metrik, keine Fußnote.

Zweitens schlägt RandomCompute LRU hier auf beide Währungen (+2,0 Punkte Hit, +3,1 Punkte Compute-Savings) — dieselbe Richtung wie die Produktions-Margen des Papiers von +10,4/+12,2 Punkten, gedämpft durch die flachen Tiefen und kurzen Horizonte des Spielzeugs.

Drittens eine ehrliche Beobachtung, die die Produktionszahlen nicht so deutlich zeigen: In diesem Spielzeug fallen die zwei Oracles fast zusammen (0,388 vs. 0,375). Weil der Sitzungstakt das Timing des Reuse so regelmäßig macht, ist TimeUntilNextAccess für die meisten Blöcke bereits proportional zu ihrer Zwischenrunden-Lücke, und Tiefe und Rezenz korrelieren — die Multiplikation der Kosten in den Oracle-Score kauft daher wenig Extra. Die Produktions-Trennung des Papiers zwischen den zwei Oracles ist deutlich breiter (12,6 Punkte unter dem gemessenen Modell, 14,6 unter dem linearen bei 24 GiB), weil echte Traces billigen One-Hit-Traffic mit 100-K-Token-Agent-Kontexten mischen, was dieses 150-Sitzungs-Spielzeug komprimiert. Die Lektion ist dieselbe: Gegen welches Oracle man misst, ändert, was „Spielraum" bedeutet, und das Compute-Oracle ist jenes, das Entscheidungen in der Währung preist, die tatsächlich FLOPs kauft.

5. Die Belady-Lücke ist real und größtenteils unbenutzbar

Die schwächste Lesart dieses Papiers wäre: „Härter tunen; Belady zeigt 18 weitere Punkte verfügbar." Die eigenen Daten des Papiers argumentieren das Gegenteil, und die Simulation unten macht den Mechanismus explizit: Sie gibt Belady ein beschränktes Look-ahead-Fenster — ein Offline-Oracle, das die Zukunft nur N Zugriffe voraus kennt, die einzige Zukunft, die irgendein Online-Policy je näherungsweise kennen könnte — und misst, wie viel vom Full-Information-Spielraum überlebt.

import random
from collections import OrderedDict, defaultdict
import heapq
 
random.seed(20260925)
 
# Same session-paced workload as cell 1 (identical seed -> identical stream).
S_SYS = 30
accesses = []
for s in range(150):
    sess = 1000 + s
    pacing = random.uniform(6.0, 12.0)
    onehit = random.random() < 0.45
    turns = 1 if onehit else min(2 + int(random.expovariate(1/6)), 30)
    t0 = random.uniform(0, 3600)
    grow = random.choice([24, 32, 40])
    for turn in range(1, turns + 1):
        t = t0 + turn * pacing + random.gauss(0, pacing * 0.05)
        depth = S_SYS + turn * grow
        for b in range(depth):
            accesses.append((t, b if b < S_SYS else sess * 100000 + (b - S_SYS)))
accesses.sort(key=lambda a: a[0])
 
fut = defaultdict(list)
for i, (t, b) in enumerate(accesses):
    fut[b].append(i)
INF = 10**9
 
def replay_lru(cap):
    cache = OrderedDict(); hits = total = 0
    for t, b in accesses:
        total += 1
        if b in cache:
            hits += 1; cache.move_to_end(b)
        else:
            if len(cache) >= cap:
                cache.popitem(last=False)
            cache[b] = t
    return hits / total
 
def replay_belady_limited(cap, horizon):
    """Belady restricted to a lookahead window of `horizon` accesses. Blocks
    whose next access lies beyond the window are indistinguishable, so the
    oracle degrades toward FIFO among them."""
    ptr = defaultdict(int)
    cache = set(); heap = []; hits = total = 0
    for i, (t, b) in enumerate(accesses):
        total += 1
        if b in cache:
            hits += 1
        else:
            if len(cache) >= cap:
                while True:
                    key, pid, v = heapq.heappop(heap)
                    if v in cache and pid == ptr[v]:
                        cache.remove(v); break
            cache.add(b)
        ptr[b] += 1
        na = fut[b][ptr[b]] if ptr[b] < len(fut[b]) else INF
        if na - i > horizon and na != INF:      # beyond the window
            na = INF
        heapq.heappush(heap, (-na, ptr[b], b))
    return hits / total
 
CAP = 600
lru = replay_lru(CAP)
print(f"capacity {CAP} blocks -- Belady headroom vs usable lookahead")
print()
print(f"{'policy':28s} hit ratio   gap to LRU (pts)")
print(f"{'LRU':28s}   {lru:.3f}          -")
for h, name in ((INF, "Belady (full future)"), (20000, "Belady, 20k-access window"),
                (5000, "Belady, 5k-access window"), (1000, "Belady, 1k-access window"),
                (250, "Belady, 250-access window")):
    hr = replay_belady_limited(CAP, h)
    print(f"{name:28s}   {hr:.3f}        {(hr - lru) * 100:+5.1f}")

Ausgabe eines echten Laufs (Python 3, Seed 20260925):

capacity 600 blocks -- Belady headroom vs usable lookahead
 
policy                       hit ratio   gap to LRU (pts)
LRU                            0.576          -
Belady (full future)           0.754        +17.9
Belady, 20k-access window      0.754        +17.9
Belady, 5k-access window       0.754        +17.9
Belady, 1k-access window       0.742        +16.7
Belady, 250-access window      0.427        -14.9

Das Full-Information-Oracle führt LRU um 17,9 Punkte — eine große, ehrliche Lücke, die der Beobachtung des Papiers entspricht, dass Belady weit über dem besten Online-Algorithmus thront. Aber der Spielraum ist vor-verlagert in perfektes Wissen über die ferne Zukunft: Fenster von 5.000 und sogar 20.000 Zugriffe bergen alles davon, und jedes Oracle, das genug Zukunft kennt, um zu zählen, braucht den gesamten Trace. Echte Prädiktion kommt dorthin nicht — die gelernten Policys in der eigenen Evaluation des Papiers (LeCaR, LRB, 3LCache), die genau diese Art begrenzten Look-aheads approximieren, landen auf LRU's Niveau oder darunter. Das 250-Zugriffe-Fenster ist der lehrreiche Fehlschlag: Nur die nahe Zukunft kennend, performt das „Oracle" schlechter als LRU, weil innerhalb eines kurzen Fensters die fernzukünftigen Blöcke ununterscheidbar sind und die Eviction unter ihnen zu FIFO degeneriert, das für das Sitzungstakt-Signal blind ist, das LRU gratis ausnutzt. Die Lücke ist real, der algorithmisch erreichbare Spielraum ist im Wesentlichen null, und die Schlussfolgerung des Papiers ist exakt, dass der exploitierbare Teil der Lücke bereits geerntet wurde — durch Rezenz plus wenige chirurgische Ergänzungen.

6. Die vier chirurgischen Fixes

Die Design-Antwort des Papiers ist bewusst keine neue monolithische Policy. Sie behält Rezenz als Fundament — LRU als „Bedrock", robust bei minimalen Metadaten-Kosten — und ergänzt vier gezielte Techniken für die Failure-Modi, die die Workload-Charakterisierung tatsächlich zeigt¹:

• Quick Demotion, bedingt. Wenn One-Hit-Prompts ein überwältigendes Trafficvolumen bilden, können sie den Zulassungspfad fluten, bevor ihr Schicksal (kein Reuse) bekannt ist. Ein früher Frequenz-Filter (S3-FIFO-Stil) behebt den Qwen-To-B-Fall: Bei 24 GiB erreicht S3-FIFO 0,491 gegen LRU's 0,403⁴. Aber One-Hit-Prompts sind flach und kurz, belegen also wenig Footprint — Quick Demotion zahlt sich nur aus, wenn ihr Trafficvolumen extrem ist, und das Papier ist explizit, dass es ein bedingter Zusatz ist, kein Default.
• Compute-bewusste Eviction mit partiellen Knoten. Opfer nach Recompute-Kosten gewichten (RandomComputes gesampelte ComputeIntensity über TimeSinceLastAccess), um Kapazität für teure tiefe Blöcke auszugeben. Der Haken ist Fragmentierung: verstreut evictierte Blöcke hinterlassen „Löcher" — zusammenhängende Läufe, die ein Request neu berechnen muss — im Schnitt 9,21 Löcher pro Request, was die Attention-Matrix-Parallelisierung bricht und plain RandomCompute End-to-End schlechter als LRU macht (4,0-faches TTFT, 3,9-fach niedrigeren Durchsatz). Der Fix: partielle Knoten/zusammenhängende Segmente statt Einzelblöcke evictieren — dasselbe Recompute-Volumen (258,0 M vs. 257,9 M Blöcke) in 8,7-mal weniger, 8,7-mal längere Löcher gepackt, was die Gewinne zurückbringt — auf einer H200 bei 48 GiB mit Replay von 10.000 Requests sinkt das durchschnittliche TTFT von 1,29 s auf 1,04 s und der Durchsatz steigt von 55 auf 66 K tok/s relativ zu LRU.
• Kapazitätsabhängige Eviction-Granularität. Im knapp beschränkten HBM vermeidet Blocklevel-Management destruktive Alles-oder-Nichts-Entscheidungen über die schwer-tailingen Sitzungen (die obersten 10 % halten 76,2 % der KV-Bytes — ganze Sitzungen zu evictieren verschwendet den wiederverwendbaren Teil). Im großen Pool reduziert Sitzungsebene-Eviction die Metadaten-Last drastisch, bei geringem Effizienzverlust, sobald die Kapazität reicht.
• Rezenz als Basis von allem. Keines davon ersetzt LRU; es sind Zulassungs-Filter und Opfer-Gewichtungsschichten auf einem rezenz-geordneten Cache — gerade weil das negative Ergebnis aus Abschnitt 3 zeigt, dass das Ordnungssignal selbst bereits richtig ist.

7. Anti-Hype: Was dieses Ergebnis belegt und was nicht

LRU-Near-Optimalität ist eine Eigenschaft dieser Workloads, nicht von Caches. Das Ergebnis gilt für Prefix-Reuse, getaktet durch aktive Sitzungen. Es ist keine allgemeine Cache-Empfehlung: Auf den eigenen Vergleichs-Workloads des Papiers aus Web-CDN- und Blockstorage-Domänen existieren die klassischen raffinierten Policys, weil Popularität und Ankunftsstruktur dort tatsächlich von Rezenz abweichen. Wenn dein Workload persistente Hot-Objects und burstige unabhängige Requester hat, sagt dieses negative Ergebnis dir nichts — außer dass du nicht in seinem Regime bist.

Die Traces sind zwei spezifische Deployments. „Zwei Organisationen" heißt zwei öffentliche LLM-Inferenzdienste mit unterschiedlicher Mixtur (agentisch-lastig vs. konversationell-agentisch-API), validiert gegen sechs externe Workloads — eine starke, aber begrenzte Stichprobe. Ein Trace, dessen Reuse nicht sitzungsgetaktet ist (massiv geteilte System-Prompts über Sitzungen hinweg, intensives Cross-User-Template-Reuse, Einzelschuss-Dokumentsuche), läge außerhalb des charakterisierten Regimes; das Papier selbst hat eine solche Grenze gemessen (Qwen To-B, wo Quick Demotion plain LRU bei 24 GiB um 8,8 Punkte schlägt). Generalisierung jenseits von Prefix-Cache-Serving — auf KV-Offload-Policy, Weight-Caching, alles ohne Sitzungstakt — ist nicht belegt.

Die Compute-Savings-Ratio nimmt das Miss-Kostenmodell an. Beide Instanziierungen (gemessene Qwen3-Coder-30B-FLOPs pro Block; linear tiefenproportional) sind Kostenmodelle, und das Papier sagt das: Sliding-Window-Attention klemmt das Kostenwachstum mit der Tiefe, Hybrid- und GQA/MQA/MLA-Designs, KV-Quantisierung und Cross-Layer-Sharing verändern die Recompute-Kosten und erfordern eine Rekalibrierung des Modells, bevor die Compute-Maschinerie übertragbar ist. Im Sliding-Window-Grenzwert nähert sich die Kostenpro Block einer Konstanten und die Compute-Savings-Ratio kollabiert zurück zur Hit-Ratio — das raffinierte Ziel zahlt sich exakt proportional dazu, wie voll-attention-dominiert dein Modell und deine Kontextlängen sind.

Volltext über Abstract. Eine Abstract-Ebene-Aussage verdient eine Schärfung: „Quick Demotion für One-Hit-Prefixe" liest sich wie eine allgemeine Empfehlung, aber der Volltext gewinnt — das Papier zeigt, dass es sich nur unter extremem One-Hit-Trafficvolumen auszahlt und auf anderen Workloads um 10,1 Punkte unter LRU regredieren kann (LIRS auf Qwen To-C bei 724 GB), und das Headline-Design ist seine bedingte, workload-getriggerte Nutzung.

8. Fazit

Der dauerhafte Beitrag ist eine Grenze, gezogen mit Produktionsdaten: das raffinierte-Eviction-Forschungsprogramm hat, angewandt auf sitzungsgetakteten Prefix-Reuse, keinen Spielraum mehr, den zu jagen sich lohnt, weil der harte Teil des Workloads — vorherzusagen, wann die Blöcke einer Sitzung zurückkehren — von den Sitzungen selbst beantwortet wird. Was schwer bleibt, ist anders, und das Papier benennt es: Misses kosten wild unterschiedliche Mengen Rechenzeit, Sitzungen konsumieren wild ungleiche Kapazität, und die richtige Granularität hängt davon ab, wie viel Speicher du hast. Sein konstruktives Programm folgt — eine compute-gewichtete Metrik mit zwei Offline-Oracles als Diagnose-Instrumenten und vier chirurgischen Rezenz-bewahrenden Fixes, deren Wert pro Failure-Modus demonstriert wird, statt als monolithischer Gewinner.

Für Praktiker ist die Checkliste kurz. Serviere agentischen oder konversationellen Traffic mit sitzungsgetaktetem Reuse: liefere zuerst LRU aus, miss nach, und füge nur hinzu, was deine Messung als fehlend zeigt — eine Demotion-Queue, falls One-Hit-Traffic dich flutet, compute-bewusste Opfer-Gewichtung, falls deine langen Kontexte tiefe Blöcke teuer machen, blockgranulare Eviction, falls der Speicher knapp ist. Serviere etwas anderes: wisse, dass jede Aussage oben in einem Regime verifiziert wurde, in dem du vielleicht nicht bist. Und wenn ein Vendor behauptet, seine gelernte Eviction-Policy nutze „genau wie Beladys Spielraum", frage, welchen Teil der Oracle-Zerlegung dieses Papiers sie zu erreichen glaubt — die Evidenz des Papiers sagt, dass der online erreichbare Teil der Lücke bereits von einem Algorithmus von 1966 eingesackt wurde.

Footnotes