acceptodds
Under review as a conference paper at ICLR 2027

Learning to Optimize Non-Clairvoyant Scheduling via Behavioral Cloning

Abstract

Large-scale cluster systems must schedule jobs whose processing times are unavailable at decision time, a challenge known as non-clairvoyant scheduling. Learning-augmented scheduling has been applied to this problem, feeding machine-learned predictions of job sizes (processing time) into classical online algorithms. However, it collapses the scheduling decision into a single predicted scalar, and the precision of induced ordering only depends on the prediction error of the processing time. In contrast, behavioral cloning has been shown to be a simple yet effective learning-to-schedule method based on imitation learning. In this paper, we propose a behavioral-cloning framework for non-clairvoyant scheduling in both the single-machine and the parallel-machine settings. Our main contributions are as follows. (1) We directly learn the scheduling policy rather than feeding predicted job sizes into a classical online algorithm, so that the scheduling decision no longer depends on the single scalar of predicted processing time only. (2) We address the variable action space that both settings share an attention-based pointer mechanism, which assigns scores to an arbitrary number of pending jobs at every decision step. (3) We conduct experiments on two practical production workloads: ATLAS and AI Spot TRAces (ASTRA), which we construct from the publicly released trace of a production GPU cluster—spanning 463,279 jobs whose size distribution is far heavier-tailed than ATLAS. The learned policy outperforms the strongest learning-augmented baselines on total completion time, maximum stretch, and makespan.

Primary area:
reinforcement learning
Keywords:
behavioral cloning, imitation-learning, non-clairvoyant scheduling, learning-augmented scheduling, attention-based pointer mechanism

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_X2hdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3(+1)
Soundness
2
Read review
Paper summary

This paper studies non-clairvoyant scheduling through behavioral cloning of clairvoyant scheduling policies. The method is evaluated on ATLAS and ASTRA, a workload constructed from a public production GPU-cluster trace. Experiments cover total completion time and maximum stretch on a single machine, and makespan on parallel machines. The reported results improve over the evaluated prediction-based baselines.

Critical strengths
  • The paper addresses a meaningful mismatch between prediction accuracy and scheduling quality. Optimizing processing-time regression does not necessarily optimize the downstream scheduling objective. Training on expert decisions is a reasonable way to introduce task-specific supervision.
  • The architecture provides a simple way to handle variable-sized pending sets.
  • The empirical improvements are promising, especially for maximum stretch. Makespan improvements appear on both workloads, and the expert-selection ablation usefully shows that the best expert to imitate can depend on the workload.
Critical weaknesses
  • The central motivation does not adequately distinguish the method from existing order-prediction approaches. The paper broadly characterizes learning-augmented scheduling as relying on scalar processing-time predictions. However, Lindermayr's Permutation Predictions for Non-Clairvoyant Scheduling explicitly predicts relative job orderings rather than processing requirements, and studies both learnability and empirical performance. Although this work is cited in the introduction, its implications for the claimed distinction are not addressed in the related-work discussion or experiments.
  • The comparisons do not cleanly isolate the benefit of decision supervision from predictor quality and baseline choice. The “without decoder” ablation uses SPRPT for the single-machine setting, whereas the strongest total-completion-time baseline in Table 1 is Meta-SPJF.
  • The parallel-machine model is not fully connected to the stated network architecture. Section 4.1 includes predicted machine loads in the state, but Section 4.3 describes global inputs as current time and pending-job count, without explaining how the machine-load vector enters the decoder. The expert-data construction should also clarify whether teacher trajectories use true or predicted machine loads and how their states correspond to those encountered by the learned policy.
  • The production-cluster interpretation is broader than the evaluated scheduling model. ASTRA contains heterogeneous GPU models and jobs requesting widely varying resources, including multi-GPU jobs, but the parallel-machine experiment assigns each job to one identical machine and releases all jobs simultaneously.
  • Scalability is not sufficiently documented. Handling an arbitrary number of jobs architecturally does not establish practical efficiency. No scheduling-latency or scaling measurements are provided despite the emphasis on thousands of pending jobs.
Questions for authors

Please refer to the weaknesses.

9 comments

Thank you for your valuable and constructive feedback.

[W1] Distinction from Existing Order-Prediction Approaches

We agree that our original characterization was too broad. The permutation-prediction model (Lindermayr & Megow, 2022) predicts relative job orderings rather than processing requirements. That work also studies the theoretical and empirical learnability of such predictions.

Permutation predictions in existing work.

Lindermayr and Megow conduct two types of experiments on synthetic job instances.

First, their sensitivity experiments construct permutation predictions by adding Gaussian noise to processing times and sorting the perturbed values. These experiments evaluate prediction robustness in single-machine and parallel-machine settings, rather than learning a ranking function from job features.

Second, their online-learning experiment considers a fixed synthetic base instance and generates successive instances by independently perturbing its job processing times. An ERM procedure uses historical instances to learn a permutation for the next round. Specifically, in the single-machine setting, it averages the historical processing times of each indexed job and sorts the jobs in ascending order of these averages. Thus, this experiment demonstrates learning a permutation, but its learned hypothesis is an ordering over a fixed set of indexed jobs, rather than a feature-based function that predicts priorities for previously unseen jobs.

