Tree-based speculative decoding: draft trees win latency, lose batches, return cost-aware

Timeline: from SpecInfer's token tree to cost-aware trees over block drafters

The lineage starts in May 2023 with SpecInfer, which introduced the token tree abstraction, tree-based parallel decoding (storing tree tokens in the KV cache by topology and masking attention to ancestors only) and multi-step speculative sampling, a recursive residual-renormalizing rejection walk over the tree, with a theorem that output matches incremental decoding; its trees were static expansion vectors such as ⟨1,1,3,1,1,1,1,1⟩ and it reported 1.5–2.8× for distributed and 2.6–3.5× for offloaded inference (SpecInfer 2305.09781). Staged Speculative Decoding (Aug 2023) restructured the speculative batch as a tree on GPT-2-L for a 3.16× latency gain (Staged SD 2308.04623), and SpecTr (Oct 2023) reframed multi-draft token selection as optimal transport, delivering a K-SEQ rule with a (1−1/e) approximation guarantee (SpecTr 2310.15141).

January–February 2024 brought the static-tree boom. Medusa added K decoding heads and verified a Cartesian-product tree pruned to a 64-node sparse static shape via per-head calibration accuracies, reaching 2.2–3.6× (Medusa 2401.10774); EAGLE-1 drafted at the feature level with a static tree and showed in its ablation that the tree alone adds about +0.74 tokens/step (Vicuna-7B τ 3.20→3.94) (EAGLE-1 2401.15077); Hydra made Medusa heads sequentially dependent for up to 1.31× over Medusa (Hydra 2402.05109); and Sequoia formalized expected accepted tokens as a sum over nodes of path acceptance products, solved it exactly by dynamic programming, proved fixed shapes have finite yield ceilings while optimal trees grow as Ω(b·log n/log log n), switched to sampling without replacement, and chose (size, depth) with a hardware-aware speedup model, hitting 4.04× on Llama2-7B and 9.96× under offloading with 768-node trees (Sequoia 2402.12374). Recursive Speculative Decoding independently arrived at without-replacement tree sampling via Gumbel-Top-k and stochastic beam search (RSD 2402.14160).

Mid-2024 made trees dynamic. EAGLE-2 observed that acceptance depends on context, not just position, and that EAGLE's draft confidence is well calibrated (tokens with confidence <0.05 are accepted ≈4% of the time, >0.95 ≈98%), so it grows the tree by expanding top-k nodes by path-product value and reranking to keep the top-m (60 tokens, depth 6 for 7B targets), yielding 3.05–4.26×, 20–40% over EAGLE-1 (EAGLE-2 2406.16858). OPT-Tree greedily maximized the same proxy per step with a δ stopping threshold tied to the draft/target time ratio and pushed to >10 tokens per step with large budgets, while noting a 500-node tree gave no wall-clock speedup on an A100 (OPT-Tree 2406.17276). SpecExec and DySpec took best-first search to 64–2048-node trees in the offloaded regime, where verification is nearly free, reaching 20.6 accepted tokens per step and 18.7× over sequential offloaded decoding (SpecExec 2406.02532; DySpec 2410.11744).

2025 was the year of cost-awareness and sharper verification. EAGLE-3 kept EAGLE-2's dynamic tree (depth raised to 8) and reached up to 6.5× at batch 1 but reported only 1.38× in SGLang at batch 64, without trees (EAGLE-3 2503.01840). C2T and HeteroSpec cut verified tokens by 20–25% at equal acceptance length (C2T 2502.13652; HeteroSpec 2505.13254); Traversal Verification extended block verification to trees (2505.12398); CAST modeled inference time with lookup tables and lifted EAGLE-3 at batch 16 from 1.35× to 2.17× (CAST 2510.26577); Yggdrasil made dynamic trees CUDA-graph-capturable with static Equal-Growth shapes (2512.23858); and SpecDecode-Bench delivered the first controlled tree-vs-chain batch sweep on a production engine (2601.11580).

