- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes Online Backward Conformal Prediction (OBCP), extending backward conformal prediction to sequential classification under distribution shift while enforcing a fixed prediction-set size budget. The authors introduce a clipped-product surrogate that upper-bounds the miscoverage indicator without relying on the e-value expectation condition. They establish a fixed-time high-probability risk bound consisting of a recency-weighted historical statistic, a target-drift term, and a concentration term. The paper further investigates the relationship between the proposed surrogate and empirical error counting, theoretically characterizing when the former yields tighter risk certificates. Experiments on synthetic distribution shifts and the CLEAR10 dataset demonstrate the behavior of the proposed risk-reporting framework.
Critical strengths
-
Unlike conventional conformal prediction approaches that primarily control coverage while allowing prediction-set sizes to vary, the proposed framework emphasizes risk reporting under a fixed set-size budget. This complementary perspective is well motivated.
-
The introduction of effective sample size and weighted mean lag provides an intuitive interpretation of the tradeoff between emphasizing recent observations and retaining sufficient statistical information.
Critical weaknesses
- Theorem 1 provides a risk bound involving the target-drift term , which depends on unknown conditional expectations. Corollary 1 replaces this term with a prediction-time allowance, but the framework does not provide a generally applicable procedure for obtaining such an allowance from observed data.
- The paper defines the conditional surrogate target as , where includes the current input . Consequently, variations in may arise not only from changes in the underlying data-generating distribution but also from differences between consecutive inputs. Even under a stationary i.i.d. data distribution, the conditional risk and conditional surrogate expectation can fluctuate substantially across heterogeneous inputs. The paper would benefit from a clearer discussion of the assumptions under which conditional target variation remains sufficiently small, particularly when the covariate distribution is heterogeneous.
Questions for authors
- How can a valid drift allowance be constructed in a realistic deployment setting? Corollary 1 requires a prediction-time upper bound on . Can the authors provide an implementable estimator or conservative bound based only on observable online data, without access to the true conditional label distributions? In particular, could such a procedure generate nonvacuous certificates on CLEAR10 or another real-world dataset?
- Since the candidate ratios preserve the ordering of the nonconformity scores, it appears that feasible prediction sets reduce to selecting the smallest-score labels when scores are distinct. Can the authors confirm this characterization? If so, what is the main advantage of the online backward construction over applying a fixed top- predictor with a separate sequential risk-monitoring procedure?
4 comments
Question 2. We thank the reviewer for this insightful observation. Importantly, the connection with Top- prediction concerns label selection, rather than the conditional risk-certification framework developed in our work. In fact, the relationship between fixed-size prediction and Top- selection is already recognized in classical BCP (Gauthier et al., 2025, Remark 3.4), where empirical Top- error counting is explicitly discussed as a natural alternative. Similarly, when our construction is feasible, the reference-score sum is positive, and candidate scores are distinct, OBCP selects the smallest-score labels. This shared selection property does not, however, determine how prediction risk should be monitored and certified over time, which is the central focus of our work.
The central novelty of OBCP lies in its risk-certification framework for fixed-budget online predictions, which goes substantially beyond Top- label selection. Specifically, we construct an inflation-corrected clipped-product surrogate that pointwise upper-bounds miscoverage under distribution shift. Equation (3) establishes its exact decomposition into empirical error counting and an additional soft component that retains continuous boundary information. Theorem 1 provides a fixed-time conditional risk bound combining historical products, target drift, and sampling uncertainty, while Corollary 1 yields a prediction-time certificate given a valid drift allowance. Furthermore, Corollary 3 characterizes the tradeoff between the additional conservatism of the Product statistic and the potential improvement in target stability, which can lead to tighter risk certificates. These theoretical properties and certification guarantees are not provided by Top- selection alone.
Beyond our existing comparison with empirical counting (Sections 3.4 and 4.3), we further consider an independent and straightforward score-aware monitor constructed directly from the Top- selection threshold, without relying on BCP or OBCP:
Q_t^{\mathrm{Margin}} = \min\left\\{\frac{S(X_t,Y_t)}{S_{t,(B+1)}},1\right\\},
where is the nonconformity score of the realized label, and is the -th smallest score among all candidate labels, corresponding to the Top- selection threshold. The corresponding rolling monitoring statistic is . For a fair comparison, both methods use the same three-component risk certification framework: a historical surrogate average, a drift allowance, and a concentration radius.
Using identical Top- predictions in an exploratory controlled simulation with AR(1) covariates, ordered-probit labels, and fixed softmax NLL scores (, , , ), we evaluate both monitors over independent trajectories. As in Section 5, we use the known data-generating distribution to compute the oracle accumulated drift.
| Metric | OBCP | Plain Margin |
|---|---|---|
| Historical surrogate average | 0.086 | 0.073 |
| Oracle Gamma | 0.278 | 0.315 |
| Full certificate | 0.451 | 0.475 |
The full certificate is the sum of the historical surrogate average, Oracle Gamma, and a common concentration radius, which is omitted as a separate row for brevity. These results illustrate that backward normalization can reduce accumulated target drift sufficiently to offset its additional conservatism, yielding a tighter oracle risk certificate. We will further clarify the Top- equivalence and the novelty of our monitoring construction in the revised manuscript.
Closing Remark. We sincerely thank the reviewer for the careful evaluation and constructive feedback. We greatly appreciate the opportunity to strengthen the manuscript through this discussion. If any questions or concerns remain, we would be very grateful to hear them and would be happy to provide further clarification.
References
Gauthier, E., Bach, F., and Jordan, M. I. (2025). Backward Conformal Prediction. The Thirty-ninth Conference on Neural Information Processing Systems (NeurIPS 2025).
Thank you for the detailed rebuttal and revisions. Most of my concerns have been addressed and I have raised my score to 3.
We sincerely thank the reviewer for taking the time to carefully consider our rebuttal and revised manuscript. We truly appreciate your constructive feedback and reconsideration of our work.
We thank the reviewer for their careful assessment and valuable feedback. We have strengthened the manuscript to address the key concerns. We respond to each point below.
Responses to Critical Weaknesses
Weakness 1. We have addressed this concern by constructing a prediction-time observable drift allowance under a simple normalized-mean stability condition, without requiring unknown conditional label distributions or future outcomes. On CLEAR10, our construction yields nonvacuous full risk certificates at 82.68 of evaluation times. We have added the construction and results in blue to Section 6 and Appendix C.8, with further details in our response to Question 1 below.
Weakness 2. We agree that heterogeneous covariates can cause conditional-target variation even under stationarity. Our theory accounts for such variation without restricting the underlying shift mechanism. To address this concern, we have added a four-dimensional Gaussian experiment (Section 5.3; response to Reviewer zbzx, Question 1) and observable CLEAR10 certificates under an explicit stability condition (Section 6; Question 1 below), both highlighted in blue in the revised manuscript.
Responses to Questions
Question 1. Yes. We now provide a concrete, prediction-time implementable drift allowance that yields nonvacuous full risk certificates on CLEAR10, using only observable online information, without requiring the true conditional label distributions or future outcomes.
Before presenting our construction, we first emphasize that we strictly exclude any future information from prediction-time computation. Without additional conditions, there is no general procedure that can guarantee nontrivial conditional risk certificates in arbitrary online settings. This is a fundamental information limitation of online conditional risk certification, independent of the dataset, the prediction method, or the specific form of the drift correction. It is not a limitation specific to OBCP. We have added a rigorous proof in Appendix A.4, highlighted in blue.
Nevertheless, a simple normalized-mean stability condition already suffices to construct a nontrivial observable allowance. At each feasible time, let ℓt=miny∈Yut(y) and Zt=(Qt(1)−ℓt)/(1−ℓt)∈[0,1]. Writing θt=E[Zt∣Gt] gives the exact identity βt∘=ℓt+(1−ℓt)θt.
Under the stability condition θt=θ∈[0,1], we use previously revealed normalized products to construct a confidence lower bound θt−1 and obtain
Γt,w=(1−θt−1)∑q=1mAq(w)∣ℓt−q+1−ℓt−q∣.
This upper-bounds our original accumulated Γβ,t(w) with high probability, so Corollary 1 applies directly without modification. We have added this construction in blue to Section 6, with the detailed confidence procedure and proof in Appendix C.8. We also tested the temporal stability of the normalized-product mean on CLEAR10, obtaining encouraging results (HAC(20) Wald test, p=0.534). The test is detailed in Appendix C.8 (highlighted in blue).
We evaluate the resulting prediction-time observable drift allowance and the complete three-term risk certificate on the chronological CLEAR10 stream:
The complete numerical results have been added in blue to Appendix C.8 (Table 10). The core implementation code for this CLEAR10 experiment is provided in the supplementary material under the
CLEAR10_Rebuttalfolder. These findings demonstrate that our original Gamma-based certificate is practically implementable using only observable online information and need not be overly conservative.