TreeGraft: Adaptive Multi-Drafter Grafting for Tree-Based Speculative Decoding

Jiaming Fan; Daming Cao; Canchen Huang; Jiale Fu; Jin Zhang; Junjie Gao; Kai Yang; Xiangzhong Luo

cs.CLMay 28, 2026

TreeGraft: Adaptive Multi-Drafter Grafting for Tree-Based Speculative Decoding

Authors: Jiaming Fan, Daming Cao, Canchen Huang, Jiale Fu, Jin Zhang, Junjie Gao, Kai Yang, Xiangzhong Luo,

Organizations: Key Laboratory of New Generation Artificial Intelligence Technology and Its Interdisciplinary Applications (Southeast University), Ministry of Education, China · Southeast University · Ant Group · Nanjing University of Information Science and Technology

Abstract

Speculative decoding accelerates large language model inference through a draft-then-verify paradigm. Building on this, tree-structured methods improve inference by organizing proposals into multiple candidate paths, increasing the accepted length. However, existing tree-structured methods use a single drafter for all drafting steps, creating a dilemma: a smaller drafter is fast but yields lower-quality trees, whereas a larger drafter improves tree quality but suffers from high latency. To address this, we propose TreeGraft, a multi-drafter framework in which drafters of different costs jointly construct a shared draft tree. TreeGraft uses the stronger drafter to rescore candidates by updating scores assigned by the weaker drafter, reselect grafting positions, and recover promising paths left unexplored. It also integrates stronger drafter expansions non-destructively, preserving existing branches that may still be accepted by the target model. Together, these designs improve the quality of the shared draft tree. To control the drafting cost, TreeGraft introduces a lightweight scheduler distilled from an offline value system to decide when to call the stronger drafter. Across 10 model pairs and 6 benchmarks, TreeGraft outperforms the better of the two fixed single-drafter endpoint strategies by 15.1% on average, reaching a maximum gain of 26.6%. Our code is available at https://github.com/fjm9933/TreeGraft.

Figures & tables

Figure 1: Overview of TreeGraft. (a) Standard single-drafter expansion is contrasted with TreeGraft. (b–d) The resulting design is organized around three questions: where to graft, how to graft, and when to graft.

Figure 2: Illustration of expanded grafting-position selection under a middle–small–middle schedule. Panels (1) and (3) show that middle drafter steps reconsider earlier nodes in the shared tree, while panel (2) shows that the small drafter step only expands nodes generated in the previous step.

Target–Middle	Five-task average			MT-Bench			Overall average			Improvement
Target–Middle	TG	S	M	TG	S	M	TG	S	M	TG vs S	TG vs M
Qwen3-32B/1.7B	1.49	1.20	1.27	1.51	1.26	1.21	1.49	1.21	1.26	23.1%	18.3%
Qwen3-32B/0.6B	1.47	1.20	1.19	1.46	1.26	1.18	1.47	1.21	1.19	21.5%	23.5%
Qwen3-32B/8B	1.39	1.20	1.06	1.43	1.26	1.08	1.40	1.21	1.06	15.7%	32.1%
LLaMA-70B/1B	2.30	1.44	2.32	2.26	1.44	2.21	2.30	1.44	2.30	59.7%	0.0%
LLaMA-70B/3B	1.95	1.44	1.96	1.91	1.44	1.91	1.95	1.44	1.95	35.4%	0.0%

Table 1: Online evaluation results. Values are speedups over autoregressive target decoding. TG denotes TreeGraft; S and M denote All Small and All Mid. The five-task average is the arithmetic mean over Alpaca, GSM8K, HumanEval, NQ, and CNN/DM; the overall average includes MT-Bench. Blue rows denote held-out target–middle pairs, green columns denote the held-out MT-Bench task, and orange cells denote their intersection. For LLaMA pairs, 70B, 8B, 3B, and 1B refer to LLaMA 3.3-70B, LLaMA 3.1-8B, LLaMA 3.2-3B, and LLaMA 3.2-1B, respectively. The full speedups are in Table 11 .

Panel of Figure 3 — Figure 3: Setting-wise percentage speedup gains of TreeGraft over All Small (left) and All Mid (right). Cell labels show gains computed from the reported two-decimal speedups. An asterisk (*) marks held-out model pairs and MT-Bench.

Figure 4: Step-wise middle drafter usage learned by the TreeGraft online scheduler under the value system setting. Each subplot corresponds to one target–middle model pair. The y-axis shows the middle drafter call rate at each drafting step, averaged over the five fit datasets. Higher values indicate a stronger tendency to call the middle drafter at that step.

