BATCHING

The naive approach: collect B requests, run them together until all are done, then collect the next B.

The problem is that generation lengths vary enormously and are not known in advance. Real traffic has a heavy right tail — most responses are short, a few are very long. If your batch of 8 has lengths [20, 35, 40, 60, 80, 120, 200, 900], the batch runs for 900 steps. The sequence that finished at step 20 occupies a slot doing nothing for the remaining 880.

Quantify it. Utilization is mean length over max length:

total useful work  = 20+35+40+60+80+120+200+900 = 1455 sequence-steps
slots x steps      = 8 x 900                    = 7200 sequence-steps
utilization        = 1455 / 7200                = 20.2%

Four fifths of your paid-for capacity produced nothing. And this is not a contrived example — a lognormal length distribution with a realistic tail gives numbers in this range routinely. The larger the batch, the worse it gets, because max over more samples reaches further into the tail. Static batching is one of the few optimizations that gets worse as you scale it up.

There is a second cost that is easy to miss: padding. Sequences in a static batch must be padded to a common length for the tensors to be rectangular. Attention over padding positions is wasted arithmetic, and the padding also sits in the KV cache consuming memory that could have held real sequences.

Orca's contribution begins with noticing that the padding problem and the early-finish problem have the same root cause — treating a batch as a fixed rectangular object with a lifetime.

Orca's insight is to move the scheduling granularity from the request to the iteration. The loop becomes:

loop forever:
    1. remove any sequence that emitted EOS or hit its length limit
    2. free its KV cache blocks
    3. admit waiting requests while memory allows
    4. run one forward step for the whole current batch
    5. sample one token for each sequence

A sequence that finishes at step 20 releases its slot at step 20. Someone else takes it at step 21. The batch stays near capacity permanently, and utilization goes from ~20% to ~90%+ on the same traffic.

Orca reported throughput improvements of up to 36.9× over FasterTransformer at comparable latency. That number is large partly because the baseline was weak, but the mechanism is real and it is why every serious engine implements this.

There is a genuine technical obstacle, and Orca's solution to it is the part people skip. Different sequences in the batch are at different positions, so their attention computations have different shapes. You cannot batch them into one rectangular attention call the way you can for a uniform batch.

Orca's answer is selective batching: batch the operations that permit it and split the one that does not.

QKV projections, MLP, LM head   ->  batch across sequences
                                     (these are position-independent; each
                                      token is an independent row of a matmul)

attention                       ->  handle per-sequence
                                     (each has a different KV length)

This works because the position-independent operations are where nearly all the weight traffic lives. Flatten all the batch's tokens into a single [total_tokens, d_model] matrix, do one big matmul, and the weights are amortized across everyone. Attention is then handled with a kernel that takes per-sequence lengths and offsets — which is exactly what PagedAttention and FlashAttention's varlen variants provide.

Two costs worth knowing. First, admitting a request means running its prefill, which is a different and much heavier operation than a decode step — the subject of the next two concepts. Second, the scheduler now runs every iteration, so it must be fast; at 100 steps/second a scheduler taking 2 ms is consuming 20% of your wall clock. This is why production schedulers are C++ and why vLLM's V1 rewrite moved the scheduling loop out of the Python hot path.

Continuous batching creates a problem it did not have to solve before: prefill and decode now contend for the same GPU, iteration by iteration.

Numbers make it concrete. Llama-3-8B on an H100:

one decode step, batch 32       ~10 ms
one prefill of 8,000 tokens    ~130 ms  (compute-bound: 2 x 8.03e9 x 8000 FLOP)

If the scheduler runs that prefill as a single unit, then for 130 ms every one of your 32 decoding sequences produces nothing. Their inter-token latency for that step is 130 ms instead of 10 ms — a 13× spike. To a user watching text stream, it is a visible stall.

Worse, this is not rare. Any traffic mix with both chat (short prompts, long outputs) and document processing (long prompts, short outputs) produces it constantly. A single user pasting a long document degrades the experience of everyone currently streaming.

The scheduling policies you can choose between all have a real cost:

Prefill-priority. Run prefills as soon as they arrive. Best TTFT, worst TPOT stability. This is what naive continuous batching does by default.

Decode-priority. Never interrupt decoding; queue prefills until there is slack. Smooth token streams, terrible TTFT under load, and requests can starve.

Chunked prefill. Split a long prefill into fixed-size chunks and process one chunk per iteration alongside the ongoing decode. The next concept, and the answer most systems settled on.

Disaggregation. Put prefill and decode on separate hardware entirely so they cannot interfere. The cleanest fix, and the subject of Module 9.

The underlying reason the conflict exists is the asymmetry from Module 1: prefill is compute-bound and decode is memory-bound. They are not competing for the same resource, which sounds like it should help, but they cannot run simultaneously on the same SMs — so in practice they simply take turns, and the long one wins.

Chunked prefill splits a long prompt into pieces and processes one piece per iteration, mixed in with ongoing decode work. Since causal attention only looks backward, chunk k can attend to all of chunks 0..k-1 from the cache — the result is identical to prefilling the whole prompt at once.

