acceptodds
Under review as a conference paper at ICLR 2027

When Predictions Take Time: Cost-Aware Predictor Selection for Learning-Augmented Scheduling

Abstract

Learning-augmented scheduling algorithms use predictions of unknown job processing times to improve over non-clairvoyant baselines, but prior work often treats predictions as costless. In practice, more accurate predictors require more complex models and longer inference times; this latency is itself a scheduling cost. We fill this gap by studying predictor selection for single-machine scheduling to minimize total completion time: given this accuracy–latency tradeoff, which predictor should be used? We call predictor selection *cost-aware* when it accounts for inference latency alongside prediction accuracy, and *cost-unaware* when it minimizes prediction error alone. We introduce an algorithm-agnostic framework in which any learning-augmented scheduler with an error-response curve can be analyzed. We prove that inference latency contributes an unavoidable term to the objective via a tight lower bound for deterministic algorithms and establish that the cost-aware objective has a unique optimal complexity following a power-law scaling: heavier workloads justify more complex predictors. Ignoring prediction cost incurs a non-vanishing performance ratio of , where . Experiments on the ATLAS GPU-cluster trace, the Azure Functions serverless trace, and the Alibaba microservices trace confirm the theoretical results.

Primary area:
optimization
Keywords:
Learning-augmented scheduling, inference-aware optimization, cost-aware predictor selection, single-machine scheduling, total completion time

Reviews

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

This paper studies learning-augmented scheduling when obtaining job-size predictions incurs inference latency. The authors consider a model where all jobs are available at the beginning, and the goal of the scheduler is to minimize the total completion time. Predicting/learning the job processing-times more accurately will help the scheduler make better decisions, e.g., to schedule the shortest jobs first. However, when the time to perform learning/prediction increases with the accuracy, it is then unclear whether using the highest-accuracy predictor is still the best choice. The authors study this trade-off between prediction accuracy and inference latency. The paper's main contribution is to prove an Ω(nτ)\Omega(n\tau) additive lower bound under an adversarial setting, even when jobs can be processed during inference. Experiments using traces from Alibaba GPU clusters, Azure Functions, and Alibaba microservices seem to be confirm that using suboptimal predictor can result into the shortest total completion time.

Critical strengths
  1. The adversarial lower-bound in Theorem 2 on the total completion time seems to be interesting. Assuming that the adversarial can pick arbitrary processing times of the jobs, the author reveals that there exists at least an nτn \tau additive gap compared to the offline OPT.

  2. The main conclusions are confirmed using real-world traces from Alibaba GPU clusters, Azure Functions, and Alibaba microservices.

Critical weaknesses
  1. Other than Theorem 2, the rest of the theoretical results seem to be straight-forward. For example, Thm 1 follows directly from adding the inference latency to each job. Thm 3 follows from standard optimality conditions.

  2. There seems to be a gap between the theoretical results and the trace-based experiments. The theory relies on the knowledge of the competitive ratio ρA(η)\rho_A(\eta) of the scheduling algorithm AA at a given prediction accuracy η\eta. It is unclear how one can obtain this competitive ratio in practice. The experiments seems to ignore this difficulty, and directly use a grid search to select the best predictor. It is thus unclear how the derived theory can be used to guide the choice.

  3. One alternative algorithm that the authors did not study is the following: Use the fast predictor to decide which job to schedule first; while the first job is being run, use the slow predictor simultaneously to learn the processing times of the other jobs more accurately. It seems that this strategy could hide the latency of the slow predictor in most cases, making the theoretical results in the paper less interesting.

Questions for authors
  1. Can you explain how to obtain the competitive ratio ρA(⋅)\rho_A(\cdot) in practice? If not, how can the derived theory help us making better choices in practice?

  2. Could you comment on how the results would change if one first picks a job using a fast predictor, and then utilizes the processing time of first job to run the slow predictor for other jobs.

4 comments
AuthorsOpenReview ↗

Author Response

Thank you for the careful review, and for the positive assessment of soundness and presentation. We are glad that the lower bound of Theorem 2 and the experiments on three real-world traces stand out as strengths. The revision addresses the three weaknesses. The lower bound of Theorem 2 is now exact (W1). The selection works with a measured ratio in place of ρA\rho_A and without a grid search (W2 and Q1). The strategy proposed under W3 and Q2 is analysed in theory and on the traces.

W1: Depth of the theoretical results.

Theorems 1 and 3 prepare the two main results, and the revision makes both main results exact.

We first recap the logic of the theortical section: Theorem 1 is the upper bound that pairs with the lower bound of Theorem 2, and Theorem 3 is the step to the closed form of Corollary 2.

