Conformal Prediction Sets with Improved Conditional Coverage using Trust Scores

Thank you for your review, and in particular, for highlighting the ability of our method to advance the practical applicability of conformal prediction in high-stakes applications. We respond to specific questions and remarks below.

Regarding Proposition 1

Thank you for bringing this point to our notice. Our result holds conditionally on $\hat{q}$, and not marginally. We have updated the paper to clarify this. The paper cited by the reviewer studies the interactive effects between temperature, the calibration scheme, and the set size, whereas our result only studies the effect of temperature, holding everything else fixed and is meant to provide insight into why the patterns in Figure 1 emerge. Our goal is to show that if the true $Y$ is ranked further down in the sorted order of probabilities and the model is more confident, the probability of miscoverage is higher than if it was less confident. The temperature allows us to tune the amount of confidence that goes to the top score in a parametric way. To answer your question, temperature does not interact with our method in a unique way and has the same effect as shown in prior work. If we have similar assumptions as in prior works, we will achieve a similar non-monotonic relationship.

Regarding class-conditional coverage and inclusion of baselines

That is true, our method outputs sets that are slightly larger than standard conformal prediction on average, however this is not surprising given the consistent improvement in conditional coverage – there is no free lunch!

Regarding the reviewer’s comment on class-conditional coverage, we would like to emphasize that our primary goal is not to achieve class-conditional coverage as it is in the methods mentioned above; rather, we aim to improve coverage over instances where the classifier is overconfident in its incorrect predictions as identified by our lower-dimensional statistic. We evaluate over a suite of metrics to show our method generally improves conditional coverage as a consequence, including class-conditional coverage over standard conformal prediction. We include a special case of Mondrian CP as we mention in Section 4.3, 4.4 in the form of NAIVE baseline, where the procedure has access to group information it will be evaluated on.

That said, methods for class-conditional CP can potentially improve approximate $X$-conditional coverage if the class-wise computed quantiles align with quantiles of the conditional distribution, however this is not always expected or guaranteed. Following the reviewer’s suggestion, we perform an evaluation with Mondrian CP that splits the calibration data by class and runs conformal prediction once for each class. We add the results table below and include a new figure with approximate $X$-conditional coverage evaluation in the paper (Appendix C.5, Figure 8). We see that Mondrian CP improves $\textsf{Conf} \times \textsf{Rank}$ coverage gap in ImageNet-LT and Places365-LT at the cost of even larger set sizes. In the approximate $X$-conditional coverage evaluation, we see Mondrian CP performs worse than our Conditional method. Interestingly, Mondrian CP does not always achieve the lowest Class-conditional coverage gap despite computing class-wise quantiles during calibration.

Ablation on $k$ of k-NN radius in trust score computation

As we mentioned in Appendix B.3, we follow the original work (Jiang et al., 2018 [1]) to skip the initial filtering step in the trust score implementation for improving computational efficiency. The $k$-nearest neighbor calculations make up the bulk of the computational cost, and the original work found the procedure to not be very sensitive to the choice of $k$. Our datasets are larger than the ones used in [1], and hence this choice made intuitive sense. This also leads to a hyperparameter-free procedure as noted by Jiang et al.

In response to questions:

Are authors using the non-randomized version of RAPS in Appendix C.4, similar to how authors implemented APS?

Yes, we are consistent in using the non-randomized version in order to generate deterministic prediction sets and maintain fair comparison.

For the long-tailed datasets (ImageNet-LT and Places365-LT), do the test sets maintain the same imbalanced distribution? If so, this could lead to unreliable evaluation metrics for minority classes due to insufficient test samples. Have authors considered this potential bias in evaluation?

The reviewer raises a valid point. We use ImageNet-LT and Places365-LT as introduced by [2], where the training set is imbalanced while the validation and test sets are balanced. As mentioned in the appendix, we obtain data splits from previous benchmarks [3, 4].

Since the trust score is computed using features from the model's penultimate layer, could we explore using alternative encoders for trust score calculation? A better encoder might provide more discriminative features, potentially leading to more accurate trust scores and consequently smaller prediction sets.

That is an interesting direction to explore, and there can be variants that improve performance. We chose a representation that made intuitive sense and found it to work well in practice. Better encoders can lead to better approximation using trust scores and improve performance even further. We will highlight this in the paper.

[1] Jiang, H., Kim, B., & Gupta, M.R. (2018). To Trust Or Not To Trust A Classifier. Neural Information Processing Systems.

[2] Liu, Z., Miao, Z., Zhan, X., Wang, J., Gong, B., & Yu, S.X. (2019). Large-Scale Long-Tailed Recognition in an Open World. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2532-2541.

[3] Zhong, Z., Cui, J., Liu, S., & Jia, J. (2020). Improving Calibration for Long-Tailed Recognition. 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 16484-16493.

[4] Yuksekgonul, M., Zhang, L., Zou, J.Y., & Guestrin, C. (2023). Beyond Confidence: Reliable Models Should Also Consider Atypicality. ArXiv, abs/2305.18262.

Thank you again for taking the time to review our paper. As we approach the end of the discussion phase, we would like to confirm if our responses addressed your comments. In case there are any remaining questions or clarifications required, we are happy to discuss further.

Thank you,

Authors

We are glad we were able to address the rest of your concerns. We understand your point here, and we will surely make Proposition 1 clearer in the final version and contextualize it with respect to our specific setting, which as we explained in our rebuttal, differs from the setting in the paper you cited. Also, we are not sure what you refer to as "my experimental results", so we would perhaps not be able to comment on that.

That said, the above point is secondary to our main contribution which is largely appreciated by you as well as other reviewers. We hope you reconsider whether the significance of our contribution is appropriately weighted in your final assessment. We are happy to continue the discussion and incorporate any further suggestions you have.

Thank you for your continued engagement.

Unfortunately, we cannot compare the coverage probability for two samples as the model probabilities beyond the top output may be arbitrarily different. We did consider this initially, however it is not possible to marginally explain the coverage results in Figure 1 without further assumptions.

Please note that the goal of this proposition is not to study the effect of temperature but rather use the temperature as a way to parameterize confidence to study the relation between confidence and miscoverage in a stylized setting. The parameterization allows us to vary the amount of confidence that goes to the top score while keeping everything else fixed, and hence we study conditional miscoverage in Proposition 1. The result in this proposition is meant to be illustrative and is not central to our contribution or proposed methods. We will explain this more carefully in the camera-ready version and include the clarification suggested by the reviewer. If the reviewer feels it might cause some confusion to readers or muddle our main contributions, we can consider moving it.

We hope this resolves your concern, and we are happy to discuss further.

Thank you for your review, and for acknowledging the importance of the problem we address through our work. We are glad you found our approach to be theoretically sound and practically applicable, and our paper easy to follow.

In response to weaknesses:

W1: Regarding Conf×Trust and Conf×Rank coverage gaps

Our aim was to identify a lower dimensional statistic indicative of instances where conformal prediction is most likely to fail—specifically when the classifier is overconfident in its incorrect predictions. As can be seen in Figure 1, trust score approximately captures the patterns of miscoverage as the rank-based partitions. However, the exact values of coverage are not expected to be similar — rank can be thought of as an oracle metric that neatly partitions the space into bins ranging from coverage of 0 to 1. The trust scores are used as a proxy to identify test instances prone to error, enabling us to improve coverage along the Conf×Trust and indirectly Conf×Rank axes. We did not expect, and hopefully did not claim that the coverage gap values will be close. We are happy to clarify this in the final version if needed.

W1, W2: Comparison between Naive and Conditional

We would like to start by emphasizing that Naive might have been a misnomer since it is an ablation of our method rather than an existing or a naively implemented procedure. We understand that this terminology might be confusing, and will make sure to update this in the final version but will refer to it as such in the rebuttal. Naive runs conformal prediction within each ConfxTrust bin in Table 1 (and Figure 2) and within each skin type group in Table 2 – these are the same groups that are also used in evaluation. That is to say, Naive has strictly more information about the evaluation groups, which makes it a very competitive baseline. In what follows, we discuss the comparative results of Naive and Conditional in Section 4.3 and Section 4.4 individually:

1. Section 4.3: The success of both Naive and Conditional method over standard conformal prediction in Table 1 indicate that our proposed lower-dimensional statistic $V$ is effective in improving conditional coverage, since both methods use our proposed statistic $V$. While Naive has access to the discrete binning we use for evaluation, our proposed Conditional method still outperforms Naive in terms of the ConfxRank coverage gap, which demonstrates the utility of our proposed function class $\mathcal{F}$.

   Additionally, the Naive approach has conceptual limitations—the discretization involved in this baseline may limit its generalization to other forms of conditional coverage, as we can see from the approximate $X$-conditional coverage evaluation. Moreover, the success of the Naive approach depends on whether there are adequate numbers of samples in each bin to compute a non-trivial quantile. Our proposed approach faces no such constraint.

2. Section 4.4: Our evaluation on Fitzpatrick 17k also highlights the effectiveness of our method. Here, we consider an analogous Groupwise baseline to Naive. Despite Groupwise having access to skin type group labels during calibration, our method outperforms the approach in terms of all metrics. This comes with no significant increase in size. This demonstrates the utility of our method in real-world applications, especially when access to group labels is limited or collection may be expensive.

W3: Regarding inclusion of additional metrics

Thank you for your suggestion. We perform evaluation with the SSCV metric for all datasets and methods. We would like to note that the RAPS paper does not provide a clear protocol to select the set-size strata. For our evaluation, we use 6 partitions and choose the strata based on set-size quantiles of standard conformal prediction, ensuring that the evaluation is not biased/favorable toward our method. Despite that, we find Conditional and Naive methods to outperform standard conformal prediction in terms of this metric as well.

[Contd.] Regarding the comparison with other “Mondrian approaches”, we are only aware of Mondrian approaches that cluster the input space based on predetermined subgroups. Our approach is much more general as it can operate on any input space without the need to define a set of subgroups for group-wise conditioning. In the context of image classification, it is not clear what a sensible selection of subgroups would be. If you have suggestions regarding relevant baselines, we would be happy to include them in the updated version.

“it tends to be overly conservative in many cases while offering only minimal improvement in achieving the desired conditional coverage” – in the specific evaluation you mention (Table 1), we would like to highlight again that Naive has access to the discrete bins we use for evaluation, hence comparing the efficiency of Naive and Conditional is not fair. Despite that, the proposed Conditional method still outperforms Naive in terms of the ConfxRank coverage gap. When we go beyond the binning-based evaluation to measure approximate $X$-conditional coverage, we see the conditional approach outperforms Naive. The utility of our proposed function class $\mathcal{F}$ is also demonstrated through results on Fitzpatrick 17k, where we outperform Groupwise (Mondrian CP) without having access to skin type group labels and with no significant increase in size.

Regarding the reviewer’s comment on the computational complexity of the conditional approach, we agree that higher-dimensional function classes can increase computational cost and discuss this in the paper. However, this is where we believe our lower two-dimensional statistic may offer an advantage over other alternative functions of the representation space – intuitively, there is a limited range of interactions to model between the dimensions and increasing the degree beyond a threshold may result in diminishing returns (see Figure 5(b)). This is a significant consideration as the cost for computing prediction sets with the procedure in Gibbs et al. is O$(nd^2)$ for each test point, where $n$ is the number of calibration samples and $d$ is the dimension of the function class.

We hope this helps clarify our motivation and the experimental choices. We are happy to continue the discussion further in case there are any other questions.

Thank you for engaging with us and for your comments. We respond pointwise below:

In the paper, you begin reasoning about your proposed approach by highlighting that Conf×Rank is what matters and then proceed to suggest using the trust score as a proxy since Rank is not available... Otherwise, you could omit the Conf×Rank discussion entirely and directly present Conf×Trust as the chosen conditioning factor. So, I believe my critique here is fair.

The $\textsf{Rank}$ variable, by definition, inherently captures miscoverage patterns, as miscoverage events are characterized by a high $\textsf{Rank}$ for the true label and low confidence—a relationship we empirically validate in Figure 1. Our goal is to identify and improve coverage over instances where a classifier is overconfident in its incorrect predictions, as identified by a lower dimensional statistic $V$. The $\textsf{Trust}$ score is intended to approximate the same miscoverage trend as $\textsf{Rank}$, and not the exact value of $\textsf{Rank}$. In line with our goal above, the $\textsf{Trust}$ score can help identify instances where the classifier is incorrectly over-confident. So, bins based on ConfxTrust may not be identical to ConfxRank and that is not surprising.

The justification for the use of $\textsf{Trust}$ score for this approximation as follows: Theorem 4 in Jiang et al., 2018 demonstrates that, under certain regularity assumptions, the $\textsf{Trust}$ score can indicate whether the model $f(X)$ aligns with the Bayes-Optimal model $f^*(X)$ as:

$\textsf{Trust}(X) < \gamma \Rightarrow f(X) \neq f^*(X),$

$1/\textsf{Trust}(X) < \gamma \Rightarrow f(X) = f^*(X),$

for some threshold $\gamma$. This result suggests that the $\textsf{Trust}$ score stratifies prediction instances based on their alignment with the Bayes-Optimal classifier. In essence, it provides a coarser analog to the binning in Figure 1 into $\textsf{Rank}=1$ and $\textsf{Rank}>1$ categories. Since the $\textsf{Trust}$ score evaluates alignment with the Bayes-Optimal classifier through thresholding, it is intuitive that higher continuous values of the $\textsf{Trust}$ score correlate with increasing $\textsf{Rank}$ scores.

We evaluate the quality and usefulness of this approximation by evaluating the improvement in conditional coverage over standard conformal prediction (i.e., reduction in coverage gap (Table 1, Table 2, Figure 2, Figure 3)). Figure 3 specifically shows that we are able to improve coverage in instances where a classifier is overconfident in its incorrect predictions. ConfxRank coverage gap (CovGap) is one of the metrics we evaluate on and improve coverage on; however, this notion improves conditional coverage generally as evaluated by approximate $X$-conditional coverage (Figure 2), coverage over demographic subgroups (Table 2), and class-conditional coverage (Figure 3).

Regarding your point on omitting the ConfxRank notion, we would like to emphasize again that our choice of the statistic $V$ was motivated by our investigation of the miscoverage patterns in standard conformal prediction in the first place. The motivation behind our method based on trust score is that both $\textsf{Trust}$ and $\textsf{Rank}$ share the same patterns. We believe that keeping the discussion on the $\textsf{Rank}$ score will help readers better understand the rationale behind our method from first principles.

Regarding the naive approach, my point is that if your contribution were solely to define a Mondrian approach based on a new criterion—which you correctly label as naive—then your contribution would be highly incremental... I completely agree with the author regarding the limitations of the naive approach. However, the conditional approach is also not without its limitations, such as the added computational complexity.

Our main contribution is that we identify a lower-dimensional statistic $V$ to capture miscoverage trends in standard conformal prediction, and improve conditional coverage with respect to $V$. We do not feel it is fair to say identifying this new criterion is incremental – we believe this is a significant contribution considering the challenges involved in achieving conditional coverage with respect to high-dimensional features. This is also noted independently by reviewers dbo9 and BLuB. The “Naive” baseline in our results corresponds to a naive approach for conditioning on $V$, and is meant to serve as an ablation to assess the contribution of the functional modeling of the relation between $V$ and the threshold $\hat{q}$ on performance.

(Continued in the next comment)

