# SkipPredict: When to Invest in Predictions for Scheduling

arXiv: https://arxiv.org/abs/2402.03564 · HTML: https://mlsanity.com/paper/2402.03564/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 5 Feb 2024.

## Builds on (most cited first, 8 of 8)

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Distortion-Oblivious Algorithms for Minimizing Flow Time](https://mlsanity.com/paper/2109.08424/) (2021)
- [Uniform Bounds for Scheduling with Job Size Estimates](https://mlsanity.com/paper/2110.00633/) (2021)
- [Queues with Small Advice](https://mlsanity.com/paper/2006.15463/) (2020)
- [PSBS: Practical Size-Based Scheduling](https://mlsanity.com/paper/1410.6122/) (2014)
- [Scheduling With Inexact Job Sizes: The Merits of Shortest Processing Time First](https://mlsanity.com/paper/1907.04824/) (2019)

## Built on by (most cited first, 3 of 3)

- [Don't Stop Me Now: Embedding Based Scheduling for LLMs](https://mlsanity.com/paper/2410.01035/) (2024)
- [Queueing, Predictions, and LLMs: Challenges and Open Problems](https://mlsanity.com/paper/2503.07545/) (2025)
- [Learning-augmented smooth integer programs with PAC-learnable oracles](https://mlsanity.com/paper/2602.02505/) (2026)

## Abstract (arXiv)

In light of 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. In particular, 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 based on their prediction requirements. 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 latter, SkipPredict applies a second round of more detailed "expensive predictions" to approximate Shortest Remaining Processing Time for these jobs. Our analysis takes into account the cost of prediction. We examine the effect of this cost for two distinct models. In the external cost model, predictions are generated by some 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.