1. The price of prediction latency is now exact. The submission left a factor of about 2 between the lower bound (Theorem 2) and the cost of waiting (Theorem 1). The revision shows that Round Robin during inference attains the lower bound on every instance (Theorem 2 (b)). The price is also exact on mm machines, which the submission listed as open, for randomized algorithms (Theorem 6), and with a second, fast predictor (Theorem 7, see W3).

2. The price of ignoring latency is now exact. We before gave an instance that loses the factor 1+κ1+\kappa (Theorem 4). Proposition 2 of the revision proves the matching upper bound for every finite set of predictors, with no smoothness. The regime parameter is therefore a two-sided guarantee.

W2 and Q1: How the theory guides the choice in practice.

We understand the concern. We compared the candidates on a batch whose true durations are known, and did not say how a predictor is chosen beforehand. We propose how the predictor is chosen before a batch runs, with no grid search on that batch. With trained models and measured latencies, this choice lowers JJ by 7.4% ± 1.0% relative to the most accurate model, and two guarantees hold before the run.

1. How the predictor is chosen. ρA\rho_A is the upper bound proved for the scheduler (1+x1 + x for SPJF), so it is not estimated. In practice the measured ratio (total completion time over OPT\mathrm{OPT}) takes its place, and the selection results hold verbatim.

  • Across model classes there is no common curve, so we take the model with the smallest JJ on the previous batch. With 36 trained models of three classes on the microservices trace, this choice has lower JJ than the most accurate model in 19 of 19 pairs of consecutive batches (Wilcoxon p=3.8×10−6p = 3.8 \times 10^{-6}) and stays within 1.05% of the best model of the batch.

  • Within one model class, the best complexity θ⋆\theta^\star has a closed form. Fitted on the five smallest of the 12 trained LightGBM models of the microservices trace (Table 1), the closed form gives θ⋆≈17,900\theta^\star \approx 17{,}900, between the measured optimum and a model that costs 0.41% more .

  • When the workload changes, the closed form follows the workload through OPT/n\mathrm{OPT}/n. On Azure and ATLAS, OPT/n\mathrm{OPT}/n varies across batches by a factor of 5,756 and 3. We fit the constants once, on the first batch, with the controlled predictors. For every later batch, the closed form takes OPT/n\mathrm{OPT}/n of the previous batch. The resulting choice costs a median of 0.42% and 0.05% more than a grid search on the batch itself.

2. The guarantees before the run.

  • The most accurate predictor costs at most 1+κ1+\kappa times the best choice, whatever the candidates. κ\kappa needs only the latency of a predictor and OPT\mathrm{OPT}, which logged batches estimate.

  • The closed form needs an estimate of OPT\mathrm{OPT}. An estimate that is off by a factor of 2 costs at most 6.2%.

W3 and Q2: A fast predictor first, a slow predictor in parallel.

Thank you for proposing this concrete strategy. We analysed it in theory and ran it on the traces. The strategy lowers the cost when the fast predictions order all jobs. The trade-off between accuracy and latency remains. It moves to the fast predictor.

1. Theory. Given a fast predictor at time zero with total absolute error at most δ\delta, and perfect predictions at time τ\tau, the exact worst-case loss is (n−1)min⁡{δ,τ/2}(n-1)\min\lbrace\delta, \tau/2\rbrace. Without the fast predictor it is (n−1)τ/2(n-1)\tau/2 (Theorem 2). In the worst case, the latency is hidden only when δ\delta is below τ/2\tau/2.

The results obtained from traces are illustrated in next comment.

AuthorsOpenReview ↗

Author response 2/2

2. Traces. We use the controlled predictors of Section 4.2. The slow predictor is the most accurate one, and both predictors start at time zero. We ran the strategy in two forms and with every fast predictor of the grid.

  • As the reviewer suggests, the fast predictor picks one job, and this job runs while the slow predictor computes. The other n−1n-1 jobs still wait for the slow predictions. Even with the best fast predictor, the mean cost over 20 seeds stays within 0.4% of waiting for the most accurate predictor.

  • We extended the setting into a new form: all jobs run in the order of the fast predictions, and the slow predictions take over when they arrive. With the best fast predictor, this form has the lowest cost in Table 7. The cost is 4.4% ± 0.1% (Azure) and 6.1% ± 0.1% (ATLAS) below waiting for the cost-aware predictor, in all 20 seeds.

However, the gain of the second form depends on the fast predictor. A fast predictor that is too inaccurate or too slow costs 3.3% to 7.3% more than the best one. On each trace, one of the two costs more than waiting for the cost-aware predictor. The selection problem of the paper therefore remains, now for the fast predictor.

Thank you again for the careful review, which improved the paper. The strategy proposed under W3 is now analysed exactly in the paper (Theorem 7) and measured on the traces. The question on ρA\rho_A led to a selection made before the run, tested on 36 trained models on the Alibaba microservices trace. We hope that these changes, together with the exact results under W1, address the three concerns. We would be grateful if the reviewer would consider raising the rating, and we are glad to answer any remaining questions.

