Post

LLM Inference #5: Batching

Why batching makes LLM decoding cheaper, why static batching wastes most of the gain, and how continuous batching fixes it, explained with diagrams instead of code.

LLM Inference #5: Batching

Earlier in this series we looked at what one decode step actually does: to produce a single next token, the GPU reads every model weight out of memory, plus that sequence’s KV cache. The arithmetic done per byte read is tiny. At batch size 1, the GPU spends most of each step waiting on memory, not computing. (See the KV cache, prefill, and decode article for that background.)

That leaves an obvious question. If we are paying to read all those bytes anyway, can we get more out of each read?

That is what batching does. This post covers why it works, why the simple version throws away most of the gain, how continuous batching recovers it, and the two new problems the fix creates.

Why batching works

Take a 7-billion-parameter model stored in 16-bit floats. That is 7B × 2 bytes ≈ 14 GB of weights, and every decode step reads all of it.

At batch size 1, those 14 GB produce exactly one token. The work per weight is one multiply and one add, so the compute units finish almost immediately and then sit waiting for the next bytes to arrive. Decode at batch 1 is memory-bandwidth bound: the speed limit is how fast bytes move, not how fast the GPU computes.

Now run 32 sequences through the same step. Each weight is read once and used 32 times, once per sequence. The step still reads about 14 GB, but it now produces 32 tokens. Since the step was waiting on memory anyway, the extra arithmetic is close to free.

memory traffic arithmetic batch = 1 read 14 GB of weights compute units mostly idle 1 token batch = 32 read the same 14 GB of weights compute units busy 32 tokens Step time is set by the blue bar. Widening the amber bar underneath it is nearly free.

That is the whole trick: same bytes, more tokens.

A systems analogy: group commit

If you have worked on databases, this is group commit. One fsync is expensive, so you collect many transactions and pay for one fsync on behalf of all of them. Two properties carry over directly:

  • Throughput rises much faster than per-request cost.
  • Waiting to fill a batch adds latency for whoever arrived first.

Where the analogy breaks. In group commit, the transactions in a batch share the fsync and add almost nothing else. In LLM decoding, each sequence brings its own KV cache. It is shared with nobody, it has to be read every step, and it grows by one token’s worth of keys and values every step. The weights get amortized across the batch; the KV cache reads do not.

model weights, 14 GB — read once per step, used by the whole batch sequence 1 sequence 2 sequence 3 sequence 4 KV cache KV cache KV cache KV cache Each KV cache is private, sized by that request's conversation, and one token taller after every step.

So adding a sequence to the batch costs real memory, and that cost keeps growing while the sequence runs.

Why you cannot batch forever

Two limits show up as the batch grows.

Compute catches up. The arithmetic per step grows with batch size while the weight bytes stay fixed. At some batch size the GPU stops waiting on memory and starts waiting on its own compute units. Past that crossover a bigger batch is no longer nearly free: each step takes longer, so every request sees slower token-to-token latency.

KV cache memory runs out. Every sequence in the batch needs its KV cache resident in GPU memory, right next to the weights. In practice this is usually the wall you hit first, and it shapes the rest of this post.

KV cache memory runs out everything to the right is unreachable compute catches up (steps get slower) nearly free: each added sequence rides the same bytes 1 2 4 8 16 32 64 128 256 batch size throughput (tokens/s) shape is illustrative, not a benchmark

Static batching and its waste

The simplest way to batch is to collect N requests and keep that group fixed until all of them finish. This is static batching.

A batch finishes when its longest sequence finishes. Output lengths vary from a one-line answer to a multi-page essay, with no way to know the exact length in advance.

Say one request in the batch needs 20 tokens and another needs 2,000. The short one finishes at step 20, and its slot then sits empty for 1,980 steps. Meanwhile new requests wait in the queue, because the batch is not done.

The Orca paper, Section 3, describes this as request-level scheduling. The engine receives a batch and runs its generation loop until the batch finishes. New requests wait outside that loop. A server might stream tokens to clients during execution, but streaming alone does not let a waiting request join the batch.

