acceptodds
Under review as a conference paper at ICLR 2027

Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling

Abstract

The goal of -step speculative decoding is to accelerate autoregressive decoding of a target model by using a cheaper draft model to generate a candidate path of tokens. Based on a verification algorithm involving target and draft model probabilities, a prefix of the candidate sequence is accepted, and an additional correction token is sampled from a residual distribution to ensure that the final output adheres to the target distribution. While standard speculative decoding uses a verification algorithm which is independent at each token on the path, a recent extension called block verification uses a joint condition involving all sampled on-path probabilities. Block verification (BV) was shown to be optimal over all verification algorithms which use only on-path probabilities, improving on standard speculative decoding. In this work, we first show that block verification is optimal even over verification algorithms that use off-path probabilities, by constructing an information-agnostic linear program (LP). Further, we can extend our LP to the setting where the draft model samples multiple candidate paths, and use it to construct a natural class of multi-path block verification generalizations. While computing the optimal algorithm in this class is not tractable, by considering a stricter class of greedy algorithms, we can formulate an efficient method called greedy multi-path block verification (GBV). Empirically, GBV can improve block efficiency by over 30% and reduce decoding walltimes by over 15% relative to BV. At temperature 0.2 on Llama-3 70B, GBV can improve the end-to-end decoding throughput of SOTA multi-path verification methods by over 15%.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
inference, LLMs

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_nYuqOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Greedy Multi-Path Block Verification (GBV), an extension of block verification for speculative decoding with multiple independently sampled draft paths. The authors formulate single-path and multi-path verification as linear programs and characterize optimal multi-path verification through path selection followed by block verification under the distribution induced by that selection. Since finding the optimal selection rule is computationally impractical, GBV uses a tree-based ranking to select a candidate path and efficiently compute its modified draft distribution. Experiments demonstrate speedups in selected configurations, while also revealing substantial sensitivity to model pairs, sampling temperatures, and ranking heuristics.

Critical strengths
  1. Useful theoretical characterization. The information-agnostic LP formulation provides a systematic framework for studying verification efficiency. In particular, the single-path analysis identifies the prefix-plus-correction requirement as a limitation that persists even when off-path probabilities are available. The extension to multiple paths offers further insight into the potential benefits of expanding the candidate set.
  2. Principled treatment of selection bias. The method explicitly accounts for the fact that selecting a path changes its sampling distribution. Computing the induced distribution qΓq^\Gamma and using it in block verification provides a principled approach to maintaining the target distribution. The tree-based ordering makes this computation feasible using on-path probability distributions.
  3. Informative empirical analysis. The evaluation covers several model families and examines path count, draft length, sampling temperature, alternative ranking rules, distillation, and integration with an EAGLE-3 drafter. Reporting both block efficiency and wall-clock performance, including configurations where GBV underperforms, helps clarify the practical trade-offs.
Critical weaknesses
  1. The connection between the optimality analysis and the practical heuristic remains limited. The theoretical characterization does not establish an approximation ratio or a non-degradation guarantee for the proposed ranking rule. Greedy selection can move an already well-aligned draft distribution away from the target. For example, with L=1L=1, p=(0.51,0.49)p=(0.51,0.49), and q=(0.5,0.5)q=(0.5,0.5), the default p/qp/q ordering prefers the first token. Selecting the highest-ranked of two independent drafts produces qΓ=(0.75,0.25)q^\Gamma=(0.75,0.25), reducing the acceptance probability from 0.990.99 to 0.760.76. This is an efficiency limitation rather than a failure of distribution preservation. A clearer characterization of when the heuristic helps would strengthen the methodological contribution.
  2. Practical gains depend strongly on configuration. Tables 3-4 show that the default GBV configuration underperforms single-path BV on the evaluated Qwen3 and Llama3 settings. For Qwen3-32B/0.6B on GSM8K, increasing KK from 1 to 3 reduces block efficiency from 4.322 to 3.571 and increases latency from 79.638 to 100.547 ms/token. Subsequent experiments recover gains through changes to generation length, temperature, or ranking rules, but the paper provides limited guidance on selecting these configurations in advance. A practical selection strategy or fallback to BV would make the method more useful.
  3. The strongest comparative claims require broader experimental support. In Table 10, the clearest low-temperature advantage is demonstrated against Traversal Verification on Llama3-70B/8B with K=2K=2. SpecTr and SpecInfer are not evaluated at this temperature, and the advantage over Traversal does not persist at K=3K=3. These results support a configuration-specific improvement, while broader claims about superiority among low-temperature multi-path methods would require additional comparisons. Repeated runs and uncertainty estimates would also help assess smaller performance differences.
  4. Compatibility and system-level benefits need further qualification. GBV assumes independently sampled draft paths and therefore cannot directly replace verification on deterministic draft trees. The EAGLE-3 integration changes both draft construction and verification, which complicates attribution of improvements over native EAGLE-3. Although the comparison with Traversal provides a useful control, further ablations with matched draft budgets would clarify the contribution of each change. The discussion of applicability to batched serving also remains largely extrapolative without direct multi-request experiments.
Questions for authors
  1. Discrepancy between Table 10 and its description. Appendix Q states that GBV slightly outperforms Traversal at temperature 0.20.2 with K=3K=3. However, Table 10 reports lower block efficiency for GBV (5.663 versus 5.763) and lower throughput (9.775 versus 9.962 tokens/s). Could the authors reconcile the text and table?
  2. Configuration selection and experimental uncertainty. How were KK, draft length, and ranking heuristics selected for the reported comparisons? Were these choices made on separate validation data? Please also clarify the number of independent runs and provide uncertainty estimates for the principal speedup results.
4 comments
AuthorsOpenReview ↗

Rebuttal (part 1)

Thank you for your review. We are glad that you appreciate our theoretical characterization and empirical analysis. We address your points below.

W1

Thank you for raising this point. Your counterexample is correct. Using the skewed draft qΓq^\Gamma in BV is necessary to preserve the target pp distribution. However, greedy ranking rules can sometimes move a well-aligned qq further from pp and thus reduce block efficiency. We do not claim theoretical non-degradation guarantees for GBV ranking rules.

However, we emphasize that this does not detract from the main contribution of our work. Our LP motivates an entire class of greedy multi-path valid verification algorithms, which have never been explored in prior work. GBV-p/qp/q is just one efficiently computable member of this class, and the p/qp/q ranking rule is a knob that practitioners can directly tune. For example, Appendix M shows that other ranking rules can be better in certain scenarios. The thesis of our work does not require theoretical claims about the optimal ranking rule.

We have also added exact-LP experiments that directly quantify how far GBV-p/qp/q is from the optimal multi-path verification algorithm. These results show that, despite the lack of a uniform theoretical guarantee, the simple tree-local p/qp/q heuristic is often near-optimal in practice. On realistic deeper Qwen3 trees, mean GBV/optimal block-efficiency ratios are over 0.98, and GBV matches the exact LP optimum on every tested tree at target temperature 0.20.2. These experiments also characterize when the GBV approximation is strongest. Block efficiency is basically optimal at low temperatures, while larger approximation gaps occur as temperature increases. We discuss the full analysis in our response to W1/Q1 for Reviewer jCZW.

W2

We agree with your point that our L=8,K=3L=8,K=3 recommendation was too broad. Thanks to your feedback, we now suggest selecting K,LK,L on a small calibration workload. As described in our Q2 response to Reviewer jCZW, calibration of BV and GBV on OPT-6.7B/350M selects L=2L=2 for both and K=3K=3 for GBV. Over 100 disjoint prompts and three seeds, the resulting GBV configuration reduces latency by 6.6% relative to independently tuned BV, with 95% CI 5.5--7.8%. We will revise our practical recommendation accordingly.

We also emphasize that single-path BV is exactly the K=1K=1 case of our framework, so BV can always be included as a fallback when selecting a configuration.

W3

We agree that our low temperature claim is a bit broader than the current experiment supports. At target temperature 0.20.2 and K=2K=2, GBV achieves 11.415 tokens/s versus 9.773 for Traversal, a 16.8% throughput improvement. At K=3K=3, Traversal is slightly faster, and we did not evaluate SpecTr and SpecInfer at temperature 0.20.2.

Thus, we will clarify our claim that GBV is the strongest multi-path method at low temperatures to the following. First, GBV substantially outperforms Traversal on Llama-3 70B/8B, GSM8K, at temperature 0.20.2 and K=2K=2. Second, although Traversal slightly beats GBV at K=3K=3 at this temperature, the best GBV KK configuration is significantly faster (15%) than the best Traversal KK configuration.

We address the Table 10 discrepancy in Q1.

AuthorsOpenReview ↗

Rebuttal (part 2)

W4

Thank you for raising this point. There is a key structural reason why our EAGLE-3 experiment changes draft construction instead of just replacing EAGLE-3's verification algorithm.

Natively, EAGLE-3 constructs a deterministic draft tree. For deterministic trees, the only multi-path verification algorithm that preserves the target distribution is the trivial one: direct autoregressive sampling from pp until the sampled token exits the tree (if you would like, we can provide a formal proof). This is what EAGLE-3 already does: there is no stochasticity in the draft paths. Thus, GBV, Traversal, or any non-trivial multi-path verification algorithm (as defined in Definition 4.1), cannot be substituted into the native deterministic EAGLE-3 tree without biasing the output distribution away from pp.

This is why Appendix R keeps the trained EAGLE-3 drafter but uses it to sample i.i.d. paths, creating the stochastic proposals needed for GBV. GBV and Traversal then operate on the same K=3,L=6K=3,L=6 draft paths, so our comparison of these EAGLE-3 integrations isolates the effects of verification algorithms in the i.i.d. setting.

Importantly, this is a deliberately naive integration that is strongly mismatched to GBV. The EAGLE-3 drafter was trained for deterministic direct-token prediction, not for calibrated i.i.d. sampling or GBV, and we perform no retraining. Despite this mismatch, GBV already substantially outperforms native EAGLE-3 at high temperature: at temperature 1.31.3, throughput increases from 32.8932.89 to 60.3860.38 tokens/s. A better optimized integration would train the drafter for the i.i.d.-draft and GBV pipeline, similar to our GBV-aligned distillation experiments, and likely further improve our GBV results.

We agree that a matched draft budget would be useful from a systems standpoint. However, this would not isolate the impact of the verification algorithm. Deterministic EAGLE-3 trees must use direct pp-sampling, but GBV needs stochastic i.i.d. draft paths. Thus, even with matched drafting cost, this experiment would compare two different end-to-end pipelines, not two verification algorithms on the same drafts. Our GBV-versus-Traversal comparison uses identical i.i.d. draft paths and thus directly isolates the effect of verification, so it is more relevant to our work.

We also agree that batched request experiments would be useful, but since our work focuses on improving verification algorithms, this is again more relevant to systems and deployment.

Q1

Thank you for catching this. Table 10 is correct, but the corresponding Appendix Q sentence reverses the K=3K=3 comparison. At temperature 0.20.2 and K=3K=3, Traversal has higher block efficiency (5.763 versus 5.663) and throughput (9.962 versus 9.775 tokens/s). We will correct this sentence. At K=2K=2, GBV achieves 11.415 versus 9.773 tokens/s for Traversal, a 16.8% improvement. We discussed how we would clarify our low temperature claims in W3.

Q2

The original headline results were obtained from one end-to-end run, and original experiments did not use a held-out calibration protocol. We will clarify both points. The main OPT experiments fixed L=8L=8 and the p/qp/q ordering and reported the full K∈{1,2,3,4}K\in\{1,2,3,4\} sweep, with those ranges chosen from values used in prior speculative decoding papers. Appendix M explores alternative rankings and generation lengths, and the EAGLE-3 integration uses K=3,L=6K=3,L=6 after tuning. We will clarify these and no longer present K=3K=3 as a universal default.

To robustly address configuration selection and uncertainty, we ran the held-out calibration experiment described in our response to Q2 for Reviewer jCZW. We selected configurations on 32 calibration prompts and evaluated the frozen choices on 100 disjoint prompts over three seeds. Independent calibration chooses L=2L=2 for BV and L=2,K=3L=2,K=3 for GBV, and held-out latency is 19.9619.96 versus 18.6318.63 ms/token, a 6.6% reduction with paired-bootstrap 95% CI 5.5--7.8%. We will recommend this cheap calibration procedure, with K=1K=1 included as the BV fallback, rather than suggesting a fixed universal configuration.

In light of these improvements and clarifications, we would greatly appreciate it if you would consider raising your score. Do you have any other questions we can address?

Thank you for the detailed rebuttal and additional experiments. The new LP comparisons and held-out calibration study meaningfully address my concerns, and I appreciate the corrected and narrowed performance claims. I will raise my score from 2 to 3, while retaining two follow-up questions. Could you validate the calibration procedure on Qwen3/Llama3, where default GBV underperformed? How representative are the top-k-truncated distributions in the multi-step LP experiments of the original full-vocabulary setting?

AuthorsOpenReview ↗

Qwen calibration and LP truncation representativeness

Thank you for your positive reassessment and the two follow-up questions. Our correction comment documents the position-indexing fix and supersedes the earlier Qwen/Llama block-efficiency regressions, low-temperature advantage over Traversal, and temperature-1.3 EAGLE-3 speedup claims. The theoretical results and main OPT conclusions are unchanged.

The corrected Table 3 shows higher block efficiency than BV at every tested multi-path K.

Corrected Table 3. Block efficiency at L=8 and temperature 1.0. Higher is better.

Model pairDatasetK=1 (BV)K=2K=3K=4
Qwen-3 32B/0.6BGSM8K4.2324.7454.9555.081
Qwen-3 32B/0.6BHumanEval4.2434.7295.0345.116
Qwen-3 32B/0.6BMATH5004.8405.3125.5415.637
Qwen-3 32B/0.6BMGSM3.5443.9084.1324.247
Qwen-3 32B/0.6BToolBench2.9993.3543.5593.669
Llama-3 70B/8BGSM8K5.1295.4975.4275.327
Llama-3 70B/8BHumanEval6.0186.4326.5856.500

Calibration beyond OPT. Independently calibrated Qwen-3 GBV reduces held-out latency by 10.52%, with a 95% CI of [9.08%, 11.89%], across 100 disjoint prompts and three seeds. Calibration selects L=4 for BV and L=5, K=4 for GBV, using temperature 1.0 and a 128-token generation limit. Separately, the corrected Llama sweep improves both block efficiency and latency at every tested multi-path K, with best latency reductions of 8.24% on GSM8K and 10.59% on HumanEval.

Truncation representativeness. A controlled width sweep at L=2, K=2, and temperature 1.0 reaches 99.06% mean retained draft path mass at k=16, where GBV achieves 99.46% of the corresponding exact LP optimum on average. Its block efficiency differs from the full-vocabulary GBV control by −0.16%, with a paired 95% CI of [−0.50%, +0.08%]. This directly checks approximation quality when nearly all draft probability mass is retained.

Our experimental follow-up reports the corrected LP comparisons and depth-dependent retained-mass diagnostics alongside the calibration results. Given these results addressing both follow-up questions, we would appreciate your considering a further increase in your score.

Reviewer_7mpyOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies efficient verification algorithms for multi-path speculative sampling to accelerate autoregressive LLM decoding while preserving the target distribution. The authors first formulate single-path and multi-path verification as linear programming problems, establishing the generalized optimality of block verification in the single-path setting and characterizing the optimal multi-path verification algorithm as path selection followed by block verification with a skewed draft distribution. Since the optimal solution is computationally intractable, the authors propose Greedy Multi-Path Block Verification (GBV), which employs efficient tree-based greedy path selection. Experiments on OPT, Qwen3, and Llama3 model families, as well as integration with EAGLE-3, demonstrate improvements in block efficiency and decoding throughput under certain configurations, although the performance gains vary across experimental settings.

Critical strengths
  1. The paper presents a rigorous theoretical framework for both single-path and multi-path speculative verification, with several nontrivial results, including the generalized optimality of block verification and the canonical decomposition of optimal multi-path verification. The theoretical analysis appears technically sound and is supported by detailed derivations and proofs.

  2. The authors further develop an efficient greedy approximation that only requires on-path probability information while preserving the target distribution. The proposed method is computationally tractable and demonstrates meaningful decoding speedup improvements in certain settings.

Critical weaknesses

My major concern is on the empirical speedup side. If we look at the actual end-to-end decoding speedups of GBV, it appear rather limited and highly dependent on the experimental settings. While the main experiments on OPT models show promising improvements, the results on larger models are considerably less encouraging. For example, in Table 4, increasing K from 1 (BV baseline) to 3 increases the decoding walltime from 79.64 to 100.55 ms/token on Qwen3 32B/0.6B, and from 114.12 to 136.27 ms/token on Llama3 70B/8B (GSM8K). More concerningly, the block efficiency itself also decreases in these settings (Table 3), suggesting limitations of the proposed greedy approximation beyond computational overhead. Furthermore, in the comparison with other multi-path methods (Table 10), GBV underperforms Traversal Verification at temperature 1.0 for both K=2 and K=3, and only demonstrates a clear advantage at temperature 0.2 with K=2. Overall, although GBV achieves meaningful speedups under certain configurations, the experimental evidence does not stably establish the effectiveness over existing methods.

Questions for authors

I have a major question on why the block efficiency decreases with more draft paths. In Table 3, the block efficiency of GBV decreases substantially as K increases, even though more draft paths should theoretically provide greater opportunities for verification. Could the authors explain why the proposed greedy approximation exhibits this behavior? In particular, under what conditions might the greedy path selection cause the skewed draft distribution (qΓq^\Gamma) to become less aligned with the target distribution?

4 comments

Thank you for your strong review. We are glad that you found our theoretical framework technically sound and appreciate our practical motivation. We address your points below.

W1

We agree that GBV's gains are configuration-dependent, and we will revise the manuscript to clarify this. We do not claim that increasing KK with a fixed greedy ranking rule must improve block efficiency or walltime. The decreases in Table 3 reflect growing approximation gaps between the greedy rule and the non-decreasing LP optimum as KK increases. We explain this mechanism directly in Q1.

Thus, as described in our response to Q2 for Reviewer jCZW, we now recommend selecting K,LK,L on a small calibration workload and evaluating the frozen configuration on held-out prompts. In our new held-out OPT experiment, calibrated GBV reduces latency by 6.6% relative to independently tuned BV, with 95% CI 5.5–7.8% over 100 held-out prompts and three seeds. Thus, our practical recommendation is not that larger KK always helps, but rather to calibrate the configuration based on the workload. Single-path BV is exactly the K=1K=1 case of GBV, so this procedure can automatically fall back to BV when additional paths do not help.

We also agree that the experiments do not establish universal superiority over all multi-path methods, so we will narrow our empirical claims. As discussed in our response to W3/Q1 for Reviewer nYuq, we will clarify low temperature gains. On Llama-3 70B/8B, GSM8K, temperature 0.20.2, and K=2K=2, GBV improves throughput over Traversal by 16.8%. When selecting the best KK configuration for low temperature, GBV beats Traversal by around 15%.

Q1

This is a great question. Your intuition is right for the optimal multi-path verifier. Optimal block efficiency is non-decreasing in KK, because the verification algorithm can always ignore additional draft paths and recover the optimal strategy for smaller KK.

