DominoTree: Growing a Tree for Speculative Decoding with Conditional Drafting
An Old Problem
When you chat with an LLM, tokens stream out one by one — roughly 30 ms each, meaning a 1,000-character reply takes about half a minute. This is autoregressive decoding: every generated token requires a full forward pass of the model, even just to append a filler word.
Can the model guess several tokens at once and verify them in batch? That's the core idea of speculative decoding: a lightweight drafter quickly generates candidate tokens, and the large model verifies them in parallel. Correct guesses yield free tokens; wrong ones trigger a rollback.
Sounds great, but the details matter. How does the drafter guess? How many tokens? How are candidates organized? These answers set the ceiling on the speedup.
In July 2026, researchers Saw S. Lin (Zhiqi Zhang) and Jyh-Shing Roger Jang from National Taiwan University published DominoTree: Conditional Tree-Structured Drafting with Domino for Speculative Decoding on arXiv, offering an elegant answer: let the dominoes grow a tree by themselves.
The Dilemma of Two Approaches
Route 1: Block Diffusion (e.g., DFlash). It generates an entire block of draft tokens at once (e.g., 8), which is extremely fast. The problem: it models only marginal probabilities per position — isolated guesses that ignore context. Token 3 is predicted without regard to tokens 1 and 2, so accuracy suffers.
Route 2: Best-First Tree (e.g., DDTree). It builds a candidate tree from marginal probabilities, expanding promising branches via best-first search. Trees naturally express conditional relationships ("if token 1 is A, token 2 is more likely B"). But DDTree's scoring function is factorized: path probability is a product of independent marginal probabilities — mathematically convenient, but not how language works.
Then came Domino, a drafter that adds a GRU for causal correction on top of DFlash-style drafting. Each draft token's distribution becomes path-dependent — far more accurate than marginal probabilities. But Domino is a linear sequence with no tree structure, and DDTree's factorized scoring cannot use Domino's conditional information.
The advantages of both routes could not be combined — until now.
DominoTree's Breakthrough
The core insight is simple: why not use Domino's conditional scoring to build the tree directly?
DDTree's score:
DominoTree's score:
Each position is scored conditioned on previous choices — non-factorized scoring, like re-evaluating the board after every chess move rather than following a precomputed table.
Candidate Restriction: Since conditional scoring is expensive, each node only scores the top-M candidates (M typically 8 or 16). This cuts computation to an acceptable range with almost no quality loss, since LLM distributions are long-tailed.
A GPU-Native Tree Builder
DominoTree's second contribution is a GPU-native CUDA-graph tree builder. The entire tree construction is compiled into a CUDA graph executed on GPU without CPU-GPU sync. Its output is bit-identical to the Python reference implementation — it doesn't change any acceptance rate, it just makes construction overhead nearly free.
The design philosophy: engineering optimization should not change algorithmic semantics.
Results: Up to 6.6x Speedup
On Qwen3-4B across 8 benchmarks:
- Up to 6.6x speedup over autoregressive decoding
- Average accepted length up to 10.7 tokens/round — the highest among all methods at all temperatures
- Throughput vs. Domino (its base drafter): 9-10% overall, up to +22% on Alpaca
- vs. DDTree/CaDDTree: wins comprehensively at T=0 (greedy decoding), slightly behind at high temperatures
A notable ablation: the gains come from conditional scoring, not tree construction itself. Using the same tree structure with factorized scoring drops performance to DDTree's level.
A Navigation Analogy
Block diffusion is like a navigation system that independently computes the most likely direction at each intersection, ignoring your route so far. DDTree builds a path tree but still scores each intersection independently. DominoTree is a true navigation system: at every junction, it recalculates the best direction based on the actual path taken — because language generation is inherently path-dependent ("The cat sat on the" makes "mat" far more likely than "quantum", but only if you know the context).
Honest Limitations
1. Research prototype, not production system: not yet integrated into vLLM, TensorRT-LLM, etc. 2. Adaptive budget remains open: tree size and top-M need manual tuning; the paper's CondAdaptive calibration-driven scheme underperformed fixed budgets. 3. Advantage narrows at high temperature: flatter distributions reduce the marginal value of conditional information. 4. Hardware comparisons not direct: A6000 vs. RTX 5080 numbers aren't comparable due to architecture differences.
The Bigger Picture
DominoTree's story points to a deeper truth: many "engineering bottlenecks" in AI systems are really about underutilized information. DFlash is fast but discards path-dependence. DDTree wants path information but its math doesn't allow it. Domino has path information but no tree. DominoTree combines them not with a revolutionary new algorithm, but by using existing information in the right place — removing an unnecessary simplifying assumption rather than adding complexity.
With 6.6x speedup being training-free (no retraining, no extra data), the same hardware can serve 6.6x the request volume for a 4B model.
---
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