Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding
Yuxuan Zhou, Fei Huang, Heng Li, Fengyi Wu, Tianyu Wang, jianwei zhang, Junyang Lin, Zhi-Qi Cheng
Abstract
Verification is a key bottleneck in improving inference speed while maintaining distribution fidelity in Speculative Decoding. Recent work has shown that sequence-level verification leads to a higher number of accepted tokens compared to token-wise verification. However, existing solutions often rely on surrogate approximations or are constrained by partial information, struggling with joint intractability. In this work, we propose Hierarchical Speculative Decoding (HSD), a provably lossless verification method that significantly boosts the expected number of accepted tokens and overcomes joint intractability by balancing excess and deficient mass across accessible branches. Through extensive large-scale experiments, we show that HSD consistently improves acceptance rates, especially with longer draft sequences. Its strong explainability and generality further highlight the potential for integration into a wide range of speculative decoding frameworks.
BibTeX
@inproceedings{
zhou2026overcoming,
title={Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding},
author={Yuxuan Zhou and Fei Huang and Heng Li and Fengyi Wu and Tianyu Wang and jianwei zhang and Junyang Lin and Zhi-Qi Cheng},
booktitle={The Fourteenth International Conference on Learning Representations},
year={2026},
url={https://openreview.net/forum?id=LaVrNaBNwM}
}