SkipPredict: When to Invest in Predictions for Scheduling
Authors: Rana Shahout
Michael Mitzenmacher
Venue: NeurIPS 2024 poster (2024)
Keywords: Algorithms with predictions; scheduling
Primary area: optimization

Abstract: Expanding on recent work on scheduling with predicted job sizes, we consider the effect of the cost of predictions in queueing systems, removing the assumption in prior research that predictions are external to the system’s resources and/or cost-free. Additionally, we introduce a novel approach to utilizing predictions, SkipPredict, designed to address their inherent cost. Rather than uniformly applying predictions to all jobs, we propose a tailored approach that categorizes jobs to improve the effectiveness of prediction on performance. To achieve this, we employ one-bit “cheap predictions” to classify jobs as either short or long. SkipPredict prioritizes predicted short jobs over long jobs, and for the long jobs, SkipPredict applies a second round of more detailed “expensive predictions” to approximate Shortest Remaining Processing Time for these jobs. Importantly, our analyses take into account the cost of prediction. We derive closed-form formulas that calculate the mean response time of jobs with size predictions accounting for the prediction cost. We examine the effect of this cost for two distinct models in real-world and synthetic datasets. In the external cost model, predictions are generated by external method without impacting job service times but incur a cost. In the server time cost model, predictions themselves require server processing time and are scheduled on the same server as the jobs.

SkipPredict: When to Invest in Predictions for Scheduling
Rana Shahout Harvard University
Michael Mitzenmacher Harvard University
Abstract
Expanding on recent work on scheduling with predicted job sizes, we consider the effect of the cost of predictions in queueing systems, removing the assump- tion in prior research that predictions are external to the system's 's resources and/or cost-free. Additionally, we introduce a novel approach to utilizing predictions, SkipPredict, designed to address their inherent cost. Rather than uniformly ap- plying predictions to all jobs, propose tailored approach that categorizes jobs to improve the effectiveness of prediction on performance. To achieve this, we employ one-bit "cheap predictions" to classify jobs as either short long. SkipPredict prioritizes predicted short jobs over long jobs, and for the long jobs, SkipPredict applies a second round of more detailed "expensive predictions" approximate Shortest Remaining Processing Time for these jobs. Importantly, our analyses take into account the cost of prediction. We derive closed-form formulas that calculate the mean response time of jobs with size predictions accounting for the prediction cost. We examine the effect of this cost for distinct models in real-world and synthetic datasets. the external cost model, predictions are gen- erated by external method without impacting job service times but incur cost. In the server time cost model, predictions themselves require server processing time and scheduled the same server as the jobs.
Introduction
Machine learning research is advancing rapidly, reshaping even traditional algorithms and data struc- tures. This intersection has led to the rise of "algorithms with predictions", also called learning- augmented algorithms, where classical algorithms are optimized by incorporating advice predic- tions from machine learning models (or other sources). These learning-aus sarminggauggmnnedd algorithms have demonstrated their effectiveness across a range of areas, shown in the collection of papers (git) [n. d.) on the subject and as discussed in the surveys (Mitzenmacher and Vassilvitskii 2020 2022).
Queueing systems are an example where the learning-augmentee algorithm paradigm has been ap- plied for scheduling. Several studies have examined queues with predicted service times rather than exact service times, generally with the goal of minimizing the average time a job spends in the system (Dell' Amico et al. 2015) Dell' Amico 2019 MMizzemmacher 2019 2021 Wierman and Nuyens] 2008), and additionally some recent works also consider scheduling jobs with deadlines (Salman et al. 2202bbaa a). Minimizing response time crucial in data centers for reduced latency, in cloud computing for enhanced user experience and optimized resource utilization, and in real- time telecommunication systems for maintaining reliability and performance through quick task processing.
However, existing works do not adequately model the resources required to obtain such predictions. They often assume that predictions are provided "for free" when job arrives, which may not be
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

