GitHub - gauravapiscean/agentic-kv-cache: Reproducing agentic KV-cache policy claims on real traces. 68k requests from 393 Claude Code sessions. LRU is harder to beat than the papers suggest. · GitHub
Skip to content
Navigation MenuSign inAppearance settingsPlatformAI CODE CREATIONGitHub CopilotWrite better code with AIGitHub Copilot appDirect agents from issue to mergeMCP RegistryIntegrate external toolsDEVELOPER WORKFLOWSActionsAutomate any workflowCodespacesInstant dev environmentsIssuesPlan and track workCode ReviewManage code changesCode QualityEnforce quality at mergeAPPLICATION SECURITYGitHub Advanced SecurityFind and fix vulnerabilitiesCode securitySecure your code as you buildSecret protectionStop leaks before they startEXPLOREWhy GitHubDocumentationBlogChangelogMarketplaceView all featuresSolutionsBY COMPANY SIZEEnterprisesSmall and medium teamsStartupsNonprofitsBY USE CASEApp ModernizationDevSecOpsDevOpsCI/CDView all use casesBY INDUSTRYHealthcareFinancial servicesManufacturingGovernmentView all industriesView all solutionsResourcesEXPLORE BY TOPICAISoftware DevelopmentDevOpsSecurityView all topicsEXPLORE BY TYPECustomer storiesEvents & webinarsEbooks & reportsBusiness insightsGitHub SkillsSUPPORT & SERVICESDocumentationCustomer supportCommunity forumTrust centerPartnersView all resourcesOpen SourceCOMMUNITYGitHub SponsorsFund open source developersPROGRAMSSecurity LabMaintainer CommunityGitHub StarsArchive ProgramREPOSITORIESTopicsTrendingCollectionsEnterpriseENTERPRISE SOLUTIONSEnterprise platformAI-powered developer platformAVAILABLE ADD-ONSGitHub Advanced SecurityEnterprise-grade security featuresCopilot for BusinessEnterprise-grade AI featuresPremium SupportEnterprise-grade 24/7 supportPricingSearch/Sign inSign upAppearance settings
You signed in with another tab or window. Reload to refresh your session.
You signed out in another tab or window. Reload to refresh your session.
You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
gauravapiscean
/
agentic-kv-cache
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
5
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
mainBranchesTagsGo to fileCodeOpen more actions menuLatest commit History2 Commits2 CommitsFolders and filesNameNameLast commit messageLast commit dateexperimentsexperiments resultsresults srcsrc .gitignore.gitignore LICENSELICENSE MakefileMakefile README.mdREADME.md fetch_data.shfetch_data.sh requirements.txtrequirements.txt View all filesRepository files navigationREADMEMIT licenseMore itemsLRU is harder to beat than the KV-cache papers suggest
I replayed 68,266 requests from 393 real Claude Code sessions and 23,608 Mooncake
requests through a prefix-cache simulator, tried to beat the production baseline three
different ways, and failed. The interesting part is why: under capacity pressure, most
recomputation comes from tool-calling loops seconds apart, not from sessions idling past a
TTL — and the TTL never fires at all.
Everything here reproduces from a cold checkout with make setup data repro.
Contents
What I built
Validation: reproducing Mooncake's published curve
1. Agent sessions are idle more than published
2. Under capacity pressure, the waste isn't where I expected
3. The 5-minute TTL never fired under capacity pressure
4. Three ways to beat LRU, three failures
5. The harness bug that makes Belady lose to LRU
What I think this means
Limitations
Reproduce it
Cross-request KV prefix caching is the largest practical lever in agentic LLM serving. It's why
your coding agent's fiftieth turn costs a fraction of its first. Every serving stack has one —
vLLM's automatic prefix caching, SGLang's RadixAttention, LMCache, Mooncake Store — and all of
them evict with LRU by default. (SGLang also ships LFU, SLRU, Priority and others behind
--radix-eviction-policy; LRU is the shipped default.)
There's a large, fast-growing literature arguing LRU is the wrong policy for agentic workloads,
because agent sessions go idle and LRU can't tell a paused session from a dead one. The
argument is intuitive. I believed it, and built a simulator to exploit it.
It didn't work, and why it didn't work turned out to be more interesting than the policy would
have been.
What I built
A block-granular, discrete-event simulator of a cross-request prefix cache. Three properties
that matter, and that quick implementations tend to get wrong:
Hits are prefix-contiguous. A hit is the longest resident prefix of the block chain, not
a set intersection. Miss one block at depth 3 and everything after it is unusable even if it's
still resident.
The radix structure constrains eviction. A block with resident children isn't evictable. So
the baseline is LRU over radix leaves, which is what SGLang and vLLM actually implement.
Beating naive flat LRU would be a strawman.
The in-flight chain must be pinned. See finding 5.
Traces are real, not synthetic:
trace
requests
block size
hash scope
source
SemiAnalysis AgentX
68,266 across 393 Claude Code sessions
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
same
Validation: reproducing Mooncake's published curve
Before trusting anything, I reproduced Mooncake's published hit-rate-vs-capacity table on
Mooncake's own released trace, with their stated policy.
cache (blocks)
1k
10k
30k
50k
100k
∞
published (LRU)
0.30
0.40
0.48
0.50
0.51
0.51
measured (radix-leaf LRU)
0.341
0.460
0.537
0.551
0.552
0.553
measured (flat block LRU)
0.340
0.460
0.537
0.551
0.552
0.553
The shape reproduces exactly, including the saturation point they describe in prose ("1,000 to
50,000 blocks boosts the cache hit ratio from 30% to 50%; further capacity increases show
minimal improvement").
There is a systematic +4–6pp offset I could not explain. I tested five metric definitions —
block denominator, token denominator, dropping the partial tail block, per-request averaging —
and none closes it. The infinite-cache case is policy-free, a pure property of the trace, so
the discrepancy is definitional or a trace-version mismatch, not a replay bug.
Publishing it unresolved rather than tuning until it matches. If you know why, please open an
issue.
Incidental finding: flat block LRU and radix-leaf-restricted LRU differ by 0.02pp on
this workload. The leaf restriction both major engines implement buys essentially nothing here.
Reproduce: make validate
1. Agent sessions are idle more than published
sessions=393 requests=68266
session span (h): 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 days)
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/session: p50=70 max=3551
DUTY CYCLE (fraction of wall-clock actually executing):
p25=3.4% p50=13.9% p75=33.9%
sessions executing <50% of lifetime: 85.5%
The most-cited characterization of agentic serving reports a 20% median duty cycle and
70% of sessions below 50%. On this independent trace it's 13.9% and 85.5% — the
premise is more extreme than published, not less.
Note the shape: gaps are bimodal. A median of 2.1 seconds (tight tool loops) with a heavy
tail out to days.
Reproduce: make characterize
2. Under capacity pressure, the waste isn't where I expected
This is the finding that changed my mind.
AgentSysBench (arXiv:2608.15127) reports that "cache
evictions contribute 55.9% of the total cache-create tokens and account for 31.5% of
aggregate monetary cost," driven by a 5-minute provider TTL colliding with 1–10 minute idle
gaps. That motivated my entire approach.
So before optimizing for it, I measured where recompute comes from — policy-independently.
Replay the trace, and bucket every request's recomputed tokens by the idle gap that preceded it:
gap before request
requests
share of all 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 h
123
5.8%
Requests arriving after a gap longer than 5 minutes account for 17.5% of recompute.
Requests arriving within 10 seconds account for 33.1%.
The dominant source of cache misses here is tight two-second tool loops whose 88k-token
working sets exceed cache capacity — a capacity problem, not a liveness-prediction problem.
With a p50 gap of 2.1 seconds, almost every session is "about to return," so a liveness
estimator has essentially nothing to discriminate on.
⚠️ This does not contradict the 31.5% figure — read this before citing either
The two numbers measure different things in different regimes, and I initially framed this
as a contradiction. It isn't.
AgentSysBench
this repo
numerator
eviction-caused cache-create tokens, priced at $6.25/M
recomputed prefill tokens after a >5min gap
denominator
total bill (incl. cache reads and output tokens)
all recompute tokens
regime
TTL-bound — a provider cache where per-customer capacity is effectively unlimited and entries die on a timer
capacity-bound — 40,000 blocks against a ~10.7M-token working set
In a TTL-bound cache, essentially all evictions are gap-driven by construction. My setup
never enters that regime — which finding 3
demonstrates directly, since TTL-300s was byte-identical to LRU-leaf in every run.
Both results can be entirely correct. The claim here is narrower and it is this: when
capacity binds, it dominates the TTL, and the recompute it causes looks nothing like the
idle-session story. If you are provisioning cache capacity, that changes what you optimise.
If you are reasoning about provider TTLs, the 31.5% figure is the relevant one, not this.
Reproduce: make gap
3. The 5-minute TTL never fired under capacity pressure
TTL-300s produced byte-identical results to LRU-leaf in every single run.
LRU always evicted before the timer expired, so the TTL never became the binding constraint at
any cache size I tested. This is also the cleanest evidence that these runs sit in a
capacity-bound regime rather than the TTL-bound one a provider cache operates in.
4. Three ways to beat LRU, three failures
I implemented a policy with three separable, independently ablatable components:
H — hazard-based P(session returns) replacing recency. Online Bayesian estimator over
observed inter-turn gaps and continuation rates. No oracle: it only ever sees completed
observations.
C — physically-modelled recompute cost. Prefill cost at position i is a linear term
plus an attention term proportional to i, so recomputing the tail of a 100k-token chain is
far more expensive per byte than it looks.
G — coherent session-granularity eviction. Instead of taking the N globally-oldest
leaves (which may truncate 50 different chains), sacrifice one session's private tail.
Hit rate, 40 AgentX sessions, 4,751 requests:
cache (blocks)
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%
Effective recompute cost versus LRU-leaf (negative is worse):
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%
Monotone negative. Every component made it worse, and the one I was most confident in —
coherent eviction — was the worst.
Given finding 2, this is exactly what should
have happened. I was optimizing for a signal carrying 17.5% of the waste, using a predictor
that can't discriminate at a 2.1-second median gap.
Reproduce: make ablation
5. The harness bug that makes Belady lose to LRU
In my first run, Belady — an offline oracle — lost to LRU. That's not a result, that's a
broken harness, and it's worth publishing because I expect it to be common.
The cause: inserting a long chain into a near-full cache lets a policy evict the very prefix
it is currently building. LRU is accidentally immune because just-inserted blocks have the
newest timestamp. Every non-recency policy cannibalises itself. Real engines prevent this with
refcount pins; a from-scratch simulator usually doesn't.
If you build one of these, make your first test "does Belady beat LRU?" If it doesn't, you
have this bug, and every policy comparison you run will be silently wrong in LRU's favour.
Two other implementation notes:
Only the deepest hit block can ever be a leaf, so touch() need only update that one
block. An O(chain length) walk becomes O(1) — which matters at AgentX's 1,387-block median.
Score eviction candidates by sampling k least-recently-used leaves rather than scanning the
cache. This is what production caches do anyway, so it's realism, not a shortcut.
What I think this means
Which constraint binds determines what you should optimise, and the two regimes want
opposite things. If your cache is TTL-bound, liveness prediction and retention policy are the
levers, and the published eviction-cost work applies directly. If it's capacity-bound — which
is where these runs sit — the question isn't "will this session come back?" but "how do I fit
88k-token working sets for N concurrent sessions in tight tool loops?" That points at
compression, tiering, admission control and working-set-aware scheduling instead, and liveness
prediction has essentially nothing to work with at a 2.1s median gap.
I went in assuming the liveness framing and it cost me three failed policies. Establishing
which regime you're in first would have saved all of it.
LRU-leaf is a stronger baseline than the literature treats it as. I couldn't beat it with
three independent mechanisms on real traces. Meanwhile several published alternatives are
evaluated against degraded ports of their competitors — two separate papers benchmark against
Continuum with its adaptive TTL replaced by a fixed 2s or 0.3s pin, which disables the thing
that makes it work. This null result suggests those margins are softer than they read.
Validate against a published curve before trusting your own numbers. Doing that surfaced a
discrepancy I still can't explain, and it's the only reason I trust anything else here.
Limitations
These runs are capacity-bound, not TTL-bound. 40,000 blocks against a ~10.7M-token
working set. A provider cache like Anthropic's is the opposite: per-customer capacity is
effectively unlimited and entries die on a 5-minute timer. Findings 2 and 3 characterise the
capacity-bound regime and say nothing about the TTL-bound one.
This is simulation. It models cache policy faithfully and GPU execution not at all. Valid
for "what should I keep in cache"; not valid for throughput, latency, or SLO attainment.
AgentX block hashes are session-local, so they're namespaced per session. That models
zero cross-session sharing — conservative, but it means shared system prompts across users
are invisible here. Mooncake's hashes are global but its trace is one dense hour with no idle
structure.
AgentX session arrival times are synthesised (uniform over a window), because the trace
stores session-relative timestamps only.
393 sessions and one hour of Mooncake is not the world.
I am not claiming the liveness literature is wrong. I'm claiming that in a
capacity-bound cache the lever it targets has little to work with, and that establishing
which regime you're in should come before choosing a policy.
Reproduce it
git clone https://github.com/<you>/agentic-kv-cache && cd agentic-kv-cache
make setup # venv
make data # ~1.1 GB of traces (Apache-2.0), then flattens AgentX to a pickle
make repro # all four experiments, writes results/
Individually:
make validate # Mooncake reproduction -> results/01_validate.txt
make characterize # AgentX duty cycle and gaps -> results/02_characterize.txt
make gap # recompute by idle gap -> results/03_gap.txt
make ablation # policy ablation -> results/04_ablation.txt
The simulator is pure stdlib Python; numpy is only used by helper scripts. Committed outputs
in results/ let you check the tables without downloading anything.
Open questions
If you can answer any of these, please open an issue — I'd genuinely like to know:
Why the +4–6pp Mooncake offset? Policy-free at infinite cache, so it should be
explicable by metric definition alone, and five definitions don't close it.
Is there a workload where liveness-aware eviction beats radix-leaf LRU? Plausibly one
with much longer median gaps than 2.1s — human-in-the-loop approval flows, perhaps.
Does the 33%-from-sub-10-second-gaps result hold on other agentic traces? If it does,
a good chunk of this subfield is aimed at the wrong term.
Credits
Traces: Mooncake (Moonshot AI, FAST'25) and the
AgentX corpus (SemiAnalysis), both Apache-2.0.
This work is independent of and unaffiliated with either.
MIT licensed.
About Reproducing agentic KV-cache policy claims on real traces. 68k requests from 393 Claude Code sessions. LRU is harder to beat than the papers suggest.Topicskv-cachellm-agentsllm-inferenceprefix-cachingreproducibilitysglangvllmResourcesReadmeMIT licenseActivityStars5 starsWatchers0 watchingForks0 forksReport repositoryContributorsLanguages
Footer
© 2026 GitHub, Inc.
Footer navigation
Terms
Privacy
Security
Status
Community
Docs
Contact
Manage cookies
Do not share my personal information
You can’t perform that action at this time. |
The work presented explores the reproducibility of claims regarding agentic KV-cache policies by replaying real traces from agentic LLM sessions. The main objective was to test whether the Least Recently Used (LRU) eviction policy is truly the optimal method for cross-request prefix caching in agentic workloads, comparing it against published literature. The experiment involved replaying 68,266 requests from 393 Claude Code sessions and 23,608 Mooncake requests through a prefix-cache simulator designed to model block-granular, discrete-event behavior, incorporating constraints such as prefix contiguity, radix structure, and the need to pin in-flight chains.
The validation phase focused on reproducing Mooncake's published hit-rate versus capacity curve using the simulated traces. While the overall shape of the performance curve was reproduced, a systematic offset was observed that could not be accounted for by modifying the metric definitions. This suggests the discrepancy might stem from a definitional difference in the metrics or trace versions rather than a bug in the simulation itself.
A critical finding emerged when analyzing the session dynamics, which revealed that the impact of idle time is context-dependent. The analysis of agent session behavior indicated that the dominant source of cache recomputation arises from tight tool-calling loops separated by short gaps, rather than sessions idling for long periods. This leads to a distinction between two operating regimes: a TTL-bound cache environment, where entries expire based on a fixed timer, and a capacity-bound environment, where eviction is dictated by physical limits, such as a working set size relative to cache capacity.
In the capacity-bound regime, the central hypothesis shifts from predicting session liveness to optimizing the fitting of large working sets within the cache constraints. When capacity binds, the cost associated with recomputation caused by idle gaps is less significant than the cost of fitting large working sets for concurrent sessions. This suggests that liveness-aware eviction policies may be less effective in this regime, as the median gaps observed in the trace are too short—around two seconds—for liveness predictors to effectively discriminate between sessions.
The research also explored three separable methods for improving cache performance over LRU: hazard-based prediction for session return time, modeling the physical recompute cost, and coherent session-granularity eviction. Ablation studies comparing these policies against LRU revealed that none provided a substantial advantage across tested cache capacities. This outcome reinforces the conclusion that in capacity-bound scenarios, the focus should shift toward managing working-set fitting, compression, tiering, and admission control instead of liveness prediction. Furthermore, the simulation highlighted a potential harness bug where an offline oracle, such as Belady's algorithm, could lose to LRU when inserting long chains, demonstrating the necessity of robust implementation details like reference counting pins in production systems to prevent policies from cannibalizing themselves.
In summary, the research posits that the effectiveness of cache policies depends critically on the operational regime. When caches are capacity-bound, capacity management is the primary concern, and liveness prediction based on short idle gaps is less relevant. When caches are TTL-bound, liveness prediction becomes more relevant. The work emphasizes that establishing the operational regime before selecting an eviction policy is essential for deriving meaningful optimization strategies. |