Skip to content

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

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/junemily/SpecTr-GBV.git
Area: LLM Reasoning
Keywords: Speculative Decoding, Multi-Draft Generation, Greedy Block Verification, Optimal Transport, Conditionally Independent Couplings

TL;DR

SpecTr-GBV unifies multi-draft speculative generation and greedy block verification under optimal transport theory, rigorously achieving the theoretical upper bound of expected acceptance length under conditionally independent couplings while preserving exact target distribution fidelity and substantially improving inference throughput.

Background & Motivation

Autoregressive large language models (LLMs) have achieved state-of-the-art breakthroughs across diverse reasoning, code generation, and complex comprehension benchmarks. However, their inference latency remains fundamentally bounded by the memory-bandwidth-bound, sequential decoding nature of autoregressive generation, where producing each single token demands a full forward pass through billions or tens of billions of parameters. To overcome this sequential bottleneck, speculative decoding (SD) employs a lightweight draft model to propose a sequence of candidate tokens in parallel, which are subsequently scored and verified in a single batched pass by the target model. By accepting valid candidate tokens via rejection sampling, SD accelerates inference without altering the target model's output distribution. Nonetheless, standard SD operates on a single draft sequence, typically accepting only a small number of tokens per iteration and leaving substantial acceleration potential untapped.

To push beyond the limits of standard SD, two independent lines of inquiry have recently emerged. The first direction focuses on multi-draft generation (such as SpecTr), which expands candidate search coverage by having the draft model sample \(K\) independent and identically distributed (i.i.d.) candidate sequences. However, SpecTr relies on position-by-position verification across draft columns; once all candidate tokens at any single column are rejected, the entire remaining draft suffix is discarded immediately. The second direction, greedy block verification (GBV), demonstrates that token-by-token verification fails to attain optimal acceptance length, and instead evaluates draft sequences as unified token blocks. Nevertheless, GBV is strictly formulated for the single-draft setting and cannot directly ingest multiple candidate sequences without encountering combinatorial distribution complexity.

These two promising paradigms have remained completely isolated: multi-draft techniques lack holistic block-level joint verification, while block verification methods cannot handle the joint couplings and sample redundancies of multiple concurrent drafts without risking exponential overheads or distributional drift. Core idea: Formulate the joint verification of multiple i.i.d. draft sequences and target token blocks as an optimal transport problem constrained to conditionally independent couplings (CIC), deriving closed-form verification and dynamic distribution modification rules that strictly attain the theoretical upper bound of expected acceptance length with linear computational complexity and zero distribution loss.

Method

Overall Architecture

SpecTr-GBV coordinates parallel candidate drafting, sequential sub-block evaluation across multiple sequences, residual token sampling, and cross-iteration distribution modification. Given a context prefix \(c\), a compact draft model \(M_s\) generates \(K\) i.i.d. draft sequences of length \(L\), denoted as \(X_L = \{x_L^1, x_L^2, \dots, x_L^K\}\). The larger target model \(M_b\) then scores all draft tokens in parallel across all candidate positions. Rather than checking columns independently, SpecTr-GBV traverses candidate sequences sequentially while maintaining a pointer to the length \(\tau\) of the longest accepted sub-block found so far. For each sequence, it attempts to verify longer sub-blocks starting from position \(\tau + 1\) using the optimal transport acceptance probability \(h_{ik}\). A hash set of previously rejected sub-blocks is maintained to bypass redundant sampling, and the sequence traversal terminates early whenever an entire candidate sequence of length \(L\) is accepted. If verification halts with \(\tau < L\), an extra correction token is sampled from a closed-form residual distribution, and the target distribution over the remaining unaccepted positions is analytically re-weighted before the subsequent SD iteration to maintain flawless distributional consistency.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Context Prefix c<br/>Sample K i.i.d. Draft Sequences"] --> B["Conditionally Independent Coupling<br/>Formulate Multi-Draft OT Bound"]
    B --> C["Cross-Draft Greedy Block Verification<br/>Dynamic Sub-Block Expansion and Pruning"]
    C --> D["Distribution Modification & Residual Sampling<br/>Lossless Cross-Step Target Re-weighting"]
    D --> E["Emit Accepted Token Block<br/>Update Prefix and Advance SD Iteration"]

Key Designs

1. Conditionally Independent Coupling: Formulate Multi-Draft OT Bound Standard discrete optimal transport across \(K\) draft blocks \(X_L\) and target token block \(y_L\) requires solving large-scale linear programs whose computational complexity scales exponentially with \(K\), rendering it intractable for practical LLM vocabularies \(|\Omega|\). SpecTr-GBV resolves this bottleneck by defining the space of Conditionally Independent Couplings (CIC), \(\Pi_{\text{CIC}}(p^{\oplus K}, q)\), which enforces that the \(K\) draft blocks are mutually independent when conditioned on the target token sequence \(y_L\):

