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

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 $\tau$ contributes an unavoidable $\Theta (n\tau )$ term to the objective via a tight lower bound for deterministic algorithms and establish that the cost-aware objective has a unique optimal complexity ${\theta }^{\star }$ following a power-law scaling: heavier workloads justify more complex predictors. Ignoring prediction cost incurs a non-vanishing performance ratio of $1+\kappa$, where $\kappa =n\tau /\mathrm{OPT}$. Experiments on the ATLAS GPU-cluster trace, the Azure Functions serverless trace, and the Alibaba microservices trace confirm the theoretical results.