Method	Q32B/0.6B GSM8K		Q32B/0.6B CNN/DM		L70B/1B GSM8K		L70B/1B CNN/DM		Average
Method	Speedup ( $\times$ )	$A$	Speedup ( $\times$ )	$A$	Speedup ( $\times$ )	$A$	Speedup ( $\times$ )	$A$	Speedup ( $\times$ )	$A$
CSD	0.75	0.82	0.78	0.72	1.07	0.90	1.14	0.78	0.94	0.81
w/o EG	1.49	1.76	0.85	1.56	1.72	1.92	1.34	1.97	1.35	1.80
w/o ND	1.44	1.69	0.82	1.18	1.33	1.64	1.21	1.37	1.20	1.47
TreeGraft	1.55	1.84	0.95	2.15	1.80	2.18	1.42	2.52	1.43	2.17

Table 2: Ablation of grafting mechanism components. All variants use the same fixed middle drafter schedule

[1,0,1,0,1]

, i.e., the middle drafter participates only at drafting steps 1, 3, and 5. Speedup is relative to autoregressive decoding with the target model.

A

denotes average accepted length.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Signal	Definition	Meaning
$\mathrm{depth\_before}$	$\displaystyle\frac{1}{\|\mathcal{F}_{k}\|}\sum_{v\in\mathcal{F}_{k}}d(v)$	Average depth of the current frontier
$\mathrm{leaf\_ratio\_before}$	$\displaystyle\frac{1}{\|\mathcal{F}_{k}\|}\sum_{v\in\mathcal{F}_{k}}\mathbf{1}[\|\mathrm{child}(v)\|=0]$	Ratio of leaf nodes in the current frontier
$\mathrm{pre\_reselect\_depth\_delta}$	$\displaystyle\frac{1}{\|\widehat{\mathcal{F}}_{k}\|}\sum_{v\in\widehat{\mathcal{F}}_{k}}d(v)-\frac{1}{\|\mathcal{F}_{k}\|}\sum_{v\in\mathcal{F}_{k}}d(v)$	Change in average frontier depth after reselection preview
$\mathrm{pre\_reselect\_cands}$	$\displaystyle\|\mathcal{R}_{k}\|$	Number of candidate nodes in the reselection preview
$\mathrm{max\_depth\_before}$	$\displaystyle\max_{v\in\mathcal{F}_{k}}d(v)$	Maximum depth of the current frontier
$\mathrm{collapse\_debt}$	$\displaystyle\max(0,\;-\mathrm{pre\_reselect\_depth\_delta})$	Amount by which the preview frontier becomes shallower

Appendix

Table 3: Candidate tree signals used for state selection.

Method	Throughput (tok/s)
Best enumerated scheduling trajectory in the call/skip space	24.78
TreeGraft online scheduler	24.30

Appendix

Table 4: Scheduler distillation evaluation on scheduling traces. The online scheduler closely approximates the highest throughput achieved by the enumerated scheduling trajectories in the call/skip space.

Method	Offline mean actual gap	Overall speedup
Direct value-system planner	0.3718	0.95 $\times$
TreeGraft scheduler	0.4826	1.60 $\times$

Appendix

Table 5: Ablation on direct value-system planning. A smaller offline mean actual gap indicates a closer match to the offline enumerated oracle. Overall speedup is measured in real online evaluation relative to autoregressive target decoding.

Model family	Model	Per-call latency (ms)
LLaMA	LLaMA 3.3-70B-Instruct target	$122.2$
LLaMA	LLaMA 3.2-1B-Instruct	$29.1$
LLaMA	LLaMA 3.1-8B-Instruct	$48.9$
Qwen	Qwen3-32B target	$77.6$
Qwen	Qwen3-0.6B	$44.8$
Qwen	Qwen3-8B	$55.0$

Appendix

Table 6: Per-call latency of representative neural drafters and target models under the online evaluation setting in Section 5 .

Small drafter	Type	Per-call latency (ms)
N-gram (ours)	Lookup-based	$0.92$
LLaMA 3.2-1B-Instruct	Neural LLM	$29.1$
Qwen3-0.6B	Neural LLM	$44.8$

Appendix

Table 7: Per-call latency of candidate small drafter choices under the online evaluation setting in Section 5 .

Component	Per-call latency (ms)	Ratio vs. target
Target-side verification	$69.39$	$1.000\times$
Middle-model correction	$44.23$	$0.637\times$
N-gram small drafter	$0.92$	$0.013\times$
Online scheduler	$0.318$	$0.005\times$

Appendix

Table 8: Per-call latency of the online scheduler and the main runtime components under the online evaluation setting in Section 5 .