Static batching — 8 requests, 4 slots step 1 step 9 slot 1 A idle E slot 2 B — the longest in its group F idle slot 3 C idle G slot 4 D idle H barrier: E–H cannot start until A–D have all finished 14 steps. 23 of the 56 slot-steps the GPU offered went to empty seats.

Continuous batching

The fix is to let the scheduler choose batch membership for each GPU iteration. This is continuous batching, also called iteration-level scheduling. The Orca paper introduced this scheduling approach at OSDI 2022.

A request and an iteration are different units. A request lasts until its answer is complete. It usually needs many GPU iterations. During ordinary decode, one iteration processes the latest token of each selected request and produces its next token.

A new request can join between GPU iterations while earlier requests are still generating. Nobody has to finish first if there is capacity. The scheduler prepares a new batch for a later iteration. It does not insert work into a GPU kernel that is already running.

A new request joins before anyone finishes

Suppose the server allows up to three active requests. A and B are already decoding. C arrives during iteration 1. There is enough KV memory and token budget for C, so the scheduler admits it for iteration 2.

Iteration 2 processes A’s next decode token, B’s next decode token, and C’s prompt. A and B are still generating their answers. C has joined without replacing either of them.

C joins before anyone finishes iteration 1 iteration 2 iteration 3 iteration 4 place 1 A decode A decode A decode A decode place 2 B decode B decode B finishes D prefill place 3 empty C prefill C decode C decode C uses spare capacity in iteration 2. D uses capacity freed by B in iteration 4. Each column is an iteration, not equal elapsed time. Scroll sideways on phones.

Now D arrives during iteration 2. All three places are occupied, so D waits. B finishes in iteration 3 when its generation reaches a stopping condition. D can join iteration 4 while A and C continue decoding.

Both admissions are continuous batching. C uses capacity that was already free. D uses capacity that a completed request releases. This example assumes short prompts that each fit in one iteration, enough KV memory, and no preemption.

The next diagram shows the second case at a larger scale. It starts with a full batch, so each new request replaces one that has finished.

Continuous batching — the same 8 requests, the same 4 slots step 1 slot 1 A F G slot 2 B queue empty slot 3 C E queue empty slot 4 D H A free seat is refilled on the very next step. Watch slot 3: C ends, E moves straight in. 11 steps instead of 14. The only idle time left is the tail, when nothing is waiting.

The places in these diagrams are a way to count active requests. They are not permanent GPU workers. Admission also needs a share of the iteration’s token budget and enough KV memory. A long conversation can need much more KV than a short one, so a free place alone does not guarantee that a request fits.

Why A can continue while C joins

A’s next token depends on A’s earlier tokens. It has no dependency on whether B or C has finished. Each request keeps its own token history and KV state.

The engine can therefore prepare one iteration containing requests at different positions. A might be generating its 50th answer token while B generates its fifth and C processes its prompt. The attention metadata keeps their contexts separate.

The vLLM engine walkthrough shows how this works. The engine schedules work for an iteration, runs the model, then updates each request’s state. The runner packs the selected token inputs together and uses each request’s positions and KV block table to read its context. Changing the next iteration’s membership does not require starting A’s generation again.

In the vLLM V1 scheduler used in article #8, running requests receive work first. The scheduler then considers waiting requests if the active-request limit, token budget, and KV allocation allow it. That admission path does not require a running request to finish first. Scheduling policy can still delay a request, so being eligible to join is not a promise of immediate admission.

Which methods wait for a request to finish?

Yes, serving can work that way. The condition depends on how requests are scheduled:

Serving method When a waiting request can start on that engine
One request at a time After the current request finishes.
Static batching After every request in the current batch finishes.
Continuous batching At an iteration boundary when capacity and scheduling policy allow it.

At a full continuous-batching server, a completion often creates the capacity a waiting request needs. That is the D example above. It is still continuous batching, not a separate algorithm that always requires a completion.

There is also a naming trap. Triton’s dynamic batcher groups queued requests before sending a batch to an available model instance. Its documented purpose is batching stateless model calls. Forming batches dynamically does not, by itself, mean that an engine can add requests between the decode iterations of an ongoing generation. Orca’s contribution is to make that iteration boundary available to the scheduler.

What the difference looks like at scale

