Elamur Research⌕
☰
home / papers / 2025 / SEED: Accelerating Reasoning Tree Construction via Scheduled Speculative Decoding

SEED: Accelerating Reasoning Tree Construction via Scheduled Speculative Decoding

Paper · 2025 · Zhenglin Wang, Jialong Wu, Yilong Lai et al.

Summary

Tree-search-based (TSB) reasoning methods such as Tree-of-Thoughts (ToT) help LLMs plan and reason. However, they are slow because many thoughts must be generated and scored before the tree can grow. Earlier work sped up the search algorithms. This paper targets tree construction itself with SEED, a training-free inference framework.

SEED combines speculative decoding with parallel drafting. Several small draft models propose tokens at the same time, and one large target model verifies them. Since only one target model is available, a Rounds-Scheduled strategy borrowed from operating-system process scheduling decides which draft gets verified next. It uses a First-Come-First-Serve queue, so verifications never conflict. The State Evaluator uses this scheme, as does the Thought Generator.

On GSM8K, Creative Writing and Blocksworld, SEED runs 1.1–1.5× faster than baselines. Outputs stay lossless, with the same distribution as the target model. The approach matters for users with consumer GPUs, where fully parallel decoding would exhaust memory. It also suggests a practical route to batched speculative decoding.

Key points

  • Evaluated on three reasoning and planning datasets: GSM8K, Creative Writing and Blocksworld. The tree is built with BFS, following the ToT setup.
  • SEED reaches 1.1–1.5× speedups and generates up to about 20 extra tokens per second. Verification follows Leviathan et al. (2023), so output quality is unchanged under greedy and non-greedy sampling.
  • The Thought Generator gains more than the State Evaluator in both acceptance rate α and speedup. The authors suggest draft and target models agree more when proposing thoughts than when making evaluative decisions.
  • Compared with standard SD, GPU utilization is steadier because the target model is idle less often. Speedup grows with the number of thoughts n but saturates around n=6, where draft models start queuing for verification.
  • Small draft models (68M/160M) keep the extra KV-Cache cost low; KV-Cache management is left unoptimized. Code is available at github.com/Linking-ai/SEED.

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

🎓Southeast UniversityNanjing · China28 works · 354 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Zhenglin Wang, Jialong Wu, Yilong Lai, Congzhi Zhang and Deyu Zhou. 2025. SEED: Accelerating Reasoning Tree Construction via Scheduled Speculative Decoding. Proceedings of the 31st International Conference on Computational Linguistics.

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

