acceptodds
Under review as a conference paper at ICLR 2027

CurveK: Throughput-Curve Estimation for Batched Speculative Decoding

Abstract

Speculative decoding accelerates large language model inference by drafting multiple tokens and verifying them simultaneously, but its efficiency critically depends on selecting an appropriate draft length \(k\). This choice is particularly challenging in batched serving environments, where diverse requests share a common draft length but exhibit different acceptance patterns. Existing methods dynamically adjust \(k\) using arm-level rewards, draft-side statistics, or acceptance estimates. However, we theoretically show that these signals remain coarse: they do not directly represent how acceptance changes across draft positions in the current batch. This position-specific view defines a throughput curve over candidate draft lengths, whose maximum gives the draft length selected by our objective. Motivated by this insight, we formulate dynamic draft-length selection as estimating the batch throughput curve and choosing its peak. We propose CurveK, a lightweight and easy-to-implement method that estimates this curve from accepted-token depths already returned by the verifier. Importantly, CurveK requires neither additional training nor changes to the verification process. Experiments with 8B and 70B models in vLLM show throughput improvements over baselines across diverse workloads, including mixed-workload settings. Ablation studies validate the design of CurveK, and further analysis shows that its curve estimates consistently select high-throughput draft lengths.

Primary area:
foundation or frontier models, including LLMs
Keywords:
speculative decoding, large language models, efficient inference

Reviews

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

The paper proposes CurveK, an algorithm to adaptively choose the draft length in speculative decoding based on an estimate of the throughput at each draft length (where throughput is defined abstractively as the ratio of expected token count divided by a relative draft cost, i.e. the cost of generating draft tokens relative to the target model cost). This estimate is recomputed at every batch at inference. Since it's estimated from previous iterations, its computation is cheap. Compared against other adaptive baselines (OTF, TurboSpec, vanilla SD), CurevK achieves measured throughput speedups of between 3-11%.

Critical strengths
  • the method is easy to implement and (presumably) cheap
  • the gains seem to hold across datasets and over a variety of baselines
  • the paper is generally pretty well-written with only minor exceptions
Critical weaknesses
  • novelty is arguably somewhat limited. Baselines like OTF and TurboSpec also feature adaptive draft length based on online-estimates
  • there is a substantive gap between the formula used for the algorithm, and the actual throughput, stemming from taking the mean across within a sample/across samples. The authors acknowledge this (it's the big equation in the middle of page 29), but it remains an unresolved gap. In particular, proposition 3 seems to just assume concentration, without showing this is warranted empirically, and furthermore features bias and online-loss terms that are not discussed and could be large from what I'm seeing
  • a big amount of the gains over vanilla speculative decoding (although not all of it) disappears when picking "adaptively chosen, but then kept fixed throughput generation" draft lengths (table 8). This shows that a well-calibrated fixed draft length could achieve almost the same speedup
  • potential issue with the oracle evaluations, see "questions" below
Questions for authors
  • in the "oracle" experiments (section 6.4, appendix I) there's potentially an issue with how CurveK estimates are updated: from my reading, in these experiments, information from the full-length draft step is used to update the CurveK depth estimates for the next iteration, which would "leak" information from the full-length draft step (say, CurveK would've picked draft length=2 but the full-length step shows 5 tokens were accepted, then it seems that the CurveK depth estimates use 5 for their next update, instead of 2). Could the authors clarify if this is the case? If it is, it seems to me the experimental setup should be changed to be fairer (and CurveK should only use its own values)
  • not a question, but I feel like the experimental results could be a bit more extensive (not that many datasets), and presented a bit better: e.g. it's not clear at first what the red boxes in tables mean (they look like something "negative"); some tables are a bit hard to read, especially when only reading their captions; some of them could benefit from better formatting
3 comments

Thank you for the thoughtful review. We address your points in order and report the fairer oracle replay you asked for in Tab. R1.

W1\color{blue}{\textbf{W1}}: Novelty is arguably somewhat limited. Baselines like OTF and TurboSpec also feature adaptive draft length based on online estimates.

A: Thank you for the comment. OTF and TurboSpec also adapt kk online; the difference is what is estimated. Both fit one geometric acceptance rate to the whole batch. CurveK keeps one accepted depth per request and evaluates each candidate through 1B∑imin⁡(k,μi)\frac1B\sum_i\min(k,\mu_i), so differences between requests are kept until each candidate length is scored.

