PagedAttention

PagedAttention is an attention algorithm and memory manager for large language model (LLM) serving that stores each request's KV cache in small fixed-size blocks placed anywhere in GPU memory and tracks them through a per-request block table, the way an operating system maps virtual memory pages. Woosuk Kwon, Zhuohan Li, and colleagues at UC Berkeley and partner universities introduced it together with the vLLM serving engine in Efficient Memory Management for Large Language Model Serving with PagedAttention, presented at SOSP 2023. Removing the fragmentation of contiguous cache allocations lets one GPU hold many more sequences at once, and the paper reports 2-4x higher throughput than FasterTransformer and Orca at the same latency.

The Memory Problem It Solves#

During text generation, a transformer keeps the key and value vectors of every earlier token so it never recomputes them. That cache grows by one entry per token per layer, and a single sequence of the 13-billion-parameter LLaMA model can occupy up to 1.7 GB. Output length is unknown when a request arrives, so earlier serving systems reserved one contiguous region per request sized for the maximum possible length. Most of that region stayed empty, and the gaps between regions were too small to reuse. The vLLM team measured that such systems wasted 60-80% of KV cache memory, which capped the batch size long before compute ran out.

How Paging Works#

PagedAttention splits the cache into blocks that each hold the keys and values of a fixed number of tokens, 16 by default in vLLM. A request receives a new block only when its last one fills, from wherever a free block exists, and its block table records the order. The attention mechanism kernel follows that table to gather keys and values block by block, so a sequence's cache never needs to be contiguous. Waste is limited to the unfilled tail of each sequence's last block, under 4% in the vLLM measurements.

This PyTorch sketch stores one request's keys in scattered blocks of a shared pool and reads them back through its block table:

import torch

block_size, head_dim = 16, 64
key_pool = torch.zeros(64, block_size, head_dim)  # physical blocks shared by every request
free_blocks = [41, 7, 19, 2, 33]  # free blocks are scattered across the pool

# A 40-token request needs ceil(40 / 16) = 3 blocks, wherever they happen to be free
keys = torch.randn(40, head_dim)
num_blocks = -(-len(keys) // block_size)
block_table = [free_blocks.pop(0) for _ in range(num_blocks)]
for pos, key in enumerate(keys):
    key_pool[block_table[pos // block_size], pos % block_size] = key

# The attention kernel reads the request's keys back through its block table
gathered = key_pool[block_table].reshape(-1, head_dim)[: len(keys)]
print(f"block table {block_table}, keys intact: {torch.equal(gathered, keys)}")
print(f"unused slots: {num_blocks * block_size - len(keys)} paged vs {2048 - len(keys)} with a 2,048-token reservation")

It prints the block table [41, 7, 19] and keys intact: True, then 8 unused slots for the paged request against 2,008 for a region reserved for 2,048 tokens.

Sharing Blocks Between Sequences#

Block tables also let several sequences point at the same physical blocks. Parallel sampling, beam search, and requests that start with the same system prompt reuse one copy of the shared prefix, with a reference count on each block. When a sequence needs to write into a block that others still use, the engine copies that block first, a copy-on-write step borrowed from operating systems.

The vLLM authors report that this sharing cuts the memory use of parallel sampling and beam search by up to 55%, worth up to 2.2x more throughput. Hashing full blocks extends the idea across requests, which is how vLLM implements prompt caching.

Related Techniques#

PagedAttention decides where cached keys and values live, and it combines with methods that change how much there is to store or how fast it is read:

• Flash Attention: Tiles the attention computation so the full score matrix is never written to GPU main memory. Current engines run FlashAttention-style kernels that read from paged blocks.
• Continuous batching: Admits a new request whenever another finishes, and paging returns the finished sequence's blocks to the free pool at once, so the newcomer has room.
• Grouped-query attention: Shares key and value heads across query heads, shrinking every block's contents.
• FP8 cache quantization: Stores keys and values at 8-bit precision, roughly halving cache memory compared with 16-bit formats.

The Ultralytics LLM interface forwards request arguments unchanged, so a Chat Completions call with n=3 sent through its base_url to a local vLLM server returns three samples that share the prompt's cached blocks, and only their diverging continuations take new memory.