v_{1},v_{2},\ldots\leftarrow\mathrm{Sort}\bigl(V(\mathcal{T})\setminus\{r\},(-s(v),d(v),\mathrm{id}(v))\bigr)

Appendix

Algorithm 3 Global score-based pruning with ancestor closure

Small / Middle / Target	Speedup
LLaMA 3.2-1B-Instruct / LLaMA 3.1-8B-Instruct / LLaMA 3.3-70B-Instruct	1.116 $\times$
n-gram / LLaMA 3.1-8B-Instruct / LLaMA 3.3-70B-Instruct	1.299 $\times$
Qwen3-0.6B / Qwen3-4B / Qwen3-32B	0.735 $\times$
n-gram / Qwen3-4B / Qwen3-32B	1.108 $\times$
Qwen3-0.6B / Qwen3-8B / Qwen3-32B	0.743 $\times$
n-gram / Qwen3-8B / Qwen3-32B	1.134 $\times$

Appendix

Table 9: Effect of the small drafter choice under a fixed middle drafter schedule. The middle drafter is called at steps

1

3

, and

5

. Values are speedups over autoregressive target decoding.

Target–middle pair	Run 1	Run 2	Abs. diff.
Qwen3-32B / Qwen3-0.6B	1.470 $\times$	1.473 $\times$	0.003 $\times$
LLaMA 3.3-70B-Instruct / LLaMA 3.2-1B-Instruct	2.297 $\times$	2.289 $\times$	0.008 $\times$
Average	1.884 $\times$	1.881 $\times$	0.003 $\times$

Appendix

Table 10: Stability of repeated online evaluation. Run 1 denotes the result used in the main table, and Run 2 denotes an independent repeated evaluation with the same scheduler and decoding settings. Values are average speedups over six benchmarks.

Target–Middle	Alpaca			GSM8K			HumanEval			NQ			CNN/DM			MT-Bench			Average			Improvement
Target–Middle	TG	S	M	TG	S	M	TG	S	M	TG	S	M	TG	S	M	TG	S	M	TG	S	M	TG vs S	TG vs M
Qwen3-32B/1.7B	1.43	1.07	1.23	1.72	1.46	1.47	1.49	1.19	1.27	1.39	1.06	1.15	1.42	1.22	1.23	1.51	1.26	1.21	1.49	1.21	1.26	23.1%	18.3%
Qwen3-32B/0.6B	1.38	1.07	1.09	1.79	1.46	1.48	1.46	1.19	1.24	1.34	1.06	1.07	1.39	1.22	1.09	1.46	1.26	1.18	1.47	1.21	1.19	21.5%	23.5%
Qwen3-32B/8B	1.32	1.07	0.99	1.60	1.46	1.24	1.35	1.19	1.03	1.33	1.06	0.98	1.34	1.22	1.04	1.43	1.26	1.08	1.40	1.21	1.06	15.7%	32.1%
LLaMA-70B/1B	2.24	1.19	2.21	2.48	1.57	2.52	2.52	1.82	2.58	2.19	1.16	2.14	2.09	1.46	2.14	2.26	1.44	2.21	2.30	1.44	2.30	59.7%	0.0%
LLaMA-70B/3B	1.87	1.19	1.87	2.05	1.57	2.08	2.10	1.82	2.13	1.89	1.16	1.84	1.85	1.46	1.87	1.91	1.44	1.91	1.95	1.44	1.95	35.4%	0.0%

Appendix

Table 11: Online evaluation results. Values are speedups over autoregressive target decoding. TG denotes TreeGraft, while S and M denote the single-drafter endpoints All Small and All Mid, respectively. The small drafter used by TG and S is a training-free n-gram drafter. Blue rows denote held-out target–middle pairs not used in offline fitting or scheduler distillation; green columns denote the held-out MT-Bench task; orange cells denote their intersection. For LLaMA pairs, 70B, 8B, 3B, and 1B refer to LLaMA 3.3-70B, LLaMA 3.1-8B, LLaMA 3.2-3B, and LLaMA 3.2-1B, respectively.

Method	Setting	Average speedup	Improvement over better fixed endpoint
All-Small ( $T=1$ )	—	1.34 $\times$	—
All-Mid ( $T=1$ )	—	1.01 $\times$	—
TreeGraft ( $T=1$ )	Refit	1.56 $\times$	+16.4%
TreeGraft ( $T=1$ )	No refit	1.55 $\times$	+15.7%

Appendix

Table 12: Average speedup under sampling decoding with

T=1

Tree width	TreeGraft	All-Small	All-Mid	Improvement over better fixed endpoint
$W=10$	1.60 $\times$	1.32 $\times$	1.39 $\times$	+15.1%
$W=5$	1.50 $\times$	1.32 $\times$	1.24 $\times$	+13.6%

