acceptodds
Under review as a conference paper at ICLR 2027

How to Use Predictions? Dependence-Aware Scheduling with Runtime Distributions

Abstract

Non-clairvoyant schedulers choose which task to run before its runtime is known. Runtime histories can help estimate a runtime distribution for each task. Using these distributions separately misses what a completed task's runtime reveals about unfinished tasks. When runtimes are dependent, that information can change which task should run next. This raises the question: how should a scheduler use a predicted runtime distribution to choose its next action as tasks complete? We introduce a scheduler that updates a predicted joint runtime distribution using completed runtimes and the time unfinished tasks have already run. It then chooses the action with the lowest expected remaining workflow completion cost. We show that ignoring runtime dependence can increase expected total workflow completion time. Both predictions have the correct runtime distribution for each task and are passed to the same exact scheduling algorithm. We bound how prediction error affects cost relative to an optimal scheduler that knows the true distribution. From complete histories, *Truncated Joint Fitting (TJF)* caps long runtimes while preserving task pairings. For fixed model parameters and a bounded second moment of total runtime, TJF attains expected excess cost for under arbitrary dependence among task runtimes. A matching worst-case lower bound shows this exponent is unavoidable, while fitting tasks separately under independence attains . In a constructed four-task offline replay using recorded Alibaba runtimes, an uncapped empirical joint prediction reduces total workflow completion time by 13.94% across 1,796 held-out batches relative to independent prediction with the same task marginals.

Primary area:
learning theory
Keywords:
Non-clairvoyant scheduling, learning-augmented scheduling, runtime dependence, joint distribution estimation, sample complexity

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_uH79OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to use dependencies among task runtimes to improve non-clairvoyant workflow scheduling. The authors use joint runtime distributions to update predictions based on observed task runtimes and apply dynamic programming to minimize the expected sum of workflow completion times. They also propose Truncated Joint Fitting (TJF) to estimate the joint distribution and provide matching upper and lower bounds on the expected excess scheduling cost. The experiments use runtime traces from Alibaba and Shell Chronos, with scheduling evaluations mainly conducted on constructed four-task workflows. Compared with independent prediction, untruncated joint prediction reduces total completion time by 13.94%, while TJF achieves a 0.54% improvement under the prescribed truncation setting.

Critical strengths

S1. The paper provides theoretical analysis of scheduling with dependent task runtimes, including matching upper and lower bounds on the expected excess scheduling cost.

Critical weaknesses

W1. Insufficient baselines. The experiments only compare against independent prediction and fixed-order scheduling, without including any existing scheduling methods from prior work.

W2. Limited empirical gains. The reported 13.94% improvement is heavily influenced by a single batch, while the proposed TJF method achieves only a 0.54% improvement under the prescribed setting.

W3. Limited scalability. Experiments are restricted to constructed four-task workflows, and the scalability of the exact dynamic programming approach is not evaluated.

Questions for authors

Q1. On the same 1,796 test batches, add a baseline that estimates each terminal task's conditional mean runtime from the two predecessor runtimes (any standard regressor or nearest-neighbour estimate) and orders by it, with the same bootstrap interval.

Q2. Report the distribution of per-batch savings for the uncapped joint prediction (for example, total savings with the top 1, 5 and 20 batches removed), and the eightfold-cap result on the 1,794 development batches, where the cap is chosen without seeing test outcomes.

Q3. Does any cap chosen from h alone, as Theorem 4 requires, give a gain beyond the five-draw spread at any history size, or on the Shell or Alibaba three-task cohorts of Figure 3(a)? If not, how should the cap be chosen under heavy-tailed runtimes?

4 comments
AuthorsOpenReview ↗

Author Response (1/2)

We thank the reviewer for highlighting the matching upper and lower bounds on expected excess scheduling cost. We also appreciate the concrete suggestions to add a conditional mean baseline and to examine how much of the total savings comes from the most influential batches. We respond to each point below.

Q1/W1

Original experimental setup and updates. Section 5.2 used independent prediction and fixed-order scheduling as baselines to test the benefit described in Theorem 1. Ordering by conditional mean runtimes can reduce expected total completion time when predecessor runtimes change which terminal task is expected to be shorter. To isolate this benefit, each terminal task had to run to completion once started, so the baseline comparisons focused on which initial order saved more time. To test whether feedback during execution could save time, the supplementary experiment let the joint and independent prediction schedulers continue or switch if a terminal task had run for some time without finishing.

Changes to the test batches. The original experiment used the time from start to finish for a single task instance. To evaluate stage-level scheduling, the supplementary experiment used the time from start to finish for the entire stage. The baselines estimate the runtime of each terminal stage and use those estimates to set the order. When one instance finishes, others in the same stage may still be running, so the runtime of a single instance does not tell us when the whole stage finishes.

Supplementary baseline experiment. We evaluated nearest neighbour and gradient boosting regression as additional baselines. Both use the same two predecessor runtimes to estimate each terminal task's conditional mean runtime. They then run the tasks to completion in increasing order of these estimates. All methods in the supplementary experiment used the same 1,796 test batches. We followed the original 95% paired bootstrap procedure, resampling whole batches 5,000 times.

Table 1. Baseline

MethodTotal completion time (s)Savings vs. independent prediction95% paired bootstrap interval
Independent prediction853,612––
Nearest neighbour846,5310.83%[−1.97%-1.97\%, 3.20%3.20\%]
Gradient boosting regression849,6110.47%[−2.43%-2.43\%, 2.86%2.86\%]
Joint prediction828,7102.92%[1.45%, 4.54%]

