PagedAttention & Continuous Batching
PagedAttention and continuous batching are the default pair behind modern open serving. Block tables make KV virtual memory. An iteration-level scheduler admits and finishes requests without waiting for a static batch. RadixAttention is a different sharing layer and stays in the SGLang study.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
How does the batch change?
Prefer
Iteration-level schedule on a block pool
Every step can admit a prefill or a chunk, drop a finished sequence, and run whatever remains. Blocks are allocated as the sequence grows and freed when it ends.
- Logical tokens map to physical block ids.
- Attention gathers through the table.
- Beams share blocks until a write forces a copy.
Alternative
Wait for a full static batch, then run to completion
Short sequences finish and the GPU waits on the long one. Late arrivals sit in queue. Contiguous slabs cannot be carved when membership changes every step.
- Simple to explain, poor occupancy under chatty arrivals.
- p99 latency tracks the slowest member of the batch.
- No copy-on-write, so beams duplicate the prefix.
Overview
PagedAttention, popularized by vLLM, and continuous (in-flight) batching are the mechanism pair this cluster treats as the default. SGLang also runs continuous batching. Its distinctive prefix structure is RadixAttention. That walk-through is SGLang — RadixAttention, Continuous Batching & Structured Generation. This page does not repeat it.
Block tables
Physical memory is a pool of fixed-size KV blocks. A common teaching size is 16 tokens of K and V. Real engines differ on whether a block covers all layers or a per-layer pool. The idea is stable.
A block table maps logical token positions to physical block ids. The sequence grows by allocating a block when the current one fills. Finished requests return blocks to the free list. Tokens 0..N may sit in scattered physical blocks. The attention kernel gathers through the table instead of assuming one contiguous slab.
That is virtual memory. Logical pages, a page table, a physical frame pool. Internal fragmentation is the leftover slots in the last block. External fragmentation of the old slab allocator mostly goes away.
Copy-on-write
Beam search and n parallel samples share a prompt prefix. On fork, the child copies the parent’s block ids and increments a reference count. A later write into a shared block allocates a fresh block, copies, then writes. Until that write, the prefix KV is stored once.
Forgetting copy-on-write and cloning the whole prefix is a fast way to OOM a beam.
Continuous batching
Static batching waits until a batch fills, then runs every member to completion. The GPU goes idle when short sequences finish. Late joiners wait for the next batch. Tail latency follows the longest member.
Continuous batching recomputes the working set every iteration:
- Admit new requests (full prefill or a chunk).
- Drop finished requests and free their blocks.
- Run one mixed batch of whatever lengths remain.
Occupancy goes up because the iteration is full of useful tokens. Fairness is now a policy: without admission control, a flood of new prefills starves decode and time-to-first-token explodes.
TensorRT-LLM’s in-flight batching is the same family of idea, productized inside the engine. See TensorRT-LLM — Engine Build, In-Flight Batching & Quantization. This page does not build an engine.
Why paging and continuous batching need each other
Membership changes every iteration. A contiguous max-length slab cannot be sliced cheaply for sequences that arrive and leave. Fine-grained blocks can. Continuous batching without paging falls back to waste. Paging without an iteration-level scheduler still waits on static batch barriers.
vLLM, as the reference story
The PagedAttention paper introduced the block table to raise throughput by using KV memory more tightly. Many engines now page, or do something analogous. vLLM remains the open reference for the block-table explanation. It is not the only implementation. The comparative choice against SGLang is vLLM vs SGLang — Runtime Choice (comparative).
Paging versus prefix trees
| Mechanism | Unit of sharing | Best when | Depth |
|---|---|---|---|
| PagedAttention block table | Blocks inside one sequence, and forks of that sequence | General multiplexing, beams | This lesson and vLLM docs |
| RadixAttention prefix tree | Token prefixes across requests | Shared system prompts, multi-turn, routers | SGLang study |
Both compose with continuous batching. Radix is cross-request prefix hits. Paging is allocation geometry. Paging alone does not reuse a system prompt that arrived as a different request. You still want the prefix layer for that.
Flow
- 1
1 Logical tokens 0 through S
- next2 Block table maps ids
- 2
2 Block table maps ids
- next3 Physical block 7
- 3
3 Physical block 7
- next4 Physical block 3
- 4
4 Physical block 3
- next5 Physical block 19
- 5
5 Physical block 19
- next6 Scheduler iteration t
- 6
6 Scheduler iteration t
- next7 Admit, finish, or run
- 7
7 Admit, finish, or run
Lesson map
PagedAttention & Continuous Batching
PagedAttention and continuous batching are the default pair behind modern open serving. Block tables make KV virtual memory. An iteration-level scheduler admits and finishes requests without waiting for a static batch. RadixAttention is a different sharing layer and stays in the SGLang study.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1 Logical tokens 0 through S"] b["2 Block table maps ids"] c["3 Physical block 7"] d["4 Physical block 3"] a -->|1 Logical tokens 0 through S| b b -->|2 Block table maps ids| c c -->|3 Physical block 7| d
The blocks are a chain in the diagram so the page stays a single column. In the pool they are scattered. The table is what makes the scatter addressable.
Flow
- 1
1 Iteration t starts
- next2 Allocate blocks for prefills
- 2
2 Allocate blocks for prefills
- next3 Run mixed prefill and decode
- 3
3 Run mixed prefill and decode
- next4 Append KV into mapped blocks
- 4
4 Append KV into mapped blocks
- next5 Free finished sequences
- 5
5 Free finished sequences
- next6 Copy-on-write fork for beams
- 6
6 Copy-on-write fork for beams
- next7 Next iteration, new membership
- 7
7 Next iteration, new membership
Sandbox: toy block table
Block size is 4 tokens. Growing 10 tokens allocates 3 blocks. A fork shares those ids and bumps the reference count. The toy stops before a real copy on write.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pros and cons
| Choice | Gain | Cost |
|---|---|---|
| PagedAttention | Utilization and copy-on-write | Kernel complexity. Block too small means overhead. Block too large means internal fragmentation |
| Continuous batching | Tokens per second under load | Needs admission control so TTFT holds |
| Static batching | Predictable | Rarely right for multi-tenant chat |
| Radix prefix cache | Cross-request sharing | Separate from paging. SGLang study |
Pitfalls
Block size 16. A request ends at 20 tokens. How many blocks, and how many tokens of internal fragmentation? Now fork a beam of width 4 before any divergence. How many physical blocks do you hold before the first differing token, with copy-on-write versus a full clone?
Interview Q&A
Explain PagedAttention like virtual memory.
Answer
Logical token pages map through a block table to physical KV blocks. The engine allocates and frees those blocks independently, so a sequence does not need one contiguous max-length region. Attention gathers with the table. Packing goes up because finished requests return blocks immediately.
Why does continuous batching need something like paging?
Answer
The set of running sequences changes every iteration. Contiguous max-length slabs cannot be carved and returned cheaply as requests arrive and finish. Fixed blocks can. Without that, the scheduler either wastes memory or stops being iteration-level.
How is this different from SGLang RadixAttention?
Answer
Paging is allocator geometry for one engine’s KV pool, including forks of a sequence. RadixAttention is a prefix tree that reuses KV across requests that share tokens. See SGLang — RadixAttention, Continuous Batching & Structured Generation for the tree. Both sit on continuous batching.
What does copy-on-write save in beam search?
Answer
Until a beam writes a new token into a shared block, every beam points at the same physical prefix. You store the prompt KV once. The first divergent write copies that block. Naive duplication stores the prefix once per beam and OOMs at modest width.
Static versus continuous batching in one minute.
Answer
Static waits for a full batch and runs it to completion. Simple, and the GPU waits on stragglers while new requests queue. Continuous rebuilds the batch every iteration: admit, finish, run. Utilization and tail latency improve if you also limit admissions. Unbounded admission trades TTFT away.
How do you pick a block size?
Answer
Too small and you pay table overhead and more kernel bookkeeping. Too large and the last block wastes tokens (internal fragmentation). Sixteen is a common teaching number, not a universal optimum. Measure waste and allocator overhead on your length mix.
Is TensorRT-LLM in-flight batching the same code as vLLM?
Answer
Same idea family: do not freeze a static batch. The product integration, engine build, and quantization are TensorRT-LLM — Engine Build, In-Flight Batching & Quantization. Do not pretend the block-table toy is that engine.
What fails if you page KV but never cap concurrency?
Answer
The free list hits empty, or decode steps share the GPU with a stampede of prefills. Time-to-first-token blows up even though the allocator is “efficient.” Admission control is part of the scheduler, not an optional dashboard.
Does a block table reuse a system prompt across users?
Answer
Not by itself. Forks share blocks inside one request family. Two HTTP requests with the same system prompt are two sequences unless a prefix cache hits. That is the radix layer, not the page table.
Where did the block-table story come from?
Answer
The vLLM PagedAttention work used it to raise serving throughput through KV memory efficiency. Treat vLLM as the reference open implementation of that story. Other runtimes adopted paging or analogous allocators afterward.