Making generation faster

You can already say why generating tokens is expensive. This section is about the techniques that make it less so: batching that never pauses to refill, a KV cache allocated in pages, a small model drafting tokens for a large one to check. Each has a workload it suits and a workload where it does nothing or makes things worse, so the section is built around predicting which will help before you spend a week implementing it.

Two workloads, one model#

A generation request has two phases that behave nothing like each other. Prefill reads the whole prompt at once: every token goes through every layer together, so each weight is read once and used for hundreds or thousands of positions. That is a large matrix multiplication and it is compute-bound. Decode produces one token at a time: each step reads every weight again and uses it for a single position, which is very little arithmetic for a great deal of memory traffic, and it is memory-bound.

Prefill    scales with prompt length      compute-bound     sets time to first token
Decode     scales with output length      memory-bound      sets time per output token

Almost every technique below is an answer to the second row. Quantization helps because there are fewer weight bytes to read. Batching helps because the same read serves more requests. Speculative decoding helps because a memory-bound step has spare arithmetic going unused.

Roofline reasoning#

Arithmetic intensity is the number of floating point operations performed per byte moved to and from memory. Every accelerator has its own ratio of peak compute to peak bandwidth. If your intensity is below the hardware's ratio you are memory-bound, and no faster arithmetic will help; above it you are compute-bound.

arithmetic intensity = FLOPs performed / bytes moved

card with 1000 TFLOP/s and 3 TB/s  ->  ratio about 330 FLOP per byte

decode at batch 1    about 2 FLOP per weight byte   ->  far below: memory-bound
decode at batch 256  about 500 FLOP per weight byte ->  above: compute-bound
prefill, 2k prompt   thousands of FLOP per byte     ->  compute-bound

The useful consequence is that you can compute the floor on decode speed before renting anything. At batch size one, a decode step must read every weight, so the time per token cannot be less than the weight bytes divided by the memory bandwidth.

8B parameters at 16-bit  = 16 GB read per token
card with 2 TB/s         = 16 / 2000 s = 8 ms per token = about 125 tokens/s

the same model at 4-bit  = 4 GB  -> 2 ms -> about 500 tokens/s (ceiling)

Continuous batching#

Static batching collects requests, runs them together and returns when the longest finishes. A request wanting 20 tokens waits behind one wanting 500, and the GPU spends the tail of the batch mostly idle. Continuous batching admits and retires sequences at every decode step instead, so a finished sequence leaves immediately and a waiting one takes its slot.

It wins so much because decode is memory-bound. One step reads the weights once whether it serves one sequence or sixty, so the extra sequences use arithmetic that was being wasted. Throughput rises nearly linearly with batch size until either the KV cache fills the remaining memory or the batch grows large enough to become compute-bound, which is where the roofline arithmetic tells you to stop.

Paged attention#

The naive way to hold a KV cache is to reserve, per sequence, enough contiguous memory for the maximum length it might reach. A request that stops after 200 tokens of a possible 8,000 has held onto memory nobody could use. Paged attention allocates the cache in small fixed-size blocks, the way an operating system pages memory, and hands them out as a sequence grows.

Waste falls from most of the reserved cache to under one block per sequence, and the blocks make prefix sharing possible: two requests with the same system prompt can point at the same blocks until they diverge. The work that introduced it reported two to four times the throughput at the same latency, which is concurrency bought purely by not wasting memory.

Speculative decoding#

A small draft model generates the next few tokens cheaply. The large model then checks all of them in a single forward pass, because verifying k proposed positions costs about what one decode step costs: the weights are read once either way, and a memory-bound step has the arithmetic to spare. Tokens are accepted up to the first one the large model would not have produced, and generation continues from there.

draft proposes   the cat sat on the mat
large verifies   the cat sat on the  |  rug      -> 5 accepted, 1 corrected

one large-model pass produced 6 tokens instead of 1

Whether it pays depends on the acceptance rate. Each round costs the draft model's k steps plus one large pass, so the draft has to be both much cheaper, commonly ten to twenty times, and right often enough. Acceptance in the region of two thirds and above is where the arithmetic usually works; below that the drafting costs more than the accepted tokens save. Acceptance is also task-dependent, which is why it should be measured on your own traffic rather than taken from a paper. Code and structured output accept well; open-ended prose accepts worse.

The one place it disappoints is a server already batching heavily. It spends spare compute, and at large batch sizes there is none spare, so it can make throughput worse while still improving latency for a single stream.