GBV, however, uses a greedy selection rule, which is not always optimal. Increasing KK changes the skewed draft qΓq^{\Gamma} and sometimes makes it less aligned with pp. For example, with L=1L=1, q=(0.5,0.5)q=(0.5,0.5), and p=(0.6,0.4)p=(0.6,0.4), the p/qp/q ranking prefers the first token. This gives qΓq^{\Gamma} as (0.5,0.5)(0.5,0.5) for K=1K=1, (0.75,0.25)(0.75,0.25) for K=2K=2, and (0.875,0.125)(0.875,0.125) for K=3K=3, with corresponding GBV block efficiencies 1.901.90, 1.851.85, and 1.7251.725. In the limit K→∞K \to \infty, qΓq^{\Gamma} approaches (1,0)(1,0), with block efficiency 1.61.6. (Our response to Q1 for Reviewer jCZW explains how these are computed.) Thus, while additional drafts offer greater opportunities for the optimal verifier, the fixed greedy rule can over-select a region and introduce misalignment with the target distribution.

Specifically, if a highest-ranked set of paths has draft mass ss, GBV assigns it skewed draft mass 1−(1−s)K1-(1-s)^K. If KK is too large, this can exceed the mass assigned by pp. For L>1L>1, such mismatches at early depths can also propagate to later acceptance probabilities. Thus, the degradation in Table 3 arises because as KK increases, the fixed GBV selector moves further from the LP optimum by overshooting the target distribution. Of course, this does not always happen: it depends on whether the sharpening from larger KK moves qΓq^\Gamma closer to pp or overshoots it, and this depends on the alignment between p,qp,q and the ranking rule.

This dependence appears in Qwen3. In Appendix M, using the same Qwen3 pair and p/qp/q ranking on MATH500 but increasing generation length from 128 to 1024 tokens reverses the Table 3 trend. Block efficiency increases from 4.8614.861 at K=1K=1 to 5.9395.939 at K=4K=4. Likewise, on GSM8K, lowering temperature from 1.01.0 to 0.20.2 changes K=3K=3 from worse than BV (3.5713.571 vs. 4.3224.322) to better (4.2194.219 vs. 3.8673.867). This means the Table 3 degradation is configuration-dependent, not intrinsic to Qwen3: generation length and temperature change target-draft alignment and whether KK-induced sharpening moves qΓq^\Gamma closer to pp.

These results show that whether larger KK helps GBV depends on skewed draft alignment. Separately, our new exact-LP experiments quantify how close GBV is to optimal in practice, as described in our response to W1/Q1 for Reviewer jCZW. They show that the p/qp/q ranking is often near-optimal despite this potential failure mode. On realistic deeper Qwen3 trees, mean GBV/optimal block efficiency ratios exceed 0.98, and GBV matches the multi-path LP optimum on every tested tree at temperature 0.2. Thus, while the approximation can degrade with KK in cases like Table 3, it remains very accurate in many other regimes, especially at low temperatures.

In light of these additional experiments and clarifications, we would greatly appreciate it if you would consider raising your score. Do you have any other questions we can address?

Thank you for the detailed rebuttal and additional experiments. The explanation of how greedy path selection can overshoot the target distribution convincingly addresses my main question regarding the degradation in block efficiency as K increases. I also appreciate the new exact-LP comparisons and held-out calibration experiments, which strengthen the empirical analysis.

My primary concern regarding practical speedups is only partially addressed. The new calibration experiment is conducted on OPT, where GBV already demonstrated favorable results. It remains unclear whether the same strategy can yield improvements on Qwen3 and Llama3, where GBV substantially underperformed BV in the original experiments.

Overall, I acknowledge the improvements brought by the rebuttal and continue to appreciate the theoretical contributions. I will maintain my original rating of weak accept.

AuthorsOpenReview ↗

Corrected Qwen/Llama results and held-out calibration

Thank you for your follow-up and for prompting closer examination of the Qwen/Llama regressions. Our correction comment documents the position-indexing fix. The theoretical results and main OPT conclusions are unchanged.

The corrected Qwen/Llama results show higher block efficiency than BV at every tested multi-path K. These supersede our earlier attribution of Table 3’s regressions to greedy overshooting. The analytical example remains valid. The revised Traversal comparison also supersedes our earlier low-temperature advantage claim.

Corrected Table 3. Block efficiency at L=8 and temperature 1.0. Higher is better.

Model pairDatasetK=1 (BV)K=2K=3K=4
Qwen-3 32B/0.6BGSM8K4.2324.7454.9555.081
Qwen-3 32B/0.6BHumanEval4.2434.7295.0345.116
Qwen-3 32B/0.6BMATH5004.8405.3125.5415.637
Qwen-3 32B/0.6BMGSM3.5443.9084.1324.247
Qwen-3 32B/0.6BToolBench2.9993.3543.5593.669
Llama-3 70B/8BGSM8K5.1295.4975.4275.327
Llama-3 70B/8BHumanEval6.0186.4326.5856.500

To address your remaining concern directly, we extended independent calibration to Qwen-3 32B/0.6B on GSM8K. Calibration selects L=4 for BV and L=5, K=4 for GBV. Across 100 disjoint held-out prompts and three seeds, GBV reduces latency by 10.52%, with a 95% CI of [9.08%, 11.89%], at temperature 1.0 with a 128-token generation limit.

For Llama, the corrected L=8 sweep improves both block efficiency and latency at all six tested multi-path configurations, with best latency reductions of 8.24% on GSM8K and 10.59% on HumanEval. Our experimental follow-up provides the updated calibration and LP results.

Given these results directly addressing your remaining concern about performance beyond OPT, we would appreciate your considering an increase in your score.

Thank you for the thorough follow-up. I'm glad that a bug has been identified and corrected in time, which helps to clear the major performance concern. I also have checked the code change and believe the correction is right. I appreciate the authors' efforts in rerunning the experiments.

The corrected results, with the new held-out calibration, substantially strengthen the empirical evidence and convincingly address my primary concern regarding the practical effectiveness of GBV. Now in most cases GBV outperforms BV, and I believe the strong theoretical contributions and improved empirical validation make this a solid paper.

I will therefore raise my rating from 3 to 4.

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

This paper proves the optimality of Block Verification (BV) even with off-path probabilities using a linear programming formulation. It then extends the framework to multi-path speculative decoding and proposes an efficient greedy algorithm (GBV). Experiments show that GBV can improve block efficiency and decoding speed over BV and existing multi-path methods in certain settings.

Critical strengths
  1. The paper provides a well-motivated LP formulation and establishes the optimality of BV even with access to off-path probabilities.

  2. The extension to multi-path verification reveals how off-path information can improve decoding efficiency and characterizes the structure of the optimal verification algorithm.

  3. The proposed GBV algorithm provides an efficient approximation to the intractable optimization problem, with theoretical motivation and empirical speedups in certain settings.

