Pooled cache placement: a solver-certified optimum
Misses on one fixed test instance, one block per miss
The pooled cache: 32
The fewest possible, proved by an outside solver (Google OR-Tools): 32
Pooled cache placement reaches a solver-certified optimum on one fixed test instance
What it does not claim
It is one uncapacitated instance, not a fleet benchmark, so it says nothing about caches that must evict. It does not claim that pooling is optimal at any scale. Pooling cached work across servers is itself published design, as in the Mooncake paper cited below.
The limits, in the lab’s words:
ONE committed instance, not a fleet benchmark — the CP-SAT certification is of THAT instance and the Lean half is the general statement; they are separate objects and must not be merged into "provably optimal at any scale".
Excerpts, word for word from the published file, where the full text can be read.
When a fleet of model servers shares one pool of cached work, instead of keeping a separate cache on each server, a prompt opening computed on one server can be reused by the others. On one fixed test instance that the lab's code builds, pooled placement reached the fewest misses possible in the lab's model of it, and an outside solver confirms it.
What it shows
In this model: one fixed instance that the lab's code builds, a set of requests over prompt openings on a group of hosts. It is uncapacitated: each host keeps everything it fetches. The optimum is of the lab's model of that instance.
A large language model server keeps a key-value (KV) cache of work it has already done on prompts. In a fleet, each server can keep its own cache, or the servers can share one pool.
- With separate caches, the same opening of a prompt is computed again on every server that sees it.
- With a pool, it is computed once and, as long as the pool keeps it, fetched by the others.
One instance, counted exactly
The lab took one fixed test instance: a set of requests, prompt openings and hosts, built by its code. The instance is uncapacitated: hosts keep what they fetch, with no cap on how much each can hold. It counted the misses, meaning the times a request found nothing to reuse. Pooled placement reached the count given in the lab's claim, quoted below.
The lab then gave the same instance to CP-SAT, the constraint solver in Google's OR-Tools suite. The solver returned a proven optimum equal to that count. So in the lab's model of this instance, no placement, pooled or not, can do better.
What the optimum counts
That optimum is also the number of distinct prompt openings in the instance. With no cap on what a host holds, the pool misses only the first time each opening appears. No demand cache that starts empty can avoid those misses; a demand cache is one that fetches only what a request asks for. They are the compulsory misses of the lecture cited below, which also lists prefetching among its ways to reduce misses. The solver confirms that floor independently.
Why it matters, and to whom
For teams that run serving fleets or build cache-sharing layers, the instance makes one point exactly. Separate caches on each server pay again for the same opening on every server that sees it; a pool pays once, and on this instance that reaches the fewest misses possible. Because there is no cap on cache size, any pool that never evicts reaches the same floor, so the instance does not rank one pooling design against another.
Why now
Serving systems now pool cached work across many servers instead of keeping it on each one, as the Mooncake design cited below does. A team deciding between a pool and separate caches wants to know what the separate caches give up. On this instance the answer is exact, because the solver proves the pool's count is the floor. A harder test, with a cap on cache size so that caches must evict, is not published yet.
How it was checked
The optimum comes from the outside solver, which reports both a solution and a matching proven bound. The published results file records the command that regenerates the certificate. A separate Lean statement is the general half: a lower bound on fleet misses for every routing, demand policy and trace. Lean is a proof checker, and a routing decides which host serves each request. No file we publish shows that general statement as proved, so this page does not rely on it. The lab keeps the two apart, as the limit below says.
How to reproduce
The published results file names the command that regenerates the certificate, including the solver run, and the commit it was read at. Anyone with access to the lab's code and OR-Tools can rerun it and compare. The lab's code is not public yet; the certificate itself is, and the verifier on the home page confirms, in your browser, that it is the unaltered published file. 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.
The result, in the lab's exact words
Read it with this condition: the committed instance is the one fixed test instance described above, and it has no limit on cache size. There the optimum equals the number of distinct prompt openings, so optimal means only that the pool pays no misses beyond the unavoidable first lookup of each opening; any pool that never evicts would do the same. The solver is outside software, but the model and the instance it solved were built by the lab's own code.
On the committed instance, pooled KV placement achieves 32 misses and Google OR-Tools CP-SAT independently returns OPTIMAL with a matching proven bound of 32 — so pooling is not merely better than per-instance caching, it is optimal.
Quoted word for word from the lab's published claim and limits.
Prior art
- Qin et al., "Mooncake: Trading More Storage for Less Computation" (Conference on File and Storage Technologies, 2025): a serving architecture built around a shared pool of cached model state
- David A. Patterson, "Memory Hierarchy: 3 Cs and 7 Ways to Reduce Misses" (Berkeley course lecture): the classical kinds of cache miss, including the compulsory miss on a block's first access
- Google OR-Tools, the CP-SAT solver: the constraint solver used to certify the optimum
Evidence
- The measured results behind this page, read from the lab's own files at a named version.
- The lab's current claim and limits, word for word.
- Every file this site publishes.