Distinction from our setting and additional baseline.

The organization of ATLAS (Jiang et al., 2026) and ASTRA makes direct application of the index-based ERM procedure used for permutation predictions (Lindermayr & Megow, 2022) unsuitable. Jobs come from non-overlapping instances and time windows, so individual jobs do not recur under stable indices, leaving no aligned observations from which ERM can aggregate per-job histories. Instead, priorities must be predicted from job features to generalize across unseen jobs. Pointwise learning-to-rank provides a natural formulation: each candidate receives an independent relevance score (Lee et al., 2024). In our setting, the candidate is a job and the score is its dispatch priority; we derive per-job targets from processing times and deadlines. We therefore construct a feature-based LightGBM ranker as a task-compatible test of the order-prediction alternative, rather than a reproduction of the permutation-learning procedure in that work.

Pointwise rank-prediction baseline.

Using the same features, training data, and temporal splits as the size predictors, we fit two pointwise LGBM rankers (Ke et al., 2017) on normalized rank labels. Let FtrpF_{tr}^p and FtrdF_{tr}^d be the empirical CDFs of training processing times and synthetic deadlines. For a job jj with observed training duration pjp_j, its synthetic deadline is djd_j, obtained by adding ten times pjp_j to its block-relative submission time (the multiplier is tuned on validation). The two targets are

yjdur=Ftrp(pj),y_j^{dur}=F_{tr}^p(p_j),

yjddl=1−Ftrd(dj).y_j^{ddl}=1-F_{tr}^d(d_j).

Thus yjdury_j^{dur} is a normalized duration score and yjddly_j^{ddl} a normalized earliness score: larger values mean longer training durations and earlier synthetic deadlines, respectively. The duration model drives SPJF, SPRPT, PRR, LPPT, and SPPT, whereas the deadline model drives EDF.

At test time, each job receives a scalar rank score s^j\hat{s}_j from the LGBM model. SPJF sorts jobs by ascending duration score; PRR alternates between this order and round-robin; EDF uses descending deadline scores. For SPRPT, the score is first clipped to [0,1][0,1], then inverted through the training processing-time CDF to give a pseudo-length p^j\hat{p}_j, and the remaining time is updated as r^j(t)=p^j−ej(t)\hat{r}_j(t)=\hat{p}_j-e_j(t), with ej(t)e_j(t) the processing already received. The scheduler always dispatches the pending job with the smallest predicted remaining time. For parallel machines, LPPT/SPPT sort by pseudo-length (descending/ascending) and assign to the least-loaded machine; ground-truth test processing times are never used.

Table R2. Scheduling performance on ATLAS across three objectives, together with makespan on ASTRA; lower is better. Max-stretch on n=5,000n=5{,}000 jobs; total completion time on n=10,000n=10{,}000 jobs; makespan ratios averaged over m∈{5,10,20,50,100}m\in\{5,10,20,50,100\} and reported as ATLAS / ASTRA. Results are mean ± std over five test windows. The best learned result in each column is bolded; objective-specific reference values and bounds are also bolded.

AlgorithmρS,max⁡\rho_{S,\max}ρS,99\rho_{S,99}AlgorithmρTC\rho_{\mathrm{TC}}AlgorithmρMS\rho_{\mathrm{MS}} (ATLAS / ASTRA)
OPT (EDF at S∗S^\ast)1.00 ± 0.001.00 ± 0.00SRPT1.0000 ± 0.0000LPT1.0000 ± 0.0000 / 1.0000 ± 0.0000
SRPT1.57 ± 0.051.29 ± 0.04SJF1.0008 ± 0.0010SPT1.4864 ± 0.0820 / 1.3620 ± 0.0185
Random1.8386 ± 0.1165 / 2.3317 ± 0.1194
LGBM-SPRPT1704.47 ± 316.0749.11 ± 11.86LGBM-SPJF1.3873 ± 0.0525LGBM-SPPT1.6381 ± 0.1461 / 2.1931 ± 0.3775
LGBM-EDF1735.04 ± 326.2171.83 ± 13.06LGBM-PRR1.6201 ± 0.061LGBM-LPPT1.6499 ± 0.2464 / 2.3111 ± 0.4157
Ours102.83 ± 44.327.16 ± 3.36Ours1.1687 ± 0.0575Ours1.4346 ± 0.1533 / 1.8178 ± 0.0932

Results and interpretation (Table R2).

Table R2 provides the direct test for the order-prediction alternative. If directly predicted priorities were sufficient, the pointwise ranker combined with predefined rules would approach our method. It does not: the mean ratios are 1.1687 against 1.3873 for total completion time, 1.4346 against 1.6381 for makespan on ATLAS, and 1.8178 against 2.1931 for makespan on ASTRA. Max-stretch and 99th-percentile stretch show gaps of similar size. The pointwise rank-prediction alternative does not close the gap, indicating that the state-conditioned architecture provides benefits beyond learning a relative order.