Joint prediction had the shortest total completion time in Table 1. With independent prediction as the reference, the time saved by joint prediction was 3.52 times the time saved by nearest neighbour and 6.22 times the time saved by gradient boosting regression. These gains support the central idea of our work that accounting for dependence between task runtimes can help a scheduler make better decisions as it receives new feedback during execution.

Revision We will add the baseline comparisons to the appendix.

Q2

Distribution of per-batch savings. On the 1,796 test batches from the Q1 experiment, we ranked the batches by the time joint prediction saved relative to independent prediction. We removed the batches with the largest savings and recalculated each method's savings relative to independent prediction on the same remaining batches.

Table 2. the distribution of per-batch savings for the uncapped joint prediction

Test batchesJoint prediction (Seconds)Joint prediction (%)Nearest neighbour (Seconds)Nearest neighbour (%)Gradient boosting regression (Seconds)Gradient boosting regression (%)
All 1,796 batches24,9022.927,0810.834,0010.47
Top 1 removed19,0912.351,2700.16−1,810-1,810−0.22-0.22
Top 5 removed11,5901.48−6,265-6,265−0.80-0.80−9,345-9,345−1.19-1.19
Top 20 removed5,0800.68−11,691-11,691−1.56-1.56−15,226-15,226−2.04-2.04

After we removed the 20 batches with the largest savings, joint prediction still saved 5,080 seconds. Both baselines took longer than independent prediction on the remaining batches.

Eightfold cap. We identified a set of 1,794 development batches. Before examining the test results, we selected the eightfold cap based on total completion time on these batches. Total completion time on the development batches tells us whether keeping longer runtimes helps the scheduler choose a better order for the terminal tasks. The same rule lets us choose a cap before testing for workflows with different runtime patterns. After locking the 64 s cap, we evaluated it on a separate set of 2,048 held-out test batches.

Table 3. the eightfold-cap result on the 1,794 development batches

Formula cap 8 secondsEightfold cap 64 secondsTime saved with the eightfold cap
179,870 s173,292 s6,578 s, 3.66%

Revision We will add the per-batch savings and the eightfold cap results to the appendix.

AuthorsOpenReview ↗

Author Response (2/2)

Q3

Yes. In the original four-task offline experiment, the formula in Theorem 4 gives a cap of 8 seconds when the history size is h=4,096h=4,096 batches. Across the five draws, TJF's longest total completion time was 102,481 seconds, still 104 seconds less than the shortest time of 102,585 seconds for independent prediction with the same cap. This shows that at this history size, TJF with the formula cap can achieve a gain beyond the five-draw spread.

Choosing the cap under heavy-tailed runtimes We ran an offline experiment using Snowset's public query logs. In the holdout logs, the median query execution time was 0.95 seconds and the 99th percentile was 6.72 seconds. This is about seven times the median, so the runtime distribution in these logs shows heavy-tailed behavior. We compared several caps using only the development set and chose the one that gave TJF the shortest total completion time, breaking ties in favor of the smaller cap. This gave a 2.4-second cap, which we fixed before testing it on the holdout logs. Snowset data source

TJF with the 2.4-second cap compared withTotal completion time savedPaired 95% interval with refitting and cap reselectionTime still saved after removing the batch with the largest saving in each comparison
TJF with the 0.4-second formula cap575.834 s, 3.35%480.032 to 650.294 s572.281 s
Independent prediction with the same 2.4-second cap920.632 s, 5.25%780.654 to 1,025.912 s877.175 s

Revision We will add the formula cap results and explain how we selected the cap on Snowset in the appendix.

W2

We added controlled JSON experiments with new test data and different training histories at a truncation level of 6.4 ms selected using only the development set, as detailed in Tables 1 and 2 of our response to Reviewer XYEW's Q1/W1. Compared with independent prediction, joint prediction saved 9.06% on new test data, 8.94% after removing the batch with the largest saving, and 8.86% to 10.61% across eight independent fits. In these supplementary experiments, the savings from joint prediction could be reproduced across different training histories with the truncation level held fixed.

W3

We added experiments on workflows from Alibaba production logs to extend the evaluation of exact dynamic programming from 4 to 15 tasks, as detailed in Table 3 in Part 1 of our response to Reviewer XYEW's Q2/W2. In the 15-task non-preemptive setting, all three runs completed exact planning, with a median total planning time of 12.160 s and a maximum peak memory of 1,235.31 MiB. State encoding and contiguous storage improved the practical scalability of exact dynamic programming, allowing it to handle more tasks within the same memory budget.

We hope the added baseline comparisons and the analyses of per-batch savings and truncation address your concerns about the experimental evidence, and we would be grateful if you would consider raising your score.

Reviewer_uH79OpenReview ↗

Limited gains in practice.

Thank you for your reply. The new experiments confirmed my suspicions: Join prediction achieves a 2.92% gain, compared to 0.83% for NN. Moreover, in 1796 batches, only 20 of them carry 80% of the savings. While the ideas described in the paper are interesting, I am not impressed by the savings in practice. Therefore, I will maintain my score.

AuthorsOpenReview ↗

Further Response

Thank you for actively engaging in the discussion and for stating your concern so clearly! Your comment shows us that our previous reply may have suggested the small and concentrated gain reflects a weakness of the method, while it comes from how rarely this dataset offers decisions where runtime feedback matters. We will explain this below.

