PagedAttention: Treating KV Memory Like Virtual Memory

A serving process has to keep, for every conversation it is holding, the keys and values of every token that conversation has seen. That memory has two awkward properties: it grows by one token at a time, and nobody knows in advance how large it will get. The request that is about to arrive might answer in eight tokens or in two thousand, and it will not say which.

The obvious way to deal with an array that grows is to reserve room for the largest it could become. It is also the way that wastes most of a GPU.

The bill for a reservation

Take the setup the inference note measured: a half-billion-parameter model on a Tesla T4, 12 KiB of cache per token of context, and a server that allows sequences of up to 2,048 tokens, prompt and answer together. One reservation is then 24 MiB, contiguous, held for as long as the request lives.

Allocating those reservations on the real card, one after another, until it refuses gives the honest number: 573 of them fit beside the model's weights. That is the most this design can hold — 573 sequences, however short they turn out to be — and an upper bound, since it leaves nothing for the activations a running model needs. Given the budget the engine below gives its cache, it would be 453.

Everything measured below ran on one machine and one build: a Tesla T4 — Turing, compute capability 7.5, 14.6 GiB — with vLLM 0.29.0 on PyTorch 2.13 and CUDA 13, running Qwen2.5-0.5B-Instruct in half precision, in blocks of 16 tokens and at a context limit of 2,048 except where a measurement needs otherwise: the long shared prompts below ran at 4,096 and the longest prefix at 8,192. That is worth pinning down, because several of the numbers here are properties of a build rather than of the idea. Which attention kernel the engine picks depends on what the card supports — asked, this one named the Triton kernel, the fused CUDA paths wanting a newer card than this; which block sizes that kernel accepts depends on the kernel; how finely a shared prefix can be matched has been changing from release to release. Where a result belongs to this build rather than to paging, the text says so.

The awkward part is what those buffers hold. Most requests are short; the reservation is for the longest one allowed. A request that ends after 200 tokens spends its life holding 2,048 tokens' worth of memory, using a tenth of it and denying the rest to everyone else. Capacity is set by the longest sequence the server permits, not by the sequences it actually serves — and the way to raise capacity, in that design, is to promise users shorter answers.

Two kinds of waste

That is one of two ways a reservation scheme loses memory, and they are worth separating because they have different cures.

Internal waste is the part of a reservation that is never used: the 1,800 tokens of a 2,048-token buffer that a short request never reaches. It is invisible to the allocator — as far as it is concerned that memory is in use.

External waste is memory that is free but unusable: after requests of different sizes have come and gone, the free space is scattered in pieces, and a new request that needs a contiguous run cannot be placed even though the total free memory is several times what it asks for.

Both are easy to see in a simulation of the same pool. The card's real numbers are used — 929,024 tokens of cache, 12 KiB per token, sequence lengths drawn from a distribution that is mostly short with a long tail — and three allocators see the same arrivals: one reserving the maximum; one reserving exactly what each sequence turns out to need, an oracle no real server can be, since it would have to know the length in advance, but the cleanest way to separate the two kinds of waste; and one handing out fixed-size blocks.

Under moderate load the reservation scheme turns away 14% of requests while its memory is 95% occupied and one quarter used. The other two admit everything. Push the load up and the second kind of waste appears: exact-fit reservations, which never waste a byte internally, begin refusing requests at 87% occupancy, because the free memory is there but in pieces too small to hold a sequence. The paged allocator refuses more requests at that load, not fewer — but it refuses them at 95% occupancy, when the memory really is gone. The difference is not how often each says no; it is whether a refusal means the pool is full or merely awkward.

The cure for internal waste is to stop reserving for the worst case. The cure for external waste is to stop needing contiguity. Operating systems solved both, half a century ago, with the same idea.

What operating systems did about it

A program on a modern machine does not see physical memory. It sees addresses, and those addresses are translated — page by page, a page being a fixed-size chunk, 4 KiB on an ordinary machine — into wherever the bytes actually live. A table per process records the mapping, and the processor keeps recent translations in a dedicated cache so that the common case never reads that table at all.

