PagedAttention

On this page 7

PagedAttention is an attention algorithm for large language model inference that stores the key-value (KV) cache in small, fixed-size blocks that need not be contiguous in GPU memory, in the same way an operating system maps virtual memory pages to physical frames. In AI infrastructure, it is the core memory management technique of the vLLM serving engine, introduced by researchers at UC Berkeley in 2023.

By allocating cache memory on demand, block by block, PagedAttention removes most of the fragmentation that earlier serving systems suffered, lets requests share cache blocks for common prompt prefixes, and allows a server to batch substantially more concurrent sequences on the same GPU.

Why the KV cache needs paging

PagedAttention exists because the KV cache is large, grows unpredictably and dominates inference memory. During autoregressive decoding, every generated token appends a key vector and a value vector per layer and per attention head. For a 13-billion-parameter model in 16-bit precision, one token occupies roughly 800 KB of cache, so a single 2,000-token sequence can consume about 1.6 GB.

Earlier serving systems reserved a contiguous buffer sized for the maximum sequence length for each request. Because the final output length is unknown in advance, most of that reservation stayed empty. The original vLLM analysis reported that such systems used only 20 to 40 percent of KV cache memory for actual token states, with the remainder lost to three kinds of waste.

Waste typeCauseEffect of PagedAttention
Reservation wasteSpace held for tokens not yet generatedBlocks allocated only when needed
Internal fragmentationSequence ends before the reserved maximumWaste limited to the last partial block
External fragmentationFree memory split into unusable gapsAny free block can serve any sequence
Duplicated prefixesIdentical prompts cached once per requestShared blocks with reference counting
Sources of KV cache waste that paging addresses

How PagedAttention maps logical blocks to physical memory

PagedAttention divides each sequence’s cache into logical blocks of a fixed number of tokens, commonly 16 tokens per block, and records in a block table which physical GPU block holds each logical block. The physical blocks can sit anywhere in a preallocated memory pool.

The attention kernel is rewritten to follow this indirection. When computing attention for a new query token, the kernel reads the block table, gathers keys and values block by block from scattered locations and accumulates the result. A small amount of extra address computation is the price for removing the contiguity requirement, and optimized kernels keep that overhead modest.

  1. A request arrives and the prefill phase writes the prompt’s keys and values into as many blocks as required.
  2. During decoding, each new token fills the last partial block; a fresh block is allocated only when it is full.
  3. When the request finishes, its blocks return to the free pool immediately for reuse by other sequences.
  4. Under memory pressure, the scheduler can preempt a sequence by swapping its blocks to CPU memory or discarding them for later recomputation.

Block sharing and copy-on-write

Because the block table adds a level of indirection, several sequences can point to the same physical blocks. This enables memory sharing in decoding scenarios where outputs share a common history, and each block carries a reference count that tracks how many sequences use it.

When a shared block must be modified by one sequence, the engine applies copy-on-write: it copies the block, updates that sequence’s table and leaves the others unchanged. The table below shows where sharing saves the most memory.

ScenarioWhat is sharedTypical benefit
Parallel samplingPrompt blocks across several candidate outputsPrompt cached once for all samples
Beam searchPrompt and common beam historyLarge savings as beams overlap
Common system promptIdentical instruction prefix across usersLower memory and faster prefill
Multi-turn chatEarlier conversation turnsReuse when prefix caching is enabled
Decoding scenarios that benefit from block sharing

PagedAttention is a memory layout technique, and it is often confused with optimizations that address compute speed or scheduling. In practice it is combined with them rather than chosen instead of them.

TechniqueMain targetRelation to PagedAttention
PagedAttentionKV cache memory efficiencyDefines block-based cache layout
FlashAttentionAttention compute and memory bandwidthComplementary; paged variants exist
Continuous batchingGPU utilization across requestsBenefits from freed memory capacity
Prefix cachingRepeated prompt computationBuilt on shared block tables
KV cache quantizationBytes per cached tokenShrinks each block, stacks with paging
How PagedAttention relates to neighboring optimizations

The combination with continuous batching is especially important. Paging frees memory as soon as a sequence finishes, and the scheduler immediately fills that capacity with waiting requests. Together they explain the two to four times higher throughput that vLLM reported against earlier systems at similar latency; the exact gain depends on model, hardware and request length distribution.

Tuning limits and practical trade-offs

PagedAttention is now standard in production serving, but its benefits depend on configuration and workload. Engines such as vLLM, SGLang and TensorRT-LLM implement paged KV caches, each with its own kernels and defaults.

  • Block size trades memory efficiency against kernel efficiency: small blocks waste less memory, while larger blocks improve memory access patterns.
  • GPU memory utilization settings decide how much memory the cache pool reserves; setting them too high leaves no headroom for activations and causes out-of-memory errors.
  • Preemption by recomputation saves PCIe bandwidth but repeats prefill work, which hurts latency for long prompts.
  • Custom kernels must support paging, so new attention variants or hardware may lag behind until paged implementations exist.

A common misconception is that PagedAttention makes models faster per token. Its main effect is higher throughput through larger batches; single-request latency stays similar or rises slightly from indirection overhead.

In plain words

When a chatbot writes an answer, it keeps a running memory of everything said so far, and that memory grows with every word. Older systems set aside one big empty shelf for each conversation in case the answer turned out long, and most of that shelf stayed unused.

PagedAttention instead hands out small boxes as they are needed and keeps a list of where each box is stored. Nothing is reserved in advance, boxes can sit anywhere, and identical content can be shared. The result is that the same graphics card serves many more people at once.

A real-world example

A software company runs an internal coding assistant on a single server with eight 80 GB GPUs hosting a 70-billion-parameter model. With its earlier serving stack, which reserved full-length cache buffers, the server handled about 20 concurrent requests before running out of memory, and developers saw queues during busy hours.

After moving to an engine that uses PagedAttention and continuous batching, the team keeps the same hardware. Every request starts with an identical 1,500-token system prompt, which is now cached once and shared. Concurrency rises to roughly 70 simultaneous requests, throughput grows about threefold, and queuing delays at peak hours largely disappear, so the planned purchase of a second server is postponed by several quarters.