PaperlayerView exact revision on arXiv

Source-linked AI summary

Where Draft Trees Lose Target Mass: Exit-Guided Speculative Decoding

Shijing Hu, Xuancheng Ren, Zhihui Lu, Pan Zhou

arXiv:2610.11750v1cs.AI

TL;DR

Finite draft trees can omit target-likely continuations, limiting what exact verification can accept on a fixed tree. The paper derives a canonical exit law, uses it for direct verification and target-guided tree training, and reports higher output-block length alongside lower verification latency.

  • Problem

    Under a finite tree budget, draft-score construction can leave target-likely branches insufficiently expanded, raising the question of whether verification or target feedback can improve acceptance.

    Source: §1 · p. 2

  • Method

    The paper derives a verifier-independent canonical exit law, uses it to build direct Tree Exit Verification, and trains draft trees with target-derived node-level exit feedback.

    Source: §1 · pp. 2–3

  • Results

    13% higher average output-block length and 14% higher decode throughput versus DDTree, with TEV reducing verifier-stage latency by 15% on a fixed tree.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The framework separates two opportunities in tree speculative decoding: improve tree coverage for higher acceptance and verify the same support more efficiently.

    Source: §7 · p. 9

    Systems results are limited to batch-one decoding with DDTree; alternative builders and high-throughput serving remain future work.

    Source: §7 · p. 9

Abstract

from arXiv · show

Tree-based speculative decoding verifies multiple draft continuations in one target-model pass, but finite trees built from draft scores face a fundamental draft-target mismatch. We ask whether better exact verification can increase acceptance on a fixed tree and how target feedback can improve the tree itself. Through a target-flow view, we identify a canonical exit law and prove that one plus target coverage sharply bounds the expected output-block length, including the bonus token, of any exact path verifier. All optimal verifiers share the same exit and bonus-token law, already attained by representative predraw-and-follow and sequential residual verifiers. This yields Tree Exit Verification (TEV), an exact, level-parallel procedure using one exit-node decision and one bonus-token decision. The exit law also identifies missing target probability, providing node-level feedback for Exit-Guided Draft-Tree Training (ExitTrain) on inference-time draft trees. Experiments across dialogue, code, and mathematical reasoning validate fixed-tree equivalence: ExitTrain increases average output-block length by 13%, while TEV reduces verifier-stage latency by 15%, yielding a 14% end-to-end speedup over DDTree. Our results distinguish two opportunities: better draft trees for higher acceptance and more direct verification for lower latency. Code: https://github.com/hsj576/TEV.

1 INTRODUCTION

Finite draft trees can omit target-likely branches, limiting acceptance even when verification is exact. The paper characterizes that fixed-tree limit, introduces direct verification and exit-guided tree training, and reports complementary acceptance and latency gains.

1 INTRODUCTION

  • Draft-score builders can spend limited tree budget on branches favored by the drafter while leaving target-likely branches insufficiently expanded.The mismatch can arise whenever a bounded tree is built from draft-side information before target verification.Source: §1 · p. 2
  • The paper asks whether exact verification can improve acceptance on a fixed tree and how target feedback can improve future trees.These questions separate tree coverage from the efficiency of verifying that support.Source: §1 · p. 2
  • On a fixed tree, the maximum expected output-block length is one plus target-mass coverage, and saturated exact verifiers share the same exit and bonus-token law.DDTree predraw-and-follow and EAGLE-style sequential residual verification already attain that law.Source: §1 · p. 2
  • TEV realizes the optimal fixed-tree law by directly sampling an exit node and then a bonus token, enabling level-parallel execution.It avoids auxiliary per-node samples or sequential residual decisions.Source: §1 · p. 2
  • ExitTrain uses target-derived exit mass to reweight draft likelihoods and direct finite tree budget toward high-impact exit boundaries.Its supervision localizes uncovered target mass on the realized draft tree.Source: §1 · p. 3
  • Against DDTree with the same tree builder and budget, ExitTrain + TEV improves average output-block length (including the bonus token) by up to 13% and decode throughput by up to 14%.Separately, TEV reduces verifier-stage latency by 15% without changing saturated expected output-block length on a fixed tree.Source: §1 · p. 3

