---
title: "OPT-Tree — paper by Wang et al. (2025) — summary and ideas"
description: "The authors argue that for a fixed node budget, the best tree shape depends on the input at every step. 16 references, cited by 21 papers here."
authors: ["Jikai Wang", "Yi Su", "Juntao Li", "Qingrong Xia", "Zi Ye", "Xinyu Duan", "Zhefeng Wang", "Min Zhang"]
year: 2025
venue: "Transactions of the Association for Computational Linguistics"
source: "https://aclanthology.org/2025.tacl-1.8/"
doi: "10.1162/tacl_a_00735"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/wang-2025-opt-tree-speculative-decoding-adaptive/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/wang-2025-opt-tree-speculative-decoding-adaptive/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2025](https://md.research.elamur.ai/free/en/papers/2025/page/3/) / OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure

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

**Authors:** [Jikai Wang](https://md.research.elamur.ai/free/en/authors/jikai-wang/), [Yi Su](https://md.research.elamur.ai/free/en/authors/yi-su/), [Juntao Li](https://md.research.elamur.ai/free/en/authors/juntao-li/), [Qingrong Xia](https://md.research.elamur.ai/free/en/authors/qingrong-xia/), Zi Ye, [Xinyu Duan](https://md.research.elamur.ai/free/en/authors/xinyu-duan/), [Zhefeng Wang](https://md.research.elamur.ai/free/en/authors/zhefeng-wang/) and [Min Zhang](https://md.research.elamur.ai/free/en/authors/min-zhang/) · **Year:** 2025 · **Venue:** [Transactions of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/tacl/) ([Transactions of the Association for Computational Linguistics (TACL) 2025](https://md.research.elamur.ai/free/en/venues/tacl/2025/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2025.tacl-1.8/) · [PDF](https://aclanthology.org/2025.tacl-1.8.pdf) · [DOI 10.1162/tacl\_a\_00735](https://doi.org/10.1162/tacl_a_00735) · [OpenAlex](https://openalex.org/W4408105642)

**Citations:** 11 citations (OpenAlex, 2026-10-14) · [21](https://md.research.elamur.ai/free/en/papers/wang-2025-opt-tree-speculative-decoding-adaptive/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Speculative decoding speeds up LLM inference without changing outputs: a cheap draft model proposes several tokens, and the large target model checks them all in one parallel pass. Most earlier systems arrange the proposals as a single sequence, which wastes compute on repeated prefixes, or as a hand-designed tree whose shape never changes. The authors argue that for a fixed node budget, the best tree shape depends on the input at every step. Their algorithm, OPT-Tree, rebuilds the draft tree at each decoding step. It treats draft-model probabilities as acceptance probabilities and maximizes an estimate of the expected acceptance length, computed as the sum of the prefix probabilities of all nodes. They prove that keeping the n nodes with the highest prefix probability yields the optimal subtree for a given depth. Drafting stops once the expected gain falls below a threshold δ. OPT-Tree works with any autoregressive draft model. Across ten target/draft model pairs and two datasets, it beat existing draft structures and was up to 3.2× faster than ordinary autoregressive decoding.

## Key points
- The estimate of expected acceptance length tracks the real acceptance length well. Tree construction is greedy, and the stopping threshold δ is set between μ (draft-step time divided by decode-step time) and 1.
- On an RTX 4090 with a 7B model, verifying 10 tokens costs about the same wall time as verifying 200. This is why a node budget is a reasonable design constraint.
- With LLaMA-2-7B drafting for LLaMA-2-70B and a budget above 500 nodes, the target model accepts about 10 tokens per decoding step.
- Case study (50 nodes, δ = 0.7, temperature 0): mean acceptance length was 9.34 at 12.07 tokens per second. Function words, punctuation, and sentence openings were the tokens most often rejected.
- Code is released at github.com/Jikai0Wang/OPT-Tree.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Huawei Technologies](https://md.research.elamur.ai/free/en/companies/huawei-technologies/) — Company, Shenzhen, China · 75 works · 12,975 citations
- [Soochow University](https://md.research.elamur.ai/free/en/universities/soochow-university/) — University, Suzhou, China · 63 works · 4,507 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works

🧭 Topics (1): [🪶 Efficient models & compression](https://md.research.elamur.ai/free/en/topics/efficient-models/) · 242 works

## Cite

Cite as: Jikai Wang, Yi Su, Juntao Li, Qingrong Xia, Zi Ye, Xinyu Duan, Zhefeng Wang and Min Zhang. 2025. OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@article{wang2025opt,
  title = {{OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure}},
  author = {Jikai Wang, Yi Su, Juntao Li, Qingrong Xia, Zi Ye, Xinyu Duan, Zhefeng Wang and Min Zhang},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2025},
  doi = {10.1162/tacl\_a\_00735},
  url = {https://doi.org/10.1162/tacl_a_00735}
}
```

- [← previous Evaluating Language Models as Synthetic Data Generators](https://md.research.elamur.ai/free/en/papers/kim-2025-evaluating-language-models-as-synthetic/)
- [next → QIAS 2025: Overview of the Shared Task on Islamic Inheritance Reasoning and Knowledge Assessment](https://md.research.elamur.ai/free/en/papers/bouchekif-2025-qias-2025-overview-shared-task/)
- [↑ back to papers of 2025](https://md.research.elamur.ai/free/en/papers/2025/page/3/)

## References

16 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Sidney Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, Michael Pieler, Usvsn Sai Prashanth, Shivanshu Purohit, Laria Reynolds, Jonathan Tow, Ben Wang, and Samuel Weinbach. 2022. [GPT-NeoX-20B: An open-source autor…](https://md.research.elamur.ai/free/en/papers/black-2022-gpt-neox-20b-open-source/)
2. Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock… [find](https://scholar.google.com/scholar?q=Albert+Q%2E+Jiang%2C+Alexandre+Sablayrolles%2C+Antoine+Roux%2C+Arthur+Mensch%2C+Blanche+Savary%2C+Chris+Bamford%2C+Devendra+Singh+Chaplot%2C+Diego+de+las+Casas%2C+Emma+Bou+Hanna%2C+Florian+Bressand%2C+Gianna+Lengyel%2C+Guill)
3. Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jerem… — [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://md.research.elamur.ai/free/en/papers/touvron-2023-llama-2-open-foundation-fine/)
4. Yaniv Leviathan, Matan Kalman, and Yossi Matias. 2023. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pages 19274–19286. PMLR. [find](https://scholar.google.com/scholar?q=Yaniv+Leviathan%2C+Matan+Kalman%2C+and+Yossi+Matias%2E+2023%2E+Fast+inference+from+transformers+via+speculative+decoding%2E+In+International+Conference+on+Machine+Learning%2C+pages+19274%E2%80%9319286%2E+PMLR%2E)
5. Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2024. [EAGLE: Speculative sampling requires rethinking feature uncertainty](https://md.research.elamur.ai/free/en/papers/li-2024-eagle-speculative-sampling-requires-rethinking/). arXiv preprint arXiv:2401.15077v2.
6. Heming Xia, Tao Ge, Peiyi Wang, Si-Qing Chen, Furu Wei, and Zhifang Sui. 2023. [Speculative decoding: Exploiting speculative execution for accelerating seq2seq generation](https://md.research.elamur.ai/free/en/papers/xia-2023-speculative-decoding-exploiting-speculative-execution/). In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 3909–3925. https://doi.org/10.18653/v1/2023 .find… [↗](https://doi.org/10.18653/v1/2023)
7. Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. 2023. Efficiently scaling transformer inference. Proceedings of Machine Learning and Systems, 5. [find](https://scholar.google.com/scholar?q=Reiner+Pope%2C+Sholto+Douglas%2C+Aakanksha+Chowdhery%2C+Jacob+Devlin%2C+James+Bradbury%2C+Jonathan+Heek%2C+Kefan+Xiao%2C+Shivani+Agrawal%2C+and+Jeff+Dean%2E+2023%2E+Efficiently+scaling+transformer+inference%2E+Proceedings+)
8. Heming Xia, Zhe Yang, Qingxiu Dong, Peiyi Wang, Yongqi Li, Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui. 2024. [Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding](https://md.research.elamur.ai/free/en/papers/xia-2024-unlocking-efficiency-large-language-model/). arXiv preprint arXiv:2401.07851v3.
9. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020. [Exploring the limits of transfer learning with a unified text-to-text transformer](https://md.research.elamur.ai/free/en/papers/raffel-2019-exploring-limits-transfer-learning-unified/). Journal of Machine Learning Research, 21(140):1–67.
10. Seongjun Yang, Gibbeum Lee, Jaewoong Cho, Dimitris Papailiopoulos, and Kangwook Lee. 2023. Predictive pipelined decoding: A compute-latency trade-off for exact LLM decoding. arXiv preprint arXiv:2307.05908v2. — [arXiv:2307.05908](https://arxiv.org/abs/2307.05908) [find](https://scholar.google.com/scholar?q=Seongjun+Yang%2C+Gibbeum+Lee%2C+Jaewoong+Cho%2C+Dimitris+Papailiopoulos%2C+and+Kangwook+Lee%2E+2023%2E+Predictive+pipelined+decoding%3A+A+compute%2Dlatency+trade%2Doff+for+exact+LLM+decoding%2E+arXiv+preprint+arXiv%3A2307%2E)
11. Benjamin Spector and Chris Re. 2023. Accelerating LLM inference with staged speculative decoding. arXiv preprint arXiv:2308.04623v1. — [arXiv:2308.04623](https://arxiv.org/abs/2308.04623) [find](https://scholar.google.com/scholar?q=Benjamin+Spector+and+Chris+Re%2E+2023%2E+Accelerating+LLM+inference+with+staged+speculative+decoding%2E+arXiv+preprint+arXiv%3A2308%2E04623v1%2E+%E2%80%94+%5BarXiv%3A2308%2E04623%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2308%2E04623%29)
12. Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. 2018. Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems, 31. [find](https://scholar.google.com/scholar?q=Mitchell+Stern%2C+Noam+Shazeer%2C+and+Jakob+Uszkoreit%2E+2018%2E+Blockwise+parallel+decoding+for+deep+autoregressive+models%2E+Advances+in+Neural+Information+Processing+Systems%2C+31%2E)
13. Jun Zhang, Jue Wang, Huan Li, Lidan Shou, Ke Chen, Gang Chen, and Sharad Mehrotra. 2023. [Draft & verify: Lossless large language model acceleration via self-speculative decoding](https://md.research.elamur.ai/free/en/papers/zhang-2024-draft-verify-lossless-large-language/). arXiv preprint arXiv:2309.08168v2.
14. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller,… — [OPT: Open Pre-trained Transformer Language Models](https://md.research.elamur.ai/free/en/papers/zhang-2022-opt-open-pre-trained-transformer/)
15. Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. 2024. [Judging LLM-as-a-judge with MT-Bench and Chatbot Arena](https://md.research.elamur.ai/free/en/papers/zheng-2023-judging-llm-judge-mt-bench/). Advances in Neural Information Processing Systems, 36.
16. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao A The Relationship between the Output Probability of the Draft Model and the Probability of Acceptance *Figure 11: Acceptance frequency with different range of draft model output probability.* We counted the frequency of… [find](https://scholar.google.com/scholar?q=Lianmin+Zheng%2C+Wei%2DLin+Chiang%2C+Ying+Sheng%2C+Siyuan+Zhuang%2C+Zhanghao+Wu%2C+Yonghao+A+The+Relationship+between+the+Output+Probability+of+the+Draft+Model+and+the+Probability+of+Acceptance+%2AFigure+11%3A+Accept)

*Updated 30 October 2026*