- Experimental coverage is way too limited for the breadth of the claims
Section 5 evaluates synthetic multiplicative prediction noise, with the interruption time fixed to one by scaling invariance. While fixing the interruption time is justified within the model, the limitation is that the evaluation explores only a narrow family of prediction errors and a small collection of parameter settings.
Furthermore, there is no evaluation on an implemented interruptible application, even though the motivating examples involving planning, diagnosis, and LLM reasoning. While a theoretical paper need not to demonstrate all such applications, it is still necessary to provide some evidence connecting contract-length improvements to meaningful output quality, or measuring practical scheduling overhead and finite-startup effects.
More importantly, the history-based smoothing estimator from Theorem 9 is not evaluated at all. The experiments therefore do not validate whether this estimator learns useful parameters, improves on fixed smoothing, or approaches the best fixed parameter in hindsight. This is a substantial omission because adaptive calibration is presented as a distinct contribution.
Finally, the evaluation lacks biased and asymmetric prediction errors, uncertainty estimates, and a convergence check for the inner Monte Carlo estimation. These are particularly important because the analysis explicitly distinguishes overprediction from underprediction, and the reported metric takes the reciprocal of an estimated expected contract length.
- Comparisons do not adequately establish the value of the complete approach
The paper compares with an adapted randomized bidding construction and, at robustness four, deterministic consistency-oriented schedules. While they are relevant baselines, they do not sufficiently isolate which components are responsible for the observed improvements.
The main noise-sweep experiments should include unsmoothed CF, a wider range of fixed smoothing parameters, and the adaptive estimator. An actual-cost-optimal fixed smoothing parameter selected in hindsight would provide an informative reference for the proposed calibration method. Without such comparisons, the empirical advantage of adaptive smoothing remains unknown, and the practical tradeoff introduced by smoothing is sufficiently characterized.
The related-work discussion also omits Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms by Angelopoulos, Dürr, and Melidi (arXiv:2501.17701). Section 5 and Appendix C of that work explicitly study prediction-augmented contract scheduling, optimizing distance-based and CVaR criteria within deterministic 4-robust doubling schedules. This does not subsume the present randomized results. That said, it is directly relevant to evaluating performance beyond consistency and robustness and to selecting among prediction-dependent schedules.
This paper should also explain this distinction and consider an appropriately matched comparison at robustness four. Any empirical comparison must account for different information requirements and objectives of the approaches. That said, I am not requesting a comparison that gives one method privileged distributional information.
- The presentation makes the main guarantees unnecessarily difficult to assess
The reader must navigate several constructions and different levels of certainty: the explicit piecewise-exponential schedule, the conditional DDE construction, the smoothed schedule, and the history-based estimator. Their applicability and dependencies are spread across the main text and appendix rather than summarized in one place.
Specifically, the distinction between a proven guarantee and numerical evidence is essential. Theorem 7 assumes feasibility, while Appendix B.7 provides finite-horizon numerical evidence for selected parameters, but not an infinite-horizon certificate over the entire low-robustness regime. The introduction's description of computer-assisted verification seems obscuring this distinction.
The paper would benefit from a compact table listing each construction, its parameter range, prediction assumptions, performance guarantee, and proof status. Explicit pseudocode for generating contracts from a prediction and for updating the smoothing parameter would also make the algorithmic contribution substantially easier to understand and reproduce.
Finally, Theorem 9 benchmarks the estimator against the minimum of a surrogate upper bound, not against the best achievable actual expected cost within the smoothing family. This limitation should be stated prominently rather than left for the reader to infer from the formulas.
- The broader significance is not sufficiently validated beyond the mathematical results
The matching agnostic lower bound is a legitimate contribution. However, it primarily confirms the optimality of a previously-known randomized guarantee; it does not itself provide a new agnostic algorithm or demonstrate improved application performance.
The stronger case for this submission therefore rests on the new prediction-augmented construction and adaptive smoothing. However, their practical value is not convincingly demonstrated: the adaptive method is not tested and its theorem optimizes a potentially loose surrogate, and part of the low-robustness construction remains conditional.
Bring the above all together, the limitations leave a gap between the established mathematical advances and the paper's broader claims about significantly improved interruptible systems. I think more focused empirical evidences and clearer positioning are necessary to make the paper more convincing.
Response
We thank the reviewer for their careful reading of our paper and their constructive feedback. Below we respond to the questions asked.
Question 1: Thank you for these suggestions, which we implemented in the revision. Specifically:
In Theorem 2, the log-uniform distribution is motivated by the scale invariance of contract scheduling: scaling all contract lengths and interruption times by the same factor does not affect the acceleration ratio. A log-uniform distribution has density proportional to 1/t , so every interval [a,ca] has the same probability, independently of a, provided it lies within the support. In particular, this prevents any schedule from gaining an advantage simply by choosing large contract lengths, since the distribution assigns equal probability to interruption times at increasingly large multiplicative scales.
Theorem 3 relies on a key inequality which expresses a fundamental constraint on contract schedules: the expected length of the longest completed contract at a given interruption time cannot be optimized independently of the performance at earlier interruption times. More precisely, for any schedule X and interruption time T, we establish
TE[ℓ(X,T)]+∫T/2Tt2E[ℓ(X,t)]dt≤1.
The two terms capture consistency and robustness, respectively. Indeed, setting T=T, the first term equals 1/cons(X). On the other hand, R-robustness requires E[ℓ(X,t)]≥t/R for every interruption time t, implying that the integral is at least
R1∫T/2Ttdt=Rln2.
Consequently, 1/cons(X) + ln 2 R ≤ 1, which establishes the lower bound on consistency. In other words, the inequality quantifies how guaranteeing better performance at earlier interruption times limits the performance achievable when the prediction is correct.
In Theorem 6, the definition of the transform CF was already given in the statement of Proposition 5. Nevertheless, we agree with the reviewer that it could be presented more clearly. We have therefore moved the definition immediately before Proposition 5, making it easier to locate.
Question 2: We thank the reviewer for this suggestion. The cited works consider richer prediction models in which the oracle provides additional information, such as uncertainty estimates or calibrated predictions. Our approach is somewhat different, in that we use historical point predictions (i.e., single-valued predictions on the interruption time) so as to adjust the smoothing parameter accordingly, without requiring any additional information from the oracle. Incorporating prediction-specific uncertainty information into our framework is a natural possibility. For instance, one could consider selecting the smoothing parameter based on both historical prediction errors and uncertainty information associated with the current prediction. This combination could potentially improve average-case performance.