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
- •For software engineers building language apps: Optimize the speed of language model inference in applications like chatbots or text generation without reducing output quality.
- •For cloud platform teams: Improve throughput and reduce compute costs for hosted language model APIs by integrating faster parallel decoding methods like UBTree.
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.