Research map / Large language models / Reasoning and chain of thought
Sequoia: Scalable and Robust Speculative Decoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SEQUOIA, a speculative decoding method with a dynamic-programming optimal token-tree construction and a without-replacement sampling/verification scheme that stays robust across temperatures, reporting up to 4.04x on A100 and 9.5x offloading speedups.
Problem
Existing tree-based speculative decoding methods scale poorly to large speculation budgets and their verification performs inconsistently across decoding hyperparameters such as temperature and top-p.
Approach
Formulate speculative token-tree construction as a constrained optimization solved exactly by dynamic programming under a positional acceptance assumption, and modify SpecInfer verification to sample without replacement from the draft model with a uniform fallback, yielding provable optimal-transport and cover properties.
Key results
- SEQUOIA achieves up to 4.04x speedup for Llama2-7B on A100 (on-device) and 9.5x for Llama3-70B-Instruct offloading on L40, reaching 0.60 s/token versus 5.7 s/token for DeepSpeed-Zero-Inference.
- The SEQUOIA tree generates up to 33% more tokens per decoding step than 16 independent sequences at tree size 512.
- SEQUOIA sampling/verification outperforms SpecInfer and top-k sampling by up to 1.65x and 1.27x across temperatures.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Sequoia tree instead of independent sequences (ablation) | Sequoia speculative decoding · CNN Daily Mail, Llama2-13B, temperature 0.6, tree size ≤512 | generated tokens per decoding step: up to 33% more tokens | Helped |
| Use sampling without replacement and Sequoia verification instead of SpecInfer verification (ablation) | Llama2-7B speculative decoding · CNN Daily Mail, across temperature values | speedup: up to 1.65× speedup relative to SpecInfer | Helped |
| Use sampling without replacement and Sequoia verification instead of top-k sampling (ablation) | Llama2-7B speculative decoding · CNN Daily Mail, across temperature values | speedup: up to 1.27× speedup relative to top-k sampling | Helped |
| Use Sequoia's full method instead of SpecInfer | Llama2-7B speculative decoding · A100, C4, temperature 0 | speedup: 4.04 ×(5.08) vs 3.45×(3.96) | Helped |
Surprising findings
- Top-k sampling and SpecInfer/SpecTr each perform well at opposite temperature extremes, with SpecInfer/SpecTr weak at low temperatures due to repeatedly sampling the same rejected token.
Limitations
- Optimal tree depends on the acceptance rate vector, which must be measured per draft/target pair, temperature, and data domain.
- Theoretical optimality relies on a positional acceptance assumption and a power-law acceptance rate assumption.
- Evaluation uses limited datasets and hardware configurations, with offloading results on 50 examples.
Experimental setup
Datasets: C4 OpenWebText CNN DailyMail MT Bench WikiText-103
Benchmarks: C4 OpenWebText CNN DailyMail MT Bench WikiText-103
Metrics: speedup tokens generated per decoding step rejection rate time between tokens (ms/token or s/token)
Baselines: SpecInfer SpecTr top-k sampling DeepSpeed-Zero-Inference k independent sequences
Builds on: speculative decoding SpecInfer SpecTr Medusa
Closest papers by meaning
- SPEED-Bench: A Unified and Diverse Benchmark for Speculative Decoding (ICML 2026 · similarity 0.88)
- Falcon: Faster and Parallel Inference of Large Language Models Through Enhanced Semi-Autoregressive Drafting and Custom-Designed Decoding Tree (AAAI 2025 · similarity 0.88)
- MoESD: Unveil Speculative Decoding's Potential for Accelerating Sparse MoE (NeurIPS 2025 · similarity 0.88)
- SpecExec: Massively Parallel Speculative Decoding For Interactive LLM Inference on Consumer Devices (NeurIPS 2024 · similarity 0.88)
- Scaling LLM Speculative Decoding: Non-Autoregressive Forecasting in Large-Batch Scenarios (AAAI 2026 · similarity 0.88)
- SpecForge: A Flexible and Efficient Open-Source Training Framework for Speculative Decoding (ICML 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.