2026 split in two. Block and parallel drafters that verify a single linear block (DFlash, P-EAGLE, DSpark, Domino, EAGLE 3.1) dominated engine adoption: NVIDIA's DFlash post describes verification as accepting "the longest valid prefix" (NVIDIA 2026-06-23), and DeepSeek's DSpark chooses a per-request verification length from prefix-survival probabilities and the engine's throughput profile for +60–85% per-user speed over MTP-1 in DeepSeek-V4 serving (DSpark 2607.05147). A counter-wave then re-attached trees to these drafters: DDTree builds a best-first tree from DFlash's per-position distributions (2604.12989); CaDDTree optimizes throughput jointly over tree structure and budget (2606.01813); JetSpec's causal parallel tree drafting reaches 9.64× on MATH-500 (2606.18394); DARTree hits 12.97 accepted tokens per round (2608.13524); TreeSpark's tree "shrinks back to a chain" under rising load (2609.22098); and CAST (Lee & Eo) packs block-drafter candidates into a tree whose width grows only while expected gain exceeds added verification time, beating chain in all 8 settings by up to 43% (2610.00321). In parallel, trees were re-engineered for architectures where branch state cannot be shared naively: DeepSeek-V4's compressed attention (2609.24698), Gated DeltaNet hybrids (TreeWY 2608.20961; LumoTree 2609.23900) and Ascend NPUs (EAGLE-Pangu 2603.08088).

Taxonomy: four axes separate the methods

The literature is best organized along four nearly orthogonal axes: tree topology (how candidates are arranged), tree construction policy (how the shape is chosen and when it changes), drafter type (what produces the candidates), and verification rule (how the target decides what to accept). A fifth, systems axis (kernels, KV handling, parallelism) determines whether a method can be deployed at all.

On topology, static trees fix a shape offline from calibration statistics: SpecInfer's expansion vectors, Medusa's greedy sparse tree from per-head top-i accuracies, Hydra's throughput-tuned ≤100-node trees, EAGLE-1's shape, Sequoia's exact DP solution under a positional acceptance model, Falcon's custom tree, and Yggdrasil's Equal-Growth trees that trade some adaptivity for CUDA-graph capture (Medusa; Sequoia; Falcon 2412.12639; Yggdrasil). Dynamic trees choose shape per step from the draft distribution and split into two algorithmic families: layer-wise top-k expansion followed by a global rerank (EAGLE-2, OPT-Tree, TALON), which keeps draft calls equal to depth and is GPU-friendly, and global best-first heap expansion (SpecExec, DySpec, DDTree, DARTree's pruning), which yields better trees per node but needs many sequential draft calls unless the drafter emits all positions at once (EAGLE-2; DySpec; TALON 2601.07353). Within dynamic trees there is a further distinction between "dynamic in shape but static in size" (EAGLE-2 verifies a fixed 60-token budget every step) and size-adaptive methods (DDD, C2T, HeteroSpec, TALON, Graft, AdaptiveSpec, CAST, CaDDTree, TreeSpark) that vary total verified tokens per step. DAG/graph structures (GSD's merged hypotheses, Token Recycling's adjacency matrix) save draft compute by sharing repeated sub-sequences, but the target still sees a tree-attention mask (GSD 2407.16207; Token Recycling 2408.08696). Mega-trees of 128–2048 nodes are a regime-specific class (SpecExec, Sequoia offloading, DySpec on Llama2-70B offload) that pays only when verification is nearly free. Finally, none/chain methods matter as the baseline and as the current production default: SpecTr and the multi-draft theory papers verify K sibling drafts at one position (width without depth), Block Verification verifies a single chain jointly, and the 2026 block drafters verify a linear block.

On the drafter axis, trees have been fed by independent small LMs (SpecInfer, Sequoia, SpecExec, DySpec), parallel heads on the target's hidden state (Medusa, Hydra, Amphista, KOALA), feature-level autoregressive heads (EAGLE-1/2/3, HASS, GTO), semi-autoregressive or block drafters (Falcon, DFlash, DSpark, Domino, with trees added by DDTree, DARTree, DominoTree, TreeSpark, CAST-2610, JetSpec), and training-free retrieval (REST's datastore Trie, SuffixDecoding's suffix trees, SAM-Decoding's automaton, Lookahead's n-gram pool, Token Recycling, Graft's grafted retrieval tokens) (REST 2311.08252; SuffixDecoding 2411.04975; Graft 2605.20104). The 2026 insight from TreeSpark is that per-position marginals from block drafters "ignore which parent a candidate extends", so a correction head (DARTree), Markov head (TreeSpark) or surrogate ranking (DDTree) is needed before best-first pruning is meaningful (TreeSpark).

On the verification axis the literature uses six rules: (a) greedy exact match (Medusa/Hydra/EAGLE greedy settings); (b) multi-draft rejection sampling with replacement, which is SpecInfer's MSS, "recursive rejection sampling" and MCSD Algorithm 1; (c) RRS without replacement (MCSD Algorithm 2, Sequoia, RSD, TreeSpark); (d) optimal-transport-based rules (SpecTr K-SEQ, SpecHub, Hu et al.'s Greedy sampling, Thomas & Pal's convex reformulation); (e) sequence-level joint verification (Block Verification for chains, Traversal Verification for trees); and (f) lossy rules (Medusa's typical acceptance, AdaptiveSpec's margin rule, Cactus's constrained acceptance) (MCSD 2401.06706; SpecHub 2411.05289; Block Verification 2403.10444; Cactus 2604.04987). The construction policy axis ranges from hand-designed proxies (path probability products, entropy bins, confidence thresholds) through learned components (C2T's 2-layer classifier, HeteroSpec's CART bins, TreeGraft's distilled scheduler, Dynamic Delayed Tree Expansion's neural selector) to RL that directly rewards per-cycle throughput (Learning to Draft) (LTD 2603.01639; DDTE 2602.16994).

