🤖 machine learning

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

This paper proposes Greedy Multi-Path Block Verification (GBV), an efficient algorithm that extends optimal block verification to multiple draft paths using a linear programming framework, achieving over 30% better block efficiency and 15% faster decoding throughput compared to state-of-the-art methods.

Original authors: Rahul Thomas, Arka Pal

Published 2026-02-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rahul Thomas, Arka Pal

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, perfect story, but you are writing it very slowly because every time you think of a word, you have to ask a super-smart, but very slow, "Grandmaster Editor" to check if it's the right word. This is how current AI models (Large Language Models) work: they generate text one word at a time, and for every word, they have to do a massive, slow calculation to make sure it's correct.

Speculative Sampling is a trick to speed this up. Instead of asking the Grandmaster Editor for every single word, you use a Speedy Assistant (a smaller, faster model) to guess the next 8 words for you. Then, you ask the Grandmaster Editor to check those 8 guesses all at once. If the Editor agrees with the Assistant, you get 8 words for the price of 1! If the Editor disagrees, you only keep the words they agreed on and try again.

The paper you shared introduces a new, smarter way to do this checking process called Greedy Multi-Path Block Verification (GBV). Here is how it works, broken down with simple analogies:

1. The Problem: The "First Word" Bottleneck

In the old way of doing this (Standard Speculative Sampling), the Speedy Assistant guesses a straight line of words: Word 1, Word 2, Word 3...
The Grandmaster Editor checks them one by one.

The Issue: If the Assistant guesses the first word wrong, the Editor rejects it immediately. Even if words 2 through 8 were perfect, you get nothing. It's like a relay race where the first runner trips; the whole team loses, even if the others were fast.

2. The Previous Fix: "Block Verification" (BV)

Researchers realized that instead of checking word-by-word, they should check the whole group of words together.

The Analogy: Imagine the Assistant writes a whole paragraph. The Editor doesn't just check the first sentence; they look at the whole paragraph and say, "Okay, the first 3 sentences are great, but the 4th is weird. Let's keep the first 3."
The Result: This is better because even if the first word is shaky, if the group makes sense, you might still keep a few words. This is called Block Verification (BV).

3. The New Solution: "Greedy Multi-Path Block Verification" (GBV)

The authors of this paper asked: "What if the Speedy Assistant doesn't just write one paragraph, but writes four different paragraphs at the same time?"

Since modern computers (GPUs) are like super-fast assembly lines, they can generate 4 different guesses simultaneously without much extra cost.

The Analogy: Imagine you are a chef. Instead of asking one sous-chef to guess the recipe for a cake, you ask four sous-chefs to write down four different cake recipes at the same time.
- Chef A writes: "Flour, Sugar, Eggs..."
- Chef B writes: "Flour, Cocoa, Milk..."
- Chef C writes: "Flour, Honey, Yogurt..."
- Chef D writes: "Flour, Salt, Water..."

Now, you (the Grandmaster Editor) look at all four lists. You don't just pick the first one. You look at all of them and say, "Chef B's first two ingredients are perfect! Chef A's first one is okay, but the second is wrong. Chef C's first one is wrong."

GBV is the smart rulebook that decides:

Look at all 4 paths (paragraphs).
Pick the one that looks the "best" overall (the Greedy part).
Check that specific path against the Grandmaster Editor's rules.

Why is this a big deal?

The paper proves mathematically that this "Multi-Path" approach is the most efficient way to use the computer's power.

The "Tree" Metaphor: Imagine the guesses are branches of a tree. The old methods walked down one branch. The new method looks at the whole tree, picks the strongest branch, and walks down that.
The Result: By looking at multiple options at once, the AI rarely gets stuck on a "bad first word." It almost always finds a path where the first few words are correct.

The Real-World Impact

The authors tested this on powerful AI models (like Llama-3).

Speed: They found that this method makes the AI 15% to 30% faster than previous methods.
Efficiency: It's like upgrading from a bicycle to a sports car. You are still using the same engine (the AI model), but you are getting to your destination much quicker because you aren't wasting time on dead-end roads.

Summary

Think of GBV as a "Safety Net" for AI speed.

Old Way: Guess one path. If it fails early, you lose time.
New Way (GBV): Guess four paths at once. Pick the best one. Even if one path fails, another might succeed. You almost never lose time, and you get more words generated per second.

It's a clever way of using the computer's ability to do many things at once to trick the AI into thinking it's working faster, without actually making the AI "dumber."

1. Problem Statement

Large Language Models (LLMs) suffer from high inference latency, which is often dominated by memory bandwidth rather than compute. Speculative Sampling is a technique used to mitigate this by using a smaller, faster "draft" model to propose a sequence of $L$ tokens, which are then verified by the larger "target" model in a single forward pass.

The paper addresses two specific limitations in existing speculative decoding methods:

Early-Token Bottleneck: Standard speculative sampling verifies tokens independently. If the first draft token is rejected, the entire block is discarded, yielding no speedup even if subsequent tokens were correct.
Sub-optimality of Multi-Path Methods: While recent "Block Verification" (BV) methods improved efficiency by verifying prefixes jointly, they are limited to single-path drafts. Existing multi-path methods (generating $K > 1$ draft sequences) often rely on complex tree traversals or Optimal Transport Linear Programs (OTLP) that do not fully exploit the joint probability space or are computationally inefficient.

The core question is: How can we optimally verify multiple candidate draft paths to maximize the number of accepted tokens (block efficiency) while maintaining the target model's distribution, without incurring prohibitive computational overhead?

