acceptodds
Under review as a conference paper at ICLR 2027

When Better Drafts Cost More Verification: Safety Boundaries for Multi-Token Drafting

Abstract

Speculative-decoding draft heads are trained to match the target model at each position. Yet a better local draft can make a whole response more expensive to verify: accepting more tokens moves where verification restarts, possibly to a costlier continuation. We characterize this effect for a fixed target path with a fixed proposal cap, full-prefix commitment and unit cost per verifier call. First, same-rank readouts can raise some target-match probabilities, lower none, yet raise verifier calls in proportion to the cap. Second, every such improvement is safe when the expected accepted length is at most one at every restart, the largest uniform threshold, or when prefix-survival probabilities are consistent across restarts; a sharp bound prices departures from consistency. Third, an exact backward recursion decides safety outside both regions, certifying 370 of 10,752 fitted probability fields against every coordinatewise increase in match probabilities, where the threshold alone certifies two. Finally, in a preregistered ten-seed comparison on two frozen backbones with matched anchors and evaluation budgets, whole-response training wins none of eight comparisons against a local objective covering every anchor, and the local objective reduces sampled verification calls in four. Draft-head changes should therefore be judged by whole-response verification work; our conditions and exact test show when a local improvement is guaranteed safe.

Primary area:
foundation or frontier models, including LLMs
Keywords:
speculative decoding, multi-token prediction, draft heads, verification cost, stochastic monotonicity, safety certificates

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_phsnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies whether improving draft-token agreement necessarily reduces whole-response verification work. Under a fixed target path, proposal cap, maximal-prefix commitment, and unit verification cost, it constructs same-rank draft heads whose coordinate-wise match-probability improvements increase verification calls by a factor proportional to the proposal cap. It then establishes a sharp expected-prefix safety threshold, a cross-restart nesting condition with a quantitative risk bound, and an exact backward recursion for detecting harmful coordinate-wise improvements. Experiments examine 10,752 fitted probability fields and compare all-anchor local training with whole-response training across ten seeds on two frozen backbones. The theoretical analysis provides a useful distinction between local agreement and global verification cost, while the empirical results, including negative findings, show that these guarantees do not automatically translate into better shared-parameter optimization or practical decoding performance.

Critical strengths
  1. This paper shows clear and informative theoretical insight. The same-rank construction isolates a genuine restart-position effect: verification becomes more expensive despite nondecreasing match probabilities, without increasing drafter capacity or per-call cost.
  2. The sharp threshold, nesting-based bound, and distinction between conditional-probability and survival-order safety provide a coherent characterization of when the failure is excluded. The fixed-cap result further identifies where the two safety notions can disagree under strictly interior probabilities.
Critical weaknesses
  1. The organization of this paper should be further improved. The presentation is substantially more extensive than necessary for the central contribution. The 84-page manuscript interleaves the main safety results with numerous historical experiments, solver failures, and optimizer-state investigations. Providing a more detailed table of contents for the appendix would improve readability. In addition, the "Limitations" section alone occupies an entire page of the main text. this discussion should be significantly condensed, while more substantial theoretical content, experimental analyses, and conclusions, currently relegated to the appendix, should be incorporated into the main body of the paper.
  2. The empirical bridge from field-level vulnerability to shared-model updates remains incomplete. None of the 3,072 fitted endpoint pairs satisfies coordinate-wise dominance, the successful path-specific constructions use different updates for different paths, and the joint attempts do not establish a common dominating, work-increasing update. Consequently, the experiments demonstrate scalar-loss/work disagreement and path-wise vulnerability, but not the central dominance-with-harm phenomenon for one shared update across a prompt collection.
  3. Applicability to native speculative decoding is not empirically established. Although the paper supplies extensions through conditional prefix-survival probabilities and fixed unequal costs, its fitted experiments remain restricted to cached greedy paths, linear readouts, at most four proposals, and responses of at most 64 tokens.
  4. The practical significance of the certificates remains limited. The exact test is informative once the complete future probability field is available, but its acquisition cost is excluded, the mean relaxed conditional risk is only about 0.70% of baseline calls, and risk-based head selection establishes no reduction in prospective verification work. These findings do not invalidate the theoretical contribution, but they leave the practitioner-facing use of the certificates beyond retrospective diagnosis insufficiently demonstrated.
