DySpec: Faster Speculative Decoding with Dynamic Token Tree Structure
This work addresses the speed and scalability limitations in speculative decoding for LLM inference, offering a significant improvement over existing methods like Specinfer and Sequoia, though it is incremental in optimizing token tree structures.
The paper tackles the problem of accelerating large language model inference via speculative decoding by addressing the bottleneck of token acceptance rates, proposing DySpec with a dynamic token tree structure that improves throughput up to 9.1x and reduces latency up to 9.4x on Llama2-70B under low temperature settings.
While speculative decoding has recently appeared as a promising direction for accelerating the inference of large language models (LLMs), the speedup and scalability are strongly bounded by the token acceptance rate. Prevalent methods usually organize predicted tokens as independent chains or fixed token trees, which fails to generalize to diverse query distributions. In this paper, we propose DySpec, a faster speculative decoding algorithm with a novel dynamic token tree structure. We begin by bridging the draft distribution and acceptance rate from intuitive and empirical clues, and successfully show that the two variables are strongly correlated. Based on this, we employ a greedy strategy to dynamically expand the token tree at run time. Theoretically, we show that our method can achieve optimal results under mild assumptions. Empirically, DySpec yields a higher acceptance rate and speedup than fixed trees. DySpec can drastically improve the throughput and reduce the latency of token generation across various data distribution and model sizes, which significantly outperforms strong competitors, including Specinfer and Sequoia. Under low temperature setting, DySpec can improve the throughput up to 9.1$\times$ and reduce the latency up to 9.4$\times$ on Llama2-70B. Under high temperature setting, DySpec can also improve the throughput up to 6.21$\times$, despite the increasing difficulty of speculating more than one token per step for draft model.