acceptodds
Under review as a conference paper at ICLR 2027

Tsubame: Tree Replay for Diffusion-Based Speculative Decoding

Abstract

Context-aware dynamic trees allocate the speculative decoding budget according to draft path probabilities, adapting their depth and branching to the current context. Under stochastic decoding, however, we find that this structural advantage does not always compensate for the acceptance gains of random sampling paired with advanced verification, and such dynamic trees can fall behind sampled chains in some settings. These trees grow their topology from the candidates themselves, so the tokens submitted for verification are typically the deterministic high-score tokens selected during construction. This coupling is not inherent: once the topology is fixed, its nodes can be repopulated by sampling, allowing dynamic trees to retain their structural advantage while also benefiting from random sampling and advanced verification. Diffusion-based drafters make this practical, as their parallel outputs or lightweight conditional corrections allow candidates to be regenerated cheaply after the complete topology is known. We introduce Tsubame, a two-pass tree speculative decoding framework for diffusion-based drafters. The first pass plans and freezes a context-aware topology using draft path scores; the second replays the fixed topology, sampling the tokens that populate its nodes to form the candidate tree for verification. We prove that Tsubame is lossless under compatible sampling and verification strategies. Experiments across three diffusion-based drafters, six datasets, and multiple candidate budgets show that Tsubame improves acceptance length and throughput over deterministic trees, including settings where it reverses their disadvantage against sampled chains.

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

Reviews

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

Tsubame proposes a two-pass speculative decoding framework for diffusion-based drafters that separates tree topology planning from candidate generation. The first pass constructs a deterministic, context-aware tree, while the second freezes its structure and repopulates its nodes using a chosen sampling strategy. Parallel backbone outputs and lightweight conditional updates make this replay inexpensive. The framework preserves the target distribution when paired with compatible verification algorithms. Experiments with Domino, DSpark, and DFlash2 across six datasets report improvements in acceptance length and throughput over deterministic trees, with suitable configurations also outperforming sampled-chain baselines.

Critical strengths
  1. The method fully decouples context-aware tree construction from stochastic candidate sampling.
Critical weaknesses
  1. Tsubame’s Domino Chain Top1 baseline reports substantially lower speedups across all six benchmarks than the original Domino paper (Domino: Decoupling Causal Modeling from Autoregressive Drafting in Speculative Decoding, with T = 1, draft budget = 16). For example, on GSM8K in qwen3-8B , the baseline drops from 6.47× to 5.54×, while Tsubame achieves 6.44×—even below the original reported result.

  2. Although the two-pass design decouples tree construction from sampling, the frozen topology may not suit the replayed tokens. For example, a deep subtree planned for token a may become inefficient when replay replaces it with token b. It is therefore unclear whether replay preserves the benefits of context-aware budget allocation.

Questions for authors
  1. Why are your Domino baseline results lower than the original paper’s, and do Tsubame’s gains persist under matched evaluation settings?
5 comments
AuthorsOpenReview ↗

Response to Reviewer voBZ (1/3)

We thank the reviewer for the review. We address the reviewer's concerns below.

Q1/W1. On Comparing Absolute Speedups Across Hardware

It is well established in speculative decoding that speedup ratios measured under different hardware conditions cannot be directly compared.

Even with identical code, the hardware (CPU/GPU specifications, device–host communication latency, and even runtime settings such as SMT siblings and GPU clock frequency), the CUDA/PyTorch versions (which determine the actual implementations of the backend kernels), and many other factors all affect the measured speedup.

This is precisely why benchmarks such as Spec-Bench exist.

