Search papers, labs, and topics across Lattice.
This paper benchmarks verification strategies for multi-path speculative decoding, finding that Traversal Verification consistently outperforms OT-based methods due to the latter's limitations in deeper tree branches where draft and target distributions diverge. To address this, they propose delayed tree expansion, which drafts a partial single path before i.i.d. branching, and a dynamic neural selector that estimates the block efficiency of OT-based verification methods. The dynamic neural selector enables OT-based methods to outperform Traversal Verification, achieving a 5% throughput increase across various models, datasets, and sampling settings.
By strategically delaying tree expansion and dynamically selecting verification methods, OT-based speculative decoding can finally surpass Traversal Verification in throughput.
Multi-path speculative decoding accelerates lossless sampling from a target model by using a cheaper draft model to generate a draft tree of tokens, and then applies a verification algorithm that accepts a subset of these. While prior work has proposed various verification algorithms for i.i.d rollouts, their relative performance under matched settings remains unclear. In this work, we firstly present a systematic evaluation of verification strategies across model families, tasks, and sampling regimes, and find that Traversal Verification dominates consistently, with OT-based methods lagging far behind. Our analysis uncovers that this occurs because OT-based methods achieve high multi-token acceptance near the root of the draft tree, while multi-token gains are most impactful deeper in the draft tree, where draft and target distributions diverge. Based on this insight, we propose delayed tree expansion, which drafts a partial single path, delaying the i.i.d. branching point. We show that delayed tree expansion preserves the target distribution and improves on root-node i.i.d rollouts. Further, we develop a dynamic neural selector that estimates the expected block efficiency of optimal-transport-based verification methods from draft and target features, enabling context-dependent expansion decisions. Our neural selector allows OT-based methods like SpecInfer to outperform Traversal Verification for the first time, achieving 5% higher average throughput across a wide range of models, datasets, and sampling settings.
