Autoregressive language models demonstrate excellent performance in various
scenarios. However, the inference efficiency is limited by its
one-step-one-word generation mode, which has become a pressing problem recently
as the models become increasingly larger. Speculative decoding employs a "draft
and then verify" mechanism to allow multiple tokens to be generated in one
step, realizing lossless acceleration. Existing methods mainly adopt fixed
heuristic draft structures, which fail to adapt to different situations to
maximize the acceptance length during verification. To alleviate this dilemma,
we proposed OPT-Tree, an algorithm to construct adaptive and scalable draft
trees. It searches the optimal tree structure that maximizes the mathematical
expectation of the acceptance length in each decoding step. Experimental
results reveal that OPT-Tree outperforms the existing draft structures and
achieves 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 can
generate more than ten tokens in a single step. Our code is available at
this https URL

OPT-Tree 算法通过构建自适应和可扩展的缓冲树结构，实现了一步生成多个标记，从而解决了自回归语言模型中推理效率受限的问题。该算法优于现有的缓冲结构，与自回归解码相比，实现了最高 3.2 倍的加速比。