Questions for authors

See critical weaknesses.

1 comment

Thanks for the comments.

W1. Organization. The revised main text asks one question. If some draft-match probabilities rise and none falls, when is the whole response guaranteed to cost no more verifier calls? Section 2 defines what one call accepts and where verification starts next. Section 3 gives the counterexample, the two sufficient conditions and the exact retrospective test. Section 4 separates the test on fitted heads from the training comparison. The revised PDF has 54 pages against 84 at submission. Optimizer histories, early comparisons and unsuccessful searches moved to the extended technical record in the supplement. The guide on p. 15 maps reader questions to the retained appendices, and the main text names the appendix that holds each proof. Theorem 4, the drafter classes and the sampling extension now sit in Section 3 (pp. 4–5). Limitations takes two paragraphs on p. 9.

W2. Can the same weights hurt several prompts? We replayed the first two consecutive local-training steps after warm-start on SmolLM3-3B and OLMo-2-1B, with three seeds each. We evaluated each step on the same 128 development prompts excluded from all fitting. Each of the twelve steps reduced both mean local loss and mean expected verifier calls. In 103 of 1,536 individual comparisons, local loss fell while expected calls rose. These reversals spanned 63 prompts. The largest increase was 0.00250 calls per output token from 0.65250. Every reversal had at least one match probability fall. These early steps on previously studied prompts establish a response-level mismatch. The stronger coordinatewise reversal remains unobserved (Appendix L, Table 15 on p. 54). The separate sweep of 816 candidate updates yielded nine batch reversals. None of their 216 responses met the stronger premise. Of all 26,112 candidate-update/response pairs, 70 met it, all on one short response, and all reduced work (Appendix J.2).

A zero result in Equation (4) guarantees safety for every shared-weight change that satisfies the premise on that response. A positive result supplies a change to the probability entries individually. Across the original 10,752 tables, 10,266 admit numerical constructions with one update per response (Appendix F). Those updates differ across responses. In the 3,072 actual pairs of final trained heads, neither head improves every entry in any pair. These endpoint comparisons do not test a shared training step, which is why we ran the update test above.

There is a distinct result for the weaker criterion that training actually uses. Even restricting the comparison to the 1,536 pairs where both objectives see all anchors, 539 rank oppositely by local loss and verifier calls (p. 7). This counts individual prompt–head pairs on Qwen3.5-0.8B. The matched training study on SmolLM3-3B and OLMo-2-1B instead compared averages over seeds and prompts. Whole-response training won none of its eight comparisons.

W3. Native applicability. Our fitted heads are parallel readouts on frozen backbone features. A drafter depending only on the text prefix is nested. EAGLE's feature chain can start from a different target state at each anchor. The idealized constructions in Appendix D.7–D.8 show how parallel heads, feature chains and sequential modules can violate nesting. They do not measure the incidence in released heads. Theorems 3 and 4 use joint prefix survival and permit dependence among draft tokens. Theorem 4 holds for every cap K ≥ 2 and every response length, so the limits of four proposals and 64 tokens apply only to the fitted experiments. Appendix D.9 treats lossless chain sampling with fresh randomness. Tree verification and serving latency require their own cost models.

W4. Size of the risk and cost of measuring it. On the original 10,752 fitted tables, mean worst extra work is 0.2345 calls against 33.2905 baseline calls. Dividing the worst case by its own baseline on each response gives 0.408% at the median, 2.597% at the 95th percentile and 8.479% at the maximum. The 0.70% ratio of the means measures a different quantity (Section 4.1, p. 5). Across seven additional backbones, 325 of 21,504 tables have zero worst-case risk. The largest increase is 0.063694 calls per token (Section 4.1, p. 6). Exact arithmetic classifies zero risk, and an independent enumeration of each row's choices checks the magnitudes (Appendix J.3).