\[P_\pi(X_L \mid y_L) = \prod_{k=1}^K P_\pi(x_L^k \mid y_L)\]

This mathematical constraint naturally mirrors the non-communicating nature of i.i.d. drafting. Under this structural family, the verification problem is cast as minimizing the rejection cost \(C(\pi) = L - \mathbb{E}_{X_L, y_L \sim \pi}[\tau]\). The authors analytically establish that the optimal coupling achieves a theoretical upper bound on the expected acceptance length:

\[\mathbb{E}_{X_L, y_L \sim \pi^*}[\tau] = \sum_{\tau=1}^L \sum_{x_\tau} q(x_\tau) \left[ 1 - \left( 1 - \min\left\{\frac{p(x_\tau)}{q(x_\tau)}, 1\right\} \right)^K \right]\]

This upper bound is proven to be strictly monotonically increasing with draft count \(K\) (\(\text{Bound}(K_1) > \text{Bound}(K_2)\) for \(K_1 > K_2\)), converging to the full draft length \(L\) as \(K \to \infty\), and exactly recovering the single-draft GBV bound when \(K=1\).

2. Cross-Draft Greedy Block Verification: Dynamic Sub-Block Expansion and Pruning To realize the theoretical upper bound without solving costly linear programs, SpecTr-GBV evaluates candidate sub-blocks sequentially across the \(K\) draft sequences. Tracking the current maximum accepted length \(\tau\), verification of sequence \(x_L^k\) begins directly at sub-block length \(i = \tau + 1\). Each candidate sub-block \(x_i^k = (x_1^k, \dots, x_i^k)\) is accepted with an exact closed-form probability \(h_{ik}\):

\[h_{ik} = \frac{\sum_{x} q(x_i, x) \left[1 - \min\left\{\frac{p(x_i, x)}{q(x_i, x)}, 1\right\}\right]^K - q(x_i) \left[1 - \min\left\{\frac{p(x_i)}{q(x_i)}, 1\right\}\right]^K}{1 - (1 - p(x_i))^K - q(x_i) + \sum_{x} q(x_i, x) \left[1 - \min\left\{\frac{p(x_i, x)}{q(x_i, x)}, 1\right\}\right]^K}\]

When a sub-block is rejected, it is recorded in a rejected set \(H\); any identical sub-block encountered later is skipped without redundant random number sampling. Furthermore, once an entire block \(x_L^k\) passes verification, the outer sequence loop terminates early. This algorithm computes at most \(KL\) sub-block probabilities, which are fully parallelized via GPU tensor operations, reducing the per-selection arithmetic complexity from SpecTr's \(\mathcal{O}(|\Omega| \log K)\) to \(\mathcal{O}(|\Omega|)\).

3. Distribution Modification & Residual Sampling: Lossless Cross-Step Target Re-weighting Preserving strict distribution fidelity across multi-draft block verification requires precise residual sampling and cross-iteration correction. When the longest accepted sub-block satisfies \(\tau < L\), SpecTr-GBV samples the subsequent correction token from a specialized residual distribution:

\[p_{\text{res}}(x \mid x_\tau) = \frac{q(x_\tau, x) \left[1 - \min\left\{\frac{p(x_\tau, x)}{q(x_\tau, x)}, 1\right\}\right]^K}{\sum_{x'} q(x_\tau, x') \left[1 - \min\left\{\frac{p(x_\tau, x')}{q(x_\tau, x')}, 1\right\}\right]^K}\]

To prevent error accumulation across successive speculative decoding iterations caused by conditional truncated acceptance, the target distribution over the subsequent \(L - \tau - 1\) steps is adjusted according to the analytic formula:

\[q_{\text{new}}(x^{(i)}) = \frac{q(t_\tau, y, x_{i-1}, x^{(i)}) \left[ 1 - \min\left\{\frac{p(t_\tau, y, x_{i-1}, x^{(i)})}{q(t_\tau, y, x_{i-1}, x^{(i)})}, 1\right\} \right]^K}{\sum_{x'} q(t_\tau, y, x_{i-1}, x') \left[ 1 - \min\left\{\frac{p(t_\tau, y, x_{i-1}, x')}{q(t_\tau, y, x_{i-1}, x')}, 1\right\} \right]^K}\]

By backward induction, Theorem 4.2 formally proves that for all decoded tokens \(O_i\), the marginal equality \(P(O_i = x_i) = q(x_i)\) holds exactly, guaranteeing that multi-draft block acceleration introduces zero distributional divergence.

Key Experimental Results

Main Results

