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”.
Inspect every prefix score
| Draft prefix | Unary path score | Conditional path score |
|---|---|---|
| hot | 0.5200 | 0.5200 |
| hot → soup | 0.2132 | 0.3744 |
| hot → soup → steams | 0.0874 | 0.2696 |
| hot → soup → melts | 0.0831 | 0.0300 |
| hot → cream | 0.2028 | 0.0416 |
| hot → cream → steams | 0.0831 | 0.0033 |
| hot → cream → melts | 0.0791 | 0.0300 |
| ice | 0.4800 | 0.4800 |
| ice → soup | 0.1968 | 0.0384 |
| ice → soup → steams | 0.0807 | 0.0276 |
| ice → soup → melts | 0.0768 | 0.0031 |
| ice → cream | 0.1872 | 0.3456 |
| ice → cream → steams | 0.0768 | 0.0276 |
| ice → cream → melts | 0.0730 | 0.2488 |
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.
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.
Uncertainty of the PairTree advantage
| Dataset | PairTree − unary K64 | 95% CI |
|---|---|---|
| GSM8K | +0.543 | [0.498, 0.589] |
| MATH500 | +0.554 | [0.503, 0.603] |
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.
Exact intervals and measurement details
| Budget | Dataset | Difference | 95% CI |
|---|---|---|---|
| 16 | GSM8K | +5.28 | [1.75, 8.82] |
| 16 | HumanEval | +2.54 | [-0.95, 5.99] |
| 64 | GSM8K | +16.80 | [12.91, 20.90] |
| 64 | HumanEval | +14.28 | [11.16, 17.50] |
Budget 16 was the primary comparison; budget 64 is secondary.
Against the original system, none of it mattered. I had carefully improved a system that was slower than the original.
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.
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.
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.