Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning

Regarding the definition of $\hat{\tau}$ (Q1). The definition of $\hat{\tau}(\alpha)$ just corresponds to a quantile function, in this case the inverse of the CDF $F$ of the Binomial distribution $\text{Bin}(k_c, 1-\alpha)$. Intuitively, we select $\hat{\tau}$ such that the probability of a class $y$ being in at most $\hat{\tau}$ of $k_c$ prediction sets is at most $\alpha$, provided that $y$ is in each individual prediction set with probability at least $1-\alpha$ (which holds for $y_{n+1}$ since the smaller prediction sets are calibrated). Following your suggestion, we have added further intuition and clarifications about $\hat{\tau}$ along with a proof sketch for Theorem 2 to the manuscript.

Regarding coverage guarantee vs. reliability (Q2). You are correct that while the coverage guarantee is a marginal guarantee over the entire data distribution, our definition of coverage reliability is point-wise, meaning it applies to individual prediction sets $\mathcal{C}(x)$. Please note that, unlike the coverage guarantee, point-wise reliability can indeed be affected by training poisoning. In response to your comment, we have updated the manuscript to clarify this distinction. Specifically, we address it directly when introducing our notion of reliability (line 161) and further elaborate on it in the discussion (lines 521–529). Thank you for helping us improve the clarity of our work.

Regarding set-size reliability in calibration poisoning (Q3). As we previously clarified, our notion of reliability is point-wise, meaning it applies to individual prediction sets. We believe that demonstrating the point-wise size reliability of prediction sets is both sound and meaningful. Additionally, while expanding set sizes might serve as an empirical defense mechanism to flag invalid prediction sets, such defenses lack provable guarantees under worst-case adversarial attacks. In contrast, our approach ensures that prediction sets remain small while providing provable stability guarantees within a defined attack radius.

Regarding Figure 3 (Q4). Intuitively, we observe initial jumps in empirical coverage and set size in Figure 3 when using only $k_t=2$ or $3$ classifiers, because a sufficient number of classifiers is required to achieve consistent majority vote consensus and reliability in practice. Please note that our analysis demonstrates that four classifiers are already sufficient to prevent such jumps. In response to your comment, we have revised the manuscript to clarify this observation (lines 471-475).

We hope that we could address all your questions to your satisfaction. Please let us know if you have any additional comments or questions.

Thank you for your review!

Regarding our threat model. Thank you for acknowledging the novelty of our threat model for conformal prediction. Following your suggestion, we have clarified the threat model in the introduction (line 47) and point out limitations of the threat model presented in (Zargarbashi et al., 2024) more explicitly within the related work section (line 98).

Regarding the background. We have updated $\alpha_n$ in line 135 to the correct threshold when scores capture the agreement between data and label. Please note this minor correction in the background does not affect any of our theoretical or empirical results. Thank you for bringing this to our attention.

Regarding desiderata for reliable conformal prediction. Please note that the desiderata serve as foundation for how we envision reliable conformal prediction, focusing not only on the reliability of prediction sets but also on their practical relevance. This includes maintaining small set sizes (comparable to prediction sets without reliability guarantees), and ensuring computational efficiency in their construction, making them applicable in real-world settings. Regarding desideratum IV, it is not intended as a strict requirement for prediction sets, it rather ensures that algorithms have the flexibility to increase reliability when practical risk increases with more data. In response to your feedback, we have added clarifications to desiderata II, IV, and V, expressing more clearly that reliable conformal prediction requires efficient and flexible algorithms. Thank you for pointing out opportunities for further clarification.

Regarding conformal score ties. As you correctly pointed out, one has to take care of ties in practice for tighter coverage. To address this issue, we employ a deterministic softmax function to smooth the voting function $\pi_y(x)$. As demonstrated in our ablation study (Figure 4), this approach effectively keeps the prediction set size low, resulting in tighter empirical coverage. Please note that introducing additional random noise to the score function would compromise provable reliability guarantees under training poisoning. Interestingly, this also means that most existing score functions in the literature lack reliability by definition (see our discussion in Appendix D). In contrast, our first approach addresses this issue while ensuring stability of prediction sets at the same time. Thank you for bringing this up, this discussion highlights again the inherent challenges of providing provably reliable prediction sets.

Regarding a study of statistical efficiency. As you correctly pointed out, the empirical coverage is a random variable following a Beta distribution concentrated around the nominal coverage level. As we partition the calibration set, this concentration naturally decreases for the smaller prediction sets. In response to your comment, we have conducted additional experiments (Appendix C, Figure 13) to provide empirical evidence that the majority prediction sets are again closely concentrated around the nominal coverage level. We have also added the discussion to the main text (line 469-470).

Typos (L250, L349). We also fixed the typos, thank you for pointing this out.

References

Soroush H. Zargarbashi, Mohammad Sadegh Akhondzadeh, Aleksandar Bojchevski. Robust Yet Efficient Conformal Prediction Sets. ICML 2024.

Thank you for your review!

Regarding existing conformal prediction methods. Thank you for acknowledging our contribution toward improving the reliability of conformal prediction sets under data poisoning. Please note that all existing conformal prediction methods do not provide any provable guarantees for reliability under our poisoning threat model. Given the development of first poisoning attacks against conformal prediction (Li et al., 2024), this discussion highlights again the need for developing provably reliable prediction sets.

Regarding the relationship between reliability vs. number of partitions. Thank you for pointing out opportunities for further clarifications. Intuitively, a larger number of training partitions $k_t$ increases reliability against training poisoning, and a larger number of calibration partitions $k_c$ increases reliability against calibration poisoning. In response to your comment, we provide additional experiments and details in Appendix B (Figure 10) to demonstrate this relationship empirically.

Regarding large-scale experiments. Please note that we present results on CIFAR-100 in Figure 4 (1) and include additional results regarding this dataset in Appendix B. In response to your comment, we provide additional plots for this dataset in Appendix B for completeness (Figure 9 and 10). Beyond this, we believe that our experiments on standard benchmarks commonly used in reliability research are sufficient to demonstrate the effectiveness of our method. Nevertheless, we are prepared to provide additional resource-intense training experiments in the final version of the manuscript.

Regarding typos. We also fixed the typos (L176, L300, L350), thank you for bringing this to our attention.

We hope that we could address all your questions to your satisfaction. Please let us know if you have any additional comments or questions.

References

Yangyi Li, Aobo Chen, Wei Qian, Chenxu Zhao, Divya Lidder, Mengdi Huai. Data Poisoning Attacks against Conformal Prediction. ICML 2024.

Thank you for acknowledging the novelty of our approach for conformal prediction. We would like to emphasize that existing methods for robust classification are not applicable for certifying conformal prediction due to two key differences: (1) prediction sets inherently involve multiple classes, and (2) they can be manipulated through poisoning during both training and calibration. We believe our contributions are technically solid and non-trivial, as also highlighted by other reviewers. Overall, we believe our work represents a significant step forward at the intersection of both communities (conformal prediction and robustness), providing a solid foundation for future research.

Regarding your questions. Regarding Definition 1, your understanding is correct. We design prediction sets reliable against adversaries that aim to inflate or shrink the prediction sets $C(x_{n+1})$ by changing the labeled datasets. As you suggested, we have also added a reminder that $K$ represents the number of classes in Equation 2.

Thank you for your review! We hope that we could address all your questions to your satisfaction. Please let us know if you have any additional comments or questions.