A new speculative decoding method, DARTree, enhances the speed of large language models (LLMs) by constructing a fixed-width candidate tree of potential tokens. The technique, detailed in a paper by Tianyi Li, Yaxin Luo, Xinyi Shang, and Zhiqiang Shen, aims to reduce the latency associated with autoregressive generation, where LLMs typically produce one token at a time.
Speculative decoding is an optimization that allows a smaller, faster "draft" model to propose multiple tokens simultaneously. A larger "target" model then verifies these proposals in a single pass, accepting the longest correct prefix. This process maintains the output quality of the larger model while accelerating generation. Existing diffusion-based drafters predict blocks of tokens in parallel, but their position-wise distributions are often marginal, not fully conditioned on tokens already selected along a specific draft path. Previous methods to incorporate causal information have largely focused on single draft chains, or have used diffusion-based tree construction without carrying this correction along individual branches.
DARTree addresses this by extending a pretrained autoregressive (AR) correction head from chains to trees. The method begins by building a fixed-width candidate tree. It expands and scores all nodes at each depth in a single batch, using a pretrained causally corrected block-parallel drafter. This means that all branches at the same depth are evaluated together, and their corrected scores are used to determine which nodes are retained for the next depth, while carrying selected correction states forward.
The core methodology of DARTree involves three stages, as outlined in a review of the paper. First, it performs a depth-wise parallel supertree construction. Starting with the target model's verified prefix, a block-parallel diffusion drafter generates a sequence of token distributions. A pretrained causal correction head then incorporates intra-block causal dependencies. This method decouples the AR-head inference from sequential heap operations, which are typically used for node-by-node pruning. Instead, DARTree applies best-first pruning to select the verification tree after the initial tree construction.
The researchers evaluated DARTree across seven benchmarks covering mathematics, code, and chat tasks. The method achieved the highest average acceptance length and speedup across all four model-temperature configurations tested. DARTree accepted up to 12.97 tokens per verification round, which represents a 98.6% increase over DFlash and a 27.9% increase over Domino in the same settings. These improvements translated to a lossless speedup of up to 9.73 times compared to locally measured autoregressive decoding.
While DARTree offers efficiency gains, it requires a pretrained diffusion drafter that includes a causal correction head. This means it cannot be directly applied to naive diffusion drafters without additional training. Additionally, as a speculative decoding method, DARTree does not reduce the total floating-point operations (FLOPs), which measure total computational work. Instead, it uses additional computation to reduce inference latency. The method also incurs greater computational overhead than non-tree-based methods due to the verification of a large tree of candidate tokens, which may make it less suitable for all deployment environments.
Previous work on speculative decoding, such as DART, also focused on leveraging parallel generation to reduce drafting latency. DART predicted logits for multiple future masked positions in parallel within a single forward pass, eliminating autoregressive rollouts in the draft model. DARTree builds upon these concepts by extending the causal correction mechanism to a tree structure, aiming for broader candidate coverage. Another related method, DDTree, constructs a draft tree directly from the per-position distributions of a block diffusion drafter, aiming to maximize the expected number of accepted tokens.
The development of DARTree contributes to ongoing efforts to make LLM inference faster and more efficient, a critical factor in reducing the cost of generative AI and expanding its adoption.