Theory bounds acceptance logarithmically and separates shape from verification

The theoretical results fall into three groups that, read together, explain the empirical knee in tree size. The first group optimizes shape under a positional acceptance model. Sequoia's Table 1 is the clearest impossibility statement: a sequence yields at most 1/(1−P₁) expected tokens, k independent sequences 1 + P_k/(1−P₁), a k-ary tree 1/(1−P_k), while the DP-optimal tree is unbounded and grows as Ω(b·log n/log log n) under a b-power-law acceptance model (Sequoia). Medusa observed the same thing empirically: acceptance gain grows only logarithmically with tree size while compute grows linearly, so tokens/s eventually drops (Medusa). OPT-Tree's E(A) objective is the per-context analogue, and its Theorem 3.1 shows the n largest path-product nodes always form a root-connected subtree, with the stopping threshold δ ∈ [μ, 1] tying construction to the draft/target time ratio μ (OPT-Tree). Pankratov and Alistarh's "speed-of-light" bound closes this group: by mapping token generation to branching random walks they prove that for any deterministic speculative scheme the expected accepted tokens per iteration satisfy E[X] ≤ (μ + μ₂)·log(P)/μ² + O(1), where P is verifier capacity and μ the expected target entropy, and report Llama experiments consistent with it (2512.11718, EACL 2026 per ACL Anthology). How P maps to tree size and the O(1) constant are not defined on the abstract page, so the bound's practical tightness remains to be checked.

The second group studies single-step multi-draft verification as an optimal-transport problem. SpecTr showed the exact plan is an LP exponential in the number of drafts and gave K-SEQ with a (1−1/e) guarantee (SpecTr). Khisti et al. derived a canonical decomposition (importance-sampling selection of one intermediate token, then single-draft speculative sampling) and a closed form for two identical drafts, α = min_S[q(S) − p(S)² + 1], conjecturing exponent K for K drafts but proving only K=2 (Khisti 2410.18234). Hu et al. (ICLR 2025) then showed the LP dual is a weighted vertex cover whose integral optimum reduces to α* = 1 + min_H [P(H) − Q(H)], computable in O(|Σ| log|Σ|) by sorting tokens on q/p, and measured the gap of practical RRS to this optimum at only 0.1–3.3 acceptance percentage points at three drafts and T=0.7, with without-replacement sampling strictly better than with-replacement and gaps growing with temperature and draft count (Hu et al. 2502.18779). SpecHub compacts the OT LP and gains 0.05–0.27 tokens/step over RRS (SpecHub); Thomas and Pal recast the problem as max-flow and reduce it via polymatroid theory to a convex program in at most V variables (Global Resolution 2511.15898). The practical lesson is that the choice of draft sampling (without replacement, or greedy top-(n−1) plus one sample) matters more than the verifier, since SpecTr's 63%-of-optimal worst case is far looser than the observed single-digit gaps.

The third group handles the sequence axis. Block Verification proves optimality among all valid verifiers for a single chain, with +8.3% block efficiency and 5–8% wall-clock over token verification (Block Verification); Traversal Verification extends leaf-to-root joint verification to trees, proves losslessness, matches block verification on chains, and gains 2.2–5.7% acceptance length on EAGLE and binary trees, with larger gains at higher temperature and depth (Traversal Verification). Yin et al. characterize rejections as a sum of TV distances between draft and target, prove speculative decoding optimal among unbiased rejection methods, and show batch (multi-draft) gains saturate at TV(p,q) so rejections never vanish when p and q differ substantially (Yin 2411.00841). Hu and Huang's Tree Monte Carlo argues per-token maximal coupling is "not optimal" and couples over the tree space instead (PMLR 2024). Critically, no paper proves a joint optimality result over tree shape plus tree verification: Traversal Verification proves optimality only for chains, Hu et al. leave multi-step × multi-draft open, and Dynamic Delayed Tree Expansion's 2026 comparison finds Traversal Verification dominates OT-based methods in practice because OT wins near the root "where it matters least" (DDTE).

Dynamic trees converge on one signal and now adapt size, not just shape