We will revise the introduction and related-work discussion to explicitly acknowledge permutation prediction as an existing action-prediction approach and clarify its distinction from our state-conditioned policy. We will also describe the additional rank-prediction experiment and its findings in the experimental section, making clear that it complements, rather than directly reproduces, the permutation-prediction study.

References.

  1. A. Lindermayr and N. Megow. Permutation Predictions for Non-Clairvoyant Scheduling. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 357–368, 2022. DOI: 10.1145/3490148.3538579. arXiv:2202.10199.
  2. Z. Jiang, T. Zhao, C. Xia, and A. Zomaya. ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling. In International Conference on Learning Representations (ICLR), pp. 137404–137421, 2026.
  3. G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T.-Y. Liu. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. In Advances in Neural Information Processing Systems (NeurIPS), vol. 30, pp. 3146–3154, 2017.
  4. J. Lee, G. Bernier-Colborne, T. Maharaj, and S. Vajjala. Methods, Applications, and Directions of Learning-to-Rank in NLP Research. In Findings of the Association for Computational Linguistics: NAACL 2024, pp. 1900–1917, 2024.

We thank the reviewer for the helpful comments. We address the weaknesses and questions below.

[W2] The ablation does not isolate decision supervision from predictor quality and baseline choice

We agree with this observation. The strongest total-completion-time baseline, Meta-SPJF, is built on SPJF, whereas our original no-decoder row applied SPRPT. The original row therefore did not provide a rule-based control corresponding to SPJF, the rule used by the strongest baseline; consequently, it could not isolate the contribution of the learned decoder.

To address this, we re-evaluated the no-decoder variant using the non-preemptive SPJF rule, retaining the same trained processing-time predictor and evaluation settings, including the five test windows and SRPT normalization. The reported results are averages over the five test windows. The no-decoder variant attains ρTC=1.3588\rho_{\mathrm{TC}}=1.3588, whereas the full model attains 1.16871.1687, corresponding to a 14.0% reduction relative to the matched no-decoder control (lower is better). By keeping the predictor and evaluation protocol fixed, this comparison isolates the contribution of the learned decoder.

In the revised manuscript, we will update the ablation section to report the matched no-decoder result of ρTC=1.3588\rho_{\mathrm{TC}}=1.3588 and clarify that it is obtained by applying the non-preemptive SPJF rule to the same trained processing-time predictor as the full model. We will also report the complete results of applying our processing-time predictor with all learning-augmented scheduling rules across all objectives in Appendix E.

Reviewer_2hYjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper trains a scheduling policy by behavioral cloning of clairvoyant expert decisions, rather than using predicted job sizes solely to order jobs through a classical algorithm. Its attention-based pointer scores a variable-size set of pending jobs, and an auxiliary head predicts processing times. Tests on ATLAS and a production GPU-cluster trace called ASTRA show improvements over learning-augmented baselines on the reported objectives.

Critical strengths
  • The policy handles a variable action set directly. The pointer mechanism scores pending jobs at each decision, including workloads with thousands of pending jobs.
  • The evaluation includes a large production workload. ASTRA contains 463,279 jobs from a GPU-cluster trace, with a substantially heavier-tailed job-duration distribution than ATLAS.
Critical weaknesses
  • The novelty of the learning approach appears limited. The paper combines behavioral cloning, a pointer-network-style decoder, and an auxiliary processing-time prediction loss, while its main distinction is applying these components to non-clairvoyant scheduling at larger scale. The paper would benefit from a clearer account of which methodological insight is new beyond adapting established imitation-learning components to this setting.
  • After selecting a job, the method assigns it to the machine with the smallest predicted load, which is updated using that job’s predicted processing time. Thus, the learned policy avoids making job selection depend only on a scalar prediction, but the final schedule remains sensitive to prediction errors.
Questions for authors

Please see the above comments.

4 comments

Thank you for your valuable and constructive feedback.

[W1] Limited novelty of the learning approach

We agree that behavioral cloning, pointer-based job selection, and auxiliary processing-time prediction are established techniques, and we do not claim novelty in these components individually. Our methodological contribution lies in formulating scheduling as a state-conditioned dispatch decision, rather than deriving dispatch decisions from independently predicted job sizes.

Decision-oriented learning of state-dependent dispatch policies (Sections 3, 4.1, and 4.4). Minimizing per-job processing-time prediction error is not equivalent to learning effective scheduling decisions. A job's dispatch priority is not determined solely by its predicted processing time, but also depends on the pending-job set and current scheduling state. We therefore formulate the primary learning objective as directly predicting the expert's next-job selection through behavioral cloning, with processing-time regression serving as an auxiliary objective. Importantly, the role of processing-time predictions differs across the two settings: they do not enter the dispatch decision in the single-machine setting, while in the parallel-machine setting, they are used to estimate and update machine loads but do not determine job selection. Table 3 provides direct evidence for the contribution of decision-oriented learning. With the encoder and processing-time predictions held fixed, and the assignment rule unchanged in the parallel-machine setting, replacing the learned behavioral-cloning decoder with prediction-based dispatch rules degrades performance across all objectives. This degradation demonstrates the additional contribution of the behavioral-cloning decoder: it learns job-selection decisions conditioned on the pending-job set and scheduling state, beyond what can be achieved using the encoder's predictions and predefined scheduling rules.

