Skip to content

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

Conference: ECCV 2026
arXiv: 2604.09731
Code: To be confirmed
Area: LLM Efficiency
Keywords: Speculative Decoding, Speculative Tree, Hardware-Aware, Marginal Analysis, End-to-End Acceleration

TL;DR

SMART proposes a hardware-aware marginal analysis framework that reformulates speculative tree construction in speculative decoding as a sequential decision-making problem aimed at maximizing the end-to-end speedup ratio. A node is expanded only when its marginal benefit-to-cost ratio exceeds the overall speedup ratio of the current tree. This avoids the "negative acceleration" paradox caused by the superlinear growth of verification overheads under large batch sizes, yielding an average of 20.0% (for MLLMs) and 15.4% (for LLMs) extra speedup without requiring retraining.

Background & Motivation

Tree-based speculative decoding is one of the mainstream techniques to accelerate autoregressive generation. Its core idea is to let a lightweight draft model generate a tree of candidate tokens with multiple branches, which is then verified in parallel by the target model in a single forward pass. Compared to single-chain speculative decoding, the tree structure covers more potential candidate paths, thereby significantly increasing the expected acceptance length per target model forward step. Existing tree construction methods—including EAGLE-2 and MSD—typically drive tree expansion based on token-level cumulative probabilities, prioritizing candidates with the highest likelihood to "capture" more acceptable tokens with larger trees. While GTO shifts the training objective from maximizing likelihood to maximizing acceptance length, it still focuses on "accepting more tokens."

However, the ultimate goal of speculative decoding is not to accept as many tokens as possible, but to maximize the wall-clock speedup. An easily overlooked efficiency paradox exists here: as the tree grows larger, the verification overhead scales rapidly. During deployment with large batch sizes, the GPU shifts from a memory-bound state under small batch sizes to a compute-bound state—where every additional verified token incurs superlinearly growing verification latency. This implies that greedily expanding the speculative tree can be counterproductive: the extra overhead of verifying a large tree outweighs the gained acceptance length, leading to a speedup of less than 1×, making it even slower than vanilla autoregressive decoding. Experimental results of MSD clearly illustrate this: on an RTX Pro 6000, as the batch size increases from 1 to 32, the speedup of MSD plummets from 2.20× to 0.82×; on L40S, it drops to 0.90× at batch size 12. More troublingly, this "inflection point" is highly hardware-dependent—the same tree might perform well on an RTX Pro 6000 but experience negative acceleration on an L40S, and different GPU architectures and batch sizes alter the optimal tree shape. Core Idea: SMART abandons the objective of maximizing likelihood or acceptance frequency, and instead models speculative tree construction as a sequential decision-making problem to maximize the end-to-end speedup ratio. At each expansion step, a localized marginal benefit-to-cost ratio of a node is evaluated using a hardware cost-profiling model measured on the target device. The node is expanded only if this ratio exceeds the average speedup ratio of the current tree, enabling online, adaptive, and hardware-aware construction of optimal speculative trees during inference without any training.

Method

Overall Architecture

SMART is a plug-and-play inference-time controller that does not modify any parameters of the draft model, target model, or verification mechanism. It replaces the likelihood-maximization-based tree construction strategies in existing systems (such as MSD, EAGLE-3) with a speedup-maximization strategy. The overall pipeline consists of three phases: first, light-weight device profiling is conducted on the target hardware to fit the function mapping inference cost to tree size; then, during actual inference, a greedy expansion decision is executed layer-by-layer during tree generation—calculating whether the marginal acceleration benefit of each candidate node exceeds the global speedup ratio of the current tree; finally, a hardware-aware pruned speculative tree is produced and passed to the existing parallel verification mechanism.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Offline: Device Cost Profiling<br/>5 forward passes → fit cost function"] --> B["Online: Layer-by-layer speculative tree construction"]
    B --> C["For each layer, generate top-k<br/>candidate tokens for parent nodes"]
    C --> D["Traverse candidates u<br/>Compute marginal benefit ΔC_target(u)<br/>Compute marginal cost ΔC_spec(u)"]
    D --> E{"ΔJ(u) > 0 ?<br/>α·ΔC_target/ΔC_spec<br/>− C_target/C_spec > 0"}
    E -->|Yes| F["Keep u<br/>→ Add to active set A_ℓ"]
    E -->|No| G["Prune u"]
    F --> H["Active set A_ℓ<br/>acts as next-layer parents"]
    G --> H
    H --> I{"A_ℓ is empty<br/>or reaches budget B ?"}
    I -->|No| C
    I -->|Yes| J["Output final speculative tree<br/>→ Parallel verification"]

