What is paged attention in vLLM, and why does it matter?

In this article

1. Before you start
2. Why interviewers ask this
3. Paged attention from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the large language model (LLM) inference optimization learning path.

Why interviewers ask this

PagedAttention is the idea that made modern language model serving cheaper, and it is the standard example of an operating-system idea solving a machine learning problem. Interviewers ask about it to see whether you know that serving capacity is a memory-management question, not only a compute question.

A weak answer says "it makes attention faster." A strong answer says what is wasted today (space reserved for tokens that never arrive), what the fix is (small fixed blocks plus a table), and what it costs (a lookup in the attention kernel). The question also arrives as "how would you serve more concurrent users on one GPU?", where paging is one of three or four levers.

Paged attention from first principles

PagedAttention

PagedAttention is an attention method that reads a request's KV cache from fixed-size blocks located through a block table, so the cache need not sit in one contiguous stretch of GPU memory.

KV block

A KV block is a fixed-size unit of cache memory that holds the keys and values of a fixed number of tokens, 16 by default in vLLM, the open serving engine built on PagedAttention.

In plain words

Think of a hotel that books a whole floor for every guest group. The floor is sized for the largest party that might ever come. Most groups use two rooms. The rest of the floor sits empty but locked. Paging is the hotel switching to single rooms, handed out as guests arrive. A front-desk list says which rooms belong to which group. The analogy breaks in one place: the list costs a lookup each time a guest is found. In a model, that lookup happens inside the attention computation.

In one precise sentence: PagedAttention divides every request's KV cache into small blocks, allocates a block only when the last one is full, and finds blocks through a table. It borrows the virtual-memory idea of an operating system. Blocks play the part of pages, tokens of bytes and requests of processes (Kwon et al., 2023).

Step 1: A contiguous reservation wastes memory

Before paging, serving systems reserved one contiguous slab per request, sized for the longest sequence the request might reach. The cache of a sequence is not known in advance because the model decides when to stop, so the safe choice was the maximum length.

For Llama 3 8B, whose configuration lists 32 layers, 8 KV heads, a head size of 128 and a maximum of 8,192 positions as of October 2026 (model configuration), each token costs 128 KiB of cache, so a full reservation is 1 GiB per request.¹ A request that has produced 700 tokens uses 8.5% of it and wastes 91.5% for as long as it runs.¹ Kwon et al. add that other short requests cannot use the idle part, and that slabs of different sizes also fragment the memory around them. You now know the problem: reserved space that no one can use.

Step 2: Fixed-size blocks replace the single slab

PagedAttention cuts the cache into blocks that each hold a fixed number of tokens. The default in vLLM is 16 tokens, which the authors chose because it is large enough to use the GPU efficiently and small enough to avoid much waste. Internal fragmentation is the unused tail of a request's last block.

Because every block has the same size, a free block always fits any request, so external fragmentation disappears. External fragmentation is the memory lost between differently sized allocations. A request holding 700 tokens needs 44 blocks, which is 704 slots, so only 4 slots are idle, 0.57% of what it holds.¹ Input: a growing request. Output: a list of small blocks. The waste per request is now bounded by one block.

Step 3: A block table maps logical blocks to physical blocks

The blocks of one request do not have to sit next to each other. The block table records, for each logical block in token order, which physical block holds it and how many of its slots are filled, and the attention kernel follows the table to read the keys and values.

Kwon et al. (2023) walk through a 7-token prompt with 4 tokens per block: logical blocks 0 and 1 map to physical blocks 7 and 1, the prefill pass fills them, and the last slot waits for the next generated token. The vLLM design page shows the kernel computing key addresses from a block number (vLLM documentation).

This table plays the part of the operating system's page table; vLLM's block manager keeps it beside a pool of free blocks and a reference count per block (Kwon et al., 2023). Because any free block can be the next one, allocation follows the tokens instead of a reserved maximum: vLLM kept 96.3% of cache memory holding tokens, against 20.4% to 38.2% above (Kwon et al., 2023, Fig. 2).

Step 4: Blocks are allocated on demand and freed on finish

At each decoding step the system writes the new token's keys and values into the last block. A new physical block is allocated only when the last one is full, and the request never reserves its maximum length in advance. As Kwon et al. put it, all of a request's waste is limited to within one block.

When the request ends, its blocks return to a free pool and any other request can take them immediately. That is why more requests fit into the same memory, which raises the batch size and with it throughput: the authors report 2 to 4 times higher throughput than FasterTransformer and Orca at the same latency, with larger gains for longer sequences and larger models (their own evaluation).

1 · Reserve the maximum2 · Cut into blocks3 · Map with a table4 · Free on finishReplay

Step-by-step description

1. One slab is reserved for the whole maximum length.
2. The cache becomes fixed-size blocks of 16 tokens.
3. A block table maps logical blocks to physical blocks.
4. Blocks are freed to the pool when the request ends, then reused on demand.

• A contiguous reservation holds the whole maximum length for the life of the request.
• Fixed-size blocks hold a fixed number of tokens each.
• The block table maps each logical block to a physical block.
• When the request ends, its blocks return to a free pool.

Worked example

Take eight requests on Llama 3 8B whose current lengths are 128, 700, 1,500, 300, 2,900, 50, 4,100 and 900 tokens, an illustrative batch, not a measurement.¹ Together they hold 10,578 tokens. With a maximum-length slab each, the system reserves 8 × 8,192 = 65,536 slots, so 16.1% of the reserved slots hold tokens. With 16-token blocks the same requests occupy 10,640 slots, so 99.4% are in use.¹

