Vanilla speculative decoding samples one K-token draft chain per round. Tree-based speculative decoding samples a TREE of candidate continuations and verifies all branches in a single target forward pass via a tree attention mask. Why does this dominate the chain version at the same number of verified positions?
Free · 2 AI evals / day
**Speculative decoding** speeds up generation by letting a small draft model guess several future tokens, then having the big target model check them in one pass. If the guesses match what the target would have produced, you accept them for free. Verifying many positions at once costs about the same as generating one token, because decode is memory bound, not compute bound.
The original version drafts a single chain: a token, then the next token, then the next. The problem is fragility. The moment the target rejects one token, every guess after it is thrown away, because those later guesses assumed the rejected token was correct.
Tree-based decoding fixes this by drafting several alternatives at each step instead of one. You build a small tree of candidate continuations rather than a single line. A custom attention mask lets the target verify the whole tree in one forward pass.
Because the tree offers more candidate paths, the longest path the target agrees with tends to be longer than a single chain's accepted prefix. You still accept only one path per round, but you expect that path to be longer, so you generate more tokens per expensive target call.
**Tree-based speculative decoding** drafts a branching tree of candidate continuations, not one linear chain, and verifies the entire tree in a single target forward pass.
The mechanism is a tree attention mask. Each tree node attends only to its ancestors, so sibling branches stay logically independent inside one batched pass. The target therefore scores many distinct continuations at once. Decode is memory-bandwidth-bound, so adding tree positions costs extra arithmetic but barely more wall-clock time. The cost is matched to a chain of similar width.
Why it dominates is a question of expected accepted length. On a chain, the first rejected token ends the round and discards everything to its right. On a tree, that same rejection kills only one branch; sibling paths survive. Exactly one root-to-leaf path is accepted per round, but it is the best path through a wider candidate set. So expected accepted tokens per target call rise.
Two systems efficiencies make it practical. Sibling branches share the common prefix's draft KV cache, so memory grows sub-linearly in tree size. The single masked target pass keeps verification at one call. In practice this yields roughly 1.5 to 2 times more accepted tokens per round than a chain at matched compute.
Quick reference
TL;DR
A tree verifies many draft branches in one target pass via a tree attention mask, so one rejection kills only a branch, not the round, raising expected accepted tokens at matched target cost.
Imagine guessing the next few words in someone's sentence so they only have to nod yes or no. A linear draft is one long guess: the first wrong word ends the whole guess. A tree guesses several alternatives at each step, like offering two endings for every word. The listener checks all the branches at once and keeps the one good path. Because you offered more options, the longest agreed run is usually longer. Checking all branches together costs barely more than checking one, since they share the same starting words. So per question you get more confirmed words for almost the same effort, which is exactly what makes generation faster.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Workloads where draft acceptance probability is already very low If few tokens are accepted, wider trees just verify more rejected nodes and waste target arithmetic for little gain.
Tight memory budgets where even sub-linear tree KV is too much Large trees still grow the draft KV footprint, and on constrained hardware that memory may be better spent on batch size.
Very small target models where the target pass is already cheap The speculative overhead of drafting and masking can exceed the savings when a single target step is not the bottleneck.
Latency-insensitive offline batch jobs that are throughput bound Large continuous batches already saturate the GPU, so speculative tree decoding adds complexity for little wall-clock benefit.
Quick scan · 2–4 min
Everything important, quickly.
4 min: chain fragility on first rejection, then the tree mask in one target pass, then one accepted path but longer expected length, then sibling KV sharing, then width versus depth and dynamic trees.
Real-world examples
Real products, models, and research that use this idea.
1Medusa adds parallel decoding heads to a frozen model and verifies their tree of candidates with a tree attention mask in one pass.
2EAGLE-2 drafts in feature space and grows a dynamic, confidence-weighted token tree, reporting roughly 1.5 to 2 times the accepted tokens of chain drafting.
3vLLM and SGLang ship speculative decoding with tree or n-gram drafting as a production throughput lever for serving Llama 4 and Qwen 3.
4TensorRT-LLM (NVIDIA) implements Medusa-style tree verification on H100 and B200 as part of its production inference stack.
5DeepSeek V4 ships multi-token prediction heads that draft several future tokens for speculative verification at serving time.
Interviewer follow-ups
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy does tree verification preserve the target model's exact sampling distribution?
Sign in or go Pro to see the approach for this follow-up.
QHow do you choose tree width versus depth for a given draft and target pair?
Sign in or go Pro to see the approach for this follow-up.
QWhat changes in the tree mask and KV layout when you batch many requests together?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
Claiming the tree accepts multiple paths per round. Exactly one path is accepted; the gain is a wider candidate set raising the expected length of that single accepted path.