The scheduling effect is easy to isolate without a GPU. Give 1,000 requests a random output length between 10 and 1,000 tokens, run them through both schedulers with the same batch size, and count how many GPU steps each needs. Every step advances every active request by one token, so both schedulers generate exactly the same tokens; only the seating differs.

Batch size Output lengths Static Continuous Speed-up
16 10–1,000 59,603 steps, 53% of slots busy 32,313 steps, 98% of slots busy 1.84×
64 10–1,000 15,726 steps, 50% of slots busy 8,555 steps, 93% of slots busy 1.84×
16 all exactly 500 31,500 steps, 99% of slots busy 31,500 steps, 99% of slots busy 1.00×

Two things fall out of that table.

The waste comes from variance, not from batching. When every request produces exactly 500 tokens, the two schedulers tie perfectly. It is the mix of short and long outputs that leaves static batching’s seats empty.

Bigger static batches are worse, not better. Going from 16 slots to 64 drops static utilization from 53% to 50%, because a larger group is more likely to contain one very long request that everyone else waits on.

This model deliberately ignores two things: the cost of processing prompts, and memory limits. Every slot is treated as identical and free. Those two omissions are exactly the next section.

The new problems continuous batching creates

Prefill stalls

Before a new request can generate anything, it has to process its whole prompt. This phase is prefill. Unlike decode, prefill handles all the prompt’s tokens at once, so it is compute-heavy rather than memory-bound.

With continuous batching, the scheduler can admit a new request for a later iteration while earlier requests are still generating. In a mixed prefill-and-decode iteration, the new prompt shares the iteration with their decode work. Processing a whole long prompt can make that iteration take much longer. Users see the delay as a stall in the middle of a stream of tokens.

One long prompt joins the batch plain decode + a 4,000-token prefill every active request waits out this one step each small box is one decode step for the whole batch Chunked prefill chunked decode + one quarter of the prompt, four times over Total prefill work is the same. No single step is huge, so nobody sees a stall. The cost: the new request waits a little longer for its own first token.

Sarathi-Serve (Agrawal et al., OSDI 2024) combines prefill chunks with ongoing decodes to control this tradeoff. Article #8 on chunked prefill works through the token budget and vLLM implementation. A heavier alternative runs prefill and decode on separate GPUs entirely.

Reserving memory you do not know you will need

The scheduler has to be sure a request’s KV cache will fit before admitting it. But it does not know how long the output will be. The safe move is to reserve enough room for the maximum possible length.

Most requests use far less than the maximum. All that reserved-but-unused memory cannot hold anyone else’s KV cache, so the batch stays smaller than the GPU could actually fit — and batch size is where the throughput came from in the first place.

Reserve for the worst case reserved, never used actually used 3 sequences admitted — a 4th is refused Hand out memory as it is needed room for more sequences the same 3 sequences, plus many more

This is the problem PagedAttention (Kwon et al., SOSP 2023) attacks, by managing the KV cache the way an operating system manages virtual memory. That is the next post.

Summary

  • Decode is memory-bound, so batching gets more tokens out of the same weight reads.
  • The batch cannot grow forever: compute eventually catches up, and KV cache memory usually runs out first.
  • Static batching wastes slots because output lengths vary and the batch waits for its slowest member.
  • Continuous batching chooses membership for each GPU iteration. A new request can join while earlier requests are still generating if capacity and scheduling policy allow it.
  • Replacing a finished request is one case of continuous batching. Using spare capacity before anyone finishes is another.
  • Keeping KV across iterations lets each request continue at its own position. Mixing new prefill work with decode can cause stalls, and admitting requests still needs enough memory.

References

  • Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models, OSDI 2022. USENIX page
  • Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023. arXiv
  • Agrawal et al., Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve, OSDI 2024. USENIX page
  • Gordic, Inside vLLM: Anatomy of a High-Throughput LLM Inference System, September 2025. vLLM blog
  • vLLM launch article, for the KV memory problem behind larger active batches
  • vLLM V1 scheduler admission path, pinned to the same revision as article #8
  • NVIDIA Triton batcher documentation, for the distinction between dynamic batch formation and iteration-level scheduling
This post is licensed under CC BY 4.0 by the author.