Decoding chains: speculative speedup, draft length, sampling and masks

Speculative decoding questions are algebra with two inputs that move: the acceptance rate and the cost of a draft. The sampling and masking chains are short but come up in almost every decoding round.

Tokens per verification

inputs   acceptance alpha per drafted token, gamma drafts per verification
formula  E[tokens] = (1 - alpha^(gamma + 1)) / (1 - alpha), bonus token included
alpha 0.7, gamma 5   (1 - 0.7^6) / 0.3 = 2.94 tokens
alpha 0.8, gamma 4   (1 - 0.8^5) / 0.2 = 3.36 tokens
sanity   always between 1 (every draft rejected) and gamma + 1

The tempting answer is 1 + gamma x alpha, which gives 4.5 for the first case. It assumes later drafts survive independently of earlier ones; in fact one rejection discards every draft after it.

Drilled in: Speculative speedup and losslessness · Speculative decoding algebra

Accepted drafts are not alpha

inputs   alpha 0.7, gamma 5, as above
accepted E[tokens] - 1 = 1.94 drafts per verification
ratio    1.94 / 5 = 0.39 of drafted tokens accepted
sanity   0.39 and 0.7 describe the same drafter; the ratio falls as gamma
         grows because late positions rarely get a chance

A dashboard that divides accepted by drafted tokens reports the 0.39. Converting it back to alpha needs gamma, and comparing two drafters by the ratio at different gamma compares nothing.

Drilled in: Measure acceptance in production

Draft cost from bytes

inputs   target Llama 3.1 8B BF16, 16.06 GB; drafter Llama 3.2 1B BF16,
         1.24e9 x 2 B = 2.47 GB; same tokenizer; batch 1 on an H100 SXM
draft    2.47 GB / 3.35 TB/s = 0.74 ms per draft step
c        0.74 / 4.79 = 0.154 of a target step
speedup  E[tokens] / (1 + gamma x c) = 2.94 / (1 + 5 x 0.154) = 1.66x
sanity   at batch 1 both models are bandwidth-bound, so c is close to the
         ratio of their weight bytes

A 1B drafter is cheap per step and expensive per verification, because it runs gamma times. Draft heads that reuse the target's hidden states bring c down to a few percent, which is where long drafts start to pay.

Drilled in: Medusa heads or a separate draft model

The best draft length

inputs   alpha 0.7; speedup(gamma) = E[tokens] / (1 + gamma x c)
c 0.154  gamma 1: 1.47  2: 1.67  3: 1.73  4: 1.71  5: 1.66
c 0.05   gamma 3: 2.20  4: 2.31  5: 2.35  6: 2.35  7: 2.33
sanity   the cheaper the draft, the longer the best draft; at c = 0.154 the
         peak is gamma 3, at c = 0.05 it is gamma 5 or 6

A fixed gamma tuned on one drafter is wrong for the next. The curve is flat near its peak, where one step either side costs 1 to 4%, so the drafter's cost matters more than fine-tuning the length.

Drilled in: Draft length for a parallel drafter

The verify-token budget at batch

inputs   gamma 5, so each sequence sends gamma + 1 = 6 tokens to verification
batch 8  8 x 6 = 48 tokens per verification step
batch 64 64 x 6 = 384 tokens per step
ridge    H100 SXM BF16 about 295 FLOP per byte: a weight GEMM over 384 rows
         is past it
sanity   below the ridge verification rides on bandwidth already paid for;
         past it every verified token costs compute

Speculation spends spare compute. At batch 64 the spare compute is gone, which is why a speedup measured at batch 1 can become a slowdown on a loaded server.

Drilled in: Speculative decoding from batch 1 to 256

Temperature, then top-p

inputs   three tokens with logits 2, 1, 0; vLLM v0.32.0 applies temperature
         before the top-k and top-p cut
T 1.0    softmax = 0.665, 0.245, 0.090
T 0.5    logits become 4, 2, 0: softmax = 0.867, 0.117, 0.016
top-p 0.85  at T 1.0 keeps 2 tokens (0.665 + 0.245); at T 0.5 keeps 1
sanity   lowering temperature sharpens the distribution, so the same p keeps
         fewer tokens

Applying the two in the other order keeps a different set. When two engines disagree on outputs at the same settings, the order of the sampling steps is one of the first things to compare.

Drilled in: Order of temperature, top-k and top-p · Sampling

A grammar mask per step

inputs   Llama 3 vocabulary of 128,256 tokens; one bit per token
mask     128,256 / 8 = 16,032 B per sequence per step
batch    256 sequences: 4.1 MB per step
sanity   the bytes are small; the cost is computing which tokens the grammar
         allows, on the CPU, before the GPU can sample

A mask that arrives after the forward pass finishes stalls the step. That is why grammar engines precompute masks for states they can predict and why a new schema's first request is slow.

Drilled in: Grammar mask cost · Grammar-constrained decoding

Beam search on paged KV

inputs   4 beams, 1,000-token prompt, 200 generated tokens each, 16-token blocks
unshared 4 x 1,200 = 4,800 tokens of KV
shared   1,000 + 4 x 200 = 1,800 tokens, plus at most one copied block per
         fork point
sanity   2.7x less KV, and the saving grows with prompt length

Beams share blocks by reference. The copy happens only when a beam is about to write into a partly filled block that another beam also holds, which is the copy-on-write rule the allocator must get right.

Drilled in: Beam search on paged KV