Skip to content
Road to Intelligence

Concept · Chapter 11: Inside Modern LLMs

PagedAttention and Continuous Batching

Should knowUnderstand10 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 Established. 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 Established.

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 Established.

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 Established.

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 Established. 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