UBTree speeds up language model decoding with new parallel token drafting

UBTree: Parallel Tree Drafting via Unigram and Bigram Models for Speculative Decoding

Computation and Language

Summary

Language models write text one word at a time, which can be slow. The paper presents UBTree, a method that guesses many possible next words in parallel using two models—a unigram model to suggest candidates for each position, and a bigram model to pick pairs of words that fit together better. This approach creates a tree of possible word drafts that can be quickly checked and accepted, making the process faster. The authors tested UBTree on standard benchmarks and found it speeds up decoding more than previous methods without losing accuracy.

What this means in practice

Authors

Chumeng Liang, Linxuan Wang, Xinyu Peng, Huabin Liu, Yuxin Chen, Ge Liu, Guang Lin, Qifan Song, Jianguo Li

Abstract

Speculative decoding accelerates language model inference by verifying multiple draft tokens in a single target-model pass. Recent parallel drafters have achieved breakthrough performance in frontier production models, but their effectiveness deteriorates as the entropy of target distributions increases due to insufficient draft diversity. To overcome this bottleneck without sacrificing parallelism, we introduce UBTree, a parallel drafter that couples a Unigram proposer with a Bigram selector to construct drafting Trees. The unigram proposer is trained with the standard cross-entropy objective to generate candidate tokens independently for each position, while a lightweight bigram selector predicts transition scores between adjacent candidate pairs. Unlike the proposer, the selector is trained with a renormalized KL objective on high-temperature data. This tree-native training broadens the supervision beyond the greedy path, encouraging plausible alternative branches that improve the chance of accepting additional tokens during tree verification. Across seven standardized benchmarks with Qwen3-4B and Qwen3-8B, UBTree achieves an average speedup of $5.84$--$6.94\times$ over autoregressive decoding and outperforms DARTree in all 28 comparisons. Production-scale evaluation further demonstrates UBTree's advantage over frontier baselines such as DSpark.