CMU 11-868 L22 and L24 LLM Serving: Scheduling, RadixAttention, and PagedAttention

🌏 中文版

Version note: This post follows the Spring 2026 offering of CMU 11-868 LLM Systems. The main sources are two slide decks: the April 6 Lecture 22, Design of Efficient LLM Inference Server (Lei Li, 47 PDF pages), and the April 13 Lecture 24, Paged Attention & vLLM for Efficient LLM Inference Engine (Woosuk Kwon, credited to Inferact on the slides, 82 PDF pages). Page numbers below are PDF page order. The Syllabus lists ORCA, SGLang, and vLLM as readings. All facts were checked against the official materials on 2026-09-30. Access level A3: the slides are public. What you can't get is lecture video (this course publishes none) and the quizzes.

Series: Previous L23 Efficient Fine-Tuning: LoRA and QLoRA | Next HW6: DeepSpeed ZeRO + LoRA Training and SGLang Inference | Series overview

The official order is SGLang on April 6, PEFT on April 8, and vLLM on April 13. This series puts the two serving lectures together because they solve the same problem, and page 9 of Lecture 22 says outright that "SGLang / vLLM share similar arch".

The setting: one server, many requests

Page 3 of Lecture 22 opens with scale: 200 million daily active users, 2.5 billion prompts a day, 30,000 requests per second. Pages 4–6 then list three common usage patterns, each hiding a systems problem:

• Many users, single round: different users may send the exact same prompt.
• Multi-round chat: should the server keep a user's chat history in GPU memory while waiting for the next turn?
• Multiple answers: the same prompt (maybe with in-context examples) has to be generated three times. Do you really run it from scratch three times?

Page 7 turns this into design goals: maintain multi-user chat sessions; handle many requests at once, with varied generation lengths and shared prompt prefixes; balance throughput and latency; use heterogeneous CPU/GPU devices. The examples it names are ORCA, SGLang, and vLLM.

Intuition: the bottleneck is the KV cache

Ordinary neural network inference keeps only the current layer's output. Transformers can't: generating the next token needs every earlier token's keys and values in every layer. So each layer's K and V are stored in GPU memory. That's the KV cache (Lecture 22, pages 18–19).

It's big. Lecture 22's page 20 estimates about 2.5MB per token for LLaMA3 70B (80 layers, dimension 8192), or about 20GB for one request at 8k context. Lecture 24's page 11 says about 1MB per token, several GB for a full request. The two decks assume different models and precisions; the real size also depends on whether the model shares KV heads, as GQA does. What matters is the order of magnitude: the KV cache competes with the model weights for memory.

Pages 12–13 of Lecture 24 draw this as one chart. A 13B model on an A100-40GB (the slide notes this was a common setup in 2023) spends 26GB (65%) on parameters, leaving about 12GB (30%) for KV cache. Earlier systems filled the 40GB at a batch of 8, for about 0.8 req/s. PagedAttention stretches the batch to 40, for about 3.2 req/s. The slide's conclusion is one sentence: how well you manage the KV cache decides whether high-throughput serving is possible.

The two lectures attack it from opposite ends. SGLang covers scheduling and reuse. vLLM covers allocation without waste.

Mechanism 1: the scheduling loop and continuous batching

Page 9 of Lecture 22 shows the server architecture: Client API (native generation API, OpenAI-compatible API, structured language frontend) → FastAPI server → tokenizer → scheduler → detokenizer. Under the scheduler sits the model worker, which manages the memory pool, the radix tree cache, and the attention backend.

The scheduler is one infinite loop (page 10): receive requests, process input, pick the next batch, run it, process the results. The five jobs inside the loop are receiving input, streaming output, checking stop conditions, reordering requests into a batch, and allocating memory for the next batch and the running batch.

while True:
    recv_reqs = recv_requests()
    process_input_requests(recv_reqs)
    batch = get_next_batch_to_run()
    result = run_batch(batch)
    process_batch_result(batch, result)

