acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Speculative decoding accelerates language model inference by verifying multiple draft tokens predicted by lightweight draft models in a single target-model forward pass. Recent parallel drafters have achieved breakthrough performance in frontier production models, yet their gains diminish as the target distribution becomes more entropic, particularly for later positions within draft blocks and under long-context settings, where limited draft diversity increasingly constrains acceptance. To overcome this bottleneck without sacrificing parallelism, we introduce **UBTree**, a parallel drafter that couples a **U**nigram proposer with a **B**igram selector to construct drafting **Tree**s. 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 – over autoregressive decoding and outperforms DARTree in all 28 comparisons. Production-scale evaluation further demonstrates UBTree's advantage over frontier baselines such as DSpark.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Speculative Decoding

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_8Po5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces UBTree, a speculative decoding technique that combines the efficiency of parallel drafting with dependency-aware tree construction. A parallel drafter first proposes multiple per-position unigrams in parallel. Then, the bigram selector identifies the plausibility of the bigrams to effectively construct tree drafts from the unigrams. The paper provides broad experiments to showcase the effectiveness, spanning over multiple models, benchmarks, and serving scenarios, where UBTree provides consistent and significant speedups.

Critical strengths

The motivation of the paper is strong and agreeable (naive tree construction from unigrams would likely be suboptimal in terms of high-quality draft tree construction), and the proposed parallel bigram selection approach directly and effectively addresses this problem. The proposed approaches, including both tree construction and tree-aware training, leads to significant empirical performance gains. The gains are consistent over an extremely broad range of evaluation, suggesting the significant practical value of the paper.

Critical weaknesses

I did not find any critical weakness.

Questions for authors

I do not have any further questions that may materially affect my assessment.

1 comment

We sincerely thank the reviewer for the positive assessment.

Reviewer_46jyOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes UBTree, a parallel tree-based drafting method for speculative decoding. To address the trade-off between token dependency modeling and drafting efficiency, UBTree combines a DFlash-based unigram proposer with a lightweight bigram selector to construct candidate trees without sequential neural computation. It further introduces deep codebooks and depth-dependent calibration to improve transition scoring. To mitigate the mismatch between single-path training and multi-path verification, the authors propose a tree-native training strategy using high-temperature target rollouts and a renormalized KL objective to better capture plausible alternative branches.

Experiments on seven benchmarks across Qwen3-4B, Qwen3-8B, and two production-scale models demonstrate improvements in acceptance length and decoding speedup over existing methods, including DARTree and DSpark. The paper also evaluates concurrent serving and long-context scenarios to assess practical efficiency.

Critical strengths

S1. Well-motivated design balancing token dependency modeling and parallel efficiency.

By combining a unigram proposer with a parallel bigram selector, UBTree models adjacent-token dependencies while avoiding the sequential neural computation introduced by autoregressive corrections in existing tree-based drafting methods. This design effectively integrates parallel drafting with multi-path tree verification and provides a clear and technically reasonable approach to improving decoding efficiency.

S2. Broad experimental evaluation and practical relevance.

The paper evaluates UBTree across multiple model scales, seven benchmarks, and different decoding temperatures, including concurrent serving and long-context scenarios. The results demonstrate overall improvements in acceptance length and decoding speedup over major baselines. Furthermore, the latency breakdown shows a substantial reduction in draft post-processing overhead, providing direct evidence of the method's practical efficiency.

Critical weaknesses

W1. Limited methodological novelty and insufficient differentiation from prior work.

As acknowledged in the paper, the unigram proposer is adopted from DFlash, the parallel bigram selector builds upon DFlash 2, and the tree construction strategy follows DARTree. While the proposed deep codebooks, depth calibration, and tree-native training introduce additional improvements, the overall framework largely integrates existing techniques. It remains unclear whether these modifications constitute a sufficiently substantial methodological advance beyond existing parallel tree drafting methods.

