PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding Target Probability Reuse in Speculative Decoding

Jungseob Lee, Giyoon Jang, Chailin Nam, Jiwoo Kum, Sihyeon Lee, Kyojun Choo, Jihun Song, Eunseo Song, Chanjun Park

arXiv:2610.29210v1cs.CL

TL;DR

Speculative decoding verifies draft-token trees in parallel, but the next tree must be selected before verification reveals target probabilities, even when previous passes computed distributions at candidate prefixes. This paper characterizes exact reuse of those rows and evaluates row-based selection, finding improved acceptance and faster decoding under the reported overlap setting.

  • Problem

    Tree selection generally precedes verification’s revelation of target probabilities, although previous passes may already have computed distributions at candidate prefixes.

    Source: §1 · p. 1

  • Method

    The paper characterizes when a prior row at the next round’s complete context permits exact reuse and evaluates reranking or drawing the first token from a separately computed root row for tree selection.

    Source: §1 · p. 1, §6 · p. 8

  • Results

    A separately computed root row improves expected acceptance over draft ranking, root-draw improves on pruning at equal mean tree size, and both rules decode faster when the separate pass overlaps standalone drafting.

    Source: §6 · p. 8

  • Takeaways & Limitations

    Making target probabilities available before tree allocation can improve speculative-decoding efficiency within the evaluated settings.

    Source: §6 · p. 8

    Acceptance experiments use six targets with public EAGLE-3 drafters and recorded target rows, while timing is for batch-one decoding with a standalone drafter on a second RTX A6000 GPU.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Speculative decoding uses a target model to verify a tree of draft tokens in parallel. We study whether the resulting next-token distributions can help select the next tree. For unrestricted target models, we show that guaranteed exact reuse requires a distribution computed at the next round's complete context. We characterize when retaining this distribution requires sacrificing accepted tokens and establish conditions under which this loss persists across decoding rounds. Across six targets, we find that reranking first-token branches with a separately computed distribution at the current context improves expected acceptance over draft ranking, especially with small tree budgets. Drawing the first token from this distribution before allocating the tree further improves expected acceptance over pruning a preselected tree, even at equal mean tree size. In our experiments, both selection rules also decode faster than draft ranking when the separate target pass overlaps standalone drafting. Our findings show that making target probabilities available before tree allocation can improve the efficiency of speculative decoding. Our code is available at https://github.com/js-lee-AI/TargetRows.

1 Introduction

Tree-based speculative decoding must choose branches within a node budget before verification reveals target probabilities, although prior passes may already have computed distributions at candidate prefixes. The paper characterizes when those rows can be reused exactly and how reuse relates to accepted tokens, then evaluates row-based tree selection.

1 Introduction

  • Tree-based speculative decoding verifies candidate branches in parallel, but fixed node budgets require choosing which branches to retain before target probabilities are revealed; prior passes may already contain rows at candidate prefixes.Source: §1 · p. 1
  • For an unrestricted target, guaranteed exact reuse requires a row computed at the next round’s complete context, or address; matching only the final token is insufficient.Two addresses can end in the same token while containing different preceding tokens.Source: §1 · p. 1
  • When a pass scores only its candidate tree, exact address coverage occurs precisely when the accepted path plus continuation remains inside the tree, costing at least one accepted token versus exhaustive traversal on the same target-token sequence.This trade-off is stated for rounds that accept one tree path, emit one continuation token, and preserve the target distribution for each chosen tree.Source: §1 · p. 2
  • Scoring prefixes beyond the candidate tree can cover the next root even after exhaustive traversal, while adding those prefixes as candidates would let traversal accept one more token on covered rounds.Source: §1 · p. 2
  • For the stated verifier class, a one-pass decoder using target information only along its emitted path can be matched by one that never covers the next root, scores no more prefixes, and emits at least as many tokens after every round.This is a run-level comparison.Source: §1 · p. 2
  • Reranking first-token branches with a separately computed root row increases expected accepted draft tokens over draft ranking, especially for small trees and when draft and target most-likely first tokens differ.The experiments cover six targets, seven task types, and two decoding temperatures.Source: §1 · p. 2
  • Root-draw selection improves expected acceptance over pruning a preselected tree at equal mean tree size, and both selection rules decode faster than draft ranking when the separate pass overlaps standalone drafting.The timing condition is standalone drafting on a second GPU.Source: §1 · p. 2

2 Related Work

Related work spans speculative verification, target-information reuse, and adaptive or pipelined compute allocation. This paper distinguishes its focus as exact next-address row availability and its value for tree selection.

2 Related Work

3 Setting and Reuse Criterion

