From Chains to Trees: Parent-Conditioned Drafting for Semi-Autoregressive Speculative Decoding
2026-08-03 • Computation and Language
Computation and Language
AI summaryⓘ
The authors study a way to speed up how large language models generate text by improving a method called DSpark, which drafts multiple tokens at once but loses speed if an early prediction is wrong. They propose a new method, Parent-Conditioned Drafting Tree (PCTree), that lets the model explore multiple possible next words in a tree structure rather than a single chain, without needing extra training. By checking only the most likely paths, PCTree achieves faster and better predictions on various benchmarks compared to DSpark and traditional methods. This shows that reorganizing the decoding process alone can make inference more efficient.
speculative decodingsemi-autoregressive decodingDSparkParent-Conditioned Drafting TreeMarkov headlarge language modelsinference speeduptoken blockautoregressive decodingconditional structure
Authors
Zixian Li, Tong Li, Chi Xie, Xiaohui Song, Haonan Lu
Abstract
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{\times}$ to $6.60{\times}$. 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.