Research map / Large language models / Reasoning and chain of thought
Block Verification Accelerates Speculative Decoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Block Verification, a joint draft-verification rule for speculative decoding that provably preserves the target distribution, is optimal among valid verifiers in expected tokens per iteration, and yields 5-8% wall-clock speedups over token verification.
Problem
Standard speculative decoding verifies draft tokens one at a time with token-level rejection, which may leave accepted tokens on the table; the question is whether a better verification rule exists that keeps the lossless guarantee.
Approach
Verify the whole draft block jointly by considering sub-blocks of every length, accepting each with a coupled probability computed along the sample path, and keeping the longest accepted sub-block; this is a drop-in replacement for token verification that is never worse and provably optimal among valid verifiers.
Key results
- With gamma=8 and PALM-2-XXS drafter, block verification improves block efficiency by 8.30% on average (7.00% to 10.06%) over token verification.
- Wall clock speedup improves by 6.49% on average (5.36% to 8.14%) across eight datasets.
- On Spec-Bench with Vicuna-7B and Vicuna-68M at temperature 1.0, block efficiency improves by 8.70% and wall clock by 6.07%; no gain at greedy decoding.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace token-by-token verification with joint block verification | Speculative decoding with PALM-2-S and PALM-2-XXS drafter · LM1B, GPT Prompt, WebQA, PIQA, ShareGPT, XSum, GSM8K, WMT-DeEn | block efficiency: 8.68± 0.79%; 10.06± 1.66%; 7.53± 0.24%; 8.30± 0.62%; 8.45± 0.98%; 7.63± 0.94%; 8.74± 0.56%; 7.00± 0.78% | Helped |
| replace token-by-token verification with joint block verification | Speculative decoding with PALM-2-S and PALM-2-XXS drafter · LM1B, GPT Prompt, WebQA, PIQA, ShareGPT, XSum, GSM8K, WMT-DeEn | wall-clock speedup: 6.85± 0.74%; 8.14± 1.55%; 5.75± 0.22%; 6.52± 0.58%; 6.68± 0.91%; 5.82± 0.88%; 6.84± 0.51%; 5.36± 0.73% | Helped |
| replace token-by-token verification with joint block verification | Speculative decoding with Vicuna-7B-v1.3 and Vicuna-68M drafter · Spec-Bench, T=0.2, 0.6, 1.0 | block efficiency: 3.72%; 5.32%; 8.70% | Helped |
| replace token-by-token verification with joint block verification | Speculative decoding with Vicuna-7B-v1.3 and Vicuna-68M drafter · Spec-Bench, T=0.2, 0.6, 1.0 | wall-clock speedup: 1.66%; 4.24%; 6.07% | Helped |
| increase draft length gamma (ablation) | Block verification versus token verification · PALM-2 experiments, across datasets | relative block-efficiency improvement | Helped |
| increase draft length gamma beyond the wall-clock optimum (ablation) | Block verification · PALM-2 experiments, all settings | wall-clock speedup | Hurt |
| use PALM-2-XXS instead of PALM-2-XXXS as drafter (ablation) | Block verification · PALM-2 experiments, across datasets | relative block-efficiency improvement | Helped |
| use greedy decoding (temperature 0) instead of sampling (ablation) | Block verification · Spec-Bench | wall-clock speedup | No clear effect |
Surprising findings
- At temperature 0 (greedy decoding) block verification degenerates to token verification and gives no additional speedup.
Limitations
- Gains are modest (around 5-8% wall clock), and the paper does not study combination with improved drafters systematically.
- Optimality is proven only for single-draft verification; multi-draft extension left open.
- Experiments are limited to PALM-2 and Vicuna models with batch size 1 in the main results.
Experimental setup
Datasets: LM1B GPT Prompt (LearnGPT) WebQA PIQA ShareGPT XSum GSM8K WMT DeEn Spec-Bench
Benchmarks: LM1B GPT Prompt WebQA PIQA ShareGPT XSum GSM8K WMT DeEn Spec-Bench
Metrics: block efficiency wall clock speedup
Baselines: token verification SpecTr multi-round token verification tree Monte Carlo verification
Builds on: speculative decoding token verification
Closest papers by meaning
- BASTION: Budget-Aware Speculative Decoding with Tree-structured Block Diffusion Drafting (NeurIPS 2026 · similarity 0.92)
- Speculative Speculative Decoding (ICLR 2026 · similarity 0.92)
- SpecBlock: Block-Iterative Speculative Decoding with Dynamic Tree Drafting (NeurIPS 2026 · similarity 0.92)
- Traversal Verification for Speculative Tree Decoding (NeurIPS 2025 · similarity 0.92)
- PEARL: Parallel Speculative Decoding with Adaptive Draft Length (ICLR 2025 · similarity 0.91)
- Performance-Driven Policy Optimization for Speculative Decoding with Adaptive Windowing (NeurIPS 2026 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.