Valid Selection among Conformal Sets

We thank the reviewer for their detailed feedback and for recognizing our work's mathematical rigor and originality. We are glad you found our contributions noteworthy. Your comments on the paper's clarity and experimental justification are very helpful, and we address them below. They are roughly by the order of first mention of the review.

1. On the paper's clarity and flow: We agree that the paper is dense and thank you for taking the time for a second reading. We will use the extra page for the camera-ready version to revise the manuscript, focusing on improving the flow and better motivating our design choices to make the story easier to follow.

2. Application Setting and Ensembling: Thank you for this question, which allows us to clarify a key aspect of our contribution. There are two ways to use ensembles for uncertainty quantification: (1) average the model predictions and then conformalize the final predictor, or (2) generate a conformal set for each model and then select among the sets. Our work focuses on the second, which can be seen as "ensembling in the space of conformal predictors." This is a general concept that applies even with a single underlying prediction model, which itself can be an ensemble. For instance, one could have a single model but multiple different nonconformity scores. Our framework provides a valid way to select the among the different conformal prediction strategies. As such, even with the mean of an ensemble, it is possible to leverage it to build multiple conformal predictors. Thus, even in this case, our approach can still be valuable to select among different conformal predictors.

3. Experimental Motivation: The synthetic experiment aimed to illustrate this core idea by creating a diverse pool of conformal predictors. To make the application setting clearer, we will add a new experiment in the revision where we fix the underlying regression model but vary the conformalization procedures themselves. As such, we will have different conformal predictor build on the same single model.

4. On the baselines from references [11] and [12]: The baseline from [12] is the "best-on-average" conformal predictor in the sense that all $K$ conformal predictors are reevaluated on the full calibration set. Then, a single predictor (among the $k$ predictors) with best average performance (e.g., smallest average set size) is identified and then use that predictor for all future test points. This contrasts sharply with our method, which makes a dynamic, pointwise selection for each new point. We are pointwise in the sense that for every new test point $X$, we evaluate the conformal sets at $X$, and try to select the smallest set at $X$. To refer to example 3 in the paper, a best-on-average predictor will try to find the better performing conformal predictor among the third and fourth images ($f(X)=X$ and $f(X)=-X$) based on the average set size. Then, this predictor will be used for all future test points. Meanwhile, a pointwise mechanism makes the choice based on the specific realization of $X$ and as such produces the fifth figure ($\eta=\ln(2)$).

5. On the looseness of the coverage bound: The bound involving the $e^\eta$ factor, while potentially conservative, is tight. We show in Example 1 that there exist pathological (but valid) settings where the miscoverage is exactly $e^\eta \alpha$. This is the theoretical price for a guarantee that holds under minimal assumptions, even in non-stationary online settings. For practical use, we propose two solutions that address this: AdaMinSE, which adaptively tunes the stability parameters, and our Recal procedure, which completely circumvents this factor in split-conformal settings by performing recalibration after the selection procedure.

6. On the "pointwise selection" claim. This is an important point: the MinSE optimization is solved separately for each test point $X$. The optimization's input is the vector of set sizes $\xi = [\lambda(C_1(X)),\ldots, \lambda(C_k(X))]$, which explicitly depends on $X$. Consequently, the optimal probabilities $p_i(\xi)$ are a function of the current test point, enabling true pointwise selection. We will revise the text to emphasize this mechanism and clarify this aspect in the paper.

7. Real data models: Indeed, those are six regression models from scikit-learn and $K=6$.

8. On the nonconformity score and interval length: We do not use absolute residuals, which would lead to constant-length intervals. Our nonconformity score is $s_i(X, Y) = |f_i(X) - Y|/g_i(X)$, where $g_i(X)$ is a model trained to predict the residuals. This creates adaptive prediction intervals whose lengths vary with the input $X$, allowing each method to produce tighter intervals for "easier" instances.

9. On the details of the real-data experiments. For the real-data experiments, we used $K=6$ models, and we will make this explicit.

10. On the applicability to classification: Yes, our method is directly applicable to classification. To demonstrate this, we conducted a new set of experiments on the ImageNet_1k, which we will include in the revised manuscript. We believe this new experiment provides a compelling use case for our proposed selection framework.

    The experimental setup was designed to create a heterogeneous and challenging selection environment. We began with two pre-trained base models with different performance characteristics—one with a top-1 accuracy around 90% and another around 80%—and converted each into a standalone conformal predictor. These models naturally exhibit varying performance across the diverse classes in ImageNet. For the conformal scores, we used an adaptive score similar to the one used in the Appendix of [11].

    From these two base predictors, we constructed eight composite predictors. Each composite model creates a unique "risk profile" by outputing the conformal set either from the high-accuracy model or from the lower-accuracy model, depending on the specific input $X$. These eight models use different probability distributions for this choice, creating a diverse pool of predictors for the selection algorithms to manage.