Nearly every runtime tree builder uses the same signal, cumulative draft probability along the root path, as an acceptance proxy, and EAGLE-2's calibration measurement is its empirical license (EAGLE-2). The methods differ in budget rule, search and whether size varies. EAGLE-2's ablation shows what each piece buys on Vicuna-7B: removing both value and reranking drops speedup from 3.62× to 2.81× (τ 4.98→3.92) (EAGLE-2). OPT-Tree raises τ from 3.73 to 4.36 over EAGLE's static tree on LLaMA-2-7B but speedup only from 2.51× to 2.56×, and on LLaMA-2-70B with a 7B drafter τ jumps 4.97→7.74 for a speedup gain of 1.80×→1.85×, a vivid demonstration that accepted length is a poor proxy for wall-clock once trees are large (OPT-Tree). DySpec's heap-based expansion beats Sequoia's static trees on Llama2-70B (9.10 vs 6.08 accepted tokens at T=0) but the gap nearly closes at T=0.6 (6.21 vs 5.72), and the authors note node-by-node selection "does not naturally support layer-by-layer generation" (DySpec).

The 2025–2026 generation makes size adaptive. Dynamic Depth Decoding stops EAGLE-2's beam search when a log-sum-exp confidence heuristic drops below a threshold for ≈4–5% over EAGLE-2 (DDD 2409.00142). C2T's 2-layer classifier over path probability, child entropy and depth cuts candidate tokens by ~25% (2.6M→2.0M on LLaMA-2-7B) at equal or better τ, and the 18% wall-clock gain appears only on 70B across 2×A100 "when GPU parallel capacity is saturated" (C2T). HeteroSpec stratifies contexts by cumulative top-K entropy into CART-derived bins, extends depth and prunes top-N for low-entropy bins, and averages 4.26× vs EAGLE-3's 4.07× while cutting verification tokens ≈20% (HeteroSpec). TALON keeps EAGLE-3's budget of 60 but gates each layer on cumulative probability relative to the pool maximum (μ = 0.03), producing chain-like deep trees in deterministic contexts and shallow-wide trees under uncertainty, for 5.16× vs 4.77× on Vicuna-13B HumanEval and 3.97× vs 3.78× at T=1 (TALON). Graft prunes depth then grafts retrieval tokens into freed slots, reaching 5.41× and up to 21.8% over EAGLE-3 on Qwen3-235B (Graft); TreeGraft lets a stronger drafter rescore and graft onto a weak drafter's tree for +15.1% average over the better fixed drafter, metric unspecified in the abstract (TreeGraft 2608.26112); AdaptiveSpec combines a lossy margin acceptance rule with a per-step depth/width/node policy for up to 56% throughput over EAGLE-3 in SGLang at 93%-to-lossless accuracy (AdaptiveSpec 2609.02897); SAGE adapts depth and width from output entropy for vision-language models at up to 3.36× on LLaVA-OneVision-72B (SAGE 2602.00523).

Learned policies are moving from acceptance proxies to time-aware rewards. OPT-Tree's δ ∈ [μ,1] and the Pruned Candidate Tree's "expected time gain" are hand-designed precursors (PCT, ACL 2025); CAST (Hong, Tan, Hu) models inference time f(B,c,n) via lookup tables and prunes by marginal utility per cost, recovering EAGLE-2/3's rule as the linear-cost special case and lifting batch-16 EAGLE-3 from 1.35× to 2.17× (CAST 2510.26577); CaDDTree proves throughput is unimodal in node budget under convex verification cost, enabling greedy stopping that matches an oracle-budget DDTree (CaDDTree); Group Tree Optimization identifies "draft policy misalignment" (training on the greedy path, decoding on a tree) and trains EAGLE-3 with a draft-tree reward for +7.4% acceptance length and +7.7% speedup (GTO 2509.22134); Learning to Draft frames draft-and-verify as RL with per-cycle throughput as reward for up to 36.4% over EAGLE-3 (LTD). No paper yet applies RL to per-node expansion decisions; the learned components are classifiers, bin lookups or length predictors.

Temperature is a recurring weak spot. OPT-Tree and DySpec both report degraded gains at T>0 because the E(A)–acceptance correlation weakens under sampling; HeteroSpec evaluates only at T=0; EAGLE-2 retains most of its gain at T=1 (Vicuna-13B 3.65× vs EAGLE 2.39×) but loses 0.3–0.5× relative to T=0 (EAGLE-2; OPT-Tree). The methods that stay robust make the sampling itself tree-consistent: Sequoia and TreeSpark sample siblings without replacement with matching residuals, and SpecExec caches target next-token distributions for every prefix and samples sequentially so output is seed-identical to sequential sampling (Sequoia; TreeSpark; SpecExec).

