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 .