The setting models each decoding round as a target and drafter sharing committed context while the drafter supplies a finite candidate trie and a target pass scores selected prefixes. Exact address coverage identifies when a scored row is the next round’s root distribution.

3 Setting and Reuse Criterion

  • At each round, target p and drafter q share committed context, and the drafter selects a finite prefix-closed candidate trie with at most B non-root nodes.Each node represents a token sequence appended to the committed context; siblings with the same token are merged.Source: §3 · p. 3
  • A target pass scores a set of prefixes that may extend beyond the candidate trie and computes rows at those prefixes.Source: §3 · p. 3
  • The next committed context appends the accepted draft-token sequence and the single continuation token to the current context.Source: §3 · p. 3
  • A round has exact address coverage when the accepted path plus continuation was scored; that row then equals the next round’s root distribution.Without coverage, rows from the pass cannot guarantee exact recovery for an unrestricted target, since two targets may agree on those rows but differ at the next root.Source: §3 · p. 3
  • Path-aligned verification accepts only a root path, with conditional exactness requiring the target law given the tree and prior history, and marginal exactness requiring it after averaging over tree selection.Source: §3 · p. 3

4 Coverage and Verification

Section 4 characterizes when a verification pass covers the next root and the acceptance cost of that coverage, then shows how retained rows can guide tree selection without changing the target law under suitable conditions.

4.1 Exhaustive traversal and early stopping

  • When the scored set is the candidate trie, coverage occurs exactly when the accepted path plus continuation stays inside the trie, and positive coverage entails strictly lower expected acceptance.Exhaustive target sampling has zero coverage; on covered rounds it could have accepted at least one more token.Source: §4.1 · p. 3
  • Scoring a frontier outside the trie covers the next root exactly when the first exit prefix lies there; exhaustive traversal of the expanded trie accepts one more token on covered rounds.Rejection-based verifiers with Q = T never cover the next root because rejected children retain zero probability in later residual distributions.Source: §4.1 · pp. 3–4
  • Under the theorem’s path-alignment, exactness, and selection-input conditions, a comparator is never covered, scores no more prefixes, and emits at least as many tokens after each round.It emits more after the original decoder’s covered rounds.Source: §4.1 · p. 4
  • The comparison extends to decoders using off-path target outputs only when the cache attention mask permits scoring branches that diverge within the comparator’s emitted context.Source: §4.1 · p. 4

4.2 Adaptive selection preserves exactness

  • Retained rows may guide adaptive tree selection without changing the target law when verification remains conditionally exact and selection does not use future verifier draws.The verifier must preserve the target conditional at every emitted prefix; sampling directly from a row at another address can change the output distribution.Source: §4.2 · p. 4

5 Experiments

Across six targets and seven task types, root selection improves expected acceptance over draft ranking, while root-draw selection further improves acceptance over pruning a preselected tree. The experiments also examine when target rows can be reused, the coverage trade-off, and speed under a measured deployment setup.

5.1 Setup

  • The evaluation uses six targets with public EAGLE-3 drafters and 644 prompts across seven task types, under a default 256-token limit.The setup includes greedy decoding and untruncated sampling at temperature 1; trees are grown from 710 candidates and draft selection keeps 59 non-root candidates.Source: §5.1 · p. 4

5.2 Coverage on EAGLE-3 trees

  • With only the candidate tree scored, exhaustive traversal provides no coverage; obtaining coverage through extra scoring can sacrifice a token that could extend the accepted path.Sampled-leaf stopping accepts one fewer token than exhaustive traversal on covered rounds.Source: Table 1 · p. 5, §5.2 · p. 6

5.3 Rows at matched addresses

  • Rows at matched complete addresses closely match the next root row, with mean total variation below 0.01 in every run; final-token-only matches have mean total variation of 0.38–0.47.Address-matched variation is comparable to evaluating the same row in batches of different sizes.Source: §5.3 · p. 6

5.4 Value of exact rows for tree selection

  • Across six targets, seven task types, and two temperatures, root selection improves acceptance especially when draft and target most-probable first tokens differ.Gains remain positive under equal task or prompt weighting, and persist beyond the default output limit with all 95% intervals above zero.Source: §5.4 · pp. 7–8
  • Root-draw selection yields higher expected acceptance than pruning a preselected tree, including at equal mean verified tree size.At a 59-node root-draw cap, it improves expected acceptance by up to 2.4% over an enlarged baseline; online, it exceeds PEARL-style decoding on all six targets at both temperatures.Source: §5.4 · p. 7
  • Root-draw selection decodes up to 2.2% faster than PEARL-style decoding while verifying at least as many nodes on average.The comparison uses root-draw caps of 40–43 and a PEARL-style cap of 59; with standalone drafters on a second GPU, the root pass finishes during drafting.Source: §5.4 · p. 7, Figure 4 · p. 8
  • At B = 59, root selection improves expected acceptance over draft ranking by up to 8.0%, with larger gains at 8 nodes.Under greedy decoding, root selection cannot shorten the accepted path relative to draft selection.Source: §5.4 · p. 6, Table 6 · p. 8

5.5 Rows at other addresses

  • Rows from other addresses improve acceptance when used as learned reranker features, but direct substitution of those rows for the first draft factor lowers acceptance.Rows beats both draft ranking and the Base reranker for every evaluated target, temperature, and budget; root selection performs better than either reranker.Source: §5.5 · p. 8

6 Conclusion

The paper characterizes when target rows can be reused and when obtaining next-root coverage costs accepted tokens. It also reports acceptance and speed gains from separately computing a root row for tree selection.

6 Conclusion

  • For path-aligned, conditionally exact verification with one continuation, avoiding next-root coverage can score no more prefixes and emit at least as many tokens after every round.The result applies when each round uses one target pass and target information only along its emitted path.Source: §6 · p. 8
  • A separately computed root row improves expected acceptance over draft ranking, especially when draft and target favor different first tokens.Drawing the first token before allocating the tree also beats pruning a preselected tree at equal mean verified tree size.Source: §6 · p. 8
  • In the measured deployment, both selection rules decode faster than draft selection when the separate target pass overlaps standalone drafting on a second GPU.The paper motivates evaluating the cost of obtaining target rows alongside the tree-selection gains.Source: §6 · p. 8

Limitations

The paper states boundaries on both its acceptance study and its coverage result.

Limitations

  • The acceptance study covers six targets with public EAGLE-3 drafters and recorded target rows.This describes the evaluated models and rows, not a claim about other target or drafter settings.Source: Limitations · p. 9
  • Timing results are limited to batch-one decoding with a standalone drafter on a second RTX A6000 GPU, where drafting outlasts the separate target pass.Source: Limitations · p. 9
  • The coverage identity assumes path-aligned, conditionally exact verification with one continuation and identical scored and candidate sets.Its run-level comparison uses target information on the emitted path; an extension to off-path outputs under a suitable cache attention mask is described in Appendix A.7.Source: Limitations · p. 9

Ethics Statement

The ethics statement describes the study’s data and decoding scope.

Ethics Statement

  • The experiments analyze model probabilities on public Spec-Bench and HumanEval prompts, whose models and datasets retain their licenses and usage restrictions.The studied selection rules preserve the target’s output distribution and change only how many tokens a round emits.Source: Ethics Statement · p. 9

A Proofs and Scope

The proofs distinguish exact row recovery from merely matching a token, and characterize how coverage relates to accepted tokens. They extend this analysis to scored frontiers, adaptive selection, and decoding across rounds.

A.1 Cache-only recovery

  • For an unrestricted target, finitely many queried rows cannot guarantee recovery at an unqueried address because targets can agree on all queried rows yet differ there.Additional structure or a learned approximation can help, but token matching alone does not guarantee exact reuse.Source: §A.1 · p. 11

A.2 Fixed-tree ceiling and coverage identity

  • With the scored set equal to the candidate trie, coverage occurs exactly when the continuation remains inside the trie, and the extra accepted path length is positive exactly when coverage has positive probability.This result assumes path alignment, conditional exactness given the tree, and one emitted continuation.Source: §A.2 · p. 12

A.3 Scored frontier

  • When scored prefixes extend beyond the candidate trie, coverage occurs when the first exit prefix lies in the scored frontier.The frontier consists of scored prefixes outside the trie whose parents lie inside it; enlarging the trie by this frontier adds one accepted token exactly on coverage.Source: §A.3 · p. 12

A.4 Rejection-based verifiers

  • Rejection-based verifiers that score only the trie never score the next root, although they need not be conditionally exact given the tree.After a rejection, the rejected child has zero mass under later residual rows; a continuation at a leaf also exits the trie.Source: §A.4 · p. 12

A.5 Adaptive selection

  • Adaptive tree selection preserves the target autoregressive law at any fixed horizon when token-level conditionals are exact, even if round boundaries depend on token values.The proof conditions on emitted history and the information used to select the current tree.Source: §A.5 · pp. 12–13

A.6 A row at the wrong branch

  • Exactness of each scored row at its own address does not ensure exactness when a sequence uses rows from the wrong branch.In the example, the assembled sequence is abb while autoregressive decoding emits aba.Source: §A.6 · p. 13

A.7 Covering over a run

  • Across rounds, a comparator can avoid coverage while emitting at least as many tokens after every round, using no more scored prefixes and preserving the target law.The construction uses exhaustive traversal and available target outputs; after a covered round, its emitted length is strictly larger.Source: §A.7 · p. 13

B.1 Stopping placement and row cost

The stopping rule affects both the chance of retaining a next-root row and the accepted path length. In the uniform binary example, rules with equal coverage can leave different amounts of unused path length.

B.1 Stopping placement and row cost

  • With eight scored rows, exhaustive traversal has zero coverage and expected acceptance 2; cap 1 has coverage 3/4 and acceptance 1, sampled-leaf stopping has coverage 3/4 and acceptance 5/4, and cap 2 has coverage 1/4 and acceptance 7/4.The corresponding shortfalls are 1, 3/4, and 1/4 for cap 1, sampled-leaf stopping, and cap 2.Source: §B.1 · p. 14
  • Cap 1 and sampled-leaf stopping have equal coverage, but cap 1 leaves two accepted tokens unused on one covered path and one on the others.Sampled-leaf stopping instead leaves one token unused at each covered endpoint.Source: §B.1 · p. 14
  • Scoring the frontier prefix b beyond the candidate trie gives coverage 1/2 and expected acceptance 1, versus zero coverage when only the trie is scored.The added token is accepted exactly in covered rounds.Source: §B.1 · p. 14

C Measurement Protocol

The measurement protocol evaluates EAGLE-3 trees across targets, tasks, and decoding settings, with replay used to compare retained rows against next-round root rows. The reported acceptance comparison favors root-based selection over draft selection, with larger gains at the smaller budget.

C Measurement Protocol

  • The runs use target-specific chat templates and prompts from Spec-Bench and HumanEval, and stop at EOS or the output limit.The twelve default-length runs contain 365,922 verification rounds; the default output limit is 264 tokens.Source: C Measurement Protocol · p. 14
  • Each round scores the root, verified tree, expanded nodes, and 160 highest-ranked candidates, retaining the emitted-address row when scored and up to 24 other eligible rows.Retained rows are compared with the next-round root row at the complete emitted context; replayed root rows match recorded rows on the same GPU type in nine runs.Source: C Measurement Protocol · p. 16
  • At B = 59, EAGLE-3’s expected acceptance on recorded rounds lies within the 95% prompt-bootstrap interval of the online decoder’s realized acceptance in every run.The relative difference is at most 1.1%.Source: C Measurement Protocol · p. 16

D.1 Acceptance length

  • At B = 8, root selection’s gain over draft selection in emitted tokens is 6.1% to 14.2%, compared with 2.3% to 5.5% at B = 59.Root-draw selection’s gain over the PEARL-style decoder is 7.7% to 9.0% at B = 8 and 2.9% to 4.9% at B = 59.Source: §D.1 · p. 16

D.2 Selection values with intervals

Root-draw selection improves expected acceptance over a PEARL-style decoder and retains an advantage after mean tree sizes are matched. Root selection also reaches draft selection’s value with fewer nodes in the reported B = 8 comparison.

D.2 Selection values with intervals

  • At B = 8, draft selection needs 11 to 22 nodes to reach root selection’s value, while root selection reaches draft selection’s value with 4 to 7 nodes.The search is conducted within the same candidate pool and repeated in each resample.Source: §D.2 · p. 18
  • Under the same node cap, root-draw selection improves expected acceptance over the PEARL-style decoder by up to 14.2% at B = 8 and 7.0% at B = 59.All confidence intervals lie above zero; root-draw selection also retains larger trees on average.Source: §D.2 · pp. 18–19
  • The root-draw value is below the PEARL-style value in every run for the variant that keeps the drafter’s top first token, with the gap ranging from 0.5% to 1.5% at B = 8 and 6.7% to 9.1% at B = 59.Every interval excludes zero.Source: §D.2 · p. 19
  • After mean tree sizes are matched, root-draw selection improves expected acceptance by up to 4.8% at B = 8 and 2.4% at B = 59.Every confidence interval remains above zero when matching is repeated in each resample.Source: §D.2 · p. 19

D.3 Online decoding

Online decoding evaluations examine how target-row-based selection and reuse affect acceptance and speed across budgets and decoding conditions. They cover row availability and coverage, as well as pipelined root-draw selection at matched tree sizes.

D.3 Online decoding

  • At temperature 1, root selection improved expected acceptance over draft ranking by 3.0% to 7.5% across the six targets, with every interval above 2.8%.Root-draw selection also gained 10.7% to 13.7% over the PEARL-style decoder at an 8-node cap, with every interval above 9.8%.Source: §D.3 · pp. 20–21, Table 14 · p. 21, Table 17 · p. 22

D.4 Tasks, weighting and targets

  • Prompt-weighted root gains were 2.9% to 7.9% at B = 59 and 8.6% to 23.4% at B = 8, with every interval above zero.Every task interval for root and root-draw gains was above zero at both budgets.Source: §D.4 · p. 21

D.5 Longer outputs

  • Under a 1,024-token limit, whole-output root-selection gains stayed within 0.3 percentage points of default-length runs at B = 59 and within 1.1 at B = 8.Root-draw selection also improved late-round expected acceptance over draft ranking at both budgets, with no interval below 3.4%.Source: §D.5 · p. 22

D.6 Pool size

  • At B = 59, the oracle advantage grew from 0.12 to 0.19 tokens at M = 100 to 0.33 to 0.39 at M = 710, while root selection recovered 44% to 67% at M = 100.These results concern restricting each rule to the M highest-ranked pool candidates.Source: §D.6 · p. 22

D.7 First-token agreement

  • At B = 59, rows through depth two recovered 45% to 62% of the oracle advantage when first tokens agreed, while rounds with differing first tokens carried a larger share of root gain.In the upper two root-entropy quintiles, rounds carried 1.6 to 12.8 times the gain of the lower two.Source: §D.7 · pp. 22–23

D.8 Calibrated and reranked draft scores; D.12 Rows at other addresses

  • The reranker recovered at most 29% of the root gain at B = 8 and 33% at B = 59, but its gains over draft selection and a no-row reranker had intervals above zero.By contrast, direct substitution of rows from other addresses lowered acceptance in all tested variants; cache-row mixtures had no consistently positive gain.Source: §D.8 · p. 25, §D.12 · p. 27

D.9 Coverage from the scored frontier; D.10 Selection with reused rows

  • A candidate set covered 12% to 17% of next roots, versus 28% to 35% for the complete frontier of 380 to 418 candidates on average, matching the whole pool’s share.Root selection raised expected acceptance over draft ranking by 0.5% to 0.9% at B = 59 and 4.9% to 10.1% at B = 8 when verification scored the 100 highest-ranked candidates. The covering decoder emitted fewer tokens per target pass at both budgets.Source: §D.9 · p. 26, §D.10 · p. 27

D.13 Standalone drafters; D.11 Token and address matches

  • At B = 59, the root row recovers 35% to 57% of the oracle’s advantage; against a PEARL-style decoder enlarged to equal mean tree sizes in each run, root-draw selection gains 0.5% to 1.3%.Matched pairs have median total variation below 0.0004 in every run. Accepted-path token-only rows have mean total variation of 0.72 to 0.79 from the next root row.Source: §D.11 · p. 27, §D.13 · p. 28

D.14 Pipelined decoding

  • Root-draw selection and root selection draw the first token from a one-token target pass run while the drafter works, then verify their trees; draft selection waits for the pool.When the drawn token is absent from the tree’s first level, in 1.2% to 8.4% of rounds at B = 59, it becomes the continuation and the second pass is skipped.Source: §D.14 · p. 28
  • At matched tree sizes, root-draw selection is 1.3% to 2.2% faster and has 1.1% to 2.5% higher expected acceptance than the PEARL-style decoder, while verifying at least as many nodes on average.The comparison uses caps of 40 to 43 nodes, chosen to match mean expected tree size at B = 59.Source: Table 29 · p. 29, §D.14 · p. 29
  • At B = 59, root selection is 3.2% to 6.2% faster than draft selection, root-draw selection 3.5% to 9.6% faster, and the PEARL-style decoder 4.3% to 8.3% faster.No lower end of these intervals falls below 2.7%.Source: §D.14 · p. 29
  • At B = 8, root selection is 9.6% to 17.3% faster than draft selection, while root-draw selection and the PEARL-style decoder also have speed-gain intervals excluding zero.Table 28 reports those latter gains with 95% prompt-bootstrap intervals.Source: §D.14 · p. 29, Table 28 · p. 29
  • At B = 59, root-draw selection’s trees average 16 to 18 more nodes than the PEARL-style decoder’s, while enlarging the latter to equal mean size exceeds the largest captured CUDA graph in 45% to 51% of rounds.At B = 8, root-draw selection’s trees average 1.4 to 2.0 more nodes.Source: §D.14 · p. 29

Related papers

Loading 2610.29210v1…