That indirection buys three things at once. A program can be given memory in pieces that are not adjacent, because it never learns where they are: external fragmentation stops mattering. Memory can be handed out as it is touched rather than reserved up front, so a program that asks for a lot and uses a little costs what it uses. And two processes can map the same physical page, which is how a shared library ends up in memory once rather than once per program.

The cost is an extra step on every access and a table to keep. Machines have paid it for decades, and have built hardware — the TLB, page-table walkers — to keep it cheap.

The same trick for the cache

PagedAttention is that idea applied to the key/value cache of a transformer.

The pool is cut once into blocks of a fixed number of tokens — 16 in the engine measured here. A sequence no longer owns a contiguous buffer; it owns a block table, a list of the physical blocks that hold its tokens in order. When it needs room for a seventeenth token, it takes any free block, anywhere in the pool, and appends it to its table. The attention kernel is written to walk that table instead of reading a flat array.

Three consequences follow immediately, each answering one of the three.

Internal waste is bounded by one block. A sequence wastes at most fifteen tokens — the unfinished tail of its last block — which at this model's 12 KiB per token is 180 KiB, against up to 24 MiB for a reservation. That is a factor of over a hundred.

External waste disappears inside the pool. Blocks are interchangeable, so there is no such thing as free-but-unusable memory: if a block is free, it can be used by anyone.

Sharing becomes possible. Two sequences that begin with the same tokens can point their tables at the same physical blocks, and each keeps its own blocks only from the point where they diverge. Possible is the operative word: paging supplies the address indirection and the reference counts that make sharing safe, and says nothing about when two sequences are entitled to it. That decision belongs to a separate mechanism, further down.

The price is an extra indirection in the hottest kernel in the system, and a table to keep per sequence. That price is where the idea either survives or does not, so it is worth seeing exactly what the kernel does with it.

How the kernel reads a block table

The indirection is usually where a reader expects the idea to fall apart. An extra lookup on every memory access, in the hottest kernel of the system, sounds like the kind of thing that eats the saving it just bought. It does not, and the reason is worth following, because it says something about why the idea transferred at all.

Start with what attention does for one new token. The query is a single row. The keys and values are the whole history — everything the conversation has said so far. A kernel that computed this naively would build the full row of scores, softmax it, and multiply by the values; for a long conversation that row is large enough that nobody writes it that way. The kernel instead walks the history in tiles: take the next few dozen key positions, multiply the query by them, update a running maximum and a running sum, scale the accumulated output by however much the maximum moved, add this tile's contribution, move on. Nothing bigger than a tile ever exists.

That loop is not a concession to paging. It is what the kernel looks like anyway, on a contiguous cache, for the ordinary reason that the score row does not fit. Which means the kernel already had a line in it that computed the address of the next tile.

On a contiguous cache that line is arithmetic: the tile starting at position $i$ lives at the base address plus $i$ times a stride. With a block table, the same line reads

$\text{address} = \texttt{block\_table}[\,i \div B\,] \cdot \text{block stride} + (i \bmod B) \cdot \text{slot stride}$

where $B$ is the block size. Both operations are cheap in the only sense that matters here: $B$ is a power of two, so the division is a shift and the remainder is a mask, and the table itself is a few hundred bytes for a long sequence — small enough that reading it is not competing with the keys and values for bandwidth.

The tensors those strides run over are worth seeing once, since the whole argument is about addresses. Asked from inside, this build keeps the cache as one tensor per layer — 24 of them — each shaped [blocks, 2, 16 slots, 128 numbers] in half precision: keys and values in the same tensor, a block's sixteen slots laid out consecutively inside it, and a slot holding its two key/value heads of 64 dimensions flat. A tile of one head therefore stays inside one block: sixteen 128-byte pieces, one per slot, within a single 4 KiB stretch of keys and another of values.

In this build the kernel runs one program for each key/value head, and it walks the history sixteen positions at a time whatever the block size. On every tile the program reads the block number for each of the tile's sixteen positions: 64 bytes, the same number sixteen times over at decode, which the hardware serves as one read. Against that it fetches 4 KiB of its head's keys and values and does 14,336 multiply–adds — seven query heads against sixteen positions of 64 dimensions, once for the scores and once for the values. The other head's program does the same. So the expectation is that paging costs nothing worth measuring.

