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?
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.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Tree-based speculative decoding is the current state of the art in lossless LLM inference acceleration, and it is a favourite senior interview probe because it forces you to reason jointly about probability, attention masking, and memory-bandwidth economics. Get it right and you signal that you understand decode as a systems problem, not just a model-architecture detail.
The starting point is plain speculative decoding. A cheap draft proposes several future tokens; the expensive target verifies them in a single forward pass; you accept the longest target-consistent prefix. Because decode is memory-bandwidth-bound, the GPU spends most of its time streaming the target's weights and KV cache from HBM rather than doing arithmetic. That means verifying many positions in one pass costs barely more wall-clock time than generating a single token, since the expensive memory traffic is amortized. Crucially, the speculative acceptance test is designed so the output distribution is provably identical to ordinary autoregressive sampling. This is a pure speed win, not a quality tradeoff, which is what makes it safe to deploy in production.
The original formulation drafts a single linear chain, and that is its weakness. This deep dive explains why a branching tree of candidates strictly dominates a chain at matched target cost, how the tree attention mask makes it affordable in one pass, why sibling KV sharing keeps memory sub-linear, and how tree shape becomes the central tuning knob in systems like Medusa and EAGLE-2. By the end you should be able to derive the expected-accepted-tokens argument, sketch the mask on a whiteboard, and explain to an interviewer exactly which resource each design choice spends.
Why a draft chain is fragile
In chain speculative decoding the draft proposes tokens sequentially: each guess assumes every earlier guess was correct. The target then verifies them left to right with an acceptance test against its own conditional distribution. The first time the draft and target disagree, the round stops.
The fragility is structural. The first rejected position ends the round, and every drafted token to its right is discarded, because those tokens were conditioned on a token the target just rejected. They are now off distribution and worthless. A draft that proposed five tokens but missed on the second has wasted three positions of work, even though the target had to score all of them.
So the accepted length per round is a single sample of a random variable: how far the draft's one line of reasoning happens to agree with the target before the first miss. If per-token acceptance probability is α, the expected accepted run follows a geometric tail that decays quickly. At α around 0.7 the expected run is only a couple of tokens, and a single early rejection wastes the whole draft budget for that round.
The deeper problem is that the chain commits to one hypothesis. If the draft's most likely next token is wrong but its second most likely token would have been accepted, the chain never finds out. There is no mechanism to hedge across alternatives, and that lost optionality is exactly what the tree recovers.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- Medusa adds parallel decoding heads to a frozen model and verifies their tree of candidates with a tree attention mask in one pass.
- EAGLE-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.
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?
Each node uses the standard speculative acceptance test against the target's own conditional distribution at that position, with a residual correction on rejection. Verification only changes the order tokens are proposed in, not the distribution accepted from, so the output is provably identical to plain autoregressive sampling.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
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.
60 second bullets to scan on the way to the call.
Why a chain round collapses entirely on the first rejected token
How a tree mask lets siblings share a prefix yet verify independently
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.