What a cache hit rate is
A cache hit rate is the share of lookups that find what they need already in the cache.
A single request makes many lookups, one for each block of its prompt. A lookup that finds the saved block is a hit, and one that does not is a miss. The first post in this series explains why a hit saves real computation. The hit rate is therefore the number that turns a cache into money: every hit is prompt work that no GPU has to repeat.
The Mooncake trace is a public record of requests to a production conversation service. Each line gives an arrival time, the lengths of the request and its reply, and a list of anonymized block identifiers. Two requests that share an identifier share a block they could reuse. The trace holds no text.
The lab works from an excerpt of that trace and sets part of it aside as a held-out test stream. All the numbers below are measured on that stream.
Why the first lookup must miss
A cache that fetches only what a request asks for has nothing stored before the first request for a block, so the first lookup of every block must miss.
That gives a ceiling. The most a cache of this kind can hit is the share of lookups that are repeats. A stream in which no block ever returns has a ceiling of nothing, whatever the cache. A stream that loops over a few blocks forever has a ceiling close to every lookup. Real traffic sits between the two, and the trace shows where.
Here is how it works out on the held-out stream:
- It holds 21,069 lookups.
- Those lookups touch 16,930 different blocks.
- Each different block must miss once. That leaves a ceiling of 19.645% on the hit rate of any cache that fetches only on request and starts empty.
Such a cache is called a demand cache. The idea is old. The first access to a block is a compulsory miss, a standard topic in computer architecture courses that a Berkeley lecture defines. What the lab did was prove the statement in Lean, a proof checker, for every trace and every demand policy, and then evaluate it on this trace. A statement proved in Lean has been checked by a program, not only by people.
How far an ordinary cache falls below it
On this trace a simulated least-recently-used cache reaches only a fraction of the ceiling, and the gap is the room a better policy could use.
Two simulated policies show where designs land. Belady’s policy, set out in a standard textbook chapter, is the offline ideal. It evicts the block that will be needed furthest in the future, which needs knowledge of the future, so only a simulator can run it. Least recently used (LRU) evicts the block used longest ago and needs no foresight. LRU does well when a block returns soon after its last use. When blocks return after a long gap, LRU has already dropped them.
The lab’s claim gives two cache sizes:
- At 1,693 blocks, Belady reaches the ceiling and LRU reaches 5.497%.
- At the smallest size the lab swept, 423 blocks, Belady reaches 12.687% and LRU reaches 4.059%.
- offline ideal (Belady)
- least recently used
- proven ceiling, 0.19645
The share of lookups served from the cache at each cache size the lab swept, as a fraction of all lookups. The rust line is the proven ceiling. The text above gives the same shares as percentages. The values come from the certificate behind the chart.
Read the two sizes together. At the larger size even the offline ideal only just reaches the ceiling, so the whole gap between LRU and the ceiling belongs to the policy. At the smaller size the cache is too small for even the ideal to reach it. There, size is the limit, not policy.
Every policy number here comes from a simulation that starts with an empty cache and runs over the held-out stream. None of them is a deployed cache.
What a prefetching cache can do that the ceiling does not cover
A cache that can fetch blocks before they are asked for sits outside the ceiling, and the lab’s certificate proves a case where a prefetching policy beats it.
The limit to demand policies is therefore shown, not assumed. A prefetching cache would have to know, or guess, what will be asked next. Knowing costs something, and a wrong guess wastes bandwidth and space. The ceiling says nothing about how well anyone can guess.
The Mooncake paper reports reuse over its whole trace. The ceiling here is for the held-out part of the lab’s excerpt, counted from an empty cache, so the two measure different things. Do not read one as a check on the other.
How to use a ceiling when you plan capacity
Work out the ceiling from your own traffic before you buy cache. It bounds a demand cache counted from an empty start on that traffic; a cache that is already warm can go above it.
- Count every lookup in a sample of your traffic, one per block of each prompt.
- Count how many different blocks those lookups touch.
- The share of lookups that are repeats is your ceiling. A cache that starts empty and fetches only on request cannot hit more often than that.
- Compare your measured hit rate with it. The gap is what a better policy or a bigger cache might still win.
A low ceiling is a finding too. On a long enough sample, it means no demand cache that starts empty will cut your cost much on that traffic; a cache that starts warm can do better, so check warm behaviour before deciding. A high ceiling with a low hit rate points at the policy or the size of the cache.
What this means for you
A ceiling turns a hit rate from a number into a judgment, and it matters to anyone who buys, sells or checks cached inference.
- Inference providers. Compute the ceiling for each workload before you promise a cache discount. A promise above the ceiling cannot be met by a demand cache that starts empty on that traffic. A warm cache that runs continuously can go above a ceiling counted from an empty start.
- GPU clouds. If you price cached tokens, price them against what the traffic allows, not against a best case.
- Enterprise AI platforms. When a vendor quotes a hit rate, ask what the ceiling is for your traffic, and how close the quote is to it.
- Auditors. A quoted hit rate has a ceiling to check it against. Ask for the trace, the count of lookups and the count of different blocks.
What this does not show
This is one held-out stream from one public trace, and every policy figure is a simulation.
- The ceiling covers demand policies only. A prefetching policy can beat it.
- It describes this trace. A different workload has a different ceiling, so it is no forecast for yours.
- No deployed cache was measured. LRU and Belady are simulated here.
- It does not compare with the reuse the Mooncake paper reports over its whole trace.
The lab’s own limits for this result, word for word
A ceiling on DEMAND policies only — prefetching escapes it, and the certificate proves that rather than assuming it.