Block-diffusion drafters propose a whole block of tokens in one forward pass, and draft trees built from their position-wise marginals increase the expected accepted length of speculative decoding. Every tree node occupies a query row in target verification, so under concurrent serving low-yield branches compete with other requests for verification capacity. Existing tree methods select verified nodes by draft probability under a fixed or cost-selected per-request budget, and thus always retain a prefix of the drafter's ranking. We present D3Tree, which learns which nodes of a block-diffusion draft tree are worth verifying. A tree-size head with 2H+2 parameters predicts each candidate's conditional survival from the draft state, the candidate embedding, and its draft log-probability. Thresholding the product of these scores along parent chains yields an ancestor-closed subtree whose size adapts to each request and decoding round. The head is trained on a frozen drafter with conditional labels on the full candidate tree; an optional joint mode also steers the drafter toward the retained reference path. At serving time, D3Tree verifies whole trees under light load and, under heavy load, allocates one batch-wide node budget by predicted survival, sized to the target's matrix-multiplication tiles. Retained trees share one ancestor-masked target pass, while construction, pruning, and scheduling run on the GPU and overlap with the host. Across six vision-language verifiers and 17 text and multimodal benchmarks, D3Tree is fastest in 70 of 72 load settings, with 3.2-4.0x speedup over autoregressive decoding for one request and 1.3-1.8x at 64 concurrent requests, where fixed-budget trees fall below autoregressive speed. Under a time-varying arrival trace, it has the lowest mean end-to-end latency in every arrival phase.
Figures & tables
Fig. 1: Verification selection in closely related methods. (a) Each method on one candidate space; numbers give the best-first order by draft path score, and W counts target query rows, including the root. Chips mark the selection signal. (b) CaDDTree and D3Tree under light load (one request) and heavy load ( R=4 requests in one target pass whose matrix multiplications process tiles of s=16 rows); below the trees, each step’s query rows fill the tiles (dashed: idle; red: a second tile). CaDDTree sizes each tree from a latency table profiled offline for a single request, regardless of the current load, so here it verifies B∗=4 nodes per request at either load: rows stay idle under light load and spill into a second tile under heavy load. D3Tree sets the size from the current load: the whole tree when the tile has room, and otherwise the 12 nodes of highest survival across the batch, which fill one tile.
Fig. 2: D3Tree in one decoding round (top) and in training (bottom), on a running example with B=7 . (a) One drafter pass yields position-wise marginals pd . (b) Best-first construction keeps the B highest-scoring prefixes; numbers give their order. (c) The tree-size head scores each depth–token pair, so repeated pairs share q . (d) Parent-chain products S (above the nodes) are thresholded: N=4 nodes survive and the target verifies W=5 rows. (e) Under the ancestor mask the target accepts tea with lemon , rejects the retained sibling and , emits the bonus token, and commits the KV rows of the accepted path. Survival labels come from the full tree and are all that head-only fitting uses; in the optional joint mode, the coverage L and frontier F of the pruned tree weight the token loss. Discrete construction and pruning are stop-gradient (sg). The threshold δ=0.25 is illustrative.
Fig. 3: Survival landscape of the example in Fig. 2 . Each node sits at its depth and its path survival S(v) on a log scale; edge labels give the conditional score q that multiplies S , so no node rises above its parent. At δ=0.25 , N=4 of the B=7 candidates survive: the depth-3 path is kept, whereas milk , second in the best-first order, is pruned. The lower threshold 0.12 keeps a superset, here all B nodes. Both thresholds are illustrative; Section III-E chooses the threshold of each step.
Fig. 4: Multi-request serving with D3Tree (illustrative, R=4 , B=7 , Rfull=2 ). (a) Every request’s full candidate tree on its path survival S(v) (log scale; edges join parents and children). Above Rfull one threshold serves the whole batch: δt is the Ntot -th largest survival, with Ntot from ( 33 ) (here nˉ=3 and a tile of s=16 rows). Requests keep different numbers of nodes, R2 only its root, and the R+Ntot=16 rows fill one tile instead of the R(B+1)=32 of full trees. (b) All retained trees share one target pass. Each query row attends to its request’s committed prefix through the block table and to its own ancestors; rows of other requests are masked. KV slots stay sequential while RoPE uses tree depth. (c) Each request accepts a path independently and commits Ai+1 tokens; accepted rows are compacted, and GDN layers replay the accepted path into the request’s state slot.
Text benchmarks
Multimodal benchmarks
Model
Strategy
Budget
Math
Code
Chat
Document & OCR
General vision
Capt. & chat
GSM8K
MATH
AIME
HEval
MBPP
LCB
MT-B
ODoc
OCR2
DVQA
olmO
CXiv
TVQA
MMMU
GQA
COCO
MMMT
Q3.5-4B
DFlash
5.35
6.63
6.56
5.43
5.12
4.68
3.81
3.08
3.77
4.20
4.86
5.30
3.70
4.33
3.69
3.59
4.29
DSpark
N=15
4.95
6.22
5.94
5.10
4.61
4.25
3.50
2.86
3.43
3.77
4.64
4.62
3.24
3.86
3.24
3.09
3.84
DDTree
6.09
7.46
7.59
6.25
5.78
5.51
4.58
3.45
4.43
4.80
5.61
6.00
4.34
5.17
4.42
4.31
5.07
CaDDTree
6.08
7.42
7.70
6.23
5.81
5.49
4.53
3.42
4.44
4.82
5.64
6.01
4.35
5.14
4.44
4.29
5.10
TABLE I: Accepted length τ per benchmark at concurrency R=1 , greedy decoding. All strategies for a verifier share the same drafter and runtime. DFlash verifies the full linear draft; DSpark a prefix chosen by the drafter’s length head; DDTree the full best-first tree of B=15 nodes; CaDDTree a cost-selected prefix of its best-first tree; D3Tree prunes the B=15 tree under its load-dependent node budget. Benchmarks: GSM8K, MATH-500, AIME25, HumanEval, MBPP, LiveCodeBench, MT-Bench, OmniDocBench, OCRBench-v2, DocVQA, olmOCR, CharXiv, TextVQA, MMMU-Pro, GQA, COCO Caption, and MM-MT-Bench. Highest per verifier and benchmark in bold.
Text benchmarks
Multimodal benchmarks
Model
Strategy
Budget
Math
Code
Chat
Document & OCR
General vision
Capt. & chat
GSM8K
MATH
AIME
HEval
MBPP
LCB
MT-B
ODoc
OCR2
DVQA
olmO
CXiv
TVQA
MMMU
GQA
COCO
MMMT
Q3.5-4B
DFlash
3.38 ×
4.07 ×
4.07 ×
3.40 ×
3.23 ×
2.92 ×
2.40 ×
1.99 ×
2.41 ×
2.40 ×
3.08 ×
3.26 ×
2.32 ×
2.71 ×
2.32 ×
2.25 ×
2.64 ×
DSpark
N=15
3.25 ×
3.98 ×
3.79 ×
3.37 ×
2.97 ×
2.74 ×
2.24 ×
1.88 ×
2.24 ×
2.27 ×
3.00 ×
2.95 ×
2.07 ×
2.49 ×
2.12 ×
2.03 ×
2.48 ×
DDTree
3.70 ×
4.34 ×
4.39 ×
3.68 ×
3.42 ×
3.23 ×
2.72 ×
2.09 ×
2.67 ×
2.55 ×
3.31 ×
3.46 ×
2.53 ×
3.04 ×
2.61 ×
2.59 ×
2.95 ×
CaDDTree
2.77 ×
3.36 ×
3.37 ×
2.81 ×
2.57 ×
2.49 ×
2.05 ×
1.60 ×
2.03 ×
1.98 ×
2.57 ×
2.65 ×
1.92 ×
2.27 ×
1.95 ×
1.90 ×
2.19 ×
TABLE II: Speedup over AR per benchmark at concurrency R=1 : output throughput divided by that of AR for the same verifier, GPU, and prompts. Strategies and benchmark abbreviations as in Table I . Best per verifier and benchmark in bold.
Model
Strategy
Budget
Text benchmarks
Multimodal benchmarks
R=1
R=4
R=8
R=16
R=32
R=64
Avg. τ
R=1
R=4
R=8
R=16
R=32
R=64
Avg. τ
Q3.5-4B
DFlash
3.35 ×
3.33 ×
2.92 ×
1.92 ×
1.31 ×
1.02 ×
5.36
2.54 ×
2.39 ×
2.09 ×
1.40 ×
1.01 ×
0.78 ×
4.06
DSpark
N=15
3.19 ×
3.31 ×
3.05 ×
2.42 ×
1.78 ×
1.40 ×
4.95
2.35 ×
2.34 ×
2.18 ×
1.82 ×
1.41 ×
1.17 ×
3.66
DDTree
3.64 ×
3.49 ×
2.89 ×
1.83 ×
1.20 ×
0.94 ×
6.16
2.78 ×
2.55 ×
2.13 ×
1.40 ×
0.97 ×
0.75 ×
4.76
CaDDTree
2.77 ×
2.72 ×
2.44 ×
1.86 ×
1.30 ×
1.03 ×
6.16
2.11 ×
2.05 ×
1.82 ×
1.39 ×
1.03 ×
0.83 ×
4.75
D3Tree
B=15
4.15 ×
3.78 ×
3.09 ×
2.60 ×
1.94 ×
1.56 ×
5.57
3.06 ×
2.69 ×
2.34 ×
1.89 ×
1.48 ×
1.21 ×
4.37
TABLE III: Speedup over AR at concurrency R and mean accepted length τ (Avg. over benchmarks and loads), greedy decoding. Strategies as in Table I . Best speedup per verifier and column in bold.
Fig. 5: Every strategy serving 200 requests at a fixed concurrency of 64 (Q3.5-9B, RTX A6000; all requests are due at once, as in the sweeps of Table III ). (a) Each curve ends, with a dot, when the last request of that run finishes. From top: requests completed; requests in flight; tokens per target pass, i.e., the roots and verified draft tokens of all decoding requests; verified draft tokens per request and decoding round; and accepted length τ (sliding means over about 12, 12, and 28 s). (b) Output throughput over the run and the time until all 200 requests have finished. (c) Distribution of the latency from sending a request to its last token.
Fig. 6: Every strategy serving the same time-varying load. (a) Each curve ends, with a dot, when the last request of that run finishes. From top: one tick per arriving request; requests in the system (in flight or waiting at the client; 4-s moving average; the axis is compressed above 100); and, as in Fig. 5 , tokens per target pass, verified draft tokens per request and decoding round, and accepted length τ . (b) Mean verified draft tokens and accepted length τ over the decoding steps with at most 8 (open) and at least 16 (filled) requests in flight; AR is omitted. (c) Mean end-to-end latency, from arrival to the last token, of the requests arriving in each phase (log scale).
Model
Strategy
Budget
Speedup over AR at concurrency R
Accepted length τ / verified draft tokens at concurrency R
1
4
8
16
32
64
1
4
8
16
32
64
Q3.5-4B
N=5
2.44 ×
2.41 ×
2.34 ×
2.00 ×
1.58 ×
1.29 ×
3.67 / 5.0
3.67 / 5.0
3.67 / 5.0
3.66 / 5.0
3.66 / 5.0
3.67 / 5.0
N=7
2.66 ×
2.65 ×
2.52 ×
2.04 ×
1.48 ×
1.19 ×
4.06 / 7.0
4.05 / 7.0
4.07 / 7.0
4.05 / 7.0
4.06 / 7.0
4.07 / 7.0
DFlash
N=15
2.88 ×
2.78 ×
2.45 ×
1.63 ×
1.15 ×
0.89 ×
4.61 / 15.0
4.58 / 15.0
4.60 / 15.0
4.59 / 15.0
4.60 / 15.0
4.59 / 15.0
DSpark
N=15
2.71 ×
2.74 ×
2.55 ×
2.09 ×
1.58 ×
1.28 ×
4.19 / 5.5
4.20 / 5.5
4.20 / 5.5
4.19 / 5.5
4.19 / 5.5
4.18 / 5.5
B=15
3.14 ×
2.94 ×
2.46 ×
1.59 ×
1.07 ×
0.84 ×
5.35 / 15.0
5.35 / 15.0
5.34 / 15.0
5.33 / 15.0
5.32 / 15.0
5.35 / 15.0
TABLE IV: Every strategy at every verification budget over all 17 benchmarks: speedup over AR, and accepted length τ / verified draft tokens per request and decoding round (tree nodes, root excluded), at each concurrency R . DFlash verifies the first N tokens of the linear draft (budget N ); DSpark a prefix of at most N=15 tokens chosen by the drafter’s length head; DDTree verifies the full best-first tree of B nodes, CaDDTree a cost-selected prefix of its best-first tree, and D3Tree prunes the B -node tree under its load-dependent node budget. Best speedup per verifier and column in bold.
Model
Budget
Speedup over AR at concurrency R
Accepted length τ / verified draft tokens at concurrency R
1
4
8
16
32
64
1
4
8
16
32
64
Q3.5-4B
B=15
3.52 ×
3.14 ×
2.66 ×
2.20 ×
1.70 ×
1.37 ×
5.33 / 15.0
5.35 / 15.0
4.72 / 7.5
4.75 / 7.5
4.52 / 5.9
4.52 / 5.9
B=31
3.44 ×
2.80 ×
2.58 ×
2.10 ×
1.72 ×
1.39 ×
5.77 / 31.0
5.77 / 31.0
4.72 / 7.8
4.74 / 7.7
4.52 / 6.0
4.53 / 6.0
B=63
3.10 ×
1.81 ×
2.32 ×
2.00 ×
1.67 ×
1.35 ×
6.07 / 63.0
6.04 / 63.0
4.74 / 8.2
4.74 / 8.1
4.54 / 6.2
4.54 / 6.2
Q3.5-9B
B=15
3.73 ×
3.05 ×
2.58 ×
2.17 ×
1.60 ×
1.28 ×
5.20 / 15.0
5.20 / 15.0
4.61 / 7.4
4.62 / 7.4
4.41 / 5.8
4.40 / 5.9
B=31
3.63 ×
2.73 ×
2.61 ×
2.12 ×
1.63 ×
1.30 ×
5.65 / 31.0
5.66 / 31.0
4.62 / 7.6
4.62 / 7.6
4.40 / 6.0
4.40 / 6.0
TABLE V: D3Tree at construction budgets B∈{15,31,63} with the same allocation table, columns as in Table IV : speedup over AR and accepted length τ / verified draft tokens per request and decoding round, over all 17 benchmarks. Best speedup per verifier and column in bold.
GPU
Model
Strategy
Budget
Text benchmarks
Multimodal benchmarks
R=1
R=4
R=8
R=16
R=32
R=64
Avg. τ
R=1
R=4
R=8
R=16
R=32
R=64
Avg. τ
RTX 5090
Q3.5-4B
DFlash
3.02 ×
3.18 ×
2.90 ×
2.06 ×
1.35 ×
0.98 ×
5.35
2.21 ×
2.30 ×
2.10 ×
1.52 ×
1.01 ×
0.79 ×
4.05
DSpark
N=15
2.79 ×
2.94 ×
2.92 ×
2.32 ×
1.69 ×
1.33 ×
4.94
2.04 ×
2.11 ×
2.16 ×
1.76 ×
1.32 ×
1.11 ×
3.66
DDTree
3.12 ×
3.15 ×
2.81 ×
1.79 ×
1.10 ×
0.83 ×
6.15
2.36 ×
2.40 ×
2.10 ×
1.41 ×
0.89 ×
0.68 ×
4.75
CaDDTree
2.31 ×
2.49 ×
2.33 ×
1.74 ×
1.22 ×
0.95 ×
6.15
1.78 ×
1.86 ×
1.74 ×
1.34 ×
0.95 ×
0.76 ×
4.75
D3Tree
B=15
3.62 ×
3.61 ×
3.18 ×
2.43 ×
1.72 ×
1.35 ×
5.56
2.66 ×
2.61 ×
2.35 ×
1.83 ×
1.35 ×
1.08 ×
4.38
TABLE VI: Speedup over AR and Avg. τ on an RTX 5090 (32 GB) and an A800 (80 GB), with the protocol of Table III . On the A800, D3Tree uses an allocation table retuned for that GPU at R≥16 .
Tree-based speculative decoding verifies multiple draft continuations in one target-model pass, but finite trees built from draft scores face a fundamental draft-target mismatch. We ask whether better exact verification can increase acceptance on a fixed tree and how target feedback can improve the tree itself. Through a target-flow view, we identify a canonical exit law and prove that one plus target coverage sharply bounds the expected output-block length, including the bonus token, of any exact path verifier. All optimal verifiers share the same exit and bonus-token law, already attained by representative predraw-and-follow and sequential residual verifiers. This yields Tree Exit Verification (TEV), an exact, level-parallel procedure using one exit-node decision and one bonus-token decision. The exit law also identifies missing target probability, providing node-level feedback for Exit-Guided Draft-Tree Training (ExitTrain) on inference-time draft trees. Experiments across dialogue, code, and mathematical reasoning validate fixed-tree equivalence: ExitTrain increases average output-block length by 13%, while TEV reduces verifier-stage latency by 15%, yielding a 14% end-to-end speedup over DDTree. Our results distinguish two opportunities: better draft trees for higher acceptance and more direct verification for lower latency. Code: https://github.com/hsj576/TEV.
Shijing Hu, Xuancheng Ren, Zhihui Lu +1
Fudan University · Singapore Management University
Speculative decoding accelerates inference by having a lightweight drafter propose tokens verified in parallel by the target language model. Block diffusion drafters such as DFlash generate an entire draft block in one pass, yielding per-position marginals; DDTree uses these to build a candidate tree that maximizes expected acceptance length under a fixed node budget. We observe, however, that acceptance length is non-decreasing in budget: it always favors larger trees regardless of verification cost, offering no principled basis for budget selection. We introduce CaDDTree (Cost-aware Diffusion Draft Tree), a method that directly optimizes token throughput (expected tokens generated per unit time) by jointly selecting the tree structure and node budget. We model draft and verification latencies explicitly, show that the throughput objective decomposes into a per-round one-dimensional search over the budget, and prove that under a convex verification cost the throughput function is unimodal, enabling an efficient greedy stopping rule. CaDDTree requires no offline budget search, adapting the budget each round from the current per-position distributions and verification cost. Experiments on Qwen3-4B and Qwen3-8B across eight benchmarks spanning reasoning, coding, and instruction-following tasks show that \caDDTree{} matches or surpasses DDTree with oracle budget selection on nearly all tasks.
Speculative decoding speeds up language models by having a lightweight drafter propose future tokens that the target model verifies in parallel. Block diffusion drafters such as DFlash predict an entire block in one forward pass, and DDTree builds draft trees directly from their per-position distributions. Each distribution implicitly assumes that the drafter's own greedy continuation is accepted, whereas a draft tree improves over a chain only on branches that leave this greedy path. Once a path forks, the drafter's top-1 accuracy drops from 89% to 18% and its top candidates often miss the true token. Re-running the drafter from the fork token largely restores its accuracy, showing that the errors stem from conditioning on an outdated prefix rather than from limited model capacity. In this paper, we introduce DForkTree, a training-free method that re-anchors each branch on its own tokens. It adjusts the drafter's scores with pointwise mutual information from target-generated n-grams, weighted more heavily after a fork, and a layer-wise GPU search recovers the exact optimal tree under these scores. On Qwen3.5-4B and 9B, DForkTree outperforms all baselines on every benchmark, by up to 41.5% over DFlash and 15.1% over DDTree, with average speedups of up to 4.75x over autoregressive decoding.
Zhicheng Zheng, Cheng Zhang, Chenkai Tang +1
The Hong Kong University of Science and Technology (Guangzhou) · Tsinghua University