Research map / Architectures and efficiency / RNNs and normalization
SkipPredict: When to Invest in Predictions for Scheduling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SkipPredict, a two-stage queueing policy that uses one-bit cheap predictions to split jobs into short (FCFS, priority) and long, then applies costly service-time predictions with SPRPT only to long jobs, and analyzes it under external and server-time prediction-cost models via SOAP.
Problem
Scheduling with predicted job sizes in M/G/1 queues usually assumes predictions are free; when predictions cost resources (external cost or server time), it is unclear when they are worth their cost and whether all jobs should be predicted.
Approach
Use cheap one-bit predictions to classify jobs and spend expensive service-time predictions only on predicted-long jobs, scheduling predicted-short jobs FCFS at higher priority and long jobs by SPRPT; derive mean response times with SOAP under two prediction-cost models.
Key results
- SkipPredict's advantage over SPRPT grows as the cost gap between expensive and cheap predictions increases (e.g., c2 = k*c1 with larger k).
- When prediction costs are close (k=1), SkipPredict is less useful and SPRPT may be better; under high load, expensive predictions become beneficial and SkipPredict yields the lowest cost in both exponential and Weibull simulations.
- For Weibull service times, SkipPredict and SPRPT costs are similar due to heavy tails, though SkipPredict still gains over SPRPT.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SkipPredict instead of FCFS, 1bit, or SPRPT | M/G/1 scheduling with exponential or Weibull service times · High arrival rates | total cost | Helped |
| Increase the expensive-prediction cost relative to the cheap-prediction cost (ablation) | SkipPredict · Exponential and Weibull service times | total cost | Helped |
| Use SkipPredict when cheap and expensive prediction costs are similar | SkipPredict · Exponential service times | total cost | Hurt |
| Invest in expensive service-time predictions | SkipPredict · Exponential and Weibull service times at high arrival rates | total cost | Helped |
| Use prediction-based scheduling at extremely high load | SkipPredict, SPRPT, and 1bit · Extremely high load | total cost | Hurt |
| Increase the short/long threshold T (ablation) | SkipPredict · Exponential and Weibull service times | total cost | Mixed |
| Use a larger T so fewer jobs receive expensive predictions (ablation) | SkipPredict · Large T, where most jobs are predicted short | total cost | Hurt |
| Replace SkipPredict with DelayPredict, which skips cheap predictions and delays expensive prediction until service reaches L | Single-queue scheduling · Cost gap between cheap and expensive predictions | total cost | Hurt |
| Replace SkipPredict with DelayPredict | Single-queue scheduling · Prediction costs are close | total cost | Helped |
| Increase the service limit L (ablation) | DelayPredict · Single-queue scheduling | total cost | Hurt |
| Use SkipPredict rather than SPRPT | Scheduling with Weibull service times · Weibull service times | total cost | Helped |
Surprising findings
- For heavy-tailed Weibull service times, the gain of SkipPredict over SPRPT is smaller because SPRPT is already effective for long jobs.
- Under extremely high load, prediction-based scheduling risks overflow so FCFS may be better.
Limitations
- Analysis assumes fixed (deterministic) prediction costs; random costs are only outlined theoretically.
- Simulations use simplified predictor models (the cheap predictor is derived from the uniform model by thresholding), not real ML predictors.
- Under extremely high load prediction-based policies risk instability, so FCFS may be preferable.
Experimental setup
Metrics: mean response time (cost) total cost including prediction cost
Baselines: FCFS SPRPT 1bit DelayPredict
Builds on: SOAP SPRPT 1bit advice scheduling algorithms with predictions
Closest papers by meaning
- Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret (NeurIPS 2026 · similarity 0.83)
- DON’T STOP ME NOW: EMBEDDING BASED SCHEDULING FOR LLMS (ICLR 2025 · similarity 0.82)
- Beyond Prediction: Tail-Aware Scheduling for LLM Inference (ICML 2026 · similarity 0.82)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.81)
- Learning-Augmented Priority Queues (NeurIPS 2024 · similarity 0.81)
- FastPERT: Towards Fast Microservice Application Latency Prediction via Structural Inductive Bias over PERT Networks (AAAI 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.