{"id":"ac574c60-0186-4288-b411-f81dd767e81b","arxiv_id":"2501.05563","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A prediction-assisted SRPT scheduler for mixed-parallelism deep learning jobs in GPU clusters, with a graph-based placement heuristic and a competitive-ratio analysis.","lead":"This paper proposes A-SRPT, a scheduler that predicts how long recurring deep learning training jobs will run and uses those predictions to prioritize short jobs across GPUs. It also includes a graph-based placement step and claims up to 92% lower total job completion times in simulations.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's 'G−gmax busy GPUs' premise is false; a lone small job can run alone, so the makespan bound and Theorem 1's proof are unsupported.","rationale":"Reader's verdict is CONDITIONAL, and my stress-test supports that. The strongest claim is a provable competitive ratio (Theorem 1). The proof depends on Lemma 2's claim that during execution of jobs 1..i−1 at least G−gmax GPUs are continuously busy. This claim is not an algorithmic invariant of A-SRPT. The minimal 2-job example shows the claimed makespan bound in Lemma 2 is false as written. The example preserves the paper's model: homogeneous servers, jobs with fixed GPU counts, predicted iterations equal to actual, and no communication-heavy delay. The failure mode is not adversarial placement or prediction error but the algorithm's own behavior: once a single small job is the only remaining work, the cluster runs it alone, so the denominator G−gmax in the makespan bound is unjustified. I do not claim the theorem's numerical inequality is false; the bound is loose enough that it may hold. But the paper's submitted proof is invalid at a load-bearing step, so the advertised theoretical guarantee is unsupported until Lemma 2 is repaired or replaced. Empirical results and Heavy-Edge evaluation are useful and are not the object of this concern. Because the reader already conditioned acceptance on fixing the proof and adding sensitivity/artifacts, my verdict is UNCHANGED.","tokens_in":21376,"tokens_out":23560,"duration_ms":231726,"concrete_test":"Simulate Algorithm 1 on the 2-job instance above (G=100, gmax=50, perfect predictions, τ=0, COMM_HEAVY=∞, tie-break A before B in \\tilde A1) and check the Lemma 2 intermediate inequality for i=B: the left side makespan_1 equals the actual completion time of A (101000), while the claimed right side is C_2 + g_A n_A αmax_A/(G−gmax) = 2000 + 100000/50 = 4000. The violation settles that the Appendix B busy-GPU premise is false. If the authors respond that makespan_1 is defined under a different (non-A-SRPT) schedule, the revised definition should be stated and shown to imply the subsequent display (12).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix B, Lemma 2, bounds the makespan of the first i−1 jobs by C_i + Σ_{j<i} g_j n_j αmax_j/(G−gmax) + Σ τ..., asserting that 'with no further delays, we can ensure at least G−gmax GPUs are continuously busy for each job's training.' Algorithm 1 does not establish this invariant. The head-of-line wait at line 25 is not the only problem; the invariant fails whenever the last unfinished job among 1..i−1 runs by itself with gi < G−gmax, because all other GPUs are idle for its entire duration. Counterexample: G=100, gmax=50, perfect predictions, τ=0, two jobs released at 0: A (g=1, duration 100000, αmax=1) and B (g=50, duration 2000). In \\tilde A1 both have virtual processing 1000; with tie-breaking A before B, A is appended at t=1000 and B at t=2000. A-SRPT starts A at 1000 and B at 2000; B finishes at 4000, A at 101000. For i=B, C_i(OPT_{\\tilde A1})=2000, and the intermediate bound of Lemma 2 gives makespan_1 ≤ 2000 + 1·100000/50 = 4000, while actual makespan_1 (completion of A) is 101000. The busy-GPU premise is false from t=4000 to 101000, when A runs alone on 1 GPU (1 < G−gmax=50). The final Lemma 2 inequality is not violated in this instance because B overlaps with A, but the proof's derivation is invalid; hence Theorem 1 is not proven by the submitted argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes A-SRPT, an online non-preemptive scheduler for distributed deep learning jobs with mixed parallelism (DDLwMP) in GPU clusters. It combines a graph-based placement heuristic (Heavy-Edge) with a random-forest predictor of training iterations, and maps the original cluster scheduling problem to a single-machine preemptive instance that is solved by SRPT. The central claims are a competitive-ratio bound (Theorem 1) that degrades with the average prediction error, and trace-driven experiments showing up to a 92% reduction in total job completion time over baselines.","tokens_in":21775,"tokens_out":13480,"duration_ms":132044,"significance":"If the competitive-ratio bound were established, this would be a useful addition to the DDL scheduling literature: it treats heterogeneous multi-GPU jobs with mixed parallelism, handles uncertain training durations through learned predictions, and separates placement (Heavy-Edge) from ordering (SRPT). The experimental study is reasonably thorough: a testbed using MIG, large-scale simulations over a 758k-job trace, comparison with five baselines, and a head-to-head evaluation of Heavy-Edge against ILP showing orders-of-magnitude speedup with only a small per-iteration training time penalty. The prediction model is evaluated on a held-out portion of the trace, and A-SRPT comes within 7% to 14% of a perfect-prediction variant. However, the main theoretical guarantee currently rests on an invalid proof step, and the workload trace is synthesized because model information is absent, so both the theoretical and the empirical claims need strengthening.","major_comments":[{"comment":"The proof of the makespan bound is invalid because it relies on the assertion that \"with no further delays, we can ensure at least G−gmax GPUs are continuously busy for each job's training.\" Algorithm 1 does not enforce this invariant: line 25 advances time when the head of pending_queue cannot fit, so GPUs can remain idle even when later jobs in the queue could start, and a job running alone with g_i < G−gmax leaves more than gmax GPUs idle for its whole duration. Concretely, take G=100, gmax=50, τ=0, perfect predictions, and two jobs released at time 0: A with g=1, n=100000, αmax=1, and B with g=50, n=2000. In A1 both jobs have virtual processing time 1000; if ties are broken A before B, A-SRPT starts A at t=1000 and B at t=2000, so B finishes at 4000 and A at 101000. For i=B, the intermediate bound makespan_1 ≤ C_i(OPT_A1) + Σ_{j<i} g_j n_j αmax_j / (G−gmax) equals 2000 + 100000/50 = 4000, but the actual makespan of the first job is 101000. The final inequality of Lemma 2 is not violated in this instance, but the derivation of Eq. (12) is false, so Theorem 1 is not proven by the submitted argument.","section":"Appendix B, Lemma 2"},{"comment":"The exchange argument for underestimated jobs is under-specified. Inequality (14) compares total durations, but SRPT decisions depend on remaining processing times at the time of divergence, and the schedules may already have processed part of the jobs. After shortening ipred's duration, the SRPT schedule can change the entire subsequent order, so the statement that we \"identify the subsequent time step t' ... and repeat\" does not, by itself, establish the claimed decrease of at least Σ_{i∈U} (g_i/G) ϵ_i α~min_i in the objective. Since Lemma 3 is used in the proof of Theorem 1, this step needs a rigorous exchange argument or a direct citation to a lemma that already covers this transformation.","section":"Appendix C, Lemma 3 (Phase 2)"},{"comment":"The trace-driven evaluation is synthetic in a way that materially limits the empirical claims. The two-month trace contains no DNN model information, so profiled models and their distributed configurations are randomly assigned to job groups, and the number of training iterations is obtained by dividing the trace duration by the estimated α~min_i. This procedure can create arbitrary correlations among iteration count, GPU demand, and communication pattern; the reported reductions (31% to 92% depending on setting) may therefore not transfer to actual DDLwMP workloads. The comparisons are internally fair because all algorithms see the same constructed workload, but the authors should at minimum report sensitivity to the random assignment (e.g., multiple seeds or an alternative model-to-group mapping) before claiming \"real-world trace-driven\" validation.","section":"Section V-A-1-b and V-B"}],"minor_comments":[{"comment":"In the displayed algebra, the term I gmax αmax (1 + τ/G + (1+ρ)/(G−gmax)) ε should read I gmax αmax ((1+τ)/G + (1+ρ)/(G−gmax)) ε; the final bound in the next line uses the correct expression, so this is a typesetting error, but it makes the derivation hard to follow.","section":"Theorem 1 proof"},{"comment":"The condition in Algorithm 1 uses αmax_i / α~min_i ≥ COMM_HEAVY, while the text says the job is communication-heavy when the ratio \"exceeds COMM_HEAVY (1.5)\"; the threshold should be made consistent.","section":"Algorithm 1 line 8 and Section IV-C-1"},{"comment":"Because MIG vGPUs share the same PCIe interconnect, the testbed cannot exercise Heavy-Edge's placement decisions; the discussion should state more clearly that the testbed validates the SRPT ordering logic under a homogeneous interconnect, while placement benefits are supported only by the simulation study.","section":"Section V-A-1-a"},{"comment":"The large-scale simulation results are reported as single numbers without confidence intervals; since jobs are sampled from the trace, reporting the mean and spread over multiple random samples would make the comparisons more robust.","section":"Section V-B-2-a"},{"comment":"The prediction-error histogram uses absolute iteration counts; adding a normalized (relative) error axis would make the accuracy of the random forest model more interpretable across jobs of very different lengths.","section":"Fig. 4"}],"recommendation":"major_revision","confidential_remarks":"I see two viable paths for a revised version. First, repair the proof of Lemma 2 by either changing Algorithm 1 so that the busy-GPU invariant actually holds (for example, by a work-conserving packing that respects the SRPT order) or by proving the makespan bound with a different argument. Second, if the proof cannot be repaired, the authors should remove the \"provable\" competitive-ratio claim and reposition the paper as an empirical/heuristic scheduling study. Either path also requires a sensitivity analysis for the synthetic trace construction. Given the timely topic and the otherwise careful evaluation, I would not reject outright."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Should know: A-SRPT is a real attempt at a genuinely open problem—non-preemptive online scheduling for DDL jobs with mixed data/model/pipeline parallelism—and the empirical part is honestly built. But the headline theoretical guarantee is not proven. Lemma 2's proof asserts that for each job's training at least G−gmax GPUs remain continuously busy, and Algorithm 1 does not maintain that invariant. A tiny job can run alone while the rest of the cluster idles. The stress-test counterexample (G=100, one 1-GPU long job and one 50-GPU short job released at 0) does exactly that, so the makespan bound that feeds Theorem 1 is unsupported. This is a genuine gap, not a nitpick.\n\nWhat is new and good: the paper separates placement from ordering, using a greedy graph-cut algorithm (Heavy-Edge) for GPU mapping and a virtual single-machine SRPT instance built from predicted iteration counts for scheduling order. That decomposition is sensible and not present in the cited single-parallelism literature. Heavy-Edge is evaluated against an ILP (6% PITT gap, orders of magnitude faster), and the full scheduler is compared against five baselines on a 758k-job production trace, including 150k-job simulations, with 12–92% total completion time reductions. The baselines also use Heavy-Edge, so the comparison isolates the scheduling policy. The random forest prediction model is trained on the first 80% of the trace, so prediction evaluation is not circular to the scheduling claim.\n\nSoft spots beyond the proof: the trace lacks DNN model information, so models and training configurations are randomly assigned to job groups, and iteration counts are derived by dividing trace durations by estimated per-iteration times. That makes the \"trace-driven\" claim weaker than it sounds. COMM_HEAVY=1.5 and the delay factor τ are hand-tuned with no sensitivity analysis. No code or data is released. The testbed runs on 14 MIG vGPUs on one box, and the authors admit placement has little effect there—so the testbed is a sanity check, not a validation of Heavy-Edge.\n\nBottom line: the empirical core is plausible and likely salvageable, but the theoretical claim should not be accepted as-is. A serious referee should ask for either a corrected proof or an honest downgrade of the theory to a conjecture, plus artifact release and sensitivity studies. It deserves referee time, but not acceptance in its current form.","headline":"Plausible heuristic with strong experiments, but the Theorem 1 competitive-ratio proof has a real gap and should not be accepted as-is.","tokens_in":22259,"tokens_out":2374,"would_cite":false,"duration_ms":24375,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A prediction-assisted scheduler for mixed-parallelism deep learning jobs reduces total completion time by up to 92 percent by scheduling a virtual single machine with SRPT and using that order to place real jobs on GPUs.","keywords":["distributed deep learning","GPU cluster scheduling","mixed parallelism","shortest remaining processing time","online scheduling","prediction-assisted scheduling","graph partitioning","random forest regression"],"falsifier":"Run A-SRPT on a small cluster (say two GPUs) with a trace where the first pending job needs both GPUs while a queued single-GPU job could run, and count total idle GPU time. If the measured idle time exceeds the makespan term Lemma 2 allows, then the Theorem 1 bound is not supported for the algorithm as implemented, because the busy-GPU premise in Appendix B would be violated.","tokens_in":21175,"feed_emoji":"⚡","tokens_out":6414,"duration_ms":59212,"temperature":0.7,"pith_summary":"The paper is trying to establish that a practical non-preemptive scheduler for distributed deep learning jobs with mixed parallelisms can be built by pretending the whole GPU cluster is a single machine. It argues that running preemptive SRPT on that virtual machine yields a sound ordering for placing real jobs onto GPUs, and that the resulting A-SRPT algorithm has a worst-case completion-time guarantee that degrades only linearly in the average training-iteration prediction error $\\bar{\\epsilon}$. If correct, this gives cluster schedulers a principled way to exploit the fact that most deep learning jobs recur, replacing user-supplied durations with learned predictions. The paper backs this with trace-driven testbed experiments and large-scale simulations reporting up to 92 percent reduction in total job completion time over existing schedulers.","feed_headline":"GPU-cluster scheduler cuts DL job completion by up to 92%","feed_subtitle":"By modeling the cluster as one machine and learning job durations, A-SRPT keeps a provable bound that weakens only as predictions err.","key_machinery":"The argument is carried by four interacting pieces. Each job is modeled as a graph $\\Omega=(V,E)$ whose vertices are stage replicas and whose edge weights are communication volumes, so placing a job becomes a graph-cut problem. Heavy-Edge is the greedy heuristic that co-locates the heaviest communicating replicas on the same server, favoring intra-server bandwidth. A random forest regression model predicts each job's training iterations $\\tilde{n}_i$ from recurrent job metadata. The central reduction maps the cluster to a single machine: job $i$'s virtual duration is $(g_i/G)\\tilde{n}_i\\tilde{\\alpha}_i^{\\min}$, SRPT schedules that virtual instance preemptively, and the completion order guides real non-preemptive placements. The competitive-ratio proof, through Lemmas 1–3 and Theorem 1, connects the virtual optimum to the real optimum by bounding placement sensitivity with $\\rho = \\max_i \\alpha_i^{\\max}/\\alpha_i^{\\min}$ and prediction error with $\\bar{\\epsilon}$.","core_discovery":"On its own terms, the paper's central claim is that the online non-preemptive DDLwMP scheduling problem can be approximated by a hypothetical single-machine preemptive instance in which each job's workload is scaled to $(g_i/G)\\tilde{n}_i\\tilde{\\alpha}_i^{\\min}$, scheduled by SRPT. The completion order of that virtual schedule is then used to dispatch real jobs onto GPUs, with communication-heavy jobs delayed and consolidated onto few servers while communication-light jobs are started immediately. Theorem 1 states that the resulting total completion time is within $(2+\\tau+\\rho G/(G-g_{\\max}))\\rho + 2\\rho g_{\\max}\\bar{\\rho}(1+\\tau+(1+\\rho)G/(G-g_{\\max}))\\bar{\\epsilon}$ of optimal, so the guarantee degrades gracefully as average prediction error grows. The paper also claims its Heavy-Edge placement is near-optimal in practice, coming within 6 percent of an ILP solution while computing in milliseconds.","pith_inferences":["Editorial inference: because the prediction model assigns zero iterations to unseen jobs, A-SRPT implicitly prioritizes first-time jobs; an ablation that reverses this choice would reveal how much of the reported gain comes from SRPT ordering versus this novelty bias.","Editorial inference: the competitive ratio depends on Heavy-Edge delivering placements close to $\\tilde{\\alpha}_i^{\\min}$; replacing it with a weaker placement heuristic in the same experiments would quantify how much of the 92 percent gain comes from placement rather than scheduling order.","Editorial inference: the single-machine reduction suggests a direct extension to tensor and expert parallelism by re-weighting the graph edges for AllReduce and token-routing traffic, a direction the paper sketches but does not evaluate."],"forward_implications":["Cluster operators can use predicted training iterations from recurring jobs and still keep a provable worst-case bound that degrades only with average prediction error, not with the worst misprediction.","Communication-heavy jobs should be delayed until they can be consolidated onto few servers, while placement-insensitive jobs should be launched immediately to absorb fragmentation; A-SRPT encodes this split with a COMM_HEAVY threshold.","The reduction to a single-machine SRPT instance provides a template for adapting the scheduler to new parallelism types: only the graph model and the per-iteration time formula need to change.","In the paper's comparisons, the gap to a perfect-prediction version is small (7 percent in the testbed and 14 percent in simulation), indicating prediction quality is not the main bottleneck to realizing the reported gains."],"supporting_citations":[{"why":"Supplies the two-month production workload trace whose recurrence statistics motivate prediction and whose jobs drive the evaluation.","marker":"[6]"},{"why":"Supplies the random-forest regression method used to predict training iterations from historical job data.","marker":"[16]"},{"why":"Supplies the optimality of SRPT for single-machine preemptive scheduling, the basis for the virtual-machine ordering.","marker":"[17]"},{"why":"Supplies the pipeline-parallel per-iteration training-time model used to compute $\\alpha_i$ and estimate $\\tilde{\\alpha}_i^{\\min}$.","marker":"[20]"},{"why":"Supplies the learning-augmented single-machine framework with untrusted predictions whose bounds the paper adapts for Lemma 3.","marker":"[29]"},{"why":"Supplies the online SRPT-to-parallel-machines framework that motivates the single-machine reduction.","marker":"[36]"},{"why":"Supplies the SPWF baseline scheduler from Tiresias used in the comparisons.","marker":"[14]"}],"fun_headline_variants":["AI job scheduler uses predictions to cut GPU cluster delays","Predictive scheduler slashes DL training completion times in GPU clusters","SRPT-inspired scheduler with predictions for distributed DL workloads","Provably efficient GPU scheduler for deep learning jobs with predictions","A-SRPT: prediction-assisted scheduler speeds up DL training on GPU clusters"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bound in Lemma 2 assumes that once jobs are placed, at least $G-g_{\\max}$ GPUs stay continuously busy on those jobs, but Algorithm 1 can advance the clock without placing anything when the head job does not fit, so the proof's busy-GPU premise may not hold for the actual schedule.","fun_headline_variants_meta":{"raw":{"variants":["AI job scheduler uses predictions to cut GPU cluster delays","Predictive scheduler slashes DL training completion times in GPU clusters","SRPT-inspired scheduler with predictions for distributed DL workloads","Provably efficient GPU scheduler for deep learning jobs with predictions","A-SRPT: prediction-assisted scheduler speeds up DL training on GPU clusters"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000386,"raw_usage":{"total_tokens":2044,"prompt_tokens":956,"completion_tokens":1088,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":1004}},"tokens_in":572,"tokens_out":1088,"duration_ms":8101,"temperature":1.0,"reasoning_tokens":1004,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:14:13.833233+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run A-SRPT on a small cluster (say two GPUs) with a trace where the first pending job needs both GPUs while a queued single-GPU job could run, and count total idle GPU time. If the measured idle time exceeds the makespan term Lemma 2 allows, then the Theorem 1 bound is not supported for the algorithm as implemented, because the busy-GPU premise in Appendix B would be violated.","supporting_citations":[{"cited_title":"MLaaS in the Wild: Workload Analysis and Scheduling in Large-Scale Heterogeneous GPU Clusters,","cited_arxiv_id":null,"evidence_quote":"Supplies the two-month production workload trace whose recurrence statistics motivate prediction and whose jobs drive the evaluation."},{"cited_title":"Random Forests,","cited_arxiv_id":null,"evidence_quote":"Supplies the random-forest regression method used to predict training iterations from historical job data."},{"cited_title":"Sequencing and Scheduling: Algorithms and Complexity,","cited_arxiv_id":null,"evidence_quote":"Supplies the optimality of SRPT for single-machine preemptive scheduling, the basis for the virtual-machine ordering."},{"cited_title":"Efficient Pipeline Planning for Expedited Distributed DNN Training,","cited_arxiv_id":null,"evidence_quote":"Supplies the pipeline-parallel per-iteration training-time model used to compute $\\alpha_i$ and estimate $\\tilde{\\alpha}_i^{\\min}$."},{"cited_title":"Scheduling with Untrusted Predictions,","cited_arxiv_id":null,"evidence_quote":"Supplies the learning-augmented single-machine framework with untrusted predictions whose bounds the paper adapts for Lemma 3."},{"cited_title":"Approximation Techniques for Average Completion Time Scheduling,","cited_arxiv_id":null,"evidence_quote":"Supplies the online SRPT-to-parallel-machines framework that motivates the single-machine reduction."},{"cited_title":"Tiresias: A GPU Cluster Manager for Distributed Deep Learning,","cited_arxiv_id":null,"evidence_quote":"Supplies the SPWF baseline scheduler from Tiresias used in the comparisons."}],"review_version":1}