Why 20 batches accounted for about 80% of the net savings. The concentration comes from the dataset. In most batches, the two terminal tasks ran for similar times, so their order barely mattered. Most of the savings came from 244 of the 1,796 batches, or 13.6%, where the two policies disagreed at a checkpoint on whether to continue or switch. These batches included 19 of the top 20 and accounted for 78.3% of the net savings, with joint prediction saving 6.52% within them. When such decisions are common, as in the Snowset experiment below, the savings are larger and spread across batches.

Practical settings where our work applies. Our method helps most when an early runtime tells the scheduler how long later tasks will take. We chose the Alibaba dataset to isolate this effect: both policies used the same scheduler and the same task marginals, so any difference came from using the dependence. The effect is small in this dataset because early runtimes rarely change the order, but it can be strong in a cloud data warehouse. There, a query’s compilation time can indicate how long it will execute, so observing it can change which queued query should run first. Production systems already act on runtime feedback, as Spark SQL adjusts execution plans [2] and Mantri restarts slow tasks [1]. Our Snowset experiment below tests this setting.

Supplementary Snowset experiment. If you would like to see how much time our method can save in a real setting suited to it, we ran an additional experiment using real query logs from Snowset [3].

Table 1. Time savings on the Snowset query logs

MethodTime savings relative to independent prediction95% paired block bootstrap interval
Joint prediction7.24%[6.98%, 7.47%]
Nearest neighbour0.47%[0.12%, 0.82%]
Gradient boosting regression0.53%[0.39%, 0.66%]

Table 2. Time saved by joint prediction after removing the batches with the largest savings

Batches retainedTime savings relative to independent predictionShare of original net time savings retained
All 32,768 batches7.24%100.00%
Excluding the top 1 batch6.95%95.97%
Excluding the top 5 batches6.87%94.85%
Excluding the top 20 batches6.63%91.44%

The concern about the baseline experiment in Q1/W1. Joint prediction saved more time than both regression baselines you suggested. Relative to independent prediction, it reduced total completion time by 2.92%, or 24,902 seconds, which is 3.52 times the saving of nearest neighbour and 6.22 times that of gradient boosting regression. A gain of a few percent matters at production scale, because the same workflows run repeatedly. The authors of Mantri note that even a few percent of efficiency improvement in a cluster of tens of thousands of nodes can save millions of dollars a year [1].

The value of our work. You found the ideas in the paper interesting, and these ideas are the main contribution of our work. We believe this paper is valuable for the learning-augmented scheduling community. To our knowledge, the following points were not known before.

  • Even when every task's runtime distribution is exact, ignoring the dependence between task runtimes can raise the expected completion time. Theorem 1 shows when and by how much using this dependence helps.
  • Proposition 3 bounds the excess cost of a learned scheduling policy by the error of its predicted joint distribution.
  • Under arbitrary dependence, an excess cost of O(h−1/n)O(h^{-1/n}) from hh histories is achievable and cannot be improved in the worst case, even for schedulers that probe and preempt.

The experiments play a supporting role and check the mechanism, the estimator and the planning algorithm behind our theory on measured runtimes. Future work can apply joint prediction to workflows where predecessor feedback often changes the order, such as query scheduling in cloud data warehouses and multi-stage data processing jobs. We see strong potential for runtime dependence to improve real schedulers, and our theory offers a principled way to use it.

Thank you again for the careful reading. We hope this addresses your concern about the practical gains, and we would be grateful if you would consider raising your score.

References

[1] G. Ananthanarayanan et al., Reining in the Outliers in Map-Reduce Clusters using Mantri, OSDI 2010.

[2] Apache Spark, Adaptive Query Execution.

[3] M. Vuppalapati et al., Snowset, NSDI 2020 companion dataset.

Reviewer_LWkjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies non-clairvoyant workflow scheduling with statistically dependent task runtimes. It conditions a predicted joint runtime distribution on completed runtimes and unfinished-task ages, then uses exact Bellman planning to minimize expected total workflow completion time. Its principal contribution is statistical: a distribution-error-to-scheduling-cost bound, an O(h−1/n)O(h^{-1/n}) finite-history guarantee for Truncated Joint Fitting (TJF), and a matching worst-case lower-bound exponent on a fixed workflow graph. Validation uses constructed four-task replays based on Alibaba runtime records. Uncapped joint prediction improves the measured objective by 13.94%, whereas prescribed TJF achieves 0.54% at the largest history size.

Critical strengths
  1. Substantive statistical guarantees Proposition 3 and Theorems 4–5 connect distribution estimation to scheduling performance and characterize the worst-case dependence on history size under arbitrary runtime dependence. The feedback-event decomposition in Appendix B.7 and the fixed-graph lower-bound construction are the strongest technical contributions. In particular, the lower bound permits probing and preemption, showing that the statistical difficulty cannot generally be removed by choosing a more adaptive scheduler. These results provide a meaningful basis for acceptance as a theoretical contribution.

  2. Controlled comparison of information value Theorem 1 identifies when predecessor feedback changes the preferred terminal-task order, while the empirical comparison holds task marginals and the scheduling algorithm fixed (§5.2). This separates the value of retaining dependence from improvements in individual-task marginal predictions. The paper also candidly reports unsupported feedback, sensitivity to a high-impact batch, and the distinction between prescribed and exploratory truncation settings (§5.3), which makes the evidence easier to assess.

