Efficient Memory Management for Large Language Model Serving with PagedAttention

Who should read it

Core reading for AI-infrastructure, inference-serving and systems-for-ML research roles, and an excellent systems paper for anyone who knows virtual memory: it explains why KV-cache memory management limits batch size and therefore throughput. Modelling-focused research roles and applied-AI roles only need the idea (paged KV blocks enabling larger batches and prefix sharing). It is not needed if you will not work on serving systems.

Study objectives

• Explain how KV-cache size grows with sequence length and batch size, and why reserving contiguous memory per request wastes it.
• Describe the block table, logical-to-physical block mapping, copy-on-write sharing and the attention-kernel changes the design requires.
• Explain the scheduling and preemption policy (swapping versus recomputation) and when each is cheaper.
• Critique the evaluation: workloads, request-arrival model, baselines (including reimplemented ones) and the normalized-latency metric.

Prerequisites

• Virtual memory and memory management
• Prefill, decode and KV-cache sizing

Main concepts to understand

• KV cache as the dominant dynamic memory consumer in LLM serving
• Reserved slots, internal fragmentation and external fragmentation when output lengths are unknown
• Fixed-size KV blocks, block tables and on-demand allocation (the paging analogy)
• Sharing blocks across sequences with reference counts and copy-on-write (parallel sampling, beam search, shared prefixes)
• Iteration-level batching combined with memory-aware admission
• Preemption with all-or-nothing eviction by swapping to CPU memory or by recomputation
• Kernel support for attention over non-contiguous blocks and fused block operations

What to inspect in the evaluation

• Workloads: requests synthesized from ShareGPT and Alpaca input and output lengths with Poisson arrivals at several rates; consider how burstiness or real timestamps could change the results.
• Metric: normalized latency (mean end-to-end latency divided by output length) against request rate; check whether tail latency or time to first token are reported and what the mean can hide.
• Baselines: FasterTransformer with a custom batching scheduler, and Orca reimplemented by the authors in three reservation variants (Oracle, Pow2, Max) because Orca was not publicly available; judge how faithfully a reimplementation represents the original.
• Models and hardware: OPT 13B, 66B and 175B and LLaMA 13B on A100 GPUs, with shorter traces for the largest model because of cost.
• Ablations (Section 7): kernel overhead microbenchmark, block-size sensitivity, and swapping versus recomputation; check which conclusions depend on the test machine’s CPU-GPU bandwidth.
• Memory-waste measurements in the introduction: check how the used fraction of KV memory is measured for each system.

Guarantees versus empirical results

Reading plan

1. Pass 1 (20 minutes): abstract, the memory-waste figure in the introduction, Section 3 on memory challenges and the conclusion.
2. Pass 2 (90 minutes): Section 4 (PagedAttention, KV cache manager, decoding scenarios, scheduling and preemption) next to an OS virtual-memory refresher, then the Section 6 setup and main figures.
3. Pass 3 (3–5 hours, serving roles): write a toy block allocator with reference counts and copy-on-write, simulate admission under a Poisson trace with several block sizes, and compare it with contiguous reservation.

Discussion prompts

• Which virtual-memory ideas transfer directly to KV caches, and which do not (for example, there is no hardware TLB)?
• How might results change with real arrival timestamps, longer contexts or a prefix-heavy chat workload?
• Why use normalized latency, and which serving metrics (time to first token, inter-token latency, tail latency) would you add?
• When is recomputation cheaper than swapping, and how does the answer depend on hardware?
• What risks come from comparing against a reimplemented baseline, and how would you mitigate them?

Related topics

• Prefill, decode and KV-cache sizing
• PagedAttention, continuous batching and scheduling
• Serving metrics: goodput, TTFT and inter-token latency
• AI paper route: Attention, FlashAttention, LoRA, DPO, RAG
• Performance modeling, traces and bottleneck attribution