DominoTree: Growing a Tree for Speculative Decoding from Domino's Conditional Drafts
An Old Problem
When you chat with an LLM, it produces text token by token. Each token takes roughly 30 milliseconds, so a 1,000-word reply means waiting about half a minute. This is autoregressive decoding: every generated token requires a full forward pass of the model, even if you only want one more character.
Can the model guess several tokens at once and verify them in a batch? That is the core idea of speculative decoding: a lightweight "drafter" quickly generates a few candidate tokens, and the large model verifies them in parallel. Correct guesses yield extra tokens for free; wrong guesses trigger a rollback to the correct position.
Sounds great, but the devil is in the details. How should the drafter guess? How many tokens? How should candidates be organized? The answers directly determine the upper bound of the speedup.
In July 2026, researchers Saw S. Lin (Zhiqi Zhang) and Jyh-Shing Roger Jang from National Taiwan University published a paper on arXiv titled DominoTree: Conditional Tree-Structured Drafting with Domino for Speculative Decoding, offering an elegant answer: let the dominoes grow a tree themselves.
The Dilemma of Two Routes
To understand DominoTree's contribution, consider the two prior technical routes.
Route one: Block Diffusion. The representative method is DFlash. It generates an entire block of draft tokens (e.g., 8) at once, extremely fast. The problem: it models only the marginal probability at each position—isolated guesses that ignore context. What the 3rd token predicts doesn't depend on what the 1st and 2nd tokens guessed. Like writing a novel by predicting each character independently—accuracy naturally suffers.
Route two: Best-First Tree. The representative method is DDTree. Starting from marginal probabilities, it builds a candidate token tree and expands the most promising branches via best-first search. A tree naturally expresses conditional relations like "if token 1 is A, then token 2 is more likely B." But DDTree has a fatal limitation: its scoring function is factorized—it splits path probability into a product of independent marginal probabilities. Mathematically convenient, but real language doesn't work that way.
Then came Domino. Domino is a drafter that adds a GRU (gated recurrent unit) for causal correction on top of DFlash. Each draft token's distribution becomes path-dependent—the 3rd token's prediction considers what was guessed before. Far more accurate than marginal probabilities.
But Domino is only a linear sequence, with no tree structure. DDTree wants a tree, but its factorized scoring can't use Domino's conditional information.
The advantages of the two routes could not be combined—until now.
DominoTree's Breakthrough
DominoTree's core insight is simple: why not build the tree directly with Domino's conditional scoring?
Specifically, DDTree's scoring function is:
Each position is scored independently, then multiplied. This is factorized scoring.
DominoTree's scoring function is:
Each position's score depends on what was selected before. This is non-factorized scoring.
Mathematically, this is equivalent to applying Domino's conditional correction step by step along the root-to-node path. Intuitively, it's like playing chess by re-evaluating the board after every move, rather than following a precomputed score table.
But there's an engineering challenge: conditional scoring is far more expensive than marginal scoring. If each node's candidate set is the whole vocabulary (usually 50k+), building a depth-8 tree requires 50,000 × 8 conditional scorings—too slow.
DominoTree's solution is Candidate Restriction: each node only conditionally scores the top-M candidates, with M typically 8 or 16. This cuts computation to an acceptable range with almost no quality loss—language model distributions are long-tailed, and tokens outside the top-16 have negligible probability.
A GPU-Native Tree Builder
Algorithms alone aren't enough. The bottleneck in speculative decoding often lies in engineering—especially tree-building overhead.
The traditional approach builds the tree node by node in Python, launching a GPU kernel per node—huge overhead. On a 4B model, a Python builder can consume 30% of end-to-end time.
DominoTree's second contribution is a GPU-native CUDA-graph tree builder. It compiles the entire tree-building process into a CUDA graph executed on the GPU in one shot, with no CPU-GPU synchronization in between. Crucially, this builder's output is bit-identical to the Python reference implementation—it changes no acceptance rates, only reducing build overhead from "non-negligible" to "nearly free."
The design philosophy is worth savoring: engineering optimization should not alter algorithm semantics. Many speculative decoding "speedups" trade acceptance rate for throughput; DominoTree's CUDA builder achieves speedup without changing results.
Experimental Results: Up to 6.6x Speedup
On Qwen3-4B across 8 benchmarks, DominoTree's scorecard:
- Up to 6.6x speedup over autoregressive decoding
- Average accepted length up to 10.7 tokens per round—i.e., each verification round accepts 10.7 tokens on average
- Highest average accepted length among all methods across all temperatures
- Throughput gain over Domino (its base drafter): 9-10% overall, up to +22% on the Alpaca dataset
- Versus DDTree/CaDDTree: wins across the board at T=0 (greedy decoding), with slight losses at high temperature
A notable ablation: the gains come from conditional scoring, not the tree structure itself. Using the same tree with factorized scoring degrades performance to DDTree's level. This shows DominoTree's core value is indeed the introduction of conditional information, not merely "having a tree."
An Analogy: Navigation Route Planning
Imagine using navigation software. Block diffusion (DFlash) is like a navigation system that computes the most likely direction at each intersection independently, ignoring which road you came from—it knows "from A, you most likely go to B," but not "if you just turned from C, from A you'd more likely go to D."
DDTree is better: it builds a route tree, but still scores by "independent per-intersection scores multiplied together"—it knows paths are dependent but can't handle it mathematically.
DominoTree is a true navigation system: at every intersection, it recomputes the best direction based on the actual path traveled. This matches reality, because language generation is inherently path-dependent—the probability of "mat" after "The cat sat on the" is far higher than "quantum," but that judgment only holds if you know the preceding context.
Limitations and an Honest Assessment
The paper candidly acknowledges several limitations:
1. Prototype, not production-grade: DominoTree is currently a research prototype, not integrated into inference frameworks like vLLM or TensorRT-LLM. Real deployment requires engineering adaptation.
2. Adaptive budgeting remains open: how large a tree to build per round, what top-M to set—currently requires manual tuning. The paper tried an adaptive scheme called CondAdaptive, but results were negative—calibration-driven adaptation underperformed fixed budgets.
3. Advantage narrows at high temperature: at T>0, DominoTree's edge over DDTree shrinks, occasionally falling slightly behind. At high temperature, model distributions flatten and the marginal value of conditional information drops.
4. Hardware comparisons are not direct: throughput numbers from the A6000 and RTX 5080 cannot be directly compared due to architectural differences.
The Bigger Picture
DominoTree's story points to a deeper truth: in AI systems, many "engineering bottlenecks" are fundamentally about underutilized information.
DFlash is fast but discards path-dependence. DDTree wanted path information but its mathematical framework wouldn't allow it. Domino had the path information but no tree. DominoTree combines the two—not via a revolutionary new algorithm, but by putting existing information where it belongs.
This recalls an old engineering principle: good optimization isn't about adding more—it's about removing unnecessary constraints. DDTree's factorization assumption is a mathematical simplification, convenient for derivation but limiting in expressiveness. DominoTree removed that assumption, and performance followed.
With LLM inference costs often running into millions of dollars, a 6.6x speedup is no small feat. If you're serving a 4B model, the same hardware can handle 6.6x the requests. And all of this is training-free—no retraining, no extra data, just a change in how the drafter scores candidates.
Sometimes the best innovation is simply seeing the elephant in the room.
---
Paper: https://arxiv.org/abs/2607.08642
Code: https://github.com/slin-zhq/Domino-Tree
Authors: Saw S. Lin (Zhiqi Zhang), Jyh-Shing Roger Jang (Department of Computer Science and Information Engineering, National Taiwan University)
Published: July 9, 2026