acceptodds
Under review as a conference paper at ICLR 2027

Queue-Aware Combinatorial Bandit Scheduling for Speculative Decoding in Cloud–Edge LLM Serving

Abstract

Speculative decoding accelerates autoregressive LLM inference by enabling a draft model to generate candidate token blocks, which the target model then verifies in parallel. Existing research largely targets draft-model quality and point-to-point cloud-edge efficiency, leaving unaddressed the contention among edge-generated verification demands for the central target model's resources under multi-user workloads. The scheduling problem that arises when candidate blocks generated asynchronously by multiple edge nodes compete for limited verification resources has become a major bottleneck in improving system efficiency. To address this problem, we formulate shared-verifier admission as a queue-aware combinatorial semi-bandit problem for speculative decoding and propose the Speculative Decoding Pipeline Scheduling (SDPS) algorithm. Each node places its locally generated draft blocks into a pending-verification queue, while the central verifier selects a set of nodes in each round based on queue pressure, verification yield, and latency constraints. Without prior knowledge of node-specific yields, SDPS provably reduces its utility loss as the scheduling horizon grows, while average pending backlog is bounded under a windowed load condition through a single control parameter. Experiments on a distributed LLM system demonstrate that SDPS effectively improves the utilization of centralized verification resources while controlling pending backlog and protecting latency SLOs under multi-user contention. Code is available at https://anonymous.4open.science/r/SDPS1-2E52/.

Primary area:
optimization
Keywords:
bandits, speculative decoding

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_PYGKOpenReview ↗
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

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.0 \le G_t^\nu(S^\nu(t)) - G_t^\nu(S(t)) \le 2V k_t \eta_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).\left|w_n(t)-\nu_n(t)\right| \le \left|\widehat{\mu}_n(t)-\bar{\nu}_n(t)\right| + \left|\bar{\nu}_n(t)-\nu_n(t)\right| + r_n(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.

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.

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

This paper addresses the scheduling problem in cloud-edge LLM serving with speculative decoding. In a multi-user cloud-edge deployment, multiple edge nodes asynchronously generate candidate token blocks that must be verified in parallel by a central target model. When verification resources are limited, contention among edge-generated verification demands becomes a major bottleneck. The authors propose SDPS , a queue-aware combinatorial bandit scheduling algorithm. Experiments on both simulation and a real testbed demonstrate that SDPS achieves higher goodput with zero SLO violations compared to strong baselines.

Critical strengths

1 The paper makes a clean and insightful distinction between upload time and exposure time, measuring per-block latency from the moment a block becomes visible to the scheduler rather than from its upload time. This cleanly separates the delay directly controllable by the scheduling policy from the delay incurred while a block waits behind preceding blocks in node-level FIFO queues. The resulting formulation captures the true scheduling challenge in cloud-edge speculative decoding more faithfully than prior work.

2 The evaluation covers both controlled simulation and a real testbed, compares against eight baselines (including ablated variants SDPS-no-quality and SDPS-greedy), and includes multiple ablation studies isolating the contribution of each component (queue awareness, waiting-time weighting, critical-first promotion). The reward-reversal experiment (Figure 4a) cleanly demonstrates online adaptation capability, and the one-component-at-a-time ablations (Figure 7) provide clear evidence for each design choice.

3 The work bridges theory and practice by addressing a concrete deployment bottleneck in cloud-edge LLM serving. The exposure-based latency metric aligns with real SLO requirements, the critical-first mechanism provides hard latency guarantees, and the testbed evaluation validates the approach beyond simulation. The AI use statement and ethics statement are also appropriately included.

Critical weaknesses

1 The theoretical guarantees rely on Assumptions 1-2, which include independence and boundedness conditions on arrivals and verification yields. In practice, LLM workloads exhibit heavy-tailed request lengths, bursty arrival patterns, and non-stationary verification yields. The paper does not analyze how the bounds degrade under violated assumptions, nor does it provide empirical robustness tests under deliberately non-stationary workloads beyond the reward-reversal scenario.

2 The experiments assume a single target model with relatively homogeneous verification costs across edge nodes. In real deployments, different edge nodes may run different model versions or have different GPU capabilities, leading to heterogeneous verification latencies. The scheduler does not explicitly model or adapt to per-node verification time heterogeneity, which could be significant in heterogeneous cloud-edge deployments.

3 The V controls the utility-backlog trade-off, and the paper uses a fixed V = 5 throughout experiments. While Corollary 3 analyzes parameter scaling, there is no principled method for selecting V a priori given system constraints.

Questions for authors

see weakness

2 comments

Thank you for highlighting workload nonstationarity, verification-cost heterogeneity, and the choice of V. We added a conditional-mean mismatch analysis, a real task-mixture switch, and controlled cost/calibration stress tests. We also clarify which boundedness conditions follow from the block-level interface and which remain assumptions about the operating environment. The additions addressing the review comments are highlighted in blue in the revised manuscript for ease of reference.

Q1 Departures from assumptions and deliberate nonstationarity

The concerns involve three different conditions. First, bounded block reward is not a bounded request-length assumption: a fixed-length draft block contributes a bounded normalized committed-token reward even if a request spans many blocks. Heavy-tailed request lengths can still change queue occupancy, context lengths, and verification times; our 32/64/128-token budgets do not evaluate unbounded request tails. Second, the drift proof does not require i.i.d. or exogenous arrivals: it retains the conditional arrival term and permits history-dependent uploads. It does, however, require the stated upload bound and weighted windowed-load certificate. Bursts are covered only insofar as these conditions hold. Third, stationary conditional means are substantive: context changes or task shifts can violate them even with bounded rewards.

For the third issue, the new Appendix D.5 proves that replacing the current conditional means by SDPS’s indices incurs at most 2Vkₜηₜ statewise score loss per dispatch, hence 2V Σₜ kₜηₜ cumulatively. The error separates into sampling error, historical-mean mismatch, and the confidence bonus. This quantifies degradation as the learned index departs from the current mean without changing the algorithm; it does not imply a sublinear rate for unrestricted drift.

We also added a real A–B–A workload switch, beyond the original temperature-reversal scenario. Over three 200 s phases, the QA/code/reasoning/mixed request proportions switch from 60/15/15/10% to 15/35/40/10% and back. The original SDPS retains its full-history estimates. In the single reported trial it achieves 12.370 tok/s SLO goodput versus EDF’s 11.723 (+5.52%), and 8.845 versus 8.192 tok/s accepted-draft throughput (+7.98%). Existing requests cross phase boundaries, and some slow nodes complete no B-phase blocks, so this is a task-composition stress test rather than a synchronized reward switch for every node.

To test a different failure mode, a separate ten-seed simulation freezes the cycle calibration while doubling or quadrupling verification times in the middle phase. SDPS’s exposure-SLO violations rise to 2.75% and 66.74%, then recovery-phase goodput returns to 49.24 and 49.09 tok/s, compared with 49.43 in the control. This directly exposes the dependence on valid timing bounds. For heavier-tailed arrivals and service times, the next step is to specify finite-moment or tail-probability conditions and develop probabilistic delay guarantees together with load control. Such conditions matter because arbitrarily large bursts or single service times can exceed any fixed deterministic deadline; online recalibration and admission throttling are practical extensions suggested by the measured failure mechanism.

Manuscript changes: Section 5 and Appendices D.1/D.5 clarify the assumptions and mismatch analysis; Appendix F.2/Table 7 reports the real switch; Appendix F.8 reports cost shifts and calibration failure. Appendix F.4 separately retains the open-arrival load sweep.

Q2 Heterogeneous nodes and verification costs

The evaluation already includes edge heterogeneity, and the single shared verifier follows the system architecture studied in this paper. Seven edge nodes run 0.6B/1.7B/4B draft models; their different generation speeds affect when heads become ready, while their different yields enter SDPS through online observations. Using one common target keeps the verification criterion consistent across nodes and focuses the comparison on allocation of a shared bottleneck. Thus, edge generation speed and central verification cost play different roles: a slower edge supplies candidates less frequently, whereas longer contexts or different batch shapes can make those candidates more expensive to verify. We address the latter directly with measured-cost stress tests. Adding multiple target versions or verifier GPUs would introduce routing and model-specific verification as additional decisions. A natural follow-up is to extend the current admission formulation to jointly choose a verifier and a batch, while keeping the present shared-target comparison controlled.

To isolate the cost issue, Appendix F.8 adds ten-seed simulations using independently measured equal-length two-request cost scales of 53.49–194.08 ms. In the middle 200 s evaluation phase, SDPS/EDF SLO goodput is 62.77/52.64 tok/s with equal costs and 48.41/41.49 tok/s with costs independent of yield; both have zero violations in these cases. When cost increases with node mean yield, the ordering reverses: 37.56/43.20 tok/s. Comparisons are within each scenario because mean costs are not matched across scenarios.

The equal-cost and independent-cost results illustrate the potential advantage of learned admission when exposed heads differ in yield. They also identify an important condition for extrapolating to more heterogeneous or future draft models: larger acceptance-yield gaps help only if availability and service costs allow the scheduler to exploit them. The adverse correlated-cost result establishes a concrete boundary: maximizing yield per admission need not maximize yield per unit time when productive heads are expensive. The present yield index keeps online learning focused on bounded token outcomes; verification duration, by contrast, can depend jointly on all heads in a batch, making a simple per-node yield/time ratio insufficient to represent batch cost. The stress results motivate a follow-up joint reward-and-batch-duration model, with corresponding feasibility checks and a time-aware objective.

Manuscript changes: Appendix E.1 describes physical node/model heterogeneity; Appendix F.8 specifies the cost model, favorable and adverse results, and the distinction between per-admission productivity and wall-clock optimization.

Q3 Choosing V before deployment

We have evaluated V explicitly rather than relying on a single setting. Thank you for prompting us to make this evidence and its deployment implications clearer. Appendix F.4 reports a ten-seed parameter sweep over V ∈ {0.5, 1, 2, 5, 10, 20}. We keep V = 5 fixed across policy comparisons so that each workload is evaluated with the same SDPS configuration. Across this 40-fold range, mean SLO goodput varies by only 0.39% in the tested near-capacity simulation, while mean run-level exposure P99 remains within 1371–1426 ms, below the 1500 ms SLO. This shows that the reported behavior is supported by a broad operating range rather than a narrowly tuned V. Corollary 3 provides the complementary theoretical explanation of how utility and backlog bounds scale with V when its uniform load condition holds.

These results suggest a practical constraint-based selection procedure: predeclare a small V grid, evaluate it on an independent calibration workload, retain values meeting measured latency and backlog budgets, select a value with favorable goodput and adequate margin, and freeze it for held-out evaluation. If the feasible set is empty, load or capacity must be adjusted as well. This is a deployment recommendation informed by the sensitivity study; V = 5 remains the common operating point used in the reported experiments. A further extension is to combine this calibration with workload-change detection so that parameter review is triggered by a change in operating conditions.

Manuscript changes: Appendix F.4 reports the sensitivity range and calibration procedure; Corollary 3 retains the assumptions needed for its scaling statement.

Comments on the paper

4 comments

Thank you for the careful assessment of our contribution, component evidence, theoretical benchmark, and deployment setting. Your comments motivated a matched WISP scheduling comparison, an expanded seven-node mixed-workload evaluation, separate quality ablations, and additional latency and calibration diagnostics. We address each concern below and distinguish the empirical serving gains from the scope of the theoretical guarantees. The additions addressing the review comments are highlighted in blue in the revised manuscript for ease of reference.

Q1 Distinction from prior scheduling work

We agree that urgency-first admission and combining queue information with UCB are not, by themselves, new contributions. SDPS addresses the specific admission problem created by asynchronous per-node FIFO exposure: only exposed heads compete for verification, their committed-token yields are selectively observed after service, and critical heads must retain strict priority. Its contribution is the formulation and analysis of online yield learning within this queue- and exposure-aware scheduling rule, rather than the first use of its individual ingredients.

To make the closest comparison concrete, we added a scheduling-only WISP adaptation to the same verification engine. It retains urgency-based ordering, productivity-based residual filling, and predicted batch-feasibility checks. All methods share draft length, capacity, workload, and exposure deadlines. The adapter uses an independently calibrated timing profile for our engine; it does not reproduce WISP’s dynamic drafting controller. When no feasible batch is available, its disclosed single-head EDF fallback prevents indefinite closed-loop blocking, and any resulting violations remain counted. Across five paired runs with the 12 s exposure SLO, SDPS achieves 12.670 tok/s SLO goodput versus 12.267 for the WISP adaptation, with 0% versus 4.03% observed completed-block violations. Under the tighter 6 s SLO, the corresponding means are 12.541 versus 11.161 tok/s, with 0% versus 8.91% violations over three runs.

Manuscript changes: Section 6 and Table 2 report the mixed-workload comparison; Appendix E.1 describes the shared protocol and WISP substitutions, and Table 3 reports the tight-SLO results. Appendix F.3 reports the component ablations.

Q2 Serving benefit and the role of exploration

Thank you for identifying the distinction between deadline protection and the benefit of learning. SDPS uses learned verification yield to allocate ordinary capacity productively, while queue/waiting terms and strict critical priority keep that allocation responsive to congestion and exposure deadlines. This gives it a different operating objective from pure EDF or pure yield ranking: increase on-time token output under contention while retaining deadline protection. We added a broader paired comparison to quantify this benefit and a separate ablation to identify the contribution of the quality term and the UCB bonus. The original six-node result alone does not establish a goodput advantage over EDF, nor does the reversal shift establish a unique advantage of the bonus; the new evidence addresses these questions separately.

The new evaluation uses seven heterogeneous 0.6B/1.7B/4B drafters, a fixed mixed-task prompt corpus, and 32/64/128-token output budgets. With the 12 s exposure SLO, five paired 600 s runs give the following means. SLO goodput remains the original on-time committed-token metric; accepted-draft throughput is an additional diagnostic. All rates include the controlled 500 ms batch delay.

MetricExposure-EDFSDPSSDPS − EDF
Accepted draft tokens per 600 s5138.25482.4+344.2
Accepted-draft throughput, tok/s8.5649.137+6.70%
SLO goodput, tok/s12.09612.670+4.75%
Accepted draft tokens per round4.8445.168+6.69%
Completed-block violations0%0%—
Exposure P99, s1.8782.849+0.971

The expanded evaluation shows a consistent output advantage over EDF across both deadline settings: accepted-draft throughput and SLO goodput improve by 6.70% and 4.75% under the 12 s SLO, and by 5.96% and 4.28% under the 6 s SLO. The five-run 12 s comparison supports positive gains in both metrics at the 95% paired-confidence level. Since both policies fill more than 99.8% of batches, the improvement comes with greater accepted yield per verification round. Appendix E.1 describes the paired protocol. Table 6 reports the per-run differences and their 95% confidence intervals.

Interpreting the size of the gain. The absolute rate difference and the additional token count express the same measured benefit: 344.2 additional accepted draft tokens / 600 s = approximately 0.574 tok/s. Reporting only the sub-one-token-per-second difference can make the accumulated output benefit less intuitive; the count and the increase from 4.844 to 5.168 accepted tokens per round show what the scheduler actually produces. The common time denominator does not dilute the relative gain: the accepted-token count and its rate both improve by 6.70%, and dividing paired differences by the same positive constant does not change their statistical significance. We therefore report counts, per-round yield, wall-clock rates, and paired uncertainty together. SLO goodput remains the primary serving metric and improves by 4.75%e.

When can the advantage be larger? Quality-aware selection has more opportunity when simultaneously available ordinary heads differ in expected yield and there is spare capacity after critical admissions. With nearly equal yields, or when critical heads consume all capacity, learning has little room to improve the selection. If future speculative-decoding developments or more heterogeneous draft-model deployments produce larger acceptance-yield differences across model sizes, they could increase the benefit of learned admission, provided those differences remain learnable and are not offset by slower drafting or more expensive verification. A controlled sweep over acceptance-yield gaps, candidate availability, and verification cost would be a useful follow-up to quantify this potential; model size alone is not a substitute for measuring those quantities.

The independent three-run ablation keeps the queue, waiting, and critical-first rules fixed. Removing the quality term lowers mean goodput from 12.689 to 12.189 tok/s; accepted-draft throughput falls from 9.154 to 8.661 tok/s. All three paired differences favor SDPS, although their 95% intervals include zero. Replacing the optimistic index with the empirical mean gives greedy higher goodput, 13.187 tok/s, but higher exposure P99, 6.597 versus 3.106 s, and backlog, 13.730 versus 10.245 blocks. Thus, the ablation identifies two component effects: the quality term shows a consistent direction of output improvement, while the optimistic index trades some throughput for lower observed tail delay and backlog relative to greedy. Across the main five-run comparison, SDPS also exceeds the mean goodput of FIFO, Random, Sync-round, and the WISP adaptation. Taken together, these comparisons support SDPS’s practical advantage: combining productive admission with exposure protection in the tested contention regime.

Manuscript changes: Section 6 and Table 2 provide the expanded output comparison; Appendix E.1 specifies paired statistics; Appendix F.3 and Table 8 isolate the quality term and UCB bonus. Appendix F.7 reports the additional latency trade-off.

Q3 Meaning of the theoretical benchmark and stability

Your observation about repeated credit is correct: the reference is evaluated on SDPS’s current state and does not remove blocks from an independently evolving system. Its accumulated score must therefore not be interpreted as tokens completed by another scheduler. The benchmark answers a narrower question: how much is lost from learning unknown yields when the exposed candidates, queue state, waiting times, and critical-first constraint are held fixed?

We now state this explicitly in Section 5 and Appendix D.3. The theorem provides a finite-horizon statewise learning comparison, not executable-policy regret or near-optimal wall-clock goodput. Appendix D.4 separately explains the timing conditions needed to relate per-dispatch utility to throughput; this does not remove the comparator restriction.

Likewise, the weighted-drift certificate remains an explicit sufficient condition along the trajectory, not an independently characterized capacity region. It is the condition used to close the drift argument. The closed-loop testbed has structurally bounded outstanding work, so its backlog measurements compare queue occupancy rather than prove open-system stability. The separate open-arrival simulation in Appendix F.4 examines load sensitivity, including increasing backlog above capacity, without replacing the theoretical certificate. The reward-independent exposure-delay result remains useful under its timing and exposure assumptions.

Manuscript locations: Section 5; Appendices D.2–D.4 and F.4. These passages distinguish learning loss, conditional stability, and physical throughput.

Q4 Broader workloads and deployment robustness

Thank you for these concrete suggestions on deployment evaluation. We have expanded the experiments along four dimensions: workload diversity, verification contention, latency accounting, and calibration mismatch. The additions are highlighted in blue in the revised manuscript.

1. Broader real workloads and system configurations. We expanded the physical testbed from six to seven heterogeneous edge nodes running 0.6B, 1.7B, and 4B draft models. The original single-prompt setting is supplemented with 64 prompts covering question answering, code, reasoning, summarization, and mixed tasks, with varying input lengths and 32/64/128-token output budgets. We evaluate both 6 s and 12 s exposure SLOs, using three and five paired repetitions, respectively. Under these settings, SDPS improves accepted-draft throughput over EDF by 5.96% and 6.70%, and SLO goodput by 4.28% and 4.75%. These results show that the output gains extend beyond the original single-prompt experiment to more diverse tasks and deadline settings. The protocol and results appear in Appendix E.1 and Tables 2–3.

2. Verification contention and heterogeneous service costs. With the available edge equipment, seven nodes do not supply enough concurrent work to keep the native verifier persistently saturated. We therefore apply the same fixed batch delay across policies to create a controlled verification bottleneck while retaining real drafting, uploads, target-model verification, and queue feedback. This is a practical substitute for inducing contention with limited hardware, and all headline throughput rates include the added delay. To complement this physical evaluation, we added contention simulations without injected batch sleep, using measured verification-cost scales and synthetic drafting to sustain demand. These experiments examine equal costs, heterogeneous costs independent of yield, and costs correlated with yield. Together, they broaden the evaluation of admission decisions under constrained verification capacity; the simulation protocol and results are reported in Appendix F.8.

3. Latency beyond the exposure clock. We additionally measure hidden FIFO waiting and upload-to-completion latency to examine whether the output gains incur waiting costs omitted by the original exposure SLO. Across the five runs with a 12 s SLO, mean upload-to-completion latency is 3.158 s for SDPS versus 3.230 s for EDF, while P99 is 8.550 s versus 5.616 s. Thus, SDPS increases output without increasing mean completed-block turnaround in this setting, while exhibiting a tail-latency trade-off. These measurements include hidden FIFO waiting after upload and cover blocks completed within the measurement window. Extending the instrumentation to drafting and result return is the next step toward full request-level end-to-end measurement. The additional latency results appear in Appendix F.7.

4. Robustness to violations of the calibrated cycle bound. We directly test calibration mismatch rather than examining only runs that remain within the calibrated bound. In a ten-seed stress simulation, we freeze both the SLO and the assumed cycle bound, increase verification times by 2× or 4× during the middle phase, and then restore the original service times. SDPS’s exposure-SLO violation rates rise to 2.75% and 66.74%, respectively. During recovery, goodput returns to 49.24 and 49.09 tok/s, close to the control value of 49.43 tok/s. These experiments quantify degradation under timing-bound violations and recovery after service times return to normal. They also identify concrete motivations for online cycle monitoring, recalibration, and load control when operating conditions change. The protocol and results appear in Appendix F.8.

Manuscript changes: Section 6 and Appendix E.1 describe the broader protocol; Appendix F.7 reports hidden waiting and block turnaround; Appendix F.8 reports the timing audit and deliberate calibration mismatch. The next deployment evaluation can extend this protocol to request-level timing from drafting through result return and to a larger edge population that saturates the verifier natively.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.