Set-conditioned modeling of dispatch decisions (Sections 4.1–4.3). The policy must score each job relative to the pending set, whose size varies and can reach thousands. We pool the set permutation-invariantly into a context and score jobs by query-key attention, with the context as the query and each runtime-augmented job embedding as a key. The score is thus not an absolute per-job estimate but a comparison against the current pending set, and the softmax over pending jobs makes it a relative priority order rather than a scalar to be sorted. The same scorer serves both settings; only the transition differs. The MLP-scorer ablation keeps the same embeddings and pooled context but removes the query-key comparison; its consistent degradation, including makespan on ATLAS and ASTRA, shows that the benefit comes from the query-key context--candidate interaction, not from pooled context alone.

Empirical validation across scheduling settings and workload characteristics (Sections 5.1–5.4). We construct ASTRA from a production GPU-cluster trace (Duan et al., 2026), which exhibits a substantially heavier-tailed job-size distribution than ATLAS, and evaluate our method on both workloads. Our method achieves the best performance among learned methods across all evaluated objectives and outperforms the strongest learning-augmented baseline (Table 1), with particularly substantial gains in max-stretch. The case study in Section 5.4 further illustrates the contrast: prediction-based ordering propagates processing-time prediction errors into subsequent machine assignments, whereas our policy makes dispatch decisions conditioned on the current scheduling state.

We will revise the abstract, introduction, and method overview to more clearly articulate the methodological contribution of our approach and distinguish it from existing learning-augmented methods.

References.

  1. J. Duan, S. Xu, S. Qian, D. Yang, K. Wang, C. Liao, Y. Yu, Q. Hua, H. Hu, Q. Wang, W. Wu, D. Bao, T. Lu, J. Cao, G. Xue, G. Yang, L. Zhang, and G. Chen. GFS: A Preemption-aware Scheduling Framework for GPU Clusters with Predictive Spot Instance Management. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Volume 1, pp. 117–131, 2026. DOI: 10.1145/3760250.3762231.

We thank the reviewer for the helpful comments.

[W2] The final schedule remains sensitive to prediction errors

We agree that prediction errors remain in the pipeline. In the parallel-machine setting, a selected job must still be assigned, and the assignment needs a load estimate. True durations are unknown until completion, so the estimate must come from predicted processing times: without p^j\hat{p}_j, the least-loaded rule has no load signal. Thus, prediction errors can still affect machine assignment. The distinction is that learning-augmented scheduling baselines use predicted processing times for both job selection and machine assignment, whereas our method uses them only for assignment.

Prediction-error sensitivity. To examine the impact of prediction noise, we inject multiplicative lognormal noise into the predicted processing times on ATLAS:

p^i(s)=max⁡(ϵ,,p^iexp⁡(szi)),\hat p_i^{(s)} = \max(\epsilon,\\, \hat p_i\exp(s z_i)),

where p^i\hat p_i is the original predicted processing time, ss controls the noise magnitude, and ziz_i is drawn from a standard normal distribution and fixed for each job set across noise levels. Thus, s=0s=0 recovers the original predictions, while larger values introduce stronger multiplicative perturbations. We keep all trained model parameters fixed and do not retrain either method. The perturbed estimates are used by every prediction-dependent component: both job selection and machine assignment for LPPT, but only machine assignment for our method. Makespan is evaluated using the true processing times and normalized by the same preemptive lower bound computed from them. The true processing times are not supplied as additional policy inputs.

Table R4. Sensitivity to multiplicative lognormal prediction noise on ATLAS (multi-machine makespan). For each test window, we first average the makespan ratios across the five machine counts m∈{5,10,20,50,100}m\in\{5,10,20,50,100\}, and then report the mean ± std across the five test windows. The same noise realization is used for each job set across noise levels. Lower is better.

Methods=0.0s=0.0s=0.25s=0.25s=0.5s=0.5s=0.75s=0.75s=1.0s=1.0
Meta-LPPT1.603 ± 0.3111.552 ± 0.2321.627 ± 0.2631.703 ± 0.2601.809 ± 0.288
CQR-LPPT1.661 ± 0.3161.661 ± 0.3181.668 ± 0.2561.763 ± 0.2831.797 ± 0.273
Rec-LPPT1.642 ± 0.2881.670 ± 0.2401.705 ± 0.2761.804 ± 0.2491.765 ± 0.304
TwoSt-LPPT1.649 ± 0.3131.616 ± 0.2671.662 ± 0.2651.728 ± 0.2791.812 ± 0.259
Iso-LPPT1.619 ± 0.2801.612 ± 0.2221.682 ± 0.2281.721 ± 0.2471.844 ± 0.316
HRAS-LPPT1.687 ± 0.2021.710 ± 0.2881.767 ± 0.3251.814 ± 0.3071.853 ± 0.299
Ours1.4346 ± 0.15331.484 ± 0.2221.526 ± 0.3191.497 ± 0.2081.627 ± 0.332

