💬 NLP

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

This paper introduces SpecTr-GBV, a novel speculative decoding framework that unifies multi-draft generation with greedy block verification by formulating token verification as an optimal transport problem, thereby achieving theoretically optimal acceptance lengths and superior empirical speedup while maintaining output quality.

Original authors: Yijun Lin, Jinhao Sheng, Qingyue Cai, Feng Zhou

Published 2026-04-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yijun Lin, Jinhao Sheng, Qingyue Cai, Feng Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to write a long story, but you have a very strict editor (the Target Model) who is incredibly intelligent but moves very slowly. Every time you want to add a new word, you must wait for the editor to reread the entire sentence and decide whether that word fits. This makes writing the story take an eternity.

Speculative Decoding is a clever trick to speed up this process. You hire a fast and energetic intern (the Draft Model) to guess the next words for you. The editor then quickly checks these guesses. If the guesses are correct, the editor says "Good!" and you move on. If they are wrong, the editor corrects them. This saves time because the intern can guess several words at once, and the editor only has to do the bulk of the work occasionally.

The Problem with Current Methods

The article highlights that existing methods for this "intern" system have two major flaws:

The "One-by-One" Problem: Some methods require the intern to make a single guess, verify it, and then make another. This is slow.
The "Single Intern" Problem: Other methods ask the intern to write an entire paragraph, but they have only one intern. If this intern makes a mistake at the beginning of the paragraph, the entire paragraph is discarded, and you must start over.

Some researchers have attempted to solve this problem by hiring multiple interns (Multi-Draft) to write different versions of the next words, hoping that at least one will be correct. Others have tried to verify the entire paragraph at once (Block Verification) instead of word by word. But until now, no one had succeeded in combining multiple interns with whole-paragraph verification.

The Solution: SpecTr-GBV

The authors propose a new system called SpecTr-GBV. Imagine it as an ultra-efficient editorial team with a new workflow:

The "Squad" of Interns: Instead of a single intern, they hire a squad of $K$ interns. Each intern writes their own version of the next words (a "draft").
"Block" Verification: Instead of checking word #1, then word #2, then word #3, the editor examines the entire block of words from all interns at once.
Selecting the "Best Fit": The editor uses a mathematical strategy (called Optimal Transport, which resembles a smart matching game) to find the longest possible sequence of words that any one of the interns got right.

The Analogy:
Imagine you are trying to cross a river by jumping on stones.

Old Method: You ask one person to guess where the stones are. You jump one stone at a time. If you miss, you fall into the water and start over.
New Method (SpecTr-GBV): You ask five people to guess where the stones are. You examine all five guesses together. You find the longest path of stones that someone guessed correctly. You jump as far as possible along that path. If you still cannot cross the entire river, you simply jump to the next safe spot and ask for new guesses.

Why It Is Better

The article claims that this new method is the "optimal" way to proceed. Here is what that means in plain French:

Maximum Success: Theoretically, this method is proven to achieve the longest possible "streak" of accepted words. You cannot do better without changing how the interns work.
More Interns = More Speed: The more interns you hire (the more drafts you generate), the longer the streak of correct words becomes. It is like having more eyes on the problem; the chances that someone guesses the next correct word increase.
No Loss of Quality: Even though it is faster, the final story is written exactly the same way as if the slow editor had done it alone. The quality does not drop.

The Results

The authors tested this on five different types of tasks (such as writing code, solving math problems, and writing stories) using different AI models.

Faster: Their method was significantly faster than standard ways of doing this. In some cases, it was nearly 30% faster than the previous best method.
More Efficient: It managed to accept more correct words per second, meaning the slow editor had less work to do.
Robust: It worked well even when they modified the parameters (such as the level of "creativity" allowed for the interns).

In summary, SpecTr-GBV is a smarter way to use a fast assistant to help a slow expert, ensuring that you get the most out of every guess made by the assistant, which leads to a much faster writing process without losing any quality.

1. Problem Statement

Autoregressive Large Language Models (LLMs) suffer from high inference latency due to their sequential token generation, where each token requires a full forward pass. Speculative Decoding (SD) mitigates this by using a smaller "draft" model to propose candidate tokens, which are then verified by a larger "target" model.

However, existing SD methods, when considered in isolation, face two distinct limitations:

Single-Draft Limitations: Standard SD uses only one draft sequence, resulting in low acceptance rates.
Trade-off between Multi-Draft and Block Verification:
- Multi-Draft Methods (e.g., SpecTr): Generate multiple independent draft sequences to enlarge the pool of candidates. However, they typically verify tokens position-wise (column-wise). This sequential verification stops as soon as a token at a specific position is rejected, failing to maximize the total number of accepted tokens in a single iteration.
- Block Verification Methods (e.g., GBV): Verify entire blocks of tokens jointly rather than token-by-token, achieving optimal acceptance for a single draft. However, they do not leverage the benefits of multiple draft sequences.

The Core Question: Can the advantages of multi-draft generation (increasing candidate diversity) and greedy block verification (optimizing acceptance within a block) be combined to achieve the theoretically maximum acceptance length?

