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:
- 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.
- 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.
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.
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