In Tab. 1, CurveK is 9.9% and 8.5% higher than TurboSpec and OTF on average across the six 8B settings. A controlled ablation links this to the aggregation choice: MeanDepth-K uses the same depth states, cost model, and selection rule and only averages before truncating, and CurveK is 6.8% higher across the same six settings (Tab. 3).

W2\color{blue}{\textbf{W2}}: There is a substantive gap between the formula used for the algorithm and the actual throughput, stemming from taking the mean within a sample / across samples (the big equation on page 29). Proposition 3 seems to just assume concentration, and features bias and online-loss terms that are not discussed and could be large.

A: Thank you for the careful reading. Prop. 3 is meant as a decomposition that identifies where selection loss can come from, under the concentration condition in App. D.1, with the Jensen gap and online mismatch kept explicit. We examine each term empirically and will add this discussion to Sec. 5.4.

  • Finite-sample term. Tab. 23 recomputes the estimated curve from subsets of the request states at B=64B=64. On GSM8K the maximum curve discrepancy falls from 0.214 to 0.142, 0.082, and 0.047 as the subset grows from 8 to 16, 32, and 48 requests, and across the three workloads the selection-score loss falls from 0.034–0.039 at 4 requests to 0.0002–0.001 at 48.
  • Jensen gap. The equation on p. 29 contains two gaps. Truncating each request before averaging removes the across-request gap; reversing the order (MeanDepth-K) lowers throughput, with CurveK 6.8% higher on average. The remaining within-request gap equals 12(E∣X−k∣−∣m−k∣)\tfrac12(\mathbb E|X-k|-|m-k|) with m=EXm=\mathbb EX, which is zero when a request's depth stays on one side of kk and at most half its standard deviation. A per-position history, which avoids truncating a scalar mean, gives lower throughput in practice: CurveK is 9.6–16.0% higher across the six settings (Tab. 3).
  • Online mismatch. Under deployed feedback, the next-step prediction at the executed length has a mean absolute error of 0.312–0.404 tokens on four workloads (Fig. 5, Tab. 13), throughput is stable around the default update rate (Tab. 4), and in the censored replay of Tab. R1 below CurveK retains 93.9–96.7% of the oracle-best score.

The decomposition names the error sources; these measurements, together with the end-to-end throughput tables, evaluate their effect on the selected lengths.

W3\color{blue}{\textbf{W3}}: A big amount of the gains over vanilla speculative decoding disappears when picking "adaptively chosen, but then kept fixed" draft lengths (Table 8). This shows that a well-calibrated fixed draft length could achieve almost the same speedup.

A: Thank you for this point. A fixed length chosen for each setting is indeed a strong reference, and CurveK reaches about the same throughput without that calibration. The per-setting reference requires a seven-length sweep for each workload, batch size, and decoding mode, and is chosen after seeing the results. We compare against both this reference and the best single fixed length across settings:

Reference (21 settings per decoding mode, Tabs. 7–8)GreedySampling
Best fixed length per setting, after a 7-length sweepCurveK +0.41%, ahead in 14/21CurveK −0.76%, ahead in 8/21
Best single fixed length across settingsCurveK +2.37%, ahead in 17/21CurveK +1.97%, ahead in 15/21

The percentages compare mean throughput across the 21 settings.

The distinction matters because the best fixed length moves with the setting. On GSM8K under greedy decoding it is k=4k=4 at B=8B=8 and k=2k=2 at B=64B=64, and using either at the other batch size loses 9–10%. The best single fixed length (k=3k=3 for greedy, k=2k=2 for sampling) loses up to 6.9% and 9.3% in individual settings (App. A.2). A table of fixed lengths indexed by batch size would also need to know the workload, which a server handling mixed traffic does not know in advance. On the mixed-workload trace (Tab. 2), where request types change during serving, CurveK is ahead of the strongest dynamic baseline by 4.7%, 5.3%, and 4.9% at B=32B=32, 6464, and 128128, and within 0.5% of it at B=16B=16.

W4/Q1\color{blue}{\textbf{W4/Q1}}: In the "oracle" experiments there's potentially an issue with how CurveK estimates are updated: information from the full-length draft step is used to update the depth estimates for the next iteration, which would "leak" information (say, CurveK would've picked draft length=2 but the full-length step shows 5 tokens were accepted, then the depth estimates use 5 for their next update, instead of 2). Could the authors clarify if this is the case? If it is, the experimental setup should be changed to be fairer.

