Identify PagedAttention and the project it ships with

Attempt it

PagedAttention is the KV-cache allocator introduced by vLLM (UC Berkeley). It stores K and V in fixed-size blocks indexed by a per-sequence block table, exactly mirroring how an operating system maps virtual pages to physical frames. The win is that naive contiguous allocation has to reserve max-length up front per sequence, wasting tens of percent of HBM to internal fragmentation. Paging lets vLLM pack many more concurrent sequences into the same GPU, which is the single biggest reason its throughput jumped over earlier servers.

Your answer

**PagedAttention** is a memory-allocation trick for the KV cache, introduced by the vLLM serving engine from UC Berkeley in 2023. Before PagedAttention, serving stacks allocated the KV cache as one contiguous slab per sequence, sized for the maximum context the model could handle. If the model supported 8k tokens but the user only sent a 200-token request, the allocator still reserved 8k worth of cache. That reservation sat half-empty while other waiting requests could not be admitted because HBM was nominally full. PagedAttention borrows the operating-system paging idea. The KV cache is split into fixed-size blocks (typically 16 tokens each), and each sequence holds a block table that lists which physical blocks it currently uses. When the sequence grows by one token, it asks for another block from a free pool. When it finishes, its blocks return to the pool for reuse. The consequence is dense HBM packing. Many more concurrent sequences fit on the same GPU, batches stay full, and throughput jumps. That was the single biggest reason vLLM outperformed earlier servers when it launched. The attention kernel itself does not change; only the memory layout and the address indirection do.

**PagedAttention** is the block-based KV-cache allocator that ships with vLLM, the open-source LLM serving engine from UC Berkeley. It is the canonical example of borrowing a systems idea (OS virtual memory paging) and applying it to ML serving. The problem it solves is fragmentation. Without paging, the KV cache must be allocated contiguously per sequence. The only safe size for that contiguous allocation is the model's maximum supported context length, because the system does not know in advance how long the sequence will become. So a 200-token request reserves space for 8k or 32k tokens. Across many concurrent sequences, this wastes tens of percent of HBM to internal fragmentation. The GPU looks full but is mostly holding placeholders. PagedAttention divides the KV cache into fixed-size blocks (typically 16 tokens). Each sequence maintains a block table mapping its logical positions to physical block indices, exactly like a virtual-memory page table. As the sequence decodes, it claims more blocks on demand from a global free pool. As sequences finish, their blocks return to the pool. The benefits compound: more concurrent sequences fit, larger batches stay full, prefix caching becomes natural (two sequences sharing a prefix can share blocks), and continuous batching has somewhere to put newly admitted requests mid-flight. PagedAttention is the foundation under almost every modern serving optimization.

Quick reference

TL;DR

PagedAttention is vLLM's block-based KV-cache allocator that borrows OS virtual-memory paging, eliminating the fragmentation waste of contiguous max-length reservations.

Memory aid

Sign in for the mnemonic that makes this stick. See Pro pricing.

Easy to grasp

Imagine renting a parking garage where every car gets a private aisle sized for the biggest truck the garage might ever see. Hatchbacks waste most of their aisle. Now picture the garage manager dividing every aisle into uniform stalls and giving each car only the stalls it actually needs, picked from anywhere in the building. A central clipboard remembers which stalls belong to which car. The garage fits far more cars, and nobody hoards space they will never use. PagedAttention is that clipboard for the KV cache: fixed-size blocks anywhere in HBM, looked up through a per-sequence table.

Key concepts

PagedAttention vLLM KV cache Continuous batching

Detailed answer & concept explanation

~5 min read

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.

Sign in for 5 free unlocks/day or go Pro for unlimited. See Pro pricing.

Quick scan · 2–4 min

Everything important, quickly.

3 min: vLLM origin + OS paging analogy + the fragmentation problem with contiguous allocation + block tables + enabler for continuous batching and prefix caching.

Real-world examples

Real products, models, and research that use this idea.

vLLM, the project that introduced PagedAttention, is the default open-source serving engine in 2026 for Llama 3.1, Mistral Large 3, and DeepSeek V4 deployments.
Hugging Face TGI adopted block-based KV allocation directly inspired by PagedAttention.
NVIDIA TensorRT-LLM ships its own paged KV implementation to support continuous (in-flight) batching on H100 and B200.
SGLang uses RadixAttention, a tree-structured variant of paged KV that captures shared prefixes across many concurrent requests.
Anthropic's prompt caching and OpenAI's automatic prefix caching are conceptually downstream of paged KV: sharing physical blocks for byte-identical prefixes.

Interviewer follow-ups

What an interviewer would ask next. Try answering before peeking at the approach.

QHow does PagedAttention enable prompt prefix caching?

Sign in or go Pro to see the approach for this follow-up.

QWhat is the overhead of the extra indirection on attention compute?

Sign in or go Pro to see the approach for this follow-up.

QHow does SGLang's RadixAttention extend PagedAttention?

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 PagedAttention a new attention math. It is a KV-cache allocator. The math is unchanged; only how K and V are laid out in HBM differs.

Sign in or go Pro to see all red flags and common mistakes. See Pro pricing.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

Sign in for 5 unlocks/day or go Pro for unlimited revision sheets. See Pro pricing.

References

Primary sources. Skim if you want the original framing.