A prefix-cache advisor for LLM serving. Point it at your own request log and it tells you how much KV cache memory to allocate, what that memory actually buys you, and which eviction policy to run at that size.
Underneath it is a heavily verified simulator for dependency-constrained, cost-aware cache eviction, plus an open question in competitive analysis. The simulator is what makes the advisor's numbers trustworthy. The theory is a real second track and is not something you need to care about to use the tool.
For users
- What this is, and the one number that matters
- Quick start
- Reading the output
- What it is not
- Status: what is built, what is verified
For everyone
For researchers
- The formal model
- The open question and its branches
- Repository architecture
- Using the library
- Reproducing everything
- Development
- Claims discipline
If you serve LLM traffic with prefix caching turned on — SGLang's RadixCache,
vLLM's block pool — you have made two configuration decisions, probably without
much data:
- How much GPU memory to give the KV cache. In SGLang this is
--mem-fraction-static; in vLLM it is--gpu-memory-utilization. - Which eviction policy to run. In SGLang,
--radix-eviction-policy, with seven options and no published guidance on choosing between them.
This tool replays your own traffic through a verified simulator and answers both. And the first thing it will tell you is which of the two questions is worth your time.
Measured on the public Mooncake production traces, cost expressed as a multiple of the compulsory minimum — what an infinite cache would still have to compute:
| Lever | conversation trace | toolagent trace |
|---|---|---|
| Capacity, 2 percent to 25 percent of working set | 1.4413 to 1.0224 | 1.4178 to 1.0036 |
| Policy, best available versus LRU at 2 percent | 1.4413 to 1.4113 | 1.4178 to 1.3823 |
Your memory allocation is worth about 20 percent of total prefill recomputation. Your policy choice is worth 1 to 2 percent.
That ratio is the tool's central point. Almost all published work on prefix-cache eviction — including, for a long time, this project — optimises the 1 percent axis. The advisor leads with the 20 percent one, then tells you honestly how small the remaining lever is.
The dot on each line is where LRU's own curve flattens — the point section 3
calls the knee. Below it, capacity is doing the work; past it, only a policy
change can move the line at all, and by the margin in the table above.
Regenerated by python scripts/run_bench.py, off the same CapacityCurve the
advisor's own capacity section renders — no second sweep to drift out of sync.
Three commands from nothing to a capacity recommendation, on a sample log that ships with the repository:
git clone <this repo> && cd cache-worthy
python -m venv .venv && . .venv/bin/activate # or .venv\Scripts\activate
pip install . && cache-worthy analyze examples/sample_log.jsonlThen point it at your own traffic:
cache-worthy analyze yourlog.jsonl
cache-worthy analyze yourlog.jsonl --capacity-gib 40 # you know your size
cache-worthy analyze yourlog.jsonl --json # the whole resultexamples/sample_log.jsonl is constructed, not production data — it exists so
a first run needs no download. Every number quoted in this README comes from the
Mooncake production traces instead, fetched by python scripts/fetch_traces.py.
The script path this repository has documented since the beginning still works and prints exactly the same bytes, which is checked on every test run:
python scripts/will_this_help_me.py yourlog.jsonlOne JSON object per line. Two shapes are auto-detected per file, and a file has to be internally consistent:
| Shape | Detected by | How paths are derived |
|---|---|---|
| native | a hash_ids list |
used verbatim; this is the Mooncake schema |
| text | the first present of prompt, text, input, or an OpenAI-style messages list |
chunked and cumulatively hashed |
The text path is the one place the tool is approximate, and it says so on every
run. A real prefix cache hashes (parent_hash, block_tokens). With no tokenizer
in the dependency list, this hashes (parent_hash, block_chars) using
chars_per_block = round(512 * chars_per_token), where --chars-per-token
defaults to 4.0.
The sharing structure is faithful — two prompts share a block exactly when they share that character prefix, which is when they share the token prefix up to tokenizer boundary effects. Only the scale rides on the ratio: how many blocks a prompt occupies, and therefore its size and cost. The tool prints the ratio it used and the flag to change it.
Hashing is blake2b truncated to 63 bits, deliberately not Python's hash(),
which is salted per process for strings and would break determinism.
You need a request log with prompts or prefix hashes. If your gateway does not
keep one, a capture helper is planned (section 5). Failing that, the three
Mooncake traces are fetched by python scripts/fetch_traces.py and are a
reasonable stand-in for conversational and tool-agent traffic.
The advisor answers six questions, in decreasing order of what they are worth. Each one gates the next, and any of them can end the run with a useful answer.
| # | Question | What it tells you | Worth |
|---|---|---|---|
| 1 | Is prefix caching worth enabling at all? | If your reuse is near zero, stop here | stop or continue |
| 2 | What is the least memory that can serve my traffic? | A hard floor. Below it, requests cannot be served | a constraint |
| 3 | How much should I allocate? | The cost-versus-capacity curve and where the knee is | about 20 percent |
| 4 | Am I capacity-bound or policy-bound? | Whether to spend your next hour on memory or on a flag | decides 3 vs 5 |
| 5 | Which eviction policy? | Which of the seven to run, honestly including "LRU already wins" | 1 to 2 percent |
| 6 | What can I change today? | The shared prefixes worth pinning, via retention APIs that already exist | free |
Questions 1, 2, 3, 5 and 6 are answered today. Question 4 needs the LP lower bound, which is not built; until it is, the tool reports what each policy costs but not how much of the remaining gap any policy could recover.
A request pins its own path while it is being served, so your cache must be at least as large as your deepest single request. This is not theoretical: on a constructed agent workload, the deepest request was 1.19 GiB of KV against a 50.81 GiB working set — 2.3 percent, which is above the 2 percent capacity point that this project had been using as its headline regime.
So "2 percent capacity" is not automatically a runnable configuration. It is on Mooncake, whose requests are short relative to its working set. It may not be on a workload with long conversations. The tool computes this floor exactly, always includes it as a sweep point, and names it in the output. There is no other way to discover it except by crashing.
If plain LRU is already the cheapest policy at your capacity, the tool says so. On the real traces that is exactly what happens at 25 percent capacity. A tool that could only report a win would be reporting a number it cannot support.
Real output, abridged, from cache-worthy analyze examples/sample_log.jsonl —
the sample log this repository ships, which is constructed and not production
data. Question 4's headroom column is the one part not built yet.
Lines marked [...] are the only edits: twelve of the twenty curve rows and some
explanatory prose are cut for length. Every number below is what the command
prints.
WORKLOAD
--------------------------------------------------------------------
read as a text log
chunking 2048 chars/block (--chars-per-token; structure is exact, ...)
model Llama-3.1-8B
records 113
blocks 429 references, 200 distinct (53.4% reuse)
re-referenced 30.5% of distinct blocks are ever asked for twice
reuse distance p50 3, p90 5, p99 16 requests (<=10: 99%, <=100: 100%, ...)
request depth p50 4, p90 5, max 6 blocks of 512 tokens
radix nodes 173 size p50 1, p90 2, max 2 blocks
largest subtree 93 blocks must be evicted before its root can be
cost spread 2.0x p90/p10 per node, but only 1.1x per byte (Llama-3.1-8B)
working set 12.50 GiB (a cache this big never evicts)
minimum cache 0.38 GiB = 3.0% of it (your deepest request; below this ...)
QUESTION 1 WORTH CACHING
With unlimited memory and a perfect policy, prefix caching removes at most
52.7% of this log's prefill recompute. That is a ceiling: no capacity
and no policy can beat it, and a real cache lands under it.
CAPACITY under lru, the deployed default
--------------------------------------------------------------------
QUESTION 2 minimum cache 0.38 GiB = 3.00% of the working set.
[...]
capacity cost elasticity
3.00% 0.38 GiB 1.7810 -- floor: your deepest request
3.61% 0.45 GiB 1.7134 0.209
4.34% 0.54 GiB 1.6892 0.077
5.22% 0.65 GiB 1.4663 0.767
6.28% 0.78 GiB 1.3144 0.593
7.55% 0.94 GiB 1.1766 0.600
9.08% 1.13 GiB 1.0587 0.572
10.92% 1.36 GiB 1.0144 0.232 recommended
13.13% 1.64 GiB 1.0144 -0.000
15.79% 1.97 GiB 1.0096 0.026
[...]
100.00% 12.50 GiB 1.0000 -0.000 working set: never evicts
QUESTION 3 ALLOCATE 10.92% = 1.36 GiB
Costs 1.0144x the compulsory minimum. Past it, the remaining
11.14 GiB of KV buys 1.4% of the recompute you would
still be paying there.
POLICY
--------------------------------------------------------------------
compulsory cost 1.508e+15 FLOPs (any cache pays this)
Total recompute cost, as a multiple of the compulsory minimum.
Lower is better; 1.0000 would mean nothing was ever re-prefilled.
capacity cost_only freq_landlord gdsf landlord lru ...
3.0% = 0.38 GiB 1.7858 *1.7235 1.7235 1.7810 1.7810
5.0% = 0.62 GiB 1.4699 *1.4429 1.4429 1.4703 1.4663
10.0% = 1.25 GiB 1.0290 1.0788 1.0788 1.0436 *1.0243
10.9% = 1.36 GiB 1.0339 1.0642 1.0642 1.0339 *1.0144
25.0% = 3.12 GiB *1.0000 1.0000 1.0000 1.0000 1.0000
* = cheapest at that capacity.
Verdict
-------
3.0% freq_landlord saves 3.23% of total recompute vs lru (8.672e+13 FLOPs).
5.0% freq_landlord saves 1.59% of total recompute vs lru (3.525e+13 FLOPs).
10.0% no policy here beats lru, your current default. Changing it would not
help.
25.0% every policy costs exactly the same, and all of it is unavoidable.
[...]
PIN available at your current capacity, under your current policy
--------------------------------------------------------------------
QUESTION 6 5 prefixes protect at most 50.8% of what caching can save
refs depth blocks subtree pin KV protects
#0 51 0 1 93 0.06 GiB 21.5%
#1 31 0 1 52 0.06 GiB 12.9%
#2 31 0 1 55 0.06 GiB 12.9%
#3 5 1 1 8 0.12 GiB 1.8%
#4 5 1 1 9 0.12 GiB 1.8%
Together: 0.31 GiB held resident protects at most
50.8% of avoidable recompute = 26.8% of the whole prefill bill.
These are recomputation FLOPs under the analytic cost model in
src/cache_worthy/cost.py, not measured latency. This repo has not
timed a GPU, so it does not translate them into seconds or dollars.
Nothing here is a proven bound.
Two things in that output are worth pointing at, because they are the tool working rather than the tool failing. At 10 percent and above, plain LRU is already the cheapest policy and the verdict says so. And the three top pins are the three tenants' shared preambles — 51, 31 and 31 requests — which between them protect half of everything caching could ever save on this log, for 0.31 GiB and no restart.
Elasticity is the percent of recompute removed per percent of memory added, as a local log-log slope, so it is unit-free. The recommendation is the smallest capacity past which no further step on the curve reaches 0.10 — the point where another ten percent of KV buys under one percent of recompute, which is about what changing the eviction policy is worth at all.
The whole column is printed so you can apply a different threshold without re-running anything. The curve is measured under LRU, the policy your server already runs, so that the 1-percent policy axis can never move the 20-percent capacity recommendation.
Question 6 ranks shared prefixes by the recompute that holding them resident
would protect: (references - 1) x cost. It assumes no capacity and no policy,
so it is advice you can act on today through a retention API, without a restart.
Two things about that column are load-bearing. It is a ceiling — your cache
already retains some of it for free, so the real gain is smaller. And pin KV
includes the ancestors a pin implies, because a cached prefix whose own prefix
has been evicted is unreachable.
--json emits the whole result: every workload field, every curve point with its
elasticity, every policy cell, and every pin. The table is a second rendering of
the same measurement, and a test reparses the table and compares it against the
JSON cell by cell, so the two cannot drift.
cache-worthy analyze yourlog.jsonl --json | jq '.capacity.recommended_fraction'- Not a policy you install. SGLang's eviction-strategy registry is a hardcoded module-level dict with no registration hook, and an unknown policy name raises. Selecting a third-party policy today means patching SGLang. An upstream patch to add a registration hook is being written; until it lands, the advisor's value does not depend on it, because it needs nothing from any serving stack.
- Not a latency or TTFT predictor. It reports prefill recomputation in FLOPs. This repository has measured FLOPs, not wall-clock, and converting one to the other would be a claim it cannot support. Treat the output as a proxy for prefill work avoided.
- Not a claim that any policy here beats the deployed default. At large capacity on the measured traces, none of them does, and the tool reports that.
- Not a model of what cache memory costs you. KV memory trades against batch size and concurrency. The advisor gives you the benefit curve; the trade is yours to make.
- Not a proof of anything. See section 15.
Two words are used throughout this document, and they mean specific things:
- verified — its behaviour has been confirmed against at least one oracle that exists independently of the implementation. For a mathematical result it means every automated check that exists for it passes. It does not mean proven.
- unverified — not yet checked, or no oracle above self-written unit tests exists yet. Stated explicitly rather than quietly downgraded.
| Component | Verified by |
|---|---|
| Trace pipeline | Reproduces the published Mooncake figures exactly — all twelve cells. Mutation-tested: every one-unit perturbation is caught |
| Static prefix forest | Every one of 409,914 distinct blocks has exactly one parent and one depth. Node sizes sum exactly to the distinct-block count |
| Cost model | Derived non-embedding parameter counts sum to the published 8.03 B and 70.55 B model sizes |
| Online simulator and radix tree | Leaf-only eviction, byte conservation, capacity and determinism enforced in-loop as raises. Heap and linear-scan eviction agree byte-for-byte |
| Seven eviction policies | Landlord obeys the known competitive bound on every flat sequence where that theorem applies. Each diagnostic policy replays byte-identically to its reference under the conditions where they must coincide |
| Exhaustive true-OPT solver | Matches Belady exactly on every short sequence where Belady is optimal; is at most every policy's cost, always |
| Potential-function harness | Every row of the published theorem holds across 4,784 replays on flat instances |
| Adversarial construction | LRU's cost matches a closed form derived before the code ran |
| The advisor (log ingest and replay) | Reproduces the reference replay field-for-field on 12,031 real requests across every policy and capacity; text ingest and native ingest agree byte-for-byte on isomorphic logs |
| The capacity curve and the knee | The reported minimum cache serves the log and one block less does not; at a capacity equal to the working set all seven policies pay exactly the compulsory cost with zero evictions; the knee is checked against curves whose answer was computed by hand first. The benchmark and the command-line tool render the same curve byte-for-byte |
| The pin list | The per-prefix protections sum exactly to the log's total avoidable recompute, against a total computed two other ways, on all three traces, with no block counted twice. On the conversation trace the top prefix is the depth-0 preamble shared by all 12,031 requests. A three-request toy reproduces a ceiling that was derived by hand for a different oracle |
| JSON output | The rendered table is parsed back and compared with the JSON cell by cell, section by section, positionally, on a real trace and again under a non-default model. The document is strict JSON: undefined quantities are null, never NaN |
| The packaged CLI | cache-worthy analyze and the original script path print byte-identical output. The shipped example log is regenerated from its script and compared byte for byte |
| The LRU-unbounded result | Four independent automated checks, including against brute-force true OPT |
- Continuous integration. The workflow is committed but has never actually
run on a runner, so "a stranger can reproduce this on a clean non-Windows
machine" is unproven. What has been done: the hermetic job's exact commands
—
pip install -e ".[dev]", thenmake checkandmake proofs— were run against a fresh virtualenv on a tree containing only committed files, and both passed. The trace-fetching job runs green against the real traces, but not yet from a fresh virtualenv. Ubuntu and the runner itself remain untested.
| The LP lower bound | Question 4. Without it the tool reports what each policy costs but not how much is recoverable |
| Sensitivity band | Every printed number depends on the cost model's coefficients; the band is a gate, not a nicety |
| Tail statistics and cold start | p50/p95/p99 per request, and time-to-steady-state from an empty cache |
| Log adapters and capture helper | vLLM, SGLang and OpenAI-style logs behind the existing auto-detect seam, and a recorder for users with no log at all |
| The main theoretical result | Whether the standard guarantee survives these constraints. Three outcomes are pre-registered as acceptable, including that it is false |
| SGLang integration | Both the registration-hook patch and any policy contribution |
An LLM must process ("prefill") your entire prompt before it emits a single token, and prefill cost grows superlinearly with prompt length. When two requests share a prefix — a system prompt, a conversation history, a tool preamble — the shared part only has to be computed once. Those intermediate results, the KV blocks, are cached in GPU memory. Evicting a KV block means paying its recomputation cost again the next time that prefix appears.
That makes it a caching problem, but an unusual one in two specific ways.
Cached items form a tree, and only leaves are evictable. A cache holds
system prompt, then system prompt + turn 1, then system prompt + turn 1 + turn 2. Evicting an interior node would orphan everything built on top of it, so
it is forbidden. To free an interior node's space you must first evict its entire
cached subtree. Eviction cost is therefore not local, and an adversary can
exploit that.
Recomputation costs are wildly non-uniform. A short recent turn costs almost nothing to redo. A long shared prefix costs a great deal, and that cost grows with depth because attention is quadratic.
The policy deployed almost everywhere is LRU, which is blind to both.
Take a cache holding k items: one expensive item E and k cheap ones.
Requests cycle E, c1, ..., ck forever. The cycle touches k+1 distinct items
through a k-slot cache, so LRU misses on every request — and being cost-blind,
it discards E as readily as anything else, paying E's cost every cycle. A
cost-aware policy pins E and rotates the cheap items through the remaining k-1
slots.
LRU's cost grows without bound as E gets more expensive: there is no constant,
and no function of the cache size, that bounds it. The construction is
implemented and runnable, and the write-up passes four independent automated
checks — including its per-phase optimum verified against a brute-force true
optimum rather than against the prose, which is what caught an arithmetic error in
an earlier draft of it.
Run it yourself:
python scripts/run_adversary.pyCost-aware prefix-cache eviction already exists. RAGCache ships a GreedyDual-Size-Frequency variant over a knowledge tree, evicting the least-priority leaf. Two gaps remain:
- It carries no guarantee. The string
competitiveappears zero times in the RAGCache paper. "Works on the traces tested" is not a bound. - It ignores the tree in its analysis. GreedyDual-family policies were designed for flat caches. Whether their guarantees survive leaf-only eviction is an assumption, not a fact, and it is exactly what this project tests.
And, as section 7 shows, the empirical gap between all these policies on real traffic is 1 to 2 percent — which is why the tool leads with capacity instead.
Everything in this section is a measurement regenerated by a committed script. None of it is a claim about a proven result, and none of it was tuned toward. Where an expectation was written down in advance and turned out wrong, that is stated.
Three production traces from Mooncake FAST'25, Apache-2.0. Reproduced exactly against Mooncake's own published figures:
| Trace | Requests | Span | Blocks total / distinct | Block reuse | Mean input |
|---|---|---|---|---|---|
conversation_trace |
12,031 | 0.98 h | 288,500 / 182,790 | 36.6 percent | 12,035 |
toolagent_trace |
23,608 | 0.98 h | 409,616 / 183,300 | 55.3 percent | 8,596 |
synthetic_trace |
3,993 | 0.28 h | 121,877 / 43,924 | 64.0 percent | 15,325 |
Caveats stated openly. Timestamps are quantized to about 1,180 distinct values,
roughly 3-second buckets. The span is about one hour, so there are no diurnal
effects. synthetic_trace is constructed with Poisson arrivals and must never be
presented as production data; it is reported alongside the others and excluded
from any verdict.
| conversation | toolagent | synthetic | |
|---|---|---|---|
| radix nodes | 15,787 | 27,253 | 4,177 |
| node size p50 / p90 / max, in blocks | 2 / 31 / 246 | 2 / 17 / 246 | 1 / 37 / 373 |
| cost per node, p90/p10 | 41.3x | 19.8x | 49.7x |
| cost per node, max/min | 825x | 825x | 1,695x |
| cost per byte, max/min (8B model) | 5.6x | 5.6x | 8.1x |
| cost per byte, max/min (70B model) | 3.3x | 3.3x | 4.6x |
Sizes and costs really are non-uniform — recomputation cost varies by nearly three orders of magnitude within a single trace.
But that spread is dominated by size, not depth. The quantity a GreedyDual-family policy actually ranks on is cost per byte, and that spans under one order of magnitude — and narrows on bigger models, because the linear term grows faster than the attention term. There is much less for a cost-aware policy to exploit here than the raw 825x suggests, and the measured 1 to 2 percent margins are the direct consequence.
Subtree sizes are extremely skewed. The conversation_trace root — a system
prompt present in all 12,031 requests — sits above all 182,790 blocks. Under
leaf-only eviction, reaching that node means first evicting essentially the entire
cache. That asymmetry is present in production data at extreme scale, not just in
constructed adversaries.
Cost as a multiple of the compulsory minimum. recursive_lru is omitted because
it is byte-identical to lru everywhere (see 7.4). cost_only and size_only
are Landlord with exactly one ranking term flattened — diagnostics, not proposals
— so each neighbouring pair differs in one term.
| Trace | Capacity | cost_only | gdsf | landlord | lru | size_only |
|---|---|---|---|---|---|---|
| conversation | 2 percent | 1.4113 | 1.4197 | 1.4288 | 1.4413 | 1.4368 |
| conversation | 10 percent | 1.2027 | 1.1192 | 1.1259 | 1.1432 | 1.2451 |
| conversation | 25 percent | 1.0779 | 1.0263 | 1.0232 | 1.0224 | 1.0946 |
| toolagent | 2 percent | 1.3823 | 1.3894 | 1.3943 | 1.4178 | 1.4374 |
| toolagent | 10 percent | 1.1635 | 1.0799 | 1.0855 | 1.1049 | 1.2519 |
| toolagent | 25 percent | 1.0538 | 1.0090 | 1.0078 | 1.0036 | 1.1123 |
| synthetic | 2 percent | 2.6513 | 2.6879 | 2.7014 | 2.7302 | 2.8373 |
| synthetic | 25 percent | 1.4706 | 1.5022 | 1.4926 | 1.5621 | 2.0462 |
No policy wins everywhere. Cost-ranked eviction is cheapest at the tightest capacity on all three traces; a frequency-aware policy takes over in the middle; plain LRU is cheapest at 25 percent on both real traces. The whole spread is 0.5 to 1.8 percent of total cost.
Ranking on size alone is harmful here, and that reversed a prior prediction.
Before these variants existed, the expectation was written down that size_only
would track landlord and both would lead cost_only and lru, reasoning from
the narrow cost-per-byte spread and from the fact that none of SGLang's seven
strategies ranks on size at all. The measured order is the reverse. size_only
is the worst policy on the board at almost every capacity on every trace. The
inference that "nobody ranks on size" identified a gap worth filling did not
survive contact with the data.
The likely mechanism, stated as inference and not as a result: because the cost range is driven almost entirely by node size, cost and size are strongly correlated here, so "evict the cheapest leaf" and "evict the largest leaf" are closer to opposites than to independent knobs. What the traces say is keep the large expensive nodes, and dividing by size partially cancels that signal.
Recursive LRU — proven k-competitive under DAG dependencies in published work —
is byte-identical to plain LRU on all three Mooncake traces, every field of
every replay at every capacity, and also on a fourth constructed non-Mooncake log.
There is an argument for why:
A request in a prefix cache is a single root-path. Every matched node except the deepest has a child on that same path, so at most one node per request is a leaf, and the newly admitted node makes the previously-deepest node interior anyway. Two distinct evictable leaves therefore always carry timestamps from two different requests, so the clock alone orders them, and the ancestor-ordering discipline never gets to break a tie.
This is measured and argued, not proven, and it is flagged for human review — the argument is short enough to be checked and should be.
Written into the plan long before the policies existed:
H1: Landlord's advantage on these traces survives because its credit mechanism carries no frequency term, so the short-lifespan critique of arXiv:2506.02634 does not apply to it.
Verdict: false, on the causal clause. Adding a frequency term to Landlord helps at 12 of the 14 real-trace capacity points where Landlord beats LRU.
The useful part is the attribution. GDSF and Landlord differ in two places at once, so their measured gap could not be assigned to either:
gdsf key = clock + freq * cost/size clock = key of last evicted
landlord key = rent + cost/size rent = max(rent, key of last evicted)
freq_landlord key = rent + freq * cost/size rent = max(rent, key of last evicted)
Inserting the missing middle row splits one unattributable gap into two exact
one-term steps. Across all 16 real-trace points, the frequency step reaches
0.0177 while the aging-rule step never exceeds 0.0018. The reason Landlord
trails GDSF is the one term it deliberately omits, and Landlord's max() — the
place the dependency constraint enters the aging rule — buys essentially nothing
on this workload. That is a fact about Mooncake, not about the model: on
constructed forests the two aging rules genuinely diverge.
The critique's premise holds and its conclusion does not follow. Only 24.2 percent (conversation) and 21.5 percent (toolagent) of distinct blocks are ever referenced more than once, and reuse is close-range — median distance 4 requests on toolagent. So for roughly four blocks in five a frequency term is definitionally uninformative. It still helps.
One measurement that is easy to misread. At 2 percent capacity, 97.6 percent and 98.5 percent of evicted nodes leave having been hit exactly once. The tempting reading is that the frequency term is idle. That reading is wrong: the evicted population is the complement of the protected one, so a frequency term that works produces exactly this histogram. This is an inference, not a result.
Two predictions were registered in advance. One was right — that the frequency term would help at 2 percent capacity. One was wrong — the LRU crossover was predicted between 2 and 10 percent capacity, and it is between 15 and 25 percent. A pre-registration reported only when it wins is not a pre-registration.
python scripts/h1_check.pyThis is the part of the repository most worth reading if you are deciding whether to trust it.
When the same author writes the code and its tests, passing tests can encode one misunderstanding twice. A component is done when its behaviour is confirmed against an oracle — an expectation that exists independently of the implementation — and the expectation is written down before the code.
| Rank | Oracle | Example here |
|---|---|---|
| 1 | External published ground truth | The trace table reproduces Mooncake's own published figures exactly |
| 2 | Mathematical invariant that cannot hold by coincidence | The optimum is at most every policy's cost; bytes conserved; capacity never exceeded; every block has exactly one parent |
| 3 | Established theory as a test | On flat traces, where the published theorem applies, the measured ratio must obey it. A violation is a bug in this implementation, never the theory's |
| 4 | Hand-computed known answer | A toy trace with per-policy cost worked out on paper before the code ran |
| 5 | Differential | Heap and linear-scan eviction agree byte-for-byte; the advisor reproduces the reference replay field-for-field |
| 6 | Self-written unit tests | Lowest rank. Necessary, never sufficient for a correctness-critical component |
No correctness-critical component is complete on rank-6 evidence alone. Where no oracle above rank 6 exists, that is stated rather than quietly downgraded.
Four invariants run inside the replay loop, raising rather than asserting so
that python -O cannot disable them: leaf-only eviction, byte conservation,
capacity, and determinism. Reaching the end of a replay is the assertion. A
violation is a bug in the simulator, never a curiosity to work around.
The dependency-constrained survey of the potential harness passed on its first draft. It passed because four of its twelve instances had capacity above their working set and never evicted at all — a check that passes because it never ran. That is recorded here rather than quietly fixed, and every survey case now reports its eviction count and is flagged as vacuous if it never evicts.
Separately, an arithmetic claim inside an otherwise correct argument — "the optimum pays one miss per phase" — was wrong by a factor that is 2x at the smallest cache size. It was caught by differencing the brute-force true optimum, not by re-reading the prose.
These checks catch wrong constants, wrong potentials and false theorems. They do not catch an unstated assumption, a flawed asymptotic argument, or a proof that is correct but proves something weaker than claimed. Verified means "survived the checks that exist", never "is true".
Full statement in proofs/model.md. An instance is
(F, size, cost, sigma, k, h).
- Forest
F = (V, parent).parent(u) = vmeansu's KV blocks were computed withv's resident, souis meaningless withoutv. The published dependency-caching work allows an arbitrary DAG; the model here specializes to a forest because that is what a prefix cache is — and this was measured to hold on all 409,914 distinct blocks rather than assumed. size(v), a positive integer. Integrality is the one restriction the underlying theorem requires, and KV blocks satisfy it naturally.cost(v), the price of recomputingvgiven its ancestors are resident — not the price of recomputing it from nothing.kis the online capacity andh <= kthe offline optimum's, both in size units, not item counts.
A cache state must satisfy ancestor-closure (if a node is resident, its parent is) and capacity. Ancestor-closure has an operational form that is the reason this is not the classical problem:
Leaf-only eviction. From an ancestor-closed state, the single-node removals preserving ancestor-closure are exactly those of nodes with no resident children.
So the evictable set is the leaf set of the resident subforest, and it changes as
eviction proceeds — evicting a node can make its parent evictable. This is exactly
what SGLang's evict() does when it re-pushes a parent onto the heap.
Five assumptions are named explicitly: demand paging with no bypassing, the in-service path is pinned, integer sizes, one request at a time, and capacity at least the deepest requested path — which is the floor the tool reports.
Two degeneracies, asserted as tests rather than claimed in prose: a flat forest recovers classical file caching, and unit sizes with unit costs recovers published dependency-aware caching. The first is the strongest available check on this implementation; the second keeps notation compatible and prevents an accidental scoop.
Landlord (Young 2002, Figure 1, transcribed verbatim):
Maintain a real value credit[f] with each file f in the cache.
When a file g is requested:
1. if g is not in the cache then
2. until there is room for g in the cache:
3. For each file f in the cache, decrease credit[f] by delta * size[f],
4. where delta = min over f in cache of credit[f] / size[f].
5. Evict any subset of the files f such that credit[f] = 0.
6. Bring g into the cache and set credit[g] to cost(g).
7. else reset credit[g] to any value between its current value and cost(g).
The transfer this project studies changes exactly one line: line 4's minimum ranges over the evictable nodes only, because line 5 can only evict a leaf. Line 3 keeps charging rent to the whole cache. That leaves one genuine degree of freedom, and it is flagged rather than settled:
| Variant | Line 3 charges | What breaks |
|---|---|---|
| all-resident (implemented) | every resident node | credit can go negative for interior nodes, since the minimum is over a strict subset. The published proof needs non-negative credit |
| leaf-only | evictable nodes only | credits stay in range, but the rent base shrinks, and the published proof needs the larger one |
Neither is claimed to work.
An implementation note that is a fact about the algorithm, not an optimization.
Rent decreases credit/size by the same amount for every resident node at once, so
the ranking by credit/size is invariant under line 3. Landlord is therefore
exactly "evict the minimum credit/size", implementable with a global aging term
and key L + cost/size. That is what makes a heap admissible: no node's key moves
when a different node is evicted. The equivalence is asserted in the tests
against a direct transcription of the rent loop, so the shortcut is verified rather
than argued.
Two lines of published work, neither sufficient alone. Every row was verified against primary source text, not a search summary.
| Work | What it proves | What it assumes away |
|---|---|---|
| Young 2002, On-Line File Caching (Landlord) | k/(k-h+1)-competitive for arbitrary integer sizes and arbitrary costs; best possible for a deterministic algorithm |
No dependencies. Any item is evictable at any time |
| Dallot et al. 2024, Dependency-Aware Online Caching | k-competitive under arbitrary DAG dependencies, with matching randomized bounds |
Unit size, unit cost |
| Bienkowski et al. 2017, Online Tree Caching | A tree-constrained bound | Unit cost, and the bound carries a height factor |
| Wu, Silwal and Zhang, ICLR 2026 | Leaf-LRU on a RadixAttention tree is Theta(B - L)-competitive; a randomized leaf policy is Theta(log(B - L))-competitive with a matching lower bound |
Unit token size, unit per-token miss cost |
| Cao and Irani 1997, GreedyDual-Size | k-competitive, k = cache size over smallest item |
No dependencies; a different theorem from Young's — the two must not be merged |
| RAGCache 2024 | Ships GreedyDual for KV caching over a knowledge tree, evicting the least-priority leaf | No competitive analysis of any kind |
Two details that are commonly misstated and are load-bearing: in Young's bound
k and h are capacities in size units, not item counts, and arbitrary
sizes together with arbitrary costs are fine for deterministic Landlord — the
unit-cost restriction people remember attaches to a different, randomized line of
work.
The gap is the conjunction. Dallot's own conclusion names it:
"it will be interesting to study dependency aspects in more general variants of caching, such as weighted caching or file caching"
where the cited reference is Young, On-line file caching. Dependencies without costs exists. Costs without dependencies exists. Prefix-tree leaf eviction under unit sizes and costs now exists too. The conjunction does not.
Written down before any proof was attempted, so that a negative result reads as a result:
| Branch | Trigger | Deliverable |
|---|---|---|
| A | The potential argument goes through, possibly with a worse constant (a height factor is expected; the tree-caching literature carries one) | The positive theorem |
| B | The dependency constraint turns out harmless and the published proof survives unchanged | Report honestly; the LRU-unbounded result becomes the headline |
| C | An adversary exploits forced-subtree-eviction to defeat every online policy | Impossibility plus a matching lower bound |
Branch C is a success, arguably the better paper. It closes the open problem just as definitively and is more surprising. This is written in advance specifically so that finding it is not mistaken for failure.
None of the three changes the tool. The advisor, the capacity curve, the lower bound and the pin list are identical under all of them. A branch-A theorem adds a sentence to the policy recommendation; branches B and C cost the product nothing.
Young's potential is implemented as code and checked after every event of the amortised argument, not per request, against a true-optimum schedule.
On flat instances, where the dependency constraint is vacuous and the published theorem applies verbatim, the harness is green across 4,784 replays with zero violations. That is the gate: it reproduces a known bound before being trusted on new mathematics.
On dependency-constrained forests, exactly one row breaks — and it is not the one the analysis leads with. The credit-floor row breaks on 8 of 12 surveyed cases across 34 events; the rent row did not break on any surveyed case.
Both halves matter. The obstruction is genuine and reproduces on demand: the rent minimum is taken over evictable nodes only, so an interior node gets charged past zero, measured at a raw credit of -1 on the smallest probe. The clamp that restores non-negativity is ours, not Young's, so every downstream row rests on a step the published proof never took. But twelve instances of at most eight nodes is a survey, not a search, and the surviving rent row is not evidence that the positive result holds. It only says where to look first.
python scripts/potential_check.pycache-worthy/
plan.md what is being built and why
CLAUDE.md how: verification discipline, tiering, gates
README.md this file
LICENSE Apache-2.0
Makefile check / verify / proofs / bench
.github/workflows/ci.yml hermetic check; verify with fetched traces
data/
raw/ Mooncake JSONL, gitignored, fetched by script
checksums.json committed; a fresh clone verifies rather than trusts
ATTRIBUTION.md provenance and privacy caveats
examples/
sample_log.jsonl constructed; the quickstart's first run
README.md says so, at length
src/cache_worthy/
cli.py `cache-worthy analyze`, argument parsing only
ingest.py a user's log to prefix paths, either shape
advisor.py the six-question funnel; measure, render, document
result.py the JSON document, and the table-vs-JSON reparse
workload.py question 1: the caching ceiling
capacity.py questions 2 and 3: the floor, the curve, the knee
pins.py question 6: shared prefixes worth holding resident
trace.py JSONL to Request
forest.py static offline prefix forest, radix-compressed
cost.py THE cost model, one definition
tree.py [1] online mutable radix forest; leaf-only eviction
simulator.py [1] the replay loop; invariants enforced with raises
policies/
base.py EvictionPolicy ABC, mirrors SGLang's interface
lru.py the deployed default
gdsf.py RAGCache's variant
recursive_lru.py Dallot
landlord.py [1] Young 2002 Fig. 1 under leaf-only eviction
ablations.py size-only / cost-only: diagnostics, not proposals
frequency.py freq-landlord: a diagnostic, not a proposal
bruteforce.py [1] exhaustive true optimum plus Belady
potential.py [1] Young's potential as an event-level checker
adversary.py the LRU-unbounded construction, runnable
scripts/
fetch_traces.py download and checksum
characterize.py reproduces the published trace table
plot_distributions.py structure and cost spread
replay_check.py real-trace simulator oracles
potential_check.py flat gate plus dependency survey
run_adversary.py the construction's checks, one command
h1_check.py the hypothesis test and its verdict
make_example_log.py regenerates examples/sample_log.jsonl
run_bench.py the advisor pointed at this project's own three
traces; also writes figs/capacity_curve.png
will_this_help_me.py the documented script path, plus its oracles
proofs/
model.md the formal model
related_work.md each work quoted from fetched source text
figs/ committed; regenerated by plot_distributions.py
and run_bench.py
tests/
[1] marks correctness-critical components: full typing, property-based tests,
and at least one rank-3-or-better oracle. A subtly wrong simulator produces
plausible wrong numbers that survive all the way into someone's capacity decision.
Deliberately mirrors SGLang's EvictionStrategy, so an upstream patch is one new
file implementing an existing interface rather than a new subsystem.
class EvictionPolicy(ABC):
@abstractmethod
def priority(self, node: Node, clock: float) -> float:
"""Lower is evicted first."""
def on_hit(self, node: Node, clock: float) -> None: ...
def on_insert(self, node: Node, clock: float) -> None: ...
def on_evict(self, node: Node, clock: float) -> None: ...
def on_split(self, upper: Node, lower: Node, clock: float) -> None: ...on_split is the one method added beyond SGLang's interface. A radix cache splits
nodes, and a split must not look like an eviction plus an insertion, or a node's
age resets for a reason the workload never caused. The default copies the parent's
state to the new child, matching SGLang's handling of last_access_time; for
Landlord that is provably the right rule, since copying the GreedyDual key is
identical to splitting the credit in proportion to size. GDSF takes the same rule
deliberately, so a modelling choice made in one policy and not another cannot
surface as a measured difference.
You can drop in your own policy and have the advisor score it against the seven shipped ones. This is deliberate: an upstream patch to give SGLang a registration hook is being written, and it would be incoherent to reproduce the limitation that patch is meant to fix.
The cost function used in the proofs and the one used in the simulator are the same object. Theory-implementation drift is a standard failure mode in theory-plus-systems work and it invalidates results silently.
Prefilling n tokens through a decoder-only transformer, per layer, counting
multiply and add separately:
projections and FFN 2 FLOPs per parameter per token -> 2*N*n
attention scores heads * (n^2/2 causal pairs) * 2 * d -> n^2 * d_model
attention-weighted V same shape -> n^2 * d_model
cost(n) = a*n + b*n^2 with a = 2N, b = 2 * n_layers * d_model
a and b are derived from published architecture constants, not fitted, and
the derived non-embedding parameter counts are checked against the published model
sizes, so a mistyped constant cannot pass silently. A node's cost is the difference
form prefill(end) - prefill(start), which is exact rather than approximate: the
causal pairs whose query lies in the range number exactly (end^2 - start^2)/2.
No theorem depends on a or b. The advisor's output does — which is why both
target models are reported and why a sensitivity band is a gate rather than a
nicety.
Not built yet, and the method is chosen for a reason. The standard offline 4-approximation for weighted caching is proven without dependencies, and there is no reason to assume it transfers. Rather than assume it:
- Formulate dependency-constrained offline caching as an integer program.
- Drop the dependency constraints — valid, because the constrained feasible set is a subset, so the unconstrained optimum is at most the true optimum.
- Relax integrality — valid, because the LP optimum is at most the integer optimum.
The result is a provable lower bound. Reporting a policy's cost against it overstates the true ratio, which is the conservative direction: it lets the tool say "at most this much is recoverable" and be right. For policy-versus-policy comparison the bound cancels, so relative comparisons stay exact.
from cache_worthy.cost import DEFAULT_MODEL, kv_bytes, segment_cost
from cache_worthy.policies import POLICIES
from cache_worthy.simulator import replay
from cache_worthy.trace import BLOCK_SIZE_TOKENS, load_trace
requests = load_trace("data/raw/conversation_trace.jsonl")
paths = tuple(r.hash_ids for r in requests)
def size(block_ids, depth):
return kv_bytes(len(block_ids) * BLOCK_SIZE_TOKENS, DEFAULT_MODEL)
def cost(block_ids, depth):
start = depth * BLOCK_SIZE_TOKENS
return segment_cost(start, start + len(block_ids) * BLOCK_SIZE_TOKENS, DEFAULT_MODEL)
result = replay(paths, POLICIES["landlord"](), capacity=200 * 2**30,
size_fn=size, cost_fn=cost)
print(result.total_cost, result.compulsory_cost, result.block_hit_rate)replay enforces every invariant as it goes, so reaching the end of a replay is
the assertion. Heap and linear-scan eviction are byte-for-byte equivalent: the scan
is the obvious-correctness reference, the heap is SGLang's structure.
from cache_worthy.bruteforce import Instance, optimal_cost
instance = Instance(
parent=(None, 0, 0, 1), # 0 -> 1 -> 3, and 0 -> 2
size=(1, 2, 1, 3),
cost=(4.0, 1.0, 7.0, 2.0),
requests=(3, 2, 3, 2),
)
print(optimal_cost(instance, capacity=6)) # exact, not an approximationfrom cache_worthy.potential import check_potential
report = check_potential(instance, k=6, h=6, keep_events=True)
print(report.summary())
for violation in report.violations:
print(violation.describe()) # which row broke, at which event, and by how muchgit clone <this repo> && cd cache-worthy
python -m venv .venv && . .venv/bin/activate # or .venv/Scripts/activate
pip install -e ".[dev]"Four gates, each meaning something different:
make check # lint, types, tests. Hermetic: no network, no data.
make verify # cumulative milestone oracles. Needs the real traces.
make proofs # mathematical oracles.
make bench # headline numbers: the advisor, pointed at the three traces.make verify is cumulative: it re-runs every completed milestone's oracles,
so a later change that breaks an earlier guarantee fails immediately. It fails
loudly rather than skipping if the trace data is absent.
Individual steps:
python scripts/fetch_traces.py # 3 traces, about 8.5 MB, records SHA-256
python scripts/characterize.py --check # against Mooncake's published table
python scripts/plot_distributions.py # regenerates figs/, prints section 7.2
python scripts/replay_check.py --check # simulator oracles on real traces
python scripts/potential_check.py # flat gate plus dependency survey
python scripts/h1_check.py # the section 7.5 hypothesis test
python scripts/run_adversary.py # the LRU-unbounded construction
python scripts/make_example_log.py # regenerate examples/sample_log.jsonl
python scripts/run_bench.py # headline numbers, figs/capacity_curve.png
cache-worthy analyze LOG # the advisor, on your own logEverything runs on a laptop CPU. Expected cloud spend: zero.
Environment note.
makeis not onPATHon every Windows machine; MSYS2'smingw32-makeworks and is what this repository is developed against. Makefile recipes are written shell-agnostically, one command per line with no POSIX-only constructs, so they run identically undermingw32-make, GNUmakein CI, and any contributor's shell.
- Python 3.13.
rufffor lint and format, default rules, not hand-tuned.mypy --strictonsrc/andscripts/. - Full type annotations in
src/. Frozen slotted dataclasses for value types. - Docstrings state why, and cite the paper and section for anything implementing a published algorithm.
- Determinism: seed everything; no wall-clock or dict-ordering dependence in any result.
- Simplicity is the default and needs no justification; complexity must be triggered in writing at the point of introduction. No abstraction before the second use case. Dependencies are a fixed short list. No Rust until a measured wall-clock trigger fires, and never for the simulator loop.
- Rigid core, flexible edges. The simulator, tree, cost model and shipped policies are fixed and oracle-covered. Log adapters, user-supplied cost constants and third-party policies are injected through existing interfaces, validated at the boundary, and explicitly outside oracle coverage — and the output says which numbers came from which.
- Git hooks (
core.hooksPath = .githooks): commit runsmake check, push runsmake verify. Committed, so they survive a fresh clone. - No emoji anywhere in the repository.
Every numeric claim in this file or in proofs/ traces to a committed script that
regenerates it.
This section exists so that nothing above it gets quoted out of context.
- No theorem in this repository has been proven. "Verified" means it survived the automated checks that exist. It never means "is true".
- The positive result is human-gated. It may not be described as proven anywhere — including in this file — until a human mathematician has read it and agreed. That gate is not a formality: the specific failure mode it guards against is a confident, locally plausible, globally wrong amortised argument, and this project's contribution is exactly the kind of result that failure mode produces.
- What may be claimed, once earned: a competitive-ratio guarantee for dependency-constrained caching with non-uniform sizes and costs. That qualifier is load-bearing and may not be dropped — an ICLR 2026 result already holds the unqualified ground for prefix-cache eviction under unit sizes and costs.
- What may never be claimed: "provably optimal" (the offline optimum here is NP-hard and every online policy has a lower bound against it); "first cost-aware KV eviction" (RAGCache); "first leaf-constrained competitive analysis" (Bienkowski, Dallot); "first guarantee for a deployed policy" (nothing here is deployed); or any merging of Young's bound with Cao and Irani's, which are different theorems.
- Numbers here are external ground truth, measurements of the input data, or measurements of code behaviour — never a project result dressed as a proof.
- The cost coefficients are analytic, not measured on hardware. They come from a FLOPs derivation over published architecture constants. A GPU validation run is optional and gates nothing. No theorem depends on them; the advisor's output does, which is why both target models are reported.
- The tool reports prefill FLOPs, not latency. Do not convert.
- Constructed data is never presented as production data.
synthetic_traceis reported and excluded from every verdict. - The measured policy margins are 0.5 to 1.8 percent of total cost, on two real traces from one source spanning one hour. That is why the tool leads with capacity.
- Predicting your own negative results is a credibility signal. A pre-registered hypothesis was tested and found false (section 7.5); a pre-registered expectation about the size channel was reversed by the data (section 7.3); and one of two registered predictions was wrong and is reported as wrong.
Learned or predictive policies, which destroy the guarantee that is the point. Multi-replica and distributed caching. CPU and disk tiering. Online self-tuning.
The cache-worthy code is Apache-2.0 — see LICENSE, matching the
declaration in pyproject.toml. The Mooncake trace data is
separately licensed Apache-2.0 by its authors — see
data/ATTRIBUTION.md for full provenance, including the
privacy and representativeness caveats that apply to it.