D3Tree speeds up verifying draft token blocks during heavy loads
D3Tree: Learning to Prune Block-Diffusion Draft Trees for Efficient Verification
Machine LearningArtificial Intelligence
Summary
Verifying parts of generated text or images can be slow, especially when many requests come in at once. The authors developed D3Tree, which learns to pick only the most promising pieces from a block of suggestions to verify, adapting automatically to how busy the system is. This method makes the process much faster without losing quality, working well across many types of tasks. It helps speed up generating text and images especially when multiple users request outputs simultaneously.
What this means in practice
- •For ai system engineers: Accelerate verification in models generating multiple tokens at once to improve response times under heavy user loads.
- •For multimodal app developers: Integrate faster verification for vision-language and text generation features by pruning draft token proposals efficiently.
Authors
Hong Nie, Zhangchi Gao, Jun Yu, Bo Wang, Jianqing Sun, Shengping Liu
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.