DominoTree: Growing a Tree for Speculative Decoding with Conditional Drafting

Forum topic · ✨步子哥 · 2026-07-11

Summary

DominoTree is a speculative decoding method for large language models proposed by Saw S. Lin and Jyh-Shing Roger Jang of National Taiwan University (arXiv, July 2026). It combines the conditional, path-dependent scoring of the Domino drafter (a GRU-corrected drafter) with tree-structured drafting, replacing the factorized marginal-probability scoring used by DDTree with conditional scoring P(token | path so far). To keep conditional scoring tractable, it restricts each node's evaluation to top-M candidates. It also ships a GPU-native CUDA-graph tree builder that is bit-identical to the Python reference, eliminating build overhead without changing accept rates. On Qwen3-4B across 8 benchmarks, DominoTree achieves up to 6.6x speedup over autoregressive decoding and a peak average accepted length of 10.7 tokens per round; on Qwen3-8B it gains +24% throughput over DDTree at T=0. Ablations show gains come from conditional scoring rather than tree construction itself. The method is training-free but remains a research prototype not yet integrated into vLLM or TensorRT-LLM, with advantages narrowing at high temperatures.

DominoTree: Letting Speculative Decoding Grow Its Own Draft Tree

An Old Problem

When you chat with ChatGPT, it produces text one token at a time—roughly 30ms per token, so a 1,000-word reply takes half a minute. Behind this is the autoregressive decoding of large language models (LLMs): every generated token requires a full forward pass, even if you just want to add one more word.

Could the model guess several tokens at once 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 ones fall 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? These answers determine the ceiling 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, DominoTree: Conditional Tree-Structured Drafting with Domino for Speculative Decoding, offering an elegant answer: let the dominoes grow into a tree by themselves.

The Dilemma of Two Approaches

To understand DominoTree's contribution, look at the two prior technical routes.

Route 1: Block Diffusion. The representative method is DFlash. It generates an entire block of draft tokens (say, 8) at once—very fast. But it only models marginal probabilities for each position: isolated guesses that ignore context. What the 3rd token predicts doesn't consider what the 1st and 2nd guessed. Like writing a novel predicting each character independently—accuracy naturally suffers.

Route 2: Best-First Tree. The representative method is DDTree. Starting from marginal probabilities, it builds a candidate token tree, expanding the most promising branches via best-first search. Trees 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 decomposes 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 came before. Far more accurate than marginal probabilities.

But Domino is only a linear sequence, no tree structure. DDTree wants a tree, but its factorized scoring can't use Domino's conditional information.

The advantages of both routes could not be combined.

DominoTree's Breakthrough

DominoTree's core insight is simple: why not build the tree using Domino's conditional scores directly?

DDTree's scoring function:

\text{score}(\text{path}) = \prod_{i} P_{\text{marginal}}(\text{token}_i)

Each position scored independently, then multiplied—factorized.

DominoTree's scoring function:

\text{score}(\text{path}) = \prod_{i} P_{\text{conditional}}(\text{token}_i \mid \text{path so far})

Each position's score depends on what was chosen before—non-factorized.

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 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 means 50k × 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 top-16 have negligible probability.

A GPU-Native Tree Builder

The algorithm alone isn't enough. The bottleneck of 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—huge overhead. On a 4B model, the 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 construction into one CUDA graph executed on the GPU in one shot, with no CPU-GPU synchronization in between. Crucially, its output is bit-identical to the Python reference implementation—it doesn't change any accept rate, just 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 "speedups" trade accept rates for speed; 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/round—each verification round accepts 10.7 tokens on average
Highest average accepted length across all temperatures
Throughput vs. Domino (its base drafter): 9-10% overall, up to +22% on the Alpaca dataset
Vs. DDTree/CaDDTree: fully wins at T=0 (greedy decoding), slight losses at high temperatures

On Qwen3-8B, DominoTree keeps the highest accepted length, with +24% throughput over DDTree at T=0.

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. This confirms DominoTree's core value is truly the introduction of conditional information, not "having one more tree."

An Analogy: Navigation Software

Imagine using navigation software. Block diffusion (DFlash) is like a system computing the most likely direction at each intersection independently of where you've been—it knows "from A, B is most likely" but not "if you just turned from C, D is more likely from A."

DDTree is better: it builds a path tree, but still scores by "each intersection independently, multiplied together"—it knows paths are dependent but can't handle it mathematically.

DominoTree is a real navigation system: at every intersection, it recomputes the optimal direction based on the actual path traveled. 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 words.

Limitations and Honest Assessment

The paper candidly 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 needs engineering adaptation.

2. Adaptive budget remains open: tree size per round and top-M require manual tuning. The paper tried an adaptive scheme called CondAdaptive, but the result was negative—calibration-driven adaptation underperformed a fixed budget.

3. Advantage narrows at high temperature: at T>0, DominoTree's edge over DDTree shrinks and can even slightly lag. At high temperature distributions flatten, reducing the marginal value of conditional information.

4. Hardware comparisons aren't direct: A6000 and RTX 5080 throughput numbers aren't directly comparable due to architectural differences.

The Bigger Picture

DominoTree's story points to a deeper truth: in AI systems, many "engineering bottlenecks" are really "underutilized information."

DFlash is fast but discards path-dependence. DDTree wants path information but its math forbids it. Domino has path information but no tree. DominoTree combines them—not through some groundbreaking new algorithm, but by "using existing information in the right place."

This recalls an old engineering principle: good optimization doesn't add more; it removes unnecessary restrictions. DDTree's factorization assumption was a mathematical simplification—convenient but limiting. DominoTree dropped the assumption, and performance rose.

With LLM inference costs running into millions of dollars, a 6.6x speedup is no small matter. If you're serving a 4B model, the same hardware can serve 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 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