That is an expectation and not a proof. A load and a multiply–add are not commensurable, and whether one extra dependent load costs anything depends on its latency, on how much other work the kernel has in flight to hide that latency behind, and on what the memory system is already busy with. A ratio of counts captures none of it.

The block size is the one knob this build exposes, so it is worth turning. Doubling the block from 16 tokens to 32 does not halve the reads in this kernel, since it still looks up a number for every position; it halves the number of different numbers in the table and the blocks the allocator hands out. Throughput did not notice: 4,740 tokens per second at blocks of 16 and 4,711 at 32, 0.6% apart, while three runs of blocks of 16 alone, on the identical configuration, span 4,720 to 4,820: 2.1%. What that shows is narrower than it looks. The block size is not a speed setting on this workload and card; the price of the indirection itself is not isolated by it, because that would take the same kernel without a table, and this build has none.

Blocks smaller than 16 were not slow on this card; they were refused at start-up. The Triton backend declares that it accepts multiples of sixteen, which matches the sixteen-position tile it walks at decode, so the allocator's granularity is not a free parameter: it is set by the kernel that has to read the result. The clamp people expect — a tile cut down so that it never straddles two blocks — exists only on an optional path built for other hardware. Here a tile simply looks up a block number for each of its positions.

What the allocator actually sees

The other half of the machinery is the part nobody writes a kernel for: who hands out blocks, and how often.

Prefill is the other shape of the request. A 2,407-token prompt — the prefix measured further down — will occupy 151 blocks before decode begins, and that much is arithmetic. What is not fixed is when it takes them. The scheduler works to a token budget per step, and a prompt larger than the budget is cut into chunks; the blocks are allocated for the chunk about to be computed, not for the whole prompt. The large demand at the front of a request is therefore itself spread across steps, and can ride alongside sequences that are already decoding instead of freezing them. Admission is stricter than allocation: by default this release lets a new request in only if its whole prompt would fit, so that a half-admitted prompt cannot thrash the pool.

Decode is the other extreme, and it is the one worth looking at. A sequence of $n$ tokens needs $\lceil n/B \rceil$ blocks. On every step the scheduler works that number out for the tokens each running sequence is about to have, subtracts the blocks it already holds, and asks the pool for the difference. In steady-state decoding the difference is zero fifteen steps out of sixteen, and one on the sixteenth. Growth touches the allocator once per block, not once per token.

The asymmetry is larger than it sounds. The kernel reads a block number for every position of history, in every layer, for each of the two key/value heads, so a sequence two thousand tokens deep has its table read 96,000 times in a single decode step — sixteen neighbouring positions asking for the same number each time — while the allocator is called once every sixteen steps. The structure people worry about is the cold one; the structure in the hot path is read-only, which is the only reason the arrangement survives at all.

The table itself is worth a number, since it is the thing that replaced contiguity. A sequence at the full 2,048 tokens needs 128 block numbers, which at any plausible integer width is half a kilobyte of table against 24 MiB of cache — one part in fifty thousand. Across the 453 such sequences this pool could hold, every block table in the engine together comes to a few hundred kilobytes. The bookkeeping is cheaper than the rounding error on the thing it is keeping track of.

No sequence gets a maximum-length buffer up front. It is given room for the tokens of this step and no promise about the next one, which is what makes the pool's occupancy meaningful: memory that is held is memory in use, not memory that might be.

That honesty has to be paid for somewhere, and the place is the step where the pool cannot serve everyone. There is no way to stall a sequence until memory appears — the batch is assembled fresh every step, so a sequence is either in it or it is not. Under the first-come-first-served policy these runs used, the engine takes the most recently scheduled one out, frees its blocks, sets its count of computed tokens back to zero, and puts it at the front of the queue of waiting requests. When it comes back, it re-prefills.

As configured here, the engine has no other move. There is no swapping the cache out to host memory and back, which an operating system would do with a page: a preempted sequence loses its keys and values and computes them again. With the prefix cache switched on, the blocks it gave up keep their identity while they sit in the free list — the next section explains how — so a sequence that comes back before someone else has taken them can find its own cache still there. In a pool starved enough to preempt, it mostly cannot; the count is further down.