Systems: trees pay where verification is idle and collapse where it is saturated

The systems evidence is unusually consistent. SpecDecode-Bench ("Speculative Decoding: Performance or Illusion?", MLSys 2026) ran the only controlled tree-vs-chain batch sweep on a production engine (SGLang v0.5.9, depth 3): at batch 1 a 21-node tree raises Qwen3-8B/GSM8K from 1.65× to 1.85× and Llama3-70B/ShareGPT from 1.81× to 2.03×, with accepted length rising 2.25→2.92 while per-token acceptance rate collapses 0.415→0.095; "by batch size 64, the k=21 tree fell below 1× on all workloads for both models, while the chain stayed above 1×" (2601.11580). The same study finds verification consumes 42–95% of step time, rising with model and batch size, with EAGLE drafting 12–20% at batch 1 and 3–7% at batch 512, and its cost model is still the Leviathan chain formula E(speedup) = (1 − α^(k+1))/((1 − α)(kc + 1)) with a footnote that it assumes memory-bound verification (2601.11580). EAGLE-3's own serving tables agree: chain-mode EAGLE-2 goes from 1.40× at batch 2 to 0.93× at batch 24 in SGLang, EAGLE-3 to 1.38× at batch 64, and vLLM gains fall to 1.01× at batch 56 (EAGLE-3). CAST reports EAGLE-3 dropping from 3.99× at batch 1 to 1.35× at batch 16 (CAST). The DeepSeek-V4 adaptation finds the mirror-image positive case: at equal budget trees give longer accepted length (2.83–3.41 vs 2.39–2.84 at D=8) and up to ~18.5% higher throughput, largest "for less predictable workloads at small-to-medium batch sizes", with throughput plateauing even as accepted length rises (2609.24698).

The regimes where trees shine are those where the verifier would otherwise idle. Offloading makes a 2048-token tree nearly free (SpecExec 18.7×, Sequoia 9.96×). Pipeline parallelism has bubbles: SpecPipe fills an 8-stage pipeline with a dynamic token tree for 4.19–5.53× better time-between-tokens than plain PP and 2.08–2.38× over prior tree SD, with its dynamic-batching variant 1.64–2.08× over vLLM (SpecPipe 2504.04104); FlowSpec pipelines tree SD across edge devices for 1.37–1.73× (FlowSpec 2507.02620). Yet vLLM's documentation still lists pipeline parallelism as "not composable with speculative decoding as of vllm<=0.15.0" (vLLM docs), and the WAN analysis of edge-cloud split speculation concludes pipelined distributed SD matches co-located SD only when RTT is below the edge drafting window, with the real win being capacity rather than single-request latency (Speculation at a Distance 2606.25091). None of the edge-cloud frameworks found (PicoSpec, DSSD, SPADE, PipeSD, SLED) use trees.

Kernels and KV handling are the quiet constraint. Every engine that runs tree verification implements it as a custom additive or boolean mask on an existing prefill/append kernel: FlashInfer's bit-packed custom_mask (FlashInfer docs), SGLang's build_tree_kernel_efficient plus sgl_kernel verification (sglang eagle_utils.py), and vLLM's Triton unified_attention with a qq_bias tree mask (vLLM tree_attn.py @ v0.11.1). DeFT (ICLR 2025) is the only dedicated tree-attention kernel paper, with KV-guided grouping and flattened tree KV splitting for up to 2.23× end-to-end and 73–99% KV IO reduction on tree-structured workloads generally (DeFT 2404.00242). For KV, the reference EAGLE implementation compacts accepted slots in place via retrieve_indices gathers (EAGLE utils.py), while SGLang uses slot-indexed paged allocation where trailing unaccepted slots "are freed as overshoot" and, when page_size>1 with topk>1, duplicates the prefix's partially-filled last page into each branch (sglang eagle_worker_common.py). LongSpec identifies "inefficient tree attention over long sequences" and combines fast prefix computation with standard tree attention for up to 3.26× (LongSpec 2502.17421); Yggdrasil shows CUDA Graphs alone give Llama-2-7B 2.32× but dynamic drafting prevents capture (Yggdrasil). For MoE targets, draft tokens "collectively activate more expert weights", raising verification time 2–3× and causing slowdowns up to 1.5×; Cascade's utility metric controls chain length K only (Utility-Driven SD 2506.20675), and TensorRT-LLM's dynamic tree is unsupported for MLA and sliding-window models (TRT-LLM docs).

Summary table

