speculative decoding: better trees weren't enough

I wanted to understand LLM inference well enough to try improving something in it. So in September I spent three weeks on PairTree, an attempt to make speculative decoding pick better guesses.

I’m a software engineer, not an inference researcher, and I leaned heavily on coding agents for the code and the planning.

The idea worked: the trees did pick better guesses. The system was still slower than the one I wanted to beat, and the measurement that showed this came in on my second day. This post is about the idea, and about how I spent three weeks on a question that left that measurement out.

The idea

In speculative decoding, a small draft model guesses several upcoming tokens and the large target model checks them all in one pass. If enough guesses are right, one expensive pass produces several tokens instead of one.

DFlash drafts a whole block of tokens in parallel. DDTree, by Liran Ringel and Yaniv Romano, turns those guesses into a tree of alternative continuations, so the target can check several branches in the same pass.

DDTree scores each guess on its own, without looking at the guesses before it in the same draft. I’ll call this unary scoring. Suppose the draft offers “hot” or “ice” at one position and “soup” or “cream” at the next. Unary scoring gives “soup” the same score after “hot” as after “ice”, although “hot soup” and “ice cream” are far more likely than “ice soup”.

DFlash2 adds a small trained selector that scores each guess given the guess right before it. DFlash2 uses it to pick a single path. PairTree uses the same scores to pick a whole tree.

None of the parts were new. The drafter, the selector and the tree builder already existed. The work was connecting them and testing whether the combination helped.

A tree’s budget is how many guessed tokens it can hold across all its branches. Try changing it below. With six nodes, PairTree covers the whole target phrase. Unary spends its nodes on every two-word pair, “ice soup” and “hot cream” included, and runs out before “melts”.

Fig. 1 · Interactive
Same budget. More of the right phrase.
Targetice → cream → melts
Unary
2 / 3target words matched
ice: matchedcream: matchedmelts: missing
PairTree
3 / 3target words matched
ice: matchedcream: matchedmelts: matched
PairTree matches 1 more target word. Unary spends its six nodes on every two-word pair, “ice soup” and “hot cream” included.
Unary tree
hot1soup3steamsmeltscream4steamsmeltsice2soup5steamsmeltscream6steamsmelts
PairTree
hot1soup3steams5meltscreamsteamsmeltsice2soupsteamsmeltscream4steamsmelts6
Inspect every prefix score
Draft prefixUnary path scoreConditional path score
hot0.52000.5200
hot → soup0.21320.3744
hot → soup → steams0.08740.2696
hot → soup → melts0.08310.0300
hot → cream0.20280.0416
hot → cream → steams0.08310.0033
hot → cream → melts0.07910.0300
ice0.48000.4800
ice → soup0.19680.0384
ice → soup → steams0.08070.0276
ice → soup → melts0.07680.0031
ice → cream0.18720.3456
ice → cream → steams0.07680.0276
ice → cream → melts0.07300.2488
Illustrative scores, not a model run; one word stands for one token. Unary gives each word one score per position, averaged over the earlier choice, so “ice soup” and “ice cream” look almost equally likely. Counts exclude the known root and any bonus token, and matching stops at the first missing target word.
How the scores become a tree

I kept the top 16 candidates at each position, turned the selector’s scores into probabilities, and multiplied them along each path. Then I repeatedly added the highest-scoring path until the budget ran out. A node could only join the tree after its parent had.

One detail mattered more than I expected. Suppose the 16 candidates held 80% of the draft’s probability. Rescaling their scores to 100% would pretend the other 20% didn’t exist. Instead, I split the original 80% among them according to the selector, and left 20% for tokens outside the set.

Fig. 2 · Interactive
Keep room for the missing candidates.
Hold the within-set ranking at A:B = 3:1; vary the retained mass and depth.
Top-K renormalized: A 75% · B 25% · outside 0%
Mass preserved: A 60.0% · B 20.0% · outside 20%
Candidate ACandidate BOutside the set
Mass on paths inside the candidate sets, after 4 draft positions
Mass preserved
41.0%
Renormalized each step
100%
Renormalizing gives these paths 2.44× the mass the scoring model assigns them.
Illustrative arithmetic: each position retains the same mass. This counts the whole candidate lattice before allocating nodes, not target acceptance. At 80% over four positions, retained-path mass is 0.8⁴ = 40.96%.

Day two