At the original prediction estimates ((s=0)), our method already achieves a lower mean makespan ratio than all LPPT variants. As the multiplicative noise increases, our method's makespan ratio exhibits some variation and increases at the highest noise level, confirming that machine assignment remains affected by prediction errors. Nevertheless, our method consistently achieves lower mean makespan ratios than all LPPT variants across the tested noise levels. This difference is consistent with the distinct roles of predicted processing times in the two methods: in LPPT, prediction errors affect both job selection and machine assignment, whereas in our method, they affect only machine assignment. These results show that, although our method does not eliminate prediction-error sensitivity, its performance advantage over prediction-based dispatch rules persists under the tested levels of multiplicative noise.

We will incorporate this prediction-error sensitivity analysis, including Table R4 and the corresponding discussion, into the revised manuscript.

I remain concerned about novelty. This work appears to offer no new insights to the community, and I will keep my score unchanged.

Thank you for taking the time to read our rebuttal and for your continued consideration of our work. We would like to take this opportunity to further clarify the contributions of our work. Our work proposes a behavioral-cloning framework for non-clairvoyant scheduling that directly learns a job-selection policy from expert demonstrations.

First, a new learning formulation for job-selection decisions. Most learning-augmented scheduling methods use predicted job sizes to guide online scheduling decisions, separating the prediction objective from the ultimate scheduling objective. Although some approaches directly predict the relative ordering of jobs, they restrict their hypothesis class to permutations over a fixed set of indexed jobs, which limits generalization to unseen jobs and to pending sets whose membership changes as jobs arrive and complete. In contrast, we directly learn the expert's next-job selection based on job features rather than fixed job indices, enabling the policy to generalize to unseen jobs and dynamically changing pending sets. The expert's selection serves as the primary supervision target, while predicted job size is retained as an auxiliary objective, allowing the policy to account for both the pending-job set and the current scheduling state.

Second, a context-dependent job-selection mechanism. We develop an attention-based pointer decoder that evaluates each pending job in the context of the entire pending set. By explicitly modeling the query-key interaction between each pending job and the pending-set context, the decoder learns state-dependent job selection over variable-sized action spaces, including those with thousands of pending jobs. In the revised manuscript, we further investigate the source of our performance gains. The decoder ablation in Table 3 shows that replacing our learned decoder with learning-augmented scheduling rules degrades performance even when the encoder and its processing-time predictions are held fixed. The rank-prediction baselines in Table 4 show that directly learning relative job priorities and applying predefined scheduling rules does not achieve comparable performance. Together, these results show that our gains are not attributable solely to encoder predictions or to learning relative job rankings, highlighting the contribution of the learned state-dependent job-selection policy.

Third, a single framework across scheduling settings. Our framework applies to both single-machine and parallel-machine scheduling, accommodating their different uses of processing-time information while retaining a common approach to learning job-selection policies.

Fourth, comprehensive empirical evaluation. We construct ASTRA from an open-source production GPU-cluster trace, providing a workload with substantially heavier-tailed job-size distributions than ATLAS. Extensive experiments across both workloads demonstrate the effectiveness of our approach in minimizing maximum stretch and total completion time in single-machine scheduling, as well as makespan in parallel-machine scheduling.

Thank you again for your thoughtful feedback. We hope these clarifications better convey the motivation, methodological contributions, and empirical significance of our work.

Reviewer_G6MwOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes behavioral cloning for non-clairvoyant scheduling as an alternative to feeding predicted job sizes into classical online algorithms. A Transformer encodes each pending job’s submission-time features, and an attention-based pointer decoder, which also sees runtime information such as attained service, selects the next job by imitating a clairvoyant expert (EDF, SRPT, LPT or SPT, depending on the objective). Predicted processing time is learned as an auxiliary target and is used to assign jobs to machines in the parallel setting. Experiments on ATLAS (total completion time, maximum stretch, and makespan) and on ASTRA, a heavy-tailed GPU workload the authors build from a public trace (makespan only), show gains over the learning-augmented baselines, with ablations on the choice of expert and on the decoder.

Critical strengths
  1. The paper provides a simple alternative to predict-then-schedule with a clear payoff. Imitating a clairvoyant expert lets the policy use the whole pending set and runtime information, rather than a single predicted size per job. The gain is largest on maximum stretch, where the prediction-based baselines are highly sensitive to a few badly mispredicted jobs

  2. While this field has advanced theoretical knowledge, real traces and workloads might be very different from the assumed theoretical settings. Under this context, I appreciate the evaluation on real production traces, including a new GPU workload, with a time-based split and ablations that isolate the choice of expert and the role of the decoder.