realistic assumption in the practical evaluation of system. Incorporating the cost of predictions is essential, as it could be argued that the resources devoted to calculating predictions might be more effectively used to directly process the jobs themselves. This perspective challenges the potential efficiency of integrating predictions into real-world queueing systems. As a result, the following questions arise:
When does the use of predictions, including their computation, justify their costs? Should all jobs be treated uniformly by computing predictions for each one?
As a simple example, let us consider a model where predictions of the service time arrive with the job and do not affect the arrival or service times, but do introduce a fixed cost e per job, so the total cost per job is the sum of the mean response time and fixed prediction cost. When we look at Shortest Predicted Remaining Processing Time (SPRPT) policy (Mitzenmacher 2019), which simply always runs the job with the smallest predicted remaining time, the improvement in the cost over FCFS naturally varies with the prediction cost.
In this paper, we focus on the cost of predictions in settings where two stages of predictions are available. We consider the setting of an M/G/1 queueing system: jobs arrive to single-server queue, according to a Poisson arrival process with general i.i.d service times. We examine two distinct cost models. In the first model, referred as the external cost model, predictions are provided by an external server, and they do not affect job service time, but we do factor in a fixed cost for these predictions. The expected overall cost per job in this model is the sum of the job's expected response time within the system and the cost associated with the time for prediction. In the second model, referred to as the server time cost model. predictions themselves require a fixed time from the same server as the jobs to produce, and hence a scheduling policy involves also scheduling the predictions. In this model, the expected overall cost per job is determined by the expected response time. As this model integrates the prediction process within the primary job processing system, it offers a different perspective on the cost implications of predictions as compared to the external model. (In partieular, for heavily loaded systems, adding time for jobs to obtain predictions could lead to an overloaded, unstable system.)
As adding a single prediction to an M/G/1 model is relatively straightforward, we consider systems where we have two stages of prediction. In the first stage, we may simply predict whether job is short or long. This type of one-bit prediction (studied in (Mitzenmacher, (021)) is very natural for machine learning, and in practice may be much simpler and faster to implement. We therefore call these "cheap predictions." In a possible second stage, we predict the service time for job, which we refer to as "expensive predictions," as in practice we expect them to be substantially more costly. (While we focus on these types of two stages, one could alternatively consider variations where the two stages could yield the same type of prediction; e-g. service time, with the cheap prediction being less accurate but consuming fewer resources.) We introduce a scheduling policy, called SkipPredict (Skip or Predict), which first categorizes jobs into short and long jobs with the first prediction, prioritizes short jobs over long ones, and restricts additional service time predictions exclusively to long jobs. We analyze the effect of the cost of prediction by considering SkipPredict with the previously described external cost model and server cost model. Our approach could be applied to applications where the cost is critical, such as data centers, cloud computing systems, and real-time telecommunication systems; in all these applications, system, optimizing resources and the user experience while accounting for the overall costs.
can reduce the expected time in
We compare SkipPredict with three distinct previously studied policies, re-analyzing them with pre- diction costs the two proposed models. First, we consider First Come First Served (FCFS), which does not require predictions (and hence incurs no cost from predictions). Second, 1bit (Mitzen- macherr| 2021). a policy using only cheap predictions, separates jobs into predicted short and long jobs, and applies FCFS for each category, thereby eliminating the need for a second stage of pre- diction. Third, Shortest Predicted Remaining Processing Time (SPRPT) performs expensive predic- tions for all jobs, and no cheap predictions. We find that service time predictions are particularly effective in logh systems. Our analysis shows that SkipPredict potentially outperforms the other policies (FCFS, 1bit, SPRPT) in both cost models using real-world and synthetic datasets, especially when there is a cost gap between cheap and expensive predictions. Additionaly, we present another alternative algorithm called DelayPredict which avoids cheap predictions by running jobs for fixed period before executing an expensive prediction. DelayPredict initially schedules all jobs FCFS but
In Section 4.4 we discuss the case of random costs from a distribution.

---

limits them to time L. Jobs exceeding the limit L are preempted, and given lower priority, and then they are scheduled by SPRPT. We find SkipPredict can also perform better than DelayPredict when there is a cost gap between these predictions.
While we focus on scheduling, we believe the approach of using multiple layers of predictions may be useful for other algorithms with predictions problems.
2 Related Work
We make extensive use of the SOAP framework (Schedule Ordered by Age-based Priority) (Scully and Harchol- Balter 2018), which was recently developed to analyze age-based scheduling policies. We use this framework to derive mean response time formulas. We provide brief background to the framework in Section B.1 For scheduling with predictions, Mitzenmacher (Mitzenmacher) (219)) demonstrated that the analyses of various single-queue job scheduling approaches can be generalized to the context of predicted service times instead of true values. Later, Mitzenmacher (Mitzenmacher 2021 considered scheduling algorithms with a single bit of predictive advice for whether job is "long" or "short", based on if its size is above or below a certain threshold. This work shows that small amounts of possibly inaccurate information can yield significant performance improve- ments. Scully, Grosof, and Mitzenmacher (Scully et al.] 2022) design a scheduling approach for M/G/1 queues that has mean response time within constant factor of shortest remaining processing time (SRPT) when estimates have multiplicatively bounded error, improving qualitatively over sim- ply using predicted remaining service times. Azar, Leonardi, and Touitou study similar problems in the online setting, without stochastic assumptions, and consider the approximation ratio versus SRPT Azar et al. 2021 2022).
Our work has a similar flavor to various "2-stage" problems, such as 2-stage stochastic program- ming and 2-stage stochastic optimization (e.g., (Grass and Fischer [2016] Kolbin 1977; Shmoys and Swamy 2004; Swamy and Shmoys, 2006)). Here, somewhat differently, our two stages are both predictions of service time at different levels of specificity.
Two recent works have explored incorporating costly predictions into online algorithms. (Benomar and Perchet 2024) examines how online algorithms can optimally use limited budget to query for advice. (Drygala et al.) 2023) studies the trade-off between the expense of acquiring predictions and the operational benefits they offer. We note that these papers address traditional online prob- lems, such as the ski rental problem. However, the queueing setting introduces unique complexities. Notably, much of the literature in this area focuses on budgeted settings, where the number of pre- dictions is limited. In contrast, our work seeks to optimize overall costs by considering prediction and operational expenses.
3 Model
We consider M/G/1 queueing systems with arrival rate X. The processing times for each arriving job are independent and drawn based on the cumulative distribution F(x), with an associated density function f(x)
Scheduling Algorithm: SkipPredict SkipPredict initially categorizes jobs based on a binary pre- diction of either short long, which we refer to as a cheap prediction. Only jobs predicted long are further scheduled for a detailed expensive prediction to get the predicted processing time. With SkipPredict, jobs that are predicted short have priority over all other jobs. Specifically, predicted short jobs are not preemptible and are scheduled based on First-Come, First-Served (FCFS). Jobs predicted to be long are preemptible and scheduled according to the Shortest Predicted Remaining Processing Time (SPRPT) with predicted size given by the expensive prediction.
We focus on model where, given a modulated threshold parameter T, the cheap predictions are assumed to be independent over jobs, a job of true size x being predicted as short (less than 7' with probability (x)). Similarly, the expensive predictions are assumed to be independent over jobs, and they are given by density function g y), where g(r, y) is the density corresponding to a job with actual size x and predicted size y. Hence fy= 9(. y) = fz). We consider two different models, external cost, in which the predictions are provided by an external server, and server cost, in which the predictions are scheduled on the same server as the job.

---

Single-Queuee External Cost In this model, job can be described by triple (I, b, r); we refer to this as a job's type. Here z is the service time for the predictor, b is the output from binary predictor that determines whether the job is short or long, and for any long job, is the result of service-time predictor that provides a real-number prediction of the service time. If a job is predicted to be short, we do not consider r, and so we may take r to be null. Again, we refer to b as the cheap prediction and r as the expensive prediction.
In this model, the predictions do not affect the service time of the job, and we treat the overall arrival process, still, as Poisson. Accordingly, SkipPredict can be viewed as a two-class priority system: Class 1 is for short jobs, managed by FCFS within the class. Class 2 is for long jobs, according to SPRPT using service time prediction. However, we do associate a cost with predictions which is the mean response time to get the prediction. All jobs obtain a cheap prediction at some constant fixed cost c1, and all long jobs obtain an expensive prediction at some fixed cost c2. Accordingly, we can model the total expected cost for predictions per job in equilibrium as C = c1 + C22, where the expected fraction of jobs requiring the second prediction. In general, both and с₁ will depend on choice of first layer prediction function, and similarly 0s will depend on the choice of second layer prediction function. Therefore, for some parameterized families of prediction functions, we may wish to optimize our choice of predictors. Specifically, letting T be the expected response time for a job in the system in equilibrium, we might typically score a choice of predictors by the expected overall cost per job, which we model function (CC,T) T), such as the sum of the C' and T.
J (1)
pr(z))dr
Single-Queus Server Time Cost The server time cost model refers to the setting where predic- tions are scheduled on the same server as the jobs, so there is a server time cost based on a defined policy. Jobs predicted short are categorized as con-preemptible while in execution, thereby pri- oritizing their completion before predicting new jobs. However, jobs predicted as long are further scheduled for detailed expensive prediction. Thus, cheap predictions outrank expensive predictions and long jobs. Similarly, expensive predictions are prioritized over predicted long jobs.
SkipPredict now can be viewed as four-class priority preemptive system. Class I (highest priority) is designated for predicted short jobs, managed by FCFS within the class. Consequently, short jobs are non-preemptible, and are prioritized over predictions for new jobs. This priority is appropriate because even if new jobs are predicted to be short, they will run after the already running short jobs (from FCFS). Class 2 is for (entering) jobs awaiting cheap predictions, which are also handled using FCFS. Class is for jobs awaiting expensive predictions, and also uses FCFS. Finally, Class 4 is reserved for predicted long jobs, served using SPRPT using the service time predictions the jobs obtained when they were Class 3. (Note all jobs enter in Class 2, and the either move to Class 1, or to Class 3 and then Class 4.)
lenty ElT and B[T) lerv are the expected response time for predicted short job and predicted long job in the external cost model and the server cost model in equilibrium respectively. Then, the total cost in the external cost model is
Definition 1. Suppose E[TESS leat E
(1 2) 2) EITPSS
PS Text
+ E[TPL PL C
while the total cost in the server cost model is
(1 (1-2) 2) ETT + E(T PL
where z is the expected fraction of jobs requiring the second prediction and C is the expected cost for prediction per job.
4 SkipPredict Theorems
For SkipPredict with a given T in both models, the expected mean response times for a pre- dicted short job (B[T) Ps (soodet>) and predicted long job of true size Φ, and predicted size TE J PL
< are given in Table [] We provide proofs in Appendix C in Lem- mas 2 and We get [T[]eodddd using Lemma 5 and by plugging [E[T] <modet> and we get the total cost of SkipPredict in both models. e₁ is the cost of the cheap prediction, C2 is the cost of the expensive prediction and (r - a)+ mar(r - a, 0). The symbols used in the equations are later expressed and described in Table
E[T <moddtt into Definition I

---

Table 1: SkipPredict equations
Predicted
External Cost
Server Time Cost
A ( 201E|S'<r] E[S'=T")
xE|S'eT 2(1 Per))
Short
+ E[S'er]
2(1 pps)
Long
A 2(1 pfat)s
BlSS'T F
2 (c)]]+
2(1 paroja
+ (a)
(a (e) Q(T.)( + E|S"
(cc + c2)l
+ +a(r)
da
- 1-per-)) P(r-a))
+ +a(r)
da
Prr (r-a)+
Table Description of symbols used the equations (defined in Appendix C
Symbol
Description
B[(' BiSTT (())
Expected service time of predicted short jobs
E
Expected service time of predicted long jobs with predicted size S r Expected service time of predicted short jobs including prediction cost e1
P'T
Load due to predicted short jobs
pfat
Load due to predicted short jobs, long jobs with predicted size Load due to predicted short jobs and their cheap prediction cost Load due to predicted short, long (with predicted size S r) and prediction jobs
PPS pr
a(r)
Integral related to predicted long jobs with predicted size r Probability of a job being predicted as long with predicted size >
Q(T,r)
4.1 Proof intuition of SkipPredict
External Cost Model. Response time is defined as the sum of the waiting time in the queue and the residence time, which the time from when the job is first processed until completion. For SkipPredict in the external cost model, predicted short job has wait behind only previous short jobs. This case is straightforward and follows the mean response time in the system for FCFS, which is given by Equation 23.15 in (Harchol-Bal Balter 2013). Since there is preemption in this case, the residence time is simply the service time for the predicted short job, E[S"Zr] A predicted long job of true size æ. and predicted size has wait behind previous short jobs, expressed by the term E[S'ZT 3. and long jobs with shorter remaining time, expressed by the terms E[S" 2] and a(r) well the final term involving the load. The waiting time is represented by the first term. Since we perform preemption for predicted long jobs, there is preemption delay that causes a slowdown in the residence time due the load from jobs predicted short and jobs predicted long but with a service time prediction of less than r.
Server Time Cost Model. For the server cost model, predicted short job has to wait behind previous short jobs and previous cheap predictions. This addition of the cheap prediction, compared to the external cost model, is expressed by terms involving CJ. In this case, there is preemption, so the residence time is simply the service time for the predicted short job, E[S
A predicted long job of true size and predicted size must wait behind previous short jobs along with their cheap predictions, expressed by the term (c,)), ].. It must also wait behind cheap and expensive predictions of long jobs that arrive earlier but with larger remaining time, expressed by (cr + 02) Q(T, r), and long jobs with a shorter remaining time frame along with their cheap and expensive predictions, expressed by EiS" (c2 + c2)] + a(r). The slowdown due to preemption affected by the load from jobs predicted as short, jobs predicted as long but with a service time prediction less than and the load from all predictions.

---

4.2 SkipPredict Models Comparison
In the server cost model, we observe that the mean response times for both predicted short and long jobs are consistently higher than those in the external cost model, because predictions are scheduled on the same server as the jobs. When we set the costs to zero, so there is no cost to predictions, both models yield identical mean response times. This follows from the definitions of 8% (12) and S (c)) (Table 3) because with zero costs, these definitions match with those of S-T,, and S" Additionally, setting the threshold T to zero in SkipPredict results in SPRPT (Shortest Predicted Remaining Processing Time) scheduling. With this threshold, there are no short jobs (i.e., [[[ = 0), necessitating expensive predictions for all johs. Thus, the mean response time for the predicted long johs aligns with the mean response time of SPRPT (Mitzenmacher 2019) (analyzed for both of the two models in Appendix D.1p.
We emphasize that while we have derived equations for total costs for both models, comparing the practical implications of these total costs for the two models is challenging. First, resource allocation differs between the models: in the external cost model, predictions are scheduled on server separate from the one handling the jobs, whereas in the server cost model, both predictions and jobs are scheduled on the same server. Incorporating a fixed cost into the mean response time for the external cost model does not translate directly to service time. This leads to potential differences in the interpretation of the costs of predictions between the two models.
Baselines. As baselines, we compare SkipPredict with three distinct policies in the two proposed models. These policies are 1) FCF non-size-based policy that does not require predictions; 2) SPRPT, which involves performing expensive predictions for all jobs; and 3) 1bit advice (Mitzen- macher 2021), which uses only cheap predictions, separating jobs into predicted shorts and pre- dicted longs, and using FCFS as a scheduling policy for each category. These policies, along with SkipPredict, can be placed on spectrum based on their prediction costs, FCFS requires no predic- tions, while SPRPT requires expensive predictions for each job. The 1bit policy and SkipPredict are positioned in the middle of this spectrum, with the 1 policy incurring lower prediction costs than SkipPredict. The question becomes, given prediction costs, what is the most cost-effective policy?
To compare all these policies, analyze SPRPT and 1bit policies in the external cost model and the server cost model. These policies, initially introduced by Mitzenmacher (Mitzenmacher) 2019) 202I], were analyzed without considering the cost of predictions, so in Appendix D.I we re-analyze them with prediction costs.
Without looking at the formulas, it is intuitive that under even moderate loads, when the cost of the expensive prediction is low (close to ct). the total cost of SkipPredict would be greater than that for SPRPT. Also in this case SPRPT would outperform the 1bit approach, are generally more effective than non-size- son-size-based ones when predictions are reasonably accurate. However, when the expensive prediction cost 02 is high, SkipPredict or 1hit would be better options than SPRPT. Note SkipPredict and 1bit have the same response times for jobs predicted to be short, as both schedule these jobs in the same way. Thus, the efficiency of SkipPredict over the bit approach depends on the value of using an SPRPT-strategy for the remaining jobs.
size-based policies
SkipPredict limitations. SkipPredict's performance depends on the accuracy of its predictions, as poor prediction quality would diminish its effectiveness in practical applications. Our experiments (Section 5) demonstrate direct correlation between prediction accuracy and overall performance. Regarding robustness, inaccurate cheap predictions could potentially lead to more long jobs delaying short jobs, highlighting the importance of achieving high prediction accuracy for cheap predictions.
4.3 What if the cheap predictions are not really cheap?
Another limitation of SkipPredict arises in situations where sufficiently low-cost predictions are not available are not substantially less costly than expensive predictions. In such scenarios, Skip- Predict may be less effective. However, on the positive side, our work could provide insights into the necessary cost thresholds for achieving performance gains. Here, we also suggest alternative algorithm, DelayPredict, as a potential solution in these cases. Rather than apply predictions to all jobs, DelayPredict does not cheap predictions, while still avoiding expensive predictions for short jobs. DelayPredict schedules jobs initially with FCFS, but limits each job to a given limit L. We could also consider any non-size-based based policy such LCFS FB.

---

(a) large cost gap. C1
(b) small cost gap, C1
(c) cost vs. threshold
0.5, C2 4
3.5, c2
4
SPRPT
SkipPredict
DelayPredict
Figure 1: DelayPredict vs. SkipPredict and SPRPT in the external cost model with exponential
service times and exponential predictor described in Section [5 (a) cost arrival rate with e₁ 0.5, C2 = 4, T L (b) cost vs. arrival rate with e 3.5, C2 = 4, T = L (c) cost vs.
threshold (T for SkipPredict and L for DelayPredict), a 0.5, C2
0.9.
of service time, at which point it is preempted, and treated as long.job. At that point, the job can go through expensive prediction and be scheduled based on SPRPT scheduling. A job that finishes before L units of service would, in this setting, be a short job that finishes without any prediction. We define 2' --= (ar)dx as the expected fraction of jobs requiring the expensive prediction and use it in Definitions to analyze DelayPredict cost in the external cost model and in the server cost model. We provide mean response times for DelayPredict with proof's in Appendix
DelayPredict SkipPredict. The main difference between DelayPredict and SkipPredict is in the waiting time. In SkipPredict, predicted short job sees only short jobs while a short job in De- layPredict sees all jobs the queue ahead of limited to size L. Similarly, in DelayPredict a long job has to wait behind incoming jobs (including all other long jobs) for at lest time L. Thus, while DelayPredict saves the cheap predictions, its waiting time can be higher than SkipPredict. Figure shows setting where there is cost gap between prediction costs, and SkipPredict outperforms DelayPredict. However, DelayPredict still performs better than SPRPT (with e 0.5, C2 4). When the costs are close, DelayPredict is better than both SkipPredict and SPRPT, as in this case SkipPredict less effective. Since the waiting time of DelayPredict depends on I., we see in Fig- ure I(c) that as I, increases, the cost of DelayPredict gets higher. (Note for comparison purposes the for DelayPredict and the T for SkipPredict are chosen to be the same value.)
4.4 Generalization to Non-Fixed Costs
While we assume that the prediction costs as fixed, our approach naturally generalizes theoretically to random costs from distribution, where that distribution may also depend on the service time of the job. Here we outline the necessary modifications in the analysis for this generalization.
We may consider prediction costs that are assumed to be independent over jobs. The cheap predic- tion cost given by a density function ky (z,c1). where (1 e1) is the density corresponding to
job with actual size and cost of cheap prediction e1. Hence, JC An (Ir, c)dc = f(x)). Similarly, the expensive prediction cost given by density function (z c2). where ky (xx c2) is the density corresponding to a job with actual size x and the cost of expensive prediction is C2-
In our analysis of the server cost model with fixed costs, for jobs with rank 4 in the first dimension, we used r-aa to encode the second dimension of the rank rather than the predicted remaining service time, which we noted is technically r (a not change the rankings of jobs, but for non-fixed costs, we would want to use the actual predicted remaining service time (a 02) for the rank function.
oz). When ei and are fixed, doing so does

---

5 Experimental Results
To gain more insight into when to invest in prediction and how SkipPredict compares to other poli- cies. in this section we compare SkipPredict, SPRPT, 1bit and FCFS using simulation with real- world and synthetie traces in the setting of the single queue with Poisson arrivals. For real-world traces, we used three traces from Amvrosiadis et al. (Amvrosiadis et al.) 2018): Twosigma, Google, and Trinity. Their system leverages machine learning to predict job runtimes in large clusters, uti- lizing features like user IDs, job names, and input sizes, Appendix F contains more details about the datasets and the predictor. For the synthetic traces, we considered two job service time dis- tributions: exponentially distributed with mean (z)) = 6 e) and the Weibull distribution with
cumulative distribution F = 1 e- /2r (which also has mean 1). Also, for the synthetic traces, use two prediction models where each of the two-stage predictors could be from a different model: 1) Exponential predictions (Mitzenmacher 2019), where prediction for a job with service time is itself exponentially distributed with mean r. 2) Uniform predictions (Mitzenmacher 2019), where prediction for a job with service time x is uniformly distributed between (1 axx and (1 + a)x for a parameter a. For the synthetic datasets, in this section we present results for the exponen- tially distributed service time with uniform predictor. Appendix F contains results for the rest of the combinations.
To handle wtoee predictions, both for the real-world traces and for the synthetic ones, the cheap predictor here returns a single bit by comparing the predicted value with the threshold; this is not how an actual prediction would work, but it is just test model for simulation. We note that, as part of verifying our equations and our system, we have checked simulation results for single queues against the equations using the "perfect predictor," the integrals simpler in this case.
Cost vs. arrival rate A. 2 3(d] 4(b) show the cost using real-world and synthetic datasets. These Figures show that investing in service time predictions is more beneficial at higher arrival rates. SkipPredict yields the lowest cost above X = 0.7 in all datasets. We should note, how- ever, that under extremely high load in the server cost model, prediction-based scheduling (SPRPT, SkipPredict or lbit) risks overflowing the system (since the average time per job with predictions is larger than 1), making FCFS a better option.
4(c) we compare the cost vs. T. As T increases, both SkipPredict and bit demonstrate reduced costs. However, past a certain T threshold, which depends on the dataset, arrival rate, and actual costs, we observe a rise in costs due to the decreasing number of jobs requiring expensive prediction. This leads to reduced load for expensive predic- tions, making job size prediction for scheduling between predicted long jobs less effective. In the synthetic datasets, as T gets large, SkipPredict and 1bit become the same, as both serve predicted short jobs similarly, and for large T nearly all jobs are predicted short.
Cost vs. T. In Figures 2gg 2(h 3(a) 3(c) (a)
Accuracy/Cost tradeoff. To evaluate a setting where one has to choose accuracy levels by accu- racy/cost tradeoff, we conducted experiments where we controlled the accuracy, and consequently, the cost, so higher accuracy corresponded to higher prediction costs. Again, the point here is to show a possible use case, where a user might decide from a set of possible available accuracies and costs to optimize the system. The measured total cost is presented as heat map matrix in Figures 5(a) 5(b) using exponential service time and T 1. In this matrix, rows represent the probability accurate prediction and associated costs for the cheaper model, columns represent the 1 values of the uniform predictor, and each cell displays the corresponding total cost for that setting. These figures indicate that reducing the accuracy of the cheap prediction is more crucial since the cheap model's prediction is performed for every job. For expensive predictions, the relationship between a values and the total cost is not strictly linear and the cost can be optimized based on expensive prediction costs and number of predicted long jobs.
SkipPredict benefit increases with larger cost gaps. We have found that SkipPredict is more cost- effective than other policies when there is a difference between the costs of the two predictions, with greater gap leading to higher improvement. In Figures ((o) S(d) we have exponential service times, 7 = 1, ei is fixed to the default value, and we change 02 by varying where C2 = kej. For similar or very close costs (k= = 1). SkipPredict is less useful, and SPRPT may be better option. However, as 02 values increase, SkipPredict becomes more efft-efeet FCFS and 1hit are not affected as they do not require expensive predictions.

---

(a) A, Twosigma, server
(b) X, Twosigma, external
(c) Google, server
(d) Google, external
203
(c) A, Trinity, server
(f) Trinity, external
(g) T, Trinity, server
(h) T, Trinity, external
X
1bit
SkipPredict
Figure 2: Cost in the server time model and in the external model using real-world datasets (a-f) (with T = 4) (g-h) vs. T with Trinity dataset (with 0.6). The default costs for the external model are = 0.5, e2 20, and in the server time are = 0.05, C2 0.5.
8
8
(a) cost vS T External
(b) cost vs. A External
(c)
cost VS Server
(d) cost VS.
Server
SPRPT
FCFS
1bit
SkipPredict
Figure Cost in the external and is configured with 0.8, expensive predictor with 0.2, service times are exponentially distributed with mean 1. The default costs for the external model are 6 0.5, C2 and for the server cost model are 0.01, C2 = 0.05 (a c) Cost vs. T when À 0.9 (b + d) Cost vs. when T 1.
cost models using uniform predictor, cheap predictor
6
Conclusion
We have presented SkipPredict, the first prediction-based scheduling policy we aware of that takes into account the cost of prediction. SkipPredict is designed for systems where two levels of prediction available, good (and cheap) and better (but expensive) prediction. While here have focused on having a binary prediction (short/long) and a prediction of the service time, our frame- work would also work for other settings. For example, both the cheap and expensive predictions could be for the service time, with the expensive prediction being more refined, time-consuming variation of the cheaper process (that even takes the cheap prediction as an input). We considered the cost of prediction in scheduling in two models; the external cost model with externally generated predictions, and the server time cost model where predictions require server time and are scheduled alongside jobs. We derived the response time of SkipPredicr and analyzed total cost formulae in the two cost models for SkipPredict. We similarly derived formulae these models for previously pro- posed prediction policies where previous analyses ignored prediction costs, namely 1it and SPRPT, as well as a new policy, DelayPredict. We have demonstrated, using both real-world and synthetic datasets, that SkipPredict potentially outperforms FCFS, 1bit, SPRPT, and DelayPredict in both

---

(a) cost v8 External
(b) cost vs,
External
(c) cost VS
Server
(d) cost vs. A- Server
X
1bit
SkipPredict
Figure 4: Cost in the external cost and server cost models using exponential predictor for both cheap and expensive predictors, service times are distributed exponentially with mean The default costs for the external model are e1 0.5, 2 and for the server cost model are c₁ 0.01, C2 0.05.
2.8
013
66.2
Expercive 201
MAU
Expencive
(a) External
(b) Server
(c) External
(d) Server
SPRPT
X
FCFS
1bit
SkipPredict
Figure (a+b) cost external and service time models in setting where one has choose accuracy levels by accuracy/cost tradeoff. (c+d) Cost vs. C2 with = 0.5. We use exponential service time with, X 0.9 and
cost models, especially when there a significant cost gap between cheap and expensive predic- tions. While focused analyzing SkipPredict for cases with prediction costs, there many potential variations to explore. These include using separate servers for prediction, offering more than two priority classes, selectively predicting only some jobs with probability to reduce costs while prioritizing between predicted short and long jobs, as well as employing load-based predictions to make predictions only when the queue length exceeds certain threshold.
While scheduling itself a foundational problem that provides sufficient motivation for our work, believe the issue of accounting for the costs of predictions in the "algorithms with predictions" framework (and arguably other similar problems) is understudied. Our idea of choosing one or more predictions, and optimizing the overall cost including that choice, is an approach that we believe will be useful for other similar problems.
Impact Statement. This paper presents work whose goal is to advance the field of Machine Learn- ing. There are many potential socictal consequences our work, none which we feel must be specifically highlighted here.
Acknowledgments
Rana Shahout was supported in part by Schmidt Futures Initiative and Zuckerman Institute. Michael Mitzenmacher was supported in part by NSF grants CCF-2101140, CNS-2107078, and DMS- 2023528.

---

References
[n. d.]. Algorithms with Predictions Paper List.
github.
George Amvrosiadis, Jun Woo Park, Gregory Ganger, Garth A Gibson, Elisabeth Baseman, and Nathan DeBardeleben. 2018. On the diversity of cluster workloads and its impact on research results. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). 533-546.
Yossi Azar, Stefano Leonardi, and Noam Touitou, 2021. Flow time scheduling with uncertain pro- cessing time. In STOC. 1070-1080. https://doi. org/10. 1145/3406325.36666 3451023
Yossi Azar, Stefano Leonardi, and Noam Touitou. 2022.
Distortion-OOliviouss Algorithms https:///oi.orrg/0.. 1137//
for Minimizing Flow Time. In ACM-SIAM. 252-274.
9781611977073.25
Ziyad Benomar and Vianney Perchet. 2024. Advice querying under budget constraint for online algorithms. Advances in Neural Information Processing Systems 36 (2024).
Matteo Dell' Amico. 2019. Scheduling with inexact job sizes: The merits of shortest processing time first. arXiv preprint arXiv:1907004824 (2019).
Matteo Dell' Amico, Damiano Carra, and Pietro Michiardi. 2015. PSBS: Practical size-based scheduling. IEEE Trans. Comput. 65, (2015), 2199-2212.
Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. 2023. Online algorithms with costly predictions. In International Conference on Artificial Intelligence and Statistics. PMLR, 8078- 8101.
Emilia Grass and Kathrin Fischer. 2016. Two-stage stochastic programming in disaster management: A literature survey. Surveys in Operations Research and Management Science 21, (2016), 85- 100.
Mor Harchol-Balter. 2013. Performance modeling and design of computer systems: queueing theory in action. Cambridge University Press.
Benjamin Hindman, Andy Konwinski, Matei Zaharia, Ali Ghodsi, Anthony D Joseph, Randy Katz, Scott Shenker, and lon Stoica. 2011. Mesos: A platform for FraineG) resource sharing in the data center. In 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI I1).
Viacheslav Viktorovich Kolbin. 1977. Stochastic programming. Number 14. Springer Science & Business Media.
Michael Mitzenmacher. 2019. Scheduling with predictions and the price of misprediction. arXiv preprint arXiv:1902.007332 (2019).
Michael Mitzenmacher. 2021. Queues with small advice. In SIAM Conference Applied and Computational Discrete Algorithms (ACDA2I). SIAM, 1-12.
Michael Mitzenmacher and Sergei Vassilvitskii. 2020. Algorithms with Predictions. In Beyond the Worst-Cawe Analysis of Algorithms, Tim Roughgarden (Ed.). Cambridge University Press, 646 662,
/1t./////00////11/077///11111130 037
Michael Mitzenmacher and Sergei Vassilvitskii. 2022. Algorithms with predictions. Commun. ACM 65, 7 (2022), 33-35. https://doi..rgg: 1145/35288183
Salman Salloum, Ruslan Dautov, Xiaojun Chen, Patrick Xiaogang Peng. and Joshua Zhexue Huang- 2016. Big data analytics on Apache Spark. International Journal of Data Science and Analyties (2016), 145-164.
Shaik Mohammed Salman, Van-Lan Dao, Alessandro Vittorio Papadopoulos, Saad Mubeen, and Thomas Nolte. 2023a. Scheduling firm real-time applications on the edge with single-bit exeeu- tion time prediction. In JSORC. 207-213.