Critical weaknesses
  1. Limited evidence for the general scheduling construction The empirical study establishes the value of conditional information more clearly than the value of the proposed general scheduling construction. In the four-task replay, both predecessors finish before either of two nonpreemptible terminal tasks can start (§5.1). The remaining decision therefore reduces to ordering the tasks by their conditional expected runtimes; general Bellman planning is unnecessary for this particular decision. The independent and fixed-order baselines answer a valid information-isolation question, but do not establish an advantage of full joint fitting over directly learning conditional means or a ranking rule from the same observations. This leaves the practical justification for the general formulation insufficiently established. It does not invalidate the statistical results, but makes the contribution primarily theoretical rather than a demonstrated algorithmic advance.

  2. Weak connection between the headline result and the guaranteed estimator The strongest empirical result is weakly connected to the estimator receiving the main guarantee, and its magnitude is sensitive to the evaluation sample. The 13.94% improvement uses an uncapped empirical joint distribution, whereas prescribed TJF achieves only 0.54% against its matched independent comparator at full history, without a monotone improvement trend (§5.3). One batch contributes 11,188 of the 14,366 seconds saved by the uncapped method; excluding it leaves a positive but substantially smaller 3.95% gain. The exploratory wider cap achieves 2.94%, but was selected after inspecting test outcomes. These disclosures are welcome, yet the results support the potential value of dependence information more convincingly than the practical effectiveness of the theoretically motivated learning prescription.

Questions for authors
  1. Clarification of theoretical novelty Relative to the closest finite-sample scheduling results discussed in Section 2, which technical obstacle requires the new analysis? In particular, is the feedback-event representation yielding the ℓn−2\ell^{n-2} estimation term the essential advance behind the matching exponent? A precise comparison would help assess the contribution beyond the natural conditioning and Bellman construction.

  2. Clarification of methodological scope Do the authors agree that the terminal decision in §5 is equivalent to ordering conditional expected runtimes under the fitted distribution? If so, is this experiment intended solely to demonstrate the value of dependence information, or is there evidence that joint-distribution fitting offers an advantage over a conditional predictor using the same feedback?

  3. Additional evidence relevant to the assessment Is there additional held-out evidence for a truncation level selected exclusively on development data, with uncertainty accounting for refitting on different histories? Such evidence could materially change my assessment of TJF’s practical effectiveness. Broader production deployment would be future work, rather than a requirement for resolving this concern.

5 comments
AuthorsOpenReview ↗

Author Response (1/2)

We thank the reviewer for the detailed assessment and for highlighting the feedback-event decomposition and the fixed-graph lower bound, which applies even to schedulers that can probe and preempt. Below, we respond to the reviewer's comments and outline the corresponding revisions.

Q1

Technical obstacle. With precedence constraints and dependent runtimes, we need uniform bounds linking joint distribution estimation error to scheduling cost under the true distribution.

Table 1. Related finite-sample and distribution-error guarantees.

WorkContributionsTechnical obstacles
Empirical Gittins [1]Finite-sample convergence to optimal mean response time.Workload terms use only a task's own progress; dependence makes other tasks' feedback relevant.
Robust Gittins [2]Cost bounds for modified Gittins under errors in predicted distributions.Factoring joint probabilities using independence generally fails for dependent runtimes.

Contribution beyond the natural conditioning and Bellman construction. Theorems 1--2 quantify the potential cost of ignoring runtime dependence. We therefore optimize a policy under the fitted joint distribution using conditioning and the Bellman equation. To account for fitting error, Proposition 3 and the feedback-event decomposition bound this policy's expected excess cost under the true distribution. With more historical samples, the upper bound on expected excess cost converges to zero. The lower bound on a fixed execution graph rules out a better exponent in the worst case.

About ℓn−2\ell^{n-2}. Feedback-event decomposition and uniform error analysis yield this dependence, key to exponent matching in the upper-bound proof. For n≥3n\ge3, fix the second-moment bound on the sum of task runtimes and other problem parameters. Balancing expected estimation error O(ℓn−2/h)O(\sqrt{\ell^{n-2}/h}) with capping error O(1/ℓ)O(1/\ell) yields expected excess cost O(h−1/n)O(h^{-1/n}) against the optimal policy with the same feedback. Theorem 5 gives a matching Ω(h−1/n)\Omega(h^{-1/n}) worst-case lower bound for any learning algorithm on a constructed fixed execution graph.

Revision Section 2.

Our joint feedback-event decomposition controls how distribution error affects scheduling cost, uniformly over the policy class. This bounds expected excess workflow completion cost relative to the optimal policy with the true distribution and the same feedback.

References

[1] S. Ramakrishna, A. Harlev, and Z. Scully, "Empirical Gittins for Data-Driven M/G/1 Scheduling with Arbitrary Job Size Distributions," Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 10, no. 1, pp. 9:1--9:38, 2026.

[2] B. Moseley, H. Newman, K. Pruhs, and R. Zhou, "Robust Gittins for Stochastic Scheduling," arXiv preprint arXiv:2504.10743, 2025.

Q2/W1

In the Section 5 experiment, the terminal choices of the general method and conditional mean ordering coincide under the fitted distribution, while their choices can differ in multi-step settings. The original comparison specifically tests the scheduling value of dependence information, since using dependence between task runtimes need not change the order or reduce completion time. In the original experiment, both predecessors finish before the two nonpreemptive terminal tasks are scheduled, leaving only their order to decide. Later feedback cannot change the schedule, so Bellman and conditional mean ordering choose the same order. Replacing general Bellman planning with conditional mean ordering requires more than this agreement, because in multi-step settings the task run first affects which feedback arrives first, and that feedback may change later scheduling decisions.

