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.
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.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
PagedAttention is the single change that turned LLM serving from a memory-wasting embarrassment into a dense, high-throughput system. It is also a favorite hard short-answer because it sits at the intersection of two things candidates rarely hold together: the autoregressive KV cache and operating-system memory management.
The core claim is small and exact. PagedAttention does not change the attention computation at all. It changes where the KV cache lives in memory. Naive serving reserves a contiguous block per request, sized for the maximum possible completion, and most of that reservation is never used. PagedAttention instead allocates the cache in small fixed-size blocks on demand, tracked by a per-request block table, exactly the way an operating system maps a process's virtual pages to physical frames.
This deep dive builds the argument in order. First, why the KV cache forces an allocation decision. Second, why the naive contiguous choice wastes most of the memory through internal fragmentation. Third, how the paging design eliminates that waste and unlocks copy-on-write prefix sharing as a bonus. Finally, why reclaimed memory converts so directly into batch size and throughput. By the end you should be able to defend the claim that this is an allocator, not a kernel, and that the win is utilization rather than arithmetic.
Why the KV cache forces an allocation problem
Autoregressive decoding emits one token at a time. To produce the next token, the attention layer reads the keys and values of every prior token. To avoid recomputing those projections each step, the server stores them in the KV cache, which grows by one row per layer per decode step.
The awkward part is that nobody knows how long a completion will be when the request arrives. A chat reply might be 20 tokens or 2000. The server must decide how much memory to set aside before it has any idea of the answer length.
This is the allocation problem PagedAttention exists to solve. Get it wrong and you either crash when a long generation overflows its reservation, or you over-reserve and starve the rest of the batch. The naive answer to this uncertainty is the source of the waste, as the next section shows.
Two flavors of waste are worth separating now. The first is the obvious one: you reserve for a 4096-token answer and the user gets 50 tokens, so the tail is dead. The second is subtler. Even requests that do eventually grow long spend most of their lifetime short, so a slab sized for the eventual maximum is mostly idle for most of the request's duration. Both flavors are internal fragmentation, and both are present at every instant the scheduler tries to admit new work. The allocator's job is to make memory usage track actual token count rather than a worst-case guess.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| 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 products, models, and research that use this idea.
- vLLM (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.
- SGLang 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.
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?
Internal is the reserved but untouched tail inside one request's max-length slab. External is unusable gaps between separate allocations. Paging fixes internal directly by allocating per generated token; non-contiguous physical blocks also remove external fragmentation.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
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.
60 second bullets to scan on the way to the call.
What internal fragmentation is and why contiguous max-length reservation causes it
The rough magnitude of wasted KV memory under naive allocation
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.