---

Shaik Mohammed Salman, Alessandro Vittorio Papadopoulos, Saad Mubeen, and Thomas Nolte. 2023b. Evaluating Dispatching and Scheduling Strategies for Firm Jobs in Edge Com- puting. In IECON. 1-6.
Ziv Scully, Isaac Grosof, and Michael Mitzenmacher. 2022. Uniform Bounds for Scheduling with Job Size Estimates. In ITCS. 114:1-114:30. https://dol orddoi.orr/o....00 4230/LIPICs............./ ITCS.
2022. 114
Ziv Scully and Mor Harchol-Balter 2018. SOAP bubbles: Robust scheduling under adversarial noise. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 144-154.
David Shmoys and Chaitanya Swamy. 2004. Stochastic optimization is (almost) easy as de- terministic optimization. In 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 228-228-22 237.
Chaitanya Swamy and David B Shmoys. 2006. Approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News 37, 1 (2006), 33-46.
Alexey Tumanov, Angela Jiang, Jun Woo Park, Michael A Kozuch, and Gregory R Ganger. 2016. CMU-PDL-I6-10M September 2016. (2016).
Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, and John Wilkes. 2015. Large-scale cluster management Google with Borg. In Proceedings of the tenth european conference on computer systems. 1-17.
Adam Wierman and Misja Nuyens. 2008. Scheduling despite inexact job-size information. In Pro- ceedings of the 2008 ACM SIGMETRICS international conference Measurement and modeling of computer systems. 25-36.