Critical weaknesses
  1. The evidence for the main claims is thin. Results come from one sampled instance per setting, without repeated runs or variance. On total completion time, the gain over the best baseline is about 1%, an incremental improvement that a single run cannot establish. On maximum stretch, the gain is large, but the metric is determined by a single job and can vary substantially across instances. Total completion time and maximum stretch are also tested on ATLAS only, under the same setting as the ATLAS benchmark. I understand that this keeps the comparison consistent with the ATLAS baselines, but those baselines are a starting point. A new method should show either clear gains that hold over repeated runs or an advantage that persists in harder settings, e.g., other time windows, other workloads, or online arrivals on multiple machines. Results with means and standard deviations over several test windows are needed.

  2. The experiments cannot tell why the method wins. The method learns which job to run next by cloning an expert with a pointer decoder, whereas all learning-augmented baselines first predict job sizes and then schedule by them. The gains have two possible explanations: (a) the behavioral-cloning framework is better, as the paper claims; or (b) it is enough to learn the order of jobs instead of their sizes, without this framework. Because every baseline predicts sizes, the results cannot distinguish (a) from (b). Rank-based methods, which predict the order of jobs directly, would settle this; the paper cites one, permutation predictions (Lindermayr & Megow, 2022), but does not compare with it. If the paper’s framework performs close to such rank-based methods, the gains come mainly from learning the order, and the framework adds little. If it is clearly better, the framework itself is shown to be useful.

Questions for authors

Please address the two weaknesses above.

Minor: The experimental section follows the ATLAS benchmark (Jiang et al., 2026) almost exactly, with the same settings, baselines, table layout, and baseline numbers. Reusing the benchmark is reasonable, but please state which results are reproduced from ATLAS and organize the experiments around the paper’s own claims, for example, what the learned policy does differently from size-based rules, so that the new contribution is easier to see.

If the authors address the weaknesses and questions above, I am willing to raise my score.

8 comments

Thank you for your valuable and constructive feedback.

[W1] The evidence for the main claims is thin

We agree that the original evaluation, based on a single sampled instance per setting, did not sufficiently characterize performance variability or establish the generality of our findings. We therefore extended the evaluation to five distinct test windows, using ATLAS to assess result variability and ASTRA to examine the generality of our findings across workloads.

To address the concern about result variability, we evaluated all methods across five distinct ATLAS test windows and report mean ± standard deviation for every evaluated metric. To examine cross-workload generality, we additionally evaluate parallel-machine makespan on ASTRA, also reporting mean ± standard deviation across five test windows. The results are summarized in Table R1.

Table R1. Scheduling performance on ATLAS across three objectives, together with makespan on ASTRA; lower is better. Max-stretch on n=5,000n=5{,}000 jobs; total completion time on n=10,000n=10{,}000 jobs; makespan ratios averaged over m∈{5,10,20,50,100}m\in\{5,10,20,50,100\} and reported as ATLAS / ASTRA. Results are mean ± std over five test windows; reference and best results are bolded.

AlgorithmρS,max⁡\rho_{S,\max}ρS,99\rho_{S,99}AlgorithmρTC\rho_{\mathrm{TC}}AlgorithmρMS\rho_{\mathrm{MS}} (ATLAS / ASTRA)
(A) Max-stretch(B) Total completion time(C) Makespan
OPT (EDF at S∗S^*)1.00 ± 0.001.00 ± 0.00SRPT1.0000 ± 0.0000LPT1.0000 ± 0.0000 / 1.0000 ± 0.0000
SRPT1.57 ± 0.051.29 ± 0.04SJF1.0008 ± 0.0010SPT1.4864 ± 0.0820 / 1.3620 ± 0.0185
LAS/FB191.83 ± 17.37130.94 ± 12.85RR1.6803 ± 0.0080Random1.8386 ± 0.1165 / 2.3317 ± 0.1194
FIFO4.3532 ± 0.1218
CQR-SPRPT2186.39 ± 413.4731.91 ± 13.02CQR-SPJF1.3946 ± 0.0410CQR-LPPT1.6611 ± 0.0366 / 2.0684 ± 0.1756
CQR-EDF2351.71 ± 442.51241.49 ± 44.44CQR-PRR1.5972 ± 0.0521CQR-SPPT1.6768 ± 0.0684 / 2.2380 ± 0.2792
HRAS-SPRPT1282.70 ± 94.52272.82 ± 43.37HRAS-SPJF1.8275 ± 0.0506HRAS-LPPT1.6866 ± 0.0756 / 2.4950 ± 0.3300
HRAS-EDF2435.27 ± 416.49940.84 ± 75.91HRAS-PRR1.9624 ± 0.0493HRAS-SPPT1.7973 ± 0.0872 / 2.1305 ± 0.1560
Iso-SPRPT2211.37 ± 444.35112.72 ± 33.02Iso-SPJF1.4588 ± 0.0487Iso-LPPT1.6188 ± 0.1096 / 2.5901 ± 0.2831
Iso-EDF2407.63 ± 437.42332.73 ± 49.55Iso-PRR1.6753 ± 0.0591Iso-SPPT1.7165 ± 0.1364 / 2.3103 ± 0.2060
Meta-SPRPT2332.87 ± 438.0926.51 ± 23.32Meta-SPJF1.3238 ± 0.0361Meta-LPPT1.6033 ± 0.1790 / 2.1549 ± 0.2187
Meta-EDF2452.87 ± 470.42123.38 ± 24.42Meta-PRR1.5119 ± 0.0419Meta-SPPT1.6664 ± 0.0918 / 2.1574 ± 0.2303
TwoSt-SPRPT2102.24 ± 429.7738.95 ± 13.81TwoSt-SPJF1.4278 ± 0.0466TwoSt-LPPT1.6492 ± 0.0680 / 2.3290 ± 0.1381
TwoSt-EDF2262.24 ± 455.73302.15 ± 42.54TwoSt-PRR1.6394 ± 0.0594TwoSt-SPPT1.6604 ± 0.0408 / 2.1591 ± 0.2469
Rec-SPRPT2487.18 ± 456.6228.33 ± 12.34Rec-SPJF1.3999 ± 0.0470Rec-LPPT1.6416 ± 0.1771 / 2.2967 ± 0.1592
Rec-EDF2657.81 ± 490.32272.44 ± 33.11Rec-PRR1.5932 ± 0.0538Rec-SPPT1.7286 ± 0.0941 / 2.1930 ± 0.1431
Ours102.83 ± 44.327.16 ± 3.36Ours1.1687 ± 0.0575Ours1.4346 ± 0.1533 / 1.8178 ± 0.0932

The results provide additional evidence of the performance advantage across different test windows. For total completion time, our method achieves a mean ratio of 1.1687 ± 0.0575, compared with 1.3238 ± 0.0361 for Meta-SPJF, the strongest learning-augmented baseline. This corresponds to an 11.7% reduction in the mean ratio, substantially larger than the approximately 1% improvement observed in the original single-window evaluation. This difference suggests that the original randomly sampled window did not fully capture the performance advantage of our method. Evaluating across five windows provides a more representative assessment while also accounting for performance variability.

For maximum stretch, our method achieves 102.83 ± 44.32, compared with 191.83 ± 17.37 for LAS/FB. We acknowledge that the standard deviation of maximum stretch remains relatively large, reflecting the sensitivity of this worst-case metric to individual jobs and workload variations. To further examine whether the improvement is limited to the single worst-served job, we also report the 99th-percentile stretch. Our method achieves 7.16 ± 3.36, substantially lower than 26.51 ± 23.32 for Meta-SPRPT. This complementary result indicates that the improvement extends beyond the single most extreme job and is also evident in the broader tail of the stretch distribution.

We further examine the generality of the method across workloads through parallel-machine makespan evaluation. On ATLAS, our method achieves a mean ratio of 1.4346 ± 0.1533, compared with 1.6033 ± 0.1790 for Meta-LPPT, corresponding to a 10.5% reduction. On ASTRA, it achieves 1.8178 ± 0.0932, compared with 2.0684 ± 0.1756 for CQR-LPPT, yielding a 12.1% reduction. In both workloads, our method obtains the lowest mean ratio among the learning-augmented methods. This result is particularly relevant because ASTRA is derived from Alibaba's production GPU-cluster trace and has a substantially more heavy-tailed job-size distribution than ATLAS. The performance advantage is therefore maintained not only across different test windows but also on a workload with markedly different statistical characteristics.

We report only makespan on ASTRA because its production workload and scheduling assumptions differ from those underlying the two single-machine objectives on ATLAS. These differences arise at both the cluster and job levels.

At the cluster level, ASTRA is drawn from a multi-tenant production GPU cluster, where jobs from different tenants are submitted and scheduled onto the cluster's GPUs (Duan et al., 2026). This naturally calls for a parallel-machine formulation: scheduling involves assigning jobs across multiple machines rather than sequencing them on a single machine. A single-machine model would serialize the jobs and fail to capture this concurrent execution and machine-assignment structure. For comparability with the ATLAS benchmark (Jiang et al., 2026, §3.3), we adopt its job-level reduction, treating each trace job as one scheduling unit on identical parallel machines. At the job level, most ASTRA jobs are large-model tasks, such as LLM training and online inference. These high-priority jobs are not evicted once placed and are subject to strict service-level objectives. The preemptive single-machine formulations underlying ATLAS's total-completion-time and maximum-stretch objectives do not directly match this setting. We therefore model them as non-preemptive, run-to-completion tasks and restrict the ASTRA evaluation to makespan under the adopted non-preemptive parallel-machine formulation.

Regarding online arrivals on multiple machines, our current evaluation follows the batch-release (P∥Cmax⁡P\Vert C_{\max}) formulation of ATLAS, under which the LPPT/SPPT baselines and McNaughton's bound (McNaughton, 1959) are defined. Extending it to (P∣rj∣Cmax⁡P|r_j|C_{\max}) would require arrival-triggered decisions, release-aware baselines and lower bounds, and training on arrival streams (e.g., Bampis et al., 2023). This constitutes a different scheduling formulation rather than a direct extension of the current evaluation. We will identify it as an important direction for future work.

We will incorporate the mean ± standard deviation results into the main results (Table 1) and ablation tables (Tables 2–3) of the revised manuscript, and update the corresponding discussions and future work.

