The Mooncake trace: a proven hit-rate ceiling

The Mooncake trace is a public record of requests to Mooncake, a production model-serving system; the lab works from an excerpt of it kept with its code, and sets part of that excerpt aside as a test slice. A demand cache is one that fetches a block only when a lookup asks for it. The lab proved a ceiling on the share of cache-block lookups that any demand cache starting empty can serve from memory on that test slice. It then simulated the offline ideal, Belady's policy, and least-recently-used caching to show where each lands.

What it shows

In this model: a demand cache, one that fetches a block only when a lookup asks for it, starts empty and serves the test slice of the lab's excerpt of the Mooncake trace. A reference is one lookup of one cached block; a request usually makes many of them. Lean is a proof checker: a statement proved in it has been checked by a program, not only by people.

Why the first lookup must miss

A demand cache fetches a block only when a request asks for it. The first request for any block must miss, because nothing can be in the cache before it is ever asked for. So on any trace, the share of hits can never exceed the share of references that are repeats.

The lab proved this in Lean for every trace and every demand policy, then computed the ceiling for the test slice of the Mooncake trace, the part kept apart from the rest for evaluation. The lab's claim, quoted below, gives the ceiling and the counts behind it.

Two policies, simulated

The claim reports two of the simulated policies, each run from a cold start:

• Belady's policy is the offline ideal, as the textbook chapter cited below explains. It evicts the block that will be needed furthest in the future. That gives the fewest misses, but it needs knowledge of the future, so only a simulator can run it.
• Least recently used (LRU) evicts the block that was used longest ago; it needs no knowledge of the future.

A cold start means each cache begins empty. The claim reports both at two cache sizes. Belady reaches the ceiling only at the larger size; LRU stays far below it at both.

Why it matters, and to whom

For teams that build or run serving engines with a shared prompt cache, the ceiling separates two questions. How much better could any demand policy do on this trace? And how much is lost to the policy in use? At the larger cache size, where the offline ideal reaches the ceiling, the gap between LRU and the ceiling is the most a better demand policy could win. At the smaller size even the offline ideal stays below it; the claim gives both.

Above the ceiling

No demand cache that starts empty can go above the ceiling; the lab also proved that a prefetching policy can beat such a ceiling. The Mooncake paper reports reuse over its whole trace; this ceiling is for the test slice of the lab's excerpt, counted from an empty cache, so the two are not the same measure.

Why now

Providers now sell prompt caching to their customers, and some explain how it works, as in one provider's prompt-caching guide. Cached-token pricing makes the hit rate matter to what customers pay. A ceiling computed from the traffic itself tells a buyer which hit rates a demand cache that starts empty cannot reach on that traffic, before any cache is built. A cache that starts warm, or one that prefetches, can go higher, so the ceiling does not bound those. The theorem holds for every trace, so it can be evaluated on a buyer's own traffic, which has its own ceiling.

How it was checked

The ceiling is a Lean theorem evaluated on the trace. The policy figures are simulations, and the limits say so. The claim reports each cache size separately.

How to reproduce

The published results file names the command that regenerates the certificate, the file of computed values the claim rests on, and the commit it was read at. Anyone with access to the lab's code, which carries its excerpt of the trace, can rerun it. The lab's code is not public yet. The proof itself is: read the Lean proof of the ceiling and its certificate, which the verifier on the home page can confirm, in your browser, are the unaltered published files. Each receipt file named on this page is listed with its hash in the site's receipt manifest, so a downloaded copy can be checked byte for byte.

In words: take a trace τ with N references to d distinct blocks. Every demand policy π starting from an empty cache must fetch each block at least once, so at most the remaining references can hit. This is the classical bound on compulsory misses; the lab proved it in Lean for all traces and all demand policies, then evaluated it on this trace.