# OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure

arXiv: https://arxiv.org/abs/2406.17276 · HTML: https://mlsanity.com/paper/2406.17276/

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 23 of its 25 references that are in the map.
- First posted on arXiv 25 Jun 2024.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 23 of 23)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [GPT-NeoX-20B: An Open-Source Autoregressive Language Model](https://mlsanity.com/paper/2204.06745/) (2022)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding](https://mlsanity.com/paper/2401.07851/) (2024)
- [Speculative Decoding: Exploiting Speculative Execution for Accelerating Seq2seq Generation](https://mlsanity.com/paper/2203.16487/) (2022)
- [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023)
- [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023)
- [Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding](https://mlsanity.com/paper/2402.12374/) (2024)
- [Cascade Speculative Drafting for Even Faster LLM Inference](https://mlsanity.com/paper/2312.11462/) (2023)
- [Predictive Pipelined Decoding: A Compute-Latency Trade-off for Exact LLM Decoding](https://mlsanity.com/paper/2307.05908/) (2023)
- [Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement](https://mlsanity.com/paper/2402.14160/) (2024)

## Built on by (most cited first, 30 of 67)

- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Accelerating Speculative Decoding with Block Diffusion Draft Trees](https://mlsanity.com/paper/2604.12989/) (2026)
- [Seer: Online Context Learning for Fast Synchronous LLM Reinforcement Learning](https://mlsanity.com/paper/2511.14617/) (2025)
- [Speculative Decoding and Beyond: An In-Depth Survey of Techniques](https://mlsanity.com/paper/2502.19732/) (2025)
- [ParallelSpec: Parallel Drafter for Efficient Speculative Decoding](https://mlsanity.com/paper/2410.05589/) (2024)
- [FR-Spec: Accelerating Large-Vocabulary Language Models via Frequency-Ranked Speculative Sampling](https://mlsanity.com/paper/2502.14856/) (2025)
- [QSpec: Speculative Decoding with Complementary Quantization Schemes](https://mlsanity.com/paper/2410.11305/) (2024)
- [AdaEAGLE: Optimizing Speculative Decoding via Explicit Modeling of Adaptive Draft Structures](https://mlsanity.com/paper/2412.18910/) (2024)
- [D-PACE: Dynamic Position-Aware Cross-Entropy for Parallel Speculative Drafting](https://mlsanity.com/paper/2605.18810/) (2026)
- [Taming the Titans: A Survey of Efficient LLM Inference Serving](https://mlsanity.com/paper/2504.19720/) (2025)
- [TETRIS: Optimal Draft Token Selection for Batch Speculative Decoding](https://mlsanity.com/paper/2502.15197/) (2025)
- [LogitSpec: Accelerating Retrieval-based Speculative Decoding via Next Next Token Speculation](https://mlsanity.com/paper/2507.01449/) (2025)
- [TALON: Confidence-Aware Speculative Decoding with Adaptive Token Trees](https://mlsanity.com/paper/2601.07353/) (2026)
- [ECHO: Elastic Speculative Decoding with Sparse Gating for High-Concurrency Scenarios](https://mlsanity.com/paper/2604.09603/) (2026)
- [Alignment-Augmented Speculative Decoding with Alignment Sampling and Conditional Verification](https://mlsanity.com/paper/2505.13204/) (2025)
- [C2T: A Classifier-Based Tree Construction Method in Speculative Decoding](https://mlsanity.com/paper/2502.13652/) (2025)
- [CORAL: Learning Consistent Representations across Multi-step Training with Lighter Speculative Drafter](https://mlsanity.com/paper/2502.16880/) (2025)
- [Traversal Verification for Speculative Tree Decoding](https://mlsanity.com/paper/2505.12398/) (2025)
- [Spec-LLaVA: Accelerating Vision-Language Models with Dynamic Tree-Based Speculative Decoding](https://mlsanity.com/paper/2509.11961/) (2025)
- [Faster Language Models with Better Multi-Token Prediction Using Tensor Decomposition](https://mlsanity.com/paper/2410.17765/) (2024)
- [Closer Look at Efficient Inference Methods: A Survey of Speculative Decoding](https://mlsanity.com/paper/2411.13157/) (2024)
- [Nightjar: Dynamic Adaptive Speculative Decoding for Large Language Models Serving](https://mlsanity.com/paper/2512.22420/) (2025)
- [Cost-Aware Diffusion Draft Trees for Speculative Decoding](https://mlsanity.com/paper/2606.01813/) (2026)
- [MASSV: Multimodal Adaptation and Self-Data Distillation for Speculative Decoding of Vision-Language Models](https://mlsanity.com/paper/2505.10526/) (2025)
- [SpecExtend: A Drop-in Enhancement for Speculative Decoding of Long Sequences](https://mlsanity.com/paper/2505.20776/) (2025)
- [SpecMamba: Accelerating Mamba Inference on FPGA with Speculative Decoding](https://mlsanity.com/paper/2509.19873/) (2025)
- [D-cut: Adaptive Verification Depth Pruning for Batched Speculative Decoding](https://mlsanity.com/paper/2607.14647/) (2026)
- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (2025)
- [Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding](https://mlsanity.com/paper/2512.23858/) (2025)
- [Sparrow: Text-Anchored Window Attention with Visual-Semantic Glimpsing for Speculative Decoding in Video LLMs](https://mlsanity.com/paper/2602.15318/) (2026)

## Abstract (arXiv)

Autoregressive language models demonstrate excellent performance in various scenarios. However, the inference efficiency is limited by its one-step-one-word generation mode, which has become a pressing problem recently as the models become increasingly larger. Speculative decoding employs a "draft and then verify" mechanism to allow multiple tokens to be generated in one step, realizing lossless acceleration. Existing methods mainly adopt fixed heuristic draft structures, which fail to adapt to different situations to maximize the acceptance length during verification. To alleviate this dilemma, we proposed OPT-Tree, an algorithm to construct adaptive and scalable draft trees. It searches the optimal tree structure that maximizes the mathematical expectation of the acceptance length in each decoding step. Experimental results reveal that OPT-Tree outperforms the existing draft structures and achieves a speed-up ratio of up to 3.2 compared with autoregressive decoding. If the draft model is powerful enough and the node budget is sufficient, it can generate more than ten tokens in a single step. Our code is available at https://github.com/Jikai0Wang/OPT-Tree.