cs.PFNov 6, 2026

Sparse Predict and Demote: Optimal Scheduling with Minimal Size Advice

Authors: Chengyi Liu, Thodoris Lykouris, Junxuan Shen, Adam Wierman

Organizations: California Institute of Technology · Massachusetts Institute of Technology

Abstract

Knowledge of job sizes is crucial for optimizing the mean response time in single-server scheduling. However, predictions of job sizes are typically inexact and may be costly to obtain. Thus, a long-standing research question is: what is the minimal information about job sizes required to obtain near-optimal mean response time? We introduce a novel policy, Sparse Predict and Demote (SPD), and prove that it achieves order-optimal mean response time in heavy traffic while requiring only one-bit job-size predictions for a vanishing fraction of arrivals. SPD achieves heavy-traffic order-optimality even in situations when predictions are (i) inexact up to any fixed multiplicative error bound, and (ii) costly, i.e., the server is used to compute predictions and is thus unavailable to serve jobs while processing prediction queries. Finally, we use numerical experiments to illustrate that SPD maintains near-optimal performance beyond the heavy-traffic regime.

Figures & tables

Explore similar work

CardsList
  1. Beyond Prediction: Tail-Aware Scheduling for LLM Inference

    Jun 16, 2026Yueying Li, Yuanfan Chen, Jiayang Chen +6LLM ServingInference-Time Optimization

  2. Learning-Augmented Online Scheduling with Parsimonious Preemption

    May 22, 2026Mugen Blue, Sungjin Im, Alexander LindermayrCombinatorial OptimizationLearning-Augmented Algorithms