Why continuous batching. Page 13 names the obvious problem: requests in a batch generate different lengths, and a naive implementation waits for the longest one. The fix on page 14 comes from ORCA (OSDI 2022): schedule at the iteration level. After every generated token, check the batch; whenever a request finishes, slot a new one in.

Page 15 is ORCA's other idea, selective batching. Non-attention operations like linear, layer norm, and GeLU run as one batch, and prefill is merged into one step. Attention goes to a dedicated attention engine; the slide gives PagedAttention as an example.

Inside SGLang's scheduler (page 16). get_next_batch_to_run() handles three cases:

• A request just finished prefill: move it to the decode batch.
• New prefill requests are waiting: pick requests based on free batch slots and the waiting queue's priorities, and add them to prefill.
• No new prefill: keep decoding. First check_decode_mem asks whether GPU memory suffices. If yes, prepare for decode and lower new_token_ratio. If no, retract_decode, raise new_token_ratio, and put the request back on the prefill waiting list.

process_batch_result checks for finished requests and frees their KV cache. The slide notes that this frees only the reference, not the memory itself. The next section shows why those KVs are worth keeping.

Mechanism 2: RadixAttention, reusing KV through a prefix tree

Go back to the three usage patterns: identical prompts, multi-round chat history, shared in-context examples. All of them are "same prefix". SGLang's RadixAttention is built for exactly this (pages 21–24):

• KV memory pointers live in a radix tree (prefix tree).
• Each edge is a string, each node holds the KV memory pointers for its edge, and the path from root to node is a prefix.
• Looking up a prompt walks the edges to find the longest cached prefix and returns the number of matched tokens and the node.

Page 23 adds an implementation detail: the tree itself lives on the CPU, and nodes point to the GPU memory holding each edge's KVs.

Pages 25–32 are a sequence of diagrams showing how the tree grows. A new request adds nodes. The next round of a chat extends the same path. A new user's prompt that only partly matches splits a node. When the GPU cache overflows, the least-used KV nodes are evicted. The HW6 assignment page is more specific about eviction: LRU evicts the least recently used leaf, so shared ancestors stay until they become leaves themselves.

Cache-aware scheduling and load balancing (pages 35–38). With the tree in place, scheduling can look at the cache. Requests in the queue are sorted by matched prefix length, and hit rate is defined as cached tokens ÷ total prompt tokens. With several workers, a load balancer predicts each worker's prefix hit rate and routes to the best match. Page 38's comparison: round robin gets 82,665 tokens/s at a 20% hit rate; the cache-aware balancer gets 158,596 tokens/s at 75%.

Mechanism 3: hiding CPU scheduling

Pages 40–43 deal with the last source of waste: the GPU waiting on the CPU scheduler. The scheduler's jobs (receiving messages, streaming output, checking stop conditions, maintaining the radix tree and matching prefixes, allocating memory for the next batch) leave the GPU idle if they alternate with GPU compute.

The fix is to overlap the CPU scheduler with the GPU worker. The slides name two keys: resolve the dependency by delaying the stop-condition check by one step, and use CUDA events and streams for fine-grained scheduling. They cite NanoFlow (Zhu et al.), and report 1.3× faster than the best open-source baseline at the time (page 43).

Page 45 lists extra server features the lecture doesn't expand on: speculative decoding (SpecForge), constrained decoding (XGrammar), expert parallelism (DeepEP), and model-specific support (MLA).

Mechanism 4: PagedAttention, KV cache as virtual memory

Lecture 24 is given by Woosuk Kwon, first author of the vLLM paper (SOSP 2023).

What went wrong before (pages 15–16). Earlier systems followed the static-shape convention of deep learning and pre-allocated one contiguous chunk per request, sized to that request's maximum length. That causes two kinds of fragmentation. Unknown output length causes internal fragmentation (reserved slots never used). Different maximum lengths across requests cause external fragmentation. Page 16's conclusion: only 20–40% of KV cache space actually stores token states.

PagedAttention (pages 17–21) borrows paging from operating systems:

• The KV cache is cut into fixed-size KV blocks, for example 4 tokens' worth of KV per block.
• Each request sees contiguous logical blocks, which live in arbitrary physical blocks.
• A block table maps between them: which physical block the i-th logical block uses, and how many slots are filled.

Pages 22–26 walk through the prompt "Alan Turing is a computer scientist". Each generated token fills the next free slot in the last block. Only when a block is full does a new physical block get allocated and a new row get added to the block table.

At attention time, the kernel fetches the non-contiguous blocks through the block table and computes attention on the fly. Page 20 admits the indirection adds 5–10% to GPU kernel latency. Page 21 says that in practice PagedAttention is a custom GPU kernel that avoids gathering keys and values into contiguous tensors first, and that it can be combined with FlashAttention.

How much it saves (page 27). Internal fragmentation happens only in a sequence's last block, so each sequence wastes less than one block. External fragmentation disappears. The slide's scale is a sequence of about 1,000 tokens with blocks of about 10 tokens.

The second payoff of paging: sharing (pages 28–32). In parallel sampling, several samples share the same prompt, and every prompt block except the last can be shared. When a sample needs to write into a shared block, it copies it first (copy-on-write). Beam search has a more complex sharing structure; the slides compare it to a process tree with fork and kill, and it's supported the same way, by paging plus copy-on-write.

When memory runs out (pages 34–37). If no physical block is free, some requests have to pause. There are two options: swap their KV to the CPU and back, or delete it and recompute later. Every step needs all earlier tokens, so both work on whole requests. The slides observe that smaller blocks make swapping pay more overhead for small transfers, while recomputation is surprisingly fast because all tokens' KV can be computed in parallel. vLLM uses recomputation with an FCFS policy.

Page 38 compares this with OS virtual memory. OS pages map to KV blocks; pages shared across processes map to blocks shared across samples. The differences: vLLM uses a single-level block table (the table is tiny next to the data), and preemption is per request with recomputation-based recovery.

Results on pages 39–40 (OPT-13B, one A100-40G): greedy decoding on a ShareGPT trace is 2.4× faster than Orca(Pow2). On an Alpaca trace, it's 1.8× faster without beam search, and 2.4×, 3.2×, and 3.5× faster at beam widths 2, 4, and 6. Page 41 lists systems that adopted PagedAttention, such as TensorRT-LLM and HuggingFace TGI.

Page 14 adds a newer reason this matters more now: MoE models are sparse. The slide computes 32× for DeepSeek V3 (top 8 of 256 experts) and 48× for Kimi K2 (top 8 of 384). Each expert sees only 1/32 to 1/48 of the tokens in a batch, so saturating the GPU takes batches 32–48× larger, and KV cache demand grows with them.

Mechanism 5: how vLLM squeezes out another layer

The second half of Lecture 24 covers vLLM itself. It offers two APIs (pages 44–45): the LLM class for offline batched inference, and an OpenAI-compatible server built on FastAPI (vllm serve). Page 47 groups its optimizations into four areas.

1. Cutting CPU overhead (pages 49–62). Page 49 makes the argument plainly. An inference step takes just 5–10 ms (100–200 tokens/s), while a training step takes 100 ms to over a second. So 1 ms of extra CPU overhead can cut inference performance by 20%, and 1 ms is easy to hit in Python. The countermeasures:

• Rewrite the API server from Python to Rust.
• Async scheduling and async de-tokenization: schedule and prepare the next batch one step ahead, overlapping host overhead with model execution so the GPU never waits on the CPU (page 52, also citing NanoFlow).
• GPU-native input preparation: the batching, paged-attention, and sampling-parameter bookkeeping that used to run as many small PyTorch ops on the CPU is rewritten as Triton kernels (page 53). This also makes async scheduling compatible with speculative decoding (page 54).
• CUDA graphs: Python/PyTorch overhead can take up to 50% of total latency (page 55). Capturing the whole model as one CUDA graph minimizes overhead, but requires static shapes and forbids CPU operations during execution. LLM inference is dynamic: prefills and decodes mix arbitrarily in one batch, kernels rely on runtime heuristics, and CPU offloading may be needed. vLLM's compromise is the piecewise CUDA graph: torch.compile splits the model, attention runs in PyTorch eager, and the other per-token ops run as CUDA graphs (pages 58–61). Page 62 measures it as 6–39% faster than PyTorch eager, 2–7% slower than a full CUDA graph in the worst case, and only 0–2% slower at batch size ≥ 8.