Critical weaknesses
  1. While the theoretical formulation in the first part of the paper is rigorous, the final algorithm relies on an intuition-driven approximation and lacks theoretical guarantees.

  2. The proposed method is not guaranteed to outperform Block Verification (BV), and the paper lacks a theoretical analysis of this limitation. Moreover, the experimental comparisons are not sufficiently rigorous (see Questions for details).

Questions for authors
  1. My understanding is that selecting a single sequence and then skewing the probability mass may reduce its acceptance probability compared to standard Block Verification (BV) (please correct me if I am mistaken). Therefore, the proposed method does not appear to have a theoretical guarantee of strictly outperforming single-path BV, and it remains unclear under what conditions the proposed method performs better or worse. Empirically, Table 3 in Appendix L shows that block efficiency is consistently highest at K=1K=1. While the authors provide an explanation for the walltime results, they do not explain the degradation in block efficiency. Could the authors provide further theoretical or empirical insights into when and why the proposed algorithm is beneficial?

  2. The ablation study on block length L is relatively coarse-grained. Table 9 only reports results for L=8,16,24L=8,16,24, without considering smaller values of L, while the other experiments fix L=8L=8. Since prior works such as EAGLE often use relatively small block lengths (e.g., L=5L=5), the motivation for choosing L=8L=8 is unclear. This raises the concern that the comparisons with single-path BV K=1K=1 in Tables 1 and 2 may be conducted under a parameter setting that favors the proposed method. Could the authors provide a more comprehensive ablation study, particularly for smaller values of L?

  3. The paper presents multi-path speculative decoding as a key contribution. However, several existing speculative decoding methods have already studied iterative verification of multiple draft candidates [1]. Could the authors clarify the conceptual differences between the proposed approach and these existing methods, particularly in terms of their underlying mechanisms and design motivations? An experimental comparison is not necessary; a conceptual discussion would be sufficient.

[1] https://arxiv.org/abs/2502.18779

4 comments
AuthorsOpenReview ↗

Rebuttal (part 1)

Thank you for your detailed review. We are glad that you appreciate our LP formulation, multi-path characterization, and practical motivation for GBV. We address your points below.

W1

Thank you for raising this point. However, we believe this does not detract from the impact of our work. We emphasize that our main contribution is a unified LP framework for multi-path verification algorithms. This motivates the class of greedy multi-path valid verification algorithms, which have never been explored in prior work. GBV with the p/qp/q heuristic is only one method in this class. Even though it has a simple intuition-driven derivation, it maintains significant improvements over baselines. Also, the choice of the local tree-based ranking is a design choice that practitioners should vary: we see in Appendix M that various alternative ranking rules perform well in different settings. Thus, the significance of our work does not rest on explicitly computing or making theoretical claims about the optimal ranking rule. Thanks to your feedback, we will make these clarifications more explicit in our manuscript.

We have also now added exact-LP experiments that quantify the approximation gap for tree-based heuristics, i.e. tell us how far off GBV-p/qp/q is from the optimal multi-path block efficiency. These significantly strengthen our point above, showing that even without theoretical guarantees on our approximation rule, our simple heuristic often turns out to be near-optimal in practice.

First, we generate 1,600 synthetic examples with (∣V∣,L)∈{(3,2),(2,3)}(|V|,L)\in\{(3,2),(2,3)\} and K∈{2,3}K\in\{2,3\}, GBV-p/qp/q has a median ratio of 0.9528 to optimal block efficiency, a 5th-percentile ratio of 0.7680, and a minimum of 0.6689. On 200 instances with full enumeration of global rankings, median ratios to optimal block efficiency are 0.9884 for the best global greedy ranking, 0.9386 for the best tree-local ranking, and 0.9373 for p/qp/q. Thus, for general token distributions, not much block efficiency is lost by restricting path selection to an efficiently computable ranking.

Next, to include more realistic LLM distributions, we evaluate 192 full-vocabulary Qwen3 32B/0.6B contexts from MATH500 and test single-token draft paths. At L=1L=1, the exact LP optimum can be found with the i.i.d. case of Hu et al.’s method (your linked paper [1]). Mean ratios of GBV block efficiency to the LP optimum are shown below, and demonstrate that our p/qp/q approximation is empirically near-optimal in various settings.

KTarget temperature 0.2Target temperature 0.6Target temperature 1.0
20.99980.99800.9980
30.99940.99550.9927
40.99860.99250.9877

Finally, testing the most realistic setting of deeper Qwen3 draft trees (L>1L>1), we solve 144 exact multi-path LPs using top-kk drafting, with (k,L)∈{(2,8),(3,5),(4,4)}(k,L)\in\{(2,8),(3,5),(4,4)\} and K=2K=2. GBV matches the LP optimum on every tree at target temperature 0.2. At temperatures 0.6 and 1.0, mean ratios to the optimum range from 0.9860 to 0.9896. Some cases have larger gaps, with minimum ratios at temperature 1.0 of 0.8061, 0.8626, and 0.8843 for the three tree settings. Each comparison uses the same truncated draft distribution for GBV and the optimal verifier. Thus, approximation quality still remains strong, especially at low temperatures.

W2

We address your point on the theoretical guarantees compared to BV in Q1, and your point on the experimental comparisons in Q2.

Q1

Thank you for raising this important point. Your understanding is correct. GBV fixes a ranking and selects the highest-ranked sampled path, which induces a skewed draft qΓq^\Gamma, and then runs single-path BV. Thus, the question of whether GBV or single-path BV is better boils down to which of qq and qΓq^\Gamma is better aligned with the target distribution pp.

For example, take L=1L=1 and a 2-token vocabulary with q=(0.5,0.5)q=(0.5,0.5) and p=(0.6,0.4)p=(0.6,0.4). The p/qp/q ordering prefers the first token, so selecting the highest-ranked of 2 i.i.d. drafts gives qΓ=(0.75,0.25)q^{\Gamma}=(0.75,0.25). Now, for L=1L=1, single-path BV with target pp and draft rr has block efficiency 1+∑xmin⁡p(x),r(x)1+\sum_x\min{p(x),r(x)}. Thus, by plugging in r=qr=q for single-path and r=qΓr=q^{\Gamma} for two-path GBV, we find single-path BV has block efficiency 1.90 and two-path GBV is 1.85. GBV is not better here since it places too much emphasis on the first token. Conversely, with p=(0.8,0.2)p=(0.8,0.2) and the same qq, two-path GBV is better: it correctly puts emphasis on the first token and improves block efficiency from 1.70 to 1.95.

AuthorsOpenReview ↗

Rebuttal (part 2)

