THE AUTOREGRESSIVE LOOP

Generation is a strict dependency chain. To sample token n+1 you need the logits at position n, which need the hidden state at position n, which needs token n to have already been sampled. There is no reordering that breaks this.

The practical consequence is that generation latency has a floor set by the number of sequential model invocations, not by total arithmetic. If one forward pass takes 5 ms, then 500 tokens take at least 2.5 seconds. Buying a GPU with twice the FLOPs does not help if each pass is waiting on memory. Buying two GPUs does not help either, unless you split each pass across them (Module 9) — you cannot run pass n and pass n+1 concurrently.

This is what makes LLM serving strange compared to most inference workloads. An image classifier is one forward pass; you scale it by adding replicas. A language model is N forward passes with a serial dependency, and the only ways out are:

1. Make each pass cheaper — quantization, smaller models, better kernels (Modules 6, 7).
2. Do more per pass — batching, so one weight load serves many sequences (Module 5).
3. Take more than one token per pass — speculative decoding, the only technique that attacks the chain length itself (Module 8).

Category 3 is worth flagging now because it is the only one that shortens the dependency chain rather than making each link cheaper. That is why it gets a whole module and why people find it so satisfying.

One caveat on "inherently sequential": it is true for a fixed model and a fixed output. It is not a law of nature. Diffusion language models and other non-autoregressive approaches sidestep it entirely, at a quality cost that has so far kept them out of production for general text.

When a request arrives you have the entire prompt already. There is no dependency problem — every prompt token is known — so you run one forward pass over all of them at once, exactly like a training step without the backward pass.

For a 2,000-token prompt, the W_gate matmul is [2000, 4096] @ [4096, 14336]. You read the 58.7 M-parameter weight matrix once and do 2,000 positions' worth of arithmetic with it. The arithmetic-to-bytes ratio is excellent, the tensor cores are fed, and you are compute-bound.

The cost model for prefill is roughly:

prefill_FLOPs ~= 2 * N_params * S     +     attention term
                 (the matmuls)              (grows as S^2)

The 2 * N_params per token is the standard estimate — every parameter participates in one multiply and one add. For Llama-3-8B that is 2 x 8.03e9 = 16.1 GFLOP per token. A 2,000-token prompt costs about 32.1 TFLOP in matmuls alone.

The attention term is separate and quadratic. Per layer, Q @ K.T and weights @ V together cost about 4 * S^2 * d_model FLOPs. Across 32 layers at S = 2000: 4 x 2000^2 x 4096 x 32 = 2.1 TFLOP. Small next to 32 TFLOP — but at S = 32000 it becomes 4 x 32000^2 x 4096 x 32 = 537 TFLOP against 514 TFLOP of matmul, and attention has taken over. This crossover is why long-context prefill is its own engineering problem.

Because prefill is compute-bound, TTFT scales roughly linearly with prompt length (plus a quadratic term that bites at long context). Doubling the prompt roughly doubles time-to-first-token. And because it already saturates the GPU, batching prefill buys you very little — the machine was already busy.

After prefill you have one token. Now you need the next, and you have exactly one new position to process.

The same W_gate matmul is now [1, 4096] @ [4096, 14336]. You still read all 58.7 M parameters. You do 1 position of arithmetic with them. The ratio has collapsed by 2,000×.

Per decode step, for Llama-3-8B at fp16:

bytes moved:  ~15.0 GB   (every weight, once; embedding is a lookup)
FLOPs done:    ~16.1 GFLOP
intensity:      16.1e9 / 15.0e9  ~=  1.07 FLOP per byte

An H100 can do about 295 FLOPs for every byte it moves. You are asking it to do 1. You are using roughly 0.4% of the machine's arithmetic capability. The GPU spends essentially the whole step waiting for HBM.

Two consequences follow, and both are counterintuitive until you see the numbers:

Decode time is almost independent of context length. The weights are the same 15 GB whether your context is 100 tokens or 100,000. Only the attention step touches the KV cache, and that cache is usually small relative to the weights. Going from 1k to 8k context might move TPOT by a few percent — nothing like the linear growth in TTFT.

Decode gets dramatically cheaper per token when batched. If 32 sequences decode together, you read the 15 GB once and produce 32 tokens. Per-token cost falls by 32×, and arithmetic intensity rises from 1 to 32. This is the single largest lever in LLM serving, and Module 5 is about the machinery required to actually exploit it.

Note what does not change: the latency of a single step. Batching improves throughput while leaving per-user speed roughly flat (slightly worse, in practice). Latency and throughput are different currencies, and batch size is the exchange rate.