A: Thank you for the careful reading; your example describes the diagnostic accurately. It updates with 5, whereas a deployed CurveK that executed length 2 and saw both tokens accepted would update with 3, since a fully accepted draft of length k<Kk < K is recorded as k+1k+1. The end-to-end throughput tables are unaffected: those runs execute CurveK's chosen length and update only from the feedback it reveals.

To make the oracle evaluation fair, as you suggest, we reran it with a second controller that chooses its own length ata_t and updates only from its own values, min⁡(at,zt,i(K))\min(a_t, z_{t,i}^{(K)}). Both controllers are scored on the same full-depth curve.

Tab. R1. Retained oracle-best score in the paired full- vs. censored-feedback replay.

WorkloadBBFull feedbackCensored feedbackGap
GSM8K1696.5%96.0%−0.5 pp
GSM8K6497.1%96.7%−0.4 pp
HumanEval1695.8%95.1%−0.7 pp
HumanEval6494.2%93.9%−0.3 pp
SpecBench-Mix1696.3%95.7%−0.6 pp
SpecBench-Mix6497.4%96.5%−0.9 pp
Mean—96.2%95.6%−0.6 pp

Using only its own feedback, CurveK retains 93.9–96.7% of the oracle-best score, 0.3–0.9 points below the full-feedback controller. Both columns come from this new run. We will add Tab. R1 to App. I and describe both feedback protocols in Sec. 6.4.

Q2\color{blue}{\textbf{Q2}}: Not a question, but the experimental results could be a bit more extensive (not that many datasets), and presented a bit better: it's not clear at first what the red boxes in tables mean (they look like something "negative"); some tables are hard to read, especially from their captions alone.

A: Thank you for both suggestions.

On presentation: the peach cells mark the second-highest mean in a row, or the strongest alternative within each ablation group in Tab. 3, and the red Δ\Delta values in Tabs. 7–8 mark throughput below the per-setting best fixed length. We agree the shading can read as negative. In the revision we will replace it with bold for the best and underline for the second-best, add a legend to each table, and state the model, batch size, decoding mode, and comparison reference in every caption.

On coverage: the single-benchmark tables use GSM8K (math), HumanEval (code), AlpacaEval (instructions), and SpecBench-Mix, which combines eight task groups (coding, math, QA, dialogue, RAG, summarization, translation, writing). LMSYS-Chat-1M dialogue is reported in App. A.8, and the mixed serving trace adds CNN/DailyMail summarization and Natural Questions/DPR retrieval QA. These are evaluated on 8B and 70B targets, A100 and H20, EAGLE-3 and Medusa drafters, greedy and sampling decoding, B=4B=4–128128, and K=3K=3–1212. We will summarize this coverage at the start of Sec. 6 so that it is visible without the appendix.

Reviewer_KcUUOpenReview ↗

Acknowledging author's response

Thank you for your detailed response, which strengthens the paper. I will maintain my positive rating and recommend acceptance of the paper.

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

This paper studies dynamic draft-length selection for batched speculative decoding. CurveK maintains request-level accepted-depth statistics from verifier feedback, uses them to estimate the expected accepted-token count for each candidate draft length, and selects the peak of a cost-normalized throughput curve. The method requires no additional training or verifier modification. Experiments across multiple models, workloads, batch sizes, and hardware platforms show consistent throughput improvements over several adaptive baselines.

Critical strengths
  1. The empirical evaluation is extensive and generally convincing. CurveK is evaluated across multiple model scales, workloads, batch sizes, decoding settings, and hardware platforms, with consistent gains over several adaptive speculative-decoding baselines.

  2. The method is lightweight and practically appealing. It reuses verifier feedback, requires no additional training or model modification, and introduces negligible decision overhead. The ablations and oracle analyses also provide useful evidence that the proposed controller is making effective draft-length decisions.

Critical weaknesses
  1. The core idea—using acceptance information together with a cost model to adapt draft length—is well explored in prior speculative-decoding work. CurveK’s main distinction appears to be preserving request-level accepted-depth states and aggregating them in a candidate-specific manner. This is useful, but relatively simple, and some of the theoretical results (e.g., scalar summaries being insufficient) mainly formalize fairly intuitive observations.

  2. The empirical comparison could be stronger relative to closely related adaptive systems. In particular, the paper includes an AdaSpec-style confidence estimator only inside CurveK’s own selection framework, rather than a full system-level comparison with AdaSpec. In addition, the dynamic-serving evaluation mainly studies workload-composition changes, while arrival-rate variation, queueing, and SLO behavior are not directly evaluated. The simplified throughput objective also assumes a relatively simple cost model, whose faithfulness to end-to-end serving latency is only indirectly validated.