References.

  1. J. Duan, S. Xu, S. Qian, D. Yang, K. Wang, C. Liao, Y. Yu, Q. Hua, H. Hu, Q. Wang, W. Wu, D. Bao, T. Lu, J. Cao, G. Xue, G. Yang, L. Zhang, and G. Chen. GFS: A Preemption-aware Scheduling Framework for GPU Clusters with Predictive Spot Instance Management. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Volume 1, pp. 117–131, 2026. DOI: 10.1145/3760250.3762231.
  2. Z. Jiang, T. Zhao, C. Xia, and A. Zomaya. ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling. In International Conference on Learning Representations (ICLR), pp. 137404–137421, 2026.
  3. E. Bampis, A. Kononov, G. Lucarelli, and F. Pascual. Non-Clairvoyant Makespan Minimization Scheduling with Predictions. In 34th International Symposium on Algorithms and Computation (ISAAC), LIPIcs 283, Article 9, pp. 9:1–9:15, 2023. DOI: 10.4230/LIPIcs.ISAAC.2023.9.
  4. R. McNaughton. Scheduling with Deadlines and Loss Functions. Management Science, 6(1):1–12, 1959.

We thank the reviewer for the helpful comments. We address the weaknesses and questions below.

[W2] The experiments cannot tell why the method wins

We agree that the original size-prediction baselines, which pair learned size predictors with classical prediction-based rules (Purohit et al., 2018; Im et al., 2021; Bampis et al., 2023; Zhao et al., 2025; Zhao and Zomaya, 2026) and follow the ATLAS predictor protocol (Jiang et al., 2026), cannot distinguish whether the observed gains arise from learning job priorities directly or from the state-conditioned behavioral-cloning framework itself. To address this concern, we introduce a rank-prediction baseline that learns per-job ranking scores and applies predefined scheduling rules. This additional comparison allows us to examine whether replacing processing-time prediction with direct priority prediction can account for the improvements of our method.

Relation to LM22 and its applicability. Lindermayr and Megow study permutation predictions for non-clairvoyant scheduling (Lindermayr & Megow, 2022). Their PAC hypothesis class consists of all permutations over a fixed set of nn indexed jobs (Secs. 2.2 and 4). Although their scheduling model allows online job arrivals, their online-learning experiment relies on repeated, index-aligned observations for ERM: it fixes a synthetic base instance and generates noisy copies over successive rounds while preserving job indices. In each round, ERM uses previous instances, allowing information to be aggregated across corresponding jobs. Related work predicts a weight order over front jobs under online precedence constraints (Lassota et al., 2023), but it likewise does not provide a feature-to-priority map for a time-disjoint stream. In contrast, ATLAS (Jiang et al., 2026) and ASTRA are time-disjoint streams in which each job appears only once, so the repeated index-aligned observations required by this experimental learning procedure are unavailable. Therefore, we do not reproduce the permutation-learning procedure. Instead, we adopt a feature-based pointwise ranking formulation to instantiate the alternative of direct job-priority prediction under our scheduling setting.

Pointwise rank-prediction baseline. Pointwise learning-to-rank is a rank-based method: it trains a model to score each candidate independently against a per-candidate target (Lee et al., 2024). Following this formulation, we construct a feature-based rank-prediction baseline using LightGBM. Specifically, instead of predicting raw processing times, it learns normalized rank scores derived from the empirical distributions of training processing times and synthetic deadlines. At inference, the predicted scores induce an ordering of available jobs, which is used by predefined scheduling rules. This provides a pointwise rank-based baseline for learning per-job priorities, using LightGBM as the base learner and retaining the same per-job input features and temporal splitting protocol. Unlike permutation predictions over a fixed indexed job set, this feature-to-rank mapping can assign priorities to previously unseen jobs in time-disjoint streams.

Rank-based LGBM implementation. We train two separate pointwise LGBM regressors on the same features, data, and temporal splits as the size-prediction baselines, using normalized rank labels. Let FtrpF_{tr}^p and FtrdF_{tr}^d denote the empirical CDFs of training processing times and synthetic deadlines, respectively. For each job jj, let pjp_j be its observed processing time in the training split, and let djd_j be a synthetic deadline obtained by adding ten times pjp_j to the job's block-relative submission time; the factor 10 is chosen on validation. We define two targets on a common [0,1][0,1] scale:

yjdur=Ftrp(pj)y_j^{dur}=F_{tr}^p(p_j)

yjddl=1−Ftrd(dj)y_j^{ddl}=1-F_{tr}^d(d_j)

where yjdury_j^{dur} and yjddly_j^{ddl} are the duration and deadline targets for job jj; a larger duration target indicates a longer training duration, and a larger deadline target indicates an earlier synthetic deadline. Duration-based rules (SPJF, SPRPT, PRR, LPPT, and SPPT) use the duration model, while EDF uses the deadline model.

At inference, LGBM outputs a real-valued rank score s^j\hat{s}_j. SPJF ranks jobs by ascending duration scores, while PRR interleaves the predicted shortest-job order with round-robin selection. For SPRPT, we clip the predicted score to the interval [0,1][0,1] and map it through the inverse empirical CDF of training processing times to obtain a pseudo-length p^j\hat{p}_j. The predicted remaining time is updated as r^j(t)=p^j−ej(t)\hat{r}_j(t)=\hat{p}_j-e_j(t), where ej(t)e_j(t) is the cumulative processing received by job jj; the scheduler preemptively selects the job with the smallest predicted remaining time. EDF ranks jobs by descending deadline scores.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.