I thank the authors for the additional results. While it is good to see that using the fast/slow predictor leads to improvements compared to the original proposal, I feel that this result raises doubts on whether the original model is the most relevant one for this problem. A more thorough study of this type of sequential decision making is needed to properly understand the right control policy (e.g., no need to made the machine idle if the first job finishes sooner). Thus, I am unable to raise my score.

AuthorsOpenReview ↗

Further response

Thank you for actively engaging in discussions! We will clarify and answer your further questions below.

The reviewer noticed the improvement over waiting for the predictions. In our previous reply, however, the fast predictor was not just any fast predictor. It was the best fast predictor. We found it by comparing the total cost of every candidate on the batch, as we did for the cost-aware predictor, so it was chosen by total cost rather than by accuracy or at random. In other words, the fast/slow strategy already uses our predictor selection. We then compared it with the weakest baseline, waiting for the predictions, and this may have suggested that a smarter strategy can replace predictor selection. We are sorry for the confusion.

In the experiments, we ran the strategy in two example forms. In the first, the fast predictor chooses one job, which runs while the slow predictor computes, and the other jobs wait for the slow predictions. If this job finishes early, the machine idles, which is indeed not needed. In the second, all jobs run in the order of the fast predictions until the slow predictions take over, so the machine never idles. These are two examples of the fast/slow strategy, not our setting.

A fast predictor helps only when it is accurate, and it is usually less accurate. You can imagine that if a random fast predictor's predictions are wrong, the machine can start a very long job that looks short. Every other job waits behind it, raising the total completion time significantly. In the worst case, following an inaccurate fast predictor loses twice as much as simply sharing the machine equally among all jobs until the slow predictions arrive. Picked by accuracy alone, the fast predictor would be the slowest candidate. On the traces, a fast predictor that is too inaccurate or too slow costs 3.3% to 7.3% more than the best one, and on each trace one of them is even worse than our original cost-aware choice.

Our theory shows that using the waiting time reduces the cost of the delay but does not remove it, so the choice of predictor matters under every strategy. Besides waiting, we also study strategies that keep the machine busy, such as Round Robin while predicting and predictions delivered job by job. The fast/slow strategy is one more strategy of this kind in our setting, not a new model that beats our design.

We believe this paper is valuable for the learning-augmented scheduling community. To our knowledge, the following points were not known before.

  • The time a prediction takes is a cost that no scheduling strategy can hide, and its exact price is known.
  • One number, computed from a trace and the per-job latency before any model is trained, tells how much choosing the most accurate predictor can cost.
  • The best predictor grows with the workload in a closed form, so it can be chosen without testing every model.

Thank you again for the careful reading. We hope this clarifies the point, and we would be grateful if it could be considered in the final assessment.

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

This paper studies how to choose a predictor for learning-augmented single-machine batch scheduling (minimizing total completion time) when more accurate predictors take longer to run, since every job waits for inference before execution. It plugs any learning-augmented scheduler into the framework through an error-response curve ρ\rho. It shows the bounds in a wait-then-schedule policy and in an adaptive-adversary policy. Under convexity assumptions, It then considers the cost-aware objective where the power-law forms for latency and error give a closed-form scaling. Experiments cover the ATLAS GPU-cluster, Azure Functions, and Alibaba microservices traces.

Critical strengths
  • Practical, well-illustrated problem settings. Prior learning-augmented scheduling treats predictions as free. The toy example (a perfect but slow predictor losing to Round Robin) makes the accuracy–latency tradeoff immediately intuitive.
  • Sound theoretical results. The derivations of the theoretical results seem correct.
  • Interpretable regime diagnostic. κ\kappa is computable from a trace and per-job latency. This is helpful to link the theoretical results and intuitions to the empirical results for validations.
  • Empirical experiments have good coverage and are reproducible. All traces are public, code is released, and configurations are reported.
Critical weaknesses
  • Although the derivations seem correct for the theoretical results, I find the theories relatively shallow.
  • Restrictive inference model: Batch inference is assumed to block a single machine serially. This ignores per-job prediction on arrival, pipelining, running Round Robin during the wait, and inference on separate or parallel hardware. The setting seems to be narrow, making the results in this paper hard to generalize.
  • Weak scaling-law support. On ATLAS the slope is 1.24 against a predicted 0.61. Additionally, the argument for “restores per-bucket agreement on both traces.” could be strengthened.
  • Unclear novelty versus prior work, in particular, Jiang et al. (RTCSA 2025). The contribution in the ML aspects seem light for ICLR.
  • An additional section on lessons learned/guides to practitioners in the field would be very helpful, considering the experiments used realistic real-world traces.
Questions for authors

I think there are few questions that could be addressed from the weakness section.

5 comments
AuthorsOpenReview ↗

Author Response 1/2

