PagedAttention

1. Why Each Request Needs Its Own Memory

A model processes text as tokens, which can be words, parts of words, or punctuation. Inside each attention layer, a token produces lists of numbers called its query, key, and value. The query is compared with keys to decide how strongly to use the corresponding values. This is how attention brings information from earlier positions into the current calculation.

For ordinary causal generation, the keys and values of an earlier position can be reused when later tokens are processed. The model stores them in the key-value cache, usually shortened to KV cache. Keeping these results avoids recomputing them at every step. The cache contains numerical vectors from attention layers, rather than a copy of the text or the model's weights. Hugging Face's cache explanation describes this reuse in more detail.

The initial prompt-processing stage is called prefill. It builds the prompt's cache and produces the prediction for the first output token. During decoding, that output token is fed back through the model, its keys and values are added, and the model predicts the next token. The cache grows as more tokens are processed.

Requests use the same model weights, but generally need separate caches because their contexts differ. A single long conversation can therefore consume substantial cache memory, and a busy server must make room for many such conversations at once.

2. The Problem with Reserving Space Up Front

A straightforward design gives each request one continuous region of memory, meaning its cache entries sit next to one another. To avoid moving the cache as it grows, the server could reserve enough room for the request's maximum allowed length. However, a limit of 4,096 tokens does not mean that every request will actually use 4,096 tokens.

Consider a request with 600 cached tokens and space reserved for 4,096. The remaining 3,496 slots are unavailable to other requests even though they contain no useful cache entries yet. Some may be filled later, while others may never be used. This is the cost of reserving memory for an uncertain future.

Variable-size allocations can also leave gaps between occupied regions. There may be enough free memory in total, but no single gap large enough for the next allocation. This is external fragmentation. Unused space inside an allocated region is internal fragmentation. The original PagedAttention paper identifies these allocation problems as obstacles to serving larger batches.

3. Dividing the Cache into Small Blocks

PagedAttention was introduced with vLLM, an open-source engine for serving language models. It lets a sequence's cache occupy several separate blocks. Each block has room for the keys and values of a fixed number of tokens. These blocks do not need to be adjacent in GPU memory, so the server can use whichever suitable blocks are free.

We will use four tokens per block in the examples. Six cached tokens need two blocks: one holds tokens 1 through 4, and the other holds tokens 5 and 6 with two slots left over. Tokens 7 and 8 can fill those slots. Only when token 9 is processed does the request need a third block.

The word paged comes from a related memory-management idea in operating systems. A program can see an ordered address space even when its data occupies separate physical pages. Here, the serving engine manages KV-cache blocks and the attention implementation reads them through a mapping. This does not require moving the cache to CPU memory or disk. vLLM's introduction explains this connection to paging.

In practice, a server can reserve a GPU cache pool in advance and then assign blocks from that pool to requests on demand. Allocating a block to a request does not necessarily mean asking the GPU driver for a new allocation at every step.

4. Finding Tokens with a Block Table

Separating the blocks creates a new question: how does attention find the right cache entries? Each sequence has a block table, a small list that maps blocks in sequence order to their locations in the physical cache pool.

A logical block describes a range of positions in the sequence. A physical block is the storage assigned to that range. For example, logical block 0 might live in GPU block 3, while logical block 1 lives in GPU block 0. The IDs start at zero; they are labels, not token positions. The sequence still reads tokens 1, 2, 3, and so on in their original order.

Add tokens until the cache reaches nine entries. A third mapping appears, but the earlier entries stay in place. Finishing A returns its blocks to the pool without disturbing B. The block table lets storage change in these small units while preserving each request's view of its own sequence.

5. Reading the Cache During Attention

Now follow one decoding step at one layer. The incoming token produces a new query, key, and value. The cache manager has arranged space for the new entry, and the key and value are written to its assigned block and offset. The query then attends to the valid keys and values in that sequence, including the current position.

A paged attention kernel, the GPU implementation of the operation, follows the block table to read those entries. If the table is [3, 0, 6], the logical sequence draws its cache from those physical blocks. There is no need to copy them into one continuous sequence-sized buffer before attention. The sequence length tells the kernel which slots in the final block are valid.

The attention calculation still compares the query with the allowed keys, applies softmax, and combines the values. Softmax must normalize over all valid positions for that query. Normalizing each page independently and simply adding its output would give the wrong result. Physical placement also does not change a token's logical position or the causal mask.

