Technical Summary: DominoTree

Problem Statement

Speculative decoding accelerates Large Language Model (LLM) inference by drafting candidate tokens and verifying them in parallel. However, existing methods face a fundamental efficiency trade-off between draft quality (acceptance length, $\tau$) and draft cost (sequential forward passes).

• Autoregressive drafters (e.g., EAGLE) condition every token on previous ones, ensuring high quality but incurring strictly sequential costs that scale with draft length.
• Block-diffusion drafters (e.g., DFlash) generate an entire block in one parallel pass but model only per-position marginals. They ignore the causal dependency between tokens within the block, capping the maximum achievable acceptance length.
• Domino bridges this gap by adding a lightweight, sequential GRU-based correction to DFlash's parallel backbone. This makes the draft distribution path-dependent (conditional on realized tokens) without re-running the expensive backbone. However, the released Domino implementation is chain-only; it walks a single path and does not support branching.
• Tree-based methods (e.g., DDTree, CaDDTree) verify multiple candidates in parallel to increase $\tau$, but they rely on factorized formulations where a token's score depends only on its position, not the path taken to reach it. This assumption holds for DFlash but is structurally false for Domino's GRU-corrected logits. No existing method constructs a tree that exploits Domino's conditional structure without discarding the correction or reverting to a single chain.

Methodology

The paper introduces DominoTree, a training-free method that constructs a best-first draft tree on top of the released Domino checkpoint. It scores nodes using Domino's conditional (non-factorized) correction along each root-to-node path.

Core Components

1. Conditional-Scored Best-First Heap:

   • The algorithm uses DDTree's best-first heap mechanism (max-priority queue keyed by cumulative path log-probability).
   • Key Innovation: Instead of using path-independent marginals ($L^{base}_i$), the heap scores children by re-running Domino's GRU correction ($\Delta L_i$) for the specific path leading to the current node.
   • Structural Fact: The expensive backbone hidden states ($H_i$) are shared and path-independent. Only the cheap GRU correction and the correction head need to be recomputed per node. This makes conditional tree construction computationally feasible.

2. Candidate Restriction (Top-M):

   • Re-running the full-vocabulary projection ($W_2$) for every node in a best-first expansion is too costly.
   • Optimization: The method restricts the correction to the Top-M marginal candidates at each depth. The correction is applied only to this slice ($256 \times M$) before selecting the Top-k children. This reduces FLOPs significantly without altering the tree's expansion order or depth.

3. GPU-Native Builder (CUDA-Graph):

   • Best-first expansion is inherently sequential (one node popped at a time), creating high Python-to-CUDA kernel launch overhead.
   • Solution: The per-node correction logic is captured as a CUDA graph. While the Python heap still manages the control flow (deciding which node to pop next), the actual correction computation for each node is executed via graph replay.
   • Result: This reduces per-round tree construction time significantly (e.g., from 3.67 ms to 2.31 ms on Qwen3-4B) while remaining bit-identical to a Python reference implementation.

4. CondAdaptive (Negative Result):

   • The paper attempts to adapt CaDDTree's cost-aware adaptive budget (which stops growing the tree when throughput gains diminish) to the conditional setting.
   • Finding: The GRU-corrected path probabilities are over-credited as estimates of target acceptance. This causes the adaptive rule to saturate at its maximum budget cap on nearly every round, offering no gain over a fixed budget. Consequently, DominoTree uses a fixed node budget.

5. Verification:

   • Uses standard tree-attention verification (ancestor-only causal mask) borrowed from DDTree/SpecInfer, which remains unmodified and lossless.

Key Contributions

• DominoTree Algorithm: A training-free tree construction method that scores nodes using Domino's path-dependent conditional logits. It achieves the highest mean accepted length ($\tau$) among evaluated methods at every tested temperature.
• GPU-Native Implementation: A CUDA-graph builder that makes conditional tree construction cheap enough to convert the acceptance-length advantage into a throughput advantage. It is verified to be bit-identical to a Python reference.
• Ablation of Conditioning: By comparing conditional scoring against marginal scoring (holding the drafter and tree structure fixed), the paper isolates that the throughput gain (+9.2% overall) comes specifically from conditioning on the realized path, not merely from having a tree structure.
• CondAdaptive Analysis: A rigorous negative result demonstrating that cost-aware adaptive budgeting fails in this non-factorized setting due to miscalibration of path probabilities, justifying the use of a fixed budget.

Experimental Results

Evaluated on Qwen3-4B and Qwen3-8B across eight benchmarks (Math, Code, Chat) at temperatures $T \in \{0.0, 0.5, 1.0\}$.

• Acceptance Length: DominoTree achieves the highest mean accepted length ($\tau$) of any evaluated method (DFlash, DDTree, CaDDTree, Domino) at every temperature. On Qwen3-4B at $T=0$, it reaches up to 10.7 tokens per round (vs. 7.98 for Domino chain).
• Throughput (Speedup over AR):
  • vs. Domino: DominoTree outperforms the released Domino decoder (running at its own best CUDA-graph configuration) at every temperature. Gains are 9–10% on Qwen3-4B and 4–6% on Qwen3-8B.
  • vs. DDTree/CaDDTree: DominoTree shows statistically significant throughput improvements over DDTree/CaDDTree at $T=0$ and $T=0.5$ (e.g., +24% on Qwen3-8B at $T=0$). At higher temperatures ($T=1.0$), the edge narrows to a tie or slight loss on some datasets, but aggregate wins persist.
  • Code Workloads: The method generally trails DDTree/CaDDTree on code-specific benchmarks (LiveCodeBench, MBPP), where marginal trees perform competitively.
• Losslessness: The method is lossless (up to floating-point tie-breaking), matching the token-serial greedy decoding distribution.

Significance and Claims

The paper claims that DominoTree successfully bridges the gap between the efficiency of block-diffusion drafting and the quality of autoregressive conditioning without requiring retraining.

• Structural Insight: It demonstrates that a "partial-conditional" drafter (Domino) can support a full tree structure because the expensive backbone is shared, and only the cheap correction needs to be path-dependent.
• Practical Impact: By combining a conditional scoring function with a GPU-native builder, DominoTree achieves the highest throughput among speculative decoding methods on the tested models, particularly in chat and math tasks.
• Modesty: The authors explicitly note that their method is a "prototype" running on a single-stream research harness, not a production serving system (e.g., vLLM). They also acknowledge that their adaptive budgeting attempt failed, leaving that as an open problem for future work. The distinction from training-based methods like JetSpec is emphasized: DominoTree is training-free, reusing existing weights, whereas JetSpec requires training a new causal head.