Thank you for the review, and for recognizing the practical problem setting, the regime parameter κ\kappa as a diagnostic, and the reproducibility of the experiments. The revision makes the two central results exact (W1), measures the four deployment alternatives named under W2, tests the scaling law with no fit per bucket (W3), and adds the guidance for practitioners suggested under W5. We respond to each weakness below. Revised text is quoted from the revision.

W1: Depth of the theoretical results.

The revision deepens the two main theoretical results. Both are now exact.

1. The price of prediction latency is now exact. The submission left a factor of about 2 between the lower bound (Theorem 2) and the cost of waiting. An analysis of Round Robin as equal sharing shows that Round Robin during inference attains the lower bound (Theorem 2 (b)). The price is also exact on mm machines, which the submission listed as open (Theorem 5), and for randomized algorithms (Theorem 6).

2. The price of ignoring latency is now exact. The submission gave an instance that loses the factor 1+κ1+\kappa (Theorem 4). Proposition 2 proves the matching upper bound for every finite set of predictors, with no smoothness. The regime parameter is therefore a two-sided guarantee.

W2: Scope of the inference model.

Thank you for suggesting these inference models. They fit the framework and extend the theory to more complex systems. The added tests and results follow.

The framework carries over to each of the four alternatives.

1. The four alternatives. The submission treats two of them in theory, running jobs during the wait (Theorem 2) and per-job prediction on arrival, and measured none, so the scope looked narrower than it is. We now measure all four with the controlled predictors of Section 4.2 (Appendices E.4 and E.6).

  • Each alternative lowers the latency term, and the trade-off between accuracy and latency remains. Relative to the most accurate predictor under the same alternative, the cost-aware predictor lowers JJ by 6.0% on Azure and 5.2% on ATLAS with Round Robin during the wait (inference on separate hardware), by 3.2% and 2.8% with pipelining, by 4.2% and 3.4% with parallel inference on 4 devices, and by 11.6% and 14.9% with per-job prediction on arrival at load 0.9.

  • The cost-aware predictor still has the lower JJ in all 20 seeds of each case (standard deviation at most 0.1 percentage points in the first three cases and 1.6 in the fourth).

2. More machines. The exact price of latency is almost independent of the number of machines mm, while OPT falls about mm-fold, so κ\kappa grows about mm-fold. Under Round Robin during inference, the reduction rises from 6.0% on one machine to 37.7% on 16 machines on Azure (Appendix E).

W3: Support for the scaling law.

To strengthen the support for the scaling law, the revision tests the law on every batch of both traces, with no fit per bucket (Section 4.3).

1. The bucket test of the submission. The slope 1.24 includes a seventh bucket in which the best predictor is the smallest point of the grid. Without this bucket, the slope falls to 0.80. The bucket test is kept in Appendix D.

2. The new test on every batch. Constants fitted once on the first batch predict the best complexity of each later batch from the OPT/n\mathrm{OPT}/n of that batch alone, with the controlled predictors of Section 4.2. There are 72 later batches on ATLAS and 197 on Azure, where OPT/n\mathrm{OPT}/n varies by a factor of 5,756.

  • The measured slope is 0.50 on ATLAS (95% interval 0.46 to 0.54) and 0.49 on Azure (0.43 to 0.55). The predicted slope is 0.51 and 0.57 with the exponent fitted where the optima lie, and 0.61 and 0.55 with the whole-grid exponent.

  • The measured optimum is within a factor of 1.25 of the prediction in 72 of 72 and 179 of 197 batches, and the predicted choice costs at most 0.19% and 0.51% more than the best one.

  • On the trained LightGBM models of the microservices trace, Corollary 2 gives θ⋆≈12,000\theta^\star \approx 12{,}000 against a measured optimum of 12,600.

W4: Relation to prior work and the machine-learning contribution.

Jiang et al. (2025) observe the phenomenon in simulation. The submission explains the phenomenon and turns the observation into a selection rule. The submission discusses this work in Section 1. The table makes the comparison explicit.

Jiang et al. (2025)This submission
QuestionHow do accuracy and inference time trade off?Which predictor to select, and when does the choice matter?
ResultEmpirical. Beyond some point, latency outweighs accuracy.Theorems. The latency cost cannot be scheduled away, the best predictor has a closed form, and κ\kappa says when the choice matters (Theorems 2 to 4, Corollary 2).
EvidenceSimulated datasetsThree production traces, trained models of three classes
AuthorsOpenReview ↗

Author Response 2/2

W4: The contribution lies at the interface of machine learning and scheduling. Its core is a new term in the competitive analysis of learning-augmented scheduling, the inference latency of the learned predictor.

1. What the submission studies about the predictor. Earlier competitive analyses assume that predictions are available when scheduling starts (Section 1). Here the predictor is a trained model, and the question is how much accuracy is worth waiting for. Accuracy and inference latency are measured on trained LightGBM, k-NN and MLP models (Section 4).