W2. Insufficient ablation studies and statistical validation.

Although the paper provides some ablation studies, the evidence supporting its core contributions remains insufficient. First, the authors do not independently ablate deep codebooks and depth calibration, making it difficult to assess their individual contributions. Second, while tree-native training is presented as a central contribution, forward KL yields only marginal speedup improvements of 0.01–0.04× over cross-entropy, without statistical analysis across independent training runs. While the current experiments support the overall effectiveness of the combined approach, they do not sufficiently establish the individual contributions of the newly introduced components or the robustness of the marginal gains from KL over CE.

Questions for authors

Q1. Methodological novelty.

Given that several key components of UBTree build upon existing methods such as DFlash, DFlash 2, and DARTree, could the authors further elaborate on the substantive contributions of deep codebooks, depth calibration, and tree-native training, and how these improvements support the overall methodological novelty of the paper?

Q2. Ablation of architectural components.

Could the authors provide separate ablation studies for deep codebooks and depth calibration to better understand their individual effects on acceptance length and decoding speedup?

Q3. Statistical reliability of the training strategy.

Given the relatively small improvements of forward KL over cross-entropy, could the authors report results across multiple independent training seeds, including means and standard deviations or confidence intervals, to better assess the robustness of these gains?

2 comments

We sincerely thank the reviewer for the constructive and insightful review and would like to resolve them by points:

W1 & Q1: Methodological novelty. The plain combination of the existing components does not work: DFlash proposer + DFlash 2 selector + DARTree search reaches only 5.95× / τ\tau 8.82, below DARTree (6.31× / 10.13). Our redesigned selector raises this to 6.57× / 9.86, and tree-native training raises it further to 6.88× / 10.23 (Qwen3-4B, Tinfer=0T_\text{infer}=0, Table 4). Each design fixes a specific limitation of the plain combination:

  • Deep codebooks: a tree must score all K2K^2 candidate pairs per depth, including low-ranked tokens that single-path selection rarely uses. Anchoring the codebooks in the target embedding gives these tokens informed representations.
  • Depth calibration: the proposer predicts all positions in parallel, and its logits become less reliable at farther positions, whereas the selector additionally conditions on the concrete predecessor token. The right balance between proposer logits and selector scores therefore shifts with depth, which DFlash 2's fixed unit weights cannot capture.
  • Tree-native training: tree branches pass through non-greedy predecessors, which temperature-matched training never shows the selector.

W2 & Q2: Ablation studies. We trained the two single-component variants in the same setting as Table 4 (Top) (Qwen3-4B, Ttrain=Tinfer=0T_\text{train}=T_\text{infer}=0) and evaluated them on GSM8K:

Selector (GSM8K)τ\tau
DFlash 2 selector (neither component)11.08
+ deep codebooks only11.76
+ depth calibration only12.04
+ both (UBTree selector)12.11

Each component improves τ\tau on its own (+0.68 and +0.96), and the combination is best (+1.03). The gains partly overlap: with depth calibration in place, deep codebooks add a further +0.07. Depth calibration has the larger individual effect.

W2 & Q3: Multiple training seeds to test the signifance of KL divergence We agree that the gain of the renormalized KL over hard-label CE is a small refinement (+0.04× / +0.15 τ\tau at Tinfer=0T_\text{infer}=0; +0.01× / +0.08 τ\tau at Tinfer=1T_\text{infer}=1) that comes at no extra inference cost, since it only changes the training loss. We will state this explicitly in the updated manuscript.

Within tree-native training, the main performance gain comes from high-temperature training data, and its effect is clear:

  • In Table 4 (Top), training at Ttrain=1T_\text{train}=1 instead of the temperature-matched Ttrain=0T_\text{train}=0 improves both speedup and τ\tau on all seven benchmarks (+0.31× / +0.37 τ\tau on average). The gain holds even with sampled hard labels (+0.27× / +0.22 τ\tau), so it does not depend on the KL objective.