Before writing any PairTree code, I ran plain DFlash and DFlash2 on 32 math prompts. I expected the newer drafter to be faster. It wasn’t: original DFlash generated 126.5 tokens per second and DFlash2 88.4. Original DFlash with DDTree was about twice as fast as DFlash2.

The reasons were concrete. DFlash2’s drafter took 64% longer per round. The DFlash2 checkpoint I was using, an experimental community release rather than the authors’ own, drafts 7 tokens per round. Original DFlash drafts 15. However good my tree, it could never accept more than 7 draft tokens in a round.

So I narrowed the question. Instead of racing original DFlash with DDTree, I would compare PairTree with unary trees on the same DFlash2 drafter, change nothing else, and treat the gap between the two drafters as a separate systems question. That’s good science. It isolates exactly what PairTree changes. It also meant the cleaner question gradually replaced the one I’d started with.

The narrow question went well

On saved traces from the 32 math prompts, PairTree matched more of the target’s actual continuation at every budget. At budget 16, it matched 4.82 draft tokens per round against unary’s 4.38. Live generation on math, code and conversation prompts showed the same pattern: 0.3 to 0.6 more matched tokens per round at budget 32.

The test I found most convincing challenged a simpler explanation: maybe unary just needed more candidates. Giving unary 64 candidates per position instead of 16 barely moved it. At a fixed budget of 64 on GSM8K, it went from 4.946 matched tokens per round to 4.948. PairTree, still limited to 16 candidates, reached 5.491.

Fig. 3 · Measured
More candidates barely helped unary.
Matched draft tokens per round, at a fixed budget of 64 nodes
GSM8K
Unary · 16 candidates
4.946
Unary · 64 candidates
4.948
PairTree · 16 candidates
5.491
MATH500
Unary · 16 candidates
5.190
Unary · 64 candidates
5.196
PairTree · 16 candidates
5.750
Uncertainty of the PairTree advantage
DatasetPairTree − unary K6495% CI
GSM8K+0.543[0.498, 0.589]
MATH500+0.554[0.503, 0.603]
128 prompts per dataset, A100 40GB. Candidate counts are per position; the tree budget stays fixed. These are prompt-mean matched tokens, excluding the root. Report, Table 2.

The effect also carried over to the authors’ own, much larger DFlash2 checkpoint for a 27B model: about 0.4 more matched tokens per round at every budget I tested.

Back to the bottom line

On day five I went back to tokens per second, which had been the bottom line all along, and built the full benchmark: plain decoding, original DFlash, original DFlash with DDTree, and the DFlash2 variants. Same 4B model, same prompts, one H100.

Inside DFlash2, PairTree was faster than unary, but not by much. At budget 16, the gain was 3.5% on GSM8K, and on HumanEval the interval included zero. Larger trees did better, with gains of about 10% at budget 64.

Fig. 4 · Measured
A small gain over unary on the same drafter.
PairTree minus unary, in tokens/s. Dot = mean difference; line = 95% interval.
Budget 16 · primary comparison
GSM8K +5.28
HumanEval +2.54
Budget 64 · secondary comparison
GSM8K +16.80
HumanEval +14.28
HumanEval at budget 16 crosses zero: the primary result there is inconclusive.
Exact intervals and measurement details
BudgetDatasetDifference95% CI
16GSM8K+5.28[1.75, 8.82]
16HumanEval+2.54[-0.95, 5.99]
64GSM8K+16.80[12.91, 20.90]
64HumanEval+14.28[11.16, 17.50]

Budget 16 was the primary comparison; budget 64 is secondary.

Full-generation timing, 32 development prompts per dataset. Report, Table 5.

Against the original system, none of it mattered. I had carefully improved a system that was slower than the original.

Fig. 5 · Measured
A better tree inside a slower system.
Tokens/s on Qwen3-4B, H100. Tree methods use budget 64.
GSM8K
DFlash2 + unary
163
DFlash2 + PairTree
180−82 vs DDTree
Original DFlash, no tree
206
Original DFlash + DDTree
262
HumanEval
DFlash2 + unary
151
DFlash2 + PairTree
165−117 vs DDTree
Original DFlash, no tree
228
Original DFlash + DDTree
282
Mean rates on 32 prompts per dataset, rounded to whole tokens/s. Different drafter checkpoints, draft lengths, and attention backends make this a system comparison. Gains quoted in the text average per-prompt changes, so they differ slightly from ratios of these means. Exact results and timing.

