The bookkeeping floor for a shared KV cache
Bits of state a shared cache needs to answer exactly who may reuse which block, for T customers and n blocks
- Any customer may be granted any block
- at least T·n
- Each block belongs to one customer (the model the lab says ships)
- n · log₂ T
A condition on state only: it says nothing about timing or content channels.
A shared KV cache that never leaks between customers and still lets any customer reuse any block must keep at least one bit of state per customer and block; checked in Lean, for a model the lab says does not ship
What it does not claim
The T·n floor is for the dense model, where any customer may be granted any block, not for the model the lab says ships, where each block belongs to one customer. It is a necessary condition on state only. It does not cover timing channels, content channels or probabilistic isolation. It is not an independent proof: it composes an earlier result of the lab's. The counting itself is textbook. The Lean source is published; the rest of the lab's code is not public yet.
The limits, in the lab’s words:
T*n is the DENSE rights model; the one-tenant-per-block model that ships pays n*log2(T), exponentially smaller, and is composed separately here.
NEG-F5-35 applies: this file imports IsolationBound and calls inj_le, so it is a COMPOSITION, never an independent proof.
The pigeonhole is classical.
Excerpts, word for word from the published file, where the full text can be read.
When many customers share one KV cache, the cache must remember which customer may use which stored block. The lab asked how small that memory can be, if the cache must never serve a block to a customer who may not have it and must let every allowed customer reuse every block. Its answer is a counting bound, checked in Lean, for the case where any customer may be granted any block.
What it shows
In this model: a shared cache over T customers and n stored blocks, where each customer may or may not be allowed each block, and the cache's state must answer that question exactly.
If the cache never serves a block to a customer who may not have it, and lets every allowed customer reuse every block, its state must be able to tell apart every possible pattern of permissions. There are two to the power T·n such patterns, so the state needs at least T·n bits. Lean checks this for every T and n.
What it does not reach
The bound is about state, not about leaks through time or content. It also assumes the dense case, where any customer may be granted any block. When each block belongs to exactly one customer, as in the model the lab says ships, the floor drops to n times the base-two logarithm of T, which the lab composes separately.
Why it matters, and to whom
For teams that build multi-tenant serving with a shared prefix cache, the bound says what exact per-customer access control costs in memory before any design is chosen: with arbitrary sharing, the bookkeeping grows with customers times blocks. A design that wants less must restrict who may share what, and the one-customer-per-block case shows how much that saves.
Why now
Some providers share prompt caches across requests and customers, and others state that they do not; researchers have shown that shared caches can leak between users, as the admission-gate page on this site explains. Exact per-customer rules are the obvious fix; this bound prices them.
How it was checked
The theorem is in a Lean file, EssentialBits.lean, published here beside its certificate, and the lab's result file lists the axioms it rests on. The lab notes that this file builds on another proof of its own rather than standing alone, and that the counting is classical.
How to reproduce
The measured results name the lab's Lean file and the commit it was read at, and the lab's claim and limits are published word for word. The home page's theorem section prints the same floor beside its certificate. Each file is listed with its hash in the site's receipt manifest.
The bound
In words: each customer-and-block pair can independently be allowed or not, so there are two to the power T·n possible permission patterns, and a cache that must answer exactly for every pair has to tell them all apart. That is the pigeonhole principle, applied to the cache's state. Both conditions are needed: a cache that only has to avoid leaks can keep no state at all and refuse everything.
The result, in the lab’s exact words
Read it with this condition: the bound is for the dense rights model, where any customer may be granted any block. In the model the lab says ships, each block belongs to exactly one customer and the floor is n times the base-two logarithm of T, far smaller. It is a condition on the cache's state only: it says nothing about timing or content channels.
A zero-leak AND full-reuse pooled-KV policy over T tenants and n cache blocks needs at least 2^(T*n) states, i.e. at least T*n bits, as one machine-checked theorem general in T and n.
Quoted word for word from the lab’s published claim and limits.
Prior art
- Pigeonhole principle (Wikipedia): the counting argument the bound rests on
- Theorem Proving in Lean 4, "Axioms and Computation": the standard axioms a Lean proof may rest on, which this proof's audit lists
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.