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

Rahul Thomas; David Hidary; Arka Pal

cs.ITFeb 18, 2026

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

Authors: Rahul Thomas, David Hidary, Arka Pal

Organizations: Ritual · Columbia University

Abstract

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%.

Figures & tables

Model pair	$K$	Block efficiency $\uparrow$ (tokens/ $M_{p}$ -call)
		GSM8K	HumanEval	MATH500
OPT 6.7B/350M	1	3.294	3.157	3.227
	2	3.827	3.538	3.721
	3	3.867	3.809	3.856
	4	3.884	3.863	3.896
OPT 6.7B/125M	1	2.937	2.653	2.814

Table 1: We compute the block efficiency (tokens per target model call) for decoding with GBV, for target-draft model pairs OPT 6.7B/350M and OPT 6.7B/125M on up to 500 prompts from each of the datasets GSM8K, HumanEval, and MATH500. Larger numbers are better. In all settings, efficiency improves as

K

increases from

1

(block verification baseline) to

4

Model pair	$K$	Walltime $\downarrow$ (ms/token)
		GSM8K	HumanEval	MATH500
OPT 6.7B/350M	1	44.482	46.955	45.851
	2	39.592	43.373	40.473
	3	38.862	41.017	38.889
	4	48.473	50.656	48.440
OPT 6.7B/125M	1	34.479	38.824	36.022

Table 2: We compute the walltimes (ms/token) for decoding with GBV, for target-draft model pairs OPT 6.7B/350M and OPT 6.7B/125M on up to 500 prompts from each of the datasets GSM8K, HumanEval, and MATH500. Smaller numbers are better. In all settings, walltimes improve as

K

increases from

1

(block verification baseline) to

3

, but drop off at

K=4

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Model pair	Dataset	Block efficiency (tokens/ $M_{p}$ -call)
		$K=1$	$K=2$	$K=3$	$K=4$
Qwen-3 32B/0.6B	GSM8K	4.322	3.910	3.571	3.429
	HumanEval	4.204	3.423	3.331	2.960
	MATH500	4.342	3.917	3.693	3.411
	MGSM	4.329	3.973	3.468	3.445
	ToolBench	3.090	2.706	2.791	2.681

Appendix

Table 3: We compute the block efficiency (tokens per target model call) for decoding with GBV, for target-draft model pairs Qwen-3 32B/0.6B and Llama-3 70B/8B on up to 500 prompts from each of the datasets GSM8K, HumanEval, and MATH500, MGSM, and ToolBench (only the first two for Llama-3). Larger numbers are better. In almost all settings, efficiency decreases monotonically as

K

increases from

1

(block verification baseline) to

4

Model pair	Dataset	Walltime (ms/token)
		$K=1$	$K=2$	$K=3$	$K=4$
Qwen-3 32B/0.6B	GSM8K	79.638	92.823	100.547	106.123
	HumanEval	84.166	106.051	109.215	124.554
	MATH500	81.517	91.133	97.880	106.575
	MGSM	80.992	90.312	102.296	105.387
	ToolBench	113.563	132.477	128.405	133.973

Appendix

Table 4: We compute the walltimes (ms/token) for decoding with GBV, for target-draft model pairs Qwen-3 32B/0.6B and Llama-3 70B/8B on up to 500 prompts from each of the datasets GSM8K, HumanEval, and MATH500, MGSM, and ToolBench (only the first two for Llama-3). Smaller numbers are better. In almost all settings, walltime increases monotonically as

K

increases from

1

(block verification baseline) to

4

$K$	$M_{p}$ Temp.	Block Efficiency	Throughput	Walltime
		(tokens/ $M_{p}$ -call)	(tokens/s)	(ms/token)
1	0.2	3.867	11.034	90.626
1	0.4	4.313	12.407	80.598
1	0.6	4.308	12.368	80.851
1	0.8	4.430	12.761	78.362
1	1.0	4.322	12.557	79.638

Appendix

Table 5: We evaluate how temperature impacts the block efficiency, throughput, and walltime for GBV with

K=1,3

when run on Qwen-3 32B/0.6B with GSM8K (500 prompts) and

L=8

. We use temperature 0.2, 0.4, 0.6, 0.8, and 1.0 sampling from the target model. While BV (

K=1

) performs best at high temperatures (0.8, 1.0), GBV (

K=3

) works better at low temperatures (0.2, 0.4, 0.6).

$L$	$K$	Block Efficiency	Walltime	Draft Cost	Target Cost
		(tokens/ $M_{p}$ -call)	(ms/token)	(%walltime)	(%walltime)
8	1	4.322	79.638	71.5	21.3
	2	3.910	92.823	71.3	21.0
	3	3.571	100.547	71.1	21.1
	4	3.429	106.123	70.8	21.3
16	1	5.667	102.970	81.7	13.2

Appendix

Table 6: We evaluate GBV with

