Tree speculative decoding on DeepSeek-V4 — Branch-isolated compressed state — What does it mean?

The news. On September 21, 2026, Changxu Liu and Zhaogeng Li (Baidu's Baige AI team and Fudan University) posted a report on adapting tree-structured speculative decoding to DeepSeek-V4-Flash inside SGLang. They add branch-aware causal verification, temporary state isolation and accepted-path state refresh, then compare tree against single-chain speculation at matched budgets D=5 to D=8, batch sizes 1 to 64, and three workloads (GSM8K, MBPP, ShareGPT) on one eight-GPU NVIDIA machine. The tree accepted more tokens per round in every setting and raised decode throughput in nearly all configurations, by up to about 18.5%. Read the paper →

Picture a novelist who keeps a notebook in ink and, at the top, a running summary that squeezes every few pages into one line. To try three possible next scenes, the novelist writes each one on its own sticky note. The rule that keeps the notebook correct: no sticky note touches the summary until one scene is chosen. If the novelist summarized all three drafts together, the summary would describe a story that never happened, with scene A's argument and scene C's ending blended into one line.

That is the problem speculative decoding meets with a draft tree. The target model checks every candidate branch in one pass, and each branch is a different, mutually exclusive continuation of the same accepted prefix. A classic transformer's notebook has no summary: the KV cache stores one separate entry per token. So the model can put all branches in the same batch and use a tree-shaped causal mask that stops each candidate from seeing tokens on other branches. Covering the other sticky notes with your hand is enough.

DeepSeek-V4 adds the summary. Its CSA and HCA attention paths compress the history along the sequence, merging information from several token positions into shorter entries as the text grows. Once two branches split, they compress into different states, so a mask over shared entries is no longer enough. The compressed entry for branch A is built from branch A's tokens. Reusing it for branch B, or writing it into the persistent cache before verification finishes, would carry a rejected branch into every later decoding step.

The paper's fix has three parts, and each one follows the sticky-note rule:

1. Branch-aware causal verification. A verify preprocess turns the tree into a plan. It extracts each candidate chain and marks the compression boundaries, so chains share compression work only up to the point where they split.
2. Temporary state isolation. Each chain's compressed tokens and intermediate compression results live in a scratch pad, not in the persistent page-based cache. Nothing speculative is written to the permanent history before it is accepted.
3. Accepted-path state refresh. After verification picks one path, only that path's states are committed, so the tokens, the attention cache and both compressed states describe the same prefix again.

Some of this work can be skipped. If there is only one chain, or the accepted chain is already the latest one cached, the refresh is skipped. The two compression paths, which the paper calls C4 and C128, are refreshed on different schedules: C4 compresses more often and is updated promptly, while some C128 writes can wait and be combined after the accepted path is known.

Where the speedup actually goes. Hold three things fixed: the ShareGPT chat workload, a budget of D=8 candidate tokens checked per round, and 1,000 generated tokens, using the paper's accepted lengths averaged over batch sizes 1 to 64. The single chain accepts about 2.39 tokens per round, so it needs about 1,000 ÷ 2.39 ≈ 418 target-model passes. The best tree at the same budget accepts about 2.84, so it needs about 1,000 ÷ 2.84 ≈ 352 passes: 66 fewer verification rounds, about 16% fewer (Table 1). Averaged over all three workloads, accepted length at D=7 and D=8 rises about 17–19%, yet decode throughput rises only about 9–10%. The gap is the price of the sticky notes: building the tree, the verify plan, the scratch-pad states and the accepted-path refresh all add time to every round, and beyond about D=6 that overhead grows as fast as the extra acceptances. Batch size moves the result too: at D=6 the gain is about +8% at batch size 1, about +11% at batch size 4 and about +7% at batch size 64, because at large batches the target pass is already compute-bound and extra candidates compete for compute instead of saving memory reads. The single best case, about +18.5%, was ShareGPT with 3 draft steps, two branches per step (top-2), D=6 and batch size 4.

Tree speculation pays off only when two things are true together: the drafter's accuracy is the bottleneck, and the target model can verify a tree cheaply. The first already holds here. At a fixed budget, a deeper chain barely changes accepted length (the configurations differ by about 2%), so extra depth buys nothing and width is the remaining lever. The second is where the architecture decides. The authors argue that as more models store context in compressed, sparse or structured form, the verify side becomes the deciding factor. It also has to fit around CUDA Graph replay, which expects stable shapes while tree shapes change from round to round, so the paper sizes its graph coverage to the tree configurations it expects.

Goes deeper in: LLM Serving → Speculative Decoding → The Verification Algorithm

Related explainers

• JetSpec — Parallel tree drafting — why a tree of guesses beats one chain, from the drafter's side
• DeepSeek V4 — long-context cost cut — what CSA and HCA compress, and what that saves
• vLLM 0.29 — Mamba prefill checkpoints — another case where a running state, not a per-token cache, must be saved and restored