2 BACKGROUND AND FIXED-TREE SETUP

Tree speculative decoding separates drafting, budgeted tree construction, and target verification. Prior systems use different builders and verifiers, while related draft-training methods provide alternatives to ExitTrain’s node-level supervision.

2 BACKGROUND AND FIXED-TREE SETUP

  • A drafter proposes candidates, a budgeted builder selects a prefix-closed tree, and one target pass lets a verifier return an accepted path plus a bonus token.The paper instantiates DFlash with DDTree’s cumulative-score best-first builder.Source: §2 · p. 3
  • DDTree predraws target tokens at nodes, whereas EAGLE-style sequential residual verification tests children in order and updates the remaining target probability.Both attain the same optimal law on a fixed tree despite their different computations.Source: §2 · p. 3
  • Prior draft training uses distillation, feature or token objectives, tree rewards, replayed trajectories, acceptable-path modeling, or simulated rejection positions.ExitTrain instead derives normalized node-level supervision from the canonical exit law to reallocate a fixed tree budget toward uncovered target mass.Source: §2 · p. 3

3 THE CANONICAL EXIT LAW AND THE FIXED-TREE CEILING

For a realized finite tree, target continuations induce a verifier-independent distribution over where they leave the tree. This canonical exit law yields a sharp bound on exact verification, identifies the common law at equality, and points to tree coverage as the remaining route to higher output-block length.

3 THE CANONICAL EXIT LAW AND THE FIXED-TREE CEILING

  • A fixed-tree setup conditions on a context and realized prefix-closed tree, and defines exact path verification through a target-coupled output prefix and stopping length.The stopping-time condition ensures variable-length blocks compose safely across decoding rounds.Source: §3 · pp. 3–4

3.1 TARGET FLOW AND THE CANONICAL EXIT LAW

  • A target continuation follows matching drafted children until its next token is absent or it reaches a leaf; its deepest matched node is the exit node.The exit marks where the tree stops covering that continuation.Source: §3.1 · p. 4
  • The canonical exit law assigns each node the probability that target flow reaches it and leaves there; these probabilities sum to one and depend only on the target model and fixed tree.At a leaf, no drafted child is available, so the local exit probability is one.Source: §3.1 · p. 4

3.2 FROM THE EXIT LAW TO THE FIXED-TREE ACCEPTANCE CEILING

  • At saturation, expected output-block length, including the bonus token, is 1 + target coverage of the tree.Target coverage is also the maximum expected number of accepted draft tokens.Source: §3.2 · p. 5
  • Every exact path verifier has expected output-block length at most 1 + target coverage; equality forces the canonical exit-node and residual bonus-token laws.Saturated DDTree predraw-and-follow and EAGLE-style sequential residual verification share the same accepted-path distribution and expected lengths on the same tree.Source: §3.2 · p. 5

3.3 WHAT REMAINS AFTER FIXED-TREE SATURATION

  • Once fixed-tree verification is saturated, higher output-block length requires increasing tree coverage; exit mass identifies boundaries where target flow reaches but leaves the tree.That signal motivates both more efficient execution of the common law and training to improve finite-budget coverage.Source: §3.3 · p. 5

4 TEV: DIRECT VERIFICATION FROM THE CANONICAL EXIT LAW

TEV implements the canonical fixed-tree law directly rather than reproducing it through per-node draws or sequential child tests. It is exact and saturated while offering a level-parallel, fixed-shape verification procedure.

4 TEV: DIRECT VERIFICATION FROM THE CANONICAL EXIT LAW

  • TEV computes the exit distribution, samples one exit node, and then draws one bonus token from that node’s target residual.The target-model tree forward pass supplies the distributions; the drafter need not be queried again.Source: §4 · pp. 5–6
  • For any context and realized prefix-closed tree, TEV is an exact path verifier and attains the fixed-tree ceiling.Its expected output-block length equals 1 + target coverage.Source: §4 · p. 6
  • TEV replaces per-node samples or data-dependent child tests with node-local reductions, depthwise propagation, and two draws, enabling sibling-order-invariant, fixed-shape, level-parallel execution.The paper evaluates this latency benefit separately from output-block length.Source: §4 · p. 6

