- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies verification of multiple independently sampled draft sequences. It derives an upper bound on expected accepted length and proposes MDSeq, which can accept a longer prefix even when a shorter prefix failed its individual acceptance test. A scaling factor, residual sampling, and subsequent distribution modification compensate for the accepted probability mass. The paper proves target-distribution preservation and, under a relative depth-level acceptance assumption, a constant-factor lower bound relative to the derived upper bound. Experiments on Spec-Bench report higher average accepted length and modest wall-clock improvements over the strongest evaluated baselines.
Critical strengths
-
The upper bound accounts for both the chance that a prefix appears among the sampled drafts and the probability mass the target assigns to it. The proof of distribution preservation includes residual sampling and the modification of future distributions. The worked example in Appendix A helps explain why that correction is necessary.
-
The comparison with SpecTr and recursive rejection sampling uses the same five independent length-five drafts, making this part of the experimental comparison informative about the verifier itself. MDSeq achieves the best reported average wall-clock speedup on both main model pairs, with additional results for a separate Tiny-Vicuna/Vicuna pair.
Critical weaknesses
-
The near-optimality result depends on Assumption 1, but the paper does not establish when this assumption holds in practice. Uniformly relaxing the prefix threshold does not imply the required inequality between normalized acceptance rates. For example, take , , vocabulary , and . Set . The root is , but
Thus, Assumption 1 can fail even in a small example. This does not contradict the conditional theorem or the distribution-preservation result. The description of the condition as mild needs justification, and the abstract should state that near-optimality is conditional.
-
The wall-clock gains over the best baselines are small, and their variability is not reported. Average speedup improves from 1.87 to 1.94 on Vicuna and from 1.82 to 1.86 on Llama2, but only means over three runs are given. A timing breakdown is also needed for solving for , evaluating residuals, and maintaining the modified distributions after correction. These operations are necessary for exact verification, and their cost matters when the relative speed advantage is only 2.2–3.7%.
Questions for authors
-
Can you provide sufficient conditions for Assumption 1, or measurements of how often it holds and how much it is violated in the evaluated draft–target pairs? What can be said about near-optimality when Assumption 1 fails, as in the example above?
-
How is Algorithm 2 represented and evaluated after a correction introduces a prefix outside the original draft paths? What happens if a new speculative round starts while some positions are still subject to a previous distribution modification? Please explain which model evaluations are needed and whether all these costs are included in WS.
-
What is the run-to-run variability of the wall-clock comparison with RRSw and SpecTr? How much time is spent on drafting, target scoring, and verifier calculations?
2 comments
Response to Q3:
What is the run-to-run variability of the wall-clock comparison with RRSw and SpecTr? How much time is spent on drafting, target scoring, and verifier calculations?
We have added Appendix I, "Computational Overhead Breakdown".We repeated each experiment three times and reported the run-to-run variability in the wall-clock time breakdown comparison with RRSw and SpecTr. The results show that MDSeq achieves the lowest total runtime and highest throughput among baseline methods. Specifically, MDSeq incurs lower cumulative drafting and target-scoring costs because its higher block efficiency (BE) allows more tokens to be generated per decoding iteration, thereby reducing the number of iterations required to produce an output of a given length.
| Method | Drafting | Target scoring | Verifier | DistMod | Prefill | Other | Total | Tokens/s ↑ |
|---|---|---|---|---|---|---|---|---|
| SpecTr | 0.49±0.12 | 1.44±0.33 | 0.112±0.025 | – | 0.04±0.00 | 0.02±0.00 | 2.11±0.48 | 77.65±2.41 |
| RRSw | 0.45±0.13 | 1.42±0.42 | 0.043±0.012 | – | 0.04±0.00 | 0.02±0.01 | 1.98±0.57 | 81.01±3.86 |
| MDSeq | 0.39±0.11 | 1.13±0.32 | 0.066±0.019 | 0.035±0.010 | 0.04±0.00 | 0.02±0.00 | 1.68±0.47 | 83.97±2.31 |
Response to W1 and Q1:
Thanks for the comment. We have added Appendix G, Discussion of Assumption 1, to further investigate the necessity of this assumption and provide both theoretical and empirical evidence supporting our method.
Theoretical guarantee without Assumption 1. We prove that MDSeq achieves an expected acceptance length at least as large as that of Greedy Block Verification [1], without requiring Assumption 1. Specifically, EMDSeq[τ]≥EBV[τ].
Assumption-free lower bound for ρ=K. We further prove that, when the division factor is set to ρ=K, the lower bound on the expected acceptance length in Theorem 3 holds without Assumption 1:
Eρ=K[τ]≥[1−(1−K1)K]⋅∑i=1L∑xi∈Vimin(1−(1−p(xi))K,q(xi)).
To further investigate its practical implications, we compare the BE of MDSeq using ρ=ρ∗ and ρ=K. Our experiments show that ρ=ρ∗ consistently achieves higher BE than ρ=K across all evaluated datasets. Since the lower bound is guaranteed to hold for ρ=K without Assumption 1, the consistently superior empirical performance of ρ=ρ∗ suggests that this lower-bound guarantee also holds for ρ=ρ∗ across the evaluated workloads.
Response to W2:
We respectfully note that we have reported the standard deviations in Table 1 of the main experiments.
Thanks for the comment. We have added Appendix I, Computational Overhead Breakdown, to provide a detailed analysis of the computational costs.
Distribution modification introduces only a small additional cost of 0.035 seconds per question, which is outweighed by the savings in drafting and target scoring.
MDSeq’s verifier cost is higher than RRSw’s primarily because MDSeq additionally solves for ρ. However, MDSeq solves for ρ only once per decoding iteration, whereas SpecTr requires multiple solves. This reduces MDSeq’s cumulative ρ-solving cost to 0.022 seconds per question, compared with 0.061 seconds for SpecTr, and contributes to its lower overall verifier cost.
Response to Q2:
Following greedy block verification [1], we evaluate Algorithm 2 lazily: we store only the parameters, prefix probability masses, and remaining horizon of each distribution modification, without explicitly constructing all possible continuations. When a correction token leaves the original draft paths, the next round generates new drafts from the actual emitted prefix and scores them with the target model, obtaining the conditional distributions required along the new paths.
Unfinished modifications persist across rounds and are applied in chronological order. Each new modification is constructed from the effective target distribution after applying the existing modifications. The corresponding states are updated whenever a token is emitted, until their horizons expire. Distribution modification involves only probability-vector operations and does not require an additional model forward pass for each modification. All costs, including processing corrected prefixes, subsequent drafting and target scoring, distribution modification, and KV-cache updates, are included in the end-to-end timing used to compute WS.
[1] Sun et al. Block Verification Accelerates Speculative Decoding. ICLR 2025.