LRU is moeilijker te verslaan dan KV-cache papers suggereren

Alles in dit project kan worden gereproduceerd vanaf een schone installatie met make setup data repro.

Wat ik heb gebouwd

Ik heb een block-granular, discrete-event simulator gebouwd van een cross-request prefix cache. Er zijn drie eigenschappen die cruciaal zijn, en die snelle implementaties vaak fout doen:

1. Hits zijn prefix-continu: Een hit is het langste aanwezige prefix van de block-keten, niet een set-intersectie. Als er één blok op diepte 3 ontbreekt, is alles daarna onbruikbaar, zelfs als het nog in het cachegeheugen staat.
2. De radix-structuur beperkt eviction: Een blok met aanwezige kinderen kan niet worden verwijderd (evicted). De baseline is dus LRU (Least Recently Used) over radix-leaves; dit is wat SGLang en vLLM daadwerkelijk implementeren. Het verslaan van een naïeve 'flat LRU' zou een stroman-argument zijn.
3. De in-flight chain moet worden vastgezet (pinned): Zie bevinding 5.

Gebruikte traces (niet synthetisch)

Trace	Requests	Block size	Hash scope	Bron
SemiAnalysis AgentX	68.266 (over 393 Claude Code sessies)	64 tok	session-local	HF (Apache-2.0)
Mooncake mooncake_trace / toolagent	23.608	512 tok	global	GitHub (Apache-2.0)
Mooncake conversation	12.031	512 tok	global	GitHub (Apache-2.0)

Validatie: het reproduceren van de gepubliceerde curve van Mooncake

Voordat ik de resultaten vertrouwde, heb ik de gepubliceerde tabel met hit-rate versus capaciteit van Mooncake gereproduceerd, met hun eigen trace en hun opgegeven beleid.

Cache (blokken)	1k	10k	30k	50k	100k	$\infty$
Gepubliceerd (LRU)	0.30	0.40	0.48	0.50	0.51	0.51
Gemeten (radix-leaf LRU)	0.341	0.460	0.537	0.551	0.552	0.553
Gemeten (flat block LRU)	0.340	0.460	0.537	0.551	0.552	0.553

De vorm is exact gereproduceerd, inclusief het verzadigingspunt dat zij beschrijven ("1.000 tot 50.000 blokken verhoogt de cache hit ratio van 30% naar 50%; verdere capaciteitsverhogingen tonen minimale verbetering").

Er is een systematisch verschil van +4–6 procentpunt dat ik niet kon verklaren. Ik heb vijf definitie-metrieken getest — blok-noemer, token-noemer, het weglaten van het gedeeltelijke staartblok, middeling per request — maar geen enkele sloot het gat. Aangezien het geval met de oneindige cache beleidsvrij is (een pure eigenschap van de trace), is het verschil definitie-gerelateerd of een mismatch in trace-versie, en geen fout in de replay. Ik publiceer dit onopgelost in plaats van het te tunen tot het matcht.

Bijkomstige bevinding: Flat block LRU en radix-leaf-restricted LRU verschillen met 0,02 procentpunt op deze workload. De leaf-restrictie die de meeste engines implementeren, levert hier in feite niets op.

Reproduceer via: make validate

1. Agent-sessies zijn vaker inactief dan gepubliceerd

sessions=393 requests=68266

• Sessie-spanne (u): p50=1.84, p90=28.36, max=254.8
• Inter-req gap (s): p50=2.1, p90=51.1, p99=3426.3, max=491922 (5,7 dagen)
• Gaps > 60s: 9.5%
• Gaps > 300s: 3.3%
• Gaps > 3600s: 1.0%
• Input tokens: p50=88768, p90=204288, max=255808
• Output tokens: p50=376, p90=1845
• Requests per sessie: p50=70, max=3551

DUTY CYCLE (fractie van de wandklok die daadwerkelijk wordt uitgevoerd):

