acceptodds
Under review as a conference paper at ICLR 2027

When Is Calibrated Confidence Sufficient for Optimal Stopping in Sequential Prediction?

Abstract

Sequential predictors use confidence to decide whether to answer, abstain, or spend more computation. Calibration at each fixed time is insufficient for this task: it pools histories with the same score even when they differ in current error risk or future informativeness. We separate these two roles. For the terminal answer/abstain choice, the relevant quantity is the probability that the current answer is correct conditional on the observed history. We study scores equal to this conditional probability, the binary form of an ideal forecast relative to the available information. This condition holds at every fixed time exactly when it holds at every bounded stopping time, and it characterizes calibrated scores that support Bayes-optimal terminal decisions for every reject cost. For continuation, however, even an ideal confidence forecast need not be a sufficient statistic for control: equal scores can require opposite actions and leave a constant-order risk gap. A Bellman recursion based only on confidence is valid uniformly over bounded horizons, costs, and terminal losses exactly when the next-score law depends on history only through the current score. Calibration at each fixed time can also leave a constant-order gap. If the score is uniformly within of the history-conditional probability, optimizing the surrogate stopping problem on the same filtration incurs at most regret; a tie-free construction makes the constant tight. Numerical examples recover the theoretical gaps. A real-data diagnostic reveals residual history dependence but no decision-cost gap under the tested costs.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
confidence calibration, uncertainty quantification, sequential prediction, optimal stopping, selective prediction, abstention, Bayesian decision theory, state abstraction

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_4Zy3OpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper is a pure theory work, and studies calibrated confidence in sequential predictors. Specifically, it shows when calibration scores at each timestamp are insufficient for decision making. The authors introduce the notion of ideal confidence, and show that for the final "abstain vs answer" decision, their introduced notion of ideal confidence is enough. In contrast, for the decision to continue, even ideal confidence is insufficient and only works under additional Markov assumptions. The paper concludes with an error bound under this Markov assumption.

Critical strengths

The strengths of the paper are mainly that it is a complete piece of theory:

  • The question is timely and relevant.
  • The paper is self-contained, introduces necessary notation and provides proofs in the appendix.
  • While I did not check the proofs in detail, they appear to be sound.
Critical weaknesses

I have three major concerns:

  • The most obvious one is that there is no empirical validation in the main paper whatsoever. There is no problem with theory-heavy papers that have somewhat limited experimental evidence, but the paper moves all results to the appendix. This makes it, in my opinion, not suited for ICLR.

  • This connects to the missing experiments, and is, in my opinion, even more important: While I do think the formalization and the core findings are sound, and are possibly interesting for a mathematics outlet, there is no practical algorithm or deployable method. The paper is merely characterizing the problem (sometimes confidence is sufficient, sometimes it is not), but gives no guidance on i) how to estimate the ideal confidence, or ii) what to do in practice for the non-markovian case.

  • To be fair with the authors, I also checked the appendix for the (limited) experiments they attached. The real world dataset is basically a negative result of their theory. I appreciate the honesty of the authors that they attached this result, but there are basically no improvements in terms of decision risk.

So in summary, while the theory looks good, I have serious doubts that the work in its current stage has the potential for ICLR; sufficient experimental validation is missing, practical tools are missing, and the limited experiments in the appendix are more or less a negative report.

Questions for authors
  • How would you estimate ideal confidence in practice?

  • How do you deal with the non-markovian case?

  • Do you have explanations why your experiments do not show any serious improvements?

2 comments

Thank you for your comments. The revision makes the theoretical objective explicit: identify the information needed for stopping decisions and quantify the cost of approximating it. We have added controlled numerical illustrations and concrete learning procedures to connect those results to policy construction.

How would we estimate ideal confidence? The target is the conditional mean of the observed correctness indicator, $r_t(h_t)=\mathbb{E}

