SMART: When is it Actually Worth Expanding a Speculative Tree?

• URL: http://arxiv.org/abs/2604.09731v1
• Date: Thu, 09 Apr 2026 13:17:56 GMT
• Title: SMART: When is it Actually Worth Expanding a Speculative Tree?
• Abstract summary: Tree-based speculative decoding accelerates autoregressive generation by verifying a branching tree draft tokens in a single targetmodel forward pass.<n>Existing methods prioritize maximizing token-level likelihood of the number of accepted tokens while ignoring a critical efficiency paradox''<n>We propose SMART, a system-aware marginal analysis framework for runtime tree construction.
• Score: 26.986851887229054
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tree-based speculative decoding accelerates autoregressive generation by verifying a branching tree of draft tokens in a single target-model forward pass. However, existing methods prioritize maximizing token-level likelihood or the number of accepted tokens while ignoring a critical ``efficiency paradox'': the computational overhead of drafting and verifying big trees can grow super-linearly, particularly at scale. This often leads to negative wall-clock speedup when batch sizes increase or hardware saturation limits are reached. To address this, we propose SMART, a system-aware marginal analysis framework for runtime tree construction. SMART reformulates tree expansion as a hardware-aware optimization problem that directly maximizes end-to-end speedup. By applying a principled marginal benefit--cost rule at inference time, SMART expands a node only when its marginal benefit--cost ratio exceeds the tree-level speedup. SMART is training-free and serves as a plug-and-play controller for existing frameworks like MSD and EAGLE. Extensive evaluations across three MLLMs (e.g., LLaVA, Qwen2-VL) and four LLMs (e.g., Llama-3.1, DeepSeek-R1) demonstrate that SMART consistently outperforms state-of-the-art baselines. It delivers an average additional speedup of 20.0\% for MLLMs and 15.4\% for LLMs across compute-bound batching regimes and diverse GPU architectures without performance loss.

Related papers

• ECHO: Early-layer Collaborative Hierarchical Orchestration with Bonus Logits in Speculative Decoding [60.34475274870224]
  ECHO is a hierarchical dual-loop framework that exploits the functional asymmetry between LLM layers.<n>Within the inner loop, early-layer bonus logits drive rapid, multi-step draft-tree exploration at a minimal cost.<n>ECHO significantly boosts mean accepted tokens and achieves a 2.4$times$ to 2.9$times$ speedup.
  arXiv  Detail & Related papers  (2026-09-15T14:21:33Z)
• Beyond FLOPs: Benchmarking Real Inference Acceleration of LLM Pruning under a GEMM-Centric Taxonomy [13.790557800221057]
  Pruning has emerged as a dominant paradigm for accelerating large language model (LLM) inference.<n>We introduce a GEMM-centric taxonomy that reorganizes existing pruning methods according to the logical textbfM, textbfN, and textbfK dimensions of general matrix multiplication.
  arXiv  Detail & Related papers  (2026-06-08T06:26:18Z)
• You Only Index Once: Cross-Layer Sparse Attention with Shared Routing [61.29627714699688]
  Cross-layer sparse attention (A) is built on top of KV-sharing architectures such as YOCO.<n>A single indexer computes token-level top-k selection once and reuses the resulting index across layers.<n>Results show CLSA is both accurate and efficient, achieving up to 7.6x decoding speedup and 17.1x overall throughput improvement at 128K context.
  arXiv  Detail & Related papers  (2026-06-04T17:54:04Z)
• $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators [7.020725160596732]
  STATIC is an efficient and scalable constrained decoding technique for generative retrieval on hardware accelerators.<n>We deploy STATIC on a large-scale industrial video recommendation platform serving billions of users.
  arXiv  Detail & Related papers  (2026-02-26T06:00:56Z)
• Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding [49.16776388429616]
  Yggdrasil is a system that enables latency-optimal speculative decoding through context-aware tree drafting and compiler-friendly execution.<n>Yggdrasil supports unmodified LLMs and achieves up to $3.98times$ speedup over state-of-the-art baselines across multiple hardware setups.
  arXiv  Detail & Related papers  (2025-12-29T20:51:38Z)
• Opportunistic Expert Activation: Batch-Aware Expert Routing for Faster Decode Without Retraining [34.97996720624093]
  We introduce a framework for dynamically re-routing token-to-expert mapping to lower MoE latency.<n>We evaluate our method on the Qwen3-30B and Qwen3-235B models with a batch size of $16$.
  arXiv  Detail & Related papers  (2025-11-04T04:00:20Z)
• Chain-in-Tree: Back to Sequential Reasoning in LLM Tree Search [4.12237459236889]
  Chain-in-Tree (CiT) is a framework that decides when to branch during search rather than expanding at every step.<n>It achieves 75-85% reductions in token generation, model calls, and runtime on GSM8K and Math500.
  arXiv  Detail & Related papers  (2025-09-30T06:18:44Z)
• Bridging Draft Policy Misalignment: Group Tree Optimization for Speculative Decoding [24.681973968208364]
  We introduce Group Tree Optimization (GTO), which aligns training with the decoding-time tree policy.<n>We prove that increasing Draft Tree Reward provably improves acceptance length and speedup.<n>GTO offers a practical, general solution for efficient large language model inference.
  arXiv  Detail & Related papers  (2025-09-26T09:55:35Z)
• Spiffy: Multiplying Diffusion LLM Acceleration via Lossless Speculative Decoding [40.96405124314983]
  Diffusion LLMs (dLLMs) have recently emerged as a powerful alternative to autoregressive LLMs (AR-LLMs)<n>Currently available open-source dLLMs often generate at much lower rates, typically decoding only a single token at every denoising timestep.<n>We present Spiffy, a speculative decoding algorithm that accelerates dLLM inference by $mathbf2.8-3.1times$ while provably preserving the model's output distribution.
  arXiv  Detail & Related papers  (2025-09-22T17:58:21Z)
• 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)
• Turning Trash into Treasure: Accelerating Inference of Large Language Models with Token Recycling [24.04649159686283]
  Speculative decoding is an approach to accelerate inference through a guess-and-verify paradigm.<n> Token Recycling stores candidate tokens in an adjacency matrix and employs a breadth-first-search algorithm.<n>It significantly outperforms existing train-free methods by 30% and even a widely recognized training method by 25%.
  arXiv  Detail & Related papers  (2024-08-16T12:20:56Z)
• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
  We propose an optimization-based structural pruning that learns the pruning masks in a probabilistic space directly by optimizing the loss of the pruned model.<n>We achieve this by learning an underlying Bernoulli distribution to sample binary pruning masks.<n>Experiments conducted on LLaMA, LLaMA-2, LLaMA-3, Vicuna, and Mistral models demonstrate the promising performance of our method in efficiency and effectiveness.
  arXiv  Detail & Related papers  (2024-06-15T09:31:03Z)
• HiRE: High Recall Approximate Top-$k$ Estimation for Efficient LLM Inference [68.59839755875252]
  HiRE comprises of two novel components: (i) a compression scheme to cheaply predict top-$k$ rows/columns with high recall, followed by full computation restricted to the predicted subset, and (ii) DA-TOP-$k$: an efficient multi-device approximate top-$k$ operator. We demonstrate that on a one billion parameter model, HiRE applied to both the softmax as well as feedforward layers, achieves almost matching pretraining and downstream accuracy, and speeds up inference latency by $1.47times$ on a single TPUv5e device.
  arXiv  Detail & Related papers  (2024-02-14T18:04:36Z)

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.