5 EXITTRAIN: EXIT-GUIDED DRAFT-TREE TRAINING

ExitTrain uses target-derived exit mass to identify where an inference-time draft tree misses target probability and steer its finite node budget. Its exit weights distinguish missing next-step coverage from successful reach to the hard horizon, while the training objective remains a surrogate for discrete tree allocation.

Exit weights

  • For expandable nodes, w(v) measures target mass that reaches the node but is missing from its drafted children; at hard-horizon leaves, it instead rewards target mass reaching the full depth.At depth H, ρ(v) = 1 and w(v) = P(v).Source: §5 · p. 6

Training signal

  • ExitTrain evaluates each fixed inference-time tree with the frozen target under actual tree-parent contexts and uses the resulting exit weights to supervise beyond a single draft path.The tree structure and target-derived weights are detached; gradients flow only through the drafter.Source: §5 · p. 6
  • Weighting a node’s incoming draft token by w(v) raises its future priority in DDTree, directing the discrete top-B builder toward prefixes with uncovered target mass.The update is a tree-allocation surrogate, not the exact gradient of target coverage.Source: §5 · p. 7

Training objective

  • The objective combines dense token prediction with exit-guided supervision; the root is omitted from the exit loss, so missing first-position tokens receive no direct exit credit.The dense token objective addresses coverage of missing first-position tokens.Source: §5 · p. 7

6 EXPERIMENTS

Across the reported tasks and target-model families, ExitTrain + TEV improves output-block length and speedup over DDTree, while TEV reduces verifier-stage latency without changing fixed-tree expected output length. Ablations attribute most acceptance gains to exit-guided training and show gains persist across tree budgets.

6.1 MAIN RESULTS

  • 8.8%–13.8% higher average τ and 11.5%–13.8% higher average SR than DDTree on Qwen3-4B/8B; Table 1 reports results across four benchmarks at B = 64.The comparison uses the same builder and budget.Source: §6.1 · p. 7, Table 1 · p. 8
  • ExitTrain + TEV improves average τ and SR across LLaMA-3.1-8B, Gemma-4-12B-IT, and Qwen3-Coder-30B-A3B, with gains varying by target family.Reported τ gains range from 4.3% to 17.7% across the stated temperatures and families.Source: §6.1 · p. 7
  • On Qwen3, GSM8K shows the largest τ gains, while HumanEval gains are smaller but consistent; with B = 64 fixed, increased accepted length reflects better target-prefix coverage.The passage attributes the additional accepted length to higher saturated output-block length, not more verified candidates.Source: §6.1 · p. 7
  • With a fixed drafter, Predraw and TEV differ by at most 0.03 tokens per benchmark, while TEV reduces verifier-decision and cache-commit latency by 12.0%–24.3% across tested budgets.Exit training supplies most acceptance gains; TEV's end-to-end SR gains are 0.4% with the original drafter and 0.7% with the exit-trained drafter.Source: §6.1 · p. 8

6.2 ABLATION STUDY

  • 5.9%/7.9% higher τ and 6.4%/6.3% higher SR than matched token-only finetuning show exit-guided training adds gains beyond additional training alone.The τ gains correspond to T=0/1; the comparison shares initialization, data, and compute.Source: §6.2 · p. 8, Table 2 · p. 9
  • Exit weighting outperforms prefix weighting by 7.8%/4.4% in τ and 7.4%/4.5% in SR, supporting localized exit feedback over reachability weighting alone.The τ and SR pairs are reported at T=0/1; prefix weighting measures reachability, while exit weighting also identifies uncovered target mass.Source: §6.2 · p. 9
  • TEV reduces verifier-decision and cache-commit latency by 15.2%/14.0% at B = 64 for T = 0.6/1.0, with larger reductions at wider tested budgets.The evaluation holds the drafter, builder, and realized tree fixed and excludes the shared target-model tree forward pass.Source: §6.2 · p. 9
  • Without budget-specific retraining, ExitTrain + TEV remains best at B ∈ {32, 64, 128}, improving τ and SR over both DDTree and Draft-OPD.Against DDTree, the reported gains are 11.6%–13.8% in τ and 11.4%–12.9% in SR.Source: §6.2 · p. 9

