{"id":"f6e0e08e-7dec-48fd-8b79-130fc1e1b0bb","arxiv_id":"2504.15720","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"SeaLLM shares GPU resources across multiple LLM services with a preemptive, service-characteristic-aware scheduler, search-based placement, adaptive replacement, and a merged-block unified KV cache, cutting normalized latency by up to 13.6x.","lead":"SeaLLM is a GPU-cluster system that lets multiple different large language models share the same hardware, using latency-aware request scheduling, careful model placement, and a single unified memory cache. The authors report up to 13.6x lower normalized latency, 18.7x lower tail latency, and up to 3.64x higher SLO attainment than prior sharing systems on a 32-GPU testbed.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"DB scheduling uses remaining budget, not estimated remaining time, as priority; within a service this raises the priority of an aging request and blocks fresh short requests, so Theorem 2 does not apply to the implemented algorithm.","rationale":"The reader's weakest assumption was profiling accuracy: the priority rule requires T'_r estimated from historical distributions. My concern is distinct and more specific: even with perfect profiling, the implemented DB algorithm does not use T'_r at all. It uses the remaining budget Q_r, which decreases with elapsed time and therefore gives higher priority to older requests before budget expiry, inverting the theoretical rule within a service. This affects the load-bearing claim because the scheduling algorithm is the core contribution and the ablations (Figure 8) show it is the main source of the reported improvements. The empirical 13.60x result may still be real, but the theoretical support claimed by Theorem 2 does not cover the evaluated system. This does not force rejection: a systems paper can present DB as a heuristic with empirical support, but then the optimality claims and the wording 'latency-optimized scheduling algorithm' must be tempered, and the distance from the theoretical scheduler should be measured. Since the reader's verdict is already CONDITIONAL, and this concern adds a precise technical condition rather than changing the overall assessment, the verdict remains CONDITIONAL. I marked agreement as partial because the reader identified profiling accuracy as the weakest assumption, which is related but does not capture the structural mismatch between Q_r and T'_r.","tokens_in":20966,"tokens_out":22708,"duration_ms":219308,"concrete_test":"Add a single-service microbenchmark to the simulator using the paper's Algorithm 2: service with Lhat_s = 5, Var_s = 3, one long request of length 10 arriving at t=0 and one short request of length 1 arriving at t=1. Compute the normalized latency and compare it against a scheduler implementing the theoretical priority O_r = T'_r Lhat_s, where T'_r is the estimated conditional residual time from the profiled output-length distribution. If DB's normalized latency exceeds the T'_r scheduler, Theorem 2 does not justify DB and the paper should either prove a performance bound for DB or present it as a heuristic with the gap quantified on the MAF traces. If the two schedulers match on this and on the full trace, the concern is refuted and no claim change is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In §4.2 and Algorithm 2, the implemented priority is O_r = Q_r Lhat_s, where Q_r is the remaining budget, initialized to Lhat_s + Var_s and decreased as the request executes. Consequently, a partially executed request has a smaller Q_r and therefore a higher priority until its budget expires, at which point the budget is doubled and the priority drops. The priority proven optimal in Theorem 2 (Eq. 7 and Eq. 13) is O_r = T'_r Lhat_s, where T'_r is the estimated remaining time. For two requests of the same service with different lengths, these rules order the requests oppositely: a short request arriving while a long request is partway through its budget has the larger priority value because it starts with the full initial budget, so it waits up to Lhat_s + Var_s, whereas the theoretical rule would preempt because the short request's T'_r is small. Concretely, with Lhat_s = 5, Var_s = 3, a length-10 request arriving at t=0 and a length-1 request arriving at t=1, Algorithm 2 completes the long request at t=11 and the short request at t=9, giving normalized latency 4.0; preemptive shortest-remaining-time scheduling completes the long request at t=11 and the short request at t=2, giving normalized latency 2.6. Thus DB is not merely an approximation of the proven priority; it is a different heuristic whose within-service ordering can substantially increase normalized latency. The paper's own admission that 'it is difficult to tell how far our scheduling decision is from the optimal scheduling decision' is therefore the operative statement, and the central improvement claim rests on an unproven heuristic rather than on Theorem 2.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"SeaLLM is a cluster-level system for sharing multiple LLM services on GPU clusters. The paper makes three main design contributions: a service-aware placement algorithm with adaptive replacement intervals, a preemptive 'doubling budget' (DB) request scheduler that uses profiled per-service execution characteristics, and a unified KV cache that lets different LLM architectures share GPU memory efficiently. The system is implemented on a 32-GPU testbed and evaluated against vLLM, AlpaServe, and MuxServe under real-world traces, with a simulator cross-checked against the testbed. The headline results are reductions in normalized latency by up to 13.60x, tail latency by up to 18.69x, and improvements in SLO attainment by up to 3.64x relative to baselines.","tokens_in":21269,"tokens_out":8129,"duration_ms":75498,"significance":"The problem addressed is important: multi-LLM serving on shared GPU clusters is increasingly common, and existing systems are either designed for classical models or optimize throughput at the expense of latency. SeaLLM's real-testbed evaluation on 32 GPUs with modern LLMs, its simulator cross-validation (Table 2 reports differences under 3%), and its ablation study separating scheduling, placement, and KV-cache effects are genuine strengths. The unified KV cache for heterogeneous architectures is a practical contribution, and the comparisons are against credible baselines. However, the paper's central theoretical claim that its scheduling algorithm minimizes normalized latency is not supported for the algorithm actually implemented: the DB scheduler differs structurally from the priority rule proven optimal, and the paper itself concedes that the distance from the optimal schedule is unknown. The empirical results may still stand, but the formal framing needs substantial revision.","major_comments":[{"comment":"The implemented priority is not the priority proven optimal. Theorem 2 proves optimality of O_r = T'_r Lhat_s (Eq. 13), where T'_r is the estimated remaining execution time. Algorithm 2 instead uses O_r = Q_r Lhat_s, where Q_r is the remaining budget, initialized to Lhat_s + Var_s and decremented as the request runs. For two requests of the same service, this orders them essentially oppositely: a partially executed long request has a small Q_r and therefore higher priority, while a newly arrived short request starts with the full budget and lower priority. The paper's own statement in §4.2 that 'it is difficult to tell how far our scheduling decision is from the optimal scheduling decision' acknowledges this gap. Consequently Theorem 2 does not apply to the DB scheduler as implemented; the paper must either prove an optimality property for the DB rule or reframe the scheduler as a heuristic and adjust the abstract and Section 4.2 claims accordingly.","section":"§4.2 and Algorithm 2 (Appendix A.2)"},{"comment":"The optimality claim is conditional on accurate knowledge of the remaining time T'_r, but at scheduling time the true output length of a running request is unknown. T'_r is therefore only a historical estimate derived from profiled per-service distributions. The paper acknowledges this limitation in Figure 13, which shows that SeaLLM's advantage shrinks as the variance of output length grows, yet the abstract and Section 4.2 present the minimization of normalized latency as an unconditional property. The formal statements and the central claims should explicitly state the profiling-accuracy condition and characterize how the guarantee degrades when the profile is wrong.","section":"§4.2, Theorem 2 and Figure 13"},{"comment":"The proof of Theorem 1 considers only pairwise swaps of two individual requests and does not model the batched execution that the system actually performs, the memory constraints on the number of concurrently resident requests, or preemption only at iteration boundaries. Since the implemented scheduler batches same-phase requests of the same service and cannot preempt arbitrarily, the idealized model in Theorem 1 is not shown to describe the deployed system. The paper should either extend the proof to the batched, memory-constrained setting or explicitly state that Theorem 1 is an idealized bound that does not directly apply to the implementation.","section":"Appendix A.2, proof of Theorem 1"}],"minor_comments":[{"comment":"Equation 1 defines normalized latency as a sum over requests, while Section 6.1 defines it as the average of end-to-end latency divided by average execution time. The two definitions differ by a factor of the number of requests; please align them and state which one is used in the experiments.","section":"Equation 1 and §6.1"},{"comment":"The budget is defined as Q = Lhat_s + Var_s, but Var_s is described as the 'standard variance' of execution time. If Var_s is a variance, the sum adds quantities with different units; if it is a standard deviation, the terminology and notation should be corrected for clarity.","section":"§4.2, budget definition"},{"comment":"The testbed and simulator results are presented as single curves without error bars, confidence intervals, or repeated-run information. Given the headline multipliers (13.60x, 18.69x), a small number of repeated runs with variance information would substantially strengthen the evaluation.","section":"Figures 6–13"},{"comment":"The hyperparameters alpha, beta, I0, and the per-service starvation threshold are chosen as fixed values, but no sensitivity analysis is provided. Since these parameters affect placement and scheduling behavior, a brief study of their influence would improve reproducibility.","section":"§4.3 and §6.1"},{"comment":"The first column of Table 2 is labeled 'Baseline' but the rows list system names; consider renaming the column to 'System' for clarity.","section":"Table 2"}],"recommendation":"major_revision","confidential_remarks":"The empirical evaluation appears reasonably executed and the system is likely to be useful, but the mismatch between the proven scheduling priority and the implemented DB rule is a real correctness gap in the paper's central claim. I would not reject the paper, but the authors need to either supply a proof for the DB scheduler under its actual semantics or substantially weaken the optimality claims. The reviewer should also watch whether the revised paper responds to the profiling-accuracy condition rather than merely citing Figure 13."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read SeaLLM. It's a serious systems paper with strong empirical results on a real 32-GPU cluster: up to 13.6x normalized-latency improvement over MuxServe, 18.7x tail-latency, 3.64x SLO attainment, and a simulator that tracks the real testbed within 3%. The combination of service-characteristic-aware scheduling, two-stage placement, adaptive replacement interval, and merged-block unified KV cache is genuinely new and well-integrated. The ablations show each piece contributes.\n\nThe soft spots are real but not fatal. The biggest is the gap between the scheduling theory and the implemented algorithm. Theorem 2 proves optimality for priority O_r = T'_r * Lhat_r (estimated remaining time times profiled execution time). Algorithm 2 actually uses remaining budget Q_r as the priority. Those order requests differently within a service. The stress-test example is correct: for a service with Lhat=5, a long request that has consumed part of its budget gets higher priority than a fresh short request, which is the opposite of the proven rule. The paper's own admission — 'it is difficult to tell how far our scheduling decision is from the optimal scheduling decision' — is honest but concedes the central optimality claim does not apply to the shipped scheduler. That should be fixed, either by proving something about DB or by repositioning it explicitly as a heuristic with the theory as inspiration.\n\nOther issues are minor. No code or artifacts released; no error bars or repetition counts; hyperparameters like alpha, beta, I0, and starvation thresholds are not swept. The Theorem 1 proof in Appendix A.2 actually checks out algebraically on my read; the sign of D is consistent with a contradiction proof, so I wouldn't make that a review point. Simulator-only results are clearly labeled, and Table 2 gives a reasonable fidelity check.\n\nNet: this deserves a serious referee. The empirical contribution is substantial and the serving-systems crowd will want to build on it. The theory needs to be aligned with the implementation, and the reproducibility bar (code, error bars, hyperparameter sensitivity) should be met before acceptance. I'd lean conditional accept with major revisions, not desk reject.","headline":"Solid systems paper with real 32-GPU gains and an honest theory-implementation gap; deserves peer review but needs code release and a proper justification for the DB scheduler.","tokens_in":21898,"tokens_out":3521,"would_cite":false,"duration_ms":31780,"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":"SeaLLM claims that a preemptive priority scheduler using profiled per-service execution times minimizes normalized latency when several LLMs share a GPU cluster, cutting normalized latency by up to 13.60x, tail latency by up to 18.69x…","keywords":["LLM inference serving","resource sharing","latency-optimized scheduling","preemptive priority scheduling","doubling budget","key-value cache","GPU cluster","normalized latency"],"falsifier":"Run SeaLLM on a trace whose output-length distribution is deliberately different from the profile used to set priorities (for example, profile on short outputs and then serve mostly long outputs), and compare normalized latency with FCFS and round-robin baselines; the central claim would be overturned if SeaLLM's advantage disappears or reverses once the output-length variance multiplier reaches the range (about 16x) where the paper's own accuracy study shows degradation.","tokens_in":20710,"feed_emoji":"⚡","tokens_out":9067,"duration_ms":74549,"temperature":0.7,"pith_summary":"SeaLLM's central claim is that GPU clusters serving multiple large language models can be shared with much better latency if the scheduler exploits each service's profiled execution-time distribution instead of using generic first-come-first-serve or round-robin policies. The paper assigns every request a priority equal to its estimated remaining execution time multiplied by its service's average per-GPU execution time, and runs the smallest-priority request preemptively. It proves that this rule minimizes normalized latency under idealized assumptions, and adds a placement search, an adaptive replacement interval, and a unified KV cache to make the gains hold under real traffic. On real-world traces with four LLMs on a 32-GPU cluster, the authors report up to 13.60x lower normalized latency, up to 18.69x lower tail latency, and up to 3.64x higher SLO attainment against existing sharing systems. The conclusion is that multi-LLM sharing can be made latency-competitive, not just throughput-oriented.","feed_headline":"Scheduling by remaining time cuts LLM sharing latency up to 13.6x","feed_subtitle":"The priority rule beats FCFS and round-robin on real traces, keeping SLO attainment above 90 percent.","key_machinery":"The central object is the priority rule $O_r = T'_r \\hat{L}_r$ for preemptive request scheduling: a request's priority is its estimated remaining execution time multiplied by the profiled average per-GPU execution time of its LLM service, with smaller values served first. This is the c-$\\mu$ rule specialized to minimizing normalized latency $L_N = \\sum_{s}\\sum_{r \\in R_s} L_r / \\hat{L}_s$, and it is carried by a doubling-budget mechanism: each request gets a budget $Q = \\hat{L}_s + \\mathrm{Var}_s$, and when that budget is exhausted the budget is doubled and the priority is reset. The placement controller, adaptive replacement interval, and unified KV cache are secondary machinery that keep the scheduling rule effective under dynamic traffic and heterogeneous model architectures.","core_discovery":"On the paper's own terms, SeaLLM's discovery is that the head-of-line blocking that plagues FCFS sharing of LLM services can be removed by a preemptive priority rule informed by service profiles, at the cost of preemptions only when a request exceeds its budget. The priority is $O_r = T'_r \\hat{L}_r$, the product of the estimated remaining time and the profiled average per-GPU execution time, and the budget is $Q = \\hat{L}_s + \\mathrm{Var}_s$, doubled when exhausted. Theorem 1 states that with arbitrary preemption and identical per-service execution times this scheduling minimizes normalized latency; Theorem 2 states that the priority is optimal for expected normalized latency at every scheduling moment. The paper then shows how to keep that scheduling rule effective in practice: a two-stage placement search chooses sharing groups and parallelism, an adaptive replacement algorithm lengthens or shortens the placement interval according to the gap between estimated and achieved performance, and a unified KV cache with merged blocks lets LLMs with different block shapes share memory. The evaluation on real traces reports the normalized-latency, tail-latency, and SLO-attainment gains summarized above.","pith_inferences":["A natural extension is to replace the profiled static estimate $T'_r$ with dynamic output-length predictions from the model itself (for example, from early-exit or speculative-decoding signals), which would sharpen priorities without changing the scheduling rule.","The same normalized-latency objective could be applied to other autoregressive workloads, such as multimodal generation, whose service-specific length distributions would feed the same priority and budget scheme.","The paper's identical-execution-time theorem suggests a direct lower-bound comparison: on traces with known output lengths, an offline shortest-remaining-processing-time schedule weighted by $\\hat{L}_s$ should bracket SeaLLM's latency; the gap would quantify the cost of profiling error.","Because the benefit shrinks as output-length variance grows (the paper's own profiling-accuracy experiment), the scheduler would benefit from online re-profiling or anomaly detection that updates $\\hat{L}_s$ and $\\mathrm{Var}_s$ during a replacement interval."],"forward_implications":["Under accurate profiling, the scheduling rule removes the head-of-line blocking of FCFS by letting short requests overtake long ones, with the doubling budget limiting how often long requests are preempted.","Bursty services no longer pay the memory and latency penalty of round-robin, because only requests that exhaust their budget are interrupted rather than rotating all services.","The adaptive replacement interval lets a cluster shift LLM services between GPU groups as request traffic changes, without an operator choosing a fixed interval.","At tested rates SeaLLM keeps SLO attainment above 90 percent while baselines drop, implying fewer GPUs are needed to meet the same service-level objectives.","Token-level time-to-first-token improves because prefill is not round-robinned away from bursty services; time-per-output-token stays comparable to dedicated serving."],"supporting_citations":[{"why":"Closest prior LLM-sharing system; it contributes the round-robin-plus-FCFS scheduling and fixed GPU quotas that SeaLLM compares against and claims to outperform by up to 13.60x normalized latency.","marker":"[18]"},{"why":"Provides the statistical-multiplexing placement model that SeaLLM extends and the FCFS-sharing baseline used in evaluation.","marker":"[32]"},{"why":"Underlying LLM engine and FCFS single-model serving baseline; SeaLLM reuses its components in the implementation.","marker":"[29]"},{"why":"Supplies the skip-join MLFQ scheduling baseline whose service-oblivious preemption SeaLLM's service-aware DB scheduling improves on.","marker":"[50]"},{"why":"Establishes the c-mu rule for scheduling with convex delay costs, which Theorem 2 cites for optimal priority.","marker":"[46]"},{"why":"Provides the queueing-model lemma on optimal priority policies used in the proof of Theorem 2.","marker":"[45]"},{"why":"Supplies the real-world serverless function trace used to generate request arrivals in the evaluation.","marker":"[39]"},{"why":"Defines the chatbot service workload with long output lengths that shapes service characteristics in the experiments.","marker":"[5]"},{"why":"Defines the summarization service workload with long input lengths that shapes service characteristics in the experiments.","marker":"[12]"},{"why":"Supplies the LLM architectures (7B/13B/70B) used in the evaluation and the block-shape example for the unified KV cache.","marker":"[44]"}],"fun_headline_variants":["Preemptive scheduling cuts LLM sharing latency up to 13.6x","Remaining-time priority cuts LLM sharing latency up to 13.6x","SeaLLM's preemptive rule cuts LLM sharing latency up to 13.6x","Service-aware scheduling trims LLM latency up to 13.6x in shared GPUs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the profiled per-service execution-time statistics (average and variance) predict live request behavior; if actual output lengths drift from the profile, the priority rule and budget are miscalibrated and the reported gains shrink.","fun_headline_variants_meta":{"raw":{"variants":["Preemptive scheduling cuts LLM sharing latency up to 13.6x","Remaining-time priority cuts LLM sharing latency up to 13.6x","SeaLLM's preemptive rule cuts LLM sharing latency up to 13.6x","Service-aware scheduling trims LLM latency up to 13.6x in shared GPUs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00127,"raw_usage":{"total_tokens":5227,"prompt_tokens":1009,"completion_tokens":4218,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":625,"completion_tokens_details":{"reasoning_tokens":4126}},"tokens_in":625,"tokens_out":4218,"duration_ms":27667,"temperature":1.0,"reasoning_tokens":4126,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:19:32.123998+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SeaLLM on a trace whose output-length distribution is deliberately different from the profile used to set priorities (for example, profile on short outputs and then serve mostly long outputs), and compare normalized latency with FCFS and round-robin baselines; the central claim would be overturned if SeaLLM's advantage disappears or reverses once the output-length variance multiplier reaches the range (about 16x) where the paper's own accuracy study shows degradation.","supporting_citations":[{"cited_title":"Muxserve: Flexible spatial-temporal multiplex- ing for multiple llm serving","cited_arxiv_id":null,"evidence_quote":"Closest prior LLM-sharing system; it contributes the round-robin-plus-FCFS scheduling and fixed GPU quotas that SeaLLM compares against and claims to outperform by up to 13.60x normalized latency."},{"cited_title":"Alpaserve: Sta- tistical multiplexing with model parallelism for deep learning serving","cited_arxiv_id":null,"evidence_quote":"Provides the statistical-multiplexing placement model that SeaLLM extends and the FCFS-sharing baseline used in evaluation."},{"cited_title":"Gonza- lez, Hao Zhang, and Ion Stoica","cited_arxiv_id":null,"evidence_quote":"Underlying LLM engine and FCFS single-model serving baseline; SeaLLM reuses its components in the implementation."},{"cited_title":"Dynamic scheduling with convex delay costs: The generalized c| mu rule","cited_arxiv_id":null,"evidence_quote":"Establishes the c-mu rule for scheduling with convex delay costs, which Theorem 2 cites for optimal priority."},{"cited_title":"Finding Optimal Policy for Queueing Models: New Parameterization","cited_arxiv_id":"2206.10073","evidence_quote":"Provides the queueing-model lemma on optimal priority policies used in the proof of Theorem 2."},{"cited_title":"Serverless in the wild: Characterizing and optimizing the serverless workload at a large cloud provider","cited_arxiv_id":null,"evidence_quote":"Supplies the real-world serverless function trace used to generate request arrivals in the evaluation."},{"cited_title":"https://sharegpt.com/, 2023","cited_arxiv_id":null,"evidence_quote":"Defines the chatbot service workload with long output lengths that shapes service characteristics in the experiments."}],"review_version":1}