Q1 (cont.)

For L>1L>1, GBV concentrates mass on higher-ranked paths. For a highest-ranking set with draft mass ss, its skewed draft mass becomes 1−(1−s)K1-(1-s)^K. This can sometimes overshoot the mass allocated to this set by the target pp distribution, leading to a mismatch and decreasing block efficiency. This mechanism explains the block efficiency degradation in Table 3.

We want to reiterate that this does not detract from our results, because practitioners should adapt GBV K,LK,L based on their experimental setting (single-path BV is the K=1K=1 setting). Thanks to your feedback, we will add this discussion and clarify this point in our manuscript.

Q2

We agree that comparisons at fixed LL do not establish performance at each method’s best draft length. We have now run all 15 combinations of L=2,4,5,6,8L=2,4,5,6,8 and K=1,2,3K=1,2,3 for OPT-6.7B/350M and MATH500, using target/draft temperature 1.0 and a 128-token generation cap. We selected configurations on 32 calibration prompts and evaluated them on 100 disjoint prompts across three seeds. The table below reports held-out end-to-end latency in ms/token.

Draft length (L)BV (K=1)GBV (K=2)GBV (K=3)
219.9618.7618.63
421.5419.8919.50
522.6620.6420.65
624.3322.2121.95
827.2924.7924.58

At the requested L=5L=5, block efficiencies are 2.871, 3.322, and 3.376 tokens per target call for BV, 2-path GBV, and 3-path GBV. GBV reduces latency by 8.9% for K=2K=2, with a paired prompt-bootstrap 95% CI of 7.1--10.7%, and 8.9% for K=3K=3, with CI of 6.8--10.9%. The corresponding reductions at L=8L=8 are 9.1% and 9.9%.

Calibration selected L=2L=2 for both methods and K=3K=3 for GBV. These independently selected configurations have 19.96 ms/token for BV and 18.63 ms/token for GBV on held-out prompts, a 6.6% latency reduction with a 95% CI of 5.5--7.8%. Thus, GBV’s advantage persists after tuning the BV baseline on this workload.

Q3

Thank you for bringing up the Hu et al. paper. They study optimal acceptance of a single next token from multiple draft candidates in general draft settings, and construct an algorithm to achieve this acceptance in their own non-i.i.d. draft setting. Our framework instead studies optimal verification of multiple length LL i.i.d. draft paths and focuses on maximizing block efficiency. These two objectives coincide at L=1L=1 for i.i.d. drafting. For i.i.d. L>1L>1, making locally optimal next-token choices (i.e. achieving Hu et al’s optimal i.i.d. acceptance) does not necessarily maximize block efficiency. This is why the methods Hu et al. propose cannot be applied to our multi-path LP.

To reiterate, our main contribution is an multi-path LP that captures constraints across depths. This shows that optimal multi-path verification can be decomposed into path selection, and BV with the selection-skewed draft distribution. GBV makes this approach practical via tree-local rankings and an efficiently computable skewed distribution, resulting in a strong multi-path verification algorithm. While Hu et al. also demonstrate their method in a multi-step (L>1L>1) setup with EAGLE experiments, they do not use i.i.d. drafting and are not technically a multi-path verification algorithm under our Definition 4.1. We will clarify this distinction in the related work discussion.

In light of these improvements and clarifications, we would greatly appreciate it if you would consider raising your score. Do you have any other questions we can address?

Thank you for the detailed explanations and additional experiments, which address some of my concerns. However, the following concerns remain unresolved.

  1. Regarding Q1: Empirically, Table 3 in Appendix L shows that block efficiency is consistently highest at K=1K=1. This raises a concern about the discrepancy between the theoretical motivation of the proposed method and its empirical performance. Simply suggesting that practitioners should adapt KK and LL based on their experimental settings is insufficient. A deeper theoretical understanding is needed, particularly regarding under what characteristics of the original draft and target distributions GBV can outperform single-path BV, rather than retrospectively explaining its improvement by the better alignment of the skewed distribution with the target distribution.

  2. Regarding Q3: I believe the fundamental objective of developing a theoretically better verification algorithm is to maximize the overall number of accepted tokens, regardless of whether the draft sequences are generated in an i.i.d. manner. Restricting the discussion to i.i.d. drafting should not serve as a justification for excluding comparisons with other relevant verification methods. I encourage the authors to discuss the advantages and limitations of their approach within a broader framework.

AuthorsOpenReview ↗

Corrected results, shorter drafts, and Hu et al. comparison

Thank you for your detailed follow-up. Our correction comment documents a position-indexing fix. The theoretical results and main OPT conclusions are unchanged.

Q1. Corrected Table 3 shows higher GBV block efficiency than BV at every tested K=2,3,4 across all seven Qwen/Llama pairs. This supersedes our earlier attribution of those regressions to greedy overshooting. The analytical counterexample remains valid.

Corrected Table 3. Block efficiency at L=8 and temperature 1.0. Higher is better.

Model pairDatasetK=1 (BV)K=2K=3K=4
Qwen-3 32B/0.6BGSM8K4.2324.7454.9555.081
Qwen-3 32B/0.6BHumanEval4.2434.7295.0345.116
Qwen-3 32B/0.6BMATH5004.8405.3125.5415.637
Qwen-3 32B/0.6BMGSM3.5443.9084.1324.247
Qwen-3 32B/0.6BToolBench2.9993.3543.5593.669
Llama-3 70B/8BGSM8K5.1295.4975.4275.327
Llama-3 70B/8BHumanEval6.0186.4326.5856.500

Corrected LP comparisons yield mean GBV/optimal block-efficiency ratios of 98.90–100% for full-vocabulary L=1 and 98.63–100% for deeper truncated trees, strengthening the empirical support for the heuristic.

Q2. Gains persist with shorter drafts. At L=5, K=3, OPT latency falls 9.69% (95% CI 7.45–11.94%). Independently calibrating both methods gives a 6.17% held-out reduction (95% CI 4.74–7.58%).

Q3. Appendix S now directly compares with Hu et al.’s non-i.i.d. method. GBV has higher block efficiency than all three tested tree variants, including 23.88% higher than their best variant by this metric.

Hu et al. comparison. Block efficiency on Qwen-3 32B/0.6B and GSM8K, using 500 prompts, three seeds, temperature 1.0, and 128 generated tokens.

MethodBlock efficiency (tokens per target call)
BV, K=14.169
GBV, K=24.745
GBV, K=34.955
GBV, K=45.081
Hu et al., binary depth 43.911
Hu et al., four-way depth 33.604
Hu et al., sparse depth 54.101

We would appreciate your reconsideration of the rating in light of the corrected evidence and broader comparison.

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