2. Structural insights for model selection. The most accurate model can be the wrong model. On the trained LightGBM models of Table 1, it costs 8.5% more than a model about 16 times less complex. Latency and prediction error both enter the objective as completion time, so the selection has no weight to tune (Section 3.2). κ\kappa tells, before training, which model classes pay off.

How much prediction an algorithm needs is a topic at ICLR. Sadek & Elias (ICLR 2024) design caching algorithms that use few predictions, because producing predictions can be costly. Guyot & Lassota (ICLR 2025) study which predictions help an online scheduler. The submission asks the same question when a prediction takes time.

W5: Guidance for practitioners.

Thank you for this suggestion. The revision adds a paragraph "Lessons for practitioners" to Section 4.3, and Appendix F gives a step-by-step guide.

1. Lessons from the traces (added paragraph in Section 4.3).

  • Choose by measured total cost, not by accuracy. On the microservices trace, the model with the smallest JJ on the previous batch stays within 1.05% of the best of 36 trained models.

  • The job scale decides where the selection matters. The same 10 ms-per-job predictor has κ=2.88×10−5\kappa = 2.88 \times 10^{-5} on ATLAS, 0.1590.159 on Azure and 11.411.4 on the microservices trace.

2. The four steps. Compute κ\kappa before training any model, and deploy the most accurate model if κ\kappa is below 1%. Otherwise select by measured cost on a sample of 1,000 jobs. Track the workload with the closed form. Lower the latency term before buying accuracy.

We hope this response addresses your main concerns, and we are glad to provide further clarification or targeted experiments. Given the new trace, the cross-architecture candidate set and the practitioner guide, we would be grateful if the reviewer could reassess the significance of the contribution. Thank you for the care you have given our paper.

AuthorsOpenReview ↗

Reply summary and follow-up for concerns

Dear Reviewer,

Thank you again for the review, and for recognizing the practical setting, the regime parameter as a diagnostic and the reproducibility of our experiments. Several changes in the revision follow your suggestions directly, and we would value your view on them before the discussion closes.

On the depth of the theory, both main results are now exact. The price of latency is exact, also on many machines and for randomized algorithms. The price of ignoring latency is exact too, and its bound now holds for any finite set of predictors, so the diagnostic you noted applies to any set of trained models. On the scope, we now measure all four alternatives to blocking batch inference that you named (Round Robin during the wait, pipelining, parallel inference and per-job prediction on arrival). Each lowers the latency cost, and choosing the predictor by total cost still beats the most accurate one under each of them.

For the scaling law, we now test it on every batch with constants fitted once, and the measured optimum is within a factor of 1.25 of the prediction in 179 of 197 batches on Azure and in all 72 on ATLAS. On prior work, Jiang et al. (2025) show the trade-off empirically using simulated data, while our paper proves when it matters and turns it into an algorithm-agnostic selection rule, tested on 36 trained models of three classes. Following your last suggestion, Section 4.3 now has a paragraph of lessons for practitioners, and Appendix F gives a step-by-step guide.

If any part still seems narrow or light to you, could you tell us which one? We would be glad to answer it directly. We believe this paper is valuable to the ICLR community. It asks a machine learning question, which model to deploy when inference takes time. To our knowledge, the following points were not known before.

  • The time a prediction takes is a cost that no scheduling strategy can hide, and its exact price is known.
  • The regime parameter, computed from a trace and the per-job latency before any model is trained, tells how much choosing the most accurate model can cost.
  • The best model grows with the workload in a closed form, so it can be chosen without testing every model.

Best regards, The authors

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

This paper investigates cost-aware predictor selection for learning-augmented single-machine batch scheduling to minimize total completion time. They prove that batch inference latency incurs an unavoidable additive penalty which scales with the batch size. Under smooth, continuous power-law assumptions for error and latency, they derive a closed-form scaling law showing that optimal complexity scales with workload pressure. Finally they introduce a regime parameter which is ratio of prediction cost to optimal time for clairvoyant policies to evaluate whether prediction cost matters.

Critical strengths
  1. Formally introducing inference latency into the competitive analysis of learning-augmented scheduling
  2. The regime parameter provides a clean heuristic for system designers to gauge whether prediction overhead will ruin a schedule
Critical weaknesses
  1. The framework assumes a strict batch, single-machine model and smooth, differentiable power-law trade-offs for error and latency without any justification for such assumptions. While the internal mathematical derivations are rigorous, the transition from smooth continuous power-law abstractions to discrete, messy real-world engineering environments introduces notable modeling gaps.
  2. While formalizing inference latency in competitive analysis is a necessary step forward, the core qualitative insight—that running slower models can degrade completion time—is intuitive. Furthermore, the heavy reliance on idealized continuous trade-offs limits the depth of new insights regarding complex, discrete systems.