Questions for authors
  1. The paper compares CurveK with an AdaSpec-style confidence estimator while keeping CurveK’s own cost model and draft-length selection rule. Could the authors clarify why a full end-to-end comparison with AdaSpec is not included? Such a comparison would help distinguish the benefit of CurveK’s accepted-depth estimator from that of the overall controller design.

  2. CurveK selects the draft length using the surrogate throughput objective R(k) =1+L(k) / (1+k c_r). Could the authors provide more evidence that this surrogate accurately reflects the measured end-to-end throughput across different batch sizes and context lengths? In particular, it would be useful to compare the estimated ranking of candidate draft lengths with their actually measured throughput.

5 comments

Thank you for the constructive review. Below we address the contribution, the AdaSpec comparison, and the serving scope, and report the measured comparison you asked for in Q2 (Tab. R2).

W1\color{blue}{\textbf{W1}}: The core idea—using acceptance information together with a cost model to adapt draft length—is well explored in prior work. CurveK's main distinction appears to be preserving request-level accepted-depth states, which is useful but relatively simple, and some theoretical results mainly formalize intuitive observations.

A: Thank you for the comment. CurveK's contribution is candidate-specific aggregation of request-level verifier feedback. For a shared draft length the relevant quantity is L(k)=1B∑iE[min⁡(k,Zi)]L(k)=\frac1B\sum_i\mathbb E[\min(k,Z_i)], and estimating it requires keeping how accepted depths vary across requests until each candidate length is scored. TurboSpec and OTF fit one geometric rate to the batch; BanditSpec and Nightjar update only the length that was played. CurveK keeps one smoothed depth per request, so each request informs every candidate length without extra model calls.

The mechanism is simple, and the ablations show that its details matter for measured throughput:

  • Order of truncation and averaging. MeanDepth-K uses the same per-request states, cost model, and selection rule, and only averages before truncating. CurveK is 6.8% higher on average across six settings (Tab. 3).
  • Continuation update. Recording k+1k+1 after a fully accepted draft of length k<Kk < K gives 9.7% over the variant without it (Tab. 9).
  • Richer or parametric alternatives. CurveK is 12.4% higher than per-position histories and 15.8% higher than confidence products across six settings (Tab. 3), and 11.3% higher than per-request geometric fits on the three LLaMA workloads (Tab. 10).

On the theory, Prop. 2 quantifies what scalar summaries can lose: in the two equal-mixture constructions of App. B.2 at K=7K=7 and cr=0.08c_r=0.08, any rule using only p1p_1 loses at least 10.0% relative to the oracle, and any rule using only L(K)L(K) loses at least 9.9%. The ablations above then test the effect in serving.

W2(a)/Q1\color{blue}{\textbf{W2(a)/Q1}}: The paper compares CurveK with an AdaSpec-style confidence estimator while keeping CurveK's own cost model and draft-length selection rule. Could the authors clarify why a full end-to-end comparison with AdaSpec is not included?

A: Thank you for asking. We chose a controlled comparison to isolate how the acceptance estimator affects throughput: with the cost model and selection rule held fixed, CurveK's accepted-depth estimator is higher than confidence products in AdaSpec's form in all six settings, by 15.8% on average (Tab. 3, App. A.5).

A full-system comparison would also change when decisions are made. AdaSpec decides during drafting from the current step's confidences and couples that decision to SLO-aware scheduling, which requires changes to the drafting loop; CurveK chooses one shared length before drafting from earlier verifier feedback. We see the two as complementary, since in-draft stopping could run on top of a shared length chosen before drafting. We will label the variant as an estimator ablation in Sec. 6.3 and App. A.5 to make its scope clear.

W2(b)\color{blue}{\textbf{W2(b)}}: The dynamic-serving evaluation mainly studies workload-composition changes, while arrival-rate variation, queueing, and SLO behavior are not directly evaluated.

A: As you note, our serving experiments are controlled-concurrency throughput measurements: the batch-size experiments cover B=4B=4–128128 in separate runs, and the eight-phase trace changes request composition at fixed concurrency (Tab. 2, Fig. 7). We will state this scope in the paper and list arrival-rate, queueing, and SLO evaluation as future work.

On how the design relates to variable load: CurveK keeps one state per active request, removes it when the request finishes, and recomputes its curve from the active requests at every step. Its estimate therefore follows the active set as requests arrive and leave, without a batch-level history to reset.

W2(c)/Q2\color{blue}{\textbf{W2(c)/Q2}}: Could the authors provide more evidence that the surrogate R(k)R(k) accurately reflects measured end-to-end throughput across batch sizes and context lengths? In particular, compare the estimated ranking of candidate lengths with their actually measured throughput.

A: We appreciate the suggestion and ran this comparison. We timed drafting and verification with CUDA events in the same vLLM path for every k∈{0,…,7}k\in\lbrace 0,\ldots,7\rbrace at B=8B=8, 3232, and 8080, on short-context GSM8K and long-context CNN/DailyMail, plus LMSYS dialogue at B=8B=8, and measured end-to-end throughput at every length. Both cost models are applied to the same full-depth acceptance curve.

Tab. R2. Measured step cost by draft length, and the fixed length each cost model selects.

SettingStep cost at k=2/4/7k=2/4/7Implied crc_rBest kk: surrogate R(k)R(k)Best kk: R(k)R(k) with measured costBest kk: measured throughput
Profiled model1.16 / 1.32 / 1.560.08———
B=8B=8, short1.34 / 1.44 / 1.890.13444
B=8B=8, long1.44 / 1.53 / 1.970.14344
B=8B=8, LMSYS dialogue1.35 / 1.45 / 1.870.12343
B=32B=32, short1.52 / 1.98 / 2.300.19433
B=32B=32, long1.63 / 2.02 / 2.300.19333
B=80B=80, short1.72 / 2.70 / 3.620.37422
B=80B=80, long2.09 / 2.86 / 3.590.37302

Step costs are normalized by the verification time at k=0k=0; the implied crc_r is (cost(7)−1)/7(\mathrm{cost}(7)-1)/7.

At B=8B=8 and B=32B=32, for both short and long contexts, the surrogate selects a length within one of the measured best. Batch size matters more than context length: the implied ratio is similar for short and long contexts at each batch size and grows from 0.13 at B=8B=8 to 0.37 at B=80B=80. At B=80B=80 the surrogate ranks k=3k=3 or 44 above the measured best k=2k=2, because 1+kcr1+kc_r charges for drafting while verification time also grows with kk (the target verifies B(k+1)B(k+1) tokens; 17.1 ms at k=0k=0 versus 53.0 ms at k=7k=7).

Using measured step costs in R(k)R(k) raises agreement with the measured-best fixed length from 3 of 7 to 5 of 7 settings and reduces the average throughput loss of the static choice from 4.0% to 0.8%. Tab. R2 evaluates static choices on a fixed acceptance curve; during serving CurveK re-estimates the acceptance curve at every step, and the paper's tables report the resulting end-to-end throughput. At the large batch sizes where the surrogate is least accurate, CurveK's measured throughput stays between −2.3% and +0.6% of the per-setting best fixed length (B=64B=64 and 8080, Tab. 7). The implementation accepts a measured per-length cost table in place of 1+kcr1+kc_r. We will add Tab. R2 to App. G.

Thank you for your responses, which have addressed most of my concerns. I would still encourage the authors to include evaluations under varying request arrival rates and SLO constraints, particularly the latter, as SLO-aware performance is crucial in practical LLM serving systems.

Overall, I will maintain my positive rating.

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

CurveK selects a shared draft length for batched speculative decoding. It maintains a smoothed accepted-depth estimate for each request, adds a continuation heuristic for fully accepted drafts, and estimates the benefit of each candidate length by clipping request-level depths before averaging. A profiled draft-to-verification cost ratio converts these estimates into a throughput score. The paper analyzes the score's shape and estimation errors, then evaluates the controller across model sizes, hardware platforms, decoding modes, and workloads. On the mixed serving trace, measured throughput improves by ~5% over the strongest competing dynamic controller at batch sizes 32-128, while batch size 16 is essentially tied. Gains over the best single fixed length across settings are ~2%. Full-depth diagnostic traces separately assess decisions under the modeled cost function.

Critical strengths
  1. The controller addresses a useful serving decision with a compact mechanism. It reuses verifier feedback, preserves request-level information, and leaves the acceptance test unchanged. Periodic probes allow recovery after selecting zero speculation. The measured decision overhead is small in the tested setting.
  2. The evaluation includes multiple model sizes, A100 and H20 hardware, greedy and sampling decoding, mixed workloads, and an extension beyond EAGLE. Controllers share the serving path, and the fixed-length sweep provides a stronger reference than a single default. The results include exceptions and small gains rather than supporting an unqualified win claim.
  3. The ablations separate throughput-based selection, confidence estimates, batch-mean aggregation, history-based estimates, and the continuation update (Tbls. 3 and 9). The error decomposition also explains why clipping each request before aggregation avoids an additional Jensen gap. These results provide useful evidence for the chosen design, even though they do not establish calibrated estimation of the full acceptance curve.
Critical weaknesses
  1. The full-depth oracle protocol leaves an important feedback ambiguity. Appendix I executes the maximum draft length regardless of the recommendation, then forms later recommendations from preceding feedback. It does not state whether that feedback is censored back to what normal execution would reveal. The reported 94.7%-98.1% retained oracle score therefore needs this qualification before it can support deployed decision accuracy. These scores also use the profiled cost formula rather than a measured wall-clock oracle (Fig. 6, Tbl. 21).
  2. The simplified cost model is not directly validated against the variation of verification time with draft length inside a serving configuration. Fig. 10 perturbs its cost ratio while retaining the same modeled objective, which answers a different question. The measured throughput tables support practical usefulness, but the ~2% average gain over the best globally fixed choice and the small-batch dialogue mismatch make the residual modeling error relevant. A limited measured cost-versus-length comparison would help establish when the score ranks candidates correctly.
  3. The close dynamic-baseline comparisons depend on controller adaptations and tuning that are not fully validated. Appendix H gives concrete implementations, but, for example, replaces TurboSpec's described forward-time regression with runtime per-arm timing and extrapolation. The chosen parameters are listed without a clear tuning search or held-out selection workload. This leaves uncertainty about how much of the modest advantage comes from the estimator rather than the ports or tuning.
  4. No reproduction code was supplied or linked in the manuscript. The pseudocode and configuration descriptions do not make the serving-engine changes, controller ports, and timing experiments reproducible.
Questions for authors
  1. During the full-depth oracle runs, are estimator updates restricted to the feedback that the recorded recommendation would have exposed? Please specify the update rule and, if full-depth feedback is used, report a small replay with feedback censored to the recommended length.
  2. On representative batch and context settings, how well does the profiled cost formula preserve the ordering obtained from measured draft and verification times across candidate lengths? Does using those measured costs explain the dialogue case where the best fixed length is 5 but CurveK usually selects at most 2?
  3. What tuning data, search spaces, and selection budgets were used for each controller, and what checks establish that the runtime ports preserve the intended baseline behavior? The distinction between the original timing models and the implemented per-arm estimates is particularly relevant.
5 comments

Thank you for the detailed and constructive review. We ran both experiments you suggested: a replay with feedback censored to the recommended length (Tab. R1) and a measured cost-versus-length sweep (Tab. R2). The tuning, port, and code details follow.

W1/Q1\color{blue}{\textbf{W1/Q1}}: During the full-depth oracle runs, are estimator updates restricted to the feedback that the recorded recommendation would have exposed? Please specify the update rule and, if full-depth feedback is used, report a small replay with feedback censored to the recommended length.

A: Thank you for raising this. The Appendix I diagnostic updates from full-depth feedback: each recommendation is formed before its own step is verified, and the diagnostic then executes K=7K=7. The end-to-end throughput tables are unaffected, since those runs execute CurveK's chosen length and update only from the feedback it reveals.

Following your suggestion, we reran the diagnostic with a second controller that chooses its own length ata_t and updates only from min⁡(at,zt,i(K))\min(a_t, z_{t,i}^{(K)}), using the rule below. Both controllers are scored on the same full-depth curve under the profiled cost model.

Tab. R1. Retained oracle-best score in the paired full- vs. censored-feedback replay.

