Speculative Decoding for Mixture-of-Experts Models: Expert Bytes, Kernel Bandwidth and the Best Draft Length
Yuzheng Lan
cs.LG
Oct 25, 2026 · v1
cs.DC cs.PF
TL;DR
Theorems on when speculative decoding beats plain decoding, the optimal draft length, and bandwidth-error bounds are proved in Lean 4 against Mathlib (package MoESpec).
Abstract
Speculative decoding checks several drafted tokens in one verification pass. On a mixture-of-experts (MoE) model, consecutive tokens often select the same experts. A deduplicating engine reads each selected expert once per pass, so it requests fewer bytes than a per-slot engine, which reads it once per token. We write a step's time as the bytes each kernel requests over its effective bandwidth, plus fixed time. Under geometric acceptance, we derive from this step time when speculation is faster than plain decoding. The best draft length is a monotone staircase in the acceptance rate. We bound how a bandwidth error moves each result, and we check the main steps in Lean. Deduplication is faster exactly where its share $\bar u(n)$ of the per-slot bytes is below its ratio $r(n)$ of the per-slot bandwidth. On llama.cpp Metal, MLX-LM and llama.cpp CUDA, which we modified to deduplicate, the per-slot kernel has the higher effective bandwidth (r = 0.32 to 0.75). Thus deduplication is faster only from 5 to 8 tokens per pass, or never. We fit the bandwidths on one layer's expert operation, run alone, in under an hour per model. Bytes from routing traces over these bandwidths predict the time that deduplication saves. The measured saving lies inside its error bound at every point on CUDA and MLX-LM and at 36 of 48 points on Metal. The crossover is the first pass size at which deduplication is faster. The prediction places it within one pass size in 10 of 12 configurations of engine, model and depth. We computed these predictions after the measurements. On DeepSeek-V2-Lite, operation times measured before its speculative runs give the best draft length on CUDA within one at all 22 acceptance values.
Problem
Speculative decoding on mixture-of-experts models gives inconsistent speedups because verification-pass cost depends on expert reuse across tokens and on kernel bandwidth. The open questions are when speculation and expert deduplication are faster, and which draft length is best.
Approach
Step time is modeled as the bytes each kernel requests divided by its effective bandwidth, plus fixed time. Under geometric acceptance, the paper derives conditions for speculation to beat plain decoding, shows the best draft length is a monotone staircase in acceptance rate, and bounds the effect of bandwidth errors. The main steps are machine-checked in a Lean 4/Mathlib package called MoESpec. Predictions are tested on llama.cpp Metal, MLX-LM and llama.cpp CUDA, with engines modified to deduplicate.
Results
The per-slot kernel has the higher effective bandwidth everywhere measured (r = 0.32 to 0.75), so deduplication is faster only from 5 to 8 tokens per pass, or never. The predicted crossover lies within one pass size in 10 of 12 configurations. On DeepSeek-V2-Lite, operation times measured before its speculative runs give the CUDA best draft length within one at all 22 acceptance values.
| engine | model | β_slot | β_dedup | r | ū |
|---|
| llama.cpp CUDA | OLMoE | 618 | 464 | 0.75 | 0.82 |
| llama.cpp CUDA | gpt-oss | 654 | 346 | 0.53 | 0.72 |
| llama.cpp Metal | Qwen3 | 131 | 65 | 0.50 | 0.77 |
| MLX-LM | OLMoE | 129 | 75 | 0.58 | 0.82 |
Effective bandwidths (GB/s), bandwidth ratio r and byte share ū at n=2 (subset)