Both all-anchor objectives compute the table on their training responses. An online decoder would also need the future output and unvisited anchors. Selecting among 24 heads by risk changed six of eight choices and gave no established prospective reduction (Appendix B). The demonstrated use is retrospective. Once a complete table is available, Equation (4) gives a response-specific upper bound in O(MK) arithmetic operations.

Reviewer_YgtROpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The authors argue that a better local draft can make a whole response more expensive to verify, because accepting more tokens moves where verification restarts, possibly to a costlier continuation. For a fixed target path, proposal cap, full-prefix commitment and unit call cost, they construct readouts that raise some target-match probabilities, lower none, yet raise verifier calls in proportion to the cap; prove two safety conditions with a sharp risk bound; and give an exact backward recursion that certifies 370 of 10,752 fitted fields. In a preregistered ten-seed comparison, whole-response training wins none of eight comparisons against a local objective.

Critical strengths

A rigorous and novel theoretical view of draft quality. The paper investigated a overlooked mechanism: improving per-position match probabilities can increase total verification work, because the restart anchor moves.

Critical weaknesses
  1. The paper does not clearly state what it is or what question it answers. The paper mixes several different questions without saying which one is central. The abstract and introduction list four loosely connected results, but never state one main claim that the paper sets out to prove.
  2. The main text relies on terms that are introduced with little or no intuition, such as "same-rank readouts", "probability fields", "joint-rank-two pre-unembedding factor stratum", "free-field risk", "stored gauge", "posterior controller", and "five distinct objects". Most definitions, proofs and experiments are deferred to an 84-page appendix, so the main paper cannot be read on its own.
  3. Narrow setting. The theory assumes a fixed greedy target path, independent proposal sampling, full-prefix commitment and unit call cost. By the paper's own result, autoregressive drafters such as EAGLE satisfy cross-restart nesting and are therefore safe, so the harmful effect mainly concerns Medusa-style independent heads. Tree drafting, rejection sampling at T > 0 and real latency are not covered.
  4. Small-scale experiments. Frozen 1B and 3B backbones, linear readouts, responses of at most 64 tokens, at most four proposals, and no wall-clock measurement.
Questions for authors
  1. What is the single main research question of the paper, and how does each section (Theorem 1, Theorems 2 and 3, the exact test, and the training comparison) answer it?

  2. Is the contribution a theoretical analysis, a training method, or a practical diagnostic tool? If the message is to judge draft heads by whole-response work, why does training on whole-response work never win?

  3. Which widely used drafters violate cross-restart nesting in practice? Can you measure the nesting defect and the risk for Medusa, Hydra, EAGLE and MTP heads on real models?

  4. Can you show a realistic training update (not a constructed or path-specific one) that improves local acceptance but measurably increases verification calls on held-out data?

  5. Do the conclusions hold under rejection sampling at T > 0, tree verification, longer responses, more proposals, and wall-clock latency in a serving engine?

1 comment

Thanks for the comments. W1–W4 correspond to Q1, Q2, Q3/Q5 and Q5 below.

Q1. What question does the paper answer? Under a fixed chain verifier, can making some match probabilities higher and none lower ever increase the expected calls to finish the same response? Figure 1 shows how an extra accepted token skips an especially useful starting position. Theorem 1 realizes the reversal with two heads of equal rank. Theorems 2 and 3 give sufficient conditions for safety. Equation (4) tests the individual drafter and response exactly. Theorem 4 gives the largest possible increase at each length across ordered prefix-survival tables. The training experiment asks whether minimizing calls helps when both objectives see every anchor.

