Continuous Function

Legacy Concept Lab

Speculative Decoding: Lossless Multi-Token Generation

Production inference systems (DeepMind Gemini, Google Vertex AI) use speculative decoding to reduce latency while maintaining exact output quality

Concept 20 of 100EfficiencyPhase 6
Open New NotebookAll Foundations
#20Speculative DecodingEfficiency
key equation
αi=min⁡ ⁣(1,pi[xi]qi[xi])\alpha_i = \min\!\left(1, \frac{p_i[x_i]}{q_i[x_i]}\right)
Phase 6: Modern efficiency & inferenceConcept 20 of 100
Migrated:view the updated version in /domains →This /foundations page is legacy during migration.

Why It Matters for Modern Models

  • Production inference systems (DeepMind Gemini, Google Vertex AI) use speculative decoding to reduce latency while maintaining exact output quality
  • Enables 2-3× speedups on common workloads without changing model quality—pure systems optimization
  • Tree-based speculation (Sequoia) extends this to multiple branches, achieving >3× speedups
  • Critical for interactive applications where latency matters—chat, code completion, real-time agents
  • Combines with #19 (efficient attention) since verification step is attention-heavy and benefits from FlashAttention/GQA

What Tutorials Skip

What is still poorly explained in textbooks and papers:

  • Why is this lossless? The rejection sampling mechanism ensures target distribution p is preserved exactly—not approximation
  • Draft model doesn't need to be good everywhere, just similar enough to target on the current input—specialization matters
  • Verification is parallel attention over k tokens, so #19 optimizations directly improve speculative decoding throughput
  • Tree speculation trades compute for coverage—explore multiple futures instead of one linear sequence

Interactive Visualization

Core Math (Optional Deep Dive)

If you want intuition first, start with the key equation and the visualization. Come back here for the full walkthrough.

Key Equation
αi=min⁡ ⁣(1,pi[xi]qi[xi])\alpha_i = \min\!\left(1, \frac{p_i[x_i]}{q_i[x_i]}\right)

Autoregressive LLMs generate one token per forward pass—the sequential bottleneck. Speculative decoding breaks this by using a fast draft model to propose multiple tokens, then verifying them in parallel with the target model.

Key insight: This is lossless—output distribution matches the target model exactly via rejection sampling.

Acceptance probability for each draft token xix_i:

αi=min⁡ ⁣(1,pi[xi]qi[xi])\alpha_i = \min\!\left(1, \frac{p_i[x_i]}{q_i[x_i]}\right)

where pip_i is the target model distribution and qiq_i is the draft distribution at position ii.

Residual sampling when rejected:

xi∼Normalize ⁣(max⁡(0,pi−qi))x_i \sim \text{Normalize}\!\left(\max(0, p_i - q_i)\right)

This ensures output distribution is exactly pp, not qq—the method is mathematically lossless.

Speedup comes from accepting multiple draft tokens at once when the draft model is accurate. With acceptance rate α\alpha and draft length kk:

Speedup≈α⋅k1+(1−α)⋅k\text{Speedup} \approx \frac{\alpha \cdot k}{1 + (1-\alpha) \cdot k}

Canonical Papers

Fast Inference from Transformers via Speculative Decoding

Leviathan, Kalman, Matias2023ICML
Read paper →

Sequoia: Scalable and Robust Speculative Decoding

Chen et al.2024NeurIPS
Read paper →

SpecInfer: Accelerating Generative Large Language Model Serving

Miao et al.2024ASPLOS
Read paper →

Connections

Prerequisites

ℒML/CE/KL⊗Attention⚡Efficiency⚙Efficient Attention

Enables

⚡LLM Serving🎲Decoding

Next Moves

Explore this concept from different angles — like a mathematician would.

Semantic Connections

↔️ Mathematical Dual
🎲Direct ↔ Rejection→Decoding
⚠️ Breaks When
⚡Low acceptance→LLM Serving🎲Entropy kills acceptance→Decoding
≈ Analogy
⚡Student as draft→Efficiency🔀Draft-verify routing→MoE
🔧 Invented to Fix
⚡Latency reduction→LLM Serving⊗Autoregressive latency→Attention
🔄 Same Technique
🎲Accept/reject sampling→Decoding⚡Hide latency with parallelism→MoE Serving