acceptodds
Under review as a conference paper at ICLR 2027

Harnessing Randomization in Learning-Augmented Contract Scheduling

Abstract

Contract scheduling is a fundamental framework for systems that trade computation time for solution quality when the available running time is unknown. While deterministic contract schedules have been extensively studied, the benefits of randomization remain largely unexplored. In this work, we study randomized contract scheduling both in the classical, agnostic setting and in the presence of predictions. First, we settle the agnostic setting by proving a tight lower bound on the best-possible performance of a randomized schedule. We then address learning-augmented contract scheduling, where the scheduler receives a prediction of the interruption time. We characterize the consistency–robustness tradeoff by providing a lower bound and a randomized schedule with nearly matching guarantees. We further mitigate the brittleness inherent in consistency-optimized algorithms via smoothing, obtaining provably gradual degradation under prediction error at only a small cost in consistency. Finally, we give the first analysis of a general sequential learning game that uses historical prediction data to calibrate trust in subsequent predictions, and determine the appropriate smoothness. Our theoretical and experimental results demonstrate that randomization can significantly improve the performance of interruptible systems based on contract scheduling.

Primary area:
optimization
Keywords:
Learning-augmented algorithms, randomized algorithms, anytime algorithms, contract scheduling, beyond worst-case analysis

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_EtGoOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies randomized contract scheduling—a methodology used to make algorithms “interruptible” by running them repeatedly for increasing durations—across multiple settings. In the agnostic setting (i.e., when there is no knowledge of when an interruption may occur), the authors characterize the optimal acceleration ratio achievable by a randomized contract schedule by proving a lower bound matching a previously-known upper bound. They then explore a learning-augmented setting in which the scheduler receives a predicted interruption time. In this setting, the authors characterize the consistency/robustness tradeoff of randomized contract schedules by proving analytic upper and lower bounds on the Pareto frontier where possible, and supplementing the remaining regions with numerical results. Because the resulting contract schedules are brittle to prediction errors, they also consider a smoothing mechanism that produces schedules whose performance degrades gracefully as prediction quality decreases. Finally, under i.i.d. assumptions they propose a method for selecting smoothing parameters from historical prediction errors.

Critical strengths

• The tight lower bound provided for the agnostic setting is a nice result that settles the optimality of a previous construction.

• The paper establishes close upper and lower bounds on the consistency/robustness frontier for randomized schedules over a substantial range of robustness values, demonstrating a significant improvement over deterministic schedules.

Critical weaknesses

Several proof sketches in the main body would benefit from more explanation of the central ideas. For example, the sketch of Theorem 2 does not explain what motivates a log-uniform interruption time distribution, the sketch of Theorem 3 lacks intuition for how the key inequality captures consistency/robustness, and the sketch of Theorem 6 appeals to a quantity CF~\widetilde{CF} that is not defined explicitly in the main body.

Questions for authors

• Could the authors expand the intuition behind the core proof sketches? See the weaknesses above for concrete suggestions.

• The adaptive smoothing procedure in Theorem 9 selects a global smoothing parameter based on historical prediction errors. Could incorporating prediction-specific uncertainty information further improve average-case performance? Potentially of interest are papers such as Sun et al. (ICML 2024) and Shen et al. (ICML 2025).

