Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding

Rahul Thomas; Teo Kitanovski; Micah Goldblum; Arka Pal

cs.LGFeb 19, 2026

Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding

Authors: Rahul Thomas, Teo Kitanovski, Micah Goldblum, Arka Pal

Organizations: Ritual · Columbia University · Vanderbilt University

Abstract

Multi-path speculative decoding accelerates lossless sampling from a target model by using a cheaper draft model to generate a draft tree of tokens, and then applies a verification algorithm that accepts a subset of these. While prior work has proposed various verification algorithms for i.i.d rollouts, their relative performance under matched settings remains unclear. In this work, we firstly present a systematic evaluation of verification strategies across model families, tasks, and sampling regimes, and find that Traversal Verification dominates consistently, with OT-based methods lagging far behind. Our analysis uncovers that this occurs because OT-based methods achieve high multi-token acceptance near the root of the draft tree, while multi-token gains are most impactful deeper in the draft tree, where draft and target distributions diverge. Based on this insight, we propose delayed tree expansion, which drafts a partial single path, delaying the i.i.d. branching point. We show that delayed tree expansion preserves the target distribution and improves on root-node i.i.d rollouts. Further, we develop a dynamic neural selector that estimates the expected block efficiency of optimal-transport-based verification methods from draft and target features, enabling context-dependent expansion decisions. Our neural selector allows OT-based methods like SpecInfer to outperform Traversal Verification for the first time, achieving 5% higher average throughput across a wide range of models, datasets, and sampling settings.

Figures & tables

Algorithm	Appears In	Multi-Path	OT-Based
NaiveTree	Leviathan et al. (2023)	✓	✓
NSS	Miao et al. (2024)	✓	✓
SpecTr	Sun et al. (2023)	✓	✓
SpecInfer	Miao et al. (2024)	✓	✓
Khisti	Khisti et al. (2025)	✓	✓
Naive	Chen et al. (2023)

Table 1: Summary of all single-path and multi-path verification algorithms, and whether multi-path algorithms are OT-based.

Method	Qwen	Gemma	Llama	Average
NSS	4.44	1.99	5.72	4.05
BV	4.24	3.30	5.37	4.30
Khisti	4.90	2.05	6.29	4.41
NaiveTree	5.00	2.01	6.50	4.50
Naive	4.60	3.44	5.52	4.52
SpecInfer	5.13	2.07	6.55	4.58

Table 2: Average block efficiency across datasets and sampling configurations of existing verification algorithms. For more detailed data, see Appendix F .

Method	Qwen	Gemma	Llama	Average
NSS	16.88	5.94	12.91	11.91
Naive	16.55	9.20	11.58	12.44
Khisti	18.67	5.93	13.66	12.75
NaiveTree	19.16	6.00	14.71	13.29
SpecTr	19.01	6.09	14.86	13.32
BV	17.30	10.57	12.20	13.36

Table 3: Average throughput (tokens per second) across datasets and sampling configurations of existing verification algorithms. For more detailed data, see Appendix F .

Panel of Figure 1 — Figure 1: We generate 200,000+ draft (Llama-3 8B-Instruct) trees from roots of target model (Llama-3 70B-Instruct) trajectories and compute both L1 target-draft distance and average OTLP acceptances across varying draft tree depths. The divergence between target and draft distributions spikes deeper in the tree, and acceptances across all OTLP methods consistently decrease with depth.

Method	Qwen	Gemma	Llama	Average
Khisti NDE	1.01	1.90	1.09	1.19
NaiveTree NDE	1.07	0.99	1.17	1.09
NSS NDE	0.97	1.68	1.01	1.11
SpecInfer NDE	0.98	1.65	1.01	1.10
SpecTr NDE	0.97	1.68	1.01	1.10

Table 4: Block efficiency ratio improvement of our NDE (neural dynamic expansion) approach over the baseline algorithms.

Method	Qwen	Gemma	Llama	Average
Khisti NDE	0.99	2.17	0.97	1.16
NaiveTree NDE	1.31	1.40	1.21	1.30
NSS NDE	1.20	2.09	0.96	1.26
SpecInfer NDE	1.15	2.14	0.96	1.23
SpecTr NDE	1.14	2.17	0.96	1.23

Table 5: Throughput (tokens per second) ratio improvement of our NDE (neural dynamic expansion) approach over the baseline algorithms.

Method	Qwen	Gemma	Llama	Average
Traversal	5.33	3.81	6.78	5.31
NSS NDE	4.31	3.34	5.78	4.48
NaiveTree NDE	4.94	3.42	6.47	4.94
SpecInfer NDE	5.03	3.42	6.64	5.03
SpecTr NDE	4.97	3.44	6.74	5.05
Khisti NDE	4.97	3.89	6.84	5.23