2. Methodology: SpecTr-GBV

The authors propose SpecTr-GBV, a framework that combines multi-draft generation with Greedy Block Verification (GBV).

Core Concept

Instead of verifying tokens position-wise (as in SpecTr) or verifying a single block (as in GBV), SpecTr-GBV performs the following steps:

Generate $K$ independent and identically distributed (i.i.d.) draft sequences of length $L$ .
Formulate the verification step as an Optimal Transport (OT) problem between the set of $K$ draft token blocks and the target token block.
Iterate through the $K$ draft sequences to find the longest accepted sub-block across all drafts.

Algorithmic Flow

The verification process (Algorithm 1) proceeds as follows:

Initialization: Start with an acceptance length $\tau = 0$ . A set $H$ of rejected sub-blocks is maintained to avoid redundant sampling.
Sequential Iteration: Iterate through each of the $K$ draft sequences ( $x^L_1, \dots, x^L_K$ ).
Sub-block Verification: For a current sequence, sub-blocks starting at position $\tau + 1$ $τ + 1$ are verified.
- The acceptance probability $h_{ik}$ for a sub-block $x^i_k$ is calculated using a derived formula (Equation 2), which accounts for the joint probability of the sub-block across all $K$ drafts.
- Upon acceptance, $\tau$ is updated to the new length, and the sequence index is recorded.
- Upon rejection, the sub-block is added to the set $H$ and skipped in future iterations.
Termination:
- If the entire block of a draft is accepted, a correction token is sampled from the target model.
- If the process stops at a length $\tau < L$ , a correction token is sampled from a residual distribution (Equation 4) to ensure distributional fidelity.
Distribution Modification: Before the next SD iteration, the target distribution for non-accepted positions is modified (Algorithm 2) to ensure consistency with the original target model distribution.

Theoretical Foundation

Optimal Transport Formulation: The method is formulated as minimizing a cost function over conditionally independent couplings (CIC).
Optimality: The authors prove that SpecTr-GBV achieves the optimal expected acceptance length that is physically achievable within the framework of i.i.d. draft generation.
Monotonicity: The theoretical upper bound for the expected acceptance length strictly increases as the number of drafts ( $K$ ) increases.

3. Main Contributions

Unified Framework: SpecTr-GBV is the first method to unify multi-draft strategies and block verification in a single framework, extending GBV from single-draft to multi-draft scenarios.
Theoretical Guarantees:
- Proof that the method preserves the output distribution of the target model.
- Proof that it achieves the maximum possible expected acceptance length for a fixed number of drafts.
- Demonstration that this optimal bound improves as the number of drafts increases.
Efficiency:
- Reduction of computational complexity per selection step to $O(|\Omega|)$ (where $|\Omega|$ is the vocabulary size), which is more efficient than the binary search for scaling factors in SpecTr with $O(|\Omega| \log K)$ .
- Elimination of the need for expensive linear programming solutions for the OT problem.

4. Experimental Results

The authors evaluated SpecTr-GBV on five datasets (HumanEval, GSM8K, MGSM, LM1B, Alpaca) using four baselines (Autoregressive, Standard SD, SpecTr, GBV) with DeepSeek, CodeLlama, and Vicuna models.

Key Findings:

Performance: SpecTr-GBV consistently outperforms all baselines.
- Compared to Standard SD: ~12.4% improvement in Block Efficiency (BE) and ~29.3% improvement in Speedup Ratio (SR) (DeepSeek-33B setting).
- Compared to SpecTr: ~2.3% improvement in BE and ~8.2% improvement in SR.
- Compared to GBV: ~9.7% improvement in BE and ~27.0% improvement in SR.
Time Efficiency:
- The number of decoding iterations decreased by an average of 2.6%.
- Verification overhead was reduced by >50% compared to SpecTr, due to the removal of the binary search for $\rho$ .
- Total wall-clock time decreased by 6.3% to 11.8%, depending on the dataset and model size.
Ablation Studies:
- Number of Drafts ( $K$ ): Acceptance rates increase monotonically with $K$ , confirming theoretical predictions. SpecTr-GBV maintains higher acceptance rates than SpecTr across all $K$ .
- Draft Length ( $L$ ): BE improves with larger $L$ , but SR eventually decreases due to the computational cost of generating long drafts.
- Temperature ( $T$ ): The method is robust across various sampling temperatures (0.1, 0.4, 0.7).

5. Significance

SpecTr-GBV represents a significant advancement in accelerating LLM inference. By theoretically proving that combining multi-draft generation with block-level verification yields the optimal acceptance length, it sets a new standard for speculative decoding.

Practical Impact: It offers a "plug-and-play" improvement for existing SD pipelines, significantly reducing latency without compromising output quality (distributional fidelity).
Scalability: The method scales effectively with the number of draft models, suggesting that future hardware enabling the parallelization of multiple small models could achieve even greater speedups.
Theoretical Insight: It clarifies the open question of whether multi-draft and block verification can be optimally combined, providing a rigorous mathematical foundation for future research in efficient decoding.