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

Jun 16, 2026

Beyond Prediction: Tail-Aware Scheduling for LLM Inference

LLM serving exhibits extreme length variability, making size-based scheduling difficult in practice. Recent LLM schedulers approximate SJF/SRPT using predicted decode lengths or ranks and primarily report mean-centric metrics such as TTFT and TBT. We show that these prediction-driven policies can be fragile under distribution shifts, bursty arrivals, and GPU memory pressure, while offering limited control over the tail latency (P90-P99) that dominates user experience, even with perfect decode-length knowledge. We introduce a distribution-aware, prediction-free scheduling framework that replaces explicit length prediction with soft priority boosting driven by lightweight statistical signals. Our design co-optimizes scheduling and cache-aware preemption to account for memory-coupled decode dynamics across workload mixes. Evaluated on production and open-source traces, our method reduces P99 TTLT by up to 35-50% relative to SRPT with perfect length knowledge and reduces TTFT by 34-47% across workloads, including reasoning-heavy and chat-heavy tasks. These results demonstrate a robust alternative for optimizing tail latency in online LLM serving.
May 30, 2025

TIP-Search: Time-Predictable Inference Scheduling for Market Prediction under Uncertain Load

Real-time market prediction services need correct predictions before a decision deadline; a correct prediction delivered late is not usable. TIP-Search studies time-predictable inference scheduling over fixed market predictors under uncertain load. It filters conformal latency-quantile feasible models, dispatches over finite workers, and uses shielded constrained online experts to trade accuracy, queue pressure, and deadline risk. On the optimized deployable pool, TIP-Search reaches 0.994 raw accuracy and 0.991 timely accuracy. On official TLOB FI-2010 h=10, TIP-Search++ raises timely accuracy from 0.156 to 0.239 and deadline satisfaction from 0.391 to 0.962. In matched h10 profiled systems replay, OCO-ACPO reaches 0.303 timely accuracy and 0.951 deadline satisfaction, with paired gains over RAMSIS/SneakPeek/utility-style comparators of +0.00285+0.00285 timely accuracy (p=0.0118p=0.0118) and +0.0146+0.0146 deadline satisfaction (p=1.5×10−5p=1.5{\times}10^{-5}). SA-OCO-ACPO improves timely/deadline service by 0.188--0.417 over CPO under nonstationary stress. The claim is a systems scheduling result, not a broad LOB classifier leaderboard.
May 22, 2026

Learning-Augmented Online Scheduling with Parsimonious Preemption

Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, ``blind'' preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include O(1)O(1)-competitive algorithms for single and unrelated parallel machines with only O(1)O(1) preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.