# Traversal Verification for Speculative Tree Decoding arXiv: https://arxiv.org/abs/2505.12398 ยท HTML: https://mlsanity.com/paper/2505.12398/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving. - Builds on 23 of its 32 references that are in the map. - First posted on arXiv 18 May 2025. ## Placed in - Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/) ## Builds on (most cited first, 23 of 23) - [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017) - [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024) - [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021) - [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023) - [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020) - [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024) - [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022) - [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022) - [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023) - [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023) - [LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale](https://mlsanity.com/paper/2208.07339/) (2022) - [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024) - [Abstractive Text Summarization Using Sequence-to-Sequence RNNs and Beyond](https://mlsanity.com/paper/1602.06023/) (2016) - [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024) - [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024) - [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023) - [Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding](https://mlsanity.com/paper/2401.07851/) (2024) - [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023) - [OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure](https://mlsanity.com/paper/2406.17276/) (2024) - [Revisiting Knowledge Distillation for Autoregressive Language Models](https://mlsanity.com/paper/2402.11890/) (2024) - [Block Verification Accelerates Speculative Decoding](https://mlsanity.com/paper/2403.10444/) (2024) - [Towards Optimal Multi-draft Speculative Decoding](https://mlsanity.com/paper/2502.18779/) (2025) - [SpecHub: Provable Acceleration to Multi-Draft Speculative Decoding](https://mlsanity.com/paper/2411.05289/) (2024) ## Built on by (most cited first, 9 of 9) - [Trees from Marginals: Autoregressive drafting with factorized priors](https://mlsanity.com/paper/2607.06763/) (2026) - [Spend Search Where It Pays: Value-Guided Structured Sampling and Optimization for Generative Recommendation](https://mlsanity.com/paper/2602.10699/) (2026) - [TriSpec: Ternary Speculative Decoding via Lightweight Proxy Verification](https://mlsanity.com/paper/2601.23180/) (2026) - [UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding](https://mlsanity.com/paper/2605.04543/) (2026) - [Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling](https://mlsanity.com/paper/2602.16961/) (2026) - [Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding](https://mlsanity.com/paper/2602.16994/) (2026) - [Tsubame: Tree Replay for Diffusion-Based Speculative Decoding](https://mlsanity.com/paper/2609.33652/) (2026) - [BV Loss: Block Verification-Aware Loss for Block Diffusion Speculative Decoding](https://mlsanity.com/paper/2609.34832/) (2026) - [CAST: Cost-Aware Speculative Trees from One-Pass Block Drafters](https://mlsanity.com/paper/2610.00321/) (2026) ## Abstract (arXiv) Speculative decoding is a promising approach for accelerating large language models. The primary idea is to use a lightweight draft model to speculate the output of the target model for multiple subsequent timesteps, and then verify them in parallel to determine whether the drafted tokens should be accepted or rejected. To enhance acceptance rates, existing frameworks typically construct token trees containing multiple candidates in each timestep. However, their reliance on token-level verification mechanisms introduces two critical limitations: First, the probability distribution of a sequence differs from that of individual tokens, leading to suboptimal acceptance length. Second, current verification schemes begin from the root node and proceed layer by layer in a top-down manner. Once a parent node is rejected, all its child nodes should be discarded, resulting in inefficient utilization of speculative candidates. This paper introduces Traversal Verification, a novel speculative decoding algorithm that fundamentally rethinks the verification paradigm through leaf-to-root traversal. Our approach considers the acceptance of the entire token sequence from the current node to the root, and preserves potentially valid subsequences that would be prematurely discarded by existing methods. We theoretically prove that the probability distribution obtained through Traversal Verification is identical to that of the target model, guaranteeing lossless inference while achieving substantial acceleration gains. Experimental results across different large language models and multiple tasks show that our method consistently improves acceptance length and throughput over existing methods.