SpecTr-GBV: Unifying Multi-Draft and Block Verification for Faster Speculative Decoding

Large language models generate tokens autoregressively, causing high inference latency as model size grows. Speculative decoding (SD) accelerates this by using a lightweight draft model to propose candidate tokens, which the target model verifies in parallel, reducing expensive target-model forward passes.

Background and Bottleneck

Standard SD generates a single draft sequence of length L. The target model computes the true conditional distribution for each position and applies rejection sampling sequentially. Once a token is rejected, subsequent tokens are discarded. This limits the number of accepted tokens per iteration to the prefix match length between draft and target distributions.

Existing Approaches: Two Separate Lines

Multi-draft (e.g., SpecTr, NeurIPS 2023): Generates K independent draft sequences. At each position, optimal transport couples the draft and target distributions to select an acceptable token from the K candidates. Increasing K raises the probability that at least one candidate is accepted.

Block verification (GBV): In a single-draft setting, verifies prefix sub-blocks as a whole rather than token-by-token, proving it achieves the optimal expected acceptance length per iteration.

These two lines have been designed separately: multi-draft expands candidate diversity, while block verification extends the maximum accepted block length.

SpecTr-GBV: Unified Framework via Optimal Transport

SpecTr-GBV unifies both ideas. Starting from K i.i.d. draft sequences of length L, it treats every prefix of every draft as a candidate sub-block. The acceptance length is defined as the maximum i such that at least one draft's length- i prefix exactly matches the target's length- i prefix. The verification objective becomes maximizing the expected acceptance length over the joint distribution of draft blocks and target block.

Step 1: Construct Coupling as Optimal Transport

The verification is formulated as an optimal transport problem: find a coupling between the multi-draft block distribution and the target block distribution that preserves marginals while maximizing expected acceptance length. Because drafts are generated independently, the authors restrict to conditionally independent couplings (CIC) , matching the algorithmic structure where drafts are not jointly adapted.

Step 2: Greedy Block Verification per Draft

Algorithmically, SpecTr-GBV processes each draft sequentially. For each draft, it performs block-level verification from short to long prefixes, retaining the longest sub-block that passes. If a draft yields no longer acceptable prefix, the next draft is examined. The overall accepted block is the longest among all drafts.

Step 3: Residual Sampling and Distribution Correction

If the longest accepted block does not cover the full length L, the next token is sampled from the residual distribution (target minus accepted mass). If the entire length L is accepted, an extra token is generated from the target model. Unaccepted positions' target distributions are corrected before the next speculative iteration to maintain cross-iteration output distribution consistency.

Theoretical Guarantees

The paper derives an upper bound on expected acceptance length for any coupling in the CIC class and proves three properties:

Monotonicity: The bound strictly increases with draft count K — more independent drafts increase the chance of a longer matching prefix.

Convergence: As K → ∞, the bound approaches the maximum block length L.

Consistency: When K=1, the bound reduces to the single-draft case, matching GBV.

SpecTr-GBV is proven to achieve this upper bound, making it optimal within the CIC class for any fixed K, with optimality improving as K grows.

Experimental Evaluation

Evaluated on five datasets: HumanEval (Python code), GSM8K (grade-school math), MGSM (multilingual math), LM1B (language modeling), and Alpaca (instruction following). Two target-draft pairs: DeepSeek-33B/1.3B and DeepSeek-6.7B/1.3B. Baselines: Autoregressive Decoding (AR), standard Speculative Decoding (SD), SpecTr, and GBV.

Two metrics reported:

Block Efficiency (BE): Average tokens decoded per serial target-model call.

Speedup Ratio (SR): Wall-clock time of AR divided by method's time, capturing end-to-end speedup including draft generation overhead and batch verification latency.

SpecTr-GBV achieves higher BE and SR than all baselines on all five tasks under both model configurations. The paper notes that SR is typically lower than BE because BE ignores draft generation cost and target-model batch verification latency — an engineering reality in SD systems.

Ablation Studies

Draft number K (1, 3, 5, 7): Both SpecTr-GBV and SpecTr show rising acceptance rates with larger K, consistent with theory; SpecTr-GBV maintains higher acceptance at every setting.

Draft length L (12, 16, 20, 24): BE increases monotonically with L, but SR peaks then declines. Longer drafts offer more acceptance potential but increase draft generation cost; when that cost outweighs saved target calls, actual speedup drops.

Temperature T (0.1, 0.4, 0.7) with L=12,16 : BE and SR vary little, indicating robustness across the tested temperature range.

Limitations and Future Work

SpecTr-GBV's efficiency still depends on draft-target alignment. Computational complexity and memory may grow with vocabulary size, draft length, or draft count. The current theory and algorithm assume i.i.d. draft sequences; extensions to non-independent structures (e.g., tree-based candidates) remain for future research.

OpenReview: https://openreview.net/forum?id=4BZ8R9wHhy