Operating-system virtual memory applied to attention, the prefix that was already computed yesterday, and one flag worth exactly two times.
Cache memory caps concurrency, and concurrency caps throughput. None of what follows makes the model better. All of it makes the same hardware serve several times as many people — which is why a serving engine is 14 to 24 times a research library on identical silicon.
Each request books a block sized to the maximum sequence length.
Five hundred users, five hundred copies of the same system prompt.
Yesterday’s prefill thrown away and done again today.
The naive way is booking every guest an entire floor in case their family shows up. Paging gives each guest one room and hands them another only when someone actually arrives.
Block sharing is noticing that two people are photocopying the same document at the same moment and giving them one copy.
Prefix caching goes further: keeping the photocopy so tomorrow’s person does not have to make it at all.
The paper draws the analogy itself: blocks are pages, tokens are bytes, requests are processes. The idea is sixty years old; applying it here is what was new.
Four requests using 300, 2,000, 600 and 4,400 tokens of an 8,192 limit.
63% of the reserved memory untouched — and no fifth request can be admitted.
Fixed 16-token blocks handed out on demand, anywhere in memory.
Maps each sequence’s logical positions to physical blocks.
Kills external fragmentation entirely — every free block fits every need.
Caps internal waste at 15 tokens per sequence.
Identical blocks can be shared between requests rather than duplicated.
Free memory becomes more cache. More cache means more sequences resident. More sequences means a bigger batch. A bigger batch means the weights are read once and used for far more tokens.
The results are bit-for-bit identical. It is a memory-management change with a matching attention kernel that knows how to read from scattered blocks.
The same 2,000-token system prompt. Byte-for-byte identical.
Both sequences’ block tables point at it.
0.24 GiB per additional request — and the prefill too.
A sequence that needs to write into a shared block gets its own copy first.
Shares blocks between requests running at the same time, and has prefix caching available.
When a request finishes, its cache is kept rather than discarded, filed in a tree organised by shared beginnings. The tree branches where the traffic branches — one system prompt at the root, then tool schemas, few-shot blocks and chat histories hanging off it. A new request walks down from the root, matching as far as it can, and prefills only the remainder.
On a chat workload with a 300-token answer, prefill is under 5% of the request. Cutting an 86-millisecond prefill to 21 is a real 4× on that stage and moves total request time by about three per cent. Users perceive the total.
Paging removes waste. Quantisation makes what is left smaller. It is the cleanest capacity lever in the whole runbook.
--kv-cache-dtype fp8. One byte per element instead of two.
Error that accumulates over a generation — a key quantised at token 10 is still read at token 10,000.
It acts on bytes_per_element, which no other lever touches.
Saying “these are independent levers, so they compose” in a capacity answer shows you understand them as a stack rather than as a menu — which is the distinction most candidates miss.
Cache memory is finite and conversations grow. Eventually the server holds more than it can fit.
Drop the evicted request’s cache and redo its prefill later.
Ship the blocks over PCIe and bring them back.
Do not admit the request in the first place.
Sharing blocks means one request’s cached content can be reused by another that happens to start with the same tokens. For a shared system prompt that is exactly the intent. For anything containing user data it deserves thought. Two distinct concerns: access control — a shared cache should be keyed per tenant so one tenant’s blocks cannot be matched by another’s request; and a timing side channel — someone measuring TTFT can in principle infer that a prefix was already cached.
What does PagedAttention do, and why does it help?
vLLM or SGLang, and why?
Prefix caching gave 4× on prefill and users say nothing changed.
Is prefix caching safe across different users?
What happens when the GPU runs out of cache mid-generation?
Our cache hit rate dropped from 85% to 12% overnight.
QDoes PagedAttention change the maths of attention?
No. The results are identical. It is a memory-management change with a matching kernel that reads from scattered blocks. Which is why there is nothing to evaluate before enabling it.
QWhat block size should I use?
16 is the vLLM default and rarely worth changing. Smaller wastes less on the final partial block and adds bookkeeping; larger is the reverse. The one place it matters is prefix matching, which is block-aligned — a larger block makes the rounding coarser.
QWhy does my prefix cache hit rate not match what I expect?
Matching is on exact token ids, block-aligned, from the very start. Anything that shifts the sequence invalidates everything after the difference. Log the rendered prompt for two consecutive requests and diff them — the cause is usually obvious in seconds.
QDoes prefix caching help RAG?
Much less than people expect. Retrieved passages differ per query, so the only reusable part is the system prompt — typically 5 to 15 per cent. Still free to enable, but do not build a capacity plan on it. Agents and multi-turn chat are where the large wins are.
QIs an fp8 cache safe?
Generally, at 8 bits. What makes it different from weight quantisation is that the error accumulates over a generation. Test it on long outputs and long conversations. The failure mode to look for is drift: coherent early, degrading late.
QCan I cache prefixes to disk or across machines?
There is active work on exactly this — tiering to host memory and beyond, and sharing across a fleet. The arithmetic is what the hierarchy predicts: host memory is 52× slower than HBM, so it pays only when the alternative is a full recompute. A real but maturing capability.
QBlock sharing versus prefix caching?
Block sharing works between requests running at the same time. Prefix caching keeps blocks after a request finishes. The first saves memory; the second saves memory and prefill work.
QShould I worry about the timing side channel?
Know that it exists and decide deliberately. For an internal tool it is almost always acceptable; for a public API handling sensitive prompts it may not be. Mitigations are per-tenant cache keys, or disabling cross-request sharing for the sensitive route.
QWhy is throughput falling while I add load?
You are almost certainly in a preemption loop: the server is evicting mid-generation requests and then redoing their work. Cache utilisation pinned at 100% with a growing queue is the signature. Adding load makes it worse.
QWhat single change would you make first?
Measure the repeated-prefix fraction of real traffic, because it decides whether the biggest lever here applies to you at all. 90% and prefix caching is transformational; 10% and you should spend the effort on the decode loop. An afternoon, and it redirects everything else.
None of this makes the model better. All of it makes the same hardware serve several times as many people. Paging takes waste from sixty or eighty per cent to a few; sharing removes the duplicates; keeping blocks after a request finishes removes the recomputation. Stack an fp8 cache on top and thirteen users on an MHA bf16 baseline becomes three hundred and eighty-two on the same card. And the first thing to measure is what fraction of your prompts actually repeats — because that one number decides whether any of it applies to you.
What fraction of a typical prompt is a prefix that repeats? Has anyone measured it?
Is prefix caching enabled, and what is the hit rate?
Is there anything variable near the start of your system prompt?
Is the cache in fp8, and if not, why not?
Is preemption count monitored, or only latency?
In a multi-tenant deployment, is the prefix cache keyed per tenant?