Where Draft Trees Lose Target Mass: Exit-Guided Speculative Decoding

Shijing Hu; Xuancheng Ren; Zhihui Lu; Pan Zhou

cs.AIOct 8, 2026

Where Draft Trees Lose Target Mass: Exit-Guided Speculative Decoding

Authors: Shijing Hu, Xuancheng Ren, Zhihui Lu, Pan Zhou

Organizations: Fudan University · Singapore Management University

Abstract

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.

Figures & tables

Figure 1: Target-flow view of tree speculative decoding. Blue denotes selected draft prefixes, gray dashed branches omitted candidates, red target-probability flow, and green reallocated tree budget. (a) Under a finite budget, draft-score-based tree construction can miss target-important branches, causing target mass to exit the tree. (b) On a fixed tree, prior exact verifiers realize the same optimal acceptance law through node-wise draws or tests, whereas TEV realizes it by direct exit-node sampling followed by bonus-token sampling. (c) Exit-guided training reallocates budget toward high-exit boundaries, improving target-mass coverage and output-block length.

Figure 2: Visualization of a fixed-tree.

Temperature = 0
		MT-Bench		HumanEval		GSM8K		MATH-500		Average
Model	Method	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$
Qwen3-4B	DDTree	3.81	5.41	5.71	8.13	5.65	8.48	6.83	9.16	5.50	7.80
	Draft-OPD	4.16	5.73	5.96	8.35	6.11	9.30	7.02	10.14	5.81	8.38
	ExitTrain + TEV	4.28	6.17	6.09	8.74	6.91	10.22	7.23	10.26	6.13	8.85
Qwen3-8B	DDTree	3.75	5.54	5.83	8.01	5.88	8.49	6.23	9.76	5.43	7.95

Table 1: Speedup ratio (

SR

) and average output-block length including the bonus token (

\tau

) on MT-Bench, HumanEval, GSM8K, and MATH-500. All tree-based systems share the same builder and tree budget

B=64

. ExitTrain + TEV combines our exit-guided drafter with TEV.

	MT-Bench		HumanEval		GSM8K		MATH-500		Average
Draft training objective	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$
Temperature = 0
Original DFlash drafter	3.81	5.41	5.71	8.13	5.65	8.48	6.83	9.16	5.50	7.80
Finetuned DFlash drafter	3.97	5.71	5.83	8.36	6.33	9.54	6.91	9.83	5.76	8.36
Prefix weight $P(v)$	4.05	5.82	5.99	8.43	6.07	9.25	6.71	9.33	5.71	8.21
Exit weight $w(v)$ (ours)	4.28	6.17	6.09	8.74	6.91	10.22	7.23	10.26	6.13	8.85

Table 2: Effect of the draft-training objective on Qwen3-4B. All three trained drafters share the initialization, the open-perfectblend mixture, the compute budget, the tree builder, and the budget

B=64

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Temperature = 0.6
		MT-Bench		HumanEval		GSM8K		MATH-500		Average
$B$	Verifier	ms $\downarrow$	red.	ms $\downarrow$	red.	ms $\downarrow$	red.	ms $\downarrow$	red.	ms $\downarrow$	red.
32	Predraw	1.371	—	1.435	—	1.428	—	1.393	—	1.407	—
32	TEV	1.204	12.2%	1.245	13.2%	1.239	13.2%	1.211	13.0%	1.225	12.9%
64	Predraw	1.392	—	1.487	—	1.443	—	1.488	—	1.453	—
64	TEV	1.212	12.9%	1.268	14.7%	1.193	17.3%	1.257	15.5%	1.232	15.2%

Appendix

Table 3: Verifier-stage latency per decoding cycle on Qwen3-4B across tree budgets. The measured interval covers verifier decision and cache commit and excludes the shared target-model tree forward pass. For each

B

, both verifiers use the same drafter, builder, and realized trees.

		MT-Bench		HumanEval		GSM8K		MATH-500		Average
Drafter	Verifier	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$
Original DFlash	Predraw	3.44	5.04	5.22	7.53	5.48	7.85	5.65	7.88	4.95	7.08
Original DFlash	TEV	3.47	5.07	5.22	7.52	5.51	7.88	5.67	7.90	4.97	7.09
Exit-trained DFlash	Predraw	3.95	5.86	5.61	8.05	6.44	9.23	6.22	9.06	5.55	8.05
Exit-trained DFlash	TEV	3.98	5.86	5.64	8.06	6.47	9.25	6.26	9.08	5.59	8.06

Appendix

Table 4: Crossed drafter–verifier evaluation on Qwen3-4B at

T=1

. Each cell reports end-to-end speedup ratio (

SR

) and average output-block length including the bonus token (

\tau

). The builder and tree budget

B=64

are fixed across all four combinations.

Temperature = 0
		MT-Bench		HumanEval		GSM8K		MATH-500		Average
$B$	Method	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$	$SR\uparrow$	$\tau\uparrow$
32	DDTree	3.69	5.19	5.47	7.74	5.40	8.03	6.50	8.74	5.26	7.43
	Draft-OPD	3.91	5.32	5.60	7.82	5.87	8.92	6.84	9.70	5.56	7.94
	ExitTrain + TEV	4.11	5.87	5.72	8.22	6.68	9.78	6.94	9.77	5.86	8.41
64	DDTree	3.81	5.41	5.71	8.13	5.65	8.48	6.83	9.16	5.50	7.80

Appendix

Table 5: Qwen3-4B performance across tree budgets on MT-Bench, HumanEval, GSM8K, and MATH-500. ExitTrain is trained at

B=64

and evaluated at every budget without retraining.

Explore similar work

Cost-Aware Diffusion Draft Trees for Speculative Decoding
Jun 1, 2026Shuai Zhang, Huachuan Qiu, Hongliang He +1Cost-Aware Inference Speculative Decoding for Diffusion Language Models
1Zhejiang University · 2Westlake University
Tsubame: Tree Replay for Diffusion-Based Speculative Decoding
Sep 27, 2026Yepeng Weng, Qiao Hu, Takehisa YairiSpeculative Decoding for Diffusion Language Models Speculative Decoding
The University of Tokyo · National Center for Mathematics and Interdisciplinary Sciences (NCMIS), AMSS, CAS
UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding
May 6, 2026Yepeng Weng, Qiao Hu, Takehisa YairiSpeculative Decoding LLM Inference Acceleration
The University of Tokyo · 2Lenovo AI Technology Center · National Center for Mathematics and Interdisciplinary Sciences (NCMIS), AMSS, CAS

Jun 1, 2026, cs.CLJ/K move · Enter open · S save

Cost-Aware Diffusion Draft Trees for Speculative Decoding

Shuai Zhang, Huachuan Qiu, Hongliang He, Yong Dai

1Zhejiang University · 2Westlake University

Cost-Aware Inference Speculative Decoding for Diffusion Language Models Speculative Decoding Diffusion Language Model Decoding

Open paper AskPDF arXiv

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 \textbf{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 \emph{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.

Abstract

Explore similar work

Cost-Aware Diffusion Draft Trees for Speculative Decoding

Tsubame: Tree Replay for Diffusion-Based Speculative Decoding

UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding