- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proposes SDPS, a queue-aware combinatorial bandit scheduler for cloud-edge speculative decoding, combining UCB-based verification-yield estimation, queue-aware prioritization, and EDF latency protection. The authors derive utility-loss, backlog, and latency bounds and validate the approach using a six-edge-node LLM testbed simulations.
Critical strengths
-The paper addresses centralized verification bottlenecks in multi-user cloud-edge speculative decoding.
-The algorithm combines UCB learning, queue-aware scheduling, and EDF latency protection. The paper establishes formal utility-loss, backlog, and latency bounds under stated assumptions.
-The work evaluates the algorithm on LLM hardware demonstrating low SLO violations and modest yield improvements.
Critical weaknesses
-Weak theoretical guarantees: The derived regret bounds rely on a restricted statewise comparator and strong queue-stability assumptions, limiting their practical significance.
-Marginal performance gains: SDPS achieves nearly identical goodput to conventional EDF while exhibiting worse tail latency.
Questions for authors
1-How can the stationary conditional-unbiasedness assumption be justified in realistic LLM serving workloads? Can the authors establish regret or utility guarantees under context-dependent or nonstationary reward distributions, rather than relying on a stationary model that excludes their adaptation experiment?
2-Why should SDPS be preferred over significantly simpler EDF scheduling when its primary throughput metric shows no meaningful improvement and its tail latency is worse? Can the authors provide statistically robust paired comparisons, with substantially more than three independent runs?
5 comments
This also identifies what stronger guarantees would require. A sublinear statewise score-loss bound at fixed V follows if Σₜ kₜηₜ = o(H); bounded rewards alone do not imply this under arbitrary drift. For context-dependent rewards, one would need a specified predictor class, controlled prediction error, and sufficient observation coverage. For time-varying rewards, one could combine a bounded variation or change budget with a windowed/restarted estimator and bound estimation error plus drift bias. A utility/backlog extension would additionally need a load condition for the time-varying reference and would carry the resulting selection-error term through the drift argument. These extensions provide a concrete agenda for subsequent analysis, building on the mismatch-sensitive score bound proved here; the exposure-delay argument remains independent of reward stationarity under its original timing and exposure conditions.
Manuscript changes: Section 5 clarifies the modeling role of the assumption; Appendix D.1 explains what it excludes; Appendix D.5 gives the mismatch proposition and proof; Appendix F.7 reports predictability diagnostics; Appendix F.2 and Table 7 report the real task-composition switch.
Q2 Why choose SDPS over EDF and how reliable are the gains
Thank you for requesting paired evidence of a practical advantage. SDPS can turn available deadline slack into additional on-time token output by learning which exposed heads use scarce verification capacity more productively. EDF prioritizes urgency; SDPS preserves strict critical priority while also using learned yield, queue occupancy, and waiting time to rank ordinary heads. The expanded mixed-workload experiment tests this advantage under the same exposure deadline. The original single-prompt setting, where goodput is effectively tied and EDF has lower P99, is a case in which the observed benefit is limited; we do not use that case alone to justify SDPS.
In five independent paired repetitions of the seven-node mixed workload with a 12 s SLO, SDPS increases SLO goodput from 12.096 to 12.670 tok/s (+4.75%) and accepted-draft throughput from 8.564 to 9.137 tok/s (+6.70%). It accepts 344.2 additional draft tokens per 600 s window. Both gains are positive in all five repetitions. The paired 95% Student-t intervals for the absolute improvements are [0.283, 0.865] tok/s for goodput and [0.282, 0.865] tok/s for accepted throughput. Both intervals lie above zero, supporting a positive improvement under this paired protocol. The three tight-SLO repetitions independently show gains of 4.28% in goodput and 5.96% in accepted-draft throughput; protocol details are in Appendix E.1.
The absolute rate should be read together with accumulated output. An additional 344.2 accepted draft tokens over 600 s corresponds to about 0.574 tok/s. The small-looking rate difference is therefore a persistent output increment over the measurement window, not merely a change in an internal score. The 6.70% relative accepted-token gain is unchanged by division by the common 600 s denominator, as is the significance of the paired comparison; we do not use the long window to explain away a modest percentage gain. The distinct 4.75% goodput gain measures on-time committed tokens, including correction/bonus tokens.The mechanism is consistent with more productive selections: accepted draft tokens per round increase from 4.844 to 5.168, with full-batch rates above 99.8% for both policies. The independent ablation also shows lower mean output when the quality term is removed, while distinguishing that effect from the UCB bonus: greedy achieves higher throughput but higher exposure P99 and backlog than SDPS. The smaller ablation sample does not statistically resolve the no-quality difference at 95% confidence.
Opportunity for larger gains. The relevant factor is the acceptance-yield separation among competing heads, not model parameter count by itself. If future speculative-decoding methods or a broader deployment mix create larger learnable differences across draft models, SDPS could make more valuable admission choices, provided ordinary capacity remains available and verification cost does not negate the yield advantage. Conversely, nearly uniform yields leave little benefit for quality ranking. A follow-up acceptance-gap sweep would quantify the relationship between yield heterogeneity and scheduling gains while controlling candidate supply and service costs.EDF remains better on tail latency: exposure P99 is 1.878 s versus 2.849 s, and upload-to-completion P99 is 5.616 s versus 8.550 s. Both policies have zero observed completed-block exposure violations. The practical reason to choose SDPS is therefore the measured gain in on-time output when contention and yield heterogeneity allow deadline slack to be used productively.
Manuscript changes: Section 6 and Table 2 report the five-run comparison; Appendix E.1 specifies the paired protocol; Table 3 gives the separate tight-SLO results; Appendix F.3/Table 8 and F.7 provide ablations and extended latency accounting. Section 5 and Appendix D clarify the theoretical scope.
Thank you for focusing on the applicability of the reward model and the practical reason to prefer SDPS over a simpler EDF scheduler. We have strengthened both parts of the evidence: a conditional-mean mismatch result and a real task-composition switch address departures from the stationary model, while five paired mixed-workload repetitions quantify the serving benefit and its latency cost. The additions addressing the review comments are highlighted in blue in the revised manuscript for ease of reference.
Q1 Conditional unbiasedness and guarantees beyond stationarity
Why use this assumption? The assumption is a conditional-mean model, not a requirement that every reward be independent or identical. It permits reward distributions to change in ways that preserve the conditional mean. Its role is to make the observed reward minus the node mean a martingale difference, so concentration remains valid under adaptive admissions.
There is a useful systems motivation for a node-level mean. With fixed draft/target weights and decoding settings, each node has a persistent source of yield variation associated with its draft model. Scheduling determines when an already-generated head is verified; in our model it does not alter that head’s target-consistent token yield. Under a stable request mix and weak dependence between residual yield and the admission state, a node mean can therefore be a useful, low-overhead approximation without predefined task labels or a per-request predictor. An exact sufficient condition would be that each candidate reward has the same node-specific conditional mean given the full information available at admission. This is weaker than i.i.d. rewards, but stronger than merely having a stable workload mixture or a stable marginal mean.
The distinction matters in autoregressive serving: successive contexts are related, and context length or task difficulty may covary with waiting and queue state. Merely not changing a block’s reward by scheduling does not make adaptive selection unbiased. We consequently justify the node mean as an analytical abstraction and evaluate its usefulness; we do not claim that realistic LLM workloads universally satisfy the exact condition.
What do the new data establish? In a diagnostic that holds out whole repetitions, adding context-length features to training-set node means reduces prediction MSE by 3.38%/3.33% under the 6 s/12 s settings; adding queue, waiting, and elapsed-time features gives 3.77%/3.82% reductions. Thus, observable state retains predictive information beyond node identity. These reductions are not bounds on conditional-mean bias. The five-run serving comparison nevertheless shows that the existing node-level estimator supports 6.70% higher accepted-draft throughput and 4.75% higher SLO goodput than EDF. A separate real A–B–A task-mixture trial changes QA/code/reasoning/mixed proportions from 60/15/15/10% to 15/35/40/10% and back. Without resets or sliding windows, SDPS achieves 8.845 versus 8.192 tok/s accepted-draft throughput and 12.370 versus 11.723 tok/s SLO goodput relative to EDF, gains of 7.98% and 5.52%. This is one empirical stress trial, not statistical verification of the assumption or a general adaptation guarantee.
What can be guaranteed without a fixed node mean? Appendix D.5 now allows a context-dependent, time-varying conditional mean νₙ(t) for each exposed head. The potential-head mean must be well defined and independent of which other heads share the batch. On the same state and with the same critical-first constraint, let S^ν(t) be the selection obtained by using these current means, kₜ the ordinary capacity, and ηₜ the maximum ordinary-head error |wₙ(t) − νₙ(t)|. If Gₜ^ν is the queue-plus-waiting-plus-current-mean score, the new proposition proves
0≤Gtν(Sν(t))−Gtν(S(t))≤2Vktηt.
Hence the cumulative statewise score loss is at most 2V Σₜ kₜηₜ. For previously observed nodes, the error separates as
∣wn(t)−νn(t)∣≤∣μn(t)−νˉn(t)∣+∣νˉn(t)−νn(t)∣+rn(t).
where ν̄ₙ(t) averages conditional means at prior admissions and rₙ(t) is the existing confidence bonus. The terms represent sampling error, historical-to-current mean mismatch, and optimism. The result applies to the unchanged SDPS rule and quantifies the effect of model mismatch without assuming stationary means.