Advantages over conditional predictors using the same feedback. To test whether the joint distribution method can turn the same feedback into lower completion times, we designed an experiment using execution records from real CI workflows with multiple stages. The experiment allows early feedback to change later scheduling decisions and keeps the training histories, observed information, and comparison starting point the same for all methods.

Table 2. Joint distribution fitting versus same-feedback baselines on development decisions with predicted planning benefit $\ge$5%. Costs sum remaining completion times (s). Reductions and 95% intervals across weeks are in %.

Method128 historiesReduction512 historiesReduction
Smoothed joint distribution fitting + Bellman planning466.295--499.472--
Conditional mean predictor481.4303.14 [-2.18,7.46]528.1095.42 [-0.55,21.37]
Direct learning of ranking rules488.8334.61 [-0.64,10.59]514.9283.00 [-1.97,8.90]
AuthorsOpenReview ↗

Author Response (2/2)

Bellman planning versus conditional mean ordering. We fix the joint prediction and start both methods at the first state where they choose different tasks. With the same joint prediction and feedback, Bellman planning gave lower mean remaining completion time than conditional mean ordering.

Table 3. Conditional mean ordering versus Bellman. Costs sum workflow completion times (s), measured from the start or the stated decision.

ScopeHistoriesMeanBellmanReduction (%)
All batches, full execution128319.877316.5381.04
512318.398315.1531.02
First differing decision128411.757398.0403.33
512435.146419.7623.54
Subset: predicted benefit ≥5%\ge5\%128503.144466.2957.32
512540.187499.4727.54

Gains from using task runtime dependence and from general multi-step planning. In the same subset, dependence information barely changes choices under conditional mean ordering. Bellman uses it to choose which feedback to obtain and adapt later decisions. Table 4 fixes one component to examine the other; the reductions reflect their combined effect.

Table 4. Completion time reductions from using task runtime dependence and from multi-step planning for the subset in Table 2.

Controlled comparison128 histories (%)512 histories (%)
Independent →\to joint prediction; Bellman fixed7.247.55
Conditional mean ordering →\to Bellman; joint prediction fixed7.327.54

Revision We will add the multi-step experiment and same-feedback comparisons to the appendix.

Q3/W2

Truncation level selection. We used 4,096 historical batches from a controlled JSON workload for fitting and selected 6.4 ms from five truncation levels using only the 1,536 development batches. The selected level gave TJF the lowest total workflow completion time. In the original Alibaba experiment, we explored a higher truncation level after inspecting the test results to assess whether more predecessor runtimes could inform later task ordering. To address the reviewer concern about practical effectiveness, we added the JSON experiment because JSON input size affects both parsing and compression, allowing tests of task ordering using predecessor feedback with new historical and test batches.

Table 5. Test results with the cap selected on development data. Total workflow completion times are in seconds.

EvaluationTest batchesIndependent predictionTJFSaving95% CI
Measured runtimes8,19217.958316.46948.29%[6.57%, 9.04%]
Online with decision time8,19214.885113.53729.06%[8.06%, 10.12%]

Uncertainty from refitting on different histories. The 95% interval for the 8.29% saving was estimated using 1,024 block bootstrap replicates that include history refitting, truncation level selection and test variation. It remains above zero after accounting for these changes. For the 9.06% saving, the interval reflects test variation with the fitted predictions held fixed.

Sensitivity of online savings to the training history. We kept the 6.4 ms truncation level selected on the development set and refitted on eight disjoint new histories of 4,096 batches each. As shown in Table 2 of our response to XYEW's W1/Q1, all eight fits produced positive savings ranging from 8.86% to 10.61%, with a spread of less than 1.8 percentage points.

Total savings with the top batches removed. For each experiment in Table 5, we ranked batches by the absolute time saved by TJF and separately removed the top one and five batches. We removed the same batches from both predictions and recalculated the saving using the remaining batches.

Table 6. Savings after removing the largest contributors.

Batches removedRemaining batchesMeasured runtimesOnline execution
None8,1928.29%9.06%
Top 18,1918.24%8.94%
Top 58,1878.05%8.72%

After removing the five largest contributors, both experiments retained savings above 8%, showing that the remaining batches accounted for most of the total saving. For these eight fits, removing the top five batches left online savings of 8.72% to 10.47%. The new savings persisted across histories and after removing the largest contributors, addressing the concern that a few batches drove the result.

Revised text. We will add the JSON experiments, including refitting uncertainty and savings after removing the top batches, to the appendix.

We hope our explanation of the statistical contribution and the new comparisons with conditional predictors address your concerns, and we would be grateful if you would consider giving the paper a higher score.

Thank you for the detailed response and the new experiments. Your explanation makes the main theoretical contribution clearer. The JSON results also address much of my concern about the practical value of TJF. In particular, selecting the cap on development data, including refitting in the uncertainty estimate, and checking the results after removing the largest contributors are useful additions.

The CI experiment is a useful response to my question about conditional mean and ranking baselines. However, all four confidence intervals in Table 2 include zero. Table 3 also shows that the gain over conditional mean ordering is about 1% across all batches, while the larger gains come from a selected subset. These results suggest a possible benefit, but the advantage over simpler methods is still uncertain.

Could you clarify the evaluation setup for this experiment? Table 2 refers to “development decisions” with predicted planning benefit ≥5. Was this rule fixed before evaluation on separate test data? Were the reported costs measured using runtime records that were not used for fitting or selecting the rule? It would also help to report confidence intervals for the full-execution gains of 1.04% and 1.02% in Table 3.