A separate mechanism: automatic prefix caching

Paging makes block sharing possible. It does not decide when blocks from an earlier request may be reused — that is automatic prefix caching, a mechanism built on top of the block table, and the two are worth keeping apart. Paging is the address indirection and the reference count; prefix caching is what exploits them. An engine can page without caching prefixes at all, and the measurements further down separate the two by switching the cache off.

Sharing a block is easy to draw and harder to make safe. Two sequences may point at one block only if the tokens in it are identical and everything before it was identical too — a model's keys and values depend on the entire prefix, so sixteen matching tokens in the middle of two different conversations are not interchangeable.

The way this is settled is worth knowing because it explains the shape of every sharing result further down. When a block fills up, the engine hashes it, and what goes into the hash is three things: the hash of the previous block, the token ids in this one, and a handful of extras that change what a token means — which adapter is loaded, which image the text refers to. The hashes form a chain. A block's identity is therefore the whole prefix that leads to it, and a lookup that matches means the two sequences agree from their first token, not that a window happened to coincide.

Two consequences follow, and both are visible in measurements.

A match ends on a block boundary. The 2,407-token prefix measured further down is 150 full blocks of 16 tokens — 2,400 tokens. The remaining seven live in a partial block that belongs to whoever wrote it and is shared with nobody. Sharing is block-aligned, and the tail is the rounding error paid for the convenience. This is the part of the mechanism that has been moving, and this release already carries a finer match as an option, prefix_match_unit, which lets a match end inside a block. It is built for hybrid models, whose blocks run to hundreds of tokens; on an ordinary transformer like this one the engine keeps matching whole blocks whatever the setting. Set to 1 or to 8, it left every one of the sixteen requests with exactly 2,400 tokens found, and the same answers token for token.

Nothing is copied on a hit. Each block carries a count of how many sequences point at it. A hit increments it; a sequence that finishes decrements it; at zero the block returns to the free list. Crucially it returns with its hash intact: a free cached block is an eviction candidate, not an evicted block, and it is only really lost when the pool needs it. The free list is ordered so that uncached blocks are taken first and cached ones oldest-first, which is the least-recently-used rule arrived at from the other direction.

The original design adds one more rule, for a shared block that has to be written — the case where one prompt branches into several answers: copy it first, write afterwards. That is copy-on-write, and it is the mechanism by which one prompt with eight continuations should cost one copy of the prompt plus eight tails rather than eight copies of everything.

Should. Whether it does on this engine is a separate question, and the answer turns out to be no. Asking for eight samples of one 1,447-token prompt, with the prefix cache switched off, took 1.54 seconds; eight separate requests carrying the identical prompt took 1.56. With long answers instead of short ones, 4.02 against 4.06. There is nothing to find. If the fork were sharing the prompt, seven of the eight prefills would have vanished and 1,447 tokens would not have been computed eight times over — at these prompt lengths that would not hide.

The reason is in how a request for several samples is handled at all: it is split into that many independent requests with one sample each, differing only in their random seed. Nothing in that arrangement shares a block. What makes the eight of them cheap is the same thing that makes any repeated prefix cheap — the hash lookup — so with the cache switched on the measurement stops being a new one and becomes the one below.

Copy-on-write did not disappear from this build; it moved. Shared blocks here are full, so nobody needs to write into one — except when a match ends inside a block, the finer option above. Then the shared block is copied into a private one before the new request writes its own tokens into it. On this model that never happens, since matches stay on block boundaries: nothing in these runs copied a block, and nothing needed to. Which is the same lesson as the section heading, arriving from the other direction: the block table makes the sharing possible, and something else has to go looking for it.

What it is worth on a real card

The engine measured here is vLLM. It is an inference server rather than a library: instead of being called to run a forward pass, it takes the whole loop over — it loads the model, owns the cache and cuts it into blocks, keeps a queue of requests, decides which of them are in the batch at each step, and streams results back. A program using it hands over prompts and sampling settings and gets tokens; everything between is the engine's.