• p25=3.4%, p50=13.9%, p75=33.9%
• Sessies die <50% van hun levensduur uitvoeren: 85.5%

De meest geciteerde karakterisering van agentic serving rapporteert een mediane duty cycle van 20% en 70% van de sessies onder de 50%. Op deze onafhankelijke trace is dat 13,9% en 85,5% — de premisse is dus extremer dan gepubliceerd. De gaps zijn bimo-daal: een mediaan van 2,1 seconden (strakke tool-loops) met een zware staart die uitloopt tot dagen.

Reproduceer via: make characterize

2. Onder capaciteitsdruk zit de verspilling niet waar ik het verwachtte

Dit is de bevinding die mijn mening veranderde.

AgentSysBench (arXiv:2608.15127) rapporteert dat "cache evictions verantwoordelijk zijn voor 55,9% van de totale cache-create tokens en 31,5% van de totale monetaire kosten," gedreven door een provider TTL van 5 minuten die botst met inactieve gaps van 1–10 minuten. Dit motiveerde mijn hele aanpak.

Ik heb daarom gemeten waar de recompute vandaan komt, onafhankelijk van het beleid. Ik heb de trace afgespeeld en alle recomputed tokens van elk request gecategoriseerd op basis van de inactieve gap die eraan voorafging:

Gap voor request	Requests	Aandeel in alle recompute tokens
< 10 s	10.069	33.1%
10–60 s	912	7.0%
1–5 min	701	20.5%
5–30 min	236	8.6%
30–60 min	50	3.0%
> 1 u	123	5.8%

Requests die arriveren na een gap van langer dan 5 minuten zijn verantwoordelijk voor 17,5% van de recompute. Requests die binnen 10 seconden arriveren, zijn verantwoordelijk voor 33,1%.

De dominante bron van cache misses hier zijn strakke tool-loops van twee seconden waarvan de working sets van 88k tokens de cachecapaciteit overschrijden — een capaciteitsprobleem, geen liveness-voorspellingsprobleem. Met een p50 gap van 2,1 seconden is bijna elke sessie "op het punt om terug te keren", waardoor een liveness-estimator in feite niets heeft om op te discrimineren.

Waarschuwing: dit spreekt de 31,5% figuur niet tegen

De twee getallen meten verschillende dingen in verschillende regimes.

Aspect	AgentSysBench	Deze repo
Numerator	eviction-caused cache-create tokens, geprijsd op $6.25/M	recomputed prefill tokens na een gap > 5min
Denominator	totale rekening (incl. cache reads en output tokens)	alle recompute tokens
Regime	TTL-bound — provider cache waar capaciteit per klant effectief onbeperkt is en entries sterven op een timer	capacity-bound — 40.000 blokken tegenover een working set van ~10,7M tokens

In een TTL-bound cache zijn in essentie alle evictions gap-gedreven. Mijn setup komt nooit in dat regime terecht — wat bevinding 3 direct aantoont, aangezien TTL-300s in elke run byte-identiek was aan LRU-leaf.

Beide resultaten kunnen correct zijn. De claim hier is specifieker: wanneer capaciteit de beperkende factor is, domineert dit de TTL, en de recompute die het veroorzaakt lijkt in niets op het verhaal van de inactieve sessie. Als je cachecapaciteit provisioneert, verandert dat waar je op optimaliseert.

Reproduceer via: make gap

3. De 5-minuten TTL trad onder capaciteitsdruk nooit in werking

TTL-300s produceerde in elke enkele run byte-identieke resultaten als LRU-leaf. LRU verwijderde altijd blokken voordat de timer verliep, waardoor de TTL nooit de beperkende factor werd bij elke cachegrootte die ik testte. Dit is het duidelijkste bewijs dat deze runs zich in een capacity-bound regime bevinden.

4. Drie manieren om LRU te verslaan, drie mislukkingen

Ik heb een beleid geïmplementeerd met drie scheidbare componenten:

• H (Hazard-based): Vervangt recency door de waarschijnlijkheid $P(\text{sessie keert terug})$. Een online Bayesiaanse estimator over waargenomen inter-turn gaps en voortzettingspercentages. Geen oracle: het ziet alleen voltooide observaties.
• C (Cost-model): Fysiek gemodelleerde recompute-kosten. Prefill-kosten op positie $i$ zijn een lineaire term plus een attention-term proportioneel aan $i$, waardoor het herberekenen van de staart van een 100k-token keten per byte veel duurder is dan het lijkt.
• G (Granularity): Coherente eviction op sessieniveau. In plaats van de $N$ wereldwijd oudste leaves te nemen (wat 50 verschillende ketens kan trunceren), offer ik de private staart van één sessie op.

Hit rate (40 AgentX sessies, 4.751 requests)

Cache (blokken)	LRU-leaf	TTL-300s	LFU-leaf	+H	+HC	+HCG
8.000	83.48%	83.48%	63.61%	82.89%	71.77%	68.63%
20.000	93.92%	93.92%	69.96%	93.61%	84.86%	78.89%
50.000	95.76%	95.76%	79.58%	95.68%	94.45%	91.40%

Effectieve recompute-kosten versus LRU-leaf (negatief is slechter)

Cache	LFU-leaf	+H	+HC	+HCG
8.000	−129.7%	−3.2%	−38.9%	−81.0%
20.000	−434.3%	−4.5%	−90.4%	−207.8%
50.000	−447.1%	−1.0%	−15.4%	−66.8%

Het resultaat is monotone negatief. Elke component maakte het slechter, en de component waar ik het meest in vertrouwde — coherente eviction — was het slechtst. Gegeven bevinding 2 is dit precies wat er zou moeten gebeuren. Ik optimaliseerde voor een signaal dat slechts 17,5% van de verspilling veroorzaakte, met een voorspeller die niet kan discrimineren bij een mediane gap van 2,1 seconde.

Reproduceer via: make ablation

5. De harness-bug waardoor Belady verliest van LRU

In mijn eerste run verloor Belady — een offline oracle — van LRU. Dat is geen resultaat, maar een kapotte harness. Het is de moeite waard om te publiceren omdat ik verwacht dat dit een veelvoorkomende fout is.

De oorzaak: Het invoegen van een lange keten in een bijna volle cache zorgt ervoor dat een beleid het prefix kan verwijderen dat het op dat moment aan het opbouwen is. LRU is hier per ongeluk immuun voor, omdat net ingevoegde blokken de nieuwste timestamp hebben. Elk beleid dat niet op recency is gebaseerd, cannibaliseert zichzelf. Echte engines voorkomen dit met refcount pins; een simulator vanaf nul doet dat meestal niet.

Als je zo'n simulator bouwt, moet je eerste test zijn: "Verslaat Belady LRU?". Als dat niet zo is, heb je deze bug, en zal elke beleidsvergelijking die je uitvoert stilzwijgend onjuist zijn in het voordeel van LRU.

Overige implementatienotities:

• Alleen het diepste hit-blok kan een leaf zijn, dus touch() hoeft alleen dat ene blok bij te werken. Een walk van $O(\text{chain length})$ wordt $O(1)$, wat belangrijk is bij de mediane 1.387 blokken van AgentX.
• Score eviction-kandidaten door $k$ least-recently-used leaves te samplen in plaats van de hele cache te scannen. Dit is wat productie-caches sowieso doen.

Wat dit volgens mij betekent

Welke beperking bindend is, bepaalt waar je op moet optimaliseren, en de twee regimes vragen om tegenovergestelde zaken.