Table 6: Average block efficiency across datasets and sampling configurations. Traversal is best existing algorithm; NDE (neural delayed expansion) is ours. For more detailed data, see Appendix F .

Method	Qwen	Gemma	Llama	Average
Traversal	21.35	11.56	14.77	15.89
Khisti NDE	18.41	12.84	13.24	14.83
NSS NDE	20.29	12.40	12.45	15.05
NaiveTree NDE	21.67	12.86	14.01	16.18
SpecTr NDE	21.74	13.22	14.23	16.40
SpecInfer NDE	22.54	13.26	14.27	16.69

Table 7: Average throughput (tokens per second) across datasets and sampling configurations. Traversal is best existing algorithm; NDE (neural delayed expansion) is ours. For more detailed data, see Appendix F .

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

	Qwen-2.5 (32B / 500M)					Gemma-3 (27B / 270M)					Llama-3 (70B / 8B)
	Writing	Coding	Translation	Math (E)	Math (H)	Writing	Coding	Translation	Math (E)	Math (H)	Writing	Coding	Translation	Math (E)	Math (H)
Khisti, delayed expansion	14.21	17.81	14.16	23.05	22.80	8.93	9.90	10.73	17.39	17.28	11.00	14.24	13.93	13.75	13.26
Khisti	11.22	19.87	13.88	24.29	24.07	3.53	5.08	8.88	6.60	5.58	11.71	14.25	14.23	14.18	13.92
NaiveTree, delayed expansion	14.57	21.91	16.29	28.89	26.69	9.95	8.45	11.95	15.84	18.10	11.31	15.66	15.04	14.76	13.29
NaiveTree	10.25	19.08	13.28	27.52	25.67	3.48	5.26	9.74	6.48	5.04	11.77	16.10	15.71	15.68	14.28
Naive	7.90	17.47	9.76	24.84	22.77	4.72	6.79	7.30	13.15	14.07	8.65	13.05	12.72	12.42	11.04

Appendix

Table 8: Tokens per second by dataset and algorithm

	Qwen-2.5 (32B / 500M)					Gemma-3 (27B / 270M)					Llama-3 (70B / 8B)
	Writing	Coding	Translation	Math (E)	Math (H)	Writing	Coding	Translation	Math (E)	Math (H)	Writing	Coding	Translation	Math (E)	Math (H)
Khisti, delayed expansion	2.56	5.21	3.22	7.04	6.81	2.01	3.51	2.69	5.72	5.53	5.59	7.48	7.24	7.06	6.85
Khisti	2.78	5.16	3.50	6.59	6.50	1.21	1.77	3.09	2.26	1.92	5.26	6.64	6.63	6.57	6.35
NaiveTree, delayed expansion	2.41	5.31	3.42	7.06	6.49	1.89	2.75	2.82	4.62	5.00	5.15	7.36	6.98	6.75	6.10
NaiveTree	2.62	5.14	3.63	7.00	6.60	1.17	1.78	3.25	2.19	1.68	5.18	7.19	7.01	6.88	6.24
Naive	2.18	4.91	2.73	6.91	6.30	1.74	2.60	2.80	4.91	5.17	4.08	6.33	6.12	5.85	5.22

Appendix

Table 9: Block efficiency by dataset and algorithm

	Temperature (top-p=1)						Top-p
	0.2	0.4	0.6	0.8	1.0	1.2	0.90	0.99
Khisti, delayed expansion	19.59	19.94	20.06	19.42	17.36	13.58	19.50	17.80
Khisti	18.23	18.66	18.90	19.07	19.37	18.53	18.11	18.47
NaiveTree, delayed expansion	22.17	22.41	22.52	22.01	21.47	19.28	21.88	21.65
NaiveTree	19.75	20.20	19.82	19.52	18.98	16.90	19.03	19.06
Naive	15.40	15.86	16.58	16.85	16.74	16.05	17.51	17.39

Appendix

Table 10: Throughput (tokens per second) for Qwen

	Temperature (top-p=1)						Top-p
	0.2	0.4	0.6	0.8	1.0	1.2	0.90	0.99
Khisti, delayed expansion	4.85	5.02	5.21	5.42	5.28	3.91	4.88	5.18
Khisti	5.13	5.25	5.37	5.28	4.51	3.40	5.09	5.21
NaiveTree, delayed expansion	5.15	5.14	5.25	5.02	4.86	4.26	4.95	4.89
NaiveTree	5.16	5.20	5.17	5.11	4.97	4.44	4.98	4.96
Naive	4.48	4.65	4.84	4.93	4.61	4.18	4.59	4.56

Appendix

Table 11: Block Efficiencies for Qwen

	Temperature (top-p=1)						Top-p
	0.2	0.4	0.6	0.8	1.0	1.2	0.90	0.99
