DominoTree: Conditional Tree-Structured Drafting with Domino for Speculative Decoding
Source: arXiv:2607.08642 · Published 2026-07-09 · By Saw S. Lin, Jyh-Shing Roger Jang
TL;DR
This paper presents DominoTree, a novel training-free speculative decoding method that builds a best-first tree of draft token sequences scored conditionally by Domino's GRU-based correction, extending prior best-first trees (DDTree) which assume factorized per-position marginals. DominoTree scores nodes by re-running Domino's conditional correction along each root-to-node path, capturing the path-dependent token distributions that vanilla DDTree cannot represent. To keep computation tractable, the authors restrict corrections at each node to a top-M candidate slice, and implement a GPU-native CUDA-graph builder to minimize overhead. Evaluation on Qwen3-4B across eight benchmarks shows DominoTree achieves up to 6.6× speedup over autoregressive decoding, consistently higher mean accepted token lengths (up to 10.7 tokens per round), and 9–10% throughput gains over the original Domino decoder. On Qwen3-8B, it retains highest accept length and substantial improvements at low temperature. Attempts to adapt CaDDTree's cost-aware budget adaptation to the conditional tree fail due to miscalibration, leading to a fixed-node budget approach. Overall, DominoTree bridges the gap between block-diffusion marginals and full autoregressive conditional drafting, improving both draft quality and decoding speed through a practical, GPU-optimized conditional tree structure.
Key findings
- DominoTree achieves up to 6.63× speedup over autoregressive decoding on Qwen3-4B across eight datasets at temperature T=0 (Fig 1b).
- It attains the highest mean accept length τ of any evaluated method, up to 10.7 tokens per round on Qwen3-4B (Fig 1a).
- GPU-native CUDA-graph builder reduces per-round tree build time from 3.67ms to 2.31ms for node budget 16 and candidate width M=64 (Table 3).
- Compared to released Domino decoder, DominoTree wins 9–10% overall throughput on Qwen3-4B and 4–6% on Qwen3-8B at various temperatures (Table 2).
- Against DDTree and CaDDTree, DominoTree improves throughput by +7.67% at T=0 and remains better at T=0.5 and T=1.0 with 95% confidence intervals (Table 2).
- Restricting per-node correction to the top-M marginal candidates makes the conditional scoring computationally practical, without affecting tree shape.
- Conditional scoring yields a +9.2% throughput gain over marginal scoring ablation at matched budget and verifier (Section 4.4).
- The proposed CondAdaptive per-round adaptive budget based on CaDDTree fails due to miscalibrated path-probabilities, degenerating to a fixed budget.
Threat model
Speculative decoding accelerates autoregressive LLM inference by using a drafter model to propose candidate token continuations verified by an expensive target model. The 'adversary' is essentially the trade-off between draft cost and draft quality; no external attacker is considered. DominoTree assumes access to the drafter's logits and requires fixed target model weights; it does not defend against malicious input or model manipulation. The method guarantees lossless decoding up to floating-point precision tie-breaking by construction.
Methodology — deep read
The threat model involves accelerating decoding of large language models (LLMs) by using a cheaper drafter to propose multiple token candidates in batches that are verified by the full target model. The adversary is the underlying model controlling drafting and verification, with no explicit attack vector—the focus is on inference speedup without output distribution change.
The core data is the token-level conditional distributions output by Domino, a drafter that adds a GRU-based causal logit correction on top of a block-diffusion backbone (DFlash). This correction makes each draft token's distribution depend on the realized previous tokens in the draft path, producing path-dependent distributions rather than independent marginals per position.
DominoTree implements a best-first heap-based tree construction over candidate token sequences. Unlike DDTree, which scores tree nodes by factorized marginal log-probabilities, DominoTree scores each node using Domino's GRU-corrected conditional logits along the specific root-to-node path. This requires passing and updating the GRU hidden state along each candidate path and applying the correction network per node. To keep this scalable, the algorithm restricts the per-node correction to only the marginal top-M candidate tokens (M=64 in experiments), fetching corresponding rows of the correction matrices and base logits. This restriction reduces the costly full-vocabulary projection into a smaller matrix multiplication.
The tree builder reuses DDTree's best-first algorithm with a max-priority queue keyed by cumulative conditional log-probability, expanding nodes until a fixed node budget (n=16) or max depth is reached. Each expansion computes the conditional children's scores by applying the GRU update and correction to the top-M candidates. The resulting tree is prefix-closed and verified with an unmodified ancestor-only causal attention mask in a single target-model forward pass (borrowed from DDTree/SpecInfer).
Because best-first expansion issues many small kernel launches from Python, a GPU-native CUDA-graph implementation of the per-node correction was developed. This captures the fixed-shape correction computation in a CUDA graph that is replayed for each node, eliminating kernel-launch overhead and maintaining bit-identical results to the Python reference.
They implement CondAdaptive, an adaptive stopping rule transferring CaDDTree's cost-aware budget heuristic to the conditional tree. However, empirical calibration shows Domino's path probabilities over-credit acceptance likelihood causing the adaptive procedure to degenerate to the max node budget regularly. Thus they use a fixed node budget in final results.
Experiments run on Qwen3-4B and Qwen3-8B models paired with released Domino draft checkpoints, spanning eight benchmark datasets covering math, code, and chat tasks. Each prompt generates up to 2048 tokens, evaluating 29–50 prompts per dataset at temperatures T={0, 0.5, 1.0}. They compare against autoregressive decoding, block-diffusion DFlash, DDTree and CaDDTree (factorized tree methods), and the released Domino chain-only drafter.
Key metrics include mean accepted token length per speculative round and overall throughput speedup over autoregressive decoding. Ablations fix the drafter, verifier, and node budget, varying only the tree scoring function to isolate the benefit of conditional scoring. Statistical significance is established via paired bootstrap confidence intervals.
One concrete example is constructing the draft tree with node budget n=16 and candidate width M=64 on Qwen3-4B at T=0. The GPU-native builder precomputes top-M marginal tokens per depth, then expands nodes one by one using Domino's GRU state and correction to score children conditioned on the path. It verifies the longest accepted root-to-leaf path by a single target-model forward pass, accepting up to 10.7 tokens per round with 4.81× speedup over AR.
Overall, the method achieves a practical compromise between full autoregressive conditional decoding and marginal block diffusion drafting by exploiting Domino's partial conditional structure and efficient GPU graph techniques to build better conditional draft trees with scalable inference costs.
Technical innovations
- Introduce a conditional best-first draft tree construction method (DominoTree) that scores nodes using Domino’s GRU-based conditional logit correction along each root-to-node path, rather than factorized marginals.
- Restrict per-node conditional logit correction to only the top-M marginal candidate tokens at each depth to drastically reduce computation and make conditional tree scoring practical.
- Implement a GPU-native CUDA-graph builder for the sequential per-node correction that removes kernel-launch overhead and achieves bit-identical results to the Python reference, enabling fast tree construction.
- Provide controlled ablations isolating conditional scoring benefits (+9.2% throughput over marginal scoring) and show adaptive budget heuristic (CondAdaptive) fails due to miscalibrated path probability estimates.
Datasets
- GSM8K — 50 prompts — publicly available math benchmark
- MATH-500 — 50 prompts — math benchmark
- AIME25 — ~29-30 prompts — math benchmark
- HumanEval — 50 prompts — code generation benchmark
- MBPP — 50 prompts — code generation benchmark
- LiveCodeBench (LCB) — 50 prompts — code benchmark
- MT-Bench — 50 prompts — chat/instruction dataset
- Alpaca — 50 prompts — chat/instruction dataset
Baselines vs proposed
- Autoregressive decoding (AR): baseline speedup = 1.0, DominoTree reach up to 6.63× speedup on Qwen3-4B at T=0.
- DFlash: mean accept length τ = ~7.5, DominoTree: τ = 10.7 tokens per round (Fig 1a).
- DDTree(16) at T=0: throughput baseline; DominoTree improves throughput by +7.67% (95% CI [+5.63, +9.80]).
- CaDDTree: adaptive budget method; CondAdaptive adaptation fails and yields no gain over fixed budget DominoTree.
- Released Domino decoder baseline: DominoTree achieves 9–10% overall throughput improvement on Qwen3-4B, up to +22% on Alpaca.
- On Qwen3-8B at T=0, DominoTree achieves +24% throughput improvement over DDTree.
Limitations
- The adaptive budget heuristic CondAdaptive, inspired by CaDDTree, fails due to miscalibrated path log-probabilities overestimating acceptance likelihood, leading to fixed budget usage.
- Candidate restriction to top-M tokens prunes candidate space, potentially excluding some valid candidates outside the top-M marginal slice.
- Tree construction is sequential best-first expansion, limiting parallelism and requiring careful CUDA-graph batching to mitigate kernel-launch overhead.
- Evaluations are limited to English benchmarks and released checkpoints Qwen3-4B and Qwen3-8B; no cross-lingual or substantially larger models tested.
- No explicit adversarial or distribution-shift robustness evaluation of the drafts or verification procedure.
- Verification method (tree-attention verification) is reused from prior works without additional improvements or analysis specific to DominoTree.
Open questions / follow-ons
- Can the conditional tree scoring approach scale efficiently to larger node budgets or wider candidate sets beyond top-M restriction without losing throughput?
- How to improve path probability calibration to enable effective adaptive budget heuristics like CondAdaptive in conditional draft trees?
- What are the impacts of conditional scoring on draft quality and throughput in more diverse multilingual or multimodal LLM benchmarks?
- Can the GPU-native tree builder design be further optimized to reduce sequential bottlenecks inherent in best-first expansion?
Why it matters for bot defense
DominoTree's method of building conditional draft trees that incorporate path-dependent token distributions presents a meaningful advance for speculative decoding approaches used in large-scale language model inference acceleration. For practitioners working on bot defense or CAPTCHA systems leveraging LLMs, these techniques could enable faster, high-throughput generation of challenge-response content where token sequence quality and validity are critical. By conditioning proposed drafts on realized prior tokens, DominoTree reduces errors from naive marginal sampling, thus potentially producing more coherent, valid outputs usable for CAPTCHAs or interactive bot-defense mechanisms.
Implementing a GPU-native builder to reduce overhead demonstrates practical feasibility for low-latency settings. However, practitioners should note the trade-offs on candidate pruning and the lack of an adaptive stopping rule due to calibration challenges, which might impact dynamic workload environments. The principle of combining conditional corrections with block-level parallelism may inspire more robust speculative decoding schemes for real-time bot interaction systems requiring both speed and output integrity.
Cite
@article{arxiv2607_08642,
title={ DominoTree: Conditional Tree-Structured Drafting with Domino for Speculative Decoding },
author={ Saw S. Lin and Jyh-Shing Roger Jang },
journal={arXiv preprint arXiv:2607.08642},
year={ 2026 },
url={https://arxiv.org/abs/2607.08642}
}