Traversal Verification for Speculative Tree Decoding
Authors: Yepeng Weng
Qiao Hu
Xujie Chen
Li Liu
Dianwen Mei
Huishi Qiu
Jiang Tian
zhongchao shi
Venue: NeurIPS 2025 poster ()
Keywords: Large Language model (LLM)
speculative decoding
acceleration
Primary area: deep_learning

Abstract: Speculative decoding is a promising approach for accelerating large language models. The primary idea is to use a lightweight draft model to speculate the output of the target model for multiple subsequent timesteps, and then verify them in parallel to determine whether the drafted tokens should be accepted or rejected. To enhance acceptance rates, existing frameworks typically construct token trees containing multiple candidates in each timestep. However, their reliance on token-level verification mechanisms introduces two critical limitations: First, the probability distribution of a sequence differs from that of individual tokens, leading to suboptimal acceptance length. Second, current verification schemes begin from the root node and proceed layer by layer in a top-down manner. Once a parent node is rejected, all its child nodes should be discarded, resulting in inefficient utilization of speculative candidates. This paper introduces Traversal Verification, a novel speculative decoding algorithm that fundamentally rethinks the verification paradigm through leaf-to-root traversal. Our approach considers the acceptance of the entire token sequence from the current node to the root, and preserves potentially valid subsequences that would be prematurely discarded by existing methods. We theoretically prove that the probability distribution obtained through Traversal Verification is identical to that of the target model, guaranteeing lossless inference while achieving substantial acceleration gains. Experimental results on various models and multiple tasks demonstrate that our method consistently improves acceptance length and throughput over token-level verification.