Questions for authors
  1. How does your continuous power-law optimization hold up when faced with discrete model updates (e.g., jumping across model architectures where error and latency do not scale smoothly)? What is the basis for selecting power law dependency of error and latency on model complexity? Is this for mathematical tractability or is this based on empirical evidence?
  2. Given that the optimal complexity depends explicitly on OPT(I) how brittle is this plug-in selection mechanism under non-stationary online traffic where offline estimates of OPT experience rapid temporal drift?
3 comments
AuthorsOpenReview ↗

Author Response 1/2

Thank you for the review, and for recognizing two strengths of the paper, (1) formally introducing inference latency into the competitive analysis of learning-augmented scheduling and (2) the regime parameter as a clean heuristic for system designers. We respond to each point below.

W1: Assumptions and real-world models.

Thank you for raising this point. The submission states the assumptions and their basis in Section 2, but too briefly. We address each of them here, and the revised Section 2 now states why the analysis starts from batch arrivals on one machine and which results use each assumption.

The main results use neither Assumptions 1 to 3 nor the power law. These assumptions serve only to locate the best predictor, and the selection of a predictor uses no curve.

1. Where each assumption is used.

AssumptionUsed inBasis
Batch arrivals, one machineTheorems 1, 2 and 4The model of Purohit et al. (2018) and Im et al. (2023), whose guarantees the framework takes as its input ρ\rho
Differentiability and convexity (Assumptions 1 to 3)Theorem 3 onlyA more complex predictor is slower and more accurate (Jiang et al., 2025), with diminishing returns. No functional form is assumed.
Power lawCorollary 2 and Proposition 1 onlyEmpirical scaling laws, in which the loss decays as a power law in model size (Kaplan et al., 2020)

The main results are the price of latency (Theorems 1 and 2) and the price of ignoring it (Theorem 4 and κ\kappa). They need only the setting in the first row of the table. The revised Problem definition in Section 2 explains why the analysis starts there.

  • It is the base of the field. Learning-augmented scheduling started on one machine with batch arrivals, where consistency and robustness for non-clairvoyant scheduling were first proved (Purohit et al., 2018) and later refined (Im et al., 2023). The framework takes these guarantees as its input ρ\rho, so it starts from the same base.
  • It isolates the latency. Batch arrivals remove release-time structure, and one machine removes parallel slack that could hide part of the delay.
  • It is the starting point, not the limit. The revision gives the exact price on mm identical machines (Theorem 5) and discusses online arrivals (Appendix C.2).

Real predictors are discrete, and real environments are messy. The framework covers both, because the selection uses no curve and the model contains the noise.

Both points were part of the submission, though not explicitly. Predictor selection (Algorithm 1) already works on a finite set of trained models, and its model already contains the noise of the traces through the irreducible error ηmin⁡\eta_{\min}. The revision makes both explicit and strengthens them as follows.

1. Discrete predictors. The revision adds the discrete form of the theory (Proposition 2), which needs no curve.

  • Within one model family, the smooth theory applies directly. When the models are grid points of a family that satisfies Assumptions 1 to 3, the best model is one of the two grid points next to the continuous optimum θ⋆\theta^\star (Proposition 2 (vi)). We test on real traces.
  • Across model families, no curve is needed. Only models on the lower convex hull of the (latency, ratio) points are ever the best, and each is the best on an interval of workloads OPT/n\mathrm{OPT}/n with explicit thresholds (Proposition 2 (ii), (iv)). Heavier workloads select slower and more accurate models, which is the discrete form of Corollary 2 (Proposition 2 (iii)).
  • In practice, the selection measures JJ for each model and takes the smallest (Algorithm 1). This works on irregular sets. On Azure, the largest trained models even schedule worse than a mid-sized one. The 36 trained models of Q1 follow no common curve.

2. Messy environments.

  • The model contains an irreducible error ηmin⁡\eta_{\min} (Section 2). On the traces, job durations are shaped by gang scheduling, fragmentation, interference and queuing, and ηmin⁡\eta_{\min} absorbs this noise (Appendix D).
  • Theorem 3 holds for every ηmin⁡≥0\eta_{\min} \ge 0. In Corollary 2 the floor adds the same constant to the cost of every predictor, so the best predictor does not move.

Q1 and Q2 in the next comment give the measurements.

AuthorsOpenReview ↗

Author Response 2/2

W2: What the theory adds to the intuition.

The direction of the effect is intuitive. The contribution is to quantify the effect, and the structural insights behind the quantities are not intuitive. The revision now states these insights explicitly.

1. Simple quantities are how this field measures predictions. Consistency and robustness are simple to state, and their value is that they measure the benefit and the risk of a prediction (Purohit et al., 2018). The regime parameter κ\kappa, which the reviewer calls a clean heuristic, does the same for prediction cost.

