Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding
Authors: Yuxuan Zhou
Fei Huang
Heng Li
Fengyi Wu
Tianyu Wang
jianwei zhang
Junyang Lin
Zhi-Qi Cheng
Venue: ICLR 2026 Oral (2026)
Keywords: Speculative Decoding
Joint Intractability
Lossless Verification
Primary area: foundation or frontier models, including LLMs

Abstract: Verification is a key bottleneck in improving inference speed while maintaining distribution fidelity in Speculative Decoding. Recent work has shown that sequence-level verification leads to a higher number of accepted tokens compared to token-wise verification. However, existing solutions often rely on surrogate approximations or are constrained by partial information, struggling with joint intractability. In this work, we propose \emph{Hierarchical Speculative Decoding (HSD)}, a provably lossless verification method that significantly boosts the expected number of accepted tokens and overcomes joint intractability by balancing excess and deficient probability mass across accessible branches. Our extensive large-scale experiments demonstrate that HSD yields consistent improvements in acceptance rates across diverse model families and benchmarks. Moreover, its strong explainability and generality make it readily integrable into a wide range of speculative decoding frameworks. Notably, integrating HSD into EAGLE-3 yields over a 12\% performance gain, establishing state-of-the-art decoding efficiency without compromising distribution fidelity. Code is available at https://github.com/ZhouYuxuanYX/Hierarchical-Speculative-Decoding.

Published as a conference paper at ICLR 2026
OVERCOMING JOINT INTRACTABILITY WITH LOSSLESS
HIERARCHICAL SPECULATIVE DECODING
Yuxuan F Fei Huang", Heng Li', Fengyi Wu', Tianyu Wang", Jianwei Zhang,, Junyang Lin"; Zhi-Qi Chengst
Indepeedentt Researcher
2wen Team, Alibaba Inc. University of Washington
zhouyuxuaanyx@@mail com, junyang. 1 jygalibaba-aaaa ibaba-baabbaaa inc. com, zhiqi ciliiics@ue csêuw eduu
ABSTRACT
Verification a key bottleneck in improving inference speed while maintain- ing distribution fidelity in Speculative Decoding. Recent work has shown that sequence-level verification leads to a higher number of accepted tokens com- pared token-wise verification. However, existing solutions often rely on sur- rogate approximations or are constrained by partial information, struggling with joint intractability. In this work, we propose Hierarchical Speculative Decod- ing (HSD), provably lossless verification method that significantly boosts the expected number of accepted tokens and overcomes joint intractability by bal- ancing excess and deficient probability mass across accessible branches. Our extensive large-scale experiments demonstrate that HSD yields consistent im- provements in acceptance rates across diverse model families and benchmarks. Moreover, its strong explainability and generality make it readily integrable into wide range of speculative decoding frameworks. Notably, integrating HSD into EAGLE-3 yields over 12% performance gain, establishing state-of-the-art de- coding efficiency without compromising distribution fidelity. Code is available https://github..c http://github.oom/hhuuuu com//Zou Yuxuan H'/Hirrrrchiaall WWHiicarchhchuu.pplllaaaaaaoeee Decoodnn.
INTRODUCTION
Inference speed has become paramount for Large Language Models (LLMs) (Achiam et al., 2023; Touvron al., 2023; Bai et al., 2023), which generate text auto-regressively. Recent advances in test-time scaling (OpenAI, 2024; Guo et al., 2025; Yu et al., 2025; Peng et al., 2025) have further underscored its importance. While techniques like pruning (Frankle and Carbin, 2018; Sun et al., 2023a) and quantization (Shen et al., 2020; Xiao al., 2023) improve efficiency but sacrifice performance, Speculative Decoding (Leviathan et al., 2023) achieves speedups while preserving the target model's distribution, making it particularly appealing alternative. It adopts smaller model to make proposals and a larger model to select from them with a grounded verification strategy. Most approaches prioritize the drafting phase, but further gains face diminishing returns. Driven by the verification bottleneck, recent methods (Cai et al., 2024: Zhou et al., 2024; Narasimhan et al., 2024) trade off fidelity for speed, relying on spec-fc tuning: their performance typically remains constrained to carefully curated scenarios.
Recent work (Sun et al., 2024; Qin al., 2025) shows that jointly verifying draft tokens can improve the expected number of accepted tokens, but faces joint intractability: simply applying the resampling strategy used in tokenwise verification (Leviathan al., 2023) would require full joint probabilities over all possible decoding paths to correctly recover the target distribution, which is computationally infeasible. To address this, (Qin et al., 2025) employs lossy fixed acceptance threshold, while (Sun al., 2024) proposes Blockwise Verification, which provably recovers the target distribution. However, Blockwise Verification still falls short of the ideal case, and both its underlying mechanism and compatibility with other methods remain unclear.
In this work, we propose Hierarchical Speculative Decoding (HSD), a provably lossless verification method built upon novel hierarchical branch resampling strategy. In speculative decoding, resam-
Work done during internship at Qwen Team, Alibaba Inc.
Corresponding author.

---

