{"id":"d708671d-00c5-40a0-81da-230c422ed8d3","arxiv_id":"2505.17074","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"LAPS-SD schedules speculative decoding requests by combining LAS-style preemption during early unstable acceptance rates with SJF ordering once acceptance rates stabilize, cutting average inference latency by about 39% in experiments.","lead":"Speculative decoding speeds up LLM text generation, but scheduling these requests is tricky because execution time depends on the request's token acceptance rate, not just output length. This paper presents LAPS-SD, a scheduling algorithm that first uses preemption and then switches to shortest-job-first once acceptance rates stabilize, claiming an average latency reduction of about 39%.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 39% latency claim rests on acceptance rates stabilizing early enough for Eq. (6) estimates to order requests correctly; evidence is three curves and unspecified gamma/delta.","rationale":"The reader's weakest assumption identifies the same load-bearing point: the method's effectiveness hinges on acceptance rates becoming stable and predictable, yet Section 4.3 leaves the stability criterion (gamma, delta) unspecified and Section 4.1 supports it only with three illustrative curves. I agree that this is the most critical vulnerability. If the stability premise fails, the transition to the SJF phase is based on an unreliable fixed acceptance rate, and the execution time estimates from Eq. (6) are wrong; the algorithm then degenerates into a LAS variant with arbitrary queue assignments, and the claimed 39% improvement over LP-SJF and LAS is unsupported. The concrete test I propose directly probes both the timing of stabilization and the ordering accuracy of the estimates, which is what SJF actually requires. I do not see an internal inconsistency in Eq. (6) that would be fatal; the notation for T_SSM and T_LLM is confusing, but the formula's structure (expected rounds times per-round speculation and verification costs) is plausible. I also acknowledge the paper's other weaknesses (batch-size-1 assumption, unspecified K in the main results, limited baselines, no error bars) as secondary. Since the reader already rendered a CONDITIONAL verdict incorporating this concern, my analysis does not change that recommendation; it strengthens the specific reason for the condition. Therefore the verdict remains UNCHANGED.","tokens_in":12545,"tokens_out":6742,"duration_ms":66915,"concrete_test":"Run the same LLaMA-7B / LLaMA-68M speculative decoding setup on a held-out set of at least 500 requests per dataset, logging per-round acceptance rates. Apply the stability criterion with explicit values (e.g., gamma=5, delta=0.05) and record the output-token fraction at which each request stabilizes. Then compute the fraction of request pairs whose SJF order according to Eq. (6) disagrees with the order by actual measured execution times. If more than 20% of pairs are inverted, or if the median stabilization point occurs after 50% of the output length, the semi-clairvoyant ordering is unreliable and the headline 39% reduction cannot be attributed to the proposed estimation mechanism.","verdict_should_be":"UNCHANGED","load_bearing_attack":"LAPS-SD's 'perceptible' phase switches to SJF only when a request's acceptance rate is judged stable (Section 4.3: max difference over gamma consecutive rounds below delta). The claimed advantage over LP-SJF and LAS depends on this criterion firing early enough and on the fixed A_i in Eq. (6) being accurate enough that SJF ordering matches true execution times. The paper's support is Figure 3, which shows only three example curves, and an aggregate 6.84% estimation error in Section 5.2. That aggregate is not sufficient because Figure 7 shows individual real/estimated time ratios ranging from about 0.6 to 1.6, i.e., per-request errors of up to roughly 40-60%. Such errors can invert pairwise SJF decisions even when the mean error is small, and SJF is sensitive to ordering, not to mean error. Moreover, gamma and delta are never specified, so the stability trigger is not reproducible and there is no evidence that it fires before a large fraction of a request's output has been generated. If acceptance rates remain volatile or stabilize late, Eq. (6) is inaccurate, the SJF phase is effectively a guess, and the attributed benefit of LAPS-SD over the baselines is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes LAPS-SD, a scheduling algorithm for speculative-decoding LLM requests. The method assumes that a request's token acceptance rate is volatile in early decoding and stabilizes later; while a request is non-perceptible it is managed with LAS-style preemption across K priority queues, and once its acceptance rate is judged stable, the algorithm predicts output length (via an existing method) and acceptance rate (from recent history), estimates the remaining execution time using Eq. (6), and schedules perceptible requests by the SJF principle. The paper formulates a non-preemptive average-latency minimization problem in Section 3, describes the algorithm in Section 4, and evaluates it in Section 5 on three datasets against LP-SJF and LAS, reporting an average latency reduction of about 39% and an average execution-time estimation error of 6.84%.","tokens_in":12938,"tokens_out":5970,"duration_ms":54635,"significance":"The paper addresses a real and under-studied problem: scheduling speculative-decoding requests whose execution time depends on both output length and token acceptance rate. The two-phase design—preemption while acceptance rates are volatile, then SJF after stabilization—is a sensible idea that is motivated by the example curves in Figure 3. The paper also makes an honest effort to evaluate the execution-time estimator, and the 39% figure is an empirical measurement rather than a parameter fitted to the target result. If the latency reduction is reproducible under fully specified hyperparameters and with run-to-run variance reported, this would be a useful contribution to LLM serving systems. However, the current evidence under-supports the headline quantitative claim and the optimality wording in the abstract.","major_comments":[{"comment":"The central premise—that acceptance rates stabilize early enough and remain stable for the rest of decoding—is not quantitatively established. The stability condition uses parameters gamma and delta that are never specified, and Figure 3 shows only three example curves. This matters because the perceptible phase uses the fixed acceptance rate A_i in Eq. (6) as a predictor for the remaining execution, so without evidence on how early stabilization occurs, the semi-clairvoyant stage may start too late to affect latency or may start while A_i is still volatile.","section":"Section 4.3, Eq. (6)"},{"comment":"The reported aggregate estimation error (6.84% overall; 7.63%, 11.21%, and 8.51% per dataset) is not the right metric for validating SJF ordering. The scatter plots show individual real/estimated time ratios spanning roughly 0.6 to 1.6, i.e., per-request errors of about 40–60%. Since SJF is sensitive to pairwise order rather than mean error, these errors can invert scheduling decisions even when the mean error is small; the paper should report order-preservation statistics or error quantiles by output length.","section":"Section 5.2, Figure 7"},{"comment":"The number of priority queues K is a free parameter, and the optimal K varies with dataset and request count (e.g., K=6 for 10 Chatbot requests vs. K=4 for 10 MiniThinky requests). The main comparison in Figure 5 does not state which K was used for LAPS-SD, nor whether K was tuned per dataset. Without this information the 39% claim is not reproducible, and the reported advantage could be partly due to per-dataset tuning of K.","section":"Section 5.2, Figure 6"},{"comment":"The statement that LAPS-SD \"minimizes\" average inference latency is not supported by any optimality proof or lower-bound argument. The formulation in Eqs. (2)–(5) is a non-preemptive problem statement, and Algorithm 1 is a heuristic. The text should either provide a formal guarantee for the idealized model or soften the claim to say that LAPS-SD reduces latency in the evaluated settings.","section":"Abstract, Section 3"},{"comment":"The notation in Eq. (6) is internally inconsistent with the definitions in the surrounding text. The text defines T_LLM as the speculation time per token and T_SSM as the verification cost per round, but Eq. (6) places T_SSM in the \"Speculation Time\" term and T_LLM in the \"Verification Time\" term. Since Eq. (6) is the basis of the execution-time estimate and the claimed 6.84% accuracy, the paper must clarify which quantity is actually used in the implementation and align the text and equation.","section":"Section 4.3, Eq. (6)"}],"minor_comments":[{"comment":"The threshold relation Sup_j = M^(j-1) * Sup_1 introduces a parameter M that is never defined or reported; please define M and explain how it was set in the experiments.","section":"Section 4.2"},{"comment":"Figures 5–7 show no error bars, confidence intervals, or repeated-run information, so it is unclear whether the reported differences between LAPS-SD and the baselines are stable across random seeds or workload samplings.","section":"Section 5"},{"comment":"The statement that LAS-based scheduling is \"adopted by [Leviathan et al., 2023]\" is questionable: that reference is a speculative-decoding paper, not a scheduling paper, and the LAS scheduling policy is credited to [Rai et al., 2003].","section":"Section 2.3 and References"},{"comment":"The reference \"[Z et al., 2024]\" is incomplete (missing full author list, title, and venue) and appears to duplicate the later [Zheng et al., 2024] entry; please merge or correct.","section":"References"},{"comment":"Minor wording: \"prioritize scheduling perception requests\" should read \"prioritize scheduling perceptible requests,\" and the pseudocode in Algorithm 1 omits the details of how the stability check and queue migration are actually implemented.","section":"Section 4.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a reasonable systems paper with a plausible core idea, but the load-bearing empirical and reproducibility issues need to be addressed before it can be accepted. I would ask the authors to specify all hyperparameters (gamma, delta, K, M), justify the stability assumption more rigorously, and provide order-sensitivity analysis for the execution-time estimator. The optimality language in the abstract should be softened unless a formal result is added."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The new thing here is the specific combination: LAS-style preemptive scheduling in an early phase, then a switch to SJF once an online estimate of each request's token acceptance rate stabilizes. That is a sensible adaptation to speculative decoding, where execution time depends on acceptance rate, not just output length. The paper correctly identifies a real gap: existing schedulers for LLM serving either ignore acceptance rate or use pure LAS with costly preemption. LAPS-SD is a reasonable middle path, and the intuition that acceptance rates stabilize after an initial phase is plausible and supported by the three example curves in Figure 3. The execution-time model in Eq. (6) is straightforward and the estimation error analysis, while limited, shows the method can track real times on average.\n\nThe soft spots are real but not fatal to the idea. The biggest issue is empirical: no error bars, no repeated runs, and the main 39% reduction is a single aggregate claim. The K parameter (number of priority queues) is left unspecified in the main experiments, and Figure 6 shows the optimal K varies by dataset and request count, so the headline number depends on tuning that is not disclosed. The stability trigger (gamma and delta in Section 4.3) is never given values, and the paper does not show how often the trigger fires early enough for the SJF phase to matter. The stress-test note is right that per-request errors in Figure 7 can be 40-60%, which can invert SJF ordering even when the mean error is small. That said, the stress-test note slightly overstates the danger: SJF is sensitive to ordering, but the paper's own comparison is against LP-SJF and LAS, not an oracle, and LAPS-SD still outperforms both in the reported runs. The bigger concern is that the batch-size-1 assumption is never relaxed, despite a hand-wave that it can be extended; for a systems paper, that is a significant limitation.\n\nThe citation pattern is fine; the related work covers the relevant scheduling and speculative decoding literature, and the claim that this specific hybrid is new holds up against the cited papers. There is no circularity: the acceptance-rate predictor uses each request's own history, and the 39% figure is an experimental outcome.\n\nWho is this for? Researchers working on LLM serving systems, especially those interested in speculative decoding and scheduling policies. It is a workshop-level or solid-poster contribution as is; with code, error bars, and a specification of gamma/delta and K, it could become a real systems paper. I would send it to peer review rather than desk reject, because the scheduling insight is worth refereeing even if the current evidence is thin.\n\nRecommendation: engage with it, but ask for a major revision that addresses reproducibility and the batch-size-1 limitation.","headline":"A plausible scheduling idea for speculative decoding, but the 39% claim is built on thin empirical support and a stability trigger that is not specified enough to check.","tokens_in":13316,"tokens_out":682,"would_cite":false,"duration_ms":8260,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Scheduling speculative-decoding requests with both predicted output length and token acceptance rate, rather than output length alone, reduces average inference latency by roughly 39%.","keywords":["speculative decoding","LLM inference","request scheduling","token acceptance rate","semi-clairvoyant scheduling","least attained service","shortest job first","latency minimization"],"falsifier":"Run LAPS-SD on a workload constructed so that token acceptance rates oscillate throughout the entire decoding process, or let requests complete before the $\\gamma$-round stability window elapses; if the average latency is no better than pure LAS or pure LP-SJF, the stabilization premise fails. In particular, compare the estimated execution time of Eq. (6) against measured times after stabilization on a large sample of requests; an average error well above the reported 6.84% would indicate the stability detector is not working.","tokens_in":12354,"feed_emoji":"⚡","tokens_out":8124,"duration_ms":64739,"temperature":0.7,"pith_summary":"Speculative decoding speeds up LLM inference by having a small model draft several candidate tokens that the large model verifies in parallel, so a request's execution time depends on how many drafted tokens are accepted, not just on how many tokens it outputs. The paper's claim is that schedulers which estimate execution time purely from predicted output length are systematically wrong for such workloads, and that a scheduler can do much better by tracking each request's token acceptance rate as it decodes. It proposes LAPS-SD, a two-phase scheduler: while acceptance rates are still unstable, it preempts requests across multiple priority queues (LAS-style); once a request's acceptance rate settles, it estimates the remaining execution time with a formula combining predicted length and acceptance rate, and switches to shortest-job-first without preemption. Experiments on three datasets place the average latency reduction at about 39% versus length-prediction-based SJF and LAS. A sympathetic reader would care because it is a concrete, parameter-light way to bring classic scheduling ideas to LLM serving systems that already use speculative decoding.","feed_headline":"Scheduling by token acceptance rate cuts LLM latency 39%","feed_subtitle":"A semi-clairvoyant scheduler preempts early, then switches to shortest-job-first once acceptance rates stabilize.","key_machinery":"The load-bearing mechanism is the two-state, multi-queue scheduling algorithm LAPS-SD with its execution-time estimator. Requests begin as 'non-perceptible' in the highest-priority queue; after each speculative round the accumulated service determines which of $K$ exponentially sized priority queues they sit in, allowing preemption of young requests at low switching cost because few KV pairs have been generated. When the acceptance rate has been stable for $\\gamma$ consecutive rounds (difference below a threshold $\\delta$), the request becomes 'perceptible,' and its remaining time is estimated by $$\\tilde{T}_i = \\frac{n L_i}{n A_i + 1} T_{\\text{SSM}} + \\frac{L_i}{n A_i + 1} T_{\\text{LLM}},$$ where $n$ is the number of speculative tokens per round and $A_i$ the stabilized average acceptance rate. Perceptible requests are scheduled SJF within their queue and are never preempted, eliminating the switching overhead that grows with KV-cache size. The key property the algorithm exploits is the empirical stabilization of acceptance rates over decoding.","core_discovery":"The central discovery is that speculative-decoding requests become 'perceptible' during execution: after an initial volatile phase, their token acceptance rate stabilizes, so the total execution time can be estimated accurately enough to run shortest-job-first scheduling. The paper shows that execution time is shaped by both output length and acceptance rate—more precisely, the number of LLM verification passes scales as $L_i/(nA_i+1)$ per request, where $L_i$ is output length, $A_i$ is average acceptance rate, and $n$ is the speculative window. Existing length-prediction-only schedulers (LP-SJF) ignore the acceptance-rate factor and therefore misorder requests; preemption-only schedulers (LAS) avoid misordering but pay increasing KV-cache switching costs. LAPS-SD runs a LAS-like preemptive multi-queue during the volatile phase, then commits each request to a non-preemptive SJF order once stability is detected, and the authors report a 39% average latency reduction over these baselines.","pith_inferences":["The same semi-clairvoyant principle—preempt while estimates are unreliable, then commit to SJF—should transfer to any workload with an early volatile phase followed by stabilization, such as auto-regressive decoding with adaptive sampling temperatures or multi-step reasoning traces.","The stability thresholds $\\gamma$ and $\\delta$ are left unspecified in the paper; a practical deployment would need to set them per model family, and an adaptive scheme that learns these thresholds online could further close the gap to the optimal schedule.","The current experimental setup fixes batch size to 1; a natural extension is to group perceptible requests with similar $\\tilde{T}_i$ into batches, trading some latency for throughput while keeping the SJF ordering.","The 39% figure compares against two baselines; a stronger test would be against a clairvoyant scheduler that knows each request's true execution time from the start, which would isolate the cost of the volatile phase."],"forward_implications":["LLM serving systems that support speculative decoding can use acceptance-rate monitoring, not just predicted output length, to estimate request execution times.","Schedulers can safely combine preemption and SJF: preempt only while estimates are unreliable, then commit to non-preemptive order, avoiding both head-of-line blocking and excessive KV-cache switching costs.","The optimal number of priority queues is not fixed: it decreases as request count grows and as switching costs rise, so deployments should tune $K$ per workload.","Execution-time estimation error is around 6.84% on average across the tested datasets, and the paper attributes the residual error to acceptance-rate prediction accuracy."],"supporting_citations":[{"why":"Introduces speculative decoding and supplies the LAS-based scheduling baseline against which LAPS-SD is compared.","marker":"[Leviathan et al., 2023]"},{"why":"Provides the LP-SJF baseline that predicts output length to estimate execution time, which LAPS-SD argues is insufficient for speculative decoding.","marker":"[Qiu et al., 2024]"},{"why":"Supplies the output-length prediction method that LAPS-SD uses as part of its execution-time estimate.","marker":"[Z et al., 2024]"},{"why":"Defines least-attained-service scheduling with preemption, the mechanism LAPS-SD uses while acceptance rates are unstable.","marker":"[Rai et al., 2003]"},{"why":"Supplies the speculative decoding serving context and the per-token verification time used in the illustrative example and experiments.","marker":"[Miao et al., 2024]"}],"fun_headline_variants":["Semi-clairvoyant scheduler cuts LLM latency 39%","Preempt first, then SJF: 39% faster LLM inference","Acceptance-rate-aware scheduling reduces LLM latency 39%","LAPS-SD: adaptive scheduling for 39% lower LLM latency"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that a request's token acceptance rate becomes stable and predictable early enough in decoding that the fixed average acceptance rate used in the execution-time estimate is accurate; if acceptance rates keep fluctuating, the shortest-job-first ordering is based on wrong job sizes.","fun_headline_variants_meta":{"raw":{"variants":["Semi-clairvoyant scheduler cuts LLM latency 39%","Preempt first, then SJF: 39% faster LLM inference","Acceptance-rate-aware scheduling reduces LLM latency 39%","LAPS-SD: adaptive scheduling for 39% lower LLM latency"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000234,"raw_usage":{"total_tokens":1516,"prompt_tokens":985,"completion_tokens":531,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":452}},"tokens_in":601,"tokens_out":531,"duration_ms":4887,"temperature":1.0,"reasoning_tokens":452,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:07:08.074356+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run LAPS-SD on a workload constructed so that token acceptance rates oscillate throughout the entire decoding process, or let requests complete before the $\\gamma$-round stability window elapses; if the average latency is no better than pure LAS or pure LP-SJF, the stabilization premise fails. In particular, compare the estimated execution time of Eq. (6) against measured times after stabilization on a large sample of requests; an average error well above the reported 6.84% would indicate the stability detector is not working.","supporting_citations":[{"cited_title":"Fast inference from transformers via speculative decoding","cited_arxiv_id":null,"evidence_quote":"Introduces speculative decoding and supplies the LAS-based scheduling baseline against which LAPS-SD is compared."},{"cited_title":"Efficient interactive llm serving with proxy model-based sequence length prediction","cited_arxiv_id":null,"evidence_quote":"Provides the LP-SJF baseline that predicts output length to estimate execution time, which LAPS-SD argues is insufficient for speculative decoding."},{"cited_title":"Analysis of las scheduling for job size distributions with high variance","cited_arxiv_id":null,"evidence_quote":"Defines least-attained-service scheduling with preemption, the mechanism LAPS-SD uses while acceptance rates are unstable."},{"cited_title":"Specinfer: Accelerating large language model serv- ing with tree-based speculative inference and verification","cited_arxiv_id":null,"evidence_quote":"Supplies the speculative decoding serving context and the per-token verification time used in the illustrative example and experiments."}],"review_version":1}