Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning

## Abstract

Abstract Conformal prediction provides model-agnostic and distribution-free uncertainty quantification through prediction sets that are guaranteed to include the ground truth with any user-specified probability. Yet, conformal prediction is not reliable under poisoning attacks where adversaries manipulate both training and calibration data, which can significantly alter prediction sets in practice.
As a solution, we propose reliable prediction sets (RPS): the first efficient method for constructing conformal prediction sets with provable reliability guarantees under poisoning.
To ensure reliability under training poisoning, we introduce smoothed score functions that reliably aggregate predictions of classifiers trained on distinct partitions of the training data. To ensure reliability under calibration poisoning, we construct multiple prediction sets, each calibrated on distinct subsets of the calibration data. We then aggregate them into a majority prediction set, which includes a class only if it appears in a majority of the individual sets.
Both proposed aggregations mitigate the influence of datapoints in the training and calibration data on the final prediction set.
We experimentally validate our approach on image classification tasks, achieving strong reliability while maintaining utility and preserving coverage on clean data. Overall, our approach represents an important step towards more trustworthy uncertainty quantification in the presence of data poisoning.

## 1 Introduction

Conformal prediction has emerged as a powerful framework for model-agnostic and distribution-free uncertainty quantification in machine learning. By constructing prediction sets calibrated on hold-out calibration data, it can transform any existing black-box classifier into a predictor with formal coverage guarantees, ensuring that its prediction sets cover the ground truth with any user-specified probability (Angelopoulos & Bates, ). This makes conformal prediction highly relevant for uncertainty quantification in safety-critical applications such as medical diagnosis (Vazquez & Facelli, ), autonomous driving (Lindemann et al., ), and flood forecasting (Auer et al., ).

However in practice, noise, incomplete data or adversarial perturbations can lead to unreliable prediction sets (Liu et al., ).
In particular data poisoning – where adversaries modify the training or calibration data (e.g. during data labeling) – can significantly alter the prediction sets, resulting in overly conservative or empty sets (Li et al., ).
This vulnerability can undermine the practical utility of conformal prediction in safety-critical applications, raising the research question:

How can we make conformal prediction sets provably reliable in the presence of data poisoning?

