Hierarchical Speculative Decoding (HSD)

Hierarchical Speculative Decoding (HSD) is a state-of-the-art lossless verification algorithm for accelerating large language model (LLM) inference. HSD verifies draft outputs using the joint probability of multiple draft tokens and reconstructs the target model’s joint distribution through a hierarchy of resampling distributions across different branches. This hierarchical verification enables HSD to accept more tokens in expectation than both token-wise and block-wise verification methods, while strictly preserving the target model’s output distribution—i.e., without any degradation in model performance.

Moreover, its strong explainability and generality make it readily integrable into a wide range of speculative decoding frameworks. Notably, HSD serves as a drop-in replacement for token-wise verification. For example, by directly replacing the token-wise verification in a pre-fine-tuned EAGLE-3 model, HSD achieves over a 12% performance improvement without requiring any additional fine-tuning.

Table of Contents

• Hierarchical Speculative Decoding (HSD)
  • Table of Contents
  • Experiment Settings
    • Experiments Setup
    • Baselines and Metrics
  • Reproduce Experiment Results on GSM8K
    • Requirements
    • Single-Draft Verification
    • Multi-Draft Verification with Recursive Reject Sampling
    • Compute Metrics
    • GSM8K Performance Results
      • Accuracy Comparison (Table 2)
      • Block Efficiency & Speed (Table 3)
  • EAGLE Integration
    • EAGLE + HSD Results
  • Citation
  • References

Experiment Settings

Experiments Setup

Experiments are conducted with the widely adopted GPTQ-quantized 8-bit instruction-tuned Qwen2.5 series Bai et al., 2023. By default, we employ the 0.5B model as the draft model and 72B as the target model, with a temperature of 1. All experiments were conducted on a single NVIDIA H20 GPU with 96 GB of memory, unless otherwise specified.

Baselines and Metrics

We compare two lossless verification methods—Token-wise Leviathan et al., 2023 and Block-wise Sun et al., 2024—using two metrics: Block Efficiency (tokens/step) and Decoding Speed (tokens/second).

• Block Efficiency measures the average tokens generated per serial call to the target model, reflecting intrinsic efficiency independent of hardware.
• Decoding Speed indicates tokens produced per second for practical reference, though it depends on hardware and implementation.

Reproduce Experiment Results on GSM8K

Requirements

Please install python=3.10 and transformers=4.46.3, then copy the provided files under the transformers directory to:

anaconda3/envs/your_environment_name/lib/python3.10/site-packages/transformers/

Then navigate to chain-of-thought-hub/gsm8k:

cd chain-of-thought-hub/gsm8k

Single-Draft Verification

Baseline methods:

• Tokenwise verification

  bash eval_speculative_qwen.sh
  

Our methods:

• HSD (clever) - optimized with smart capping mechanism

  bash eval_speculative_qwen_backward_clever.sh
  

Multi-Draft Verification with Recursive Reject Sampling

Extends HSD to use multiple independently sampled drafts for even better performance.

• Tokenwise multidraft

  bash eval_speculative_qwen_multidraft_11.sh
  

• HSD multidraft

  bash eval_speculative_qwen_backward_clever_multidraft_11.sh
  

Compute Metrics

Finally, evaluate Block Efficiency and Decoding Speed:

python compute_speculative_stats.py

GSM8K Performance Results

Using Qwen2.5-0.5B as draft model on GSM8K:

Table 1: Accuracy Comparison

HSD maintains or slightly improves accuracy (both Token-wise and HSD are lossless methods, so any deviations are due to randomness) while offering significantly faster inference.

Table 2: Block Efficiency & Speed

HSD consistently improves both Block Efficiency (BE) and Decoding Speed (DS) relative to Tokenwise and Blockwise verification. For GSM8K, the gains are stable across scales, with BE improvements of 5.2%-5.4% at 14B/32B and 3.3% at 72B, accompanied by DS increases of up to 10.7%.

EAGLE Integration

HSD can be integrated with EAGLE-3 to further improve performance. EAGLE-3 fine-tunes an additional component to predict draft tokens from the target model's hidden features, eliminating the need for a separate draft model and thereby improving decoding speed.

To demonstrate HSD’s compatibility with advanced decoding systems, we integrated it into the state-of-the-art EAGLE-3-LLaMa3.1-Instruct-8B (with a default draft length of 7) by replacing its token-wise verifier, as shown in Table 3. Importantly, HSD operates orthogonally to the drafting phase, so it can be used directly with a pre-fine-tuned EAGLE-3 model without requiring any additional fine-tuning.

Table 3: EAGLE-3 + HSD (EAGLE-3H) Results

For EAGLE integration setup, see the EAGLE-hsd/ directory in this repo.

cd EAGLE-3H
bash eagle_eval.sh

Citation

@misc{zhou2026overcomingjointintractabilitylossless,
      title={Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding}, 
      author={Yuxuan Zhou and Fei Huang and Heng Li and Fengyi Wu and Tianyu Wang and Jianwei Zhang and Junyang Lin and Zhi-Qi Cheng},
      year={2026},
      eprint={2601.05724},
      archivePrefix={arXiv},
      primaryClass={cs.AI},
      url={https://arxiv.org/abs/2601.05724}, 
}

References

1. Chain-of-Thought Hub
2. EAGLE-3 Repository