1Y=Y^t∣Ht=ht\mathbf{1}\\{Y=\hat{Y}_t\\}\mid H_t=h_t

$. Section 3.5 now describes fitting this quantity with a proper scoring rule on independent complete labeled trajectories from a frozen predictor. Splits are by trajectory, not by exit, and fitted targets and final evaluation data are separated. A score-only recalibrator estimates a conditional mean given the score; history features estimate a mean given those features. Neither automatically recovers the conditional probability given all accessible history.

The same section gives a finite-class alternative that learns stopping and terminal decisions directly from realized trajectory costs, without first estimating ideal confidence. Proposition 8 supplies its oracle excess-risk bound. We also give a pre-specified conditional-residual test with a finite-sample null bound, explain what rejection means, and explicitly exclude interpreting nonrejection as a sufficiency certificate.

What should be done when confidence is non-Markov? Retain information needed to predict continuation: prior scores, candidate identity and changes, margins, observed signal quality, and time remaining are possible features. Another option is to regress continuation directly on the observed prefix. We now state the backward recursion and its training protocol. Proposition 16 in Appendix A.22 bounds the executed policy's risk through probability error and continuation-prediction error without requiring a scalar Markov state. Section 3.5 includes its main inequality.

An example in Section 3.3 makes the remedy concrete. Under an asymmetric binary observation channel, two histories have MAP confidence 0.6 but different candidate labels. Their continuation errors are 0.22 and 0.28. At step cost 0.15, retaining the candidate identity restores the optimal decision; confidence alone loses 0.015 in total risk. This is an example-specific sufficient augmentation, not a guarantee that any larger feature vector is sufficient.

Purpose of the numerical examples. The paper's contribution is primarily theoretical. Its central comparisons concern the optimal risks attainable from different information sets under the same observation law, costs, and action space. Section 3.6 uses controlled constructions to make those comparisons explicit. Table 2 lists every policy in the finite-class example, including both fixed-time rules, so the information gap can be checked directly rather than inferred from a calibration metric.

The theory also explains why different continuation laws need not change the decision at a given cost. Proposition 2 identifies the relevant condition: histories sharing a score must favor opposing actions. A claim of general practical superiority would require an application-specific model, estimator, and evaluation beyond that information comparison. We have kept the paper's claims within its theoretical scope. The supplementary calibration plot is descriptive: refining score bins increases the empirical absolute-residual sum mechanically, so that comparison alone is not a test of history dependence or a policy-risk guarantee.

Main-text evidence and theorem scope. Figure 1 now includes exact construction checks and a finite-data learning experiment where history-based policies approach risk 0.275 while score-only policies approach 0.325. The comparison isolates the contribution of accessible history within a fully specified model. Finally, Theorem 8 does not assume Markov confidence: its true and surrogate optimizations use the same full filtration. The approximate-kernel result is separate. We have made that distinction explicit next to both statements.

We hope we addressed your comments in a satisfactory manner.

Thank you for your rebuttal. Unfortunately, I do not think the additions address my main concerns.

Your revised Section 3.5 outlines finite-class empirical risk minimization and backward regression. They are standard procedures and not a new algorithmic contribution. The theoretical guarantees either involve an uncontrolled policy-class approximation term or depend on population-level estimation errors that are not directly observable / controlled. Finally, the question of how to obtain a sufficiently informative representation + reliable stopping decisions in realistic non-Markovian settings is still unclear.

The experiments are also insufficient. Figure 1b considers only four history-based versus two score-only policies in a constructed two-step example. Convergence to the corresponding oracle risks maybe confirms the theoretical construction but does not show practical usefulness.

More importantly, there is still no convincing real-world validation of improved stopping decisions. The real-data analysis is a calibration diagnostic, and not an evaluation of decision risk, and the authors themselves acknowledge that the observed increase in ECE is a mechanical consequence of bin refinement.