1. TTL-bound: Als je cache TTL-bound is, zijn liveness-voorspelling en retentiebeleid de belangrijkste knoppen, en is het gepubliceerde werk over eviction-kosten direct van toepassing.
2. Capacity-bound: In dit regime (waar deze runs zich bevinden) is de vraag niet "komt deze sessie terug?", maar "hoe pas ik working sets van 88k tokens voor $N$ gelijktijdige sessies in strakke tool-loops?". Dit wijst in de richting van compressie, tiering, admission control en working-set-aware scheduling. Liveness-voorspelling heeft bij een mediane gap van 2,1s simpelweg niets om mee te werken.

Ik ging uit van het liveness-frame en dat kostte me drie mislukte beleidsopties. Eerst vaststellen in welk regime je zit, had dit bespaard.

LRU-leaf is een sterkere baseline dan de literatuur doet voorkomen. Ik kon het niet verslaan met drie onafhankelijke mechanismen op echte traces. Ondertussen worden verschillende gepubliceerde alternatieven geëvalueerd tegen gedegradeerde ports van hun concurrenten. Dit nulresultaat suggereert dat die marges minder groot zijn dan ze lijken.

Valideer altijd tegen een gepubliceerde curve voordat je je eigen cijfers vertrouwt. Door dat te doen, kwam er een discrepantie naar boven die ik nog steeds niet kan verklaren, en dat is de enige reden waarom ik alles wat hier staat vertrouw.

Beperkingen

• Deze runs zijn capacity-bound, niet TTL-bound. 40.000 blokken tegenover een working set van ~10,7M tokens. Een provider-cache zoals die van Anthropic is het tegenovergestelde: capaciteit per klant is effectief onbeperkt en entries sterven na een 5-minuten timer. Bevinding 2 en 3 karakteriseren het capacity-bound regime en zeggen niets over het TTL-bound regime.
• Dit is een simulatie. Het modelleert het cachebeleid getrouw, maar de GPU-executie helemaal niet. Het is geldig voor "wat moet ik in de cache houden", maar niet voor throughput, latentie of SLO-bereik.
• AgentX block hashes zijn session-local, wat betekent dat er nul cross-session sharing is. Dit is conservatief, maar betekent dat gedeelde system prompts over gebruikers heen onzichtbaar zijn.
• AgentX sessie-aankomsttijden zijn gesynthetiseerd (uniform over een venster), omdat de trace alleen sessie-relatieve timestamps opslaat.
• 393 sessies en één uur Mooncake is niet representatief voor de hele wereld.

Ik beweer niet dat de liveness-literatuur onjuist is. Ik beweer dat in een capacity-bound cache de knop waar het op richt weinig effect heeft, en dat het bepalen van het regime vooraf moet gaan aan het kiezen van een beleid.

Dit reproduceren

git clone https://github.com/<you>/agentic-kv-cache && cd agentic-kv-cache
make setup      # venv
make data       # ~1.1 GB aan traces (Apache-2.0), vlakt AgentX af naar een pickle
make repro      # alle vier de experimenten, schrijft resultaten naar results/

Individueel:

• make validate → Mooncake reproductie → results/01_validate.txt
• make characterize → AgentX duty cycle en gaps → results/02_characterize.txt
• make gap → recompute per idle gap → results/03_gap.txt
• make ablation → beleids-ablatie → results/04_ablation.txt

De simulator is puur stdlib Python; numpy wordt alleen gebruikt door helper-scripts.

Openstaande vragen

Als je een antwoord hebt op een van deze vragen, open dan graag een issue:

1. Waarom de +4–6pp Mooncake offset? Het is beleidsvrij bij een oneindige cache, dus het zou alleen verklaarbaar moeten zijn door de definitie van de metriek, maar vijf definities lossen het niet op.
2. Is er een workload waar liveness-aware eviction wel wint van radix-leaf LRU? Waarschijnlijk een workload met veel langere mediane gaps dan 2,1s — zoals human-in-the-loop approval flows.
3. Blijft het resultaat van 33% uit gaps korter dan 10 seconden overeind op andere agentic traces? Als dat zo is, is een groot deel van dit subveld gericht op de verkeerde term.