{"id":"410130d1-8daf-4ab9-bbf2-bc5fc18a67df","arxiv_id":"2502.15763","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A hybrid offline-online scheduler claims to raise LLM inference hardware utilization by about 9 points, but its MIP model and 'Lagrangian' rules contain mathematical flaws.","lead":"This paper proposes a hybrid offline-online scheduling method for large language model inference, using bin packing for request assignment and a preemption rule for prefill versus decode stages. The authors report a utilization increase from 80.2% to 89.1% on a LLaMA-65B and GSM8K benchmark, though the supporting theoretical derivations contain errors.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reported gains assume oracle knowledge of output token counts; in real deployment N^d_i is unknown, so the measured utilization improvement may not transfer.","rationale":"I considered the internal inconsistencies in the original MIP—Eq. (9) appears to forbid decode stages after a request's prefill bin, contradicting Fig. 2's preemption, and the Lagrangian derivatives in Eqs. (42)-(43) are not valid partial derivatives of a max. These are serious correctness defects for the paper's modeling contribution. However, the paper's headline is an empirical scheduling claim, and those defects do not by themselves invalidate the measured heuristic performance; a heuristic can work despite a bad derivation. The load-bearing empirical premise is oracle output length, because every claimed improvement is computed using ground-truth future work. Since the paper itself states this quantity is unknown, the experiment is a favorable-conditions test rather than a deployment test. If the authors add a prediction-based ablation and the gains survive, the empirical claim would be substantially stronger; otherwise the reported numbers likely overstate real-world benefit. The reader's weakest_assumption identified the same concern, so my stress-test agrees with the existing REJECT verdict rather than moving it.","tokens_in":17579,"tokens_out":6435,"duration_ms":69141,"concrete_test":"Re-run the Section V-C experiments under a simulator that reveals N^d_i only as tokens are generated, and compare three schedulers: (a) oracle lengths as in the paper, (b) predicted lengths from a simple estimator (e.g., E[N^d_i] = 344.83), and (c) predicted lengths with noise. Record utilization and makespan for the GSM8K workload and the 100 synthetic cases. If the predicted-length variants fall below baseline by an amount comparable to the paper's claimed gains, the central claim depends on oracle output lengths and does not transfer to real deployments.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The empirical headline—89.1% utilization vs. 80.2%, makespan 190.58s vs. 201.00s—is contingent on exact knowledge of N^d_i. Section III-B states 'the output token number is unknown,' but N^d_i appears as a known parameter in the decode-length constraint (8), in the offline bin-packing objective via T_i (28), in Algorithm 1's sorting key N^p_i+N^d_i and remain_token(j), and in the online preemption cost C_d = T^d * sum(N^d_i * w_ijk) (Eq. 43). The experiments then feed actual GSM8K output lengths (Table III: E[N^d_i] = 344.83) into these decisions. This makes the offline assignment and every preemption/stealing decision exact in simulation. In a real deployment N^d_i must be predicted; prediction error changes remain_token, request order, and the preemption threshold, so the measured 9-point utilization gain and 10-second makespan reduction are not established outside the oracle setting. The authors list stochastic output length as future work (Section VI), confirming the gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies scheduling of LLM inference under the PD-competition mode, where prefill and decode stages alternate on a shared batch of clients. It proposes a mixed-integer programming formulation of the scheduling problem, then decomposes it into an offline bin-packing model for request-to-client assignment (with a claimed theoretical lower bound) and online heuristics for request sorting and for deciding when to preempt decoding to insert prefill. Experiments with LLaMA-65B on the GSM8K dataset report that the full hybrid method improves hardware utilization from 80.2% to 89.1% and reduces total inference time from 201.00s to 190.58s, and a 100-case study reports an average utilization improvement of 8.0 percentage points.","tokens_in":17973,"tokens_out":11582,"duration_ms":123635,"significance":"If the claims were sound, the paper would be a useful operations-research-style contribution to LLM serving: it makes the scheduling problem explicit, provides fast heuristics for a millisecond-scale decision loop, and validates on a real model and dataset with concrete Gantt charts. The paper deserves credit for profiling the hardware (T^p and T^d in Section V-A), reporting a 100-case experiment, and attempting to give a theoretical lower bound. However, the central formal model undercounts decode time by a factor of the batch size, the claimed lower bound is not a lower bound, the 'Lagrangian' derivation is not a Lagrangian method, and the experiments assume oracle knowledge of output token counts that the paper itself states are unknown. These issues are load-bearing for the paper's main contributions, and the empirical headline gains are therefore not established as stated.","major_comments":[{"comment":"The decode-stage duration constraint is written per client, but the hardware profile in Section V-A says a decode stage with 200 clients each producing one token takes 200 × 0.21 + 29 = 71 ms, i.e. the stage length scales with the total number of decode tokens in the batch. Constraint (8), n^d_k ≥ T^d Σ_i N^d_i w_{i,j,k} for each j, only lower-bounds the stage by the busiest client, so with |J|=200 active clients it underestimates the decode stage length by up to a factor of about 200. The same error is repeated in Eq. (39) in the online iteration problem. Since decode time dominates the makespan (T^{d*} = 167s in Section V-C), the MIP model and the online cost comparison of Section IV-C do not describe the hardware they claim to optimize.","section":"Eq. (8), Eq. (39), Section V-A"},{"comment":"The problem statement in Section III-B says 'the output token number is unknown,' yet N^d_i is used throughout as a known parameter: in Eq. (8), in the offline objective through T_i in Eq. (28), in Algorithm 1's sorting key N^p_i+N^d_i and in remain_token(j), and in the decode cost C_d of Eq. (43). Section IV-B explicitly states 'We assume that the output length is predetermined,' and Section VI lists stochastic output length as future work. The experiments feed actual GSM8K output lengths into these decisions (Table III reports E[N^d_i] = 344.83), so the offline balancing and every preemption decision are exact only in an oracle setting. The reported utilization gain from 80.2% to 89.1% and makespan reduction from 201.00s to 190.58s are not shown to transfer to a real deployment where N^d_i must be predicted.","section":"Section III-B, Section IV-B, Algorithm 1, Section V-C, Section VI"},{"comment":"The claimed theoretical lower bound is not actually a lower bound. Equation (31) states tp* ≥ T^p_L · ceil(Σ_i N^p_i / N^cap_L), where T^p_L and N^cap_L are the time and capacity of the largest-capacity prefill level. The right-hand side is the time needed to prefill all tokens using only that level, which is a feasible schedule; a schedule using faster smaller-capacity levels can finish in less time, so the right-hand side is an upper bound on the optimal prefill makespan, not a lower bound. The fixed prefill overhead of 25 ms reported in Section V-A is also omitted. Consequently the value T_LB = 180s and the claimed 52.4% reduction in the 'primal-dual gap' are not justified.","section":"Eqs. (31)-(32), Section V-C"},{"comment":"The online iteration scheduler is described as using a Lagrangian method, but the derivation in Eqs. (42)-(43) is not a Lagrangian relaxation: there is no dual function, multiplier, or stationarity condition. Equation (42) sets ∂tmax/∂y_{k,l} = Σ_l T^p_l, a quantity that is independent of k and l and sums over all levels, and Eq. (43) sets ∂tmax/∂w_{i,j,k} = T^d Σ_i N^d_i, summing over all requests in I rather than the tokens of the specific request whose w variable is changed. As written, Cp is a constant and the rule 'if Cp ≥ C_d, continue decoding; otherwise preempt' is an arbitrary threshold, not a cost-efficiency comparison derived from the MIP. The claim that a Lagrangian method is applied is therefore unsupported.","section":"Section IV-C, Eqs. (42)-(43)"},{"comment":"There is no constraint linking the continuous decode-work variable w_{i,j,k} to the binary assignment variable d_{i,j,k}. Equations (14) and (15) only constrain the sums of w, while constraints (9)-(13) constrain d, so the model permits d_{i,j,k}=1 in stages where no decode work is assigned (w=0) and permits w_{i,j,k}>0 in stages where d_{i,j,k}=0. A feasible solution to the MIP therefore need not correspond to a real schedule of decode stages. This further undermines the claim that Eqs. (1)-(25) describe the inference scheduling problem.","section":"Eqs. (12)-(15), Section III-C"}],"minor_comments":[{"comment":"The phrases 'An Minimizing Makespan Bin Packing Problem' and 'an Minimizing Makespan Bin Packing model' should be corrected to 'A Minimizing Makespan Bin Packing Problem'.","section":"Abstract, Section I"},{"comment":"The text says the hybrid method reduces the total inference time to 190.58s in one paragraph and to 190.08s in the lower-bound paragraph; please reconcile the two numbers.","section":"Section V-C"},{"comment":"The table reports a mean output length of 344.83 tokens with standard deviation 187.99 while the maximum output length is capped at 512 tokens; the paper should state how the cap affects the reported distribution and the resulting N^d_i values used in the experiments.","section":"Table III, Section V-A"},{"comment":"The mapping between the offline model and the original constraints is unclear: the text says the offline method considers 'constraints (2), (12), and (15)–(16)', but Eq. (2) is the makespan constraint and Eqs. (15)-(16) concern w and p assignments that do not appear in the offline model (26)-(30); please clarify the intended relationship.","section":"Section IV-A"},{"comment":"The Gantt charts would be more informative if preemption events were marked and if all four charts used the same time axis scale, so that the reader could directly compare bubble locations across baseline, offline, online-only, and hybrid runs.","section":"Figs. 6-9"},{"comment":"Reference [9] (FastServe) is cited as an arXiv preprint from 2023, but the paper appeared at MLSys 2024; the citation should be updated to the published version.","section":"References"}],"recommendation":"reject","confidential_remarks":"The manuscript would require a full revision of the MIP formulation, the lower bound, and the derivation of the online preemption rule, followed by a new experimental study that does not assume oracle knowledge of output lengths and that compares against existing serving baselines such as vLLM or Orca. As it stands, the central theoretical claims are not sound and the headline empirical results are contingent on an acknowledged unrealistic assumption."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2502.15763.\n\nThe paper has a real kernel: treating LLM inference as a prefill/decode scheduling problem and using a hybrid offline bin packing + online preemption heuristic to reduce GPU idle bubbles. That's a legitimate angle, and the authors actually ran LLaMA-65B on Ascend hardware with GSM8K, which is more than most scheduling papers do. The Gantt charts show visible bubble reduction. I agree with the reader that the core idea is not conceptually new—it's a new application of known scheduling techniques—but that's not fatal by itself.\n\nHowever, the paper has a load-bearing problem: the experiments assume the scheduler knows each request's output token count in advance. Section III-B explicitly says the output token number is unknown, yet N^d_i appears as a known parameter in the MIP, in the offline bin packing objective, in Algorithm 1's sorting key, and in the preemption cost. The experiments feed actual GSM8K output lengths into these decisions. That makes the offline assignment and every preemption decision exact in simulation. In a real deployment, output length must be predicted; prediction error changes the sorting, the remaining-token counts, and the preemption threshold. So the reported 8.9-point utilization gain and 10-second makespan reduction are not established outside this oracle setting. The authors acknowledge this as future work, but it's central, not a side issue.\n\nThere are also technical errors in the model equations. Eq. (8) constrains decode stage length per client, but the hardware profile in Sec. V-A says decode time scales with the total tokens across all clients in the batch (200 clients x 1 token = 71 ms). So the MIP underestimates decode stage length by up to a factor of J. The 'Lagrangian' cost formulas in Eqs. (42)-(43) have incorrect derivatives: the derivative w.r.t. y_{k,l} should be T^p_l, not the sum over l, and the derivative w.r.t. w_{i,j,k} should be T_d, not T_d times the sum of all N^d_i. So the online heuristic is a greedy rule that happens to work in simulation, not a Lagrangian method.\n\nThe baseline is also weak: they only compare against their own 'no scheduling' policy, not against vLLM, Orca, Sarathi-Serve, or any other serving system. Without a stronger baseline, the '8% improvement' is not convincing. No code or data is released, and the 100-case study has no error bars.\n\nWhat's genuinely useful: the problem is well-motivated, the offline/online decomposition is sensible, and the lower bound is a valid relaxation. The flaws are fixable. If they switch to predicted output lengths with error models, correct the decode constraint, benchmark against real systems, and release artifacts, this could become a solid engineering paper. As is, I'd reject it, but I'd send it to review rather than desk-reject because the topic is important and there's a real experimental component.","headline":"Useful scheduling idea and real hardware runs, but the evaluation uses oracle output lengths and the MIP has a load-bearing decode-time error; reject as is, though the direction is worth a serious look.","tokens_in":18335,"tokens_out":8108,"would_cite":false,"duration_ms":77585,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B35","90C11"],"pacs":[],"model":"deepseek-v4-flash","headline":"A hybrid offline-online scheduler raises LLM serving hardware utilization from 80.2% to 89.1% and cuts makespan from 201 to 190.58 seconds on LLaMA-65B over GSM8K.","keywords":["large language model inference","inference scheduling","prefill-decode scheduling","mixed-integer programming","bin packing","online scheduling","preemptive scheduling","GPU utilization"],"falsifier":"Run the same hybrid scheduler on a live workload in which output lengths are predicted rather than taken from finished responses, and compare utilization with the 89.1% reported here; if the gain over the baseline shrinks toward zero, the output-length assumption is the cause.","tokens_in":1470,"feed_emoji":"⚙️","tokens_out":4138,"duration_ms":77789,"temperature":0.7,"pith_summary":"The paper argues that LLM inference serving can be treated as a scheduling problem with two decision layers, and that a hybrid offline-online method beats the common prefill-first policy. It formulates the full problem as a mixed-integer program, then decomposes it: an offline bin-packing model balances requests across clients, while an online rule sorts requests by total token count and uses a Lagrangian cost comparison to decide when to preempt decode stages with prefill stages. On a real deployment of LLaMA-65B serving the GSM8K dataset, the combined method raises measured hardware utilization from 80.2% to 89.1% and lowers total inference time from 201.00 to 190.58 seconds. A 100-case study reports the method consistently beats the baseline by an average of 8.0 percentage points in utilization.","feed_headline":"Scheduler lifts LLM inference utilization from 80% to 89%","feed_subtitle":"Hybrid offline bin-packing plus online preemption cuts GSM8K inference time from 201 to 190.58 seconds.","key_machinery":"The carrying mechanism is a two-level decomposition of a single mixed-integer program. Offline, a Minimizing Makespan Bin Packing Problem assigns requests to clients to minimize the maximum client decode load, and a theoretical lower bound is computed by adding the minimum possible total prefill time to the optimal decode makespan. Online, a sorting and preemptive rule lets an idle client take the request with the largest remaining token count from a busy client, while an iteration scheduler compares the prefill cost $C_p=\\sum_l T^p_l$ against the waited decode time $C_d=T^d\\sum_i N^d_i w_{i,j,k}$ and inserts a prefill stage only when $C_p < C_d$. This cost comparison is designed to be evaluated within milliseconds, matching the roughly 50-millisecond decode rounds of real serving systems.","core_discovery":"The central discovery is that the idle 'bubbles' in LLM serving come from unbalanced client workloads plus a prefill-first policy that never reorders or preempts, and both can be attacked in milliseconds. The paper claims that balancing requests across clients by solving a minimax bin-packing model, treating each request's estimated total token time as its size, raises utilization from 80.2% to 85.5%. Adding online request sorting, where an idle client steals the request with the largest remaining token load, plus iteration-level preemption, where a prefill round is inserted when its marginal cost is below the waiting decode cost, further lifts utilization to 89.1%. These gains are claimed to be consistent over 100 randomly generated cases, with an average utilization improvement of 8.0% over the baseline.","pith_inferences":["Because the reported gains rely on knowing each request's true output length when balancing clients and when computing the preemption comparison, a deployment that must predict output lengths may see smaller gains; a testable extension is to replace true lengths with quantile estimates and measure the utilization drop.","The same cost-comparison rule could be extended to heterogeneous GPU clusters by making the prefill and decode costs per device rather than global, a direction the paper does not explore.","The 100-case study suggests the method transfers across input and output length distributions drawn from the same moments, but distribution shift toward much longer outputs or multi-turn conversations is an untested boundary.","The theoretical lower bound could serve as a live headroom signal: when the current makespan is far above the bound, preemption is worth more; the paper does not close that feedback loop."],"forward_implications":["Deploying the offline assignment alone, for workloads known in advance such as RLHF-style batch training, should reduce client idle time and raise utilization to about 85.5% without changing the online policy.","The online-only variant, which needs no prior knowledge of the request set, still improves utilization to 86.2% and cuts inference time to 193.3 seconds, so the method claims applicability to ordinary interactive serving.","The Lagrangian comparison gives a concrete and cheap decision rule: begin a prefill round whenever its stage cost is less than the decode time currently waiting, a rule that can be evaluated in under 10 milliseconds per iteration.","The hybrid method brings the makespan to within 10 seconds of the theoretical lower bound, versus 21 seconds for the baseline, meaning it closes about half of the reducible gap the authors quantify through their bound."],"supporting_citations":[{"why":"This reference supplies the baseline serving system whose first-come-first-served prefill-first scheduler is the comparison point.","marker":"[1]"},{"why":"This reference supplies the continuous-batching technique that lets decode stages be preempted by prefill stages in the proposed scheduler.","marker":"[2]"},{"why":"This reference supplies the 1,319 math-word problems used as the real deployment workload, including the token-length statistics that drive the experiments.","marker":"[34]"}],"fun_headline_variants":["Hybrid scheduler lifts LLM utilization from 80.2% to 89.1%","Offline-online scheduling cuts inference time by 10.4 seconds","Bin-packing and preemption boost LLM utilization by 9%","LLM inference scheduler: 5% faster, 9% more efficient"],"cache_read_input_tokens":20480,"weakest_assumption_plain":"The load-bearing premise is that each request's output token count is known when requests are balanced and when the preemption rule is evaluated, even though the paper states that output length is unknown until generation ends.","fun_headline_variants_meta":{"raw":{"variants":["Hybrid scheduler lifts LLM utilization from 80.2% to 89.1%","Offline-online scheduling cuts inference time by 10.4 seconds","Bin-packing and preemption boost LLM utilization by 9%","LLM inference scheduler: 5% faster, 9% more efficient"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000344,"raw_usage":{"total_tokens":1904,"prompt_tokens":972,"completion_tokens":932,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":588,"completion_tokens_details":{"reasoning_tokens":847}},"tokens_in":588,"tokens_out":932,"duration_ms":9085,"temperature":1.0,"reasoning_tokens":847,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T18:48:19.561091+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same hybrid scheduler on a live workload in which output lengths are predicted rather than taken from finished responses, and compare utilization with the 89.1% reported here; if the gain over the baseline shrinks toward zero, the output-length assumption is the cause.","supporting_citations":[],"review_version":1}