1\leq K\leq 4

for Qwen-3 32B/0.6B temperature 1.0 sampling on GSM8K (500 prompts), over varying draft block lengths

L=8,16,24

. We report block efficiency, walltime, and draft and target forward pass runtimes as percentages of end-to-end walltime. We find that around

L=8

is an ideal length for avoiding more pronounced draft bottlenecks.

$M_{p}$ Temp.	$K$	Method	Block Efficiency	Throughput	Walltime
			(tokens/ $M_{p}$ -call)	(tokens/s)	(ms/token)
1.0	2	GBV	4.430	7.508	133.188
		SpecTr	3.716	6.355	157.365
		SpecInfer	3.259	5.603	178.480
		Traversal	4.760	8.114	123.245
1.0	3	GBV	4.271	7.338	136.272

Appendix

Table 7: We compare GBV, SpecTr, SpecInfer, and traversal verification for Llama-3 70B/8B on GSM8K (500 prompts). We report block efficiency and throughput (higher is better), and walltime (lower is better), for

K=2,3

and temperature

0.2,1.0

sampling from the target model. While traversal verification outperforms other methods for temperature

1.0

, GBV achieves over

1.5

tokens/s higher throughput at temperature

0.2

Speculative Decoding

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

See all 308 papers

Apr 1, 2026

SpecTr-GBV: Multi-Draft Block Verification Accelerating Speculative Decoding

Autoregressive language models suffer from high inference latency due to their sequential decoding nature. Speculative decoding (SD) mitigates this by employing a lightweight draft model to propose candidate tokens, which are selectively verified by a larger target model. While existing methods either adopt multi-draft strategies to increase acceptance rates or block verification techniques to jointly verify multiple tokens, they remain limited by treating these improvements in isolation. In this work, we propose SpecTr-GBV, a novel SD method that unifies multi-draft and greedy block verification (GBV) into a single framework. By formulating the verification step as an optimal transport problem over draft and target token blocks, SpecTr-GBV improves both theoretical efficiency and empirical performance. We theoretically prove that SpecTr-GBV achieves the optimal expected acceptance length physically attainable within the framework of i.i.d. draft generation, and this bound improves as the number of drafts increases. Empirically, we evaluate SpecTr-GBV across five datasets and four baselines. Our method achieves superior speedup and significantly higher block efficiency while preserving output quality. In addition, we perform comprehensive ablation studies to evaluate the impact of various hyperparameters in the model.

Yijun Lin, Jinhao Sheng, Qingyue Cai +1

Center for Applied Statistics and School of Statistics, Renmin University of China · School of Intelligent Medicine, China Medical University · Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing

Speculative Decoding LLM Inference Acceleration

Ask PDF

Aug 4, 2026

Approximate Speculative Decoding

Speculative decoding accelerates autoregressive generation by verifying a draft block with a target model in parallel. Under standard greedy verification, decoding stops at the first draft token that differs from the target argmax, discarding the remaining target-scored suffix. Although accepting such a mismatch changes the decoding trajectory, it can make a contiguous suffix reusable when its tokens remain target-greedy under the realized prefix. In this paper, we introduce Approximate Speculative Decoding (ASD), a training-free verifier that replaces binary first-mismatch truncation with budgeted longest-prefix selection. ASD accepts selected mismatches subject to a local target-logit regret gate, a per-block exception cap, and a persistent request-level regret budget, then reuses the contiguous target-greedy suffix without additional approximate decisions or target-model forward passes. ASD requires neither a new draft model nor fine-tuning, and exactly reduces to standard greedy verification when the budget is zero. Experiments show that ASD improves fixed-workload throughput by

3.05\%

15.26\%

over matched strict verification and averages a

7.78\%

gain across seven Qwen3-14B + DSpark-14B tasks. On DeepSeek-V4-Flash (284B) with DSpark it also raises verifier-side acceptance by roughly

10\%

16\%

on GSM8K and MATH-500 in an FP4-to-FP8 compatibility setting. The source code is publicly available at: https://github.com/Kissmetothemoon/ASD

Yuannuo Feng, Zegang Peng, Yuxin Xie +5

School of Integrated Circuit Science and Engineering, Beihang University, Beijing, China · Department of Precision Instrument, Tsinghua University, Beijing, China · Faculty of Engineering, The University of Hong Kong, Hong Kong SAR, China +2

Speculative Decoding LLM Inference Acceleration Autoregressive Decoding Parallel Speculative Decoding

Ask PDF

Feb 19, 2026

Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding

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.

Rahul Thomas, Teo Kitanovski, Micah Goldblum +1

Ritual · Columbia University · Vanderbilt University

Speculative Decoding LLM Inference Acceleration

Ask PDF

Abstract

Speculative Decoding

Explore similar work

SpecTr-GBV: Multi-Draft Block Verification Accelerating Speculative Decoding

Approximate Speculative Decoding

Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding