acceptodds
Under review as a conference paper at ICLR 2027

Attaining and Surpassing the IID Ceiling in Multi-Draft Speculative Decoding

Abstract

Multi-draft speculative decoding has a computable acceptance ceiling under independent and identically distributed (IID) proposals, but turning this value into an exact, scalable sampler remains a constructive challenge. We resolve this problem with Optimal IID, which preserves the target distribution exactly and attains the IID ceiling for any candidate count without iterative optimization or an approximation tolerance. Its finite-score construction uses near-linear arithmetic preprocessing. To exceed this ceiling, Stratified changes proposal dependence through equal-mass stratification, preserving each slot's draft marginal and matching or exceeding IID coverage for every token subset. Its optimal acceptance is no lower than the IID ceiling for any target, with strict improvements on some inputs. A recursive exact verifier attains this new ceiling with near-linear arithmetic work and polylogarithmic arithmetic span. Across three model pairs from the Qwen3 and Gemma 2 families, Stratified recovers approximately 85–92% of the gap from optimal IID to a target-aware coupling oracle with the same proposal marginals. The evaluation uses four candidates, top-100 draft support, and temperature 1. In a feasibility study at this setting, a single-GH200 implementation for Qwen3-32B/1.7B averages 0.49 ms per output token for verification-plan construction and online sampling, including residual correction, and accelerates decoding by 1.58× over autoregressive sampling. Proposal dependence thus enables further acceptance gains after IID verification is optimal.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
speculative decoding, exact sampling, probabilistic coupling, efficient language model inference, inference acceleration

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_6JYZOpenReview ↗
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.

  1. 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.
  2. 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
  1. 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 Y∼pY \sim p 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.

  1. 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
  1. 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?

  2. 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?

  3. 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?

  4. 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
AuthorsOpenReview ↗

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≥100K\geq100 on Gemma-2 and Llama-3, with gaps approaching 2 percentage points in many configurations with n≥4n\geq4. 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-nn proposals achieve acceptance p(Top⁡n(q))p(\operatorname{Top}_n(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-nn, and successive sampling with recursive rejection sampling (SS+RRS)—on Qwen3-4B/0.6B (n=4),(T=1)(n=4), (T=1):

Draft supportOptimal IIDStratifiedHu GreedyTop-nnSS+RRS
Full-qq90.513%91.891%96.014%95.506%94.937%
K=100K=10090.537%91.915%96.035%95.506%94.992%

To examine whether this advantage of non-marginal-preserving methods generalizes, we further evaluated Gemma-2-27B/2B at T=1T=1, K=10,000K=10{,}000, across multiple candidate counts:

nnOptimal IIDStratifiedHu GreedyTop-nnSS+RRS
489.81%90.28%87.52%69.55%87.42%
691.89%92.18%89.15%73.54%89.68%
893.03%93.26%89.88%75.61%91.02%

In these Gemma-2 settings, both Optimal IID and Stratified outperform all three non-marginal-preserving baselines.

AuthorsOpenReview ↗

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-qq order by only 0.001 percentage points, and all 32 random orders fall within 0.024 percentage points of it.

Token orderAcceptance rate
Canonical (Table 7)86.5294%
Decreasing-qq (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.

Reviewer_6JYZOpenReview ↗

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).

Reviewer_3CqCOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents the first verification algorithm, Optimal IID, which attains optimal acceptance in IID multi-draft speculative decoding without any approximation. Then, its presents the Stratified algorithm, which enforces dependence between draft samples through equal-mass stratification. The authors prove that Stratified has subset-coverage dominance over Optimal IID and develop a verification algorithm to obtain its optimal acceptance.

Critical strengths
  1. The paper's theoretical contributions on IID multi-draft are impressive. While previous work (Global Resolution) is able to obtain near-optimal IID acceptance, it requires an approximation tolerance threshold and convex optimization, and thus cannot always be applied efficiently. The authors have discovered a novel finite-score method with near-linear complexity that entirely avoids such optimization. This is a substantial theoretical contribution.

  2. The authors also prove that Stratified provably improves IID acceptance, and are able to construct a verification algorithm which achieves the improved optimal acceptance, which is a significant result.

Critical weaknesses
  1. The main weakness I can identify is the lack end-to-end throughput comparison of Stratified and Optimal IID. Table 2 does not include the proposed Optimal IID sampler. Furthermore, the acceptance gains of Stratified over Optimal IID are somewhat limited, and thus it is not clear whether the Stratified algorithm overhead could outweigh its acceptance benefits over Optimal IID when measuring end-to-end latency.
Questions for authors
  1. Can the authors provide an end-to-end throughput comparison between the proposed Optimal IID and Stratified samplers? I am willing to raise my score if the Stratified gains are meaningful.

  2. In practice, do any components of the two samplers prevent us from efficiently implementing them in a framework such as vLLM?

2 comments

Q1. Can the authors provide an end-to-end throughput comparison between the proposed Optimal IID and Stratified samplers? I am willing to raise my score if the Stratified gains are meaningful.

A1. We have added the Optimal IID results to Table 2 (see line 413 of the revised manuscript). Under our current hardware implementation, Optimal IID is indeed slower than Stratified, with Stratified achieving a 1.0450× E2E speedup over Optimal IID.

However, this likely reflects both the lower acceptance rate of Optimal IID and its less mature hardware optimization. Sequential IID and Stratified have undergone more rounds of hardware optimization. In fact, our current Optimal IID implementation is even slower than Sequential IID.

Q2. In practice, do any components of the two samplers prevent us from efficiently implementing them in a framework such as vLLM?

A2. From a computational perspective, the components of both samplers should not pose major obstacles to integration into frameworks such as vLLM, given the near-linear arithmetic complexity of the overall algorithms. However, they may still introduce practical challenges related to data movement between stages, CUDA kernel-launch and synchronization overhead, and the effectiveness of kernel fusion. The impact of these factors on performance depends on the specific hardware architecture and implementation.

Thank you for your response. The gains of Stratified over Optimal IID seem incremental, so I will keep my current score and continue to recommend acceptance.

Reviewer_jNBBOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

Multi-draft speculative decoding with n IID draft candidates has a known, efficiently computable optimal acceptance probability (the “IID ceiling”), but prior work could only evaluate this ceiling or approximate the realizing coupling (Global Resolution uses convex optimization with tunable error and reports a 14% solver success rate at K=100, n=3). This paper:

Theorem 1 (Optimal IID). Constructs an explicit selector marginal ho via a two-sided envelope of the prefix deficit profile, realizes it with a sparse symmetric moment-transfer kernel, and applies residual correction. The sampler exactly preserves p and exactly attains \alpha^*(p,q^{\otimes n}) for rational p,q and every n, with near-linear preprocessing and polynomial bit complexity.

Theorems 2–3 (Stratified). Equal-mass stratification preserves every slot’s marginal q and yields c_{\mathrm{strat}}(S)\ge c_{\mathrm{iid}}(S) for every subset S, hence \alpha^(p,Q_{\mathrm{strat}})\ge\alpha^(p,q^{\otimes n}). A recursive verifier attains the new optimum exactly with near-linear work and polylogarithmic span.

Marginal Oracle / headroom. Headroom H=\mathbb{E}[\alpha_{\mathrm{strat}}-\alpha_{\mathrm{iid}}]/\mathbb{E}[\alpha_{\mathrm{or}}-\alpha_{\mathrm{iid}}] is reported at 84.7% / 92.0% / 87.2% on Qwen3-4B/0.6B, Qwen3-32B/1.7B, Gemma-2-27B/2B (n=4, K=100, T=1; gains 1.37 / 0.78 / 0.53 pp over Optimal IID).

Systems. Finite-case exactness tests (~1e-15); construction scaling to V=151{,}936; single-GH200 E2E on Qwen3-32B/1.7B: Stratified 13.421 ms/token vs Sequential IID 13.544 and AR 21.241 (1.5828\times over AR, 1.0092\times over Sequential IID); verification averages 0.489 ms/output-token.

Validation uses matched-state evaluation, prompt-cluster bootstrap, and a code supplement whose CPU-runnable parts were executed successfully.

Critical strengths

The IID-ceiling constructive problem is genuinely resolved, exactly and at scale. Turning the known value of the IID ceiling into an explicit, non-iterative, exact sampler (Thm 1) removes the approximation tolerance and iterative solves of Global Resolution. The IID setting is now closed as an O(V\log V)-preprocessing primitive demonstrated at full LLM vocabulary — the right foundation for dependent-proposal work.

A universal, risk-free improvement with matching exact verifier and strong reproducibility. Theorem 2’s all-subset coverage dominance gives a monotone acceptance gain for every target at unchanged slot marginals and candidate count — a guarantee prior dependent-proposal schemes that change marginals (and can fall below the IID ceiling) do not provide. All nine per-dataset paired intervals in Table 5 are above zero, and the artifact is reproducible enough that the IID exactness claims re-verified on CPU.

Critical weaknesses

Demonstrated practical impact is marginal, and the headroom framing overstates the remaining opportunity. E2E gain over Sequential IID is only 1.0092\times (~0.9%) on a single GH200, batch 1, depth-one, n=4; the headline 1.58\times vs AR is essentially what any 4-candidate IID scheme already delivers. The paper’s own reference data computes Hu et al.’s greedy law at ~95.5% on Qwen3-4B/0.6B — above both Stratified (~91.9%) and the Marginal Oracle (~92.2%) — yet omits this from Table 1 while headlining “85–92% of the gap recovered.” Gains are also minority-state-driven (strict-improvement fraction 0.41–0.66; median per-state gain \approx10^{-9}). Consequence: dependence enables further gains in theory, but the evaluated instantiation buys ~1% E2E, and readers cannot see how Stratified sits against the actual acceptance frontier.

Evaluation is narrow relative to the theory’s generality. Headline numbers are n=4, K=100, T=1, depth-one, batch-one, one GPU, one pair for E2E. No E2E for Optimal IID alone; no depth>1; full-vocab construction costs (52.45 / 34.89 ms) would be prohibitive per step without top-K truncation. Unclear whether exact constructions matter beyond the demonstrated slice vs. primarily a theory contribution — while the systems framing invites the stricter reading.

Questions for authors

Clarifications (could materially change assessment):

Why is alpha_greedy (computed in the supplement for the same states) excluded from Table 1 / Figure 2? On Qwen3-4B/0.6B it reaches ~95.5% vs Stratified 91.9% and Marginal Oracle 92.2%. In what precise sense should readers interpret H (“85–92% headroom”) — as progress toward a marginal-preserving endpoint only? When are marginal-preserving laws dominated by non-marginal-preserving ones?

Is equal-mass stratification optimal among p-oblivious proposal laws with slot marginals q? If not, can you exhibit a same-marginal law with strictly better \alpha^*? This determines whether the remaining 8–15% is closable without observing p.

At K=100 in E2E, what is the per-round cost of rebuilding the Stratified plan when p,q change every step, and how does it decompose between the 0.181 ms “plan preparation” and 0.308 ms “online” rows? What support size makes fresh construction a bottleneck?

Theorem 2 gives strict improvement iff some IID-bottleneck subset has unequal stratum masses. Can you quantify expected gain’s dependence on token order?

Future work (no answer expected): depth>1 / tree-structured candidates; batch>1 and larger n in E2E.

3 comments
AuthorsOpenReview ↗

Response (1/3): Weakness 2 and Q1

Response to Weakness 2. Thank you for pointing out the issue with the paper's framing. We agree that the primary contributions of our paper are theoretical. We have revised the Abstract to explicitly acknowledge the limited end-to-end performance gain 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).

In addition, we have added the end-to-end results for 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.

Q1.

(a) Why is αgreedy\alpha_{\mathrm{greedy}} (computed in the supplement for the same states) excluded from Table 1 / Figure 2? On Qwen3-4B/0.6B it reaches ~95.5% vs Stratified 91.9% and Marginal Oracle 92.2%.

(b) In what precise sense should readers interpret H (“85–92% headroom”) — as progress toward a marginal-preserving endpoint only?

(c) When are marginal-preserving laws dominated by non-marginal-preserving ones?

A1.

(a) Our work focuses on speculative decoding under the constraint that each proposal slot preserves its marginal distribution (Xr∼q)(X_r\sim q). Accordingly, Table 1 and Figure 2 compare methods within this marginal-preserving setting, and therefore do not include αgreedy\alpha_{\mathrm{greedy}} (Hu et al., 2025), whose proposal law changes the slot marginals.

We have now explicitly stated in the captions that Table 1 compares methods within the marginal-preserving class (see line 345 of the revised manuscript) and that Figure 2 reports the marginal-preserving acceptance headroom captured beyond Optimal IID (see lines 338–339 of the revised manuscript).

In practice, existing non-marginal-preserving proposal methods including αgreedy\alpha_{\mathrm{greedy}} do not consistently outperform marginal-preserving methods in acceptance probability. We additionally compared Optimal IID and Stratified with three non-marginal-preserving methods—Hu Greedy (Hu et al., 2025), deterministic Top-nn, and successive sampling with recursive rejection sampling (SS+RRS)—on Gemma-2-27B/2B at T=1T=1 and K=10,000K=10{,}000, across multiple candidate counts:

nnOptimal IIDStratifiedHu GreedyTop-nnSS+RRS
489.81%90.28%87.52%69.55%87.42%
691.89%92.18%89.15%73.54%89.68%
893.03%93.26%89.88%75.61%91.02%

In all three settings, both Optimal IID and Stratified outperform the three non-marginal-preserving baselines. Consistently, Global Resolution (Thomas & Pal, 2026, Appendix O) reports that, on Gemma-2 and Llama-3, Optimal IID performs better at the tested K≥100K\geq100, with gaps approaching 2 percentage points in many configurations with n≥4n\geq4. Thus, Greedy's advantage in our Qwen3-4B/0.6B evaluation does not imply a universal ordering between marginal-preserving and non-marginal-preserving proposal mechanisms.

(b) Yes. HH measures progress toward a target-aware, marginal-preserving endpoint (see Section 5, Equation (14)). We have now made this scope explicit in the caption of Figure 2 to avoid ambiguity (see lines 338–339 of the revised manuscript).

(c) Greedy guarantees coverage of the highest-probability draft tokens but leaves a potential coverage deficit among the remaining tokens. When this deficit is smaller than the unavoidable deficit under the marginal-preserving constraint, Greedy strictly outperforms all marginal-preserving proposal laws.

Specifically, let G=Top⁡n−1(q)G=\operatorname{Top}_{n-1}(q) denote the set of the n−1n-1 highest-probability tokens under qq, with q(G)<1q(G)<1. This occurs if and only if

\left(p_i-\frac{q_i}{1-q(G)}\right)_+ < \sum_i(p_i-nq_i)_+.$$ Beyond this specific criterion, comparisons between marginal-preserving and non-marginal-preserving proposal mechanisms involve a much broader range of methods and settings, and we do not claim contributions to such cross-class comparisons.
AuthorsOpenReview ↗

Response (2/3): Q2 and Q3

Q2. Is equal-mass stratification optimal among pp-oblivious proposal laws with slot marginals qq? If not, can you exhibit a same-marginal law with strictly better α∗\alpha^*? This determines whether the remaining 8–15% is closable without observing pp.

A2. No. Equal-mass Stratified is not necessarily optimal among all pp-oblivious proposal laws preserving the slot marginals qq.

Consider n=2n=2, q=(1/3,1/3,1/3)q=(1/3,1/3,1/3), token order (1,2,3)(1,2,3), and p=(1/6,2/3,1/6)p=(1/6,2/3,1/6). Stratified draws independently from a1=(2/3,1/3,0)a_1=(2/3,1/3,0) and a2=(0,1/3,2/3)a_2=(0,1/3,2/3). Thus, cstrat(2)=5/9c_{\mathrm{strat}}(\\{2\\})=5/9, giving α∗_strat=8/9\alpha^*\_{\mathrm{strat}}=8/9. Alternatively, sample two distinct tokens uniformly without replacement and randomly permute their positions. Output token 2 whenever it appears, and otherwise select uniformly between tokens 1 and 3. This marginal-preserving proposal law achieves α∗=1>8/9=α∗_strat\alpha^*=1>8/9=\alpha^*\_{\mathrm{strat}}.

Moreover, a single pp-oblivious proposal law cannot universally attain the pp-aware Marginal Oracle. Consider n=2n=2 and q=(1/4,1/4,1/4,1/4)q=(1/4,1/4,1/4,1/4). For any two-token subset SS, the target uniform on SS has oracle acceptance 1. However, every two-candidate pool misses at least one of the six such subsets. Hence, for any fixed proposal law QQ, there exists a target pp with α∗(p,Q)≤5/6<1=αor(p,q,2)\alpha^*(p,Q)\leq5/6<1=\alpha_{\mathrm{or}}(p,q,2).

Therefore, further improvements over Stratified are possible without observing pp, but universal attainment of the Marginal Oracle is impossible.

Q3.

(a) At K=100K=100 in E2E, what is the per-round cost of rebuilding the Stratified plan when p,qp,q change every step,

(b) and how does it decompose between the 0.181 ms “plan preparation” and 0.308 ms “online” rows?

(c) What support size makes fresh construction a bottleneck?

A3.

(a) At each decoding round, a fresh plan is prepared at a cost of 0.342 ms per verification round at K=100K=100 (see Appendix E.8, Table 6).

(b) Plan preparation costs 0.342 ms/round, while online construction, sampling, and correction cost 0.582 ms/round (see Appendix E.8, Table 6).

We have clarified in the caption of Table 6 that the Stratified plan is rebuilt for the new p,qp,q at each decoding round, and added per-round costs for the preparation and online stages to make the requested cost decomposition explicit (see lines 2108–2118 of the revised manuscript).

(c) Our method does not encounter a computational feasibility bottleneck at vocabulary scale. Stratified remains computationally feasible even with full-vocabulary draft support (see Figure 5).

However, under our current hardware implementation, increasing KK eventually introduces a performance bottleneck, causing Stratified to become slower than the simpler Sequential IID baseline. We conducted an additional E2E support-size sweep and have added the results to Appendix E.10, Table 8 (see lines 2215–2233 of the revised manuscript):

Draft support KKSequential IID (ms/token)Stratified (ms/token)Δ\Delta (ms/token)Plan construction (ms/round)
5013.59813.429+0.1690.2923
10013.54413.421+0.1230.342
20013.54813.407+0.1410.2983
50013.56113.445+0.1160.3388
100013.53413.447+0.0870.3526
200013.53913.474+0.0650.3968
300013.66013.661−0.0010.5132
400013.58213.594−0.0120.5292
800013.66713.771−0.1040.6892

The E2E performance crossover occurs at approximately K=3000K=3000 in our current implementation.

AuthorsOpenReview ↗

Response (3/3): Q4 and References

Q4. Theorem 2 gives strict improvement iff some IID-bottleneck subset has unequal stratum masses. Can you quantify expected gain’s dependence on token order?

A4. For a given token order π\pi, let arπ(S)a_r^\pi(S) denote the probability mass of subset SS in stratum rr. By Appendix B.1 (Lemma 10), the acceptance gain is exactly

min⁡S[Diid−d(S)+gπ(S)],\min_S\left[D_{\mathrm{iid}}-d(S)+g_\pi(S)\right],

where

D_{\mathrm{iid}}=\max_S d(S),$$ and $$(1-q(S))^n-\prod_{r=1}^{n}(1-a_r^\pi(S)).$$ Since $\sum_r a_r^\pi(S)=nq(S)$, concentrating a subset's probability mass more unevenly across strata increases its coverage gain (in the majorization sense). In particular, for $n=2$, $$g_\pi(S)=\frac14\left(a_1^\pi(S)-a_2^\pi(S)\right)^2.$$ Thus, favorable orders increase coverage on the $p$-dependent IID-bottleneck and near-bottleneck subsets, which determine the actual acceptance gain. 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 results are reported as follows. The mean acceptance rate across random orders differs from the decreasing-$q$ 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-$q$ (Table 7) | 86.5408% | | Random orders (mean of 32) | 86.5398% | | Random orders (min–max) | 86.5170%–86.5642% | **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](https://proceedings.iclr.cc/paper_files/paper/2025/file/0907335ecf28faf15be54485dbcbe70e-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](https://proceedings.iclr.cc/paper_files/paper/2026/file/83995c2acef585ae0f0d647154cfdd85-Paper-Conference.pdf).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.