The authors conduct comprehensive evaluations across five benchmark datasets: Python coding (HumanEval), grade school math (GSM8K), multilingual math reasoning (MGSM), long-form language modeling (LM1B), and instruction following (Alpaca). Performance is quantified using Block Efficiency (BE: average decoded tokens per serial target model call) and Speedup Ratio (SR: wall-clock acceleration relative to autoregressive decoding).

The primary results across the DeepSeek model family are summarized below:

Configuration Dataset Metric Autoregressive (AR) Standard SD SpecTr GBV SpecTr-GBV (Ours)
DeepSeek-33B (Target)
DeepSeek-1.3B (Draft)
\(L=12, K=3, T=0.4\)
HumanEval BE
SR
1.00
1.00
9.53 ± 1.53
2.02 ± 0.32
10.25 ± 1.37
2.21 ± 0.30
9.60 ± 1.52
2.03 ± 0.32
10.45 ± 1.44
2.50 ± 0.39
GSM8K BE
SR
1.00
1.00
6.83 ± 1.66
1.57 ± 0.42
7.25 ± 1.31
2.26 ± 0.44
6.89 ± 1.44
1.57 ± 0.37
7.65 ± 1.54
2.46 ± 0.58
MGSM BE
SR
1.00
1.00
7.18 ± 1.85
1.55 ± 0.45
8.10 ± 1.86
1.97 ± 0.72
7.37 ± 1.88
1.60 ± 0.47
8.31 ± 1.81
2.12 ± 0.76
LM1B BE
SR
1.00
1.00
8.17 ± 2.76
1.71 ± 0.57
8.93 ± 2.45
1.82 ± 0.47
8.42 ± 2.66
1.75 ± 0.54
8.94 ± 2.51
1.90 ± 0.55
Alpaca BE
SR
1.00
1.00
6.51 ± 2.28
1.36 ± 0.47
7.42 ± 2.18
1.52 ± 0.42
6.89 ± 2.27
1.41 ± 0.54
7.58 ± 2.22
1.60 ± 0.48
Average BE
SR
1.00
1.00
7.64
1.64
8.39
1.96
7.83
1.67
8.59 (+12.4% vs SD)
2.12 (+29.3% vs SD)
DeepSeek-6.7B (Target)
DeepSeek-1.3B (Draft)
\(L=8, K=3, T=0.4\)
HumanEval BE
SR
1.00
1.00
7.06 ± 0.91
1.19 ± 0.15
7.53 ± 0.81
1.15 ± 0.18
7.06 ± 0.92
1.19 ± 0.15
7.70 ± 0.72
1.28 ± 0.12
GSM8K BE
SR
1.00
1.00
5.78 ± 0.55
1.02 ± 0.10
6.55 ± 0.58
1.28 ± 0.11
5.99 ± 0.65
1.04 ± 0.12
6.68 ± 0.72
1.42 ± 0.17
MGSM BE
SR
1.00
1.00
5.84 ± 1.00
1.01 ± 0.18
6.38 ± 1.01
1.06 ± 0.26
5.99 ± 1.01
1.02 ± 0.20
6.60 ± 1.11
1.14 ± 0.31
LM1B BE
SR
1.00
1.00
6.17 ± 1.78
1.02 ± 0.29
6.86 ± 1.66
1.04 ± 0.22
6.42 ± 1.73
1.03 ± 0.27
7.01 ± 1.66
1.12 ± 0.27
Alpaca BE
SR
1.00
1.00
5.81 ± 1.28
1.01 ± 0.17
6.12 ± 1.18
1.00 ± 0.42
5.89 ± 1.27
1.00 ± 0.14
6.23 ± 0.22
1.03 ± 0.18
Average BE
SR
1.00
1.00
6.13
1.05
6.69
1.11
6.27
1.06
6.84 (+11.6% vs SD)
1.20 (+14.3% vs SD)

Ablation Study

Ablation across draft sequence lengths \(L \in \{12, 16, 20, 24\}\) on HumanEval using DeepSeek-33B as target and DeepSeek-1.3B as draft (\(T=0.4, K=3\)):

Draft Length \(L\) Metric Autoregressive (AR) Standard SD SpecTr GBV SpecTr-GBV (Ours) Analysis & Observations
\(L = 12\) BE
SR
1.00
1.00
9.53
2.02
10.25
2.21
9.60
2.03
10.45
2.50
Baseline configuration, consistent lead
\(L = 16\) BE
SR
1.00
1.00
11.36
1.93
12.56
2.56
11.37
1.94
12.63
2.52
BE scales steadily with draft length
\(L = 20\) BE
SR
1.00
1.00
13.10
1.88
13.64
2.55
13.19
1.86
14.58
2.87
Peak wall-clock speedup (2.87×) achieved
\(L = 24\) BE
SR
1.00
1.00
14.63
1.80
16.22
2.33
15.08
1.85
16.52
2.68
BE reaches 16.52, but drafting overhead slightly lowers SR