As our current ablation study and updated description have clarified the source of improvement in tree-native training, we follow all baselines (DFlash, Domino, DDTree, DARTree) to not report the result of multiple training seeds here.

Thanks for your rebuttal and I will maintain my positive score.

Reviewer_uiJcOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper propose UBTree, which introduce a bigram selector for tree construction in DFlash. The scorer is trained on temperature higher than inference and renormalized KL supervision for better fit tree construction process. The method is evaluated with several recent chain or tree based baselines and show good performance and robustness.

Critical strengths
  • UBTree extend bigram selector to tree construction and achieve better speed up compared with existing baselines like DFlash2, DSpark, DARTree, the method can achieve lower draft latency (compare with other tree based methods) and can be integrated into DFlash style drafters as a selector without training a new correction head.
  • The method is integrated into serving engines like SGLang and work with tree based verification for MoE and mixed attention, the implementation of the method is complete.
  • On 4B/8B models, which is widely used for evaluate DFlash style draft model, the overall speed up exceed all baselines, as the result of longer accept length and/or faster draft speed.
Critical weaknesses
  • The comparison on production-level model with other tree based method like DARTree is missing, the chain based drafters should also support draft tree, this could also be added to comparison.
  • The improvement compare with DARTree mainly come from lower draft latency, the accept length have tiny improvement.
  • The ablation of training temperature show little variance, and the train process does not introduce tree structure, the training process is not tree native.
  • The form of the selector comes from DFlash 2, and the tree search comes from DARTree. For first-order dependency, being parallelizable is not unique to UBTree (the Markov head of DSpark can also be precomputed).
Questions for authors
  • The DFlash baseline is trained for 6 epochs, while UBTree is jointly trained for 2 additional epochs on top of it. Are the baselines trained for the same total number of steps?
  • TtrainT_{\text{train}} simultaneously changes the rollout data, the softness of the KL target, and the proposer. Which of these factors actually contributes to the improvement?
  • Can the bigram selector be extended to a trigram (3-gram) model, or incorporate other n-gram like guidance for better preformance?
3 comments

We sincerely thank the reviewer for the constructive and insightful review and would like to resolve them by points:

W1: missing drafting tree baselines DARTree requires a Domino backbone trained for the specific target, and no Domino checkpoints exist for Ling3-Flash or Qwen3.8-27B; training one for a 124B MoE target is not feasible within the discussion period. At production scale we therefore compare against the strongest released production drafters, DSpark and DFlash 2.

As for the tree versions of chain drafters, Table 1 already pairs each chain drafter with its tree counterpart: EAGLE-3 (16) → EAGLE-3 (64), i.e., EAGLE-3 with a 64-node draft tree; DFlash → DDTree (best-first tree over DFlash proposals); and Domino → DARTree (tree with an autoregressive correction head over Domino). UBTree achieves the highest speedup in all 28 instruct-model comparisons.

W2: Improvement compare with DARTree mainly come from lower draft latency Lower drafting latency is the intended benefit of our design: UBTree models token-wise dependency without DARTree's sequential correction head, cutting draft post-processing from 3.36 ms to 1.38 ms per round (Appendix C.1). As for acceptance length, we agree that at Tinfer=0T_\text{infer}=0 UBTree's τ\tau is on par with DARTree's, while the τ\tau gains are clear where entropy is higher. At Tinfer=1T_\text{infer}=1, UBTree improves τ\tau over DARTree by +0.44 (Qwen3-4B) and +0.33 (Qwen3-8B).

