Deep NLP

1 episodes

Paper: Speculative Decoding

Speculative decoding lets a cheap draft propose several tokens that the target verifies in one memory-bound pass. The module derives the accept/reject rule (accept with min(1, p/q), resample from norm(max(0, p - q))) and proves it reproduces the target exactly, derives acceptance as 1 - TV, the expected tokens per call and the wall-time speedup, and tests exactness empirically with a chi-square test on whole sequences. Three plausible wrong rules are caught by the same test. MTP heads (Paper: Multi-Token Prediction (DeepSeek-V3)) are analysed as self-speculative drafts.

Progress — loading…

Objectives

Language

  • Explain why autoregressive decoding is memory-bandwidth bound and why predictable tokens make drafting work
  • Explain how MTP heads become drafts (DeepSeek-V3, Kimi K3) and why they accept less than the main head

Math & data structures

  • Modified rejection sampling and its two-line exactness proof; total variation distance
  • Truncated geometric expectation (1 - alpha^(gamma+1)) / (1 - alpha); speedup with draft cost c
  • Chi-square goodness-of-fit testing on enumerable sequence distributions

Code

  • nlpcore/infer/speculative.py: verify_block, speculative_generate, bigram toys, exact sequence distributions, chi-square test
  • Break-it: three wrong acceptance rules, hardening (q(x) = 0, p == q, temperature)

Episodes

  1. Speculative Decoding: Draft and Verify18 min · 30 cues

    Leviathan 2023 / Chen 2023; acceptance rule preserving the distribution (derivation); MTP drafts.

Exercises

ExerciseTierLadderTime
Draft and verify: speculative sampling that is provably exact browserPredict · Scratch · Compose · Probe a claim60 min
Break it: three plausible acceptance rules that silently change the distribution browserBreak it · Harden · Predict50 min

Labs

  • Speculative Decoding: Draft and Verify browser F34.01 lab: speculative decoding on toy bigram LMs (synthetic) plus a real-English character probe. Exercises: F34.ex01-draft-and-verify (implement), F34.ex02-wrong-rules-break-it (break it). Everything here is exact and enumerable: the target and draft are bigram tables, so we can compute the true distribution of whole sequences and test the sampler against it. · 75 min

Library contributions

Files in nlpcore this module teaches you to write.

Sources

  1. Chen, Borgeaud, Irving, Lespiau, Sifre, Jumper. Accelerating Large Language Model Decoding with Speculative Sampling (2 Feb 2023) · arXiv:2302.01318
  2. DeepSeek-AI. DeepSeek-V3 Technical Report (Dec 2024) · arXiv:2412.19437
  3. Kimi Team. Kimi K3 (Jul 2026) · arXiv:2607.24653
  4. Leviathan, Kalman, Matias (Google Research). Fast Inference from Transformers via Speculative Decoding. ICML 2023 (arXiv Nov 2022) · arXiv:2211.17192
  5. Stern, Shazeer, Uszkoreit. Blockwise Parallel Decoding for Deep Autoregressive Models (NeurIPS 2018)