Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding

• URL: http://arxiv.org/abs/2605.20104v1
• Date: Tue, 19 May 2026 16:55:48 GMT
• Title: Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding
• Abstract summary: Graft is a compensation framework that couples pruning and retrieval as mutually reinforcing operations.<n>On short-context benchmarks, it achieves up to 5.41$times$ speedup and improves average speedup by up to 21.8% on the large-scale Qwen3-235B.<n>We also provide a preliminary exploration of applying Graft to the DFlash-style block drafting paradigm, offering initial evidence and insights for extending grafting beyond autoregressive draft trees.
• Score: 27.332123289262086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Speculative decoding (SD) accelerates large language model inference by leveraging a draft-then-verify paradigm. To maximize the acceptance rate, recent methods construct expansive draft trees, which unfortunately incur severe VRAM bandwidth and computational overheads that bottleneck end-to-end speedups. While dynamic-depth pruning can reduce this latency by removing marginal branches, it also discards potentially valid candidates, preventing the acceptance rate from reaching the upper bound of dense trees. In this paper, we identify a critical opportunity in resource allocation: the transition from dense to pruned drafting frees up significant computational budget. To break this Pareto tradeoff, we introduce Graft, a compensation framework that couples pruning and retrieval as mutually reinforcing operations. Pruning supplies sufficient budget for retrieval, while retrieval compensates for pruning-induced coverage loss and recovers accepted length. By employing a sequential `prune-then-graft' mechanism, Graft attaches highly predictive retrieved tokens into positions opened by pruning, filling the topological gaps with near-zero overhead. Graft is entirely training-free and lossless. Comprehensive evaluations show that Graft establishes a new Pareto frontier across practical deployment settings, including short-context generation, long-context generation, and large-scale models. On short-context benchmarks, it achieves up to 5.41$\times$ speedup and improves average speedup over EAGLE-3 by up to 21.8% on the large-scale Qwen3-235B. We also provide a preliminary exploration of applying Graft to the DFlash-style block drafting paradigm, offering initial evidence and insights for extending grafting beyond autoregressive draft trees.

Related papers

• Trees from Marginals: Autoregressive drafting with factorized priors [0.0]
  Speculative decoding greatly increases the interactivity of autoregressive language models.<n>We introduce Weaver, a lightweight autoregressive adapter that constructs proposal trees from the top-K marginals of a factorized drafter.
  arXiv  Detail & Related papers  (2026-07-07T19:48:36Z)
• Where to Refine, When to Stop: Rethinking Redundancy via Latent Discrepancy for Efficient Visual Autoregressive Generation [50.139984798361375]
  We propose a training-free framework that removes redundancy via latent discrepancy.<n> LD-Pruning substantially reduces inference while maintaining high generation quality, achieving up to 2.35x speedup on Infinity-8B.
  arXiv  Detail & Related papers  (2026-05-29T19:34:39Z)
• Bastion: Budget-Aware Speculative Decoding with Tree-structured Block Diffusion Drafting [36.83545196908392]
  BASTION is a budget-aware speculative decoding framework with tree-based diffusion drafting.<n>Our framework integrates three synergistic components: (1) an acceptance surrogate that estimates expected accepted length via path confidence, (2) an online latency estimator that calibrates a hardware-aware roofline model, and (3) an adaptive best-first expansion that grows the tree until marginal gains no longer justify incremental verification costs.
  arXiv  Detail & Related papers  (2026-05-28T10:21:34Z)
• Making Every Verified Token Count: Adaptive Verification for MoE Speculative Decoding [15.040000425985324]
  Tree-based speculative decoding accelerates autoregressive generation by verifying multiple draft candidates in parallel, but this advantage weakens for sparse Mixture-of-Experts (MoE) models.<n>We propose EVICT, a training-free, hyper parameter-free, and lossless adaptive verification method for MoE speculative decoding.<n> EVICT makes every verified token count by truncating the draft tree before target verification and retaining only the cost-effective prefix.
  arXiv  Detail & Related papers  (2026-05-01T01:52:01Z)
• ECHO: Elastic Speculative Decoding with Sparse Gating for High-Concurrency Scenarios [12.103618967955846]
  Speculative Decoding promises to accelerate the inference of Large Language Models, yet its efficacy often degrades in production-grade serving.<n>We introduce ECHO, a high-oriented framework integrated into SGLang that reformulates speculative execution as a budgeted scheduling problem.<n>ECHO consistently outperforms SOTA methods in both low-load and high-load scenarios, achieving up to 5.35x walltime speedup and delivering over 20% relative speedup gain.
  arXiv  Detail & Related papers  (2026-03-10T03:51:24Z)
• Arbor: A Framework for Reliable Navigation of Critical Conversation Flows [0.19573380763700712]
  We present Arbor, a framework that decomposes decision tree navigation into specialized, node-level tasks.<n>Abort improves mean turn accuracy by 29.4 percentage points, reduces per-turn latency by 57.1%, and an average 14.4x reduction in per-turn cost.
  arXiv  Detail & Related papers  (2026-02-16T11:09:02Z)
• SAGE: Accelerating Vision-Language Models via Entropy-Guided Adaptive Speculative Decoding [15.734450444255787]
  Speculative decoding has emerged as a promising approach to accelerate inference in vision-language models.<n>Existing methods rely on static tree structures that remain fixed throughout the decoding process.<n>We propose SAGE, a novel framework that dynamically adjusts the speculation tree structure based on real-time prediction uncertainty.
  arXiv  Detail & Related papers  (2026-01-31T05:35:40Z)
• Double: Breaking the Acceleration Limit via Double Retrieval Speculative Parallelism [19.7914286780195]
  We introduce textscDouble (Double Retrieval Speculative Parallelism)<n>We enable the draft model to execute iterative retrieval speculations to break the theoretical speedup limits.<n>Experiments demonstrate state-of-the-art speedup of $textbf5.3times$ on LLaMA3.3-70B and $textbf2.8times$ on Qwen3-32B.
  arXiv  Detail & Related papers  (2026-01-09T04:35:21Z)
• Fast Inference of Visual Autoregressive Model with Adjacency-Adaptive Dynamical Draft Trees [50.230925890958936]
  We propose an adjacency-adaptive dynamic draft tree that adjusts draft tree depth and width by leveraging adjacent token states and prior acceptance rates.<n>ADT-Tree achieves speedups of 3.13xand 3.05x, respectively, and integrates seamlessly with relaxed sampling methods such as LANTERN.
  arXiv  Detail & Related papers  (2025-12-26T04:45:49Z)
• BranchGRPO: Stable and Efficient GRPO with Structured Branching in Diffusion Models [57.304411396229035]
  We present BranchGRPO, a method that restructures the rollout process into a branching tree.<n>On HPDv2.1 image alignment, BranchGRPO improves alignment scores by up to textbf16% over DanceGRPO.<n>A hybrid variant, BranchGRPO-Mix, further accelerates training to 4.7x faster than DanceGRPO without degrading alignment.
  arXiv  Detail & Related papers  (2025-09-07T12:53:06Z)
• 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)
• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• MLPruning: A Multilevel Structured Pruning Framework for Transformer-based Models [78.45898846056303]
  Pruning is an effective method to reduce the memory footprint and computational cost associated with large natural language processing models. We develop a novel MultiLevel structured Pruning framework, which uses three different levels of structured pruning: head pruning, row pruning, and block-wise sparse pruning.
  arXiv  Detail & Related papers  (2021-05-30T22:00:44Z)

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.