WorkloadBBFull feedbackCensored feedbackGap
GSM8K1696.5%96.0%−0.5 pp
GSM8K6497.1%96.7%−0.4 pp
HumanEval1695.8%95.1%−0.7 pp
HumanEval6494.2%93.9%−0.3 pp
SpecBench-Mix1696.3%95.7%−0.6 pp
SpecBench-Mix6497.4%96.5%−0.9 pp
Mean—96.2%95.6%−0.6 pp

With feedback restricted to its chosen length, CurveK retains 93.9–96.7% of the oracle-best score, 0.3–0.9 points below the full-feedback controller. Both columns come from this new run. The retained score uses the profiled cost; Tab. R2 below compares it with measured step costs.

The update rule is as follows. For an executed length at>0a_t > 0 and observed depth yt,i=min⁡(at,Zt,i)y_{t,i}=\min(a_t,Z_{t,i}),

a_t+1, & a_t < K \text{ and } y_{t,i}=a_t,\cr y_{t,i}, & \text{otherwise}, \end{cases} \qquad \mu_i\leftarrow(1-\beta)\mu_i+\beta\widetilde y_{t,i}.$$ No update is made when $a_t=0$; after 10 consecutive zero recommendations the controller drafts one token to refresh feedback (App. E). Under the continuation rule, a fully accepted short draft pulls the depth state toward $a_t+1$, so the controller can return to longer drafts. We will add Tab. R1 to App. I.

W2/Q2\color{blue}{\textbf{W2/Q2}}: On representative batch and context settings, how well does the profiled cost formula preserve the ordering obtained from measured draft and verification times across candidate lengths? Does using those measured costs explain the dialogue case where the best fixed length is 5 but CurveK usually selects at most 2?

A: Thank you for the suggestion. We timed drafting and verification with CUDA events in the same vLLM path for every k∈{0,…,7}k\in\lbrace 0,\ldots,7\rbrace at B=8B=8, 3232, and 8080, on short-context GSM8K and long-context CNN/DailyMail, plus LMSYS dialogue at B=8B=8. Tab. R2 compares the fixed length selected by each cost model, applied to the same full-depth acceptance curve, with the length that gives the highest measured throughput.

Tab. R2. Measured step cost by draft length, and the fixed length each cost model selects.

SettingStep cost at k=2/4/7k=2/4/7Implied crc_rBest kk: profiled costBest kk: measured costBest kk: measured throughput
Profiled model1.16 / 1.32 / 1.560.08———
B=8B=8, short1.34 / 1.44 / 1.890.13444
B=8B=8, long1.44 / 1.53 / 1.970.14344
B=8B=8, LMSYS dialogue1.35 / 1.45 / 1.870.12343
B=32B=32, short1.52 / 1.98 / 2.300.19433
B=32B=32, long1.63 / 2.02 / 2.300.19333
B=80B=80, short1.72 / 2.70 / 3.620.37422
B=80B=80, long2.09 / 2.86 / 3.590.37302

Step costs are sums of median drafting and verification times on full-batch decode steps, normalized by the verification time at k=0k=0; the implied crc_r is (cost(7)−1)/7(\mathrm{cost}(7)-1)/7.

At B=8B=8 and B=32B=32 the profiled formula selects a length within one of the measured best. It understates cost growth at B=80B=80, because verification time also grows with kk (the target verifies B(k+1)B(k+1) tokens): there verification takes 17.1 ms at k=0k=0 and 53.0 ms at k=7k=7, while drafting at k=7k=7 takes 9.0 ms. Substituting measured costs selects the measured-best fixed length in 5 of 7 settings, versus 3 of 7 for the profiled formula, and reduces the average throughput loss of the static choice from 4.0% to 0.8%. The serving tables in the paper report measured end-to-end throughput: at B=64B=64 and 8080, where the formula is least accurate, CurveK stays between −2.3% and +0.6% of the per-setting best fixed length (Tab. 7). The implementation accepts a measured per-length cost table in place of 1+kcr1+kc_r. We will add Tab. R2 to App. G.

On the dialogue case, the cost model is not the cause. Applied to the same acceptance curve, the profiled cost selects k=3k=3 and the measured cost selects k=4k=4 (the measured cost is higher overall but nearly flat between k=2k=2 and k=4k=4, 1.35 versus 1.45). Neither selects k≤2k\le2, so CurveK's short choices do not come from the cost term. They come from the acceptance side: the k=5k=5 in Tab. 24 is the best length when one length is held for the whole run, whereas CurveK reselects at every step and chooses short drafts on steps where its request-level estimates predict that extra draft tokens would not repay their cost (Sec. 5.2). The k≤2k\le2 share counts these decisions and does not measure a throughput loss. The timing sweep runs on a 96-prompt subset of this workload rather than the full run behind Tab. 24; on it, throughput peaks at k=3k=3 with k=4k=4 within 0.6%.