Thank you again for taking the time to review our paper. We hope our responses through the discussion period addressed your comments and provided necessary clarifications. As the discussion phase has concluded, we would like to request you to reconsider whether the significance of our contribution is appropriately weighted in your final assessment.

Thank you,

Authors

Thank you for your review, and for acknowledging the effectiveness of our method in addressing a significant challenge in standard conformal prediction. We address specific questions and remarks below:

W1/Q1: Regarding applicability of the approach

We do discuss this in the limitations of our approach. In our analysis over four large-scale datasets, we found the trust score to correlate well with the rank of the true class (Figure 1, Table 3) to study miscoverage, however it would certainly be interesting to explore this relationship more formally. That said, a formal guarantee is not necessary for the applicability of our method as the relationship between trust and rank scores can be empirically tested in any dataset. To determine the applicability of our method, we recommend testing the hypothesis of whether trust scores are an indication of the rank on a subset of held out data and make a decision based on the correlation and p-values.

W2/Q4: Regarding scalability and computational complexity

Confidence measure is the top (max) softmax output of the classifier, which is readily available from a pretrained model. For calculating the nearest neighbor distance to each class for the trust scores computation, we use IndexFlatL2 from FAISS, Meta’s open-sourced GPU-accelerated library for efficient similarity search. This reduces the single nearest neighbor search time to ~ 0.06 ms/sample (averaged over 10 runs) on ImageNet on a single Nvidia GeForce GTX 1080. We thank the reviewer for this point and have updated the manuscript to add this in Appendix B.3.

Regarding the reviewer’s second point, we agree that higher-dimensional function classes can increase computational cost and discuss this in the paper as you mentioned. However, this is where we believe our lower two-dimensional statistic may offer an advantage over other alternative functions of the representation space – intuitively, there is a limited range of interactions to model between the dimensions and increasing the degree beyond a threshold may result in diminishing returns (see Figure 5(b)). To compute the prediction sets for conditional conformal procedure, we follow Gibbs et al., 2023. The computational complexity of this procedure is obtained as follows: for the linear program during calibration, $O((n+d)^{1.5}n)$ is a reasonable bound for the runtime, where $n$ is the number of calibration samples and $d$ is the dimension of the function class; to update the fit for each test point, an iterative algorithm is run with a small number of iterations in practice, and hence the cost for each test point can be estimated as $O(nd^2)$, which is the cost per iteration. We also check this with the authors.

W3: Regarding interpretability of coverage thresholds and sub-intervals

We would appreciate more clarification here. The thresholds are not selected manually but are computed by the conformal procedure. While the interpretability of prediction sets themselves is desirable for usability, it is not clear why we would require the thresholds to be interpretable. In an ideal scenario where we have a consistent estimate of the true conditional quantile function of $Y | X$, every sample may have a different threshold. We are happy to discuss this further based on the reviewer’s response.

W4/Q3: Regarding generalizability to non-image domains

It would be an interesting direction to explore the empirical performance on non-image domains. That said, there does not seem to be any conceptual reason why these scores will not work in other domains. The original work on trust scores [1] includes extensive evaluation on tabular datasets; additionally, there has been evidence in other works of nearest neighbor based scores working well for image as well as text domains [2, 3].

W5: Regarding applying multiple evaluation metrics

We do not believe this is a limitation of our work – in fact, we choose to include multiple metrics to provide a comprehensive evaluation of conditional coverage. Regarding the reviewer’s point, once the prediction sets are computed, it is not expensive to evaluate the performance on multiple metrics. The practitioner can choose to evaluate on one or multiple metrics based on the conditional coverage notion important for their specific application.

Thank you again for taking the time to review our paper. As we approach the end of the discussion phase, we would like to confirm if our responses addressed your comments. In case there are any remaining questions or clarifications required, we are happy to discuss further.

Thank you,

Authors

Thank you for your review, and in particular, for acknowledging the significance of the focus of our paper. We are glad you found the paper well-explained and positioned within the recent progress in the conformal prediction community. We address the specific remarks below:

Regarding the ability of trust scores to capture conditional miscoverage patterns

The $\textsf{Rank}$ variable, by definition, inherently captures miscoverage patterns, as miscoverage events are characterized by a high $\textsf{Rank}$ for the true label and low confidence—a relationship we empirically validate in Figure 1. For both theoretical and empirical reasons, we use the $\textsf{Trust}$ score as a proxy for the $\textsf{Rank}$ score:

From a theoretical perspective: Theorem 4 in Jiang et al., 2018 [1] demonstrates that, under certain regularity assumptions, the $\textsf{Trust}$ score can indicate whether the model $f(X)$ aligns with the Bayes-Optimal model $f^*(X)$ as follows:

$\textsf{Trust}(X) < \gamma \Rightarrow f(X) \neq f^*(X),$

$1/\textsf{Trust}(X) < \gamma \Rightarrow f(X) = f^*(X),$

for some threshold $\gamma$. This result suggests that the $\textsf{Trust}$ score stratifies prediction instances based on their alignment with the Bayes-Optimal classifier. In essence, it provides a coarser analog to the binning in Figure 1 into $\textsf{Rank}=1$ and $\textsf{Rank}>1$ categories. Since the $\textsf{Trust}$ score evaluates agreement with the Bayes-Optimal classifier through thresholding, it is intuitive that higher continuous values of the $\textsf{Trust}$ score correlate with increasing $\textsf{Rank}$ scores.

From an empirical perspective: While we have not formally established a theoretical one-to-one or monotonic relationship between $\textsf{Trust}$ and $\textsf{Rank}$, Figures 1, 3, 4, and 6 provide empirical evidence supporting this intuitive relationship.

We appreciate the reviewer’s insightful comment and will include a relevant discussion in Section 3 of the revised manuscript.

Regarding the expansion of our empirical evaluation

We would like to highlight that our main contribution is the selection of new input dimensions that can operate in any function class to approximate conditional coverage, and not a specific choice of a function class. This was motivated by our investigation of the miscoverage patterns in standard conformal prediction in the first place – in particular, to improve coverage in instances where a classifier is overconfident in its incorrect predictions (as can be seen from Figures 3, 4, Appendix C.1). With the confidence and $\textsf{Trust}$ scores as input dimensions, there are possible alternative function classes other than polynomial functions that may work well in practice.

It is also possible to investigate input dimensions other than confidence and $\textsf{Trust}$ as baseline. This includes the representation layers of classifiers as suggested by the reviewer. The additional advantage of our method over alternative functions of the representation space is that we propose a lower two-dimensional statistic to capture the miscoverage trends – intuitively, there is a limited range of interactions to model between the dimensions and increasing the degree beyond a threshold may result in diminishing returns (see Figure 5(b)). This is a significant consideration as the cost for computing prediction sets with the procedure in Gibbs et al. is $O(nd^2)$ for each test point, where $n$ is the number of calibration samples and $d$ is the dimension of the function class. We face computational limitations as we increase $d$ beyond 21 (i.e., degree > 5), given the scale of our datasets.

That said, we appreciate your suggestion and have included further evaluation in our work (Appendix C.4). We implement a competitive approach using the top principal components of the feature layer as our function class. We choose the number of principal components as 20, with an added intercept term to achieve marginal coverage. Performance as evaluated by all our metrics, including approximate $X$-conditional coverage shows that our method consistently outperforms this function class. We add the results table below and include the figure with approximate $X$-conditional coverage evaluation in the paper (Appendix C.4, Figure 7). We could not implement additional function classes due to the time and computational constraints during the rebuttal, but are happy to include in the final version based on further suggestions.

Regarding the inclusion of more related work

Thank you for pointing us to Kiyani et al., 2024. We have added this discussion to our related work, including other works that share similar motivation.

[1] Jiang, H., Kim, B., & Gupta, M.R. (2018). To Trust Or Not To Trust A Classifier. Neural Information Processing Systems.