Research map / Large language models / Reasoning and chain of thought

Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Speculative decoding · 0 citations (OpenAlex)

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 Hierarchical Speculative Decoding (HSD), a provably lossless token-block verification method that redistributes excess and deficient probability mass across branches via capped branch resampling, improving block efficiency and decoding speed over tokenwise and blockwise verification with Qwen2.5 models.

Problem

Verification in speculative decoding is a bottleneck: joint sequence-level verification would require full joint probabilities over all decoding paths, which is intractable for autoregressive models, so existing methods either are lossy or only partially exploit joint verification.

Approach

Organize resampling distributions hierarchically over accessible branches so that excess draft mass in one branch offsets deficits in others; a capped prefix ratio lets each branch resample only with accessible conditional probabilities, and a single resampling step within accessible branches suffices, avoiding extra target calls.

Key results

• HSD improves block efficiency over tokenwise verification by 3.3% to 12.3% across GSM8K, HumanEval and CNN/DailyMail at 14B/32B/72B targets, with an average of about 6.2% BE and 6.7% decoding speed gain.
• Integrating HSD into EAGLE-3 gives 12.4% decoding speed gain (71.59 to 80.49 tokens/s) with block efficiency 3.40 to 3.55.
• In multi-draft setting with 11 drafts, HSD yields an average 5.9% block efficiency and 4.7% decoding speed improvement over token-wise verification.

Surprising findings

• With EAGLE-3's top-K drafting (all draft probabilities equal to 1), any verification method theoretically degenerates to the same behavior, so block-efficiency gains are likely due to sampling stochasticity and floating-point precision; the speedup is attributed to implementation differences.

Limitations

• Gains are modest (typically a few percent) on most settings, and larger target models show smaller improvements.
• Gains in EAGLE-3 integration with top-K sampling are attributed to stochasticity and implementation rather than the verification rule itself.
• Multi-draft comparison omits Blockwise verification because it is not straightforward to extend it to multi-draft.

Experimental setup

Datasets: GSM8K HumanEval CNN/DailyMail

Benchmarks: GSM8K HumanEval CNN/DailyMail

Metrics: block efficiency (tokens/step) decoding speed (tokens/second)

Baselines: Tokenwise verification Blockwise verification EAGLE-3 Recursive Reject Sampling

Builds on: speculative sampling Block Verification EAGLE-3 Recursive Reject Sampling

Closest papers by meaning

• Block Verification Accelerates Speculative Decoding (ICLR 2025 · similarity 0.91)
• PEARL: Parallel Speculative Decoding with Adaptive Draft Length (ICLR 2025 · similarity 0.91)
• Traversal Verification for Speculative Tree Decoding (NeurIPS 2025 · similarity 0.90)
• UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding (NeurIPS 2026 · similarity 0.90)
• VIA-SD: Verification via Intra-Model Routing for Speculative Decoding (ICML 2026 · similarity 0.90)
• Speculative Speculative Decoding (ICLR 2026 · similarity 0.90)