Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding

• URL: http://arxiv.org/abs/2602.16994v1
• Date: Thu, 19 Feb 2026 01:41:58 GMT
• Title: Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding
• Authors: Rahul Thomas, Teo Kitanovski, Micah Goldblum, Arka Pal,
• Abstract summary: We present a systematic evaluation of verification strategies across model families, tasks, and sampling regimes.<n>Traversal Verification dominates consistently, with OT-based methods lagging far behind.<n>We propose delayed tree expansion, which drafts a partial single path, delaying the i.i.d. branching point.
• Score: 35.984745508100595
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-path speculative decoding accelerates lossless sampling from a target model by using a cheaper draft model to generate a draft tree of tokens, and then applies a verification algorithm that accepts a subset of these. While prior work has proposed various verification algorithms for i.i.d rollouts, their relative performance under matched settings remains unclear. In this work, we firstly present a systematic evaluation of verification strategies across model families, tasks, and sampling regimes, and find that Traversal Verification dominates consistently, with OT-based methods lagging far behind. Our analysis uncovers that this occurs because OT-based methods achieve high multi-token acceptance near the root of the draft tree, while multi-token gains are most impactful deeper in the draft tree, where draft and target distributions diverge. Based on this insight, we propose delayed tree expansion, which drafts a partial single path, delaying the i.i.d. branching point. We show that delayed tree expansion preserves the target distribution and improves on root-node i.i.d rollouts. Further, we develop a dynamic neural selector that estimates the expected block efficiency of optimal-transport-based verification methods from draft and target features, enabling context-dependent expansion decisions. Our neural selector allows OT-based methods like SpecInfer to outperform Traversal Verification for the first time, achieving 5% higher average throughput across a wide range of models, datasets, and sampling settings.

Related papers

• PROMISE: Process Reward Models Unlock Test-Time Scaling Laws in Generative Recommendations [52.67948063133533]
  Generative Recommendation has emerged as a promising paradigm, reformulating recommendation as a sequence-to-sequence generation task over hierarchical Semantic IDs.<n>Existing methods suffer from a critical issue we term Semantic Drift, where errors in early, high-level tokens irreversibly divert the generation trajectory into irrelevant semantic subspaces.<n>We propose Promise, a novel framework that integrates dense, step-by-step verification into generative models.
  arXiv  Detail & Related papers  (2026-01-08T07:38:46Z)
• Fast Inference via Hierarchical Speculative Decoding [65.40448210801763]
  We introduce Hierarchical Speculative Decoding (HSD), an algorithm that stacks draft models into a hierarchy, where each model proposes tokens, and the next larger model verifies them in a single forward pass.<n>HSD gives up to 1.2x speed-up over the best single-draft baseline.
  arXiv  Detail & Related papers  (2025-10-22T15:56:19Z)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)
• TreeRPO: Tree Relative Policy Optimization [65.51935468270916]
  name is a novel method that estimates the mathematical expectations of rewards at various reasoning steps using tree sampling.<n>Building on the group-relative reward training mechanism of GRPO, name innovatively computes rewards based on step-level groups generated during tree sampling.
  arXiv  Detail & Related papers  (2025-06-05T15:56:38Z)
• Traversal Verification for Speculative Tree Decoding [15.720388162422978]
  Speculative decoding is a promising approach for accelerating large language models.<n>This paper introduces Traversal Verification, a novel speculative decoding algorithm.<n>We show that our method consistently improves acceptance length and throughput over existing methods.
  arXiv  Detail & Related papers  (2025-05-18T12:51:55Z)
• RASD: Retrieval-Augmented Speculative Decoding [5.3926068062773895]
  Speculative decoding accelerates inference in large language models (LLMs)<n>This paper proposes RASD (Retrieval-Augmented Speculative Decoding), which adopts retrieval methods to enhance model-based speculative decoding.
  arXiv  Detail & Related papers  (2025-03-05T12:10:14Z)
• Jakiro: Boosting Speculative Decoding with Decoupled Multi-Head via MoE [15.003006630308517]
  Speculative decoding (SD) accelerates large language model inference by using a smaller draft model to predict multiple tokens.<n>We propose Jakiro, leveraging Mixture of Experts (MoE), where independent experts generate diverse predictions.<n>Our method significantly boosts prediction accuracy and achieves higher inference speedups.
  arXiv  Detail & Related papers  (2025-02-10T09:24:06Z)
• Graph-Structured Speculative Decoding [52.94367724136063]
  Speculative decoding has emerged as a promising technique to accelerate the inference of Large Language Models. We introduce an innovative approach utilizing a directed acyclic graph (DAG) to manage the drafted hypotheses. We observe a remarkable speedup of 1.73$times$ to 1.96$times$, significantly surpassing standard speculative decoding.
  arXiv  Detail & Related papers  (2024-07-23T06:21:24Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.