# From Chains to Trees: Parent-Conditioned Drafting for Semi-Autoregressive Speculative Decoding

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 26 of its 28 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Placed in

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

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

- [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)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [From Crowdsourced Data to High-Quality Benchmarks: Arena-Hard and BenchBuilder Pipeline](https://mlsanity.com/paper/2406.11939/) (2024)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [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)
- [Better & Faster Large Language Models via Multi-token Prediction](https://mlsanity.com/paper/2404.19737/) (2024)
- [EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test](https://mlsanity.com/paper/2503.01840/) (2025)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [MathArena: Evaluating LLMs on Uncontaminated Math Competitions](https://mlsanity.com/paper/2505.23281/) (2025)
- [Speculative Decoding: Exploiting Speculative Execution for Accelerating Seq2seq Generation](https://mlsanity.com/paper/2203.16487/) (2022)
- [DFlash: Block Diffusion for Flash Speculative Decoding](https://mlsanity.com/paper/2602.06036/) (2026)
- [OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure](https://mlsanity.com/paper/2406.17276/) (2024)
- [Semi-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1808.08583/) (2018)
- [DSpark: Confidence-Scheduled Speculative Decoding with Semi-Autoregressive Generation](https://mlsanity.com/paper/2607.05147/) (2026)
- [Accelerating Speculative Decoding with Block Diffusion Draft Trees](https://mlsanity.com/paper/2604.12989/) (2026)
- [TAPS: Target-Aware Prefix Tree Selection for Diffusion-Drafted Speculative Decoding](https://mlsanity.com/paper/2606.00487/) (2026)

## Built on by (most cited first, 3 of 3)

- [Beyond Parallel Blindness: Information Floors and Model Gaps in Block Drafting](https://mlsanity.com/paper/2608.27339/) (2026)
- [TreeSpark: Calibrated, Load-Adaptive Draft Trees for Semi-Autoregressive Speculative Decoding](https://mlsanity.com/paper/2609.22098/) (2026)
- [AdaSpark: Adaptive DSpark with Online Learning for Tree Verification and N-gram Fill](https://mlsanity.com/paper/2610.05774/) (2026)

## Abstract (arXiv)

Speculative decoding accelerates LLM inference only when drafted continuations survive target-model verification. Semi-autoregressive drafters such as DSpark predict an entire token block with one backbone forward and refine it with a lightweight Markov head. However, DSpark decodes this block as a single chain, so an early mismatch invalidates the remaining suffix and limits the benefit of large draft blocks. We show that the conditional structure already learned by DSpark can support multiple parent-consistent continuations without retraining or additional backbone passes. We introduce Parent-Conditioned Drafting Tree (PCTree), which uses the pretrained Markov head to score alternative children separately for each concrete parent and allocates a fixed verification budget to the most probable paths. This converts DSpark's linear draft into a tree while preserving its one-pass parallel backbone. Across Qwen3-4B,8B,14B and nine benchmarks, at B=7, measured speedup gains over autoregressive (AR) decoding, relative to matched DSpark, range from 3.1% to 29.5%. On Qwen3-4B GSM8K at B=16, PCTree increases mean acceptance length from 9.41 to 11.16 and three-run mean AR speedup from 6.14× to 6.60×. These show that parent-conditioned branching can turn conditional capacity already present in a semi-autoregressive drafter into end-to-end inference gains through an inference-only change.