Beam search, speculative decoding & Medusa

01 · Concept

Concept

Lesson 7.3 left decode in an uncomfortable place: at batch 1, Qwen3.8-27B streams roughly 54 GB of weights from memory for every single token it emits. The serial chain — token $t+1$ cannot be finalized before token $t$ — seems to force that price. This lesson covers the methods that spend extra parallel work around the chain, and they optimize two very different things. Beam search buys output quality. Speculative decoding and Medusa buy speed, by getting more than one token out of each expensive weight read — and Qwen3.8-27B arrives with its own native version of the trick.

Beam search first, briefly, because it is the odd one out. Instead of one partial sequence it keeps $b$ candidates, extends each with plausible next tokens, scores by cumulative log-probability (with length normalization, or short outputs win by default), and prunes back to $b$. It shines when sequence-level likelihood matters — constrained transduction, some structured tasks — and disappoints in open-ended dialogue, where beams collapse into near-duplicate, blandly probable text. Width multiplies compute and KV-cache use (beams share prefixes through copy-on-write block tables). It is a search algorithm, not an acceleration.

Speculative decoding attacks latency directly. A cheap draft model proposes a block of $k$ future tokens autoregressively; the expensive target model then evaluates all $k$ positions in a single pass — the same parallel shape as a short prefill, one weight read amortized over $k$ candidates. An acceptance rule compares draft probability to target probability token by token: accepted tokens commit, and at the first rejection the dependent suffix is discarded and a corrected token is sampled from an adjusted distribution. Done properly (Leviathan et al.), the output is distributed exactly as if the target had decoded alone under the same sampler — stronger than merely checking argmax agreement.

How much does it help? An illustrative back-of-envelope: with per-token acceptance probability $\alpha$ and block length $k$, the expected tokens committed per target pass is

counting the bonus token the target itself supplies. At $\alpha = 0.8$ and $k = 4$: $0.8^{5} = 0.32768$, so $\mathbb{E} = (1 - 0.32768)/0.2 \approx 3.36$ tokens per pass — each 54 GB weight read now yields three-plus tokens instead of one. The figures are illustrative, not Qwen benchmarks; real acceptance rates depend on prompts, sampler settings, and how well the draft mimics the target.

Now the classic wrong turn: “speculative decoding saves computation.” It does not — it increases total FLOPs. The draft runs on every token, the target re-scores every proposal, and every rejected suffix is pure waste. If decode were compute-bound, speculation would make it slower. It wins because lesson 7.3 showed decode is bandwidth-bound: arithmetic units sit idle while weights stream, so the extra verification math is nearly free, and the scarce resource — bytes moved per committed token — drops by the acceptance factor. Correcting this misconception tells you when to reach for the technique: latency-sensitive, small-batch serving. At high batch sizes the weight read is already amortized across sequences, and speculation’s appeal fades.

The draft itself is a tension: too weak and proposals get rejected; too large and proposing costs what verifying saves; and a separate model must be hosted, scheduled, and kept compatible with the target. Medusa (Cai et al.) dissolves the separate model by bolting lightweight decoding heads onto the target itself, each predicting a token at a future offset; the heads propose a small tree of continuations that one verification pass prunes to an accepted path. The heads must be trained against the exact base checkpoint — change the base, retrain the heads.

Qwen3.8-27B takes the final step: the model card states it was trained with multi-token prediction over multiple steps. The drafter is not bolted on afterward; the trunk itself learned to propose several future tokens as part of pretraining. At inference this functions as a native draft source — no second model to deploy, no post-hoc heads to fit, proposals that come from the same representations the verifier uses. Serving stacks that support it (the model card lists vLLM and SGLang among its runtimes) can verify MTP proposals exactly as they would a draft model’s.

A public RTX 5090 campaign shows why this must be measured behind a correctness gate. In that report, a stock accelerated stack with TurboQuant 4-bit KV and MTP3 launched but failed exact-output, JSON, tools, coding, and multi-turn canaries, so the speed result was held rather than published as a win. After patch #40914, the same frozen canaries passed and the matched C1 run reported 151.27 tok/s true decode, TTFT 0.920 s, E2E 7.69 s, and 830 of 834 MTP proposals accepted (99.52 percent). That is a useful case study for this one stack, not a universal Qwen number: the lesson is correctness before speed, then acceptance statistics and workload shape beside the throughput figure.

The bookkeeping is the quiet hard part. Tree-structured candidates share a prefix and diverge later; attention masks must keep branches from reading each other; accepted states commit in order while rejected branches release their cache blocks. A bug here produces plausible-but-wrong tokens, so validate against baseline decoding distributionally. Streaming clients must also tolerate bursts: when four tokens are accepted at once, they arrive at once.

The durable distinction is purpose. Beam search pays for multiple hypotheses to choose a better sequence. Speculation pays a proposer to expose parallel work while the target stays authoritative over the distribution. Medusa moves the proposer into the architecture — and Qwen3.8-27B’s MTP training moves it all the way into pretraining, turning a serving trick into a property of the model itself.