SkipPredict: When to Invest in Predictions for Scheduling

Authors: rana  shahout
michael  mitzenmacher
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:43:19

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.

Main paper: 
 introduction: 
 Machine learning research is advancing rapidly, reshaping even traditional algorithms and data structures. This intersection has led to the rise of "algorithms with predictions", also called learningaugmented algorithms, where classical algorithms are optimized by incorporating advice or predictions from machine learning models (or other sources). These learning-augmented algorithms have demonstrated their effectiveness across a range of areas, as 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-augmented algorithm paradigm has been applied 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; Mitzenmacher, 2019 Mitzenmacher, , 2021;; Wierman and Nuyens, 2008) , and additionally some recent works also consider scheduling jobs with deadlines (Salman et al., 2023b,a) . Minimizing response time is crucial in data centers for reduced latency, in cloud computing for an enhanced user experience and optimized resource utilization, and in realtime 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 a job arrives, which may not be a realistic assumption in the practical evaluation of a 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 c 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 a 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 to 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 fixed1 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 particular, 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 a job is short or long. This type of one-bit prediction (studied in (Mitzenmacher, 2021) ) 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 a 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, we can reduce the expected time in system, optimizing resources and the user experience while accounting for the overall costs.We compare SkipPredict with three distinct previously studied policies, re-analyzing them with prediction costs in 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 (Mitzenmacher, 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 prediction. Third, Shortest Predicted Remaining Processing Time (SPRPT) performs expensive predictions for all jobs, and no cheap predictions. We find that service time predictions are particularly effective in high-load 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 a fixed period before executing an expensive prediction. DelayPredict initially schedules all jobs FCFS but limits them to a 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. 
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 a brief background to the framework in Section B.1. For scheduling with predictions, Mitzenmacher (Mitzenmacher, 2019) 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 a job is "long" or "short", based on if its size is above or below a certain threshold. This work shows that even small amounts of possibly inaccurate information can yield significant performance improvements. Scully, Grosof, and Mitzenmacher (Scully et al., 2022) design a scheduling approach for M/G/1 queues that has mean response time within a constant factor of shortest remaining processing time (SRPT) when estimates have multiplicatively bounded error, improving qualitatively over simply 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 (Azar et al., , 2022)) .Our work has a similar flavor to various "2-stage" problems, such as 2-stage stochastic programming 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 a 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 problems, 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 predictions is limited. In contrast, our work seeks to optimize overall costs by considering prediction and operational expenses. 
model: 
 We consider M/G/1 queueing systems with arrival rate λ. 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 prediction of either short or long, which we refer to as a cheap prediction. Only jobs predicted as 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.Single-Queue, External Cost In this model, a job can be described by a triple (x, b, r); we refer to this as a job's type. Here x is the service time for the predictor, b is the output from a binary predictor that determines whether the job is short or long, and for any long job, r is the result of a 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 c 1 , and all long jobs obtain an expensive prediction at some fixed cost c 2 . Accordingly, we can model the total expected cost for predictions per job in equilibrium asC = c 1 + c 2 z, where z = f (x)(1 -p T (x))dx is the expected fraction of jobs requiring the second prediction. In general, both z and c 1 will depend on our choice of first layer prediction function, and similarly c 2 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 as a function H(C, T ), such as the sum of the C and T .Single-Queue, Server Time Cost The server time cost model refers to the setting where predictions are scheduled on the same server as the jobs, so there is a server time cost based on a defined policy. Jobs predicted as short are categorized as non-preemptible while in execution, thereby prioritizing their completion before predicting new jobs. However, jobs predicted as long are further scheduled for a 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 a four-class priority preemptive system. Class 1 (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 3 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.) Definition 1. Suppose E[T ] P S ext , E[T ] P L ext , E[T ] P S srv and E[T ] P L srv 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(1 -z) • E[T ] P S ext + z • E[T ] P L ext + C while the total cost in the server cost model is (1 -z) • E[T ] P S srv + z • E[T ] P L srvwhere z is the expected fraction of jobs requiring the second prediction and C is the expected cost for prediction per job. 
