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

Yijun Lin; Jinhao Sheng; Qingyue Cai; Feng Zhou

cs.CLApr 1, 2026

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

Authors: Yijun Lin, Jinhao Sheng, Qingyue Cai, Feng Zhou

Organizations: 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

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Comparison between SpecTr and SpecTr-GBV. Given multiple i.i.d. draft sequences, SpecTr performs position-by-position verification: at each position, it accepts one token (e.g., bounces , then like ) and retains only the sequences consistent with accepted tokens. If no token is accepted, a new token is sampled from the residual distribution (e.g., replacing ball with toy ). SpecTr-GBV verifies token sub-blocks across all draft sequences. It starts by jointly verifying sub-blocks with the first position (e.g., bounces , bounces when , …, bounces when I am ) and select the longest accepted sub-block (e.g., bounces ). Verification continues from the next position in the next sequence (e.g., wraps around , …, wraps around my arm ). If no sub-block is accepted, we proceed to the next sequence, progressively selecting the longest accepted sub-block (e.g., bounces like a ). A residual token is then sampled after the longest accepted sub-block (e.g., replacing ball with toy ).

\begin{aligned} &\hskip 18.49988ptq_{\text{new}}(x^{(i)})\\ &={}q\left(t^{\tau},y,x^{i-1},x^{(i)}\right)\left(1-\min\left\{\tfrac{p\left(t^{\tau},y,x^{i-1},x^{(i)}\right)}{q\left(t^{\tau},y,x^{i-1},x^{(i)}\right)},1\right\}\right)^{K}\\ &\cdot\Biggl(\sum_{x^{\prime}}q\left(t^{\tau},y,x^{i-1},x^{\prime}\right)\left(1-\min\left\{\tfrac{p\left(t^{\tau},y,x^{i-1},x^{\prime}\right)}{q\left(t^{\tau},y,x^{i-1},x^{\prime}\right)},1\right\}\right)^{K}\Biggr)^{-1}.\end{aligned}

Algorithm 2 Distribution Modification

Setting	Dataset	Metric	AR	SD	SpecTr	GBV	SpecTr-GBV
DeepSeek-33B DeepSeek-1.3B L=12 T=0.4 K=3	HumanEval	BE	$1$	$9.53\pm 1.53$	$10.25\pm 1.37$	$9.60\pm 1.52$	$\mathbf{10.45\pm 1.44}$
	HumanEval	SR	$1$	$2.02\pm 0.32$	$2.21\pm 0.30$	$2.03\pm 0.32$	$\mathbf{2.50\pm 0.39}$
	GSM8K	BE	$1$	$6.83\pm 1.66$	$7.25\pm 1.31$	$6.89\pm 1.44$	$\mathbf{7.65\pm 1.54}$
	GSM8K	SR	$1$	$1.57\pm 0.42$	$2.26\pm 0.44$	$1.57\pm 0.37$	$\mathbf{2.46\pm 0.58}$
	MGSM	BE	$1$	$7.18\pm 1.85$	$8.10\pm 1.86$	$7.37\pm 1.88$	$\mathbf{8.31\pm 1.81}$
	MGSM	SR	$1$	$1.55\pm 0.45$	$1.97\pm 0.72$	$1.60\pm 0.47$	$\mathbf{2.12\pm 0.76}$

Table 1: Performance comparison of SpecTr-GBV with baselines. The results demonstrate that SpecTr-GBV consistently outperforms all baselines across five datasets, regardless of whether DeepSeek-33B or DeepSeek-6.7B is used as the target model.

Setting	Dataset	Method	Total (s)	Iter	Draft (s)	Target (s)	Verification (s)	Other (s)	Tokens/s	Accept
DeepSeek-33B DeepSeek-1.3B $L$ =12	GSM8K	SpecTr	19.24	73.46	11.97	6.05	1.01	0.20	27.48	0.521
		SpecTr-GBV	18.03	70.13	11.57	5.79	0.47	0.20	29.64	0.555
		$\delta$	-6.3%	-4.5%	-3.3%	-4.3%	-53.5%	-0.0%	+7.9%	+6.5%
	HumanEval	SpecTr	12.91	51.72	8.91	2.83	1.03	0.12	40.99	0.772
		SpecTr-GBV	11.39	50.92	8.24	2.75	0.26	0.12	46.79	0.788
		$\delta$	-11.8%	-1.5%	-7.5%	-2.8%	-74.8%	-0.0%	+14.2%	+2.1%

