arXiv Machine Learning

Rank-Aware Speculative Sampling for Diffusion Draft Trees

The paper introduces Rank-Aware Speculative Sampling (RASS), a new verification rule for speculative draft trees in diffusion models. RASS orders draft candidates by proposal‑target mean displacement, samples a rank with weights optimized to minimize total variation, and then maximally couples the selected candidate with the target distribution, ensuring exact sampling. Experiments on Gaussian mixtures, FFHQ, CIFAR‑10, and Stable Diffusion 3.5 show that RASS reduces target‑model evaluation counts by up to 20% compared to Diffusion Greedy Rejection Sampling (D‑GRS).

arXiv AI
Sep 17

Accelerating Diffusion Sampling via Speculative Draft Trees

The paper introduces "draft trees" to accelerate diffusion model sampling by allowing non‑linear lookahead drafts, thereby increasing acceptance rates per expensive target evaluation. It connects speculative sampling to relative entropy coding, adopts greedy rejection sampling as the draft‑target coupling, and demonstrates up to 8.3% speed‑up over reflection coupling baselines in experiments.

By Marcello Bullo, Yanxiao Liu, \"Oyk\"u S{\i}la G\"uner, Arpan Mukherjee, Deniz G\"und\"uz
arXiv Computation and Language
Oct 22

Understanding Target Probability Reuse in Speculative Decoding

The paper investigates how target model probability distributions can be reused during speculative decoding to improve token selection. It shows that exact reuse requires a distribution computed with the full next-round context, and that retaining this distribution can force the rejection of accepted tokens. Experiments across six target models demonstrate that reranking first-token branches with a separately computed distribution at the current context boosts expected acceptance, especially with small tree budgets, and that drawing the first token from this distribution before tree allocation further improves acceptance and decoding speed.

By Jungseob Lee, Giyoon Jang, Chailin Nam, Jiwoo Kum, Sihyeon Lee, Kyojun Choo, Jihun Song, Eunseo Song, Chanjun Park
arXiv Machine Learning
Oct 28

Multiple Importance Sampling for Guided Speculative Inference

The paper extends Guided Speculative Inference (GSI) for test‑time scaling of large language models by allowing an ensemble of smaller LLMs to propose draft reasoning steps, which are then verified by a larger base model and a reward model. Using multiple importance sampling (MIS), the authors introduce weighting schemes to combine samples from diverse proposal distributions, prove new bounds on KL divergence and expected reward loss, and show that the balance heuristic is optimal. Experiments demonstrate that combining several diverse LLMs, while keeping the total number of samples fixed, achieves competitive downstream performance and is mathematically robust when a single draft model’s support does not cover the target distribution, a scenario where standard GSI may fail.

By Joseph Rowan, Ashish J. Khisti
arXiv Machine Learning
Oct 28

Bastion: Budget-Aware Speculative Decoding with Tree-structured Block Diffusion Drafting

Bastion is a budget‑aware speculative decoding framework that uses tree‑structured block diffusion drafting to improve the efficiency of language model inference. It dynamically builds query‑dependent trees, balancing draft quality with hardware constraints, and incorporates an acceptance surrogate, an online latency estimator, and an adaptive best‑first expansion to maximize speed without sacrificing model distribution. The method achieves up to a 6.61× speedup over standard autoregressive decoding and outperforms state‑of‑the‑art block‑diffusion baselines by 39% across various benchmarks and GPU architectures.

By Soowon Oh, Nam Cao, Yujin Kim, Hojung Jung, Huzama Ahmad, Sangmin Bae, Se-Young Yun
arXiv AI
3d ago

DForkTree: Accelerating Speculative Decoding with Fork-Aware Block Diffusion Draft Trees

DForkTree is a training‑free method that improves speculative decoding by re‑anchoring each branch of a draft tree on its own tokens. It adjusts drafter scores using pointwise mutual information from target‑generated n‑grams, weighting these adjustments more heavily after a fork, and employs a layer‑wise GPU search to recover the exact optimal tree. On Qwen3.5‑4B and 9B models, DForkTree outperforms all baselines, achieving up to 41.5% better results than DFlash, 15.1% better than DDTree, and average speedups of up to 4.75× over autoregressive decoding.

By Zhicheng Zheng, Cheng Zhang, Chenkai Tang, Tianxiang Zhao
arXiv Computation and Language
Aug 28

TreeGraft: Adaptive Multi-Drafter Grafting for Tree-Based Speculative Decoding

TreeGraft introduces a multi-drafter framework that combines drafters of varying costs to build a shared draft tree for tree-based speculative decoding. The stronger drafter rescues and rescoring candidates from the weaker drafter, while a lightweight scheduler decides when to invoke the stronger drafter to manage cost. Experiments on 10 model pairs and 6 benchmarks show TreeGraft improves over the best single-drafter strategy by an average of 15.1% and up to 26.6%.

By Jiaming Fan, Daming Cao, Canchen Huang, Jiale Fu, Jin Zhang, Junjie Gao, Kai Yang, Xiangzhong Luo, Xu Yang