We compared the following selection methods YK-Base, MinSE, and AdaMinSE. The results, averaged over multiple 10 runs, are presented below.

As shown, our proposed methods (MinSE, AdaMinSE) successfully achieve higher coverage with smaller sets. Furthermore, their pointwise selection capability allows them to produce smaller average prediction sets than the non-pointwise YK-Base baseline, demonstrating their advantage in more heterogenous settings.

• *On the missing Limitations section. We tried to discuss limitation in the checklist and throughout the paper. Nonetheless, we agree that a dedicated limitations section is of value and we will add one to the revised manuscript.

We thank the reviewer for his support and feedback. We remain available for any further discussion.

Erratum and recap on experiments We wanted to openly disclose that we detected after submission a typo in the code, in file batch_setting/rescale_residual.py line 162, cal_sigma should be cal_sigma[m]. This changes the performance of ModSel, that is ultimately on-par with YK-base (yet never better, in fact YK-base lower bounds the confidence set size of ModSel). Other methods are unaffected. It thus does not change the quality of the "best competitor".

This also doesn't change the conclusion of our experiments, summarized below:

• on bike sharing, our methods MinSE and AdaMinSE improve coverage by 2% while having a average length 10% below YK-Base. Recal achieves nominal coverage with set length more than 30% smaller.
• on abalone, differences are more minor: both YK-base and ModelSel undercover by 1%, Recal is valid and reduces set size by 5% against all competitors, while MinSE and AdaMinSE suffer from conservatism, overcovering by 2% and increasing set size by 10% w.r.t. YK-base
• on California housing, YK-base, ModSel, MinSE, AdaMinSE achieve the same length, but with more than 2% of extra coverage for MinSE and AdaMinSE. Recal has nominal coverage with length 25% smaller than any other competitor.

Thanks for the insightful discussion.

I am not an official reviewer for this paper. The following comment is not part of a formal review, and I want to avoid any undue influence on the discussion. My intent is simply to offer a pointer to the literature that might be relevant here. Please feel free to use or disregard this as you see fit.

Given two score functions, $s_0(x,y)$ and $s_1(x,y)$, the method in YK et al. performs a selection between them. This is equivalent to choosing a weight $w \in \\{0,1\\}$ for a blended score function:
s_w(x,y) = (1-w) s_0(x,y) + w s_1(x,y).\

A natural extension is to consider aggregation by allowing $w$ to be continuous in $[0,1]$ (e.g., $w=0.5$ for a simple average). This relates to work by Liang et al., where one could search for an optimal score by discretizing this range, e.g., finding the best score function among $s_0, s_{0.01}, s_{0.02}, \dots, s_{1}$.

For a different perspective, some work explores directly averaging the scores. For example, in Luo & Zhou (2025), given concavity of the score functions, the bound depends only on the dimension of $w$.

Luo & Zhou, "Conformity Score Averaging for Classification," https://openreview.net/pdf?id=Pvfd7NiUS6

We thank the reviewer for their constructive review. Your feedback is very valuable in improving our work. We address your questions and suggestions below.

• Regarding Empirical Evaluation: We thank you for this constructive suggestion. Your feedback prompted us to run new experiments on an ImageNet-1k classification task to better demonstrate the generality and scalability of our framework. Our experimental setup was designed to create a heterogeneous and challenging selection environment. We began with two pre-trained base models with different performance characteristics—one with a top-1 accuracy around 90% and another around 80%—and converted each into a standalone conformal predictor. These models naturally exhibit varying performance across the diverse samples of ImageNet. For the conformal scores, we used an adaptive score similar to the one used in the Appendix of [11]. From these two base predictors, we constructed eight composite predictors. Each composite model creates a unique "risk profile" by outputing the conformal set either from the high-accuracy model or from the lower-accuracy model, depending on the specific input $X$. These eight models use different probability distributions for this choice, creating a diverse pool of predictors for the selection algorithms to manage. All the composite predictors achieve marginal coverage guarantee.

We compared the following selection methods YK-Base, MinSE, and AdaMinSE. The results, averaged over 10 runs, are presented below.

