Title: Lecture 4 — Inside vLLM's Memory and Scheduling Engine
Course: AIINFRA 200: Production Inference Serving & GPU Orchestration > Section: Week 04 — PagedAttention and Continuous Batching Deep Dive

📖 Lecture — Inside vLLM's Memory and Scheduling Engine

Last week you stood up a vLLM server and got tokens flowing. This week we open the hood and look at the two ideas that made vLLM the reference architecture that nearly every competing inference engine has since converged toward: PagedAttention and continuous batching. Individually, each is a clever systems trick. Together, they typically deliver a 2-4x throughput improvement over naive serving, which is why understanding them is central to production inference work.

The problem: reserving memory you don't need

Every autoregressive decoder needs a KV (key-value) cache — a running record of attention keys and values for every token generated so far, so the model doesn't recompute attention over the whole sequence at every step. The naive way to manage this cache is to reserve one large contiguous block of GPU memory per request, sized to the maximum context length the request could possibly use — say, 32,000 tokens. Here is the misconception worth correcting up front: it is not that beginners imagine this happens — it genuinely does happen in naive serving frameworks. If a request specifies a 32K-token context window, the naive allocator reserves a full 32K-token contiguous KV-cache slab immediately, even if that request only ever generates 200 tokens before hitting a stop token. The other 31,800 tokens' worth of memory sit reserved and unusable by any other request for the lifetime of that generation. Multiply that across dozens of concurrent requests with varying actual lengths, and most of your expensive GPU HBM is being wasted on cache space that is never touched. Research benchmarks on naive serving found up to \~90% of allocated KV-cache memory going to waste this way.

The fix: paging, borrowed from operating systems

PagedAttention solves this the same way operating systems solved the analogous problem for process memory decades ago: stop requiring contiguous allocation. Instead of one giant reserved slab per request, the KV cache is partitioned into small fixed-size blocks (commonly holding a small, fixed number of tokens each). Blocks are allocated from a shared pool on demand, one block at a time, as a sequence actually generates tokens — not upfront based on a worst-case maximum. Because blocks no longer need to be contiguous in physical GPU memory, a block table — directly analogous to a page table in OS virtual memory — maps each sequence's logical token positions to wherever its physical blocks actually happen to live in GPU memory. The attention kernel is rewritten to gather the right physical blocks at computation time using this mapping, so the model never "sees" the physical fragmentation.

Naive contiguous KV cache | PagedAttention (block-based)
Reserves max-context-length memory upfront per request | Allocates one small block at a time, as needed
Memory fragmented / wasted when actual generation is shorter than max length | Near-zero internal fragmentation (waste bounded by a single partial block)
No easy way to share memory across requests | Blocks can be shared (e.g., common prompt prefixes) via the block table
Reported waste: up to \~90% of reserved KV-cache memory | Reclaims that memory for more concurrent requests

It's worth being precise about what problem PagedAttention actually solves. This is the second misconception to correct directly: PagedAttention's purpose is memory management, not batching. It eliminates fragmentation and enables dynamic, on-demand cache allocation and sharing across requests. It does not, by itself, decide which requests run together or when a new request joins a running batch — that is a separate, complementary mechanism: continuous batching.

Continuous batching: scheduling at the level of decode steps

Traditional static batching groups a fixed set of requests together, runs them through the model until every request in the batch is finished, and only then forms a new batch. If one request in the batch needs 500 decode steps and the rest finish in 50, the GPU spends 450 steps computing mostly-wasted forward passes for already-finished sequences (or sits idle waiting). This is the third misconception worth naming explicitly: continuous batching is not the same thing as generic "dynamic batching." Simple dynamic batching still typically waits for a batch to fill or for the current batch to complete before reshuffling. Continuous (iteration-level) batching operates at a much finer grain — the level of a single decode step. At every step, the scheduler checks whether any sequence in the running batch has finished (hit a stop token or max length); if so, that sequence's KV-cache blocks are immediately freed, and a new request waiting in the queue is inserted into the batch for the very next step. The GPU composition of "who is in the batch" can change on literally every iteration. The practical effect is that the GPU is almost never idle waiting for the slowest sequence in a batch to finish, because there effectively isn't a fixed "batch" that has to complete together. Reported gains from continuous batching alone are roughly 3-10x higher throughput compared to static batching, depending on how variable request lengths are in the workload.

How it fits together in vLLM

vLLM's scheduler is the component that ties these two ideas together every engine step. At each step it: (1) checks which running sequences have finished and evicts them, freeing their block-table entries back to the shared block pool; (2) admits new queued requests into the running batch, allocating fresh KV-cache blocks for them; and (3) does all of this while respecting hard memory constraints and coordinating with tensor-parallel and pipeline-parallel worker groups, since in multi-GPU deployments the scheduler must keep each worker's view of the batch and block tables consistent. The result is that vLLM continuously maximizes the number of concurrent sequences it can fit on a GPU without ever over-committing memory — squeezing far more useful work out of the same hardware than a system that reserves memory pessimistically and batches statically. That is the full picture: PagedAttention removes the memory-fragmentation ceiling, continuous batching removes the idle-GPU ceiling, and the vLLM scheduler is the traffic controller making both work together on every single decode step.