---

Appendix
Table of Contents
A Supplementary Figures
13
B Formulas via SOAP Analysis
14
B.I SOAP Background
14
B.2 Rank functions of SkipPredict
15
C SkipPredict Analysis
16
External cost model
16
Server time mode
17
D Baselines Analysis
21
D.I SPRPT Analysis
21
D.2 1bit Analysis
24
E DelayPredict Analysis
Simulation
30
Datasets descriptions
30
Simulation with real world datasets
31
Simulation with synthetic datasets
31
A Supplementary Figures
102
PCFS
SPAFT (Cwb)
SPHIT (u-030
SPRFT
Cost Response Time
201
0.6
Figure 6: Considering prediction cost in SPRPT algorithm in M/M/1 system. The cost is the sum of mean response time and fixed prediction cost.
1-bit prediction: short Skip or Predict: sipp short
lsng presitt short
long predlct
shorz skip shert
Ky
X,
X2
X
Figure 7: The SkipPredict algorithm.

---

B Formulas via SOAP Analysis
We employ the SOAP framework (Scully and Harchol-Balee 2018),
(relatively) recently devel-
oped analysis method, to obtain precise formulas for mean response time of SkipPredict in both the external cost model and in the server cost mode. While we could analyze the external cost model without SOAP as two-class system, we choose to use SOAP for a consistent analysis.
B.1 SOAP Background
The SOAP framework can be used to analyze scheduling policies for M/G/1 queues that can be expressed in terms of rank functions. Recent research by Scully and Harchol-Balter (Scully and Harchol-Balter 2018) has classified many scheduling policies as SOAP policies. These policies determine job scheduling through rank, always serving the job with the lowest rank. (In cases where multiple jobs share the lowest rank, the tie is resolved using First Come First Served.) The rank function determines the rank of each job, and it can depend on certain static characteristics of the job, often referred as the job's type or descriptor. For example, the descriptor could represent the job's ss class (if the model has different classes), and other static attributes, such as its size (service time). The rank can also depend on the amount of time the job has been served, often referred to as the job's age. A key assumption underlying SOAP policies is that job's 's priority depends only on its own characteristics and its age, an aspect that aligns with our model and scheduling algorithm SkipPredict. We refer the interested reader to (Scully and Harchol- Balter 2018) for more details.
SOAP analysis uses the tagged-job technique. That is, we consider tagged job, denoted by J, of size n, and with descriptor d,j. We use a, to denote the amount of time J has received service. The mean response time of is given by the sum of its waiting time (the time from when it enters to when it is first served) and the residence time (time from first service to completion). To calculate the waiting time, SOAP considers the delays caused by other jobs, including "old" jobs that arrived before J and "new" jobs that arrived after J. A key concept in SOAP analysis is the worst future rank of a job, as ranks may change non-monotonically. The worst future rank of a job with descriptor d, and age a is denoted by rankkyr (aJ). When a. = O, the rank function is denoted by Tworst rank (0). Ranks are written in (angle bruckets).
In the SOAP framework, waiting time is shown to be equivalent the transformed busy period in an M/G/1 system with arrival rate À and job size X (rank (a)] [ The initial work of this period represents the delay caused by old jobs. To deal with the delay due to old jobs, SOAP introduced a transformed system where jobs are categorized based on their rank. Discarded old jobs, exceeding the rank threshold Tworst, are excluded from the transformed system. Original old jobs, with a rank at or below Tworst, are considered as arrivals with rate À and a specific size distribution X wooeel] 5 Recycled old jobs, currently at or below Tworst but previously above this threshold, are treated as [rworat ( for i 2 in the transformed system. As explained later, in SkipPredict jobs could only be recycled once,
server vacations of length [r
only have X [[worac]-
SOAP shows that, because Poisson arrivals see time averages, the stationary delay due to old jobs has the same distribution as queueing time in the transformed M/G/I/FCIF system. This system is characterized by 'sparse' server vacations, where (original) jobs arrive at rate and follow the size distribution [rworat)
We note that SOAP provides for finding the Laplace-Sticltjp transform of the response time distribution;
we focus on the mean response time throughout this paper for convenience in comparisons.
"x" (rank") woet (a)] is a random variable representing how long new job that just arrived to the system is served until completes or surpasses rank worst (a)
xx [r is random variable representing how long a job served while it is considered original with respect the rank Fworst
"x.lll [x [[oors]] is random variable representing how long job is served while it is considered recycled for the time with respect the rank Yworst

---

Theorem (Theorem 5.5 of (Scully and Harchol- 2018)). Under any SOAP policy, the mean response time of jobs with descriptor d and size 2,
X Ei E X [oorst]
B[T(IJ.)) 2(1 XE o Faorrtt] (1 XE| Xnew Ceneerrrcon (wworst)
1 AE X (rankkk (a)l da.
B.2 Rank fuucction of SkipPredict
The relevant attributes to SkipPredict are the size, the 1-bit prediction, and the predicted service time. We can model the system using descriptor D [size, predicted short/long, predicted time] Jr, r. SkipPredict in the external cost model results in the following rank function:
{ (1,-a) rankieat (10, r), = (2, a)
if = 1, if = 0.
which uses the first dimension to encode the class priority (short or long), and the second dimension to enforce the priority for each class (FCFS for short jobs, SPRPT for long jobs). In such nested rank function, the first dimension serves the primary rank, with the priority ordering following lexicographic ordering.
In the server cost model, SkipPredict results in the following rank function:
(2, a)
0 < a S e₁ (initial rank, and cheap prediction),
{1, -a)
b = and
ci (short jobs after cheap prediction),
(1,
(3, -a)
if b = 0 and Ci + 02 > > ci (long jobs, expensive prediction),
(4,r a)
if b = 0 and 2 ci C2 (long jobs after expensive prediction).
(2)
Note entering jobs have ranked in the first dimension, placing them behind short jobs awaiting or receiving service. Since after predictions short jobs would simply be placed behind other short jobs, it makes sense to deprioritize the cheap predictions. On the other hand, we prioritize long predictions over long jobs to implement SPRPT.
Finally, for jobs with rank in the first dimension, we use r a as the secondary rank. Technically the predicted remaining service time is (a Ci 02), since the job's age includes service for predictions of time G1 c2. As ej and C2 are fixed, using r a is equivalent to using r -(a- (a-c) - 02) for ranking, and we use a for convenience.

---

C
SkipPredict Analysis
Table 3: Definition and Description of symbols used in the equations
Symbol
Description
ElS lo x pr(x) [(x) do R | pr())) x g(x, ddddy
Expected service times of predicted short jobs Expected service times predicted long jobs with service time prediction S Expected service times of predicted short jobs in- cluding prediction cost C1
+c) pr(x)- f(x) dæ E|S [T So
So (x
Per م-= x dx
Load due to predicted short jobs
P = [B|S B[S
Load due to predicted short jobs, predicted long jobs with service time prediction Load due to predicted short jobs and their cheap prediction cost
PPS = (a1 + E[5
00 (B|S (c)) (c)s (c) c2) ((T))((TT))
Load due to predicted short jobs, predicted long jobs with service time prediction S r, and prediction jobs
a(r) l - (z)) (
Integral related to predicted long jobs
(x (t - -r)) dx dt
with service time prediction > r
Q(T, = رfر l - -p((x)) g(a,, dadd
Probability of a job being predicted as long with service time prediction
C.1 External cost model
Lemma 1. For SkipPredict in the external cost model, the expected mean response time for pre- dicted short job, ETTEeS PS is
SESS Ext 2(1 P'T
PS
E[S
Proof. While SOAP can be used to analyze the mean response time for predicted short jobs, this case is straightforward and follows the mean response time in the system for FCFS, which is given by Equation 23.15 in (Harchol Balter, 2013).
Lemma 2. For SkipPredict in the external cost model, if we let a(r) - pr (z))g(Z, t) (t r)) dx dt, the expected mean response time for predicted long job of true size n and predicted size is
EIS 1 ( + 1")
([T 2(1 peztya
da
DGg-a)+
Where pfat = X (E(S')T)+ + is the load due to jobs of predicted short and jobs predicted long but their service time prediction less than and (r a)+ max(r 0).
Proof. To analyze SkipPredict for predicted long job in the external cost model using SOAP, we first find the worst future rank and then calculate X'new (rank (a)). [r and X f [rworst] for predicted long job. As described in (T). the rank function for predicted long jobs monotonic (here the job descriptor is d, = [xJ, 1, r),, and every job's rank is strictly decreasing with age, thus

---

J's worst future rank is its initial rank, here: ranksy (a) = (2, r d) and Tworst rankay (0) r2,
X"* (ranky. Suppose that new job K of predicted size rx arrives when J has age a.- Jss delay due to depends on whether K predicted to be short or long. If is predicted short then it will preempt J and be scheduled till completion because it has higher class. Otherwise, if K has a predicted job size less than J's predicted remaining process time (r a.)), K will always outrank
J. Thus
X new 2K
12, - a)] =
KK
K is predicted short is predicted long
(rx <r- a)
/000000 pr(z)x + // x 21 (r(x)))((1 (),
[ 0 x==
E new (2, - -a/]]
X :: Whether another job I is original or recycled depends on its prediction as short or long, and the case long, it also depends on predicted size relative J's prediction. If predicted short, then it remains original until its completion. Otherwise, if T is predicted long, 7 is original only if rr S r, because then until completion rank never exceeds
xT 1r) s)
if is predicted short if T is predicted long
X [(2 = 0.2y
B[X8 (2 r)) = / pr(x)=((z)dz f (1 pr(x)) x g(z, gddddy ==0
[[(( [12,,)1)) = - pr(x)x² Pr(x)x² f(x)dr + l ( (1 (-r(())) x² g(x, u)dady y= J=0
000
X Tworst]: ]: If another job I is predicted long and if > then starts discarded but becomes recycled when 11 r. This starts at age a F4 r and continues until completion, which will be Σι a1 = (r1 r). Thus, for i 2 2, X 1,21 [(2, r) 0. Let ry:
0
if is predicted short
X 1 [2,
[1 (t r) if is predicted long
g(x,t) 1). (x - (t ? dadt (1 pr(x)) (
/ 1 -=ttr
((x
Applying Theorem leads to the result.
C.2 Server time cost model
To analyze the server cost model, as explained, considering the rank function defined 2 we first find the worst future rank of J, denoted as rank-yort as follows:
[ (2, aa) (4, a) if predicted long
if J is predicted short
rank worst (a)

---

Lemma 3. For SkipPredict policy in the server time cost model, the expected mean response time for a predicted short job, E E srv
A. ( 2c, 2c1
+ FE(Ser]
2(1 PPS)
where PPS = A (c1 + E[S is the load due to jobs of predicted short and their cheap prediction cost.
Proof. To analyze SkipPredict for predicted short jobs, we calculate X (rankl) worss (a)], Xo [Tworst] and (rworst] for these predicted short jobs in the server cost model, where the job descriptor in this case is (b,r) = (1,
Let's consider new job arriving when is at age (where 0_5 S min(r, x.)). The worst rank of J depends on whether J is predicted to be short or long. If J predicted short, then J's worst future rank is its current rank (2, -a.)- Given that K's initial rank is (2, 0), at least equivalent to J's worst future rank, the delay J experiences due to K is: Xxx [(2, aa)]
X (rankys
X [ : Suppose that witnesses an old job I of initial size IT. The duration for which remains original depends on whether its prediction is short or long. If I is predicted short, remains original until completion. Alternatively, if / is predicted long, it would remain original until the cheap prediction phase (lasting c1), after which its rank shifts to (3, 0).
Cc +
if is predicted short if is predicted long
Xold 0,zy
[2) =
C1
E (2x00 0)]]= + { pr())xf(z)dz
X Faworat:: There are no instances of recycled jobs because either completes its service (if predicted short) is discarded completely (if predicted long). and thus never gets rank lower than (2, 0). Thus, for i 2 1,
X [22, 0)]
Applying Theorem yields the result.
L
Lemma 4. For SkipPredict policy in the server time cost model, the expected mean response time for a predicted long job of true size J, and predicted size is
A
EJS"
2 (c)) + + ( E.S 2(c + c2)l a(r)
2(1 pārv)z
12
+
da
P(r-a
Where Q(T,r)= = [ 100 (1 pr(x)) g(., y)drdy (r- 300+==mal( - a, 0)
= X + (er +2) + 02)))
is the load due to jobs of predicted short and jobs predicted long but their service time prediction less than along with the load of the jobs predictions.
a(r) 2=1-r
(1- pr (x)) ()xx (t rr)) dx

---

Proof. Now we calculate X [ (ranka) ["oost] and [rooss)] for predicted long jobs in the server cost most, here again the J's deseriptor is ((b, r) = r))
X (rank (a)]: J's delay due to K also depends K is predicted to be short long.
c1 zk ci + JK (rk <r-
K' is predicted short
x [4,r -a)]
K is predicted long
Employing the joint distribution g y), and setting I (rx < r ar) So=u g( v)dy, we can derive J's expected delay due to any random new job:
[ pr(2)of(z)dr p
[[ aل}ll =01 +
r-as
{e (1 (1-pr(2))ag(r,, ydddy
[ [woorat]: Regardless of I's prediction, an old job has higher priority than J, therefore J will be delayed for the duration of I's service
c + 21 Xol [(4,
if is predicted short
ca +2 1(rr s)
if is predicted long
E((X0" [1,1 [ +2)
f / (1 pr(x)) g(x, v) (cr + o2) drdy
y= x=0
(1 (1-P1 (r(p)(x)) g( (a + x) drdy
y=0 1=0
B((xo" ((4r))))3 = ( (r(x)((1 +z)) + / 1 (1 pr(x)) g(x. v) (cr + o2)² drdy
y=r x=0
[ (1- (r))) g(., (a c2 + x)²² drdy
X [:ooss:]: predicted long, job / may recycled. This occurs when / predicted long and with an expensive prediction r. is initially considered original and is served during
the cheap and expensive prediction phases, then discarded. At age aj ri - r. is recycled and served till completion, which will be æΙ as t = rz:
(rI r). For i > 2, X [(2 r)] 0, let
0
if is predicted short 11 - (t r)) if is predicted long
Xold [(4,
100
B[ (4, 1
(1 - pr(x)) g(x,t) (x (t -r))² dzdt
t=r z=t-r
Applying Theorem
I yiells the result.
Lemma 5. The mean response time for predicted long jobs in the external cost model is
Sy=o(t
pr (r()))g(z, y ET(r, y)1 dydr g (1 PT (x) ddddd
PL eat
00 -

---

and in the server cost model is:
Se - (1r(pl)))))) ()) Se (y=o(1 - pr())))(1, y) dydr
(T) (z, v) w)
E TTT

---

D Baselines Analysis
D.1 SPRPT Analysis
In SPRPT the job descriptors only include the job size and service time predictions, e.g. D = [size, predicted time] [z, rl. Thus, the rank function in the external cost model is:
ranker (12, rl,a)
(3)
In the server cost model:
(1, aa) (2
i a S ci (initial rank, scheduling prediction), if a ci (joss after prediction).
(l b),
Lemma 6. For SPRPT in the external cost model, the expected mean response time for a job of true size I and predicted size is
2(1 - 211-?,)3 (rr o7 (rgg(1,)))dn d)dr,d
(T), SPRPT
g( (01- (t (r))) dx + (a)
I1 1 l-p(raaat
+ =1=t-r
da,
where d, = À مل= u(I1,))dr
Proof. SPRPT has a rank function rank(r, a) r for job of size and predicted size r. As this rank function is monotonic, J's worst future rank is its initial prediction:
rank
worst (a) r a.
When = O, the rank function is denoted by Yworss ran k werst
و (0) = r.
X krank d..7. (a)] computation: Suppose that a new job K of predicted size r'x arrives when has age a. If K has predicted job size less than J'ss predicted remaining process time (r a), K will always outrank J. Thus
Xnew [r a) xK 1xl(rx <r-a) ox
B[ (r al]
JK glø,, dy
Ixx=
X- [[worst] computation: Whether job / is original or recycled job depends its predicted size relative to J's predicted size. If ri & r. then I original until its completion because its rank never exceeds r.
Xold [r] 2,1(rr sr).
E [r] = l 0 Dt g( dr
1y=0
1"
E((x0 (r))2]]
ot g(11,1)do
y= Jayo

---

X Tworst] computation: Ifrr >> r, then I starts discarded but becomes recycled when a This means age - r and served till completion, which will be 2, ar Iz (ri - -r),
let / = ry:
Thus, have
oold 1,y
[r] = æ - (t - r).
For i 2 2,
X
[r] = 0. 1,2y
g(r,,t) (2, -1y- (t-r))--))+ dr,dt.
Applying Theorem 5.5 of SOAP (Scully and Harchol BBaterr 2018) yields that the mean response time of jobs with descriptor (r)) and size œ, is as follows. Let
2ι g(z1,))dz P f
00
y= 001=
Then
(S - +7 g(0r, ydd + Jt 100 g(1,,) (xr - (t (5-r) r))² dxydl)
(T), SPRPPT
2(1 22)-
L 1 P/)-a)+
1 du.
1-
Let fp(y) S g(, y) ya. Then the mean response time for job with size æy, and the mean response time over all jobs are given by
E[T(x))
y=0
100
STRPTT
((T())
dydd...
2= y=0
Lemma 7. For SPRPT in the server time model, the expected mean response time for a job of true size J and predicted size is
J oi g(x, ulr,vydady- Jy
f (c2+ +x)+2)) (g(a1,,)))rre g)drrdy
B[T ) 6rU
SPRPT
2(1 ?
(t- ((-r)) rt- -))r))d)dd())))))))))))))){))) 10a 1 -ooo da,
+
g(x1,t) -x1-
where P. (02 + ly So 2i g(æn, dyy.
Proof. Xnew (rank J's worst future rank is (2. ay). In this case, J'ss delay due to new job K is plus Jæ is its predicted service time less than J's remaining process time.
Xnew [ a.)l 02 xx 1(x < <r-a.).
xx
X (2, a.m)]
02 +
JK gll., u)daky =xx=

---

computation: In this model, old job delays J at least In addition, If r1 S r, then is original until its completion because its rank never exceeds r.
[worrst] [raored X
Xol 0,2, (2, a.) = 02 + x/1(11 s)).
E[XO (2, 1 as)l 02 f xr g(zr,
x
=:=0
f Sr cg g(x, (d).yy + S Jer (02 + x1)² ( yor
[( (2, aa)))
g(r vddx
X X I worre computation: Ifrr > r, then / starts discarded but becomes recycled when ri a This means at age r7 -- and served till completion, which will be 2, as = (r) - rr) let t ry:
Thus, we have
X (2, r - a,) = Iı - (t (t- r)).
For 2 2,
X 1,,,
(2 - a,) =0. 0,
B[xpM (2,r - = | Sr
g(01,)) f). (x1 - (t (t-r)) r)) dx,dt.
--
Applying Theorem 5.5 of SOAP (Scully and Harchol Balter 2018) yields that the mean response time of jobs with descriptor (r) and size æ, is as follows. Let
pf = 02 +
21 g( g(I1, yo
x1=0
Then
[[T(,,,)) (r)), SPRPT
2(1 p') (1 o/ g(x, v)drdy + I" y=0 f
A
y (c2 ( ydr
+ 1 1 g(æn,t) (x1 (t (t-)))² drydt) 1n)
1
1 1- da
Let fp(y) f y)dr. The mean response time for job with size v, and the mean time for a general job are give by
ET((2)) I (1)))(((
E
SPAPT lext
g v) ET,r,, dydde
== y=

---

D.2
1bit Analysis
For the 1bit policy, we define the rank function of this approach and then analyze using SOAP framework. Here the job descriptors only include the job sizes and binary predictions, e.g. D [size, predicted short/long [z, b].
rankent((z,bbl = (1, a) (2, -a) if 0.
i 1,
(5)
In the server cost model, this approach results in the following rank function:
(2, -a) 0 - a S c1 (initial rank, and cheap prediction),
rank (1z, a) = (1, a)) if = 1 and > (short jobs after cheap prediction),
(6)
(3, aa) if 6 0 and
e₁ (long jobs after cheap prediction).
The mean response time for predicted short jobs of this approach similar predicted short jobs of SkipPredict as nothing has changed.
Lemma 8. For the Ibit policy in the external cost model, the expected mean response time for predicted long job of true size ZJ is
PL where Prew = Ao Pr ( (x))a, the load due to predicted short jobs.
X
EiS /
1-pert da,
2(1 p)(L Pnew
Pnew
Proof. To analyze 1-bit advice for predicted long job in the external cost model using SOAP, first find the worst future rank and then calculate X"ne [rank (a)]. -xol for predicted long job. For predicted long jobs, the rank function is monotonic as described (5) therefore I's worst future rank is its initial rank.
[I [[worst] and X [woorst]
rank (a) (2, -a),
and Tworst = rank (0) = (2, 0).
X X (rankk Suppose that new job K arrives when J has age a,. J's delay due to K depends on K' is predicted to be short or long.
Only if K predicted short then it will preempt J and be scheduled till completion because has a higher class as long jobs are scheduled also according to FCFS so in case of K predicted long will preempt
Xnew [(2, -a)] {Io sx
K is predicted short.
B[ [(2, -a)]] / pr (z)))
(rworst: Now if old job 7 either predicted short long is original job then it remains original until its completion (regardless of if it is predicted long or short). Thus, for 2 1, X [(2, 0)] 0.
Xol 0,5y [(2, оУ] rI-
E| E[xO (22, (2, / xf(x)dx.
B[(xpd (220)))11 = ( x² f()

---

Applying Theorem 5.5 of SOAP (Scully and Harchol-Balee
2018 yields the result:
x² (((() dr + /
E(T(et)lent 2(1 - p)(1 Pree J
da,
P
where Prev = X ( (x)))x
As second way of thinking about this proof, it can be said that this is the original FCFS system with slowdowns caused by subsystem (predicted short jobs) which is
1-Peew
Lemma 9. For the Ibit policy in the server time cost model, the expected mean response time for predicted long job of true size J. is
2(1 - Pa.)11 Pee 10 (x) dr (0d
[ 1b...
da,
phew
where Prew = (a + S0 pr (x))) and Per = A (So (x)
Proof. In this case, according to 66. J's worst future rank is
rank (a) (3, -a)
and Foorst rank (0) (3, 0).
X X (rank (a)]: Let's say J has age a when K arrives. The delay caused by K for J depends on whether it is predicted to short or long for K. K predicted short then it will preempt and be scheduled along with its cheap prediction till completion. Otherwise, if K is predicted long, will delay only for the cheap prediction.
c1 + FK
K is predicted short.
Xaew zx
[3,, -aj)
12
K is predicted long.
[[ -a)]] =c1 + /. f
[ [woost]]: Each old job is scheduled for cheap prediction (which costs 01), and an old job I, regardless of whether predicted long or short remains original until its completion. Thus, for i > 1, . [3, 0)] 0.
reld [3,00] = c1 + wy 0,37
E E[ ((3, 0)]] / (cr + (x)dd
(" (ar + fz))
[[(x0 (3.0))))
Using Theorem 5.5 of SOAP (Scully and Harchol
2018) yields the result:
2(1 - (1 pary 1 (a (x+ dr [ 22
X
E(T(x)))
Pb 1bitt.
da,
pery
where Prcvo = A (aI + f0º pr(z)=f(z)dd)
Pe. = > (x

---

E DelayPredict Analysis
Rank function of DelayPredict: We model the system using D [size, predicted time] [ar, r]- Here we assume that the service time prediction r is greater than L, because jobs that require expen- sive prediction
longer than L. Since job's age L when it is preempted and obtains predic- tion, in the external model, the predicted remaining time for long jobs is r L - (a L) For the service time model their age after being predicted starts L C22 so the predicted remaining C2. As C2 is fixed among all jobs, instead of the predicted use r a as the rank for convenience. Accordingly, DelayPredict in the
a.
time is r - L - (a- - L (2) = r remaining time external cost model has the following rank function:
(1, (1,
i a
(x,, = r2 aa)
In the server cost model, Delay results in the following rank function:
(1, -a)
0 S a < (initial rank),
(on = (2, a if L S < L + c2 (expensive prediction calculation), (8)
(3,r a)
if L c2 (long jobs after expensive prediction).
For DelayPredict in both the external cost model and the server time cost model, the expected mean response time for a short job is
Lemma 10.
(10)) J_ (1((s)dde) S xf(d)d
S E[T lent
B[T B[T]arr Pelaccte Jarv
2(1 11-pi PL.)
where PL = > (Jo (f(xd + + T.f(x)dx)) the load due to jobs while limiting their sizes to L.
Proof. We first find the worst future rank and then calculate X frank kworst (a)], [r [oworrd] and X [worrst] for short jobs. As both the external cost model and the server cost model treat short jobs the same, and their worst future rank is the same, the analysis holds for both.
For short jobs, the rank function is monotonic, therefore J's worst future rank its initial rank: rankaaa (a) (1, (a)
and Tworst rank (0) (1,
X (rank,y) Since short jobs have higher priorities than long jobs, and they scheduled FCRS, job does not preempt J. Hence X ((1, -a)] 0.
[oll(r [Twors]]: If an old job I is short, it remains original until it is completed. Otherwise, it remains original only for J. times. Thus, for 2 1, Xold 1,07 [1, 0)] 0 and
xt if is short
Xold [[1,0]]
(L
if is long
El (1, /' xf(x)dæ { f Lf(x)dr
E[(xo 0)1) = /' x² 2²f(x)dz | f2f(x)dr
Applying Theorem 5.5 of SOAP (Scully and Harchol-Balle 2018) yields the result
A
( f())) dx 1. L2 (2f(x)dx + (" =f(x)dr,
2(1-pr) - pr.) where PL === x/((x)dr + S ((()do).

---

Lemma 11. For DelayPredict in the external cost model, the expected mean response time for long job of true size 2 and predicted size r is
reez DelayPredict,
À
|/ T.
f2)(x
2(1
pe
[
x g(z, ydddy = - 000 [r.
+
L -(( y)drdy
ymm Jamt.
aml.
00
g(x,t) t)- (x- - L (t r])) -dddt)
da,
-Z=L---r
Pi,(r-a)+
where PL. > (Tr 2 x(()dx + fy g(x, y)dxdy + San I. g(r, y)dady) the load due short jobs, long jobs predicted be less than r, and other long jobs with their size limited at L. Here a)+ marl= a, 0).
Proof. To analyze DelayPredict for long job in the external cost model using SOAP, we first find woosst (onnk)os(()]] (a)]. X [worrss and X [Twostt] for long job. As described in 7 the rank function for long jobs is monotonic, and every job rank is strictly decreasing with age, thus J's worst future rank is its initial rank, here: rank (a) = (2, a)
the worst future rank and then calculate X=e [rank
and Tworst = rankka (0) = (2,r). r)-
X [ delay due to K depends on whether K is short or long. If K is short then it will preempt J. since it has a higher priority, and be scheduled till completion. than J's predicted remaining process time (r-ay). K will preempt and proceed until completion. Otherwise, K is long and has a predicted job size more than J's predicted remaining process time, it will preempt J but will be scheduled only for I. time.
Suppose that a new job of predicted size r'k arrives when has age a.s. J's
K is long and has predicted job size less
Thus
a x (rk <r- a)+ + L. I.(( 2- K is long
K is short
X [(2rr a)l
1' ==
p-a S x. (rrg(yy))ddd + I L g(x, y)ddd
E[X (2, (2, - a3ll
xf(x)d +
y=0 Z=L
X I :: Whether another job I is original recycled depends whether it is short long, and in the case it is long, it also depends on its predicted size relative to J's prediction. If is short, then it remains original until its completion. Alternatively, if 7 is long, it is original until completion ry & r, otherwise, it is original until L.
[gK [ 1 (rk <r) + 1(x 2r) is long
K is short
1, [(2,))]
1d xf(x))d++ 1 / x g(x glo,y)dody + /
E[xold ((2,
L g( vdddy
==
y=r J=
/ x² f()(() + SrS 2
x² g(z, y)ddd f I.? g(r, y drdd rmml
In
Xold(r [Tmorst]: If another job I is long and if rr >> then starts discarded but becomes recycled when PT r. This starts at age = ri - r and continues until completion, which will be
I L 0l II L (ri r). Thus, for > 2. X ((,r)) r)] 0. Let rf:

---

[0 [(2,))]
if I is short
1,,
21 L (t (0-r) r)
if I is long
70 00
E[ (2,r)1
(x,() (x- L (t -()= drdt
t=r
Applying Theorem leads to the result.
J x² f(z)dr
r)) Deat
DelayPredict,
2(1 y2
x² g(z, drdy + / yEr IzLL
+
L² g(x, V)dady
s=
g(rl1) (x L. (1 - r))² .d.dddd 1mm 1 -T,,(r-a)
1
da
Where PL
+ Syoo x g( yrdy + ly Sa L. g(Ø, yddddy.
Lemma 12. For DelayPredict policy in the server cost model, the expected mean response time for a long job of true size I. and predicted size is
00 ( f(((dddz + / (x (2+ o2) -g), y)rry x=0
L
E[T r) I
DelayPredict,
2(1
PL,))
a=0
(L+ 02)² g(s, u)dody
y=r I=
00
gl2, 1)- (x - (1- dodl + /0-
ass
da,
PL,t-aat o)+
where PL. - = (f)) fr (x
g(a, yddady------ + J + (z) g( 1) yddrdy
is the load due to short jobs, predictions for long jobs, long jobs predicted to be less than r, and other long jobs with their size limited at L. Here (r a)+ = max(r a, 0).
Proof. In this case, J'ss worst future rank is rank (a) (3, a) and Tworst rank worsst (0) d, (3,r). r). Now we calculate n [rank hooostt (a)), [p [worst] and [rworst] for long jobs in the server cost most.
X X [ronkkkk (a)]: J's delay due K also depends K is short long. If I short, then remains it is scheduled until its completion. Alternatively, if is long its prediction is scheduled for c2. In addition, if rf then it is scheduled until completion, otherwise it is scheduled until L.
[KK ( + +x) 1(rk <r a.) + (02 L)) 1(r 2r-a)) K is long
K short
XBEW [(3, r a.}l = EK
2
p-a
1 (x+02) 02) g(ø, y)drdy
00
E (ynew(33r - a}ll = 2f(x)dx
2=0
y= E=b
f /
00
(L (2) g(z, v)dxdy

---

[ [wwors]]: The analysis is similar to the new arrival job. Whether another job is original or recycled depends on whether it is short or long, and in the case it is long, it also depends on its predicted size relative to J's prediction.
[K (c2 xk) 1(rx <r) +c2 L)) 1(rx 2r)
K is short
X [(,rr]]
K is long
[3, r)]] = ' xf(x)dz + f I (x + 02) g( v(x,y) + f
00
00
(L + 02) g(x, ((x.d)
x=0
y=r
[3( (3,r)))²]] ["' Ma))) [" [ (a oz) g(a, vddady
000 f Se (L+ g(x, ddddy
X [F:orss]: As described before, if another job 7 long and if r, > r, then / starts discarded but becomes recycled when ry which will be 2ı - L, 31 I. (rr r). Thus, for i 2 2, Xold i,zy [33, r)] = Let = rT:
This starts age rr and continues until completion,
00
/ is short / long
1, [3,
21 L - (1 ( r)
700
E E old 11,.11111-1
J (x,tt) (x L (t r))² drdt drdd
J 1=L+t-
Applying Theorem leads to the result.
2(1 - p2,))² ( d'f(z)dz+ [" l
(x+c2)² [ (x
E[T DelayPredict, 1)r
g(x,, yddd
(L+ c2)2 g(x, y)drdy
g(x, 1). (x 1- (1-r))) drell (m)
1
da
-z=
PL](r-a)+
Where pL. (Iim of(x)dæ (x + 02) g(x, y)dxdy + Syer So (L + 02) g(x, 2)dddy

---

F Simulation
F1 Datasets deseriptions
F.1.1 Real-world datatsets
For real-world traces, we use datasets from Amvrosiadis et al. (Amvrosiadis al. 2018).
TwoSigma Dataset: The workload traces originate from two data centers of TwoSigma, a hedge fund company. The workload comprises data analytics jobs processing financial information. A portion these jobs utilize Spark (Salloum et al. (0166) while the remaining jobs are handled by proprietary data analytics frameworks developed in-house. The dataset spans period of months, starting in January 2016, across the two data centers' operations, encompassing a total of 1313 identical compute nodes equipped with 31512 CPU cores and 328TB of RAM. The logs contains 265, 029 jobs and were collected by an internally-developed job scheduler running on top of Mesos (Hindman et al. 201T).
Google Dataset: In 2012, Google released a trace of jobs that ran on one of their compute clusters.
The workload encompasses both long-running services and batch jobs (Verma et al. 2015). Some of these were issued through the MapReduce framework, and executed on 12583 heterogeneous nodes in May 2011. The dataset used contains 385, 072 jobs. Google has not disclosed the exact hardware specifications of each cluster node in this trace.
Trinity is the largest supercomputer at Los Alamos National Laboratory (LANL), dedicated to capability computing. Capability clusters are large-scale, high-demand resources intro- ducing cutting-edge hardware technologies that aid in achieving significant computing milestones, such as higher-resolution climate and astrophysics models. Trinity's hardware was deployed two pre-prood pr-podudution phases before being fully operational, and the trace was collected before the comple- tion of the second phase. Trinity consisted of 9408 identical compute nodes, totaling 301056 Intel Xeon E5-2698y3 2.3GHz cores and 1.2PB of RAM, making it the largest cluster with a publicly available trace by number of CPU cores. The dataset we used contains 18, 872 jobs collected by the MOAB scheduler.
Trinity Dataset:
Their system leverages machine learning to predict job runtimes large clusters, utilizing features like user IDs, job names, and input sizes. For each job, we have the actual runtime and predicted runtime in seconds, with runtimes summed across tasks for multi-task jobs. We only consider suc- cessfully completed jobs and normalize runtimes to mean of I, consistent with the synthetic traces.
Service time predictor for the real-world datasets
For these datasets, (Amvrosiadis et al. 2018) used JVuPredict, the job service time predictor of the Jamais Vu scheduling system (Tumanov al. 2016).
JuPPrdditt is runtime (service time) prediction module that is part of the Jamais Vu system. Its primary objective is to predict the runtime of a job when it is submitted, utilizing historical data regarding past job characteristics and runtimes. JVuPredict deviates from conventional approaches by attempting to identify jobs that repeat, even when successive runs are not explicitly declared as repeats. This approach proves to be more effective because only the relevant historical data pertaining to the newly submitted job is utilized to generate the runtime estimate. To achieve this, JVuPredict leverages various features of submitted jobs, such as user identifiers and job names, to construct multiple independent predictors. These predictors are then evaluated based on the accuracy they achieve on historical data, and the most accurate predictor is selected for generating future predictions. Once prediction is made for new job, that job's data is added to the historical dataset, and the accuracy scores of each predictor model are recalculated. Based on the updated accuracy scores, a new predictor is chosen, and the process is repeated for subsequent job submissions. In general, JVuPredict employs a dynamic approach, continuously refining its prediction models by incorporating new job data and selecting the most accurate predictor for each new job submission.
E.1.2 Synthetic datasets
For the synthetic traces, we considered two job service distributions; exponentially distributed with mean I (f(x)) ([(x)=e+e =²) and the Weibull distribution with cumulative distribution F 1- -22 The
Weibull distribution is heavy-tailed, so that while the average service time remains 1, there are many

---

more very long jobs than with the exponential distribution. For predictions, we used two prediction models; exponential and uniform predictions. Table 4 summarizes the quantities pr(z) and g y) for our prediction models. Each of the two-stage predictors could be from a different model.
E.1.3 Simulation
In our simulation, each data point is obtained by simulating initially empty queues over 0000 000 time units. The average response time is calculated for all jobs that terminate after time 100, 000. This process is repeated over 100 simulations, and the reported data point represents the average response time across these 100 simulations. We implemented the simulation in Python 3.7.6. The evaluation was performed on an AMD EPYC 7313 16-Core Processor running Ubuntu 20.04.6 LTS with Linux kernel 5.4.0 -22ggeneric.
Model
pr(
g y)
Perfect Prediction
if <
e-
Exponential Prediction
(
if & (1 a x
Uniform Prediction
1
if 2 (1 a)æ
200
T (-(1-0)z 2ne
otherwise
Table 4: Prediction Models and their Functions
F22 Simulation with real-world datasets
Here we present the cost vs. T simulations of the the rest of the real-world datasets, Twosigma and Google.
179
(a) Twosigma, server
(b) Twosigma, external
(c) Google, server
(d) Google, external
SPRPT
X
FCFS
1bit
SkipPredict
Figure 8: Cost T (with À 0.6) in real-world datasets (Twosigma and Trinity) in both the external and service time models. The default costs for the external model are o₁ = 0.5, C2 = 20, and in the server time are C₁ 0.05, Co 0.5.
F.3 Simulation with synthetic datasets
Here present some additional simulations of the the Weibull distribution using both predictors.

---

8
(a) cost VS C2 External
(b) cost vs T External
(c) cost vs. À External
8"
(d) cost Cg- Server
(e) T -Server
(f) cost A- Server
SPRPT
FCFS
1bit
SkipPredict
Figure 9: Cost in the external cost and server cost models using exponential predictor for Weibull service time. The default costs for the external model e₁ 0.5, C2 and for the server cost model are 0.01, C2 0.05 (a + d) Cost vs. C2 when À 0.9 and = (b + e) Cost vs. T when À 0.9 f) Cost vs. when T 1.
(a) cost VS 02 External
(b) cost vs T External
(c) cost vs. A External
6
(d) cost VS Cz- Server
(e) cost vs T Server
(f) cost vs. Server
SPRPT
X
FCFS
1bit
SkipPredict
Figure 10: Cost in the external cost and server cost models using the uniform predictor for Weibull
service time. The default costs for the external model are e₁ 0.5, C2 and for the server cost model are 0.01, C2 0.05 (a + d) Cost vs. when À 0.9 and T = (b + e) Cost vs. T
when À 0.9 f) Cost vs. when T

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims are justified by the Theorems in Section and experiments in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss our approach limitations in Lines 241-259.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificatton, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]

---

We state our model in Section (assumption) and provide proofs for all the theorems listed Table i Appendix Furthermore, we re-analyze the baseline policies we are comparing against, taking into account the prediction costs, in Appendix D.1
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We describe the experimental datasets Section 5 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models. it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide our code and scripts to reproduce all the results in the paper and the Appendix with readme file contains instructions supplemental material. We didn't include the real-world datasets, following to these usage restrictions on the data we received from Two Sigma:
Please do not share this data outside of your immediate research team. Instead, please forward any data requests back to Two Sigma and we will process."
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
Code wssisssssooooso onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification: In Section 5 and in Figure captions.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification: Each data point obtained by simulating initially empty queues over 1, 1,000,000 time units. The average response time is calculated for all jobs that terminate after time 100,000. This process repeated over 100 simulations, and the reported data point represents the average response time across these 100 simulations. The paper does not report error bars because we are calculating the response time system in equilibrium (steady-state and the reported data points represent the average behavior of the system

---

in this steady-state condition. (We note that, because of the long simulations, results are concentrated and errors would be very small. We can add error bars if desired for simulated data in the next version, given more time.)
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
In Appenix F and Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Fthics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eeiip....ee
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We include "Impact Statement" in Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
In Section
Guidelines:
The answer NA means that the paper does not existing assets.

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, wwtpsspppppasheeeeeeeeepeeeeeeee whoodee com/ datasses has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.


Reviews:
[{"review_id": "1GsNqako0W", "reviewer": "Reviewer_oTX6", "summary": "The paper considers the job scheduling in the M/G/1 queueing model when the system has access to predictions regarding job lengths. The paper explicitly considers the cost incurred for obtaining the predictions in such a system. Two models are considered - (i) external cost: obtaining predictions incurs a fixed cost, but do not affect the service time of a job, and (ii) server time cost: predictions are obtained via operations that themselves need to be scheduled incurring time that delays jobs.\n\nThe authors consider a setting in which there are two kinds of predictions - (i) a cheap 1-bit prediction that only classifies whether the job length is above or below a fixed threshold T, and (ii) an expensive prediction that predicts the actual job length.\nThe authors propose a natural algorithm, called SkipPredict, that first obtains cheap predictions for all jobs to classify each job as either \"short\" or \"long\". All jobs classified as \"short\" are scheduled via FCFS. The algorithm then obtains expensive predictions for all long jobs which are then scheduled using the shortest predicted remaining time first rule.\n\nThe authors analyze this algorithm under both cost models using the SOAP analysis framework and obtains explicit expressions for the mean response times of jobs.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper raises an interesting question. Most work on learning augmented algorithms assumes that predictions are available to the algorithm for \"free\" which is certainly not true in practice. Explicitly modeling prediction costs is a good area for further research. The server time cost model that models the delays due to predictions is especially interesting for scheduling problems.", "weaknesses": "- The paper is missing some references to prior work. For example, \n(i) \"Online algorithms with Costly Predictions\" (Drygala et al) considers costly predictions in other learning augmented settings. \n(ii) \"Parsimonious Learning-Augmented Caching\" (Im et al) considers caching with goal of using few predictions.\n(iii) many papers on learning augmented scheduling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for supporting our paper.\nWe appreciate your feedback on missing references and we agree that these references are relevant to our study.  In particular, we acknowledge the relevance of the paper 'Online algorithms with Costly Predictions', along with the related work 'Advice Querying under Budget Constraint for Online Algorithms'. We believe these papers (which appeared in AISTATS and NeurIPS, respectively) show the relevance of this area and our work to the NeurIPS community. We note these papers addressed standard online problems, such as the ski rental problem. However, we believe that the queueing setting introduces unique complexities not present in these more traditional problems. Notably, much of the literature in this area focuses on 'budgeted' settings, where the number of predictions is limited, whereas our work seeks to optimize overall costs considering both prediction and operational costs.\n\nIn our revision, we will:\n- Incorporate the suggested references and other pertinent works into our related works section. \n- Provide a more comprehensive review of learning-augmented scheduling literature.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1i7KD8eB02", "reviewer": "Reviewer_ckzA", "summary": "Motivated by recent prediction based scheduling of ML jobs in data centers, the paper considers the problem of prediction cost aware scheduling to optimize mean response time. It considers two cost models - external and server time. The paper proposes a novel algorithm, SkipPredict, that uses a two level hierarchical prediction with a cheap short/long prediction at the first level and an expensive total size prediction at the second level. It then uses this information to schedule short jobs as FCFS and long jobs by SRPT. The paper presents an analysis of the expected response time for both models using the SOAP framework and present a comparison against FCFS, one-level FCFS+SRPT and SRPT. Finally, it provides experimental evidence of SkipPredict’s superior performance on synthetic and real world datasets.", "questions": "- While the paper analytically shows that SkipPredict does better than the baselines for any general service distribution, it would also be good to see this in the experiments with distributions/datasets representing ML jobs\n- (Minor) It would be nice to have a short explanation of how the SOAP framework is used in the main paper as well instead of just in the appendix.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is the first to consider the important aspect of cost of prediction in scheduling\n- The proposed algorithm, SkipPredict, elegantly utilizes an efficient hierarchical scheme and is practical to implement\n- Thorough and well presented analysis of SkipPredict as well as the baselines including generalisation to non-fixed costs\n- Baselines compared against are comprehensive", "weaknesses": "- While the motivation for the problem comes from scheduling ML jobs, the algorithm and analysis are solely queueing theoretic arguments which makes me question the relevance/interest of this work to the NeurIPS community. MLSys/SIGMETRICS perhaps might be a better fit. \n- Further, I believe none of the experiments presented reflect the characteristics of a machine learning job. The Exponential and Weibull distributions of service considered in the synthetic data are unlike the very light tailed (almost deterministic) nature of ML jobs. The real world datasets consist of CPU computations which make them unlikely to be from ML jobs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and the thoughtful suggestions.\n\n- We understand the concern about the relevance of our queuing theoretic approach to NeurIPS. Our approach relies on queuing theory to develop algorithms that efficiently manage resources in systems, opening new directions in learning-augmented algorithms, a topic of growing importance in the NeurIPS community. As mentioned by reviewer R-OTX6, there has been related previous work on prediction costs for more abstract problems that have appeared in this community, with more limitations (such as a budget on the number of predictions), rather than our cost optimization framework. Unlike typical approaches in learning-augmented algorithms that assume free predictions, our work challenges this by addressing the realistic scenario of dedicated resources for jobs. This is particularly important in scheduling, where, as in our Server Cost model, the same server uses time to make the prediction as well as to execute the work of the jobs being scheduled. We believe our work will inspire new models and algorithms in the broader context of learning-augmented algorithms. Importantly, these ideas have potential applications in various predictive systems, including those for Large Language Models (LLMs), where efficient resource management and accurate cost assessment of predictions are crucial for optimal performance.\n\n- We appreciate the reviewer's observation regarding the characteristics of ML jobs. To clarify:\n\n(1) Our evaluation framework is designed to capture scheduling for general jobs, with ML-type jobs being a subset of these. Our theoretical results hold for any general distribution, including those typical of ML workloads.\n\n(2) The presented real datasets focus on scheduling jobs with predicted service times in large-scale distributed systems, which aligns with previous work (e.g., Mitzenmacher and Dell’Amico; The Supermarket Model With Known and Predicted Service Times).\n\n(3) We appreciate the reviewer's point about better-representing ML job characteristics. We are not aware of, nor have we found through web searches, definitive information about specific statistical distribution models that accurately describe machine learning (ML) job distributions. However, based on general knowledge of job distributions, exponential and normal distributions could potentially model ML jobs. In our paper, we evaluate our approach using exponential and Weibull distributions, and as part of the rebuttal, we have included the results for an example normal distribution in the provided pdf.  (We can readily include more experiments in the final version.) Regarding the real-world datasets we used, if the reviewer or others can provide or suggest real ML datasets, we would be glad to test our approach on them and include the results in our revised paper.\n\n(4) These additions will demonstrate that SkipPredict's performance extends to scenarios that closely resemble ML workloads, complementing our experimental results that show SkipPredict outperforms baselines for the tested service distributions.\n\n- We appreciate this suggestion of adding SOAP framework in the main paper would enhance reader understanding. We will add a concise overview of how SOAP is applied in our work and an explanation of the rank function of the jobs in each model.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qbeALV6Wwc", "reviewer": "Reviewer_oree", "summary": "This paper studies a scheduling problem that aims to minimize the expected response time, where jobs arrive online and the algorithm needs to decide the priority of jobs. This paper proposes a new algorithm called skip-prediction. Namely, the algorithm first uses a cheap prediction to partition the whole job set into two parts: long job set and short job set. For jobs in short job set, they have the highest priority and no prediction will be made. And, the algorithm ranks these short jobs by the first-come-first-serve rule. For jobs in long job sets, an expensive prediction will be made to predict the size of these long jobs. Then, the algorithm ranks these long jobs using the shortest remaining processing time first rule.\nThe paper considers two different models; in the first model, predictions consume some extra costs and in the second model, predictions consume server times. For each model, the total cost of the algorithm is defined as the total expected response time plus the prediction cost. The authors provide theoretical proof to compute the formula for the total cost of the proposed skip-prediction algorithm, and then run an experiment on some datasets.", "questions": "N.A.", "limitations": "N.A.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The general motivation of the paper is good. Namely, it considers the case where the prediction does not get for free. The algorithm needs to optimize the scheduling objective with the prediction cost together. On the positive side, I expect that it will have a positive impact on practice application. I also expect that one may be able to abstract some interesting theoretical models from this paper; so it’s likely to influence future work.", "weaknesses": "I have to say that I am usually working on the theoretical analysis of the algorithms (e.g., approximation or online algorithms). I am not in the right position to judge the quality and novelty of the experimental paper. To me, the presentation of the paper is not clear; the authors describe an algorithm in the model section instead of defining a problem. Besides this, the authors give the formula of the total cost of skip-prediction in Table 1, but it is not clear how good the quality of these formulas is from the theoretical perspective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the motivation behind our work and its potential impact on practical applications. We appreciate your concern about the clarity of the presentation, particularly the flow from problem definition to algorithm description. We understand this may have obscured the primary contribution of our paper.\nTo recap our objectives and contributions (see also the general Author Rebuttal):\n- Our goal: To develop a scheduling framework that accounts for the cost of predictions, addressing a gap in current learning-augmented algorithms for scheduling.\n- Why this goal: In real data systems, predictions consume resources and time. The common assumption in learning-augmented algorithms that predictions are cost-free does not reflect realistic scenarios.\n- Our main contribution: Comparison and analysis of multiple new algorithms (SkipPredict and DelayPredict). We note we also re-analyzed previous algorithms (1bit and SPRPT) under our more realistic models that take cost into account, extending the previous work. We derive closed-form formulas that calculate the mean response time of jobs with size predictions, given prediction costs. We show that when prediction costs are set to zero, our formulas for our new algorithms align with our new formulas for prior algorithms, demonstrating the robustness and generalizability of this analysis approach. In the appendix, we also explain how to generalize our formulas to non-fixed costs.\n\nThese formulas are both theoretically significant and practically applicable. For instance, if a user can estimate prediction costs (using profiling), our formulas can be used to determine the necessary thresholds that when utilizing predictions will yield performance gains.\nWe aim to enhance the presentation of our work in the following ways:\n- We recognize that the presentation of the problem definition before the algorithm introduction could be improved. In revising, we will look at restructuring this section to enhance clarity of the problem definition and highlight our end results more clearly.\n- We will provide additional context to better illustrate the significance of the formulas we have derived and their generalizations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iSgrco8SvM", "reviewer": "Reviewer_kmdF", "summary": "The paper studies the effectiveness of machine-learned predictions for queuing systems, and falls into the area of learning-augmented algorithms / algorithms with predictions.\nIn particular it studies the M/G/1 queue with poisson arrival and i.i.d. service times with the objective to minimize the average response time.\nThis problem has previously studies with service time predictions or with single-bit predictions, indicating whether a job is 'short' or 'long' depending on a certain threshold. Moreover, previously it has been assumed that predictions are for free.\nIn contrast to these previous works, in this paper an algorithm needs to 'pay' for receiving predictions. This payment can either be some additional cost (external cost), or an additional load to the machine (server time cost) which delays the execution of other jobs. The latter is motivated by the scenario that the prediction itself first needs to be computed. Moreover, in this paper an algorithm has access to both, (cheaper) 1bit predictions and (more expensive) service time predictions. \n\nThe authors propose the algorithm 'SkipPredict' which first queries a 1bit prediction for every job that arrives, and in case that this returns 'long', also queries the service time prediction. 'Short' jobs are generally preferred and scheduled First-Come-First-Serve (FCFS). Furthermore, they study a second algorithm 'DelayPredict' which only uses service time predictions. In contrast to SkipPredict, it starts scheduling every job until it can be categorized as being 'long', and only then queries a service time prediction.\n\nThe authors compare both algorithms to the baselines FCFS, 1bit (only cheap predictions) and SRPPT (only expensive predictions). They find that in theory and in empirical experiments, the benefit of SkipPredict and DelayPredict depends on the how the threshold, the system load and the costs for both prediction types relate.", "questions": "Typos:\n- Line 114 \"somewhat\"\n- Line 224 missing whitespace", "limitations": "-", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea of using a two-stage prediction setup composed of a cheap but less expressive and an expensive but more expressive prediction is to the best of my knowledge new in the area of learning-augmented algorithms, and might have an impact on this field.\n- I really like the idea that the generation of a prediction requires processing volume itself. I think such a model could also be interesting for other scheduling problems, also in adversarial models.\n- The results show that the use of this two-stage prediction setup help to lower the overall cost compared to the baselines for certain instances.", "weaknesses": "- I think the main weakness of this work is that the results seem not to be very surprising. In particular, I think it is clear that the benefit of such a two-stage algorithm like SkipPredict heavily depends on how the costs relate. I am somehow missing some hard statements which summarize the findings more precisely.\n- Moreover, the two main components of SkipPredict, 1bit and SRPPT, have been previously studied and analyzed. Thus, to me it seems that the paper does not provide many interesting techniques or analyses.\n\nGiven the conceptually interesting models, I tend to rate this paper as borderline right now. However, I am not too familiar with queueing theory and, thus, cannot for sure assess the weight of the second weakness I mentioned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful feedback and understand your concerns. We believe the perceived \"lack of surprise\" in our results may stem from our presentation, which we will improve in the revision.\n- While it may seem intuitive that the effectiveness of a two-stage algorithm depends on relative costs, our key contribution is the formalization of this intuition through precise, closed-form formulas of two new algorithms (SkipPredict and DelayPredict). These formulas calculate the mean response time of jobs with size predictions, accounting for prediction costs. This quantitative approach can provide exact thresholds for when predictions become beneficial, moving beyond just high-level qualitative understanding. \n\n- To better illustrate the potential applications of our work, we plan to discuss how our approach could be relevant to practical scenarios to show how our formulas might be used to assess the trade-offs of utilizing predictions.\n\n- We appreciate the opportunity to clarify the point on the use of 1bit and SPRPT (previous works that have been studied before). First, the previous analysis of 1bit and SPRPT did not take costs into account;  this is one of our contributions. Second, SkipPredict (and its analysis) does not directly rely on the 1bit and SPRPT analyses in deriving the closed-form average response time. Rather, SkipPredict represents a novel approach that, in extreme cases, converges to these known algorithms:\n- When the threshold T is set to infinity, SkipPredict converges to the 1bit (or more clearly, 1bit with analysis that takes costs into account).\n- When the threshold T is set to 0, it converges to SPRPT (or more clearly, SPRPT with analysis that takes costs into account).\nFor a general T, neither 1bit nor SPRPT can be used as components. Their analyses are included primarily as baselines. and because the previous analyses of 1bit and SPRPT were incomplete and arguably impractical because they did not consider costs. Moreover, our DelayPredict algorithm doesn't make use of cheap prediction (1bit) at all -- instead, we use the idea of having an initial bound on processing act as an implicit \"prediction\". We will clarify this in the revised manuscript to better convey the innovation and importance of our approach in addressing this significant gap in previous research\n\n- We agree that our paper would benefit from more explicit statements summarizing our key findings. In our revision, we will include a dedicated section that clearly articulates our main results and their implications, emphasizing the novel contributions of our work.\n\n- Thanks for pointing out the typos, we will fix them in the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thoughtful feedback. We are encouraged they found the paper raises an interesting question (R-oTX6, R-oree) and is the first to consider the important aspect of the cost of prediction in scheduling (R-ckzA, R-kmdF), which is relevant for learning-augmented algorithms, a growing field in the NeurIPS community.
Reviewers R-oTX6, R-oree, and R-kmdF believe our approach will have a positive impact on practical applications and influence future work, potentially resulting in interesting theoretical models derived from this paper (R-oree, R-kmdF). We are glad they found our proposed algorithm elegant (R-ckzA), with thorough and well-presented analysis of SkipPredict  (R-ckzA), comprehensive evaluation compared to baselines (R-kmdF), and achieved significant improvements. In our paper, we evaluate our approach using exponential and Weibull distributions; as a reviewer (R-ckzA) asked to see more results, we have here provided results for a normal distribution example (see uploaded pdf), where we also see benefits from our algorithms.   
One concern, reported mainly by reviewers less familiar with the field (R-oree, R-kmdF), was lack of clarify regarding the primary contribution of the paper. Our key contribution is the comparison and analysis of multiple new algorithms (SkipPredict and DelayPredict). We derive closed-form formulas that calculate the mean response time of jobs with size predictions accounting for the prediction cost in two different models (external cost and server time cost) for each algorithm.
More generally, previous works in scheduling with predictions, as well as other related areas where predictions could be used, often ignore the cost of the prediction in the analysis or design of the system, even if it arises in experiments. In this respect, our contribution is to raise the bar for future work by formally incorporating the costs of predictions. We do this through several additional contributions, including:  providing two general cost models; re-analyzing previous algorithms (1bit and SPRPT) with costs; and examining the idea of using multiple, different-cost predictions to improve performance with SkipPredict.  
In addition, we acknowledge the relevance of the paper 'Online algorithms with Costly Predictions" suggested by R-oTX6, along with the related work 'Advice Querying under Budget Constraint for Online Algorithms'. We believe these papers (which appeared in AISTATS and NeurIPS, respectively) show the relevance of this area and our work to the NeurIPS community. We note these papers addressed standard online problems, such as the ski rental problem. However, we believe that the queueing setting introduces unique complexities not present in these more traditional problems. Notably, much of the literature in this area focuses on 'budgeted' settings, where the number of predictions is limited, whereas our work seeks to optimize overall costs considering both prediction and operational costs.
We acknowledge that we could have emphasized and elaborated on the formulas more clearly, as they represent the main theoretical advancement of our work. We address some specific questions below and will incorporate all feedback in the final version.

Meta-review: This paper considers how to incorporate costly predictions into scheduling. This is a highly relevant paper for people working on algorithms with predictions. Most of the reviewers though the model and algorithm will be of interest to the community.  The main caveat the reviews discussed was that the results seem not surprising.  I, like some of the reviewers, believe it is the model that is of interest and sufficient enough that this paper should be accepted.
Decision: Accept (poster)