Key Findings

  • Draft Length Inversion Point: While BE consistently increases monotonically with draft length \(L\) (climbing from 10.45 at \(L=12\) to 16.52 at \(L=24\)), the wall-clock speedup ratio (SR) follows an inverted U-shape trajectory, peaking at \(L=20\) (2.87×). This confirms that generating excessively long draft sequences incurs non-trivial draft model latency that eventually offsets target verification savings.
  • Draft Scaling (\(K\)) vs Throughput: In scaling experiments with \(K \in \{1, 3, 5, 7\}\), acceptance rates for SpecTr-GBV consistently exceed SpecTr, expanding from a 0.78% lead at \(K=1\) to 2.75% at \(K=7\). In the Llama-2-7B / Llama-68M setting (\(L=6\)), increasing \(K\) from 1 to 7 boosts throughput from 44.16 to 68.77 tokens/s (+55.7%) and BE from 1.53 to 3.17 (+107.4%), while peak GPU memory increases modestly by only 14.2% (13,339 MB \(\to\) 15,236 MB).
  • Verification Overhead Reduction: Wall-clock runtime profiling indicates that SpecTr-GBV slashes algorithm-specific verification time by 74.8% on HumanEval compared to SpecTr (0.26s vs 1.03s). Due to early sequence termination and duplicate rejection caching, only 64.78% of the theoretical \(\mathcal{O}(KL)\) candidate sub-blocks are actually evaluated in practice.
  • Robustness Across Temperatures: Sweeping generation temperature across \(T \in \{0.1, 0.4, 0.7\}\) reveals near-identical BE and SR metrics across all tasks, proving that SpecTr-GBV is equally resilient in low-temperature greedy decoding and high-entropy diverse sampling.

Highlights & Insights

  • Theoretical Unification via Optimal Transport: Bridges the long-standing gap between multi-draft sampling and block verification by mathematically proving the optimal expected acceptance length under the conditionally independent coupling (CIC) class.
  • Complexity Optimization from \(\mathcal{O}(|\Omega| \log K)\) to \(\mathcal{O}(|\Omega|)\): Replaces iterative sorting-based sampling with vectorized matrix arithmetic and proactive candidate pruning, avoiding about 35% of worst-case verification evaluations in practice.
  • Lossless Dynamic Distribution Maintenance: Elegant closed-form residual distributions and inter-iteration re-weighting ensure zero distributional divergence (\(P(O_i = x_i) = q(x_i)\)) without heuristics or manual tuning.

Limitations & Future Work

  • Dependency on Draft-Target Distribution Alignment: When the draft model struggles to match the target model distribution in complex out-of-domain contexts, sub-block acceptance rates decline sharply.
  • Memory Footprint with Large Vocabularies: Storing and vectorizing probability calculations across \(K \times L\) token blocks can consume significant GPU memory when dealing with extended vocabulary sizes (e.g., 128k tokens).
  • Restriction to i.i.d. Draft Topologies: The current theoretical proof and algorithm rely fundamentally on independent candidate sequences, leaving tree-structured or graph-based draft representations as an open direction.
  • vs SpecTr (Sun et al., 2023): SpecTr performs token-by-token verification across draft columns, terminating immediately upon a single column-wide rejection. SpecTr-GBV extends verification to multi-token sub-blocks, guaranteeing strictly higher expected acceptance lengths and lowering runtime complexity from \(\mathcal{O}(|\Omega| \log K)\) to \(\mathcal{O}(|\Omega|)\).
  • vs Greedy Block Verification (Sun et al., 2025): GBV pioneered single-draft block verification. SpecTr-GBV generalizes GBV to the multi-candidate space, proving the optimal acceptance bound under conditionally independent couplings.
  • vs MultiPath-GBV (Thomas & Pal, 2026): MultiPath-GBV decouples the process into heuristic path selection followed by single-path block verification. In contrast, SpecTr-GBV performs joint optimal transport verification directly across all candidate sub-blocks.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Elegant theoretical formulation unifying multi-draft sampling and block verification with closed-form CIC optimal transport guarantees.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive cross-model validations (DeepSeek, CodeLlama, Vicuna, Llama-2), fine-grained wall-clock profiling, and extensive hyperparameter ablations.
  • Writing Quality: ⭐⭐⭐⭐⭐ Mathematically rigorous, with transparent proofs and lucid structural exposition.
  • Value: ⭐⭐⭐⭐⭐ Directly deployable, lossless inference acceleration technique offering tangible wall-clock speedups for large-scale LLM serving.