Harel Lidar

Paper summary · Aug 2026

Accelerating Speculative Decoding with Block Diffusion Draft Trees

Summary of Accelerating Speculative Decoding with Block Diffusion Draft Trees

An intuitive idea that I, along with presumably anyone that has thought about what is the next step for spec-dec post block diffusion models, has probably had - replace blocks diffusion, which is a single chain with a tree that maximizes the expected acceptance length given a budget B. It works in the following manner:

  1. Run the block diffusion drafter once to obtain per-position distributions for the next L draft positions after b.
  2. Build a draft tree with B nodes from those distributions. The node budget B controls how many candidate tokens the verifier (target model) evaluates.
  3. Compile the tree into input tensors for the target model and run one target-model forward pass with tree attention.
  4. Walk the tree, at each step, use the target model’s decoding rule to choose the next token and check whether it matches a child in the tree; accept the matched drafted path, and carry the first unmatched target token (the next bonus token) to the next round

The idea as mentioned is not novel nor very ground-breaking. The key thing here is about the implementation and execution, how efficient can one make this. To this end, the authors here introduced the following innovations:

max⁡T: ∣T∣≤B, T valid EY1:L∼p(⋅∣c,b)[αT(Y1:L)],(5)\max_{T:\,|T|\le B,\ T\text{ valid}} \ \mathbb{E}_{Y_{1:L}\sim p(\cdot\mid c,b)}\big[\alpha_T(Y_{1:L})\big], \tag{5}

however, is infeasible to optimize as it depends on the target-conditioned continuation probabilities, which are unavailable when the tree is constructed. They therefore use a surrogate based on the factorized distribution induced by the block diffusion drafter Q(⋅∣c,b)Q(\cdot \mid c, b), constructed solely from the per-position marginals {qi}i=1L\{q_i\}_{i=1}^{L}. This surrogate does not require full path-conditioned probabilities, which are unavailable from a single block diffusion forward pass.

max⁡T: ∣T∣≤B, T valid EY1:L∼Q(⋅∣c,b)[αT(Y1:L)].(6)\max_{T:\,|T|\le B,\ T\text{ valid}} \ \mathbb{E}_{Y_{1:L}\sim Q(\cdot\mid c,b)}\big[\alpha_T(Y_{1:L})\big]. \tag{6}

They show that it is equivalent to greedily choosing the Top-B prefixes where the probability is given by multiplying the full ancestor tree up to said node. Further, they show that this is the optimal tree that can be constructed given the surrogate predictions along.