For example, EAGLE-2 reports 3.62× on MT-Bench in its paper, whereas the public Spec-Bench evaluation (https://github.com/hemingkx/Spec-Bench/blob/main/Leaderboard.md) obtains only 2.56×. Even within Spec-Bench, the same method obtains different speedups in different environments (GPU, CPU, and CUDA versions): 2.84× on an A100 versus 2.56× on an RTX 3090.

The consensus in speculative decoding research is therefore to guarantee a fair comparison by using exactly the same device and backend, not to compare absolute numbers across papers. Our experiments run on RTX 3090 GPUs, whereas Domino uses A100 GPUs. The two sets of numbers are not comparable.

Moreover, third-party reproductions of Domino, such as DominoTree (6.04×) and DARTree (5.79×), all report numbers lower than the official 6.47×.

On Our Evaluation Setting

Beyond hardware, several details of the experimental protocol and statistics also affect the reported results.

For consistency throughout the paper, and to stay as close as possible to how serving is measured, we compute the speedup ratio as total tokens divided by total time (i.e., overall throughput), divided by the AR throughput. This reflects the overall single-request throughput speedup.

The official Domino aggregation instead averages the per-sample per-token latency for each method and then takes the ratio of the two averages, and it only accounts for the decoding stage (prefilling is excluded).

Here, replay uses the default configuration of the paper: Mixed sampling (the top m−1 tokens plus one sampled token at each branching point), verified with UniVer.

RTX 3090:

MethodOur protocolOfficial Domino aggregation
Top1 chain5.54×5.85×
First pass6.04×6.32×
Mixed/UniVer replay6.44×6.77×

With the code unchanged, running on an RTX PRO 6000 system instead:

MethodOur protocolOfficial Domino aggregation
Top1 chain6.23×6.52×
First pass6.71×7.04×
Mixed/UniVer replay7.23×7.56×

Under the official Domino aggregation on the RTX PRO 6000, the Top1 chain (6.52×) already exceeds the 6.47× reported by Domino, and replay reaches 7.56×. Regardless of the protocol or the device, the gain of replay is consistently present and stable: relative to the Top1 chain, +15.7% on the RTX 3090 and +16.0% on the RTX PRO 6000 under the official Domino aggregation (+16.2% and +16.1% under our protocol).

Therefore, speedup ratios are comparable only under the same experimental conditions and the same statistics.

AuthorsOpenReview ↗

Response to Reviewer voBZ (2/3)

W2. Where Is the Mismatch, and How Much Does It Matter?

For where Tsubame's gains come from (tree structure, sampling, and verification), please see Part 1 of our response to Reviewer 3m2g.

We analyze the tree in two parts: the single-chain case and the branching points.

First, for a single chain, the mismatch does not invalidate the planned budget allocation.

Using draft probabilities as a proxy for acceptance to guide tree construction is the basic premise of dynamic tree methods such as EAGLE-2 and DDTree. The same premise naturally extends to OT-based verifiers such as RS and Block Verification: at a given prefix, the expected acceptance of RS is the overlap between p and q, which does not depend on which token is actually sampled. A sampled path does change the subsequent prefixes, so two questions remain: whether the proxy itself changes along the new prefixes, and whether the planned prediction is realized on the sampled path. We verify both directly.

We run replay on a single chain with Domino. We use the top-1 draft sequence to predict the acceptance length (the planned prediction), then replay (resample and apply AR correction to obtain another draft sequence). As a post hoc diagnostic only (it is never used to decide the structure), we recompute the same prediction along the replayed prefixes, i.e., using the top-1 draft probability under each new prefix. Finally, we compute the expected acceptance length of the sampled sequence under RS or Block Verification, and of the planning top-1 draft under direct verification. We take the first 16 prompts of each of GSM8K, HumanEval, and MT-Bench.

The mean proxy prediction barely changes after replay.

DatasetPlanned prediction (top-1 path)Recomputed along the replayed prefixesChange
GSM8K10.45210.368−0.80%
HumanEval7.8897.807−1.04%
MT-Bench3.3743.322−1.52%

Although the replayed path differs from the planned one, the mean predicted acceptance length changes by only about 1%. The confidence-based proxy that dynamic trees use to estimate acceptance length remains stable before and after replay.

After replay, the gap between predicted and actual acceptance becomes smaller.

Values are expected acceptance lengths computed with the target distribution at matched starting prefixes (a paired counterfactual diagnostic).

DatasetPlanned prediction (basis of budget allocation)Top1, direct verification (no mismatch)Sample + RSSample + Block Verification
GSM8K10.4527.806 (overestimated by 33.9%)8.106 (overestimated by 28.9%)8.410 (overestimated by 24.3%)
HumanEval7.8895.870 (overestimated by 34.4%)6.013 (overestimated by 31.2%)6.286 (overestimated by 25.5%)
MT-Bench3.3742.754 (overestimated by 22.5%)2.756 (overestimated by 22.4%)2.855 (overestimated by 18.2%)

The planned prediction is closest to Block Verification, then RS, and farthest from Top1, the case with no mismatch at all.

Taken together: the mean proxy prediction is essentially unchanged after replay, and the planned prediction is realized even more accurately on the sampled sequence than on the top-1 sequence itself. Perfect alignment with the plan is therefore not required; even when the actual trajectory differs from the planned one, the basis for allocating budget along this path remains valid in our measurements.

As for why we do not use sampled nodes to estimate acceptance length: this is exactly what we deliberately avoid. If the probability of a realized sampled node itself is used as the proxy, the sampling outcome affects whether the node is retained, which breaks losslessness.

AuthorsOpenReview ↗

Response to Reviewer voBZ (3/3)

Second, at branching points, the mismatch exists, but it can be greatly mitigated by the choice of sampling scheme.

Replay can use any valid sampling scheme with its matching verifier, not only standard sampling without replacement. Here we use Mixed sampling, the scheme proposed by Hu et al. (ICLR 2025): for a branch with m slots, the first m−1 slots are filled deterministically with the highest-probability tokens, and the last one is sampled from the renormalized distribution over the remaining tokens.

The benefits are clear:

  1. Acceptance: Mixed sampling achieves higher acceptance than TopK or WoR with the same number of candidates (see the single-layer counterfactual analysis in our response to Reviewer 3m2g).
  2. Branch control: given the same prefix, the leading tokens that carry the most mass at a branch are exactly the same as in planning; only the tail slot explores additional acceptance.

We measure, under Mixed sampling and sampling without replacement (WoR), the fraction of branching points whose prefix remains consistent with the plan. A branching point is consistent if the node and all its ancestor tokens are identical to those in the first pass, weighted by the probability that the node is included in the accepted prefix. Each dataset uses 16 prompts, with 3 samples per starting point.

BudgetDatasetMixedWoR
B = 16GSM8K94.0%87.5%
B = 16HumanEval95.1%89.9%
B = 16MT-Bench99.3%88.5%
B = 64GSM8K99.4%89.7%
B = 64HumanEval99.2%81.6%
B = 64MT-Bench99.5%77.3%

The trend is clear. At B = 16, the prefix consistency of Mixed reaches 94.0%–99.3%; WoR is somewhat lower but still 87.5%–89.9%, which is why WoR/Traversal remains competitive at small budgets in the paper. At B = 64, WoR drops to 77.3% on MT-Bench, whereas Mixed rises above 99%. For Mixed, prefix mismatch is therefore rare on the accepted path.

The results reported in our paper agree well with this experiment. At small budgets, the tree has few branches, so WoR and Mixed sampling, each paired with its advanced verifier, perform similarly, each winning in some settings; here the gain from pure WoR sampling outweighs the negative effect of the mismatch. At B = 64, frequent mismatch under WoR disrupts the budget allocation across branches, and in some cases the acceptance length can fall below that of the deterministic tree, whereas Mixed sampling retains substantial gains.

To summarize:

  • Single chain: replay sampling a different path does not invalidate the planned budget.
  • Branching points: the mismatch exists, but a suitable sampling scheme (Mixed sampling) makes it rare on the accepted path. At large budgets in particular, over 99% of the branching points (weighted by their probability of being accepted) have prefixes identical to the plan.

For the reviewer's specific example of a deep subtree planned for token a: if a is among the top m−1 children at a branching point, Mixed sampling retains it as is during replay (given the same prefix), so the subtree planned under it is not replaced. Tokens change only at the last (sampled) slot of a branching point and at single-child nodes. The latter is exactly the single-chain case analyzed above, and the prefix-consistency results above already account for both, weighted by each node's probability of being on the accepted path.

Regarding whether replay preserves the benefit of context-aware budget allocation, please see the static-tree comparison in our response to Reviewer 3m2g. It is a 2×2 comparison at the same budget B = 37: static vs. dynamic topology, each with TopK and with Mixed/UniVer. Under the same Mixed/UniVer sampling and verification, the replayed dynamic topology outperforms the static topology on every dataset (e.g., τ 10.005 vs. 9.114 on GSM8K). The benefit of context-aware allocation is therefore retained after replay.

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

This paper proposes Tsubame, a two-pass speculative decoding framework that separates dynamic tree construction from stochastic candidate sampling. It first constructs a context-aware tree topology and then resamples tokens for lossless verification. Experiments across three diffusion-based drafters and six datasets demonstrate improvements in acceptance length and throughput over deterministic trees and sampled-chain baselines.

Critical strengths
  1. The paper identifies a limitation of deterministic dynamic trees under stochastic decoding, where sampled chains with advanced verification can achieve better performance.
  2. The proposed framework separates tree construction from candidate sampling, allowing different sampling and verification strategies to be applied to dynamic tree topologies.
Critical weaknesses
  1. The necessity of the two-pass design is not sufficiently justified. It remains unclear why stochastic sampling cannot be incorporated directly into dynamic tree construction.
  2. The tree topology is constructed using deterministic candidates, which are discarded during replay. The paper does not validate whether the original topology remains effective for the newly sampled tokens. Comparisons with static trees using the same sampling and verification strategies are also missing.
  3. The experimental comparisons are insufficient. The paper lacks direct comparisons with closely related methods such as DDTree and DARTree.
  4. The experimental analysis is limited. Most results are presented in tables, with little analysis of why tree replay improves acceptance and throughput. The improvements are also relatively small in some settings.
Questions for authors
  1. Why is a two-pass design necessary? Could stochastic sampling be incorporated into one-pass dynamic tree construction while preserving lossless decoding?
  2. Why should the topology constructed from deterministic candidates remain effective after replay? Could the authors compare Tsubame with static trees using the same sampling and verification strategies?
  3. Could the authors compare Tsubame with DDTree and DARTree under comparable experimental settings?
  4. Could the authors provide a deeper analysis of the performance gains from tree replay? In particular, what explains the limited improvements in some settings, and how do these gains change with different tree structures and candidate budgets?
6 comments
AuthorsOpenReview ↗

Response to Reviewer 3m2g (1/5)

We thank the reviewer for the review. Several of the reviewer’s questions relate to the interplay between sampling and verification. We therefore start from this background, explain our method step by step, and answer the reviewer’s questions along the way.

Tree Structure, Sampling, and Verification

In tree speculative decoding, there are three distinct design choices that affect acceptance:

  1. Tree structure: the most intuitive one. A good tree structure yields higher acceptance.
  2. Sampling method: different sampling methods have different theoretical upper bounds on acceptance.
  3. Verification algorithm: given a sampling method, it determines how closely this upper bound can be approached. This is essentially an optimal transport problem.

In fact, the latter two contribute substantially to acceptance. A simple example illustrates this.

We test Domino on GSM8K and MT-Bench with a single layer and up to 3 candidates. We generate with the top-3 tokens as the actual candidates and compute the counterfactual acceptance rate at every step:

#CandidatesSamplingGSM8KMT-Bench
1Top191.27%74.02%
1Sample192.84%77.24%
2Top296.82%84.32%
2Top1+Sample198.01%87.80%
2Sample2 without replacement97.33%85.86%
3Top398.23%88.33%
3Top2+Sample199.01%91.22%
3Sample3 without replacement98.45%89.37%

Each sampling scheme is verified with its matching verifier: TopK with naive token matching; Sample1 with standard rejection sampling (RS); sampling without replacement (WoR) with recursive rejection sampling (RRS); and TopK+Sample1, i.e., Mixed sampling (Hu et al., ICLR 2025), with its OT-based verifier, which coincides with UniVer in the single-layer case. We use these abbreviations (WoR, RRS, Mixed, UniVer) below.

Top1 is weaker than Sample1 (GSM8K 91.27% vs. 92.84%, MT-Bench 74.02% vs. 77.24%). With multiple candidates, TopK is also generally weaker than schemes that contain a sampled candidate. Top1+Sample1, with only two candidates, already comes close to Top3 (GSM8K 98.01% vs. 98.23%, MT-Bench 87.80% vs. 88.33%).

That is, the sampling method by itself affects acceptance, and a good sampling method can reach comparable acceptance with a smaller budget. This is one source of the gain.

For verification, consider another example. With a single sampled candidate (Sample1), replacing Rejection Sampling (RS) with token matching drops acceptance from 92.84% to 90.65% on GSM8K and from 77.24% to 69.47% on MT-Bench, which is even below Top1. This gap is exactly what the verification algorithm contributes.

Intuitively, for a sampled node, RS can exploit the overlap between the target and draft distributions. For TopK nodes, the attainable acceptance is only the target probability mass of the TopK draft tokens, and every verifier degenerates to Naive, because there is no additional distributional overlap for the verifier to exploit.

As stated above, sampling determines the theoretical acceptance ceiling, and verification determines how closely this ceiling is approached. The TopK selection used by dynamic trees is, in most cases, not a good sampling scheme.

Sampling and verification are discussed in great detail in Towards Optimal Multi-draft Speculative Decoding (Hu et al., ICLR 2025) and RheoSampling (Hu et al., NeurIPS 2026).

AuthorsOpenReview ↗

Response to Reviewer 3m2g (2/5)

The Conflict Between Dynamic Trees and Sampling

The problem is that the latter two (sampling and verification) cannot be directly combined with dynamic tree structures (EAGLE-2/3, DDTree, etc.), for a clear reason: if whether a sampled token stays in the tree is decided by the probability of its own realization, losslessness is very likely to be lost. Sections 2 and 4 of RheoSampling discuss this in detail. This is not limited to trees: a chain sometimes needs early stopping, and if the decision to verify a token depends on the probability of the token actually sampled, deciding retention based on the sampling outcome introduces selection bias and breaks losslessness (see the Appendix of DSpark).

Take DARTree, which the reviewer mentioned, as an example. It follows the EAGLE-2-style expand-then-prune mechanism: it first builds a candidate pool and then selects the top-N tokens through a single global prune (selecting the top-N tokens is equivalent to pruning with the N-th largest score as the threshold).

Consider what happens with naive sampling plus pruning in a simple example.

Let the vocabulary be {a, b, c}, the draft distribution q = (0.5, 0.3, 0.2), and the target distribution p = (0.2, 0.3, 0.5).

Standard procedure: sample a token x from q, accept it with probability min(1, p(x)/q(x)), and on rejection resample from the residual norm(max(p − q, 0)), i.e., standard single-token rejection sampling.

  • x = a (0.5): accepted w.p. 0.4 -> outputs a with 0.2; rejected with 0.3 -> the residual contains only c -> outputs c with 0.3
  • x = b (0.3): accepted w.p. 1 -> outputs b with 0.3
  • x = c (0.2): accepted w.p. 1 -> outputs c with 0.2

Total: (0.2, 0.3, 0.5) = p. Lossless.

Adding "pruning by the realized sampling probability": a token with q(x) < 0.3 is pruned, after which we sample directly from p, while the verifier still computes with q.

  • x = a and x = b are unchanged: a 0.2, b 0.3, c 0.3
  • x = c (0.2) is pruned and replaced by a sample from p: a 0.04, b 0.06, c 0.10

Total: (0.24, 0.36, 0.40), which is not equal to p.

The reason is that whether a token survives depends on its own sampling outcome, so the actual proposal distribution is no longer q, while the verifier still computes the acceptance probability and the residual with q. Global pruning in a tree follows exactly the same principle, only less visibly.

Strictly speaking, losslessness can still be enforced in some ways, e.g., building the draft tree from sampled tokens instead of TopK and verifying with token matching (see Appendix A.2 of DominoTree), but the actual speed is often worse than simply using a deterministic tree. This is what we keep emphasizing: the verification algorithm must match the sampling method. In this example, "selecting tokens while sampling" no longer permits OT-based verifiers that assume the original sampling distribution (e.g., the rejection sampling above); token matching remains a lossless fallback, but forfeits the acceptance benefit illustrated above.

Therefore, current mainstream dynamic tree designs (e.g., EAGLE-2/DDTree) only pursue the quality of the tree structure and cannot exploit the advantages of sampling and verification. This is precisely the answer to the reviewer's first question: adding random sampling to a dynamic tree while preserving losslessness is by no means trivial. We refer the reviewer to Section 2 of RheoSampling and the Appendix of DSpark.

This does not mean that a lossless stochastic dynamic tree is impossible within a single pass: RheoSampling achieves this by assigning sampled candidates prescribed proxy scores for structural decisions, at the cost of restricting where sampled candidates can be placed. Tsubame takes a different route, described next.

Our Solution

The natural question is then: how can one obtain both the structural advantage of dynamic trees and the acceptance advantage of sampling and verification?

For AR drafters, methods such as RheoSampling insert a sampled token into the TopK expansion to exploit the extra acceptance brought by randomness. For diffusion-based drafters, we find a more direct solution. Because of the nature of diffusion drafters, probability distributions can be obtained very cheaply. Hence there is no need, as in RheoSampling, to decide within a single drafting pass both what the tree structure is and where sampled nodes are placed. Instead, two drafting passes directly decouple the tree structure from sampling and verification.

Decoupling the tree structure from sampling and verification means that sampling can be performed in any valid way, not limited to pure TopK or pure sampling without replacement.

AuthorsOpenReview ↗

Response to Reviewer 3m2g (3/5)

Where Is the Mismatch, and How Much Does It Matter?

We analyze the tree in two parts: the single-chain case and the branching points.

First, for a single chain, the mismatch does not invalidate the planned budget allocation.

Using draft probabilities as a proxy for acceptance to guide tree construction is the basic premise of dynamic tree methods such as EAGLE-2 and DDTree. The same premise naturally extends to OT-based verifiers such as RS and Block Verification: at a given prefix, the expected acceptance of RS is the overlap between p and q, which does not depend on which token is actually sampled. A sampled path does change the subsequent prefixes, so two questions remain: whether the proxy itself changes along the new prefixes, and whether the planned prediction is realized on the sampled path. We verify both directly.

We run replay on a single chain with Domino. We use the top-1 draft sequence to predict the acceptance length (the planned prediction), then replay (resample and apply AR correction to obtain another draft sequence). As a post hoc diagnostic only (it is never used to decide the structure), we recompute the same prediction along the replayed prefixes, i.e., using the top-1 draft probability under each new prefix. Finally, we compute the expected acceptance length of the sampled sequence under RS or Block Verification, and of the planning top-1 draft under direct verification. We take the first 16 prompts of each of GSM8K, HumanEval, and MT-Bench.

The mean proxy prediction barely changes after replay.

DatasetPlanned prediction (top-1 path)Recomputed along the replayed prefixesChange
GSM8K10.45210.368−0.80%
HumanEval7.8897.807−1.04%
MT-Bench3.3743.322−1.52%

Although the replayed path differs from the planned one, the mean predicted acceptance length changes by only about 1%. The confidence-based proxy that dynamic trees use to estimate acceptance length remains stable before and after replay.

After replay, the gap between predicted and actual acceptance becomes smaller.

Values are expected acceptance lengths computed with the target distribution at matched starting prefixes (a paired counterfactual diagnostic).

DatasetPlanned prediction (basis of budget allocation)Top1, direct verification (no mismatch)Sample + RSSample + Block Verification
GSM8K10.4527.806 (overestimated by 33.9%)8.106 (overestimated by 28.9%)8.410 (overestimated by 24.3%)
HumanEval7.8895.870 (overestimated by 34.4%)6.013 (overestimated by 31.2%)6.286 (overestimated by 25.5%)
MT-Bench3.3742.754 (overestimated by 22.5%)2.756 (overestimated by 22.4%)2.855 (overestimated by 18.2%)

The planned prediction is closest to Block Verification, then RS, and farthest from Top1, the case with no mismatch at all.

Taken together: the mean proxy prediction is essentially unchanged after replay, and the planned prediction is realized even more accurately on the sampled sequence than on the top-1 sequence itself. Perfect alignment with the plan is therefore not required; even when the actual trajectory differs from the planned one, the basis for allocating budget along this path remains valid in our measurements.

As for why we do not use sampled nodes to estimate acceptance length: this is exactly what we deliberately avoid. If the probability of a realized sampled node itself is used as the proxy, the sampling outcome affects whether the node is retained, which breaks losslessness.

Reviewer_qKasOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses the problem of using dynamic trees with sampling for speculative decoding. Dynamic trees are valuable for speculative decoding because they let the drafter decide which paths to invest in based on the input query. However, prior attempts to use dynamic trees end up using deterministic token selection at different nodes in the dynamic tree. This paper, by contrast, proposes a two-phase approach to dynamic trees: the first phase determines the tree shape, while the second phase assigns tokens to nodes via non-deterministic sampling. The work is aided by the use of diffusion drafters that can use the intermediate computations from the first phase (the shape determination phase) and augment it with a low-overhead computation to determine the tokens that will occupy the dynamic tree.

Critical strengths

The paper's key innovation is the following core idea: decide on the tree's shape first, then fill it in with random samples, which keeps the output distribution from the drafting process exactly correct even under sampling. The paper demonstrates speedups across many settings.

Critical weaknesses

The gains are modest and not clearly explained. The approach adds complexity for improvements of a few percent over the deterministic tree. The paper also doesn’t provide sufficient intuition as to why the two-phase scheme with replay works; the planned shape is based on deterministic token generation, whereas the resampled tokens could be different, and the mismatch between the planned shape and the resampled tokens is not measured or analyzed.

Questions for authors

How much do you lose to the mismatch between the planned shape and the resampled tokens? For example, could you plan the topology using the sampled tokens’ scores, or measure how often deep branches end up with low-probability tokens?

How would the approach work with autoregressive drafters? Would they be impossible to use within your framework?

It might be worth comparing your scheme with the concurrent RheoSampling work.

5 comments
AuthorsOpenReview ↗

Response to Reviewer qKas (1/5)

We thank the reviewer for the review and for recognizing the core idea of Tsubame. Since the weakness and the questions mainly relate to where the gains come from, we start from this point and answer the reviewer's questions along the way.

Tree Structure, Sampling, and Verification

In tree speculative decoding, there are three distinct design choices that affect acceptance:

  1. Tree structure: the most intuitive one. A good tree structure yields higher acceptance.
  2. Sampling method: different sampling methods have different theoretical upper bounds on acceptance.
  3. Verification algorithm: given a sampling method, it determines how closely this upper bound can be approached. This is essentially an optimal transport problem.

In fact, the latter two contribute substantially to acceptance. A simple example illustrates this.

We test Domino on GSM8K and MT-Bench with a single layer and up to 3 candidates. We generate with the top-3 tokens as the actual candidates and compute the counterfactual acceptance rate at every step:

#CandidatesSamplingGSM8KMT-Bench
1Top191.27%74.02%
1Sample192.84%77.24%
2Top296.82%84.32%
2Top1+Sample198.01%87.80%
2Sample2 without replacement97.33%85.86%
3Top398.23%88.33%
3Top2+Sample199.01%91.22%
3Sample3 without replacement98.45%89.37%

Each sampling scheme is verified with its matching verifier: TopK with naive token matching; Sample1 with standard rejection sampling (RS); sampling without replacement (WoR) with recursive rejection sampling (RRS); and TopK+Sample1, i.e., Mixed sampling (Hu et al., ICLR 2025), with its OT-based verifier, which coincides with UniVer in the single-layer case. We use these abbreviations (WoR, RRS, Mixed, UniVer) below.

Top1 is weaker than Sample1 (GSM8K 91.27% vs. 92.84%, MT-Bench 74.02% vs. 77.24%). With multiple candidates, TopK is also generally weaker than schemes that contain a sampled candidate. Top1+Sample1, with only two candidates, already comes close to Top3 (GSM8K 98.01% vs. 98.23%, MT-Bench 87.80% vs. 88.33%).

That is, the sampling method by itself affects acceptance, and a good sampling method can reach comparable acceptance with a smaller budget. This is one source of the gain.

For verification, consider another example. With a single sampled candidate (Sample1), replacing Rejection Sampling (RS) with token matching drops acceptance from 92.84% to 90.65% on GSM8K and from 77.24% to 69.47% on MT-Bench, which is even below Top1. This gap is exactly what the verification algorithm contributes.

Intuitively, for a sampled node, RS can exploit the overlap between the target and draft distributions. For TopK nodes, the attainable acceptance is only the target probability mass of the TopK draft tokens, and every verifier degenerates to Naive, because there is no additional distributional overlap for the verifier to exploit.

As stated above, sampling determines the theoretical acceptance ceiling, and verification determines how closely this ceiling is approached. The TopK selection used by dynamic trees is, in most cases, not a good sampling scheme.

AuthorsOpenReview ↗

Response to Reviewer qKas (2/5)

The Conflict Between Dynamic Trees and Sampling

The problem is that the latter two (sampling and verification) cannot be directly combined with dynamic tree structures (EAGLE-2/3, DDTree, etc.), for a clear reason: if whether a sampled token stays in the tree is decided by the probability of its own realization, losslessness is very likely to be lost. Sections 2 and 4 of RheoSampling discuss this in detail. This is not limited to trees: a chain sometimes needs early stopping, and if the decision to verify a token depends on the probability of the token actually sampled, deciding retention based on the sampling outcome introduces selection bias and breaks losslessness (see the Appendix of DSpark).

Take the EAGLE-2-style expand-then-prune mechanism as an example: it first builds a candidate pool and then selects the top-N tokens through a single global prune (selecting the top-N tokens is equivalent to pruning with the N-th largest score as the threshold).

Consider what happens with naive sampling plus pruning in a simple example.

Let the vocabulary be {a, b, c}, the draft distribution q = (0.5, 0.3, 0.2), and the target distribution p = (0.2, 0.3, 0.5).

Standard procedure: sample a token x from q, accept it with probability min(1, p(x)/q(x)), and on rejection resample from the residual norm(max(p − q, 0)), i.e., standard single-token rejection sampling.

  • x = a (0.5): accepted w.p. 0.4 -> outputs a with 0.2; rejected with 0.3 -> the residual contains only c -> outputs c with 0.3
  • x = b (0.3): accepted w.p. 1 -> outputs b with 0.3
  • x = c (0.2): accepted w.p. 1 -> outputs c with 0.2

Total: (0.2, 0.3, 0.5) = p. Lossless.

Adding "pruning by the realized sampling probability": a token with q(x) < 0.3 is pruned, after which we sample directly from p, while the verifier still computes with q.

  • x = a and x = b are unchanged: a 0.2, b 0.3, c 0.3
  • x = c (0.2) is pruned and replaced by a sample from p: a 0.04, b 0.06, c 0.10

Total: (0.24, 0.36, 0.40), which is not equal to p.

The reason is that whether a token survives depends on its own sampling outcome, so the actual proposal distribution is no longer q, while the verifier still computes the acceptance probability and the residual with q. Global pruning in a tree follows exactly the same principle, only less visibly.

Strictly speaking, losslessness can still be enforced in some ways, e.g., building the draft tree from sampled tokens instead of TopK and verifying with token matching (see Appendix A.2 of DominoTree), but the actual speed is often worse than simply using a deterministic tree. This is what we keep emphasizing: the verification algorithm must match the sampling method. In this example, "selecting tokens while sampling" no longer permits OT-based verifiers that assume the original sampling distribution (e.g., the rejection sampling above); token matching remains a lossless fallback, but forfeits the acceptance benefit illustrated above.

Therefore, current mainstream dynamic tree designs (e.g., EAGLE-2/DDTree) only pursue the quality of the tree structure and cannot exploit the advantages of sampling and verification. Adding random sampling to a dynamic tree while preserving losslessness is by no means trivial. This also answers the reviewer's question of whether the topology could be planned using the sampled tokens' scores: not directly. Doing so makes the retention of a node depend on its own sampled realization, which introduces exactly the selection bias shown in the toy example above; verifiers that assume the original sampling distribution, such as RS and UniVer, then lose losslessness. We refer the reviewer to Section 2 of RheoSampling and the Appendix of DSpark.

This does not mean that a lossless stochastic dynamic tree is impossible within a single pass: RheoSampling achieves this by assigning sampled candidates prescribed proxy scores for structural decisions, at the cost of restricting where sampled candidates can be placed. Tsubame takes a different route, described next.

AuthorsOpenReview ↗

Response to Reviewer qKas (3/5)

Our Solution

The natural question is then: how can one obtain both the structural advantage of dynamic trees and the acceptance advantage of sampling and verification?

For AR drafters, methods such as RheoSampling insert a sampled token into the TopK expansion to exploit the extra acceptance brought by randomness. For diffusion-based drafters, we find a more direct solution. Because of the nature of diffusion drafters, probability distributions can be obtained very cheaply. Hence there is no need, as in RheoSampling, to decide within a single drafting pass both what the tree structure is and where sampled nodes are placed. Instead, two drafting passes directly decouple the tree structure from sampling and verification.

Decoupling the tree structure from sampling and verification means that sampling can be performed in any valid way, not limited to pure TopK or pure sampling without replacement.

Where Is the Mismatch, and How Much Does It Matter?

We analyze the tree in two parts: the single-chain case and the branching points.

First, for a single chain, the mismatch does not invalidate the planned budget allocation.

Using draft probabilities as a proxy for acceptance to guide tree construction is the basic premise of dynamic tree methods such as EAGLE-2 and DDTree. The same premise naturally extends to OT-based verifiers such as RS and Block Verification: at a given prefix, the expected acceptance of RS is the overlap between p and q, which does not depend on which token is actually sampled. A sampled path does change the subsequent prefixes, so two questions remain: whether the proxy itself changes along the new prefixes, and whether the planned prediction is realized on the sampled path. We verify both directly.

We run replay on a single chain with Domino. We use the top-1 draft sequence to predict the acceptance length (the planned prediction), then replay (resample and apply AR correction to obtain another draft sequence). As a post hoc diagnostic only (it is never used to decide the structure), we recompute the same prediction along the replayed prefixes, i.e., using the top-1 draft probability under each new prefix. Finally, we compute the expected acceptance length of the sampled sequence under RS or Block Verification, and of the planning top-1 draft under direct verification. We take the first 16 prompts of each of GSM8K, HumanEval, and MT-Bench.

The mean proxy prediction barely changes after replay.

DatasetPlanned prediction (top-1 path)Recomputed along the replayed prefixesChange
GSM8K10.45210.368−0.80%
HumanEval7.8897.807−1.04%
MT-Bench3.3743.322−1.52%

Although the replayed path differs from the planned one, the mean predicted acceptance length changes by only about 1%. The confidence-based proxy that dynamic trees use to estimate acceptance length remains stable before and after replay.

After replay, the gap between predicted and actual acceptance becomes smaller.

Values are expected acceptance lengths computed with the target distribution at matched starting prefixes (a paired counterfactual diagnostic).

DatasetPlanned prediction (basis of budget allocation)Top1, direct verification (no mismatch)Sample + RSSample + Block Verification
GSM8K10.4527.806 (overestimated by 33.9%)8.106 (overestimated by 28.9%)8.410 (overestimated by 24.3%)
HumanEval7.8895.870 (overestimated by 34.4%)6.013 (overestimated by 31.2%)6.286 (overestimated by 25.5%)
MT-Bench3.3742.754 (overestimated by 22.5%)2.756 (overestimated by 22.4%)2.855 (overestimated by 18.2%)

The planned prediction is closest to Block Verification, then RS, and farthest from Top1, the case with no mismatch at all.

Taken together: the mean proxy prediction is essentially unchanged after replay, and the planned prediction is realized even more accurately on the sampled sequence than on the top-1 sequence itself. Perfect alignment with the plan is therefore not required; even when the actual trajectory differs from the planned one, the basis for allocating budget along this path remains valid in our measurements.

As for why we do not use sampled nodes to estimate acceptance length: this is exactly what we deliberately avoid (see the toy example above). If the probability of a realized sampled node itself is used as the proxy, the sampling outcome affects whether the node is retained, which breaks losslessness.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.