D3Tree: Learning to Prune Block-Diffusion Draft Trees for Efficient Verification

Hong Nie, Zhangchi Gao, Jun Yu, Bo Wang, Jianqing Sun, Shengping LiuarXiv 2026 · arXiv

TL;DR

D3Tree is a novel speculative decoding framework that uses a tiny learned "tree-size head" to dynamically prune draft trees based on predicted token acceptance and real-time serving load. By aligning verification batches with GPU hardware tiles and prioritizing high-probability branches across the entire request batch, it achieves up to 4x speedup for single requests and maintains significant gains even under heavy concurrent loads where traditional methods fail.

What Problem Does This Paper Address?

Large Language Model (LLM) inference is notoriously bottlenecked by memory bandwidth—every token generated requires a full pass over the model's massive weights. Speculative decoding mitigates this by using a small, fast "drafter" model to propose several tokens, which the large "target" model then verifies in a single parallel pass.

Modern "block-diffusion" drafters can propose entire blocks of tokens at once, often organized into draft trees to explore multiple possible continuations. However, these trees come with a hidden cost: every node in the tree occupies a query row in the target model's verification pass. When a server is busy with many concurrent requests, these extra rows compete for limited GPU capacity. Existing methods typically use fixed budgets or offline profiles that don't adapt to current traffic, often wasting compute on low-probability branches that are likely to be rejected.

Fig. 1. Verification selection in closely related methods. (a) Each method on one candidate space; numbers give the best-first order by draft path score, and W counts target query rows, including the root. Chips mark the selection signal. (b) CaDDTree and D3Tree under light load (one request) and heavy load (R = 4 requests in one target pass whose matrix multiplications process tiles of s = 16 rows); below the trees, each step’s query rows fill the tiles (dashed: idle; red: a second tile). CaDDTree sizes each tree from a latency table profiled offline for a single request, regardless of the current load, so here it verifies B∗= 4 nodes per request at either load: rows stay idle under light load and spill into a second tile under heavy load. D3Tree sets the size from the current load: the whole tree when the tile has room, and otherwise the 12 nodes of highest survival across the batch, which fill one tile.

Methods

The authors introduce Block Diffusion Dynamic Draft Trees (D3Tree), which treats tree pruning as a learned optimization problem.

  1. Tree-Size Head: A lightweight module (adding only $2H+2$ parameters) is trained to predict the "conditional survival" probability of each candidate token—essentially, the likelihood that the target model will accept this token given that its parent was accepted.
  2. Survival Pruning: Instead of just looking at the drafter's own confidence, D3Tree calculates the cumulative survival probability along every path in the draft tree. It then prunes the tree by thresholding these scores. This allows the system to keep deep, confident branches while cutting shallow, uncertain ones.
  3. Load-Dependent Allocation: This is the "secret sauce." D3Tree doesn't just prune for one request; it looks at the entire batch. Under light load, it verifies full trees. Under heavy load, it allocates a global node budget across all requests, selecting the top-$N$ nodes with the highest survival scores batch-wide.
  4. Hardware Alignment: The total number of query rows is specifically sized to match the GPU's matrix-multiplication "tiles" (e.g., multiples of 64). This ensures that the target model's compute units are fully utilized without spilling into a slower, partially-filled second tile.
The survival pruning process: nodes are kept if their path survival score $S(v)$ exceeds a threshold $\delta$.

Datasets

The researchers evaluated D3Tree across a massive suite of 17 benchmarks covering text and multimodal tasks:

  • Text Benchmarks: GSM8K, MATH-500, AIME25 (Math); HumanEval, MBPP, LiveCodeBench (Code); MT-Bench (Chat).
  • Multimodal Benchmarks: OmniDocBench, OCRBench-v2, DocVQA, olmOCR, CharXiv (Document/OCR); TVQA, MMMU-Pro, GQA (General Vision); COCO Caption, MM-MT-Bench (Caption/Chat).

The models were trained on 1 million prompts with responses generated by the corresponding target verifiers to provide ground-truth labels for the survival head.