As shown, our proposed methods (MinSE, AdaMinSE) successfully achieve higher coverage with smaller sets. This is due to their pointwise selection capability, which allows them to produce smaller average prediction sets than the non-pointwise YK-Base baseline.

• Time-Series Evaluation: As you correctly noted, our method is well-suited for time-series data. We would like to highlight the online experiments already present in the appendix, where AdaCOMA algorithm is evaluated on electricity forecasting and a synthetic task.

• Regarding Readability, Presentation, and Formatting: Thank you for these helpful suggestions. We will incorporate all of them in the revised manuscript to improve clarity. We also believe that making the example non-italic is easier on the eye. Using the extra page allowed in the camera-ready version, we will a conclusion section, which discusses the limitation.

• Response to Other Questions:

  • What is the probability in Eq. (3) over: The probability is taken over $\zeta$ and the randomness of CI itself. The statement holds for all $s$ and $\alpha$ is assumed to be fixed.
  • On distributional notion of stability: This is an insightful question. Our definition of stability is asymmetric (bounding an output distribution relative to a fixed one) and it is the minimal condition required for our coverage proofs to hold. I.E., the stability statement is only required with the reference distribution on the right-hand side and the output distribution on the left-hand side, but not vice-versa. We believe it would be possible to use the notion of stability you proposed to get our coverage guarantees. Nonetheless, due to symmetry, it may be stronger than necessary for the proofs.
  3. "adversarial" setup: We use the term "adversarial" in the standard sense from online learning theory. It means the sequence of data points $(X_t, Y_t)$ can be chosen by an adversary, which allows us to prove worst-case robustness to arbitrary distribution shifts over time. This is distinct from the concept of adversarial examples (i.e., perturbed inputs). We will clarify this distinction in the text.

We hope these responses and our new experiments fully address your concerns. We are happy to answer any further questions during the discussion period.

Erratum and recap on experiments We wanted to openly disclose that we detected after submission a typo in the code, in file batch_setting/rescale_residual.py line 162, cal_sigma should be cal_sigma[m]. This changes the performance of ModSel, that is ultimately on-par with YK-base (yet never better, in fact YK-base lower bounds the confidence set size of ModSel). Other methods are unaffected. It thus does not change the quality of the "best competitor".

This also doesn't change the conclusion of our experiments, summarized below:

• on bike sharing, our methods MinSE and AdaMinSE improve coverage by 2% while having a average length 10% below YK-Base. Recal achieves nominal coverage with set length more than 30% smaller.
• on abalone, differences are more minor: both YK-base and ModelSel undercover by 1%, Recal is valid and reduces set size by 5% against all competitors, while MinSE and AdaMinSE suffer from conservatism, overcovering by 2% and increasing set size by 10% w.r.t. YK-base
• on California housing, YK-base, ModSel, MinSE, AdaMinSE achieve the same length, but with more than 2% of extra coverage for MinSE and AdaMinSE. Recal has nominal coverage with length 25% smaller than any other competitor.

We are very grateful for your review and constructive feedback. We proceed to address your questions below.

Regarding experimental performance

The stability-based coverage bound (with the $e^\eta$ factor) can be seen as a worst-case guarantee. As shown in our synthetic examples, this bound is tight in pathological cases but can be conservative in more benign settings. This generality and robustness are precisely what make the framework applicable to the challenging online setting, with no distributional assumptions. However, it can result in overcoverage in less pathological cases.

To address this potential conservativeness in the more structured batch split-conformal setting, we introduced the recalibration procedure (Recal). It circumvents the stability bound by leveraging the rank structure of split-conformal prediction. We want to emphasize that Recal does not use an additional calibration set. We split the single, existing calibration data budget. Thus, the comparison with baselines is fair in terms of the total data used.

Recal thus indeed systematically outperforms competing methods, achieving valid coverage with up to 30% smaller intervals. However, MinSE and AdaMinSE do also provide some improvement on the validity/efficiency tradeoff. On 2 datasets, they reduce or maintain the set size (by 10% on Bike Sharing) while significantly reducing miscoverage (by more than 2% out of 10%). On the third dataset (Abalone), their average set size is indeed 10% above YK-base, but YK-base simply does not achieve validity, while both MinSE and AdaMinSE achieve coverage 91+%. See detailed recap on experiments at the end.

Regarding batch vs. online settings: For our online setting, indeed, AdaCOMA can adapt to shifts more quickly than alternative methods that are purely history-based.

Response to Questions:

1. How AdaMinSE optimizes parameters: Your understanding is perfectly correct. Instead of taking $\eta$ and $\tau$ as fixed inputs, AdaMinSE treats them as optimization variables within the linear program. The key intuition is that for any initial miscoverage level $\alpha'$ and a target level $\alpha$, there is a trade-off curve defined by $e^\eta \alpha' + \tau \le \alpha$. For each test point, AdaMinSE automatically finds the point on this curve that minimizes the expected set size for that specific instance, thus adaptively choosing the best tradeoff between $\eta$ and $\tau$.

2. Why MinSE sometimes outperforms AdaMinSE: This is a subtle but important point. While AdaMinSE is adaptive, its performance depends on the initial miscoverage $\alpha'$ provided. MinSE, in our experiments, uses a fixed $(\eta=1, \tau=0)$. Theoretically, if we were to run AdaMinSE with an initial level $\alpha' = \alpha / e^1$, it would be guaranteed to perform at least as well as this specific MinSE instance. The small performance differences observed in our experiments arise because the $\alpha'$ we chose for AdaMinSE may not have perfectly corresponded to this optimal point for the given dataset, making the fixed-parameter MinSE appear slightly better by chance.

3. Proof of outperforming a single confidence set: We cannot prove that our method will produce a smaller set than the best single predictor for every point. However, our framework is designed to be superior on average in heterogeneous settings where no single predictor is uniformly best (as illustrated in our Example 3). In such cases, being able to adaptively switch between predictors pointwise will naturally lead to a smaller average set size compared to being locked into any single predictor.

4. How to select the prior $b$: We investigated this direction. A principled way to set $b$ is via cross-validation, which leads to a bilevel optimization problem. The outer loop optimizes $b$ to minimize the average selected set size on a validation set, while the inner loop is the MinSE optimization itself. To make the problem easier, we found that adding a negative entropy regularizer to the inner problem makes it strongly convex and much more tractable, admitting efficient solution methods. For simplicity and because the paper was already dense, we used a uniform prior in our experiments. We will add a brief discussion of this approach for setting the prior to the appendix.

5. Extension to PAC coverage: Thank you for this insightful question. Our current framework provides guarantees on the expected miscoverage. PAC-style guarantees, which provide high-probability bounds on the empirical miscoverage rate (e.g., $P(\text{Miscoverage} > \alpha + \epsilon) < \delta$), are indeed a very interesting and powerful extension. This is a non-trivial next step, as it would require analyzing how the randomness from our selection mechanism interacts with the sampling randomness of the test data to affect the concentration of the miscoverage rate. Nonetheless, we believe this extension is achievable.

Thank you again for your feedback, which helps us to improve the paper. We remain available to answer further questions during the discussion period.

Erratum and recap on experiments We wanted to openly disclose that we detected after submission a typo in the code, in file batch_setting/rescale_residual.py line 162, cal_sigma should be cal_sigma[m]. This changes the performance of ModSel, that is ultimately on-par with YK-base (yet never better, in fact YK-base lower bounds the confidence set size of ModSel). Other methods are unaffected. It thus does not change the quality of the "best competitor".

This also doesn't change the conclusion of our experiments, summarized below:

• on bike sharing, our methods MinSE and AdaMinSE improve coverage by 2% while having a average length 10% below YK-Base. Recal achieves nominal coverage with set length more than 30% smaller.
• on abalone, differences are more minor: both YK-base and ModelSel undercover by 1%, Recal is valid and reduces set size by 5% against all competitors, while MinSE and AdaMinSE suffer from conservatism, overcovering by 2% and increasing set size by 10% w.r.t. YK-base
• on California housing, YK-base, ModSel, MinSE, AdaMinSE achieve the same length, but with more than 2% of extra coverage for MinSE and AdaMinSE. Recal has nominal coverage with length 25% smaller than any other competitor.

We thank the reviewer for their thoughtful feedback. Below, we address your valuable comments and questions.

Response to Weaknesses:

• Regarding Novelty: We thank you for acknowledging the novelty and non-trivial nature of our contribution.

• Regarding Computational Overhead: We appreciate this practical question. The complexity has two parts: generating $K$ candidate sets, which is somewhat inherent to ensembling-like methods and scales linearly in $K$, and our selection step. The selection, using our algorithms, is efficient. For example, although, we formulated MinSE as a linear program (generally requiring approximately $O(K^3)$ steps to solve), it actually admits a greedy solution with $O(K \log K)$ complexity. This is often negligible compared to the complexity of model inference.

