Introduction
AI agents rarely complete complex tasks in a single model call [32 , 50 ] . A coding agent, for example, may inspect a repository, modify files, run commands, diagnose errors, and repeatedly revise its approach before producing a correct solution [57 , 23 ] . To effectively evaluate agents, we should therefore account not only for the final outcome, but also for how many interactions were required to reach the event of interest.
We consider an online setting where tasks arrive sequentially as a stream. At time t t t , the agent receives a task X t X_t X t and interacts with its environment until either the task is stopped or successfully completed. Success is determined by an external verifier, such as a unit test, a task-specific correctness checker, or an independent LLM-based evaluator [58 ] . Only then does the next task X t + 1 X_{t+1} X t + 1 arrive. An interaction may correspond to a model call, a tool invocation, an environment action, or an edit-and-test cycle, depending on the application [28 , 56 ] .
Following Davidov et al. [ [7 ] , Feldman and Romano [2026], we define T t T_t T t as the time-to-success —the number of interactions required for the agent to complete task X t X_t X t . For a software-engineering agent, T t T_t T t may count the number of edit-and-test iterations required to fix a bug; for a browser agent, it may count the actions required to complete a transaction; for a research or data-analysis agent, it may count the tool calls required to produce a verifiably correct response [60 , 57 ] . Unlike a binary success indicator, T t T_t T t captures the computational effort required to obtain that success and hence provides a more informative measure of agentic efficiency.
Our goal is to construct a calibrated upper predictive bound (UPB) U ^ t ( X t ) \hat{U}_t(X_t) U ^ t ( X t ) for the unknown time-to-success T t T_t T t of an arriving task X t X_t X t before executing it. We write U t = U ^ t ( X t ) U_t = \hat{U}_t(X_t) U t = U ^ t ( X t ) for ease of notation. Formally, for a given horizon T T T , at a user-specified target level 1 − α 1-\alpha 1 − α , we seek to satisfy the following finite-horizon average conditional coverage requirement:
1 T ∑ t = 1 T P ( T t ≤ U t ∣ X t , D t − 1 ) ≥ 1 − α . (1) \frac{1}{T}\sum_{t=1}^{T}\mathbb{P}(T_t \le U_t \mid X_t, \mathcal{D}_{t-1}) \ge1-\alpha. \tag*{(1)} T 1 t = 1 ∑ T P ( T t ≤ U t ∣ X t , D t − 1 ) ≥ 1 − α . (1)
Here, D t − 1 \mathcal{D}_{t-1} D t − 1 denotes the completed observed history before task t t t , as defined in § 1.2 .
In practice, however, we do not always observe the time-to-success for all tasks as agent interactions are computationally expensive. We therefore assume an average budget of C t a s k C_{\mathrm{task}} C task agentic iterations per task. To satisfy this constraint, we assign a censoring time C t C_t C t for each task t t t , which limits the maximum number of iterations the agent may spend on that task. The censored event time is therefore formulated as: T ~ t = min { T t , C t } \widetilde{T}_t = \min\{T_t, C_t\} T t = min { T t , C t } . Importantly, the bound U t U_t U t and the censoring time C t C_t C t are deliberately distinct: when C t < U t C_t < U_t C t < U t , censoring may prevent us from determining whether the UPB U t U_t U t successfully covered the true time-to-success T t T_t T t .
For example, consider an organization whose employees use AI agents for tasks such as software engineering. Before running the agent, an employee may want to know how many interactions it will take to complete the task successfully . To address this, the organization can provide calibrated UPBs on the time-to-success, updated continually from the employees’ own interactions as projects, users, and deployed agents change over time. However, if an employee stops before the task is completed, the time-to-success and correctness of the UPB may remain unknown. To recover this information, the organization can continue the stopped trajectory in a controlled environment, such as a sandbox, without affecting the employee’s workflow or production systems. Since continuing every trajectory to completion is expensive, the organization can continue only some of them. Our framework runs on top of existing usage of the user and calibrates the UPBs from the resulting censored observations, providing UPBs with coverage guarantees under a limited budget.
Our problem is related to conformal survival analysis works [4 , 20 , 40 , 39 , 6 ] , which study how to construct calibrated predictive bounds from censored observations. However, these methods are offline : they collect a fixed dataset of censored samples prior to calibrating the predictive bounds. In contrast, in our setting, the censoring times and predictive bounds are updated online . For each arriving task, we must determine for how many iterations the agent should execute based on information accumulated from previous tasks and the current task X t X_t X t . Crucially, this decision affects not only the computational cost of the current task, but also the quality of future predictions: the resulting censored trajectory becomes part of the data used to construct subsequent upper predictive bounds. Thus, prediction and data collection are inherently coupled.
To illustrate the challenge in this setup, we conduct an experiment on the software engineering tasks [30 ] . Figure 2 shows that ACI of Gibbs and Candes [2021] that is adapted to account for censoring yields overly conservative upper bounds under a limited budget. Censoring can hide prediction errors, making it more challenging to maintain informative bounds from the available feedback. This motivates the novel adaptive strategy we propose, which achieves the target coverage level by coupling budget allocation with an online calibration update that is explicitly designed to maintain tight and informative bounds under censored feedback.
Figure 2. Empirical evaluation of Upper Predictive Bounds on the SWE data. Left: Cumulative coverage rate over time comparing the Uncalibrated baseline, ACI+IPCW (§ 2 ), and the proposed method against a 90% target coverage rate. Right: Boxplots of the mean UPB across repetitions for the corresponding methods (lower is better). Full experimental details are provided in § 4 .
This raises two questions: First, how can we construct valid upper predictive bounds from censored online data? Second, how should we allocate the budget across tasks to derive efficient and informative bounds ?
Our Contribution
We introduce PRedictive Bounds for Online Budget Efficiency (PROBE), an online framework for constructing calibrated upper predictive bounds for the time-to-success of tasks under budget constraints (illustrated in Figure 1 ). Specifically, our main contributions are as follows:
Figure 1. Illustration of PROBE framework. For each arriving task (1), the system predicts the required time-to-success or token count (2). After environmental interaction where the agent executes the provided task (3), a budget is allocated for additional execution for agent evaluation (4). The result evaluation step (5) determines whether the task finished on time, leading to either a censored outcome with history-based correction (5a) or an observed outcome with direct trajectory evaluation (5b). Both outcomes are integrated via a coverage-aware update (6) (Theorem 3) consisting of (6a) online calibration to adjust predictive upper bounds (τ t + 1 \tau_{t+1} τ t + 1 ) and (6b) a budget strategy to optimize future budget allocation (π t + 1 \pi_{t+1} π t + 1 ).
Code and instructions for reproducibility are provided in our GitHub
Problem Setup
In our setup, tasks arrive sequentially over rounds t = 1 , … , T t = 1,\ldots,T t = 1 , … , T . We denote by X t ∈ X X_t \in\mathcal{X} X t ∈ X all information available before the t t t -th trajectory begins. In our software-engineering application, for example, X t X_t X t contains the model name and problem specification of the current task, together with information about the corresponding repository.
For each task X t X_t X t , the agent A \mathcal{A} A interacts sequentially with a task-specific environment Φ t \Phi_t Φ t . We initialize the interaction history as H t ( 0 ) = X t H_t(0) = X_t H t ( 0 ) = X t . At each interaction step k ≥ 1 k \ge1 k ≥ 1 , the agent selects an action based on the information observed so far A t ( k ) = A ( H t ( k − 1 ) ) A_t(k) = \mathcal{A}(H_t(k - 1)) A t ( k ) = A ( H t ( k − 1 )) . The environment then produces an observation in response to this action O t ( k ) = Φ t ( X t , H t ( k − 1 ) , A t ( k ) ) O_t(k) = \Phi_t(X_t, H_t(k - 1), A_t(k)) O t ( k ) = Φ t ( X t , H t ( k − 1 ) , A t ( k )) . A task-specific auditor J t \mathcal{J}_t J t determines whether the event of interest has occurred k k k : Y t ( k ) = J t ( X t , H t ( k ) ) ∈ { 0 , 1 } Y_t(k) = \mathcal{J}_t(X_t, H_t(k)) \in\{0,1\} Y t ( k ) = J t ( X t , H t ( k )) ∈ { 0 , 1 } . If Y t ( k ) = 1 Y_t(k) = 1 Y t ( k ) = 1 , the event occurred and the trajectory terminates; otherwise, the interaction continues to step k + 1 k + 1 k + 1 . The history is updated as H t ( k ) = ( H t ( k − 1 ) , A t ( k ) , O t ( k ) , Y t ( k ) ) H_t(k) = (H_t(k - 1), A_t(k), O_t(k), Y_t(k)) H t ( k ) = ( H t ( k − 1 ) , A t ( k ) , O t ( k ) , Y t ( k )) . The corresponding uncensored event time is
T t = inf { k ≥ 1 : Y t ( k ) = 1 } , (2) T_t = \inf\{k \ge1 : Y_t(k) = 1\}, \tag*{(2)} T t = inf { k ≥ 1 : Y t ( k ) = 1 } , (2)
with the convention T t = ∞ T_t = \infty T t = ∞ if the event never occurs. In our setup, the user runs the task up to time R t R_t R t . After this user run, we choose a censoring time C t C_t C t beyond this user runtime R t R_t R t , and the censored time-to-event is thus T ~ t = min ( T t , C t ) \widetilde{T}_t = \min(T_t, C_t) T t = min ( T t , C t ) . We denote by Δ t = 1 { T t ≤ C t } \Delta_t = 1\{T_t \le C_t\} Δ t = 1 { T t ≤ C t } the censoring indicator: Δ t = 1 \Delta_t = 1 Δ t = 1 means that the event time is observed at or before the timeout, whereas Δ t = 0 \Delta_t = 0 Δ t = 0 certifies only T t > C t T_t > C_t T t > C t . The indicator resolves equality at the boundary: T ~ t = C t \widetilde{T}_t = C_t T t = C t with Δ t = 1 \Delta_t = 1 Δ t = 1 means T t = C t T_t = C_t T t = C t , while the same equality with Δ t = 0 \Delta_t = 0 Δ t = 0 means T t > C t T_t > C_t T t > C t . The actually consumed budget for the t t t -th task is [ T ~ t − R t ] + [\widetilde{T}_t - R_t]_+ [ T t − R t ] + . Let
D t − 1 = { H s ( T ~ s ) , R s , C s , Δ s } s < t \mathcal{D}_{t-1} = \{H_s(\widetilde{T}_s), R_s, C_s, \Delta_s\}_{s<t} D t − 1 = { H s ( T s ) , R s , C s , Δ s } s < t
denote the completed observed history. The formal filtration convention is detailed in Appendix § 8 .§ 1.1 .
The budget constraint therefore limits the expected actual interaction cost to C t a s k C_{\mathrm{task}} C task per task at every prefix:
∑ s = 1 t E [ [ T ~ s − R s ] + ∣ X s , D s − 1 ] ≤ t C t a s k , ∀ t . (3) \sum_{s=1}^{t} \mathbb{E}\left[[\widetilde{T}_s-R_s]_+ \mid X_s,\mathcal{D}_{s-1}\right] \le tC_{\mathrm{task}}, \quad\forall t. \tag*{(3)} s = 1 ∑ t E [ [ T s − R s ] + ∣ X s , D s − 1 ] ≤ t C task , ∀ t . (3)
In Appendix § 10 , we consider an alternative requirement in which the budget is controlled deterministically rather than in expectation.
In addition to the budget constraint (3) , we adopt the standard assumption that C C C is conditionally independent of T T T given X , R X, R X , R :
Assumption 1 (Conditionally independent censoring). *For every round t t t , C t ⊥ ⊥ T t ∣ X t , R t , D t − 1 C_t \perp\!\!\!\perp T_t \mid X_t, R_t, \mathcal{D}_{t-1} C t ⊥ ⊥ T t ∣ X t , R t , D t − 1 .
Our budget allocator satisfies this condition by construction. Since we design the allocator, the distribution of C t ∣ R t C_t \mid R_t C t ∣ R t is known, formalized by the conditional survival function:
G t ( u ) = P ( C t ≥ u ∣ X t , R t , D t − 1 ) . (4) G_t(u) = \mathbb{P}(C_t \ge u \mid X_t, R_t, \mathcal{D}_{t-1}). \tag*{(4)} G t ( u ) = P ( C t ≥ u ∣ X t , R t , D t − 1 ) . (4)
Our goal is to construct the calibrated UPB U t = U ^ t ( X t ) U_t = \widehat{U}_t(X_t) U t = U t ( X t ) for the unknown time-to-event T t T_t T t of an arriving task X t X_t X t before executing it. Formally, for a target miscoverage level α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , this UPB should miscover T t T_t T t with probability at most α \alpha α :
1 T ∑ t = 1 T m t = 1 T ∑ t = 1 T P ( T t > U t ∣ X t , D t − 1 ) ≤ α . (5) \frac{1}{T}\sum_{t=1}^{T}m_t = \frac{1}{T}\sum_{t=1}^{T}\mathbb{P}(T_t > U_t \mid X_t,\mathcal{D}_{t-1}) \le\alpha. \tag*{(5)} T 1 t = 1 ∑ T m t = T 1 t = 1 ∑ T P ( T t > U t ∣ X t , D t − 1 ) ≤ α . (5)
Above, m t = P ( T t > U t ∣ X t , D t − 1 ) m_t = \mathbb{P}(T_t > U_t \mid X_t,\mathcal{D}_{t-1}) m t = P ( T t > U t ∣ X t , D t − 1 ) is the conditional miscoverage probability. Our objective is therefore to construct the predictive bounds U t U_t U t and allocate censoring times C t C_t C t online so that both the coverage and budget requirements are satisfied despite observing only right-censored event times.
Background
Adaptive conformal inference (ACI) generates predictive sets in an online manner that achieve a target miscoverage level α \alpha α by adjusting a calibration parameter in response to past prediction errors [17 , 18 ] . In our setting, the UPB is U t = q ^ t ( X t ; τ t ) U_t = \widehat{q}_t(X_t;\tau_t) U t = q t ( X t ; τ t ) , where q ^ t ( x ; τ ) \widehat{q}_t(x;\tau) q t ( x ; τ ) is the estimated conditional quantile at upper-tail level 1 − τ 1-\tau 1 − τ . ACI updates τ t \tau_t τ t over time according to the true UPB error:
e t = 1 { T t > U t } (6) e_t = 1\{T_t > U_t\} \tag*{(6)} e t = 1 { T t > U t } (6)
Assuming e t e_t e t is observed, ACI updates τ t \tau_t τ t as
τ t + 1 = τ t + η ( α − e t ) , η > 0. (7) \tau_{t+1} = \tau_t + \eta(\alpha-e_t), \qquad\eta> 0. \tag*{(7)} τ t + 1 = τ t + η ( α − e t ) , η > 0. (7)
Thus, when the UPB fails to cover (e t = 1 e_t = 1 e t = 1 ), the update decreases τ t \tau_t τ t and increases future UPBs, making them more conservative. When the UPB covers (e t = 0 e_t = 0 e t = 0 ), it increases τ t \tau_t τ t and turns future UPBs more liberal. Gibbs and Candes [2021] show that this procedure yields UPBs that achieve the target coverage level 1 − α 1-\alpha 1 − α on average over time.
In our setup, however, observations are right-censored, so the binary error e t e_t e t is not always observed. We define the observed-error and censoring-reach indicators:
I t e r r ( u ) = 1 { ( T ~ t > u ) ∨ ( T ~ t = u ∧ Δ t = 0 ) } , I t r e a c h ( u ) = 1 { C t ≥ u } . (8) I_t^{\mathrm{err}}(u) = 1\{(\widetilde{T}_t > u) \lor(\widetilde{T}_t = u \land\Delta_t = 0)\}, \qquad I_t^{\mathrm{reach}}(u) = 1\{C_t \ge u\}. \tag*{(8)} I t err ( u ) = 1 {( T t > u ) ∨ ( T t = u ∧ Δ t = 0 )} , I t reach ( u ) = 1 { C t ≥ u } . (8)
Here, I t e r r ( U t ) = 1 I_t^{\mathrm{err}}(U_t) = 1 I t err ( U t ) = 1 certifies observed miscoverage, T t > U t T_t > U_t T t > U t . The indicator I t r e a c h ( u ) I_t^{\mathrm{reach}}(u) I t reach ( u ) specifies whether the censoring time reaches u u u .
Thus, the standard ACI update in (7) cannot directly use the binary error e t e_t e t on every round. Treating every censored trajectory as miscover leads to overly conservative bounds, while ignoring unobserved errors leads to undercoverage.
Inverse-probability-of-censoring weighting (IPCW) corrects for the bias of the error signal induced by the missing labels. Recall that G t ( U t ) = P ( C t ≥ U t ∣ X t , R t , D t − 1 ) G_t(U_t) = \mathbb{P}(C_t \ge U_t \mid X_t, R_t, \mathcal{D}_{t-1}) G t ( U t ) = P ( C t ≥ U t ∣ X t , R t , D t − 1 ) is the probability that the censoring time reaches the bound.
Assumption 2 (Censoring positivity). For a fixed g min > 0 g_{\min} > 0 g m i n > 0 , every played round satisfies
G t ( U t ) ≥ g min > 0. (9) G_t(U_t) \ge g_{\min} > 0. \tag*{(9)} G t ( U t ) ≥ g m i n > 0. (9)
Positivity ensures that the inverse-probability weights are well defined. We define the weighted error as
e ^ t = I t e r r ( U t ) G t ( U t ) . (10) \widehat{e}_t = \frac{I_t^{\mathrm{err}}(U_t)}{G_t(U_t)}. \tag*{(10)} e t = G t ( U t ) I t err ( U t ) . (10)
Under Assumptions 1 and 2, the predictable bound and censoring law yield
E [ e ^ t ∣ X t , D t − 1 ] = P ( T t > U t ∣ X t , D t − 1 ) = m t . (11) \mathbb{E}[\widehat{e}_t \mid X_t, \mathcal{D}_{t-1}] = \mathbb{P}(T_t > U_t \mid X_t, \mathcal{D}_{t-1}) = m_t. \tag*{(11)} E [ e t ∣ X t , D t − 1 ] = P ( T t > U t ∣ X t , D t − 1 ) = m t . (11)
Therefore, by applying IPCW, we can obtain a miscoverage signal e ^ t \widehat{e}_t e t that is correct in expectation: observed miscoverages are weighted by 1 / G t ( U t ) 1/G_t(U_t) 1/ G t ( U t ) to compensate for failures hidden by censoring. By replacing e t e_t e t in (7) with e ^ t \widehat{e}_t e t , we obtain the following update for τ \tau τ
τ t + 1 = τ t + η ( α − e ^ t ) . (12) \tau_{t+1} = \tau_t + \eta(\alpha-\widehat{e}_t). \tag*{(12)} τ t + 1 = τ t + η ( α − e t ) . (12)
We refer to this method as ACI+IPCW; the full pseudocode is provided in Algorithm 1 in Appendix A.1.
Although ACI+IPCW attains a valid coverage (Theorem 13 in Appendix B.4), it can yield overly conservative upper predictive bounds, leaving a substantial gap between achieved coverage and the nominal level 1 − α 1-\alpha 1 − α , as illustrated in Figure 2 .
Proposed Method
In this section, we introduce PROBE, a framework that generates informative UPBs with a coverage rate closer to the target level. This framework is composed of two components. First, an online calibration mechanism (§ 3.1 ) that adaptively adjusts the bounds to reduce the coverage gap under censored feedback. Second, a budget allocation strategy (§ 3.2 ) that aims to reduce the coverage gap as well while satisfying the expected budget constraint.
Adaptive Calibration under Censoring
Censoring before the predictive bound U t U_t U t can leave the miscoverage indicator in (6) unobserved. We address this missing feedback by augmenting IPCW with an estimated miscoverage probability while preserving conditional unbiasedness.
Before introducing this correction, we reparameterize the calibration parameter to enforce that τ t \tau_t τ t remains in its admissible range. Rather than updating τ t \tau_t τ t directly, we introduce a t a_t a t and define
a t ∈ [ 0 , ∞ ) , τ t = τ max e − a t , U t = q ^ t ( X t ; τ t ) , (13) a_t \in[0,\infty), \qquad\tau_t = \tau_{\max}e^{-a_t}, \qquad U_t = \widehat{q}_t(X_t;\tau_t), \tag*{(13)} a t ∈ [ 0 , ∞ ) , τ t = τ m a x e − a t , U t = q t ( X t ; τ t ) , (13)
with initialization a 1 = a i n i t = log ( τ max / α ) a_1=a_{\mathrm{init}}=\log(\tau_{\max}/\alpha) a 1 = a init = log ( τ m a x / α ) for α ≤ τ max \alpha\le\tau_{\max} α ≤ τ m a x . This parameterization guarantees that τ t ∈ ( 0 , τ max ] \tau_t\in(0,\tau_{\max}] τ t ∈ ( 0 , τ m a x ] for all t t t , and allows for a faster adaptation to distributional shifts [14 ] .
Recall that e ^ t = I t e r r ( U t ) / G t ( U t ) \widehat{e}_t=I_t^{\mathrm{err}}(U_t)/G_t(U_t) e t = I t err ( U t ) / G t ( U t ) has conditional mean m t m_t m t by (11). Let F ^ t ( u ) \widehat{F}_t(u) F t ( u ) estimate the conditional CDF P ( T t ≤ u ∣ X t , D t − 1 ) \mathbb{P}(T_t\le u\mid X_t,D_{t-1}) P ( T t ≤ u ∣ X t , D t − 1 ) , and define the estimated miscoverage probability by
ρ t = 1 − F ^ t ( U t ) ∈ [ 0 , 1 ] . (14) \rho_t=1-\widehat{F}_t(U_t)\in[0,1]. \tag*{(14)} ρ t = 1 − F t ( U t ) ∈ [ 0 , 1 ] . (14)
When I t r e a c h ( U t ) = 1 I_t^{\mathrm{reach}}(U_t)=1 I t reach ( U t ) = 1 , the coverage error is observed; under the allocation strategy in § 3.2 , I t r e a c h ( U t ) = 0 I_t^{\mathrm{reach}}(U_t)=0 I t reach ( U t ) = 0 when C t = 0 C_t=0 C t = 0 . Under a general censoring policy, coverage may also be observed when the event occurs before a timeout below U t U_t U t . We use the centered corrected feedback
e ~ t = e ^ t + ρ t ( 1 − I t r e a c h ( U t ) G t ( U t ) ) , s t = e ~ t − α . (15) \widetilde{e}_t=\widehat{e}_t+\rho_t\left(1-\frac{I_t^{\mathrm{reach}}(U_t)}{G_t(U_t)}\right), \qquad s_t=\widetilde{e}_t-\alpha. \tag*{(15)} e t = e t + ρ t ( 1 − G t ( U t ) I t reach ( U t ) ) , s t = e t − α . (15)
Because ρ t \rho_t ρ t is determined by ( X t , D t − 1 ) (X_t,D_{t-1}) ( X t , D t − 1 ) and the reach indicator has conditional mean G t ( U t ) G_t(U_t) G t ( U t ) , the correction has conditional mean zero. Thus E [ e ~ t ∣ X t , D t − 1 ] = m t \mathbb{E}[\widetilde{e}_t\mid X_t,D_{t-1}]=m_t E [ e t ∣ X t , D t − 1 ] = m t even if F ^ t \widehat{F}_t F t is inaccurate. The feedback cases are
s t = { ρ t − α , I t r e a c h ( U t ) = 0 , e ^ t + ρ t ( 1 − G t ( U t ) − 1 ) − α , I t r e a c h ( U t ) = 1. (16) s_t=
\begin{cases}
\rho_t-\alpha, & I_t^{\mathrm{reach}}(U_t)=0,\\
\widehat{e}_t+\rho_t(1-G_t(U_t)^{-1})-\alpha, & I_t^{\mathrm{reach}}(U_t)=1.
\end{cases} \tag*{(16)} s t = { ρ t − α , e t + ρ t ( 1 − G t ( U t ) − 1 ) − α , I t reach ( U t ) = 0 , I t reach ( U t ) = 1. (16)
The calibration parameter is then updated using projected online gradient descent (OGD):
a t + 1 = [ a t + η s t ] + . (17) a_{t+1}=[a_t+\eta s_t]_+. \tag*{(17)} a t + 1 = [ a t + η s t ] + . (17)
Observed miscoverage gives s t > 0 s_t>0 s t > 0 and increases a t a_t a t , shifting calibration toward more conservative bounds. Observed coverage on a round that reaches U t U_t U t gives s t < 0 s_t<0 s t < 0 , pushing a t a_t a t toward zero and calibration toward less conservative bounds. On rounds that do not reach U t U_t U t , the sign of ρ t − α \rho_t-\alpha ρ t − α determines the direction of the calibration update. The correction on rounds that reach U t U_t U t compensates for this imputation.
Any predictable ρ t ∈ [ 0 , 1 ] \rho_t \in[0,1] ρ t ∈ [ 0 , 1 ] preserves unbiasedness, but its choice affects the conditional variance of the corrected feedback e ~ t \tilde e_t e ~ t . For a fixed censoring law, this variance is minimized when ρ t \rho_t ρ t equals the conditional miscoverage probability m t m_t m t , the optimal augmentation for inverse-probability-weighted estimators [45 ] . Our choice of ρ t \rho_t ρ t estimates m t m_t m t from the model F ^ t \widehat F_t F t .
We next introduce the quantities used to bound the residual coverage gap. For each observed trajectory, define the miscoverage threshold as the supremum of the calibration states that yield an observed error:
b t = sup { a ≥ 0 : I t e r r ( q ^ t ( X t ; τ max e − a ) ) = 1 } , sup ∅ = 0. (18) b_t = \sup\{a \ge0 : I_t^{\mathrm{err}}(\widehat q_t(X_t;\tau_{\max}e^{-a})) = 1\},
\qquad
\sup\varnothing= 0. \tag*{(18)} b t = sup { a ≥ 0 : I t err ( q t ( X t ; τ m a x e − a )) = 1 } , sup ∅ = 0. (18)
We track the cumulative centered correction A t ρ A_t^\rho A t ρ , the threshold-weighted sum L t L_t L t , and the sum of squared update signals Q t Q_t Q t , initialized at A 0 ρ = L 0 = Q 0 = 0 A_0^\rho=L_0=Q_0=0 A 0 ρ = L 0 = Q 0 = 0 :
A t ρ = A t − 1 ρ + ρ t ( 1 − I t r e a c h ( U t ) / G t ( U t ) ) , L t = L t − 1 + e ~ t b t + a t ( ρ t − α ) + ( 1 − I t r e a c h ( U t ) ) , Q t = Q t − 1 + s t 2 . (19) \begin{aligned}
A_t^\rho&= A_{t-1}^\rho+ \rho_t(1-I_t^{\mathrm{reach}}(U_t)/G_t(U_t)),\\
L_t &= L_{t-1}+\tilde e_t b_t+a_t(\rho_t-\alpha)_+(1-I_t^{\mathrm{reach}}(U_t)),\\
Q_t &= Q_{t-1}+s_t^2. \tag*{(19)}
\end{aligned} A t ρ L t Q t = A t − 1 ρ + ρ t ( 1 − I t reach ( U t ) / G t ( U t )) , = L t − 1 + e ~ t b t + a t ( ρ t − α ) + ( 1 − I t reach ( U t )) , = Q t − 1 + s t 2 . (19)
The OGD analysis combines L t L_t L t and Q t Q_t Q t into the envelope:
Γ t = 1 η [ − a i n i t + a i n i t 2 + η { 2 L t + η Q t } ] . (20) \Gamma_t=\frac{1}{\eta}\left[-a_{\mathrm{init}}+\sqrt{a_{\mathrm{init}}^2+\eta\{2L_t+\eta Q_t\}}\right]. \tag*{(20)} Γ t = η 1 [ − a init + a init 2 + η { 2 L t + η Q t } ] . (20)
The quantity Γ t − A t ρ \Gamma_t-A_t^\rho Γ t − A t ρ bounds the cumulative weighted excess miscoverage ∑ s = 1 t ( e ^ s − α ) \sum_{s=1}^t(\widehat e_s-\alpha) ∑ s = 1 t ( e s − α ) .
To account for stochastic variation in the IPCW feedback, let
V t = ∑ s = 1 t { E [ e ^ s 2 ∣ X s , D s − 1 ] − m s 2 } V_t=\sum_{s=1}^t\left\{\mathbb{E}\left[\widehat e_s^2\mid X_s,\mathcal{D}_{s-1}\right]-m_s^2\right\} V t = s = 1 ∑ t { E [ e s 2 ∣ X s , D s − 1 ] − m s 2 }
denote its cumulative conditional variance. Since V t V_t V t depends on unknown conditional moments, we use the deterministic upper bound V t ≤ t / g min V_t\le t/g_{\min} V t ≤ t / g m i n to define the computable confidence buffer
F ~ t ( δ ) = 2 t g min log 1 δ + 1 3 log 1 δ . (21) \widetilde{\mathcal{F}}_t(\delta)=\sqrt{\frac{2t}{g_{\min}}\log\frac{1}{\delta}+\frac{1}{3}\log\frac{1}{\delta}}. \tag*{(21)} F t ( δ ) = g m i n 2 t log δ 1 + 3 1 log δ 1 . (21)
This term captures the uncertainty underlying the IPCW feedback.
Appendix § 8 .§ 1 provides the complete derivation. Theorem 3 bounds the residual coverage gap through Γ t \Gamma_t Γ t , the confidence buffer F ~ t ( δ c o v ) \widetilde{\mathcal{F}}_t(\delta_{\mathrm{cov}}) F t ( δ cov ) , and the signed centered correction A t ρ A_t^\rho A t ρ .
Algorithm 3 summarizes the calibration procedure. The next subsection uses the resulting coverage bound to guide observation probabilities under the budget constraint.
Coverage-Informed Budget Allocation
We adapt the budget allocation of Davidov et al. [2026] to our online setting. Specifically, for each round t t t , we choose a probability π t ∈ [ g min , 1 ] \pi_t \in[g_{\min},1] π t ∈ [ g m i n , 1 ] of observing the trajectory up to iteration C t = u t : = ⌈ U t ⌉ C_t = u_t := \lceil U_t\rceil C t = u t := ⌈ U t ⌉ . With the remaining probability 1 − π t 1-\pi_t 1 − π t , we set C t = 0 C_t=0 C t = 0 and do not run the trajectory. Formally,
C t = { u t , with probability π t , 0 , with probability 1 − π t . (22) C_t =
\begin{cases}
u_t, & \text{with probability } \pi_t,\\
0, & \text{with probability } 1-\pi_t.
\end{cases} \tag*{(22)} C t = { u t , 0 , with probability π t , with probability 1 − π t . (22)
Observe that for this design choice G t ( U t ) = π t G_t(U_t)=\pi_t G t ( U t ) = π t , the IPCW weight is W t = 1 / π t W_t=1/\pi_t W t = 1/ π t , and the expected consumed budget for this step is at most π t u t \pi_t u_t π t u t . With fresh randomization independent of T t T_t T t conditional on ( X t , R t , D t − 1 ) (X_t,R_t,\mathcal{D}_{t-1}) ( X t , R t , D t − 1 ) , this allocation satisfies Assumptions 1 and 2 by construction, since G t ( U t ) = π t ≥ g min > 0 G_t(U_t)=\pi_t\ge g_{\min}>0 G t ( U t ) = π t ≥ g m i n > 0 . We select π t \pi_t π t by minimizing a model-based estimate of the residual coverage deficit subject to the budget constraint. The feasible observation probabilities are
Π t b u d = { π : ∑ s = 1 t − 1 [ π s u s − R s ] + + [ π u t − R t ] + ≤ t C t a s k } . (23) \Pi_t^{\mathrm{bud}}=\left\{\pi:\sum_{s=1}^{t-1}[\pi_su_s-R_s]_+ + [\pi u_t-R_t]_+ \le tC_{\mathrm{task}}\right\}. \tag*{(23)} Π t bud = { π : s = 1 ∑ t − 1 [ π s u s − R s ] + + [ π u t − R t ] + ≤ t C task } . (23)
Unused allowance under this cumulative constraint can support larger expected allocations on later rounds, allowing π t u t \pi_tu_t π t u t to exceed C t a s k C_{\mathrm{task}} C task while every prefix remains within budget.
Our budget allocation is guided by the same coverage gap as the calibration scheme. Among feasible allocations, we seek to reduce the anticipated deficit Γ t + F ~ t ( δ c o v ) − A t ρ \Gamma_t+\widetilde{F}_t(\delta_{\mathrm{cov}})-A_t^\rho Γ t + F t ( δ cov ) − A t ρ in Theorem 3. A candidate probability π \pi π determines both the frequency of observing coverage feedback and its inverse-probability weight W = 1 / π W=1/\pi W = 1/ π . These, in turn, affect the calibration states and the resulting coverage deficit.
Before observing the current outcome, we evaluate each candidate allocation using the same completion model F ^ t \widehat{F}_t F t used to define ρ t \rho_t ρ t . Let E ^ t , W \widehat{\mathbb{E}}_{t,W} E t , W denote estimated expectation over the predicted event time and the candidate censoring draw. The anticipated deficit is
E ‾ t ( W ) = 1 t E ^ t , W [ Γ t ( W ) + F ~ t ( δ c o v , W ) − A t ρ ( W ) ] . (24) \overline{\mathcal{E}}_t(W)=\frac{1}{t}\widehat{\mathbb{E}}_{t,W}\left[\Gamma_t(W)+\widetilde{F}_t(\delta_{\mathrm{cov}},W)-A_t^\rho(W)\right]. \tag*{(24)} E t ( W ) = t 1 E t , W [ Γ t ( W ) + F t ( δ cov , W ) − A t ρ ( W ) ] . (24)
Here, Γ t ( W ) \Gamma_t(W) Γ t ( W ) and A t ρ ( W ) A_t^\rho(W) A t ρ ( W ) denote the calibration envelope and cumulative centered correction after the synthetic update under candidate weight W W W . The term F ~ t ( δ c o v , W ) \widetilde{F}_t(\delta_{\mathrm{cov}},W) F t ( δ cov , W ) is a model-based estimate of the confidence buffer F ~ t ( δ c o v ) \widetilde{F}_t(\delta_{\mathrm{cov}}) F t ( δ cov ) . For each candidate W W W , the synthetic update uses the corresponding censoring law and IPCW weight, while keeping U t U_t U t , ρ t \rho_t ρ t , and the completed-round states fixed. Algorithm 4 specifies the synthetic updates and the model-based buffer in (24) .
When the feasible set is nonempty, we select the observation probability by solving
π t ∈ arg min π ∈ Π t b u d E ‾ t ( 1 / π ) . (25) \pi_t \in\arg\min_{\pi\in\Pi_t^{\mathrm{bud}}}\overline{\mathcal{E}}_t(1/\pi). \tag*{(25)} π t ∈ arg π ∈ Π t bud min E t ( 1/ π ) . (25)
After selecting π t \pi_t π t , we draw C t C_t C t according to (22) and run the trajectory until success or timeout, obtaining ( T ^ t , R t , Δ t ) (\widehat{T}_t,R_t,\Delta_t) ( T t , R t , Δ t ) .
The complete PROBE procedure, combining online calibration and budget allocation, is summarized in Algorithm 5 in Appendix § 7 .§ 1 . The next subsection establishes the coverage and expected-budget guarantees.
Theoretical guarantees
We establish a bound on average conditional coverage and a bound on average expected resource use, using the quantities defined above. Let A T ρ = ∑ t = 1 T ρ t ( 1 − I t r e a c h ( U t ) / G t ( U t ) ) A_T^{\rho} = \sum_{t=1}^{T} \rho_t(1-I_t^{\mathrm{reach}}(U_t)/G_t(U_t)) A T ρ = ∑ t = 1 T ρ t ( 1 − I t reach ( U t ) / G t ( U t )) , and let L T L_T L T and Q T Q_T Q T denote the terminal realized states obtained by evaluating the recurrences in (19) on each round t = 1 , … , T t = 1,\ldots,T t = 1 , … , T , with ρ t \rho_t ρ t defined by (14). Evaluating the previously defined envelope on the observed sequence at horizon T T T gives
Γ T = 1 η [ − a i n i t + a i n i t 2 + η { 2 L T + η Q T } ] . (26) \Gamma_T = \frac{1}{\eta}\left[-a_{\mathrm{init}}+\sqrt{a_{\mathrm{init}}^2+\eta\{2L_T+\eta Q_T\}}\right]. \tag*{(26)} Γ T = η 1 [ − a init + a init 2 + η { 2 L T + η Q T } ] . (26)
Theorem 3 (Coverage validity, informal). Under Assumptions 1, and 2 PROBE (13)–(17) satisfies, for every fixed T T T and δ c o v ∈ ( 0 , 1 ) \delta_{\mathrm{cov}} \in(0,1) δ cov ∈ ( 0 , 1 ) , with probability at least 1 − δ c o v 1-\delta_{\mathrm{cov}} 1 − δ cov over D T D_T D T
1 T ∑ t = 1 T P ( T t ≤ U t ∣ X t , D t − 1 ) ≥ 1 − α + 1 T [ A T ρ − Γ T − F ~ T ( δ c o v ) ] . (27) \frac{1}{T}\sum_{t=1}^{T}\mathbb{P}(T_t \le U_t \mid X_t,D_{t-1}) \ge1-\alpha+\frac{1}{T}\left[A_T^{\rho}-\Gamma_T-\widetilde{\mathcal{F}}_T(\delta_{\mathrm{cov}})\right]. \tag*{(27)} T 1 t = 1 ∑ T P ( T t ≤ U t ∣ X t , D t − 1 ) ≥ 1 − α + T 1 [ A T ρ − Γ T − F T ( δ cov ) ] . (27)
The proof is provided in Appendix B.1. The bound controls average conditional coverage under adaptive censoring.
Theorem 4 (Budget validity, informal). Under Assumptions 1, 2, and 10, PROBE (Algorithm 5) satisfies, for every fixed horizon T T T ,
1 T ∑ t = 1 T E [ T ~ t − R t ] + ≤ C t a s k . (28) \frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\widetilde{T}_t-R_t]_+ \le C_{\mathrm{task}}. \tag*{(28)} T 1 t = 1 ∑ T E [ T t − R t ] + ≤ C task . (28)
This theorem is formally proved in Appendix B.2. The accumulating constraint limits average expected additional resource consumption even when the completion model is misspecified. A corresponding high-probability bound for the realized budget, holding jointly with the residual coverage certificate, is established in Theorem 12 in Appendix B.3.
Experiments
We evaluate our proposed framework, PROBE, across three distinct real-world settings with right-censored outcomes. Adapting the evaluation procedures established by Davidov et al. [ [7 ] , Feldman and Romano [2026] to our online setting, we present tasks sequentially and censor outcomes using finite per-task budgets to assess both empirical coverage and resource use. We compare PROBE with two baselines: Uncalibrated, which reports raw model predictions, and ACI+IPCW, which applies the censoring-corrected ACI update (§ 2 ) paired with neutral budget allocation (Algorithm 2 ). We first describe the three experimental settings and then examine calibration, informativeness, and budget dynamics.
In the first setting, SWE, we construct UPBs for the interaction lengths of SWE-agent trajectories addressing real-world GitHub issues [30 ] . The outcome for each task is the number of logged agent interactions in its trajectory.
Next, in the RAG setting, we consider medical information-retrieval queries from NFCorpus [43 ] and construct UPBs for the number of retrieval iterations required to identify all relevant corpus items associated with each query.
In the instruction-following setup, we use tasks from AutoIF [8 ] . Here, the agent aims to help a target model satisfy the requirements across sequential iterations until all instructions are satisfied. The response is verified programmatically using Python scripts. Full details regarding all datasets, feature extractions, and quantile predictor architectures are provided in Appendix § 13 .
To demonstrate the effectiveness of our budget allocation, we consider the challenging setting where we receive no prior user interactions, R t = 0 R_t = 0 R t = 0 , ∀ t \forall t ∀ t , and must allocate the entire evaluation budget across tasks. Appendix § 13 details all datasets, features, and model architectures.
As illustrated in Figure 2 , PROBE achieves the target coverage rate and constructs more informative bounds compared to the ACI+IPCW method, which tends to overcover the response. Furthermore, this figure shows that the Uncalibrated predictor consistently undercovers the true event time.
The same trend is observed in the RAG setting presented in Figure 3 . Specifically, the Uncalibrated predictor systematically undercovers the time-to-success, whereas ACI+IPCW attains coverage higher than the target level and yields large and less informative UPBs. Our proposed method achieves coverage close to the nominal level with substantially tighter bounds than ACI+IPCW. This demonstrates the effectiveness of our method in accounting for censored feedback to restore reliability while preserving highly informative predictions.
Figure 3. RAG setting: Results after 1,000 steps across 10 repetitions for α = 0.10 \alpha= 0.10 α = 0.10 and budget constraint C t a s k = 25 C_{\mathrm{task}} = 25 C task = 25 , comparing the Uncalibrated , ACI+IPCW , and Proposed methods. (a) Boxplots of empirical local coverage over w i n d o w = 50 \mathrm{window} = 50 window = 50 ; the dashed line marks the target coverage level. (b) Boxplots of the mean upper predictive bound within each repetition.
We measure the local coverage of our method on the SWE data, and report it in Figure 4 . Specifically, the Uncalibrated predictor severely undercovers, whereas ACI+IPCW overcovers the response. Conversely, the coverage rate attained by PROBE across moving windows of time is closer to the desired level.
Figure 4. SWE setting: Empirical coverage over rolling windows of 50 tasks, for α = 0.10 \alpha= 0.10 α = 0.10 and C t a s k = 20 C_{\mathrm{task}} = 20 C task = 20 , comparing Uncalibrated, ACI+IPCW, and PROBE. The dashed line marks the target 90% coverage.
Finally, Figure 5 demonstrates efficient budget utilization in the AutoIF setting through the cumulative assigned timeout, ∑ s ≤ t C s \sum_{s \le t} C_s ∑ s ≤ t C s . Specifically, both methods sustain continuous allocation throughout the stream, with their mean trajectories closely tracking the nominal allowance t C t a s k t C_{\mathrm{task}} t C task . For PROBE, this stable tracking not only supports Theorem 4 but also confirms that our accumulating-budget mechanism maintains steady while efficiently utilizing the available resource allowance.
Figure 5. AutoIF settings: Mean cumulative realized spend ∑ s < t C s \sum_{s<t} C_s ∑ s < t C s at step t t t , for α = 0.1 \alpha= 0.1 α = 0.1 and budget constraint C t a s k = 25 C_{\mathrm{task}} = 25 C task = 25 , comparing the ACI+IPCW and Proposed methods over 1,000 steps and 10 repetitions. The dashed line marks the nominal budget t C t a s k tC_{\mathrm{task}} t C task .
Appendix E provides additional experiments across the SWE, RAG, and AutoIF datasets.
Discussion
We introduced PROBE, an online framework for constructing calibrated upper predictive bounds on time-to-event under limited computational resources. The key challenge is that censoring affects both calibration and data collection: when a trajectory is stopped early, the coverage error may remain unobserved, while additional computation spent on one task reduces the budget available for others. PROBE addresses these two issues jointly by correcting for censored feedback and allocating budget aiming to minimize the coverage gap. Our experiments show that our approach leads to informative and reliable bounds across several agentic evaluation settings.
Our coverage guarantee holds on average over the task stream rather than for each task or subgroup. An exciting future direction could be extending the framework to individualized or group-conditional coverage, possibly by drawing ideas from [13 , 19 ] . Second, we assume that the auditor identifying the event of interest is reliable; in practice, unit tests, automated checkers, and LLM judges may themselves be noisy or incorrect. An important direction is to develop a framework that is robust to such incorrect labels [9 , 33 ] , e.g., by leveraging privileged information [46 , 11 ] (Feldman et al. 2026). We believe using simulated data to complement censored trajectories could improve the prediction efficiency, making this a promising research direction [1 b] .
Finally, our framework can support both utility and safety evaluation. Time-to-event bounds can characterize how efficiently an agent completes tasks, as well as how many iterations are required for undesirable events—such as unsafe behavior or policy violations—to occur. Reliable evaluation under limited computation can make large-scale auditing more practical and help identify systems or task classes that warrant additional scrutiny. At the same time, the guarantees provided by PROBE consider the specified event, auditor, and coverage criterion; they should not be interpreted as a complete certificate of system reliability or safety. Thus, our framework should incorporate complementary evaluations of correctness, robustness, and security in deployment pipelines.
Acknowledgments
Y. R., R. M. L and S. F. were supported by the European Union (ERC, SafetyBounds, 101163414). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Y.R. thanks the Career Advancement Fellowship, Technion.
Algorithms
Calibration and Budget Allocation
The additional-cost feasible set used by the budget allocator is
Π t a d d = { { π ∈ [ g min , 1 ] : S t − 1 + π d t ≤ t C t a s k } , d t > 0 , { 1 } , d t = 0 , (29) \Pi_t^{\mathrm{add}} =
\begin{cases}
\{\pi\in[g_{\min},1] : S_{t-1} + \pi d_t \le tC_{\mathrm{task}}\}, & d_t > 0,\\
\{1\}, & d_t = 0,
\end{cases} \tag*{(29)} Π t add = { { π ∈ [ g m i n , 1 ] : S t − 1 + π d t ≤ t C task } , { 1 } , d t > 0 , d t = 0 , (29)
where d t = ( ⌈ U t ⌉ − R t ) + d_t = (\lceil U_t\rceil- R_t)_+ d t = (⌈ U t ⌉ − R t ) + and S t − 1 = ∑ s < t π s d s S_{t-1} = \sum_{s<t}\pi_s d_s S t − 1 = ∑ s < t π s d s . The zero-cost case uses π t = 1 \pi_t = 1 π t = 1 by convention.
Algorithm 1 ACI+IPCW
Input: Horizon T T T , target α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , step size η > 0 \eta> 0 η > 0 , initial calibration state τ 1 \tau_1 τ 1 ; prediction rules q ^ t ( x ; τ ) \widehat{q}_t(x;\tau) q t ( x ; τ ) with declared behavior for every reachable τ \tau τ ; a censoring-policy rule based on ( X t , R t , D t − 1 ) (X_t,R_t,D_{t-1}) ( X t , R t , D t − 1 ) with known survival probability G t ( v ) = P ( C t ≥ v ∣ X t , R t , D t − 1 ) G_t(v) = \mathbb{P}(C_t \ge v \mid X_t,R_t,D_{t-1}) G t ( v ) = P ( C t ≥ v ∣ X t , R t , D t − 1 ) and G t ( U t ) ≥ g min > 0 G_t(U_t) \ge g_{\min} > 0 G t ( U t ) ≥ g m i n > 0 .
Initialize the completed online history D 0 ← ∅ D_0 \leftarrow\varnothing D 0 ← ∅ .
for t = 1 , … , T t = 1,\ldots,T t = 1 , … , T do
(a) Receive X t X_t X t ; fix the prediction rule using only ( X t , D t − 1 ) (X_t,D_{t-1}) ( X t , D t − 1 ) and issue U t ← q ^ t ( X t ; τ t ) U_t \leftarrow\widehat{q}_t(X_t;\tau_t) U t ← q t ( X t ; τ t ) .
(b) Observe the user’s initial run of length R t R_t R t . Commit the censoring law supported on C t ≥ R t C_t \ge R_t C t ≥ R t and record G t ( U t ) G_t(U_t) G t ( U t ) ; draw C t C_t C t using fresh randomness, conditionally independent of T t T_t T t given ( X t , R t , D t − 1 ) (X_t,R_t,D_{t-1}) ( X t , R t , D t − 1 ) .
(c) Continue any unfinished trajectory until the event or timeout; observe T ~ t = min { T t , C t } \widetilde{T}_t = \min\{T_t,C_t\} T t = min { T t , C t } and Δ t = 1 { T t ≤ C t } \Delta_t = 1\{T_t \le C_t\} Δ t = 1 { T t ≤ C t } , with an event at the timeout counted as observed.
(d) Compute the observable IPCW feedback and update:
e ^ t ← 1 { ( T ~ t > U t ) ∨ ( T ~ t = U t ∧ Δ t = 0 ) } G t ( U t ) , τ t + 1 ← τ t + η ( α − e ^ t ) . \widehat{e}_t \leftarrow\frac{1\{(\widetilde{T}_t > U_t)\lor(\widetilde{T}_t = U_t\land\Delta_t = 0)\}}{G_t(U_t)}, \qquad\tau_{t+1} \leftarrow\tau_t + \eta(\alpha-\widehat{e}_t). e t ← G t ( U t ) 1 {( T t > U t ) ∨ ( T t = U t ∧ Δ t = 0 )} , τ t + 1 ← τ t + η ( α − e t ) .
(e) Append ( H t ( T ~ t ) , R t , C t , Δ t ) (H_t(\widetilde{T}_t),R_t,C_t,\Delta_t) ( H t ( T t ) , R t , C t , Δ t ) to D t − 1 D_{t-1} D t − 1 to obtain D t D_t D t .
return issued bounds ( U t ) t = 1 T (U_t)_{t=1}^{T} ( U t ) t = 1 T and state τ T + 1 \tau_{T+1} τ T + 1 .
Algorithm 2 Neutral Budget Allocation (Online version of Davidov et al. [2026])
Input: Round t t t , user runtime R t R_t R t , finite bound U t > 0 U_t > 0 U t > 0 , budget rate C t a s k > 0 C_{\mathrm{task}} > 0 C task > 0 , positivity floor g min ∈ ( 0 , 1 ] g_{\min} \in(0,1] g m i n ∈ ( 0 , 1 ] , and expected allocation S t − 1 = ∑ s < t π s d s S_{t-1} = \sum_{s<t} \pi_s d_s S t − 1 = ∑ s < t π s d s (initialize S 0 = 0 S_0 = 0 S 0 = 0 ).
Set u t ← ⌈ U t ⌉ u_t \leftarrow\lceil U_t \rceil u t ← ⌈ U t ⌉ and d t ← ( u t − R t ) + d_t \leftarrow(u_t - R_t)_+ d t ← ( u t − R t ) + . if d t = 0 d_t = 0 d t = 0 then (a) return ( C t , π t , W t , d t , S t ) = ( R t , 1 , 1 , 0 , S t − 1 ) (C_t,\pi_t,W_t,d_t,S_t) = (R_t,1,1,0,S_{t-1}) ( C t , π t , W t , d t , S t ) = ( R t , 1 , 1 , 0 , S t − 1 ) . end if
Set π ˉ t ← min { 1 , ( t C t a s k − S t − 1 ) / d t } \bar{\pi}_t \leftarrow\min\{1,(tC_{\mathrm{task}} - S_{t-1})/d_t\} π ˉ t ← min { 1 , ( t C task − S t − 1 ) / d t } . if π ˉ t < g min \bar{\pi}_t < g_{\min} π ˉ t < g m i n then (a) return INFEASIBLE, leaving the allocation state unchanged. end if
Set π t ← π ˉ t \pi_t \leftarrow\bar{\pi}_t π t ← π ˉ t and W t ← 1 / π t W_t \leftarrow1/\pi_t W t ← 1/ π t .
Draw Z t ∼ Bernoulli ( π t ) Z_t \sim\operatorname{Bernoulli}(\pi_t) Z t ∼ Bernoulli ( π t ) using fresh randomness conditionally independent of T t T_t T t given ( X t , R t , D t − 1 ) (X_t,R_t,D_{t-1}) ( X t , R t , D t − 1 ) .
Set C t ← R t + d t Z t C_t \leftarrow R_t + d_tZ_t C t ← R t + d t Z t and S t ← S t − 1 + π t d t S_t \leftarrow S_{t-1} + \pi_td_t S t ← S t − 1 + π t d t .
return ( C t , π t , W t , d t , S t ) (C_t,\pi_t,W_t,d_t,S_t) ( C t , π t , W t , d t , S t ) .
Algorithm 3 Censoring-Aware Online Calibration
Input: T T T , 0 < α ≤ τ max ≤ 1 0 < \alpha\le\tau_{\max} \le1 0 < α ≤ τ m a x ≤ 1 with α < 1 \alpha< 1 α < 1 , η > 0 \eta> 0 η > 0 , δ c o v ∈ ( 0 , 1 ) \delta_{\mathrm{cov}} \in(0,1) δ cov ∈ ( 0 , 1 ) , g min ∈ ( 0 , 1 ] g_{\min} \in(0,1] g m i n ∈ ( 0 , 1 ] ; predictable upper-quantile rules q ^ t ( x ; τ ) \widehat{q}_t(x;\tau) q t ( x ; τ ) nonincreasing in τ \tau τ with finite thresholds b t b_t b t ; predictable completion CDFs F ^ t \widehat{F}_t F t ; an external predictable censoring policy with known G t ( U t ) ≥ g min G_t(U_t) \ge g_{\min} G t ( U t ) ≥ g m i n and fresh randomness conditionally independent of T t T_t T t given ( X t , R t , D t − 1 ) (X_t,R_t,\mathcal{D}_{t-1}) ( X t , R t , D t − 1 ) .
Initialize D 0 ← ∅ \mathcal{D}_0 \leftarrow\varnothing D 0 ← ∅ , a i n i t ← log ( τ max / α ) a_{\mathrm{init}} \leftarrow\log(\tau_{\max}/\alpha) a init ← log ( τ m a x / α ) , a 1 ← a i n i t a_1 \leftarrow a_{\mathrm{init}} a 1 ← a init , and A 0 ρ = L 0 = Q 0 ← 0 A_0^\rho= L_0 = Q_0 \leftarrow0 A 0 ρ = L 0 = Q 0 ← 0 .
for t = 1 , … , T t = 1,\ldots,T t = 1 , … , T do
(a) Receive X t X_t X t and fix ( q ^ t , F ^ t ) (\widehat{q}_t,\widehat{F}_t) ( q t , F t ) using ( X t , D t − 1 ) (X_t,\mathcal{D}_{t-1}) ( X t , D t − 1 ) ; set τ t ← τ max e − a t \tau_t \leftarrow\tau_{\max}e^{-a_t} τ t ← τ m a x e − a t and issue U t ← q ^ t ( X t ; τ t ) U_t \leftarrow\widehat{q}_t(X_t;\tau_t) U t ← q t ( X t ; τ t ) ; set ρ t ← 1 − F ^ t ( U t ) \rho_t \leftarrow1-\widehat{F}_t(U_t) ρ t ← 1 − F t ( U t ) .
(b) Observe the user’s initial run of length R t R_t R t . Commit the external censoring law supported on C t ≥ R t C_t \ge R_t C t ≥ R t , record G t ( U t ) G_t(U_t) G t ( U t ) , and draw C t C_t C t from that law.
(c) Continue any unfinished trajectory until the event or timeout; observe T ~ t = min { T t , C t } \widetilde{T}_t = \min\{T_t,C_t\} T t = min { T t , C t } and Δ t = 1 { T t ≤ C t } \Delta_t = 1\{T_t \le C_t\} Δ t = 1 { T t ≤ C t } .
(d) Define, for any threshold v v v ,
I t e r r ( v ) ← 1 { ( T ~ t > v ) ∨ ( T ~ t = v ∧ Δ t = 0 ) } , I_t^{\mathrm{err}}(v) \leftarrow1\{(\widetilde{T}_t > v) \lor(\widetilde{T}_t = v \land\Delta_t = 0)\}, I t err ( v ) ← 1 {( T t > v ) ∨ ( T t = v ∧ Δ t = 0 )} ,
I t r e a c h ( v ) ← 1 { C t ≥ v } . I_t^{\mathrm{reach}}(v) \leftarrow1\{C_t \ge v\}. I t reach ( v ) ← 1 { C t ≥ v } .
(e) Compute
e ^ t ← I t e r r ( U t ) G t ( U t ) , b t ← sup { a ≥ 0 : I t e r r ( q ^ t ( X t ; τ max e − a ) ) = 1 } , sup ∅ = 0. \widehat{e}_t \leftarrow\frac{I_t^{\mathrm{err}}(U_t)}{G_t(U_t)}, \qquad
b_t \leftarrow\sup\{a \ge0 : I_t^{\mathrm{err}}(\widehat{q}_t(X_t;\tau_{\max}e^{-a}))=1\}, \qquad\sup\varnothing=0. e t ← G t ( U t ) I t err ( U t ) , b t ← sup { a ≥ 0 : I t err ( q t ( X t ; τ m a x e − a )) = 1 } , sup ∅ = 0.
(f) Commit the centered update and realized states:
e ~ t ← e ^ t + ρ t ( 1 − I t r e a c h ( U t ) / G t ( U t ) ) , s t ← e ~ t − α , \widetilde{e}_t \leftarrow\widehat{e}_t+\rho_t(1-I_t^{\mathrm{reach}}(U_t)/G_t(U_t)), \qquad s_t \leftarrow\widetilde{e}_t-\alpha, e t ← e t + ρ t ( 1 − I t reach ( U t ) / G t ( U t )) , s t ← e t − α ,
A t ρ ← A t − 1 ρ + ρ t ( 1 − I t r e a c h ( U t ) / G t ( U t ) ) , L t ← L t − 1 + e ^ t b t + a t ( ρ t − α ) + ( 1 − I t r e a c h ( U t ) ) , A_t^\rho\leftarrow A_{t-1}^\rho+\rho_t(1-I_t^{\mathrm{reach}}(U_t)/G_t(U_t)), \qquad L_t \leftarrow L_{t-1}+\widehat{e}_tb_t+a_t(\rho_t-\alpha)+(1-I_t^{\mathrm{reach}}(U_t)), A t ρ ← A t − 1 ρ + ρ t ( 1 − I t reach ( U t ) / G t ( U t )) , L t ← L t − 1 + e t b t + a t ( ρ t − α ) + ( 1 − I t reach ( U t )) ,
Q t ← Q t − 1 + s t 2 , a t + 1 ← max { 0 , a t + η s t } . Q_t \leftarrow Q_{t-1}+s_t^2, \qquad a_{t+1} \leftarrow\max\{0,a_t+\eta s_t\}. Q t ← Q t − 1 + s t 2 , a t + 1 ← max { 0 , a t + η s t } .
(g) Compute Γ t \Gamma_t Γ t by (20) and the distribution-free buffer F t ( δ c o v ) \mathcal{F}_t(\delta_{\mathrm{cov}}) F t ( δ cov ) by (21) .
(h) Append ( H t ( T ~ t ) , R t , C t , Δ t ) (H_t(\widetilde{T}_t),R_t,C_t,\Delta_t) ( H t ( T t ) , R t , C t , Δ t ) to D t − 1 \mathcal{D}_{t-1} D t − 1 to obtain D t \mathcal{D}_t D t .
end for
return issued bounds ( U t ) t = 1 T (U_t)_{t=1}^{T} ( U t ) t = 1 T and the final calibration states.
Algorithm 4. Censoring-Aware Budget Allocation
Input: Round t t t , context X t X_t X t , user runtime R t R_t R t , finite bound U t > 0 U_t > 0 U t > 0 , current quantile family q ^ t \widehat{q}_t q t , pre-run completion CDF F ^ t \widehat{F}_t F t ; α , τ max , η , a t , a i n i t , δ c o v , g min , C t a s k \alpha,\tau_{\max},\eta,a_t,a_{\mathrm{init}},\delta_{\mathrm{cov}},g_{\min},C_{\mathrm{task}} α , τ m a x , η , a t , a init , δ cov , g m i n , C task ; completed states ( A t − 1 ρ , L t − 1 , Q t − 1 , V ^ t − 1 ) (A^\rho_{t-1},L_{t-1},Q_{t-1},\widehat{V}_{t-1}) ( A t − 1 ρ , L t − 1 , Q t − 1 , V t − 1 ) and expected allocation S t − 1 = ∑ s < t π s d s S_{t-1}=\sum_{s<t}\pi_s d_s S t − 1 = ∑ s < t π s d s .
Input: Finite synthetic thresholds; an objective satisfying Assumption 10, with attained scalar minima.
Set u t ← ⌈ U t ⌉ u_t \leftarrow\lceil U_t\rceil u t ← ⌈ U t ⌉ and d t ← ( u t − R t ) + d_t \leftarrow(u_t-R_t)_+ d t ← ( u t − R t ) + . if d t = 0 d_t=0 d t = 0 then (a) return ( C t , π t , W t , d t ) = ( R t , 1 , 1 , 0 ) (C_t,\pi_t,W_t,d_t)=(R_t,1,1,0) ( C t , π t , W t , d t ) = ( R t , 1 , 1 , 0 ) . end if
Set π ‾ t ← min { 1 , ( t C t a s k − S t − 1 ) / d t } \overline{\pi}_t\leftarrow\min\{1,(tC_{\mathrm{task}}-S_{t-1})/d_t\} π t ← min { 1 , ( t C task − S t − 1 ) / d t } . if π ‾ t < g min \overline{\pi}_t<g_{\min} π t < g m i n then (a) return INFEASIBLE. end if
Set Π t a d d ← [ g min , π ‾ t ] \Pi_t^{\mathrm{add}}\leftarrow[g_{\min},\overline{\pi}_t] Π t add ← [ g m i n , π t ] and m ^ t ← 1 − F ^ t ( U t ) \widehat{m}_t\leftarrow1-\widehat{F}_t(U_t) m t ← 1 − F t ( U t ) ; hold ρ t ← m ^ t \rho_t\leftarrow\widehat{m}_t ρ t ← m t fixed for all candidates.
Define the following objective for each candidate π ∈ Π t a d d \pi\in\Pi_t^{\mathrm{add}} π ∈ Π t add , with W = 1 / π W=1/\pi W = 1/ π ; keep all input states fixed.
Under the synthetic law P ^ t , W \widehat{\mathbb{P}}_{t,W} P t , W , let T t ∗ ∼ F ^ t T_t^*\sim\widehat{F}_t T t ∗ ∼ F t and, independently, C t ∗ = R t + d t C_t^*=R_t+d_t C t ∗ = R t + d t with probability 1 / W 1/W 1/ W , and C t ∗ = R t C_t^*=R_t C t ∗ = R t otherwise. Set T ~ t ∗ = min { T t ∗ , C t ∗ } \widetilde{T}_t^*=\min\{T_t^*,C_t^*\} T t ∗ = min { T t ∗ , C t ∗ } , Δ t ∗ = 1 { T t ∗ ≤ C t ∗ } \Delta_t^*=\mathbf{1}\{T_t^*\le C_t^*\} Δ t ∗ = 1 { T t ∗ ≤ C t ∗ } , and Z t ∗ = ( C t ∗ , T ~ t ∗ , Δ t ∗ ) Z_t^*=(C_t^*,\widetilde{T}_t^*,\Delta_t^*) Z t ∗ = ( C t ∗ , T t ∗ , Δ t ∗ ) .
For a synthetic observation z = ( c , y , d ) z=(c,y,d) z = ( c , y , d ) , define
i z e r r ( v ) = 1 { ( y > v ) ∨ ( y = v ∧ d = 0 ) } , i z r e a c h ( v ) = 1 { c ≥ v } , i_z^{\mathrm{err}}(v)=\mathbf{1}\{(y>v)\vee(y=v\wedge d=0)\},\qquad i_z^{\mathrm{reach}}(v)=\mathbf{1}\{c\ge v\}, i z err ( v ) = 1 {( y > v ) ∨ ( y = v ∧ d = 0 )} , i z reach ( v ) = 1 { c ≥ v } , e ^ t ( W ; z ) = W i z e r r ( U t ) , b t ( z ) = sup { a ≥ 0 : i z e r r ( q ^ t ( X t ; τ max e − a ) ) = 1 } , \widehat{e}_t(W;z)=W i_z^{\mathrm{err}}(U_t),\qquad b_t(z)=\sup\{a\ge0:i_z^{\mathrm{err}}(\widehat{q}_t(X_t;\tau_{\max}e^{-a}))=1\}, e t ( W ; z ) = W i z err ( U t ) , b t ( z ) = sup { a ≥ 0 : i z err ( q t ( X t ; τ m a x e − a )) = 1 } , with sup ∅ = 0 \sup\varnothing=0 sup ∅ = 0 .
Form temporary candidate states with the fixed ρ t \rho_t ρ t :
s t ∗ ( W ; z ) = e ^ t ( W ; z ) + ρ t ( 1 − W i z r e a c h ( U t ) ) − α , s_t^*(W;z)=\widehat{e}_t(W;z)+\rho_t(1-Wi_z^{\mathrm{reach}}(U_t))-\alpha, s t ∗ ( W ; z ) = e t ( W ; z ) + ρ t ( 1 − W i z reach ( U t )) − α , A t ρ ( W ; z ) = A t − 1 ρ + ρ t ( 1 − W i z r e a c h ( U t ) ) , A_t^\rho(W;z)=A_{t-1}^\rho+\rho_t(1-Wi_z^{\mathrm{reach}}(U_t)), A t ρ ( W ; z ) = A t − 1 ρ + ρ t ( 1 − W i z reach ( U t )) , L t ( W ; z ) = L t − 1 + e ^ t ( W ; z ) b t ( z ) + a t ( ρ t − α ) + ( 1 − i z r e a c h ( U t ) ) , L_t(W;z)=L_{t-1}+\widehat{e}_t(W;z)b_t(z)+a_t(\rho_t-\alpha)+(1-i_z^{\mathrm{reach}}(U_t)), L t ( W ; z ) = L t − 1 + e t ( W ; z ) b t ( z ) + a t ( ρ t − α ) + ( 1 − i z reach ( U t )) , Q t ( W ; z ) = Q t − 1 + { s t ∗ ( W ; z ) } 2 , Q_t(W;z)=Q_{t-1}+\{s_t^*(W;z)\}^2, Q t ( W ; z ) = Q t − 1 + { s t ∗ ( W ; z ) } 2 , Γ t ( W ; z ) = − a i n i t + a i n i t 2 + η { 2 L t ( W ; z ) + η Q t ( W ; z ) } η . \Gamma_t(W;z)=\frac{-a_{\mathrm{init}}+\sqrt{a_{\mathrm{init}}^2+\eta\{2L_t(W;z)+\eta Q_t(W;z)\}}}{\eta}. Γ t ( W ; z ) = η − a init + a init 2 + η { 2 L t ( W ; z ) + η Q t ( W ; z )} . Compute the candidate model-based buffer:
V ^ t ( W ) = V ^ t − 1 + m ^ t W − m ^ t 2 , ζ ^ t ( δ c o v , W ) = 2 V ^ t ( W ) log 1 δ c o v + 1 3 log 1 δ c o v . \widehat{V}_t(W)=\widehat{V}_{t-1}+\widehat{m}_tW-\widehat{m}_t^2,\qquad
\widehat{\zeta}_t(\delta_{\mathrm{cov}},W)=\sqrt{2\widehat{V}_t(W)\log\frac{1}{\delta_{\mathrm{cov}}}+\frac{1}{3}\log\frac{1}{\delta_{\mathrm{cov}}}.} V t ( W ) = V t − 1 + m t W − m t 2 , ζ t ( δ cov , W ) = 2 V t ( W ) log δ cov 1 + 3 1 log δ cov 1 . Average over both synthetic draws:
E ‾ t ( W ) = 1 t E ^ t , W [ Γ t ( W ; Z t ∗ ) + ζ ^ t ( δ c o v , W ) − A t ρ ( W ; Z t ∗ ) ] . \overline{E}_t(W)=\frac{1}{t}\widehat{\mathbb{E}}_{t,W}\left[\Gamma_t(W;Z_t^*)+\widehat{\zeta}_t(\delta_{\mathrm{cov}},W)-A_t^\rho(W;Z_t^*)\right]. E t ( W ) = t 1 E t , W [ Γ t ( W ; Z t ∗ ) + ζ t ( δ cov , W ) − A t ρ ( W ; Z t ∗ ) ] . Select π t ← min arg min π ∈ Π t a d d E ‾ t ( 1 / π ) \pi_t\leftarrow\min\arg\min_{\pi\in\Pi_t^{\mathrm{add}}}\overline{E}_t(1/\pi) π t ← min arg min π ∈ Π t add E t ( 1/ π ) and set W t ← 1 / π t W_t\leftarrow1/\pi_t W t ← 1/ π t .
Draw C t = R t + d t C_t=R_t+d_t C t = R t + d t with probability π t \pi_t π t , and C t = R t C_t=R_t C t = R t otherwise, using fresh randomness conditionally independent of T t T_t T t given ( X t , R t , D t − 1 ) (X_t,R_t,D_{t-1}) ( X t , R t , D t − 1 ) ; record G t ( U t ) = π t G_t(U_t)=\pi_t G t ( U t ) = π t .
return ( C t , π t , W t , d t ) (C_t,\pi_t,W_t,d_t) ( C t , π t , W t , d t ) ; discard all synthetic states.
The synthetic expectation and V ^ t \widehat{V}_t V t in Algorithm 4 are working-model surrogates evaluated at the observed R t R_t R t , using the fixed pre-run CDF F ^ t \widehat{F}_t F t . They need not equal conditional moments given R t R_t R t . The coverage proofs use the distribution-free buffer (21) , and the budget proofs use only the feasible additional-cost ledger.
Algorithm 5 Full PROBE Algorithm
Input: T T T , 0 < α ≤ τ max ≤ 1 0 < \alpha\le\tau_{\max} \le1 0 < α ≤ τ m a x ≤ 1 with α < 1 \alpha< 1 α < 1 , η > 0 \eta> 0 η > 0 , δ c o v ∈ ( 0 , 1 ) \delta_{\mathrm{cov}} \in(0,1) δ cov ∈ ( 0 , 1 ) , g min ∈ ( 0 , 1 ] g_{\min} \in(0,1] g m i n ∈ ( 0 , 1 ] , C t a s k > 0 C_{\mathrm{task}} > 0 C task > 0 ; predictable upper-quantile families q ^ t \widehat{q}_t q t nonincreasing in τ \tau τ and completion CDFs F ^ t \widehat{F}_t F t , satisfying the manuscript’s quantile and allocator regularity assumptions, with 0 < U t 0 < U_t 0 < U t and 0 ≤ d t = ( ⌈ U t ⌉ − R t ) + ≤ d max < ∞ 0 \le d_t = (\lceil U_t\rceil- R_t)_+ \le d_{\max} < \infty 0 ≤ d t = (⌈ U t ⌉ − R t ) + ≤ d m a x < ∞ .
Initialize D 0 ← ∅ \mathcal{D}_0 \leftarrow\varnothing D 0 ← ∅ , a i n i t ← log ( τ max / α ) a_{\mathrm{init}} \leftarrow\log(\tau_{\max}/\alpha) a init ← log ( τ m a x / α ) , a 1 ← a i n i t a_1 \leftarrow a_{\mathrm{init}} a 1 ← a init , and A 0 p = L 0 = Q 0 = V ^ 0 = S 0 ← 0 A_0^p = L_0 = Q_0 = \widehat{V}_0 = S_0 \leftarrow0 A 0 p = L 0 = Q 0 = V 0 = S 0 ← 0 .
for t = 1 , … , T t = 1,\ldots,T t = 1 , … , T do
(a) Receive X t X_t X t and fix ( q ^ t , F ^ t ) (\widehat{q}_t,\widehat{F}_t) ( q t , F t ) using ( X t , D t − 1 ) (X_t,\mathcal{D}_{t-1}) ( X t , D t − 1 ) ; set τ t ← τ max e − a t \tau_t \leftarrow\tau_{\max}e^{-a_t} τ t ← τ m a x e − a t and issue U t ← q ^ t ( X t ; τ t ) U_t \leftarrow\widehat{q}_t(X_t;\tau_t) U t ← q t ( X t ; τ t ) ; set ρ t ← 1 − F ^ t ( U t ) \rho_t \leftarrow1-\widehat{F}_t(U_t) ρ t ← 1 − F t ( U t ) .
(b) Observe the user’s initial run of length R t R_t R t .
(c) Call Algorithm 4 with ( t , X t , R t , U t , q ^ t , F ^ t ) (t,X_t,R_t,U_t,\widehat{q}_t,\widehat{F}_t) ( t , X t , R t , U t , q t , F t ) , ( α , τ max , η , a t , a i n i t , δ c o v , g min , C t a s k ) (\alpha,\tau_{\max},\eta,a_t,a_{\mathrm{init}},\delta_{\mathrm{cov}},g_{\min},C_{\mathrm{task}}) ( α , τ m a x , η , a t , a init , δ cov , g m i n , C task ) , ( A t − 1 p , L t − 1 , Q t − 1 , V ^ t − 1 ) (A^p_{t-1},L_{t-1},Q_{t-1},\widehat{V}_{t-1}) ( A t − 1 p , L t − 1 , Q t − 1 , V t − 1 ) , and S t − 1 S_{t-1} S t − 1 .
if the allocator returns INFEASIBLE then
i. return the completed prefix and unchanged states; report incompatibility of budget and positivity at round t t t .
end if
(d) Receive ( C t , π t , W t , d t ) (C_t,\pi_t,W_t,d_t) ( C t , π t , W t , d t ) ; record G t ( U t ) = π t G_t(U_t)=\pi_t G t ( U t ) = π t . Continue any unfinished trajectory until the event or timeout and observe T ~ t = min { T t , C t } \widetilde{T}_t=\min\{T_t,C_t\} T t = min { T t , C t } , Δ t = 1 { T t ≤ C t } \Delta_t=1\{T_t\le C_t\} Δ t = 1 { T t ≤ C t } .
(e) Define, for any v v v ,
I t e r r ( v ) ← 1 { ( T ~ t > v ) ∨ ( T ~ t = v ∧ Δ t = 0 ) } , I_t^{\mathrm{err}}(v) \leftarrow1\{(\widetilde{T}_t>v)\lor(\widetilde{T}_t=v\land\Delta_t=0)\}, I t err ( v ) ← 1 {( T t > v ) ∨ ( T t = v ∧ Δ t = 0 )} , I t r e a c h ( v ) ← 1 { C t ≥ v } . I_t^{\mathrm{reach}}(v) \leftarrow1\{C_t\ge v\}. I t reach ( v ) ← 1 { C t ≥ v } . (f) Compute
e ^ t ← W t I t e r r ( U t ) , b t ← sup { a ≥ 0 : I t e r r ( q ^ t ( X t ; τ max e − a ) ) = 1 } , sup ∅ = 0. \widehat{e}_t \leftarrow W_t I_t^{\mathrm{err}}(U_t), \qquad b_t \leftarrow\sup\{a\ge0:I_t^{\mathrm{err}}(\widehat{q}_t(X_t;\tau_{\max}e^{-a}))=1\}, \qquad\sup\varnothing=0. e t ← W t I t err ( U t ) , b t ← sup { a ≥ 0 : I t err ( q t ( X t ; τ m a x e − a )) = 1 } , sup ∅ = 0. (g) Commit the realized calibration and allocation states:
e ~ t ← e ^ t + ρ t ( 1 − I t r e a c h ( U t ) / G t ( U t ) ) , s t ← e ~ t − α , \widetilde{e}_t \leftarrow\widehat{e}_t+\rho_t(1-I_t^{\mathrm{reach}}(U_t)/G_t(U_t)), \qquad s_t \leftarrow\widetilde{e}_t-\alpha, e t ← e t + ρ t ( 1 − I t reach ( U t ) / G t ( U t )) , s t ← e t − α , A t p ← A t − 1 p + ρ t ( 1 − I t r e a c h ( U t ) / G t ( U t ) ) , L t ← L t − 1 + e ^ t b t + a t ( ρ t − α ) + ( 1 − I t r e a c h ( U t ) ) , A_t^p \leftarrow A_{t-1}^p+\rho_t(1-I_t^{\mathrm{reach}}(U_t)/G_t(U_t)), \qquad L_t \leftarrow L_{t-1}+\widehat{e}_tb_t+a_t(\rho_t-\alpha)+(1-I_t^{\mathrm{reach}}(U_t)), A t p ← A t − 1 p + ρ t ( 1 − I t reach ( U t ) / G t ( U t )) , L t ← L t − 1 + e t b t + a t ( ρ t − α ) + ( 1 − I t reach ( U t )) , Q t ← Q t − 1 + s t 2 , a t + 1 ← max { 0 , a t + η s t } , Q_t \leftarrow Q_{t-1}+s_t^2, \qquad a_{t+1}\leftarrow\max\{0,a_t+\eta s_t\}, Q t ← Q t − 1 + s t 2 , a t + 1 ← max { 0 , a t + η s t } , m ^ t ← ρ t , S t ← S t − 1 + π t d t , \widehat{m}_t\leftarrow\rho_t, \qquad S_t\leftarrow S_{t-1}+\pi_td_t, m t ← ρ t , S t ← S t − 1 + π t d t , V ^ t ← V ^ t − 1 + m ^ t W t − m ^ t 2 . \widehat{V}_t\leftarrow\widehat{V}_{t-1}+\widehat{m}_tW_t-\widehat{m}_t^2. V t ← V t − 1 + m t W t − m t 2 . (h) Compute Γ t \Gamma_t Γ t by (20) and F t ( δ c o v ) \mathcal{F}_t(\delta_{\mathrm{cov}}) F t ( δ cov ) by (21) .
(i) Append ( H t ( T ~ t ) , R t , C t , Δ t ) (H_t(\widetilde{T}_t),R_t,C_t,\Delta_t) ( H t ( T t ) , R t , C t , Δ t ) to D t − 1 \mathcal{D}_{t-1} D t − 1 to obtain D t \mathcal{D}_t D t ; only then update models for future rounds.
end for
return issued bounds ( U t ) t = 1 T (U_t)_{t=1}^T ( U t ) t = 1 T and the final states.
Theory
Proof of Theorem 3: Coverage Validity
Theorem 3 (Coverage validity, informal). Under Assumptions 1, 2, and 5, PROBE (13)–(17) satisfies, for every fixed T T T and δ c o v ∈ ( 0 , 1 ) \delta_{\mathrm{cov}} \in(0,1) δ cov ∈ ( 0 , 1 ) , with probability at least 1 − δ c o v 1-\delta_{\mathrm{cov}} 1 − δ cov over D T \mathcal{D}_T D T
1 T ∑ t = 1 T P ( T t ≤ U t ∣ X t , D t − 1 ) ≥ 1 − α + 1 T [ A T P − Γ T − ς ~ T ( δ c o v ) ] . (30) \frac{1}{T}\sum_{t=1}^{T}\mathbb{P}(T_t \le U_t \mid X_t,\mathcal{D}_{t-1})
\ge1-\alpha+\frac{1}{T}\left[A_T^{\mathsf{P}}-\Gamma_T-\widetilde{\varsigma}_T(\delta_{\mathrm{cov}})\right]. \tag*{(30)} T 1 t = 1 ∑ T P ( T t ≤ U t ∣ X t , D t − 1 ) ≥ 1 − α + T 1 [ A T P − Γ T − ς T ( δ cov ) ] . (30)
Assumption 5 (Quantile and threshold regularity). For every t t t and x x x , the map τ ↦ q ^ t ( x ; τ ) \tau\mapsto\widehat{q}_t(x;\tau) τ ↦ q t ( x ; τ ) is nonincreasing on ( 0 , τ max ] (0,\tau_{\max}] ( 0 , τ m a x ] . The threshold b t b_t b t in (18) , with sup ∅ = 0 \sup\varnothing=0 sup ∅ = 0 , is finite on every played round.
Observable history and information timing. The observed history is
D t − 1 = { H s ( T ~ s ) , R s , C s , Δ s } s < t . \mathcal{D}_{t-1}=\left\{H_s(\widetilde{T}_s),R_s,C_s,\Delta_s\right\}_{s<t}. D t − 1 = { H s ( T s ) , R s , C s , Δ s } s < t .
We take initialization, fitted prediction rules, predictable completion models, and tie-breaking rules as fixed. Every completed calibration and allocation state is therefore a measurable function of this history. Let P s e q \mathbb{P}_{\mathrm{seq}} P seq and E s e q \mathbb{E}_{\mathrm{seq}} E seq denote probability and expectation under the full sequential law, including task, environment, and algorithmic randomness. Define the completed-round and prediction-time information by
F t − 1 = σ ( D t − 1 ) , P t = σ ( F t − 1 , X t ) , \mathcal{F}_{t-1}=\sigma(\mathcal{D}_{t-1}),\qquad\mathcal{P}_t=\sigma(\mathcal{F}_{t-1},X_t), F t − 1 = σ ( D t − 1 ) , P t = σ ( F t − 1 , X t ) ,
with F 0 \mathcal{F}_0 F 0 trivial. By the main-text predictability convention, U t U_t U t , F ^ t \widehat{F}_t F t , and ρ t \rho_t ρ t are P t \mathcal{P}_t P t -measurable and fixed before the user run. The committed censoring law may also depend on the subsequently observed runtime R t R_t R t . Let G t \mathcal{G}_t G t denote the information after committing this law but before revealing its fresh randomization or continuing the trajectory. Thus, up to completion under P s e q \mathbb{P}_{\mathrm{seq}} P seq ,
G t = σ ( P t , R t ) = σ ( X t , R t , D t − 1 ) . \mathcal{G}_t=\sigma(\mathcal{P}_t,R_t)=\sigma(X_t,R_t,\mathcal{D}_{t-1}). G t = σ ( P t , R t ) = σ ( X t , R t , D t − 1 ) .
For the two-point allocator, π t \pi_t π t , u t u_t u t , and d t d_t d t are already measurable at this time. After observing the censored trajectory, set
D t = { H s ( T ~ s ) , R s , C s , Δ s } s ≤ t , F t = σ ( G t , H t ( T ~ t ) , R t , C t , Δ t ) = σ ( D t ) . \mathcal{D}_t=\left\{H_s(\widetilde{T}_s),R_s,C_s,\Delta_s\right\}_{s\le t},\qquad
\mathcal{F}_t=\sigma\left(\mathcal{G}_t,H_t(\widetilde{T}_t),R_t,C_t,\Delta_t\right)=\sigma(\mathcal{D}_t). D t = { H s ( T s ) , R s , C s , Δ s } s ≤ t , F t = σ ( G t , H t ( T t ) , R t , C t , Δ t ) = σ ( D t ) .
The information flow is
F t − 1 ⊆ P t ⊆ G t ⊆ F t . (31) \mathcal{F}_{t-1}\subseteq\mathcal{P}_t\subseteq\mathcal{G}_t\subseteq\mathcal{F}_t. \tag*{(31)} F t − 1 ⊆ P t ⊆ G t ⊆ F t . (31)
We use the conditional operators
P t ( ⋅ ) = P s e q ( ⋅ ∣ G t ) , E t [ ⋅ ] = E s e q [ ⋅ ∣ G t ] , G t ( u ) = P t ( C t ≥ u ) . (32) \mathbb{P}_t(\cdot)=\mathbb{P}_{\mathrm{seq}}(\cdot\mid\mathcal{G}_t),\qquad
\mathbb{E}_t[\cdot]=\mathbb{E}_{\mathrm{seq}}[\cdot\mid\mathcal{G}_t],\qquad
G_t(u)=\mathbb{P}_t(C_t\ge u). \tag*{(32)} P t ( ⋅ ) = P seq ( ⋅ ∣ G t ) , E t [ ⋅ ] = E seq [ ⋅ ∣ G t ] , G t ( u ) = P t ( C t ≥ u ) . (32)
In particular, E t [ Z ] = E [ Z ∣ X t , R t , D t − 1 ] \mathbb{E}_t[Z] = \mathbb{E}[Z \mid X_t, R_t, D_{t-1}] E t [ Z ] = E [ Z ∣ X t , R t , D t − 1 ] for every integrable Z Z Z . Distinguish the allocation-time miscoverage probability m t R = P t ( T t > U t ) m_t^R = \mathbb{P}_t(T_t > U_t) m t R = P t ( T t > U t ) from the prediction-time target m t = P ( T t > U t ∣ P t ) m_t = \mathbb{P}(T_t > U_t \mid\mathcal{P}_t) m t = P ( T t > U t ∣ P t ) in the main text. The tower property gives E [ m t R ∣ P t ] = m t \mathbb{E}[m_t^R \mid\mathcal{P}_t] = m_t E [ m t R ∣ P t ] = m t ; no independence between R t R_t R t and T t T_t T t is assumed.
The potential event time T t T_t T t is defined under the fixed agent–environment policy without the evaluator timeout. The timeout only truncates observation and does not alter that policy. Conditional on G t \mathcal{G}_t G t , fresh randomization samples C t C_t C t independently of T t T_t T t from the known survival function G t G_t G t , as required by Assumption 1. Assumption 2 ensures that G t ( U t ) ≥ g min G_t(U_t) \ge g_{\min} G t ( U t ) ≥ g m i n . The completion-based correction ρ t = 1 − F ^ t ( U t ) ∈ [ 0 , 1 ] \rho_t = 1 - \widehat{F}_t(U_t) \in[0,1] ρ t = 1 − F t ( U t ) ∈ [ 0 , 1 ] is P t \mathcal{P}_t P t -measurable before the censoring draw. Since E t [ I t r e a c h ( U t ) ] = G t ( U t ) \mathbb{E}_t[I_t^{\mathrm{reach}}(U_t)] = G_t(U_t) E t [ I t reach ( U t )] = G t ( U t ) , the centered correction ρ t { 1 − I t r e a c h ( U t ) / G t ( U t ) } \rho_t\{1 - I_t^{\mathrm{reach}}(U_t)/G_t(U_t)\} ρ t { 1 − I t reach ( U t ) / G t ( U t )} has conditional mean zero. The tower property gives mean zero conditional on P t \mathcal{P}_t P t as well. No independence across tasks, stationarity, or exchangeability is required.
Variance of the correction. For a fixed allocation rule, write w t = G t ( U t ) − 1 − 1 w_t = G_t(U_t)^{-1} - 1 w t = G t ( U t ) − 1 − 1 . The part of Var ( e ~ t ∣ P t ) \operatorname{Var}(\widetilde{e}_t \mid\mathcal{P}_t) Var ( e t ∣ P t ) depending on a P t \mathcal{P}_t P t -measurable ρ t \rho_t ρ t is E [ w t ( ρ t 2 − 2 ρ t m t R ) ∣ P t ] \mathbb{E}[w_t(\rho_t^2 - 2\rho_t m_t^R) \mid\mathcal{P}_t] E [ w t ( ρ t 2 − 2 ρ t m t R ) ∣ P t ] . Thus its minimizer is
ρ t ∗ = E [ w t m t R ∣ P t ] E [ w t ∣ P t ] . \rho_t^* = \frac{\mathbb{E}[w_t m_t^R \mid\mathcal{P}_t]}{\mathbb{E}[w_t \mid\mathcal{P}_t]}. ρ t ∗ = E [ w t ∣ P t ] E [ w t m t R ∣ P t ] .
when the denominator is positive; otherwise every ρ t ∈ [ 0 , 1 ] \rho_t \in[0,1] ρ t ∈ [ 0 , 1 ] gives the same variance. In particular, ρ t = m t \rho_t = m_t ρ t = m t is optimal when G t ( U t ) G_t(U_t) G t ( U t ) is P t \mathcal{P}_t P t -measurable. If the propensity depends on informative R t R_t R t , this choice need not be optimal, but unbiasedness is unchanged.
Proof of Theorem 3. We first establish the pathwise calibration bound and then transfer it to conditional miscoverage.
Lemma 6 (Threshold implication). Under Assumption 5,
I t e r r ( U t ) = 1 ⟹ a t ≤ b t . I_t^{\mathrm{err}}(U_t) = 1 \quad\Longrightarrow\quad a_t \le b_t. I t err ( U t ) = 1 ⟹ a t ≤ b t . Derivation. When I t e r r ( U t ) = 1 I_t^{\mathrm{err}}(U_t) = 1 I t err ( U t ) = 1 , substituting U t = q ^ t ( X t ; τ max e − a t ) U_t = \widehat{q}_t(X_t; \tau_{\max}e^{-a_t}) U t = q t ( X t ; τ m a x e − a t ) shows that a t a_t a t belongs to the set whose supremum defines b t b_t b t . Hence a t ≤ b t a_t \le b_t a t ≤ b t . The empty-set convention is relevant only when the premise is false.
Lemma 7 (Compatibility of the corrected signal). Under Assumptions 5 and 2, for every predictable ρ t ∈ [ 0 , 1 ] \rho_t \in[0,1] ρ t ∈ [ 0 , 1 ] ,
a t s t ≤ e ^ t b t + a t ( ρ t − α ) + ( 1 − I t r e a c h ( U t ) ) . (33) a_t s_t \le\widehat{e}_t b_t + a_t(\rho_t - \alpha)_+ (1 - I_t^{\mathrm{reach}}(U_t)). \tag*{(33)} a t s t ≤ e t b t + a t ( ρ t − α ) + ( 1 − I t reach ( U t )) . (33) Derivation. On I t r e a c h ( U t ) = 0 I_t^{\mathrm{reach}}(U_t) = 0 I t reach ( U t ) = 0 , the observed error indicator vanishes and s t = ρ t − α s_t = \rho_t - \alpha s t = ρ t − α , hence a t s t ≤ a t ( ρ t − α ) + a_t s_t \le a_t(\rho_t - \alpha)_+ a t s t ≤ a t ( ρ t − α ) + . On I t r e a c h ( U t ) = 1 I_t^{\mathrm{reach}}(U_t) = 1 I t reach ( U t ) = 1 with I t e r r ( U t ) = 0 I_t^{\mathrm{err}}(U_t) = 0 I t err ( U t ) = 0 , we have s t = − α − ρ t ( 1 − G t ( U t ) ) / G t ( U t ) ≤ 0 s_t = -\alpha- \rho_t(1 - G_t(U_t))/G_t(U_t) \le0 s t = − α − ρ t ( 1 − G t ( U t )) / G t ( U t ) ≤ 0 . On I t r e a c h ( U t ) = 1 I_t^{\mathrm{reach}}(U_t) = 1 I t reach ( U t ) = 1 with I t e r r ( U t ) = 1 I_t^{\mathrm{err}}(U_t) = 1 I t err ( U t ) = 1 , Lemma 6 gives a t ≤ b t a_t \le b_t a t ≤ b t ; because ρ t ( 1 − I t r e a c h ( U t ) / G t ( U t ) ) ≤ 0 \rho_t(1 - I_t^{\mathrm{reach}}(U_t)/G_t(U_t)) \le0 ρ t ( 1 − I t reach ( U t ) / G t ( U t )) ≤ 0 , we obtain a t s t ≤ a t e ^ t ≤ e ^ t b t a_t s_t \le a_t\widehat{e}_t \le\widehat{e}_t b_t a t s t ≤ a t e t ≤ e t b t .
These cases exhaust all outcomes, and the right-hand side in (32) is nonnegative.
Lemma 8 (Projected-OGD regret). For every comparator a ≥ 0 a \ge0 a ≥ 0 , the update in (17) satisfies
∑ t = 1 T s t ( a − a t ) ≤ ( a − a i n i t ) 2 2 η + η 2 Q T , Q T = ∑ t = 1 T ( s t ) 2 , Q 0 = 0. (34) \sum_{t=1}^{T} s_t(a-a_t) \le\frac{(a-a_{\mathrm{init}})^2}{2\eta}+\frac{\eta}{2}Q_T,\qquad Q_T=\sum_{t=1}^{T}(s_t)^2,\qquad Q_0=0. \tag*{(34)} t = 1 ∑ T s t ( a − a t ) ≤ 2 η ( a − a init ) 2 + 2 η Q T , Q T = t = 1 ∑ T ( s t ) 2 , Q 0 = 0. (34) Derivation. Projection onto [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) is nonexpansive. Consequently,
( a t + 1 − a ) 2 ≤ ( a t + η s t − a ) 2 . (a_{t+1}-a)^2\le(a_t+\eta s_t-a)^2. ( a t + 1 − a ) 2 ≤ ( a t + η s t − a ) 2 . Expanding and rearranging gives
s t ( a − a t ) ≤ ( a t − a ) 2 − ( a t + 1 − a ) 2 2 η + η 2 ( s t ) 2 . s_t(a-a_t)\le\frac{(a_t-a)^2-(a_{t+1}-a)^2}{2\eta}+\frac{\eta}{2}(s_t)^2. s t ( a − a t ) ≤ 2 η ( a t − a ) 2 − ( a t + 1 − a ) 2 + 2 η ( s t ) 2 . Summation telescopes the distance terms; dropping the nonpositive terminal distance and using a 1 = a i n i t a_1=a_{\mathrm{init}} a 1 = a init proves (33).
Proposition 9 (Observable surrogate envelope). Let
L T = ∑ t = 1 T { e ^ t b t + a t ( ρ t − α ) + ( 1 − I t r e a c h ( U t ) ) } , L 0 = 0 , L_T=\sum_{t=1}^{T}\{\hat e_t b_t+a_t(\rho_t-\alpha)+(1-I_t^{\mathrm{reach}}(U_t))\},\qquad L_0=0, L T = t = 1 ∑ T { e ^ t b t + a t ( ρ t − α ) + ( 1 − I t reach ( U t ))} , L 0 = 0 , A T ρ = ∑ t = 1 T ρ t ( 1 − I t r e a c h ( U t ) / G t ( U t ) ) , A 0 ρ = 0. A_T^\rho=\sum_{t=1}^{T}\rho_t(1-I_t^{\mathrm{reach}}(U_t)/G_t(U_t)),\qquad A_0^\rho=0. A T ρ = t = 1 ∑ T ρ t ( 1 − I t reach ( U t ) / G t ( U t )) , A 0 ρ = 0. Then, pathwise,
∑ t = 1 T ( e ^ t − α ) ≤ Γ T − A T ρ . (35) \sum_{t=1}^{T}(\hat e_t-\alpha)\le\Gamma_T-A_T^\rho. \tag*{(35)} t = 1 ∑ T ( e ^ t − α ) ≤ Γ T − A T ρ . (35) where Γ T \Gamma_T Γ T is defined in (26) .
Derivation. Write S T c a l = ∑ t = 1 T s t S_T^{\mathrm{cal}}=\sum_{t=1}^{T}s_t S T cal = ∑ t = 1 T s t and define the regret envelope
R T ( a ) = ( a − a i n i t ) 2 2 η + η 2 Q T , a ≥ 0. \mathcal{R}_T(a)=\frac{(a-a_{\mathrm{init}})^2}{2\eta}+\frac{\eta}{2}Q_T,\qquad a\ge0. R T ( a ) = 2 η ( a − a init ) 2 + 2 η Q T , a ≥ 0. Expanding (33), taking the supremum over a ≥ 0 a\ge0 a ≥ 0 , and applying Lemma 7 yields the Fenchel reduction
R T ∗ ( S T c a l ) ≤ ∑ t = 1 T a t s t ≤ L T . \mathcal{R}_T^*(S_T^{\mathrm{cal}})\le\sum_{t=1}^{T}a_t s_t\le L_T. R T ∗ ( S T cal ) ≤ t = 1 ∑ T a t s t ≤ L T . The conjugate over the half-line is
R T ∗ ( z ) = { a i n i t z + η z 2 2 − η 2 Q T , z ≥ − a i n i t / η , − a i n i t 2 2 η − η 2 Q T , z < − a i n i t / η . \mathcal{R}_T^*(z)=
\begin{cases}
a_{\mathrm{init}}z+\dfrac{\eta z^2}{2}-\dfrac{\eta}{2}Q_T, & z\ge-a_{\mathrm{init}}/\eta,\\
-\dfrac{a_{\mathrm{init}}^2}{2\eta}-\dfrac{\eta}{2}Q_T, & z<-a_{\mathrm{init}}/\eta.
\end{cases} R T ∗ ( z ) = ⎩ ⎨ ⎧ a init z + 2 η z 2 − 2 η Q T , − 2 η a init 2 − 2 η Q T , z ≥ − a init / η , z < − a init / η . If S T c a l ≤ 0 S_T^{\mathrm{cal}}\le0 S T cal ≤ 0 , its asserted upper bound is immediate. Otherwise the first branch applies, so
η ( S T c a l ) 2 + 2 a i n i t S T c a l − ( 2 L T + η Q T ) ≤ 0. \eta(S_T^{\mathrm{cal}})^2+2a_{\mathrm{init}}S_T^{\mathrm{cal}}-(2L_T+\eta Q_T)\le0. η ( S T cal ) 2 + 2 a init S T cal − ( 2 L T + η Q T ) ≤ 0.
Solving this quadratic inequality gives S T c a l ≤ Γ T S_T^{\mathrm{cal}} \le\Gamma_T S T cal ≤ Γ T . Finally,
S T c a l = ∑ t = 1 T ( e ^ t − α ) + A T P , S_T^{\mathrm{cal}} = \sum_{t=1}^{T}(\hat{e}_t-\alpha)+A_T^P, S T cal = t = 1 ∑ T ( e ^ t − α ) + A T P ,
which proves (34).
IPCW moments and concentration. The boundary convention T ~ t = min { T t , C t } \widetilde{T}_t=\min\{T_t,C_t\} T t = min { T t , C t } and Δ t = 1 { T t ≤ C t } \Delta_t=1\{T_t\le C_t\} Δ t = 1 { T t ≤ C t } gives
I t e r r ( U t ) = 1 { T t > U t , C t ≥ U t } . I_t^{\mathrm{err}}(U_t)=1\{T_t>U_t,\ C_t\ge U_t\}. I t err ( U t ) = 1 { T t > U t , C t ≥ U t } .
Indeed, T ~ t > U t \widetilde{T}_t>U_t T t > U t certifies both inequalities, while T ~ t = U t \widetilde{T}_t=U_t T t = U t and Δ t = 0 \Delta_t=0 Δ t = 0 certifies C t = U t < T t C_t=U_t<T_t C t = U t < T t . Conversely, T t > U t T_t>U_t T t > U t and C t ≥ U t C_t\ge U_t C t ≥ U t give one of these two observed cases. Conditional independence therefore yields E t [ I t e r r ( U t ) ] = m t R G t ( U t ) \mathbb{E}_t[I_t^{\mathrm{err}}(U_t)]=m_t^R G_t(U_t) E t [ I t err ( U t )] = m t R G t ( U t ) . Since the indicator is binary and e ^ t = I t e r r ( U t ) / G t ( U t ) \hat{e}_t=I_t^{\mathrm{err}}(U_t)/G_t(U_t) e ^ t = I t err ( U t ) / G t ( U t ) , positivity gives
E t [ e ^ t ] = m t R , E t [ e ^ t 2 ] = m t R G t ( U t ) ≤ 1 g min , 0 ≤ e ^ t ≤ 1 g min . (36) \mathbb{E}_t[\hat{e}_t]=m_t^R,\qquad\mathbb{E}_t[\hat{e}_t^2]=\frac{m_t^R}{G_t(U_t)}\le\frac{1}{g_{\min}},\qquad0\le\hat{e}_t\le\frac{1}{g_{\min}}. \tag*{(36)} E t [ e ^ t ] = m t R , E t [ e ^ t 2 ] = G t ( U t ) m t R ≤ g m i n 1 , 0 ≤ e ^ t ≤ g m i n 1 . (36)
Conditioning these identities back on prediction-time information gives
E [ e ^ t ∣ P t ] = m t , E [ e ^ t 2 ∣ P t ] = E [ m t R G t ( U t ) ∣ P t ] ≤ 1 g min . \mathbb{E}[\hat{e}_t\mid\mathcal{P}_t]=m_t,\qquad\mathbb{E}[\hat{e}_t^2\mid\mathcal{P}_t]=\mathbb{E}\left[\left.\frac{m_t^R}{G_t(U_t)}\right|\mathcal{P}_t\right]\le\frac{1}{g_{\min}}. E [ e ^ t ∣ P t ] = m t , E [ e ^ t 2 ∣ P t ] = E [ G t ( U t ) m t R P t ] ≤ g m i n 1 .
Together with the centered-correction identity, this also proves E [ e ~ t ∣ P t ] = m t \mathbb{E}[\widetilde{e}_t\mid\mathcal{P}_t]=m_t E [ e t ∣ P t ] = m t . Let ξ t = e ^ t − m t \xi_t=\hat{e}_t-m_t ξ t = e ^ t − m t . Then E [ ξ t ∣ P t ] = 0 \mathbb{E}[\xi_t\mid\mathcal{P}_t]=0 E [ ξ t ∣ P t ] = 0 and
E [ ξ t 2 ∣ P t ] = E [ m t R G t ( U t ) ∣ P t ] − m t 2 ≤ 1 g min . (37) \mathbb{E}[\xi_t^2\mid\mathcal{P}_t]=\mathbb{E}\left[\left.\frac{m_t^R}{G_t(U_t)}\right|\mathcal{P}_t\right]-m_t^2\le\frac{1}{g_{\min}}. \tag*{(37)} E [ ξ t 2 ∣ P t ] = E [ G t ( U t ) m t R P t ] − m t 2 ≤ g m i n 1 . (37)
These variances sum to V T V_T V T as defined in the main text. For the filtration H 2 t − 1 = P t \mathcal{H}_{2t-1}=\mathcal{P}_t H 2 t − 1 = P t , H 2 t = F t \mathcal{H}_{2t}=\mathcal{F}_t H 2 t = F t , with H 0 = F 0 \mathcal{H}_0=\mathcal{F}_0 H 0 = F 0 , inserting zero increments at odd indices makes ξ t \xi_t ξ t the even martingale difference.
Set ε t = − ξ t = m t − e ^ t \varepsilon_t=-\xi_t=m_t-\hat{e}_t ε t = − ξ t = m t − e ^ t . For every λ ≥ 0 \lambda\ge0 λ ≥ 0 , the inequalities e − x ≤ 1 − x + x 2 / 2 e^{-x}\le1-x+x^2/2 e − x ≤ 1 − x + x 2 /2 for x ≥ 0 x\ge0 x ≥ 0 and 1 + y ≤ e y 1+y\le e^y 1 + y ≤ e y imply
E [ e λ ε t ∣ P t ] ≤ e λ m t ( 1 − λ m t + λ 2 2 E [ e ^ t 2 ∣ P t ] ) ≤ exp ( λ 2 2 g min ) . \mathbb{E}[e^{\lambda\varepsilon_t}\mid\mathcal{P}_t]\le e^{\lambda m_t}\left(1-\lambda m_t+\frac{\lambda^2}{2}\mathbb{E}[\hat{e}_t^2\mid\mathcal{P}_t]\right)
\le\exp\left(\frac{\lambda^2}{2g_{\min}}\right). E [ e λ ε t ∣ P t ] ≤ e λ m t ( 1 − λ m t + 2 λ 2 E [ e ^ t 2 ∣ P t ] ) ≤ exp ( 2 g m i n λ 2 ) .
Iterated conditioning along (30) gives
E s e q [ exp ( λ ∑ t = 1 T ε t ) ] ≤ exp ( T λ 2 2 g min ) . \mathbb{E}_{\mathrm{seq}}\left[\exp\left(\lambda\sum_{t=1}^{T}\varepsilon_t\right)\right]\le\exp\left(\frac{T\lambda^2}{2g_{\min}}\right). E seq [ exp ( λ t = 1 ∑ T ε t ) ] ≤ exp ( 2 g m i n T λ 2 ) .
Exponential Markov inequality, optimized over λ ≥ 0 \lambda\ge0 λ ≥ 0 , therefore gives
P s e q ( ∑ t = 1 T ε t > 2 T g min log 1 δ ) ≤ δ . (38) \mathbb{P}_{\mathrm{seq}}\left(\sum_{t=1}^{T}\varepsilon_t>\sqrt{\frac{2T}{g_{\min}}\log\frac{1}{\delta}}\right)\le\delta. \tag*{(38)} P seq ( t = 1 ∑ T ε t > g m i n 2 T log δ 1 ) ≤ δ . (38)
In particular, with probability at least 1 − δ 1-\delta 1 − δ ,
− ∑ t = 1 T ξ t ≤ 2 T g min log 1 δ + 1 3 log 1 δ = F T ( δ ) . (39) -\sum_{t=1}^{T}\xi_t \le\sqrt{\frac{2T}{g_{\min}}\log\frac{1}{\delta}}+\frac{1}{3}\log\frac{1}{\delta}=\mathcal{F}_T(\delta). \tag*{(39)} − t = 1 ∑ T ξ t ≤ g m i n 2 T log δ 1 + 3 1 log δ 1 = F T ( δ ) . (39)
The elementary exponential-moment calculation thus implies the confidence buffer used in the main statement.
Coverage conclusion. The basic decomposition is
∑ t = 1 T ( m t − α ) = ∑ t = 1 T ( e ^ t − α ) − ∑ t = 1 T ξ t . \sum_{t=1}^{T}(m_t-\alpha)=\sum_{t=1}^{T}(\widehat{e}_t-\alpha)-\sum_{t=1}^{T}\xi_t. t = 1 ∑ T ( m t − α ) = t = 1 ∑ T ( e t − α ) − t = 1 ∑ T ξ t .
Combining Proposition 9 with (39) gives, with probability at least 1 − δ c o v 1-\delta_{\mathrm{cov}} 1 − δ cov ,
∑ t = 1 T ( m t − α ) ≤ Γ T − A T ρ + F T ( δ c o v ) . \sum_{t=1}^{T}(m_t-\alpha)\le\Gamma_T-A_T^{\rho}+\mathcal{F}_T(\delta_{\mathrm{cov}}). t = 1 ∑ T ( m t − α ) ≤ Γ T − A T ρ + F T ( δ cov ) .
Because P ( T t ≤ U t ∣ P t ) = 1 − m t \mathbb{P}(T_t\le U_t\mid\mathcal{P}_t)=1-m_t P ( T t ≤ U t ∣ P t ) = 1 − m t , rearranging proves (27).
The certificate bounds average conditional coverage using the observed calibration envelope and signed centered correction, with a distribution-free confidence buffer. Terminal cancellation is not required for this residual bound.
Proof of Theorem 4: Expected-Budget Validity
Theorem 4 (Budget validity, informal). Under Assumptions 1, 2, and 10, PROBE (Algorithm 5) satisfies, for every fixed horizon T T T ,
1 T ∑ t = 1 T E [ ( T ~ t − R t ) + ] ≤ C t a s k . (40) \frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[(\widetilde{T}_t-R_t)_+]\le C_{\mathrm{task}}. \tag*{(40)} T 1 t = 1 ∑ T E [( T t − R t ) + ] ≤ C task . (40)
Assumption 10 (Budget and allocator regularity). The requested additional runtimes satisfy 0 ≤ d t = ( u t − R t ) + ≤ d max < ∞ 0\le d_t=(u_t-R_t)_+\le d_{\max}<\infty 0 ≤ d t = ( u t − R t ) + ≤ d m a x < ∞ , where u t = ⌈ U t ⌉ u_t=\lceil U_t\rceil u t = ⌈ U t ⌉ . For each fixed horizon T T T under consideration, the feasible interval Π t a d d \Pi_t^{\mathrm{add}} Π t add in (29) is nonempty almost surely at every round t = 1 , … , T t=1,\ldots,T t = 1 , … , T . The condition C t a s k ≥ g min d max C_{\mathrm{task}}\ge g_{\min}d_{\max} C task ≥ g m i n d m a x suffices inductively. The completion model F ^ t \widehat{F}_t F t is a right-continuous distribution function measurable with respect to ( X t , D t − 1 ) (X_t,D_{t-1}) ( X t , D t − 1 ) , before the user run. The objective in (24) is jointly measurable, lower semicontinuous in π \pi π on the compact feasible interval, and finite at a feasible point, with a fixed measurable tie-breaking rule.
Proof of Theorem 4.
Proposition 11 (Predictable validity of the selected law). Under Assumption 10, minimizing (24) over Π t a d d \Pi_t^{\mathrm{add}} Π t add , with the zero-demand convention in Algorithm 4, yields a G t \mathcal{G}_t G t -measurable allocation probability. If its Bernoulli draw is fresh and conditionally independent of T t T_t T t , then
E t [ T ~ t − R t ] ≤ E t [ C t − R t ] = π t d t , ∑ s = 1 t π s d s ≤ t C t a s k , G t ( U t ) = π t ≥ g min , \mathbb{E}_t[\widetilde{T}_t-R_t]\le\mathbb{E}_t[C_t-R_t]=\pi_t d_t,\qquad\sum_{s=1}^{t}\pi_s d_s\le tC_{\mathrm{task}},\qquad G_t(U_t)=\pi_t\ge g_{\min}, E t [ T t − R t ] ≤ E t [ C t − R t ] = π t d t , s = 1 ∑ t π s d s ≤ t C task , G t ( U t ) = π t ≥ g m i n ,
and C t ⊥ T t ∣ G t C_t \perp T_t \mid\mathcal{G}_t C t ⊥ T t ∣ G t .
Derivation. The past sum ∑ s < t π s d s \sum_{s<t}\pi_s d_s ∑ s < t π s d s , R t R_t R t , and d t d_t d t are G t \mathcal{G}_t G t -measurable. On { d t > 0 } \{d_t>0\} { d t > 0 } ,
π ‾ t = min { 1 , t C t a s k − ∑ s < t π s d s d t } \overline{\pi}_t=\min\left\{1,\frac{tC_{\mathrm{task}}-\sum_{s<t}\pi_s d_s}{d_t}\right\} π t = min { 1 , d t t C task − ∑ s < t π s d s }
is measurable and Π t a d d = [ g min , π ‾ t ] \Pi_t^{\mathrm{add}}=[g_{\min},\overline{\pi}_t] Π t add = [ g m i n , π t ] is a nonempty compact measurable correspondence. On { d t = 0 } \{d_t=0\} { d t = 0 } , the algorithm sets π t = 1 \pi_t=1 π t = 1 by convention, without division by d t d_t d t . Lower semicontinuity and the deterministic tie-breaking rule give a measurable minimizer when d t > 0 d_t>0 d t > 0 , and the zero-demand branch is measurable. Writing the two-point law as C t = R t + d t Z t C_t=R_t+d_tZ_t C t = R t + d t Z t , with Z t ∼ Bernoulli ( π t ) Z_t\sim\operatorname{Bernoulli}(\pi_t) Z t ∼ Bernoulli ( π t ) conditionally on G t \mathcal{G}_t G t , gives
0 ≤ T ~ t − R t ≤ C t − R t = d t Z t , E t [ C t − R t ] = π t d t . 0\leq\widetilde{T}_t-R_t\leq C_t-R_t=d_tZ_t,\qquad\mathbb{E}_t[C_t-R_t]=\pi_t d_t. 0 ≤ T t − R t ≤ C t − R t = d t Z t , E t [ C t − R t ] = π t d t .
Here the first inequality uses R t ≤ T t R_t\leq T_t R t ≤ T t and R t ≤ C t R_t\leq C_t R t ≤ C t . Conditional monotonicity and membership in the feasible set give the claimed cost and prefix inequalities. If d t > 0 d_t>0 d t > 0 , integer-valued R t R_t R t implies R t < U t ≤ R t + d t R_t<U_t\leq R_t+d_t R t < U t ≤ R t + d t , so { C t ≥ U t } = { Z t = 1 } \{C_t\geq U_t\}=\{Z_t=1\} { C t ≥ U t } = { Z t = 1 } and G t ( U t ) = π t G_t(U_t)=\pi_t G t ( U t ) = π t . If d t = 0 d_t=0 d t = 0 , then R t ≥ U t R_t\geq U_t R t ≥ U t and G t ( U t ) = 1 = π t G_t(U_t)=1=\pi_t G t ( U t ) = 1 = π t . Thus G t ( U t ) ≥ g min G_t(U_t)\geq g_{\min} G t ( U t ) ≥ g m i n in both cases. Finally, R t R_t R t , d t d_t d t , and π t \pi_t π t are fixed under G t \mathcal{G}_t G t , and the fresh Bernoulli draw is conditionally independent of T t T_t T t , establishing the last claim.
By Assumption 10, the feasible-set constraint holds almost surely at every round through T T T . Hence, for every prefix t ≤ T t\leq T t ≤ T ,
∑ s = 1 t E s [ T ~ s − R s ] ≤ ∑ s = 1 t E s [ C s − R s ] = ∑ s = 1 t π s d s ≤ t C t a s k almost surely . (41) \sum_{s=1}^{t}\mathbb{E}_s[\widetilde{T}_s-R_s]\leq\sum_{s=1}^{t}\mathbb{E}_s[C_s-R_s]=\sum_{s=1}^{t}\pi_s d_s\leq tC_{\mathrm{task}}\qquad\text{almost surely}. \tag*{(41)} s = 1 ∑ t E s [ T s − R s ] ≤ s = 1 ∑ t E s [ C s − R s ] = s = 1 ∑ t π s d s ≤ t C task almost surely . (41)
Here E s [ C s − R s ] = π s d s \mathbb{E}_s[C_s-R_s]=\pi_s d_s E s [ C s − R s ] = π s d s follows from the predictable two-point law, and the first inequality is conditional monotonicity applied to T ~ s − R s ≤ C s − R s \widetilde{T}_s-R_s\leq C_s-R_s T s − R s ≤ C s − R s . Here E s [ ⋅ ] = E [ ⋅ ∣ X s , R s , D s − 1 ] \mathbb{E}_s[\cdot]=\mathbb{E}[\cdot\mid X_s,R_s,D_{s-1}] E s [ ⋅ ] = E [ ⋅ ∣ X s , R s , D s − 1 ] , so this is the prefix bound conditional also on the user runtime. It implies (3) when each R s R_s R s is measurable with respect to ( X s , D s − 1 ) (X_s,D_{s-1}) ( X s , D s − 1 ) . For general random user runtimes, (3) does not follow from this ledger alone; the unconditional guarantee below still holds. Taking outer expectations and applying the tower property at any prefix gives
E s e q [ ∑ s = 1 t ( T ~ s − R s ) ] ≤ E s e q [ ∑ s = 1 t ( C s − R s ) ] ≤ t C t a s k , t = 1 , … , T . \mathbb{E}_{\mathrm{seq}}\left[\sum_{s=1}^{t}(\widetilde{T}_s-R_s)\right]\leq\mathbb{E}_{\mathrm{seq}}\left[\sum_{s=1}^{t}(C_s-R_s)\right]\leq tC_{\mathrm{task}},\qquad t=1,\ldots,T. E seq [ s = 1 ∑ t ( T s − R s ) ] ≤ E seq [ s = 1 ∑ t ( C s − R s ) ] ≤ t C task , t = 1 , … , T .
Setting t = T t=T t = T and dividing by T T T proves (28).
The accumulating constraint controls expected additional consumption at every prefix. The conclusion follows from predictable feasibility and conditional monotonicity, without requiring an accurate completion model.
Joint Coverage and High-Probability Budget Validity
Theorem 12 (Joint coverage and high-probability budget validity). *Under Assumptions 1, 2, 5, and 10, let PROBE use Algorithm 5. Fix δ c o v , δ b u d ∈ ( 0 , 1 ) \delta_{\mathrm{cov}},\delta_{\mathrm{bud}}\in(0,1) δ cov , δ bud ∈ ( 0 , 1 ) with δ c o v + δ b u d < 1 \delta_{\mathrm{cov}}+\delta_{\mathrm{bud}}<1 δ cov + δ bud < 1 . Then,
for every fixed horizon T T T , with probability at least 1 − δ c o v − δ b u d 1-\delta_{\mathrm{cov}}-\delta_{\mathrm{bud}} 1 − δ cov − δ bud , the residual coverage certificate (27) and
\begin{aligned}
\sum_{t=1}^{T}(\widetilde{T}_t-R_t)
&\le\sum_{t=1}^{T}(C_t-R_t) \\
&\le TC_{\mathrm{task}}+\frac{d_{\max}}{3}\log\frac{1}{\delta_{\mathrm{bud}}}
+\sqrt{2d_{\max}TC_{\mathrm{task}}\log\frac{1}{\delta_{\mathrm{bud}}}
+\frac{d_{\max}^{2}}{9}\log^{2}\frac{1}{\delta_{\mathrm{bud}}}.
\end{aligned}} \tag*{(42)}\end{aligned}
hold simultaneously.
Proof of Theorem 12. For the realized additional allocation, define ζ t = ( C t − R t ) − π t d t = d t ( Z t − π t ) \zeta_t=(C_t-R_t)-\pi_td_t=d_t(Z_t-\pi_t) ζ t = ( C t − R t ) − π t d t = d t ( Z t − π t ) , where Z t ∣ G t ∼ Bernoulli ( π t ) Z_t\mid\mathcal{G}_t\sim\operatorname{Bernoulli}(\pi_t) Z t ∣ G t ∼ Bernoulli ( π t ) . Conditional on G t \mathcal{G}_t G t , E t [ ζ t ] = 0 \mathbb{E}_t[\zeta_t]=0 E t [ ζ t ] = 0 , ζ t ≤ d t ≤ d max \zeta_t\le d_t\le d_{\max} ζ t ≤ d t ≤ d m a x , and
E t [ ζ t 2 ] = π t ( 1 − π t ) d t 2 . \mathbb{E}_t[\zeta_t^2]=\pi_t(1-\pi_t)d_t^2. E t [ ζ t 2 ] = π t ( 1 − π t ) d t 2 .
Inserting a zero increment between F t − 1 \mathcal{F}_{t-1} F t − 1 and G t \mathcal{G}_t G t produces an ordinary martingale difference sequence. Its predictable quadratic variation obeys
V T b u d = ∑ t = 1 T π t ( 1 − π t ) d t 2 ≤ d max ∑ t = 1 T π t d t ≤ d max T C t a s k . V_T^{\mathrm{bud}}=\sum_{t=1}^{T}\pi_t(1-\pi_t)d_t^2
\le d_{\max}\sum_{t=1}^{T}\pi_td_t
\le d_{\max}TC_{\mathrm{task}}. V T bud = t = 1 ∑ T π t ( 1 − π t ) d t 2 ≤ d m a x t = 1 ∑ T π t d t ≤ d m a x T C task .
One-sided Freedman concentration therefore implies that, with probability at least 1 − δ b u d 1-\delta_{\mathrm{bud}} 1 − δ bud ,
∑ t = 1 T ζ t ≤ d max 3 log 1 δ b u d + 2 d max T C t a s k log 1 δ b u d + d max 2 9 log 2 1 δ b u d . \sum_{t=1}^{T}\zeta_t
\le\frac{d_{\max}}{3}\log\frac{1}{\delta_{\mathrm{bud}}}
+\sqrt{2d_{\max}TC_{\mathrm{task}}\log\frac{1}{\delta_{\mathrm{bud}}}
+\frac{d_{\max}^{2}}{9}\log^{2}\frac{1}{\delta_{\mathrm{bud}}}.} t = 1 ∑ T ζ t ≤ 3 d m a x log δ bud 1 + 2 d m a x T C task log δ bud 1 + 9 d m a x 2 log 2 δ bud 1 .
Combining this inequality with ∑ t π t d t ≤ T C t a s k \sum_t\pi_td_t\le TC_{\mathrm{task}} ∑ t π t d t ≤ T C task and T ~ t − R t ≤ C t − R t \widetilde{T}_t-R_t\le C_t-R_t T t − R t ≤ C t − R t proves (42) on an event of probability at least 1 − δ b u d 1-\delta_{\mathrm{bud}} 1 − δ bud .
Assumptions 1, 2, and 5 allow us to apply Theorem 3. Hence the residual coverage certificate (27) holds on an event of probability at least 1 − δ c o v 1-\delta_{\mathrm{cov}} 1 − δ cov . A union bound shows that this event and the budget event above hold simultaneously with probability at least 1 − δ c o v − δ b u d 1-\delta_{\mathrm{cov}}-\delta_{\mathrm{bud}} 1 − δ cov − δ bud ; no independence between the events is required.
The realized-budget guarantee is a fixed-horizon high-probability statement; it is not a strict pathwise hard-budget cap.
Coverage of ACI+IPCW
Theorem 13 (Coverage of ACI+IPCW). Consider Algorithm 1 with fixed step size η > 0 \eta> 0 η > 0 and deterministic initialization τ 1 \tau_1 τ 1 . Assume Assumptions 1 and 2, predictable bounds and censoring laws, and known censoring probabilities. The prediction rule must be defined at every reachable calibration state, and the update is unprojected:
τ t + 1 = τ t + η ( α − e ^ t ) . \tau_{t+1} = \tau_t + \eta(\alpha- \widehat e_t). τ t + 1 = τ t + η ( α − e t ) . Define the average conditional coverage
c ‾ T : = 1 T ∑ t = 1 T P ( T t ≤ U t ∣ X t , D t − 1 ) . \overline{c}_T := \frac{1}{T}\sum_{t=1}^{T} \mathbb{P}(T_t \le U_t \mid X_t, D_{t-1}). c T := T 1 t = 1 ∑ T P ( T t ≤ U t ∣ X t , D t − 1 ) . For every fixed horizon T ≥ 1 T \ge1 T ≥ 1 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ ,
c ‾ T ≥ 1 − α − τ 1 − τ T + 1 η T − 2 log ( 1 / δ ) T g min . (43) \overline{c}_T \ge1-\alpha-\frac{\tau_1-\tau_{T+1}}{\eta T}-\sqrt{\frac{2\log(1/\delta)}{Tg_{\min}}}. \tag*{(43)} c T ≥ 1 − α − η T τ 1 − τ T + 1 − T g m i n 2 log ( 1/ δ ) . (43) If, additionally,
( τ 1 − τ T + 1 ) + T ⟶ 0 almost surely , (44) \frac{(\tau_1-\tau_{T+1})_+}{T}\longrightarrow0 \qquad\text{almost surely}, \tag*{(44)} T ( τ 1 − τ T + 1 ) + ⟶ 0 almost surely , (44) where ( x ) + = max { x , 0 } (x)_+ = \max\{x,0\} ( x ) + = max { x , 0 } , then
lim inf T → ∞ c ‾ T ≥ 1 − α almost surely . \liminf_{T\to\infty}\overline{c}_T \ge1-\alpha\qquad\text{almost surely}. T → ∞ lim inf c T ≥ 1 − α almost surely . Condition (42) holds, in particular, whenever inf t ≥ 1 τ t > − ∞ \inf_{t\ge1}\tau_t > -\infty inf t ≥ 1 τ t > − ∞ almost surely.
Proof. Let P t = σ ( X t , D t − 1 ) \mathcal{P}_t = \sigma(X_t,D_{t-1}) P t = σ ( X t , D t − 1 ) , G t = σ ( P t , R t ) \mathcal{G}_t = \sigma(\mathcal{P}_t,R_t) G t = σ ( P t , R t ) , and F t = σ ( D t ) \mathcal{F}_t = \sigma(D_t) F t = σ ( D t ) , so that F t − 1 ⊆ P t ⊆ G t ⊆ F t \mathcal{F}_{t-1} \subseteq\mathcal{P}_t \subseteq\mathcal{G}_t \subseteq\mathcal{F}_t F t − 1 ⊆ P t ⊆ G t ⊆ F t . The bound U t U_t U t is fixed given P t \mathcal{P}_t P t ; the censoring law is fixed given G t \mathcal{G}_t G t . The boundary-aware indicator satisfies
I t e r r ( U t ) = 1 { T t > U t , C t ≥ U t } . I_t^{\mathrm{err}}(U_t)=1\{T_t>U_t,\ C_t\ge U_t\}. I t err ( U t ) = 1 { T t > U t , C t ≥ U t } .
Conditional independence and positivity give E [ e ^ t ∣ G t ] = m t R \mathbb{E}[\widehat e_t\mid\mathcal{G}_t]=m_t^R E [ e t ∣ G t ] = m t R and E [ e ^ t 2 ∣ G t ] = m t R / G t ( U t ) \mathbb{E}[\widehat e_t^2\mid\mathcal{G}_t]=m_t^R/G_t(U_t) E [ e t 2 ∣ G t ] = m t R / G t ( U t ) , where m t R = P ( T t > U t ∣ G t ) m_t^R=\mathbb{P}(T_t>U_t\mid\mathcal{G}_t) m t R = P ( T t > U t ∣ G t ) . The tower property therefore gives the prediction-time moments
E [ e ^ t ∣ P t ] = m t , \mathbb{E}[\widehat e_t\mid\mathcal{P}_t]=m_t, E [ e t ∣ P t ] = m t ,
E [ e ^ t 2 ∣ P t ] = E [ m t R G t ( U t ) ∣ P t ] ≤ 1 g min . (45) \mathbb{E}[\widehat e_t^2\mid\mathcal{P}_t]
=\mathbb{E}\left[\left.\frac{m_t^R}{G_t(U_t)}\right|\mathcal{P}_t\right]
\le\frac{1}{g_{\min}}. \tag*{(45)} E [ e t 2 ∣ P t ] = E [ G t ( U t ) m t R P t ] ≤ g m i n 1 . (45)
Set ε t = m t − e ^ t \varepsilon_t=m_t-\widehat e_t ε t = m t − e t . Since e ^ t ≥ 0 \widehat e_t\ge0 e t ≥ 0 , the elementary inequalities e − x ≤ 1 − x + x 2 / 2 e^{-x}\le1-x+x^2/2 e − x ≤ 1 − x + x 2 /2 for x ≥ 0 x\ge0 x ≥ 0 and 1 + y ≤ e y 1+y\le e^y 1 + y ≤ e y imply, for every λ ≥ 0 \lambda\ge0 λ ≥ 0 ,
E [ e λ ε t ∣ P t ] ≤ e λ m t ( 1 − λ m t + λ 2 2 E [ e ^ t 2 ∣ P t ] ) ≤ exp ( λ 2 2 g min ) . \mathbb{E}[e^{\lambda\varepsilon_t}\mid\mathcal{P}_t]
\le e^{\lambda m_t}\left(1-\lambda m_t+\frac{\lambda^2}{2}\mathbb{E}[\widehat e_t^2\mid\mathcal{P}_t]\right)
\le\exp\left(\frac{\lambda^2}{2g_{\min}}\right). E [ e λ ε t ∣ P t ] ≤ e λ m t ( 1 − λ m t + 2 λ 2 E [ e t 2 ∣ P t ] ) ≤ exp ( 2 g m i n λ 2 ) .
Iterated conditioning along the above filtration yields
E [ exp ( λ ∑ t = 1 T ε t ) ] ≤ exp ( T λ 2 2 g min ) . \mathbb{E}\left[\exp\left(\lambda\sum_{t=1}^{T}\varepsilon_t\right)\right]
\le\exp\left(\frac{T\lambda^2}{2g_{\min}}\right). E [ exp ( λ t = 1 ∑ T ε t ) ] ≤ exp ( 2 g m i n T λ 2 ) .
Consequently, exponential Markov inequality, optimized over λ ≥ 0 \lambda\ge0 λ ≥ 0 , gives
P ( ∑ t = 1 T ε t > 2 T g min log 1 δ ) ≤ δ . \mathbb{P}\left(\sum_{t=1}^{T}\varepsilon_t>\sqrt{\frac{2T}{g_{\min}}\log\frac{1}{\delta}}\right)\le\delta. P ( t = 1 ∑ T ε t > g m i n 2 T log δ 1 ) ≤ δ .
Summing the unprojected ACI update gives the exact identity
∑ t = 1 T ( ε ^ t − α ) = τ 1 − τ T + 1 η . \sum_{t=1}^{T}(\widehat{\varepsilon}_t-\alpha)=\frac{\tau_1-\tau_{T+1}}{\eta}. t = 1 ∑ T ( ε t − α ) = η τ 1 − τ T + 1 .
Hence
c ‾ T = 1 − α − τ 1 − τ T + 1 η T − 1 T ∑ t = 1 T ε t . \overline{c}_T=1-\alpha-\frac{\tau_1-\tau_{T+1}}{\eta T}-\frac{1}{T}\sum_{t=1}^{T}\varepsilon_t. c T = 1 − α − η T τ 1 − τ T + 1 − T 1 t = 1 ∑ T ε t .
Combining the last two displays proves (41).
Finally, apply the finite-horizon bound with δ T = T − 2 \delta_T=T^{-2} δ T = T − 2 for T ≥ 2 T\ge2 T ≥ 2 . Since ∑ T = 2 ∞ δ T < ∞ \sum_{T=2}^{\infty}\delta_T<\infty ∑ T = 2 ∞ δ T < ∞ , the Borel–Cantelli lemma implies that almost surely, for all sufficiently large T T T ,
c ‾ T ≥ 1 − α − ( τ 1 − τ T + 1 ) + η T − 4 log T T g min . \overline{c}_T\ge1-\alpha-\frac{(\tau_1-\tau_{T+1})_+}{\eta T}-\sqrt{\frac{4\log T}{Tg_{\min}}}. c T ≥ 1 − α − η T ( τ 1 − τ T + 1 ) + − T g m i n 4 log T .
Condition (42) then proves the asymptotic claim.
The calibration-state condition is an additional requirement; conditional unbiasedness of the IPCW feedback alone does not establish it.
Selection Rule for the Positivity Floor g min g_{\min} g m i n
For the additional-budget allocator in Algorithm 4, a larger g min g_{\min} g m i n limits IPCW weights but increases the minimum expected additional allocation g min d t g_{\min}d_t g m i n d t . From a disjoint pilot sample, estimate the mean requested additional runtime μ ^ d = n − 1 ∑ i = 1 n d i r e f \widehat{\mu}_d=n^{-1}\sum_{i=1}^{n}d_i^{\mathrm{ref}} μ d = n − 1 ∑ i = 1 n d i ref , where d i r e f = ( ∣ U i r e f ∣ − R i r e f ) + d_i^{\mathrm{ref}}=(|U_i^{\mathrm{ref}}|-R_i^{\mathrm{ref}})_+ d i ref = ( ∣ U i ref ∣ − R i ref ) + . With a planning-slack factor γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) , set
g min = { min { 1 , γ C t a s k / μ ^ d } , μ ^ d > 0 , 1 , μ ^ d = 0 , g_{\min}=
\begin{cases}
\min\{1,\gamma C_{\mathrm{task}}/\widehat{\mu}_d\}, & \widehat{\mu}_d>0,\\
1, & \widehat{\mu}_d=0,
\end{cases} g m i n = { min { 1 , γ C task / μ d } , 1 , μ d > 0 , μ d = 0 ,
and freeze the floor before the evaluated online run. At the pilot mean, the floor commits at most a γ \gamma γ fraction of the per-task budget.
If a valid positive upper bound d t ≤ d max d_t\le d_{\max} d t ≤ d m a x is available, additionally cap g min g_{\min} g m i n at C t a s k / d max C_{\mathrm{task}}/d_{\max} C task / d m a x to guarantee a nonempty feasible interval on every round (Assumption 10). Without this cap, the pilot rule is a heuristic: check Π t a d d \Pi_t^{\mathrm{add}} Π t add before each allocation and invoke the declared infeasibility protocol if it is empty, as in Algorithm 5.
Deterministic Budget Allocation
For a hard cap on additional evaluation cost, fix a finite budget B g l o b a l ≥ 0 B_{\mathrm{global}} \ge0 B global ≥ 0 for an accounting window and initialize B 1 = B g l o b a l B_1 = B_{\mathrm{global}} B 1 = B global , with no replenishment. After the user run and before continuing the evaluation, compute d t = ( ⌈ U t ⌉ − R t ) + d_t = (\lceil U_t \rceil- R_t)_+ d t = (⌈ U t ⌉ − R t ) + . If B t ≥ d t B_t \ge d_t B t ≥ d t , set C t = R t + d t C_t = R_t + d_t C t = R t + d t , reserve the additional runtime C t − R t = d t C_t - R_t = d_t C t − R t = d t , continue the round, and update B t + 1 = B t − ( C t − R t ) B_{t+1} = B_t - (C_t - R_t) B t + 1 = B t − ( C t − R t ) . Debit the full additional reservation even if the task completes earlier. Since 0 ≤ C t − R t ≤ B t 0 \le C_t - R_t \le B_t 0 ≤ C t − R t ≤ B t , induction gives B t + 1 ≥ 0 B_{t+1} \ge0 B t + 1 ≥ 0 . Telescoping the ledger update yields, for every prefix,
0 ≤ ∑ t = 1 n ( T ~ t − R t ) ≤ ∑ t = 1 n ( C t − R t ) = B g l o b a l − B n + 1 ≤ B g l o b a l . 0 \le\sum_{t=1}^{n}(\widetilde{T}_t - R_t) \le\sum_{t=1}^{n}(C_t - R_t) = B_{\mathrm{global}} - B_{n+1} \le B_{\mathrm{global}}. 0 ≤ t = 1 ∑ n ( T t − R t ) ≤ t = 1 ∑ n ( C t − R t ) = B global − B n + 1 ≤ B global .
If B t < d t B_t < d_t B t < d t , set C t = R t C_t = R_t C t = R t and B t + 1 = B t B_{t+1} = B_t B t + 1 = B t , report budget exhaustion, and terminate the active sequence. Freeze the calibration state and IPCW statistics and set all subsequent additional allocations C s − R s C_s - R_s C s − R s in the window to zero. Because B t < d t B_t < d_t B t < d t implies R t < U t R_t < U_t R t < U t , this branch has G t ( U t ) = 0 G_t(U_t) = 0 G t ( U t ) = 0 . Do not form the undefined IPCW ratio or replace it with an artificial zero.
On funded rounds, G t ( U t ) = 1 G_t(U_t) = 1 G t ( U t ) = 1 and the coverage error is fully observed. The hard cap holds pathwise; coverage is not claimed for skipped rounds or an average stopped at exhaustion. A fixed-horizon coverage guarantee still requires the original coverage assumptions and funding every round; B g l o b a l ≥ T d max B_{\mathrm{global}} \ge T d_{\max} B global ≥ T d m a x suffices when d t ≤ d max d_t \le d_{\max} d t ≤ d m a x .
Figure 6. Cumulative coverage rate over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 7. Upper predictive bound, α = 0.1 \alpha= 0.1 α = 0.1
Figure 8. Local coverage over time, α = 0.1 \alpha= 0.1 α = 0.1 , window=50
Figure 9. Coverage boxplot, α = 0.15 \alpha= 0.15 α = 0.15
Additional Experiments
In this section, we provide additional empirical results that further support the findings presented in the main text. Specifically, we expand upon the evaluations of our proposed PROBE framework across various target coverage levels and budget constraints. As in § 4 , all experiments use R t = 0 R_t = 0 R t = 0 ; the reported assigned budget ∑ t C t \sum_t C_t ∑ t C t therefore equals the additional assigned budget ∑ t ( C t − R t ) \sum_t(C_t - R_t) ∑ t ( C t − R t ) .
SWE Settings
Building upon the software engineering evaluation in § 4 , we present further experiments on the SWE dataset (G.1) under more stringent resource limitations. All experiments in this subsection are evaluated over 1,000 sequential trials across 10 independent repetitions, with an expected budget constraint of C t a s k = 15.0 C_{\mathrm{task}} = 15.0 C task = 15.0 . The evaluation protocol and metrics remain identical to the experiments appearing in the main paper.
Figure 10. Cumulative budget spend over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 11. Coverage boxplot, α = 0.2 \alpha= 0.2 α = 0.2
Figure 12. Cumulative coverage rate over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 13. Upper predictive bound, α = 0.1 \alpha= 0.1 α = 0.1
Figure 14. Local coverage over time, α = 0.1 \alpha= 0.1 α = 0.1 , window=50
Figure 15. Cumulative coverage, α = 0.15 \alpha= 0.15 α = 0.15
RAG Settings
Building upon the retrieval-augmented generation evaluation in § 4 , we present further experiments on the NFCorpus benchmark G.2. All experiments in this subsection evaluate the predicted number of relevant corpus items over 1,000 sequential trials across 10 independent repetitions. These evaluations apply various expected budget constraints C t a s k C_{\mathrm{task}} C task and target miscoverage levels α \alpha α , mirroring the experimental structure introduced in the main text.
Figure 16. Cumulative budget spend over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 17. Cumulative coverage, α = 0.2 \alpha= 0.2 α = 0.2
Figure 18. Cumulative coverage rate over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 19. Upper predictive bound, α = 0.1 \alpha= 0.1 α = 0.1
Figure 20. Local coverage over time, α = 0.1 \alpha= 0.1 α = 0.1 , window=50
Figure 21. Cumulative coverage, α = 0.15 \alpha= 0.15 α = 0.15
AutoIF Settings
Building upon the instruction following evaluation in § 4 , we present further experiments on the NFCorpus benchmark G.3. All experiments in this subsection evaluate the predicted number of relevant corpus items over 1,000 sequential trials across 10 independent repetitions. These evaluations apply various expected budget constraints C t a s k C_{\mathrm{task}} C task and target miscoverage levels α \alpha α , mirroring the experimental structure introduced in the main text.
Figure 22. Cumulative budget spend over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 23. Cumulative coverage, α = 0.2 \alpha= 0.2 α = 0.2
Figure 24. Cumulative coverage rate over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 25. Upper predictive bound, α = 0.1 \alpha= 0.1 α = 0.1
Ablation Study: ACI+IPCW Calibration Variants
We assess the effect of a small implementation adjustment to ACI+IPCW: assigning a unit penalty on zero-budget rounds (C t = 0 C_t = 0 C t = 0 ). The variant ACI+IPCW (w/o penalty) uses the standard IPCW feedback, whereas ACI+IPCW (w/ penalty) replaces its zero feedback on these rounds with one. Under tight budgets, the unpenalized implementation exhibits undercoverage: skipped rounds induce optimistic calibration updates, while clipping limits the compensating corrections from rare, large IPCW penalties. The unit penalty counteracts this effect and restores empirical coverage in the reported experiments, at the cost of wider upper predictive bounds. We therefore use the penalized variant in the main experiments to provide a fair comparison with a baseline that maintains empirical coverage. Appendix G.5 details this conservative adjustment and its relation to the theoretical coverage guarantee.
Real Data (SWE settings)
We first examine the effect of the zero-budget penalty on the real-world SWE data described in Appendix G.1, using an expected budget of C t a s k = 15 C_{\mathrm{task}} = 15 C task = 15 . The results below compare the two ACI+IPCW variants with PROBE and the uncalibrated baseline in terms of cumulative and local coverage, upper predictive bounds, and budget expenditure.
Figure 26. Local coverage over time, α = 0.1 \alpha= 0.1 α = 0.1 , window=50
Figure 27. Cumulative coverage, α = 0.15 \alpha= 0.15 α = 0.15
Figure 28. Cumulative budget spend over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 29. Cumulative coverage, α = 0.2 \alpha= 0.2 α = 0.2
Figure 30. Cumulative coverage rate over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 31. Upper predictive bound, α = 0.1 \alpha= 0.1 α = 0.1
Synthetic Data
We next evaluate the calibration variants on the synthetic distribution shift dataset described in Appendix G.4. This controlled setting tests adaptation when the target distribution drifts upward while the uncalibrated predictive distribution remains stationary, progressively reducing the coverage of the uncalibrated UPBs. We compare PROBE, the two ACI+IPCW variants, and the uncalibrated baseline at nominal coverage 1 − α = 0.9 1-\alpha=0.9 1 − α = 0.9 , using C t a s k = 5 C_{\mathrm{task}}=5 C task = 5 . Each configuration is evaluated over ten repetitions, preserving the same temporal data order while varying the observation randomness.
Figure 32. Local coverage over time, α = 0.1 \alpha= 0.1 α = 0.1 , window = 200
Figure 33. Cumulative coverage, α = 0.15 \alpha= 0.15 α = 0.15
Figure 34. Cumulative budget spend over time, α = 0.1 \alpha= 0.1 α = 0.1
Figure 35. Cumulative coverage, α = 0.2 \alpha= 0.2 α = 0.2
Ablation of the Penalty and Exponential Parametrization
We investigate whether the advantage of our method can be explained solely by exponential parametrization [14 ] or by adding a conservative penalty under ambiguous feedback. Table 1 compares the proposed method, the uncalibrated baseline, and four ACI+IPCW variants obtained by independently enabling these two components. Results use the real SWE dataset with C t a s k = 15.0 C_{\mathrm{task}} = 15.0 C task = 15.0 , α ∈ { 0.1 , 0.15 , 0.2 } \alpha\in\{0.1, 0.15, 0.2\} α ∈ { 0.1 , 0.15 , 0.2 } , and ten repetitions of 1,000 rounds. All ACI variants share the remaining hyperparameters, including γ = 5 × 10 − 4 \gamma= 5 \times10^{-4} γ = 5 × 1 0 − 4 . Entries report mean ± \pm ± sample standard deviation across repetitions; local coverage averages complete 50-round windows.
Table 1: SWE ablation of the ACI+IPCW penalty and exponential parametrization at C t a s k = 15.0 C_{\mathrm{task}} = 15.0 C task = 15.0 . Values are mean ± \pm ± sample standard deviation across 10 repetitions of 1,000 rounds each. Local coverage is the mean coverage over all complete trailing 50-round windows within each repetition. Coverage and UPB are the final cumulative coverage and mean requested upper predictive bound, respectively. Budget spend is total assigned budget ∑ t C t \sum_t C_t ∑ t C t . The uncalibrated baseline uses full observation without the budget constraint. Bold entries in Local coverage and Coverage minimize the absolute distance of the mean from the target 1 − α 1 - \alpha 1 − α among methods at the same α \alpha α .
Table 1.
In Table 1 , the proposed method achieves mean coverage closest to the nominal target at every evaluated α \alpha α . Exponential ACI+IPCW undercovers even with the penalty, while the non-exponential variant with the penalty becomes overly conservative and produces much larger bounds. For example, at α = 0.2 \alpha= 0.2 α = 0.2 , the proposed method achieves coverage 0.7963 with mean UPB 79.5382, compared with 0.9126 and 191.5697 for the non-exponential penalized variant, at comparable spending. These results support an advantage beyond either modification alone under the tested settings, although they do not separately isolate the contribution of the proposed budget allocator.
Additional Related Work
Our work builds on conformal prediction [48 , 42 ] , including split conformal prediction [31 ] and weighted conformal methods for covariate shift [44 ] . Conformal prediction has recently been extended to censored survival outcomes [4 , 20 , 39 , 40 , 6 , 7 ] (Feldman and Romano 2026), including history-aware methods with inverse-probability-of-censoring weighting [53 ] . Adaptive conformal inference further extends calibration to sequential and potentially nonstationary data by updating the nominal level according to past errors [17 , 18 , 14 ] . Our setting includes all these challenges: censoring hides coverage errors, while the censoring mechanism itself is chosen adaptively under a computational budget. Thus, we jointly adapt online the predictive bound and the mechanism that determines which outcomes are observed.
Our budget allocation is related to active learning [41 ] , optimal experimental design [10 ] , and adaptive data collection for valid statistical inference [62 , 21 ] . Related works also study adaptive experimentation with censored survival outcomes [52 ] . These methods typically decide which observations or participants to sample. In contrast, we decide how many interactions to sample from a sequential trajectory, which induces right censoring and changes the feedback available for the calibration. Furthermore, our allocator optimizes the stated model-based coverage criterion under the accumulating budget constraint.
Modern agent benchmarks evaluate systems over iterative trajectories, including software-engineering agents [23 , 57 ] and browser agents [60 ] . Our framework complements standard evaluation of agentic utility by modeling the number of interactions until an event of interest. This perspective also applies to LLM safety, where prior work studies harmful texts [16 , 47 ] , inference-time guardrails [22 , 35 ] , adversarial red teaming and jailbreaks [34 , 61 , 54 , 29 , 5 ] , and certified safety guarantees [26 , 37 ] . These approaches focus on whether such events occur; in contrast, our objective is to provide calibrated bounds on when an event occurs along a multi-turn trajectory.
Our framework also relates to methods that reduce the cost of model evaluation [25 ] , including active testing [27 ] , bandit-based allocation [59 ] , adaptive dataset partitioning [49 ] , and finite-population inference with adaptive benchmark-item selection [55 ] . These methods primarily choose which benchmark items to evaluate. We instead choose how long to evaluate each trajectory. Early stopping therefore produces censored observations rather than simply excluding examples, requiring the evaluation and budget-allocation procedures to account explicitly for censoring.
Experimental Details
Software Engineering Settings (SWE)
Original Dataset. We use the train split of the nebius/SWE-agent-trajectories dataset hosted on Hugging Face Datasets [30 ] . The collection contains SWE-agent-style trajectories for resolving real-world GitHub software issues, following the task setting introduced by SWE-bench and SWE-agent [24 , 57 ] . A raw record contains an instance identifier, model name, trajectory, generated patch, exit status, evaluation logs, and a Boolean resolution target. The Boolean target is not the response modeled by our UPB predictor. Instead, we define T i t r u e T_i^{\mathrm{true}} T i true as the number of logged entries in the agent trajectory. The parser first accepts trajectories represented as Python lists, JSON strings, or Python-literal strings. If these parsing paths fail, it counts the logged role markers and returns at least one step. The retrieved raw artifact contains 80,036 records.
Feature Extraction. For each trajectory, we extract six lexical features from its first logged entry: character length, line count, whitespace-delimited word count, number of literal triple-backtick delimiters, the summed case-insensitive occurrence count of error, exception, traceback, and fail, and the summed case-sensitive occurrence count of .py, .json, .md, .sh, and .txt. We also retain the model name and derive the repository identifier from the portion of instance_id preceding __. Using only the training split, the categorical variables are target encoded as the model-specific mean and standard deviation of T t r u e T^{\mathrm{true}} T true , together with the repository-specific mean. An unseen model or repository receives the global training mean; an unseen model receives a standard-deviation feature of zero. Thus,
X i = [ μ m o d e l , σ m o d e l , μ r e p o , n c h a r , n l i n e , n w o r d , n b a c k t i c k , n e r r o r , n f i l e ] i ∈ R 9 . X_i = [\mu_{\mathrm{model}}, \sigma_{\mathrm{model}}, \mu_{\mathrm{repo}}, n_{\mathrm{char}}, n_{\mathrm{line}}, n_{\mathrm{word}}, n_{\mathrm{backtick}}, n_{\mathrm{error}}, n_{\mathrm{file}}]_i \in\mathbb{R}^{9}. X i = [ μ model , σ model , μ repo , n char , n line , n word , n backtick , n error , n file ] i ∈ R 9 .
The resulting matrix is stored as float32 and standardized coordinate-wise using means and standard deviations computed on the training split. A standard deviation smaller than 10 − 12 10^{-12} 1 0 − 12 is replaced by one.
Quantile Predictor. Records with T t r u e > 300 T^{\mathrm{true}} > 300 T true > 300 are removed, leaving 79,090 examples; duplicate removal is disabled. A permutation generated with seed 42 assigns 500 examples to training, 55 to validation, and the remaining 78,535 to the reported holdout set. For every α ∈ { 0.01 , 0.02 , … , 0.99 } \alpha\in\{0.01, 0.02, \ldots, 0.99\} α ∈ { 0.01 , 0.02 , … , 0.99 } , we train a separate predictor for quantile level β = 1 − α \beta= 1 - \alpha β = 1 − α . Its architecture is
9 → Linear 128 → ReLU 128 → Linear 128 → ReLU 128 → Linear 1 → Softplus 1. 9 \xrightarrow{\text{Linear}} 128 \xrightarrow{\text{ReLU}} 128 \xrightarrow{\text{Linear}} 128 \xrightarrow{\text{ReLU}} 128 \xrightarrow{\text{Linear}} 1 \xrightarrow{\text{Softplus}} 1. 9 Linear 128 ReLU 128 Linear 128 ReLU 128 Linear 1 Softplus 1.
The objective is the mean pinball loss ℓ β ( y , y ^ ) = max { β ( y − y ^ ) , ( β − 1 ) ( y − y ^ ) } \ell_{\beta}(y,\widehat{y}) = \max\{\beta(y-\widehat{y}),(\beta-1)(y-\widehat{y})\} ℓ β ( y , y ) = max { β ( y − y ) , ( β − 1 ) ( y − y )} . Each network is optimized for 50 epochs using AdamW, a learning rate of 2 × 10 − 3 2 \times10^{-3} 2 × 1 0 − 3 , weight decay 10 − 4 10^{-4} 1 0 − 4 , and shuffled mini-batches of size 512. Validation loss and empirical coverage are logged, while the parameters from the final epoch are retained. Predictions are upper-clipped at 300. Device selection is automatic; the generated experiment metadata records CUDA execution.
Retrieval-Augmented Generation Settings (RAG)
Original Dataset. We use the BEIR distribution of NFCorpus, loading queries from BeIR/nfcorpus with configuration and split queries, and relevance judgments from the train and test splits of BeIR/nfcorpus-qrels. NFCorpus is a medical information-retrieval dataset, and BEIR provides its standardized retrieval representation [3 , 43 ] . The raw task is to retrieve corpus items relevant to a natural-language medical query. After verifying that query–corpus identifier pairs are unique, we retain judgments whose relevance score is at least one. We define
T i t r u e = # { retained relevance judgments associated with query i } . T_i^{\mathrm{true}} = \#\{\text{retained relevance judgments associated with query }i\}. T i true = # { retained relevance judgments associated with query i } .
The query table is inner-joined with these counts, producing 2,913 raw examples.
Feature Extraction. Only the query text, denoted by q u e r y i \mathrm{query}_i query i for query i i i , is used to construct X i X_i X i . Each query is encoded with the SentenceTransformers checkpoint sentence-transformers/all-MiniLM-L6-v2 using an encoding batch size of 64 [36 , 51 Sentence Transformers] . The checkpoint produces a 384-dimensional embedding. We append the query’s character length divided by 100, giving
X_i = \left[\operatorname{Embed}_{\mathrm{all\text{-}MiniLM\text{-}L6\text{-}v2}(\mathrm{query}_i);\frac{\operatorname{chars}(\mathrm{query}_i)}{100}\right] \in\mathbb{R}^{385}.}
The matrix is converted to float32 and standardized coordinate-wise using the training-set mean and standard deviation, with standard deviations below 10 − 12 10^{-12} 1 0 − 12 replaced by one. The repository pipeline does not add document embeddings or document-level metadata.
Quantile Predictor. Examples with T t r u e > 200 T^{\mathrm{true}} > 200 T true > 200 are excluded, leaving 2,804 examples; duplicate removal is disabled. With random seed 42, the pipeline uses 500 training examples, 55 validation examples, and 2,249 holdout examples. A separate network is trained for every α ∈ { 0.01 , 0.02 , … , 0.99 } \alpha\in\{0.01, 0.02, \ldots, 0.99\} α ∈ { 0.01 , 0.02 , … , 0.99 } , with β = 1 − α \beta= 1 - \alpha β = 1 − α and architecture
385 → L i n e a r 128 → R e L U 128 → L i n e a r 128 → R e L U 128 → L i n e a r 1 → S o f t p l u s 1. 385 \xrightarrow{\mathrm{Linear}} 128 \xrightarrow{\mathrm{ReLU}} 128 \xrightarrow{\mathrm{Linear}} 128 \xrightarrow{\mathrm{ReLU}} 128 \xrightarrow{\mathrm{Linear}} 1 \xrightarrow{\mathrm{Softplus}} 1. 385 Linear 128 ReLU 128 Linear 128 ReLU 128 Linear 1 Softplus 1.
Training minimizes the mean pinball loss ℓ β ( y , y ^ ) = max { β ( y − y ^ ) , ( β − 1 ) ( y − y ^ ) } \ell_{\beta}(y,\widehat{y}) = \max\{\beta(y-\widehat{y}),(\beta-1)(y-\widehat{y})\} ℓ β ( y , y ) = max { β ( y − y ) , ( β − 1 ) ( y − y )} using AdamW for 50 epochs, with learning rate 2 × 10 − 3 2 \times10^{-3} 2 × 1 0 − 3 , weight decay 10 − 4 10^{-4} 1 0 − 4 , and shuffled mini-batches of size 512. Validation loss and empirical coverage are logged, but the final-epoch parameters are used. Predictions are upper-clipped at 200. Device selection is automatic; the generated experiment metadata records CUDA execution.
Instruction Following Settings (AutoIF)
Original Dataset. To generate the raw dataset, we followed the procedure of Davidov et al. [2026], Feldman and Romano [2026]. We sample 10,000 instruction-following tasks from the AutoIF dataset, as well as 10,000 harmful prompts from the Anthropic Red Team dataset for adversarial jailbreaks. We generate the raw multi-turn attacker-target conversations using the PAIR algorithm. We deploy Qwen 2.5 14B Instruct as the attacking model, which acts as a helper agent for the AutoIF dataset to maximize the probability that the target model passes programmatic constraints. For the target models, we evaluate safety and utility across Qwen 2.5 14B Instruct, Llama 3.1 8B Instruct, Phi 4 Mini Instruct, and Gemma 3 4B Instruct. In all generated conversations, we cap the maximum sequence length at t max = 200 t_{\max} = 200 t m a x = 200 turns. The resulting dataset of interactions is divided into three disjoint subsets: a training set of 4,000 prompts, a calibration set of 3,000 prompts, and a test set of 3,000 prompts.
Feature Extraction. We embed all texts into vectors using the Multilingual-E5-large model. These high-dimensional text embeddings of the conversation history serve as the inputs for our predictive model.
Quantile Predictor. The predictive model architecture begins by projecting the high-dimensional embeddings into a lower-dimensional latent space of 256 using a linear layer, followed by a ReLU activation and dropout with a rate of 0.2. To capture the temporal dependencies of the conversational history, we apply a Transformer Encoder utilizing 3 prenormalized Transformer layers with 6 attention heads, a feed-forward dimension of 1024, and GELU activations. An upper-triangular attention mask is applied during encoding to prevent the model from using future time steps. The sequence encoding is then concatenated with the initial projected embeddings and passed through a multi-layer perceptron (three linear layers separated by ReLU activations and 0.2 dropout) to produce the raw temporal logits. For task t t t , the model outputs a t max × ( t max + 1 ) t_{\max} \times(t_{\max}+1) t m a x × ( t m a x + 1 ) matrix containing the probabilities of an event occurring at any future step, P ( T t = k 2 ∣ T t > k 1 , H t ( k 1 ) ) \mathbb{P}(T_t = k_2 \mid T_t > k_1, H_t(k_1)) P ( T t = k 2 ∣ T t > k 1 , H t ( k 1 )) , and the probability of reaching the horizon without an event. Here, k 1 k_1 k 1 and k 2 k_2 k 2 are the current and future within-conversation steps, respectively. The network is trained using the Adam optimizer with a learning rate of 10 − 4 10^{-4} 1 0 − 4 , weight decay of 0.001, and a batch size of 64. We optimize the model for a maximum of 500 epochs to minimize the survival negative log-likelihood loss, stopping early if the validation loss does not improve for 50 consecutive epochs. Finally, the outputs are calibrated on a held-out validation set (a 10% portion of the training set) using a temperature scaling L-BFGS optimizer.
Synthetic Data Settings
Data Generation. We generate N = 10,000 N = 10{,}000 N = 10 , 000 sequential examples with targets
T i = μ i + ε i , μ i = 95 + ( 115 − 95 ) i − 1 N − 1 , ε i ∼ i i d N ( 0 , 10 2 ) . T_i = \mu_i + \varepsilon_i,\qquad\mu_i = 95 + (115 - 95)\frac{i - 1}{N - 1},\qquad\varepsilon_i \overset{\mathrm{iid}}{\sim} \mathcal{N}(0, 10^2). T i = μ i + ε i , μ i = 95 + ( 115 − 95 ) N − 1 i − 1 , ε i ∼ iid N ( 0 , 1 0 2 ) .
The target mean increases linearly from 95 to 115. All examples are processed without shuffling, preserving the temporal shift.
Uncalibrated Predictions. For each example i i i , the 99 uncalibrated UPBs are defined as
U i , α u n c a l = 100 + ξ i + 4 Φ − 1 ( 1 − α ) , α ∈ { 0.01 , 0.02 , … , 0.99 } , U^{\mathrm{uncal}}_{i,\alpha} = 100 + \xi_i + 4\Phi^{-1}(1 - \alpha),\qquad\alpha\in\{0.01, 0.02, \ldots, 0.99\}, U i , α uncal = 100 + ξ i + 4 Φ − 1 ( 1 − α ) , α ∈ { 0.01 , 0.02 , … , 0.99 } ,
where ξ i ∼ i i d Uniform ( − 1 , 1 ) \xi_i \overset{\mathrm{iid}}{\sim} \operatorname{Uniform}(-1, 1) ξ i ∼ iid Uniform ( − 1 , 1 ) and Φ \Phi Φ denotes the standard normal cumulative distribution function. The predictive-location noise is independent of the target noise. Thus, the uncalibrated predictive distribution remains stationary while the target distribution drifts upward.
Additional Implementation Details
Raw predictions at different quantile levels can cross. For each task, let τ 1 g r i d > ⋯ > τ K g r i d > 0 \tau^{\mathrm{grid}}_1 > \cdots> \tau^{\mathrm{grid}}_K > 0 τ 1 grid > ⋯ > τ K grid > 0 denote the available tail levels no greater than τ max \tau_{\max} τ m a x , and let r t , j r_{t,j} r t , j be the corresponding raw predictions. We construct the conservative envelope v t , j = max 1 ≤ i ≤ j r t , i v_{t,j} = \max_{1 \le i \le j} r_{t,i} v t , j = max 1 ≤ i ≤ j r t , i , d j = log ( τ max / τ j g r i d ) d_j = \log\left(\tau_{\max}/\tau^{\mathrm{grid}}_j\right) d j = log ( τ m a x / τ j grid ) . Thus the repaired bound increases as the requested tail probability decreases, and no table entry is reduced. This is the smallest monotone majorant in the given ordering. Writing q t ( a ) = q ^ t ( X t ; τ max e − a ) q_t(a) = \widehat{q}_t(X_t; \tau_{\max}e^{-a}) q t ( a ) = q t ( X t ; τ m a x e − a ) , we set q t ( a ) = v t , j q_t(a) = v_{t,j} q t ( a ) = v t , j for the first index j j j satisfying a ≤ d j a \le d_j a ≤ d j . The resulting function is piecewise constant, with each endpoint assigned to the interval on its left.
Furthermore, our ACI+IPCW implementation clips the calibration parameter τ t \tau_t τ t to [ 0 , 1 ] [0, 1] [ 0 , 1 ] . Under tight budgets, zero-budget rounds yield raw IPCW feedback e ^ t = 0 \widehat{e}_t = 0 e t = 0 , increasing τ t \tau_t τ t and shrinking subsequent bounds, while clipping can truncate the compensating updates from observed errors weighted by 1 / π t 1/\pi_t 1/ π t . We therefore apply a small conservative adjustment, using e ^ t p e n = e ^ t + 1 { C t = 0 } \widehat{e}^{\mathrm{pen}}_t = \widehat{e}_t + 1\{C_t = 0\} e t pen = e t + 1 { C t = 0 } , which assigns unit feedback on skipped rounds. Under the two-point allocation in (22), E [ e ^ t p e n ∣ X t , D t − 1 ] = m t + 1 − G t ( U t ) ≥ m t \mathbb{E}[\widehat{e}^{\mathrm{pen}}_t \mid X_t, \mathcal{D}_{t-1}] = m_t + 1 - G_t(U_t) \ge m_t E [ e t pen ∣ X t , D t − 1 ] = m t + 1 − G t ( U t ) ≥ m t . This conservative modification preserves the coverage lower-bound argument for the unprojected update in Theorem 13, with asymptotic validity retaining its calibration-state condition. Its behavior with practical clipping is assessed empirically in Appendix E.4, motivating its use in the main evaluation.
Additionally, the completion distribution F ^ t \widehat{F}_t F t can be learned using a dedicated predictive model; we use a lightweight estimator to reduce computational overhead and enable faster experimentation. Full implementation details, all hyperparameters, and the configurations used to generate the experimental results reported in this paper are available in our GitHub
Compute Infrastructure and Hardware Specifications
All experiments were conducted on a Linux server running Ubuntu 22.04.5 LTS, equipped with an Intel Xeon 6746E processor (224 threads) and 2 TB of RAM. Hardware acceleration was provided by a cluster of 8 NVIDIA H200 NVL GPUs, each with 141 GB of VRAM. The experimental framework and models were implemented in Python using PyTorch 2.13.0 (CUDA 13.2, cuDNN 9.2.0).