@inproceedings{wang2025seed,
  title = {{SEED: Accelerating Reasoning Tree Construction via Scheduled Speculative Decoding}},
  author = {Zhenglin Wang, Jialong Wu, Yilong Lai, Congzhi Zhang and Deyu Zhou},
  booktitle = {Proceedings of the 31st International Conference on Computational Linguistics},
  year = {2025},
  url = {https://aclanthology.org/2025.coling-main.328/}
}

References

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

  1. Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774.
  2. Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. 2023. Qwen technical report. arXiv e-prints, pages arXiv–2309.
  3. Nikhil Bhendawade, Irina Belousova, Qichen Fu, Henry Mason, Mohammad Rastegari, and Mahyar Najibi. 2024. Speculative streaming: Fast llm inference without auxiliary models. arXiv e-prints, pages arXiv– 2402. find
  4. Ondřej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Aleš Tamchyna. 2014. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the…
  5. Alan Bundy and Lincoln Wallen. 1984. Breadth-first search. Catalogue of artificial intelligence tools, pages 13–13. find
  6. Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D. Lee, Deming Chen, and Tri Dao. 2024. Medusa: Simple LLM inference acceleration framework with multiple decoding heads. In Forty-first International Conference on Machine Learning.
  7. Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. 2023a. Accelerating large language model decoding with speculative sampling. arXiv e-prints, pages arXiv–2302. find
  8. Ziyi Chen, Xiaocong Yang, Jiacheng Lin, Chenkai Sun, Jie Huang, and Kevin Chen-Chuan Chang. 2023b. Cascade speculative drafting for even faster llm inference. arXiv preprint arXiv:2312.11462. — [arXiv:2312.11462](https://arxiv.org/abs/2312.11462) find
  9. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168.
  10. Tri Dao. 2024. Flashattention-2: Faster attention with better parallelism and work partitioning. In The Twelfth International Conference on Learning Representations.
  11. Luciano Del Corro, Allison Del Giorno, Sahaj Agarwal, Bin Yu, Ahmed Hassan Awadallah, and Subhabrata Mukherjee. 2023. Skipdecode: Autoregressive skip decoding with batching and caching for efficient llm inference. find
  12. Mostafa Elhoushi, Akshat Shrivastava, Diana Liskovich, Basil Hosmer, Bram Wasti, Liangzhen Lai, Anas Mahmoud, Bilge Acun, Saurabh Agarwal, Ahmed Roman, Ahmed Aly, Beidi Chen, and Carole-Jean Wu. 2024. LayerSkip: Enabling early exit inference and self-speculative decoding. In Proceedings of the 62nd…
  13. Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. 2019. Mask-predict: Parallel decoding of conditional masked language models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Pro…
  14. Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. 2023. Leveraging pre-trained large language models to construct and utilize world models for model-based task planning. Advances in Neural Information Processing Systems, 36:79081–79094. find
  15. Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu. 2023. Reasoning with language model is planning with world model. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 8154–8173. find
  16. Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100–107. find
  17. Zhenyu He, Zexuan Zhong, Tianle Cai, Jason D Lee, and Di He. 2023. Rest: Retrieval-based speculative decoding. arXiv e-prints, pages arXiv–2311. find
  18. Wenyang Hui, Yan Wang, Kewei Tu, and Chengyue Jiang. 2024. Rot: Enhancing large language models with reflection on search trees. arXiv preprint arXiv:2404.05449. — [arXiv:2404.05449](https://arxiv.org/abs/2404.05449) find
  19. Levente Kocsis and Csaba Szepesvári. 2006. Bandit based monte-carlo planning. In European conference on machine learning, pages 282–293. Springer. find
  20. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199– 22213.
  21. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 611–626.
  22. 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
  23. Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2024. EAGLE: Speculative sampling requires rethinking feature uncertainty. In Forty-first International Conference on Machine Learning.
  24. Haoran Liao, Jidong Tian, Shaohua Hu, Hao He, and Yaohui Jin. 2024. Look before you leap: Problem elaboration prompting improves mathematical reasoning in large language models. arXiv e-prints, pages arXiv–2402. find
  25. Xiaoxuan Liu, Lanxiang Hu, Peter Bailis, Ion Stoica, Zhijie Deng, Alvin Cheung, and Hao Zhang. 2023. Online speculative decoding. find
  26. Bo-Ru Lu, Nikita Haduong, Chien-Yu Lin, Hao Cheng, Noah A Smith, and Mari Ostendorf. 2024a. Encode once and decode in parallel: Efficient transformer decoding. arXiv e-prints, pages arXiv–2403. find
  27. Jinghui Lu, Ziwei Yang, Yanjie Wang, Xuejing Liu, and Can Huang. 2024b. Padellm-ner: Parallel decoding in large language models for named entity recognition. arXiv e-prints, pages arXiv–2402. find
  28. Yunsheng Ni, Chuanjian Liu, Yehui Tang, Kai Han, and Yunhe Wang. 2024. Ems-sd: Efficient multi-sample speculative decoding for accelerating large language models. arXiv e-prints, pages arXiv–2405. find
  29. OpenAI. 2022. Introducing ChatGPT. find
  30. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730–27744.
  31. Andysah Putera Utama Siahaan. 2016. Comparison analysis of cpu scheduling: Fcfs, sjf and round robin. International Journal of Engineering Development and Research, 4(3):124–132. find
  32. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. 2024. Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314.
  33. Hanshi Sun, Zhuoming Chen, Xinyu Yang, Yuandong Tian, and Beidi Chen. 2024a. Triforce: Lossless acceleration of long sequence generation with hierarchical speculative decoding. In First Conference on Language Modeling. find
  34. Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. 2024b. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems, 36. find
  35. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023a. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971.
  36. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023b. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288.
  37. Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. 2023. On the planning abilities of large language models-a critical investigation. Advances in Neural Information Processing Systems, 36:75993–76005. find
  38. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations.
  39. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837.
  40. Siwei Wu, Zhongyuan Peng, Xinrun Du, Tuney Zheng, Minghao Liu, Jialong Wu, Jiachen Ma, Yizhi Li, Jian Yang, Wangchunshu Zhou, et al. 2024. A comparative study on reasoning patterns of openai’s o1 model. arXiv preprint arXiv:2410.13639. — [arXiv:2410.13639](https://arxiv.org/abs/2410.13639) find
  41. 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. In Findings of the Association for Computational Linguistics ACL 2024, pages 7655–7…
  42. Yuxi Xie, Anirudh Goyal, Wenyue Zheng, Min-Yen Kan, Timothy P Lillicrap, Kenji Kawaguchi, and Michael Shieh. 2024. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint arXiv:2405.00451. find
  43. Hanqi Yan, Qinglin Zhu, Xinyu Wang, Lin Gui, and Yulan He. 2024. Mirror: A multiple-perspective self-reflection method for knowledge-rich reasoning. arXiv preprint arXiv:2402.14963. — [arXiv:2402.14963](https://arxiv.org/abs/2402.14963) find
  44. Sen Yang, Shujian Huang, Xinyu Dai, and Jiajun Chen. 2024. Multi-candidate speculative decoding. arXiv e-prints, pages arXiv–2401. find
  45. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2024. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36. find
  46. Di Zhang, Jianbo Wu, Jingdi Lei, Tong Che, Jiatong Li, Tong Xie, Xiaoshui Huang, Shufei Zhang, Marco Pavone, Yuqiang Li, et al. 2024a. Llama-berry: Pairwise optimization for o1-like olympiad-level mathematical reasoning. arXiv preprint arXiv:2410.02884. find
  47. Linhai Zhang, Jialong Wu, Deyu Zhou, and Guoqiang Xu. 2024b. STAR: Constraint LoRA with dynamic active learning for data-efficient fine-tuning of large language models. In Findings of the Association for Computational Linguistics ACL 2024, pages 3519– 3532, Bangkok, Thailand and virtual meeting. Ass… find
  48. Xuan Zhang, Chao Du, Tianyu Pang, Qian Liu, Wei Gao, and Min Lin. 2024c. Chain of preference optimization: Improving chain-of-thought reasoning in LLMs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. find
  49. Wei Zhao and John A Stankovic. 1989. Performance analysis of fcfs and improved fcfs scheduling algorithms for dynamic real-time computer systems. In 1989 Real-Time Systems Symposium, pages 156–157. IEEE Computer Society. find
  50. Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Rostamizadeh, Sanjiv Kumar, Jean-François Kagy, and Rishabh Agarwal. 2023. Distillspec: Improving speculative decoding via knowledge distillation. In The Twelfth International Conference on Learning Representations. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wang-2025-seed-accelerating-reasoning-tree-construction/