- 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
- 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.
- Principled treatment of selection bias. The method explicitly accounts for the fact that selecting a path changes its sampling distribution. Computing the induced distribution 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.
- 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
- 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 , , and , the default ordering prefers the first token. Selecting the highest-ranked of two independent drafts produces , reducing the acceptance probability from to . 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.
- 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 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.
- 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 . SpecTr and SpecInfer are not evaluated at this temperature, and the advantage over Traversal does not persist at . 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.
- 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
- Discrepancy between Table 10 and its description. Appendix Q states that GBV slightly outperforms Traversal at temperature with . 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?
- Configuration selection and experimental uncertainty. How were , 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
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 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 .
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 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 , throughput increases from to 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 -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 comparison. At temperature and , 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 , 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 and the ordering and reported the full 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 after tuning. We will clarify these and no longer present 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 for BV and for GBV, and held-out latency is versus ms/token, a 6.6% reduction with paired-bootstrap 95% CI 5.5--7.8%. We will recommend this cheap calibration procedure, with 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?
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 pair | Dataset | K=1 (BV) | K=2 | K=3 | K=4 |
|---|---|---|---|---|---|
| Qwen-3 32B/0.6B | GSM8K | 4.232 | 4.745 | 4.955 | 5.081 |
| Qwen-3 32B/0.6B | HumanEval | 4.243 | 4.729 | 5.034 | 5.116 |
| Qwen-3 32B/0.6B | MATH500 | 4.840 | 5.312 | 5.541 | 5.637 |
| Qwen-3 32B/0.6B | MGSM | 3.544 | 3.908 | 4.132 | 4.247 |
| Qwen-3 32B/0.6B | ToolBench | 2.999 | 3.354 | 3.559 | 3.669 |
| Llama-3 70B/8B | GSM8K | 5.129 | 5.497 | 5.427 | 5.327 |
| Llama-3 70B/8B | HumanEval | 6.018 | 6.432 | 6.585 | 6.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.
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Γ in BV is necessary to preserve the target p distribution. However, greedy ranking rules can sometimes move a well-aligned q further from p 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/q is just one efficiently computable member of this class, and the p/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/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/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.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=3 recommendation was too broad. Thanks to your feedback, we now suggest selecting K,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=2 for both and K=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=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.2 and K=2, GBV achieves 11.415 tokens/s versus 9.773 for Traversal, a 16.8% throughput improvement. At K=3, Traversal is slightly faster, and we did not evaluate SpecTr and SpecInfer at temperature 0.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.2 and K=2. Second, although Traversal slightly beats GBV at K=3 at this temperature, the best GBV K configuration is significantly faster (15%) than the best Traversal K configuration.
We address the Table 10 discrepancy in Q1.