1 comment

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:

  1. 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/t1/t , so every interval [a,ca][a,ca] has the same probability, independently of aa, 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.

  2. 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 XX and interruption time TT, we establish

    E[ℓ(X,T)]T+∫T/2TE[ℓ(X,t)]t2 dt≤1.\frac{\mathbb{E}[\ell(X,T)]}{T} + \int_{T/2}^{T} \frac{\mathbb{E}[\ell(X,t)]}{t^2}\,dt \le 1.

    The two terms capture consistency and robustness, respectively. Indeed, setting T=T^T=\widehat T, the first term equals 1/cons⁡(X)1/\operatorname{cons}(X). On the other hand, RR-robustness requires E[ℓ(X,t)]≥t/R\mathbb{E}[\ell(X,t)]\ge t/R for every interruption time tt, implying that the integral is at least

    1R∫T^/2T^dtt=ln⁡2R.\frac1R \int_{\widehat T/2}^{\widehat T}\frac{dt}{t}=\frac{\ln 2}{R}.

    Consequently, 1/cons⁡(X)1/\operatorname{cons}(X) + ln 2 RR ≤\le 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.

  3. In Theorem 6, the definition of the transform CF~\widetilde{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.

Reviewer_D5NgOpenReview ↗
Rating
3
Confidence
2(+1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to schedule repeated runs of a contract algorithm when the interruption time is unknown, with and without predictions. It proves that an existing randomized strategy is optimal without predictions and develops new randomized schedules that use predictions. It also introduces prediction smoothing to reduce sensitivity to errors and proposes learning the smoothing level from historical errors.

Critical strengths
  1. The paper establishes a matching lower bound, showing that an existing randomized strategy achieves the best possible performance without predictions.

  2. The proposed prediction-based schedules have explicit performance guarantees that approach the lower bound over part of the parameter range.

  3. The smoothness analysis explains how performance degrades with prediction errors and quantifies the cost of reducing this sensitivity.

Critical weaknesses
  1. Applications such as LLM reasoning remain largely motivational; please provide a concrete example explaining why repeated runs are needed instead of continuing previous computation.

  2. When R is close to 2.455, the bounds remain far apart, and feasibility is supported numerically. Can you please clarify these limits when claiming near-optimality?

  3. The evaluation measures completed contract lengths. Please explain how improvements translate into actual solution quality and reliability in individual runs.

  4. The history-based smoothing method is not evaluated experimentally. Will you compare it with fixed smoothing parameters to show whether adaptation improves performance?

Questions for authors

I recommend Weak Accept because the paper provides substantial theoretical analysis, is well written, and is clearly organized. My confidence is low, as I am less familiar with contract scheduling and some of the proof techniques used in this paper.

However, if any concerns listed in the Weaknesses can be addressed, it could further strengthen the paper.

2 comments

We thank the reviewer for their careful reading of our paper and their constructive feedback. Below we respond to the questions asked.

Question 1\textbf{Question 1}: The connection to LLM reasoning is motivated by the broader problem of allocating computational resources to reasoning procedures, which also motivated the original work on contract scheduling, and bounded-resource reasoning, more generally (Russell and Zilberstein, 1991, 1996). Recent work on test-time computation has shown the importance of computational budget allocation in LLM reasoning (e.g., Snell et al., 2025). We agree that, when a computation can be resumed, restarting it from scratch may not be desirable. However, there are related sequential scheduling models that allow computations to be suspended and resumed, particularly in the multi-problem setting (Angelopoulos, 2015). Thus, we view LLM reasoning as a possible connection to this broader family of resource-allocation problems, rather than a direct, clean-cut application of the specific contract scheduling model. Since establishing such a connection is beyond the scope of this work, we will remove the reference to LLM inference from the paper.

[Charlie Victor Snell, Jaehoon Lee, Kelvin Xu and Aviral Kumar. Scaling LLM Test-Time Compute Optimally Can be More Effective than Scaling Parameters for Reasoning. ICLR 2025]

Question 2\textbf{Question 2}: We refer the reviewer to Figure 1, which compares our lower and upper bounds on the consistency--robustness tradeoff. The figure illustrates the extent to which our schedules approach the theoretical lower bound across different robustness values. For the entire regime R≥2.65R\ge 2.65, the upper bound is established analytically (Theorem 6), whereas for R∈[2.455,2.65)R\in[2.455,2.65), the guarantee is supported computationally. Note that RR can never take values less than 2.455, as we showed in Theorem 2. Thus, our near-optimality claim concerns the proximity of the achievable consistency to the lower bound, rather than an exact characterization of the optimal tradeoff.

Question 3\textbf{Question 3}: If we understand the question correctly, the reviewer is asking how evaluating schedules in terms of completed contract lengths relates to their actual performance. To address this, it is useful to recall the interpretation of the acceleration ratio. As its name suggests, the acceleration ratio has a natural interpretation in terms of processor speedup: for deterministic schedules, speeding up the processor by a factor equal to the acceleration ratio allows an interruptible schedule to complete a contract at least as long as one completed by a system that knows the interruption time in advance. This interpretation, first discussed in (Russell and Zilberstein 1991) extends to randomized schedules in terms of the expected length of the longest completed contract. Equivalently, this implies that the sped-up schedule is at least as efficient as any system that knows the exact interruption time ahead of its execution. This framework thus provides a meaningful, application-independent relationship between processor speedup and interruptible

Question 4\textbf{Question 4}: Thank you for this suggestion. In the revised experiments (Section 5), we now evaluate the adaptive smoothing algorithm CFρ^CF_{\hat{\rho}}, where the smoothing parameter is learned from a historical dataset (samples). We compare its performance against the fixed smoothing parameters ρ∈0.3,0.9\rho \in \\{0.3, 0.9\\}, as well as the best parameter in hindsight, ρ^h\hat{\rho}_h. The latter is chosen with knowledge of the joint distribution PP of predictions and interruption times, and therefore provides a benchmark for assessing the effectiveness of adaptive smoothing. Namely, ρh=arg⁡min⁡ρEP[nc⁡(CFρ(T^),T)].\rho_h=\arg\min_{\rho}\mathbb{E}_{P}\left[\operatorname{nc}(\mathrm{CF}{\rho}(\widehat T),T)\right].

The results (Figure 2) show that the adaptive algorithm CFρ^CF_{\hat{\rho}} achieves empirical acceleration ratios very close to those of the best fixed smoothing parameter in hindsight, CFρhCF_{\rho_h}. Moreover, it substantially outperforms the unsmoothed algorithm CF\mathrm{CF} in the challenging overprediction regime, while smoothing offers less benefit with perfect predictions or predominantly underpredicted interruption times, as expected from the theoretical analysis. It also outperforms the bidding-based baselines AS and AS$_{\rho}$, particularly at low and moderate prediction-error levels. These results demonstrate the effectiveness of learning the smoothing parameter from historical data, without requiring knowledge of the underlying distribution.

Thank you for the reply. After reading the new explanation and the evidence, I feel more confident in this work.

I hope this theoretical work can provide valuable insights for designing new algorithms to solve real contract scheduling problems. Perhaps discuss this in the article.

I will keep the current score but raise my confidence to 2.

Reviewer_26EqOpenReview ↗
Rating
4(+1)
Confidence
2(−1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies randomized and learning-augmented algorithms for contract scheduling. In contract scheduling, there is a hidden interruption time TT that is unknown to the scheduler. The scheduler's goal is to complete a contract of maximum length before the hidden interruption time TT. More precisely, the normalised objective is to minimize the ratio between TT and the longest completed contract before TT. If TT was known to the scheduler, the solution would be to schedule one contract from time 00 to time TT for an objective value of 11. Since TT is not known, the scheduler specifies an increasing sequence XX of contract durations that are scheduled after each other. The goal becomes to minimize the supremum over TT of the ratio between TT and the longest contract completed before TT, also called the acceleration ratio. In the deterministic setting, geometric increasing contract duration achieve the best-possible acceleration ratio of 44.

As a first main result, the authors give a randomized lower bound of 2.4552.455 matching the upper bound by Angelopoulos, 2015. This settles the question for the best randomized acceleration ratio. The proof exploits Yao's theorem and a cleverly chosen distribution of interruption times TT.

Afterwards, the authors move to the learning-augmented setting, where the scheduler has access to a prediction T^\hat{T} of TT and the goal is to improve the acceleration ratio when TT is close to T^\hat{T} (consistency) while at the same time maintaining robustness against arbitrary TT. For deterministic algorithms, the optimal consistency and robustness tradeoff has already been fully characterised by Angelopoulus and Kamali, 2023. Here, the authors give a nearly tight trade-off for randomized algorithms. The main result is the upper bound which is based on contract functions that are a representation of certain contract schedules, inspired by bidding function in online bidding. Finding the best-possible contract function can be modelled as a continuous optimisation problem. The authors characterise the optimal solution to this problem for different robustness ranges. If the robustness is at least 2.652.65, they manage to obtain a consistency that nearly matches their lower bound. For the case where the robustness is smaller, they only show a nearly tight bound under the assumption that their contract function is indeed feasible. They give computational evidence that the contract function is indeed feasible but no analytical proof.

Finally, the authors address the brittleness of their algorithm. Brittleness refers to the phenomenon that algorithms with the best-possible consistency and robustness trade-off often don't have a good guarantee as soon as the prediction is slightly off. To address this, the authors adjust a smoothing framework from online bidding. The framework can be used to make algorithms less brittle at a small cost in the consistency,

Critical strengths
  • The paper advances the state-of-the-art for the online contract scheduling problem. The question of the best-possible randomized acceleration factor is completely settled, and the randomized consistency and robustness trade-off is shown to be better than the deterministic one. The latter proves that randomisation indeed helps for designing learning-augmented algorithm for contract scheduling. Both results fill gaps in the existing literature.
  • The technical contributions seem non-trivial. They build on existing approaches from online bidding, but they also seem to require significant additional care and work in the analysis.
Critical weaknesses
  • The trade-off bounds are not completely tight, and partially rely on computer-aided computations.
  • The major ideas of most results seem to be heavily inspired by existing work on online bidding. They do require additional work (as mentioned under strength), but the technical novelty is still somewhat limited.
Questions for authors

Can you highlight the main new technical ideas that you use in order to adjust the ideas from online bidding to this setting?

2 comments

We thank the reviewer for their careful reading of our paper and their constructive feedback. Below we respond to the question asked.

Although our approach draws inspiration from the continuous-function framework developed for online bidding, the differences between the two problems lead to distinct technical challenges and require new arguments.

  • First, the lower-bound analysis requires a fundamentally different approach. In online bidding, exchange arguments establish an equivalence between bidding functions and randomized bidding strategies. However, these exchange arguments provably fail for contract scheduling, so the same approach cannot be used to evaluate randomized schedules. We therefore need to establish an explicit lower bound, independently of the continuous-function framework. This is a problem that is already hard without predictions, as we discuss in the third point below. To this end, we prove an integral inequality relating the expected longest completed contracts at different interruption times, yielding our explicit lower bound on the consistency-robustness tradeoff for all randomized schedules (Theorem 3).

  • Second, establishing the feasibility of contract functions requires substantially new technical arguments. The main difficulty comes from the delay differential equation (DDE) describing the robustness constraint. In online bidding, this equation involves only positive terms, whereas in contract scheduling, the corresponding DDE is

    B′(t)=R(B(t)−2B(t−1)+B(t−2)).B' (t) = R(B(t) - 2B(t-1) + B(t-2)).

    The negative term introduces possible oscillations, so the resulting function is not necessarily increasing and may fail to define a valid schedule. We overcome this difficulty using a piecewise exponential construction and a careful proof of its feasibility (Theorem 6). For smaller robustness values, we additionally use Laplace transforms to identify and cancel problematic exponential modes (Theorem 7), with the guarantees supported computationally.

  • Third, the agnostic lower bound (Theorem 2) requires a substantially different analysis in comparison to online bidding. In online bidding, the expected normalized cost reduces to a sum of ratios of consecutive bids, and the lower bound follows from AM--GM. In contract scheduling, however, we must upper-bound the expected normalized length of the longest completed contract, which leads to products involving consecutive contract-completion times. This requires a new inequality (Appendix A, Eq (26)) that exploits the specific structure of contract schedules and yields the optimal acceleration ratio.

Thank you to the authors for the response. This settles my main concerns about the technical novelty of the paper. Overall, I think this is a nice submission with meaningful contributions to the theoretical state-of-the-art for contract scheduling. I'm increasing my score to a 4.

However, reading the other reviews and reponses also made me realise that I'm less familiar with the related work on this topic than I thought, so I'm lowering my confidence from 3 to 2.

Reviewer_Pg54OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper investigates randomized contract scheduling both with and without the prediction of interruption times. It establishes a matching lower bound for the optimal agnostic randomized acceleration ratio. It then develops a contract-function construction for prediction-augmented scheduling, and then studies prediction smoothing and history-based calibration of the smoothing parameter.

The theoretical contribution seems nontrivial. That said, I am not quite convinced by the experimental validation, the accessibility of the presentation, or the positioning and comparison against related alternatives. In particular, the paper's broad claims about improved interruptible systems and adaptive use of historical predictions are not adequately backed up by the evaluation.

Critical strengths
  • The agnostic lower bound seems confirming a previously-unaddressed theoretical gap that establishes the optimal randomized acceleration ratio of approximately 2.4554

  • The contract-function abstraction yields an explicit construction with rigorous guarantees for robustness parameters at least 2.65

  • The analysis tries to address the prediction brittleness rather than exclusively focusing on perfect-prediction and worst-case performance

Critical weaknesses
  • 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.

Questions for authors
  • Can you evaluate the adaptive smoothing estimator against fixed parameters and the best fixed parameter in hindsight, using actual expected normalized cost?

  • Can you include unsmoothed CF and biased prediction errors in the main experiments to isolate the benefit of smoothing?

  • How does the work relate to the decision-theoretic contract-scheduling approaches of Angelopoulos, Dürr, and Melidi, and can a comparison be made under matched information assumptions at robustness four?

  • Can you provide a concise algorithm-and-guarantee table that clearly separates proven results from conditional constructions and numerical evidence?

  • Can you provide either an application-level evaluation or a finite-startup simulation that tests whether the idealized improvements remain useful under implementation constraints?

8 comments
AuthorsOpenReview ↗

Response to Questions (Part 1)

We thank the reviewer for their careful reading and the constructive feedback. We appreciate the opportunity to further demonstrate the effectiveness of our algorithms in the extended settings suggested by the reviewer.

Due to space limitations, and since the reviewer has made many comments, we split our response into several parts.

Question 1\textbf{Question 1}: In the revised experiments (Section 5), we now evaluate our adaptive smoothing algorithm CFρ^\mathrm{CF}_{\hat\rho}, where the smoothing parameter is learned from a historical dataset (samples). We compare its performance against both fixed smoothing parameters, as well as the best parameter in hindsight, ρh\rho_h. The latter is chosen with knowledge of the joint distribution PP of predictions and interruption times, and therefore provides a benchmark for assessing the effectiveness of adaptive smoothing. Importantly, the hindsight-optimal parameter minimizes the actual expected normalized cost, not the surrogate upper bound used in Theorem 9. Specifically, we define

ρh=arg⁡min⁡ρEP[nc⁡(CFρ(T^),T)].\rho_h = \arg\min_\rho \mathbb{E}_P[\operatorname{nc}(\mathrm{CF}_\rho(\widehat{T}), T)].

Thus, the comparison directly evaluates our adaptive estimator against the best fixed smoothing parameter in terms of the actual objective, independently of the tightness of the surrogate upper bound. The revised results (Figure 2) show that the adaptive algorithm CFρ^\mathrm{CF}_{\hat\rho} achieves empirical acceleration ratios very close to those of the best fixed smoothing parameter in hindsight, CFρh\mathrm{CF}_{\rho_h}.

Moreover, it substantially outperforms the unsmoothed algorithm CF\mathrm{CF} in the challenging overprediction regime, while smoothing offers less benefit with perfect predictions or predominantly underpredicted interruption times, as expected from the theoretical analysis. It also outperforms the bidding-based baselines AS and AS$_{\rho}$, particularly at low and moderate prediction-error levels.

These results demonstrate the effectiveness of learning the smoothing parameter from historical data, without requiring knowledge of the underlying distribution.

Question 2\textbf{Question 2}: In the revised paper, we include the unsmoothed contract-function algorithm CF\mathrm{CF} in the experimental evaluation. The results show that smoothing substantially improves the empirical performance relative to CF, for any non-negligible error, which is consistent with the theoretical study.

Concerning asymmetric prediction errors, we note that our original experimental setup already incorporates asymmetry. Specifically, predictions are generated according to T^=TeZ\widehat{T} = Te^Z , where Z∼N(0,σ2)Z \sim \mathcal{N}(0, \sigma^2). Moreover, E[T^]=Teσ2/2>T\mathbb{E}[\widehat{T}] = T e^{\sigma^2/2} > T, so the predictions are also biased toward overestimation. Thus, our original experiments already evaluate the algorithms under an error distribution that captures a difficult case for contract scheduling: overpredictions, which can be especially damaging when an interruption occurs before the completion of a long contract. To study the effect of even more asymmetric errors, we considered additional distributions. Specifically, we study the case where ZZ follows a skew-normal distribution. The experimental results show that the smoothing mechanism in its adaptative version is particularly efficient in the more challenging case of overprediction.

Furthermore, to account for symmetric errors, we also consider an unbiased and symmetric distribution with T^T=1+Z\frac{\hat{T}}{T} = 1+Z with ZZ a truncated version of N(0,σ2)N(0, \sigma^2). The results replicate the same conclusions as in the asymmetric setting. Last, we have added new experimental results addressing the reviewer's concern about convergence. Specifically, we evaluate the convergence of the learned smoothing parameter ρ^\hat\rho as a function of the history size. The results demonstrate fast convergence both in terms of the learned parameter and the actual empirical acceleration ratio.

AuthorsOpenReview ↗

Response to Questions (Part 2)

Question 3\textbf{Question 3}: We thank the reviewer for pointing out this work, which we now include in the revised manuscript. First, the framework and analysis of (Angelopoulos, Dürr, and Melidi 2025) are restricted to deterministic contract schedules, for which robustness below 4 is impossible. Second, and equally importantly, the decision-theoretic framework considers additional information in the form of a weighting function or a probability distribution over possible interruption times. In contrast, our algorithms operate in the point-prediction model: the prediction consists solely of a single-value estimate of the interruption time. To match the information assumptions, we can consider a weighting function concentrated entirely at the predicted interruption time. In this case, however, the relevant comparison reduces to the classical deterministic consistency-robustness tradeoff, against which our randomized algorithm CF achieves considerably better performance, as depicted in Figure 2.

Question 4\textbf{Question 4}: We believe that our theoretical results are already clearly stated in the corresponding theorems, discussed in the introduction, and illustrated in Figure 1. Specifically, the lower bound of Theorem 3 is established analytically for all admissible robustness values RR. The upper bound of Theorem 6 is also fully analytical for all R≥2.65R\ge 2.65. For R∈[2.455,2.65R \in [2.455, 2.65], the consistency guarantee of Theorem 7 is supported by strong computational evidence, as detailed in Appendix B.7. As explained in the manuscript, establishing this result analytically presents substantial technical challenges due to the complexity of the underlying delay differential equation. Note that from our lower bound of Theorem 2, the robustness cannot be smaller than 2.455, hence all regimes are covered in our study.

We believe that Figure 1, which explicitly distinguishes the analytical lower bound, analytical upper bound, and computationally supported upper bound, already provides a concise visual summary of these results and their respective guarantees.

AuthorsOpenReview ↗

Response to Questions (Part 3)

Question 5\textbf{Question 5}: Concerning the request for an application-level evaluation, we would first like to emphasize that our work adopts the standard formulation of the contract-scheduling problem and its established performance measure, the acceleration ratio. This formulation has been extensively studied in the literature, including numerous papers published in leading AI/ML conferences and journals, as documented by the references in our introduction. Representative examples include Bernstein et al. (2003), Zilberstein et al. (2003), López-Ortiz et al. (2014), and Angelopoulos and Kamali (2023). As first discussed in the seminal work of Russell and Zilberstein (1991), the acceleration ratio has a natural interpretation in terms of processor speedup: speeding up the processor by a factor equal to the acceleration ratio allows an interruptible schedule to complete a contract at least as long as one completed by a system that knows the interruption time in advance. For randomized schedules, this interpretation extends to the expected length of the longest completed contract. Thus, the acceleration ratio provides a meaningful, application-independent measure of the efficiency of interruptible systems. The relevance of the contract-scheduling framework to concrete AI applications has already been established in prior work. In particular, Zilberstein and Russell (1996) study the relationship between computation time and solution quality through performance profiles, and establish guarantees for transforming contract algorithms into interruptible algorithms. They also discuss applications including diagnosis and treatment planning, automated reasoning, and search. Our work builds on this established framework, focusing on improving its theoretical and experimental performance guarantees as all recent works have done, rather than revisiting the application-level motivations already established in the literature.

Concerning the finite-startup simulation, we assume that the the reviewer is referring to the use of bi-infinite contract schedules in our theoretical analysis. To obtain a finite acceleration ratio, one is required to impose an assumption on the earliest possible interruption time. One possibility is to consider bi-infinite schedules, as in Angelopoulos et al. (2024), which also simplifies the analysis. Another is to assume that interruptions can occur only after the completion of the first contract, as in the classical model of Russell and Zilberstein (1991). A bi-infinite schedule X=(xi)i∈ZX = (x_i)_{i\in\mathbb{Z}} can be easily converted into a finite-startup schedule as follows. Let T0>0T_0>0 be the minimum admissible interruption time, and choose an index j0j_0 such that

∑i=−∞j0xi≤T0.\sum_{i=-\infty}^{j_0}x_i\le T_0.

We take this sum as the length of the first contract and subsequently execute xj0+1,xj0+2,…x_{j_0+1}, x_{j_0+2}, \ldots. This construction preserves the acceleration-ratio guarantees of the original schedule for all admissible interruption times T≥T0T\ge T_0.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.