2. GPU kernels (pages 64–67). Complex or critical kernels come from FlashInfer and other libraries. vLLM provides AttentionBackend and FusedMoE abstractions so implementations can be swapped. Memory-bound kernels like RMS norm and RoPE are either fused automatically by torch.compile or written by hand as fused kernels. The slides use DeepSeek V3.2 as the example.

3. Model parallelism (pages 69–78). Models keep growing: the slide cites Kimi K2.5 at 1T parameters, about 600GB after quantization, while one B200 has 285GB of HBM. The goals are to minimize communication (keeping in mind the large gap between NVLink and InfiniBand bandwidth) and to balance load. The trade-offs of five kinds of parallelism:

Page 76 introduces prefill/decode disaggregation: separate prefill workers and decode workers make TTFT and TPOT more controllable, and each side can be optimized independently. Routing can use vLLM Router, NVIDIA Dynamo, llm-d, or Ray Serve LLM, with NIXL for KV transfer. This series covers the topic in depth in L26–L30 Serving at Scale.

4. Memory management (pages 80–81). Modern models often mix full attention with other layer types; the slides cite GPT-OSS (with sliding window attention) and Qwen 3.5 (with Gated DeltaNet). Static partitioning of memory causes severe fragmentation. vLLM's hybrid memory allocator partitions a shared pool dynamically and adjusts block sizes per layer type. The slides claim 0–12% memory waste across all open-source models.

The two lectures side by side

This isn't either/or. Lecture 22's page 9 says the architectures are similar, and its page 15 uses PagedAttention as the example attention engine.

Limits and how to study it

• Performance numbers in both decks come from the speakers' own systems and setups. PagedAttention's speedups, for instance, are against Orca(Pow2) on OPT-13B. Measure on your own model and traffic.
• The vLLM internals in Lecture 24 (Rust API server, GPU-native input prep, hybrid allocator) reflect spring 2026. The engine moves fast; check the vLLM documentation for current details.
• The course has no video, and many diagrams (pages 11, 25–32, 44) have no accompanying text. You'll need the papers alongside.

Suggested order:

1. Read Lecture 24 pages 15–27 and the PagedAttention section of the vLLM paper, then draw a block-table update on paper.
2. Read Lecture 22 pages 21–32 and the RadixAttention part of the SGLang paper. Work out what shape of tree multi-round chat and parallel sampling each produce.
3. Do the SGLang problem in HW6, tune mem_fraction_static, dp_size, and batch size, and watch how throughput changes.

Further reading

• Another course's take on inference: CS336 Inference
• Making attention itself faster: L21 FlashAttention
• Beyond one machine: L26–L30 Serving at Scale: Prefill/Decode Disaggregation, KV Cache, and Heterogeneous Hardware

References

• CMU 11-868 LLM Systems (Spring 2026) course home
• 11-868 Syllabus (Spring 2026) — the April 6 and April 13 sessions and the ORCA, SGLang, vLLM readings
• Lecture 22 slides: Design of Efficient LLM Inference Server — server architecture, scheduling loop, continuous/selective batching, RadixAttention, cache-aware load balancing, overlap scheduler
• Lecture 24 slides: Paged Attention & vLLM for Efficient LLM Inference Engine (Woosuk Kwon) — fragmentation, block table, copy-on-write, preemption, throughput experiments, vLLM's four optimization areas
• Yu et al., ORCA: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022)
• Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs (arXiv 2312.07104)
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023, arXiv 2309.06180)
• HW6 assignment page — description of RadixAttention's LRU leaf eviction and cache-aware scheduling
• vLLM documentation