The KV Cache Is the Whole Problem

Every part so far has been circling this one. Part 0 established a pool of roughly 3.8 GiB. Part 4 worked out how to make it bigger. This post is about what actually goes in it, and about the fact that on one machine the pool is not a resource each tenant has — it is a resource they are all in.

---

Why it dominates

Weights are fixed. You load them once, they never grow, and after Part 0’s arithmetic they are simply gone from the budget. The KV cache is the opposite: it grows with every request admitted and every token generated, and it is released only when a sequence finishes.

Its size follows a formula worth being able to write down:

bytes per token = 2 × layers × kv_heads × head_dim × bytes_per_element

The 2 is keys and values. The rest is architecture, and Gemma 4 12B’s is unusual enough that the formula has to be applied twice.

The retraction

An earlier version of this post carried a warning arguing the opposite of what the numbers say. It claimed that if Gemma 4 12B used sliding-window attention, then windowed layers would cap their KV contribution and this would “make long-context requests far cheaper than Part 0 implied, and the worry substantially wrong.”

The sliding windows are real and the conclusion was wrong. The eight full-attention layers use head_dim 512 — double the sliding layers — so they cost 128 KiB per token and never stop growing. A 256K-token context needs about 32.3 GiB of KV cache, which is more than the chip’s entire 28.7 GiB of usable HBM, let alone the ~3.8 GiB pool.

Windowing helps enormously in relative terms: at a uniform head_dim of 256 across all 48 layers the same context would need roughly 96 GiB. It does not help in the terms that matter. Part 0’s worry was correct, and the correction to it was the error.

What the pool actually holds

With real numbers rather than adjectives, at bf16 and a ~3.8 GiB pool:

• ~8,894 tokens of KV in total, across every tenant at once
• ~28,570 tokens for the longest single sequence that fits
• ~12 sequences is the hard ceiling from the 320 MiB-per-sequence sliding-layer floor alone, before a single token of global-layer cache

Part 0 said “a handful of concurrent tenants”. Twelve is the ceiling, and they would have to be short. The pool is tighter than this series had been assuming, which does not change any of the mechanisms below — it raises the stakes on all of them.

---

PagedAttention: making the pool accountable

The naive way to store a sequence’s KV is contiguously — pick an address, reserve space for however long the sequence might get, fill it in as you go.

Reserving versus paging the same pool

The problem is the reservation. You do not know how long a response will be when you start it, so you reserve for the worst case, and the difference between reserved and used is stranded: unusable by anyone else for as long as that sequence lives. Three sequences holding nine blocks of real data can occupy a pool that would have fit eighteen.

PagedAttention borrows the fix from virtual memory. Split the pool into fixed-size blocks, let a sequence’s blocks be scattered anywhere, and keep a block table mapping logical positions to physical blocks. A sequence allocates a block when it needs one and not before. Waste drops to at most one partly-filled block per sequence.

The performance win is what gets written about. For this series the more important consequence is different:

---

Prefix caching, and the part that is a security question

If two requests share a prefix — and in multi-tenant serving they very often do, because everyone gets the same system prompt prepended — then the KV blocks for that prefix are identical. Computing them twice is waste, and storing them twice is worse waste on a 3.8 GiB pool.

Prefix caching keeps blocks keyed by the content that produced them, so a second request with the same prefix maps straight onto the existing blocks. The prefill it skips is real work not done, and the memory it saves is real pool not spent. In a deployment where one long system prompt is shared across every tenant, this is one of the largest wins available.

Now the part that is easy to miss.

If blocks are shared across tenants by content hash, you have built a side channel. Tenant B can test whether a particular prefix is already cached by sending it and timing the response — a hit skips prefill and returns measurably faster. That is a mechanism for asking “has anyone else recently sent this exact text?”, and depending on what your tenants send each other’s users, that ranges from harmless to a serious disclosure.

The mitigations are not complicated, but they have to be chosen deliberately:

• Scope the cache per tenant. Safe, and gives up the cross-tenant sharing that made it valuable.
• Share only known-public prefixes. The system prompt you control is shared; anything tenant-supplied is scoped. This keeps most of the win and is where I would start.
• Share freely and accept it. Defensible only if your tenants are not mutually distrusting — which, in a system whose whole premise is isolating tenants from each other, is a strange thing to conclude.

I have not seen this discussed much in serving write-ups, and the default configuration in most engines is the permissive one. On a single shared machine the question is unavoidable: there is no hardware boundary between tenants, so the cache is exactly as shared as you let it be.

---

Budgeting a pool nobody owns

Here is the shape of the problem. Every tenant allocates from the same blocks. There is no partition in hardware. A tenant that opens many long sequences will hold many blocks, and blocks it holds are blocks nobody else can have.

The design space is small and the trade-off is the same one every time:

Free-for-all. No per-tenant accounting; first come, first served. Maximum utilization, zero isolation. One tenant with a burst of long requests can take the entire pool and every other tenant stalls. This is the default in most engines, and it is fine right up until it isn’t.

Static partitions. Each tenant gets a fixed share of blocks. Perfect isolation, and it wastes whatever a quiet tenant isn’t using — which on a pool this small is most of it, most of the time. Paying a large permanent cost to bound a rare event.

Reservation plus burst. Each tenant gets a guaranteed minimum it can always obtain, and may use surplus beyond that when the pool is idle. Surplus is reclaimable; the guarantee is not. This gets you most of the utilization of a free-for-all and most of the isolation of a partition, at the cost of being the only one of the three that requires thinking about reclamation.

The third is almost always the right answer, and the reason it isn’t the default is that it needs an eviction policy, which is the next problem.

---

What happens when the pool is full

A request needs a block, there are none. Something has to give, and there are two ways to give it.

Recompute. Drop a victim sequence’s blocks entirely and, when it is next scheduled, re-run prefill to regenerate them. You pay the prefill cost again, and prefill is the compute-bound phase the hardware is comparatively good at.

Swap. Copy the victim’s blocks out to host memory over PCIe, and copy them back when it resumes. You pay the transfer, twice, over the link that Part 2 noted is orders of magnitude slower than HBM.

My expectation — and it is an expectation, not a measurement — is that recompute usually wins on this hardware, because prefill is well-suited to the MXU while a PCIe round trip is exactly what the machine is worst at. But it depends on the sequence’s length, on how loaded the chip is when it resumes, and on whether prefix caching means the recompute is partly free. The crossover is measurable and I do not know where it is.

The choice of victim is the more interesting question, and it is a fairness question rather than a performance one: evicting the largest sequence frees the most blocks fastest, and also reliably punishes whichever tenant is doing the most legitimate work. That belongs to Part 6.

---

What the hardware has to settle

• The attention configuration, and therefore the real bytes-per-token — answered above, and against my guess
• Whether the 320 MiB-per-sequence sliding-layer floor is really paid in full, or whether the engine allocates windowed layers lazily until a sequence reaches 1024 tokens
• Prefix cache hit rate under a realistic multi-tenant workload, which decides whether it is a large win or a rounding error
• Actual fragmentation under paging, and whether one partly-filled block per sequence is really the whole cost
• Where recompute stops beating swap
• Whether reservation-plus-burst holds isolation under a deliberately abusive tenant, which is the only test of it that means anything

---

Part 6 is next, and it is where all of this becomes policy: continuous batching, priority tiers, per-tenant rate limits, and choosing who to evict — the point at which multi-tenancy stops being a property of the hardware and becomes a set of decisions somebody has to write down.