Khisti, delayed expansion	12.73	12.52	13.36	12.76	12.96	12.76	12.79	12.87
Khisti	5.95	5.87	5.86	5.82	6.01	6.00	5.98	5.95
NaiveTree, delayed expansion	13.36	12.97	12.55	12.53	12.75	12.93	12.94	12.82
NaiveTree	6.03	5.96	5.86	6.01	6.10	5.94	6.01	6.11
Naive	8.99	9.19	9.37	9.45	9.06	9.04	9.25	9.29

Appendix

Table 12: Throughput (tokens per second) for Gemma

	Temperature (top-p=1)						Top-p
	0.2	0.4	0.6	0.8	1.0	1.2	0.90	0.99
Khisti, delayed expansion	3.82	3.78	4.06	3.90	3.91	3.89	3.86	3.92
Khisti	2.05	2.04	2.02	2.01	2.07	2.06	2.09	2.06
NaiveTree, delayed expansion	3.51	3.41	3.34	3.34	3.43	3.51	3.37	3.43
NaiveTree	2.02	2.00	1.97	2.02	2.04	1.98	2.04	2.04
Naive	3.47	3.34	3.40	3.53	3.50	3.57	3.37	3.37

Appendix

Table 13: Block Efficiencies for Gemma

	Temperature (top-p=1)						Top-p
	0.2	0.4	0.6	0.8	1.0	1.2	0.90	0.99
Khisti, delayed expansion	13.20	13.14	13.56	13.44	13.52	11.44	13.91	13.67
Khisti	13.52	13.46	13.82	13.89	13.79	12.75	14.06	13.99
NaiveTree, delayed expansion	13.79	14.11	13.99	14.13	14.24	13.56	14.05	14.22
NaiveTree	14.22	14.39	14.41	15.32	14.50	14.34	15.35	15.12
Naive	10.61	11.09	11.57	11.96	12.08	11.38	12.06	11.87

Appendix

Table 14: Throughput (tokens per second) for Llama

	Temperature (top-p=1)						Top-p
	0.2	0.4	0.6	0.8	1.0	1.2	0.90	0.99
Khisti, delayed expansion	6.49	6.52	6.77	6.97	7.32	6.59	6.88	7.19
Khisti	6.58	6.58	6.75	6.85	5.72	4.25	6.78	6.81
NaiveTree, delayed expansion	6.34	6.54	6.46	6.50	6.60	6.27	6.50	6.55
NaiveTree	6.42	6.51	6.51	6.61	6.56	6.20	6.65	6.52
Naive	5.06	5.30	5.54	5.70	5.73	5.41	5.76	5.68

Appendix

Table 15: Block Efficiencies for Llama

Speculative Decoding

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

See all 308 papers

Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling
Feb 18, 2026Rahul Thomas, David Hidary, Arka PalSpeculative Decoding LLM Inference Acceleration
Ritual · Columbia University
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
DIVERSED: Relaxed Speculative Decoding via Dynamic Ensemble Verification
Apr 8, 2026Ziyi Wang, Siva Rajesh Kasa, Ankith M S +6Speculative Decoding LLM Inference Acceleration
Purdue University · Amazon Inc. · University of Illinois Urbana-Champaign +1

Feb 18, 2026J/K move · Enter open · S save

Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling

Rahul Thomas, David Hidary, Arka Pal

Ritual · Columbia University

Speculative Decoding LLM Inference Acceleration

Open paper AskPDF arXiv

The goal of

L

-step speculative decoding is to accelerate autoregressive decoding of a target model by using a cheaper draft model to generate a candidate path of

L

tokens. Based on a verification algorithm involving target and draft model probabilities, a prefix of the candidate sequence is accepted, and an additional correction token is sampled from a residual distribution to ensure that the final output adheres to the target distribution. While standard speculative decoding uses a verification algorithm which is independent at each token on the path, a recent extension called block verification uses a joint condition involving all sampled on-path probabilities. Block verification (BV) was shown to be optimal over all verification algorithms which use only on-path probabilities, improving on standard speculative decoding. In this work, we first show that block verification is optimal even over verification algorithms that use off-path probabilities, by constructing an information-agnostic linear program (LP). Further, we can extend our LP to the setting where the draft model samples multiple candidate paths, and use it to construct a natural class of multi-path block verification generalizations. While computing the optimal algorithm in this class is not tractable, by considering a stricter class of greedy algorithms, we can formulate an efficient method called greedy multi-path block verification (GBV). Empirically, GBV can improve block efficiency by over 30% and reduce decoding walltimes by over 15% relative to BV. On Llama-3 70B, GBV can improve the end-to-end decoding throughput over SOTA multi-path verification methods by more than 15%.

Abstract

Speculative Decoding

Explore similar work

Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling

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

DIVERSED: Relaxed Speculative Decoding via Dynamic Ensemble Verification