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

May 19, 2026

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

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.

Yuhao Shen, Tianyu Liu, Xinyi Hu +9

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

Speculative Decoding LLM Inference Acceleration

Ask PDF

Aug 12, 2026

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

Speculative decoding accelerates language-model inference by letting a cheap drafter propose tokens that the target model verifies in parallel. Recent block drafters make drafting nearly free: a single backbone pass emits an entire block of draft tokens. Draft trees promise a further gain -- several alternative continuations verified in one target forward -- but existing constructions rank candidates by per-position marginals that ignore which parent a candidate extends, so on semi-autoregressive drafters wider trees mostly add mis-ranked nodes; and a tree of fixed size ignores how much speculation each decoding round, and each serving load, can support. We introduce TreeSpark, which reads a parent-conditioned distribution from the drafter's existing Markov head at negligible cost, calibrates it into an edge-acceptance estimate, and lets path survival govern everything else: best-first expansion, per-round stopping, and a load-adaptive serving policy. Sampling siblings without replacement, with matching residuals in recursive rejection, keeps decoding lossless at any temperature. Adaptive trees improve on matched fixed budgets at every temperature; against a tuned chain on the same drafter, TreeSpark accepts 15-25% more draft tokens per round and decodes 8-14% faster in single-request wall-clock, and under rising load it gracefully shrinks the tree back to the chain. Code and artifacts: https://github.com/PopSoda2002/TreeSpark

Huapeng Zhou, Huayu Wang, Xinyu Wang

Boson AI · University of Washington · McGill University

Speculative Decoding LLM Inference Acceleration

Ask PDF

Apr 14, 2026

Accelerating Speculative Decoding with Block Diffusion Draft Trees

Speculative decoding accelerates autoregressive language models by using a lightweight drafter to propose multiple future tokens, which the target model then verifies in parallel. DFlash shows that a block diffusion drafter can generate an entire draft block in a single forward pass and achieve state-of-the-art speculative decoding performance, outperforming strong autoregressive drafters such as EAGLE-3. Vanilla DFlash, however, still verifies only a single drafted trajectory per round, potentially limiting its acceptance length. We introduce DDTree (Diffusion Draft Tree), a method that constructs a draft tree directly from the per-position distributions of a block diffusion drafter. Under a fixed node budget, DDTree uses a simple best-first heap algorithm to select the continuations that are most likely to match the target model according to a surrogate defined by the draft model's output. The resulting tree is verified efficiently in a single target model forward pass using an ancestor-only attention mask. Because DDTree builds on DFlash, a leading draft model for speculative decoding, these gains place DDTree among the leading approaches to speculative decoding.

Liran Ringel, Yaniv Romano

Department of Computer Science, Technion – Israel Institute of Technology. · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology.

Speculative Decoding Parallel Speculative Decoding Speculative Decoding for Diffusion Language Models

Ask PDF

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