Abstract
Contract scheduling is a general technique that allows to design a system with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has largely assumed that the interruption is a worst-case deadline that is unknown to the scheduler. In this work, we study the setting in which there is a potentially erroneous prediction concerning the interruption. Specifically, we consider the setting in which the prediction describes the time that the interruption occurs, as well as the setting in which the prediction is obtained as a response to a single or multiple binary queries. For both settings, we investigate tradeoffs between the robustness (i.e., the worst-case performance assuming adversarial prediction) and the consistency (i.e, the performance assuming that the prediction is error-free), both from the side of positive and negative results.
Introduction
In the field of artificial intelligence and flexible computation, "anytime algorithms" are highly valued for their ability to provide a valid output even if interrupted, with the quality of the result improving as more computation time is granted. However, many powerful algorithms belong to a more restrictive class known as contract algorithms. These algorithms require a pre-allocated time budget (a "contract") to produce any meaningful output. If a contract algorithm is interrupted even a fraction of a second before its allocated time expires, it typically yields no usable result.
To bridge the gap between contract algorithms and unpredictable real-world environments, researchers use scheduling strategies. By running a sequence of contracts with increasing lengths, a system can ensure that some result is always available, regardless of when an interruption occurs. This paper explores how to enhance these schedules using potentially noisy machine learning predictions about the timing of interruptions.
The Challenge of Contract Scheduling
The standard approach to making contract algorithms robust is to use an exponential schedule (e.g., executing contracts of lengths 1, 2, 4, 8, etc.). The efficiency of such a schedule is measured by the acceleration ratio: the factor by which a processor would need to be sped up to match the performance of an ideal scheduler that knew the interruption time in advance.
Traditionally, this problem is modeled as a game against a worst-case adversary. However, modern systems often have access to predictive signals—whether from historical data, ML models, or domain experts—regarding when an interruption might occur. The core challenge addressed in this research is how to integrate these untrusted predictions to improve performance (consistency) without sacrificing safety if the predictions prove to be wildly inaccurate (robustness).
Scheduling with Untrusted Predictions
The authors evaluate their framework through two primary prediction modalities:
1. Interruption Time Predictions
In this setting, the scheduler receives a specific predicted time $\tau$ for the interruption, subject to an unknown error $\eta$. A significant hurdle here is the non-monotonicity of error. Unlike many scheduling problems where a small error leads to a small performance hit, a contract schedule can fail catastrophically if an interruption occurs just moments before a large contract completes.
To mitigate this, the authors propose a parameterized schedule, $X_{\tau(1-p)}^*$. This strategy introduces a "buffer" $p$, intentionally aiming to complete the largest contracts slightly before the predicted deadline. This buffer allows the system to absorb small negative errors where the interruption arrives earlier than expected.
2. Binary Query Predictions
Alternatively, the system may receive predictions as answers to $n$ binary queries (e.g., "Will the interruption occur after time $T$?"). To handle the possibility of incorrect answers (noisy bits), the authors developed the $Robust_p$ family of schedules. This method utilizes a cyclic ordering trick to select from $n$ shifted exponential schedules, providing fault tolerance even if a fraction $p$ of the query answers are erroneous.
Key Insights and Theoretical Bounds
The research establishes several critical theoretical limits for prediction-aware scheduling:
- Information-Theoretic Limits: The authors prove that with $n$ binary queries, perfect consistency is impossible. If a scheduler maintains the optimal worst-case robustness (an acceleration ratio of 4), the best achievable consistency is $2^{1+1/n}$.
- The Necessity of Hedging: Because of the non-monotonic nature of the problem, the optimal strategy is never to trust a prediction fully. A "hedging" approach that balances the predicted time against the standard exponential growth is required to maintain robustness.
Experimental Results
The proposed schedules were tested using synthetic simulations, comparing them against the standard no-prediction exponential baseline. The results demonstrated significant performance gains:
- Continuous Predictions: With a 10% error bound, the prediction-aware schedule outperformed the baseline in 88.71% of simulated interruptions.
- Binary Predictions: Using 100 queries with a 10% error rate, the $Robust_{0.1}$ schedule surpassed the baseline 94.25% of the time.
These results confirm that even noisy or partially incorrect predictions can be leveraged to significantly reduce the acceleration ratio in practice.
Conclusion and Future Work
This work provides a robust framework for integrating predictions into contract scheduling, offering Pareto-optimal tradeoffs between consistency and robustness. While no prediction-aware schedule can outperform a lucky baseline in every single instance, the strategies presented here offer a mathematically sound way to improve average-case performance while maintaining strict worst-case guarantees.
Future research directions include extending these techniques to multi-processor environments and exploring the relationship between contract scheduling and "online searching on the line" problems, where a searcher must find a target using noisy hints.
Summary updated