PagedAttention: How vLLM Cut KV Cache Memory Waste from 80 Percent to 4 Percent

Serving a large language model at scale is, at its core, a memory problem. Every token an autoregressive transformer generates requires reading and writing key and value tensors for each attention layer in the model. Those tensors, collectively called the KV cache, grow as the sequence gets longer and must stay in GPU memory until generation finishes. Before vLLM, the standard approach was to pre-allocate a contiguous block of memory per request sized to the maximum allowed sequence length. A request that ends in 200 tokens still held a reservation for 2,048 tokens. The original PagedAttention paper (arXiv:2309.06180), published at SOSP 2023 by Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica at the UC Berkeley Sky Computing Lab, measured 60 to 80 percent of reserved KV cache memory going to waste under that scheme. The paper introduced PagedAttention, an attention algorithm that borrows virtual memory and paging from operating system design, and built vLLM, a serving system on top of it that reduces KV cache waste to roughly 4 percent.

Where the 60 to 80 percent memory waste comes from

The per-token KV cache cost follows a formula: 2 times the number of KV heads times head dimension times bytes per element, per layer. That factor of 2 accounts for separate key and value tensors. Models using grouped-query attention (GQA), like LLaMA 3, use fewer KV heads than query heads, which reduces per-token cost compared to full multi-head attention. For LLaMA-13B in fp16 with full multi-head attention, the KV cache for a single sequence can reach up to 1.7 GB. With contiguous pre-allocation, the serving system reserves that full space for every request at admission time, regardless of how many tokens the request will actually generate. Two kinds of fragmentation compound this problem. Internal fragmentation occurs when a request finishes early and the unused tail of its reservation sits empty until the sequence is evicted. External fragmentation occurs when freed blocks are too scattered in address space to satisfy a new large request, even though total free memory is sufficient. Both forces were measured in the paper: active tokens occupied fewer than half the VRAM bytes reserved for them, and the overall waste across the KV pool sat at 60 to 80 percent under realistic workloads.

How PagedAttention partitions KV cache into blocks

PagedAttention replaces the contiguous pre-allocation with a physical block pool. Each physical block holds the key and value tensors for 16 consecutive tokens across all layers (the default block size in vLLM, configurable with the --block-size flag). When a sequence has generated 16 tokens, vLLM claims one block from the free pool and records it in that sequence's block table. When the sequence reaches 32 tokens, it claims a second block from anywhere in the free pool, regardless of the first block's location. The attention kernel reads the block table at each forward pass and gathers the correct blocks before computing attention, similar to how an OS memory management unit walks a page table to translate virtual addresses to physical frames.

• Physical block size: 16 tokens by default (configurable). Each block stores the K and V tensors for those tokens across all attention layers.
• Block table per sequence: a mapping from logical block index to physical block address, maintained by the vLLM scheduler.
• On-demand allocation: blocks are claimed from the free pool only as tokens are generated, not at request admission.
• Maximum waste per sequence: 15 partially filled token slots in the last block, yielding roughly 4 percent measured waste across the pool.

The analogy to OS virtual memory is close. Blocks correspond to pages, tokens correspond to bytes, and sequences correspond to processes. A sequence's logical KV cache is contiguous from the sequence's point of view but can reside in scattered physical blocks, exactly as a process's virtual address space can map to non-contiguous physical RAM pages. Because allocation is on-demand, a short sequence that finishes in 50 tokens claims only four blocks (50 tokens divided by 16, rounded up) and wastes at most 14 slot positions. The reserved-but-unused tail that defined the contiguous approach disappears.

Copy-on-write sharing for parallel sampling and beam search

The block table structure enables a second optimization that matters especially for parallel sampling, beam search, and speculative decoding. When a request generates multiple output completions from the same prompt (parallel sampling with best_of=4, for example), the prompt's KV blocks are identical for all candidates. PagedAttention lets all four candidate sequences share the same physical blocks for the prompt portion by pointing their block tables at the same physical addresses, with a reference count tracked per block. When a candidate sequence diverges and writes new tokens, vLLM allocates a fresh block and copies the shared block's contents to it before writing, implementing copy-on-write semantics identical to what operating systems use for forked processes. Candidates that are pruned during beam search release their block references immediately, returning physical blocks to the free pool. The paper reports that this memory sharing cuts memory usage for complex sampling algorithms by up to 55 percent, which translates to a throughput improvement of up to 2.2 times for parallel-sampling workloads.

Continuous batching keeps the GPU saturated

Static batching, the baseline approach before vLLM, groups requests into a fixed batch that must complete as a unit. Every sequence in the batch, including the shortest, waits for the longest to finish before the GPU can admit new requests. A batch where 30 sequences finish in 50 tokens and 2 run to 500 tokens leaves most GPU capacity idle for the last 450 decoding steps. GPU utilization under realistic mixed-length workloads drops to the 20 to 40 percent range under static batching. vLLM uses iteration-level scheduling, also called continuous batching. After each forward pass, the scheduler checks whether any running sequences have finished and immediately admits new sequences from the waiting queue into the next iteration. There is no batch boundary to wait for. The PagedAttention block pool makes this practical because sequence memory is released one block at a time as generation ends, rather than as one large contiguous slab that must be defragmented before the next request can fit.

Benchmark results and production adoption

The paper evaluates vLLM against HuggingFace Transformers (HF) and HuggingFace Text Generation Inference (TGI), benchmarking LLaMA-7B on an NVIDIA A10G and LLaMA-13B on an NVIDIA A100 (40 GB). Request input and output lengths are sampled from the ShareGPT dataset to represent realistic chat workloads. When each request asks for one output completion, vLLM achieves 14 to 24 times higher throughput than HF and 2.2 to 2.5 times higher throughput than TGI. When each request asks for three parallel output completions (the scenario that exercises copy-on-write sharing), vLLM achieves 8.5 to 15 times higher throughput than HF and 3.3 to 3.5 times higher throughput than TGI. Compared to FasterTransformer and Orca, the paper's primary baseline systems, vLLM improves throughput by 2 to 4 times at the same latency level, with larger gains at longer sequences, larger models, and more complex decoding.

• Throughput vs. HF Transformers (one completion): 14 to 24 times higher on LLaMA-7B and LLaMA-13B.
• Throughput vs. TGI (one completion): 2.2 to 2.5 times higher.
• Throughput vs. FasterTransformer and Orca: 2 to 4 times higher at the same latency.
• Parallel sampling memory savings: up to 55 percent reduction, yielding up to 2.2 times throughput improvement.
• Production use at LMSYS Chatbot Arena: 30,000 average daily requests and 60,000 peak, with GPU count cut by 50 percent compared to the prior HF backend.

vLLM was developed at the UC Berkeley Sky Computing Lab and initially deployed to serve Vicuna and other models on the LMSYS Chatbot Arena starting in April 2023, two months before the public launch announcement. The project is open source at github.com/vllm-project/vllm and has since added prefix caching (reusing KV blocks for shared system prompts across requests), chunked prefill (breaking long context fills into smaller chunks to avoid head-of-line blocking), and speculative decoding. PromptingIndex covers PagedAttention alongside related inference infrastructure including Flash Attention (Dao et al. 2022), grouped-query attention (Ainslie et al. 2023), speculative decoding (Leviathan et al. 2022), and KV cache mechanics, all of which address different aspects of making large language model inference fast enough and cheap enough to run at real-world scale.