Key Designs

1. System-Level Speedup Objective: Direct Optimization of Wall-Clock Speedup

Existing tree construction methods (including GTO) optimize for the expected acceptance length \(L^{\text{tree}}\). However, the speedup ratio depends not only on how many tokens are accepted, but also on the cost incurred to obtain them. SMART explicitly defines a system-level speedup metric \(\mathcal{R}(\mathcal{T})\)—which is actually the cost ratio of autoregressive decoding to speculative decoding: \(\mathcal{R}(\mathcal{T}) = \frac{c_T \cdot L^{\text{tree}}}{C_{\text{draft}} + C_{\text{verify}}}\), where \(c_T\) is the wall-clock time cost of the target model executing single-token autoregressive decoding, and \(C_{\text{draft}}\) and \(C_{\text{verify}}\) are the overheads of constructing and verifying the entire speculative tree, respectively. The numerator \(c_T \cdot L^{\text{tree}}\) represents the total time required to generate \(L^{\text{tree}}\) tokens in an autoregressive manner, while the denominator represents the time taken to obtain the same number of tokens speculatively. This ratio directly shows "how many times faster speculative decoding is compared to autoregressive decoding." Crucially, maximizing \(L^{\text{tree}}\) differs fundamentally from maximizing \(\mathcal{R}\): the former greedily expands the tree to increase the acceptance length, whereas the latter naturally accounts for the rising overhead of tree expansion. When the marginal acceptance increment \(\Delta L^{\text{tree}}\) of a candidate node is small but incurs massive overhead \(C_{\text{draft}}+C_{\text{verify}}\), retaining it degrades rather than improves the speedup ratio. This design pivots tree construction from likelihood-driven "acceptance length maximization" to cost-aware "speedup-ratio maximization."

2. Low-Cost Device Overhead Modeling: Fitting Cost Models with Minimal Forward Passes