Q2. Theory, trainer or tool? This is a theoretical analysis with an executable retrospective test. The revised PDF has 54 pages against 84 at submission. Its main text no longer uses “probability field”, “free-field risk”, “stored gauge”, “posterior controller” or “factor stratum”. Section 2 defines the probability table, the safe baseline and the two losses before the theorems use them. Whole-response training won none of eight matched comparisons. On SmolLM3-3B, local training used fewer sampled calls in all four settings. On OLMo-2-1B the four comparisons were inconclusive. The earlier advantage depended on the comparison design. Against a local loss that saw one sampled anchor it reduced work by 3.11% to 4.97%, and the gain disappeared when both objectives used the same anchors and vocabulary-row budget (Section 4.3). Optimizing one step of either loss also depends on optimizer history. In 72 direct comparisons, whole-response updates won on the update batch in all 24 cases with empty histories and none of the 48 after 32 updates (Appendix J.2).

Q3. Which drafters are exposed? Depending only on the text prefix suffices for nesting. EAGLE also uses a target feature at the anchor, so a token can receive different match probabilities when drafting starts elsewhere. Parallel heads such as Medusa and sequential modules such as Hydra can have this dependence too. A module used once to propose one token is always nested. Appendix D.7–D.8 constructs examples in all three multi-proposal classes using idealized one-hot anchor states. We have no incidence measurement for the released architectures you named.

For fitted parallel readouts on Qwen3.5-0.8B, exactly one of 10,752 tables is nested. Mean nesting-based upper bound is 0.6368 calls against 33.2905 baseline calls. On seven further frozen backbones the exact conditional test certifies 325 of 21,504 tables, with the largest worst case 0.063694 calls per token (Appendix J.3).

Q4. Can a real training step add work on prompts excluded from fitting? We replayed the first two consecutive local-training steps after warm-start on SmolLM3-3B and OLMo-2-1B, with three seeds each. We evaluated each step on the same 128 development prompts excluded from all fitting. Each of the twelve steps reduced both mean local loss and mean expected verifier calls. In 103 of 1,536 individual comparisons, local loss fell while expected calls rose. These reversals spanned 63 prompts. The largest increase was 0.00250 calls per output token from 0.65250. Every reversal had at least one match probability fall. These early steps on previously studied prompts establish a response-level mismatch. The stronger coordinatewise reversal remains unobserved (Appendix L, Table 15 on p. 54). On average the steps saved 0.00161–0.00362 calls per token. The nine earlier batch reversals used prompts already seen in warm-start training (Appendix J.2).

Q5. Sampling, caps, trees and latency. Conditional on a positive-probability output from standard lossless chain sampling with fresh randomness, a draft matches with probability min(1,Q/P) given that verification reached that position and emitted that token. Q and P are the draft and target masses there. Tokenwise improvements of min(Q,P) protect the call count in distribution if either drafter uses only the text prefix (Appendix D.9). Theorems 3 and 4 allow dependent proposals by using joint prefix-match probabilities. Theorem 4 covers every cap K ≥ 2 and every positive post-prefill length. Its sharp ratio approaches K only as length grows. The fitted experiments use at most 64 tokens and four proposals. The matched training comparison also covers eight further frozen backbones from 0.8B to 30B, and no adjusted interval there favors whole-response training (Section 4.3, Appendix J.1). Branching verifiers need a separate definition of one call. Wall-clock latency also depends on draft generation and hardware. Our construction isolates the restart effect even when every call costs exactly one.

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

This paper studies whether improving draft token predictions necessarily reduces verification cost in speculative decoding. The key observation is that accepting more draft tokens can shift verification to an unfavorable anchor, resulting in more verification steps. Theorem 1 constructs a counterexample, showing that increasing some token-match probabilities without decreasing any can actually increase the overall verification cost. The paper then establishes sufficient conditions under which such regressions cannot occur: either the expected accepted length is at most one at every anchor, or the cross-restart nesting condition holds. Theorem 3 further bounds the worst-case cost increase when this latter condition is violated. Empirically, the authors analyze 10,752 probability fields and compare local and whole-response training on two frozen language models.