I would also appreciate clarification about the eightfold cap in the Alibaba experiments. Your response to me says the original larger cap was explored after seeing the test results, while your response to Reviewer uH79 says it was selected on development data before testing. These may refer to different experiments. Please make clear which setup and test data each statement refers to.

Overall, the new evidence has improved my view of the paper, especially regarding the stability of the gains on the JSON workload. These clarifications would help me finalize my assessment.

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

The paper studies scheduling with dependent task runtimes, using a predicted joint distribution updated through completion and noncompletion feedback. Under independent complete histories, fixed model parameters, and a bounded second moment, it establishes matching worst-case �0��0� excess-cost exponents for �1��1�, alongside independence-specific guarantees and a constructed Alibaba-trace evaluation.

Critical strengths

In my opinion the paper's strengths are as follows,

  • Substantive statistical contribution. The matching upper and lower exponents, supported by the feedback-event decomposition in Appendix B.7, characterize the difficulty of learning to schedule under arbitrary dependence (Theorems 4 & 5); this addresses a setting beyond the independent-job assumptions of the cited Robust Gittins and Empirical Gittins work
  • Carefully isolated dependence benefit. The theoretical comparison and empirical ablation preserve task marginals while changing dependence information, with the experiments also sharing the scheduler, tie-breaking, and fallback. This provides a convincing basis for attributing observed differences to the use of dependence.
Critical weaknesses

However, in my view it has also the following shortcomings,

  • Limited empirical support for the prescribed estimator. The headline 13.94% improvement uses an uncapped estimator and falls to 3.95% after removing the most influential batch, whereas prescribed TJF achieves only 0.54%. The eightfold cap was selected after inspecting test outcomes, so its improvement remains exploratory.
  • Practical scope and scalability remain unestablished. Scheduling evaluation uses constructed four-task Alibaba batches with added cross-chain dependencies, one-processor contention, and durations assumed unchanged by rescheduling. These experiments provide limited evidence about larger workflows, particularly because exact planning and the theoretical constants can grow exponentially with task count
Questions for authors

My questions for the authors are as follows,

  • Using the existing development split to select the truncation level, what improvement remains on untouched test data, and how variable is that improvement across independently fitted training samples?
  • How do total planning time and memory scale beyond four tasks, including fitting and value precomputation, and how representative are the reported decision times of the general scheduling model?
4 comments
AuthorsOpenReview ↗

Author Response (1/2)

We sincerely thank the reviewer for carefully reading both the theory and the experiments. We appreciate the reviewer's recognition of the matching worst-case exponents and of how the comparison isolates the value of runtime dependence by holding task marginals fixed. We address the reviewer's questions in turn below.

W1/Q1

Supplementary baseline comparison. In our response to uH79's W1/Q1, we added nearest neighbour and gradient boosting regression as baselines in an experiment using Alibaba logs. With independent prediction as the common baseline, joint prediction saved 24,902 s, or 2.92%. It saved 3.52 times as much as nearest neighbour, which saved 0.83%, and 6.22 times as much as gradient boosting regression, which saved 0.47%. Both baselines saved less than 1%, and the 2.92% saving from joint prediction was more than three times that of the stronger baseline, nearest neighbour.

Truncation level selection. We compared five truncation levels on the JSON development set of 1,536 batches and fixed the level at 6.4 ms. It gave joint prediction the lowest total workflow completion time, with ties going to the smaller level. The available Alibaba archive contained no unused batches after the original development period with the original task template, resource configuration and valid instance runtimes. We therefore ran a controlled JSON experiment to measure savings on new test data at the fixed truncation level and how they varied across training histories.

Improvement remains on untouched test data. We ran both scheduling strategies on JSON test data kept separate from fitting and truncation level selection.

Table 1. Improvement on untouched test data

JSON test dataBatchesIndependent prediction Total completion time (s)Joint prediction Total completion time (s)Saving
Full test set8,19214.885113.53729.06%
After removing the batch with the largest saving8,19114.861913.53268.94%

Including online decision time, joint prediction reduced total workflow completion time on the new inputs by 9.06%. The total saving was 1.3479 s, or about 0.16 ms per batch. For this fixed fit, the paired 95% confidence interval for the saving was 8.06% to 10.12%. Joint prediction still saved 8.94% after we removed the batch with the largest saving.

Variability of improvement across independently fitted training samples. At the fixed truncation level of 6.4 ms, we fitted both predictions on each of eight disjoint 4,096-batch training histories and tested all fits on the same 16,384 batches.

Table 2. Improvement across independently fitted training samples

History groupIndependent prediction Total completion time (s)Joint prediction Total completion time (s)SavingLowest saving after removal
128.217025.71798.86%8.42%
227.522224.94599.36%9.17%
327.515724.89939.51%9.28%
427.531124.724210.20%10.06%
527.745524.886510.30%10.08%
627.555024.761110.14%9.87%
727.677024.739810.61%10.51%
827.588425.05049.20%8.61%

All eight fits saved time, with savings ranging from 8.86% in group 1 to 10.61% in group 7, a spread of less than 1.8 percentage points. Savings remained at least 8.42% across all fits after removing either test session and then the batch with the largest remaining saving. In an Alibaba production cluster, Tian et al. observed runtime variation even in recurring jobs. For about three quarters of the recurring tasks they studied, runtimes varied more than twofold between runs [1].

Revision We will add the baseline comparison and the results of the JSON experiment to the appendix.

AuthorsOpenReview ↗

Author Response (2/2)

Q2/W2