2. Three insights on which intuition is silent or wrong (Section 3, Structural insights).

  • Work done before the predictions arrive cannot hide the inference delay. Every deterministic algorithm that runs jobs during inference loses at least (n−1)τ/2(n-1)\tau/2 on some instance, even with perfect predictions at time τ\tau (Theorem 2). The revision makes this price exact, also on mm machines and for randomized algorithms (Theorem 2 (b), Theorems 5 and 6).
  • The workload enters the selection only through OPT/n\mathrm{OPT}/n. For jobs from a fixed workload, a larger batch raises the delay nτn\tau and the total work together, so more jobs do not call for a cheaper predictor (Corollary 2).
  • Both terms of JJ are completion time, so the objective has no weight to tune. The single ratio κ=nτ/OPT\kappa = n\tau/\mathrm{OPT} gives the exact worst-case factor 1+κ1+\kappa lost by ignoring latency (Theorem 4, Proposition 2).

The exact price serves the competitive analysis, and κ\kappa serves the system designer. W1 and Q1 answer the concern about discrete systems.

Q1: Discrete model updates and the basis of the power law.

We thank the reviewer for the concrete example of jumps across model architectures. We added an experiment on exactly this case.

The framework covers model jumps across architectures. Across architectures the discrete rule of Proposition 2 needs no curve, and within one architecture the closed form applies.

1. Across architectures, the discrete rule selects well (Section 4.3, Figure 3).

  • We ran the reviewer's case on 36 trained models of three architectures (LightGBM, k-NN, MLP) on the Alibaba microservices trace, with measured inference latencies. The rule takes the model with the smallest JJ on the previous batch.
  • Over 19 pairs of consecutive batches, this choice lowers JJ by 7.4% ± 1.0% relative to the most accurate model, with lower JJ in all 19 pairs (Wilcoxon p=3.8×10−6p = 3.8 \times 10^{-6}), and costs at most 1.05% more than the best model of the batch.
  • The 36 models follow no common curve (one power law through them has R2=0.44R^2 = 0.44, Appendix E.9). The rule needs none, because each model enters only through its own measured cost.
  • The rule also selects well on 60 simulated sets that mix three architectures (Appendix E.8).

2. Within one architecture, the closed form applies, also to irregular models.

  • The trained LightGBM models of Table 1 do not lie on a smooth curve. Between consecutive models the latency exponent ranges from 0.25 to 1.60.
  • A power law still fits the trend (R2=0.99R^2 = 0.99), and the closed form gives θ⋆≈12,000\theta^\star \approx 12{,}000 against a measured optimum of 12,60012{,}600 (Corollary 2, Appendix E.5).

The basis of the power law is both evidence and tractability. The scaling laws cited in Section 2 (Kaplan et al., 2020) and the fit of Table 1 are the evidence, and the power law gives Corollary 2 its closed form.

Q2: The plug-in selection under drifting estimates of OPT.

The plug-in selection is not brittle. An estimate of OPT that is off by a factor of up to 2 raises JJ by at most 6.2% in the worst case and 1.53% on the traces.

1. A rough estimate of OPT is enough, because an error is damped twice.

  • The estimate enters θ⋆\theta^\star through the power 1/(a+b)1/(a+b), so a factor of 2 in OPT moves θ⋆\theta^\star by a factor of about 1.5.
  • JJ is flat around its minimum, so this shift costs little. The submission bounds the loss for errors up to 50% (Proposition 1), and the revision extends the bound to every factor (Section 3.4).

2. Under drift, the loss follows the size of the jump in OPT. Each selection uses the OPT of the previous batch, known on completion, and constants fitted once on the first batch (controlled predictors of Section 4.2, Appendix E.7).

  • On Azure, OPT changes between consecutive batches by a median factor of 1.7 and by up to 54. The estimate is within a factor of 2 in 112 of the 197 batches, and the loss relative to the best predictor is then at most 1.53% (median 0.14%).
  • The loss exceeds 5% in 8 batches, all after OPT jumps by a factor of at least 4.
  • On ATLAS the estimate is within a factor of 2 in all 72 batches, and the loss is at most 0.67%.
AuthorsOpenReview ↗

Follow-up: a short summary of our response

Dear reviewer,

Thank you again for the review, and for seeing the formalization of inference latency as a necessary step forward. We are writing because your main concern, whether the theory holds up in discrete and messy real systems, is the one we worked on most in the revision, and we would value your view before the discussion closes.

In short, the choice of a predictor never uses the smooth curve. It compares the measured total cost of each candidate, so it applies to any set of models. We tested the case you raised, jumps across model architectures. On the Alibaba microservices trace, 36 trained models of three architectures (LightGBM, k-NN and MLP) follow no common curve, and one power law through them fits poorly. Choosing the model with the smallest total cost on the previous batch still lowers the total completion time by 7.4% relative to the most accurate model, in all 19 pairs of consecutive batches. The power law is needed only for the closed form within one architecture, where it still predicts the best model closely.