All arXiv IDs were resolved by the notes against their abs pages; "Code" lists the repository given in the paper, README or community list, or "—" when none was found. "Verification rule" says "not stated" where the notes could not confirm it from primary pages. Speedups are over vanilla autoregressive decoding at batch 1 unless the cell says otherwise.

The table runs to 63 rows because the brief enumerated more than 50 named methods; rows beyond the brief (MCSD, STree, GTO, Yggdrasil, DominoTree, DSpark, LongSpec, the second CAST) are included because the notes verified them and they anchor claims elsewhere in the report.

Engine support matrix

As of the documentation fetched on 2026-10-08, only SGLang verifies a true draft tree by default and only for some model families; TensorRT-LLM offers an opt-in dynamic tree; vLLM has tree infrastructure that is neither documented nor default; llama.cpp, TGI and HF Transformers verify a single chain.

Two production-adjacent signals reinforce the matrix. AMD's Kimi-K2.5 EAGLE3 deployment on 8×MI325X with SGLang used num-steps=3, topk=1, num-draft-tokens=4, a chain, and still cut TPOT 35% at concurrency 40 (AMD ROCm blog, 2026-06-23); vLLM's AMD post (2026-08-23) describes verification as committing "stopping at the first rejected token" and found EAGLE-3 below baseline on Qwen3-8B/MATH500 at every draft length (vLLM AMD blog). Between July 2025 and August 2026 the SGLang team's own showcased EAGLE3 configuration moved from topk=8 (tree) to topk=1 (chain) (SpecForge launch; SpecForge v0.3).

Repositories and blogs

Star counts are GitHub page snapshots from 2026-10-08 (rounded as displayed; the GitHub API was blocked so push dates are unavailable). Research repositories that ship tree verification come first, then training/packaging frameworks, then blogs in date order.

Blogs and write-ups, in date order: Together AI's Medusa post explains Cartesian tree attention and ~2× on MT-Bench (2023-09-11); LMSYS's Lookahead post describes the Jacobi n-gram verification branch at 1.5–2.3× (2023-11-21); the EAGLE site notes EAGLE's tree is sparser than Medusa's, which yields "nonsensical combinations" (2023-12-08); the Sequoia page states a 64-node tree suits on-chip and 768 nodes suits offloading (2024); Together's SpecExec post reports 18.7× offloading (2024-06-18); vLLM's first SD post shows 1.4–1.8× slowdowns at high QPS (2024-10-17); Baseten's TRT-LLM post is chain-only and warns SD works "only at limited batch sizes" (2024-12-19); LMSYS's SpecForge launch fixes topk=8 "so that tree attention could be enabled" (2025-07-25); NVIDIA's introduction describes EAGLE-3 conceptually as a dynamic tree with parallel tree attention (2025-09-17); Together's ATLAS post covers adaptive lookahead length without trees (2025-10-10); vLLM's Speculators v0.3.0 (2025-12-13); Baseten on training EAGLE-3 heads, 1.5–2.5× for latency-sensitive unbatched workloads (2026-04-13); vLLM's EAGLE 3.1 post with chain config and 2.03× per-user throughput at concurrency 1 on Kimi-K2.6 (2026-05-26); AMD's Kimi-K2.5 EAGLE3 topk=1 deployment (2026-06-23); NVIDIA's DFlash on Blackwell with longest-prefix block verification and up to 15× throughput (2026-06-23); vLLM/Red Hat's "Parallel All the Way Down" on P-EAGLE, DFlash, DSpark (2026-07-28); LMSYS's SpecForge v0.3 with EAGLE3 at topk 1 (2026-08-04); vLLM on AMD GPUs with chain verification and EAGLE-3 regressions (2026-08-23); and Red Hat's P-EAGLE article, whose per-rollout flex-attention mask is not called tree attention (2026-09-03). Posts surfaced but not fetched (Fireworks, the "Inside vLLM" anatomy post, LMSYS gpt-oss and EAGLE3-on-Vertex, the two older NVIDIA TRT-LLM throughput posts) should be treated as unverified for tree content.

Research gaps