The effect on capacity follows. Suppose 64 billion bytes are left for the cache after the weights, an illustrative figure. Slabs fit 59 requests. Blocks, at the batch's average length of about 1,322 tokens, fit about 367 requests, 6.2 times as many.¹ Real servers lose some memory to other buffers and the blocks counted here are a best case, so the true gain is smaller; the authors' measured profile of earlier systems, 20.4% to 38.2% useful memory, is the number to quote.

Text description of the diagram

• With contiguous reservation at the maximum length, 16.1 percent of the reserved slots hold tokens.
• With 16-token blocks, 99.4 percent of the allocated slots hold tokens.

Trade-offs and edge cases

PagedAttention trades a small lookup cost and a block-size choice for a large saving in memory. Four points decide how it behaves.

First, kernel cost. The block table adds table reads, extra branches and variable-length handling, which Kwon et al. measured in 2023 as 20% to 26% higher attention-kernel latency than FasterTransformer's optimised kernel (a 2023 figure; kernels have changed since), while the rest of the model is unaffected; the end-to-end throughput still rises.

Second, block size. Too small, and the GPU cannot read the cache efficiently in parallel. Too large, and internal fragmentation grows and sharing becomes less likely. The authors found sizes from 16 to 128 best on one trace and 16 or 32 best on shorter sequences (Kwon et al., 2023).

Third, sharing. Because blocks are the unit, requests with the same prompt can point their tables at the same physical blocks. A reference count tracks the sharers, and copy-on-write, the rule that a block shared by several sequences is copied the moment one of them needs to change it, keeps their outputs separate. This helps parallel sampling and beam search.

Fourth, prefix reuse across requests builds on the same blocks. vLLM's automatic prefix caching hashes full blocks and evicts the least recently used ones (vLLM documentation, read October 2026), while SGLang's RadixAttention keeps prefixes in a radix tree; the SGLang authors report up to 6.4 times higher throughput than other systems on their tests (SGLang (Zheng et al., 2024)). FlashAttention is a different lever again: it speeds up the attention computation itself rather than managing cache memory, and the two combine. Narrower cache values, covered in 16-bit number formats, shrink every block. The machine learning operations (MLOps) hub places serving in the wider picture.

Text description of the diagram

• Contiguous reservation wastes the unused part of the reservation, while paging wastes under one block per request.
• External fragmentation disappears because every block has the same size.
• Requests with the same prompt can point their tables at the same physical blocks, with copy-on-write.
• The block table adds extra lookups to the attention kernel.

How to answer it in an interview

The spoken structure: name the waste, give the block-and-table fix, then say the cost and one more benefit.

Common mistakes

• "Paged attention makes the attention math faster." (wrong) It changes where the cache lives, not the arithmetic, and the kernel is slightly slower per call. (right) "It raises throughput by fitting more requests in memory."
• "It compresses the KV cache." (wrong) Every token still stores the same keys and values. (right) "It removes wasted space around the cache, not the cache itself."
• "It removes all fragmentation." (wrong) Each request still wastes up to one partly filled block. (right) "Waste is bounded by one block per request."
• "Paged attention and FlashAttention are the same idea." (wrong) One manages cache memory, the other reorganises the attention computation. (right) "They solve different problems and are used together."

Follow-up questions

What is paged attention in vLLM?

PagedAttention is the attention method at the heart of vLLM, an open-source inference engine from the authors of the paper. vLLM combines it with a block manager that allocates and frees blocks as requests grow and finish.

vLLM vs LLM: what is the difference?

An LLM, a large language model, is the neural network that generates text. vLLM is a serving engine that runs such a model efficiently; the two names are unrelated except by the abbreviation.

FlashAttention vs paged attention: which solves what?

FlashAttention speeds up the attention computation by reorganising its memory reads, while paged attention manages where the KV cache lives so less memory is wasted. A serving stack can use both.

Paged attention vs radix attention?

Paged attention is a block-based layout of the cache inside one server. Radix attention, from the SGLang system, is a way of finding and evicting cached prefixes with a radix tree. Both systems reuse prefixes across requests; they differ in how prefixes are found and evicted (vLLM hashes full blocks, SGLang walks a tree), and the block layout of paged attention is the layer underneath either.

What happens when the GPU runs out of free blocks?

The server preempts a request. Its blocks are either swapped to central processing unit (CPU) memory, which is KV cache offloading, or dropped and recomputed later in one prefill pass (Kwon et al., 2023, §4.5). Recomputation suits small blocks and swapping suits large ones, and recomputation never cost more than 20% of swapping's latency in their tests (§7.3).

How does LLM caching work?

During generation the model stores each token's attention keys and values and rereads them at each step instead of recomputing them. The KV cache page explains the mechanism; paging is how that cache is laid out in memory.

Sources

1. Efficient Memory Management for Large Language Model Serving with PagedAttention — arXiv (Kwon et al.), SOSP 2023, 12 Sep 2023
2. Paged Attention (vLLM design documentation) — vLLM documentation (date = read date; the page says it describes the original design), 24 Oct 2026
3. SGLang: Efficient Execution of Structured Language Model Programs — arXiv (Zheng et al.), v2, 6 Jun 2024
4. Automatic Prefix Caching (vLLM design documentation) — vLLM documentation (date = read date), 24 Oct 2026
5. Meta-Llama-3-8B config.json (mirror of the model configuration) — Hugging Face (date = read date), 24 Oct 2026