{"id":"02451146-7eb6-426e-aff9-0b913b14fb4b","arxiv_id":"2607.03948","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Online LP bid-price routing with warm-started dual gradient updates substantially improves multi-SLO LLM decode routing over heuristics in simulation.","lead":"The paper formulates LLM request routing under batch and KV-cache limits as online linear programming and uses dual shadow prices (bid-price control) to decide admissions. In the Vidur simulator this science-based router beats standard heuristics on latency, TTFT, throughput and tails while letting operators trade objectives via weights.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.5","headline":"The tail-indicator and saved-steps rewards are unvalidated surrogates; observed multi-objective gains may not survive a true quantile objective.","rationale":"The reader correctly isolates the reward decomposition as the weakest modeling link. Everything else—time-coupled packing constraints, warm-started dual updates, millisecond runtime, and large simulated gains—is either standard online-LP machinery or empirically demonstrated inside Vidur. The only place the argument can silently fail is if the hand-crafted indicators and saved-step rewrites do not preserve the ordering that a true multi-objective optimizer would produce. Because the paper supplies neither a competitive-ratio argument for the approximate dual nor a direct ablation against a true-quantile baseline, the claim remains conditional on that untested fidelity. My concrete test isolates exactly that gap without requiring a full production deployment; a negative result would force a redesign of the reward, while a positive result would largely close the modeling concern the reader already flagged. No stronger internal inconsistency appears in the dual derivation or the constraint accounting, so the verdict stays CONDITIONAL rather than moving to REJECT.","tokens_in":23659,"tokens_out":614,"duration_ms":5821,"concrete_test":"Re-run the exact Vidur configuration of Table 1 (λ=0.4, noisy ôj, same four A100s) but replace the indicator tail terms by a differentiable sample-average P99 surrogate (or by post-hoc selection of the weight vector that truly minimizes empirical P99 on a held-out trace). If the relative improvement of “Ours” over Round-Robin on P99 EEL/TTFT falls below 10 %, the surrogate is load-bearing and the multi-objective claim weakens.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim rests on the per-request rewards of §3.1 converting aggregate SLOs into online decisions that remain near-optimal under bid-price ranking. Average EEL/TTFT are rewritten as “saved steps” (eqs. 2–3) so that the constant (T-tj+1) drops out and the residual terms stay non-negative; tail metrics become hard indicators 1{k-tj<t′} (and the analogous EEL form) whose weights ζ1,ζ2 are said both to trade off objectives and to “map the target quantiles.” No analysis or ablation shows that greedy ranking of these surrogates under the dual prices of (6)–(8) approximates the true multi-objective program (true quantiles + true averages). If the surrogate is loose, the 25–45 % relative gains in Tables 1–2 and Figures 2–3 can vanish even when the dual tracker itself is correct. The paper never reports the realized quantile level achieved by a given (ζ,t′) pair against an oracle that optimizes the true P99, nor does it compare against a router that directly optimizes a sample-average quantile loss.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper formulates online routing of LLM decode requests to parallel workers as a multi-objective online LP under time-coupled batch-size and KV-cache constraints. It constructs per-request rewards that linearly combine throughput, QPS, average EEL/TTFT (via a non-negative “saved-steps” rewriting), and tail EEL/TTFT (via hard indicators 1{latency < t′}), then applies a bid-price policy that admits a request only when its reward exceeds the dual shadow-price cost of the resources it will occupy. Dual prices are tracked by warm-started projected mini-batch subgradient steps on an SAA dual objective so that decisions stay within millisecond budgets. The router is integrated into the Vidur simulator and shown to produce large relative gains (often 25–45 % on average/P95/P99 EEL and TTFT) over Round-Robin, LOR, Random and Power-of-2 across weight regimes, perfect/noisy decode-length prediction, stationary and rate-shift workloads, and both real and synthetic traces.","tokens_in":23962,"tokens_out":1024,"duration_ms":20829,"significance":"If the empirical gains survive more rigorous validation of the reward surrogates and real-system deployment, the work supplies a clean, weight-tunable alternative to the heuristic routers that dominate production LLM stacks, together with diagnostic shadow prices that identify batch versus memory bottlenecks. Strengths that raise the contribution above pure engineering are the explicit LP duality derivation, the predictable-runtime first-order dual tracker, the public Vidur integration, and the consistent multi-regime simulation results (including non-stationary arrivals). The paper therefore offers a useful bridge from classical online resource allocation to LLM serving systems.","major_comments":[{"comment":"§3.1 (reward construction, eqs. (2)–(3) and the subsequent indicator definitions): average EEL/TTFT are rewritten as non-negative “saved steps” and tails become hard indicators 1{k-tj < t′} (resp. for EEL). These are surrogates; the paper never shows that greedy ranking of the resulting rj,g,k under the dual prices of (6)–(8) approximates the true multi-objective program that uses sample quantiles and true averages. Figure 13 only demonstrates that larger ζ2 raises the empirical satisfaction rate for a fixed threshold; there is no oracle comparison that optimizes true P99, nor an ablation that replaces the indicators by other quantile surrogates. Because the 25–45 % gains in Tables 1–2 and Figures 2–3 rest on these rewards, the multi-objective claim remains incompletely supported.","section":"§3.1, eqs. (2)–(3)"},{"comment":"§4 and Appendix C: all quantitative claims are obtained inside the Vidur simulator on four A100s. While the authors correctly flag real-system integration as future work, the central assertion that the method “outperforms others based on heuristics” for LLM serving is therefore still provisional; at minimum a sensitivity study to the simulator’s constant-iteration-time assumption under PD disaggregation (or a single real-engine micro-benchmark) is needed before the magnitude of the reported improvements can be taken as established.","section":"§4, Tables 1–2"}],"minor_comments":[{"comment":"Abstract closing sentence (“A big picture from our result: a science-based approach …”) is informal and should be removed or rewritten in standard scientific prose.","section":"Abstract"},{"comment":"Figures 2–3 and the many appendix radar plots report only normalized values; absolute latency/throughput numbers (or at least a table of raw means) would make the practical magnitude of the gains clearer.","section":"§4.3, Figures 2–3"},{"comment":"Related-work discussion of recent workload-aware and multi-LLM routers (Jain et al., Wu & Silwal, Mei et al.) is brief; a short paragraph clarifying why those methods are not used as additional baselines would strengthen the experimental design.","section":"§1"},{"comment":"Notation for residual capacities b(k) and the scarcity vector dk is introduced somewhat abruptly; a short clarifying sentence after (6) would help.","section":"§3.2"}],"recommendation":"major_revision","confidential_remarks":"Solid applied OR-to-systems paper with reproducible code and large simulation gains, but the unvalidated reward surrogates are the main technical risk. Suitable for a systems or applied-ML venue after the major points are addressed; borderline for a pure theory track."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The useful core is concrete: they cast decode-side routing under continuous batching as online LP with time-coupled batch and KV columns, then run a warm-started projected dual tracker so decisions stay in the 1–2 ms range. That modeling of residual capacities and age-dependent kernels is the real contribution; the dual math itself is textbook (Agrawal, Talluri–van Ryzin, Li–Ye).\n\nWhat they do well is the systems packaging. The reward is weight-tunable, shadow prices give an interpretable congestion signal, and the Vidur integration shows large, consistent relative gains (often 25–45 % on average/P95/P99 EEL and TTFT) over Round-Robin, LOR, Random and Power-of-2 under perfect and noisy length prediction, stationary and rate-shift arrivals, and both real and synthetic P/D mixes. Code is public. For anyone who ships routers this is immediately readable and useful.\n\nThe soft spots are real but not fatal. The multi-objective story leans on the §3.1 surrogates—saved-steps rewriting of average latency and hard indicators 1{k-tj < t′} for tails—whose fidelity to true quantiles is never checked against an oracle or a sample-average quantile loss. Weights and thresholds are free parameters; the paper shows you can move the Pareto surface but does not prove the greedy ranking under dual prices stays near-optimal for the statistical SLOs you actually care about. Everything is still inside Vidur; no production engine, no preemption/swapping, no competitive-ratio or regret bound for the approximate dual updates under non-stationary residuals. Those are engineering and analysis gaps, not internal contradictions.\n\nThis is for systems people who already run continuous-batching decode workers and for OR people looking for a clean ML-systems application. It deserves a serious referee. I would engage: cite the formulation when I next write about LLM routing, and I would send it out for review with a clear request for surrogate validation and at least a partial real-system check.","headline":"Solid transplant of classical bid-price control into continuous-batching LLM decode routing; large Vidur gains, but the multi-objective claim rests on unvalidated reward surrogates and pure simulation.","tokens_in":24618,"tokens_out":517,"would_cite":true,"duration_ms":5293,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"An online linear program with dual shadow prices routes LLM decode requests better than standard load-balancing heuristics across competing service objectives.","keywords":["online linear programming","LLM serving","request routing","bid-price control","multi-objective SLOs","KV-cache constraints","continuous batching","shadow prices"],"falsifier":"Replace the proposed reward decomposition with a pure shortest-queue or random policy inside the same dual-price loop, or ablate the tail-indicator terms, and check whether the reported 25–45 % relative gains on average and P95/P99 end-to-end latency and TTFT disappear in the Vidur experiments under the same weight settings.","tokens_in":24494,"feed_emoji":"⚖️","tokens_out":968,"duration_ms":7989,"temperature":0.7,"pith_summary":"LLM serving systems must decide, as each request finishes prefill, which decode worker should take it next, subject to batch-size and KV-cache limits that bind for the whole remaining generation. Production stacks typically use simple rules such as join-the-shortest-queue or power-of-two choices; those rules ignore explicit service-level objectives and give operators little control over the latency-throughput trade-off. This paper recasts the problem as an online linear program whose objective is a weighted sum of per-request rewards that stand in for throughput, average and tail end-to-end latency, and time-to-first-token. Dual variables of that program become shadow prices on future batch slots and memory; a request is admitted only when its reward exceeds the imputed cost of the resources it will occupy. Warm-started projected gradient steps keep the prices up to date in a few milliseconds. In the Vidur simulator the resulting bid-price router substantially improves average and tail latency metrics relative to the usual heuristics while remaining competitive on throughput, and operators can move along the Pareto surface simply by changing the objective weights.","feed_headline":"Shadow prices beat heuristics for multi-objective LLM routing","feed_subtitle":"An online LP admits decode requests only when their SLO reward exceeds resource cost, cutting latency 25–45 % in simulation.","key_machinery":"The bid-price control rule: at each step the dual prices of residual batch and memory capacity are updated by a short warm-started projected sub-gradient pass; a waiting request is admitted to a device only when its multi-objective reward exceeds the inner product of those prices with the resource profile it will occupy for its predicted remaining length.","core_discovery":"Formulating multi-worker LLM decode routing as an online linear program with time-coupled batch and KV-cache packing constraints, then deciding admissions by comparing each request’s SLO-weighted reward against the dual shadow prices of the resources it consumes, yields large gains over standard load-balancing heuristics across multiple latency and throughput regimes, while giving operators an explicit dial for trading those objectives against one another.","pith_inferences":["The same dual-price skeleton could be reused for other online packing problems inside serving stacks, such as speculative-decoding token budgets or multi-model co-location on a shared memory pool.","If production decode-length predictors improve, the residual gap between the online dual solution and the offline clairvoyant optimum should shrink, giving a clear metric for how much prediction accuracy is still worth buying.","Admission control under overload becomes a natural by-product: any request whose reward falls below its shadow-price cost can be delayed or rejected without extra machinery."],"forward_implications":["Operators can re-target the same router for different products simply by changing a handful of non-negative weights rather than rewriting heuristics.","Shadow prices themselves become live diagnostics that identify whether batch slots or KV-cache memory is the binding bottleneck under a given workload.","When the system is lightly loaded or decode lengths are short, near-zero shadow prices correctly signal that simple heuristics already suffice.","The same packing formulation extends, with only kernel changes, to heterogeneous GPU fleets and to mixed prefill-decode workers."],"fun_headline_variants":["Online LP shadow prices beat load-balancing for LLM multi-SLO routing","Bid-price control admits LLM requests when SLO reward tops dual costs","Time-coupled online LP yields 25-45% latency cuts in decode routing","Shadow-price bids give operators explicit latency-throughput dials","First-order dual tracking routes LLM batches faster than heuristics"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The claim rests on the idea that the hand-crafted per-request reward terms (especially the indicator rewards used for tails and the “saved-steps” rewriting of average latency) faithfully turn the desired aggregate statistical SLOs into online decisions whose greedy ranking under dual prices stays near-optimal.","fun_headline_variants_meta":{"raw":{"variants":["Online LP shadow prices beat load-balancing for LLM multi-SLO routing","Bid-price control admits LLM requests when SLO reward tops dual costs","Time-coupled online LP yields 25-45% latency cuts in decode routing","Shadow-price bids give operators explicit latency-throughput dials","First-order dual tracking routes LLM batches faster than heuristics"]},"model":"grok-4.5","effort":"low","cost_usd":0.003498,"raw_usage":{"total_tokens":1137,"prompt_tokens":735,"num_sources_used":0,"completion_tokens":75,"cost_in_usd_ticks":34980000,"prompt_tokens_details":{"text_tokens":735,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":327,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":735,"tokens_out":75,"duration_ms":3034,"temperature":1.0,"reasoning_tokens":327,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T22:48:14.368304+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Replace the proposed reward decomposition with a pure shortest-queue or random policy inside the same dual-price loop, or ablate the tail-indicator terms, and check whether the reported 25–45 % relative gains on average and P95/P99 end-to-end latency and TTFT disappear in the Vidur experiments under the same weight settings.","supporting_citations":[],"review_version":1}