- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies learning-augmented scheduling when obtaining job-size predictions incurs inference latency. The authors consider a model where all jobs are available at the beginning, and the goal of the scheduler is to minimize the total completion time. Predicting/learning the job processing-times more accurately will help the scheduler make better decisions, e.g., to schedule the shortest jobs first. However, when the time to perform learning/prediction increases with the accuracy, it is then unclear whether using the highest-accuracy predictor is still the best choice. The authors study this trade-off between prediction accuracy and inference latency. The paper's main contribution is to prove an additive lower bound under an adversarial setting, even when jobs can be processed during inference. Experiments using traces from Alibaba GPU clusters, Azure Functions, and Alibaba microservices seem to be confirm that using suboptimal predictor can result into the shortest total completion time.
Critical strengths
-
The adversarial lower-bound in Theorem 2 on the total completion time seems to be interesting. Assuming that the adversarial can pick arbitrary processing times of the jobs, the author reveals that there exists at least an additive gap compared to the offline OPT.
-
The main conclusions are confirmed using real-world traces from Alibaba GPU clusters, Azure Functions, and Alibaba microservices.
Critical weaknesses
-
Other than Theorem 2, the rest of the theoretical results seem to be straight-forward. For example, Thm 1 follows directly from adding the inference latency to each job. Thm 3 follows from standard optimality conditions.
-
There seems to be a gap between the theoretical results and the trace-based experiments. The theory relies on the knowledge of the competitive ratio of the scheduling algorithm at a given prediction accuracy . It is unclear how one can obtain this competitive ratio in practice. The experiments seems to ignore this difficulty, and directly use a grid search to select the best predictor. It is thus unclear how the derived theory can be used to guide the choice.
-
One alternative algorithm that the authors did not study is the following: Use the fast predictor to decide which job to schedule first; while the first job is being run, use the slow predictor simultaneously to learn the processing times of the other jobs more accurately. It seems that this strategy could hide the latency of the slow predictor in most cases, making the theoretical results in the paper less interesting.
Questions for authors
-
Can you explain how to obtain the competitive ratio in practice? If not, how can the derived theory help us making better choices in practice?
-
Could you comment on how the results would change if one first picks a job using a fast predictor, and then utilizes the processing time of first job to run the slow predictor for other jobs.
4 comments
Author response 2/2
2. Traces. We use the controlled predictors of Section 4.2. The slow predictor is the most accurate one, and both predictors start at time zero. We ran the strategy in two forms and with every fast predictor of the grid.
-
As the reviewer suggests, the fast predictor picks one job, and this job runs while the slow predictor computes. The other jobs still wait for the slow predictions. Even with the best fast predictor, the mean cost over 20 seeds stays within 0.4% of waiting for the most accurate predictor.
-
We extended the setting into a new form: all jobs run in the order of the fast predictions, and the slow predictions take over when they arrive. With the best fast predictor, this form has the lowest cost in Table 7. The cost is 4.4% ± 0.1% (Azure) and 6.1% ± 0.1% (ATLAS) below waiting for the cost-aware predictor, in all 20 seeds.
However, the gain of the second form depends on the fast predictor. A fast predictor that is too inaccurate or too slow costs 3.3% to 7.3% more than the best one. On each trace, one of the two costs more than waiting for the cost-aware predictor. The selection problem of the paper therefore remains, now for the fast predictor.
Thank you again for the careful review, which improved the paper. The strategy proposed under W3 is now analysed exactly in the paper (Theorem 7) and measured on the traces. The question on led to a selection made before the run, tested on 36 trained models on the Alibaba microservices trace. We hope that these changes, together with the exact results under W1, address the three concerns. We would be grateful if the reviewer would consider raising the rating, and we are glad to answer any remaining questions.
I thank the authors for the additional results. While it is good to see that using the fast/slow predictor leads to improvements compared to the original proposal, I feel that this result raises doubts on whether the original model is the most relevant one for this problem. A more thorough study of this type of sequential decision making is needed to properly understand the right control policy (e.g., no need to made the machine idle if the first job finishes sooner). Thus, I am unable to raise my score.
Further response
Thank you for actively engaging in discussions! We will clarify and answer your further questions below.
The reviewer noticed the improvement over waiting for the predictions. In our previous reply, however, the fast predictor was not just any fast predictor. It was the best fast predictor. We found it by comparing the total cost of every candidate on the batch, as we did for the cost-aware predictor, so it was chosen by total cost rather than by accuracy or at random. In other words, the fast/slow strategy already uses our predictor selection. We then compared it with the weakest baseline, waiting for the predictions, and this may have suggested that a smarter strategy can replace predictor selection. We are sorry for the confusion.
In the experiments, we ran the strategy in two example forms. In the first, the fast predictor chooses one job, which runs while the slow predictor computes, and the other jobs wait for the slow predictions. If this job finishes early, the machine idles, which is indeed not needed. In the second, all jobs run in the order of the fast predictions until the slow predictions take over, so the machine never idles. These are two examples of the fast/slow strategy, not our setting.
A fast predictor helps only when it is accurate, and it is usually less accurate. You can imagine that if a random fast predictor's predictions are wrong, the machine can start a very long job that looks short. Every other job waits behind it, raising the total completion time significantly. In the worst case, following an inaccurate fast predictor loses twice as much as simply sharing the machine equally among all jobs until the slow predictions arrive. Picked by accuracy alone, the fast predictor would be the slowest candidate. On the traces, a fast predictor that is too inaccurate or too slow costs 3.3% to 7.3% more than the best one, and on each trace one of them is even worse than our original cost-aware choice.
Our theory shows that using the waiting time reduces the cost of the delay but does not remove it, so the choice of predictor matters under every strategy. Besides waiting, we also study strategies that keep the machine busy, such as Round Robin while predicting and predictions delivered job by job. The fast/slow strategy is one more strategy of this kind in our setting, not a new model that beats our design.
We believe this paper is valuable for the learning-augmented scheduling community. To our knowledge, the following points were not known before.
- The time a prediction takes is a cost that no scheduling strategy can hide, and its exact price is known.
- One number, computed from a trace and the per-job latency before any model is trained, tells how much choosing the most accurate predictor can cost.
- The best predictor grows with the workload in a closed form, so it can be chosen without testing every model.
Thank you again for the careful reading. We hope this clarifies the point, and we would be grateful if it could be considered in the final assessment.
Author Response
Thank you for the careful review, and for the positive assessment of soundness and presentation. We are glad that the lower bound of Theorem 2 and the experiments on three real-world traces stand out as strengths. The revision addresses the three weaknesses. The lower bound of Theorem 2 is now exact (W1). The selection works with a measured ratio in place of ρA and without a grid search (W2 and Q1). The strategy proposed under W3 and Q2 is analysed in theory and on the traces.
W1: Depth of the theoretical results.
Theorems 1 and 3 prepare the two main results, and the revision makes both main results exact.
We first recap the logic of the theortical section: Theorem 1 is the upper bound that pairs with the lower bound of Theorem 2, and Theorem 3 is the step to the closed form of Corollary 2.
1. The price of prediction latency is now exact. The submission left a factor of about 2 between the lower bound (Theorem 2) and the cost of waiting (Theorem 1). The revision shows that Round Robin during inference attains the lower bound on every instance (Theorem 2 (b)). The price is also exact on m machines, which the submission listed as open, for randomized algorithms (Theorem 6), and with a second, fast predictor (Theorem 7, see W3).
2. The price of ignoring latency is now exact. We before gave an instance that loses the factor 1+κ (Theorem 4). Proposition 2 of the revision proves the matching upper bound for every finite set of predictors, with no smoothness. The regime parameter is therefore a two-sided guarantee.
W2 and Q1: How the theory guides the choice in practice.
We understand the concern. We compared the candidates on a batch whose true durations are known, and did not say how a predictor is chosen beforehand. We propose how the predictor is chosen before a batch runs, with no grid search on that batch. With trained models and measured latencies, this choice lowers J by 7.4% ± 1.0% relative to the most accurate model, and two guarantees hold before the run.
1. How the predictor is chosen. ρA is the upper bound proved for the scheduler (1+x for SPJF), so it is not estimated. In practice the measured ratio (total completion time over OPT) takes its place, and the selection results hold verbatim.
Across model classes there is no common curve, so we take the model with the smallest J on the previous batch. With 36 trained models of three classes on the microservices trace, this choice has lower J than the most accurate model in 19 of 19 pairs of consecutive batches (Wilcoxon p=3.8×10−6) and stays within 1.05% of the best model of the batch.
Within one model class, the best complexity θ⋆ has a closed form. Fitted on the five smallest of the 12 trained LightGBM models of the microservices trace (Table 1), the closed form gives θ⋆≈17,900, between the measured optimum and a model that costs 0.41% more .
When the workload changes, the closed form follows the workload through OPT/n. On Azure and ATLAS, OPT/n varies across batches by a factor of 5,756 and 3. We fit the constants once, on the first batch, with the controlled predictors. For every later batch, the closed form takes OPT/n of the previous batch. The resulting choice costs a median of 0.42% and 0.05% more than a grid search on the batch itself.
2. The guarantees before the run.
The most accurate predictor costs at most 1+κ times the best choice, whatever the candidates. κ needs only the latency of a predictor and OPT, which logged batches estimate.
The closed form needs an estimate of OPT. An estimate that is off by a factor of 2 costs at most 6.2%.
W3 and Q2: A fast predictor first, a slow predictor in parallel.
Thank you for proposing this concrete strategy. We analysed it in theory and ran it on the traces. The strategy lowers the cost when the fast predictions order all jobs. The trade-off between accuracy and latency remains. It moves to the fast predictor.
1. Theory. Given a fast predictor at time zero with total absolute error at most δ, and perfect predictions at time τ, the exact worst-case loss is (n−1)min{δ,τ/2}. Without the fast predictor it is (n−1)τ/2 (Theorem 2). In the worst case, the latency is hidden only when δ is below τ/2.
The results obtained from traces are illustrated in next comment.