vLLM and PagedAttention: Virtual Memory for LLM Serving

Inference combines processing an input prompt with generating an answer one token at a time. During prefill, all prompt tokens are known, allowing large matrix operations. During decode, each new token depends on previous output. The server reads model weights and accesses the stored keys and values of earlier tokens: the KV cache. Recomputing the entire history would be expensive, but retaining it also consumes resources. Batching several requests amortizes weight reads across their outputs. The number of sequences in a batch is constrained by the memory needed for each sequence’s cache. Improving serving throughput therefore starts with concurrency and memory allocation, alongside arithmetic speed. A fast isolated request does not establish performance under a stream of requests with different input and output lengths. Each active sequence holds state for as long as generation continues.

The paper’s example places an OPT-13B model with FP16 weights on a GPU with 40 GB of memory. Weights occupy roughly 26 GB, leaving a limited budget for temporary data and a growing cache. In this model, one token requires about 800 KB of KV data; a 2,048-token sequence needs approximately 1.6 GB. Contiguous allocation reserves a large region before the final answer length is known. This produces three forms of waste: space reserved for future tokens, unused capacity beyond the answer’s actual endpoint, and gaps between regions of different sizes. The episode examines Orca variants, including an idealized version that knows the output length in advance. Even that knowledge does not eliminate every allocation problem. Empty space may remain assigned to one request while another request waits because it cannot use that space.

PagedAttention borrows an operating-system idea: a logically contiguous sequence need not occupy a contiguous physical region. The cache is divided into equally sized blocks. A table maps a request’s logical block numbers to physical blocks in GPU memory, and the attention kernel reads through that mapping. Token order remains correct while physical blocks can come from anywhere in a shared pool. Allocation happens when the previous block fills, and completion returns blocks to the pool for reuse. The slide illustration uses four tokens per block to make the mechanism visible; the implementation discussed uses sixteen. The illustration is therefore an explanation rather than a universal server setting. Unused capacity is bounded by the final partially filled block instead of a large private reservation for the entire potential answer. More of the same memory becomes available for concurrent sequences.

Shared prefixes create a second opportunity. A coding assistant may request several candidate answers to the same prompt. Copying identical KV data into every candidate’s private allocation wastes memory. Their logical tables can instead reference the same physical blocks. Sharing remains safe while the data is read only. When a sequence needs to append a token to a shared, partially filled block, the system checks references and creates a private copy for the branch being modified. This is copy on write. Completed prefix blocks can remain shared. Beam search extends the idea into a tree of candidate prefixes: discarded branches release their blocks while common data stays available to surviving candidates. The benefit depends on how much text the sequences share. A block table provides useful mechanisms; it does not establish equal gains for every request distribution or decoding strategy.

Efficient allocation does not make memory unlimited. When active sequences need additional blocks and the pool is empty, the scheduler must suspend work. Application knowledge makes this decision different from general operating-system paging: an attention step needs all blocks of a sequence, so the system evicts a whole sequence group. The design discussed chooses a later-arriving group and preserves an arrival-based service order to avoid starvation. Recovery has two options. KV data can be swapped into CPU memory and restored later, or discarded and recomputed from the known sequence through prefill. Swapping pays for data transfer; recomputation pays for arithmetic. The episode connects these choices to vLLM’s architecture: the scheduler manages requests and block tables while GPU workers execute model computation. With tensor parallelism, workers use a consistent block mapping across model shards and synchronize computation results separately.

In the experiments discussed, the paper’s authors achieved roughly two to four times Orca’s throughput at comparable latency. These are historical results for particular models, workloads, and configurations. The PagedAttention kernel itself can be slower than a conventional attention kernel because table lookups and indirect access add work. Block size also introduces a tradeoff. Very small blocks increase overhead; very large blocks waste more space in partially filled tails. The system-level gain comes from fitting more active sequences into the same memory and using expensive hardware more effectively. A kernel benchmark and a service benchmark can therefore suggest opposite conclusions. The closing engineering lesson is to locate the actual bottleneck, borrow an appropriate idea from another field, and measure its effect across the system. The improvement did not require changing the language model itself. Training with a more static tensor layout is a separate boundary: the cost of indirection can remain while the benefit of dynamic allocation disappears.