SkipPredict: When to Invest in Predictions for Scheduling

Rana Shahout, Michael Mitzenmacher

Introduction

In modern queueing theory and systems design, the ability to predict a job's service time (its "size") is a powerful lever for optimization. Policies like Shortest Remaining Processing Time (SRPT) are known to be optimal for minimizing mean response time, but they require perfect knowledge of job sizes. Recently, the field of "algorithms with predictions" has sought to bridge this gap by using machine learning models to provide size estimates. However, a significant gap remains between theory and practice: most research assumes these predictions are provided for free.

In reality, generating a prediction incurs a cost—whether it is the financial cost of an API call, the latency of a network request, or the CPU cycles required for model inference. This paper introduces SkipPredict, a scheduling policy designed to navigate the trade-off between the benefits of informed scheduling and the overhead of obtaining that information.

The Cost of Information

The authors identify a fundamental problem: if a job is extremely short, the time or resources spent calculating its predicted size might exceed the time required to simply execute the job. To address this, the paper evaluates two distinct cost models:

  1. External Cost Model: Predictions have a fixed overhead (monetary or time-based) that adds to a job's total response time but does not consume server capacity.
  2. Server Time Cost Model: Predictions are treated as tasks themselves. They must be scheduled on the same server as the jobs, meaning every prediction made reduces the total processing power available for actual work.

The SkipPredict Policy

SkipPredict is a two-stage scheduling algorithm designed to act as a filter, ensuring that expensive computational resources are only invested where they provide the most value.

Stage 1: The Cheap Filter

Every arriving job first receives a "cheap" one-bit prediction. This could be a lightweight classifier or a simple heuristic that labels a job as either "short" or "long." Jobs identified as short are prioritized and executed immediately using a First-Come, First-Served (FCFS) policy. These jobs "skip" the expensive prediction phase entirely.

Stage 2: Selective Investment

Jobs labeled as "long" are sent for an "expensive" detailed prediction to estimate their exact service time. Once this prediction is obtained, these jobs are scheduled using a Shortest Predicted Remaining Processing Time (SPRPT) policy. By only predicting the sizes of long jobs, the system avoids wasting resources on tasks that would not significantly benefit from SRPT-style optimization.

Methodology and Analysis

To analyze the performance of SkipPredict, the authors utilize the SOAP (Schedule Ordered by Age-based Priority) framework. This mathematical tool allows for the derivation of precise formulas for mean response times across complex, multi-stage scheduling policies.

The study employs synthetic simulations to explore various system behaviors, using Exponential (light-tailed) and Weibull (heavy-tailed) service time distributions. To ensure robustness, the authors also simulate various levels of prediction error, ranging from perfect advice to models with significant uniform or exponential noise.

Key Insights

The Importance of the "Cost Gap"

SkipPredict is most effective when there is a significant disparity between the cost of the initial 1-bit filter and the detailed service-time prediction. When the detailed prediction is expensive, the filtering mechanism prevents the system from becoming bogged down by the overhead of its own optimization logic.

Stability in High-Load Environments

In systems operating near capacity (e.g., load $\lambda \approx 0.9$), the Server Time Cost model reveals a critical risk: if every job requires an expensive prediction, the server can become unstable and overloaded. SkipPredict maintains system stability by drastically reducing the total number of expensive predictions, preserving server cycles for job execution.

Optimal Thresholding

A central finding is the existence of an optimal threshold ($T$) for classifying jobs. If the threshold for a "short" job is too low, the system over-invests in predictions; if it is too high, the system loses the efficiency gains of SRPT. The paper demonstrates that SkipPredict consistently outperforms standard FCFS and "predict-everything" (SPRPT) policies when these costs are non-trivial.

Conclusion and Future Directions

SkipPredict represents a paradigm shift in learning-augmented algorithms, moving from the question of "how to use advice" to "how to decide if advice is worth the investment." While the current analysis focuses on M/G/1 queues with fixed costs, it opens the door for future research into multi-server systems, bursty traffic patterns, and load-based prediction strategies—where the system might only "buy" a prediction if the current queue length justifies the expense.

Summary updated

BibTeX
@inproceedings{shahout2024skippredict,
  author = {Rana Shahout and Michael Mitzenmacher},
  title = {{SkipPredict: When to Invest in Predictions for Scheduling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=kVuw8vzsqZ},
}
Figure