At budget 64, PairTree generated 180 tokens per second on GSM8K. Original DFlash with DDTree generated 262. On HumanEval it was 165 against 282. Original DFlash without any tree, at 206 and 228, beat it too. In the full benchmark, PairTree was still 3.6–3.8 times faster than ordinary decoding. It just wasn’t the fastest option.

The per-round timings from the full benchmark (budget 16, GSM8K) show why:

Per round Original DFlash + DDTree DFlash2 + PairTree
Drafting 4.5 ms 8.1 ms
Verifying 20.3 ms 21.9 ms
Matched draft tokens 6.26 4.82
Tokens per second 261 177

Each round also produces one token from the target itself. So the original system emits about 7.3 tokens every 24.8 ms, and PairTree about 5.8 every 30.0 ms. That arithmetic alone predicts a 1.5× gap, and the measured gap was 1.48×. Building PairTree’s tree added about 0.1 ms per round. Its scoring worked fine, but it sat on a drafter that was slower per round and could never draft past 7 tokens.

Fig. 6 · Illustration
More tokens can still take longer.
Decoding rate ≈ tokens emitted per round ÷ time per round
Toy numbers, not benchmark data. Each square is one emitted token; bar length is the time one draft-and-verify round takes. This excludes prefill, while the measured rates in Fig. 5 time the full generation call.

It’s the same story I had on day two, just with a better tree in it.

One more thing needed checking. With greedy decoding, speculative decoding should reproduce ordinary decoding exactly. In 16-bit precision, none of the 4B systems did that reliably. Original DFlash and DDTree matched ordinary decoding on 39–59% of prompts, and PairTree at budget 16 on 35–57%. I replayed 16 divergences in detail. Each came down to a near-tie between two tokens that flipped when the computation was arranged differently, not to a bug I could find. Task accuracy stayed within three problems of ordinary decoding on each benchmark. The 27B runs, which verified one token at a time, matched exactly on all 768 outputs.

Even the investigation needed checking. I discarded the first diagnostic run because it restored model buffers at the wrong precision. I was debugging the code that was supposed to tell me whether my other code was wrong.

Someone had already done it

On September 23 I came across two papers. CaDDTree picks DDTree’s budget by estimating what each extra node costs. DominoTree, by Saw S. Lin and Jyh-Shing Roger Jang, is closer. Domino is a drafter that ships with a small trained module for correcting its guesses. DominoTree reuses that module, without new training, to score a DDTree-style tree. That’s the core of PairTree. I stopped the project that day.

There is a real difference. DominoTree carries a running state along each branch, so it remembers the whole path. PairTree only sees the previous token. Two branches that end in the same token get the same scores in PairTree, but can get different ones in DominoTree. I never tested whether that difference would have helped.

Fig. 7 · Concept
Same last token. Different histories.
Same verified context and draft position; different earlier branch choices.
PairTree
riverbank?centralbank?
Same next-token scores
Only the last candidate, “bank”, enters the correction.
DominoTree
riverbank?centralbank?
Next-token scores can differ
Each branch carries its own recurrent state.
Highlighting shows which branch choices the correction can use when scoring the next token. Both methods also use shared draft context. Remembering more history allows different scores; it does not guarantee better predictions. DominoTree v3.

DominoTree’s own results echoed mine. In one 4B setup, it accepted more tokens than the plain Domino drafter and was slightly slower: 4.40× faster than ordinary decoding, against 4.46×.

DominoTree’s first version was posted on July 9, eight weeks before I started. While writing this post, I went back through my logs. A search on my first day, meant to estimate how long a benchmark would take, had returned a project README that listed DominoTree among the methods it compared. I didn’t notice it. I searched for benchmark numbers, verifier implementations and serving bugs. In three weeks of logs there isn’t a single search for the idea itself.

What I’d do differently

Define what would count as a win. For this project, that meant beating original DFlash with DDTree in tokens per second, not just accepting more draft tokens. On day two, I already knew the drafting cost and the 7-token limit. Before improving the tree, I should have worked out how much room those left to close the gap.

Use prior work to decide what’s worth testing. Finding DominoTree earlier wouldn’t just have told me the idea existed. It would have given me a different question: was PairTree’s simpler, previous-token scoring a useful alternative to remembering the whole branch? I could have started with that difference instead of leaving it untested at the end.

Make the change of question explicit. Comparing PairTree with unary on the same drafter was a good experiment. It answered “does this pick better guesses?”, not “is this faster than the best system I have?” I could reasonably have chosen to study the first. The mistake was treating progress on it as progress on the second.

The code is public, and the technical report has the full experiments, confidence intervals and caveats.