7 CONCLUSION

The paper separates fixed-tree verification efficiency from tree coverage: TEV executes the canonical exit law efficiently, while ExitTrain uses exit signals to improve finite-budget coverage. The systems evaluation is limited to batch-one decoding with DDTree, and training adds target-rollout and tree-evaluation overhead.

Conclusion

  • On a fixed tree, exact verifiers share a verifier-independent output-length ceiling, so higher output-block length requires better target coverage rather than verification alone.TEV targets execution cost; ExitTrain targets finite-budget tree coverage.Source: §7 · p. 9

Limitations

  • ExitTrain incurs one-time overhead for target rollouts and tree evaluation, which can be amortized during deployment.It fine-tunes released DFlash checkpoints without architectural or verifier changes.Source: §7 · p. 9
  • Systems results cover batch-one decoding with DDTree; alternative builders and high-throughput serving remain future work..Source: §7 · p. 9

ETHICS STATEMENT

The work studies lossless LLM inference using public models and benchmarks and does not collect personal information or involve human subjects. TEV preserves the target distribution, while downstream deployment retains the underlying models’ risks.

Ethics

  • The study uses publicly available models and benchmarks under their respective terms of use.It does not involve human subjects, private user data, or collection of new personal information.Source: ETHICS STATEMENT · p. 10
  • TEV preserves the target model’s output distribution and does not intentionally modify its capabilities, safety behavior, or intended use.Source: ETHICS STATEMENT · p. 10
  • Downstream uses inherit the target models’ potential safety, bias, privacy, and misuse risks, and users remain responsible for evaluating them and complying with applicable policies.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

The appendix states the assumptions and probability accounting behind fixed-tree verification, including how exactness composes across rounds. It also documents the proofs, derivations, configurations, and code intended to support reproducibility.

REPRODUCIBILITY STATEMENT

  • The paper identifies its sections for definitions, assumptions, fixed-tree results, TEV, and training, and points to appendices for proofs, derivations, implementation details, and evaluation configurations.An anonymized repository is described as providing code, configuration files, evaluation scripts, and reproduction instructions.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1 RANDOM TREES, AUXILIARY RANDOMNESS, AND ROUND-WISE COMPOSITION

  • For a realized tree and time-zero auxiliary randomness, exactness couples the output to a target continuation prefix whose length is a stopping time.The tree may be deterministic or stochastic, and the auxiliary randomness may control stopping but excludes randomness in the coupled target continuation.Source: §A.1 · p. 13
  • Applying the conditional exactness construction at each round preserves the autoregressive distribution when returned blocks are repeatedly appended.The argument uses the updated context as the starting point for the next round.Source: §A.1 · p. 13

A.2 EXIT PARTITION, PROBABILITY CONSERVATION, AND TARGET COVERAGE

  • Target continuations partition by their deepest matching tree node, with exit probability w(v) = P(v)ρ(v) at node v.The exit events are disjoint and exhaustive; target probability reaching a node either exits there or continues through a drafted child.Source: §A.2 · pp. 13–14

A.3 PROOF OF THE FIXED-TREE CEILING AND CANONICAL SATURATION

For a fixed realized tree, exact path verifiers are bounded by target coverage, and saturation fixes their accepted-path and bonus-token law. Two representative exact verifiers attain that bound, while the result concerns a different stage from HSD's sampled-chain verification.