As a solution, we propose reliable prediction sets (RPS): the first efficient method for constructing prediction sets more reliable under data poisoning.
Our approach consists of two key components ([Figure 1](#S1.F1)):
First (i), we introduce smoothed score functions that reliably aggregate predictions from classifiers trained on distinct partitions of the training data, improving reliability under training poisoning. Second (ii), we calibrate multiple prediction sets on disjoint subsets of the calibration data and construct a majority prediction set that includes classes only when a majority of the independent prediction sets agree, improving reliability under calibration poisoning.
Using both strategies (i) and (ii), RPS effectively reduces the influence of datapoints during training and calibration.

We further derive certificates, i.e. provable guarantees for the reliability of RPS under worst-case poisoning. We experimentally validate the effectiveness of our approach on image classification tasks, demonstrating strong reliability under worst-case poisoning while maintaining utility and empirically preserving the coverage guarantee of prediction sets on clean data.
Our main contributions are:

- •
We propose reliable prediction sets (RPS) – the first scalable and efficient method for making conformal prediction more reliable under training and calibration poisoning.
- •
We derive novel certificates that guarantee the reliability of RPS under worst-case data poisoning attacks, including guarantees against label flipping attacks.
- •
We exhaustively evaluate our method and verify our theorems on image classification tasks.

Figure: Figure 1: Conformal prediction (CP) is not reliable under poisoning (orange) of training and calibration data, undermining its practical utility in safety-critical applications. As a solution, we propose reliable prediction sets (RPS): A novel approach for constructing more reliable prediction sets. We (i) aggregate predictions of classifiers trained on distinct partitions, and (ii) merge multiple prediction sets ${\mathcal{C}}_{i}(x)$$=$$\{y:s(x,y)$$\,\geq\,$$\tau_{i}\}$ calibrated on separate partitions into a majority prediction set that includes classes only if a majority of the prediction sets ${\mathcal{C}}_{i}$ agree. This way RPS reduces the influence of datapoints while preserving the coverage guarantee of conformal prediction on clean data.
Refer to caption: /html/2410.09878/assets/figures/squirrel.jpg

## 2 Related Work

Prediction set ensembles. Ensembles of prediction sets are studied in the uncertainty set literature (Cherubin, ; Solari & Djordjilović, ; Gasparin & Ramdas, ) beyond machine learning, e.g. to reduce the effect of randomness. Our work instead proposes a method to improve the reliability of conformal prediction under worst-case training and calibration poisoning.

Conformal prediction under evasion. Most works regarding reliable conformal prediction focus on evasion threat models, i.e. adversarial perturbations of the test data. They typically build upon randomized smoothing (Cohen et al., ) to certify robustness against evasion attacks (Gendler et al., ; Yan et al., ; Zargarbashi et al., ), or use neural network-specific verification (Jeary et al., ). Ghosh et al. () introduce a probabilistic notion as an alternative to worst-case evasion attacks. Unlike prior work on evasion, we consider poisoning threat models.

Conformal prediction under poisoning.
Although there are already poisoning attacks against conformal prediction (Li et al., ), the few attempts to improve its reliability focus on other notions of reliability:
Most works only consider calibration poisoning where adversaries aim to reduce coverage by removing classes from prediction sets (Zargarbashi et al., ; Park et al., ; Kang et al., ). Others study calibration poisoning empirically (Einbinder et al., ), under specific label noise (Penso & Goldberger, ), or consider distribution shifts between calibration and test data (Cauchois et al., ). Overall, none of the existing approaches considers our threat model where adversaries can poison both training and calibration data with the goal to either add or remove classes from prediction sets.

Robustness certification against data poisoning. Most certification techniques for robust classification under poisoning consider other threat models, specific training techniques or architectures (Rosenfeld et al., ; Tian et al., ; Sosnin et al., ). The strongest guarantees also partition the training data and aggregate predictions of classifiers trained on each partition (Levine & Feizi, ; Wang et al., ; Rezaei et al., ). However, all of the prior works only guarantee robust classification and are not directly applicable to certify conformal prediction since prediction sets (1) contain multiple classes, and (2) can be manipulated via poisoning during training and calibration.

## 3 Background and preliminaries

We focus on classification tasks defined on an input space ${\mathcal{X}}={\mathbb{R}}^{d}$
for a given finite set of classes ${\mathcal{Y}}=\{1,\ldots,K\}$.
We model prediction set predictors as functions ${\mathcal{C}}:{\mathcal{X}}\to Y\subseteq{\mathcal{Y}}$, which provide prediction sets as subsets ${\mathcal{C}}(x)\subseteq{\mathcal{Y}}$ of the classes ${\mathcal{Y}}$ for any given datapoint $x\in{\mathcal{X}}$.

Exchangeability. Conformal prediction is a model-agnostic and distribution-free method for constructing prediction sets. It only requires that the datapoints are exchangegable, which means that their joint distribution is invariant under permutations of the datapoints. This is more general than an i.i.d.-assumption, since it allows for dependencies between datapoints as long as their distribution remains unchanged when the order is shuffled. In this paper, we adopt the standard assumption (e.g. in image classification) that datapoints are independent and identically distributed (i.i.d.), which implies exchangeability. Specifically, we assume three datasets sampled i.i.d. from the same distribution ${\mathcal{D}}$ over ${\mathcal{X}}\times{\mathcal{Y}}$: training set ${\mathcal{D}}_{train}$, calibration set ${\mathcal{D}}_{calib}$$=$$\{(x_{i},y_{i})\}_{i=1}^{n}$ and test set ${\mathcal{D}}_{test}$.

Conformal prediction. Conformal prediction is a method for turning a given black-box classifier $f:{\mathcal{X}}\to{\mathcal{Y}}$ into a prediction set predictor. We study split conformal prediction (Papadopoulos et al., ; Lei et al., ), the most widely-used variation of conformal prediction in machine learning.
First we train a classifier $f(x)$ on the training set and use a score function $s(x,y)$ that measures conformity between samples $x$ and classes $y$ using classifier $f$. For example, homogeneous prediction sets (HPS) use class probabilities $s(x,y)$$=$$f_{y}(x)$ (Sadinle et al., ). Using a score function $s$ we then compute conformal scores $S$$=$$\{s(x_{i},y_{i})\}_{i=1}^{n}$ for samples of the calibration set ${\mathcal{D}}_{calib}$.
Finally, one can construct prediction sets with the following coverage guarantee (Vovk et al., ; ):

###### Theorem 1 .

Given user-specified coverage probability $1-\alpha\in(0,1)$, test sample $(x_{n+1},y_{n+1})\in{\mathcal{D}}_{test}$ exchangeable with ${\mathcal{D}}_{calib}$, and a score function $s$, we can construct the following prediction set

$$ ${\mathcal{C}}(x_{n+1})=\{y\in{\mathcal{Y}}:s(x_{n+1},y)\geq\tau\}$ $$

which fulfills the following marginal coverage guarantee

$$ $\Pr[y_{n+1}\in{\mathcal{C}}(x_{n+1})]\geq 1-\alpha$ $$

for $\tau=\textrm{Quant}(\alpha_{n};S)$, which is the $\alpha_{n}$-quantile of the conformal scores $S$ for a finite-sample corrected coverage level $\alpha_{n}=\frac{\lceil(n+1)(1-\alpha)\rceil}{n}$.

For a more detailed introduction to conformal prediction we refer to Angelopoulos & Bates ().

###### Theorem 1 .

## 4 Desiderata for reliable conformal prediction

First we want to outline the desired properties reliable conformal prediction should exhibit, setting clear goals for how uncertainty should be captured by prediction sets under data poisoning.

Data poisoning. While exchangeability may hold theoretically for the data distribution ${\mathcal{D}}$, the labeled data ${\mathcal{D}}_{l}=({\mathcal{D}}_{train},{\mathcal{D}}_{calib})$ can be poisoned in practice where noise, incomplete data or adversaries are present (for example during data labeling), violating exchangeability. We formally model this threat model, i.e. the strength of poisoning attacks, as a ball centered around labeled data:

$$ $B_{r_{t},r_{c}}({\mathcal{D}}_{l})=\left\{\tilde{{\mathcal{D}}}_{l}\mid\delta(\tilde{{\mathcal{D}}}_{train},{\mathcal{D}}_{train})\leq r_{t},\delta(\tilde{{\mathcal{D}}}_{calib},{\mathcal{D}}_{calib})\leq r_{c}\right\}$ (1) $$

where $\delta$ is a distance metric between datasets, and $r_{t},r_{c}$ are the radii for training and calibration sets, respectively.
Specifically, we define $\delta$ as
the number of inserted or deleted datapoints and label flips, modelling feature modifications as two perturbations (deletion and insertion):
$\delta({\mathcal{D}}_{1},{\mathcal{D}}_{2})=|{\mathcal{D}}_{1}\ominus{\mathcal{D}}_{2}|-|{\mathcal{F}}({\mathcal{D}}_{1},{\mathcal{D}}_{2})|$
where $A\ominus B=(A\setminus B)\cup(B\setminus A)$ is the symmetric set difference between two sets $A$ and $B$, $|S|$ denotes the cardinality of a set $S$,
and ${\mathcal{F}}({\mathcal{D}}_{1},{\mathcal{D}}_{2})$ represents the set of datapoints with label flips
${\mathcal{F}}({\mathcal{D}}_{1},{\mathcal{D}}_{2})$$=$$\{x\mid\exists\,y_{1}:(x,y_{1})$$\in$$\,{\mathcal{D}}_{1}\setminus{\mathcal{D}}_{2},\exists\,y_{2}:(x,y_{2})$$\in$$\,{\mathcal{D}}_{2}\setminus{\mathcal{D}}_{1}\}$.
Note that we count label flips only once, and feature perturbations can be of arbitrary magnitude.

Reliability under data poisoning.
Given a datapoint $x\in{\mathcal{X}}$ and a prediction set ${\mathcal{C}}(x)\subseteq{\mathcal{Y}}$, we define reliability of conformal prediction sets under data poisoning as follows:

###### Definition 1 (Reliability) .

We assume that reliability is compromised if adversaries can remove or add a single class from or to the prediction set ${\mathcal{C}}(x)$ under our threat model ([Equation 1](#S4.E1)).
Specifically, we call prediction sets coverage reliable if adversaries cannot compromise coverage by removing classes from the prediction set ${\mathcal{C}}(x)$, and size reliable if adversaries cannot inflate prediction set ${\mathcal{C}}(x)$ by adding classes. We further denote coverage and size reliable prediction sets as robust.

Accordingly, we propose the following novel desiderata for reliable conformal prediction:

While Desideratum I requires that prediction sets fulfil the coverage guarantee, Desideratum II ensures small prediction sets, and together they prevent that reliability can be achieved trivially by predicting empty or full sets.
Desideratum III ensures that reliability must be certifiable, i.e. a provable guarantee under worst-case poisoning. Specifically, adversaries must not add or remove classes.
Desideratum VI requires that reliability improves if more data is available since practical risk increases with more data. Finally, Desideratum V ensures efficiency for practical deployment, where reproducibility requires that the sets do not differ for the same input, ensuring stability on clean data.

###### Definition 1 (Reliability) .

## 5 Reliable conformal prediction sets

Guided by our five desiderata for reliable conformal prediction we introduce reliable conformal prediction sets (RPS): the first method that makes conformal prediction provably more reliable under both training and calibration poisoning ([Figure 1](#S1.F1)). The first component of RPS (i) reliably aggregates classifiers trained on $k_{t}$ disjoint partitions of the training data. The second component of RPS (ii) constructs reliable prediction sets by merging prediction sets calibrated separately on $k_{c}$ disjoint partitions of the calibration data. Intuitively, while larger $k_{t}$ increases reliability against training poisoning, larger $k_{c}$ increases reliability against calibration poisoning.
We provide detailed instructions for our reliable conformal prediction sets in [Algorithm 1](#alg1) and [Algorithm 2](#alg2).

### 5.1 Conformal score functions reliable under training data poisoning

First, our goal is to derive a conformal score function that is reliable under poisoning of training data. This is challenging since the score function also has to quantify agreement between samples and classes, and maintain exchangeability of conformal scores between calibration and test data.
To overcome this challenge we propose to (1) partition the training data into $k_{t}$ disjoint sets, (2) train separate classifiers on each partition, and (3) design a score function that counts the number of classifiers voting for a class $y$ given sample $x$.
Since deleting or inserting one datapoint from or into the training set only affects a single partition and thus a single classifier, this procedure effectively reduces the influence of datapoints on the score function.

Training data partitioning.
To prevent that simple reordering of the datasets affects all partitions simultaneously, we have to partition the training data in a way that is invariant to its order. To achieve this we assign datapoints to partitions by using a hash function directly defined on $x$. For example for images, we hash the sum of their pixel values. This technique that has been previously shown to induce certifiable robustness in the context of image classification (Levine & Feizi, ). Given a hash function $h$ we define the $i$-th partition of the training set as

$$ $P_{i}^{t}=\left\{(x_{j},y_{j})\in{\mathcal{D}}_{train}:h(x_{j})\equiv i\,(\textrm{mod }k_{t})\right\}.$ $$

Then we deterministically train $k_{t}$ classifiers $f_{i}:{\mathcal{X}}\rightarrow{\mathcal{Y}}$ on all partitions $P_{1}^{t},\ldots,P_{k_{t}}^{t}$ separately.

Smoothed score function.
Now we define our novel score function that measures agreement between a sample $x$ and class $y$ by counting the number of classifiers $f_{i}$ voting for class $y$ given $x$:

$$ $s(x,y)=\frac{e^{\pi_{y}(x)}}{\sum_{i=1}^{K}e^{\pi_{i}(x)}}\quad\text{with}\quad\pi_{y}(x)=\frac{1}{k_{t}}\sum_{i=1}^{k_{t}}\mathds{1}\{f_{i}(x)=y\}$ (2) $$

where $\pi_{y}(x)$ is the percentage of classifiers voting for class $y$ given sample $x$. Note that we introduce the additional softmax over class distribution $\pi_{y}(x)$ to fulfill Desideratum II, since the softmax prevents overly large prediction sets in practice (see [Section 7](#S7)).

For any function to be considered a valid score function for conformal prediction it has to maintain exchangeability of conformal scores between calibration and test data (Angelopoulos et al., ).

###### Lemma 1 .

The smoothed score function in [Equation 2](#S5.E2) is a valid conformal score function.

Proof.
We use one function to score all points independent of other datapoints and which dataset they belong to (and where in the dataset). Thus, given exchangeable data, scores computed by our smoothed score function remain exchangeable. Therefore $s$ of [Equation 2](#S5.E2) is a valid score function. $\square$

[1](#Thmlemma1) implies that the marginal coverage guarantee ([Theorem 1](#Thmtheorem1)) holds on clean data when using our smoothed score function for conformal prediction (Desideratum I). Intuitively, our score function quantifies uncertainty by the number of votes of multiple classifiers trained on disjoint partitions instead of the logits of classifiers. As long as the classifiers are trained on isolated sets without access to other partitions we can reduce the influence of datapoints on the conformal scores. We summarize instructions for the smoothed score function in [Algorithm 1](#alg1).

Figure: Algorithm 1 Reliable conformal score functionp

###### Lemma 1 .

### 5.2 Majority prediction sets reliable under calibration data poisoning

Now we derive prediction sets reliable against calibration poisoning. This is challenging since the prediction sets must also achieve marginal coverage on clean data (Desideratum I) without inflating set size (Desideratum II). We propose to (1) partition the calibration data into $k_{c}$ disjoint sets, (2) compute separate prediction sets based on the conformal scores on each partition, and to (3) merge the resulting prediction sets via majority voting.
This improves reliability since adversaries have to poison multiple partitions to alter the majority vote. We further show that such majority prediction sets achieve marginal coverage, and do not grow too much in size in practice ([Section 7](#S7)).

Calibration data partitioning. We partition the calibration data as follows: Given a hash function $h$ we define the $i$-th partition of the calibration set as $P_{i}^{c}=\{(x_{j},y_{j})\in{\mathcal{D}}_{calib}:h(x_{j})\equiv i\,(\textrm{mod }k_{c})\}$.
We then use a (potentially reliable) conformal score function $s$ to compute the conformal scores $S_{i}$$=$$\{s(x_{j},y_{j})\}_{(x_{j},y_{j})\in P_{i}^{c}}$ on each partition $P_{i}^{c}$. We can then determine the $\alpha_{n_{i}}$-quantiles of the separate conformal scores, $\tau_{i}=\textrm{Quant}(\alpha_{n_{i}};S_{i})$,
where $n_{i}$ is the size of the $i$-th partition, $n_{i}=|C_{i}|$.

Majority prediction sets. Now we propose our novel prediction sets reliable under calibration poisoning. Given a new datapoint $x_{n+1}\in{\mathcal{D}}_{test}$ we construct $k_{c}$ prediction sets for each partition as ${\mathcal{C}}_{i}(x_{n+1})=\{y:s(x_{n+1},y)\geq\tau_{i}\}$. We then construct a prediction set composed of all classes that appear in the majority of independent prediction sets:

$$ ${\mathcal{C}}^{M}(x_{n+1})=\left\{y:\sum_{i=1}^{k_{c}}\mathds{1}\!\left\{y\in{\mathcal{C}}_{i}(x_{n+1})\right\}>\hat{\tau}\right\}$ (3) $$

with $\hat{\tau}$$=$$\max\left\{x\in[k_{c}]:F(x)\leq\alpha\right\}$, where $F$ is the CDF of the Binomial distribution $\text{Bin}(k_{c},1-\alpha)$ and $[k_{c}]=\{0,\ldots,k_{c}\}$. Note that for $k_{c}=1$ we have $\hat{\tau}=0$ and thus the majority prediction sets amount to standard conformal prediction sets, ${\mathcal{C}}^{M}(x_{n+1})={\mathcal{C}}_{1}(x_{n+1})$. We summarize the construction of our majority prediction sets in [Algorithm 2](#alg2).

Interestingly, such majority voting is also used in the context of uncertainty sets (Gasparin & Ramdas, ), but their construction comes without reliability guarantees and additionally violates the coverage guarantee (see discussion in [Appendix D](#A4)). In contrast, we show that our majority prediction sets ${\mathcal{C}}^{M}$ achieve marginal coverage on clean data:

###### Theorem 2 .

Given coverage probability $1$$-$$\alpha$$\,\in\,$$(0,1)$, test sample $(x_{n+1},y_{n+1})$$\,\in\,$${\mathcal{D}}_{test}$, and a conformal score function $s$, the majority prediction set ([Equation 3](#S5.E3)) constructed on a calibration set of independent datapoints achieves marginal coverage on clean data:

$$ $\Pr[y_{n+1}\in{\mathcal{C}}^{M}(x_{n+1})]\geq 1-\alpha$ (4) $$

Proof in [Appendix D](#A4).
Notably, [2](#Thminnercustomthm1) guarantees marginal coverage for any conformal score function. This holds especially for our smoothed score function ([Algorithm 1](#alg1)). As a result, majority prediction sets based on the smoothed score function achieve marginal coverage (Desideratum II).

###### Theorem 2 .

## 6 Provable guarantees for reliable conformal prediction sets

After introducing reliable prediction sets (RPS), we derive certificates for their reliability as defined in [1](#Thmdefinition1) and required by Desideratum III. We consider the threat model $B_{r_{t},r_{c}}({\mathcal{D}}_{l})$ where adversaries can insert, delete and flip labels for up to $r_{t}$ training and $r_{c}$ calibration points ([Section 3](#S3)).
In the following we treat training poisoning, then calibration poisoning, and finally poisoning of both.

### 6.1 Guarantees for smoothed scoring function under training poisoning

We begin with the reliability of the smoothed scoring function under training poisoning ($r_{t}$$>$0 0, $r_{c}$$=$0 0). Let ${\mathcal{C}}(x_{n+1})$$=$$\{y$$\,\in\,$${\mathcal{Y}}:s(x_{n+1},y)$$\,\geq\,$$\tau\}$ be a prediction set for a new test point $x_{n+1}$ derived using conformal prediction ([Section 3](#S3)) under the clean dataset ${\mathcal{D}}_{l}$ with smoothed score function $s$.
Our goal is to bound the prediction set $\tilde{{\mathcal{C}}}(x_{n+1})$ derived under any poisoned dataset $\tilde{{\mathcal{D}}}_{l}\in B_{r_{t},r_{c}}({\mathcal{D}}_{l})$. This requires that we bound score function $s$ and quantile $\tau$. We start with the score function:

###### Lemma 2 .

We can upper bound the score function for any $\tilde{{\mathcal{D}}}_{l}\in B_{r_{t},r_{c}}({\mathcal{D}}_{l})$ as follows:

$$ $\overline{s}(x,y)=\max_{\begin{subarray}{c}0\leq\pi_{i}\leq 1\\ \Delta_{i}\in\{0,\pm\frac{1}{k_{t}},\ldots,\pm\frac{r_{t}}{k_{t}}\}\\ \sum_{i=1}^{K}\Delta_{i}=0\end{subarray}}\frac{e^{\pi_{y}}}{\sum_{i=1}^{K}e^{\pi_{i}}}\quad\textrm{with}\quad\pi=[\pi_{1}(x)+\Delta_{1},\ldots,\pi_{K}(x)+\Delta_{K}]$ (5) $$

Proof in LABEL:app:certificateproofs. Although optimizing softmax functions typically leads to non-convex optimization problems, the problem in (5) reduces to a discrete optimization problem that can be solved efficiently (Desideratum V). We derive algorithms computing lower and upper bounds in $r_{t}$ steps, presenting the upper bound in [Algorithm 3](#alg3). Intuitively, in each step we greedily redistribute $\frac{1}{k_{t}}$ probability mass from
the current class $\hat{y}$$\neq$$y$ with the largest probability mass to the target class $y$. We repeat this process until we have redistributed the entire probability mass $\frac{r_{t}}{k_{t}}$.
We present the lower bound algorithm and proofs in LABEL:app:certificateproofs.

Figure: Algorithm 3 Greedy algorithm for upper bounding the smoothed score function $s$

Given lower and upper bounds $\underline{z_{i}}=\underline{s}(x_{i},y_{i})$ and $\overline{z_{i}}=\overline{s}(x_{i},y_{i})$ on the conformal scores for all points $(x_{i},y_{i})\in{\mathcal{D}}_{calib}$ in the calibration set, we can directly determine the worst-case quantiles:

$$ $\underline{\tau}=\textrm{Quant}(\alpha_{n};\{\underline{z_{i}}\}_{i=1}^{n})\quad\quad\overline{\tau}=\textrm{Quant}(\alpha_{n};\{\overline{z_{i}}\}_{i=1}^{n})$ $$

Finally we need to identify (1) the class within the prediction set that received the fewest votes from the classifiers $f_{i}$ and (2) the class outside the prediction set that got most votes from the classifiers:

$$ $\underline{y}=\operatorname*{\arg\!\min}_{y\in{\mathcal{C}}({x_{n+1}})}\pi_{y}(x)\quad\quad\overline{y}=\operatorname*{\arg\!\max}_{y\notin{\mathcal{C}}({x_{n+1}})}\pi_{y}(x)$ $$

Then we can provide the following guarantees (Proof in LABEL:app:certificateproofs):

###### Theorem 3 .

Given $r_{c}$$=$0 0, the conformal prediction set $\tilde{{\mathcal{C}}}(x_{n+1})$ derived with the smoothed score function under any poisoned dataset $\tilde{{\mathcal{D}}}_{l}$$\in$$B_{r_{t},r_{c}}({\mathcal{D}}_{l})$ is coverage reliable, i.e. $\tilde{{\mathcal{C}}}(x_{n+1})\supseteq{\mathcal{C}}(x_{n+1})$, if $\,\underline{s}\left(x,\underline{y}\right)\geq\overline{\tau}$, and size reliable, i.e. $\tilde{{\mathcal{C}}}(x_{n+1})\subseteq{\mathcal{C}}(x_{n+1})$, if $\,\overline{s}\left(x,\overline{y}\right)<\underline{\tau}$.

Intuitively, if class $\underline{y}$ cannot be removed from ${\mathcal{C}}(x_{n+1})$ ($\overline{y}$ added), adversaries cannot remove (add) other classes and thus the prediction sets are coverage (size) reliable.

###### Lemma 2 .

###### Theorem 3 .

### 6.2 Guarantees for majority prediction sets under calibration poisoning

Now we analyze reliability of majority prediction sets under calibration poisoning ($r_{t}=0$,$r_{c}>0$). Let ${\mathcal{C}}^{M}(x_{n+1})$ be the majority prediction set for a new test point $x_{n+1}$ derived under the clean dataset ${\mathcal{D}}_{l}$ using any deterministic conformal score function $s$.
Intuitively, if adversaries cannot remove (add) a class from the majority prediction set by removing (adding) it from (to) $r_{c}$ individual prediction sets, the majority prediction set remains coverage (size) reliable even in the worst case.
This is since adversaries can perturb at most $r_{c}$ calibration partitions.
To determine if adversaries can remove or add classes, we have to count minimum and maximum support $\sum_{i=1}^{k_{c}}\mathds{1}\{y\in{\mathcal{C}}_{i}(x_{n+1})\}$ for classes in and outside of the majority set:

$$ $\underline{m}=\min_{y\in{\mathcal{C}}^{M}}\sum_{i=1}^{k_{c}}\mathds{1}\{y\in{\mathcal{C}}_{i}(x_{n+1})\}\quad\quad\overline{m}=\max_{y\notin{\mathcal{C}}^{M}}\sum_{i=1}^{k_{c}}\mathds{1}\{y\in{\mathcal{C}}_{i}(x_{n+1})\}$ $$

Using each support we can provide the following guarantees (Proof in LABEL:app:certificateproofs):

###### Theorem 4 .

Given $r_{t}$$=$0 0 and deterministic score function $s$, the majority prediction set $\tilde{{\mathcal{C}}}^{M}(x_{n+1})$ derived under any dataset $\tilde{{\mathcal{D}}}_{l}\in B_{r_{t},r_{c}}({\mathcal{D}}_{l})$ is coverage reliable, i.e. $\tilde{{\mathcal{C}}}^{M}(x_{n+1})\supseteq{\mathcal{C}}^{M}(x_{n+1})$, if $\underline{m}-r_{c}>\hat{\tau}$, and size reliable, i.e. $\tilde{{\mathcal{C}}}^{M}(x_{n+1})\subseteq{\mathcal{C}}^{M}(x_{n+1})$, if $\;\overline{m}+r_{c}\leq\hat{\tau}$,
provided that the smallest calibration partition $i^{*}$ is large enough $|P_{i^{*}}^{c}|-r_{c}\geq(\frac{1}{\alpha}-1)$.

Note that the last condition ensures that the calibration partitions are large enough such that worst-case adversaries cannot delete datapoints to prevent us from computing the majority prediction sets.

###### Theorem 4 .

### 6.3 Provable reliability guarantees for RPS under general data poisoning

Finally, we consider poisoning of training and calibration data ($r_{t}>0,r_{c}>0$).

Coverage reliability.
To ensure coverage reliability we have to show that all classes $y$$\,\in\,$${\mathcal{C}}^{M}$ are guaranteed to be in the majority prediction set under worst-case poisoning.
The majority prediction set ${\mathcal{C}}^{M}$ contains a class $y$ only if it appears in a majority of $\hat{\tau}$ individual prediction sets ${\mathcal{C}}_{i}$.
Under calibration poisoning, adversaries can remove classes from $r_{c}$ individual prediction sets. Intuitively, the number of prediction sets reliable under training poisoning $\beta_{y}$ must be large enough such that even under calibration poisoning, the number of prediction sets containing the class is still larger than the threshold, $\beta_{y}-r_{c}>\hat{\tau}$. This leads to the following guarantee (Proof in LABEL:app:certificateproofs):

###### Theorem 5 .

Let $\beta_{y}$ denote the number of prediction sets ${\mathcal{C}}_{i}\in\{{\mathcal{C}}_{1},\ldots,{\mathcal{C}}_{k_{c}}\}$ for which we can guarantee $y\in{\mathcal{C}}_{i}$ under $r_{t}$ poisoned training datapoints. If $\beta_{y}-r_{c}>\hat{\tau}$ for all $y\in{\mathcal{C}}^{M}(x_{n+1})$ then the majority prediction set is coverage reliable under any dataset $\tilde{{\mathcal{D}}}_{l}\in B_{r_{t},r_{c}}({\mathcal{D}}_{l})$, provided that the smallest calibration partition $i^{*}$ is large enough $|P_{i^{*}}^{c}|-r_{c}\geq(\frac{1}{\alpha}-1)$.

Size reliability.
To ensure size reliability we have to show that all classes $y\notin{\mathcal{C}}^{M}$ are guaranteed to stay outside of the majority prediction set under worst-case poisoning. The majority prediction set ${\mathcal{C}}^{M}$ does not contain a class $y$ if it appears in less than or equal to $\hat{\tau}$ individual prediction sets ${\mathcal{C}}_{i}$.
Under calibration poisoning, adversaries can add classes to $r_{c}$ prediction sets in the worst-case.
Intuitively, if we can guarantee that $\gamma_{y}$ prediction sets ${\mathcal{C}}_{i}$ do not contain the class $y$ under training poisoning, at most $k_{c}-\gamma_{y}$ prediction sets contain the class under worst-case training poisoning.
This number of prediction sets containing the class in the worst-case must be small enough such that even if adversaries add the class to $r_{c}$ prediction sets, the majority prediction set does not contain the class, $k_{c}-\gamma_{y}+r_{c}\leq\hat{\tau}$. This leads to the following guarantee (Proof in LABEL:app:certificateproofs):

###### Theorem 6 .

Let $\gamma_{y}$ denote the number of prediction sets ${\mathcal{C}}_{i}\in\{{\mathcal{C}}_{1},\ldots,{\mathcal{C}}_{k_{c}}\}$ for which we can guarantee $y\not\in{\mathcal{C}}_{i}$ under $r_{t}$ poisoned training datapoints.
If $k_{c}-\gamma_{y}+r_{c}\leq\tau$ for all $y\notin{\mathcal{C}}^{M}(x_{n+1})$ then the majority prediction set is size reliable under any dataset $\tilde{{\mathcal{D}}}_{l}\in B_{r_{t},r_{c}}({\mathcal{D}}_{l})$, provided that the smallest calibration partition $i^{*}$ is large enough $|P_{i^{*}}^{c}|-r_{c}\geq(\frac{1}{\alpha}-1)$.

Note that we can efficiently compute numbers $\beta_{y}$ and $\gamma_{y}$ as described in [Subsection 6.1](#S6.SS1) by computing the worst-case quantiles and verifying $\underline{s}(x,y)<\overline{\tau}$ and $\overline{s}(x,y)<\underline{\tau}$, respectively. Our overall certification approach is efficient in practice (Desideratum V) as we discuss in LABEL:app:certificateproofs and experimentally demonstrate in the next section.

###### Theorem 5 .

###### Theorem 6 .

## 7 Experimental Evaluation

In this section we evaluate our reliabe prediction sets and their worst-case guarantees, demonstrating their effectiveness in analyzing and improving reliability of conformal prediction under poisoning.
We compare three settings (calibration poisoning, training poisoning, and poisoning of both) by computing the following prediction sets: (a) majority prediction sets merging multiple homogeneous prediction sets calibrated on each partition,
(b) conformal prediction sets using our smoothed score function, and (c) majority prediction sets using our smoothed score function.

Datasets and models.
We train ResNet18, ResNet50 and ResNet101 models (He et al., ) on SVHN (Netzer et al., ), CIFAR10 and CIFAR100 (Krizhevsky et al., ). The datasets contain images with 3 channels of size 32x32, categorized into 10, 10 and 100 classes. We show results for ResNet18 on CIFAR10 and coverage level $\alpha$$=$$0.1$ here and additional results in [Appendix B](#A2).

Experimental setup.
We randomly select 1,000 images of the test set for calibration and use the remaining 9,000 datapoints for testing. To account for randomness in training and calibration set sampling we train 5 classifiers with different initializations and validate each of them on 5 different calibration splits. We report mean and standard deviation (shaded areas in the plots). We refer to [Appendix A](#A1) for the full experimental setup including detailed reproducibility instructions.

Evaluation metrics.
We report three reliability ratios: The ratios of test datapoints whose prediction sets are, according to our worst-case analysis, coverage reliable (classes cannot be removed), size reliable (classes cannot be added), or robust (classes cannot removed or added). Empirical coverage refers to the ratio of datapoints whose prediction sets cover the ground truth label of the test set. We also report the average size of the prediction sets computed on the test set.

Figure: Figure 2: Worst-case reliability guarantees across three scenarios: (a) poisoning of the calibration data, (b) poisoning of the training data, and (c) poisoning of both datasets. Our guarantees against coverage attacks are stronger when training data is poisoned, whereas for calibration attacks our method offers stronger guarantees against size attacks. Notably, even under strong adversarial conditions where both datasets can be poisoned we still provide non-trivial reliability guarantees.

(a) Reliability of majority prediction sets under calibration poisoning.
Majority prediction sets demonstrate strong reliability guarantees against calibration set poisoning in empirical evaluations ([Figure 2](#S7.F2) a).
Specifically, we construct majority prediction sets by merging $k_{c}$$=$$22$ homogeneous prediction sets, each calibrated on separate calibration partitions, resulting in an empirical coverage of 90.6% and an average set size of $0.95$.
When up to $r_{c}$$=$$4$ datapoints in the calibration set are poisoned, our method guarantees that over 97% of the prediction sets remain reliable against worst-case coverage attacks. The guarantees against set size attacks are even stronger: Even if $r_{c}$$=$$17$ datapoints are poisoned we still guarantee that over 79% of the prediction sets remain size reliable.

(b) Reliability of smoothed score function under training poisoning.
The setting of training set poisoning is considerably more challenging since adversaries can simultaneously manipulate the quantiles during calibration and the scores at inference. We compute conformal prediction sets using our smoothed score function on $k_{t}$$=$$100$ training partitions, resulting in empirical coverage of 90.6% and average set size of $3.3$ ([Figure 2](#S7.F2) b). Despite strong adversaries, our reliable prediction sets still manage to provide non-trivial reliability guarantees under worst-case perturbations.
Specifically, when up to $r_{t}=5$ datapoints in the training set are poisoned, our method guarantees that over 25% of the prediction sets remain reliable against worst-case coverage attacks.

(c) Reliability of RPS under training and calibration poisoning.
By far the most challenging setting constitute adversaries that manipulate both training and calibration data.
We compute majority prediction sets using our smoothed score function on $k_{t}$$=$$100$ training partitions and $k_{c}$$=$$40$ calibration partitions, resulting in empirical coverage of 92.3% and average set size of $3.6$ ([Figure 2](#S7.F2) c). Notably, under poisoning of up to $r_{t}=3$ training and $r_{c}=3$ calibration points, our method still guarantees that over 23% of the prediction sets remain reliable against worst-case coverage attacks.

Figure: Figure 3: Average set size and empirical coverage in all three different experiment settings (a–c). Notably, our reliable prediction sets yield valid coverage guarantees without becoming too large.

Average prediction set size. In [Figure 3](#S7.F3) (top row) we study the average set size for varying numbers of partitions. Notably, our majority prediction sets yield strong guarantees ([Figure 2](#S7.F2) a) without any significant increase in size ([Figure 3](#S7.F3) a): the average prediction set size remains below 1, which even holds for $k_{c}$$=$$40$ ($\alpha$$=$$0.1$). Interestingly, the size slowly increases with more training partitions, creating a tade-off between reliability and utility of the prediction sets. Practitioners have to fine-tune this trade-off depending on the application’s sensitivity towards reliability.
Overall, we empirically find that our reliable prediction sets do not become too large in size (Desideratum II).

Note that the set size increases when using only $k_{t}$$=$$2,3$ training partitions (spikes in the plots). This happens because a sufficient number of classifiers is needed to achieve consistent consensus in practice. However, our analysis also shows that five classifiers are already sufficient to prevent excessively large prediction sets. Finally, we also study the sizes on different datasets under calibration poisoning (setting (a)): On CIFAR100 the average set size remains around 4 for $k_{c}\leq 25$, demonstrating that our majority prediction sets scale well to datasets with more classes ([Figure 4](#S7.F4) (1)).

Coverage guarantees.
In [Figure 3](#S7.F3) (bottom row) we empirically validate the coverage guarantee ([2](#Thminnercustomthm1)) on clean data. We observe that empirical coverage matches the desired coverage probability $1-\alpha$ closely on average (Desideratum I), confirming our theoretical statements. We observe overcoverage for small numbers of training partitions, which can be explained by our previous finding that a minimum number of classifier is needed to achieve consistent consensus in practice.

Figure: Figure 4: (1): Average prediction set size of majority prediction sets across three different datasets. (2,3): Softmax ablation study for empirically justifying smoothing of the voting function ($\alpha=0.05$).

Softmax ablation study. We found that smoothing the voting function with a softmax ([Section 5](#S5)) avoids overly large prediction sets and overcoverage in practice. To demonstrate this we conduct an experiment ([Figure 4](#S7.F4) (2,3)) for varying numbers of training partitions $k_{t}$, where we compare conformal prediction with our smoothed score function $s$ against using the voting function $\pi$ only.

Computational efficiency. Training the classifiers takes most of the time (statistics in [Appendix A](#A1)). Note, however, that while having to train more classifiers, each one is trained on a subset of the training data, which can speed up the training process. Inference with the ResNet18 models takes between 4 and 10 seconds on CIFAR10. Constructing the conformal prediction sets takes at most 0.5 seconds for the entire test set. Computing certificates for majority prediction sets takes less than a second, and around one minute when computing guarantees under training and calibration poisoning. Overall, we found that reliable prediction sets are computationally efficient (Desideratum V).

## 8 Discussion

Reproducible prediction sets.
Score functions in the literature are not just unreliable but some also depend on randomization to break ties (Romano et al., ). While randomization at inference changes prediction sets by at most one class (Angelopoulos et al., ), different prediction sets for the same input may not be desirable from a reliability standpoint, violating Desideratum V. For example, a differential diagnosis for two patients with identical health should not yield different results.
As a remedy, we propose to make randomized score functions reproducible ([Appendix C](#A3)).

Limitations.
Although RPS computationally scales to larger settings, training on subsets of larger datasets such as CIFAR100 or ImageNet comes with accuracy loss, which also affects the utility of our smoothed score function (details in [Appendix B](#A2)). This accuracy loss is an open challenge in the general certifiably robust classification literature and beyond the scope of this paper.

Minimal calibration set size for majority prediction sets.
Recall that Desideratum VI requires that the reliability of prediction sets must increase for larger calibration sets. Our majority prediction sets fulfill this desideratum by construction since increasing the number partitions $k_{c}$ will decrease the influence of datapoints. However, we need enough data to construct our prediction sets: due to the finite-sample correction, the calibration partitions cannot become arbitrarily small ([Section 6](#S6)). If the hashing function would distribute all calibration images into equally-sized partitions of size $n/{k_{c}}$, we would need at least $n\geq k_{c}\left(\frac{1}{\alpha}-1\right)$ calibration points in total (Proof in [Appendix D](#A4)).
Notably, this relationship is linear: given a fixed coverage probability $1-\alpha$, increasing the calibration partitions by a factor of $k$ only requires $k$-times larger calibration sets, which is realistic for all commonly used image classification datasets and coverage probabilities used in the literature.

Training poisoning discussion. Note that as long as adversaries only know that the calibration set is any dataset exchangeable with the test data, they cannot compromise the coverage guarantee ([Theorem 1](#Thmtheorem1)) by poisoning training sets. This holds because conformal scores are computed using a fixed classifier (post-training). However in practice, worst-case adversaries may know the calibration set during training poisoning. Furthermore, even without access to the calibration data, adversaries can still attack the prediction set size: For example, adversaries can manipulate the training process to degrade the performance of the score function, leading to excessively large prediction sets. This underscores again the need to ensure coverage and size reliability as defined in [1](#Thmdefinition1).

## 9 Conclusion

We introduce reliable prediction sets (RPS), a novel method designed to improve reliability of conformal prediction in the presence of data poisoning and label flipping attacks. By leveraging smoothed score functions and a majority voting mechanism, RPS effectively mitigates the influence of adversarial perturbations during both training and calibration.
We provide theoretical guarantees that RPS maintains stability under worst-case data poisoning, and demonstrate the effectiveness of our approach on image classification tasks.
Overall, our approach represents an important contribution towards more reliable uncertainty quantification in practice, fostering the trustworthiness in real-world scenarios where data integrity cannot be guaranteed.

#### Acknowledgments

The authors want to thank Jan Schuchardt, Lukas Gosch and Leo Schwinn for valuable feedback on the manuscript. This work has been funded by the DAAD program
Konrad Zuse Schools of Excellence in Artificial Intelligence (sponsored by the Federal Ministry of
Education and Research). The authors
of this work take full responsibility for its content.

## Appendix Overview

In this appendix we provide additional results, details on our experimental setup and prove theoretical results as outlined in the following:

[sections]
\printcontents[sections]l1\contentsmargin0.1

## Appendix A Full experimental setup and reproducibility details

We provide details on the experimental setup to ensure reproducibility of our results.

Datasets. The datasets we use for evaluation are described in [Section 7](#S7) (SVHN (Netzer et al., ), CIFAR10 and CIFAR100 (Krizhevsky et al., )) and are publicly available. We use the torchvision library to load the datasets.(^1^11[https://pytorch.org/vision/stable/index.html](https://pytorch.org/vision/stable/index.html))
We normalize images before training, and we compute dataset mean and standard deviation on each training partition separately to ensure models are trained on isolated partitions, which is required by our method to improve reliability.

Training details.
We train all models with stochastic gradient descent (learning rate 0.01,
momentum 0.9, weight decay 5e-4) for 400 epochs using early stopping if the training accuracy does not improve for 100 epochs. We further deploy a cosine learning rate scheduler (Loshchilov & Hutter, ). We use a batch-size of 128 during training and 300 at inference.
To ensure that our guarantees against training-poisoning hold we require that the training process is deterministic, which not only involves fixing the random seed for data augmentation but also ensuring that the training processes are deterministic.

Image preprocessing.
We determine dataset-wide mean and standard deviation
dynamically on every training set partition separately
once before training to ensure that each classifier is trained on an isolated partition.
We subsequently normalize all images in one partition with the corresponding values.
We also augment the training set with random crops (padding of 4 pixels) and random horizontal flips (but we perform the data augmentation in a deterministic, reproducible way across runs).

Hardware details.
We train ResNet18 models on a NVIDIA GTX 1080TI GPU, and the ResNet50 and ResNet101 models on a NVIDIA A100 40GB. We perform inference of all models on a NVIDIA GTX 1080TI GPU, and compute certificates on a Xeon E5-2630 v4 CPU.

Reproducibility. To ensure reproducibility we use random seeds for all randomized functions, this especially includes the dataset preprocessing, model training and calibration splits. We will publish source code along with reproducibility instructions and all random seeds.

Training time details.
The runtime statistics for training ResNet18 models on CIFAR-10 and SVHN are as follows. Training a single ResNet18 model on CIFAR-10 takes 2.2 hours, while training 100 models requires a total of 21.7 hours, with each individual model taking approximately 2.6 minutes. For SVHN, a single ResNet18 model takes 5.6 hours to train, and training 100 models requires a total of 30 hours, with each model training taking around 3.5 minutes.

## Appendix B Additional results for reliable prediction sets

In this section, we expand on the experimental results by providing further analyses and complementary information.
[Figure 5](#A2.F5) shows the worst-case reliability guarantees for the SVHN dataset under the three different poisoning scenarios (in the same settings as described in the main paper). We again observe that our method provides reliable prediction sets even under worst-case poisoning attacks. Complementary to the main section, [Figure 6](#A2.F6) shows the average set size and empirical coverage in all three different experiment settings (a–c) on the SVHN dataset.

[Figure 7](#A2.F7) (1) shows the average set sizes of the three different architectures (ResNet18, ResNet50, ResNet101) on the CIFAR10 dataset when using majority vote prediction sets with the smoothed score function (third experimental setting). Interestingly, using the ResNet18 model yields the best results, which we attribute to the fact that models trained on subsets of the training set require less capacity to learn the data distribution, and small models prevent overfitting.
[Figure 7](#A2.F7) (2,3) show the softmax ablation study for empirically justifying the smoothing of the voting function for $\alpha=0.1$.

We also provide additional results for our reliable prediction sets for the following evaluation metrics: (1) the ratio of empty sets, (2) the ratio of full sets, (3) the singleton ratio (ratio of sets containing a single class), and (4) the singleton hit ratio (empirical coverage of singleton prediction sets). [Figure 9](#A2.F9) shows results for the CIFAR10 dataset, and [Figure 10](#A2.F10) shows results for the SVHN dataset, for all three evaluation settings (a-c) described in [Section 5](#S5).

Figure: Figure 5: SVHN: Worst-case reliability guarantees across three scenarios: (a) poisoning of the calibration data, (b) poisoning of the training data, and (c) poisoning of both datasets.

Figure: Figure 6: Avg. size and empirical coverage in all three settings (a–c) on the SVHN dataset.

Figure: Figure 7: (1): Different models on CIFAR10. (2,3): Softmax ablation study for empirically justifying smoothing of the voting function (here with $\alpha=0.1$) on CIFAR10.

Figure: Figure 8: CIFAR10, $k_{t}=100$, $k_{c}=40$, $\alpha=0.1$, (1): Coverage reliability ratio, (2): Size reliability ratio, (3): Robust ratio. Here with all radii combinations (and not just the diagonal, $r_{t}=r_{c}$).
Refer to caption: /html/2410.09878/assets/figures/fig68-img0.png

In the main plots in [Section 7](#S7), we only considered the diagonal $r_{t}=r_{c}$ for the reliability ratios. In [Figure 8](#A2.F8), we show the reliability ratios for coverage reliability, size reliability, and robustness for all combinations of $r_{t}$ and $r_{c}$ for the CIFAR10 dataset ($k_{t}=100$, $k_{c}=40$, $\alpha=0.1$). Interestingly, the reliability ratios are generally higher for larger $r_{c}$, which indicates that the majority prediction sets are more reliable when calibration data is poisoned.

As mentioned in [Section 8](#S8), training on subsets of larger datasets such as CIFAR100 or ImageNet comes with accuracy loss, which affects the utility of our smoothed score function. Specifically, when splitting the training set of CIFAR100 into 10 partitions only, each individual classifier achieves an accuracy of approximately 30% (in contrast to at least 70% when trained on the entire dataset). This affects the performance of our smoothed score function, leading to overly excessive prediction sets. Future learning algorithms could further improve the performance when training on subsets of larger datasets, ultimately boosting robustness and reliability in machine learning.

Figure: Figure 9: Various metrics for RPS in the three experiment settings (a-c) for ResNet18 on CIFAR10.

Figure: Figure 10: Various metrics for RPS in the three experiment settings (a-c) for ResNet18 on SVHN.

## Appendix C Reproducible prediction sets

There are conformal score functions that rely on random variables, e.g. for ensuring exact coverage by breaking ties. For example, adaptive prediction sets (APS) sum over class probabilities of classes with probability at least $f_{y}(x)$: $s(x,u,y)$$=$$-(\sum_{i=1}^{K}f_{i}(x)\mathds{1}[f_{i}(x)$$>$$f_{y}(x)]$$+$$uf_{y}(x))$. Conformal prediction sets are then formed by
${\mathcal{C}}(x_{n+1})=\{s(x_{n+1},u_{n+1},y)\geq\tau\}$,
where $u_{n+1}\in[0,1]$ is a uniform random variable (Romano et al., ).

Although randomization at inference changes prediction sets by at most one class (Angelopoulos et al., ), generating different prediction sets for the same input may not be desirable from a reliability standpoint and violates Desideratum V. For example, a differential diagnosis for two patients with identical health parameters should not yield different results.
As a solution we propose reproducible score functions: Instead of drawing from a random variable, we propose to compute pseudorandom numbers by hashing the sum of the image’s pixel values and initialize the pseudorandom number with the hash. We found that this is enough to break ties in practice while ensuring determinism required by our reliability guarantees. Note that our score functions with pseudo-randomization are valid since they maintain exchangeability as the numbers depend solely on the data itself (not its position in the dataset or other datapoints).

We analyze this in [Figure 11](#A3.F11): Without randomization APS results in large set sizes (2) despite tight coverage (1). With randomization the sets shrink in size, but are not reproducible. With pseudo-randomization, APS is reproducible with tight coverage and small prediction sets.

Figure: Figure 11: Comparing APS without and with randomization against our reproducible version.

## Appendix D Proofs for reliable prediction sets ( Section 5 )

Recall the definition of the majority prediction sets from [Section 5](#S5):

$$ ${\mathcal{C}}^{M}(x_{n+1})=\left\{y:\sum_{i=1}^{k_{c}}\mathds{1}\!\left\{y\in{\mathcal{C}}_{i}(x_{n+1})\right\}>\hat{\tau}\right\}$ $$

with $\hat{\tau}$$=$$\max\left\{x\in[k_{c}]:F(x)\leq\alpha\right\}$, where $F$ is the CDF of the Binomial distribution $\text{Bin}(k_{c},1-\alpha)$ and $[k_{c}]=\{0,\ldots,k_{c}\}$.
Note that by assumption the sets $C_{i}(x_{n+1})$ are independent.
We show the following result:

###### Theorem 2 .

Given coverage probability $1$$-$$\alpha$$\,\in\,$$(0,1)$, test sample $(x_{n+1},y_{n+1})$$\,\in\,$${\mathcal{D}}_{test}$, and a conformal score function $s$, the majority prediction set ([Equation 3](#S5.E3)) constructed on a calibration set of independent datapoints achieves marginal coverage on clean data:

$$ $\Pr[y_{n+1}\in{\mathcal{C}}^{M}(x_{n+1})]\geq 1-\alpha$ (6) $$

###### Proof.

Define the event $\phi_{i}=\mathds{1}\{y_{n+1}\in{\mathcal{C}}_{i}(x_{n+1})\}$.
Note that $y_{n+1}$ is fixed and the events $\phi_{i}$ and $\phi_{j}$ are independent for $i\neq j$ since
the prediction sets ${\mathcal{C}}_{i}$ and ${\mathcal{C}}_{j}$ are constructed on disjoint partitions in a calibration set of independent datapoints.
Therefore $\phi_{i}$ are independent Bernoulli random variables with $p_{i}=\Pr[\phi_{i}=1]\geq 1-\alpha$ by construction.
Further define the random variable

$$ $S_{k_{c}}=\sum_{i=1}^{k_{c}}\mathds{1}\!\left\{y\in{\mathcal{C}}_{i}(x_{n+1})\right\}.$ $$

First we consider the special case $p_{i}=1-\alpha$ for all $i$.
Then $S_{k_{c}}=\sum_{i=1}^{k_{c}}\phi_{i}$ is a Binomial random variable, $S_{k_{c}}\sim\text{Bin}(k_{c},1-\alpha)$. Thus we have:

$$ $\displaystyle\Pr[y_{n+1}\in{\mathcal{C}}^{M}(x_{n+1})]$ $\displaystyle=\Pr\left[\sum_{i=1}^{k_{c}}\mathds{1}\!\left\{y_{n+1}\in{\mathcal{C}}_{i}(x_{n+1})\right\}>\hat{\tau}\right]$ (7) $\displaystyle=\Pr\left[S_{k_{c}}>\hat{\tau}\right]$ (8) $\displaystyle=1-\Pr\left[S_{k_{c}}\leq\hat{\tau}\right]$ (9) $\displaystyle=1-\underbrace{F(\hat{\tau})}_{\leq\alpha}$ (10) $\displaystyle\geq 1-\alpha$ (11) $$

In the general case of $p_{i}\geq 1-\alpha$ we have that $S_{k_{c}}$ is distributed as a Poisson binomial random variable, $S_{k_{c}}\sim PB(k_{c},[p_{1},\ldots,p_{k_{c}}])$. However, it holds that $\prod_{i=1}^{k_{c}}p_{i}>(1-\alpha)^{k_{c}}$, which implies that the Poisson binomial distribution is stochastically larger than the Binomial distribution (Boland et al., ; Tang & Tang, ). See details in (Gasparin & Ramdas, ).
Intuitively, this means that the probability $\Pr\left[S_{k_{c}}>\hat{\tau}\right]$ can only increase in the general case where $p_{i}\geq 1-\alpha$.
∎

Discussion.
Notably, Gasparin & Ramdas () merge uncertainty sets with a similar majority vote but they define the threshold in their majority prediction set as
$q=\sup\{x\in{\mathbb{R}}:F(x)\leq\alpha\}$ instead of $\hat{\tau}=\max\{x\in[k_{c}]:F(x)\leq\alpha\}$.
However, clearly we have $F(q)>\alpha$ due to the definition of the supremum and the definition of the binomial CDF:

$$ $F(x;k_{c},1-\alpha)=\sum_{i=0}^{\lfloor x\rfloor}\binom{k_{c}}{i}(1-\alpha)^{i}\alpha^{k_{c}-i}$ $$

This means $q=\hat{\tau}+1$, which leads to smaller majority prediction sets which violate the coverage guarantee since $\Pr[S_{k_{c}}>q]<1-\alpha$ due to $F(q)>\alpha$.

Minimal calibration set size for majority prediction sets.
Recall that desideratum VI ([Section 4](#S4)) requires that the reliability of prediction sets must increase for larger calibration sets. Our majority prediction sets fulfill this desideratum by construction since increasing the number partitions $k_{c}$ will decrease the influence of datapoints. However, we need enough data to construct prediction sets: due to the finite-sample correction, the calibration partitions cannot become arbitrarily small. This naturally bounds the number of partitions $k_{c}$ for a fixed calibration size $n$ (and thus reliability):

###### Theorem 2 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: In equation 2, it might be good to remind the reader that K is the number of classes. 

 I was confused by Definition 1, I think here you mean that the adversary flips y_i for some examples x_i, and then as a result, the prediction set C(x_{n+1}) might inflate or shrink. Is this correct?
soundness: 3
strengths: I think overall, the idea of partitioning the training data and training different classifiers and aggregating their predictions is pretty natural and has been in around for both differential privacy and robustness against poisoning attacks. But anyways, they are the first to study it in the context of conformal prediction.
summary: They introduce a method called "reliable prediction sets" that constructs conformal prediction reliable sets under poisoning attacks. They consider both training and calibration data poisoning. In order to achieve robustness against training poisoning, they partition training data into different parts and train a classifier on each part, and then aggregate the predictions from these classifiers to derive a smooth conformal score function.

Furthermore, in order to be reliable against calibration poisoning, they calibrate multiple prediction sets on disjoint subsets of the calibration data and construct a majority prediction set that includes classes that are included in the majority of the independent prediction sets.

Their guarantees show that:
Under training poisoning, they show the conformal prediction set derived with smoothed score function is both size reliable and coverage reliable.
Furthermore, for calibration poisoning, they show under some conditions their majority prediction set method is coverage and size reliable.

Finally, they show the effectiveness of their approach experimentally, showing their method achieves reliability while maintaining utility on clean data.
weaknesses: I think overall, the idea of partitioning the training data and training different classifiers and aggregating their predictions is pretty natural and has been in around for both differential privacy and robustness against poisoning attacks. But anyways, they are the first to study it in the context of conformal prediction.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Is there any reason why full experiments for CIFAR-100 and ImageNet were not included? I appreciate the paper mentions the limitation in terms of accuracy loss, and I understand if full training can be expensive but I still believe there is value in showing limited results here, especially under calibration poisoning. It will be good to understand performance and the various desiderata in these relatively harder datasets with larger number of classes.
soundness: 3
strengths: 1. The paper is well-written, organized, and easy to follow for the most part. 
2. The paper is technically sound. I appreciate the paper clearly lays out the desiderata for reliable conformal prediction sets under data poisoning in the beginning. The claims regarding RPS are well supported by theory and empirical evaluation. 
3. The paper presents important results that can contribute toward improving the reliability of conformal prediction sets under data poisoning attacks in real scenarios.
summary: This paper proposes reliable prediction sets (RPS) as an efficient method for constructing conformal prediction sets under training and calibration data poisoning. The proposed approach has two components: to improve reliability under training data poisoning, authors introduce smoothed score functions that reliably aggregate predictions from classifiers trained on distinct partitions of the training data; and to improve reliability under calibration data poisoning, authors calibrate multiple prediction sets, each calibrated on distinct subsets of the calibration data, and construct a majority prediction set. Authors propose a desiderata for reliable conformal prediction, and derive certificates for the reliability of prediction sets under worst-case data poisoning attacks. The paper presents empirical evaluation of the method on image classification tasks.
weaknesses: 1. It would help to show comparison with baselines in the empirical evaluation. I see there is some comparison with APS to understand the effect of randomization; however, it would be interesting to see worst-case reliability analysis comparison with existing conformal prediction methods, and discussing how RPS fares in the different desiderata.
2. Relationship of reliability with number of partitions: the paper briefly discusses how the number of partitions (and dataset size) will affect the reliability of prediction sets; however, I did not seem to find experiments that analyze this relationship. It would help to demonstrate this relationship in order to better understand the utility of prediction sets in different scenarios.
3. Section 6 can be made more readable and the notation becomes slightly hard to follow at times. 



**Minor comments:**
1. L176: typo, Desideratum VI -> Desideratum IV
2. L300: equation reference should probably be (5) 
3. L350: typo, coverave -> coverage

---

confidence: 4
contribution: 4
initial_rating: 6
presentation: 3
questions: 1. The definition of $\hat{\tau}$ is unclear to me. Can you elaborate? What is this capturing? Why the iteration variable is called $x$? Does it have any correlation with covariates?
2. I can not understand why poisoning in training data can influence the coverage reliability. Since the coverage is only dependent to calibration set the guarantee should not break with a poisoned model (CP is guaranteed with black-box model). Then why Fig. 2-b shows a decay on coverage reliable. In general there are no comprehensive discussions on what coverage reliability and coverage guarantee have in difference. So from the conformal guarantee changes in the training data should have no influence in the “marginal” coverage of the prediction sets. However I think this reliability is defined per point. Is that so? In case yes please update the manuscript to draw this difference line in a more clear way. 
3. I think the set-size reliability is misleading to show (at least as a solid line) for calibration poisoning. Under calibration poisoning the guarantee is already invalid and with an invalid guarantee by definition it is not important if the set sizes are small or not. Even in some cases expanding set sizes can be considered as an alert to the defender that the calibration set is invalid.
4. In Fig 3. I can not understand the jumps in the beginning of the x axis for empirical coverage? What is the reason behind that intuitively? I see a quick explanation in lines 473-475 but isn’t it due to the missing randomization in the score function?

If the points in questions and weaknesses are provided I would be happy to increase my score.
soundness: 4
strengths: The other works designed to make CP robust to poisoning are not considering insertion and deletion in their threat model. This makes this work unique. Also their approach however repeated from the poisoning literature, still is novel to be adapted to conformal prediction framework. 

The score function designed by the authors is interesting and novel. It also can have interesting properties beyond the score of robustness. The interesting outcome of this is that it enables them to provide the guarantees on the set size which is novel.

The paper is theoretically solid. I think the theorems are well defined, and the results are quite far from obvious. Therefore I see this as a strong work.

The writing is also in a good shape; the story of the paper is easy to follow. However a strong recommendation is to add a discussion on differences between normal conformal coverage guarantee and coverage reliability.
summary: This work studies robustness of conformal prediction to poisoning in a threat model that allows insertion and deletion which is a limitation of the other studies e.g. zargarbashi et al, 2024. For training the authors propose to divide the training data into $k_t$ disjoint sets so that by definition any poisoning will at worst break one model. This robustness approach was previously studied in image classification as well. The conformity score function is the softmax over the votes of each classifier on each class. While the conformal guarantee is safe w.r.t. poisoning in the training process, calibration data can be poisoned as well. The authors remedy that by a similar approach of dividing the calibration set, and producing prediction sets from each calibration group, and running a majority vote-based decision on the final output. 

Overall I don’t count section 5.1 as a novel approach tailored to conformal prediction. However it is an smart approach to reduce the poisoning effect on set size. However showing that Section 5.2 is a valid approach is an important contribution.
weaknesses: **Writing.**  I expect the threat model to be mentioned more clearly in the introduction. Until the related work I did not understood that the authors are addressing a poisoning model different from zargarbashi et al 2024. I strongly suggest the authors to mention that in their threat model addition and deletion of data points is allowed which is a limitation of zargarbashi et al 2024 either in the introduction or in the corresponding section in related works.

**Wrong background.** The definition of the conformal prediction in Theorem 1 is not correct. Either you define the scores as capturing agreement between the data and the label (e.g. directly using softmax) then the for test points you add labels with scores above the threshold and the threshold is the $\alpha_n = \lfloor\alpha(n+1)-1\rfloor$ or the quantile is as authors specified in line 135, where the score should be non-conformity $1 - f_y(x)$ and the labels with score lower that the threshold should be picked. 

**Unnecessary, and unclear desiderata.** Although I agree on desiderata no. 1, 2, and 3, I still think that computational efficiency is not a necessity. Also if no. 4 means that there is an strict increasing requirement, then it contradicts the assumption of adding datapoints can be invariant to the final result. Other than that what is the concrete definition of providing small prediction sets? Is it in comparison to the same model trained on clean data? or is it in comparison to vanilla setup?

**Discrete score.**  Although the score is float, it is discrete with fixed number of possibilities. However working in practice there are corner cases where ties can become problematic. You need to add a random noise to the score in Eq. 2 which I think does not change that much in the efficiency of the output but simply avoids these small chances of failure. 

**Study of statistical efficiency.** The empirical coverage is not always $1 - \alpha$. This is on it’s own a random variable sampled from a Beta distribution concentrated around the nominal guarantee. This concentration is increased by the number of calibration points. The first question that is not addressed here is that how breaking the calibration set to smaller calibration sets influence this concentration? For sure it should decrease due to smaller calibration sets, while some of this can be remedied by the majority prediction set. Do you have any intuition on how this is affected? At least I expect a discussion on the lowerbound of this in the limitations of the work.

**Typos.** Sentence at the end of line 250 is grammatically wrong. Typos are seen in lines 349 (title). 

**Suggestions.** The intuition behind the proof of Theorem 2. is non-trivial. I would recommend the authors to add a short sketch of proof or an intuition on what is deciding the parameter of majority vote set in the manuscript.

Meta-review: This work studies the robustness of conformal inference in cases of poisoning attacks in both training and calibration datasets, and devises a new method (dubbed Reliable Prediction Sets) that recovers analogous guarantees to conformal prediction in such cases. For corruption of training samples, the approach relies on methods that are well-known in the poisoning attacks community, such as splitting the data into disjoint subsets resulting in a "smooth" score function, which enjoys theoretical guarantees. For corruptions in calibration, the method is calibrated on different subsets of that data and aggregated via a majority vote. Their methodology is demonstrated on numerical experiments for image classification. 

**Strengths**
* Novel problem formulation
* Important problem
* Novel approach
* Sound theoretical results

**Weaknesses**
None severe; all weaknesses noted by the reviewers were addressed by the authors in the rebuttal period.

**Summary** This is a good paper. The clarification on the impact of the method's parameters, related methods, as well as fixing some typos and small mistakes, have all improved the quality of the paper. I'm recommending Accept.

Decision: Accept (Spotlight)