Appendix

Table 13: Average speedup in no-refit scheduler transfer under a change in candidate-tree width.

Deployment change	TreeGraft	All-Small	All-Mid	Improvement over better fixed endpoint
Qwen fitting $\rightarrow$ LLaMA testing	1.65 $\times$	1.44 $\times$	1.32 $\times$	+14.6%
LLaMA fitting $\rightarrow$ Qwen testing	1.32 $\times$	1.24 $\times$	0.95 $\times$	+6.5%
A100 $\rightarrow$ H20	1.85 $\times$	1.40 $\times$	1.15 $\times$	+32.1%

Appendix

Table 14: Average speedup in transfer evaluation across model families and hardware.

Scheduler	Average speedup	Full-scheduler speedup improvement
Without runtime-context features	1.46 $\times$	+9.6%
Without scheduling-history features	1.45 $\times$	+10.3%
Without tree-signal features	1.49 $\times$	+7.4%
Full learned scheduler	1.60 $\times$	–

Appendix

Table 15: Ablation of scheduler features.

Method	Average speedup	Learned-scheduler speedup improvement
Always-Early (call in the first 3 drafting steps)	1.48 $\times$	+8.1%
Entropy/Confidence ( $\tau=0.7$ )	1.25 $\times$	+28.0%
Candidate-Score-Gap ( $\tau=0.7$ )	1.46 $\times$	+9.6%
Latency-Normalized ( $\tau=1.0$ )	1.50 $\times$	+6.7%
Learned scheduler	1.60 $\times$	–

Appendix

Table 16: Learned scheduler vs. heuristic baselines.

Speculative Decoding

Speculative decoding accelerates generation by drafting multiple tokens and verifying them in parallel with a larger target model.

See all 291 papers

Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding
May 19, 2026Yuhao Shen, Tianyu Liu, Xinyi Hu +9Speculative Decoding LLM Inference Acceleration
1Zhejiang University · 2Qwen Applications Business Group of Alibaba · University of Science and Technology of China
TreeSpark: Calibrated, Load-Adaptive Draft Trees for Semi-Autoregressive Speculative Decoding
Aug 12, 2026Huapeng Zhou, Huayu Wang, Xinyu WangSpeculative Decoding LLM Inference Acceleration
Boson AI · University of Washington · McGill University
Accelerating Speculative Decoding with Block Diffusion Draft Trees
Apr 14, 2026Liran Ringel, Yaniv RomanoSpeculative Decoding Parallel Speculative Decoding
Department of Computer Science, Technion – Israel Institute of Technology. · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology.

May 19, 2026J/K move · Enter open · S save

Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding

Yuhao Shen, Tianyu Liu, Xinyi Hu, Quan Kong+8

1Zhejiang University · 2Qwen Applications Business Group of Alibaba · University of Science and Technology of China

Speculative Decoding LLM Inference Acceleration

Open paper AskPDF arXiv

Speculative decoding (SD) accelerates large language model inference by leveraging a draft-then-verify paradigm. To maximize the acceptance rate, recent methods construct expansive draft trees, which unfortunately incur severe VRAM bandwidth and computational overheads that bottleneck end-to-end speedups. While dynamic-depth pruning can reduce this latency by removing marginal branches, it also discards potentially valid candidates, preventing the acceptance rate from reaching the upper bound of dense trees. In this paper, we identify a critical opportunity in resource allocation: the transition from dense to pruned drafting frees up significant computational budget. To break this Pareto tradeoff, we introduce Graft, a compensation framework that couples pruning and retrieval as mutually reinforcing operations. Pruning supplies sufficient budget for retrieval, while retrieval compensates for pruning-induced coverage loss and recovers accepted length. By employing a sequential `prune-then-graft' mechanism, Graft attaches highly predictive retrieved tokens into positions opened by pruning, filling the topological gaps with near-zero overhead. Graft is entirely training-free and lossless. Comprehensive evaluations show that Graft establishes a new Pareto frontier across practical deployment settings, including short-context generation, long-context generation, and large-scale models. On short-context benchmarks, it achieves up to 5.41

\times

speedup and improves average speedup over EAGLE-3 by up to 21.8% on the large-scale Qwen3-235B. We also provide a preliminary exploration of applying Graft to the DFlash-style block drafting paradigm, offering initial evidence and insights for extending grafting beyond autoregressive draft trees.

Abstract

Speculative Decoding

Explore similar work

Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding

TreeSpark: Calibrated, Load-Adaptive Draft Trees for Semi-Autoregressive Speculative Decoding

Accelerating Speculative Decoding with Block Diffusion Draft Trees