A.3 PROOF OF THE FIXED-TREE CEILING AND CANONICAL SATURATION

  • Any exact path verifier has expected output-block length at most one plus target coverage of the fixed tree.The proof bounds acceptance of each non-root node by its target prefix probability; equality at every node gives saturation.Source: §A.3 · pp. 14–15
  • At saturation, every verifier induces the target exit-node law and the corresponding bonus-token distribution at internal nodes and leaves.The accepted block consists of the path to the exit node followed by the target token immediately after that path.Source: §A.3 · p. 15

A.4.1 PREDRAW-AND-FOLLOW

  • Predraw-and-follow is exact and saturated: its exit probability at v is w(v), and its expected output-block length is one plus target coverage.It independently draws a target token at each visited node, follows a matching child, and otherwise exits with that draw as the bonus token.Source: §A.4.1 · p. 15

A.4.2 EXACT SEQUENTIAL RESIDUAL VERIFICATION

  • Sequential residual verification is also exact and saturated, with a local transition kernel independent of child-testing order.Its expected output-block length is one plus target coverage, matching the target-induced accepted-path and bonus-token law.Source: §A.4.2 · p. 16

A.5 WHY THE FIXED-TREE RESULT DOES NOT CONTRADICT HSD

  • The fixed-tree ceiling conditions on an already realized tree, whereas HSD studies verification of a sampled draft chain; the results address different stages.For a fixed tree, verification cannot accept draft tokens absent from that tree.Source: §A.5 · p. 17

B.1 PROOF OF EXACTNESS AND SATURATION OF TEV

The appendix establishes that TEV realizes the target-induced exit and bonus-token law and attains the fixed-tree ceiling. It also gives a budget caveat for one-step coverage gains, an efficient loss evaluation, and verifier-stage latency results.

B.1 PROOF OF EXACTNESS AND SATURATION OF TEV

  • TEV uses the target-induced exit and bonus-token distributions, satisfying non-anticipating exactness and attaining the fixed-tree ceiling.The output length is the exit-node depth plus one, and the construction also applies when conditioning on a realized random tree.Source: §B.1 · pp. 17–18

C.1 ONE-STEP TARGET-COVERAGE GAIN

  • A one-step target-coverage gain is gross: a budget-preserving tree update may also need to remove another node.The stated gain is before enforcing the fixed tree budget.Source: §C.1 · p. 18

C.2 EFFICIENT EVALUATION OF THE EXIT-GUIDED LOSS

  • The exit-guided loss reuses one log-normalizer per distinct draft-logit row and gathers selected-token logits instead of materializing a vocabulary distribution for every tree node.The position-wise draft-logit row is shared by nodes at the same depth within a training example and is not conditioned on each node's parent path.Source: §C.2 · p. 18

D.1 VERIFIER-STAGE EFFICIENCY

  • At T = 0.6, TEV cuts verifier-stage latency by 12.9%, 15.2%, and 24.3% at budgets 32, 64, and 128; at T = 1.0, reductions are 12.0%, 14.0%, and 17.1%.The comparison holds the drafter, builder, and realized tree fixed and excludes the shared target-model forward pass; the measured stage includes verifier decisions and cache commit.Source: Table 3 · p. 19, §D.1 · p. 19

D.2 CROSSED DRAFTER–VERIFIER EVALUATION

In the crossed evaluation, changing the drafter produces larger reported gains than changing the verifier; ExitTrain's advantage also persists across inference budgets without budget-specific retraining.

D.2 CROSSED DRAFTER–VERIFIER EVALUATION

  • With Predraw, ExitTrain raises average τ by 13.7% and SR by 12.1%; with TEV, the gains are 13.7% and 12.5%.At fixed drafter, Predraw and TEV differ by at most 0.03 tokens in empirical τ; the comparison fixes the DDTree builder and B = 64 budget at T = 1.Source: §D.2 · pp. 19–20

D.3 TREE-BUDGET ROBUSTNESS

  • Across budgets 32, 64, and 128, ExitTrain + TEV beats DDTree by 11.6%–13.8% in τ and 11.4%–12.9% in SR, without budget-specific retraining.The drafter was trained at B = 64 and evaluated at all three inference budgets.Source: §D.3 · pp. 20–21, Table 5 · p. 20

Related papers

Loading 2610.11750v1…