I appreciate your efforts to improve the paper. However, the fundamental limitations remain completely unchanged: the contribution is a theoretical characterization of information sufficiency, without a compelling new learning methodology or any convincing empirical evidence that the findings lead to improvements in practical applications. I therefore maintain my original concerns and rejection recommendation.

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

The paper studies mathematical conditions when the classification score of sequential data is sufficient for minimizing Bayes risk, which is a linear combination of wrong answer risk, abstention cost, and continuation risk. The paper mentions that properly calibrated score is not necessarily sufficient for the Bayes risk minimization, and characterize mathematical properties and perturbation bounds. It does not present a new learned stopping method.

Critical strengths

The paper offers mathematical characterizations of sequential early classification under finite horizon. The paper also provide useful conterexamples where ordinary calibration fails. And it provides perturbation bounds.

Critical weaknesses

Note that the following represents my initial impression of the paper, and I am open to discussion. I welcome any corrections to my potential misunderstandings.

Critical presentation issue.

The paper narrative is very hard to follow. After reading the abstract and introduction it is not clear that what task the paper studied: sequential hypothesis testing? quickest changepoint detection? Or, time-series forecasting? "optimal stopping" in the title can indicate the former two, while "sequential prediction" can be any of them (thus, title scope needs improvement). The introduction quickly moves into notation and technical examples, without clearly presenting what is the task, what is the existing problem that researchers in this field suffer, and why do we need to care. Paper in top-tier venue like ICLR needs to convey these message clearly to broad audiences.

The paper discuss sufficiency of statistics and optimality of the task, but the sufficiency must depends on the task: it must be clarify, e.g., sufficient for which decision, under which loss, relative to which available infromation, for which horizon. After reading the main text a reader can find that they cite Wald's sequential test, thus it is likely hypothesis testing, or early classification of time series (ECTS). Introduction mentions neither, and only with hindsight a reader can understand that the "target Y" is likely to be a class label.

Another severe concern is that the abstract contains a claim that is not supported in the main text. Specifically, it mentions "numerical examples" and "real-data diagnostic" but they are not in the main 9-page text. After spending some time I found that they are in Appendix. However, I believe that readers should not need Appendix to discover the principal evidence for a claim advertised in the abstract. The main paper is filled with many mathematical statements, without any figures. Although zero figures by itself cannot be a rejection ground, the paper needs to work on what is the problem and scope of the study, and what should be prioritized for presentation.

Because the presentation issue is severe and the manuscript needs to undergo rigorous major revision, and because reviewers need to access the updated version to decide if its acceptable, I am afraid that it is difficult to raise the score above the acceptance bar, unless I have a serious misunderstanding.

Limited novelty and incomplete positioning.

If I understand correctly, The paper's Theorem 2 is a specialization or Corollary that is immediately derived from Tasche's sufficiency characterization (Calibrating sufficiently, Statistics 2021). Moreover, FIRMBOUND (Ebihara et al. ICLR 2025) already learns finite horizon Bellman stopping rules with a consistency guarantee. Neither of them are cited in the manuscript. The manuscript must acknowledge the omitted papers, reorganize existing results systematically, and explain precisely what remains new in the manuscript beyond the previous works.

In light of these two existing works, the novelty of the paper narrows down to very incremental contribution. These two are the critical weaknesses that prevent me from recommending acceptance.

Questions for authors

Could you please confirm that my understanding below is correct?

  • The task is online classification of a time series data under finite horizon.
  • The paper contribution is purely theoretical characterization of existing issue, without presenting a new solution (Note that I am not suggesting that a theory without new solution is a rejection ground).

Also, the manuscript says “Estimation remains open” on page 9. That statement is hard to understand. Could you explain what estimation is mentioned here?

3 comments

Friendly reminder to the authors: As the discussion period deadline is approaching, I would appreciate an early rebuttal response if any, as I will soon be busy handling the discussion of my own paper. Thanks!