The first thing it does is work out how much of the card it may spend on cache, and the way it does it is worth a sentence, because the answer is never all of it. It loads the weights, runs one forward pass with dummy inputs to see how high the activations peak, and gives the cache what is left of its budget. On this card the part that is not cache came to 2.02 GB — a gigabyte of weights and about as much again for activations and workspace — and it stayed at 2.02 GB whether the engine was allowed 70%, 85% or 95% of the card. The overhead is a fixed cost, so every extra percent of the budget goes to cache and nothing else: 738,992 tokens of it at 70%, 929,856 at 85%, 1,057,104 at 95%.

At the 85% it was given, that is 58,064 blocks of 16 tokens — 929,024 tokens of cache; another start of the same configuration found 52 blocks more, which is how far two starts of one engine can disagree. What the number is worth depends entirely on how long the sequences are:

At the full 2,048 tokens per sequence, the pool has room for 453 against the reservation scheme's 573 — fewer, not more, and the reason is the budget rather than paging. The reservations ran until the card refused, ending on about 13.4 GiB, while the engine kept 2.02 GB of its 85% for weights and workspace and gave the cache 10.6 GiB; in the same 10.6 GiB, reservations would hold 453 too. Below the full length the two part ways. At 512 tokens per sequence the pool has room for 1,814, at 256 for 3,629, at 128 for 7,258, while reservations stay at 573 — or 453 on an equal budget — because their capacity never depended on the sequences in the first place. At 256 tokens that is 6.3 times the measured reservations and 8.0 times the equal-budget ones.

These are places in the cache, not a batch the engine runs at once: the scheduler separately caps how many sequences it takes into one step, and their activations come out of the part of the card that is not cache.

On this setup, the block size controls waste, not measurable speed. The speed half of that was settled above: doubling the block changes throughput by less than repeating the same configuration does. What the block does change is the tail. Over the sequence lengths the simulation draws — mean 260 tokens, median 180 — the unfinished last block costs on average 7.6 tokens at blocks of 16, 15.5 at 32 and 31.4 at 64, which is 2.8%, 5.6% and 10.8% of everything held. On this pool that is the difference between room for roughly 3,470 sequences, 3,370 and 3,190: real, and an order of magnitude smaller than the difference between paging and reserving at all.

A smaller pool is mostly not noticed. Cutting the cache to a quarter of its size, from 930,000 tokens to 230,000, cost nothing measurable on a batch of two dozen long requests: 2,058 tokens a second against 2,059, the same number to within a tenth of a percent. That is not paging being clever — it is a reminder that the pool only matters once the traffic wants more of it than exists, and two dozen requests do not. What happens when they do is the scheduler's problem, and it is worth starving the pool on purpose to see it.

And when the traffic does want more than exists. Two hundred requests with nine-token prompts and thousand-token answers want 204,800 tokens of cache between them. Given a pool of 77,312 — oversubscribed two and a half times — the engine put a sequence back 189 times, and all two hundred requests finished. The same batch against a pool of 929,856 tokens needed no preemptions at all: 3,406 tokens a second against 4,476, so the starved run cost 24% of the throughput and none of the requests.

Twenty-four percent is cheaper than it sounds, and the reason is an asymmetry the inference note spends its length on. A preempted sequence loses everything: its count of computed tokens goes back to zero, so when it returns, its prompt and every token it had already generated are computed again. But they are recomputed the way a prompt is — in one pass over many positions at once — while the tokens it lost were produced one slow step at a time. Getting a thousand tokens back is nothing like the cost of having generated them.

How much gets recomputed can be counted, and so can how much of it the prefix cache saves. The run above had the cache off. Repeated with the cache on and the engine's own lookups tallied, the 195 sequences that came back after preemption asked for 108,196 tokens between them — more than half of everything the batch generated — and the cache still held 5,408 of them, one in twenty. A second repeat found 32 of 75,012. Throughput did not move either: 3,256 tokens a second with the cache on, against 3,305 and 3,291 in two runs with it off. In a pool short enough to preempt, a sequence's blocks are gone by the time it comes back, and the work it lost is simply done again, at prefill speed.

What a reservation scheme does at that same moment is the whole of the comparison: the request it cannot place, it refuses. Paging turns a refusal into a delay.

