Elamur Research⌕
☰
home / papers / 2026 / Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks

Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks

Paper · 2026 · Sergey Pankratov and Dan Alistarh

Summary

Speculative decoding speeds up LLM inference. A cheap drafter proposes a sequence or tree of tokens, and the target model checks up to P of them in one parallel pass. It has been unclear how much speedup this approach can deliver in principle. Pankratov and Alistarh derive what they call the first tight limit for any deterministic speculative algorithm. Their analysis uses a simplified timing model: the verifier has constant latency, drafting is free, and acceptance probabilities are i.i.d. across prefixes. Under these conditions, they show the best drafter greedily selects the P most likely token paths. They then treat the tree of token log-probabilities as a Branching Random Walk and apply tools such as the Many-to-One Lemma. The result is that expected accepted tokens per iteration grow only logarithmically in P and decrease roughly with the inverse of the target model's expected entropy µ. Experiments with EAGLE-3 on Llama models follow the trends the bound predicts. However, real systems reach only about half the theoretical ceiling, which points to room for better drafters.

Key points

  • Main bound (Theorems 1–2): E[X] ≤ (µ + µ^(2))·log(P)/µ² + O(1).
    • µ is the expected entropy of the verifier's output distribution.
    • µ^(2) is the expected second log-moment.
    • P is the verifier's parallel token capacity.
  • Optimal strategy (Lemma 1): For deterministic drafting with perfect knowledge, the optimal draft tree takes the P most probable sequences.
  • Diminishing returns: Growing P exponentially yields only a linear gain in speedup. Higher variance in log-probabilities, captured by µ^(2), lowers the ceiling further.
  • Experiments: EAGLE-3 speedups on LLaMA 3.1 8B Instruct were measured across 6 benchmarks, including Natural Questions. They were compared with the exact bound, the P → ∞ limit, and an imperfect-knowledge drafter bound (Theorem 5, Appendix C). The roughly ×2 gap to the theoretical bound is attributed mainly to speculation error.
  • Limitations:
    • The i.i.d. assumption ignores context dependence in language; the authors name extension to stationary or ergodic processes as future work.
    • The timing model is idealized.
    • Stochastic drafting strategies are not covered.

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

🎓Institute of Science and Technology AustriaKlosterneuburg · Austria4 works · 346 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

Cite

Cite as Sergey Pankratov and Dan Alistarh. 2026. Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks. Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.eacl-long.301

@inproceedings{pankratov2026speculative,
  title = {{Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks}},
  author = {Sergey Pankratov and Dan Alistarh},
  booktitle = {Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.eacl-long.301},
  url = {https://doi.org/10.18653/v1/2026.eacl-long.301}
}

References

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

  1. John D Biggins. 1977. Martingale convergence in the branching random walk. Journal of Applied Probability, 14(1):25–37. find
  2. 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 International Conference on Machine Learning. PMLR.
  3. Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. 2023. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318. symposium on operating systems principles, pages 611–626. find
  4. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, and 39 others. 202… — Evaluating Large Language Models Trained on Code
  5. 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
  6. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168.
  7. DeepSeek-AI. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. Preprint, arXiv:2501.12948.
  8. 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…
  9. Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang. 2024. Break the sequential dependency of llm inference using lookahead decoding. In International Conference on Machine Learning.
  10. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, and 542 o… — The Llama 3 Herd of Models
  11. Geoffrey Grimmett and David Stirzaker. 2020. Probability and random processes. Oxford university press. find
  12. Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019. Natural…
  13. 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 Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2024a.…
  14. Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2024b. EAGLE: Speculative sampling requires rethinking feature uncertainty. In International Conference on Machine Learning.
  15. Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2025. EAGLE-3: Scaling up inference acceleration of large language models via training-time test. In Annual Conference on Neural Information Processing Systems. find
  16. Tianyu Liu, Yun Li, Qitan Lv, Kai Liu, Jianchen Zhu, and Winston Hu. 2025. PEARL: parallel speculative decoding with adaptive draft length. In International Conference on Learning Representations. OpenReview. find
  17. Gary Lorden. 1970. On excess over the boundary. The Annals of Mathematical Statistics, 41(2):520–527. find
  18. Russell Lyons and Yuval Peres. 2017. Probability on Trees and Networks, volume 42. Cambridge University Press. find
  19. Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Rae Ying Yee Wong, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia. 2023. Specinfer: Accelerating generative LLM serving with speculative inference and token tree verification. arXiv preprint arXiv:2305.09781. find
  20. Ramesh Nallapati, Bowen Zhou, Cicero Nogueira dos santos, Caglar Gulcehre, and Bing Xiang. 2016. Abstractive text summarization using sequence-to-sequence rnns and beyond. arXiv preprint arXiv:1602.06023.
  21. Noam Shazeer. 2019. Fast transformer decoding: One write-head is all you need. arXiv preprint arXiv:1911.02150. find
  22. Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang, Christopher Ré, Ion Stoica, and Ce Zhang. 2023. Flexgen: High-throughput generative inference of large language models with a single GPU. In International Conference on Machine Learning, pages 31094–31116. PM…
  23. Zhan Shi. 2015. Branching Random Walks, volume 2151 of Lecture Notes in Mathematics. Springer. find
  24. Benjamin Spector and Chris Re. 2023. Accelerating LLM inference with staged speculative decoding. arXiv preprint arXiv:2308.04623. — [arXiv:2308.04623](https://arxiv.org/abs/2308.04623) find
  25. Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. 2018. Blockwise parallel decoding for deep autoregressive models. In Advances in Neural Information Processing Systems. find
  26. Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. 2023. Spectr: Fast speculative decoding via optimal transport. In Advances in Neural Information Processing Systems. find
  27. Qwen Team. 2025. Qwen3 technical report. Preprint, arXiv:2505.09388.
  28. Ming Yin, Minshuo Chen, Kaixuan Huang, and Mengdi Wang. 2024. A theoretical perspective for speculative decoding algorithm. In Advances in Neural Information Processing Systems, pages 128082–128117. find
  29. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph E Gonzalez, and Ion Stoica. 2023. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in neural information processing systems, 36:46595–46…
  30. Lorden’s inequality (Lorden, 1970) gives ‹ ≥ (x)] ≤ E[ N x E[X 1 2 ] + . E[X 1 ] (E[X 1 ]) 2 find
  31. Combining the two bounds completes the proof. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/pankratov-2026-speculative-decoding-speed-light-optimal/