Beyond one machine, the revision also gives the exact price of latency on many identical machines. Under drift, when the estimate of the optimum is within a factor of 2, the loss is at most 1.53% on the traces.

We would also like to say briefly why we believe this paper is worth accepting. You saw the formalization as a necessary step, and we hope the revision shows that it also holds up in real systems. To our knowledge, the following points were not known before.

  • The time a prediction takes is a cost that no scheduling strategy can hide, and its exact price is known.
  • One number, computed from a trace and the per-job latency before any model is trained, tells how much choosing the most accurate model can cost, whatever the set of models.
  • The best model grows with the workload in a closed form, and a rough estimate of the workload is enough to use it.

If any part of the model still looks too idealized to you, could you tell us which one? We would be glad to answer it directly. Either way, thank you for helping us make this paper better.

Best regards, The authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to reviewers and AC

Dear Area Chair and Reviewers,

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

1. Contribution

Learning-augmented scheduling orders jobs by the predictions of a learned model. Earlier analyses treat these predictions as free. A more accurate model takes longer to run, and this wait is itself a scheduling cost. The paper asks which model to deploy.

  • The price of inference latency is exact. Running jobs during inference cannot hide a latency of τ\tau. The best worst-case loss is exactly (n−1)τ/2(n-1)\tau/2 for nn jobs.
  • Theory locates the best model. The total cost JJ has a unique best model complexity, and heavier workloads justify larger models.
  • One number says when the choice matters. κ\kappa needs only a trace and a per-job latency, before any model is trained. Choosing by accuracy alone loses up to the factor 1+κ1+\kappa, and never more (Theorem 4, Proposition 2).
  • Trained models confirm the theory. With 36 trained models on the Alibaba microservices trace, choosing by total cost lowers JJ by 7.4% ± 1.0% relative to the most accurate model, in 19 of 19 pairs of consecutive batches.
  • Place in the field. Algorithms with predictions are collected in the community resource ALPS. How much prediction an algorithm needs is a topic at ICLR (Sadek & Elias, 2024, and Guyot & Lassota, 2025). The paper asks this question when a prediction takes time.
  • What the community can build on. The framework needs only the error-response curve of a scheduler, so other learning-augmented schedulers fit. Algorithm 1 evaluates any trace and model class by total cost in place of accuracy. Two questions are open, a lower bound for online arrivals and the regret exponent across workloads. We hope that the question of how much accuracy is worth waiting for will be asked for other algorithms with predictions.

2. Responses to the reviews

  • Depth of the theory. Both main results are now exact, the price of latency and the price of ignoring latency. The price of latency is also exact on mm machines, for randomized algorithms and with two predictors.
  • Smooth model, real predictors. The selection compares measured costs and needs no curve. The 36 trained models follow no common curve, and the selection stays within 1.05% of the best model of each batch.
  • Scope of the inference model. Running jobs during inference, pipelining, parallel inference, per-job prediction and a fast predictor first each lower the latency term. The trade-off between accuracy and latency remains (Theorem 7, Appendices E.4 and E.6).
  • From theory to practice. ρA\rho_A is a proved bound and is not estimated. The predictor is chosen before a batch runs, and an estimate of OPT\mathrm{OPT} off by a factor of 2 costs at most 6.2%.
  • Scaling law. The law is tested on every batch of Azure and ATLAS, with constants fitted once and controlled predictors. The measured optimum is within a factor of 1.25 of the prediction in 179 of 197 and 72 of 72 batches.
  • Prior work. Jiang et al. (2025) show the phenomenon using simulated data. The paper explains the phenomenon with theorems and turns the observation into a selection rule. We also test the theorems in real-world trace.

3. Changes in the revision

  • Theory. Theorem 2 (b), Theorems 5 to 7 and Proposition 2 are new, and Proposition 1 holds for every factor (Sections 3.1, 3.4 and 3.5, Figure 2).
  • Experiments. Section 4 leads with trained models on the microservices trace (Figure 3) and tests the scaling law on every batch (Figure 4). Appendices E is new section for experiments.
  • Guidance. Section 4.3 has a paragraph "Lessons for practitioners", and Appendix F gives a step-by-step guide.

New content in the main text is in blue. The theorems of the submission stand, and the main text stays within the 10 pages allowed during the discussion.

We apologize for the late response. The reviews raised points that deserved full answers, and we took the time to prove the new results, to run the new experiments and to revise the paper with care. We sincerely thank the Area Chair and the reviewers for reading the responses and the revision, and we are glad to answer any further question. We would be grateful if the responses and the revision could be considered in the final assessment.

Best regards, The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.