DominoTree: Growing a Tree for Speculative Decoding with Conditional Domino Drafting
An Old Problem
When you chat with ChatGPT, it outputs text one token at a time. Each token takes roughly 30 ms, so a 1,000-character reply means waiting half a minute. The culprit is the autoregressive decoding of large language models (LLMs) — generating every token requires a full forward pass of the entire model, even if all you want is one more filler word.
Can the model guess several tokens ahead and verify them in batch? That is the core idea of Speculative Decoding: a lightweight "drafter" quickly generates candidate tokens, and the large model verifies them in parallel. Correct guesses yield extra tokens for free; wrong guesses roll back to the correct position.
Sounds great, but the devil is in the details. How does the drafter guess? How many tokens? How are candidates organized? The answers directly cap the achievable speedup.
In July 2026, researchers from National Taiwan University — Saw S. Lin (Zhiqi Zhang) and Jyh-Shing Roger Jang — 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 technical routes that preceded it.
Route 1: Block Diffusion. The representative method is DFlash. It generates an entire block of draft tokens at once (say, 8 tokens), which is extremely fast. The problem: it models only marginal probabilities for each position — isolated guesses without context. What the 3rd token predicts ignores what the 1st and 2nd tokens guessed. It's like writing a novel by predicting each character independently, never looking at what came before — accuracy naturally suffers.
Route 2: Best-First Tree. The representative method is DDTree. Starting from marginal probabilities, it builds a candidate token tree and expands the most promising branches with best-first search. A tree can naturally express conditional relations like "if token 1 is A, token 2 is more likely B." But DDTree has a fatal limitation: its scoring function is factorized — it splits path probability into independent marginal probabilities multiplied together. 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, not a tree. DDTree wants a tree, but its factorized scoring can't use Domino's conditional information.
The advantages of the two routes cannot be combined. Until now.
DominoTree's Breakthrough
DominoTree's core insight is simple: why not build the tree using Domino's conditional scoring directly?
DDTree's scoring function:
Each position scored independently, then multiplied — factorized.
DominoTree's scoring function:
Each position's score depends on what was chosen before — non-factorized. Mathematically, this means applying Domino's conditional corrections one by one along the root-to-node path. Intuitively, it's like playing chess by re-evaluating the position after every move, rather than following a pre-computed 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 evaluations — too slow.
DominoTree's solution is Candidate Restriction: each node performs conditional scoring only on 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 heavy-tailed, and tokens beyond top-16 have negligible probability.
A GPU-Native Tree Builder
The algorithm alone isn't enough. The bottleneck in speculative decoding often lies in engineering — especially tree construction overhead.
The traditional approach builds the tree node by node in Python, launching a GPU kernel per node, with 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. The entire tree construction is compiled into a CUDA graph executed in one shot on the GPU, with no CPU-GPU synchronization in between. Crucially, its output is bit-identical to the Python reference implementation — it changes no acceptance rates, it merely reduces construction overhead from "non-negligible" to "nearly free."
This design philosophy is worth savoring: engineering optimization should not change algorithm semantics. Many speculative decoding "accelerations" trade away acceptance rates; DominoTree's CUDA builder achieves speed without changing results.
Results: Up to 6.6x Speedup
On Qwen3-4B across 8 benchmarks, DominoTree's report card:
- Up to 6.6x speedup over autoregressive decoding
- Average accepted length up to 10.7 tokens per round — each verification round accepts 10.7 tokens on average
- Highest average accepted length of all methods at every temperature
- Throughput improvement over Domino (its underlying drafter): 9-10% overall, up to +22% on Alpaca
- Versus DDTree/CaDDTree: wins across the board at T=0 (greedy decoding), slightly behind at high temperatures
A notable ablation: the gains come from conditional scoring, not the tree itself. Using the same tree structure with factorized scoring drops performance to DDTree's level. This confirms DominoTree's core value is the introduction of conditional information, not "having a tree."
An Analogy: Navigation Path Planning
Imagine using a navigation app. Block diffusion (DFlash) is like a navigation system that independently computes the most likely direction at each intersection regardless of the route you took — it knows "from A, most likely to B," but not "if you just turned from C, then from A it's more likely D."
DDTree is better: it builds a route tree, but still scores by "independently rating each intersection and multiplying" — it knows paths depend on each other but can't handle it mathematically.
DominoTree is like a true navigation system: at every intersection it recomputes the optimal direction based on the path you actually took. This matches reality, because language generation is inherently path-dependent — "The cat sat on the" is far more likely followed by "mat" than "quantum," but that judgment only holds if you know the preceding text.
Limitations and an Honest Assessment
The paper frankly acknowledges several limitations:
1. Prototype, not production-grade: DominoTree is a research prototype, not yet integrated into inference frameworks like vLLM or TensorRT-LLM. Deployment requires engineering adaptation.
2. Adaptive budgeting remains open: how large a tree to build per round, and what top-M to set, currently require manual tuning. The paper tried an adaptive scheme called CondAdaptive, with negative results — calibration-driven adaptivity underperformed a fixed budget.
3. Advantage narrows at high temperatures: at T>0, DominoTree's edge over DDTree shrinks, and it can even fall slightly behind. At high temperature the distribution flattens, reducing the marginal value of conditional information.
4. Hardware comparisons not direct: A6000 and RTX 5080 throughput figures 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 at heart "underutilized information."
DFlash is fast but discards path-dependence information. DDTree wants to use path information but its math forbids it. Domino has the path information but no tree structure. DominoTree combines them — not via some revolutionary new algorithm, but by "putting existing information in the right place."
This recalls an old engineering principle: good optimization isn't about adding more, but removing unnecessary constraints. DDTree's factorization assumption is a mathematical simplification — convenient to derive, but limiting in expressiveness. DominoTree removed the assumption, and performance followed.
With LLM inference costs running into millions of dollars, a 6.6x speedup is no small thing. If you're serving a 4B model, the same hardware can handle 6.6x the requests. And it's all training-free — no retraining, no extra data, just a different way of scoring the drafter.
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