W3/Q3\color{blue}{\textbf{W3/Q3}}: What tuning data, search spaces, and selection budgets were used for each controller, and what checks establish that the runtime ports preserve the intended baseline behavior? The distinction between the original timing models and the implemented per-arm estimates is particularly relevant.

A: Thank you for this question.

Tuning. Each baseline was tuned on the mixed-workload serving trace by measured end-to-end throughput, and the selected configuration was held fixed across all single-benchmark evaluations. We tried the exploration coefficient c∈{0.5,1.0,2.0}c\in\lbrace 0.5,1.0,2.0\rbrace for BanditSpec, the acceptance window {50,100,200,400}\lbrace 50,100,200,400\rbrace steps for TurboSpec, and h∈{5,6,7}h\in\lbrace 5,6,7\rbrace for OTF; Nightjar uses the block and bin schedule of App. H.4. CurveK's β\beta is tunable too: the 8B results use β=0.5\beta=0.5 with the profiled cr=0.08c_r=0.08, and in Tab. 4 β=0.3\beta=0.3 or 0.70.7 is 1.4–3.6% higher in three of the six settings.

Timing models. In the reported results, the timing term of every baseline is the profiled cost 1+kcr1+kc_r shared by all controllers, not a per-arm runtime estimate, so the controllers differ only in how they estimate acceptance. TurboSpec keeps its windowed estimate of α\alpha and uses 1+kcr1+kc_r for Tbatch(k)T_{\mathrm{batch}}(k); OTF keeps its estimate of βOTF\beta_{\mathrm{OTF}} and uses 1+γcr1+\gamma c_r for γaq+bp(γ)\gamma a_q+b_p(\gamma); BanditSpec's reward and Nightjar's loss come from the realized batch score under the same cost. We will update App. H to state this.

Checks on the ports. To confirm that each port runs as its decision rule specifies, we verified that the requested controller and its parameters are the ones actually loaded, that its state is cleared between runs, that the scheduler drafts exactly the length the controller returns, and that generated tokens are counted independently of the controller.

Estimator versus ports and tuning. MeanDepth-K runs in the same code path as CurveK with the same cost and selection rule and differs only in the order of truncation and averaging; CurveK is 6.8% higher on average across six settings (Tab. 3).

W4\color{blue}{\textbf{W4}}: No reproduction code was supplied or linked in the manuscript.

A: Thank you for raising this. To make the implementation concrete, we give its core below. CurveK is lightweight to integrate: a short routine selects the draft length, and three call sites connect it to the vLLM V1 scheduler. The scheduler passes the selected length to the drafter, and verification is unchanged.

Core implementation

Selection, called once per decode step:

def select_k(mu, K, c_r, cost_table=None):
    # mu: smoothed accepted depths, one per active request
    best_k, best_score = 0, 1.0  # k = 0 is standard decoding, R(0) = 1
    for k in range(1, K + 1):
        L_k = float(np.mean(np.minimum(k, mu)))  # truncate each request, then average
        cost = cost_table[k] if cost_table is not None else 1.0 + k * c_r
        score = (1.0 + L_k) / cost
        if score > best_score:
            best_k, best_score = k, score
    return best_k

Call sites in vllm/v1/core/sched/scheduler.py:

# schedule(): before drafting
k = self.controller.next_k(list(num_scheduled_tokens), default_k=self.num_spec_tokens)
spec_decode_k = 0 if k is None else k  # 0 skips the drafter on this step

# update_from_output(): after verification, for each request that had a draft
accepted_depths[req_id] = max(0, len(generated_token_ids) - 1)
...
self.controller.update(accepted_depths, k_at_step=self._prev_spec_decode_k)
self._prev_spec_decode_k = scheduler_output.spec_decode_k

# _free_request(): when a request finishes
self.controller.evict((request_id,))

update applies the rule given under W1. next_k calls select_k and, after 10 consecutive zero selections, returns 1 to refresh feedback. Each baseline port implements the same next_k / update / evict interface, so all controllers are driven by these call sites. The timing experiments record CUDA events around the draft and verify calls.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.