Published as a conference paper at ICLR 2026
Jointly Accept
X,1
Next Decoding Step
Hierarchical Speculative Decoding
Draft
Tokens
x
Resampled Token
h 2%
Xx+1
Dropped Path
h. Rra
x
Reject
X h
x
Backward Operation
Acceptance Length
X
Resample the probability 1g (X,))
<<<
r+1
y-1
Figure I:
Overview of HSD. HSD accepts the draft X by scanning backward from yy to and then performs single resampling at position + using the corresponding distribution from the resampling hierarchy.
pling recovers portions of the target distribution that exceed the draft probability. As illustrated in Figure 1, HSD organizes multiple resampling distributions hierarchically across successive levels, with each distribution recovering only the partial target within its branch and resampling occurring immediately after the last accepted token. This design ensures the full target distribution is recovered in expectation while maximizing the expected number of accepted tokens, pushing the limits of lossless verification and enabling more efficient decoding. Notably. Blockwise verification focuses on independent verification with unclear potential for integration, while our method is designed to easily combine with other approaches, such as the widely adopted multi-draft setups.
In summary, our contributions are as follows:
We introduce Hierarchical Speculative Decoding (HSD), a lossless and explainable verifica- tion method that integrates seamlessly with existing speculative decoding frameworks while remaining largely orthogonal to them.
HSD delivers a practical advance inference scaling, achieving an average 6.7% im- provement in decoding speed across diverse benchmarks and model sizes while preserving distributional fidelity, with efficiency gains of up to 12.3% on individual datasets.
HSD further improves decoding speed across multi-draft settings. Notably, integrating HSD into EAGLE-3 yields over 12% performance gain, establishing new state-of-the-art decoding efficiency without compromising distribution fidelity.
RELATED WORK
Follow-up research speculative decoding (Levvithhan al., 2023) be organized into two main phases: the drafting phase and the verification phase.
Drafting Phase. Drafting methods can be grouped into three categories: (1) Single-draft. Early SD methods (Leviathan et al., 2023) inspired PaSS (Monea et al., 2023) and Draft& Verify (Zhang et al., 2024), improving efficiency via multi-token generation or selective layer skipping. GLIDE (Du et al., 2024) (shared K KV-cache) offers further speedups but requires task-specific tuning. (2) Retrieval- based. LLM-A (Yang al., 2023) and ReST (He al., 2023) generate drafts from reference texts, potentially reducing latency, but face database limitations, distribution gaps, and reliance on greedy decoding. (3) Multi-draft. Pree-attention frameworks SpeecSffrr (Miao et al., 2024), Medusa (Cai et al., 2024), and Eagle (Li et al., 2024; Fan et al.,
many branches, quickly exhausting memory. Medusa and Eagle also predict drafts from the target model's hidden features rather than a separate draft model, further boosting speed but requires task-specific tuning.
Verification Phase. Verification methods trade fidelity for speed. Lossless approaches (Sun et al., 2023b; Yang et al., 2024; Hu al., 2025) guarantee exact recovery but costly. Block Verifica- tion (Sun et al., 2024) partially alleviates this bottleneck but offers limited improvement and low interpretability and integrity. Lossy methods-includhe BiL.D (Kim al., 2023), MTAD (Qin et al.,
2

---

Published as a conference paper at ICLR 2026
2025), DistillSpec (Zhou et al., 2024), Medusa-2 (Cai et al., 2024), SpecCascade (Narasimhan et al., 2024) and CoS (Fu et al.. 2025) increase speed but compromise distribution fidelity and require task-specific tuning. In addition, Medusa and EAGLE always accept the first draft token to improve throughput, trading off exact recovery of the target distribution.
3 REVISITING TOKENWISE SPECULATIVE DECODING
In tokenwise speculative sampling (Leviathan al., 2023), each token is drafted from g(xe) and verified against p(zz). is accepted with probability h(x)) = min p(zz)/q(<z)) or rejected and replaced from Pres (22)) Thus the probability that 2; is finally produced ("yielded")) is:
Plr, yielded) = Pax drafted and accepted) P(ū, drafted and rejected, 2, resampled). (1)
Accept term. If xzz is proposed by and accepted,
Pax, drafted and accepted) ((x,) h(xe)) ((xx)) min(1, p(x.)/
Resampling term.
When draft ie rejected, the verifier resamples from
p(z,)= min(p(())..(m)))
Pres( Exee(p((;) min(p(()).
The total probability of rejection is ( h(++))) giving
Pix drafted and rejected, x, resampled)
Σ F.EV
(()) h(x))) Pro((ss).
(3)
Final distribution. The sum Enev (1-h(it) corresponds the total excess mass assigned by the draft distribution to tokens where it allocates more probability than the target, while the denominator of Pres(az) measures the total deficient mass, i.e., the probability assigned by the target to tokens where it allocates more than the draft. For tokenwise distributions these match (Di. (D.K(.))) = DLK (p. 4)), so they cancel, yielding
P(a, is yielded) = q(2))h(ZE) DLK(g. p(z.) q(z))((Z))) p(æx). DLK(p,9)
4 THEORETICAL FOUNDATIONS OF HIERARCHICAL SPECULATIVE DECODING
For any lossless speculative decoding, the probability of generating an output decomposes into two parts: (1) the probability a draft is accepted, becoming the final output, and (2) the probability a draft rejected, triggering a corrective resampling step. In token-wise speculative decoding, resampling is straightforward because each token's 's probability is directly accessible. In contrast, full joint probabilities over sequences are intractable for auto-regressive models. Hierarchical Speculative Decoding (HSD) overcomes this via hierarchical branch resampling, where multiple resampling distributions at different levels recover partial target distributions, which together statistically recover the full distribution. This section formalizes the theoretical foundations.
4.1 RECOVERY OF PARTIAL DISTRIBUTIONS
To guide recovery within accessible subsets, we extend the divergence from Leviathan et al. (2023) to partial distributions. Let be token or sequence, Ω the full sample space, and p()).g() the target and draft distributions. For S2' C Ω, define the generalized divergence:
Definition 1. Generalized Divergence. Given two distributions p and q over a sample space Q and subset S C Ω2 the generalized divergence over !!' is defined as:
Dav (p. 9)
Σ max(p(() q(i), 0}.
WER
The generalized divergence D (p, q) measures the total deficient mass, i.c., how much probability mass is missing in the draft y relative to the target p within the subset U! The reverse divergence
3

---

Published as a conference paper at ICLR 2026
Dr (q.p) measures the corresponding excess mass. In the whole space Ω2 this is symmetric (see Lemma in Section A.1 ) and reduces to the divergence from Leviathan et al. (2023) (see Lemma in Section A.4), which underpins standard loken-wise speculative decoding.
Next, we formalize the condition under which the partial target distribution is fully recoverable:
Theorem 1. Partial Distribution Recovery. A target distribution over St' S 92 can be fully recovered via resampling iff Dp. & Dr (g.(p.)) p). (See proof in Section A.2.)
Intuitively, this ensures the "trigger mass" the draft is sufficient to compensate for the deficit in the larget distribution. Over the full space Ω2 symmetry guarantees full recoverability.
4.2 RESAMPLING WITHIN THE ACCESSIBLE BRANCII
With these definitions, we analyze resampling within accessible branches along draft sequence. Although computing full joint probabilities is intractable, the probabilities of all next tokens over the vocabulary are accessible given any prefix X 1.t-1. We define branch as:
Branch(X x1--1) = (X = (XI+)1, 0; E V).
(5)
Branch divergence will guide redistribution of excess probability mass to correct local deficits.
Since only joint probabilities p(X1x)) 1x) within a given branch Branch X 1a-1) are available, we introduce branch divergence to quantify local deficits in the draft:
Definition 2. Branch Divergence
Branch (p.g X 1
Σ
max (ex (X 2 (x.)),
13))
(6)
X BBranch 1
Branch divergence captures how much probability mass is missing locally. Unlike total divergence, it inherently asymmetric, motivating the definition of branch asymmetry:
Definition 3. Asymmetry of Branch Divergence
ABranhh X 1:t-1)
D Deanch (p,g q x1a-1) DBaanhh (g.
X (1:t1)
Asymmetry essentially reflects the probabilistic imbalance within the current branch. Here, Branch > 0 indicates a deficit that cannot be corrected within the branch alone, while ABranch represents excess mass available to support other branches. It can be computed as follows:
Theorem 2. Quantifying Asymmetry of Branch Divergence (see proof in Section A.3);
A Branch
X x1=-1) p (X
(X::-1),
(8)
From Theorem I and Theorem 2, we conclude that resampling can fully recover the target distribution over branch whenever the draft has enough probability mass to cover the deficit:
Corollary The target distribution over the Branchi X x1+-1) can be recovered resampling. under the following condition:
0(X1=-1) S 9(x1=11) or, equivalently,
r(X $1
where (X 1xt=1)
p (( denotes the probability ratio.
For drafts of length the full target distribution cannot be recovered by applying verification solely within the accessible Branch(X X 11:--)). However, we observe that the unused probability mass in certain branches can be leveraged to compensate for the unrecoverable mass in other branches, from statistical perspective. This motivates the hierarchical branch resampling approach discussed next.
4.3 RESAMPLING IN A HIERARCHY OF ACCESSIBLE BRANCHES
Accessible branch divergences naturally form a hierarchical structure that enables systematic redistri- bution of excess probability mass. Specifically:
Theorem 4. Hierarchy of Branch Divergence
4

---

Published as a conference paper at ICLR 2026
The total positive asymunetry branch divergence across child branches is equal to the parent branch divergence, and vice versa. Specifically:
Σ Amarch
A Branch X
1:t- 1:2-2, 1t-1 Branch (p, X xitt2), and vice versa, (10)
( (x1. 2. 1)20
where X 1 -t-1 ranges over all possible Branches with the shared prefix 1:t-2, and X 1 the accessible branch along the draft sequence. (See Section A.5 for the proof.)
This result guarantees that excess mass from overrepresented branches can be aggregated to offset deficits underrepresented branches. Thus, hierarchical branch resampling guarantees exact recovery of the target distribution, even when individual branches cannot. This provides a rigorous theoretical foundation for deriving Hierarchical Speculative Decoding.
Algorithm Naive HSD
Algorithm HSD
Require: Target probabilities: (p()), pl 1x))
Require: Target probabilities: [p(-), pf X 1nn)
Require: Draft probabilities: {g( - .... q( 1))
Require: Draft probabilities: {g( ), .... q( 111-111
Require:
Draft tokens X 1: = [T1, Fzg
Require: Draft tokens X i: = [21,
1: Initialize т =
1: Initialize r =
2: for t in 7 do
2: for t in
do
Sample 7/ (O,,
3: Sample т ~ (00,
4: hr 2 T/ then
4: if he 2 1/e then
5: Set
#accept X 1tt
T
#uccept X
6: break
break
7:
else
else
8: Set r 1
#reject æt
9 88
#reject xt #step back
9: continue
#step back
continue
10: end if
10: end if
11: end for
11: end for
12: r = then
t y then
Sample token from 11))
#bonus token
Sample token from p( 11)))
#bonus token
14: else
else
do 16: Sample token from (- X X1:e) #resample
15: for / in
15: Sample token from P% X1:)) #resample
16:
end if
17:
end for
Ensure: [X I token]
18:
end if
Ensure:
HIERARCHICAL SPECULATIVE DECODING
Guided by the theoretical foundations, first develop naive algorithm (see 5.1) that exactly recovers the target distribution. The procedure evaluates a candidate sequence 1 and scans backward identify the longest accepted prefix X 1:r, then recursively resamples positions + through " using the corresponding distributions from the resampling hierarchy.
This naive approach, however, still requires 7 the resampled branches are inaccessible. To remove this overhead, we introduce Capped Branch Resampling, yielding our final Hierarchical Speculative Decoding (HSD). HSD recovers the target distribution with just one resampling step within the accessible branches. Concretely, after the resampling step at line 15 in Algorithm 2, HSD only needs sample from the target distribution to continue generation until which can be replaced by another speculative decoding step, climinating additional target calls.
1 additional calls to the target model, since
5.1 NAIVE HIERACHICIAL SPECULATIVE DECODING
Specifically, the acceptance probability is computed according to the following formula:
5

---

Published as a conference paper at ICLR 2026
Acceptance Probability h. min(((X1::)) 1xy), 1}, and when 9:
D Branch (p. q x1:e)
(11)
max Branch (p, X 11t),, Dranch (q: X 11:)]
Branch Resampling Probability (line 17 in Algorithm 1):
Pres (rt X 11:-1)= max {p (X 1:1) 9 1xx))
(12)
Branch (p, X (1:-1)
Branch Divergence Drracch
X 1st-1) 1 is defined in Definition 2. By construction, the
Branch Resampling Probability is defined within the accessible Branch( (X 1:t-1), i.e., Pres (e 1:t
Branch X X1t-1)), which reduces to the token-level form (x X 11:-1).
The probability of the Target Model generating a sequence X 1:y can be decomposed into two disjoint events: (i) full acceptance of the draft, or (ii) at least one rejection followed by resampling:
P P(X1: is yielded)
P(X 1 sampled as draft, 1:7 is accepted)
Σ
P( Ioy sampled and rejected, X X resampled).
(13)
x 1:
Accept term: probability for the case when X boy is sampled as draft and then directly accepted.
P X 1ny is sampled as draft, X 1:7 is accepted)
q X 1:7
min(r(X min(r(X1.)):)
(14)
sample probability
accopt probubility at
If (r((1 < 1, this equals to the target probability p 11y)) Otherwise, it is equal to g( X 11n), and the residual probability p( X 1:,) - (X,, 1.7)) is compensated via resampling.
Resampling term (partially resampled): This term accounts for all cases where X 1:y is obtained by resampling. Note that the accepted prefix must exactly match the corresponding subsequence of X 1:7 for this contribution to apply. Therefore, we can further decompose it by summing over all possible positions 1 of the first rejected token, with r being the length of the longest accepted prefix:
Σ
Σ
P(X1.y boy sampled and rejected, X 1iy resampled)
X
(15)
Σ
Σ X.+1o
x+17)) II (1 h2) h, 1: (=++1
II Pre((rt)
Explanation of terms:
1. Sampling: x(X 1:r x is the probability of generating the initial draft sequence.
2. Backward Scan: I1: (1- corresponds scanning backward from the end, rejecting tokens until the first accepted prefix is found.
3. Acceptance: h, is the probability of accepting the longest prefix X1.T-
1:r-
4. Resampling: [[ (re)(T:) resamples the remaining positions to recover exactly the target probability.
This decomposition defines the procedure underlying Algorithm 1 and provides the basis for its provable losslessness. The complete proof is given in Section B.2, together with an illustrative example Section B.1 showing how naive HSD recovers the target distribution.
5.2 HIERARCHICAL SPECULATIVE DECODING WITH CAPPED BRANCH RESAMPLING
To introduce the capped branch sampling, we first define the Maximum Prefix Ratio Index.
Definition& 4. Maximum Prefix Ratio Index For candidate tokens Lat the Maximum Prefix Ratio
Index m(X (X ia) is the position in the prefix X i:t1 where the joint probability ratio r(X 1:)) is
maximized; no prefix exceeds 1, we set m X 1:t) = 0:
m X (.x) arg max r X 1.)) or 0 if max ( S 1.
1513
15ist

---

Published as a conference paper at ICLR 2026
Based on the Maximum Prefix Ratio Index, define the Capped Prefix Ratio r" follows: Definition 5. Capped Prefix Ratio
r' (X1aa) minfr(X 1am(( (am(X (arg))..rr(( 1 ml x1a)+1a))
(16)
By Definition 5, have (x))))X))))) 1, and according to Equation (16), this implies the
identity r" (x)) r(X m(X m(xu))+1:).
Then we define the Capped Branch Divergence: Definition 6. Capped Branch Divergence
Branch (p,g) X 11t-1)
E
(r" (X 11) - 1 (Xis)
(17)
Er Xi 1): y' (X11>1
Branch (1,2) X (1:t-1)=
Σ
(1-r" (Xix)) (X
(18)
X1. Branchh 1 11: y" r'(X
Finally, the acceptance probability is computed according to the following formula:
Acceptance Probability h, min( (X 1:y), 1}, and when i <
he Dramch (p. 11a)
(19)
D Branch (q- P X1:e)²
Capped Branch Resampling Probability (line 15 in Algorithm 2): res
max {q (X (X1.) (r" (X1:t) 1),0} X X1+-1)=
(xt
(20)
Dranch (p, X (1s-1)
We refer to the above strategy as Capped Branch Resampling. It plays a central role in enabling effi- cient resampling within the hierarchical branch resampling framework. The resampling distribution in Equation (20) enables recovery of the full target distribution with only a single resampling step for branches with negative asymmetry. The remaining positions then be directly sampled from the target model, aligning with the start of the next speculative decoding step and thus incurring no extra computational cost.
We briefly clarify the core mechanism by which capping preserves the target joint dis- tribution. From Definition 5 and Definition 6, it follows that Diranch (p.q X1:))
Ex X 1.111) max(q (X (X.mm(x..)) .))) p (X m(Xx..)) +1x) - q (X1:)) 1,:)),0 00. Through the accep- tance probability and resampling probability at position we essentially guarantee that the probability mmX1.)) m(x partially recovering the probability of the fragment X mi "x((,,++1:+ And the deficient probability mass p( X 11mmXx..)) - (X( 1.me (..)) statistically recovered from the resampling distributions in higher hierarchies, which corresponds to the fragments X (x.)) of other trajectories. An illustrative example in Section C. demonstrates
of obtaining X 11: is equal to q (X 1.m(( (mnXx..)) )
how the algorithm recovers loss over the entire path, with further explanation of the capped ratio provided in Section C.3.
5.3 COMPUTATIONAL EFFICIENCY
The verification stage in HSD adds negligible overhead compared to the savings from reduced target model forward passes. Thanks to parallelized computations across both the vocabulary and draft positions, HSD is nearly as efficient as tokenwise verification. Runtime measurements (Appendix H) show that verification accounts for less than 1% of total decoding time, with the majority still spent on draft and target forward passes. These results demonstrate that HSD is not only theoretically lossless but also practically efficient, further confirmed by experiments in Section 6.
7

---

Published as a conference paper at ICLR 2026
GSM8K Example
Eliza's per overtime of 1.2 times her regular hourly rate. If Eliza worked for 45 hours this week, much cernings
first
each
receives
week?
determine Elisa's earnings for the week, we need to caloulate both her zeqular pay aer overtime pay.
A*Calculate Regular Pay:
2liza's s reguler rate is $10 pes hour. worked
her regular rate. Regular pay: 40 hours $10/heur $430.
2. CCCsculste Overtime Pay:** sliza worked z totel of 45 hours, 50
Figure 2: GSM8K question with the generated prefix. The text shown is the printed output of the decoded string in Markdown format.
5.4 I.LUSTRAATVV EXAMPLE
We use a GSM8K question running example demonstrate HSD (see Figure 2). This example emphasizes the hierarchical acceptance mechanism and the capping behavior that are key to HSD.
Next-token probabilities. Under the given prefix, the large (target) and small (draft) models produce the next-token probabilities:
[p(- X1:y) (0.7156, 1.0000, 1.0000, 1. 1.0000, 0.0000, 0.0000, 0.0000, 1.0000, 0.0000, 096998). [g(: X1:)} (0.8771, 7.7000, 0.6514, 0.2522, 1.6773,0014990 0.5775, 1.0000, 0.4611, 0.3630).
The corresponding draft tokens are: fshe, work, ed, 45, 5, houros of}.
Joint probabilities and ratios. We compute the joint probabilities along the draft:
(p(X):))liz, (0.7156, 7.76,6, 7.7156, 0.7156, 0, 0).
(o(X).))7= (0.8771, 0.6929,699.... 13, 1.0 0.0792, 0.01 0.00000.8, 0.0068, 0.0031, 0.0011).
{r(Xi:)))7_1 (0.8159, 1.0327, 1.5835, 6.1171, 0, 0, 0).
These ratios exhibit early growth above 1 (at = 2, 3, 4) and collapse to once the target probability vanishes (from t 5).
Maximum prefix indices and capped ratios. imum prefix indices and capped ratios
Following Definition 4, the max- (Im(X..))7 (0.0..23.444444. and
are
(x=(Wr+)) = (0.8159, 11100000111
Capped branch divergences and acceptance. evaluate the capped branch divergences:
On the full vocabulary branch Branch XIx-1).
(Perauca q Xx.)))=11 = (0.0227, 2.2416, 0.3343, 0.0991, 0, 0. 0,
(Daranch (g.p) Xm: = {0.1842, 0.2416, 0.3313, 0.0792, 0.0991, 0.0118, 0. 0068, 0.0068, O. 0.0031, 0.0011).
The hierarchical acceptance (Eq. 19) then yields (hr) 10.123111
Acceptance saturates at f 2, 4, implying the first four tokens are validated, i.e., Amatch =
Comparison to tokenwise verification. For a tokenwise baseline that validates strictly left-to-right, the per-position magnitudes are (fh ((rtoboomrnn)) )7-1 f0.8159, 0,
Since the baseline commits at the first position, an initial h = 0.8159 may trigger rejection and discard the entire draft block.
8

---

Published as a conference paper at ICLR 2026
6 EXPERIMENTS
In this section, we empirically demonstrate the superiority of HSD with comparison on various benchmarks and configurations, comprehensive ablation studies, and in-depth analysis of results.
6.1 EXPERIMENT SETTING
Experiments Setup. Experiments are conducted with the widely adopted GPTQ-quantize 8-bit instruction-tuned Qwen2.5 series (Bai et al., 2023). By default, we employ the 0.5B as the draft model and 72B the target models, with temperature of 1. We leverage GSM8K (Cobbe al., 2021) for mathematical problem-solving HumanEval (Chen et al., 2021) for code generation, and CNN/DailyMail (See et al., 2017) for text summarization. All experiments were conducted on single NVIDIA H20 GPU with 96 GB of memory, unless otherwise specified.
Baselines and Metrics. We compare two lossless verification methods Tekss-Tooknwiiin and Block- dise-using two metrics: Block Efficiency (tokens/step) and Decoding Speed (tokens/second), Block Efficiency measures the average tokens generated per serial call to the target model, reflecting intrinsic efficiency independent of hardware. Decoding Speed indicates tokens produced per second for practical reference. Additional details and extended evaluations are in Section E.
6.2 EXPERIMENT RESULTS
Main results. Table summarizes the performance of HSD across datasets and model scales using the Qwen2.5 suite (0.5B as draft, 14B, 32B, and 72B as targets). Overall, HSD consistently improves both Block Efficiency (BE) and Decoding Speed (DS) relative to Tokenwise and Blockwise verification. For GSM8K, the gains are stable across scales, with BE improvements of -..4% at 14B/32B and 3.3% at 72B, accompanied by DS increases of up to 10.7%. 1.7. On HumanEval, the effect more pronounced: BE rises by 9.5% and 12.3% at 14B and 32B, while DS improves by 9.3% and 11.4%; even at 72B, HSD maintains positive margins 13.3% BE, 4.5% DS). For CNN/Daily Mail, the improvements are moderate but consistent, with BE gains of 4.2 %.44% and DS gains of 3.4% %. On average, HSD provides consistent advantages over Tokenwise and Blockwise verification, with improvements of approximately 6.2 % in BE and 6.7 % in DS.
Multi-draft. To demonstrate the compatibility of HSD, we compare it with token-wise verificaiton in a multi-draft setting. For simplicity- and without loss of generality-we adopt Recursive Reject Sam- pling (RRS) with replacement (Yang et al., 2024) the baseline for its scalability and independence from complex tree attention mechanisms. Notably, since it is not straightforward to extend blockwise verification the multi-draft setup, we omit from our comparison. We evaluated multi-draft generation with 11 candidate drafts in Table 2, and HSD yields an average 5.9% improvement in Block Efficiency and 4.7% improvement in Decoding Speed over token-wise -ise decoding.
Table 1: Comparison of Block Efficiency (BE) and Decoding Speed (DS) across datasets and model scales. Values in parentheses show percentage improvement over Tokenwise.
Method
Block Elliciency (Token//tepp)
Decoding Speed (Token/Second)
14B
32B
72B
14B
32B
72B
GSM8K
Tokenwise Blockwise HSD (Ours)
5.99
6.14
6.44
82.28
$3.87
31.49
6.13 (+2.3%)
6.26 (+2.0%)
6.53 (+1.4%)
86.06 (+4.6%)
54.91 (+ (+1.9%)
31.79 (+1.0%)
6.30 (+5.2%)
6.47 (+5.4%)
6.65 (+3.3%)
(+10.7%)
(+6.0%)
32.52 (+3.3%)
HumanEval
Tokenwise
4.83
4,89
5.23 5.34 5+2. 19%) (+3.3%)
74.21
45.68
26.31
Blockwise
5.11 (+5.8%)
5.15 (+5.3%)
(+5.39)
48. 15 (+5.4%)
26.96 (+2.5%)
(Ours)
5.29 (+9,5%)
(+12.3%)
$1.09 (+9.3%)
50.88 (+11.4%)
(44.4%)
CNN/Daily Mail
Tokenwise
2.39
2,36
2.35 2,39 (+1.%%
37.28
21.89
11.90
Blockwise
2,50 (+4.6%)
2.42 (+2.5%
38.54 (+3.4%)
22,31 (+199)
12.10 (+1.4%)
HSD (Ours)
2.59 (+8.4%%
2.46 (+4.2%%
2.45 (+4.3%)
39.96 (+7.2%
22.78 (+4.1%)
12.33 (+3.6%)

---

Published as a conference paper at ICLR 2026
Table 2: Comparison of our HSD and tokenwise verification in Multi-draft setting.
Black Efficiency (Token/Siep)
Decuding Speed (Token/Secuudd)
Method
GSMSK
HumanEval
Mail
GSMRK
HumanEval
MaNl
Tokenwise
6,44 6.65 (+3.3%)
5.23
2.35
31.49 32.52 (+3.3%
26.31
11.90
HSD (Ours)
5.40 (+3.3%)
(+4.3%%
27.48 (+4.4%)
12.33 (+3.6%%)
Tokenwise Multi-draft
8.65
7,96
35.72
15.38 16.75 (+8.9%
HSD Multi-draft (Ours)
8.89 (+2.8%)
8.26 (+3.8%)
4.21 (+11.1%)
38.41 (+2.0%
36,83 (+3.1%
Table 3: Ablations temperature, draft length, and target model size GSM8K. Except for the ablation on target model size, we adopt Qwen2.5-0.5B and Qwen2.5-72B as the draft and target pair.
(a) Ablation on temperature
10).
(h) Ablation draft lengths (f
Block Efficiency
Decoding Speed
Block Efficiency
Decoding Speed
Method
Method 7 5
0.6
0.8
1t 0.6 0.8
y 15 y 5 = 10 y 15
Tokenwise
6.81
6.70
6.44
32.86
32.18
31.49
Tokenwise
4,48
6.44
7.61
12.01
31.49
51.03
Blockwise
6.83
6.74
6.53
33.07
32.33
31.79
Blockwise
4.52
6.53
7.74
12.14
31.79
51.75
Hierarchicial
6.86
6.79
6.65
33.21
32.90
32.52
Hierarchicul
4.59
6.65
7.88
12.35
32,52
52.95
Table 4: Extended experimental results using the LLaMA model family and EAGLE-3 framework on GSMSK. Note that we replace EAGLEE-3's tokenwise verification with our HSD, yielding EAGLE--H..
(a) Evaluation using the LLaMA-3 model family.
(b) Integration with EAGLE-3.
Single druft
Multi Decoding Speed
Method
Black Eff.
Decoding Speed
Method
Decoding Speed
EAGLE-3
71.59
Blockwise
N/A
N/A
Tokenwise
6.83
8.41 8.87(45.5%)
8.72 N/A 9.00(+3.2%)
10.21
EAGLE-3H (Ours) 3.55()
10.4%)+
Blockwise
7,32(+7.259)
N.A
HSD (Ours)
7.43(+8.8%)
9.18(+9.2%)
(1.0((+7.9%)
Ablation on Temperature. We conduct a systematic evaluation of sampling temperature" effect on decoding efficiency, with / (0.6, 0.8, 1.0) (Table 3(a)). HSD consistently outperforms other approaches across all temperature settings, demonstrating its robustness to temperature variations.
Ablation on Draft Length. We evaluate draft lengths y E (5. 10. 15) tokens, where HSD consistently outperforms baselines with increasing efficiency gains (Table 3()).. At 15. HSD achieves peak performance with 7.88 tokens/step in block efficiency and 52.95 steps/second in decoding speed, representing improvements of 3.58% and 3.88% over Tokenwise, respectively. The consistent performance advantage across all draft lengths demonstrates HSD's robust scalability.
Extended Results. We conducted additional experiments using Llama-3.1 3........BBBBB 1.11--0B-Insstrce Instruct and Llama- 3.1-8B-Instren pair (non-quantized version), with model weights distributed 8 H20 GPUs. The results are shown in Table 4a. Moreover, we integrated HSD into the SOTA HAGLE-3-LLaMas.] Instruct-8B (y 7) by replacing its tokenwise verifier in Table 4b. Following EAGLE-3, accept at least the first draft token for a fair comparison. Note that EAGLE-3 utilizes top-K sampling for drafting, making all draft probabilities equal 1. In this case, any verification method theoretically degenerates into the same behavior and the observed gain in block efficiency of HSD is likely influenced by sampling stochasticity and floating-Pon point precision. However, the observed significant practical speedup in decoding speed is expected, since our implementation (see Section F) avoids the explicit loops in EAGLE's implementation of tokenwise verification.
7 CONCLUSION
We present HSD, lossless verification method that maximizes accepted tokens while provably preserving the full target distribution. Supported by theoretical guarantees and extensive experiments, HSD consistently accelerates inference across models and benchmarks. Its drop-in integration with frameworks like EAGLE-3 demonstrates both practicality and broad applicability. HSD sets a new standard for efficient, lossless speculative decoding in large language models.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Josh Achiam, Steven Adler. Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. Qwen technical report. arXiv preprint arXiv:2309. 16609, 2023.
Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D Lee, Deming Chen, and Tri Dao. Medusa: Simple IIm inference acceleration framework with multiple decoding heads. In International Conference Machine Learning, pages 5209-5235. PMLR, 2024.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Ka- plan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Vosss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang. Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Car,, Jan Leike, Josh Achiam. Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katic Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code, 2021. URL https:
pesttss//arxivve http///axvvvvroeo org. /a///bb//// 220//2107.22 03374.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems, 2021. URL htRp::t/s//axii org/ abs/2110. 14168.
Cunxiao Du Jing Jiang, Xu Yuanchen, Jiawei Wu, Sicheng Yu, Yongqi Li, Shenggui Li, Kai Xu, Liqiang Nie, Zhaopeng Tu, et al. Glide with cape: low-hassle method accelerate speculative decoding. In Proceedings of the 41st International Conference on Machine Learning, pages 11704-11720, 2024.
Jiaming Fan, Daming Cao, Xiangzhong Luo, Jiale Fu, Chonghan Liu, and Xu Yang. Flatter tokens are more valuable for speculative draft model training. arXiv preprint 27X1v:2601.18002, 2026.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv: 1803.03635. 2018
Jiale Fu, Yuchu Jiang, Junkai Chen, Jiaming Fan, Xin Geng, and Xu Yang. Fast large language model collaborative decoding via speculation. In International Conference on Machine Learning, pages 17764-17782. PMLR, 2025.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501. 12944488, 2025.
Zhenyu He, Zexuan Zhong, Tianle Cai, Jason D Lee, and Di He. Rest: Retrieval-based speculative decoding. arXiv preprint arXiv:23/ 1...22//.00822,, 2023.
Zhengmian Hu, Tong Zheng, Vignesh Viswanathan, Ziyi Chen, Ryan A Rossi, Yihan Wu, Dinesh Manocha, and Heng Huang. Towards optimal multi-draft speculative decoding. arXiv preprint 1877: 2025.
Schoon Kim, Karttikeya Mangalam, Suhong Moon, Jitendra Malik, Michael W Mahoney, Amir Gholami, and Kurt Keutzer. Speculative decoding with big little decoder. Advances in Neural Information Processing Systems, 36:39236-39288 2023.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pages 19274-19286. PMLR, 2023.

---

Published as a conference paper at ICLR 2026
Yuhui Li. Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle: speculative sampling requires rethinking feature uncertainty. In Proceedings of the 41st International Conference on Machine Learning, pages 28935-28948, 2024.
Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang. Xiaoxiang Shi, et al. Specinfer: Accelerating large language model serving with tree-based speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, pages 932-9999 22-999 2024.
Giovanni Monea, Armand Joulin, and Edouard Grave. Pass: Parallel speculative sampling. arXiv preprint arXiv:2311.1358/1 2023.
Harikrishna Narasimhan, Wittawat Jitkrittum, Ankit Singh Rawat, Seungyeon Kim, Neha Gupta, Aditya Krishna Menon, and Sanjiv Kumar. Faster cascades via speculative decoding. arXiv preprint arXiv:2405. 19261, 2024.
OpenAl. Openai ol system card. https: https///ara.v..r//aab////// 2025-05-12.
2024. Accessed:
Yingzhe Peng, Gongrui Zhang, Miaosen Zhang, Zhiyuan You, Jie Liu, Qipeng Zhu, Kai Yang, Xingzhong Xu, Xin Geng, and Xu Yang. Lmm-rl: Empowering 3b Imms with strong reasoning abilities through two-stage rule-based rl. arXiv preprint urXiv:2503.07532 2025.
Zongyue Qin, Ziniu Hu, Zifan He, Neha Prakriya, Jason Cong, and Yizhou Sun. Optimized multi- token joint decoding with auxiliary model for 1lm inference. In The Thirteenth International Conference Learning Representations, 2025.
Abigail See, Peter J. Liu, and Christopher D. Manning. Get to the point: Summarization with pointer-generator networks. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 1073-1083, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.18653/v1/PI 1//65//11P171111 1099. URL https: // //www. web............................. org/ wwt.pe/..w.ttttooggggooo/ 2aatthollgy/11111099
Sheng Shen, Zhen Dong. Jiayu Ye, Linjian Ma, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Q-bert: Hessian based ultra low precision quantization of bert. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 0815-8821, 2020.
Mingjie Sun, Zhuang Liu, Anna Bair, and Zico Kolter. A simple and effective pruning approach for large language models. arXiv preprint arXiv:2306.1 11695, 2023a.
Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems, 36:30222-30242, 2023b.
Ziteng Sun, Uri Mendlovic, Yaniv Leviathan, Asaf Aharoni, Ahmad Beirami, Jae Hun Ro, and Ananda Theertha Suresh. Block verification accelerates speculative decoding. arXiv preprint MrXi::2403.10444 2024.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09286 2023.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac. Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the-art natural language processing. In Qun Liu and David Schlangen, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38 45, Online, October 2020. Association for Computational Linguistics. doi: 10. 1/218/3//11222000mmmm URL https::////......... / allland antho -org/oorrr.o 2000. emn e 6/.
12

---

Published as a conference paper at ICLR 2026
Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-tran post-training quantization for large language models. International Conference Machine Learning, pages 38087-38099, PMLR, 2023.
Nan Yang, Tao Ge, Liang Wang, Binxing Jiao, Daxin Jiang, Linjun Yang, Rangan Majumder, and Furu Wei. Inference with reference: Lossless acceleration of large language models. arXiv preprint arXiv:2304.04448, 2023.
Sen Yang. Shujian Huang. Xinyu Dai, and Jiajun Chen. Multi-candidate speculative decoding. arXiv preprint arXiv:2401.06706, 2024.
Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, et al. Dapo: An open-source Ilm reinforcement learning system at scale. arXiv preprint arXiv:2503. 14476, 2025.
Jun Zhang, Jue Wang, Huan Li, Lidan Shou, Ke Chen, Gang Chen, and Sharad Mehrotra. Draft& verify: Lossless large language model acceleration via self-speculative decoding. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 1263- 1282, 2024.
Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Rostamizadeh, San- jiv Kumar, Jean- Françrioço Kagy, and Rishabh Agarwal. Distillspec: Improving speculative decoding via knowledge distillation. In The Twelfth International Conference Learning Representations, 2024.
APPENDIX
THEORETICAL FOUNDATION
A.I SYMMETRY TOTAL DIVERGENCE
Lemma 1. Symmetry of Total Divergence.
Dalp,g) = Da(g.p).
(A.1)
Proof. From Definition 1, we know:
Da(p. q) Da(g.r)= = Σ max (plo) -(()).0}
Σ
max max (g(w) - p(()) 0)
WEN
WEn
(p(0) g(0))
(g(() p()))
Wen
WEN (()>>(())
(A.2)
())2((()
Σ p( Σ q(w)
GER
GER
= 0
(since both and sum to over the full sample space ?2)
Thus, De(p, q) = Dalg. p), completing the proof.
A.2 PARTIAL DISTRIBUTION RECOVERY
Proof of Theorem I. Let P(w is yielded) denote the total probability of producing w E S.. By construction, this can be decomposed
P(w is yielded) P(w is drafted & accepted) P(w is drafted & rejected, is resampled), (A.3)
where acceptance occurs with probability h(w) ((w/pppw////u) 1}, and resampling follows the distribution P. |2') with total trigger mass Drr (g. p). Here, the total trigger mass represents the sum of probabilities of all draft outcomes in S that rejected. Hence,
13

---

Published as a conference paper at ICLR 2026
P(w is yielded) ((w)((w)) + Dar (g,D)) Pres(1 12).
(A.4)
Noting that h(w) g(w)) = min(p(w),, we have
P(w is yielded) min(p(w), q(w) Dr (q, p) Pre(ww I
(A.5)
To match the target distribution exactly (P(w yielded) p(w)), we require p(w)=
g(w)) max(p(w) - g(w),
(w (2)
(A.6)
Drr (g.p)
Der Drr(1.2) p)
Summing over all E St gives
Dar(p: 9)
Σ Pres (')
(A.7)
Dar (g.
For (- (2') to be valid probability distribution, this sum must not exceed 1. Therefore, the necessary and sufficient condition is
Drr (p. I Dir
(A.8)
which completes the proof.
A.3 QUANTIFICATION ANALYSIS OF ASYMMETRY
Proof. From Definition 3 and Definition 2, obtain:
A Branch (X (x11-1)=
Σ
max tp (X1:)) - (X:),,, ,0
X BBrunch 11
Σ
max E4 (X - p (X
X BBanchhf (1)-))
Σ
p (X11))
Σ
q (xx1.)
(A.9)
X1 C.ranBBrhh (1
X E.ranchhhhi X 11a-1)
Σ p X 11111)((1; (1=-1)= - Σ q (X 11-11 X1s-1)
=
FiEV
J.EV
(X==-1) - (X (since Σ p(z: X x1=-1)=11 =1)
2.EV
A.4 RELATION TO THE DIVERGENCE IN LEVIATHAN ET AL. (2023)
Lemma 2. The total divergence is equivalent to the divergence defined in Leviathan et al. (2023) for token distributions over the full sample space.
Proof. Following Leviathan al. (2023), let ă denote token, and omit conditions in the token probabilities for simplicity. From Definition 3.2 in Leviathan et al. (2023), we have:
p(ī) (())
Dix(p.9) q)
Σ
BER
(A.10)
Σ max (p(x) g])),0)
0)
Σ - p()))
sen
14

---

Published as a conference paper at ICLR 2026
From Lemma 1, we know that (p(p.9) 9) = Dz(q. p). so can write: Da(p, (a(e, q) + Dn(g.p)
2
(A.11)
Σ FEE
max -3 +
Σ
max - p(z).
2
seft
Therefore, Dn(p.q) (p q), completing the proof.
A.5 HIERARCHY OF DIVERGENCE
Proof. Proof of Theorem 4. From Theorem 2, we recall that:
Branch [ 2.--2, = p(X 12-22 (( 1=2,,
(A.12)
Therefore, summing over the cases where this difference is positive gives:
Σ
A Branch
X 211))
Σ
max (p(X 11-2, 21 8t-1),
Anmrc (X (11-2
LEV
(A.13)
By Definition 2, this is precisely the branch divergence one level higher Draanch (p. X (1.-2), thus completing the proof.
LOSSLESS NAIVE HIERARCHICAL SPECULATIVE DECODING
B.1 I.LUSTRATIVV EXAMPLE
For example, consider the case where r(X 1zy) 1, r(X1:x(1) 11y-1) > 1, and r r(X 1:y r(X I 1. The accept term is simply equal to q( ((x1,))) 1:7), so we only need to check whether the resampling term equals 1(x) q( X 1-v)- According to Equation (12), know ( X 1 0. Consequently, contributions from positions earlier than 7 in the sum above vanish, which implies that the resampling term for X Iny arises solely from resampling positions y and 7 follows:
P (sample 11,,100,, reject ã., accept X 1 resample x.,++
P(sample X 1 reject X 1:y accept X 1:y-2 2 X x
Σ q( (1)))
h1h
Pre (x²))
+
(A.14)
drafi pritability
reject backwards
accept 1ev
resample at + =
Σ 2x--1
X 1:y-2
(1 h- h
Pres (2 -1 1 (x))
drall probubility
reject backwards 7+1=7-1 accept X 1iy-1 resample +1 +1
From Definition 2 that the excess probability mass that triggers resampling DBranch (g.P) p X 119-1) = Σe, 11 hy). Then we have:
=DBranch (q. p X 1 p (( q(x111 1:x)
DBeanch (p, X 111-1)
(A.15)
DBrnnch (g. pl 1 1)(1 Drrunch (p, q/ 22 Pres (17- By
Damnch (g.p) X| In 2
From Definition and Theorem 4, we know that Ea,1 DBranch P/ 1:7- -
Drranch (p, q X 1: 11 Drranetl (q, p X|x111-22 1:7-2). Then have:
DBrnnch q, p) X 11)--1 (p(X 1.7) 9(X (++))))+
DBranch (p, X 11)
(A.16)
D Drramch (g. X1 21)-2)- pl 1:y- 1) q 11:y-1)
p( ((11x) 9(x1111)
D (p. g X (17-2)
D Drranch (p. X 1:7-1)
15

---

Published as a conference paper at ICLR 2026
We know from Definition and Theorem 2 that p(X1:)) - 9(X1;)) Drranch (p: q 11:--11..
Branch (q, p J (1n- Then have:
Dranch (g, p) X 117-1)
Branch (p, q X 117-1) (p(X1.y) 1:y) g( ((X11)))+
D Branch (p, q X 119-1) DBranch(qss X X119-1)), (p(X11)) - ((x1:)))
(A.17)
Drranct X 11
= =p(X - 4((x(1))
Σ ((X 1 y is sampled, I. is rejected, X 11g-1 is accepted, xy is resampled) +
(A.18)
By
Σ P(X17-2XX 7-11-111 1s sampled, 7- 1s rejected, X X1:-- accepted, X 7- resampled)
X 7-11
(A.19)
Σ (( ((1))))ūm)) By
(1 hr)
h
Pres (xte)
+
(A.20)
drait prububillity
reject buckwards +
accept X 11
resample +1=9
Σ Σ 24-1 By.
g(X ((111) 1
(1 - h1 - h
h
(1
(A.21)
draft probability
reject backwards
---1 accept 11n-1
resample at + +1
From Definition 2 that the excess probability mass that triggers resampling Drranch Σn, (X11.11))))) 12 hy)) Then we have
X 117-1)>
((x 1.7) ( 1:7))
Dranch (g. 1 1.
(A.22)
Deancch (p, X 1:7-1)
Dranchh (p, X 1:g 1::-22ūg-11 2 Pres (Fn Prea
Dirrach (g. X ln 2 2ū) D Drranch (4, P..plll X 1:g 1: 2
(A.23)
From Definition and Theorem 4, we know that Σx,,1 D Drranch (1, 2:0-1) DBranh (p, X 11y-28 = Drranch (q, pl X 12) Then we have
DBrnnch q, x 1011111111 1-2-1) (p(X 1:7)) 9( ( 1
(A.24)
DBranch (p, X 11y-1)
p(X 17-11) 9( X 117-1) DBranch (p, X 1 Drannch (p, 9 1:7-1)
p(X 1:m 9(x (117))
D Branch (g. (2)
(A.25)
We know from Definition 3 and Theorem that p(X - g(X 1m Drrnch ( pl 11y-1). Then we have
DBranch (p, q X 197-1)
Drrnnch q, pl X|x 1:1-1) (p(X (.7) (++))
(A.26)
Drannhh (p, q) X 11y-1)
(Drranch (p, X1 x1y-1) 1)- Drraacchag.p X 11)-))), - -((11,)))
(A.27)
Drrnnch (p.4
X (19
=P(X1.) - (((1x.)
(A.28)
B.2 GENERAL PROOF
Lemma 3 DesectiionReesmmlinng Sum Reduction (Tokenwise)). Let 0 < m < be such that the acceptance ratios satisfy:
r(æ,)) > 1, r(x4-1) >>> r(c,-m41) >,, r(z S 1.
(A.29)
Then, the total probability of obtaining the output via resampling over the last m positions is:
P( is rejected) II P(X is resampled) (((11x) q(x1.)) 1:7)
(A.30)
16

---

Published as a conference paper at ICLR 2026
Proof. We begin by defining auxiliary quantities to simplify the notation. For I...., m, let
A = Branch (g. A = Branch (p. Xis-s);
X Ki9-s),
(A.31)
where A quantifies the probability mass to be corrected due to overestimation by q, and A represents the mass available to be allocated from alternate paths.
Define also the recursive product term:
Aj
P
for 0 Sis m 1.
(A.32)
A+
==0
H+
Using these, the rejection-resample contribution becomes:
P( is rejected) II
P(X Ioy is resampled)
1=0
(A.33)
A, P. + (4 m-1
Now observe the recurrence:
A Pk+1 (A -
(A.34)
which implies:
( - -.) A PA-11
(A.35)
We apply this recurrence in reverse simplify equation (1) by telescoping the sum:
m-1
2
A, P. + (A - Pm
A. P: + + m- Pm-1
i=1
1=1
A P. + A m- 12-2pmm2
(A.36)
At P1
A - A
p(X 1my) q(X 1,)),
where the final equality follows from the definition:
A AJ = Dreanch (g.p) X X1z)) Dreanch (p.gl X X1,)) (((X1z) g(x
(A.37)
This completes the proof.
Lemma (No Resampling of Earlier Prefixes (Tokenwise)). Let X1.x 1:y = [x1, D2,..., R.y] be a token block, and suppose that for some index m, the acceptance ratios satisfy:
r(x,)) > 1, r(x4-1) >1, ..., r(x,)-41) > 1, r(xg-m) S1.
(A.38)
Then for all t S m. the resampling probability satisfies:
P(X 1: is resampled) 0.
(A.39)
17

---

Published as a conference paper at ICLR 2026
Proof. We use the resampling probability formula:
max {p([ 12) ( 1.e,, ((11)))) 0f
Pres X 1aa) max Branch (p.q X X1:), Drranch (g. P X {
(A.40)
At position 1. 1= - m, we are given that the acceptance probability
{1, p( (X 1:n-m) 11
r(xy-m) min
(A.41)
9 117-m))
implying pl I:y-m) q( 1:7 m. Therefore,
1m)-m 9( X 1:g-m) 50,
(A.42)
and hence:
Pres X (1:y-m)) O.
(A.43)
This completes the proof.
L
Theorem 5 (Lossless).
P(yfeld X = ((11)))
(A.44)
Proof. The total probability the of the acceptance and resampling paths. We analyze cases based on the relative probabilities.
Case 1:
1.)) (X 1:7) In this case, the acceptance probability for the draft is p x The
(x,,''
probability of generating X1zy via resampling is O, as there is no probability deficit to recover.
P(yield X1n) P(X1:) 1: is accepted) P(X1: is resampled)
p(X1.) 1:7)
+0
(A.45)
q q(x 1m7)
=p(X 1:y)
Case 2: p(X (X 1:y) Here, the acceptance probability for the draft is 1. The resampling path must compensate for the probability deficit. Per lemma and lemma 4, the total probability of all relevant resampling paths is exactly p(X,,
1:y) q( ( 1.y).
P(yield X1n) P(X 1n is accepted) P(X 1:y is resampled)
=( 1:)) 1 (p(X - ((11)))
(A.46)
=p(X ((X)
These two cases cover all probability events. In both cases, the total probability correctly recovers p(X1z)) proving the method is lossless.
LOSSLESS HIERARCHICAL SPECULATIVE DECODING
C.1 ILLUSTRATIVE EXAMPLE
Let p(-) be the target and q(-) the draft. For prefix X 1:s
p p(X1a)
p (
Xatibb
X 1:a)
r(X11)
r(X+11b
X1:a)
q ( 12))
g(Xa+1.b
X 1:a.)
so r (X rl X 1:a) ( x X 1..)). Let m be the last (largest) index y at which the running
maximum of r( (X1,) x1a) is attained and exceeds 1; let n < m be the previous such index (two-peak case).
18

---

Published as a conference paper at ICLR 2026
As definition 4, define the capped ratio at the end of the draft as
1" (X 1:) min(r(X 1:m)) 1) r (XXm+1m m+1177 and the accept term
X Xim) = r m+loyy X (1mm) S 1,
r' A, = g 1x1 (X
We will also use three resample contributions: T, (at level y), T' (at level m)) and Ta (at level n)) two-peak example: n < m < 7 From definition 4, we have r(X Im)) > 1, then r(X 1.m) > r( Im). and no larger value occurs in (m, This forces r r(X n+ Iam could not be a new maximum.
X l.)) > 1; otherwise m
Step 1: accept top-level resample Since r* 1:y) (XX
(m(mmmxi m++1y
X Xim) S 1,
Ag
q( 1:n) r(X m+1
X Ism) = q(X 1:m) p(X mly X 1mm),
Ty 0,
H1 = Ar +T = 1(m) p( X m+1ry 11m) The suffix X +m+lor 1oy is now under pž the prefix X Jam is still under Step 2: add the m-term Let Rn-mm = r(X,,, I contributes
Intuition.
q.
X 1m))
The resample at level m
Tm == ((1mm)) (Rn-m 1) p m+1ry
X 1:m):
hence
H2 = H1 Tm Rn a( (11m)) pl m+ X 1mm) al (()mm) (( Intuition.
n
X Xmm).
The block X xmm is converted to p: only X remains under g. Step 3: add the n-term ((x(((1)) 1.
Tn == q(X1x1) (r 1mn) 1) pl X 1+1
X 1In),
H3
H₂ + TTa = 11))-))-
instead r(X (1)) 1, then T, 0 and H₂ 11)) already.
Intuition. Each nonzero term "tops up" the exact deficit of q on its block until the whole path is under p. Thus
A, +1, + Tm + T p(X 107)
in this two-peak case, exhibiting the (lossless) invariance of the total probability under the HSD accept-resample rule.
C.2 GENERAL PROOF
Definition 7 (Sequence of Unique Capping Indices). For given maximum sequence length 7 the sequence of maximum prefix ratio indices (mm(1, m())....,m? is generated according to Definition Let L/ the of unique values in the sequence of capping indices:
U |
(A.47)
The Sequence of Unique Capping Indices, denoted by M the ordered sequence of the elements in 2/:
M (mi mi)
(A.48)
where m <... mi and L is the total number of unique capping points.
With these definitions, we can now establish the key properties of the prefix-capped joint ratio: Lemma 5 (Property of (X between neighboring unique capping indices). Let mi and m be two consecutive unique cupping indices, and suppose
mi < mi+1-
(A.49)
For every such i, have r (X1.)) 1.
19

---

Published as a conference paper at ICLR 2026
Lemma 6 (Property of r" 11mm)) at unique capping indices). Let m and mi be consecutive unique capping indices, we have
(" lsmm))
r( (
We now define the acceptance and resampling probability masses:
Definition 8 (Accepted Probability Mass). The probability mass for accepting the full sequence 1 is:
P(X Ioy accepted) = (xin,),""Xx..)))) 1:::)):
(A.50)
Definition (Resampling Probability Mass). Let X 1:y be full sequence of length Y, and let M = (m ........ m be its Sequence of Unique Capping Indices. The total probability mass under the draft q and target p of generating this sequence can be decomposed as:
Total Generation Probability
P( P(X1, u, is generated) = P(X 1.y is accepted) + P(X 1oy is resampled)
min (1, r" (x1))) ((11)))
max(O, r (X mi_, + [mmm)) 1) q( X XImm p(X m X (X.m;)
+ max (0, r r" (X1x)) gl (1 X11--1)
(A.51)
We now establish the key lemma that characterizes the resampling probability mass:
Lemma 7 (Hierarchical Resampling Probability Mass). The total generation probability can be decomposed into acceptance and resampling masses stated in Definition 9. Only unique capping indices contribute resampling mass, and the explicit form for the resampling mass at each unique capping index is:
((X 1im; is resampled) p(Xmi (11m +117
X Xim;))
(A.52)
max(0, r(Xm, mmm_, ++:m;) )- 1) g(X1mm;) ) p p(X m; +1:y X (lm4)
To prove the lossless property, we introduce the segmented probability function:
Definition 10 (Segmented Probability Function). For each I (1,...;L) L), we define the segmented probability function Fj as:
Fi = a( X xim;) pl D(Xm++1n) X1 (im;))
mi
(A.53)
X
p(a;
X1n-1)]
im +1
This function represents hybrid probability measure that uses the draft distribution & up to position mi and the target distribution p for remaining positions, where X1 equal to the prefix.
We establish the telescoping property of resampling mass:
Lemma (Telescoping of Resampling Mass). For each 1 E {1,..., L), the mass of the resampling the unique capping index mi can be expressed as:
P(X 1mm is resampled) = Fi-1 - Ft.
(A.54)
Proof. need show that the resampling at the unique capping index m(l) equals F Fi.
20

---

Published as a conference paper at ICLR 2026
1. EXPRESS Fi-1 IN TERMS OF FJ. We have
P(X lom; is resampled) = (r(( my +lmm;) - 1) g(X 1mm; ) p( m² +1oy X tmm;)
First note
q( (X (Ximit)) = a( X Isms) al X mz +1-mg- #mf+1mm7 X Ximp))
and
p( X mi +1mi44+
X Xim;;) r (X mi +1smi a( X m² +immimi X Ximm;):
Hence
Fi-1 = q( 1:m²) p( (X mi +1 X Kimm))
(((X 1.m;) ) p X m² + +1mmi X ximm) p(Xmi my +loy X limp
lmm ) pl X m -1oy X Ximm; .)
= 4Xmm++imm g( ( mm; +1:mi
r(( ( m +amima ( l:me al (m; +lmp7a X limm
pf X mins -1oy loy X Ximmaa)
[ mf +1mm ((X Limi ,) p( p(Xms mi +loy X Nimita)
=r(X =f(mmt+1mm Fi.
2. COMPUTE THE DIFFERENCE Fi-1 Fi.
Fi-1 - Fi
r(X mi +1:mi+4 Fi Fi
(r(X mz +1ami4 - Fi
-rr(mm; +1-mi1 - 1) (000(((imm) (X1im77))) pl (X 0(mmin tle X Ximmtr))
= =(r(Xm; (r(Xmi---aamm 1) a(X lim;) ) pl X + X (imm))
This completes the proof that the resampling mass segment I equals Fi-1 Fi.
Theorem (Lossless Recovery). Under the prefix-adaptive speculative decoding scheme, the total probability of generating any sequence X1z equals the target distribution probability:
P(X 1:y is generated) = x(x 1:7))
(A.55)
Proof. From Lemma 7, we have the total generation probability decomposition:
P( P(X1r, byy is generated) P(X1s 1:y is accepted) + P(X 1.y is resampled) + P(x,, resampled) min(1, r" (X1y)) q(X 1:7)
max(0, (0, r r(Xm; m; ++mm;) ) - 1) g(X (lmm)) p( X m; +1oy X kmm;))
max (0, ('(X 1) q x(x 111-11) X X1
(A.56)
From Lemma 8, we know that for each I LI,
Fi - Fi (r(X,,, mi ) 1) ((11mm;) pl X m² +17 X1mm))
(A.57)
Therefore, rewrite the generation probability as:
P(X1., b.y is generated) min(1, r" (XX1)))) (11z)
Σ (1-1 Fi)
(A.58)
+ max(O, r- (XX 1) gl ( ((119--))p(0 X19-1)
21

---

Published as a conference paper at ICLR 2026
Since r" r'()):)) minfr(X1:m) (xm++tx+))) and (X1mm;)) 1, have r ("(1):
mi +1:)):
Case 1: If r (X mi 1:y) S 1, then:
min r" (X 1 g( ((X1.) (xy)) + max r"(1 - 1) a 1: 1n-11)((y)) (19-11
= r(x mi +1ny ( 1:7) +
r(X mz +1:9)) g(X 1:7)
(A.59)
q(X 1imz) p( +1 +1:y X Xim²)
= FL
Case 2: If r(X mi 117) 1, then there would be another unique capping index beyond mī. contradicting the definition of mi, as the last unique capping index. Therefore, we must have r(Xm m2 +1:7) 1, and thus:
min(1, rx(1x)))) 9(X in) + max(0, r" (x))) 1) q(x 1: 11) X1my-1) Pt (A.60)
Therefore, we have:
L
P(X toy is generated) = Fr. + Σ (B--1- Fi)
1=1
FL + (Fo +F) + - F2) + ... (FL-1 FL)
(A.61)
Fr. Fo Fr.
Fo
Now we evaluate Fo. From Definition 10, we have:
Fo q(
1mm5) 1:mm)) p(X mi+1:7 X X1m;)
(A.62)
By our convention, m.
Fu = q( (1.) p(X1x) 1:y
X x = p(x1,)) p(x
(A.63)
Therefore:
P(X X is generated) = p(X111)
(A.64)
This completes the proof of lossless recovery.
C.3 A EXTENDED EXPLAINATION OF CAPPED RATIO
Let r(11), r(x2 ma)...., r(x, X x1:-1) E Ryo be sequence of ratios.
Define the cumulative product up to index t as:
X 1:)
r(a X1:-1),
(A.65)
1=1
where X1:0 equal the prefix.
Let j be the last index (up to k) such that:
j max jsk
r(ag (11.-1) > 1 and II r(aa (11-1)
(A.66)
Then the capped cumulative product Rig is given by:
5'
r x [X (Xiee)
=
I r(x, X
X1s-1)
II [=
r(x, X1a-1)
(A.67)
22

---

Published as a conference paper at ICLR 2026
This ensures that the cumulative product is capped at the last index j" such that the individual ratio r(zy-1X and the cumulative product up to that point also exceeds
When is 3, lets show simplest example to show the recovery of target probability.
P (X 1:3 is accepted g(X133))
(A.68)
==3
P (XX 1:3 resampled)
Σ
P (Iyy 2g-1) -n- are resampled X x
max (r(()))()))))))))))))))))))))( 1))((113))
Branch (g,p) 1:3))
Dranch (g,9) X 1:3)
(A.69)
max((r(x2) 1)9( X 11:). p1
BBranhh (g.p) X 1:2)
Dranch (9.p) X1:2)
max ((x((((2))) 1)g(211),))
Branch (g:p) 21)
p(rs) X X12)p((2/m)
Branch (g.P 21)
Let's take y = 3 as an example, only 1x) > 1, the resampled portion probability mass is needed. Suppose r r(X 1:2) > 1 with r(21) and r(x2) < 1:
q(X 1:3) +0 + p(z1)p(Z2/22) )p(33 x1.2) (( (22)) (12)
p( 1:2
(A.70)
=(X133) 13) q( (1:3)
D EXPECTED NUMBER OF ACCEPTED TOKENS
We conduct efficiency analysis based on the expected acceptance length E[T]. For a given draft length y, the expected number of accepted tokens for the tokenwise speculative decoding Leviathan et al. (2023), blockwise verification Sun et al. (2024), and our HSD are as follows:
Lemma 9, Expected Number of Accepted Tokens (See Section D. I for proof.)
Jaken
ΣI
uken B[T]]ooc
Block h
ElT
Branch
Σ
1 1
II
(1
hx)
(A.71)
We establish Theorem 7, which guarantees that HSD is more efficient than other lossless methods: Theorem 7. HSD and Blockwise Achieves Better Expected Number of Accepted Tokens
Doronch 2 EE(] block 2 E loken
(A.72)
where equality holds in both inequalities if and only if = 1. (See Section D.2 for proof.)
We reveal that limitations acceptance probability in each method directly cause the gap from the ideal case w.r.t. expected accepted tokens. Let r(zz) = a(m.)- The acceptance probability of the entire draft hy is ideally min [[T r(x)), 1). In contrast, tokenwise acceptance is 117-, min 1). blockwise adopts lbblock min (,, 11""" T172 "172"".T7 } (see Lemma I)), and HSD uses hours min min mm r(xx), I?? ++1 r(x.),, 13. See the average acceptance probability hy on GSM8K in Fig. A.1.
10
1.75
1.20
hnoeen
075
025
6.16 07
10caratio
Bookwitee
D615
Figure A.I: The average ac- ceptance probability of the entire draft (r = 7) on GSM8K.
Let E 1.. ) denote the number of accepted tokens in decoding attempt. Since t is a negatvite integer-valued random variable, the tail-sum identity applies with lattice spacing a
23

---

Published as a conference paper at ICLR 2026
Lemma 10 (Tail Expectation). Let X be non-negative random variable with values in {na: 0, for some a > 0. Then:
X
= Σ
Pr(X 2 k).
(A.73)
Jem
Proof. Start with the right-hand side:
20 Pr(X 2 ka) a Σ
Pr(X ta)
k=112k
Pr(X Ea) Σ1
(A.74)
Σ
la Pr(X ta) = [[
t=
D.1 EXPECTED TOKEN LENGTH DERIVATION
TOKEN WISE SPECULATIVE DECODING
Referring Block-wise Verification Sun et al. (2024), the authors prove that it achieves longer expected token length than the boken-wise verification Leviathan et al. (2023) (see Appendix B.2 in Sun al. (2024)).
HIERARCHICAL SPECULATIVE DECODING
Let m. .......hh By ((0, 1) be the random draws used in verification. The accepted length is defined as:
max (i 7 M S hi)
(A.75)
where h2 is the acceptance probability at step i. By the tail-sum identity:
E|r]
Pr(T 2 i).
(A.76)
If we define the event S = {m I h,), and assume independence of the draws, then:
Pr(r 2 1)
II (1 hR).
(A.77)
Substituting into Equation (A.76), we obtain:
E|T]
Σ
(A.78)
kmi
BLOCKWISE VERIFICATION
In Algorithm 2 (blockwise decoding), the decoding continues even if some 77, >> hbblock, the resampling happens only at the end. Therefore, the token count still satisfies the same form.
Let bbblock be the acceptance probability at step computed via blockwise rules, and define events: block
S {11 S 11 block }, so Pr(S.) = 1 A
(A.79)
We then have:
Pr(r 2 1) =
II
h block
(A.80)
Am
24

---

Published as a conference paper at ICLR 2026
and hence the expected number of accepted tokens under blockwise decoding is:
Blolkkock
II k=
(A.81)
D.2 TOKEN LENGTH COMPARISON
We re-express the acceptance probability to compare token length between block-wise speculative decoding and our method Equation (19)). This yields more precise comparison via the directional divergence expressions Equation (17) and Equation (18).
Capped Branch Divergence Difference as:
The difference of capped branch divergence calculated
Branch (p, q 1xa))) Branch (q.p) x1:)
(X1:+1) 1) 1:ttt
2141
(min(r(2 (mm(t+1))) ( (f( ()((()())(()((( - 1)
Ze01
(r(X ml ( (mxxx ()
(1411)
(A.82)
Branch Acceptance Probability speculative decoding is:
Combine equations (A.82), the acceptance ratio of hierarchical
ht branch Branch (p.9 q X 1:))
D Aranch (g,P)
X 1:t)
Dirnchh (p.g. X1=)
(A.83)
De Branch (p.g q X x:.) + [1 r( X +x 1)) 11+1) E[r(X (1.())11)++e
1]+
E1r(X (0r(Xm(Xmnn (o +14+1) 1|+ + E1 r(x ((Xm(xn4))t44))
where [a]+ equal to max(a, 0}
Blockwise Acceptance Ratio Algorithm 2 (blockwise decoding). blockwise keeps an internal
clamp Pt min (P:-1 rxx 1=-11) 1}, which could be simplified based on characterization of p.
Lemma 11 (Suffix-minmmmm characterization p:). Let [r: C [0, oo) and define the sequence (prh2o recursively by
Po 1,
Pe min PI-17 1), t2 1.
(A.84)
Then for every t 0
Pr.
min
II ri: i=++1
(with the empty product for equal to 1).
(A.85)
Equivalently,
min 1, rey Tt-1Ft F172
(A.86)
Proof. We prove (A.85) by induction on t.
Base (t 0). For t 0 the right-hand side becomes
min (empty product) = 1 = Po: 05e50
(A.87)
25

---

Published as a conference paper at ICLR 2026
the claim holds.
Inductive step. Assume (A.85) holds for some - 1 2 0. Using the recurrence,
Pt = min 1, Pt-1
(A.88)
By the induction hypothesis,
1-1 II nt 0gest-1 imst1
Pt-1 = min
(A.89)
Substituting,
1-1
Pr = min 1,
min 054St-1
II i+st1
(A.90)
Multiplying every candidate product in the inner minimum by r. and then taking the outer minimum yields exactly all suffix products
II
(A.91)
1=8+1
for 0,.... . 1, together with the empty product 1 for t. Hence (A.85) holds for t, completing the induction. And obviously, pt < rr ( startt)), where start E (1,t-1)
Σ ( iit) - 1)+ (x X1x)
h+
black
(per(Ee41/ X1:1) - 1)+ (x Xx:)) + 1
R++1
(A.92)
Σ "
(minf r((++1) (xaa-)) r (x (xx=)))))_)) +
Since minf r(xe+1), r(Xect1); r r(xe-14t1,... r(X1441)) S ((m((XX))))))
E 1)+ g(#e+) X
h
block
2011
X
m(X(ee))444))) 1)+ g(3441 X1a) + Pt
(A.93)
1)+
Pe+1
(M(Xm((in))ttt)))) 1)+ Pt
2e+1
From equation A.83:
Σ r( m (114)))))) = q( m((11)41)) - ((mme+144aa
P441
(1 - r r(X m((++))+4))) m((++144a))
(A.94)
< (1 pt)q m
< (1 Pt)
26

---

Published as a conference paper at ICLR 2026
Since
Exy [r(X (m(mm(X ( +14441) - 1|+
branch
Exem [r(X ml (x 1|+ + Σ 1441 (1 r(X ia 1)+1411)
Exeri [r(Xmi mi ((Xx))))1441)) - 1]-
(A.95)
Exer [r(X (XXnn))ttee))) +|++++++++ pt
2 block
27

---

Published as a conference paper at ICLR 2026
Table A.I: Comparison of different algorithm performance on GSM8K with Qwen-2.5. We list the average and standard deviation across 5 runs with different seeds.
Method
Tokenwise
Blockwise
Ours
Block Efficiency
6.40::0.10
6.64 31.70:10.05
6.51
Decoding Speed
31.52:10.06
32.61+0.02
Table A.2: Comparison of task performance across model sizes and methods.
Metric
Method
72B
32B
14B
Tokenwise
0.8213
0.8213
0,8327
GSM8K (Accuracy)
HSD
0.8517
0.8479
0.8327
Table A.3: Ablation on capping mechanism.
Dataset
Method
ACC
BE
DS
GSM8K
HSD HSD
$4.40+1.754
6.76=0.05
33.63=+0.3
HumanEval
80.61+0.69%
5.60=0.06
29.15+0.44
GSM8K
HSD + Capping
84.96+0.93%
6.63+0.06
32.73=0.55
HumanEval
HSD + Capping
82.47:1.15%
5.45+0.08
27.54+0.48
EXTENDED EXPERIMENTS
Result Robustness To prove the robustness of our experiments and guarantee fair comparison, we conduct additional experiments with different methods shown in Table A.I. We observe that our method demonstrates stable performance and exceeds both tokenwise and blockwise methods on average.
Verification of Task Performance We compare our method with the token-wing approach on GSM8K. As shown in Table A.2, our method achieves equivalent (or better) accuracy among different model sizes, demonstrating the preserved distributional fidelity.
We conducted ablations on the role of the capped prefix ratio in Algorithm/ 2 (HSD), which is essential to preserve distributional fidelity, shown in Table A.3. Removing capping (i.e., directly using the uncapped ratio to compute divergences) yields slight increase in efficiency, but at the cost of varying degrees of performance degradation (which may or may not be obvious depending on the task).
Capped Prefix Ratio Ablation Study
PYTHON IMPLEMENTATION
We provide the Python implementation of our Hierarchical Speculative Decoding (HSD) algorithm in Listing 2, which builds upon the token-wise speculative decoding approach from Hugging Face Wolf al. (2020) Transformers v4.46.3, shown in Listing for comparison. Following Hugging Face, our implementation eliminates the use of an explicit for-loop by leveraging equivalent masking mechanism: we perform parallel sampling across positions to determine whether to accept or reject subsequences of varying lengths, and then select the longest accepted prefix as the final output.
28

---

Published as a conference paper at ICLR 2026
Listing Tokenwise Speculative Decoding (SD) SD.PY PY
Import torch
daf 87icand:date, hagpeddet_______deeee_ candidates londllaat_ooota, nox_logits):
Azge:
iandidate_inpu__aee (lensor): Voken 1Ds from the draft model. shape: [batch_size, seq_len]
candidate_loge logits (Tensor) toglts from the draft model. Shape: [batoh_atze, seq_len,
vocab_size]
logito (Tansor): Togita from the target model. Shape: [batch_aizee seg_len, + vocab_aise]
Returns:
10
R_matches (int]: : Number of accepted tokens from the draft model. walld_tokena (Tensor) Accepced token profix one new token sampled. Shape:
+ bateh_alse, cheatch
12
13
14
Convert logits to probsbilities
candidate_ wot.gtts.o.taxxddia.....
16
new loftt. (dima-1)
18
candidate Lendidate_eength candidate wew.teee____eseeeeoeee shapetsshhapee1] rex_condidate
19
candidate_inpur_idde -candidsts_eengghh]
20
21
Extract tiken-wise probabilities for the candidate tokens
q git, arange (candidato new new_candidate_ingee sepee_nnitti_ddrr its.ddddeeeeeeeee.e..o (2)
23
plt, taroh.arango (candi deandi
baanndddte__npptt.o. squaezee
24
25
probebility_ratae P_d / q_i
26
is_accepted rand_ (probability probability_ratio
27
28
assuming batch size = n_natches acada_ac cumsun(dim=-d 1).aum() this in algorithm
30
31
Next token selections if there is sejection, adopt the resampling distribution. if n_natches candidate_length:
32
33
P_n_plus_l = plt, n_matches, !]
34
q_a_plus_l glt, numatches, p-prime = tarch. torch. ((p ((p_n_plus_ plus___),, min=0)
35
p_orime.div_ wtw.w//wp_prtmmmonnnoa.
37
else:
38
P-prime pl:, n_matches, :]
39
40
Ensura we don't generate beyond nax_len or an EOS taken, sa_ddaee_addidatee0
a_matches candidate_length:
42
i Output length is assumed to be 'r_matches + token with the Larget model
Since we won't generate another
44
# due to acceptance on BOS we fix 'numatches"
45
t_matches - talkeng candidate_ input_iddaa sardiddatelennth.
46
47
48
else:
49
Next taken select ion: if there is rejection, adjust the distribution from the main model before sempling.
+
50
it The selected tckens include the matches lif any) plus the next sampled tokens if n_matches 0:
51
52
if r_mstches < candidate, Leeniddate_eenhhe
53
valid_rokens candidate_input__ie -eandidtte_logghhr_aateee
< candidate_lennee stop(valid_tokene scores=Nonel:
54
15 not torch.multinomill (p_prime, num_semples=1) valid_tokens torch, cat (valtd_rokena, t),, dima-')
55
56
57
58
else: f_matches aLmatches-1
59
60
elaes
valie_tokens centidate_innut_ideff i5 not wtaptwassdtooees, scoresmNonel:
candidate_length::
62
63
t torch.muleinom-s. (p_prima, num_camples=1)
64
valed_tokena coroh.catl tokenn, Lh, dim- 1)
65
66
67
mustchees mattche
68
else: Norch.miliiooee ip_psime, num_samplessi
69
70
vs 1ilid_tokan tokens =
71
72
retura toked_ r_mstches
29

---

Published as a conference paper at ICLR 2026
Listing 2 Hierarchical Speculative Decoding (HSD) HSD ppy
Import torch
daf
HSD (candi watpttttannn____eeee_e_ candidate__lo nog_togita):
Azge:
Landidate_inpur__ae (lensor) Voken 1Ds from the draft model. shape: [batch_size, seq_len]
candidate_loge logite (Tensor) toglts from the draft model. Shape: [batoh_atze, seq_len,
+ vocab_size]
rew_logita (Tansor): Togita from the target model. Shape: bbatoh_alzeg seg_len, + vocab_aixe]
Returns:
10
R_matches (int]: : Number of accepted tokens from the draft model. walld_tokena (Tensor) Accepced token profix with one new token sampled. Shape:
+ bateh_alse, [hentch
12
13
14
Convert logits to probsbilities
candidate_ lewiidtteeeeesseeeeooee sog.ss....tmxx(iiar.............
16
new new__oogeeeeee www.loggtttsooooo.... softmax (dim=-1)
candidate Jengh sonndddatallgttt.eeeeee
18
rew_candidate_iiguu.
cendidate_innutidddt: candidale_leng.ar
19
20
candidate intlatte__np__d_dd_ .qqueeee (2) q_i - g torch, arange (candidate pew_candidate_
Extract
probabilities
21
PLi plt, torch.arenge (candidate_ jen_enndiare_jnnet_idd
23
24
Compute cunulative joint probabilities for draft and target model g_prev recchrrollee.e shifts=l, dims-1) 1.0
25
26
g_previ:, g_oumpred exrch.exp (torch. lq .cumsum (dim=l)) uusqueeze 1) g_next q_cumprod q/t, scandidate_
27
28
P_prev torch. rollh.roll shifts=1, dims=1) P_previs, 1.0
30
31
P_oumprod Lorch.exp (Lorch. log (p_prev) (dmmsm/diime)) unsqueeze 1)
32
33
Constrain pumppod with cumpprd for computing the capped resampling distribution ratio p_euapred e_cumprod
34
35
previous_max new new_p_ pw__p_rrevous torch.ones, (2 (p_cuprodd) .to co.ppoomprodd.dvvoo for k In range joandidatee_eengihlel
37
38
if ratioli, k] axevious_mate previous_max ratiol;, k]
39
40
pow_p_pravieua(t k] P_oumprod(;, x] previous_max
41
P_next pew_p_previcus pli, :cencidate_Jengtal)
42
Corstruct resampling distrittioon p* diffs P_лext Lneext
44
45
P-plus clamp (diffs, min=0.0) p_minus corch.slamp (-diffs, min=0.0)
46
47
p_primes p_plus / torch.max' mom (om(p_plmppp hp_pppppp.ppppm www.ppll...mmcc.. (pm keepd' meTuu), P_mf nus. (d' m=-1, keepdimeiruej!
48
49
Stek-back probability: reject prefix with : mass of pr step_back_probs
50
p_primes. sum Idin- 1)
51
step_back rench (step_back__roha) step_back_prrbbs
52
53
Find first position to stop (fron the end)
atep
55
stop_posttions
else:
57
stop_pesitiens candidate_ n_natches forch..flip (-1]) + (-1, kespdims [1]
58
59
Mask to decide which tokens are accepted select torch. zeros like backp_back) .occk)tto(stte
60
61
62
apply cumprod on the ratio instead of the raw probabilities to aveid unde:flow ratt (p_i / qii.. cumprod uusguueeeeee] is_accepted torch.rand_ (probabi
63
64
<= probability_
65
66
only decide to accept or not at the last poeltion based on the joins probability ratio assign to positions + rest of the positions seiect seieeeetoorchh.araeell..... sttpppsseeeeseee0011111 (0)p stop_positions) sis_acceptedl:; -1:)
draft is rejected, otherwise assign 1 the
68
69
is_accepted
torch, cumsum(selecs dimm-1)
70
71
batch
the current ingiementation
72
n_natches - Ls_accepted. sun .item()
30

---

Published as a conference paper at ICLR 2026
Listing 2 Hierarchical Speculative Decoding HSD py (cont.)
1f "ss_done_carae [andidatee[]] and n_matches =a cand dat datg__egthhhh
# output length is assumed to be 'n_metches 1", Since we won't generate another token with the target: model
A due to acceptance on BOS we rix "n_matchee"
t_matches
#t val salid_ookeen new cew_ccadddare inwpedddde_______________e inplt_ids Runatches
walid maled_tokena candidate_input__dde
-sondidor__langth.
elac:
select if there rejection, adjust the distrioutio fon the + model be befoze sampling.
gamma candidate_ randidate_length seenttehehhhhh_eeeee
11
P_n_plus_1 = pl:, cancidate_ :]
n_matchea gamma:
13
P_prime p_primes(i, nunatches,"
14
P_prime P_primo/p_primm.am
keapdim-Trual
15
16
P_prime p_n_plus_1
18
# The selected takens include the motches lif any) plus the next sampled tokens because if n_matches=0, we one resampled boken for sure, if n_matches=10,
+ one more for
20
# as well, because the previous if checked not stop and sumscches-cadiddateeee causing problem
21
if n_matches 0 and numatcherrcandictte_. length:
22
velid_tckens condidate int
23
if not stop lcaddddadd inppdddddaeeeeaat.___mmm input_ inpat_iistt_t.t ids -amattche--aaddddtteeeee scores-None):
24
(p_prine, num__smppes--l) valid_tokens corch.cat
25
26
toxeid_ th, dim-
27
else:
n_matches n_matchaa-i
29
else:
30
Lorch www.hhmmaliillllllcc..commm (p pp_me,,,, nua_samples=l) if a__etchee==0:
31
32
valid_tokens =
33
34
valid_tokens candidate_ candidato_innputidfff input_ida(t, -candidate_iength::
valid_rokens torch.cat(
36
(valid_tokens, tl, cim=-1)
37
38
valid_tokens, n_matches
31

---

Published as a conference paper at ICLR 2026
G INTEGRATION WITH RECURSIVE REJECT SAMPLING THE MULTI-DRAFT SETUP
We demonstrate in Algorithm that our HSD algorithm is compatible with existing lossless multi- draft verification methods, exemplified by Recursive Reject Sampling (RRS) with replacement Yang et al. (2024). Notably, independently sampled parallel draft sequences do not guarantee the existence of additional draft sequence that shares the accepted subsequence its prefix.
Algorithm 3 Hierarchical Speculative Sampling with Recursive Rejection Sampling
Require: Draft tokens: X
l {-f,-.. ] 1:t
Target probabilities for all draft tokens: {x(-), ... p(-1 k=
Draft probabilities for all draft tokens: {4(-), (111 1:7/ ) Initialize т
2: Initialize {x;
3: for in 1 do
4: if X l:r = X 1rr then
5: for j in r +
do
6:
Set xy = m
#select draft X r4 for verification
7:
end for
8:
9:
for / in 7 do
10:
Compute acceptance probability h, from Equation (19) based on the corresponding probabilities for the draft tokens: 2.
11:
Sample 1/ ~ (O,
12:
if h4 1)t then
13:
Set =t break
else 15:
=
17:
continue
end if
19: end for
20: else
21:
continue
Askip draft X 1:y due prefix mismatch
22:
end if
23:
24: if r 7 then
25:
Sample token from ((-1X1n))
#accept the entire selected draft and sample bonus token
26:
break
else
28:
Compute (. X 1:r)::
Set p(- X 1:T)
Prr
X 11:):
#set Pt XX k:r) as new target distribution
Set r(: X X1:r)
P x
#set r(. X X1:r) as new probability ratio
30:
end if
31:
32:
end for
Sample token from
P X1:r)
Ensure: [X token]
32

---

Published as a conference paper at ICLR 2026
H COMPUTATION EFFICIENCY
We begin by noting that the computational cost of the verification stage in HSD is effectively as efficient as that of tokenwise verification in practice.
While there are minor differences in the computational cost of verifiattion-wethhee using any of the three verification these differences are insignificant in practice compared to the reduction in target model forward passes. Indeed, block efficiency (or equivalently, the acceptance rate) remains the most meaningful metric for evaluating performance. A detailed complexity analysis is provided in the revised version below:
Both HSD (Eqs. 17-20 our paper) and blockwise verification (Eqs. 4-5 in Sun al. (2024)) require summing over the vocabulary to compute the acceptance probability at each position. Therefore, HSD introduces no theoretical overhead compared blockwise verification.
Moreover, our implementation is more efficient than that of blockwise verification (Appendix A in Sun al. (2024)) By leveraging an equivalent masking mechanism, we eliminate the for-loop and compute probabilities for all positions in parallel. This makes HSD nearly as efficient as tokenwise verification. While tokenwise verification only sums over the vocabulary at a rejected position, our HSD computation is fully parallelized via tensor operations across both the vocabulary and the draft length % which is typically much smaller than the vocabulary size V.
Importantly, the computational cost of verification is negligible relative to the reduction in target model forward passes, which the main bottleneck in verification. Below, we compare the verification cost with the forward-pass reduction for batch size of 1.
Since the vocabulary size V is much larger than the draft length y, the main cost of HSD arises from computing branch divergences, which requires only 4// FLOPs:
1. /" (X1:1) 1 VV FLOPs
2. Selecting (X1)) 1 0) via the max operator + / FLOPs
3. Multiplication by 9 - >V FLOPs
4. Summation over the vocabulary + > FLOPs
For Qwen-2.5 with V = 151.643 and 7 = 10, this amounts approximately 5.8M FLOPs.
In contrast, the forward-pawt pass FLOPs per new token in large language models are orders of magnitude larger, even with KV-cache inference. Considering the main contributions:
K dot products
Attention score x V
All projection/MLP FLOPs
Ignoring softmax, LayerNorm, rotary embeddings, and bias
The per-token FLOPs can be approximated as:
FLOPs per new token L- [ddLpat 4d² + 2ddg
where L. is the number of transformer layers, d is the hidden size, du is the MIP intermediate size, and Test is the number cached tokens.
Using context length Lpast 1024, the per-token FLOPs for Qwen2.5 models are:
Qwen2.5-0.5B: 0.374 GFLOPs
Qwen2.5-72B: 62.915 GFLOPs
As shown in Table in our paper, all methods achieve block efficiency larger than 2. Consequently, the cost of HSD verification is negligible relative the reduction in target model forward passes.
To directly quantify the overhead of the verification stage, we evaluate verification cost on 100 GSM8K problems using GPTQ-quantized 8-bit Dwenn2.5-72BIInstruu and 0wee22.500.BB-Insttte
33

---

Published as a conference paper at ICLR 2026
target and draft models single H200 GPU. As shown in Table A.4, the verification stage consistently accounts for less than 1 % of the total decoding time. At the same time, the vast majority of rumtime is spent in the draft and target forward passes. Here, the draft forward pass accounts for about 24% of the runtime, and the target forward pass accounts for about 72% both blockwise and HSD. The verification stage of HSD is about 20% faster than that of blockwise.
Table A.4: Runtime breakdown of Blockwise and HSD.
Component
Blockwise Mean (ms/token)
Blockwise %
HSD Mean (ms/token)
HSD %
Total
34,168
100.00%
33.788
100.00 %
Prefill
0.913
2.67%
0.915
2.71%
Draft Forward
8.210
24.03%
7.865
23.28%
Target Forward
24.690
72.26%
24.695
73.09%
KV Cache Input
0.007
0.02%
0.005
0.01% %
KV Cache Output
0.070
0.20%
0.067
0.20%
Logits Processing
0.093
0.27%
0.103
0.31%
Verification
0.160
0.47%
0.127
0.37%
Other
0.025
0.08%
0.012
0.03%
34


Reviews:
[{"review_id": "lcL2jz7Sm3", "reviewer": "Reviewer_ASe8", "summary": "This paper introduces Hierarchical Speculative Decoding (HSD), a novel approach to address the \"joint intractability\" problem in speculative decoding for large language model (LLM) inference. The authors identify a fundamental limitation in existing speculative decoding methods (tokenwise and blockwise) related to how acceptance probabilities are calculated for draft sequences. HSD solves this by introducing a hierarchical approach to acceptance probability calculation that better approximates the ideal case while maintaining the lossless property (preserving the target distribution exactly). The paper provides rigorous theoretical analysis proving HSD's correctness and demonstrates consistent improvements over baselines across multiple benchmarks (GSM8K for mathematical reasoning, HumanEval for code generation, and CNN/DailyMail for summarization) using the Qwen2.5 model suite with various scale combinations (0.5B draft model with 14B, 32B, and 72B target models).", "questions": "1. How does the actual computational overhead of HSD (for hierarchical acceptance probability calculations) compare to simpler methods, particularly for smaller draft lengths? Could this overhead offset some gains in block efficiency?\n2. The paper mentions HSD can be integrated with multi-draft frameworks but provides limited evaluation. Could you share more comprehensive results comparing HSD Multi-draft against Tokenwise Multi-draft across more model combinations?\n4. Have you observed any tasks or model configurations where HSD performs worse than existing methods? Understanding the limitations would help practitioners decide when to use this approach.\n5. Could you provide more intuitive examples showing how HSD's hierarchical acceptance mechanism works in practice for concrete generation examples, perhaps with visualizations of the capped ratios and unique capping indices?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Exceptionally rigorous theoretical analysis with detailed proofs establishing the lossless property of HSD. The paper clearly demonstrates how HSD correctly recovers the target distribution through careful handling of branch divergence and capped ratios.\n2. Significant conceptual contribution by identifying and solving the \"joint intractability\" problem in speculative decoding - how existing methods miscalculate acceptance probabilities for multi-token sequences, leading to suboptimal performance.\n3. Elegant hierarchical approach to acceptance probability calculation that provides a theoretically sound solution while remaining practically implementable. The capped ratio concept and unique capping indices are particularly insightful innovations.", "weaknesses": "1. Limited experimental scope - the paper only evaluates HSD using Qwen2.5 models across three benchmarks. A broader evaluation with multiple model families and additional tasks would strengthen the empirical validation.\n2. Insufficient comparisons with state-of-the-art speculative decoding frameworks. While thoroughly comparing against tokenwise and blockwise methods, the paper omits systematic comparisons with more advanced approachesr.\n3. Limited ablation studies to understand the contribution of different HSD components. For instance, how sensitive is performance to the identification of \"unique capping indices\" or the specific hierarchical structure?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PfEi4LnkO1", "reviewer": "Reviewer_YeUo", "summary": "This paper introduces Hierarchical Speculative Decoding (HSD), a novel approach to improving the verification process in speculative decoding. The paper addresses verification bottleneck by proposing HSD, a lossless verification method that overcomes joint intractability by resampling portions of the target distribution in a hierarchical manner. Extensive experiments show that HSD significantly improves the expected number of accepted tokens, particularly when dealing with longer draft sequences. The method is also proven to work effectively across different model sizes and tasks, making it a promising tool for accelerating LLM inference.", "questions": "- Could the author provide a more intuitive example or explanation of why joint verification leads to a higher expected number of accepted tokens? While the simulation using a toy example is convincing, it still isn't entirely clear to me why this happens.\n\n- For Algorithm 2, at line 15, should it still sample from the target distribution until the sequence reaches $\\gamma$?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The proposed hierarchical branch resampling strategy is a novel and creative approach to addressing joint intractability in speculative decoding. \n\n- The theoretical analysis is rigorous, and the experimental validation is comprehensive, showing consistent improvements across various benchmarks.\n\n- The paper is clearly written, and complex ideas are explained clearly. The use of figures and equations aids in understanding the methodology and its underlying theory.", "weaknesses": "- It’s unclear whether the backward scan of HSD introduces any additional computational overhead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RbOvSbUqw6", "reviewer": "Reviewer_qE7w", "summary": "The paper proposes a method termed Hierarchical Speculative Decoding for accelerating inference in LLMs by improving the verification stage of speculative decoding. The claim is that existing methods struggle with “joint intractability” when trying to verify a draft sequence at once, so HSD uses a hierarchical branching/verification approach to boost the number of accepted tokens (i.e., less rollback) in a “lossless” manner.", "questions": "It is hard to identify in one glance “Given draft model → generate K branches → verify hierarchically → accept or rollback”", "limitations": "", "rating": null, "confidence": 3, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "The topic: Accelerating generative inference in LLMs is a highly important problem", "weaknesses": "1 The flow of the paper is not smooth. The theoretical derivation of “joint intractability” and then the transition to the hierarchical method is abrupt. It is not always clear how the high-level algorithm ties into the low-level proofs and experiments.\n2 While the paper describes “hierarchical speculative decoding”, the exact steps \nie, branch generation, verification hierarchy, mass-balancing, acceptance criteria, are somewhat buried in dense math and less in intuitive explanation or pseudo-code. Readers may struggle to follow the pipeline end-to-end.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Wf9hI3k7Ug", "reviewer": "Reviewer_JMzF", "summary": "The paper proposes Hierarchical Speculative Decoding (HSD), a verification method for speculative decoding that seeks to be provably lossless while accepting longer draft prefixes than token-wise or blockwise verification.   The key idea is to view verification as hierarchical branch resampling with a single resampling step using a capped, branch-local resampling distribution. Several experiments on the Qwen series model demonstrate the effectiveness of the method.", "questions": "please refer to weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Across three benchmarks and multiple target sizes, HSD shows consistent  improvements in block efficiency and throughput over token-wise and block-wise verification\n- This paper is overall well-written and easy to follow.\n- The appendices provide solid derivations and decomposition lemmas.", "weaknesses": "- Results only use Qwen models and three academic datasets; evaluation on modern LLMs (e.g., Llama-2/3 families) and diverse tasks (long-context, multilingual, tool-use) would strengthen external validity.\n- HSD’s acceptance and resampling probabilities depend on capped branch divergences computed over the vocabulary for each position. The authors may want to provide a clear complexity/latency breakdown of these additional reductions relative to blockwise verification (e.g., per-step FLOPs, memory accesses, kernel counts).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)