skippredict theorems: 
 For SkipPredict with a given T in both models, the expected mean response times for a predicted short job (E[T ] P S <model> ) and predicted long job of true size x J and predicted size r (E[T (x J , r)] P L <model> ) are given in Table 1 . We provide proofs in Appendix C in Lemmas 1, 2, 3and 4. We get E[T ] P L <model> using Lemma 5 and by plugging E[T ] P S <model> and E[T ] P L <model> into Definition 1, we get the total cost of SkipPredict in both models. c 1 is the cost of the cheap prediction, c 2 is the cost of the expensive prediction and (r -a) + = max(r -a, 0). The symbols used in the equations are later expressed and described in Table 2 . Load due to predicted short jobs and their cheap prediction cost ρ srv r Load due to predicted short, long (with predicted size ≤ r) and prediction jobs a(r)] 2(1 -ρ ′ <T ) + E[S ′ <T ] λ • c 2 1 + 2c1E[S ′ <T ] + E[S ′ <T 2 ] 2(1 -ρ srv P S ) + E[S ′ <T ] Long λ 2(1 -ρ ext r ) 2 E[S ′ <T 2 ] + E[S ′ ≥T,r 2 ] + a(r) + x J 0 1 1 -ρ ext (r-a) + da λ 2(1 -ρ srv r ) 2 • E[S ′′ <T 2 (c1)]+ (c1 + c2) 2 • Q(T, r) + E[S ′′ ≥T,r 2 (c1 + c2)] + a(r) + x J 0 1 1 -ρ srv (r-a) + daIntegral related to predicted long jobs with predicted size > r Q(T, r)Probability of a job being predicted as long with predicted size > rExternal Cost Model. Response time is defined as the sum of the waiting time in the queue and the residence time, which is the time from when the job is first processed until completion. For SkipPredict in the external cost model, a predicted short job has to 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-Balter, 2013) . Since there is no preemption in this case, the residence time is simply the service time for the predicted short job, E[S ′ <T ]. A predicted long job of true size x J and predicted size r has to wait behind previous short jobs, expressed by the term E[S ′ <T 2 ], and long jobs with a shorter remaining time, expressed by the terms E[S ′ ≥T,r 2 ] and a(r) as well as 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 a preemption delay that causes a slowdown in the residence time due to the load from jobs predicted as short and jobs predicted as long but with a service time prediction of less than r.Server Time Cost Model. For the server cost model, a 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 c 1 . In this case, there is no preemption, so the residence time is simply the service time for the predicted short job, E[S ′ <T ]. A predicted long job of true size x J and predicted size r must wait behind previous short jobs along with their cheap predictions, expressed by the term E[S ′′ <T (c 1 )]. It must also wait behind cheap and expensive predictions of long jobs that arrive earlier but with a larger remaining time, expressed by (c 1 + c 2 ) 2 • Q(T, r), and long jobs with a shorter remaining time frame along with their cheap and expensive predictions, expressed by E[S ′′ ≥T,r 2 (c 1 + c 2 )] + a(r). The slowdown due to preemption is affected by the load from jobs predicted as short, jobs predicted as long but with a service time prediction less than r, and the load from all predictions.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 S ′′ ≥T,r (c 2 ) and S ′′ <T (c 1 ) (Table 3 ) because with zero costs, these definitions match with those of S ′′ ≥T,r and S ′′ <T . 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., E[S ′ <T ] = 0), necessitating expensive predictions for all jobs. Thus, the mean response time for the predicted long jobs aligns with the mean response time of SPRPT (Mitzenmacher, 2019) (analyzed for both of the two models in Appendix D.1).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 a 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) FCFS2 , a non-size-based policy that does not require predictions; 2) SPRPT, which involves performing expensive predictions for all jobs; and 3) 1bit advice (Mitzenmacher, 2021), which uses only cheap predictions, separating jobs into predicted shorts and predicted longs, and using FCFS as a scheduling policy for each category. These policies, along with SkipPredict, can be placed on a spectrum based on their prediction costs. FCFS requires no predictions, while SPRPT requires expensive predictions for each job. The 1bit policy and SkipPredict are positioned in the middle of this spectrum, with the 1bit 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, we analyze SPRPT and 1bit policies in the external cost model and the server cost model. These policies, initially introduced by Mitzenmacher (Mitzenmacher, 2019 (Mitzenmacher, , 2021)) , were analyzed without considering the cost of predictions, so in Appendix D.1 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 c 1 ), the total cost of SkipPredict would be greater than that for SPRPT. Also in this case SPRPT would outperform the 1bit approach, as size-based policies are generally more effective than non-size-based ones when predictions are reasonably accurate. However, when the expensive prediction cost c 2 is high, SkipPredict or 1bit 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 1bit approach depends on the value of using an SPRPT-strategy for the remaining jobs.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 a 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.Another limitation of SkipPredict arises in situations where sufficiently low-cost predictions are not available or 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 an alternative algorithm, DelayPredict, as a potential solution in these cases. Rather than apply predictions to all jobs, DelayPredict does not use 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 of service time, at which point it is preempted, and treated as a 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 z ′ = ∞ x=L f (x)dx as the expected fraction of jobs requiring the expensive prediction and use it in Definitions 1 to analyze DelayPredict cost in the external cost model and in the server cost model. We provide mean response times for DelayPredict with proofs in Appendix E.DelayPredict vs. SkipPredict. The main difference between DelayPredict and SkipPredict is in the waiting time. In SkipPredict, a predicted short job sees only short jobs while a short job in De-layPredict sees all jobs in the queue ahead of it, 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 1 shows a setting where there is a cost gap between prediction costs, and SkipPredict outperforms DelayPredict. However, DelayPredict still performs better than SPRPT (with c 1 = 0.5, c 2 = 4). When the costs are close, DelayPredict is better than both SkipPredict and SPRPT, as in this case SkipPredict is less effective. Since the waiting time of DelayPredict depends on L, we see in Figure 1(c) that as L increases, the cost of DelayPredict gets higher. (Note for comparison purposes the L for DelayPredict and the T for SkipPredict are chosen to be the same value.)While we assume that the prediction costs as fixed, our approach naturally generalizes theoretically to random costs from a 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 prediction cost is given by a density function k 1 (x, c 1 ), where k 1 (x, c 1 ) is the density corresponding to a job with actual size x and cost of cheap prediction c 1 . Hence,∞ c=0 k 1 (x, c)dc = f (x).Similarly, the expensive prediction cost is given by a density function k 2 (x, c 2 ), where k 1 (x, c 2 ) is the density corresponding to a job with actual size x and the cost of expensive prediction is c 2 .In our analysis of the server cost model with fixed costs, for jobs with rank 4 in the first dimension, we used r-a to encode the second dimension of the rank rather than the predicted remaining service time, which we noted is technically r -(a -c 1 -c 2 ). When c 1 and c 2 are fixed, doing so does not change the rankings of jobs, but for non-fixed costs, we would want to use the actual predicted remaining service time r -(a -c 1 -c 2 ) for the rank function.To gain more insight into when to invest in prediction and how SkipPredict compares to other policies, in this section we compare SkipPredict, SPRPT, 1bit and FCFS using simulation with realworld and synthetic 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, utilizing 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 distributions: exponentially distributed with mean 1 (f (x) = e -x ) and the Weibull distribution with cumulative distribution F = 1 -e - √ 2x (which also has mean 1). Also, for the synthetic traces, we use two prediction models where each of the two-stage predictors could be from a different model: 1) Exponential predictions (Mitzenmacher, 2019) , where a prediction for a job with service time x is itself exponentially distributed with mean x. 2) Uniform predictions (Mitzenmacher, 2019) , where a prediction for a job with service time x is uniformly distributed between (1 -α)x and (1 + α)x for a parameter α. For the synthetic datasets, in this section we present results for the exponentially distributed service time with uniform predictor. Appendix F contains results for the rest of the combinations.To handle two-stage 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 a 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," as the integrals are simpler in this case.Cost vs. arrival rate λ. Figures 2, 3(b), 3(d), 4(b), 4(d) 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 λ = 0.7 in all datasets. We should note, however, that under extremely high load in the server cost model, prediction-based scheduling (SPRPT, SkipPredict or 1bit) risks overflowing the system (since the average time per job with predictions is larger than 1), making FCFS a better option.Cost vs. T . In Figures 2(g ), 2(h), 3(a), 3(c) 4(a), 4(c), we compare the cost vs. T . As T increases, both SkipPredict and 1bit 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 a reduced load for expensive predictions, 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.Accuracy/Cost tradeoff. To evaluate a setting where one has to choose accuracy levels by accuracy/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 a heat map matrix in Figures 5(a) , 5(b) using exponential service time and T = 1. In this matrix, rows represent the probability of 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 α 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 costeffective than other policies when there is a difference between the costs of the two predictions, with a greater gap leading to higher improvement. In Figures 5(c ) 5(d), we have exponential service times, T = 1, c 1 is fixed to the default value, and we change c 2 by varying k where c 2 = kc 1 . For similar or very close costs (k = 1), SkipPredict is less useful, and SPRPT may be a better option. However, as c 2 values increase, SkipPredict becomes more cost-effective. FCFS and 1bit are not affected as they do not require expensive predictions.  