Thank you for your comments on task clarity and prior work. We have rewritten the opening around finite-horizon classification, credited the terminal result to Tasche, and expanded the FIRMBOUND comparison. The main text now includes a scope table, a learning procedure, and controlled numerical illustrations.

What is the task? A fixed predictor receives observations about one fixed finite class label. After each observation, it proposes a candidate, and a controller chooses to answer with that candidate, abstain, or acquire another observation before a deadline. Early classification of time series is a direct instance. The target is not a changing quantity to be forecast, and the objective is not quickest change-point detection. Section 2 specifies the observations, decision order, available information, costs, and comparator. Table 1 distinguishes terminal sufficiency, agreement of stopping actions for one cost regime, and preservation of values across a family of stopping problems.

Tasche and Theorem 2. We agree with your attribution. Taking the event A=Y=Y^τA=\\{Y=\hat{Y}_\tau\\} and sigma-fields H=Fτ\mathcal{H}=\mathcal{F}_\tau, G=σ(sτ)\mathcal{G}=\sigma(s_\tau) makes the theorem an application of Tasche's Theorem 3.4 and Corollary 3.5. A random stopping time does not turn this into a new static sufficiency result. Section 3.1 now gives that mapping explicitly, labels Theorem 2 as an application, and removes it from the contribution claims. The proof remains for self-containment and tie handling.

FIRMBOUND and the remaining contribution. Section 4 now discusses Ebihara et al. (ICLR 2025): FIRMBOUND estimates finite-horizon stopping rules through likelihood-ratio and continuation estimation, with a consistency result for its specified density-ratio/convex-function construction under its assumptions. We distinguish that result from the Gaussian-process implementation. We do not claim that learning a Bellman stopping rule is new, or describe FIRMBOUND as restricted to i.i.d. observations.

Our focus is the information retained by a supplied scalar correctness report. The comparisons keep the predictor, observation law, action set, and costs fixed, isolating the information in the report. The revised theory makes that distinction more specific:

  • Proposition 2 gives an exact two-step expression for the risk lost by ignoring history. Different future laws matter only when they produce opposing preferred actions within a score class. For binary MAP prediction without abstention, this gives a sharp upper bound of cerr/8c_{\mathrm{err}}/8. The original near-cerr/4c_{\mathrm{err}}/4 construction permits non-MAP candidates; we now state that distinction explicitly.
  • Proposition 3 strengthens the uniform characterization for MAP confidence. Under its submartingale property, scalar values for all subhorizons, reject costs, and step costs tending to zero already imply the full-history next-score kernel condition. Thus the necessity argument can use the actual answer/abstain loss family. It still does not make that kernel necessary for one fixed cost regime.
  • Proposition 5 strengthens the probability-error sharpness result: the constant 2 is approached at every fixed admissible reject cost, including no abstention, with strict MAP candidates and strict stopping comparisons. The construction makes no terminal-action error; the regret arises entirely from stopping too early.
  • Propositions 6 and 7 separate approximate model values from the risk of the executed policy. These bounds are positioned as stopping-specific applications of approximate information-state planning, with the relevant prior work cited.

Theory versus a new solution. The paper remains principally theoretical. Section 3.5 gives a finite-class learner, a standard oracle excess-risk guarantee, and a history-based regression procedure with an error-propagation bound. Figure 1(B) connects the information comparison to a concrete statistical procedure.

Numerical illustrations and theoretical scope. The paper studies which information is sufficient for terminal decisions and continuation, and how approximation errors affect policy risk. Section 3.6 therefore uses controlled constructions whose optimal policies and risks are known. Figure 1 and Table 2 distinguish the information gap from finite-sample policy-selection error, include fixed-time policies, and illustrate the sharp regret constant without ties. These examples support the theoretical analysis; we do not claim a new general-purpose controller or empirical superiority over existing methods.

We have replaced the broad statement that estimation remains open. The remaining task is to establish history-relative approximation rates for a specified representation and data regime. Existing stopping estimators address structured cases. The opening and setup clarify the classification setting

