Abstract
Autoregressive language models demonstrate excellent performance in variousscenarios. However, the inference efficiency is limited by itsone-step-one-word generation mode, which has become a pressing problem recentlyas the models become increasingly larger. Speculative decoding employs a "draftand then verify" mechanism to allow multiple tokens to be generated in onestep, realizing lossless acceleration. Existing methods mainly adopt fixedheuristic draft structures, which fail to adapt to different situations tomaximize the acceptance length during verification. To alleviate this dilemma,we proposed OPT-Tree, an algorithm to construct adaptive and scalable drafttrees. It searches the optimal tree structure that maximizes the mathematicalexpectation of the acceptance length in each decoding step. Experimentalresults reveal that OPT-Tree outperforms the existing draft structures andachieves a speed-up ratio of up to 3.2 compared with autoregressive decoding.If the draft model is powerful enough and the node budget is sufficient, it cangenerate more than ten tokens in a single step. Our code is available athttps://github.com/Jikai0Wang/OPT-Tree.