TreeSpark: Adaptive Draft Trees Accelerate Speculative Decoding by 8–14%

Speculative Decoding's Next Step: Smarter Draft Trees

One of the core bottlenecks in large model inference is the inherently serial nature of autoregressive decoding. Speculative decoding offers an acceleration path: a cheap "drafter" model proposes several candidate tokens first, then the target model verifies them all in a single parallel pass. This "draft-then-verify" mechanism significantly reduces the number of forward passes required from the target model, while preserving lossless output.

Recent block drafters have pushed draft generation costs nearly to zero — a single backbone forward pass produces an entire block of draft tokens. Draft trees take this a step further: they verify multiple candidate continuation paths simultaneously within a single target model forward pass, squeezing out even more acceleration.

A new paper on arXiv, TreeSpark, is an optimization targeting exactly this direction. The authors propose a "calibrated, load-adaptive" draft tree construction method designed specifically for semi-autoregressive drafters.

The lossless guarantee of speculative decoding stems from a key mathematical property: if draft tokens are accepted or rejected by the target model with specific probabilities, the distribution of the final output sequence is exactly equivalent to what the target model would produce on its own through autoregressive generation. This mechanism was formally established by Leviathan et al. (2023). Block drafters are a variant of speculative decoding that, rather than generating drafts token-by-token autoregressively, produce tokens at multiple positions in parallel via a single forward pass — at the cost of slightly lower draft quality compared to autoregressive drafters. Semi-autoregressive drafters sit between the two: they generate drafts in fixed blocks, parallel within each block and serial between blocks, striking a balance between draft quality and generation speed. The introduction of draft trees extends a single candidate chain into multiple parallel candidate paths, allowing the target model to verify all nodes on the tree in a single forward pass — theoretically enabling a large increase in average accepted length without additional target model calls.

Two Fundamental Flaws in Existing Draft Trees

The paper explicitly identifies two core problems with current draft tree construction approaches.

Misaligned Ranking Signals

Existing construction methods rank candidate nodes based on per-position marginal probabilities — that is, they ignore which parent node a given candidate extends from. This is especially damaging for semi-autoregressive drafters: as the tree grows wider, most newly added nodes are poorly ranked "noise," and the gains from a wider tree are offset by the large number of misranked nodes.

The distinction between marginal probability and conditional probability is critical in tree structures. Marginal probability describes the overall likelihood of a token appearing at a given position, averaging over all possible prefix paths. Conditional probability, by contrast, precisely captures "the likelihood of this token appearing after a specific parent node." In chain-based drafts, the difference is minor since there is only one path. But in a tree, the same token at the same position may be attached to different parent nodes, and its actual probability of acceptance by the target model can vary dramatically. Ranking by marginal probability is equivalent to ignoring path context — it pushes nodes that "look frequent in isolation but are nearly impossible to accept along the current path" into high-priority positions, wasting the verification budget.

Rigidity of Fixed Tree Sizes

The other issue is that tree size is fixed. In practice, however, the amount of "speculation" that can be supported varies dynamically each decoding round, and the affordable speculation budget also differs under different serving loads. Using a fixed-size tree across all scenarios is clearly suboptimal.

TreeSpark's Core Approach

TreeSpark's key insight is to use path survival rate as the unifying signal across the board.

It reads a parent-conditioned distribution from the drafter's existing Markov head — a step that introduces almost no additional cost, since it leverages structure already present in the drafter. This distribution is then calibrated into an edge-acceptance estimate, used to assess how likely each edge is to be accepted by the target model.

With this calibrated survival estimate, TreeSpark lets path survival rate govern three things:

• Best-first expansion: prioritizing expansion of paths more likely to survive
• Per-round stopping: dynamically deciding when to stop expanding each round
• Load-adaptive serving policy: adjusting tree size based on current load

Guaranteeing Lossless Decoding

TreeSpark's handling of decoding losslessness is noteworthy. It uses sampling siblings without replacement and matching residuals in recursive rejection sampling, ensuring that decoding results remain consistent with the target model's distribution at any temperature. This matters — many acceleration methods alter the output distribution under high-temperature sampling, and TreeSpark claims to avoid this problem.

Sampling without replacement in tree verification addresses a subtle probabilistic consistency issue. When the target model rejects a token, standard speculative decoding resamples a replacement token from the residual distribution (the difference between the target and draft distributions). In a tree structure, a single parent node may have multiple sibling candidates. If these siblings are sampled with replacement, overlaps between branches cause biases in the overall acceptance probability calculation, ultimately breaking distributional losslessness. Sampling without replacement ensures siblings are mutually exclusive, keeping the residual distribution matching mathematically rigorous. This detail is especially critical at higher temperatures, where the inherently larger distribution variance means any probabilistic bias is amplified and more likely to cause the output distribution to deviate from the target model.

Empirical Gains

Based on numbers reported in the paper, TreeSpark's performance can be summarized across several dimensions:

• Under matched fixed budgets, adaptive trees outperform fixed trees at every temperature;
• Relative to a well-tuned "chain" baseline on the same drafter, TreeSpark accepts 15–25% more draft tokens per round;
• In wall-clock time for single requests, decoding speed improves by 8–14%;
• Under increasing load, it gracefully shrinks the tree back to a chain, avoiding resource waste at high load.

The last point particularly reflects engineering practicality. Acceleration methods in real serving environments must contend with fluctuating loads. The ability to smoothly transition between "pursuing maximum acceleration" and "falling back to a conservative strategy" is more valuable in production than a method that only benchmarks well under ideal conditions.

Significance and Limitations

TreeSpark's contribution is not the invention of an entirely new paradigm, but rather bringing a neglected signal — path survival rate conditioned on parent nodes — back to the center of tree construction, and using it to unify three decisions: expansion, stopping, and load scheduling. This design philosophy of "simplifying multiple heuristics with a single unified signal" tends to be more robust in systems optimization than stacking complex rules.

It is worth noting that the reported acceleration numbers (8–14%) were measured under specific drafters and baselines. Actual gains will vary with model scale, task type, and hardware configuration. Semi-autoregressive drafters themselves are also not yet a mainstream deployment choice, and their applicability awaits broader validation.

For engineers and researchers focused on LLM inference acceleration, TreeSpark has open-sourced its code and experimental artifacts, available on GitHub at PopSoda2002/TreeSpark for further exploration of implementation details.