Contract Scheduling With Predictions

Spyros Angelopoulos, Shahin Kamali

Introduction

Anytime algorithms are a cornerstone of modern AI, providing a trade-off between computation time and solution quality. In domains such as medical diagnostics or autonomous vehicle motion planning, the ability to retrieve a valid result at any moment is critical. A standard technique to transform a "contract algorithm"—one requiring a pre-specified runtime—into an anytime algorithm is through contract scheduling. This involves executing the contract algorithm repeatedly with increasing time limits.

Historically, contract scheduling has been analyzed through a worst-case lens, assuming an adversarial interruption time. Under these conditions, an exponential schedule (typically doubling the runtime at each step) achieves an optimal acceleration ratio of 4. This ratio represents the factor by which the schedule's performance lags behind an algorithm with perfect knowledge of the deadline. However, in practice, we often possess noisy predictions about when an interruption might occur. This paper explores how to integrate these predictions to surpass the theoretical worst-case bounds while maintaining robustness against prediction errors.

Prediction Models

The authors investigate two primary models for incorporating external hints:

  1. Time-Based Predictions: The scheduler is provided with a predicted interruption time $\tau$. The actual interruption $T$ is assumed to lie within a window $[\tau/(1+\eta), \tau(1+\eta)]$, where $\eta$ represents the prediction error.
  2. Binary Query Predictions: The scheduler can pose $n$ binary questions regarding the interruption time (e.g., "Will the interruption occur before time $X$?"). The prediction is a bitstring of answers, where a fraction $p$ of the bits may be incorrect.

Algorithmic Framework

To leverage these predictions, the paper introduces schedules that incorporate a "hedging" or "buffer" parameter $p$:

  • Time Prediction Schedule ($X^*_{\tau(1-p)}$): This schedule shifts contract lengths to ensure a significant computation completes just before the predicted deadline, adjusted by a safety margin.
  • Robust Binary Schedule (Robust$_p$): To handle erroneous query answers, the authors design a schedule that avoids the fragility of standard binary search. By selecting schedule indices in a cyclic order "close and above" the predicted index, the algorithm can tolerate a specific percentage of bit flips without catastrophic failure.

Key Insights: The Consistency-Robustness Tradeoff

A central theme of the work is the Consistency-Robustness tradeoff. A "consistent" schedule performs exceptionally well when predictions are accurate but may fail significantly if they are wrong. Conversely, a "robust" schedule maintains a safe performance floor regardless of prediction quality. The authors demonstrate that the most effective schedules are Pareto-efficient, balancing these two objectives.

Interestingly, performance in contract scheduling is non-monotonic relative to error. Due to the discrete nature of contract completions, a larger error might coincidentally align a contract's end with the interruption, while a smaller error might cause the interruption to occur just before a contract finishes, leading to a spike in the acceleration ratio. Furthermore, the authors establish a formal link between contract scheduling and "online bidding," allowing them to leverage existing algorithmic tools from that field to prove their schedules are optimal.

Experimental Evaluation

The proposed methods were evaluated using synthetic simulations where interruption times followed a truncated normal distribution and prediction errors were modeled as noise or bit flips.

Time Predictions

As illustrated in the evaluation of time-based predictions, the "H-aware" schedule—which accounts for the maximum possible error—provides a remarkably stable acceleration ratio.

Acceleration ratios for time predictions showing the stability of the H-aware schedule.

While the baseline exponential schedule frequently spikes to an acceleration ratio of 4.0, the prediction-aware schedules maintain ratios closer to 2.23, significantly improving efficiency.

Binary Queries

For the binary query model, the Robust$_p$ schedules exhibit a characteristic "sawtooth" pattern. Despite the fluctuations, these schedules consistently outperform the baseline.

Acceleration ratios for binary query predictions exhibiting the sawtooth performance pattern.

Empirical tests showed that the Robust$_p$ approach yielded improvements in 80% to 94% of cases, depending on the error rate $p$, demonstrating that even noisy binary hints provide a massive advantage over standard methods.

Conclusion

By moving beyond worst-case analysis, this work provides a robust framework for contract scheduling with predictions. The results demonstrate that even highly noisy hints can be leveraged to significantly reduce the acceleration ratio. Future research directions include extending these models to multi-processor environments and exploring adversarial noise models for binary queries.

Summary updated

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.
BibTeX
@inproceedings{angelopoulos2021contract,
  author = {Spyros Angelopoulos and Shahin Kamali},
  title = {{Contract Scheduling With Predictions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17394},
}
Figure