Reuse is the largest single effect measured here — and it belongs to the prefix cache. Sixteen requests that begin with the same 2,407-token prefix — a system prompt, a document everyone asks about — took 0.74 seconds with prefix caching on and 7.93 seconds with it off, almost eleven times faster. Paging is what made those blocks shareable at all; the hash lookup is what found them, and what the difference measures is fifteen 2,400-token prefills collapsing to seven-token tails. Both engines in that comparison were paged. Only one of them was looking.

And the sharing keeps. Those sixteen requests shared a prefix because they arrived together. The ordinary case is a prefix that arrives again — the same system prompt on the next request, the same document in the follow-up question — while its blocks are still in the pool, unevicted, because nothing has needed them yet. Asking prefixes of several lengths twice each, the first time costs a prefill and the second costs almost nothing: 39 ms cold against 32 warm at 128 tokens, 190 against 35 at 1,024, 375 against 40 at 2,048, and 1,251 ms against 62 at 4,096. The warm number hardly moves with length, because nothing is being computed — the blocks are found by hash and pointed at.

Where the analogy stops

Borrowed ideas are most informative at the point where the borrowing fails, and this one fails in four places.

There is no hardware. A processor translates an address in silicon, with a dedicated cache of recent translations, and a program never knows it happened. Here the translation is a load and two integer operations written by hand into an attention kernel. It is affordable only because that kernel already walked the history in tiles and already computed an address for every position it reads — the idea would not have survived a kernel that read the cache as one flat run.

There are no page faults, and nothing is overcommitted. An operating system will promise a program more memory than the machine has and go fetch a page when the program touches one that is not resident. This engine promises nothing it cannot produce now. When a block is missing there is no fault to take and no lower level to fetch from, so the problem is pushed back up to the scheduler instead of down to a disk: a sequence leaves the batch. The virtual-memory trick was borrowed; the virtual part of it was not.

The page is counted in tokens, not bytes. A block of 16 tokens is 192 KiB on this model, but not in one place: the cache is one tensor per layer, so in each layer the block is an 8 KiB stretch, the size of two ordinary 4 KiB pages. What is large is the unit of bookkeeping — one table entry covers sixteen positions in all twenty-four layers at once. That size was not chosen to suit a lookup table, and its lower bound comes from the kernel rather than from the allocator.

Nothing is being protected. Paging exists partly to keep processes out of each other's memory. Block tables have the opposite job: every sequence lives in one process, and sharing is the point rather than the exception. Which is also the one place the design gives something away — if two requests from different people begin with the same text, whether that text was already in the pool is visible in how quickly the first token comes back. This build lets a request carry a cache_salt, which is mixed into the hash of its first block, so requests with different salts never match each other's prefixes: a server shared by several tenants can close the channel at the price of their sharing nothing.

The shape of the idea

Two things it does not do, first. Paging does not make a decode step faster. Every number in the inference note about where a step's time goes is unchanged: the decode step still has to stream the model weights, and paging does not remove that bandwidth cost. What paging changes is how many sequences the cache has room for, which is a different resource entirely — and one that, for most real traffic, runs out first. For a large model on a current data-centre GPU, Where Your Prompt Goes works out how quickly.

And when every request genuinely uses the full context window, paging buys nothing but the removal of fragmentation. Its gains come from the gap between what requests are allowed to use and what they actually use, which is exactly the gap a reservation has to assume away.

What it is, then. A serving system has to place thousands of arrays that grow unpredictably into one fixed pool. That is not a machine-learning problem; it is the problem operating systems have been solving since the 1960s, and their answer came across intact: fixed-size blocks, a table per sequence, sharing by pointing at the same block, waste bounded by one block instead of one worst case.

What transferred, though, is the data structure and not the machinery around it. The block table is a page table. The fault, the hardware that walks the mapping, the willingness to promise memory that does not exist — none of that came along, and the engine covers for their absence with a scheduler that removes a sequence from the batch instead. Borrowing at that level is the useful kind: the structure is old enough to be boring, and everything that had to be invented sits in the two places a serving system can afford to be clever — the kernel that reads the table, and the policy that decides who is in the batch at all.

What it bought is one substitution. Capacity stopped being a function of the longest sequence the server permits and became a function of the tokens its sequences actually hold. Every measurement above is a way of asking how wide that gap is on one card.