Paged Attention

Why Does This Exist?

The KV cache saves enormous amounts of compute during generation, but it trades that compute for memory. As a model generates text, it appends new key and value vectors to the cache for every single token.

Historically, AI frameworks (like PyTorch) managed memory by allocating a single, large, contiguous block of GPU RAM for a sequence's cache. The problem? The framework doesn't know in advance how many tokens the model is going to generate. If it pre-allocates a maximum-size block (e.g., 8,000 tokens) and the model only generates 20 tokens, the remaining 7,980 tokens' worth of memory sits entirely empty and wasted. If it tries to grow the block dynamically, it fragments the GPU memory, eventually failing to find a contiguous space large enough for a new request. This massive waste meant early LLM servers could only handle a tiny fraction of the requests their GPUs were computationally capable of serving.

Paged attention solved this by bringing a classic operating system concept—virtual memory paging—to the GPU.

Think of It Like This

How It Actually Works

Blocks and Block Tables

Paged attention divides the KV cache into fixed-size "blocks" (typically holding the keys and values for 16 or 32 tokens).

When a user sends a prompt, the system breaks the prompt into blocks and allocates physical memory for them wherever space is available on the GPU—they do not need to be next to each other. To keep track of this scattered data, the system maintains a Block Table for each request. The block table maps the logical sequence of the tokens to their physical block addresses in the GPU memory.

Zero waste during generation

As the autoregressive generation loop runs, the model produces new tokens one by one. The system adds these new tokens to the currently active physical block. Once that block fills up (e.g., hits 16 tokens), the system simply asks the GPU for one new, empty physical block, adds it to the request's block table, and continues.

Because memory is requested exactly when it is needed, and only in small 16-token increments, internal fragmentation (wasted pre-allocated space) drops from >50% in naive systems to <4%.

The foundation for sharing

Because the memory is decoupled through a block table, different requests can easily share identical blocks of memory. If two users send identical system prompts, the server only computes and stores the KV cache for that prompt once. It simply points both users' block tables to the exact same physical blocks for those initial tokens. This is the underlying mechanism that makes prefix caching and parallel sampling (like beam search) highly efficient.

Show Me the Code

While the actual CUDA kernels for paged attention (developed by the vLLM team) are highly complex, the logical routing through a block table is straightforward to model in Python.

1class PagedKVCache:2    def __init__(self, block_size: int = 4):3        self.block_size = block_size4        # The physical memory pool (list of available blocks)5        self.physical_blocks: dict[int, list[str]] = {0: [], 1: [], 2: [], 3: []}6        self.free_blocks = [0, 1, 2, 3]7        8    def allocate_block(self) -> int:9        return self.free_blocks.pop(0)10
11class RequestTracker:12    def __init__(self, cache: PagedKVCache):13        self.cache = cache14        self.block_table: list[int] = [] # Maps logical block to physical block index15        self.logical_length = 016        17    def append_token(self, token: str):18        # Do we need a new block?19        if self.logical_length % self.cache.block_size == 0:20            new_block_idx = self.cache.allocate_block()21            self.block_table.append(new_block_idx)22            23        # Find the physical block for the current logical end24        current_logical_block = self.logical_length // self.cache.block_size25        physical_idx = self.block_table[current_logical_block]26        27        # Store the token in the physical block28        self.cache.physical_blocks[physical_idx].append(token)29        self.logical_length += 130        print(f"Token '{token}' -> Physical Block {physical_idx}")31
32# Initialize system33memory = PagedKVCache(block_size=2)34req = RequestTracker(memory)35
36# Simulate generation37req.append_token("The")  # -> Physical Block 038req.append_token("cat")  # -> Physical Block 039req.append_token("sat")  # -> Physical Block 1 (New block allocated!)40req.append_token("on")   # -> Physical Block 1

Notice how the RequestTracker seamlessly flows across physical blocks, allocating new ones exactly when the previous one fills up, wasting zero space.

Watch Out For

The Quick Version

• Naive KV cache management wastes massive amounts of GPU memory by pre-allocating large, contiguous chunks that often go unused.
• Paged attention solves this by breaking the KV cache into small, fixed-size blocks (e.g., 16 tokens).
• A Block Table maps a sequence's logical tokens to physical blocks scattered anywhere in GPU memory.
• New blocks are allocated dynamically only when needed, dropping memory waste from >50% to <4%.
• This architecture enables safe memory sharing across concurrent requests, drastically increasing total server throughput.

What to Read Next

• KV Cache explains the mathematical necessity of saving these vectors in the first place.
• Prefix Caching explores how paged attention's block tables allow multiple users to safely share the exact same physical memory.
• Beam Search (upcoming) heavily leverages paged attention, as parallel beams can share a single block table for their shared prefixes.