# Tsubame: Tree Replay for Diffusion-Based Speculative Decoding

arXiv: https://arxiv.org/abs/2609.33652 · HTML: https://mlsanity.com/paper/2609.33652/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 28 of its 33 references that are in the map.
- First posted on arXiv 27 Sep 2026.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 28 of 28)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test](https://mlsanity.com/paper/2503.01840/) (2025)
- [DFlash: Block Diffusion for Flash Speculative Decoding](https://mlsanity.com/paper/2602.06036/) (2026)
- [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023)
- [OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure](https://mlsanity.com/paper/2406.17276/) (2024)
- [DSpark: Confidence-Scheduled Speculative Decoding with Semi-Autoregressive Generation](https://mlsanity.com/paper/2607.05147/) (2026)
- [Domino: Decoupling Causal Modeling from Autoregressive Drafting in Speculative Decoding](https://mlsanity.com/paper/2605.29707/) (2026)
- [Block Verification Accelerates Speculative Decoding](https://mlsanity.com/paper/2403.10444/) (2024)
- [Accelerating Speculative Decoding with Block Diffusion Draft Trees](https://mlsanity.com/paper/2604.12989/) (2026)
- [Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement](https://mlsanity.com/paper/2402.14160/) (2024)
- [DySpec: Faster Speculative Decoding with Dynamic Token Tree Structure](https://mlsanity.com/paper/2410.11744/) (2024)
- [Towards Optimal Multi-draft Speculative Decoding](https://mlsanity.com/paper/2502.18779/) (2025)
- [Traversal Verification for Speculative Tree Decoding](https://mlsanity.com/paper/2505.12398/) (2025)
- [Breaking Entropy Bounds: Accelerating RL Training via MTP with Rejection Sampling](https://mlsanity.com/paper/2606.12370/) (2026)
- [DominoTree: Conditional Tree-Structured Drafting with Domino for Speculative Decoding](https://mlsanity.com/paper/2607.08642/) (2026)
- [UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding](https://mlsanity.com/paper/2605.04543/) (2026)
- [RheoSampling: Resolving the One-Hot Dilemma in Stochastic Dynamic-Tree Speculative Decoding](https://mlsanity.com/paper/2609.21827/) (2026)

## Abstract (arXiv)

Context-aware dynamic trees allocate the speculative decoding budget according to draft path probabilities, adapting their depth and branching to the current context. Under stochastic decoding, however, we find that this structural advantage does not always compensate for the acceptance gains of random sampling paired with advanced verification, and such dynamic trees can fall behind sampled chains in some settings. These trees grow their topology from the candidates themselves, so the tokens submitted for verification are typically the deterministic high-score tokens selected during construction. This coupling is not inherent: once the topology is fixed, its nodes can be repopulated by sampling, allowing dynamic trees to retain their structural advantage while also benefiting from random sampling and advanced verification. Diffusion-based drafters make this practical, as their parallel outputs or lightweight conditional corrections allow candidates to be regenerated cheaply after the complete topology is known. We introduce Tsubame, a two-pass tree speculative decoding framework for diffusion-based drafters. The first pass plans and freezes a context-aware topology using draft path scores; the second replays the fixed topology, sampling the tokens that populate its nodes to form the candidate tree for verification. We prove that Tsubame is lossless under compatible sampling and verification strategies. Experiments across three diffusion-based drafters, six datasets, and multiple candidate budgets show that Tsubame improves acceptance length and throughput over deterministic trees, including settings where it reverses their disadvantage against sampled chains.