W3: Methodology 1). We include two ablations for training temperature: Table 4 (Top) and Table 4 (Middle). While Table 4 (Middle) shows the optimal temperature in range 0.8-1.2, Table 4 (Top) shows the significance of switching to high temperature training, whose variance is not little. 2) Tree-native training does not necessarily draft a tree in training. Instead, it takes the goal of tree drafting into consideration. Our training improves the weight of candidate tokens, which could be suboptimal for single-candidate drafting. It is therefore tree-native training. 3) We agree that DSpark's Markov head can be precomputed and will acknowledge this in the related work. Our claim is: among tree drafters built on block-parallel proposers, DDTree omits token-wise dependency and DARTree models it with a sequential head, whereas UBTree models it with no sequential neural computation.

[continued from last post]

Q1: Baseline training We train EAGLE3, DFlash, and our method until they converge instead of using the same training steps. For EAGLE3 and DFlash, we train them for 6 epoches. Notably, more training steps do not improve the performance of our baselines. For Domino, we use the officially released checkpoints from the same data distribution. DDTree and DARTree use DFlash and Domino checkpoints. The details of baseline training have been covered by Section 4.1 (Baselines).

Q2: Main factor of tree-native training Rollout data and KL-target softness share the same temperature TtrainT_\text{train}. Since the rollouts are sampled from the target at TtrainT_\text{train}, the KL loss must use the target distribution at the same TtrainT_\text{train} (Eq. 7), so that the proposer and the selector are supervised by the same distribution that generated its training data.

Proposer and selector are trained on the same data. The proposer is also trained on the TtrainT_\text{train} rollouts (Appendix B.4), so the TtrainT_\text{train} comparison below measures the joint effect of high-temperature data on the proposer and the selector; we did not separate the two. Within the joint training stage, all variants in Table 4 (Bottom) start from the same proposer checkpoint.

High-temperature training data is the main contribution. It improves both speedup and τ\tau on all seven benchmarks, and the gain holds even with sampled hard labels (+0.27× / +0.22 τ\tau). The renormalized KL adds only a small gain on top (+0.15 and +0.08 τ\tau at Tinfer=0T_\text{infer}=0 and 1). This is expected, since both objectives share the same target in expectation, and the KL gain comes at no extra inference cost because it only changes the training loss.

We will update the paper to reflect this attribution: high-temperature training data, used for both the proposer and the selector, is the main source of improvement, and the renormalized KL is a small refinement at no extra inference cost.

Q3: Tri-gram selector Yes, the selector extends naturally. What changes is the cost. UBTree's parallelism relies on path scores factorizing over edges: with a bigram selector, each edge score depends only on (parent, child), so all scores for the candidate supertree are computed in one parallel pass before the search. An nn-gram selector conditions on n−1n-1 predecessors, so the number of scores per depth grows from K2K^2 to KnK^n. In our setting (K=64K=64, 15 draft positions):

  • Bigram: K+14K2=57,408K + 14K^2 = 57{,}408 scores per round.
  • Trigram: K+K2+13K3=3,412,032K + K^2 + 13K^3 = 3{,}412{,}032 scores per round, about 59×59\times more.

In practice, this increased computation cost will weaken our overhead advantage compared to sequentially constructed drafting trees. We therefore maintain the Bigram plan.

Reviewer_uiJcOpenReview ↗

Appreciation to Author's Reply

Thank you to the authors for the detailed and thoughtful responses. Your clarifications have addressed my concerns and raise my understanding of details of diffusion based drafting.

Sincerely appreciate the authors' effort and insights.

Comments on the paper

1 comment

We thank all reviewers for their time and constructive feedback. We have uploaded a revised manuscript with all changes highlighted in blue:

1. Attribution of tree-native training (Section 4.4, "Training objectives", Lines 458–461; Reviewers uiJc and 46jy). We now state that the main source of improvement is the high-temperature training data, used for both the proposer and the selector, and that the renormalized KL is a small refinement at no extra inference cost.

2. DSpark (Appendix E, Additional Related Work, Lines 983–984; Reviewer uiJc). We acknowledge that the first-order Markov head of DSpark can also be precomputed in parallel.

We address each reviewer's comments in the individual responses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.