Skip to content
Road to Intelligence

Concept · Chapter 11: Inside Modern LLMs

PagedAttention and Continuous Batching

10 minDifficulty

PagedAttention stores each request's KV cache in small fixed-size blocks found through a lookup table, like an operating system's virtual memory, so memory is allocated as tokens arrive, wasted space nearly disappears, and requests can share common blocks; with batching at the level of individual decode steps, far more users fit on a GPU.

The problem

Servers reserved a contiguous cache region per request for its maximum possible length; most of that memory sat empty or fragmented, which capped how many requests could be batched together.

The solution

Split the cache into blocks of a few tokens, allocate them on demand anywhere in memory, map each request's logical blocks to physical ones with a block table, and share blocks (copy-on-write) when requests have common prefixes or samples.

The consequence

Larger batches on the same hardware, and so higher throughput: the vLLM paper reports 2–4× over the systems it compared. Paging, prefix sharing and step-level scheduling became standard in LLM servers.

You should understand first

  1. Vectors
  2. Dot Product
  3. Embeddings
  4. Attention
  5. Probability and Distributions
  6. Softmax
  7. Self-Attention
  8. Causal Masking
  9. Text as Data
  10. Conditional Probability and Bayes' Theorem
  11. Probability of Sequences
  12. Language Modeling
  13. Entropy
  14. Loss Functions
  15. Cross-Entropy Loss
  16. Autoregressive Next-Token Prediction
  17. Matrix Multiplication
  18. Multi-Head Attention
  19. Positional Encoding
  20. Residual Connections
  21. Layer Normalization
  22. Feed-Forward Sublayer (MLP)
  23. The Transformer Block
  24. Prefill, Decode and the Memory Wall
  25. The KV Cache
  26. PagedAttention and Continuous Batching

Memory you reserved but never used

A request's KV cache grows one token at a time, and nobody knows in advance how long the reply will be. Earlier servers reserved a contiguous region for the maximum length up front. Kwon and colleagues measured that in existing systems only 20.4–38.2% of KV-cache memory held actual token states; the rest was lost to reservations and fragmentation . Since decoding is memory-bound, memory that can't hold another request is throughput thrown away.

Pages, from operating systems

PagedAttention, inspired by virtual memory and paging in operating systems, stores the KV cache in fixed-size blocks that need not be contiguous; a block table maps each request's logical blocks to physical ones, and new blocks are allocated as tokens are generated .

Tiny example. With 16-token blocks, a request that has produced 70 tokens holds five blocks: four full and one with 6 of 16 slots used. At most 15 slots are ever wasted per request, instead of everything between its current and maximum length.

Blocks can also be shared. When several sequences share a prefix (parallel samples from one prompt, for example), vLLM maps them to the same physical blocks and copies a block only when one sequence needs to modify it, like copy-on-write when an operating system forks a process .

The vLLM server built on PagedAttention achieved near-zero waste in KV-cache memory and 2–4× higher throughput at the same latency than FasterTransformer and Orca, with larger gains for longer sequences, larger models and more complex decoding .

Batch by step, not by request

Requests arrive at different times and finish at different lengths. If a batch runs until its longest request is done, short requests wait and their slots sit idle. Iteration-level scheduling, which vLLM builds on, works at the level of single decoding iterations rather than whole requests: finished sequences leave the batch and new ones join after each step . This is often called continuous batching. Paging makes it practical, because a new request just needs a free block, not a large contiguous region.

What to remember

  • Before: a contiguous, maximum-length reservation per request; only 20–38% of it held tokens.
  • PagedAttention: fixed-size KV blocks + a block table; allocate as tokens arrive.
  • Blocks can be shared across requests (common prompts, parallel samples), copied only when written.
  • Iteration-level (continuous) batching: requests join and leave the batch at every decode step.
  • vLLM: 2–4× throughput at the same latency in its paper's comparisons.

Key papers

Important

Efficient Memory Management for Large Language Model Serving with PagedAttention

Woosuk Kwon, Zhuohan Li et al. · 2023

Brought operating-system paging to the KV cache (the vLLM server), so many more requests fit in GPU memory at once.

How to read it: Section 3 (why existing systems waste memory) and Figure 6 (the block table) are the core.

~45 min readarXiv:2309.06180✓ verified 2026-10-05

Watch