2. Methodology

The authors approach the problem through a theoretical framework based on Linear Programming (LP) and Greedy Approximations.

A. Theoretical Foundation: Information-Agnostic LPs

The authors formulate the verification problem as an optimization task to find the maximum possible block efficiency.

Single-Path LP: They define a Linear Program that encodes the constraints of valid verification algorithms (Prefix-matching and Target-matching). Crucially, they prove that even if an algorithm has access to off-path probabilities (the full joint distribution of target and draft models, not just the sampled path), Block Verification (BV) remains the optimal solution. This implies that the bottleneck is not a lack of information, but the structural requirement to output a prefix of the draft.
Multi-Path LP: They extend the LP to the setting where $K$ $K$ draft paths are sampled independently. Here, they prove that off-path information becomes valuable. The optimal strategy involves:
1. Randomly selecting one of the $K$ paths based on a rule $\Gamma$ .
2. Running Block Verification on that selected path using a "skewed" draft distribution $q_\Gamma$ induced by the selection rule.
3. The optimal $q_\Gamma$ satisfies a submodular constraint derived from the probability of the union of prefixes across $K$ paths.

B. The Algorithm: Greedy Multi-Path Block Verification (GBV)

Solving the Multi-Path LP exactly is intractable because it requires knowledge of the full joint distributions and involves non-linear optimization. The authors propose a tractable approximation:

Greedy Approximation: They restrict the search space to greedy algorithms that globally rank all possible paths and select the highest-ranked one.
Tree-Based Ranking: To ensure efficiency, they define a tree-based ranking rule where the local ordering at each node is determined by the ratio $p(x|context) / q(x|context)$. This allows the algorithm to compute the necessary skewed probabilities using only on-path values (no off-path information required).
GBV Execution:
1. Sample $K$ draft paths.
2. Rank them lexicographically based on the $p/q$ ratios along the paths.
3. Select the highest-ranked path.
4. Compute the skewed draft probabilities $q_{\Gamma_g}$ for this path using a closed-form expression derived from the ranking.
5. Run standard Block Verification on the selected path using the target distribution $p$ and the skewed draft distribution $q_{\Gamma_g}$ .

3. Key Contributions

Optimality of Block Verification (Single-Path): Proved that Block Verification is optimal even when algorithms have access to full off-path joint distributions. This establishes that the "prefix-matching" constraint is the fundamental barrier to further efficiency gains in single-path settings.
Multi-Path Theoretical Limits: Developed a Multi-Path Information-Agnostic LP showing that for $K > 1$ , utilizing off-path information (via path selection) can theoretically improve block efficiency beyond single-path limits.
GBV Algorithm: Proposed Greedy Multi-Path Block Verification (GBV), a practical, efficient algorithm that approximates the optimal multi-path solution. It uses a tree-based greedy ranking to select the best path and adjusts the draft distribution for verification.
Empirical Validation: Demonstrated that GBV significantly outperforms existing state-of-the-art (SOTA) multi-path methods (like SpecTr, SpecInfer, and Traversal Verification) in specific regimes, particularly at lower temperatures.

4. Experimental Results

The authors evaluated GBV on various model pairs (OPT, Qwen-3, Llama-3) and datasets (GSM8K, HumanEval, MATH500).

Block Efficiency:
- Increasing the number of draft paths ( $K$ ) from 1 to 4 generally improves block efficiency.
- For OPT 6.7B, GBV with $K=3$ improved block efficiency by ~23% over standard Block Verification ( $K=1$ ).
- However, for larger models like Qwen-3 32B and Llama-3 70B, the benefits of $K > 1$ were less consistent due to increased drafting overhead. In these cases, $K=1$ (standard BV) was often optimal.
Walltime (Latency):
- OPT Models: GBV reduced decoding walltime by >15% (e.g., from ~44ms/token to ~38ms/token) with $K=3$ .
- Llama-3 70B: GBV improved end-to-end throughput by >15% compared to SOTA multi-path methods in specific settings.
- Temperature Sensitivity: A critical finding is that GBV performs exceptionally well at low temperatures (e.g., 0.2). At temperature 0.2, GBV ( $K=2$ or $3$) significantly outperforms both Block Verification and Traversal Verification, achieving the highest throughput (e.g., 11.5 tokens/s on Llama-3 70B, whereas no other method exceeded 10 tokens/s).
Comparison to SOTA:
- At temperature 1.0, Traversal Verification sometimes slightly outperforms GBV.
- At temperature 0.2, GBV is the clear winner, beating Traversal Verification by up to 1.6 tokens/s.

5. Significance

Theoretical Insight: The paper provides a rigorous theoretical boundary for speculative sampling, proving that single-path methods are already optimal given their constraints, and that gains must come from multi-path strategies that intelligently select paths.
Practical Efficiency: GBV offers a simple, low-overhead method to accelerate LLM inference without requiring complex tree structures or expensive linear programming solvers during inference.
Temperature Adaptability: The discovery that GBV excels at low temperatures (where distributions are sharper) suggests that speculative decoding strategies should be adaptive based on the sampling temperature, a nuance often overlooked in previous works.
System Optimization: The work highlights the trade-off between block efficiency (tokens per call) and walltime (latency), showing that for very large models, the cost of generating multiple draft paths can negate efficiency gains, necessitating careful tuning of $K$ and $L$ .

In summary, this paper advances speculative decoding by theoretically grounding the limits of verification algorithms and introducing GBV, a highly efficient, greedy multi-path algorithm that achieves state-of-the-art performance, particularly in low-temperature regimes.