3. Regarding Fairness of Empirical Comparison: We chose methods from Yang et al. (2024) and Liang et al. (2024) as they are prominent recent works that address the same challenge of selecting from a pool of conformal predictors. As such, the benchmarks are also methods that see and select among a pool of conformal sets.

4. Regarding the Definition of Set Size $\lambda$: The assumption that $\lambda(C_i^{\alpha}(X)) \in [0,1]$ is made only for notational convenience in Lemma 1 and 2, as noted on Line 157, and is not required for MinSE (and its extension AdaMinSE). As shown by Proposition 1, MinSE algorithm represents the optimal stable algorithm. As such, within the context of this paper, there is generally no motivation to use Lemma 1 and 2 for the selection step and we mainly included them to illustrate different examples of stable selection algorithms. Nonetheless, even for Lemma 1 and 2, the requirement that $\lambda(C_i^{\alpha}(X)) \in [0,1]$ can be relaxed up to a simple rescaling preprocessing step. For all of our experiments in the paper, we used $\lambda$ to be the size the set as measured by the Lebesgue measure. For the experiments in the classification setting, $\lambda$ can be set to the counting measure of different confidence sets.

5. Regarding AdaCOMA and Prediction Set Size: You are correct that the main text focuses on coverage. The practical advantage in set size is shown in our online experiments in the Appendix, where AdaCOMA produces smaller sets than the COMA baseline by adapting to the current data point $X_t$, while maintaining target coverage.

6. Regarding Comparison with Baselines: YK-Base indeed performs reasonably well empirically. Nonetheless, it lacks a formal theoretical coverage guarantees. Moreover, on figure 1, Recal systematically provides better results (same coverge with much smaller intervals) and MinSE and AdaMinSE provide shorter or similar intervals with higher coverage on the two of the 3 examples. On the third one YB-base actually undercovers. In addition, in [11], the authors showed an experimental settings where YK-Base undercovers.

7. Regarding Dataset Choice: This is a fair point. The authors of [11] have open-sourced their code. To facilitate a direct comparison, we commit to add experiments on their synthetic data setting in the final version of our manuscript.

8. Regarding Editorial Point We will specify the target miscoverage $\alpha=0.1$ in all figure captions.

Response to Questions:

1. How to find $\hat{S}$ in practice? Corollary 1 is a general result. For implementation, Lemmas 1-3 provide concrete algorithms. Our experiments use the MinSE algorithm from Lemma 3, which is efficient and optimal (Proposition 2). As such, we used MinSE for all of our experiments.

2. What if the prior $b$ in MinSE is non-uniform? A non-uniform prior $b$ allows incorporating prior knowledge. For a trusted predictor (producing smaller sets) $j$, a higher $b_j$ allows our MinSE algorithm to select it with higher probability. On other hand, a higher $b_j$ does necessitate decreasing another coordinate $b_i$, as $b$ is constrained to the simplex. As such, MinSE will pick a predictor $i$ with less probability (or even never pick it up if $b_i=0$ and $\tau=0$). Thus, a non-uniform prior can be seen as blending prior expert belief with the data-driven results observed during inference time (i.e., after observing the conformal set sizes). Within this paper, we did not explore how to tune the prior $b$. This is partially due our belief that further tuning of our method may cause unfair comparisons with the benchmark that required no tuning.

Finally, we thank you for the paper formatting remarks. We will revise the manuscript to better frame and transition between parts that focus on coverage and parts that focus set size. We are grateful for your feedback and remain eager to answer any follow-up questions or provide further details.

Erratum and recap on experiments We wanted to openly disclose that we detected after submission a typo in the code, in file batch_setting/rescale_residual.py line 162, cal_sigma should be cal_sigma[m]. This changes the performance of ModSel, that is ultimately on-par with YK-base (yet never better, in fact YK-base lower bounds the confidence set size of ModSel). Other methods are unaffected. It thus does not change the quality of the "best competitor".

This also doesn't change the conclusion of our experiments, summarized below:

• on bike sharing, our methods MinSE and AdaMinSE improve coverage by 2% while having a average length 10% below YK-Base. Recal achieves nominal coverage with set length more than 30% smaller.
• on abalone, differences are more minor: both YK-base and ModelSel undercover by 1%, Recal is valid and reduces set size by 5% against all competitors, while MinSE and AdaMinSE suffer from conservatism, overcovering by 2% and increasing set size by 10% w.r.t. YK-base
• on California housing, YK-base, ModSel, MinSE, AdaMinSE achieve the same length, but with more than 2% of extra coverage for MinSE and AdaMinSE. Recal has nominal coverage with length 25% smaller than any other competitor.