Explain what PagedAttention is, what allocation pathology it eliminates, and why the design choice directly translates into more concurrent requests per GPU. Draw the analogy to a familiar OS-level mechanism.
Free · 2 AI evals / day
During generation, a transformer keeps a **KV cache**: the keys and values for every token seen so far, read back on each decode step. The cache grows as the answer gets longer, and nobody knows in advance how long an answer will be.
The naive fix is to reserve, up front, enough contiguous memory for the longest answer the model could ever produce. If a request only generates 50 tokens but you reserved space for 4000, the other 3950 slots sit allocated but untouched. That waste is called internal fragmentation, and across many requests it can swallow most of the GPU.
PagedAttention borrows the operating-system idea of virtual memory. It chops the cache into small fixed-size blocks, typically 16 tokens each, and keeps a per-request block table that maps logical token positions to physical blocks. Blocks are handed out only when a token actually arrives, and returned when the request finishes.
Because almost no memory sits reserved but empty anymore, the freed space holds more concurrent requests. A bigger batch means each expensive read of the model weights from memory is shared across more tokens, so throughput climbs sharply on the very same GPU.
**PagedAttention** is a KV-cache memory manager, introduced in vLLM, that stores the cache in fixed-size blocks instead of one contiguous slab per request.
The pathology it kills is internal fragmentation. Naive serving reserves contiguous memory sized for the maximum possible completion length, per request. Most requests finish far shorter. So the reserved but untouched tail is dead weight. In practice this wastes 60 to 80 percent of KV memory, so the GPU looks full while most cells are empty.
The fix is exactly OS virtual memory. The cache is sliced into fixed blocks, often 16 tokens each. A per-request block table maps logical token positions to physical block addresses. Blocks are allocated on demand as tokens are generated, and freed when a request completes. Physical blocks need not be contiguous, so external fragmentation disappears too.
Reclaimed memory becomes spendable on more concurrent sequences. Achievable batch size rises roughly 2 to 4 times on the same hardware. Decode is memory bandwidth bound, dominated by streaming the model weights from HBM each step. A larger batch amortizes that one weight read across more tokens. Higher utilization turns directly into higher throughput.
Quick reference
TL;DR
PagedAttention stores the KV cache in fixed-size blocks indexed by a per-request block table, killing the internal fragmentation that contiguous max-length reservation wastes, so batch size and throughput jump.
Imagine a parking garage where every arriving car is told to reserve a whole long lane, just in case it tows a giant trailer. Most cars are tiny, so each lane sits mostly empty, and the garage fills up while half the space is wasted. Now switch to normal parking spots: each car takes only the spots it actually needs, and you keep a little map saying which spots belong to which car. When a car leaves, its spots free up for the next one. PagedAttention does this for the memory that holds a model's running notes. Instead of pre-reserving the longest possible answer per request, it hands out small fixed blocks on demand. The garage fits far more cars, which here means far more chat requests on one GPU.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Single-request, latency-critical decode with no concurrent traffic With one sequence there is little fragmentation to reclaim, and block indirection adds bookkeeping for no batching gain.
Tiny models or very short fixed-length outputs on abundant memory The reserved tail is small, so contiguous allocation wastes little and the allocator complexity is not justified.
Workloads already memory-saturated by weights, not by the KV cache If weights, not the cache, fill HBM, freeing KV fragmentation does not raise the batch you can fit.
Embedding or classification inference with no autoregressive decode loop There is no growing KV cache to page; a single parallel forward pass has nothing to fragment.
Quick scan · 2–4 min
Everything important, quickly.
4 min: define the KV cache and contiguous max-length reservation, name internal fragmentation and its 60 to 80 percent waste, draw the OS paging analogy with a block table, cover copy-on-write prefix sharing, then connect reclaimed memory to bigger batches and weight-read amortization.
Side-by-side
Aspect
Naive contiguous KV
PagedAttention
Allocation unit
One slab per request at max length
Fixed blocks (about 16 tokens) from a pool
Internal fragmentation
60 to 80 percent of KV memory wasted
At most one partial block per request
Indexing
Direct offset into the slab
Block table maps logical to physical
Prefix sharing
Each request holds a private copy
Copy on write across shared blocks
Achievable batch size
Limited by reservations
Roughly 2 to 4 times larger
Real-world examples
Real products, models, and research that use this idea.
1vLLM (UC Berkeley) introduced PagedAttention and reported roughly 2 to 4 times the throughput of prior serving stacks, making it the default engine for most open-source deployments in 2026.
2SGLang builds on paged KV blocks with RadixAttention, sharing prompt-prefix blocks across requests to cut redundant cache for common system prompts on Llama 4 and Qwen 3.
3TensorRT-LLM (NVIDIA) ships a paged KV cache plus chunked prefill as the production reference on H100 and B200 hardware.
4Hugging Face TGI adopted paged KV blocks to lift concurrency on shared inference endpoints serving many tenants.
5DeepSeek V4 pairs Multi-head Latent Attention with paged allocation so the already-small per-token cache packs densely across a large batch.
Interviewer follow-ups
What an interviewer would ask next. Try answering before peeking at the approach.
QWhat is the difference between internal and external fragmentation here, and which does PagedAttention target?
Sign in or go Pro to see the approach for this follow-up.
QHow does copy-on-write block sharing work for a common system prompt across many requests?
Sign in or go Pro to see the approach for this follow-up.
QWhy does a larger batch raise throughput if it does not reduce per-token compute?
Sign in or go Pro to see the approach for this follow-up.
QWhat overhead does the block table add, and why is it cheap relative to the win?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
Calling it a faster attention kernel. PagedAttention changes nothing in the attention math; it is a memory allocator for the KV cache, and the win is utilization, not arithmetic.