We hope we addressed your comments in a satisfactory manner.

Thank you for your detailed reply. I now see substantial improvement in the main text. Now the relationship to important related work, namely Tasche’s paper and FIRMBOUND, is clearer, and the task structure is also well defined. The revised manuscript is almost entirely blue and looks like a different paper, but I appreciate the authors’ hard work to address my concerns and accordingly will raise my score.

However, remaining concerns prevent me from making a clear recommendation for acceptance. First, now that the paper narrows its claims in light of the updated related-work discussion, it should clearly discuss the significance of the remaining theoretical contribution and why the problem is important. The current introduction has improved over the original, but it still reads like Section 2, setting up technical preliminaries. The introduction should clearly explain why the authors chose to tackle the problem, why it is important, and why readers should take the time to understand it. This is especially important for a top-tier conference like here, but it remains insufficiently addressed in the current introduction. Given that the contributions already established by Tasche and FIRMBOUND cannot be counted toward this paper’s novelty, I would say the remaining contribution as somewhat incremental.

Reviewer_8iqROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies a “sequential prediction problem”, where given X from a pair (X,Y), the learner is asked to iteratively produce predictions \hat Y_t to predict Y. After each prediction \hat Y_t, some relevant information Z_t is revealed to the learner, which can be used to produce the next prediction \hat Y_{t+1}. The cost of this problem is determined by the length of the prediction sequence, which itself is a random variable (stopping time), and the final answer (or abstain if the predictor chooses to so) given by the learner. The problem itself is a simple but interesting and fundamental problem by itself. The main results established in the paper are the conditions under which the various definitions of confidence (in Def. 1) are sufficient or insufficient for optimal stopping. And also how different is the cost (characterized by regret) if different types of confidence are used.

Critical strengths

I think the paper considers an interesting problem and the results obtained in the paper are potentially useful. The main concern I have for this paper is that I don’t know if this paper establishes the results that I would expect from this problem.

Critical weaknesses

For this problem, I would expect a solution (or at least some good characterization of solutions) to the “optimal” learning strategy, which would specify the stopping strategy and the decision after the stop, only based on the data (e.g. X, Z_1, Z_2…), and a characterization of the optimal cost. Also, in terms of defining “optimal”, I would expect a definition of some form of “regret”, where the learning algorithm is compared to an “oracle” which has access to additional distribution information, either the distribution of X,Y (which would the oracle to make the prediction in one step, or additional information on how Z’s are related to Y). However, this paper does not seem to provide these type of results . There are discussions on the optimal stopping strategy and expected optimal cost in Theorem 3 and 6. But they all seem to assume that we know the data distribution. There is the notion of regret in section 3.4 (Theorem 8), but they compare the cost obtained from the history-conditional probability and “reported confidence”.

It seems to me that the main result established in the paper is the conditions under which the various definitions of confidence (in Def. 1) are sufficient or insufficient for optimal stopping. Even there, I think it is assumed that a relevant probability model is available.

So these results seem to be correct, but I don’t know how useful they are for the learning problem (which is itself a very interesting problem)

Some minor comments

  • Line 55, “first quantity”, what is this?
  • In the problem formulation, it is mentioned Z_1, Z_2… are signals “revealed by the prediction system”, but it is not specified how they are related to other quantities in the problem (e.g. Y, \hat Y_t). Then I found that it is specified for an example in Proposition 3. Is there any restriction on how Z_t could be generated for the general results?
  • The notations in Definition 1 (item 1 and time 2) is not optimal. I read P(Y=\hat Y_t | p_t) as a conditional probability. But it is not very clear what event "p_t“signifies. Does it mean that the output confidence value (itself a random variable) equals the value p_t?
Questions for authors

see "weakness" section

2 comments