conclusion: 
 We have presented SkipPredict, the first prediction-based scheduling policy we are aware of that takes into account the cost of prediction. SkipPredict is designed for systems where two levels of prediction are available, good (and cheap) and better (but expensive) prediction. While here we have focused on having a binary prediction (short/long) and a prediction of the service time, our framework 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 a 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 SkipPredict and analyzed total cost formulae in the two cost models for SkipPredict. We similarly derived formulae in these models for previously proposed prediction policies where previous analyses ignored prediction costs, namely 1bit 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 cost models, especially when there is a significant cost gap between cheap and expensive predictions. While we focused on analyzing SkipPredict for cases with prediction costs, there are 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 a certain threshold.While scheduling itself is a foundational problem that provides sufficient motivation for our work, we 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 Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. 
 
 Appendix: We employ the SOAP framework (Scully and Harchol-Balter, 2018) , a (relatively) recently developed analysis method, to obtain precise formulas for mean response time3 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 a two-class system, we choose to use SOAP for a consistent analysis.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 a 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 to as the job's type or descriptor. For example, the descriptor could represent the job's 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 a job'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 a tagged job, denoted by J, of size x J and with descriptor d J . We use a J to denote the amount of time J has received service. The mean response time of J 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 J and age a J is denoted by rank worst d J (a J ). When a J = 0, the rank function is denoted by r worst = rank worst d J (0). Ranks are written in ⟨angle brackets⟩. In the SOAP framework, waiting time is shown to be equivalent to the transformed busy period in an M/G/1 system with arrival rate λ and job size X new [rank worst d J (a)]4 . 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 r worst , are excluded from the transformed system. Original old jobs, with a rank at or below r worst , are considered as arrivals with rate λ and a specific size distribution X old 0 [r worst ]5 . Recycled old jobs, currently at or below r worst but previously above this threshold, are treated as server vacations of length X old i [r worst ]6 for i ≥ 1 in the transformed system. As explained later, in SkipPredict jobs could only be recycled once, so we only have X old 1 [r worst ]. 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/1/FCFS system. This system is characterized by 'sparse' server vacations, where (original) jobs arrive at rate λ and follow the size distribution X old 0 [r worst ].Theorem 1 (Theorem 5.5 of (Scully and Harchol-Balter, 2018) ). Under any SOAP policy, the mean response time of jobs with descriptor d and size x J is:E[T (x J , d)] = λ • ∞ i=0 E[X old i [r worst ] 2 ] 2(1 -λE[X old 0 [r worst ])(1 -λE[X new [r worst ]) + x J 0 1 1 -λE[X new [rank worst d J (a)]]da.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] = [x, b, r]. SkipPredict in the external cost model results in the following rank function:rank ext ([x, b, r], a) = ⟨1, -a⟩ if b = 1, ⟨2, r -a⟩ if b = 0.(1)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 as the primary rank, with the priority ordering following a lexicographic ordering.In the server cost model, SkipPredict results in the following rank function: (2)rank srv ([x, b, r], a) =        ⟨2, -a⟩ if 0 ≤ a ≤ c 1 (initialNote entering jobs have ranked 2 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 4 in the first dimension, we use r -a as the secondary rank. Technically the predicted remaining service time is r -(a -c 1 -c 2 ), since the job's age includes service for predictions of time c 1 + c 2 . As c 1 and c 2 are fixed, using r -a is equivalent to using r -(a -c 1 -c 2 ) for ranking, and we use r -a for convenience.Table 3 : Definition and Description of symbols used in the equations Symbol Description E[S ′ <T ] = ∞ 0 x • p T (x) • f (x) dx Expected service times of predicted short jobs E[S ′ ≥T,r ] = r y=0 ∞ x=0 (1 -p T (x)) • x • g(x,(c 1 )] = ∞ 0 (x + c 1 ) • p T (x) • f (x) dxExpected service times of predicted short jobs including prediction cost c 1ρ ′ <T = λ ∞ x=0 xf (x)p T (x) dx Load due to predicted short jobs ρ ext r = λ E[S ′ <T ] + E[S ′ ≥T,r ]Load due to predicted short jobs, predicted long jobs with service time prediction ≤ rρ srv P S = λ c 1 + E[S ′ <T ]Load due to predicted short jobs and their cheap prediction costρ srv r = λ E[S ′′ <T (c 1 )] + (c 1 + c 2 ) • Q(T, r)Load due to predicted short jobs, predicted +λE[S ′′ ≥T,r (c 1 + c 2 )] long jobs with service time prediction ≤ r, and prediction jobsa(r) = ∞ t=r ∞ x=t-r (1 -p T (x))g(x, t) Integral related to predicted long jobs •(x -(t -r)) 2 dx dt with service time prediction > r Q(T, r) = ∞ y=r ∞ x=0 (1 -p T (x)) • g(x, y)dxdyProbability of a job being predicted as long with service time prediction > rLemma 1. For SkipPredict in the external cost model, the expected mean response time for a predicted short job, E[T ] P S ext isE[T ] P S ext = λE[S ′ <T 2 ] 2(1 -ρ ′ <T ) + E[S ′ <T ].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) = ∞ t=r ∞ x=t-r (1 - p T (x))g(x, t)(x -(t -r)) 2 dxdt, the expected mean response time for a predicted long job of true size x J and predicted size r isE[T (x J , r)] P L ext = λ 2(1 -ρ ext r ) 2 E[S ′ <T 2 ] + E[S ′ ≥T,r 2 ] + a(r) + x J 0 1 1 -ρ ext (r-a) + da Where ρ ext r = λ E[S ′ <T ] + E[S ′ ≥T,r] is the load due to jobs of predicted short and jobs predicted long but their service time prediction less than r and (r -a) + = max(r -a, 0).To analyze SkipPredict for a predicted long job in the external cost model using SOAP, we first find the worst future rank and then calculate X new [rank worst d J (a)], X old 0 [r worst ] and X old i [r worst ] for predicted long job. As described in (1), the rank function for predicted long jobs is monotonic (here the job descriptor is d J = [x J , 1, r]), and every job's rank is strictly decreasing with age, thus J's worst future rank is its initial rank, here: rank worst d J (a) = ⟨2, r -a⟩ and r worst = rank worst d J (0) = ⟨2, r⟩.X new [rank worst d J (a)]: Suppose that a new job K of predicted size r K arrives when J has age a J . J's delay due to K depends on whether K is predicted to be short or long. If K is predicted short then it will preempt J and be scheduled till completion because it has a higher class. Otherwise, if K has a predicted job size less than J's predicted remaining process time (r -a J ), K will always outrank J. ThusX new x K [⟨2, r -a⟩] = x K K is predicted short x K 1(r K < r -a) K is predicted long E[X new [⟨2, r -a⟩]] = ∞ 0 p T (x)xf (x)dx + r-a 0 ∞ x=0 x • (1 -p T (x))g(x, y)dxdy X old 0 [r worst ]:Whether another job I is original or recycled depends on its prediction as short or long, and in the case it is long, it also depends on its predicted size relative to J's prediction. If I is predicted short, then it remains original until its completion. Otherwise, if I is predicted long, I is original only if r I ≤ r, because then until its completion its rank never exceeds r.X old 0,x I [⟨2, r⟩] = x I if I is predicted short x I 1(r I ≤ r) if I is predicted long E[X old 0 [⟨2, r⟩]] = ∞ 0 p T (x)xf (x)dx + r y=0 ∞ x=0 (1 -p T (x)) • x • g(x, y)dxdy E[(X old 0 [⟨2, r⟩]) 2 ]] = ∞ 0 p T (x)x 2 f (x)dx + r y=0 ∞ x=0 (1 -p T (x)) • x 2 • g(x, y)dxdy X old i [r worst ]:If another job I is predicted long and if r I > r, then I starts discarded but becomes recycled when r I -a = r. This starts at age a = r I -r and continues until completion, which will be x I -a I = x I -(r I -r). Thus, for i ≥ 2, X old i,x I [⟨2, r⟩] = 0. Let t = r I :X old 1,x I [⟨2, r⟩] = 0 if I is predicted short x I -(t -r) if I is predicted long E[X old 1 [⟨2, r⟩] 2 ] = ∞ t=r ∞ x=t-r (1 -p T (x)) • g(x, t) • (x -(t -r)) 2 dxdtApplying Theorem 1 leads to the result.To analyze the server cost model, as explained, considering the rank function defined in (2), we first find the worst future rank of J, denoted as rank worst d J , as follows:rank worst d J (a) = ⟨2, -a⟩ if J is predicted short ⟨4, r -a⟩ if J is predicted longLemma 3. For SkipPredict policy in the server time cost model, the expected mean response time for a predicted short job, E[T ] P S srv isE[T ] P S srv = λ • c 2 1 + 2c 1 E[S ′ <T ] + E[S ′ <T 2 ] 2(1 -ρ srv P S ) + E[S ′ <T ]whereρ srv P S = λ c 1 + E[S ′ <T ]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 new [rank worst d J (a)], X old 0 [r worst ] and X old i [r worst ] for these predicted short jobs in the server cost model, where the job descriptor in this case is (b, r) = (1, * ).X new [rank worst d J (a)]: Let's consider a new job K arriving when J is at age a J (where a J ≤ min(r, x J )). The worst rank of J depends on whether J is predicted to be short or long. If J is predicted short, then J's worst future rank is its current rank ⟨2, -a J ⟩. 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:X new x K [⟨2, -a J ⟩] = 0 X old 0 [r worst ]:Suppose that J witnesses an old job I of initial size x I . The duration for which I remains original depends on whether its prediction is short or long. If I is predicted short, it remains original until completion. Alternatively, if I is predicted long, it would remain original until the cheap prediction phase (lasting c 1 ), after which its rank shifts to ⟨3, 0⟩.X old 0,x I [⟨2, 0⟩] = c 1 + x I if I is predicted short c 1 if I is predicted long E[X old 0 [⟨2, 0⟩]] = c 1 + ∞ 0 p T (x)xf (x)dxX old i [r worst ]: There are no instances of recycled jobs because either I completes its service (if predicted short) or it is discarded completely (if predicted long), and thus never gets a rank lower than ⟨2, 0⟩. Thus, for i ≥ 1, X old i,x I [⟨2, 0⟩] = 0 Applying Theorem 1 yields the result.Lemma 4. For SkipPredict policy in the server time cost model, the expected mean response time for a predicted long job of true size x J and predicted size r isE[T (x J , r)] P L srv = λ 2(1 -ρ srv r ) 2 • E[S ′′ <T 2 (c 1 )] + (c 1 + c 2 ) 2 • Q(T, r) + E[S ′′ ≥T,r 2 (c 1 + c 2 )] + a(r) + x J 0 1 1 -ρ srv (r-a) + da Where Q(T, r) = ∞ y=r ∞ x=0 (1 -p T (x)) • g(x, y)dxdy (r -a) + = max(r -a, 0) ρ srv r = λ E[S ′′ <T (c 1 )] + (c 1 + c 2 ) • Q(T, r) + E[S ′′ ≥T,r (c 1 + c 2 )] is the load due to jobs of predicted short and jobs predicted long but their service time prediction less than r along with the load of the jobs predictions.a(r) = ∞ t=r ∞ x=t-r (1 -p T (x))g(x, t)(x -(t -r)) 2 dx dtProof. Now we calculate X new [rank worst d J (a)], X old 0 [r worst ] and X old i [r worst ] for predicted long jobs in the server cost most, here again the J's descriptor is ((b, r) = (0, r)).X new [rank worst d J (a)]: J's delay due to K also depends on K is predicted to be short or long.X new x K [⟨4, r -a J ⟩] = c 1 + x K K is predicted short c 1 + c 2 + x K 1(r K < r -a J ) K is predicted longEmploying the joint distribution g(x, y), and setting 1(r K < r -a J ) = r-a J y=0 g(x K , y)dy, we can derive J's expected delay due to any random new job:E[X new [⟨4, r -a J ⟩]] =c 1 + ∞ 0 p T (x)xf (x)dx + ∞ 0 (1 -p T (x))c 2 f (x)dx + r-a J 0 ∞ x=0 (1 -p T (x))xg(x, y)dxdy X old 0 [r worst ]: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.X old 0,x I [⟨4, r⟩] = c 1 + x I if I is predicted short c 1 + c 2 + x I • 1(r I ≤ r) if I is predicted long E[(X old 0 [⟨4, r⟩])]] = ∞ 0 p T (x)(c 1 + x)f (x)dx + ∞ y=r ∞ x=0 (1 -p T (x)) • g(x, y) (c 1 + c 2 ) dxdy + r y=0 ∞ x=0 (1 -p T (x)) • g(x, y) (c 1 + c 2 + x) dxdy E[(X old 0 [⟨4, r⟩]) 2 ]] = ∞ 0 p T (x)(c 1 + x) 2 f (x)dx + ∞ y=r ∞ x=0 (1 -p T (x)) • g(x, y) (c 1 + c 2 ) 2 dxdy + r y=0 ∞ x=0 (1 -p T (x)) • g(x, y) (c 1 + c 2 + x) 2 dxdyX old i [r worst ]: If J is predicted long, job I may be recycled. This occurs when I is predicted as long and with an expensive prediction r I > r. I is initially considered as original and is served during the cheap and expensive prediction phases, then discarded. At age a I = r I -r, I is recycled and served till completion, which will be x I -a I = x I -(r I -r). For i ≥ 2, X old i,x I [⟨2, r⟩] = 0, let t = r I : X old 1,x I [⟨4, r⟩] = 0 if I is predicted short x I -(t -r) if I is predicted long E[X old 1 [⟨4, r⟩] 2 ] = ∞ t=r ∞ x=t-r (1 -p T (x)) • g(x, t) • (x -(t -r)) 2 • dxdtApplying Theorem 1 yields the result.Lemma 5. The mean response time for predicted long jobs in the external cost model isE[T P L ext ] = ∞ x=0 ∞ y=0 (1 -p T (x))g(x, y)E[T (x, y)] P L ext dydx ∞ x=0 ∞ y=0 (1 -p T (x))g(x, y)dydxand in the server cost model is:E[T P L srv ] = ∞ x=0 ∞ y=0 (1 -p T (x))g(x, y)E[T (x, y)] P L srv dydx ∞ x=0 ∞ y=0 (1 -p T (x))g(x, y)dydxIn SPRPT the job descriptors only include the job size and service time predictions, e.g. D = [size, predicted time] = [x, r]. Thus, the rank function in the external cost model is:EQUATIONIn the server cost model:rank srv ([x, b], a) = ⟨1, -a⟩ if 0 ≤ a ≤ c 1 (initial rank, scheduling prediction), ⟨2, r -a⟩ if a > c 1 (jobs after prediction).(4) Lemma 6. For SPRPT in the external cost model, the expected mean response time for a job of true size x J and predicted size r isE[T (x J , r)] SP RP T ext = λ 2(1 -ρ ′ r ) 2 r y=0 ∞ x I =0 x 2 I • g(x I , y)dx I dy + ∞ t=r ∞ x I =t-r g(x I , t) • (x I -(t -r)) 2 • dx I dt + x J 0 1 1 -ρ ′ (r-a) + da, where ρ ′ r = λ r y=0 ∞ x I =0 x I • g(x I , y)dx I dy.Proof. SPRPT has a rank function rank(r, a) = r -a for job of size x and predicted size r. As this rank function is monotonic, J's worst future rank is its initial prediction:rank worst d J ,x J (a) = r -a.When a J = 0, the rank function is denoted by r worst = rank worst d J ,x J (0) = r.X new [rank worst d J ,x J (a)] computation: Suppose that a new job K of predicted size r K arrives when J has age a. If K has a predicted job size less than J's predicted remaining process time (r -a), K will always outrank J. ThusX new x K [r -a] = x K 1(r K < r -a) E[X new [r -a]] = r-a 0 ∞ x K =0 x K • g(x K , y)dx K dy X old 0 [r worst ] computation:Whether job I is an original or recycled job depends on its predicted size relative to J's predicted size. If r I ≤ r, then I is original until its completion because its rank never exceeds r.X old 0,x I [r] = x I 1(r I ≤ r). E[X old 0 [r]] = r y=0 ∞ x I =0 x I • g(x I , y)dx I dy. E[(X old 0 [r]) 2 ]] = r y=0 ∞ x I =0x 2 I • g(x I , y)dx I dy.X old i [r worst ] computation: If r I > r, then I starts discarded but becomes recycled when r I -a = r. This means at age a = r I -r and served till completion, which will be x I -a I = x I -(r I -r), let t = r I : Thus, we haveX old 1,x I [r] = x I -(t -r). For i ≥ 2, X old i,x I [r] = 0. E[X old 1 [r] 2 ] = ∞ t=r ∞ x I =t-r g(x I , t) • (x I -(t -r)) 2 • dx I 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 x J is as follows. Letρ ′ r = λ r y=0 ∞ x I =0x I • g(x I , y)dx I dy.ThenE[T (x J , r)] SP RP T ext = λ r y=0 ∞ x I =0 x 2 I • g(x I , y)dx I dy + ∞ t=r ∞ x I =t-r g(x I , t) • (x I -(t -r)) 2 • dx I dt 2(1 -ρ ′ r ) 2 + x J 0 1 1 -ρ ′ (r-a) + da. Let f p (y) = ∞ x=0 g(x, y)dx.Then the mean response time for a job with size x J , and the mean response time over all jobs are given byE[T (x J )] = ∞ y=0 f p (y)E[T (x J , y)]dy, E[T ] SP RP T ext = ∞ x=0 ∞ y=0 g(x, y)E[T (x, y)]dydx.Lemma 7. For SPRPT in the server time cost model, the expected mean response time for a job of true size x J and predicted size r isE[T (x J , r)] SP RP T srv = λ 2(1 -ρ ′′ r ) 2 ∞ y=r ∞ x=0 c 2 2 • g(x, y)dxdy + r y=0 ∞ x I =0 (c 2 + x I ) 2 • g(x I , y)dx I dy + ∞ t=r ∞ x I =t-r g(x I , t) • (x I -(t -r)) 2 • dx I dt) + x J 0 1 1 -ρ ′′ (r-a) + da, where ρ ′′ r = λ c 2 + r y=0 ∞ x I =0 x I • g(x I , y)dx I dy .Proof. X new [rank worst d J (a)]: J's worst future rank is ⟨2, r -a J ⟩. In this case, J's delay due to a new job K is c 2 plus x K is its predicted service time less than J's remaining process time.X new x K [⟨2, r -a J ⟩] = c 2 + x K 1(r K < r -a J ). E[X new [⟨2, r -a J ⟩] = c 2 + r-a 0 ∞ x K =0x K • g(x K , y)dx K dy.X old 0 [r worst ] computation: In this model, old job I delays J at least c 2 . In addition, If r I ≤ r, then I is original until its completion because its rank never exceeds r.X old 0,x I ⟨2, r -a J ⟩ = c 2 + x I 1(r I ≤ r). E[X old 0 ⟨2, r -a J ⟩] = c 2 + r y=0 ∞ x I =0x I • g(x I , y)dx I dy.E[(X old 0 ⟨2, r -a J ⟩) 2 ]] = ∞ y=r ∞ x=0 c 2 2 • g(x, y)dxdy + r y=0 ∞ x I =0 (c 2 + x I ) 2 • g(x I , y)dx I dy.X old i [r worst ] computation: If r I > r, then I starts discarded but becomes recycled when r I -a = r. This means at age a = r I -r and served till completion, which will be x I -a I = x I -(r I -r), let t = r I : Thus, we haveX old 1,x I ⟨2, r -a J ⟩ = x I -(t -r). For i ≥ 2, X old i,x I ⟨2, r -a J ⟩ = 0, E[X old 1 ⟨2, r -a J ⟩ 2 ] = ∞ t=r ∞ x I =t-r g(x I , t) • (x I -(t -r)) 2 • dx I 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 x J is as follows. Letρ ′′ r = λ c 2 + r y=0 ∞ x I =0x I • g(x I , y)dx I dy .ThenE[T (x J , r)] SP RP T srv = λ 2(1 -ρ ′′ r ) 2 ∞ y=r ∞ x=0 c 2 2 • g(x, y)dxdy + r y=0 ∞ x I =0 (c 2 + x I ) 2 • g(x I , y)dx I dy + ∞ t=r ∞ x I =t-r g(x I , t) • (x I -(t -r)) 2 • dx I dt) + x J 0 1 1 -ρ ′′ (r-a) + da Let f p (y) = ∞ x=0 g(x, y)dx.The mean response time for a job with size x J and the mean time for a general job are give byE[T (x J )] = ∞ y=0 f p (y)E[T (x J , y)]dy, E[T ] SP RP T ext = ∞ x=0 ∞ y=0 g(x, y)E[T (x, y)]dydx.For the 1bit policy, we define the rank function of this approach and then analyze it using SOAP framework. Here the job descriptors only include the job sizes and binary predictions, e.g.EQUATIONIn the server cost model, this approach results in the following rank function: rank srv ([x, b], a) =    ⟨2, -a⟩ if 0 ≤ a ≤ c 1 (initialThe mean response time for predicted short jobs of this approach is similar to predicted short jobs of SkipPredict as nothing has changed. Lemma 8. For the 1bit policy in the external cost model, the expected mean response time for a predicted long job of true size x J isE[T (x J )] 1bit,P L ext = λ 2(1 -ρ)(1 -ρ ext new ) E[S 2 ] + x J 0 1 1 -ρ ext new da, where ρ ext new = λ ∞ 0 p T (x)xf (x)dx, the load due to predicted short jobs.Proof. To analyze 1-bit advice for predicted long job in the external cost model using SOAP, we first find the worst future rank and then calculate X new [rank worst d J (a)], X old 0 [r worst ] and X old i [r worst ] for predicted long job. For predicted long jobs, the rank function is monotonic as described in (5), therefore J's worst future rank is its initial rank. rank worst d J (a) = ⟨2, -a⟩, and r worst = rank worst d J (0) = ⟨2, 0⟩. X new [rank worst d J (a)]: Suppose that a new job K arrives when J has age a J . J's delay due to K depends on K is predicted to be short or long.Only if K is predicted short then it will preempt J and be scheduled till completion because it has a higher class as long jobs are scheduled also according to FCFS so in case of K predicted long it will not preempt JX new x K [⟨2, -a⟩] = x K K is predicted short. E[X new [⟨2, -a⟩]] = ∞ 0 p T (x)xf (x)dx.X old 0 [r worst ]: Now if old job I either predicted short or long is an original job then it remains original until its completion (regardless of if it is predicted long or short). Thus, for i ≥ 1, X old i,x I [⟨2, 0⟩] = 0.X old 0,x I [⟨2, 0⟩] = x I . E[X old 0 [⟨2, 0⟩]] = ∞ 0 xf (x)dx. E[(X old 0 [⟨2, 0⟩]) 2 ]] = ∞ 0 x 2 f (x)dx.Applying Theorem 5.5 of SOAP (Scully and Harchol-Balter, 2018 ) yields the result:E[T (x J )] P L ext = λ 2(1 -ρ)(1 -ρ ext new ) ∞ 0 x 2 f (x) dx + x J 0 1 1 -ρ ext new da,where ρ ext new = λ ∞ 0 p T (x)xf (x)dx . As a second way of thinking about this proof, it can be said that this is the original FCFS system with slowdowns caused by subsystem 1 (predicted short jobs) which is1 1-ρ ext new .Lemma 9. For the 1bit policy in the server time cost model, the expected mean response time for a predicted long job of true size x J isE[T (x J )] 1bit,P L srv = λ 2(1 -ρ c1 )(1 -ρ srv new ) ∞ 0 (x + c 1 ) 2 f (x) dx + x J 0 1 1 -ρ srv new da, where ρ srv new = λ c 1 + ∞ 0 p T (x)xf (x)dx and ρ c1 = λ ∞ 0 (x + c 1 )f (x)dx .Proof. In this case, according to (6), J's worst future rank is rank worst d J (a) = ⟨3, -a⟩ and r worst = rank worst d J (0) = ⟨3, 0⟩. X new [rank worst d J (a)]: Let's say J has age a J when K arrives. The delay caused by K for J depends on whether it is predicted to be short or long for K. If K is predicted short then it will preempt J and be scheduled along with its cheap prediction till completion. Otherwise, if K is predicted long, it will delay J only for the cheap prediction.X new x K [⟨3, -a J ⟩] = c 1 + x K K is predicted short, c 1 K is predicted long. E[X new [⟨3, -a⟩]] =c 1 + ∞ 0 p T (x)xf (x)dx.X old 0 [r worst ]: Each old job is scheduled for cheap prediction (which costs c 1 ), and an old job I, regardless of whether it is predicted long or short remains original until its completion. Thus, for i ≥ 1, X old i,x I [⟨3, 0⟩] = 0.X old 0,x I [⟨3, 0⟩] = c 1 + x I E[X old 0 [⟨3, 0⟩]] = ∞ 0 (c 1 + x)f (x)dx E[(X old 0 [⟨3, 0⟩]) 2 ]] = ∞ 0 (c 1 + x) 2 f (x)dxUsing Theorem 5.5 of SOAP (Scully and Harchol-Balter, 2018 ) yields the result:E[T (x J )] 1bit,P L srv = λ 2(1 -ρ c1 )(1 -ρ srv new ) ∞ 0 (x + c 1 ) 2 f (x) dx + x J 0 1 1 -ρ srv new da, where ρ srv new = λ c 1 + ∞ 0 p T (x)xf (x)dx ρ c1 = λ ∞ 0 (x + c 1 )f (x)dx .Rank function of DelayPredict: We model the system using D = [size, predicted time] = [x, r].Here we assume that the service time prediction r is greater than L, because jobs that require expensive prediction are longer than L. Since a job's age is L when it is preempted and obtains a prediction, in the external model, the predicted remaining time for long jobs is r -L -(a -L) = r -a.For the service time model their age after being predicted starts at L + c 2 , so the predicted remaining time is r -L -(a -L -c 2 ) = r -a -c 2 . As c 2 is fixed among all jobs, instead of the predicted remaining time we can use r -a as the rank for convenience. Accordingly, DelayPredict in the external cost model has the following rank function:EQUATIONIn the server cost model, DelayPredict results in the following rank function:rank srv ([x, r], a) =    ⟨1, -a⟩ if 0 ≤ a < L (initial rank), ⟨2, -a⟩ if L ≤ a ≤ L + c 2 (expensive prediction calculation), ⟨3, r -a⟩ if a > L + c 2 (long jobs after expensive prediction).(8) Lemma 10. For DelayPredict in both the external cost model and the server time cost model, the expected mean response time for a short job isE[T ] DelayPredict,S ext = E[T ] DelayPredict,S srv = λ 2(1 -ρ L ) L 0 x 2 f (x) dx + ∞ L L 2 f (x)dx + L 0 xf (x)dx, where ρ L = λ L 0 xf (x)dx + ∞ L Lf (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 new [rank worst d J (a)], X old 0 [r worst ] and X old i [r worst ] 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 is its initial rank: rank worst d J (a) = ⟨1, -a⟩ and r worst = rank worst d J (0) = ⟨1, 0⟩. X new [rank worst d J (a)]: Since short jobs have higher priorities than long jobs, and they are scheduled FCFS, a new job does not preempt J. Hence X newx K [⟨1, -a⟩] = 0. X old 0 [r worst ]: If an old job I is short, it remains original until it is completed. Otherwise, it remains original only for L times. Thus, for i ≥ 1, X old i,x I [⟨1, 0⟩] = 0 andX old 0,x I [⟨1, 0⟩] = x I if I is short L if I is long E[X old 0 [⟨1, 0⟩]] = L 0 xf (x)dx + ∞ L Lf (x)dx E[(X old 0 [⟨1, 0⟩]) 2 ]] = L 0 x 2 f (x)dx + ∞ L L 2 f (x)dxApplying Theorem 5.5 of SOAP (Scully and Harchol-Balter, 2018) yields the resultE[T ] DelayPredict,S ext = λ 2(1 -ρ L ) L 0 x 2 f (x) dx + ∞ L L 2 f (x)dx + L 0 xf (x)dx, where ρ L = λ L 0 xf (x)dx + ∞ L Lf (x)dx .Lemma 11. For DelayPredict in the external cost model, the expected mean response time for a long job of true size x J and predicted size r isE[T (x J , r)] DelayPredict,L ext = λ 2(1 -ρ ext L,r ) 2 L x=0 x 2 f (x)dx + r y=0 ∞ x=L x 2 • g(x, y)dxdy + ∞ y=r ∞ x=L L 2 • g(x, y)dxdy + ∞ t=r ∞ x=L+t-r g(x, t) • (x -L -(t -r)) 2 • dxdt + x J 0 1 1 -ρ ext L,(r-a) + da, where ρ ext L,r = λ L x=0 xf (x)dx + r y=0 ∞ x=L x • g(x, y)dxdy + ∞ y=r ∞ x=L L • g(x, y)dxdy is the load due to short 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).To analyze DelayPredict for a long job in the external cost model using SOAP, we first find the worst future rank and then calculate X new [rank worst d J (a)], X old 0 [r worst ] and X old i [r worst ] for long job. As described in (7), the rank function for long jobs is monotonic, and every job's rank is strictly decreasing with age, thus J's worst future rank is its initial rank, here: rank worst d J (a) = ⟨2, r -a⟩ and r worst = rank worst d J (0) = ⟨2, r⟩. X new [rank worst d J (a)]: Suppose that a new job K of predicted size r K arrives when J has age a J . J's 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. If K is long and has a predicted job size less than J's predicted remaining process time (r -a J ), K will preempt J and proceed until completion. Otherwise, If 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 L time.X new x K [⟨2, r -a⟩] = x K K is short x K 1(r K < r -a) + L • 1(r K ≥ r -a) K is long E[X new [⟨2, r -a⟩]] = L x=0 xf (x)dx + r-a y=0 ∞ x=L x • g(x, y)dxdy + ∞ y=r-a ∞ x=L L • g(x, y)dxdy X old 0 [r worst ]:Whether another job I 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. If I is short, then it remains original until its completion. Alternatively, ifI is long, it is original until completion if r I ≤ r, otherwise, it is original until L. X old 0,x I [⟨2, r⟩] = x K K is short x K 1(r K < r) + L • 1(r K ≥ r) K is long E[X old 0 [⟨2, r⟩]] = L x=0 xf (x)dx + r y=0 ∞ x=L x • g(x, y)dxdy + ∞ y=r ∞ x=L L • g(x, y)dxdy E[(X old 0 [⟨2, r⟩]) 2 ]] = L x=0 x 2 f (x)dx + r y=0 ∞ x=L x 2 • g(x, y)dxdy + ∞ y=r ∞ x=L L 2 • g(x, y)dxdy X old i [r worst ]:If another job I is long and if r I > r, then I starts discarded but becomes recycled when r I -a = r. This starts at age a = r I -r and continues until completion, which will be xI -L -a I = x I -L -(r I -r). Thus, for i ≥ 2, X old i,x I [⟨2, r⟩] = 0. Let t = r I : X old 1,x I [⟨2, r⟩] = 0 if I is short x I -L -(t -r) if I is long E[X old 1 [⟨2, r⟩] 2 ] = ∞ t=r ∞ x=L+t-r g(x, t) • (x -L -(t -r)) 2 • dxdtApplying Theorem 1 leads to the result.E[T (x J , r)] DelayPredict,L ext = λ 2(1 -ρ ext L,r ) 2 L x=0 x 2 f (x)dx + r y=0 ∞ x=L x 2 • g(x, y)dxdy + ∞ y=r ∞ x=L L 2 • g(x, y)dxdy + ∞ t=r ∞ x=L+t-r g(x, t) • (x -L -(t -r)) 2 • dxdt + x J 0 1 1 -ρ ext L,(r-a) + da Where ρ ext L,r = λ L x=0 xf (x)dx + r y=0 ∞ x=L x • g(x, y)dxdy + ∞ y=r ∞ x=L L • g(x, y)dxdy .Lemma 12. For DelayPredict policy in the server cost model, the expected mean response time for a long job of true size x J and predicted size r isE[T (x J , r)] DelayPredict,L srv = λ 2(1 -ρ srv L,r ) 2 L x=0 x 2 f (x)dx + r y=0 ∞ x=L (x + c 2 ) 2 • g(x, y)dxdy + ∞ y=r ∞ x=L (L + c 2 ) 2 • g(x, y)dxdy + ∞ t=r ∞ x=L+t-r g(x, t) • (x -L -(t -r)) 2 • dxdt + x J 0 1 1 -ρ srv L,(r-a) + da, where ρ srv L,r = λ L x=0 xf (x)dx + r y=0 ∞ x=L (x + c 2 ) • g(x, y)dxdy + ∞ y=r ∞ x=L (L + c 2 ) • g(x, y)dxdy 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's worst future rank is rank worst d J (a) = ⟨3, r -a⟩ and r worst = rank worst d J (0) = ⟨3, r⟩. Now we calculate X new [rank worst d J (a)], X old 0 [r worst ] and X old i [r worst ] for long jobs in the server cost most.X new [rank worst d J (a)]: J's delay due to K also depends on K is short or long. If I is short, then it remains it is scheduled until its completion. Alternatively, if I is long its prediction is scheduled for c 2 . In addition, if r I ≤ r then it is scheduled until completion, otherwise it is scheduled until L.X new x K [⟨3, r -a J ⟩] = x K K is short (c 2 + x K ) • 1(r K < r -a J ) + (c 2 + L) • 1(r K ≥ r -a J ) K is long E[X new [⟨3, r -a⟩]] = L x=0 xf (x)dx + r-a y=0 ∞ x=L (x + c 2 ) • g(x, y)dxdy + ∞ y=r-a ∞ x=L (L + c 2 ) • g(x, y)dxdy X old 0 [r worst ]:The analysis is similar to the new arrival job. Whether another job I 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.X old 0,x I [⟨3, r⟩] = x K K is short (c 2 + x K ) • 1(r K < r) + (c 2 + L) • 1(r K ≥ r) K is long E[X old 0 [⟨3, r⟩]] = L x=0 xf (x)dx + r y=0 ∞ x=L (x + c 2 ) • g(x, y)dxdy + ∞ y=r ∞ x=L (L + c 2 ) • g(x, y)dxdy E[(X old 0 [⟨3, r⟩]) 2 ]] = L x=0 x 2 f (x)dx + r y=0 ∞ x=L (x + c 2 ) 2 • g(x, y)dxdy + ∞ y=r ∞ x=L (L + c 2 ) 2 • g(x, y)dxdyX old i [r worst ]: As described before, if another job I is long and if r I > r, then I starts discarded but becomes recycled when r I -a = r. This starts at age a = r I -r and continues until completion, which will be xI -L -a I = x I -L -(r I -r). Thus, for i ≥ 2, X old i,x I [⟨3, r⟩] = 0. Let t = r I : X old 1,x I [⟨3, r⟩] = 0 if I is short x I -L -(t -r) if I is long E[X old 1 [⟨3, r⟩] 2 ] = ∞ t=r ∞ x=L+t-r g(x, t) • (x -L -(t -r)) 2 • dxdtApplying Theorem 1 leads to the result.E[T (x J , r)] DelayPredict,L srv = λ 2(1 -ρ srv L,r ) 2 L x=0 x 2 f (x)dx + r y=0 ∞ x=L (x + c 2 ) 2 • g(x, y)dxdy + ∞ y=r ∞ x=L (L + c 2 ) 2 • g(x, y)dxdy + ∞ t=r ∞ x=L+t-r g(x, t) • (x -L -(t -r)) 2 • dxdt + x J 0 1 1 -ρ srv L,(r-a) + da Where ρ srv L,r = λ L x=0 xf (x)dx + r y=0 ∞ x=L (x + c 2 ) • g(x, y)dxdy + ∞ y=r ∞ x=L (L + c 2 ) • g(x, y)dxdy .F.1 Datasets descriptionsFor real-world traces, we use datasets from Amvrosiadis et al. (Amvrosiadis et 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 of these jobs utilize Spark (Salloum et al., 2016) , while the remaining jobs are handled by proprietary data analytics frameworks developed in-house. The dataset spans a period of 9 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., 2011) .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 we used contains 385, 072 jobs. Google has not disclosed the exact hardware specifications of each cluster node in this trace.Trinity Dataset: Trinity is the largest supercomputer at Los Alamos National Laboratory (LANL), dedicated to capability computing. Capability clusters are large-scale, high-demand resources introducing cutting-edge hardware technologies that aid in achieving significant computing milestones, such as higher-resolution climate and astrophysics models. Trinity's hardware was deployed in two pre-production phases before being fully operational, and the trace was collected before the completion of the second phase. Trinity consisted of 9408 identical compute nodes, totaling 301056 Intel Xeon E5-2698v3 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.Their system leverages machine learning to predict job runtimes in 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 successfully completed jobs and normalize runtimes to a mean of 1, 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 JamaisVu scheduling system (Tumanov et al., 2016) .JVuPredict is a runtime (service time) prediction module that is part of the JamaisVu 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 a prediction is made for a 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.For the synthetic traces, we considered two job service distributions; exponentially distributed with mean 1 (f (x) = e -x ) and the Weibull distribution with cumulative distribution F = 1-e - √ 2x . 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 p T (x) and g(x, y) for our prediction models. Each of the two-stage predictors could be from a different model.In our simulation, each data point is obtained by simulating initially empty queues over 1, 000, 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. Here we present some additional simulations of the the Weibull distribution using both predictors. 38th Conference on Neural Information Processing Systems (NeurIPS 2024).In Section 4.4 we discuss the case of random costs from a distribution.We could also consider any non-size-based policy such as LCFS or FB.We note that SOAP provides for finding the Laplace-Stieltjes transform of the response time distribution; we focus on the mean response time throughout this paper for convenience in comparisons.X new [rank worst d J (a)] is a random variable representing how long a new job that just arrived to the system is served until it completes or surpasses rank worst d J (a)X old 0 [rworst] is a random variable representing how long a job is served while it is considered original with respect to the rank rworstX old i [rworst] is a random variable representing how long a job is served while it is considered recycled for the i time with respect to the rank rworst 


