Skip to content

TreeSpark: Calibrated, Load-Adaptive Draft Trees for Semi-Autoregressive Speculative Decoding

Aug 2026 · 2 citations · ⚡ 1 influential · 32 references
Computer Science

TL;DR

TreeSpark is introduced, which reads a parent-conditioned distribution from the drafter's existing Markov head at negligible cost, calibrates it into an edge-acceptance estimate, and lets path survival govern everything else: best-first expansion, per-round stopping, and a load-adaptive serving policy.

Abstract

Speculative decoding accelerates language-model inference by letting a cheap drafter propose tokens that the target model verifies in parallel. Recent block drafters make drafting nearly free: a single backbone pass emits an entire block of draft tokens. Draft trees promise a further gain -- several alternative continuations verified in one target forward -- but existing constructions rank candidates by per-position marginals that ignore which parent a candidate extends, so on semi-autoregressive drafters wider trees mostly add mis-ranked nodes; and a tree of fixed size ignores how much speculation each decoding round, and each serving load, can support. We introduce TreeSpark, which reads a parent-conditioned distribution from the drafter's existing Markov head at negligible cost, calibrates it into an edge-acceptance estimate, and lets path survival govern everything else: best-first expansion, per-round stopping, and a load-adaptive serving policy. Sampling siblings without replacement, with matching residuals in recursive rejection, keeps decoding lossless at any temperature. Adaptive trees improve on matched fixed budgets at every temperature; against a tuned chain on the same drafter, TreeSpark accepts 15-25% more draft tokens per round and decodes 8-14% faster in single-request wall-clock, and under rising load it gracefully shrinks the tree back to the chain. Code and artifacts: https://github.com/PopSoda2002/TreeSpark

View source

Similar papers

Preprint Aug 2026

DARTree: Speculative Diffusion Decoding with Autoregressive Draft Trees

DARTree is introduced, a training-free speculative decoding method that extends a pretrained AR correction head from chains to trees, and achieves the highest average acceptance length and speedup in all four model--temperature configurations.

Tian-Yi Li, Yaxin Luo, Xin-Yi Shang et al. · 5 citations · ⚡1
#artificial intelligence Preprint Oct 2026

Training Parallel Speculative Draft Models by Directly Minimizing Expected Decoding Rounds

A theoretical framework for training and evaluating parallel and semi-autoregressive drafters by representing speculative decoding as a Markov reward process, which yields the Expected Decoding Rounds (EDR) objective, which weights local rejection costs by state occupancies and exactly equals the expected number of dec...

Yun-Xiao Zhao, Chang-Xiao Cai · 3 citations
#artificial intelligence Preprint Sep 2026

LongSpark: Efficient speculative decoding with a fixed-cost parallel drafter

This work introduces LongSpark, a block-diffusion drafter that achieves state-of-the-art end-to-end efficiency across multiple model scales and realistic serving conditions by extracting fixed-size, multiscale views from the target's verification pass, thereby eliminating the need for a growing persistent state.

Hao-Yuan He, Peng-Fei Liu, Si-Shi Shen et al. · 0 citations
Preprint Aug 2026

ResiSpec: Enhancing Multi-Candidate Speculative Sampling via Residual Distribution Shaping

ResiSpec, a framework that strategically reforms the proposal distribution during verification to anchor the residual target mass within the draft model's high-confidence regions, prevents candidate obsolescence and achieves up to 1.92$\times$ speedup over state-of-the-art multi-candidate methods.

Zhi-Kai Chen, Jun Tao, Wei-Hao Mao et al. · 1 citation
#natural language process... Preprint Aug 2026

ReTrace: Rejected-Trajectory Conditioning for Speculative Decoding

ReTrace is introduced, a rejected-trajectory conditioning method that conditions each draft block on the rejected suffix from the previous round rather than generating it from fresh mask placeholders alone, indicating that the draft model can retain useful semantic and structural information despite local token-level e...

Luxi Lin, Zhan-Peng Zeng, Shuang Peng et al. · 2 citations
#natural language process... Preprint Oct 2026

D-Loop: Looped Diffusion Drafting for Speculative Decoding

D-Loop is proposed, which introduces \emph{intra-block causal conditioning} within the original diffusion drafter without additional model components, and can beat DFlash and DSpark on Qwen3-4B and Qwen3-8B with obvious gains.

Ke-Cheng Chen, Yu-Yang He, Cheng Gong et al. · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.