Research map / Probabilistic and scientific modeling / Molecules and proteins
Traversal Verification for Speculative Tree 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 Traversal Verification, a bottom-up leaf-to-root verification algorithm for speculative tree decoding that uses sequence-level acceptance, proven lossless and single-chain optimal, improving acceptance length by 2.2-5.7% over token-level verification.
Problem
Token-level verification in speculative tree decoding yields suboptimal acceptance length because per-token acceptance ignores sequence probability, and top-down layer-by-layer verification discards all children once a parent is rejected, wasting drafted candidates.
Approach
Verify draft token trees from leaves to root (bottom-up), computing acceptance rates over whole sequences from each node to the root, and recursively reallocating residual distributions after rejections so that sibling/descendant candidates are still usable; the method is a plug-and-play replacement for token-level verification.
Key results
- Traversal Verification improves average acceptance length over token-level verification by 2.2%-5.7% across chain, binary tree and EAGLE sparse tree configurations on Llama3.2-1B/Llama3.1-8B and Llama-68M/Llama2-7B.
- With Llama3.2-1B draft and Llama3.1-8B target at temperature 1, average acceptance length rises from 3.88 to 3.99 (chain) and 4.63 to 4.73 (binary tree).
- Throughput gains are smaller than acceptance-length gains (e.g., 2.5% and 1.7% token/s improvements on the same setup) due to bottom-up verification overhead.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace token-level verification with Traversal Verification | Llama3.2-1B-Instruct / Llama3.1-8B-Instruct · Spec-Bench Avg. Accept. (Chain) | acceptance length: 3.88 -> 3.99 | Helped |
| Replace token-level verification with Traversal Verification | Llama3.2-1B-Instruct / Llama3.1-8B-Instruct · Spec-Bench Avg. Accept. (Binary Tree) | acceptance length: 4.63 -> 4.73 | Helped |
| Replace token-level verification with Traversal Verification | Llama3.2-1B-Instruct / Llama3.1-8B-Instruct · Spec-Bench Avg. Accept. (EAGLE Sparse Tree) | acceptance length: 4.49 -> 4.60 | Helped |
| Replace token-level verification with Traversal Verification | Llama-68M / Llama2-7B · Spec-Bench Avg. Accept. (Chain) | acceptance length: 1.99 -> 2.10 | Helped |
| Replace token-level verification with Traversal Verification | Llama-68M / Llama2-7B · Spec-Bench Avg. Accept. (Binary Tree) | acceptance length: 2.44 -> 2.56 | Helped |
| Replace token-level verification with Traversal Verification | Llama-68M / Llama2-7B · Spec-Bench Avg. Accept. (EAGLE Sparse Tree) | acceptance length: 2.52 -> 2.62 | Helped |
| Replace token-level verification with Traversal Verification | Llama3.2-1B-Instruct / Llama3.1-8B-Instruct · Spec-Bench Avg. Token/s (Chain) | token/s: 51.2 -> 52.5 | Helped |
| Replace token-level verification with Traversal Verification | Llama3.2-1B-Instruct / Llama3.1-8B-Instruct · Spec-Bench Avg. Token/s (Binary Tree) | token/s: 54.0 -> 54.9 | Helped |
| Replace token-level verification with Traversal Verification | Llama3.2-1B-Instruct / Llama3.1-8B-Instruct · Spec-Bench Avg. Token/s (EAGLE Sparse Tree) | token/s: 57.3 -> 58.5 | Helped |
| Replace token-level verification with Traversal Verification | Llama-68M / Llama2-7B · Spec-Bench Avg. Token/s (Chain) | token/s: 58.0 -> 60.8 | Helped |
| Replace token-level verification with Traversal Verification | Llama-68M / Llama2-7B · Spec-Bench Avg. Token/s (Binary Tree) | token/s: 59.4 -> 61.6 | Helped |
| Replace token-level verification with Traversal Verification | Llama-68M / Llama2-7B · Spec-Bench Avg. Token/s (EAGLE Sparse Tree) | token/s: 69.1 -> 71.2 | Helped |
Surprising findings
- Gains shrink at lower temperatures and the advantage grows with tree size and depth.
- Actual throughput improvement is noticeably lower than the acceptance-length improvement because of verification overhead.
Limitations
- Throughput gains are smaller than acceptance-length gains due to extra verification overhead.
- Acceptance-length improvements are modest (about 1-7%) and vary with model pair and temperature.
- Generation quality evaluation is only a reference since losslessness is proven theoretically rather than empirically.
Experimental setup
Datasets: Spec-Bench MT-Bench WMT14 DE-EN CNN/Daily Mail Natural Questions GSM8K DPR
Benchmarks: Spec-Bench MT-Bench
Metrics: acceptance length tokens per second generation quality score
Baselines: token-level verification (vanilla speculative decoding with RRSw) Block Verification EAGLE sparse tree autoregressive decoding
Builds on: speculative sampling SpecInfer recursive rejection sampling RRSw Block Verification EAGLE
Closest papers by meaning
- UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding (NeurIPS 2026 · similarity 0.92)
- Block Verification Accelerates Speculative Decoding (ICLR 2025 · similarity 0.92)
- Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding (ICLR 2026 · similarity 0.90)
- RheoSampling: Resolving the One-Hot Dilemma in Stochastic Dynamic-Tree Speculative Decoding (NeurIPS 2026 · similarity 0.90)
- TreeGraft: Adaptive Multi-Drafter Grafting for Tree-Based Speculative Decoding (NeurIPS 2026 · similarity 0.90)
- VIA-SD: Verification via Intra-Model Routing for Speculative Decoding (ICML 2026 · similarity 0.90)
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.