AI research wiki
inference-efficiency · 2026-05-20 · Tier 1

Graft: Hybrid Tree Construction for Speculative Decoding (Draft Less, Retrieve More)

Graft: Hybrid Tree Construction for Speculative Decoding (Draft Less, Retrieve More)

Source: HuggingFace Daily Papers 2026-05-20 · arXiv 2605.20104 · raw

TL;DR

Speculative decoding accelerates LLM inference through a draft-then-verify pipeline. To raise the acceptance rate, recent methods build expansive draft trees, but these incur VRAM bandwidth and computational overheads that cap end-to-end speedup. Dynamic-depth pruning reduces latency by removing marginal branches but also discards potentially valid candidates, so the pruned-tree acceptance rate falls below the dense-tree ceiling. Graft identifies an opportunity in the resource freed by pruning: that freed budget can fund a retrieval step. Graft is a compensation framework that couples pruning and retrieval as mutually reinforcing operations. Pruning supplies budget for retrieval; retrieval compensates for pruning-induced coverage loss and recovers accepted length. With a sequential prune-then-graft mechanism, Graft attaches highly predictive retrieved tokens into positions opened by pruning, filling the topological gaps with near-zero overhead. The method is training-free and lossless. Comprehensive evaluation establishes a new Pareto frontier across short-context, long-context, and large-scale settings. On short-context benchmarks, up to 5.41x speedup. Average speedup over EAGLE-3 improves by up to 21.8% on the large-scale Qwen3-235B. A preliminary application to DFlash-style block drafting suggests grafting extends beyond autoregressive draft trees.

Why it matters

Speculative decoding has been the dominant production acceleration since 2024. The acceptance-rate-versus-overhead Pareto has been pushed hard by EAGLE-3 and successors. Graft identifies a new exchange rate: prune to free budget, then spend the freed budget on retrieval-grafted tokens. The retrieved tokens are not generated by the draft model; they come from a retrieval index, which means they are not constrained by the draft model's distribution. That decoupling is the key conceptual move. Combined with the Pareto frontier shifts reported, this is the most substantive speculative-decoding paper in the wiki since the NVIDIA NeMo-RL integration (2026-04-30, the EAGLE-3 / MTP integration into RL training loops).

Mechanism

Three steps. (1) Build a dense draft tree as usual. (2) Prune with a dynamic-depth policy, freeing compute budget but discarding potentially valid candidates and creating topological gaps in the tree. (3) Graft retrieved tokens into those gaps, where the retrieval source is a token-level index keyed on the prefix context. The grafted tokens are verified against the target policy the same way drafted tokens are. Because retrieval is much cheaper than additional draft generation, the retrieval-grafted tokens cost near zero, and the verifier still rejects anything wrong.

Open questions and gaps

The retrieval index design is the load-bearing component. The abstract does not describe how the index is built, how it scales, or whether it works on cold corpora versus warm ones. The 5.41x is on short-context; long-context speedups are reported as Pareto frontier shifts without a single headline number. Composition with EAGLE-3's chain extensions and MTP's medusa heads is one experiment away.

Industrial implication

Production serving stacks running EAGLE-3 or NeMo-RL-style speculative pipelines are the natural adopters. A 21.8% improvement over EAGLE-3 on Qwen3-235B is large enough to ship into vLLM and SGLang within a quarter once a reference kernel and index design land. The grafting pattern likely generalizes to medusa-head and DFlash-block paradigms (the paper offers preliminary evidence on the latter), making it a substrate-level move not a single-method optimization.

Connections

  • NeMo-RL speculative decoding integration (2026-04-30) brought EAGLE-3 / MTP into the RL training loop. Graft is the next-generation draft-tree construction that the same RL stack will inherit.
  • Orthrus dual-view diffusion (2026-05-14) ran an AR head and a diffusion head on a shared KV cache. Graft runs a draft tree and a retrieval index over a shared verification policy. Two different "parallel proposal source" designs converging on lossless acceleration.
  • MISA mixture-of-indexer sparse attention (2026-05-11) routed sparse attention on the head axis. Graft routes draft proposals across draft-generated and retrieval-grafted sources. New axes for sparsity are landing weekly.