Fifth Deep Dive post. The PagedAttention post mentioned Orca as one of the baselines vLLM was benchmarked against, without saying what Orca actually does. That's worth fixing on its own: Orca (Yu et al., OSDI 2022) introduced iteration-level scheduling — what the vLLM ecosystem now calls continuous batching — and it solves a completely different problem than PagedAttention does. PagedAttention is about where the KV cache lives in memory. Continuous batching is about when a request gets to start and stop occupying a GPU slot. The two are complementary, and vLLM ships both.

The problem with a fixed batch

The obvious way to batch LLM requests is the same way you'd batch anything else: collect N requests, run them together as one batch, return all N results, start the next batch. This is static batching, and it has a structural flaw specific to autoregressive generation: nobody knows in advance how many tokens any given request will generate, and different requests almost never finish at the same time.

Once a batch starts, static batching can't do anything about that mismatch. A request that finishes after 6 tokens still occupies a slot in the batch — doing nothing — until the slowest request in that same batch finishes, because the next batch can't start until every member of the current one is done. The GPU is fully allocated to work that, for a growing fraction of the batch, no longer exists.

Diagram comparing static batching, where sequences that finish early sit idle until the slowest sequence in the batch finishes, against continuous batching, where a finished sequence's slot is immediately filled by a new request on the next decoding iteration

Iteration-level scheduling: reschedule after every single token

Orca's fix is to stop treating "the batch" as a fixed unit that lives for its entire lifetime. Instead, the scheduler operates at the granularity of one iteration — one forward pass, which for the decode phase means one new token generated per sequence in the batch. After every iteration, the scheduler gets to make a new decision: requests that just emitted an end-of-sequence token leave the batch immediately, and requests waiting in a queue can be inserted into the now-open slots on the very next iteration. There's no such thing as "waiting for the batch to finish," because the batch's membership is never fixed for longer than a single step.

Selective batching: why this isn't free for attention

Once a batch's membership can change every iteration, the sequences inside it are no longer all at the same position — one might be generating its 3rd token while another generates its 40th. Most of a Transformer layer doesn't care about that at all: a linear projection, layer norm, or GeLU is applied independently to each token's vector, so Orca just flattens every request's tokens for the current iteration into one long list and runs those ops as a single big batched operation, regardless of which request each token belongs to or what position it's at.

Attention is the exception. softmax(QKᵀ/√d_k)V for a given token has to attend only over that request's own prior tokens — mixing tokens from different requests into one batched matrix multiply would let sequences attend across request boundaries, which is simply wrong. Batched matmul also requires uniform shapes, and requests at different positions have different numbers of keys/values to attend over. Orca's answer, which the paper calls selective batching, is to batch everything except attention across the whole flattened set of tokens, then split the batch back apart by request just for the attention computation, running each request's attention separately before re-flattening for the next layer's non-attention ops.

The prefill/decode mix makes scheduling harder, not easier

There's a second wrinkle continuous batching has to manage: a new request's first pass through the model (prefill, processing the entire prompt at once) is a very different shape of work than an already-running request's decode step (one new token, using whatever's cached from before). Prefill for a long prompt can be far more compute-heavy than a single decode step, so naively slotting a freshly arrived request's prefill into the same iteration as a batch of decode steps can spike that iteration's latency for every other request sharing it. Real schedulers (vLLM's included) have tunable policies for how aggressively to interleave new prefills against in-flight decode steps, trading a little decode latency for keeping the GPU from ever sitting on an empty queue.

What this is worth, measured

Orca's own evaluation, serving GPT-3 175B, reports a 36.9x throughput improvement over NVIDIA FasterTransformer at the same latency — entirely from iteration-level scheduling plus selective batching, with no change to the attention computation itself or to how KV cache memory is laid out. On the vLLM side, Anyscale's benchmarks tell a similar story from a different angle: under workloads with high variance in output length (up to 1536 tokens), naive static batching manages roughly 81 tokens/second, while continuous batching pushes past 1900 — and combining continuous batching with vLLM's PagedAttention gets to 23x the naive baseline, against an 8x improvement from continuous batching alone (no PagedAttention) and 4x from an optimized static-batching baseline (FasterTransformer).

Two orthogonal fixes, one serving engine

This is the same lesson the PagedAttention post closed on, from a different angle: continuous batching fixes when work gets scheduled onto the GPU, PagedAttention fixes where that work's memory lives, and FlashAttention and FP8 in WGMMA fix how the attention computation itself executes once it's scheduled. None of the four would substitute for another — vLLM's real throughput numbers come from stacking scheduling, memory management, and kernel-level optimizations on top of each other, not from any single one of them. Speculative decoding sits alongside this same list: a fourth, orthogonal axis, changing not when or where or how a decode step runs, but how many tokens one step is able to produce.

References

Batching timeline diagram above is original artwork made for this post.