Suppose you implement generation the obvious way: keep a list of tokens, append the sampled one, and re-run the full forward pass on the whole list.

This is correct. It is also profoundly wasteful, in two independent ways that are worth separating because people usually only notice one.

Waste 1 — the attention quadratic. At step t you compute a [t, t] score matrix, but you only use the last row. Total attention work over N steps is proportional to sum_{t=1..N} t^2, which is O(N³) in FLOPs — versus O(N²) if you only ever computed the new row. This is the waste that gets mentioned in textbooks.

Waste 2 — the weight re-reads. At step t you re-read all 15 GB of weights and re-derive the K and V vectors for all t positions, when t-1 of them are bit-identical to last step. This is the waste that actually dominates in practice at realistic sequence lengths, because it is bandwidth and bandwidth is what you are short of.

Concretely, generating 512 tokens from a 512-token prompt on Llama-3-8B:

Look carefully: the weight traffic is the same either way. The cache does not save weight reads — those are irreducible for a single sequence, and only batching fixes them. What the cache eliminates is the redundant recomputation of K and V and the quadratic attention blowup.

That is a genuinely important distinction and it is worth sitting with. The KV cache is not the answer to the memory-bandwidth problem. It is the answer to a different problem — redundant recomputation — and it happens to be the prerequisite that makes the real answer (batching) affordable, by keeping per-step work small enough that many sequences fit in flight at once.

Zoom into a single decode step so you know what is actually being timed:

1.  embedding lookup           one row, 8 KB
2.  for each of 32 layers:
      a. RMSNorm               read 4096, write 4096      bandwidth-bound
      b. q/k/v projections     read 25 MB of weights      bandwidth-bound
      c. RoPE on q, k          tiny elementwise           bandwidth-bound
      d. append k,v to cache   write ~4 KB                bandwidth-bound
      e. attention over cache  read the whole KV cache    bandwidth-bound
      f. o_projection          read 33 MB                 bandwidth-bound
      g. residual add          trivial                    bandwidth-bound
      h. RMSNorm               trivial                    bandwidth-bound
      i. gate/up/down          read 352 MB of weights     bandwidth-bound
      j. residual add          trivial                    bandwidth-bound
3.  final RMSNorm
4.  lm_head                    read 1.05 GB               bandwidth-bound
5.  sample from 128256 logits

Every single line is bandwidth-bound at batch 1. There is not one compute-bound operation in a decode step.

Two things this makes visible that the FLOP count hides:

Kernel launch overhead is real. That is on the order of 200+ separate CUDA kernel launches per token if nothing is fused. At roughly 5 µs of launch overhead each, you are looking at ~1 ms of pure overhead against a ~4.5 ms theoretical step — over 20% of your budget spent launching work rather than doing it. This is why CUDA Graphs (capture the launch sequence once, replay it) and aggressive kernel fusion are standard in serving engines, and why a naive PyTorch loop is often 2–3× slower than the roofline says it should be.

Step 4 is expensive and easy to forget. The LM head is a [1, 4096] @ [4096, 128256] matmul reading 1.05 GB. That is 7% of your entire per-token byte budget spent turning a hidden state into logits, for a model whose vocabulary is large. It is one reason vocabulary size is an inference cost, not just a modelling choice.

"How fast is your model?" is not a well-posed question. There are at least four distinct numbers and they trade against each other:

• TTFT (time to first token) — how long until the user sees anything. Dominated by prefill, so it scales with prompt length and with how long you queued behind other work.
• TPOT / ITL (time per output token, inter-token latency) — the gap between successive tokens. Dominated by decode. This is what "feels" fast.
• End-to-end latency — TTFT + TPOT × output_tokens, roughly. What actually matters to a user waiting for a complete answer.
• Throughput — total tokens per second across all concurrent requests. What determines your cost per million tokens.

The tension: throughput is maximized by large batches, because one weight load serves many sequences. Per-user TPOT is (slightly) hurt by large batches, and TTFT is badly hurt by them because your request waits for a slot and then contends with everyone else's prefill.

A useful frame is Little's Law: concurrency = arrival_rate × latency. If you want to serve 100 requests per second and each takes 2 seconds, you need 200 requests in flight. That number must fit in your KV cache budget — which is Module 2's subject, and the reason memory management turns out to be the discipline that governs everything.

The practical upshot is that any benchmark quoting a single "tokens per second" figure without saying at what batch size, at what context length, and at which percentile is not telling you anything. A system doing 15,000 tok/s aggregate at batch 256 may deliver a miserable 12 tok/s to each user. Both numbers are true. Module 10 returns to how to benchmark honestly.