Speculative Decoding

Every time a large language model writes a word, it runs its full stack of billions of parameters — just to produce one token. That one-at-a-time loop is the main bottleneck of modern AI inference: the model is not limited by how fast it thinks, but by how many sequential steps it must take.

Speculative decoding, introduced independently by Chen et al. and Leviathan et al. in 2023, breaks the loop. The idea is almost embarrassingly simple:

1. A small, fast draft model proposes a sequence of tokens — say, five at once.
2. The large target model verifies all five in a single parallel forward pass.
3. If the big model agrees with the draft, all five tokens are accepted for free. If it disagrees at some position, every token up to the first disagreement is still kept, and the sequence is corrected from there.

The output distribution is mathematically identical to running the big model alone — not an approximation, an exact match. Yet in practice you often need only one big-model step for every three to five tokens, giving speed-ups of 2–4× on hardware that can run the small model cheaply alongside the large one.

The simulation below models speculative decoding as a sequence of propose → verify rounds. The draft model picks a token from its own probability distribution; the big model then decides whether to accept it or sample a correction.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{label_accept_rate}} <span id="rate-val">70%</span>
    <input type="range" id="accept-rate" min="10" max="100" step="5" value="70">
  </label>
  <label>{{label_draft_len}} <span id="draft-val">4</span>
    <input type="range" id="draft-len" min="1" max="6" step="1" value="4">
  </label>
</div>
<div id="tokens-area" class="tokens-area"></div>
<div class="stats-row">
  <div class="stat-box"><span class="stat-num" id="stat-target">0</span><span class="stat-label">{{stat_target_steps}}</span></div>
  <div class="stat-box highlight"><span class="stat-num" id="stat-speedup">—</span><span class="stat-label">{{stat_speedup}}</span></div>
  <div class="stat-box"><span class="stat-num" id="stat-tokens">0</span><span class="stat-label">{{stat_tokens_out}}</span></div>
</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="legend" class="legend">
  <span class="leg accepted">{{leg_accepted}}</span>
  <span class="leg corrected">{{leg_corrected}}</span>
  <span class="leg draft">{{leg_draft}}</span>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .8rem; font-size: .88rem; }
label { display: flex; align-items: center; gap: .5rem; }
input[type=range] { flex: 1; accent-color: #1d3557; }
.tokens-area { display: flex; flex-wrap: wrap; gap: 5px; min-height: 52px;
               padding: .5rem; background: #f4f6f9; border-radius: 10px; margin-bottom: .6rem; }
.token { display: inline-flex; align-items: center; justify-content: center;
         padding: .25rem .55rem; border-radius: 6px; font: 600 13px ui-monospace, monospace;
         border: 1.5px solid transparent; transition: background .15s; }
.token.accepted  { background: #d4edda; border-color: #0a7d33; color: #0a7d33; }
.token.corrected { background: #fff3cd; border-color: #b57a00; color: #7a5200; }
.token.draft     { background: #e0e7ff; border-color: #3a5fd9; color: #1d3557; }
.stats-row { display: flex; gap: .6rem; margin-bottom: .7rem; }
.stat-box { flex: 1; text-align: center; padding: .4rem .3rem;
            background: #f0f4f8; border-radius: 8px; border: 1px solid #d0d8e2; }
.stat-box.highlight { background: #fff3cd; border-color: #e0b000; }
.stat-num  { display: block; font: 700 1.4rem system-ui; }
.stat-label{ display: block; font-size: .72rem; color: #555; margin-top: .1rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { display: flex; gap: .8rem; flex-wrap: wrap; font-size: .8rem; }
.leg { padding: .18rem .5rem; border-radius: 5px; }
.leg.accepted  { background: #d4edda; color: #0a7d33; border: 1.5px solid #0a7d33; }
.leg.corrected { background: #fff3cd; color: #7a5200; border: 1.5px solid #b57a00; }
.leg.draft     { background: #e0e7ff; color: #1d3557; border: 1.5px solid #3a5fd9; }

// Code not found

Notice how the accept rate controls everything. When the draft model is well-matched to the task, most tokens sail through and the big model does very little work. When it diverges, corrections happen more often — but you never lose correctness, because every rejection produces a valid token from the big model's own distribution.

This is analogous to how Transformers process all positions in a sequence in parallel during training — here the parallelism is exploited at inference time.

The magic of speculative decoding is that it is provably exact, not a heuristic. Here is why.

When the big model sees a draft token $x$ at position $t$, it computes its own probability $p(x)$. The draft model had probability $q(x)$. The acceptance rule is:

• Accept $x$ with probability $\min(1,\, p(x)/q(x))$.
• If rejected, sample a corrected token from a residual distribution $\max(0,\, p - q)$, re-normalised.

This rejection-sampling construction guarantees that the marginal distribution of every accepted (or corrected) token equals $p$ exactly. The big model's output distribution is preserved token-by-token.

Where the speed-up lives. Modern hardware runs matrix multiplications on a batch of sequences far faster than the same total work split into sequential steps. Verifying $k$ draft tokens costs roughly as much as generating one token autoregressively. So if the average number of tokens accepted before a rejection is $\bar{k}$, the wall-clock speed-up is approximately $\bar{k}$ — often 2–4× in practice.

The trade-off. You need a draft model whose outputs are correlated with the target. Too mismatched and $\bar{k}$ collapses to 1, giving no benefit. Too large and the draft model eats the savings. The sweet spot — a model 10–100× smaller than the target, trained on the same data — is where speculative decoding shines. Compare this to the nn-training perspective: the draft model is essentially a much smaller network whose learned distribution must approximate the bigger one.

Speculative decoding is now a standard inference optimization in production LLM deployments:

• Interactive chat: reducing first-token and per-token latency makes conversations feel instantaneous rather than slow.
• Code completion: models like GitHub Copilot benefit enormously because code is repetitive — the draft model matches well and acceptance rates are high.
• Retrieval-augmented generation (RAG): the target model verifies chunks of retrieved text faster than it could generate them from scratch.
• On-device inference: running a tiny draft model on a phone's NPU while offloading verification to a cloud model is an emerging hybrid pattern.
• Multi-model pipelines: speculative decoding generalises — any model that can cheaply approximate a larger one can act as a drafter, enabling entire chains of hierarchical speed-ups.

The technique is deployed in Google's PaLM 2, Meta's code models, and various open-source serving stacks (vLLM, llama.cpp). It represents a broader principle: parallelism that was always available in the verification step, waiting to be exploited.

Speculative decoding is one of the few techniques in machine learning that offers a genuine free lunch: the same output distribution as the large model, at a fraction of the sequential cost. The key insight is that verification is much cheaper than generation when you can batch it, and rejection sampling ensures you never trade quality for speed.

It also illustrates a deep principle about computation: the hard constraint is often not how much work you do but how sequentially you must do it. Finding the parallelism hidden inside a sequential process — as speculative decoding does for token generation — is one of the most powerful ideas in the science of efficient algorithms.

For a companion perspective on why transformers can process sequences in parallel during training but must generate them step by step at inference, see Transformers and Attention.