LLM engine from scratch · Part 6/7

Speculative Decoding: More Tokens per Weight Read

2026-11-21 · Servloci Engineering

After Part 5, single-stream decoding on the GPU ran close to the memory-bandwidth ceiling. The formula from Part 1 says the only way past it is to get more than one token out of each pass over the weights. That's what speculative decoding does. This part covers the idea, the argument for why the output is exactly the same as running the big model alone, the bookkeeping that makes rollback free, and the measurements, including where it doesn't help.

The idea

Run two models with the same tokenizer:

Each step:

  1. The draft generates k tokens autoregressively: d₁ … d_k. This is cheap.
  2. The target processes [next, d₁, …, d_k] as k+1 rows in one forward pass. Because decoding is memory-bound, a pass over 5 rows costs about the same as a pass over 1: the weights are read once either way.
  3. Compare. Row i of the target's output is the target's own prediction for position i+1. Accept drafts while they match; at the first mismatch, emit the target's token instead.

If the draft gets a tokens right, the step produces a+1 tokens for one target pass (plus k cheap draft passes). Even when every draft is wrong, the step still produces one correct token, the target's.

Why the output is exactly the target's

Greedy decoding. At each position, the target's argmax is computed from the true prefix: the draft tokens it's conditioned on were accepted only if they equal what the target itself would have chosen. So the emitted sequence is token-for-token what the target would produce alone.

Sampling (temperature > 0). The standard method (Leviathan et al., Chen et al.) accepts each draft token with probability min(1, p_target / p_draft) and resamples from an adjusted distribution on rejection. It's exact and gets high acceptance, but needs the draft's full probability distribution for every drafted token.

qpipe uses a simpler exact scheme: the target samples every row itself, with the stream's own random generator, and drafts are accepted while the target's sample equals the draft token. Every emitted token is a genuine sample from the target's distribution conditioned on the actual preceding text, so the output distribution is exactly the target's. The trade-off is lower acceptance than rejection sampling at high temperatures, because two independent samples have to agree. For greedy decoding, tool calls and low-temperature chat, the case that matters most here, the two methods are identical.

Tested: three prompts (prose, code, a list) with greedy decoding produced byte-identical output with and without speculation, for every draft length tried.

Rollback is free

The usual worry with speculation is undoing work when drafts are rejected. In qpipe the KV cache is indexed by position: row p writes its K and V to slot p (Part 4). When the target verifies [next, d₁, d₂, d₃, d₄] at positions p … p+4 and accepts only d₁, positions p+2 … p+4 hold K/V for tokens that never happened. Nothing needs to be cleaned up. The stream's position advances to p+2, attention only ever reads positions up to the current one, and the next step overwrites the stale slots.

The same holds for the draft model's cache.

The bookkeeping

Each stream tracks where the draft is relative to the target. After a step where the target accepted a of k drafts:

s->pos += acc + 1;
s->dlag = acc == k ? d[b][k] : -1;     // all accepted: draft never saw d_k

Prefill needs the draft too: it can't predict anything without having read the prompt. Whenever the target processes prompt rows, the draft processes the same rows right after, with no logits requested.

One step in code

The whole speculative step is one function in the GPU worker. Drafting, batched across every decoding stream in the group:

for (int j = 0; j < kmax; j++) {
    dr->n = dr->nw = 0;
    for (int b = 0; b < B; b++) {
        if (!isdec[b] || keff[b] <= j) continue;
        int sid = g * B + b, p = st[b].pos;
        if (j == 0 && st[b].dlag >= 0) rows_add(dr, sid, p - 1, st[b].dlag);   // catch-up row
        rows_add(dr, sid, p + j, d[b][j]);
        rows_want(dr, b, j);
    }
    embed_x(dm, dr->x, dr->tok, dr->n);
    gpu_forward(S->gd, dr->x, dr->sid, dr->pos, dr->n, dr->want, dr->nw, NULL, dtoks);
    for (int q = 0; q < dr->nw; q++) d[dr->wb[q]][j + 1] = dtoks[q];
}

Verification, one target pass for all streams, plus any prefill rows for streams still reading their prompt:

for (int b = 0; b < B; b++) {
    if (!isdec[b]) continue;
    q0[b] = tr->nw;
    for (int j = 0; j <= keff[b]; j++) {
        rows_add(tr, g * B + b, st[b].pos + j, d[b][j]);
        rows_want(tr, b, j);                    // every verify row needs the target's choice
    }
}

Acceptance:

int k = keff[b], acc = 0;
while (acc < k && ttoks[q0[b] + acc] == d[b][acc + 1]) acc++;
for (int t = 0; t <= acc; t++)
    if (emit_one(e, g, b, ttoks[q0[b] + t])) break;    // stops at end-of-turn or max tokens

The row abstraction from Part 4 is what makes this short: verification is just "k+1 rows of the same stream", causal attention inside the verify batch works for the same reason it does in prefill, and the GPU argmax kernel from Part 5 returns the target's choice for every row in one transfer.

The draft length is also capped per stream so a verify pass never runs past the context window or the request's token limit.

Fixed draft length: a trade-off

Qwen3-4B Q8, tok/s prose code
no speculation 61.3 61.3
k = 2 67.1 (45% accepted) 85.3 (72%)
k = 3 61.7 (36%) 91.5 (71%)
k = 4 56.8 (29%) 88.4 (60%)
k = 6 47.1 (22%) 83.9 (52%)

Code and structured text are predictable: the draft is right 60–70% of the time, and a 4-token draft yields over 3 tokens per target pass. Open-ended prose isn't: at k = 4 only 29% of drafts survive, and spending four draft passes to gain a little over one extra token per step makes things slower than not speculating.

Part of the gap is the draft itself. Qwen3-0.6B is a hybrid "thinking" model, while the target is the non-thinking Instruct-2507 variant. Their styles differ, so the draft's guesses diverge more on free text than on code, where there are fewer reasonable ways to write the next token.

Adaptive draft length

The best k depends on the text, and it changes within a single answer: a code block followed by an explanation. So each stream adjusts its own draft length after every step:

if (k > 0 && acc == k && s->kcur < K) s->kcur++;     // draft was fully right: try one more
else if (acc * 2 < k && s->kcur > 1)  s->kcur--;     // less than half right: back off

It starts at 2 and is capped at -K (default 6).

tok/s, 1 stream plain adaptive (max 6)
Q8: prose / code / translate 65 / 66 / 68 69 / 98 / 82
Q4: prose / code / translate 98 / 101 / 103 102 / 137 / 119

Now speculation is never slower than plain decoding: prose gets a small gain, code gets +50% at Q8 and +36% at Q4, and output is still byte-identical in greedy mode.

The best case turned out to be tool calling. Tool-call output is rigid JSON: {"name": "get_weather", "arguments": {"city": ...}}. The draft got 83% of its tokens accepted on tool calls, and generation ran at about 103 tok/s on the 4B model at Q8, against 62 without speculation.

Limits

LLM engine from scratch series

  1. The Physics of Token Speed: Why Memory Bandwidth Sets the Limit
  2. Reading GGUF and Running Qwen by Hand
  3. CPU Kernels: Q8, Q4 and AVX-512 VNNI
  4. Threads, Pinning and the Pipeline
  5. Going to the GPU: from 230 to 1,300 tok/s
  6. Speculative Decoding: More Tokens per Weight Read
  7. Serving It: OpenAI API, Tool Calling and KV Reuse
← Part 5Part 7 →