1. 01

   No fitted, hardware-parameterized cost model for tree verification.

   Every tree builder implicitly assumes step time ≈ depth × T_draft(width) + T_target(N_tree), with T_target flat while memory-bound and linear once compute-bound, but no paper publishes a fitted T_target(N_tree, batch, model) curve; the knee is known only anecdotally (OPT-Tree's 500 nodes on A100 giving no speedup; SpecDecode-Bench's k=21 tree below 1× at batch 64; CAST-2610's 128-token tree only ~2% over chain at a kernel boundary) (OPT-Tree; 2601.11580; CAST 2610.00321). The two CASTs and CaDDTree use lookup tables or convexity assumptions rather than a validated model, and SpecDecode-Bench still reports the chain-only Leviathan formula.

2. 02

   Tree collapse at batch>1 is documented but unsolved at the scheduler level.

   Only one controlled tree-vs-chain batch sweep exists (two batch sizes, one engine version) (2601.11580); all batch-aware schedulers (TurboSpec, AdaSpec, TETRIS, SGLang --speculative-adaptive, vLLM num_speculative_tokens_per_batch_size) control chain length, not tree shape, and SGLang's adaptive mode requires topk=1 (SGLang adaptive docs; TurboSpec 2406.14066). C2T and TALON explicitly evaluate only batch 1 "like other dynamic tree methods", so the serving-time value of the "fewer verified tokens at equal τ" family is largely untested (C2T).

3. 03

   No joint optimality result for tree shape plus tree verification.

   Shape optimization (Sequoia's DP, OPT-Tree's E(A)) assumes token-level verification; verification optimality is proven only for chains (Block Verification, Traversal Verification's Theorem 3.4) or single-step multi-draft (Hu et al.); Khisti et al.'s K>2 closed form is a conjecture; and the speed-of-light bound does not define how capacity P maps to tree size (Traversal Verification; Hu et al.; Khisti; 2512.11718).

4. 04

   Trees over block-diffusion and semi-autoregressive drafters are nascent.

   DFlash, DSpark, P-EAGLE and Domino shipped chain-only in all three major engines, and the tree extensions (DDTree, CaDDTree, DARTree, DominoTree, TreeSpark, CAST-2610, JetSpec) are all 2026 arXiv preprints without confirmed venues, several without numbers in their abstracts, and none yet in an engine's default path; TreeSpark's observation that per-position marginals "ignore which parent a candidate extends" means the calibration problem for such trees is only partly solved (TreeSpark; DDTree).

5. 05

   Trees for MLA, compressed-attention and hybrid recurrent targets lack kernels and controlled results.

   TensorRT-LLM's dynamic tree is unsupported for MLA and sliding-window models; the DeepSeek-V4 adaptation needs branch-aware verification and state isolation because branches "end up in different compressed states"; TreeWY and LumoTree address Gated DeltaNet hybrids but LumoTree's authors state controlled speedups remain open; SGLang's DSA index-share state is topk=1 only (TRT-LLM docs; 2609.24698; LumoTree; eagle_worker_v2.py).

6. 06

   MoE expert-activation cost of trees is unmodeled.

   For MoE verifiers the right cost is distinct (token, expert) activations, not node count; draft tokens raise verification time 2–3× and can slow decoding 1.5×, but the only utility-driven controller (Cascade) governs linear K, EAGLE-1 already saw MoE speedup fall to 1.5×, and SPEED-Bench warns synthetic inputs hide expert imbalance (2506.20675; EAGLE-1; SPEED-Bench 2604.09557).

7. 07

   Trees with pipeline parallelism, disaggregated serving and WAN remain thin.

   SpecPipe and FlowSpec show trees fill pipeline bubbles well, yet vLLM lists PP as not composable with SD, no fetched work combines trees with prefill/decode disaggregation, and the edge-cloud analysis suggests WAN-split SD wins on capacity rather than latency without addressing trees at all (SpecPipe; vLLM docs; 2606.25091).

8. 08

   Non-greedy robustness of probability-proxy trees is under-evaluated.

   OPT-Tree and DySpec report degraded gains at T>0, HeteroSpec tests only T=0, Hu et al.'s Greedy sampling is worse at T=1, and no dedicated temperature study of dynamic trees exists beyond EAGLE-2's and TALON's tables; the lossless-at-any-temperature constructions (Sequoia, TreeSpark, SpecExec) have not been compared head-to-head under matched budgets (DySpec; HeteroSpec; TALON).

9. 09

   Learned and RL policies do not yet act on per-node tree decisions.

   Learned components are node classifiers (C2T), entropy bins (HeteroSpec), length predictors (AdaEAGLE, Pacer), bandits over hyperparameters (BanditSpec) or whole-cycle policies (LTD); none applies RL to expansion choices node by node, and GTO's finding of "draft policy misalignment" between greedy-path training and tree decoding implies drafters themselves are undertrained for trees (LTD; BanditSpec 2505.15141; GTO).

10. 10

    Benchmarks are greedy, batch-1 and partly synthetic.

    Spec-Bench's leaderboard is greedy, FP16, batch 1 on two GPUs and was last updated 2025-04-22, with EAGLE-2 scoring 2.19× vs 2.36× across GPUs and 2.2–2.4× there versus 3.4–4.1× in its paper; SPEED-Bench shows random tokens overestimate throughput by up to 23% and EAGLE3's pruned vocabulary misses up to 22% of targets in multilingual/RAG tasks; no benchmark reports a tree-specific break-even batch curve (Spec-Bench Leaderboard; SPEED-Bench; 2601.11580).

11. 11

    Engine plumbing blocks dynamic trees.

    SGLang's overlap scheduler and rejection-sampling path require topk=1; TRT-LLM cannot dynamically disable speculation; vLLM's tree topology is static with pruning unimplemented and its 2026 tree-infrastructure PR closed unmerged; Yggdrasil shows dynamic drafting forfeits a 2.32× CUDA-graph gain; paged KV with topk>1 forces per-branch page duplication; and EAGLE-Pangu documents that masks, KV layouts and indexing differ across accelerators (SGLang docs; vLLM PR #59091; Yggdrasil; EAGLE-Pangu).

12. 12

    Retrieval-tree verification topology is unverified in primary sources.

    REST's Trie-tree verification is asserted only in its README, SuffixDecoding's "speculation tree" in vLLM is a proposer data structure rather than tree attention, and SAM-Decoding, Lookahead and Ouroboros abstracts are silent; SGLang's ngram BFS breadth is the only engine-level retrieval tree found (REST repo; vLLM docs; SuffixDecoding).

ID and title corrections flagged in the notes

Several identifiers in circulation are wrong or have drifted, and the report uses the verified forms. The ICLR 2025 paper "Towards Optimal Multi-draft Speculative Decoding" (Hu, Zheng, Viswanathan, Chen, Rossi, Wu, Manocha, Huang) is arXiv 2502.18779; the ID 2502.18647 resolves to an unrelated urban-overheating paper, and the paper is sometimes misattributed to Khisti et al., whose multi-draft limits paper is 2410.18234 (2502.18779; 2502.18647; 2410.18234). arXiv 2503.05096 now resolves to "AdaSpec: Adaptive Speculative Decoding for Fast, SLO-Aware LLM Serving", formerly cited as SpecServe (2503.05096). arXiv 2504.04104 is SpecPipe, not a separate "PipeDec" paper, which could not be verified (2504.04104). "Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters" (2408.04093) is a tree-structured cross-device reduction for long-context attention, an exact alternative to Ring Attention, and is unrelated to draft-tree verification despite the name (2408.04093). Likewise arXiv 2503.04398 now resolves (v5) to "Semantic Parallelism", while its v3 was titled "Speculative MoE"; it speculates expert routing, not draft tokens (2503.04398). Additional caveats: SpecExec's NeurIPS 2024 venue is not stated on its arXiv page; venue strings for SpecTr, Medusa, Hydra, Sequoia, EAGLE-2, EAGLE-3, Block Verification, SpecHub, OPT-Tree and Traversal Verification come from the community list rather than arXiv (hemingkx list); several 2026 abs pages report submission dates that do not match their ID month (TreeGraft 2608.26112 "submitted 2026-05-28"; AdaptiveSpec 2609.02897 "submitted 2026-07-03"; TreeSpark 2609.22098 "submitted 12 Aug 2026"), so exact dates for those are approximate; CAST-2510's code link (EAGLE-Research/sglang-eagle4) returned 404 and vLLM's tree_attn.py was not found at main on 2026-10-08; and Medusa's Table 1 column "Acc. rate" (3.47 etc.) is not defined on the page as mean accepted length.

Conclusion

The three-year arc reframes the question from "are trees better than chains?" to "how many verified tokens does this hardware, batch and model give away for free?" Trees unambiguously raise accepted length, and the theory now says that gain is logarithmic in capacity while cost is linear once compute-bound, so the value of a tree is a property of the serving regime, not of the algorithm. That is why the field's best 2026 work treats tree width as a runtime control variable that collapses to a chain under load (TreeSpark, CAST, CaDDTree, AdaptiveSpec), and why the same insight that made DSpark adapt chain length per request is being generalized to shape. The chain-only shipping of block drafters was not a verdict against trees but a consequence of kernel and scheduler constraints that are now being removed one engine at a time.

For practitioners the actionable conclusion is to choose by regime: at batch 1 on dense Llama-class models a 60-token EAGLE-2/3 tree or TALON-style gating is worth 10–20% over a chain; at concurrency above roughly 16–24 on current engines a 3–4-token chain is the safe default; and in offloaded or pipeline-bubbled settings mega-trees of hundreds to thousands of nodes are nearly free. For researchers the highest-leverage targets are a validated verification-cost model that a scheduler can query, tree-aware training of drafters, exact and cheap tree verification for MLA and hybrid architectures, and benchmarks that sweep batch, temperature and real traffic rather than greedy batch-1 prompts.