- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies multi-draft speculative decoding, where multiple candidate tokens are proposed from a draft distribution q and a verifier must accept as many candidates as possible while preserving the target distribution p exactly.
The paper first gives an efficient exact sampler, Optimal IID, that attains the known optimal acceptance rate when the n draft candidates are IID samples from q. It then relaxes the IID assumption while requiring each candidate to retain marginal distribution q. Under this setting, the authors derive a new upper bound on the achievable acceptance rate and propose Stratified, an efficient proposal scheme and exact verifier that can exceed the IID ceiling. Stratification provides an acceptance rate no worse than the IID optimum and strictly better on some instances. The experiments show consistent acceptance improvements over Optimal IID, and the authors also report an end-to-end decoding speedup in a feasibility experiment.
Overall, I think the theoretical contribution is good and interesting, and I think the paper is worth accepting. My main concerns are about the practical framing and the motivation for requiring every proposal slot to have marginal distribution q. Exactness only requires the final output to follow p, so other ways of generating candidates from q, for example sampling without replacement or proposing the most likely draft tokens, also seem possible. It is not clear to me that these would perform worse. A short justification of this restriction, or a comparison with alternatives, would strengthen the paper.
Critical strengths
I think the paper's contributions are strong.
- Optimal IID is an efficient, exact sampler that attains the optimal acceptance rate in the IID setting. This closes the gap between knowing the IID acceptance ceiling and having a practical method that reaches it.
- Stratified achieves higher acceptance than Optimal IID. That dependent proposals can beat IID is not surprising in itself, but the coverage-dominance result is clean, and the exact verifier they build for this setting is neat and computationally efficient.
Critical weaknesses
- The requirement that every proposal slot has marginal distribution q seems somewhat arbitrary from the perspective of exact speculative decoding: exactness requires the overall accepted output to follow p, but it does not obviously require each individual proposal slot to have marginal q.
This matters because there are other natural ways to generate candidates from q that are also exact but do not satisfy this constraint. Examples are sampling without replacement, or deterministically proposing the draft model's top-n tokens and then sampling to check membership. It is not obvious that Stratified would outperform them. Since they fall outside the constrained class, they could also exceed the Marginal Oracle, which is a ceiling only for proposals that keep per-slot marginal q. It's possible though that i am missing something here. I think the motivation for the same-marginal restriction should be discussed explicitly, ideally with a comparison against at least one such alternative.
- The evidence for practical speedup is currently limited.
Most of the reported 1.58× speedup over autoregressive decoding comes from multi-draft decoding in general. The gain over Sequential IID is only 1.009×, and I feel the abstract should be reworded to reflect this. Optimal IID is also not included in Table 2. Finally, the evaluation is limited to next-token speculative decoding. The theory is valuable on its own, but this limits how directly the results apply to the chain and tree speculative decoding methods used in practice.
I therefore think the paper's theoretical claims are substantially stronger than its current evidence for meaningful end-to-end acceleration.
Questions for authors
-
Why is the per-slot marginal constraint necessary or desirable? Exactness of the final output distribution does not appear to require each candidate to have marginal q. How would Stratified compare with exact proposals outside this class, such as deterministically proposing the top-n draft tokens or sampling without replacement?
-
How sensitive is the gain to the token order? Table 7 shows two orders give almost identical results. Does this hold more generally, e.g. across random orders?
-
Is Stratified faster than Optimal IID end to end? Table 2 compares against Sequential IID (1.009×) but not Optimal IID. Could the authors add Optimal IID to Table 2?
-
Can the method be extended beyond next-token proposals to draft chains or trees? Section 5 gives a continuation-value ordering, but no algorithm. Is a practical multi-step version of Stratified feasible, and what are the main obstacles?
4 comments
Response (2/2): Q2–Q4 and References
Q2. How sensitive is the gain to the token order? Table 7 shows two orders give almost identical results. Does this hold more generally, e.g. across random orders?
A2. Theoretically, Stratified's acceptance gain depends on token order because different orders change how token probability masses are distributed across the equal-mass strata, thereby affecting the coverage probabilities of token subsets that determine optimal acceptance.
Empirically, however, this effect is negligible in our evaluated setting. We have expanded Table 7 to include the mean and min–max range of acceptance rates over 32 independently generated random token orders evaluated in the same setting (see lines 2161–2171 of the revised manuscript). The mean acceptance rate across random orders differs from the decreasing- order by only 0.001 percentage points, and all 32 random orders fall within 0.024 percentage points of it.
| Token order | Acceptance rate |
|---|---|
| Canonical (Table 7) | 86.5294% |
| Decreasing- (Table 7) | 86.5408% |
| Random orders (mean of 32) | 86.5398% |
| Random orders (min–max) | 86.5170%–86.5642% |
Q3. Is Stratified faster than Optimal IID end to end? Table 2 compares against Sequential IID (1.009×) but not Optimal IID. Could the authors add Optimal IID to Table 2?
A3. We have added Optimal IID to Table 2 (see line 413 of the revised manuscript). Optimal IID achieves 14.0247 ms/output token, compared with 13.4206 ms/output token for Stratified. Thus, Stratified achieves a 1.0450× end-to-end speedup over Optimal IID under our current implementation.
Q4. Can the method be extended beyond next-token proposals to draft chains or trees? Section 5 gives a continuation-value ordering, but no algorithm. Is a practical multi-step version of Stratified feasible, and what are the main obstacles?
A4. There is no obstacle to repeatedly applying Stratified to generate a multi-step draft tree. However, we have not developed an efficient algorithm for achieving optimal multi-step verification. The main challenges are how to obtain the continuation values and how to efficiently construct the corresponding weighted-optimal verifier. We have now made these challenges explicit in Section 5 (see lines 312–313 of the revised manuscript).
References
Zhengmian Hu, Tong Zheng, Vignesh Viswanathan, Ziyi Chen, Ryan Rossi, Yihan Wu, Dinesh Manocha, and Heng Huang. Towards Optimal Multi-draft Speculative Decoding. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), International Conference on Learning Representations, volume 2025, pp. 3181–3203, 2025. URL https://proceedings.iclr.cc/paper_files/paper/2025/file/0907335ecf28faf15be54485dbcbe70e-Paper-Conference.pdf.
Ashish Khisti, MohammadReza Ebrahimi, Hassan Dbouk, Arash Behboodi, Roland Memisevic, and Christos Louizos. Multi-Draft Speculative Sampling: Canonical Decomposition and Theoretical Limits. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), International Conference on Learning Representations, volume 2025, pp. 1593–1633, 2025. URL https://proceedings.iclr.cc/paper_files/paper/2025/file/04cdf500730af7733a6b13cbbc230206-Paper-Conference.pdf.
Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. SpecTr: Fast Speculative Decoding via Optimal Transport. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 30222–30242. Curran Associates, Inc., 2023. doi: 10.52202/075280-1314. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/6034a661584af6c28fd97a6f23e56c0a-Paper-Conference.pdf.
Rahul Thomas and Arka Pal. Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Optimization. In C. Vondrick, B. Hariharan, C. Raffel, L. Pinto, D. Yang, and A. Faust (eds.), International Conference on Learning Representations, volume 2026, pp. 81274–81307, 2026. URL https://proceedings.iclr.cc/paper_files/paper/2026/file/83995c2acef585ae0f0d647154cfdd85-Paper-Conference.pdf.
Response to authors
Thank you for the detailed response and the revisions. I read both carefully and appreciate the effort.
The changes address my main concerns. The abstract now reports the 1.009× figure, and the Limitations section is clear that the systems experiments are a feasibility demonstration. Adding Optimal IID to Table 2 and the random-order results to Table 7 answers Q2 and Q3 directly.
Thank you especially for running the non-marginal-preserving baselines. The picture is mixed across settings, and I would encourage including both tables in the paper with a short discussion.
I am keeping my score at clear acceptance. The theoretical contributions are solid, and the revisions have improved the framing.
Thank you for your positive assessment of our work and your helpful suggestions. We have now added Section E.11 to the appendix, including both tables, to provide readers with a more complete picture of the results (see lines 2236–2260 of the revised manuscript).
Response (1/2): Weakness 2 and Q1
Response to Weakness 2. Thank you for your suggestion. We have revised the Abstract to explicitly report the 1.009× speedup over Sequential IID (see lines 27–28 of the revised manuscript) and clarified in the Limitations section that the current systems experiments mainly serve as a feasibility demonstration and that our contributions therefore remain primarily theoretical (see lines 472–474 of the revised manuscript).
Q1.
(a) Why is the per-slot marginal constraint necessary or desirable? Exactness of the final output distribution does not appear to require each candidate to have marginal q.
(b) How would Stratified compare with exact proposals outside this class, such as deterministically proposing the top-n draft tokens or sampling without replacement?
A1.
(a) The per-slot marginal constraint is widely adopted in existing multi-draft speculative decoding research, including the IID settings studied in SpecTr (Sun et al., 2023), the canonical decomposition framework of Khisti et al. (2025), and Global Resolution (Thomas & Pal, 2026). Thus, advances under this constraint can improve upon or surpass existing methods.
Beyond this connection to prior work, preserving the per-slot marginals is not an end in itself. What ultimately matters is achieving higher acceptance rates and efficient exact verification. Our Stratified method pursues this goal within the marginal-preserving class.
Intuitively, allowing arbitrary proposal marginals enlarges the space of possible proposal laws and may seem to make it easier to improve upon existing methods. However, a larger design space does not necessarily make it easier to find methods that achieve both higher acceptance rates and efficient exact verification. Such proposal laws can be difficult to verify optimally, and efficient algorithms attaining their theoretical optimal acceptance rates may not exist. For example, no efficient verifier currently attains the optimal acceptance rate for successive sampling without replacement.
Indeed, existing research has yet to demonstrate a non-marginal-preserving proposal method that is clearly better in practice than Optimal IID. Hu et al. (2025) explored non-marginal-preserving proposals, including sampling without replacement and Greedy sampling. However, Global Resolution (Thomas & Pal, 2026, Appendix O) reports that Greedy falls below even the Optimal IID ceiling at all tested K≥100 on Gemma-2 and Llama-3, with gaps approaching 2 percentage points in many configurations with n≥4. We have also clarified this comparison in the Introduction to make the motivation for our marginal-preserving approach more explicit (see lines 53 and 85–86 of the revised manuscript).
In contrast, our work advances beyond Global Resolution (Thomas & Pal, 2026) in both acceptance and computational efficiency. Optimal IID attains the IID ceiling exactly with near-linear preprocessing, while Stratified further surpasses this ceiling in some instances with efficient exact verification. We believe these constitute meaningful advances.
(b) We consider the comparison from two aspects:
Theoretically, deterministic top-n proposals achieve acceptance p(Topn(q)), which can fall below the IID optimum. Successive sampling currently lacks an efficient verifier attaining its optimal acceptance rate.
Empirically, we additionally compared Optimal IID and Stratified with three non-marginal-preserving methods—Hu Greedy (Hu et al., 2025), deterministic Top-n, and successive sampling with recursive rejection sampling (SS+RRS)—on Qwen3-4B/0.6B (n=4),(T=1):
To examine whether this advantage of non-marginal-preserving methods generalizes, we further evaluated Gemma-2-27B/2B at T=1, K=10,000, across multiple candidate counts:
In these Gemma-2 settings, both Optimal IID and Stratified outperform all three non-marginal-preserving baselines.