Day 2: High-Throughput Serving with vLLM & PagedAttention

1. The Production Memory Fragmentation Crisis

Before 2023, serving LLMs at scale was notoriously inefficient. Standard inference frameworks (Hugging Face TGI, TensorRT-LLM v1) suffered from catastrophic memory waste:

1. Internal Fragmentation (Reservation Waste): Because generation lengths are unknown in advance, systems pre-allocated contiguous memory for the maximum possible context length (e.g., 2,048 or 4,096 tokens). A request generating only 150 tokens left $>85\%$ of its reserved memory completely unused.
2. External Fragmentation: Sequences finish at different times. Releasing contiguous chunks created variable-sized memory holes that could not accommodate larger new requests.
3. The Consequence: Real-world GPU memory utilization was often below 20%, limiting concurrency to 2–4 streams per A100.

2. PagedAttention: OS Virtual Memory Applied to LLMs

Woosuk Kwon et al. (UC Berkeley, 2023) revolutionized serving with PagedAttention, the core engine of vLLM.

PagedAttention adapts the classical Operating System virtual memory page table:

• Logical Blocks: A sequence's KV cache is divided into fixed-size logical blocks of $B$ tokens (typically $B = 16$).
• Physical GPU Blocks: Physical VRAM is divided into a contiguous pool of 16-token block frames.
• Block Table: A dynamic lookup table maps logical blocks to arbitrary, non-contiguous physical blocks anywhere in GPU memory.

Why PagedAttention Eliminates Waste

• Zero External Fragmentation: All physical allocations are uniform 16-token blocks. Any free block can satisfy any request.
• Minimal Internal Fragmentation: Memory is allocated on demand as tokens are produced. Only the very last block of a sequence can have unused slots ($< 16\text{ tokens}$). Memory waste drops to less than 4%!

3. Advanced Features: Prefix Caching & Copy-on-Write (CoW)

1. Automatic Prefix Caching (APC)

In enterprise applications, hundreds of requests share the exact same system prompt or few-shot context.

• vLLM computes a cryptographic hash of each prompt block.
• If physical blocks for that hash already exist, the new request simply maps its logical block to the existing physical block and increments its reference count ($\text{ref\_count} \leftarrow \text{ref\_count} + 1$).
• Result: Zero KV cache recomputation, reducing Time-To-First-Token (TTFT) by up to 90%.

2. Copy-on-Write (CoW) Parallel Sampling

When generating multiple completions (n = 4) for a single prompt:

• All 4 branches share the prompt's physical blocks in read-only mode.
• Only when an individual branch generates a novel divergent token does vLLM allocate a new private physical block, copying over the final state.

4. Continuous Batching (Iteration-Level Scheduling)

Traditional static batching processes a batch until the slowest sequence completes. If Request A needs 50 tokens and Request B needs 1,000 tokens, Request A's slot sits idle for 950 steps!

Continuous Batching operates at the iteration level:

1. At every decode step, check if any sequence emitted an <|endoftext|> or hit max_tokens.
2. Evict finished sequences and immediately free their physical blocks.
3. Admit new incoming requests from the waiting queue, run their prefill, and insert them into the active batch for the next decode step.
4. The GPU stays continuously saturated at 100% capacity.