1. Scale of total planning time and memory beyond four tasks

Choice of task counts. We used Alibaba production logs to study how total planning time and peak memory change with task count. The experiments kept the original task dependencies and recorded runtimes. Figure 6 of [2] shows that 99.6% of Alibaba batch jobs had fewer than 30 tasks. In our analysis of the same logs [3], at least 95% of jobs with recorded dependencies had at most 15 tasks. These figures guided the choice of task counts in Table 3.

Total planning time and peak memory by task count. State encoding and contiguous storage helped control total planning time and peak memory as the number of tasks increased. At 15 tasks, the baseline stopped at the memory limit. Our method completed exact planning in all three runs. The median total planning time was 12.160 s, and the highest peak memory was 1,235.31 MiB.

Table 3. Scale of total planning time and memory.

TasksBaseline (Total planning time, s)Our method (Total planning time, s)Reduction (Planning time)Baseline (Peak memory, MiB)Our method (Peak memory, MiB)Reduction (Peak memory)
40.03530.00018299.5%51.921.5597.0%
60.4300.0012699.7%69.191.9897.1%
83.8320.017999.5%235.695.2897.8%
1038.3770.15999.6%1,387.5638.4797.2%
12Memory limit at 45.80 s1.410—1,539.70 when stopped179.33—
15Memory limit at 73.00 s12.160—1,570.63 when stopped1,235.31—

Theoretical basis. Our algorithm uses the Bellman recursion in Section 3.2 and Appendix B.1. When different scheduling sequences reach the same state, the algorithm computes and stores its optimal cost and corresponding action only once. In the worst case, the number of states can still grow exponentially as the number of tasks increases.

2. Representativeness of the reported decision times

Scalability. Our Alibaba experiments cover the common decisions in the general scheduling model. In the experiment with a join in Table 3, several ready tasks compete for a free processor [4]. In the supplementary experiments with task chains, the scheduler can free a processor by pausing a task and then resume it without losing its progress [5].

Theoretical basis. Our algorithm uses the same Bellman recursion to compute the policy in both cases. Section 3 and Appendix B.1 specify the available actions in each state under processor contention and preemption. The recursion evaluates these actions and selects the next action in advance. The original experiments measured decision time at task completion events. The supplementary experiments measured it at each time step. Both timings measure the scheduler's use of execution feedback to select the next action.

Revision The appendix will report planning time and peak memory and explain how we timed online decisions.

We hope the additional results on truncation selection and planning scalability address your concerns, and we would be grateful if you would consider raising your score.

References

[1] Huangshi Tian, Yunchuan Zheng, and Wei Wang. Characterizing and Synthesizing Task Dependencies of Data-Parallel Jobs in Alibaba Cloud. SoCC, pp. 139--151, 2019. Section 6.3.

[2] L. Ruan, X. Xu, L. Xiao, L. Ren, N. Min-Allah, and Y. Xue, “Evaluating performance variations cross cloud data centres using multiview comparative workload traces analysis,” Connection Science, vol. 34, no. 1, pp. 1582--1608, 2022.

[3] Alibaba, Alibaba Cluster Trace 2018, 2018. Dataset documentation, Section 2.3.

[4] N. Garg, A. Gupta, A. Kumar, and S. Singla, “Non-Clairvoyant Precedence Constrained Scheduling,” in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019, pp. 63:1--63:14.

[5] SchedMD, “Preemption,” Slurm Workload Manager documentation.

Reviewer_XYEWOpenReview ↗

Read your rebuttal

Thanks for producing this, taking into account the rest of the discussion and what the other reviewer noted - I think I'll keep my score as-is. While my concerns were addressed to a large extend, I do not feel the paper contributions justify raising my score to accept.

AuthorsOpenReview ↗

Further Response

Dear Reviewer,

Thank you again for the review, and for your suggestions, which helped us improve the paper. You noted that our responses addressed most of your concerns, and that the open question for you is whether the contributions justify an accept rating. We would like to say briefly why we believe the paper merits acceptance.

The paper asks a learning question, how many complete runtime histories a scheduler needs before its learned policy approaches the optimal policy that knows the true runtime distribution. As your review noted, the closest guarantees, Robust Gittins and Empirical Gittins, assume independent job sizes. To our knowledge, the following points were not known before.

  • When a finished task's runtime can reverse which unfinished task is expected to be shorter, treating runtimes as independent raises the expected total workflow completion time even when every task's runtime distribution is exact, and more histories do not remove this loss (Theorems 1 and 2).
  • Under arbitrary dependence among n≥3n \ge 3 tasks and a bounded second moment of total runtime, TJF learns a policy with expected excess cost O(h−1/n)O(h^{-1/n}) from hh complete histories, and no learner achieves a better exponent in the worst case, even one that probes and preempts (Theorems 4 and 5). Under independence, fitting each task separately attains O(log⁡h/h)O(\sqrt{\log h / h}) (Theorem 10).
  • For any predicted joint distribution, the extra scheduling cost relative to the optimal policy is bounded by the prediction error, so the guarantee applies to predictors other than TJF (Proposition 3).