To make marginal decisions practical, one must quantify "how much overhead is added by expanding a node." SMART performs a lightweight offline profiling on each target device, collecting drafting and verification latencies as functions of the tree size \(|\mathcal{T}|\) (i.e., the total number of tokens in the tree), and fits two analytical cost models. The drafting overhead is approximately linear with the total token count because the draft model is generally small and memory-bound, meaning the per-token cost remains constant—SMART fits this with \(C_{\text{draft}}(\mathcal{T}) = \lambda |\mathcal{T}| + \beta\). The verification phase is far more complex: the target model is large, and its verification latency exhibits a noticeable superlinear convex growth under compute-bound conditions at large batch sizes. SMART adopts a power-exponential model \(C_{\text{verify}}(\mathcal{T}) = \gamma(\exp(\delta |\mathcal{T}|^\rho) - 1) + \eta\) to capture this trend, where the coefficients \(\gamma, \delta, \rho\) are fitted using least squares on 5 forward pass data points. The bias terms \(\beta, \eta\) are fixed to 0 to ensure the output passes through the origin. Profiling on a LLaMA-3.1-8B takes only about 10 seconds (1.67% of the evaluation dataset's inference time), which is virtually negligible, yet provides a robust quantitative basis for each marginal decision.

3. Marginal Benefit-Cost Ratio Greedy Expansion Rule: Expand Only When Benefit Exceeds Cost

SMART formalizes speculative tree construction as a layer-by-layer sequential decision-making problem. Let \(S_{\ell-1}\) be the set of all selected nodes in the first \(\ell-1\) layers, and \(A_{\ell-1}\) be the set of expandable parent nodes retained in layer \(\ell-1\). At layer \(\ell\), for each parent node in \(A_{\ell-1}\), top-\(k\) candidates are generated to form the candidate set \(\mathcal{U}_\ell\). For each candidate \(u\), two quantities are computed: the marginal benefit \(\Delta C_{\text{target}}(u) = c_T \cdot \Delta L^{\text{tree}}(u)\), where \(\Delta L^{\text{tree}}(u) \approx \frac{1}{|\mathcal{P}|} P(\tilde{\mathbf{x}}_u \mid \text{anc}(u))\) (cumulative probability divided by the number of paths, representing the dilution contribution of adding a new leaf node to the average acceptance length); and the marginal cost \(\Delta C_{\text{spec}}(u) \approx \lambda + \gamma\delta\rho |\mathcal{T}|^{\rho-1} \exp(\delta |\mathcal{T}|^\rho)\) (the derivative sum of the cost models at \(|\mathcal{T}|\)). The criterion to decide whether to retain \(u\) is simple and elegant: keep it only if adding it increases the overall speedup. Since \(\mathcal{R}(\mathcal{T}) = C_{\text{target}} / C_{\text{spec}}\) is a fraction, the authors expand the log speedup ratio \(\mathcal{J} = \log \mathcal{R} = \log C_{\text{target}} - \log C_{\text{spec}}\) using a first-order Taylor expansion to derive the decision criterion \(\alpha \cdot \frac{\Delta C_{\text{target}}(u)}{\Delta C_{\text{spec}}(u)} - \frac{C_{\text{target}}}{C_{\text{spec}}} > 0\), where \(C_{\text{target}} / C_{\text{spec}}\) represents the global speedup ratio of the current tree. The physical meaning of this criterion is clear: the marginal benefit-cost ratio of a candidate node must exceed the average benefit-cost ratio of the current tree; otherwise, expanding it will drag down the overall speedup ratio. Here, \(\alpha \in (0,1]\) is a discount factor used to counteract the draft model's over-optimism regarding acceptance probabilities (as the target model may reject a highly confident prediction from the draft model). The empirically optimal value is \(\alpha=0.8\). The computational complexity of building the entire tree is \(\mathcal{O}(kB)\) (where \(k\) is the number of candidates per node and \(B\) is the budget), reducing the complexity from exhaustive search \(\mathcal{O}(2^{k^d})\) to linear—making each decision an \(\mathcal{O}(1)\) local evaluation.

Loss & Training

SMART is a training-free method—it does not modify any model weights, nor does it require additional training for the draft model or validator. The only "training" is profiling on each new device (which takes about 5 forward passes) to fit the cost model parameters, after which all decisions are performed on-the-fly during inference.

Key Experimental Results

Main Results

MLLM Speedup Ratio (Temperature T=0)

Model Method VQAv2 ChartQA TextVQA Hallusion Average SR Gain
LLaVA-1.5 7B MSD 1.23× 1.14× 1.26× 1.26× 1.18× -
LLaVA-1.5 7B MSD+SMART 1.55× 1.59× 1.55× 1.62× 1.53× +29.7%
LLaVA-1.5 13B MSD 1.30× 1.45× 1.22× 1.17× 1.26× -
LLaVA-1.5 13B MSD+SMART 1.56× 1.72× 1.51× 1.42× 1.53× +21.4%
Qwen2VL 7B MSD 1.18× 1.24× 1.16× 1.15× 1.14× -
Qwen2VL 7B MSD+SMART 1.22× 1.34× 1.24× 1.22× 1.25× +9.6%

LLM Speedup Ratio (Temperature T=0)

Model Method MT-Bench HumanEval GSM8K Avg. SR Gain
LLaMA-3.1 8B EAGLE-3 1.35× 1.44× 1.28× 1.36× -
LLaMA-3.1 8B EAGLE-3+SMART 1.56× 1.71× 1.51× 1.59× +16.9%
LLaMA-3.3 70B EAGLE-3 2.46× 2.92× 2.67× 2.69× -
LLaMA-3.3 70B EAGLE-3+SMART 2.97× 3.72× 3.32× 3.35× +24.5%
DeepSeek-R1 8B EAGLE-3 1.24× 1.49× 1.61× 1.46× -
DeepSeek-R1 8B EAGLE-3+SMART 1.45× 1.65× 1.87× 1.68× +15.1%

Ablation Study

Comparison of Speedup Degradation in Large Batch Scenarios (MSD vs. MSD+SMART on L40S)

Configuration Batch=1 Batch=4 Batch=8 Batch=12
MSD 1.82× 1.63× 1.22× 0.90×
MSD+SMART 1.77× 1.65× 1.50× 1.40×

Ablation on Speculative Token Budget (RTX Pro 6000, batch=16)

Configuration Avg. SR (T=0) Description
Budget=100 tokens 1.43× Over-pruned, under-utilizing parallelism
Budget=200 tokens 1.58× Optimal balance point
Budget=300 tokens 1.28× Excessive verification overhead
Budget=400 tokens 1.27× Excessive verification overhead

Ablation on Discount Factor α (RTX Pro 6000, batch=16)

α Avg. SR (T=0) Description
1.0 1.51× Too aggressive, retains too many inefficient nodes
0.9 1.55× Better
0.8 1.56× Optimal
0.7 1.55× Slightly conservative
0.5 1.54× Over-pruned

Key Findings

  • The bottleneck under large batch sizes is a core finding: Under small batch sizes (batch=1), MSD and SMART perform similarly (2.20× vs 2.17×), but as batch size increases, the speedup of MSD plummets to 0.82× (negative acceleration), whereas SMART consistently maintains a speedup above 1.39×. This demonstrates that the bottleneck lies not in "optimized redundancy" in small batches, but in the superlinear scaling of marginal verification cost for each extra token when the computation becomes saturated under large scaling.
  • Hardware heterogeneity significantly impacts the optimal strategy: The same MSD tree achieves a 1.84× speedup on RTX Pro 6000 at batch=8, but only 1.22× on L40S at the same batch size, indicating that the compute saturation point occurs earlier on L40S. SMART automatically adapts to these hardware differences via runtime marginal decisions without manual parameter tuning.
  • Discount factor \(\alpha=0.8\) offers the best trade-off: An excessively large \(\alpha\) retains candidates that the draft model was over-confident in (which are later rejected by the target model), while a too small \(\alpha\) mistakenly prunes high-yield nodes. Within the 0.6–1.0 range, SMART's performance remains stable, illustrating that the marginal criteria are robust.
  • SMART is also effective for non-autoregressive draft models (DFLASH): DFLASH generates all draft tokens based on block diffusion, producing a tree structure entirely distinct from the EAGLE family. Nevertheless, SMART still delivers +15.3% (\(T=0\)) and +16.2% (\(T=1\)) extra speedups, showing its generalizability across different drafting paradigms.

Highlights & Insights

  • Formulating speedup as a cost ratio for optimization elegantly unifies objectives and constraints: The formulation \(\mathcal{R}(\mathcal{T}) = \frac{c_T \cdot L^{\text{tree}}}{C_{\text{draft}} + C_{\text{verify}}}\) places "acceleration" and "cost" in the same physical dimension (time), naturally preventing the mismatch between likelihood maximization and system-level speedup.
  • The marginal benefit-cost ratio criterion is highly straightforward and efficient: The criterion \(\alpha \cdot \frac{\Delta C_{\text{target}}}{\Delta C_{\text{spec}}} > \frac{C_{\text{target}}}{C_{\text{spec}}}\) requires only \(O(1)\) local operations to make mathematically optimal greedy decisions, offering an intuitive physical interpretation: "The efficiency of a new node must not be lower than the average efficiency of the existing nodes."
  • The power-exponential form of the cost model is not arbitrary: The authors observed that verification latency grows exponentially under large batch compute saturation (rather than quadratic or power law), which matches theoretical hardware bottlenecks. Fitting a power-exponential form \(\gamma(\exp(\delta |\mathcal{T}|^\rho)-1)\) with just 5 data points successfully captures this non-linearity, balancing accuracy with minimal profiling costs.
  • The divergence between acceptance rate (\(\beta\)) and speedup ratio (SR) under SMART is an important insight: Traditional wisdom assumes high \(\beta\) leads to high SR, but under SMART, SR improves while \(\beta\) remains largely steady (e.g., on LLaMA-3.3-70B at \(T=0\), where \(\beta\) only increases from 0.67 to 0.70). This indicates that speedup mainly stems from "pruning inefficient tokens" rather than "accepting more tokens," which provides guidance for evaluating future speculative decoding schemes.

Limitations & Future Work

  • Limitations acknowledged by the authors: SMART was thoroughly evaluated only on RTX Pro 6000 and L40S, omitting larger-scale data center GPUs like key A100, H100, and H200 (though the appendix supplies preliminary results on A100 and H200 that mirror the trend). Furthermore, the budget \(B\) still requires manual setting, and its optimal value fluctuates across hardware and batch sizes.
  • Independently identified limitations: The cost model relies on offline profiling. If batch configurations vary drastically during runtime or if workload patterns shift dynamically, re-profiling or introducing online incremental updates may be necessary. Additionally, the marginal rules consider only single-step greedy optimization; in extreme cases, it might miss optimal multi-step joint expansions (though experiments demonstrate that greedy is sufficient in practice).
  • Specific improvement ideas: The budget \(B\) could be integrated into the adaptive framework, using similar marginal analysis to adjust verification budgets for each sequence dynamically. Furthermore, since SMART currently only controls tree topology, future work could combine it with dynamic draft model selection (switching between multiple differently-sized draft models) to make marginal decisions during the drafting phase itself.
  • vs. Likelihood-Maximization-Based Tree Construction (EAGLE-2 / MSD): These methods select candidates using cumulative probability \(P(u)\) and rely on fixed \(w \times d\) tree structures, neglecting hardware costs entirely. In contrast, SMART starts with speedup calculations, expanding a node strictly when it is cost-effective. The key difference is that SMART strives for the "most appropriate tree" rather than the "largest tree."
  • vs. GTO (Training-End Optimization): GTO optimizes the draft model using PPO during the training phase to maximize acceptance length, but still relies on likelihood heuristics during inference. SMART optimizes at inference time in a hardware-aware manner, making it orthogonal to GTO; indeed, experiments verify that combining GTO with SMART yields compounding gains (e.g., on LLaMA-3.1-8B, where GTO goes from 1.40× to 1.60×).
  • vs. TapOut / SVIP (Heuristic Stopping): These methods use entropy or confidence thresholds to halt drafting, which require manual tuning and transfer poorly. SMART's marginal decisions are built on quantitative cost models, eliminating manual threshold tuning and spontaneously adapting to hardware and batch variations.

Rating

  • Novelty: ⭐⭐⭐⭐☆ Introducing marginal benefit-cost analysis to speculative tree construction is academically intuitive, and linking acceptance length, drafting cost, and verification cost under a unified speedup formulation is both robust and novel.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Conducted comprehensive comparisons across 3 MLLMs + 4 LLMs over multiple hardware models (RTX Pro 6000/L40S/A100/H200), multiple baselines (MSD/EAGLE-2/3/GRIFFIN/GTO/DFLASH), and two temperature setups, completed by elaborate budget, alpha, and hardware generalization ablations.
  • Writing Quality: ⭐⭐⭐⭐⭐ The motivation is exceptionally clear with solid data support. Methodology derivation unfolds progressively from speedup definitions to marginal criteria and the greedy algorithm. Experimental interpretations provide deep rationales rather than raw metric comparisons.
  • Value: ⭐⭐⭐⭐⭐ Speculative decoding is pivotal for accelerating LLM inference. SMART's plug-and-play formulation means production pipelines can directly enjoy 15-20% extra throughput without altering model weights or framework structures, translating directly to substantial practical value.