Module 4 · Serving the batch

Batching, Scheduling, and Paging

GPUs are wasted one request at a time. We walk through how continuous batching (Orca) keeps every slot full by rescheduling each iteration, and how PagedAttention (vLLM) ends the memory waste by treating the KV cache like operating-system virtual memory.

Static batching: the batch waits for its slowest member

step-through

Requests of different lengths are launched as one fixed batch. The batch can't be released until the longest sequence finishes, so finished short requests leave their GPU slot idle — wasted.

request / generated token GPU slot doing work idle slot (wasted)

Two problems hide in that picture. The batch is gated by the slowest request, and any request that arrives while the batch runs suffers head-of-line blocking — it cannot start until the whole batch is done. Orca's fix is to stop thinking in whole requests and start thinking in single iterations.

Continuous batching: reschedule every iteration

auto-play

Orca runs the model's kernels for just one token across the whole batch, then evicts finished sequences and admits waiting ones into the freed slots. The batch is rebuilt each iteration, so the GPU stays full.

active slot (this iteration) sequence / new token just finished → evicted waiting in queue
Tradeoff Switching between CPU and GPU every token adds scheduling overhead. It used to be negligible — token generation dwarfed it — but as kernels got faster, scheduling can now cost up to 50% for small models. Continuous batching is still the execution model behind every major runtime.

Continuous batching creates a new problem: if requests are constantly admitted and evicted, and each needs HBM for its KV cache, memory could be carved up so that no request can finish — a deadlock. Orca avoids this by pre-allocating the maximum response length for every admitted request. Safe, but wasteful: most requests stop well short of that maximum. That waste is exactly what paging attacks.

PagedAttention: page the KV cache like virtual memory

step-through

Reserving max-length per sequence wastes most of HBM to internal fragmentation. vLLM instead splits each KV cache into fixed-size blocks (pages) stored non-contiguously, with a per-sequence block table mapping logical → physical.

sequence KV block (page) reserved-but-unused (fragmentation) block table (logical→physical)

The block table is managed on the CPU, which allocates a new block only when the previous one fills and frees blocks when a request completes. Because the KV cache no longer lives in contiguous memory, vLLM ships paging-aware attention kernels that gather K and V through that layer of indirection. If HBM is ever exhausted, vLLM evicts a request — swapping it to CPU memory or discarding and recomputing it later.

Block sharing: one prefix, many samples

auto-play

Decoupling logical from physical memory lets blocks be shared. A common prompt prefix is stored once; parallel samples point at the same physical blocks. On the first divergent write, vLLM does copy-on-write — and reference counts keep a shared block alive until its last user finishes.

shared prefix block sample A / sample B copy-on-write block refcount
Looking ahead Sharing identical prefixes across different requests is the seed of prefix caching — the star of Module 8 (KV Cache Management and Offload).