ML//inference//parallel decoding

Parallel decoding is a name for inference schemes that produce more than one token's worth of generation in a single forward pass of a language model, and in practice it covers two different things that answer different questions: several tokens of *one* sequence per step, which makes one user's answer arrive sooner, and one token of *many* sequences per step, which makes the server cheaper per token. Both exploit the same fact. A decoding step is memory-bound, its time set by one read of every weight, so extra tokens in the same pass ride on a read already paid for.

Parallel decoding is a name for inference schemes that produce more than one token's worth of generation in a single forward pass of a language model, and in practice it covers two different things that answer different questions: several tokens of one sequence per step, which makes one user's answer arrive sooner, and one token of many sequences per step, which makes the server cheaper per token. Both exploit the same fact. A decoding step is memory-bound, its time set by one read of every weight, so extra tokens in the same pass ride on a read already paid for.

The first meaning is the one papers usually intend (Jacobi decoding was introduced for translation under this very name). Generation is sequential because each token depends on the last, so every scheme of this kind guesses future tokens cheaply and lets the model check the guesses in one pass, keeping the longest prefix it agrees with. The schemes differ in where the guesses come from:

Speculative decoding takes them from a separate small draft model with the same tokenizer, which costs its own memory and its own steps.

Medusa (Cai and colleagues, 2024) adds a few extra decoding heads on the model's last hidden state, each guessing one position further ahead than the one before it (the model's own head guesses the next token, the first extra head the token after, and so on). The top candidates of the heads are combined into a tree of possible continuations, and the model checks the whole tree in one pass with tree attention, a mask that lets each candidate see only its own ancestors. The heads can be trained on a frozen model; the paper also offers a relaxed acceptance rule for sampling that accepts more tokens and gives up exact equality with the model's distribution.

Multi-token prediction builds the extra heads or layers in during pre-training, so the draft ships inside the model file.

Jacobi decoding guesses nnn future tokens at once (even arbitrary ones), runs them through the model in one pass, and replaces every guess by the model's prediction given the guesses before it, repeating until nothing changes. The fixed point is exactly the greedy output, and each iteration fixes at least the first token, but a wrong early guess spoils the ones after it, so plain Jacobi rarely gains much. Lookahead decoding (Fu and colleagues, 2024) keeps the trajectories of those iterations, harvests the n-grams that appear in them into a pool, and verifies the ones that continue the current text in the same pass; it needs neither a draft model nor extra training, and leaves greedy output unchanged.

Ask which speed a scheme buys.

Several tokens of one sequence per step lower the latency of one answer; many sequences per step, inference batching and its continuous form, raise the server's throughput and make no single user faster, often a little slower. The two compete for the same idle arithmetic below the ridge of the roofline: a server already batching hundreds of sequences has little left for verifying guesses.

Every scheme of the first kind lives on its acceptance rate. Guesses are cheap only while most of them survive; when the text is unpredictable (high temperature, creative prose) most guesses are rejected, the work of making and checking them is wasted, and the scheme can end slower than plain decoding.