무손실 계층적 추측 디코딩을 통한 결합 난해성 극복

Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding

추측 디코딩(Speculative Decoding)에서 분포 충실도를 유지하면서 추론 속도를 향상시키는 데 있어 검증은 핵심적인 병목 구간입니다. 최근 연구에 따르면 시퀀스 수준의 검증이 토큰 단위 검증에 비해 더 많은 수의 토큰을 승인받게 하는 것으로 나타났습니다. 그러나 기존 솔루션들은 종종 대리 근사(surrogate approximations)에 의존하거나 부분적인 정보에 국한되어 있어, 결합 난해성(joint intractability) 문제를 해결하는 데 어려움을 겪고 있습니다. 본 연구에서는 접근 가능한 분기 전반에 걸쳐 초과 및 부족 확률 질량의 균형을 맞춤으로써 결합 난해성을 극복하고 승인 토큰의 기대 개수를 크게 높이는, 증명 가능한 무손실 검증 방법인 계층적 추측 디코딩(HSD)을 제안합니다. 광범위한 대규모 실험을 통해 HSD가 다양한 모델군과 벤치마크에서 일관된 승인율 향상을 가져온다는 것을 입증했습니다. 또한, 강력한 설명 가능성과 범용성을 갖추고 있어 다양한 추측 디코딩 프레임워크에 쉽게 통합될 수 있습니다. 특히 HSD를 EAGLE-3에 통합했을 때 분포 충실도를 저해하지 않으면서도 12% 이상의 성능 향상을 달성하여 최고 수준(SOTA)의 디코딩 효율성을 확립했습니다. 코드는 https://github.com/ZhouYuxuanYX/Hierarchical-Speculative-Decoding 에서 확인할 수 있습니다.

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 probability mass across accessible branches. Our extensive large-scale experiments demonstrate that HSD yields consistent improvements in acceptance rates across diverse model families and benchmarks. Moreover, its strong explainability and generality make it readily integrable into a wide range of speculative decoding frameworks. Notably, integrating HSD into EAGLE-3 yields over a 12% performance gain, establishing state-of-the-art decoding efficiency without compromising distribution fidelity. Code is available at https://github.com/ZhouYuxuanYX/Hierarchical-Speculative-Decoding.