Critical strengths

S1. The paper considers an interesting, novel problem.

  • To my knowledge, no prior work has considered the possibility that improving local draft predictions could increase the overall verification cost in speculative decoding.
Critical weaknesses

W1. The paper contains severe writing issues.

  • I had an extremely difficult time understanding this paper, and there are still parts that I could not fully understand. Below, I list only a few examples that make the paper unnecessarily difficult to read.
  • "Maximal-prefix commitment" (line 55) and "full-prefix commitment" (line 122) appear to refer to the same concept, but the paper uses different terminology.
  • “Local and whole-response training” (line 90), “backward recursion of this finite increasing chain“ (line 105), “safe baseline“ (line 158), “witness replay“ (line 228): These terms and expressions are introduced before being clearly defined or without sufficient explanation.
  • Lines 232–234 are particularly problematic: "free-field risk" → "reachable subset" → "stored gauge" → "rectangular risk" → "common-update risk" → "full row rank" → "exposed target columns" → "free-field equality".
  • “Ten training seeds give 80 heads: 24 historical heads and 56 new fits” (line 253): I don’t understand what the authors mean by “historical heads”.
  • The notation nn is used with different meanings in lines 95 and 144.
  • For these reasons, I suspect that the paper relies heavily on AI-assisted writing without sufficient human review. I am fully aware that using AI for paper writing is not itself a valid reason for rejection, and the authors explicitly acknowledge AI assistance in the AI Use Statement. However, the issues above suggest that the manuscript was not carefully checked by the authors.

W2. The experiments provide limited evidence for the practical relevance of the theoretical findings and fail to establish the importance of the problem in practice.

  • In my understanding, the authors conduct two main empirical analyses: (1) comparing local and whole-response training, and (2) examining the theoretical risks of the probability fields obtained from trained draft heads. In the first experiment, whole-response training does not outperform local training in any of the 8 comparisons. In the second, while most probability fields (10382/10752) exhibit positive risks, these risks are computed under hypothetical changes rather than actual training updates. If I understand correctly, these results do not demonstrate that this risk actually leads to performance degradation in practical speculative decoding, which may leave readers questioning focusing solely on local acceptance when training draft heads is a meaningful practical concern.
Questions for authors

See the weaknesses.

1 comment

Thanks for the comments. W1. Writing and author responsibility. Your examples identified where the submitted text made an elementary question hard to follow. We recorded five AI-assistance uses on the submission form. The revised statement on p. 10 explicitly includes drafting sections and developing proofs, alongside research ideation, implementation including the update-replay scripts, literature discovery and polishing. The authors take responsibility for the content. We address your concrete examples as follows. Unless a bullet names an appendix, the change is in the main text (pp. 1–9).

“Full-prefix commitment” has one definition on p. 2. Keep each accepted draft token and then emit the target’s next token.

Section 2 defines both training losses. The local loss rewards longer accepted prefixes at the starting positions. The whole-response loss counts expected verifier calls per output token.

The “backward recursion” starts from zero remaining calls at the end. Each earlier position costs one call plus the average remaining calls from its possible next positions.

A “safe” baseline is now defined before the theorem. Expected calls cannot rise for any change that improves some match probabilities and lowers none.

Section 3 now explains how to check the particular harmful change returned by Equation (4).

The paragraph at submitted lines 232–234 is replaced by the operational distinction in Section 3. Zero risk protects all qualifying changes to shared weights on that response. Positive risk permits a harmful change to individual table entries. One set of trained weights may be unable to make that change across several responses.

The 24 earlier heads came from the first three-seed study. Another 56 extend that study to ten seeds. All 80 were evaluated on the new prompts (p. 6).