In your comment, you also took into account the rest of the discussion and the points raised by the other reviewers. To address these points together with yours, we have uploaded a revised version that follows the suggestions of all reviewers. The main changes are as follows.

  • Truncation level. For your first concern, the revision evaluates TJF with a truncation level selected on development data only. On held-out test data of a controlled JSON workload, TJF lowers total workflow completion time by 9.06% relative to independent prediction, and by 8.86% to 10.61% when refitted on eight disjoint training histories.
  • Scale. For your second concern, exact planning completes on Alibaba workflows of up to 15 tasks with a median total planning time of 12.16 s. Workflows of at most 15 tasks make up at least 95% of the Alibaba jobs with recorded dependencies.
  • Baselines. For the concerns of the other reviewers, joint prediction with Bellman planning lowers mean remaining completion cost on held-out CI workflows by 3.35% to 5.36% relative to a conditional mean predictor and a learned ranking rule, and all four 95% intervals lie above zero.
  • Real query logs. On Snowset query logs, joint prediction lowers total workflow completion time by 7.24% against 0.47% for nearest neighbour, and keeps 91% of this saving after the 20 batches with the largest savings are removed.

We believe this paper is valuable to the learning-augmented scheduling community. It shows how much runtime history a scheduler needs when task runtimes are dependent, and the revision shows that joint prediction lowers completion time on real traces. We would be grateful if you could take another look at the revision and consider raising your score. As your concerns are now largely resolved, we would be appreciate if you could support the paper in the discussion with the Area Chair.

Best regards,

The authors

Comments on the paper

2 comments

Dear Reviewers,

The authors have provided rebuttals to your review. Could you please check their responses and provide any further feedback or questions for the authors to address at your convenience?

Thank you for your time and contribution.

Regards,

AC

AuthorsOpenReview ↗

General response to reviewers and AC

Dear Area Chair and Reviewers,

Thank you for the time. This comment summarizes the contribution to machine learning, our responses to the reviews and the changes in the revision. We are willing to address your further concerns!

1. Contribution Learning-augmented schedulers increasingly receive predicted runtime distributions instead of point predictions. Earlier analyses treat the runtimes of different tasks as independent. When runtimes are dependent, a completed runtime tells the scheduler about unfinished tasks. The paper asks how a scheduler should use a predicted joint distribution, and how many histories it needs to learn one.

  • Dependence has value even with exact marginals. Ignoring dependence can raise expected total completion time when every task marginal is exact. Theorem 1 gives the gap and the condition under which it is positive.
  • Distribution error bounds scheduling cost. Relative to the optimal policy with the true distribution and the same feedback, the excess cost of the learned policy is at most twice a uniform distribution error (Proposition 3).
  • Matching rates. Under arbitrary dependence, TJF attains O(h−1/n)O(h^{-1/n}) for n≥3n\ge 3, and no learner does better in the worst case, even one that probes and preempts (Theorems 4 and 5). Under independence, the rate is h−1/2h^{-1/2} up to a log factor (Theorem 10, Proposition 14). Dependence thus raises the exponent of the histories needed for excess ε\varepsilon from 2 to nn.
  • Why the exponents match. The feedback-event representation (Appendix B.7) writes the cost of every candidate policy through joint events with at most n−2n-2 completed runtimes, and the hard instances of Theorem 5 use the same number of rare contexts.
  • What the community can build on. Proposition 3 applies to any fitted joint distribution. When dependence follows a known graph of indegree rr, structured fitting attains O(h−1/(r+4))O(h^{-1/(r+4)}) (Theorem 18). Guarantees for faster planning algorithms remain open.

2. Responses to the reviews Section 5 now reports the main results below, and Appendix C gives the full setups.

  • Technical novelty (LWkj). Robust Gittins factors joint tail probabilities through independence, and Empirical Gittins ranks each job by its own age. Both steps fail under dependence, and Theorem 1 shows that an error measure on marginals alone cannot bound the cost.
  • Practical value of TJF (XYEW, LWkj, uH79). A cap chosen on development data makes TJF effective. On held-out JSON batches it saves 8.29%, and the 95% interval [6.57%, 9.04%] stays above zero after refitting on new histories and reselecting the cap. On heavy-tailed Snowset logs, the selected cap saves 5.25% against independent prediction and 3.35% against the formula cap of Theorem 4.
  • Concentration of savings (XYEW, LWkj, uH79). The savings are spread across many batches, so removing the largest contributors changes them little. Without its top 20 of 32,768 batches, Snowset keeps 91% of the net saving, and without its top five of 8,192 batches, JSON still saves 8.05%.
  • Baselines with the same information (LWkj, uH79). Using dependence beats estimating conditional means directly. On Snowset, joint prediction saves 7.24%, more than 13 times the best regression baseline. Planning adds a second gain once feedback arrives over several steps: in multi-step CI workflows, our method saves 3.35% to 5.36% on held-out decisions against baselines that receive the same feedback.
  • Scalability (XYEW, uH79). Exact planning is practical for most recorded Alibaba jobs. At least 95% of jobs with recorded dependencies have at most 15 tasks, and our C++ planner solves 15-task workflows in about 12 s.

3. Changes in the revision

  • Related work. Section 2 adds the technical comparison with Robust Gittins and Empirical Gittins.
  • Experiments. Section 5 states when Bellman planning reduces to conditional-mean ordering, reports the development-selected cap, and summarizes the supplementary results with references to Appendix C. Appendix C is a new section with regression baselines on Snowset (C.1), cap selection (C.2), a controlled JSON workload (C.3), multi-step CI workflows (C.4), and planning time, memory and decision timing (C.5). The stage-level Alibaba comparison with regression baselines stays in our response to uH79.

The theorems of the submission stand, and the main text stays within the 10 pages allowed during the discussion.

We sincerely thank the Area Chair and the reviewers for reading the responses and the revision, and we would be grateful if both could be considered in the final assessment.

Best regards,

The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.