Decision: 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.

Reviews: review: paper_summary: paper_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.

The 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.
The 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.

The authors analyze this algorithm under both cost models using the SOAP analysis framework and obtains explicit expressions for the mean response times of jobs.
strength_weakness: strength_weakness: - The paper is missing some references to prior work. For example, 
(i) "Online algorithms with Costly Predictions" (Drygala et al) considers costly predictions in other learning augmented settings. 
(ii) "Parsimonious Learning-Augmented Caching" (Im et al) considers caching with goal of using few predictions.
(iii) many papers on learning augmented scheduling.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- 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.
questions: 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
- (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: limitations: N/A
paper_summary: paper_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.
The 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.
strength_weakness: strength_weakness: 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.
questions: questions: N.A.
limitations: limitations: N.A.
paper_summary: paper_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.
In 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.
This 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.
In 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. 

The 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.

The 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.
strength_weakness: strength_weakness: - 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.
- 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.

Given 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.
questions: questions: Typos:
- Line 114 "somewhat"
- Line 224 missing whitespace
limitations: limitations: -

Comments: comment: I thank the authors for their rebuttal. I have the impression that several issues can be indeed fixed by a strongly refined presentation. As I wrote in my initial review, the paper introduces several interesting concepts, which are interesting for the area of learning-augmented algorithms. Thus, I decided to slightly raise my score from 4 to 5.
However, I would like to leave it open to the AC/SACs on how to value potential improvements via a strongly refined presentation.
- Acknowledge the recent interest in cost of predictions for learning augmented algorithms and their role in building infrastructure for ML systems 
- Appreciate the additional experiments with the lighter tailed normal distribution
- Agree that public datasets with ML job distributions are unavailable (or atleast I am unaware of those as well). I would appreciate if the authors include a remark explaining the characteristics of the real-world dataset in the final version. 
- Given the strengths of the paper in the novel model of the costs, solid theory with closed form expressions and well-presented analysis, I increase my score to 7