Traversal Verification for Speculative Tree Decoding
Yepeng Weng'*
Qiao Hu Xujie Chen
Li Liu' Zhongchao Shi'
Dianwen Mei'
Huishi Qiu' Jiang Tian'
'Lenovo AI Technology Center, Lenovo
2 National Center for Mathematics and Interdisciplinary Sciences (NCMIS), AMSS, CAS
Abstract
Speculative decoding is promising approach for accelerating large language models. The primary idea is to use lightweight draft model to speculate the output of the target model for multiple subsequent timesteps. and then verify them in parallel to determine whether the drafted tokens should be accepted or rejected. To enhance acceptance rates, existing frameworks typically construct token trees containing multiple candidates in each timestep. However, their reliance token-level verification mechanisms introduces two critical limitations: First, the probability distribution of a sequence differs from that of individual tokens, leading suboptimal acceptance length. Second, current verification schemes begin from the root node and proceed layer by layer in a top-down manner. Once a parent node rejected, all its child nodes should be discarded, resulting in inefficient utilization of speculative candidates. This paper introduces Traversal Verification, novel speculative decoding algorithm that fundamentally rethinks the verification paradigm through leaf-to-root traversal. Our approach considers the acceptance of the entire token sequence from the current node the root, and preserves potentially valid subsequences that would be prematurely discarded by existing methods. We theoretically prove that the probability distribution obtained through Traversal Verification is identical to that of the target model, guaranteeing lossless inference while achieving substantial acceleration gains. Experimental results various models and multiple tasks demonstrate that our method consistently improves acceptance length and throughput over token-level verification.
Introduction
Large Language Models (LLMss have been widely adopted due their exceptional performance across various natural language processing tasks [10 23 34] However, the massive parameters and
the autoregressive generation scheme of transformer decoder-only (30) LLMs limit the generation speed. Speculative decoding [19 3 is an lossless acceleration technique which employs lightweight model (draft model) with fewer parameters to speculate the output tokens of the original LLM (target model) for several future timesteps, then feed the drafted tokens into the target model in parallel. After getting the probability distribution of the target model, speculative decoding determines the acceptance rejection of each token based on their probabilities in both target and draft models. If token rejected, a new token will be resampled and all subsequent tokens should be discarded.
To further improve acceleration performance, existing methods 23 candidates each drafting timestep, forming tree of drafted tokens. However, these methods generally inherit the token-level verification mechanism from vanilla speculative decoding to tree scenarios, resulting in suboptimal acceptance lengths in tree decoding. To be more specific, firstly,
14 35
generate multiple
'Equal contribution. Contact: wengypl lenovo.com, lugiao2020@amsss. a0t.0200000mmmsc.mmmm CCoresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the probability distribution of token sequence differs from that of an individual token. Vanilla speculative decoding determines acceptance based on per-token probabilities, which sacrifices global optimality for sequence-level acceptance. Secondly, existing tree decoding methods start verification from the root node of the tree, and proceed layer by layer in a top-down manner. Once a parent node is rejected, all its child nodes will be discarded accordingly, resulting in the wasting of drafted tokens.
To address these issues, we propose a novel speculative decoding method named Traversal Verification. Unlike existing methods, Traversal Verification starts from the leaf node and generally operates in bottom-up manner. the node is accepted, the entire sequence from the current node the root is accepted. If rejected, the algorithm proceeds to verify the sibling nodes (or the deepest child nodes of its siblings they exist). If all siblings are rejected, backtracks the parent node. This process repeats until either a node is accepted or all nodes in the tree are rejected.
Through Traversal Verification, we effectively resolve the limitations of existing methods. First, we consider sequence-level probabilities instead of individual token probabilities and improve the acceptance lengths. Second, in Traversal Verification, parent node will be verified only after all its child nodes have been rejected, which minimizes the wasting of drafted candidates.
We conducted experiments on Llama3 [10] series and Llama2 [29] using various tree structures. The experiments were performed on the Spec-Bench dataset [32], which encompasses six different tasks: multi-ture conversation, translation, summarization, question answering, mathematical reasoning, and retrieval-auge -uggennte generation. Experimental results demonstrate that Traversal Verification consistently outperforms existing decoding methods by 2.2%-5.7%% in average acceptance length across diverse tasks with different tree architectures. Additionally, Traversal Verification could potentially achieve greater improvements for deeper and larger decoding trees.
We highlight the advantages of Traversal Verification as follows:
1. Full utilization of drafted tokens. Traversal Verification enhances acceptance length and improves the utilization of drafted tokens by considering sequence-lever probability distributions and systematically traversing nodes in the token tree. To our knowledge, is the first verification algorithm that makes use of the whole token tree.
2. Reliable generation quality. We theoretically prove that Traversal Verification a lossless verification algorithm, that is, the output distribution is identical to that of the target model. This serves as a powerful guarantee of generation quality.
3. Pronounced improvement. Experiments across various tree structures and datasets shows that Traversal Verification outperforms token-level verification. We also rigorously prove that Traversal Verification sheoretically optimal in the case single chain.
4. Minimal implementation modification. Traversal Verification serves plag-and-play replacement of existing verification methods. There is no need to change other parts of existing speculative decoding pipelines.
2 Preliminaries
2.1 Speculative Decoding
Speculative decoding. also known as speculative sampling [19 3) is a lossless LLM acceleration algorithm. In speculative decoding. a draft model first generates chain of new tokens (i.e., token per timestep for the next 7 timesteps). then the drafted tokens are fed into the target model in parallel to get the target distribution.
Algorithm 1 Single-token verification
Input: Prefix Xo; draft token X; draft dis- tribution M- target distributions Mo(-Ix) and MM
1: Sample 77 U UO0 1).
We denote the drafted token chain by a² (on, (),,..,,,,)... 27), where og represents the pre- fix and a>o == (aI...., a.)) denotes the y new tokens generated by the draft model. After ob-
2: if n Ma(XiXa)
(x(X then
3: Sample from Mo(-|Xo. X).
4: Return: X,Y.
5:
else
taining the target distribution Ms. the drafted
6: Sample Y from norm M,.+).
tokens will be verified from timestep 1 to y fol- lowing Algorithm
7: Return: Y.
8: end if

---

M
b
Root
M
0.6
0.3
0.1
0.3
0.3
0
0
X2
Layer 1
b 0.4
0.1
0.3
0
c 0.3
0.2
0.1
X2
X
X
Lager 2
Table An example of single-token verification
Figure 1: An example token tree
If a token is accepted, the verification proceeds to the next timestep. Once a token is rejected, all subsequent tokens in the chain are discarded, and a new token will be resampled at the rejection position based on the residual probability distribution. If all y tokens are accepted, an additional token sampled from the target distribution at the timestep ? 1. The output of ttrattng-verificuue cycle thus consists of all accepted tokens plus the resampled or newly sampled token at the final step.
To illustrate the acceptance mechanism intuitively, consider simplified example with vocabulary of three tokens: [a. b, c]. Let the target model's probability distribution be Ma = [0.3. 0.4, 0.3), and the draft model's distribution be M, [0.6, 0.3, 0.1]. All possible cases summarized in Table 1
According to Algorithm]] 1 token is sampled, it will be accepted directly because Ma. > MM)
Similarly, will be accepted if sampled. If a is sampled, the acceptance probability is Ms(a)
M, = 0.5.
Thus, the probability of generating token a is Pssampl a) x P(accept a) = 0.3, which is equal to Mj(a). These cases correspond to the diagonal entries in Table [ highlighted in green.
Besides being accepted, token also faces rejection probability of 0.5. Upon rejection, new token is resampled from the residual probability distribution norm([M, - -M,]+).. Specifically, we subtract M, from M, and set the negative values to zero (yielding [0, 0.1, in this example), and then normalize the residual probabilities. Therefore, the final probabilities for b and c consist of two parts: 1) direct acceptance after sampling from M, and 2) resampling after rejection of a, indicated in cyan in Table I By this means, the final distribution is kept identical to Ma-
2.2 Recursive Rejection Sampling
Recursive Rejection Sampling (RRS) samples multiple candidates at each timestep and recursively verifies them, as described in Algorithm@ Recent works 21 without replacement (RRSw), where the probability of a rejected token in M, is set to zero, and then normalize M, of the remaining candidates. RRSw prevents repeated sampling and rejection of the same token, especially for low-temperature situations, thereby improving overall acceptance rates.
14 351 further refine RRS into RRS
We illustrate RRSw using the same example in Table [] Suppose that token is sam- pled and rejected. The residual distribution becomes M¹, = no
Algorithm 2 Recursive Rejection Sampling
Input: Prefix Xo: draft distribution M,) drafted candidates (X.), from Ma(-|Xp); target distributions Mb(1Ix)) and Mb(-IXo, X2), v1 & i & k.
.M,++)
1/3,2/3, while the new draft distribution M = norm(M,(a) = 0) = [0, 1/4]. Then sample new token from M', and repeat the speculative decoding scheme: If to- ken b sampled, it is accepted with probability (b( (2 = 4/9. c is sampled, it is always ac- cepted since (c) > (c).).. For scenarios with more candidates, this process iterates until all candidates are verified.
1: Initialize residual M' with Mo)(IXo) and draft
My with (-)o.
2: for i=l....kk do
3: Sample 7) ~ UO,
4: if M,(X)) then
M,(X))
5: Sample Y from Mo(.|Xo, X,).
Combining chain-based speculative decoding
6: Return: X, Y.
with multi-candidate per timestep yields tree decoding. In the current framework, candidate
7: else
8:
M nM, - Mc]+).
tokens are verified layer by layer from shallow to deep: if a node is rejected, we continue to verify its siblings; the current node itself and all its children are discarded. If node is accepted, the verification proceeds to its child nodes in the deeper layer.
9:
M + norm(M (X.) = 0) (if without
replacement)
10: end if
11: end for
12: Sample Y from Mí((-Xo).
13: Return: Y.
3

---

We demonstrate the token-level verification order using simplified two-layer decoding tree, as shown in Figure [I] In this tree, node X, is verified first. accepted. we proceed its children (X3 and X4) and verify them sequentially. If X1 is rejected, we discard X1, X3. X4, and go to X2- If X2 accepted, we continue verify X5, otherwise, since all the sampled tokens are rejected, we will resample new token from the residual probability distribution of Layer 1.
Method
In this section, we first introduce Traversal Verification. Subsequently, illustrate its distinctions from token-level tree decoding (vanilla speculative decoding with RRSw) through an intuitive example (see Figure 2 In the last part of this section, discuss the theoretical guarantees, such as the losslessness of Traversal Verification, and its optimality in single chain scenarios.
3.1 Traversal Verification
We present Traversal Verification in Algorithm
Algorithm 3 Traversal Verification
Input: Prefix Xo the root; valid sampling tree T on draft distribution M,; for all chains
Va (Xo,...,Xy,) C T, draft distributions vi < Yas .Ma(-I*)) and target distributions
& %a. %o. Ma I: Initialize: For all chains Va = (Xo....,XA, Xyr) T, let pir (Xn) 1 and then recursively set the acceptance rates for all nodes of o.,
MX Pa (Xi-1)
M. X 1
Pa
iné (X₂) = min
1EiE Ta-
2: Set P. (X,) pii (X:), VX, Ea, Va C T, and the acceptance length 0
3:
while T + do
4: Select (0,11) ().
(Xo.
xx,) C from root the first leaf node, with % being its depth.
5:
Sample 17
6:
if < Po (X then
7:
T= Ta and X = (Xo....,
8:
break.
9:
else
Delete the last node of a from the tree T, that is T - T {x }.
11:
Set the residual and draft distributions by [ and 22 i.e.,
M1(x|x>a-1) = norm 1)
(x norm (X -1-
0).
12:
Set P', (X -1) 33) and then modify
Pa (X (x +- (Xx=
Ma(a|X -M(x)-=-)))MM(aX(>-1- M,(x|X(a-1) MM,(s|X'>>)) Vo E X
13: Update the acceptance rates for remaining chains B = (Zo. Dzp) C with the starting nodes 7- = X
Mo M2(2; (xt))) pa(x;) = min (o((x)1)) M, (z; xx-1))1 1 %a Ei<
end if
15: end while
16: Sample from from.Ms( Mc(.IX*).
17: Return: X

---

Residual distribution in Algorithm
3 (Line 11): Vx X,
Po (X MM(r|X7001) - M
(3 Ex Pa (X,, -1) Mb(r|X
Modified draft distribution in Algorithm (Line 11): VI E X
Ma(x|X7a-1
M' XX and (2
Mc(X (xa-1] if + Xya (2)
Acceptance probability in Algorithm (Line 12):
En (X, Tu - Ma(x) Ma,
(x 2 Ex Mo(aa(Xu-1) (2x + Pa (Xaa
(3)
Traversal Verification exhibits two key distinctions from token-level tree decoding:
1. Bottom-up verification. Traversal Verification generally operates in bottom-up manner, starting verification from leaf nodes (i.e., deeper layers) and progressing toward the root, while token-level tree decoding follows top-down approach, verifying nodes layer by layer from shallow to deep. Details about traversal order are provided Appendix E
2. Sequence-level acceptance. Traversal Verification incorporates the joint probability dis- tribution of the token sequence, rather than relying solely on per-token probabilities. The acceptance rate each node represents the sequence-level acceptance rate from the current node to the root. Thus, once token is accepted, the entire sequence from the current node root accepted.
3.2
An Intuitive Example of Traversal Verification
We now demonstrate Traversal Verification using the same illustrative case as introduced in Scction Following Algorithm 3 for the tree structure in Figure 1 the traversal order is X3 Xa + X5 + X2. Consider tree with nodes sampled as [X1, X2, Na. Xx. X3] = [a, c. b, c, a] as an
2.2
intuitive example. We present the detailed process of Traversal Verification in Figure 2
Root
Rool X,
Rool X,
Root X
Root Xo
M, ce D3
If iffreected
rejected
ifrejected
rejected
X (p
X
Xs --1 11
0.5)
0.003)
01
-
0.607)
Figure 2: The traversal order verifying a sampling tree.
We define r(X,) = MM(X.a) M.(X,) for simplification. For the first chain X3, the acceptance rate of
Traversal Verification is
IPanversa (accept X1 = min (miin(((X),,))) () 1) 1) = min (0.5 0.4/0.3, 0.667, However, in token-level verification, the acceptance probability is only
Paccn-te X1X3) min(r(X,). . 1). minn((XX),,,).) 1) = 0.5.
When X,Xx 3 is rejected, we delete the node X3 and then the first chain becomes X, X4. According to Line 11-13 in Algorithm since 1p(Xx),Ms(( _M(aa) 0.05, the new p(()) and the acceptance rate of chain X4 are updated as
0 and (cc) MM,)))
0.05
p((x,) 0.05 + 0.5 0.091,
and
(accepp X1X1) = min ('((i) M1((,,,
1)
2 0.637.
My(Xx))
5

---

If X4 is rejected, the residual acceptance probability of X1, namely p' p'(),, is reduced to zero, indicating that cannot be accepted any more and should be removed immediately.
After node X1 is discarded, the draft and target distributions of token-level verification and Traversal Verification in Layer 1 return the starting line once again. Then for the single chain X Xs. Traversal Verification still expects longer acceptance than token-level verification (see Theorem 3.4.
3.3 Theoretical Guarantees
In this section, we formally establish the theoretical guarantees of Traversal Verification. Specifically, we prove that the following statements hold for Traversal Verification:
1. Traversal Verification is valid (i.e. lossless) tree verification algorithm, which means the probability distribution of output sequences is identical to that of the target model.
2. In the special where the sampling tree is a single chain, Traversal Verification achieves the optimal upper-bound of expectation of acceptance length.
We first formally define the decoding tree under autoregressive generation follows:
Definition 3.1 (Decoding tree under autoregressive generation). Let M, be given distribution and T be a decoding tree rooted at Xo under autoregressive generation. For all chains (Xo.... X C T where " denotes the depth of chain v, if all child nodes of v are generated according the conditional distribution MM(-lu) (with or without replacement), then the sampling free T is termed decoding tree based on M, under autoregressive generation.
For brevity, hereafter refer tree satisfying the above definition decoding tree.
Given an decoding tree T, we prove that Traversal Verification serves as valid tree verification algorithm. A valid tree verification algorithm is defined as follows:
Definition 3.2 (Valid tree verification algorithm). Let T be decoding tree defined as Definition 3.1 For all chains v == ........ Xx)) with depth "ia. a tree verification algorithm Aver takes the tree T, draft model distributions M,(+X*), Vi Yv and target model distributions M ti & Tto as inputs, and outputs an accept chain X = (Xo..... (Xo...,,X,) C. ' where T E max,cT "fu and an additional token Y.
The tree verification algorithm Aver is called valid if its output distribution satisfies
(XT,)) Aver Ms. Mo(-1Xo),
(4)
where Mo(Xo]Xo)=11
Additionally, the tree verification Aver is also called a valid chain verification algorithu if is a single chain and Aver satisfies
For example, SpecInfer 223 Theorem 4.2] is valid tree verification algorithm. In the case where the sampling tree degenerates into single chain, both the vanilla token verification [19] Appendix.A] and Block Verification [27 Theorem 1] are valid chain verifications.
We now claim that Traversal Verification is valid tree verification algorithm and is an optimal valid chain verification algorithm with being single chain.
Theorem 3.3 (Losslessness of Traversal Verification). Traversal Verification (Algorithm 3 is valid tree verification algorithmm.
Theorem 3.4. When the sampling reduces one single chain, for any valid chain verification algorithm VERIFY in Definition 3.2 let Nuaversal. NBlock and Nuerity be the number of accepted tokens Traversal Verification, Block Verification (27) and VERIFY, respectively, then for any given distributions Mg, and draft chain T, we have
[[Nuraversal] [[Nntkck] > E[Nuarity];
where E denotes the expectation taken over the randomness of draft chain T and internal random variables utilized within the verification algorithms.
Discussions on theoretical foundations and design motivation Traversal Verification. The core idea of proving the losslessness (Theorem 3.3 of Traversal Verification lies in exploiting its

---

self-similarity. The self- similaiiyy of Traversal Verification implies that, for any parent node A in the given sampling tree T. before determining the acceptance of A, all its descendant nodes have already been processed through the same traversal mechanism. In other words, every local subtree within the sampling tree 7 essentially operates as a scaled-down instance of the Traversal Verification mechanism. Consequently, we can employ mathematical induction on the number of descendant nodes to establish the critical Lemma A.2 from which Theorem 3.3 follows as a corollary.
(the lossless theorem) directly
For the single-chain optimality of Traversal Verification (Theorem 3.4 the key proof idea is to ensure that Traversal Verification achieves the highest possible acceptance probability at each node, aligning with Block Verification. Assume that the acceptance rate for a parent node is P(A). As bottom-up verification framework, the target probability distribution for child nodes of A should be P6 By introducing pseudo-child node with target probability (1 P(A)), we can apply RRSw to transport the draft distribution M, to the target distribution P(A)MM, combining with (1 - P(4)). We refer to the above process as the sequence-level RRSw method. Comprehensive
details are provided in Appendix [ This motivation directly leads to the formulations (-3 of Traversal Verification. Since Block Verification an optimal valid chain verification algorithm 127
Theorem 2], Traversal Verification inherits this optimality in the single-chain case (see Theorem
4 Experiments
4.1 Experimental Setup
Target LLMs and draft model. We mainly conduct experiments on the Llama3 [0] series, using Llama3,2-11 1--Ittuuttttt as the draft model and 1-8ma,,--BB-Instaae as the target model. We also include Llama-68M [23] with Llama2-7b 29] as the draft and target model, which is widely adopted
in existing speculative decoding researches
13 26
Tasks. We perform experiments on the Spec-Bench Bench dataset 32 which includes 80 instances from each of six distinct domains: multi-turn conversation (MT-Bench (36)) translation (WMT14
DE-EN (I), summarization (CNN/Daily Mail (24)), question answering (Natural Questions (18)
Mathematical reasoning (GSMSK (5) aaggeeell-uummented generation (DPR (6)).
Metrics. We evaluate the performance of our method using two metrics: acceptance length and token generation speed. Acceptance length is the number of tokens generated per caafting-verifiaation cycle, which reflects the theoretical performance of the verification method. We also include the actual throughput for a comprehensive comparison. It is worth noting that there may be slight variations in acceptance length according to differences in statistical methods, and we provide detailed discussions and additional experimental results on this issue in Appendix D
Implementation. For token-level tree verification, we adopt the RRSw implementation in EAGLE 21 from Spec-Bench 322 open source repository. All experiments are conducted on a single NVIDIA RTX A6000 GPU with PyTorch backend. Due to inherent randomness in sampling, conduct three independent runs for each case and report the average as the result.
Measurement of Generation Quality. Traversal Verification is theoretically lossless speculative decoding technique, which suggests that evaluating its generation quality should not be mandatory. However, recognizing that some readers may seek assurance regarding this guarantee, we present the measurements of generation quality as a supporting reference for losslessness. Please consult Appendix for the detailed experimental findings.
4.2 Overall Effectiveness
We present the acceptance lengths and throughput of two combinations of draft and target model, namely Llama3.2-1 1--B-Instrc with Llama3. 1--aa...--BInmaa Inst-uutt and Llama-68M with Llama2-7B in Table and Table 3 For chain and binary tree, we set the depth at 5, which is equal to the maximum depth of EAGLE sparse tree. Tok.V denotes token-level verification and Tra.V denotes Traversal Verification. The acceptance lengths are rounded decimal places, and we also provide the standard errors. A denotes the relative improvement of Traversal Verification over token-level verification. The bascline
7

---

Table 2: Acceptance length and throughput on Llama3.2- IB--srruct with Llama3.1-88 I-sttruutt..
Llama3.2 1---2--111n-nnteee (draft) & Llama3.1-88 1ar-1-1----nnttuee (target)
Temperature=1
Chain
Binary Tree
EAGLE Sparse Tree
Tasks
Tok.V
Tra.
A
Tok. V
Tra.
Tok.V
Tra.
Multi-turn
3.954003
4.09:ams
3.5%
2.64
4.76
2.6%
4.53=0m
4.67=002
3.1%
Translation
3.50
3.53
1.0%
4.28
4.43
3.4%
4. 1,16-004
4.27
2.6%
Sum.
3.661am
3.762ams
2.6%
4.02
4.64
2.7%
4.32_am
4.46=001
3.1%
QA
3,51
1.68
4.7%
4.32.100
1.40
2.0%
4. 4.19=005
=0.06
2.9%
Math
4.01
4.70
1.8%
5.37
5.39
0.4%
5.13
5.21
1.5%
RAG
4.05
4.17
3.1%
4.63
4.761006
2.8%
=.60=003
4.68
1.7%
Avg. Accept.
3.88
3.99
2.8%
4.63
4.73
2.2%
4.49
4.60
2.4%
Avg. Token/s
51.2112
52.5
2.5%
54.0206
54.9+11
1.7%
57.3
58.5
2.1
Table 3: Acceptance length and throughput on Llama-68M with Llama2-7B.
Llama-68M (draft) & Llama2-7B (target)
Temperature=1
Chain
Binary Tree
EAGLE Sparse Tree
Tasks
Tok. V
Tra.
Tok. V
Tra.
A
Tok.V
Tra. V
A
Multi-turn
2.05 =0.0
2.16+000
5.5%
2.47 40o:
2.59 #0.01
4.7%
4.05
2.70
5.6%
Translation
1.97
=.10s
6.3%
2.38
2.43 +0.05
2.1%
2.49
0.9%
Sum.
1.77
1.8620m
4.9%
2.27
5.8%
2.25
2.36
4.7%
QA
2.07=0.01
2.192002
5.6%
2.59
2.71
4.8%
2.6322022
2.69
2.2%
Math
2.01 =0.05
2.15
7.0%
2.49
2.67
=0.06
7.0%
2.57
2.72+001
6.0%
RAG
2.09
2.19
4.8%
2.56
2.69
5.0%
2.63
2.71
3.2%
Avg. Accept.
1.99
2.10
5.7%
2.44
2.56=aan
4.9%
2.52
2.62+ao1
3.8%
Avg. Token/s
58.0
60.8
4.8%
59.410s
61.6106
3.7%
69.1209
71.2
3.0%
generation speed without speculative decoding for Llama3. Llama2-7B is 37.3=0.1 token/s, and the speedup ratio can be calculated accordingly.
is 34.5=a.1 token/s and for
As can be observed from the results, compared with token-level verification, Traversal Verification achieves average improvement in acceptance length of 2.2% to 5.7% across different tasks, tree architectures, and combinations of draft and target models. The performance gains from Traversal Verification exhibit variability depending the specific configurations of draft and target models.
Since Traversal Verification operates through bottom-up verification mechanism across the entire tree, it potentially introduces additional computational overhead compared token-leved verifica- tion. Consequently, the actual throughput improvement is slightly lower than the improvement in acceptance length. This issue can be mitigated through more optimized implementation.
4.3 Impact of Chain Depth and Tree Size
Since Traversal Verification considers the joint probability of the entire sequence, is intuitive that the performance improvement will become more pronounced as the tree size and depth increase. To illustrate these effects, we perform experiments across varying chain depths and tree sizes. Specifically, for chain decoding, conduct experiments at depths of 2, 4, 6, and 8. For tree decoding, we employ binary trees from depths to 5 (corresponding to trees with 23 23-1, 24-1, 25-1, and 2 nodes, respectively).
As shown in Figure 3 the advantage of Traversal Verification grows progressively with increasing chain depth and tree size. In specialized scenarios (e.g., model offloading) where large tree sizes are permissible (for example, Sequoia 4 utilizes trees with 768 nodes and depth exceeding 20), Traversal Verification is expected to demonstrate even greater performance gains.

---

Liama-3.2/344 Chain
Liama 68M/Liama-2 Chain
Llama-3.2/3.1 Tree
Llama-@M/LLlama Tree
Talce Miouiin
Acceptance Lengts
Imprövemennt (%)
Improvement (N)
Acceptance Length
Improvemtt
accept
1.3
Depth
Depth
Depth
Depth
Figure 3: Acceptance lengths and improvements under different chain depths and tree sizes.
4.4 Impact of Temperature
We investigate the impact of temperature on Traversal Verification. Intuitively, as the temperature decreases (i.e., the probability distribution becomes more concentrated), the performance gap between token-level verification and Traversal Verification narrows. Conversely, at higher temperatures, Traversal Verification demonstrates more pronounced advantages.
Table 4: Acceptance lengths under different temperature.
Chain
Binary Tree
EAGLE Sparse Tree
Temp.
Tok.V
Tra.V
A
Tok.V
Tra.V
A
Tok.V
Tra.V
A
0.2
4.161001
4.20
1.0%
5,01 1002
5,07
1.2%
4.77
1.04
1.5%
0.4
4. 4.142002
4.20=002
1.4%
5.00
5.061001
1.2%
4.76.0.02
4.83
1.5%
0.6
4. 1
4.17=003
1.5%
4.92+am
5.00
1.5%
4.71
4.78
1.5%
0.8
4.02+amz
2.2%
4.81 4ame
40me
4.90+am2
1.7%
4.64
4.72+001
1.7%
1.0
3.88+aau
=.99
2.8%
4ams
4.73 40.1
2.2%
4.49
4.60
2.4%
Table 4 presents the acceptance length of Traversal Verification and token-level verification across and
as the draft and target models. respectively. The depths of chain and binary tree set to 5. The superiority of Traversal Verification increases with rising temperature, aligning with our intuitive expectations. It is worth noting that Llama2-7B may generate repeated tokens lower temperatures, leading to unreliable acceptance length measurements; therefore, we omit the results for Llama2 in this analysis.
different temperature settings, using Llama3.2-IB-Inet
Related work
Significant efforts have been devoted accelerating LLMs. Some approaches directly reduce memory access and computational costs through techniques such as quantization 88
9 33 22 and knowledge distillation [I] 17 37]. Some other works focus on architectural innovations, such as Mixture of
Experts (MoE)
15 7 where only subset of model parameters is activated during inference, thereby
improving inference speed.
Speculative decoding 3 19] introduces distinct drafting-veri verification paradigm that leaves the LLM itself unchanged. Researches on speculative decoding primarily focus on two directions. 1) Better alignment between the draft and target model, such as EAGLE [21 20 and Medusa 22 series.
2) Better verification strategies, such innovations in tree structures 20 31 and verification algorithms, which are more closely related to this work.
In chain decoding scenarios, Block Verification [27] and Asps [2] identify the sub-optimality in token-level verification and propose enhancements. SpecTr 28 extends chain decoding multi- candidate settings by formulating it as an optimal transport problem solved via linear programming, while SpecInfer [23] employs Recursive Rejection Sampling for multi-candidate situations. Sub- sequent works refine this approach into RRSw (recursive rejection sampling without replacement)
14 35 preventing repeated sampling and rejection of identical tokens, thereby improving
acceptance rates. Beyond standard sampling, SpecHub 226 and Greedy Sampling [33 adopt hybrid strategies: deterministically selecting top-K candidates with the highest probability and sampling other candidates probabilistically, achieving higher acceptance rates in specific scenarios.

---

6 Conclusion
This paper proposes Traversal Verification, a novel speculative decoding algorithm that significantly enhances the acceptance length, thereby improving the throughput of LLM inference. We rethink the limitations of existing token-level verification methods and adopt a bottom-up verification strategy that allows sequence-level acceptance and full utilization of drafted tokens. We theoretically prove the losslessness of Traversal Verification and its optimality when the decoding tree degenerates into a single chain. Experimental results show that Traversal Verification consistently improves the acceptance length and throughput of over existing speculative tree decoding methods across various tasks, tree structures, and combinations of draft and target models.
Acknowledgments and Disclosure of Funding
This project is fully funded by Lenovo. We would like to express special thanks to the Lenovo Al Lab and the Lenovo Model Factory Team for their valuable support in providing computing resources.
References
[1] Ondrej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Kochn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve saint-Amand, Radu Soricut, Lucia Specia, and Ales Tamchyna. 2014. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the Ninth Workshop on Statistical Machine Translation, WMT ACTTAACI. 2014, June 26-27, 2014, Baltimore, Maryland, USA.
[2] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D. Lee, Deming Chen, and Tri Dao. 2024. Medusa: Simple LLM inference acceleration framework with multiple decoding heads. In Proceedings of the International Conference on Machine Learning.
[3] Charlie Chen, Schastian Borgeaud, Geoffrey Irving, Bann-Battstte Lespiau, Laurent Sifre, and John Jumper. 2023. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318.
[4] Zhuoming Chen, Avner May, Ruslan Svirschevski, Yuhsun Huang, Max Ryabinin, Zhihao Jia, and Beidi Chen. 2024. Sequoia: Scalable and robust speculative decoding. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10- 15, 2024.
[5] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jemry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.144 10.1466.
[6] Gheorghe Comanici al. 2025. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality. long context, and next generation agentic capabilities.
DeepSeek-AI, Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu,, Chenggang Zhao, Chengqi Deng. Chenyu Zhang. Chong Ruan, Damai Dai, Daya Guo. Dejian Yang, Deli Chen, Dongjie Ji, Erhang Li. Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Haowei Zhang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Li, Hui Qu, J. L. Cai, Jian Liang, Jianzhong Guo, Jiaqi Ni, Jiashi Li, Jiawei Wang. Jin Chen, Jingehang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, Junxiao Song, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Lei Xu, Leyi Xia, Liang Zhao Litong Wang, Liyue Zhang, Meng Li, Miaojun Wang. Mingchuan Zhang, Minghua Zhang, Minghui Tang. Mingming Li. Ning Tian, Panpan Huang, Peiyi Wang, Peng Zhang, Qiancheng Wang, Qihao Zhu, Qinyu Chen. Qiushi Du, R. Chen, R. L. Jin, Ruiqi Ge. Ruisong Zhang, Ruizhe Pan, Runji Wang. Runxin Xu, Ruoyu Zhang, Ruyi Chen,
Li, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shaoqing Wu, Shengfeng Ye, Shengfeng Ye, Shirong Ma. Shiyu Wang, Shuang Zhou, Shuiping Yu, Shunfeng Zhou, Shuting Pan, T. Wang. Tao Yun, Tian Pei, Tianyu Sun, W. L. Xiao, and Wangding Zeng. 2024. Deepseck-v3 technical report. arXiv preprint 2412.//9999953
[8] Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. 2022. LLM.int80: 8-bit matrix multiplication for transformers scalc. arXiv preprint 27X3:22208.03339
[9] Elias Frantar, Saleh Ashkboos, Torsten Hoefler. and Dan Alistarh. 2023, GPTQ: Accurate post-training quantization for generative pre-trained transformers, arXiv preprint 21X.122200.13333
10

---

[10] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, et al. 2024, The Ilama 3 herd of models. arXiv preprint arXiv:2407.21783.
[11] Yuxian Gu, Li Dong. Furu Wei, and Minlie Huang. 2024, MiniLLM: Knowledge distillation of large language models. In Proceedings of the International Conference on Learning Representations.
[12] Zhengmian Hu and Heng Huang. 2024. Accelerated speculative sampling based on tree monte carlo. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024.
[13] Zhengmian Hu, Tong Zheng, Vignesh Viswanathan, Ziyi Chen, Ryan A. Rossi, Yihan Wu, Dinesh Manocha, and Heng Huang. 2025. Towards optimal multi-draft speculative decoding. arXiv preprint urXiv:2502.18779
[14] Wonseok Jeon, Mukul Gagrani, Raghavy Goel, Junyoung Park, Mingu Lee, and Christopher Lott. 2024. Recursive speculative decoding: Accelerating LLM inference via sampling without replacement. arXiv preprint Xrxiv:2402.1144: 140.1
[15] Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de Las Casas, Emma Bou Hamna, Florian Bressand, Gianna Lengyel, Guillaume Bour Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang. Timothée Lacroix, and William Sayed. 2024, Mixtral of experts. arXiv preprint OrXiv:2401.04060
[16] Vladimir Karpukhin. Barlas Oguz. Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020.
[17] Jongwoo Ko, Sungnyun Kim, Tianyi Chen, and Se- Young Yun. 2024. Distillm: Towards streamlined distillation for large language models. In Proceedings of the International Conference Machine Learning.
[18] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur P. Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming- Wei Chang, Andrew M. Dai, Jakoh Uszkoreit, Quae Le, and Slav Petrov. 2019. Natural questions: a benchmark for question answering research. Trans. Assoc. Comput. Linguistics.
[19] Yaniv Leviathan, Matan Kalman, and Yossi Matias. 2023, Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, JCML 2023, 23-29 July 2023, Honolulu, Hawaii, USA.
[20] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2024. EAGLE-2: faster inference of language models with dynamic draft trees. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, EMNLP 2024, Miami, FL, USA, November 12-16, 2024.
[21] Yuhui Li, Fangyun Wei, Chan Zhang, and Hongyang Zhang. 2024. EAGLEE: rethinking feature uncertainty. In Forty-forst International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024.
speculative sampling requires
[22] Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang. Wei-Ming Chen, Wei-Chen Wang, Guangxuan Xiao, Xingyu Dang, Chuang Gan, and Song Han. 2024. AWQ: activation-aware weight quantization for on-device LLM compression and acceleration. In Proceedings of the Annuad Conference on Machine Learning and Systems.
[23] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang. Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, Chunan Shi, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia. 2024. Specinfer: Accelerating large language model serving with tree-based speculative inference and verification.
Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, ASPLOS 2024, La Jolia, CA, USA, 27 April 2024- 1 May 2024.
[24] Ramesh Nallapati, Bowen Zhou, Cícero Nogueira dos Santos. Çaglar Gülçehre, and Bing Xiang. 2016. Abstractive text summarization using sequence-to-seqee mas and beyond. In Proceedings of the 20th SIGNLL Conference Computational Natural Language Learning CoNLL 2016, Berlin, Germany, August 11-12, 2016.
[25] OpenAL. 2023. GPT-4 technical report. arXiv preprint ar3.023303.0
11

---

[26] Ryan Sun, Tianyi Zhou, Xun Chen, and Lichao Sun. 2024. Spechub: Provable acceleration to multi-draft speculative decoding. In Proceedings of the 2024 Conference Empirical Methods Natural Language Processing, EMNLP 2024, Miami, FL, USA, November 12-16, 2024.
[27] Ziteng Sun, Uri Mendlovic. Yaniv Leviathan, Asaf Aharoni, Jae Hun Ro, Ahmad Beirami, and Ananda Theertha Suresh. 2025. Block verification accelerates speculative decoding, In The Thirteenth International Conference on Learning Representations.
[28] Ziteng Sun, Ananda Theertha Suresh, Jac Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix X. Yu. 2023. Spectr: Fast speculative decoding via optimal transport. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NewrIPS 2023, New Orleans, LA, USA, December 10- 16, 2023.
[29] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog. Yixin Nie. Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian. Xiaoqing Ellen Tan, Binh Tang, Ross Taylor. Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melamie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnie, Sergey Edunov, and Thomas Scialom. 2023. Llama 2: Open foundation and fine-tuned chat models.
[30] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA.
[31] Jikai Wang, Yi Su, Juntao Li, Qingrong Xia, Zi Ye, Xinyu Duan, Zhefeng Wang, and Min Zhang. 2025. Opt-tree: Speculative decoding with adaptive draft tree structure. Trans. Assoc. Comput. Linguistics.
[32] Heming Xia, 7he Yang, Qingxiu Dong, Peiyi Wang, Yongqi Li, Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui. 2024. Unlocking efficiency in large language model inference: A comprchensive survey of speculative decoding. In Findings of the Association for Computational Linguistics, ACL 2024, Bangkok, Thailand and virtual meeting, August 11-16, 2024.
[33] Guangxuan Xiao, Ji Lin, Mickaël Seznec, Hao Wu, Julien Demouth, and Song Han. 2023. SmoothQuant: Accurate and efficient post-training quantization for large language models. In Proceedings of the International Conference on Machine Learning.
[34] An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, et al. 2024. Qwen2 technical report. arXiv preprint arXiv:2407. 10671.
[35] Sen Yang, Shujian Huang, Xinyu Dai, and Jiajun Chen. 2024. Multi-candidate speculative decoding. arXiv preprint arXiv:2401. 067606.06...
[36] Lianmin Zheng, Wei-Lin Chiang. Ying Sheng. Siyuan Zhuang. Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. 2023. Judging alm-as-a-judge with mt- becc and chatbot arena. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA,
USA. December 10 16, 2023.
[37] Qihuang Zhong, Liang Ding, Li Shen, Juhua Liu, Bo Du, and Dacheng Tao. 2024, Revisiting knowledge distillation for autoregressive language models. In Proceedings of the Annual Meeting of the Association for Computational Linguistics.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We are sure the abstract and introduction accurately reflect the paper's contri- butions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in Appendix G
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: We have discussed the proposed assumptions and theoretical results in Section and provided the formal proofs in Appendix A and Appendix B
3.3
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our algorithm is demonstrated in Algorithm We have provided the detailed experimental setups in Section 4.1 The existing assets related to this paper have been listed in Appendix and the readers can find them from the provided open-source repositories.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: The entire codebase is proprietary due to company policy, but maybe are able to release a portion of it in the future if permitted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.com
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
Codeeoomi ssioiiiiicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We have provided the detailed experimental settings in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: We have provided the error bars in our results in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided the details in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We are sure research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have provided the elaboration of broader impacts Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have provided the assets related to this paper in Appendix !
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [Yes]
This paper studies the acceleration algorithm (speculative decoding) of LLMs. We use open-source LLMs as the draft and target model in speculative decoding. We elaborate on the usage of LLMs in Section
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
19

---

A Formal Proof of Losslessness of Traversal Verification
We first prove necessary and sufficient condition for valid tree verification algorithm (Definition 3.2). Our proof technique is analogous to [27 Lemma 2 in Appendix.B BB] and extends the original lemma a tree-structured case.
Lemma A.1. MM, let T be a decoding tree rooted at Xo base on Ms. and Tmax = max "Tu be the maximum depth along all chains in T. The output tree verification algorithm
Aver is denoted as
(x", (X",Y) Aver (T, MM.
Zima (Zo; Z1....
Zriann)) be a sequence defined as follows:
7/max
Zimax
Y,
< 7/max
with Z>r+1 (Z++2.-. ..... Z m rithm Aver is valid if and only if
generated from Mo(-IX7, Y). Then the rree verification algo-
Zimax M,((1xo)
(5)
Proof. We first prove the sufficiency, i.e., Equation 5 implies that Aver satisfies Definition 3.2 Taking the output (X", Y) as new prefix into Aver, we obtain
(X*, Y) Aver MT, Mo),
with the root of 7 being Xo (XT, Y) and then generate
Ymnax
Tmax
(8*, 2,,41) 7 < Ymax
with 75741 ~ Ma6- Y). Note that by Equation (5. we have
Z mmas P(X,, M)Mo(-)Xo).
and
Zimax E ~ Mo(1(Xo),
Here, F² is extension sequence of 7 Tomax generated from MM(FFI such that the combined sequence (Z"muxx E²) has the same number of tokens as 7mmax For the sequences (Zlamx, E²) and 7 7max, by taking the expectation over all the random variables after (X"YY, we get P(XT, Y) = Mo(X", ,YXx)),
namely, the proof of the sufficiency is completed.
The necessity is straightforward: If r < Tumxx Equation holds trivially. If T Ymax- then Z Z'mmax= X and Y ~ Mc(-IX")) By (4) in Definition 3.2 also have
2 M,)-1xo).
In conclusion, the proof of the necessity is also completed.
A.1 Proof of Theorem
By Lemma A.I it would be enough prove that Traversal Verification satisfies Equation (). We observe the inherent self-similar property of Traversal Verification: When arbitrarily selecting a parent node and rejecting it, the algorithm has already evaluated all its descendant nodes through the same traversal mechanism. In other words, Traversal Verification effectively applics a recursive instance of itself to the local subtree rooted at the current parent node. Leveraging this self-similar property, we establish the following stronger lemma than Theorem 3.3
Lemma A.2. Y.M... let T be decoding
amax rooted Xo base on M, and Ymax max. Yo
be the maximum depth along all chains in T. The first chain in T is denoted as a = (ag, a1.... Orys
from root ag Xo to the first leaf node arya Zimas is the sequence generated by Traversal Verification Aira (hra(T,C MM, (i.e., Algorithm 3 in Lemma A. Then the following statements hold, v0 & l & Na.
ind Pizz= =aa) Pa (at) and PPZ (e,)) P. (a))a)()zella))
ini
(6)
20

---

Proof. When Va = 0. i.e., the tree T contains only the root node Xo, then Ymax 0, 2 Yiua Xo and the conclusion (6) holds trivially. Therefore, in subsequent proofs, we only need to consider the case where Ta > 1.
Next, begin to prove the statements in (6) hold for any fixed 0 < & Ya by induction on the number of descendant nodes of agg, For simplicity, we collect all the children nodes of as as a new set C(ae) C I'' and all the descendant nodes of at as D(ar) C.
When the number [D(az)] = O, i.e., are is the leave node of the first chain a, then & = 7a and Z Vh nh means that the traversal algorithm Aera accepts the first chain directly. Thus,
P(Z T "0 - c (an.) and P(Z Tmax To, (2nn)) pa (Arya MMo(Zz7 la").
Suppose the two equations in (6) hold when [D(ar)] & k. Then when (((s)) = k + 1, we know D(az) is nonempty since the node c1e+1 E D(ae). Trivially, we have [(ae++)) & k. then by the induction hypothesis.
P(Z = a (1) = Par (aet1)
P(Z Tmax (a' ((2411) = (ott1)
(8)
For Traversal Verification Atra (T, MM. the probability
P(Z ==) a²) P(Z = 0g- 7 aa) TP(7++1 # 01411 7, aa)
po (ac+1) + P(Z a P(Z a'17 # a141)
= Po ( + (1 - P.. (ac+1)) PP(Z' = a =11
(9)
In the case of Z++1 F ae+1, namely, all the nodes in (( U (((-+1)) have been removed from the original tree T, the remaining tree Tnew := T - ((a++1) - (aee1) modifies only the following parameters compared to the original tree:
the acceptance rate P'a (Ors):
(as) Mo(x))a))) - M,,(xaaa))
(01) E (arr Mo(xlaa) M, + p(ri((a)))
(10)
the distributions M2(t)la²) and (x(a) for all children nodes of oc:
M)(xla() = Ip Ma - M,(x(a()1+
(xpr Mo(xlat) - Mo(xlaf)]+' Vo E N,
(11)
M,(ae-ila') and M,(xlaa)) = M,(xla²)
Vo # ae+1.
(12)
M.(aetilat)
Therefore, after ae-1 has been rejected, the acceptance rate of the parent node ag decreases from pi (ag) to p'a (ake), and the remaining children nodes of as in Tew are stochastic sampling nodes on M,((laa),, with their corresponding target distributions being My(-la'). By the self-similar property of Aua. we observe that in the remaining tree Tnew. Traversal Verification utilizes only the acceptance probability p' (a(g)) of parent node ay, the new distributions (=I(")))). M,,(la"") of children nodes C(az). and the original distributions M,(-(a') and M&(-la") of other descendant nodes (ac) C(as). Since ae+1 & Tuew, the number of descendant nodes of ag in new tree T Tnew is less than the original [D(x)),. by the induction hypothesis, we know
P(Z = a /Ze+1 # a4t1) P(accept are (rejecc a1+1)
P(accept ae in T )new) = P'a (ac),
(13)
P Imnx (oe, Ze+1 # a441) P(Z Tima (a', Z> [T new)
= Mo Mo Ze41).
(14)
Now, we begin to prove P(Z'= = )²= = pe (as) at first.
p(Z = a' Pa
ini (a(+1) ) + (1 Pa ini
(a(+1)) P(z' = a'IZet1 # a(+1)
piui (as+1) ) + (1 - piui (as+1)) (ar).
(15)
21

---

Since P(Z = a') is independent to the random variable ac+1, we have
P(Z'= =a Baa,, [P(Z] = a²)]
Σ
Pa ini (at+1 x) x)Mo(r)aa) + 1 - Eva in (at+1 (x)11 valas)
Σ min (ar M.(cla)) + pa(aa))
Σ [Ma(
- pa (a)
10
Σ min {pa
+
Σ
Pa
f -
x
Ma(xla Mc(aaa)
Pa sm (at).
Then we begin to prove the second statement of (6) i.c..
P(Z = (a ->x)) p:a Molssala))
(16)
For any sequence 7wms satisfying x' = a², we have
P(Z = x (mmx))
P((e4+1 TE+1 PP Ymmx = (a e+1 (0se+1)laae x2+1)
Σ Plae+1 = I' P(rejecc a4+1) P(( Tu = (a (I,I) a(+1)
M,(ze+lla') [4t (x411)
Σ z'dzen1
M.(e'la)(11 - (at+1 = x. ()P(( (mmaa mman ( & a4t1)
tn
Ma(ze+ila') Ph
pi (aet1 =T4e))
xe+1)
+Valas))M(EE Ma la', w1+1)
E Ma(e'la9(11 per (02+1 = ='))]
=Molssett a x441) min (ra (as) Mo
+Mo(sserila (alassenla',aem)) ae+1) M.
Σ (a"
z'
We evaluate the value Equation + via case analysis of we+1:
Case 1: pad (asz) (oze & Ma
Since M3(xe+1aa = in this case (see II the Equation ( is equal to
Mo xe+1) tn (at) Mo) pa tmi (ae)
Case 2: p (a(eM((())))))) > M,(setilat).
Since (Ma pi (o ) O. we have
Σ [Mo(olla')ppp - (ac)
(.(a'laa) po im (a)
22

---

Together with 10 and
we get
((
E
- (o)
Σ IP (MM)) + po (ac)
(a)" MM( im (ar) Ma(
Taking into then
Ma( | xe+1) (M. + va ( Ma((errlaa)
My(zse-1le 22+1 1) (ax) (zee1)lla)) = pa (oo)
conclusion,
pa (o
P Tmax = x > =
> Pa (at) (o Va = x
Thus, the Equation (16) holds and have proven by mathematical induction that, in Traversal Verification Aua. for any node Or in the initial first chain, the following equations hold:
p(zz a²) = (ax) and P(Z ,a'zZ>))) Mo(ssaa)))))))
Theorem 3.3 can be directly deduced from this lemma. Specifically, by setting & = 0 in Lemma A.2
we immediately obtain that
P(Zimux (Xu, Zso)) = -Mo(Z>o|Xo)
Since Mo(XolXo) = 1, we know
7 Tiax Mo(-1Xo).
Therefore, the proof of and Theorem 3.3 has been completed.
B Formal Proof of Single-chain Optimality
To establish the optimality Traversal Verification in the single-chain case, we need to introduce two lemmas presented in (27]
Lemma B.1 (Lemma 3 in (7 Let T = -(o..... ,ry) be a decoding chain based on Ms. Ablock be Block Verification proposed in (27V, and
(X", Y) Ablock (T, Ms,
Then we have Aa E %
P(r > x o²) - (cxe).
Lemma B.2 (Lemma 4 in (27)). For chain verification algorithms that satisfy the constraints in Lemma A.2 have VY < 7
P(r > fx===od < < (as).
Proof. It suffices to observe that when the stochastic sampling tree reduces single-chain structure, the equivalent definition Lemma A.1 of valid chain verification algorithm in this paper is identical to equivalent definition 27 Lemma of the valid draft verification algorithm. Therefore, Lemmas
B. and B.2 hold automatically as the directly applications of (27 Lemma and Lemma 4J.
Note that when the sampling tree reduces to one single chain, Lemma A.2 shows that the probability of Traversal Verification accepting at least é tokens is
PP( > fxx = a') p(z a²) ind (at).
23

---

By Lemmas B.1 and B.2, we show that among all valid chain verification algorithms (i.e., valid draft verification algorithms satisfying the constraints in [27 Lemma 2)). Traversal Verification accepts any given subsequence with the highest probability as the same as Block Verification. Specifically, for given decoding chain = (o0,....,44 based on Ms. we have
E N traversaa] Barm.
Σ P( P(Teraversal 3 ffx = a²)
Ea
Σ pa (at)
smi
R [bbookk] Bo
Σ P(Tblock 3 =(x+==a) =
Ba
Σ (as) (as)
E[evertyy] EarM
Σ P(Tverity 2 21x = a²)
< Ba
Σ Σpa ini (a))
This implies Theorem 3.4 holds.
C Evaluation of Generation Quality
Although we have ulready provided mathematically rigorous proof for the losslessness of Traver- sal Verification, we understand that is also important to present experimental results regarding generation quality. We would like to emphasize that the primary application scenario of Traversal Ver- ification lies in non-greedy generation, therefore, due to the randomness introduced by sampling and hardware fluctuations, there will be variations in the results generated each time. Consequently, the losslessness of Traversal Verification cannot be "proven" through experiments, and the measurement of generation quality serves merely as reference.
We follow the method used in Medusa 2 for measuring generation quality: we use the MT-Bench 36) dataset and employ a state-of-the art LLM as a judge to evaluate the quality of generation.
Table presents the evaluation of generation quality with 1aamma..--B-Instteeee (using the same 10-point scale as Medusa, higher score is better). We use Gemini-2.55Flash [6] as the judge model
assess the quality of the MT'-hench responses. For all experiments, ran them three times and report the average.
Table 5: Evaluation of generation quality.
Method
Verification Strategy
Quality
Autoregressive
N/A
6.72
Token-level Traversal
6.78
Chain
6.77
Token-level
6.76
EAGLE Sparse Tree
Traversal
6.79
Token-level
6.69
Binary Tree
Traversal
6.74
The results show that Traversal Verification maintains roughly the same generation quality as both naive generation and token-level verification, which serves as evidence for its lossless property.
D Statistical Methods and Additional Results
When calculating the acceptance length, the results may vary slightly due to different statistical methods. Specifically, the default statistical method of BeechBench can generally be described as "the average tokens generated per
cycle across the whole dataset".
However, this statistical method is not entirely appropriate. Because Spec-Bench covers diverse tasks, the answer length for each task and each sample can vary significantly. For instance, text generation tasks (such as "Compose an engaging travel blog post about recent trip Hawaï")) often have
24

---

longer responses than short translation queries (such as "Translate German to English: Dennoch Die Wahrheit auszusprechen kein Verbrechen"). Calculating the average acceptance length by aggregating all generated tokens will clearly be heavily influenced by long responses. Therefore, when we compute the average acceptance length, we calculate for each item first and then take the average across all items. This introduces slight difference from the default metric used in Spec-Bench.
We provide the acceptance lengths obtained using different statistical methods in Table 6 We also include the speedup ratios. To align with the official Spec-Bench benchmark results, we use EAGLE- Vie--a-nuuua-ii// [21) as the draft model and Vicuna-7B-v/ [36] as the target model. As shown, although the acceptance length slightly varies under different statistical methods, Traversal Verification consistently achieves a stable improvement.
Table 6: Comparison of acceptance lengths using different statistical methods.
Acceptance length
Tree Structure
Verification
Speedup
default (by token)
ours (by item)
Token-level
2.57
2.51
1.77x
Chain
Traversal
2.63
2.57
1.81x
Token-level Traversal
3.11
3.04
1.87x
Binary Tree
3.22
3.12
1.92x
Token-level Traversal
3.18
3.10
2.00x
EAGLE Sparse Tree
3.26
3.16
2.04x
E
Traversal Order
After the tree structure determined, adopt Depth-First Search (DFS) to establish the traversal order, with only minor differences from standard (pre-order) DFS. Specifically, the initial steps of typical DFS involve starting from the root node and reaching the first leaf node, marking all intermediate nodes as visited (this can also happen for subtrees). However, our verification starts from the leaf nodes, and node marked as visited only after has been verified. In other words, the verification order is conceptually post-order DFS.
F Sequence-level RRSw
Acceptonce rafe
Rool X
P(X))
P(X))
Root Xo
X1
ooo
Xm
X,Yi
OOO
X
O
Xm
((X)),,(I)
M(X))
P(X,)
Mr(K)
My(.))
Target distribution
Torget distribution
Figure 4: The sequence-level RRSw for two-layers decoding tree.
RRSw is a lossless probability modification method, which recursively redistributes the residual probability to other candidates after rejections, and the probabilities only "flow" within the same layer of tree. Traversal Verification can be regarded first transform the original decoding tree on the left into the right one, and then utilize the classic RRSw algorithm to derive the correct probability transition formulas.
sequence-level RRSw. As shown in Figure R we
25

---

G
Limitations
Despite Traversal Verification significantly enhances the performance existing speculative decoding frameworks, there are still some limitations. Firstly, our methodology is fundamentally applied to stochastic decoding scenarios (requiring temperature 0). In greedy decoding, where the temperature parameter is set to zero, the absence of sampling mechanisms renders all verification approaches functionally equivalent, thereby eliminating any potential performance gains from Traversal Ver- ification. Secondly, the traversal of all tree nodes introduces additional computational overhead during the verification phase. This characteristic may compromise practical throughput in particular environments. However, this issue could be mitigated through optimized implementation, such as discarding the sub-sequences with extremely low probabilities to avoid redundant computational overheads.
H Broader Impacts
This paper proposes Traversal Verification, a novel speculative decoding algorithm. Traversal Verification enhances the inference speed of Large Language Models (LLMs), thereby facilitating the deployment on resource-constrained devices such as personal computers, mobile phones, and various edge devices. LLMs themselves may be applied wide range of scenarios, potentially leading to various positive or negative societal impacts. This work may indirectly contribute to such impacts, but does not directly produce them.
I Licenses for Existing Assets
We summarize the assets and available resources related to this paper in Table 7
Table 7: Licenses of assets.
1-mma.1-8BB-mm
Ilama3.1 license
Ilama3.2 license
Models
Llama2-7R
llama2 license
Llama-68M
apache-2.0
Vicuna-7B-v1.22
Non-commercial license
+8
apache-2.0
Spec-Bench EAGLE
apache-2.0
Datasets & Codes
apache-24
hntps://uugginggfcc.o////// co/meta- co/meta-llamaa///aaaaaaaaaaaa Ilama/Llama-3 tt
"httss//hugginngfac.
wo/mmttaallmm///LIaaaae Ilama/Llama-3. 1-nssttttetttt
hhtpps//hugggnngffc.coo/iie cw/meta-
Patparii//EEAAAG---iaaaaaaaaaaa Vicuna-7B-v1.3
26


Reviews:
[{"review_id": "xOAfRvKqPb", "reviewer": "Reviewer_mJgv", "summary": "This paper considers the speculative decoding problem with multiple candidates and multiple steps. The authors propose a new technique that achieves higher sampling efficiency than existing work. The effectiveness of the proposed method is validated through extensive experiments.", "questions": "No", "limitations": "While not a weakness, there is still room for improvement in this method. RRSw is not optimal for multiple candidates, though finding the optimal solution for multiple candidates is indeed very challenging. Nevertheless, this work represents sufficient progress in the field and makes a valuable contribution to speculative decoding research.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The method cleverly combines optimal single-chain verification with RRSw (Recursive Rejection Sampling without replacement), to handle tree-structured candidates with best efficiency so far.\n\nWhile I haven't checked all proofs in detail, the construction and theoretical framework look sound to me. The method recovers the optimal single-chain verification as a special case. When rejection occurs, it properly modifies the distribution on the tree to maintain the optimality property.\n\nThe experimental validation is comprehensive.\n\nJust a very minor weakness: Since the method combines optimal single-chain verification with RRSw, the baseline comparisons could also include optimal single-chain verification in addition to RRSw. Although using single chains without trees would likely perform poorly and may not be necessary to show, it could provide additional context.", "was_revised": true, "final_justification": "I believe this paper makes a valuable contribution to speculative decoding research. I will maintain my original score and recommend its acceptance.", "rebuttal": "We deeply appreciate your insightful review and are pleased to address your comments regarding our work.\n\nAs you have pointed out, Traversal Verification is essentially an extention of optimal single-chain verification to multi-candidate scenarios (tree decoding). By delicate probability modification, which is a specially-designed RRSw, we maintain lossless acceleration.\n\nIn fact, we had concerned that the paper might be overly mathematical and challenging for readers unfamiliar with the field, leading us to incorporate reader-friendly examples and detailed explanations to enhance clarity. However, your review demonstrates a deep understanding of this field, and directly extracts our core idea, and we would like to show our respect for your expertise in this field.\n \nBelow are our responses to your specific comments:\n\n1.  **There is still room for improvement in this method. RRSw is not optimal for multiple candidates, though finding the optimal solution for multiple candidates is indeed very challenging.**\n\n    We completely agree with your assessment. This observation aligns perfectly with our ongoing research. In multi-candidate scenarios, RRSw is not optimal and can indeed incur some losses in acceptance rate when trasporting probability. Existing works, such as SpecHub and Greedy selection, attempt to mitigate this issue, and we find this to be a very interesting direction for future exploration.\n\n2.  **Since the method combines optimal single-chain verification with RRSw, The baseline comparisons could also include optimal single-chain verification in addition to RRSw.**\n\n    Thank you for your valuable suggestion. We agree that including this comparison would undoubtedly enrich the paper. Although we have mathematically demonstrated that Traversal Verification is equivalent to optimal single-chain verification (i.e., Block Verification) in the single-chain case, minor discrepancies in experimental results might arise due to factors like sampling randomness. We will consider adding these experiments to the final version.\n\n**Thank you once again, for your expertise in speculative decoding and the positive feedback on our manuscript.**"}, {"review_id": "7EJQrqCeze", "reviewer": "Reviewer_QRvg", "summary": "This paper focuses on the sepeclatvie decoding to accelerate LLMs and  tree verification is a common technique in speculative decoding to further improve the acceleration. The authors identify the two potential problems in the current speculative tree decoding, including token-level and root-to-leaf. The authors accordingly propose the Traversal Verification to address the above two problems.", "questions": "See above weaknesses and questions.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1.\tThe motivation of this paper is solid. There is indeed potential waste in the token tree. If these latent tokens can be effectively utilized, there is a chance for some improvement.\n\n2.\tThere is a theoretical argument demonstrating that Traversal Verification is lossless. I believe this is crucial for Traversal Verification, as it seems difficult to ensure losslessness if the verification relies solely on accepting leaf nodes.\n\nWeaknesses and questions\n\n1.\tCould the authors introduce more baselines for comparison? Currently, only some basic native methods are used as baselines. Since the authors utilize the widely-used SpecBench dataset, there should be many existing baselines whose results can be reproduced for comparison.\n\n2.\tThe authors should apply the proposed Traversal Verification to other speculative tree decoding methods to demonstrate its generalizability. Since the authors claim this is a plug-and-play method, this should be validated through experiments.\n\n3.\tThe authors state that “Notably, since Traversal Verification is a lossless speculative decoding method, there is no need to evaluate the generation quality.” I disagree with this. Most previous speculative decoding methods are also lossless, yet they still report generation quality in their experiments.\n\n4.\tRegarding the acceleration metrics, I believe the authors follow previous work in reporting the speedup performance. The accept length and token generation per second do not align with the metrics in SpecBench.", "was_revised": true, "final_justification": "Based on the rebuttal, my concerns are addressed.  I raise the score to 4.", "rebuttal": "Thank you for your detailed review.\n\nWe understand your concerns regarding the experiment, but we believe there are some things that need clarification. Therefore, before answering your questions, we'd like to describe the motivation and methods of this paper in a simpler and more intuitive way to help you understand, and then we will address your questions.\n\nLet's first discuss about the case of a single chain. Suppose we sample a sequence of length 2, where\n\n* Draft model probability ($M_s$) = 0.9 (for the first token) and 0.1 (for the second token)\n* Target model probability ($M_b$) = 0.1 (for the first token) and 0.9 (for the second token)\n\nFor conventional speculative decoding, we first consider whether the first token is acceptable. If it is, we then move on to the second token. This is why we refer to this as \"token-level verification.\" So obviously, the acceptance rate for this sequence would be $1/9 \\times 1 = 0.11$. However, if we consider the probability of the **entire sequence**, the acceptance probability is $(0.9 \\times 0.1) / (0.1 \\times 0.9) = 1.0$. This means the entire sequence could be accepted directly.\n\nBecause **token-level verification only considers the acceptance or rejection of individual tokens, it loses the optimality at the sequence level.** This is also a problem inherit in token-level verification: the cumulated acceptance rate is monotonically non-increasing (because the acceptance probability of a child node is always no more than 1). This clearly overlooks situations of probability \"crossover\". As shown in our example above, since $M_b > M_s$ at the second position, a higher acceptance rate for the second position compared to the first is permissible when considering the sequence-level probability distribution – **meaning, even if the first token is rejected, its child and the total sequence still have a probability to be accepted.**\n\nBy this example, we assume that you have understood that considering the \"overall probability\" of a sequence, instead of merely the \"per-token\" probability, may lead to a higher acceptance length, and **the only problem is \"how to use the sequence-level probability while maintaining losslessness\". In fact, it's realizable, as both in this paper and in Block Verification (ICLR 25) found ways to solve it.**\n\nNext, let's discuss the multi-candidate scenario. When multiple candidates exist at each depth of a chain, it forms a decoding tree. Current methods typically employ Recursive Rejection Sampling (RRS, represented by SpecInfer) and Recursive Rejection Sampling without replacement (RRSw, represented by EAGLE, Sequoia, MCSD, etc.). These multi-candidate approaches are also known as \"multi-round token verification,\" which is an extension of the single-candidate case. Essentially, it remains token-level verification, simply involving multiple rounds of rejection-resampling.\n\n**Think of it like building a house: token-level verification is the foundation, while specific decoding method, such as EAGLE, SpecInfer, are the houses constructed on top of this foundation. In fact, nearly all existing methods (except for Asps and Block Verification, but they only discuss the single-chain cases) rely on token-level verification.**\n\n**So, what we are doing is to \"extend single-chain sequence-level verification to the tree cases\", which is an enhancement of this foundation. It's not to propose a specific method, nor a plug-in for tree decoding methods.** This is quite challenging because you need to carefully modify the residual probability after rejecting a token to ensure losslessness. \n\n**In this paper, we leverage a leaf-to-root traversal mechanism to make full use of sequence-level probability, and design a quite delicate probability adjustment strategy to maintain losslessness.**\n\nWe really appreciate that you acknowleged our innovation of tree traversal, but **we want to highlight that our core innovation is to reform the fundamental verification algorithm, and the traversal mechanism serves as a good means to make use of the sequence-level probability.**\n\nNow let's look at the questions you raised.\n\n---\n\n**Q1. Could the authors introduce more baselines for comparison? Currently, only some basic native methods are used as baselines.** and **Q2. The authors should apply the proposed Traversal Verification to other speculative tree decoding methods to demonstrate its generalizability.**\n\nNow, you may see that our **baseline is not \"a specific tree decoding method\" but rather \"the speculative sampling algorithm itself and its suboptimality under tree decoding conditions.\"**\n\nWe can cite numerous examples that use token-level verifications:\n\nFor chain, examples include original Speculative Decoding, REST, and so on.\n\nFor tree, examples include EAGLE, SpecInfer, Sequoia, and MCSD, etc.\n\n**All these methods are on top of token-level verification, which serves as the base. What we are doing is not to build a decoration or an auxiliary on specific tree decoding methods, but to reconstruct the basic algorithm of existing token-level speculative decoding. That's why reviewer mJgv highly praised our work and said we make a valuable contribution to speculative decoding research.**\n\nTherefore, your two challenges, concerning generalization and more baselines, are essentially the same question. **In reality, we only have one baseline: the token-level verification foundation**. No matter how the \"houses\" (specific speculative decoding methods) built on top change, it doesn't affect the validity of the foundation.\n\nWe have mathematically proven the following:\n\n1.  **For chain decoding cases, the expected acceptance length of Traversal Verification is strictly greater than or equal to token-level verification, and it achieves optimal acceptance length**. (It's almost impossible to find or prove the optimality for tree due to uncertainty in multi-candidates situations)\n2.  **Traversal Verification is lossless.**\n\nOur mathematical proof of optimality provides strong support for the generalization of our method. The only question is how much stronger it is compared to token-level verification, for example, with different draft models, the improvement might vary.\n\nWe emphasize again, **Traversal Verification stands alongside vanilla speculative sampling (token-level verification) as a fundamental verification logic, not a decoration or auxiliary for specific methods.** In our experiments, we've already used various tree structures (chain, binary tree, EAGLE tree) and different model series (e.g., Llama3, Llama2) to demonstrate and compare the improvements of our method. You can, of course, use other model as drafters, such as the methods evaluated on Spec-bench using different draft models or different tree structures, but it is not neccesary, as Traversal Verification is on a more basic level than the specific methods, and **our effectiveness comes from the sequence-level probability, and it's generalizability is mathematically orthorgonal to those \"houses\".**\n\n---\n\n**Q3. The authors state that “Notably, since Traversal Verification is a lossless speculative decoding method, there is no need to evaluate the generation quality.” I disagree with this. Most previous speculative decoding methods are also lossless, yet they still report generation quality in their experiments.**\n\nLet's start by quoting a passage from the original EAGLE paper, currently one of the most well-known speculative decoding methods: \"**Acceleration of EAGLE theoretically guarantees the preservation of the target LLMs’ output distribution. Consequently, evaluating the quality of EAGLE’s generated results is both unnecessary and meaningless.**\" (Page 5, Line 12 of the right colomn).\n\nAs far as we know, most well-known existing lossless methods such as EAGLE (ICML 24), Sequoia (NeurIPS 24), SpecInfer (ASPLOS 24), Block Verification (ICLR 25), even the foundational paper in this field, \"Fast Inference from Transformers via Speculative Decoding,\" didn't measure generation quality.\n\nYou might point out that Medusa series states the quality. However, this is because Medusa proposes \"typical acceptance\" (which is not a lossless verification strategy), and Medusa-2 even train the backbone's weights (See section 2.2.2 in the Medusa paper), so measuring the generation quality is definitely necessary. \n\nWe think your statement that \"Most previous speculative decoding methods are also lossless, yet they still report generation quality in their experiments\" is questionable, as we have not encountered any well-known published works supporting this claim. We would greatly appreciate it if you could provide some examples.\n\n---\n\n**Q4. Regarding the acceleration metrics, I believe the authors follow previous work in reporting the speedup performance. The accept length and token generation per second do not align with the metrics in SpecBench.**\n\nWe are a little confused that you mentioned \"the accept length and token generation per second do not align with the metrics in SpecBench\". \n\nFirst, we are not using the same drafters. When selecting models, we chose the widely adopted and easily accessible Llama2 & Llama3 series as our target and draft models. We select these general, widely used model to strengthen the persuasiveness of our paper, as it focuses on \"optimizing the foundation.\" Spec-Bench covers a lot of NLP tasks, and we use it as a comprehensive dataset to evaluate and compare our method with token-level verification.\n\nSecond, the actual performance of different methods is only meaningful when compared under the same hardware conditions. \n\nSince our drafters are different from the specific methods on Spec-Bench, and even our GPUs are different, thus, we are confused about what \"not align with\" means here, as it's impossible to find a method with the same experimental conditions as ours on Spec-Bench.\n\nWe hope our explanations could address your concerns and provide a clearer demonstration of this paper."}, {"review_id": "uAYJa1rGFF", "reviewer": "Reviewer_VhHZ", "summary": "This paper introduces Traversal Verification, a speculative decoding algorithm that accelerates large language model generation by addressing limitations of token-level verification. It claims to guarantee lossless inference and achieves optimality in certain cases. Empirical results show consistent improvements in acceptance length and throughput over existing methods, particularly for larger decoding trees.", "questions": "Please address the concerns in Weaknesses.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The introduced Traversal Verification is a new verification method for speculative decoding with leaf-to-root traversal and sequence-level acceptance.\n- The paper provides rigorous proofs for lossless guarantee and optimality in specific scenarios.\n- Empirical experiments demonstrates consistent (though trivial) improvements in acceptance length and throughput across various tasks.\n\n### Weaknesses\n- The description of traversal verification in Line 45 is problematic. The statement \"If the node is accepted, the entire sequence from the current node to the root is accepted\" implies a lack of control over the correctness of parent nodes. For instance, in Figure 1, if $X_3$ is accepted, blindly accepting $X_1$ is not guaranteed to be correct.\n\n- The description of tree-based decoding in Line 41 is also problematic, reflecting a misinterpretation of tree-based verification. In standard tree-based verification (e.g., SpecInfer/Medusa/EAGLE), the model verifies multiple sequences (branches from the root to each leaf) **in parallel**, not token by token. It is unlikely that the proposed token-based traversal verification would outperform tree-based verification methods.\n\n- Another major concern is that the experiments only compare with token-level speculative decoding, without comparison to standard tree-based speculative decoding methods (e.g., Medusa, EAGLE) and lack of the autoregressive decoding as a baseline. As a result, the empirical significance is questionable, especially given the trivial speedups shown in Table 1 (typically ~1 token/s faster in terms of throughput).\n\n\n- The claim in Line 210 that \"Traversal Verification is a lossless speculative decoding method\" lacks empirical support. To justify this claim, empirical evidence should be provided to confirm the output guarantee consistency with standard autoregressive decoding.", "was_revised": true, "final_justification": "I appreciate the authors' further clarifications and newly added empirical results, which addressed my major concerns and lead to an updated evaluation. The added evaluation on generation quality clearly enhances the paper. It's also good to know the authors' plan to revise the writing for better clarity.", "rebuttal": "Thank you for your detailed review. \n\n**We have carefully read your questions and found that you may have some misunderstandings on our method, please allow us to begin with an example to thoroughly explain what we are doing and why we design Traversal Verification. This should help clarify your misunderstanding and illustrate our motivation.**\n\nLet's first discuss about the case of a single chain. Suppose we sample a sequence of length 2, where\n\n* Draft model probability ($M_s$) = 0.9 (for the first token) and 0.1 (for the second token)\n* Target model probability ($M_b$) = 0.1 (for the first token) and 0.9 (for the second token)\n\nFor conventional speculative decoding, we first consider whether the first token is acceptable. If it is, we then move on to the second token (Of course you can do this in parallel, but it doesn't change the essence). This is why we refer to this as \"token-level verification.\" So obviously, the acceptance rate for this sequence would be $1/9 \\times 1 = 0.11$. However, if we consider the probability of the **entire sequence**, the acceptance probability is $(0.9 \\times 0.1) / (0.1 \\times 0.9) = 1.0$. This means the entire sequence could be accepted directly.\n\nBecause **token-level verification only considers the acceptance or rejection of individual tokens, it loses the optimality at the sequence level.** This is also a problem inherit in token-level verification: the cumulated acceptance rate is monotonically non-increasing (because the acceptance probability of a child node is always no more than 1). This clearly overlooks situations of probability \"crossover\". As shown in our example above, since $M_b > M_s$ at the second position, a higher acceptance rate for the second position compared to the first is permissible when considering the sequence-level probability distribution – **meaning, even if the first token is rejected, its child and the total sequence still have a probability to be accepted.**\n\nBy this example, we assume that you have understood that considering the \"overall probability\" of a sequence, instead of merely the \"per-token\" probability, may lead to a higher acceptance length, and **the only problem is \"how to use the sequence-level probability while maintaining losslessness\". In fact, it's realizable, as both in this paper and in Block Verification (ICLR 25) found ways to solve it.**\n\nNext, let's discuss the multi-candidate scenario. When multiple candidates exist at each depth of a chain, it forms a decoding tree. Current methods typically employ Recursive Rejection Sampling (RRS, represented by SpecInfer) and **RRS without replacement (RRSw, employed by EAGLE, Sequoia, MCSD, etc.)**. These multi-candidate approaches are also known as \"multi-round token verification,\" which is an extension of the single-candidate case. Essentially, it remains token-level verification, simply involving multiple rounds of rejection-resampling.\n\n**Think of it like building a house: token-level verification is the foundation, while specific decoding method, such as EAGLE, SpecInfer, are the houses constructed on top of this foundation. In fact, nearly all existing methods (except for Asps and Block Verification, but they only discuss the single-chain cases) rely on token-level verification**.\n\n**What we are doing is to \"extend single-chain sequence-level verification to the tree cases\", and all tree decoding methods using token-level verification can benefit from this new \"foundation\"**. This is quite challenging because you need to carefully modify the probablity after rejecting a token to ensure losslessness. \n\n**In this paper, we leverage a leaf-to-root traversal mechanism to make full use of sequence-level probability, and design a quite delicate probability adjustment strategy to maintain losslessness.**\n\nThus, Traversal Verification is actually on a more basic level than specific methods like EAGLE, Medusa, and SpecInfer. **Our aim is to addresses the suboptimality of multi-round token verification methods in tree decoding, thereby enhance all the token-level based methods including EAGLE, rather than propose a specific method parallel to EAGLE.**\n\nNow let's look at the questions you raised.\n\n---\n\n**Q3. The experiments only compare with token-level speculative decoding, without comparison to standard tree-based speculative decoding methods and lack of the autoregressive decoding as a baseline.**\n\n *You may now be able to understand that what we refer to as \"token-level speculative decoding\" in our paper refers to all token-level verification methods including EAGLE and SpecInfer.*\n\nRegarding Medusa, its uses either token-level verification (lossless) or their proposed \"typical sampling\" (lossy, but faster) as the verification strategy, while token-level verification based methods such as EAGLE and SpecInfer are completely lossless. Therefore, we do not consider Medusa a proper reference for lossless speculative decoding.\n\nRegarding to auto-regressive baseline, we have provided the generation speed for Llama3 and Llama2 in line 222-223, maybe you have missed them.\n\n---\n\n**Q1. The statement \"If the node is accepted, the entire sequence from the current node to the root is accepted\" implies a lack of control over the correctness of parent nodes. For instance, in Figure 1, if $X_1$ is accepted, blindly accepting $X_3$ is not guaranteed to be correct.**\n\n*As we've discussed, this is exactly our core contribution. We are not \"blindly\" accepting a token, but with careful probability modification to ensure losslessness.*\n\nWith token-level verification, you must accept $X_1$ before you can accept $X_3$. This is the implication you've made in your question. However, our paper utilizes sequence-level probability and addresses this limitation:even if $X_1$ is rejected, the sequence $X_1X_3$ can still be accepted.\n\n**The ultimate goal of speculative decoding is to maintain the same probability as the original model**. $X_1$ being rejected doesn't mean it's \"incorrect\"; the root cuase is that, under token-level verification, you **must** reject it to maintain consistency with the original distribution. Conversely, if you consider sequence-level probabilities, **the presence of subsequent tokens can, in some cases, allow you to keep $X_1$ while maintaining the sequence's probability consistent with the original**.\n\n---\n\n**Q2. The description of tree-based decoding in Line 41 is also problematic, reflecting a misinterpretation of tree-based verification. In standard tree-based verification (e.g., SpecInfer/Medusa/EAGLE), the model verifies multiple sequences in parallel, not token by token.**\n\n*We are confident that our understanding of tree-based decoding is accurate. Let's discuss the verification process now.*\n\nThe verification process, in fact, consists of two distinct steps:\n\n1.  **Step 1: Feeding drafted tokens into the target model.** The drafted tokens are fed into the target model in **parallel** to obtain the target distribution. Almost all methods follows this mechanism, such as SpecInfer, Medusa and EAGLE, and it is the same for our method.\n2.  **Step 2: Acceptance decision.** Based on the target and draft model distributions, a verification is performed. In some cases (e.g., chain, and maybe typical sampling in Medusa) you can perform this in parallel. However, for RRS/RRSw (such as EAGLE), parallel verification is difficult because after a token is rejected, the residual distribution (i.e., $[M_b - M_s]^+$) needs to be calculated as the new target distribution, and you need to recursively obtain the residual distribution after each rejection. You cannot verify all sequences in parallel unless you pre-calculate those residual probabilities, and this is unnecessary and not economic.\n\n**Regarding your mention of EAGLE, we recommend that you examine its source code to confirm the acceptance logic**. You can check the “evaluate_posterior” function in eagle/model/utils.py (either in the main or v1 branch) within the official EAGLE repository. **You will find that it determines acceptance token-by-token**.\n\n**Furthermore, we suggest you refer to Algorithm 2 on page 5 of the SpecInfer paper and Algorithm 1 on page 13 of the EAGLE paper**. Both clearly describe the execution logic of SpecInfer or EAGLE's verification: they verify token by token in the same layer using token-level probabilities, and adjust the remaining probabilities after rejecting a candidate.\n\n**Therefore, we do not believe there is any issue with the statement in Line 41**.\n\nBeyond this, **as we have stated in Line 211 of this paper, the baseline token-level verification method we compared against in our experiment is indeed EAGLE's tree verification implementation.** \n\nConsequently, your statement that \"It is unlikely that the proposed token-based traversal verification would outperform tree-based verification methods\" is incorrect. Our experiments clearly demonstrate an advantage over EAGLE.\n\n---\n\n**Q4. The claim in Line 210 that \"Traversal Verification is a lossless speculative decoding method\" lacks empirical support. To justify this claim, empirical evidence should be provided to confirm the output guarantee consistency with standard autoregressive decoding.**\n\n*As you highlighted in the Strengths, we have already provided a complete, mathematically rigorous proof of the losslessness of our method.*\n\n**Most existing mathematically lossless methods, such as EAGLE, Sequoia, SpecInfer, Block Verification, even the foundational paper in this field, \"Fast Inference from Transformers via Speculative Decoding\", does not empirically evaluate the losslessness.** Conversely, attempting to prove losslessness through experiments would be unconvincing. Factors like sampling variability and hardware fluctuations can introduce randomness into experimental results. Consequently, experiments alone cannot definitively prove or disprove whether a method is lossless.\n\nWe hope our explanations could address your concerns."}, {"review_id": "nCGS0gN5sT", "reviewer": "Reviewer_VunK", "summary": "The paper introduces a novel verification method for tree-based speculative decoding. Unlike the conventional verification process, which starts from the root of the tree, the proposed method works backwards from the leaf nodes, thereby boosting the verification success rate with the same lossless guarantee. Theoretically, the paper proved that the proposed method is a lossless verification algorithm. In a single-chain speculation setup, the approach is proven to be optimal in terms of the expected acceptance length. Empirically, the paper demonstrates the effectiveness of their method on multiple models and benchmarks, where the technique can be easily applied on top of existing speculative decoding algorithms.", "questions": "1. How do you decide the traversal ordering? I would assume that the traversal ordering can affect your verification success rate. For instance, starting with a path that has a lower KL divergence between the base and draft models might give you a slightly higher verification success rate. \n\n2. Theoretically, the authors prove the optimality under a single chain, which is important. It would be more interesting if the authors could prove that the proposed method is strictly better (not necessarily optimality) than the conventional verification methods that start from the roots. If this is not provable, even adding some assumptions or identifying some scenarios where the proposed method is strictly better than the conventional ones can provide the work with a more solid foundation.\n\nThese are general questions that can be open-ended, so it is fine if authors do not provide complete answers. The work at the current stage is already pretty solid and interesting, so I would give a positive rating.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The presentation is clear and self-contained with illustrative toy examples.\n- The problem itself is important and practical, as most of the best-performing speculative decoding methods use a tree-based speculation structure. \n- The theoretical guarantee and solid empirical evaluations are a plus.\n- The proposed method can be easily adopted to any speculative decoding framework.\n\nWeaknesses:\n\n- The improvements from the evaluation results are marginal.", "was_revised": true, "final_justification": "The proposed method is theoretically sound and can be directly applied on top of the existing tree-based verification process to bring additional speed-ups. Thus, I would give a positive rating for the paper.", "rebuttal": "We sincerely appreciate the your insightful review and are pleased to address the raised concerns.\n\n**Q1: How do you decide the traversal ordering? I would assume that the traversal ordering can affect your verification success rate. For instance, starting with a path that has a lower KL divergence between the base and draft models might give you a slightly higher verification success rate.**\n\nWe did not intentionally design a specific traversal order. In fact, after the tree structure was determined, we adopted a search method similar to Depth-First Search (DFS) to establish the traversal order, with only minor differences from standard DFS. Specifically, the initial steps of a typical DFS involve starting from the root node and reaching the first leaf node, marking all intermediate nodes as visited (this can also happen for subtrees). We, however, skipped this \"root-to-first-leaf\" process because our verification starts from the leaf nodes, and a node is marked as visited only after it has been verified. Aside from this, our traversal logic is almost identical to DFS.\n\nAlthough we did not deliberately adjust the traversal order, this typically doesn't cause any problems. Most existing tree structures are unbalanced, such as static trees designed manually (e.g., the EAGLE sparse tree) or dynamically adjusted tree structures (e.g., Sequoia). These tree structures tend to allocate more and deeper nodes on the left side of the tree, which is intuitive. This is because the original probabilities of draft models are more aligned with the original probabilities of target models, leading to a significantly higher acceptance rate for nodes on the left. Probabilities after RRSw, however, are harder to control. Indeed, experiments in SpecHub (Figure 9) also demonstrate that for RRS/RRSw-based methods, the overall trend of candidate acceptance rate decreases from left to right.\n\nTherefore, under most current tree structures, our verification order is highly efficient. This is because we indeed start from the leftmost leaf node and traverse in a manner similar to DFS. This effectively leverages two advantages of existing tree structures: 1) \"deeper on the left\" and 2) \"higher acceptance rate on the left.\" In some unusual cases, such as trees intentionally designed to be shallow on the left and deep on the right, using DFS might lead to a decrease in acceptance length, but this is due to the inherent unreasonable nature of the tree structure itself.\n\nFurthermore, we suspect you might be wondering if it's possible to manually adjust the verification order, for example, from an intermediate leaf and intentionally design a traversal order, to achieve a higher acceptance length. However, this is quite difficult because the depth-first traversal order matches the sampling strategy. Manually adjusting the verification order could conflict with the sampling strategy and might lead to a loss of lossless property.\n\n---\n\n**Q2: Theoretically, the authors prove the optimality under a single chain, which is important. It would be more interesting if the authors could prove that the proposed method is strictly better (not necessarily optimality) than the conventional verification methods that start from the roots. If this is not provable, even adding some assumptions or identifying some scenarios where the proposed method is strictly better than the conventional ones can provide the work with a more solid foundation.**\n\nWe've actually considered this problem in great detail both during the writing of this manuscript and after receiving your review. It is, indeed a very charming property which are pursuing for. It's rather easy to demonstrate cases of a single chain, however, for multi-candidate scenarios, even when we envisioned specific scenarios (e.g., the tree's depth strictly non-increasing from left to right), we still couldn't find a good breakthrough to prove it. Therefore, we can only offer some of our current thoughts for discussion.\n\nIn our view, there are two primary factors that make demonstrating optimality or supriority extremely challenging. \n\nFirst, RRSw itself is sub-optimal (although it's one of the best multi-candidate methods and widely adopted by far). After rejecting a token using RRSw, both the remaining $M_b$ and $M_s$ must be adjusted. This adjustment introduces some sub-optimal probability transport, which leads to a non-optimal acceptance rate. So compared with single-chain scenarios, we need to additionally measure \"how much acceptance rate is lost\" in the RRSw process. Second, the acceptance rate of speculative sampling depends on the overlap between $M_b$ and $M_s$ (which is closely related to KL divergence). However, **the overlaps between the adjusted $M_b'$ and $M_s'$ after rejecting a token are different in token-level Verification and Traversal Verification.** Although Traversal Verification can still benefit from the sequence-level probability advantage, the different distributions after rejection make it quite difficult to prove Traversal Verification's superiority over token-level verification. In other words, compared to \"deterministic\" single-chain cases, the new probability distribution after rejecting a token using RRSw is \"uncontrollable\".\n\nSo what about considering a different approach? For example, if we temporarily set aside the RRSw algorithm and instead assume there's some optimal multi-candidate method, then combining Traversal Verification with it seems promising. However, finding such an algorithm is actually very tricky, and we aren't even sure if an \"optimal multi-candidate algorithm that can be practically employed\" truly exists. Therefore, we apologize that we temporally have no idea for this issue, even though we made many attempts so far."}]

Author rebuttal:

Meta-review: This paper introduces Traversal Verification, a novel and interesting leaf-to-root verification method for tree-based speculative decoding. The core idea of utilizing sequence-level probabilities to improve acceptance length, as opposed to the traditional token-level top-down approach, is well-motivated and technically sound. The reviewers unanimously acknowledged the paper's strengths, including the practical importance of the problem (Reviewers Vunk, QRvg), the solid theoretical guarantees of losslessness (Reviewers VhHZ, mjgv), and the comprehensive experimental validation (Reviewer mjgv). Initial concerns were raised by Reviewers VhHZ and QRvg regarding the need for empirical validation of the lossless claim and the inclusion of more baselines to demonstrate generalizability. However, the authors provided a thorough rebuttal with additional experiments, including generation quality scores on MT-Bench and results on the EAGLE-vicuna model, which successfully addressed these concerns and led the reviewers to raise their scores. After the discussion phase, there is a clear consensus that this work represents a valuable contribution to the field of speculative decoding. Therefore, I recommend accepting this paper for a poster presentation.
Decision: Accept (poster)