Thank you for distinguishing the information question from the learning question. The submitted paper primarily answered the former. Theorems 3 and 6 are population optimal-control statements: they require conditional probabilities or transition laws and are not, by themselves, learning algorithms. We have made that scope explicit and added a data-only learner, its oracle comparison, and an experiment showing how estimation error differs from information lost by the policy class.

Learning and the comparator. Section 2 now fixes the predictor, observation process, deadline, and available actions. The oracle knows their joint distribution, but receives the same realized observations at the same times as the learner. It cannot see future signals, observe the target, change the predictor, or answer with an arbitrary label instead of the current candidate. Knowing the distribution alone therefore need not permit a correct one-step answer.

Section 3.5 specifies a finite-class learner. Given independent complete labeled trajectories, replay each candidate policy, average its realized observation and terminal costs, and select an empirical minimizer. A policy specifies both stopping and answer/abstain decisions. The candidate class must be fixed independently of the policy-selection trajectories, or constructed on separate data. Proposition 8 gives, with probability at least 1−δ1-\delta,

R(π^)−R∗_F≤inf⁡π∈ΠR(π)−R∗_F+2Blog⁡(2∣Π∣/δ)2n,B=cstep(T−1)+cerr.R(\hat{\pi})-R^*\_{\mathcal{F}}\le \inf_{\pi\in\Pi}R(\pi)-R^*\_{\mathcal{F}}+2B\sqrt{\frac{\log(2|\Pi|/\delta)}{2n}},\qquad B=c_{\mathrm{step}}(T-1)+c_{\mathrm{err}}.

This is a standard uniform-convergence argument, which we identify as such. Its first term matters: a policy class that omits relevant history can remain separated from the full-history oracle even with unlimited data. Figure 1(B) implements this learner in the two-step revelation model. Empirical selection over four history-based policies approaches risk 0.275; selection over the two score-only policies approaches 0.325. Training uses realized trajectory losses, and the selected policies' test risks are computed exactly from the synthetic law.

Approximation and implementation. Theorem 8 retains its original scope: it compares true and surrogate stopping problems on the same full filtration and requires no Markov assumption. Proposition 6 separately bounds the risk of a policy executed after an approximate scalar Bellman calculation:

R(π~)−R∗_F≤2cerrε+2∑t<Tκt.R(\widetilde{\pi})-R^*\_{\mathcal{F}}\le 2c_{\mathrm{err}}\varepsilon+2\sum_{t < T}\kappa_t.

Here ε\varepsilon bounds error relative to full-history correctness, and κt\kappa_t bounds error in the predicted next-step value. We repaired the approximate-kernel argument by evaluating the executed policy separately from the approximate model value. The revised Proposition 7 states both bounds. Section 3.5 and Appendix A.22 also describe history-based backward regression; Proposition 16 bounds its risk through probability and continuation regression errors, conditional on independent training data. These bounds do not establish that arbitrary fitted models satisfy their assumptions.

Signals, timing, and notation. Section 2 now states the order explicitly: observe ZtZ_t, receive (Y^t,pt)(\hat{Y}_t,p_t), then act. The general results allow arbitrary dependence in the fixed joint law; conditional independence is imposed only in the particular sufficient models. We also explain that deterministic computations of an already fully visible input do not enlarge the statistical filtration. Definition 1 now writes calibration as $\mathbb{E}

1Y=Y^t∣σ(pt)\mathbf{1}\\{Y=\hat{Y}_t\\}\mid\sigma(p_t)

=p_t$. Conditioning on the random score means conditioning on its generated sigma-field. Finally, the introduction replaces “the first quantity” with “the conditional error cost of answering now.”

The added learning comparison is deliberately modest. It supplies a complete finite-data procedure and exposes its approximation term, while leaving estimator-specific rates for richer history representations to a separate analysis.

We hope we addressed your comments in a satisfactory manner.

Thank you for your detailed response. It seems that the entire main text is marked in blue in the revised version. Does this mean that the whole paper has been completely rewritten?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.