The paper formulates single- and multi-path speculative verification as linear programs, strengthens the optimality result for single-path block verification, and characterizes optimal multi-path verification. It proposes greedy multi-path block verification (GBV), which selects a draft path and adjusts its proposal distribution before verification. Experiments across OPT, Qwen, and Llama models, including integration with EAGLE-3, demonstrate configuration-dependent efficiency gains, with walltime reductions exceeding 15% in selected settings.

Critical strengths
  1. Substantive theoretical characterization. The LP framework strengthens single-path BV optimality and characterizes feasible multi-path verification, clarifying the limits of exact speculative sampling.
  2. Principled handling of path selection. GBV explicitly accounts for the proposal distribution induced by selecting among multiple drafts. This connects the theoretical framework to an implementable algorithm, with measurable walltime improvements in selected configurations.
Critical weaknesses

Inconsistent practical gains. GBV is slower than BV in several default Qwen and Llama settings, and its EAGLE-3 integration reduces throughput at temperature 1. Improvements depend substantially on temperature, generation length, and ordering heuristic. Without a configuration-selection strategy validated on held-out settings, its practical advantage remains uncertain.

Questions for authors

Configuration selection: How were the path count, draft length, and ordering heuristic selected? Were they tuned on separate validation data?

3 comments

Thank you for your strong review. We are glad that you appreciate our theoretical contributions and find our presentation clear. We address your points below.

W1

Thank you for raising this important point. We agree that the gains of GBV relative to BV depend on the model, temperature, generation length, and ordering heuristic. Practitioners should select the best GBV configuration (BV is one of these configurations) prior to deployment.

Thus, we recommend calibrating KK, LL, and the ranking heuristic on a small representative workload for each target-draft pair and hardware configuration, including K=1K=1 (standard BV). Selection aims to minimize end-to-end latency under the intended generation settings. This calibration can be performed before deployment, avoiding runtime selection overhead.

The existing results motivate this approach. BV is best in the default Qwen and Llama settings, but temperature and generation-length ablations show regimes where GBV wins. Also, while native EAGLE-3 has higher throughput at temperature 1.0, the GBV integration improves throughput at higher temperatures.

We have now tested this selection strategy on OPT-6.7B/350M and MATH500. We choose KK and LL based on 32 calibration prompts, with the p/qp/q ranking fixed, then evaluate the frozen configurations on 100 held-out prompts over three seeds. Calibration selects L=2L=2 for both methods and K=3K=3 for GBV. Now, GBV reduces held-out latency by 6.6% relative to an independently calibrated BV baseline, with paired prompt-bootstrap 95% CI 5.5–7.8%. This shows that cheap workload calibration can be highly effective in deploying the best version of GBV. Thanks to your feedback, we will clarify our tuning procedure and change our recommendation of K=3,L=8K=3,L=8 in the manuscript to a discussion on calibration.

Q1

Our default experiments use L=8L=8 and the theoretically motivated p/qp/q ranking, while varying the number of draft paths across K=1,2,3,4K=1,2,3,4. The bounds on K,LK,L were selected by looking at choices used in prior speculative decoding papers. We include a finer-grained sweep over LL in our Q2 response to Reviewer jCZW. Appendix M also explores alternative local ranking functions and longer generation lengths, and the EAGLE-3 integration uses K=3,L=6K=3,L=6 following configuration tuning. Our original manuscript does not always apply a held-out configuration selection protocol. Thanks to your feedback, we will clarify which choices were defaults and which followed calibration or exploratory sweeps.

In light of our configuration-selection strategy results, we would highly appreciate it if you could consider increasing your score. Do you have any other questions we can address?

AuthorsOpenReview ↗

Follow-up: Corrected results and held-out Qwen calibration

Following up on our earlier response, we now have corrected Qwen-3 and Llama-3 results and a completed held-out calibration study on Qwen-3.

The corrected results substantially strengthen the evidence beyond OPT. We identified and fixed a position-indexing error in the batched target forward pass as detailed in our correction comment, the main OPT conclusions are unchanged. GBV now improves block efficiency over BV in every tested Qwen-3 and Llama-3 multi-path configuration, as shown below.

Corrected Table 3. Block efficiency in tokens per target-model call. Higher is better.

Model pairDatasetK=1 (BV)K=2K=3K=4
Qwen-3 32B/0.6BGSM8K4.2324.7454.9555.081
Qwen-3 32B/0.6BHumanEval4.2434.7295.0345.116
Qwen-3 32B/0.6BMATH5004.8405.3125.5415.637
Qwen-3 32B/0.6BMGSM3.5443.9084.1324.247
Qwen-3 32B/0.6BToolBench2.9993.3543.5593.669
Llama-3 70B/8BGSM8K5.1295.4975.4275.327
Llama-3 70B/8BHumanEval6.0186.4326.5856.500

The best tested GBV configuration also reduces latency in six of these seven settings, and 12 of 13 model–dataset pairs overall, including OPT.

Held-out calibration also succeeds on Qwen-3. We selected K and L on 32 GSM8K calibration prompts, then evaluated the frozen configurations on 100 disjoint prompts over three seeds. We retained the p/q ranking, temperature 1.0, and a 128-token generation limit, with independent draft-length calibration for BV.

Calibration selected L=4 for BV and L=5, K=4 for GBV. Held-out latency decreased from 41.410 to 37.053 ms/token, a 10.52% reduction [95% CI 9.08–11.89%]. The corrected OPT calibration likewise confirms a 6.17% reduction [4.74–7.58%].

These results address the concern about practical gains beyond OPT and support the calibration procedure proposed in our earlier response. Our theoretical results remain unchanged. Given the strengthened larger-model results and successful held-out calibration, we would appreciate your considering an increase in your score.

Thanks for rerunning the experiments. GBV still reduced latency on held-out prompts after both methods were tuned, which addresses my main concern. My score stays the same.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Fixed error in Qwen/Llama code, and GBV now beats BV comprehensively on Qwen/Llama