Table 2: Wall-clock time breakdown of SpecTr-GBV and SpecTr.We report the total wall-clock time (Total), number of decoding iterations for SD (Iter), time spent by the draft model (Draft) and target model (Target), verification algorithm overhead (Verification), other system overheads (e.g., cache operations) (Other), throughput (Tokens/s), and mean acceptance rate (Accept) for every data point. The

\delta

row quantifies the percentage change of SpecTr-GBV relative to the SpecTr baseline.

$L$	AR		SD		SpecTr		GBV		SpecTr-GBV
$L$	BE	SR	BE	SR	BE	SR	BE	SR	BE	SR
12	1	1	9.53	2.02	10.25	2.21	9.60	2.03	10.45	2.50
16	1	1	11.36	1.93	12.56	2.56	11.37	1.94	12.63	2.52
20	1	1	13.10	1.88	13.64	2.55	13.19	1.86	14.58	2.87
24	1	1	14.63	1.80	16.22	2.33	15.08	1.85	16.52	2.68

Table 3: Ablation results of SpecTr-GBV under different draft lengths

L

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	Dataset	Metric	AR	SD	SpecTr	GBV	SpecTr-GBV
CodeLlama-13B CodeLlama-7B L=8 T=0.4 K=3	HumanEval	BE	$1$	$7.58\pm 0.76$	$7.99\pm 0.70$	$7.59\pm 0.79$	$\mathbf{8.02\pm 0.73}$
	HumanEval	SR	$1$	$1.45\pm 0.15$	$1.67\pm 0.17$	$1.42\pm 0.15$	$\mathbf{1.67\pm 0.18}$
	GSM8K	BE	$1$	$7.33\pm 0.69$	$7.89\pm 0.51$	$7.52\pm 0.61$	$\mathbf{7.95\pm 0.53}$
	GSM8K	SR	$1$	$1.18\pm 0.12$	$1.48\pm 0.24$	$1.18\pm 0.11$	$\mathbf{1.51\pm 0.22}$
	MGSM	BE	$1$	$6.83\pm 1.11$	$7.36\pm 0.95$	$6.89\pm 1.16$	$\mathbf{7.39\pm 0.96}$
	MGSM	SR	$1$	$1.28\pm 0.21$	$1.39\pm 0.18$	$1.26\pm 0.21$	$\mathbf{1.51\pm 0.21}$

Appendix

Table 4: Performance comparison of SpecTr-GBV with baselines using CodeLlama and Vicuna models. The results show that SpecTr-GBV consistently outperforms all baselines across five datasets with both model families.

$L$	AR		SD		SpecTr		GBV		SpecTr-GBV
$L$	BE	SR	BE	SR	BE	SR	BE	SR	BE	SR
4	1	1	4.42	1.19	4.57	1.15	4.44	1.19	4.62	1.26
8	1	1	7.06	1.19	7.53	1.15	7.06	1.19	7.70	1.28
12	1	1	9.39	1.12	10.11	1.16	9.89	1.14	10.29	1.26
16	1	1	11.23	1.06	12.22	1.13	11.58	1.08	12.49	1.23

Appendix

Table 5: Ablation results of SpecTr-GBV under different draft lengths

L

with

T=0.4

K=3

, in the DeepSeek-6.7B-1.3B setting.

Panel of Figure 3 — Figure 3: Ablation results of SpecTr-GBV under different draft number (a) and temperature (b) in the DeepSeek-6.7B-1.3B setting.

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
SpecBlock: Block-Iterative Speculative Decoding with Dynamic Tree Drafting
May 8, 2026Weijie Shi, Qiang Xu, Fan Deng +9Speculative Decoding LLM Inference Acceleration
Hong Kong University of Science and Technology · MetaX · Zhejiang Normal University +1
LibraSpec: Dynamic Diffusion-Based Speculative Decoding via Marginal-Gain-Driven Optimization
Aug 9, 2026Zexun Lin, Yuan Feng, Junlin Lv +2Inference-Time Optimization Speculative Decoding for Diffusion Language Models
Suzhou Institute for Advanced Research, University of Science and Technology of China Suzhou, Jiangsu, China

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

SpecBlock: Block-Iterative Speculative Decoding with Dynamic Tree Drafting

LibraSpec: Dynamic Diffusion-Based Speculative Decoding via Marginal-Gain-Driven Optimization