Throughout Theorem 1 and its proof, n denotes the response length and T the number of periods in the example (Appendix C). Section 2 defines the proposal cap K and collects the table notation before the main derivations.

W2. Do the hypothetical changes occur in practice? Your reading is correct. The positive risks are worst cases over hypothetical changes, and no observed update in our data met the theorem’s premise and raised calls. For a given table we now distinguish the size of its worst-case change from an observed change to a trained model. Across the original 10,752 fitted Qwen3.5-0.8B tables, the worst additional calls relative to each table’s own baseline have median 0.408%, 95th percentile 2.597% and maximum 8.479%. On seven further frozen backbones, 325 of 21,504 fitted tables are safe against every change that raises some match probabilities and lowers none. Appendix J.3 gives every model's result. This includes all 3,072 tables on Qwen3.8-27B, where zero qualify.

We replayed the first two consecutive local-training steps after warm-start on SmolLM3-3B and OLMo-2-1B, with three seeds each. We evaluated each step on the same 128 development prompts excluded from all fitting. Each of the twelve steps reduced both mean local loss and mean expected verifier calls. In 103 of 1,536 individual comparisons, local loss fell while expected calls rose. These reversals spanned 63 prompts. The largest increase was 0.00250 calls per output token from 0.65250. Every reversal had at least one match probability fall. These early steps on previously studied prompts establish a response-level mismatch. The stronger coordinatewise reversal remains unobserved (Appendix L, Table 15 on p. 54).

In the separate candidate-update scan, 70 of 26,112 comparisons met the coordinatewise premise. All 70 repeated one three-token probe response, and each reduced expected work (Appendix J.2). Whole-response training won none of eight matched comparisons. The earlier advantage disappeared when both objectives used all anchors with matched budgets (Section 4.3).

Comments on the paper

1 comment

Thank you very much to all the reviewers.

Accepting one more draft token can skip the best place to start the next block. In Figure 1 the original drafter reaches a position where four tokens match and finishes in three target calls. Improving only the first match skips that position. The same seven tokens then take six calls. Theorem 4 gives the sharp worst-case increase at each response length and proposal cap under equal call costs. For a particular drafter and response, Equation (4) computes whether any upward change to its conditional match probabilities could add work.

What happened in actual training? We replayed the first two consecutive local-training steps on six readouts, spanning two backbones and three seeds. Each step reduced mean local loss and mean expected verifier calls on the same 128 previously studied development prompts excluded from fitting. In 103 of 1,536 individual comparisons, local loss fell while expected calls rose. These reversals spanned 63 prompts. The largest increase was 0.00250 calls per output token from 0.65250. At least one match probability fell in every reversal. The stronger reversal in the theorem remains unobserved. In a separate scan of 816 candidate updates, 70 of 26,112 response comparisons improved some probabilities and lowered none. All 70 concerned one short response, and every one saved calls (Appendices J.2 and L, pp. 51 and 54).

How large is the hypothetical risk? Among 10,752 fitted tables on Qwen3.5-0.8B, the maximum extra work relative to each table’s own baseline has a median of 0.408%, a 95th percentile of 2.597% and a maximum of 8.479%. On seven further frozen backbones the exact test certified 325 of 21,504 tables as safe under any qualifying change. Each remaining table permits an adverse change to its probabilities. The largest worst case was 0.063694 calls per output token (Appendix J.3). Direct training on verifier calls won none of eight matched comparisons.

What changed in the paper? The revised PDF has nine main pages and 54 pages overall, compared with 84 at submission. Section 2 defines the verifier, the probability table and the two losses. Section 3 covers the sharp bound, the conditions for safety and the stochastic-target extension. Appendices D.7–D.9 distinguish drafters that use the text prefix alone from feature chains and parallel or sequential heads that can depend on their starting point. These are architectural possibilities. Released-system incidence and serving latency remain open. The guide on p. 15 and READER_GUIDE.txt in the supplementary material locate the proofs, data and executable checks.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.