We thank Reviewer 7mpy for encouraging closer examination of the Qwen and Llama regressions. This prompted us to revisit our code, where we discovered a position-indexing bug in the batched target forward pass. For your inspection, we have uploaded our fixed code (https://anonymous.4open.science/r/GBV-5898/inference_util.py) as well as a diff from the original code (https://anonymous.4open.science/r/GBV-5898/position_ids_fix.patch).

Accordingly, we have rerun all experiments in Tables 1–12 and updated the discussion. We have modified our manuscript (including our abstract) and uploaded a revised version. The modified text is shown in red. In tables, we color values red when they lie more than 3 bootstrap SEs from original values. Please note that our revised tables and discussion supersede the initial comparisons and interpretations in our original manuscript and earlier rebuttals.

We apologize for this error and graciously thank the reviewers for encouraging us to perform a deeper inspection. The corrected reruns confirm our main OPT claims and reproduce the original OPT block efficiency values within three bootstrap SEs (see [1]). The fixed Qwen and Llama results reverse the previously reported block efficiency regressions relative to BV. This directly addresses a central concern raised by all reviewers and significantly strengthens our paper. In the original manuscript, GBV did not beat BV in the default Qwen and Llama settings: we had to modify generation length, rankings, temperature, and distill to beat BV in limited settings. Now, in the fixed code, at temperature 1.0, GBV achieves lower latency than BV in 12/13 model-dataset pairs spanning all three model families (OPT, Qwen, Llama), when using the best tested path count for each pair.

To highlight the impact of the bug, we evaluate Qwen-3 32B/0.6B on 16 GSM8K prompts over three seeds, with L=8L=8, temperature 1.0, and 128 tokens. Corrected GBV has 16.0% lower latency than BV, while restoring the bug makes its latency 21.4% higher than BV. This direction holds across all three seeds.

MethodBlock efficiencyLatency (ms/token)
BV, (K=1)4.09145.978
GBV, (K=3), corrected5.05638.600
GBV, (K=3), old code3.49755.813

OPT (Section 6). The updated OPT results reproduce the benefits of GBV. In Table 1, all original block efficiency values fall within three bootstrap standard errors of our new results.

Qwen and Llama (Appendix L). Corrected Tables 3 and 4 show higher block efficiency than BV in every tested multi-path configuration, and lower latency for the best tested GBV configuration in six of seven model-dataset pairs.

Multi-path comparison (Appendix Q). GBV now exceeds Traversal’s throughput by 2.75% at temperature 1.0, K=2K=2. Traversal is faster at K=3K=3 and has slightly higher throughput at temperature 0.2. Thus, although our previous claims about GBV winning at low temperatures do not persist, GBV still remains competitive with the top multi-path methods.

EAGLE-3 integration (Appendix R). With the EAGLE-3 drafter, GBV-p/qp/q achieves the highest block efficiency at temperatures 1.2–1.4 and exceeds native EAGLE-3 throughput at 1.4. Native EAGLE-3 has the highest throughput at 1.0–1.3, and Traversal is fastest at 1.4. These results use a simple integration without draft retraining, and we expect GBV-specific training to give further gains.

Separately, the secondary Qwen ablations (Appendices M, N, and O) now complement gains in the main setting, and we have updated their discussions accordingly. The draft length conclusions in Appendix P also persist. Appendix S addresses Reviewer jCZW's request for a broader comparison with Hu et al.’s non-i.i.d. method: GBV has higher block efficiency than all tested Hu tree variants.

We are also rerunning our LLM-based LP approximation, calibration, and shorter LL rebuttal experiments with the fixed code, and extending held-out calibration to Qwen and Llama. We will report the updated results upon completion, within the next few hours. The synthetic data LP results are unaffected by our code bug.

[1] The original experiments used an A100-80GB for OPT/Qwen3 while the original Llama-3 experiments used four NVIDIA A6000 GPUs. Original machines and the seeded prompt subsets on them were unavailable, so our updated experiments use H100 GPUs and fixed public prompt subsets. Hardware differences affect walltime, and prompt selection also impacts block efficiency.

AuthorsOpenReview ↗

Calibration, shorter draft, and LP approximation results still hold after the error fix

Following our error fix above, we report the updated rebuttal experiments below. These results supersede the empirical numbers and interpretations in our earlier responses. As we have previously mentioned, our theoretical results and main OPT conclusions are unchanged, and our Qwen and Llama results are now significantly strengthened. Our main rebuttal conclusions still hold.

Qwen calibration. We select BV and GBV configurations on 32 calibration prompts, then evaluate the frozen choices on 100 disjoint prompts over three seeds, at temperature 1.0 with a 128 tokens and the p/qp/q ranking. On OPT-6.7B/350M and MATH500, calibration chooses L=2L=2 for both methods and K=2K=2 for GBV. Held-out latency is 6.17% lower than calibrated BV, with paired-bootstrap 95% CI 4.74–7.58%. On Qwen-3 32B/0.6B and GSM8K, calibration chooses L=4L=4 for BV and L=5,K=4L=5,K=4 for GBV. Held-out latency is 10.52% lower, with 95% CI 9.08–11.89%. This calibration extension covers Qwen, and we will include Llama results in the camera ready.

Shorter drafts. The corrected OPT sweep shows lower GBV latency at all L=2,4,5,6,8L=2,4,5,6,8 and K=2,3K=2,3. At the previously discussed L=5L=5 setting in our rebuttal, we see that K=3K=3 reduces latency by 9.69%, with 95% CI 7.45–11.94%.

LP approximation quality. The corrected Qwen LP approximation runs have mean GBV-to-optimal block efficiency ratios of 98.90–100% for full-vocabulary L=1L=1 and 98.63–100% for deeper truncated trees. At temperature 0.2, the deeper-tree mean ratios are 99.94–100%. Thus, it is still the case that GBV-p/qp/q is near-optimal empirically.

Top-k truncation representativeness. We test whether GBV’s near-optimality holds when more draft probability mass is retained than in our top-kk deeper-tree LP experiments, where mean mass retention is 62–90% at temperature 1.0. On the same 16 contexts at L=2,K=2,T=1.0L=2,K=2,T=1.0, increasing the truncation width to k=16k=16 retains 99.06% of the original draft path mass on average, while GBV achieves 99.46% of the corresponding LP optimum on average. We also evaluate GBV using the original, untruncated full-vocabulary draft distribution. The truncated version’s block efficiency differs by only −0.16% from this untruncated version, with paired 95% CI −0.50% to +0.08%. Thus, in this controlled two-step setting, high approximation quality persists even when nearly all draft probability mass is kept, and GBV’s top-kk efficiency closely matches its full-vocabulary efficiency.

Hu et. al. comparison. Appendix S now shows GBV has 23.88% higher block efficiency than the strongest tested Hu tree variant. Thus, when maximizing expected accepted tokens, our method beats strong non-i.i.d. drafting approaches.

These results complement our corrected default results for Qwen/Llama, which show block efficiency gains over BV up to 22.34% for Qwen and 9.42% for Llama (Table 3). At K=3K=3, latency reductions reach 23.89% on Qwen/GSM8K at temperature 0.4 and 10.59% on Llama/HumanEval at temperature 1.0 (Tables 8 and 4).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.