Key Insights and Ideas

  • Global vs. Local Pruning: The value of a draft token isn't absolute; it depends on what else is in the batch. By pruning globally, D3Tree ensures that compute is spent on the most promising tokens across all active users.
  • Learned Survival is Superior: The drafter's own internal probabilities are often poor indicators of whether the target model will actually agree. Training a dedicated head on target-model feedback provides a much more reliable signal for pruning.
  • GPU-Native Execution: To avoid the "host-to-device" latency bottleneck, tree construction, scoring, and pruning are implemented as fused GPU kernels that overlap with other CPU-side serving logic.
  • Beyond Depth Cuts: Traditional methods often just cut the tree at a certain depth. D3Tree's survival-based approach can maintain a single, very long, high-confidence chain while pruning away multiple short, low-confidence branches.

Key Results

D3Tree emerged as the fastest strategy in 70 out of 72 tested load settings across six different vision-language model families (Qwen3.5, InternVL3.5, and Gemma 4).

  • Single Request Speedup: Achieved 3.2–4.0× speedup over standard autoregressive decoding.
  • High Concurrency Performance: At 64 concurrent requests, it maintained a 1.3–1.8× speedup. In contrast, traditional fixed-budget tree methods often performed worse than standard decoding (0.26–0.84×) at this load because their massive trees overwhelmed the GPU.
  • Efficiency: It consistently outperformed CaDDTree (the previous state-of-the-art for cost-aware trees) by at least 1.15× at every load level.
  • Real-world Serving: In tests using time-varying arrival traces (simulating real web traffic), D3Tree maintained the lowest mean end-to-end latency across all phases of the trace.

Limitations and Future Work

While highly effective, the authors noted a few areas for improvement:

  • Hardware-Specific Overhead: On certain GPUs (like the NVIDIA A800) using hybrid models with recurrent states, the overhead of managing tree attention can be high enough that simple linear chains occasionally outperform trees under extreme load.
  • Greedy Only: The current implementation focuses on greedy decoding. Extending this learned pruning to stochastic sampling (where multiple tokens might be valid) is a logical next step.
  • Scaling Joint Training: While they proposed an optional joint training mode to improve the drafter, they suggest that evaluating this at a larger scale remains future work.

Summary updated

Abstract

Block-diffusion drafters propose a whole block of tokens in one forward pass, and draft trees built from their position-wise marginals increase the expected accepted length of speculative decoding. Every tree node occupies a query row in target verification, so under concurrent serving low-yield branches compete with other requests for verification capacity. Existing tree methods select verified nodes by draft probability under a fixed or cost-selected per-request budget, and thus always retain a prefix of the drafter's ranking. We present D3Tree, which learns which nodes of a block-diffusion draft tree are worth verifying. A tree-size head with 2H+2 parameters predicts each candidate's conditional survival from the draft state, the candidate embedding, and its draft log-probability. Thresholding the product of these scores along parent chains yields an ancestor-closed subtree whose size adapts to each request and decoding round. The head is trained on a frozen drafter with conditional labels on the full candidate tree; an optional joint mode also steers the drafter toward the retained reference path. At serving time, D3Tree verifies whole trees under light load and, under heavy load, allocates one batch-wide node budget by predicted survival, sized to the target's matrix-multiplication tiles. Retained trees share one ancestor-masked target pass, while construction, pruning, and scheduling run on the GPU and overlap with the host. Across six vision-language verifiers and 17 text and multimodal benchmarks, D3Tree is fastest in 70 of 72 load settings, with 3.2-4.0x speedup over autoregressive decoding for one request and 1.3-1.8x at 64 concurrent requests, where fixed-budget trees fall below autoregressive speed. Under a time-varying arrival trace, it has the lowest mean end-to-end latency in every arrival phase.
BibTeX
@misc{nie2026d,
  author = {Hong Nie and Zhangchi Gao and Jun Yu and Bo Wang and Jianqing Sun and Shengping Liu},
  title = {{D3Tree: Learning to Prune Block-Diffusion Draft Trees for Efficient Verification}},
  year = {2026},
  eprint = {2611.11371},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11371},
}
Figure