The mechanism is a token budget per iteration. A scheduler with a budget of 2,048 tokens might assemble:

iteration budget: 2048 tokens

  32 decode sequences        ->    32 tokens
  1 prefill chunk            -> 2,016 tokens
                                 -------
                                 2,048

Decode tokens are admitted first because they are latency-critical and cheap — 32 of them cost 32 of your 2,048. Prefill chunks fill the remainder. The result is that every iteration takes about the same amount of time, so inter-token latency stays flat regardless of what prompts are arriving.

The choice of budget is a real trade-off:

There is also a subtle benefit that is easy to miss and is arguably the main one. A pure decode iteration at batch 32 has arithmetic intensity 32 — deep in memory-bound territory, GPU mostly idle. Adding 2,016 prefill tokens to that same iteration raises the intensity to roughly 2,048. The prefill work is nearly free, because it uses the arithmetic capacity that the decode step was wasting anyway.

That reframes chunked prefill entirely. It is not a scheduling compromise that trades TTFT for TPOT. It is a way to run prefill in the compute the decode step was leaving on the floor — the purest possible expression of this course's thesis. Both workloads finish faster than they would if you ran them separately.

Sarathi-Serve, which introduced this technique as "stall-free batching", reported substantial improvements in serving capacity under latency SLOs for exactly this reason.

The scheduler decides, every iteration, who runs. It faces a problem with no clean solution: it does not know how long any sequence will be, but it must commit memory to it anyway.

Admission control. How many sequences to admit is a bet. Admit too few and you waste throughput. Admit too many and you run out of KV cache mid-generation, because every admitted sequence's cache grows every step. Some systems admit conservatively based on max_tokens; others admit optimistically and deal with the consequences.

Preemption is how you deal with the consequences. When memory runs short, a running sequence must give some back. Two options:

• Swap — copy its KV cache to CPU memory and restore it later. Costs a PCIe round trip: moving 2.5 GiB at ~50 GB/s is about 50 ms each way.
• Recompute — discard the cache and re-prefill from the tokens when the sequence resumes. Costs a prefill.

Which is cheaper depends on sequence length and interconnect, and vLLM implements both. The crossover is roughly where prefill time exceeds transfer time — so short sequences favour recomputation, long ones favour swapping.

Queueing policy. FCFS is the default and is fair in the obvious sense, but it lets one 100k prompt delay everyone behind it. Shortest-job-first would be better for mean latency, but you cannot see job length in advance — output length is unknown at admission time. Some systems predict it; the predictions are not good.

Priority and fairness. A production system with multiple tenants needs to prevent one user from occupying the whole batch. This is genuinely hard because the natural unit of fairness is unclear: is it requests, tokens, or GPU-time? A user sending one 100k-token request and a user sending a thousand 100-token requests consume comparable resources through very different shapes.

The starvation trap. Any policy that prioritizes decode over prefill can starve new requests indefinitely under sustained load, because there is always more decode work. Real schedulers need an aging mechanism — a request's priority rises with its wait time — or they will occasionally never serve someone.

The honest summary is that scheduling here is a live research area with no settled answer, and the defaults in every engine are heuristics tuned against a particular traffic assumption. If your traffic looks different from that assumption, the defaults will be wrong for you, and measuring is the only way to find out.

Tie this module back to Module 4. Batching is the mechanism that moves you right along the roofline, but the movement is bounded twice.

Bound 1 — the ridge point. Beyond intensity ≈ 295 on an H100, you are compute-bound and further batching buys nothing per weight-byte. In practice you rarely get there.

Bound 2 — the KV cache. Every sequence brings its own cache, so batch is capped by memory — and, more subtly, throughput saturates before the memory cap, because KV traffic grows with batch while weight traffic does not.

The throughput curve therefore has a characteristic shape:

throughput
    |                    ........................  <- flat: KV-traffic dominated
    |              .....
    |         ....
    |      ...
    |    ..                                        <- steep: weight-amortization region
    |  ..
    | .
    +--------------------------------------------> batch size
        ^                    ^
     the steep part      the knee -- operate here

For Llama-3-8B on an H100 at 4k context (from Module 4's table), the knee is around batch 32–64: going from 1 to 32 gains 15× throughput, and from 64 to 111 gains only 14%.

Operating past the knee is usually a mistake. You gain a few percent of throughput and pay for it with substantially worse tail latency, more preemption, and less headroom for traffic spikes. The right operating point is the knee, or wherever your latency SLO puts you if that is tighter.

Two practical consequences:

Measure the knee for your own workload. It moves with model, context length, KV dtype and hardware. A batch size copied from someone else's blog post is a guess.

Anything that shrinks the KV cache moves the knee right. fp8 KV, GQA, MLA, better paging — each one lets the steep region continue further before KV traffic flattens it. This is why Module 6 belongs immediately after this one: memory optimization is how you get more out of batching, and batching is how memory optimization turns into throughput.