vLLM's historical kernel walkthrough shows these reads and reductions. It documents the original implementation, rather than every attention backend used by current vLLM releases.

6. How Much Memory Is Saved?

Paging reduces unused allocation space; it does not make an individual key or value smaller. In our four-token example, nine cached tokens occupy three blocks with a total capacity of twelve tokens. Three slots remain unused. At eight tokens, two blocks are exactly full and there are no unused slots.

For an unshared sequence that grows by appending tokens, with no extra blocks reserved ahead of time, only its final block can be partly empty. With B slots per block, that leaves at most B minus 1 unused slots per sequence. Equal-size blocks also remove the need to find one long continuous gap within the cache pool.

Smaller blocks can reduce unused tail space, but require more block-table entries and may be less efficient for a particular kernel. Larger blocks make the allocation coarser. Four is only a teaching choice here; supported sizes and suitable choices depend on the attention backend and hardware.

7. Sharing a Prefix Without Overwriting It

Suppose we want two different continuations of the same prompt. They begin with identical context, so their already-computed prefix can share physical cache blocks. Each continuation has its own block table, but the prefix entries point to the same storage. A reference count records how many active sequences use each block.

Sharing needs care when a block is only partly filled. If B appends a new entry to a block that A also uses, it must not modify A's storage. Copy-on-write handles this by giving B a private copy when a write becomes necessary. Full prefix blocks that will not be modified can remain shared.

In this example, the first four entries are never copied. Only the partly filled second block needs a private copy for B. When A finishes, a block still referenced by B cannot be reclaimed. The original design uses this combination of block tables, reference counts, and copy-on-write for forked generation, including parallel sampling. vLLM's introduction illustrates the same sharing mechanism.

8. Reusing Work Across Separate Requests

Sharing can also help when a later request starts with a prefix that the server has already processed. For example, several questions might begin with the same system instructions and document. Automatic prefix caching identifies reusable KV blocks so the server can skip the corresponding prefill work. It reuses model computation, not a previously written answer. vLLM's feature guide describes this use case.

Matching a few words anywhere in the text is insufficient. A cached entry depends on the context before it, so reuse requires a matching prefix and compatible model state. vLLM's hash-based prefix-cache design identifies blocks using their tokens, preceding-prefix information, and relevant identifiers such as the LoRA adapter. Its documented block-cache scheme stores full blocks, which is distinct from the partial-block branching example above.

A prefix cache may retain a finished request's blocks as reusable entries. Once no active request references a block, the manager can evict it when that space is needed. Paged allocation makes block-level reuse convenient, while prefix matching and eviction decide which results to keep. Even with a prefix-cache hit, decoding still has to compute the new answer.

9. Making Room for More Requests

Better cache utilization can let a server keep more requests active within the same memory budget. A scheduler decides which of them run in each iteration. With continuous batching, finished requests leave the batch and waiting requests can join as capacity becomes available, instead of waiting for every request in the original batch to finish.

The two responsibilities work together: the scheduler chooses the work, while the cache manager provides and tracks its storage. In our first example, finishing A makes several blocks available. A waiting request can use those blocks even though they are separated by B's cache. It does not need B to finish or move elsewhere.

The pool still has a finite capacity. If every usable block is occupied, a request that needs another block must wait or the engine must make space. For example, vLLM can preempt a request, release its cache, and recompute the needed state later. That has a latency cost, as its preemption documentation explains.

The main opportunity is higher serving throughput, meaning more useful work completed over time. A larger active batch does not guarantee that one person's answer finishes sooner. The result also depends on request lengths, available compute, the attention implementation, and scheduling decisions.

10. How PagedAttention Fits with FlashAttention

FlashAttention focuses on how the attention calculation moves data through GPU memory. Tiling and online softmax let it avoid storing the full table of attention weights. PagedAttention focuses on allowing the persistent KV cache to occupy separate, manageable blocks as requests grow and share context.

These ideas can be combined when a kernel supports a paged cache layout. The FlashAttention implementation, for example, includes support for paged KV caches. Neither paging nor tiling by itself removes the need for full attention to consider the allowed context positions.

The useful separation is between the sequence a model sees and the storage a server manages. Token order and attention semantics remain intact, while block tables let the underlying cache grow and be reclaimed in small pieces. That flexibility is what makes PagedAttention valuable when many conversations compete for the same GPU memory.