On Temperature Scaling and Conformal Prediction of Deep Classifiers

## Abstract

Abstract In many classification applications, the prediction of a deep neural network (DNN) based classifier needs to be accompanied by some confidence indication. Two popular approaches for that aim are: 1) Calibration : modifies the classifier’s softmax values such that the maximal value better estimates the correctness probability; and 2) Conformal Prediction (CP): produces a prediction set of candidate labels that contains the true label with a user-specified probability, guaranteeing marginal coverage, rather than, e.g., per class coverage. In practice, both types of indications are desirable, yet, so far the interplay between them has not been investigated. We start this paper with an extensive empirical study of the effect of the popular Temperature Scaling (TS) calibration on prominent CP methods and reveal that while it improves the class-conditional coverage of adaptive CP methods, surprisingly, it negatively affects their prediction set sizes. Subsequently, we explore the effect of TS beyond its calibration application and offer simple guidelines for practitioners to trade prediction set size and conditional coverage of adaptive CP methods while effectively combining them with calibration. Finally, we present a theoretical analysis of the effect of TS on the prediction set sizes, revealing several mathematical properties of the procedure, according to which we provide reasoning for this unintuitive phenomenon.

## 1 Introduction

Modern classification systems are typically based on deep neural networks (DNNs) [, , ].
In many applications, it is necessary to quantify and convey the level of uncertainty associated with each prediction of the DNN. This is particularly crucial in high-stakes scenarios, such as medical diagnoses [],
autonomous vehicle decision-making [],
and detection of security threats []
, where human lives are at risk.

In practice, DNN classification models typically generate a post-softmax vector, akin to a probability vector with nonnegative entries that add up to one.
One might, intuitively, be interested in using the value associated with the prediction as the confidence [].
However, this value often deviates substantially from the actual correctness probability.
This discrepancy, known as miscalibration, is prevalent in modern DNN classifiers, which frequently demonstrate overconfidence:

the maximal softmax value surpasses the true correctness probability [].
To address this issue, post-processing calibration methods are employed to adjust the values of the softmax vector.
In particular, Guo et al. []
demonstrated the usefulness of a simple Temperature Scaling (TS) procedure (a single parameter variant of Platt scaling []),
which since then has gained massive popularity [, , , , , ].

Another post-processing approach for uncertainty indication is Conformal Prediction (CP), which was originated in [, ]
and has attracted much attention recently.
CP algorithms are based on devising scores for all the classes per sample (based on the softmax values) that are used for producing a set of predictions instead of a single predicted class.
These methods have theoretical guarantees for marginal coverage:

given a user-specified probability,
the produced set will contain
the true label with this probability, assuming that the data samples are exchangeable (e.g., the samples are i.i.d.).
Note that this property does not ensure conditional coverage, i.e., coverage of the true label with the specified probability when conditioning the data, e.g., to a specific class.
Consequently, CP methods are
usually compared by both their prediction set sizes and their conditional coverage performance.

Clearly, in critical applications, both
calibration and CP
are desirable, as they provide complementary
types of information that can lead to a comprehensive decision.
However, as far as we know, so far the interplay between them has not been investigated.
Most of the works on CP do not use any calibration. The few works [, , , ] that do, apply CP techniques on the outputs of an initial TS calibration. Yet, none of them investigates what is the effect of this procedure on the methods.
In this work, we study the effect of TS, arguably the most common calibration technique, on three prominent CP methods: Least Ambiguous set-valued classifier (LAC) [, ], Adaptive Prediction Sets (APS) [], and Regularized Adaptive Prediction Sets (RAPS) [].
Interestingly, our discoveries have motivated us to explore how the TS mechanism can be utilized in adaptive CP, beyond its calibration application.

Our contributions can be summarized as follows:

- •
We conduct an extensive empirical study on DNN classifiers that shows that an initial TS calibration affects CP methods differently. Specifically, we show that its effect is negligible for LAC, but intriguing for adaptive methods (APS and RAPS):
while their class-conditional coverage is improved, surprisingly, their prediction set sizes typically become larger.
Moreover, this behavior is more distinguishable in settings where the classifiers have limited accuracy.
- •
Motivated by these findings, we explore the effect of TS on CP outside of its calibration application.
We reveal that TS
enables to conveniently trade
the prediction set sizes and the conditional coverage performance for RAPS and APS.
Consequently, we offer practitioners simple guidelines for combining adaptive CP methods with calibration while adjusting them to better fit their specific requirements.
- •
We present a theoretical analysis of the effect of TS on the prediction set sizes of APS and RAPS.
Specifically, we establish new results on effect of TS on their scores, according to which we provide a reasoning for the phenomenon.

## 2 Background and Related Work

Let us present the notations that are used in the paper, followed by some preliminaries on TS and CP.

We consider a $\displaystyle C$-classes classification task of the data $\displaystyle(X,Y)$ distributed on $\displaystyle\mathbb{R}^{d}\times[C]$, where $\displaystyle[C]:=\{1,\ldots,C\}$.
The classification is tackled by a DNN that for each input sample $\displaystyle\mathbf{x}\in\mathbb{R}^{d}$ produces a logits vector $\displaystyle\mathbf{z}=\mathbf{z}(\mathbf{x})\in\mathbb{R}^{C}$ that is fed into a final softmax function $\displaystyle\boldsymbol{\sigma}:\mathbb{R}^{C}\to\mathbb{R}^{C}$, defined as $\displaystyle\sigma_{i}(\mathbf{z})=\frac{\exp{(z_{i})}}{\sum_{j=1}^{C}\exp{(z
_{j})}}$.
Typically, the post-softmax vector $\displaystyle\hat{\boldsymbol{\pi}}(\mathbf{x})=\boldsymbol{\sigma}(\mathbf{z}
(\mathbf{x}))$ is being treated as an estimate of the class probabilities. Note that $\displaystyle\hat{\boldsymbol{\pi}}(\mathbf{x})$ is a valid probability vector,
namely, $\displaystyle\hat{\boldsymbol{\pi}}(\mathbf{x})\in\Delta^{C-1}$, where $\displaystyle\Delta^{C-1}:=\{\boldsymbol{\pi}\in\mathbb{R}^{C}:\pi_{i}\geq 0,
\pi_{1}+\ldots+\pi_{C}=1\}$ is the simplex in $\displaystyle\mathbb{R}^{C}$.
The predicted class is given by $\displaystyle\hat{y}(\mathbf{x})=\mathrm{argmax}_{i}\,\hat{\pi}_{i}(\mathbf{x})$.

### 2.1 Calibration and Temperature Scaling

The interpretation of $\displaystyle\hat{\boldsymbol{\pi}}(\mathbf{x})$ as an estimated class probabilities vector promotes treating $\displaystyle\hat{\pi}_{\hat{y}(\mathbf{x})}(\mathbf{x})$ as the probability that the predicted class $\displaystyle\hat{y}(\mathbf{x})$ is correct, also referred to as the model’s confidence.
However, it has been shown that DNNs are frequently overconfident — $\displaystyle\hat{\pi}_{\hat{y}(x)}(x)$ is larger than the true
correctness probability [].
Formally,
$\displaystyle\mathbb{P}\left(\hat{y}(X)=Y|\hat{\pi}_{\hat{y}(X)}(X)=p\right)<p$ with significant margin.
Post-processing calibration techniques aim at reducing the aforementioned gap.
They are based on optimizing certain transformations of the logits $\displaystyle\mathbf{z}(\cdot)$, yielding a probability vector $\displaystyle\tilde{\boldsymbol{\pi}}(\cdot)$ that minimizes an objective computed over a dedicated calibration set of labeled samples $\displaystyle\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}$ [, , , ].
Popular calibration objectives include the Negative Log-Likelihood (NLL) [] and the
Expected Calibration Error (ECE) [], detailed in Appendix B.3.

Temperature Scaling (TS) [] stands out as, arguably, the most common calibration approach, surpassing many others in achieving calibration with minimal computational complexity [, , , , , ].
It simply uses the transformation $\displaystyle\mathbf{z}\mapsto\mathbf{z}/T$ before applying the softmax, where $\displaystyle T>0$ (the temperature) is a single scalar parameter that is set by minimizing NLL or ECE. Additionally, TS preserves the accuracy rate of the network (the ranking of the elements – and in particular, the index of the maximum – is unchanged), which may otherwise be compromised during the calibration phase.

Hereafter, we use the notation $\displaystyle\hat{\boldsymbol{\pi}}_{T}(\mathbf{x}):=\boldsymbol{\sigma}(
\mathbf{z}(\mathbf{x})/T)$ to denote the output of the softmax when taking into account the temperature.
Observe that $\displaystyle T=1$ preserves the original probability vector.
Let us denote by $\displaystyle T^{*}$ the temperature that is optimal for TS calibration.
Since DNN classifiers are commonly overconfident, TS calibration typically yields some $\displaystyle T^{*}>1$, which “softens" the original probability vector.
Formally, TS with $\displaystyle T>1$ raises the entropy of the softmax output (see Proposition A.6 in the appendix).(^1^11We have not encountered a result like Proposition A.6 in the literature. Note that increasing the entropy of $\displaystyle\boldsymbol{\pi}\in\Delta^{C-1}$ implies nearing it to uniform probability in the “Kullback-Leibler divergence sense”.)

Figure: Before TS calibration
Refer to caption: extracted/5706552/ICML24/Plots/Reliability_diagrams_updated/cifar100_resnet50_B.png

The reliability diagram [, ]
is a graphical depiction of a model before and after calibration.
The confidence range $\displaystyle[0,1]$ is divided into bins and the validation samples (not used in the calibration) are assigned to the bins according to $\displaystyle\hat{\pi}_{\hat{y}(\mathbf{x})}(\mathbf{x})$. The average accuracy (Top-1) is computed per bin.
In the case of perfect calibration, the diagram should be aligned with the identity function. Any significant deviation from slope of 1 indicates miscalibration.
For example, the reliability diagram in Figure 1 shows the effectiveness of TS, based on ECE minimization, for calibrating a ResNet50 model trained on CIFAR-100 dataset.

### 2.2 Conformal Prediction

Conformal Prediction (CP) is a methodology that is model-agnostic and distribution-free, designed for generating
a prediction set of classes $\displaystyle\mathcal{C}_{\alpha}(X)$ for a given sample $\displaystyle X$, such that $\displaystyle Y\in\mathcal{C}_{\alpha}(X)$ with probability $\displaystyle 1-\alpha$ for a predefined $\displaystyle\alpha\in(0,1)$, where $\displaystyle Y$ is the true class associated with $\displaystyle X$ [, , ].
The decision rule is based on a calibration set of labeled samples $\displaystyle\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}$, which we hereafter refer to as the CP set, to avoid confusion with the set used for TS calibration.
The only assumption in CP is that the random variables associated with the CP set and the test samples are exchangeable (e.g., the samples are i.i.d.).

Let us state the general process of conformal prediction given the CP set $\displaystyle\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}$ and its deployment for a new (test) sample $\displaystyle x_{n+1}$ (for which $\displaystyle y_{n+1}$ is unknown), as presented in []:

- 1.
Define a heuristic score function $\displaystyle s(\mathbf{x},y)\in\mathbb{R}$ based on some output of the model. A higher score should encode a lower level of agreement between $\displaystyle\mathbf{x}$ and $\displaystyle y$.
- 2.
Compute $\displaystyle\hat{q}$ as the $\displaystyle\frac{\lceil(n+1)(1-\alpha)\rceil}{n}$ quantile of the scores $\displaystyle\{s(\mathbf{x}_{1},y_{1}),\dots,s(\mathbf{x}_{n},y_{n})\}$.
- 3.
At deployment, use $\displaystyle\hat{q}$ to create prediction sets for new samples:
$\displaystyle\mathcal{C}_{\alpha}(\mathbf{x}_{n+1})=\{y:\,s(\mathbf{x}_{n+1},y
)\leq\hat{q}\}$.

CP methods possess the following coverage guarantee.

###### Theorem 2.1 (Theorem 1 in [ 32 ] ) .

Suppose that $\displaystyle\{\left(X_{i},Y_{i}\right)\}_{i=1}^{n}$ and $\displaystyle(X_{n+1},Y_{n+1})$ are i.i.d.,
and define $\displaystyle\hat{q}$ as in step 2 above and $\displaystyle\mathcal{C}_{\alpha}(X_{n+1})$ as in step 3 above. Then the following holds:

$$ $\displaystyle\displaystyle\mathbb{P}\left(Y_{n+1}\in\mathcal{C}_{\alpha}(X_{n+ 1})\right)\geq 1-\alpha.$ (1) $$

The proof of this result is based on [].
A proof of an upper bound of $\displaystyle 1-\alpha+1/(n+1)$ also exists.
This property is called marginal coverage since the probability is taken over the entire distribution of $\displaystyle(X,Y)$.
While achieving marginal coverage is practically feasible, it unfortunately does not imply the much more stringent property of conditional coverage:

$$ $\displaystyle\displaystyle\mathbb{P}\left(Y_{n+1}\in\mathcal{C}_{\alpha}(X_{n+ 1})|X_{n+1}=\mathbf{x}\right)\geq 1-\alpha.$ (2) $$

Yet, coverage for any value $\displaystyle\mathbf{x}$ of the random $\displaystyle X$ is impracticable [], [], and a useful intuitive relaxation is to consider class-conditional coverage.

CP methods are usually compared by the size of their prediction sets and by their proximity to the conditional coverage property.
Over time, various CP techniques with distinct objectives have been developed [].
There have been also efforts to alleviate the exchangeability assumption [, ].
In this paper we will focus on three prominent CP methods. Each of them devises a different score $\displaystyle s(\mathbf{x},y)$ based on the output of the classifier’s softmax $\displaystyle\hat{\boldsymbol{\pi}}(\cdot)$.

Least Ambiguous Set-valued Classifier (LAC) [, ].
In this method, $\displaystyle s(\mathbf{x},y)=1-\hat{\pi}_{y}(\mathbf{x})$. Accordingly, given $\displaystyle\hat{q}_{LAC}$ associated with $\displaystyle\alpha$ through step 2,
the prediction sets are formed as: $\displaystyle\mathcal{C}^{LAC}(\mathbf{x}):=\{y:\hat{\pi}_{y}(\mathbf{x})\geq 1
-\hat{q}_{LAC}\}$.
LAC tends to have small set sizes (under the strong assumption that $\displaystyle\hat{\boldsymbol{\pi}}(\mathbf{x})$ matches the posterior probability, it provably gives the smallest possible average set size). On the other hand, its conditional coverage is limited.

Adaptive Prediction Sets (APS) [].
The objective of this method is to improve the conditional coverage.
Motivated by theory derived under the strong assumption that $\displaystyle\hat{\boldsymbol{\pi}}(\mathbf{x})$ matches the posterior probability, it uses $\displaystyle s(\mathbf{x},y)=\sum\nolimits_{i=1}^{L_{y}}\hat{\pi}_{(i)}(
\mathbf{x})$, where $\displaystyle\hat{\pi}_{(i)}(\mathbf{x})$ denotes the $\displaystyle i$-th element in a descendingly sorted version of $\displaystyle\hat{\boldsymbol{\pi}}(\mathbf{x})$ and $\displaystyle L_{y}$ is the index that $\displaystyle y$ is permuted to after sorting.
Following steps 2 and 3, yields $\displaystyle\hat{q}_{APS}$ and $\displaystyle\mathcal{C}^{APS}(\mathbf{x})$.

Regularized Adaptive Prediction Sets (RAPS) [].
A modification of APS that aims at improving its prediction set sizes
by penalizing hard examples to reduce their effect on $\displaystyle\hat{q}$.
With the same notation as APS, in RAPS we have $\displaystyle s(\mathbf{x},y)=\sum\nolimits_{i=1}^{L_{y}}\hat{\pi}_{(i)}(
\mathbf{x})+\lambda(L_{y}-k_{reg})_{+}$, where $\displaystyle\lambda,k_{reg}\geq 0$ are regularization hyperparameters and we use the notation $\displaystyle(\cdot)_{+}:=\mathrm{max}\{\cdot,0\}$.
Following steps 2 and 3, yields $\displaystyle\hat{q}_{RAPS}$ and $\displaystyle\mathcal{C}^{RAPS}(\mathbf{x})$.

Note that all these CP methods can be readily applied on $\displaystyle\boldsymbol{\pi}_{T^{*}}(\cdot)$
after TS calibration.
This is done, in [, , , ], where the authors stated that they applied TS calibration before examining the CP techniques.
However, none of these works has examined how TS calibration impacts any CP method. All the more so, no existing work has experimented applying TS with a range of temperatures before employing CP methods.

###### Theorem 2.1 (Theorem 1 in [ 32 ] ) .

## 3 The Effect of Temperature Scaling on CP Methods for DNN Classifiers

In this section, we empirically investigate the effect of TS on the performance of CP algorithms.
Specifically, we consider different datasets and models, and start by reporting the mean prediction set size, marginal coverage, and class-conditional coverage of CP algorithms, with and without an initial TS calibration procedure.
Then, we extend the empirical study to encompass a variety of temperatures. We analyze the findings and propose a general guideline for optimizing user utilization of CP algorithms.

### 3.1 Experimental setup

Datasets. We conducted our experiment on CIFAR-10, CIFAR-100 [] and ImageNet [] chosen for their diverse content and varying levels of difficulty.

Models. We utilized a diverse set of DNN classifiers, based on ResNets [] and DenseNets [].
For CIFAR-10: ResNet34 and ResNet50. For CIFAR-100: ResNet50 and DenseNet121.
For ImageNet: ResNet152 and DenseNet121.
Details on the training of the models are provided in Appendix B.1.

TS calibration.
For each dataset-model pair, we create a calibration set by randomly selecting 10% of the validation set.
We obtain the calibration temperature $\displaystyle T^{*}$ by optimizing the ECE objective. The optimal temperatures when using the NLL objective are very similar, as displayed in Table 3 in the Appendix  B.3.1. This justifies using ECE as the default for the experiments.

CP Algorithms.
For each of the dataset-model pairs, we
construct the “CP set" (used for computing the thresholds of CP methods) by randomly selecting $\displaystyle\{5\%,10\%,20\%\}$ of the validation set, while ensuring not to include in the CP set samples that are used in the TS calibration.
The CP methods that we examine are LAC, APS, and RAPS, detailed in Section 2.2 (we use the randomized versions of APS and RAPS, as done in []).
For each technique, we use $\displaystyle\alpha=0.1$ and $\displaystyle\alpha=0.05$, so the desired marginal coverage probability is $\displaystyle 90\%$ and $\displaystyle 95\%$, as common in most CP literature [, , ].

Metrics.
We report metrics over the validation set samples that were not included in the calibration set or CP set.
The metrics are as follows:

$\displaystyle\bullet$ Average set size (AvgSize) - The mean prediction set size of the CP algorithm.
$\displaystyle\bullet$ Marginal coverage gap (MarCovGap) - The deviation of the marginal coverage from the desired $\displaystyle 1-\alpha$.
$\displaystyle\bullet$ Top-5% class-coverage gap (TopCovGap) - The deviation from the desired $\displaystyle 1-\alpha$ coverage, averaged over the 5% of classes with the highest deviation.
We use top-5% classes deviation due to the high variance in the maximal class deviation.

The mathematical definitions of the metrics, along with additional details about the experimental setup, are presented in Appendix B.4.
Note that for these metrics: the lower the better.
Similar metrics have been used in [, ]. All the reported results, per metric, are the median-of-means along 100 trials where we randomly select the calibration/CP sets, similarly to [].

### 3.2 The effect of TS calibration on CP methods

**Table 1: Prediction Set Size. AvgSize metric along with $\displaystyle T^{*}$ and accuracy for dataset-model pairs using LAC, APS, and RAPS algorithms with $\displaystyle\alpha=0.1$, CP set size $\displaystyle 10\%$, pre- and post-TS calibration.**
|  |  | Accuracy(%) | AvgSize | AvgSize after TS |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset-Model | $\displaystyle T^{*}$ | Top-1 | Top-5 | LAC | APS | RAPS | LAC | APS | RAPS |
| ImageNet, ResNet152 | 1.227 | 78.3 | 94.0 | 1.95 | 6.34 | 2.71 | 1.92 | 11.1 | 4.30 |
| ImageNet, DenseNet121 | 1.024 | 74.4 | 91.9 | 2.73 | 9.6 | 4.70 | 2.76 | 11.3 | 4.88 |
| CIFAR-100, ResNet50 | 1.524 | 80.9 | 95.4 | 1.62 | 5.31 | 2.88 | 1.57 | 9.14 | 4.96 |
| CIFAR-100, DenseNet121 | 1.469 | 76.1 | 93.5 | 2.13 | 4.26 | 2.98 | 2.06 | 6.51 | 4.27 |
| CIFAR-10, ResNet50 | 1.761 | 94.6 | 99.7 | 0.91 | 1.04 | 0.98 | 0.91 | 1.13 | 1.05 |
| CIFAR-10, ResNet34 | 1.802 | 95.3 | 99.8 | 0.91 | 1.03 | 0.94 | 0.93 | 1.11 | 1.05 |

For each of the dataset-model pairs we compute the aforementioned metrics with and without an initial TS calibration procedure.
In Table 2, we report the the calibration temperature $\displaystyle T^{*}$, the accuracy (not affected by TS), and the median-of-means of the prediction set sizes metric, AvgSize. In Table 2, we report the median-of-means of the marginal and conditional coverage metrics, MarCovGap and TopCovGap. In both tables, the specified coverage probability is 90% ($\displaystyle\alpha=0.1$), and we use 10% of the samples for the CP set and 10% of the samples for the calibration set.

Due to space limitation, the results for coverage probability of 95% ($\displaystyle\alpha=0.05$) and sizes $\displaystyle\{5\%,20\%\}$ of the CP sets are deffer to Appendix B.5.
The insights gained from Tables 2 and 2 hold also for the deferred results.

Examining the results, we first see that the TS calibration temperatures, $\displaystyle T^{*}$, in Table 2 are greater than 1, indicating that the models exhibit overconfidence.
The reliability diagrams for ResNet50 trained on CIFAR-100 before and after TS calibration are presented in Figure 1.
In Appendix B.4.1, we present the reliability diagrams for the other dataset-model pairs.

By examining MarCovGap in
Table 2, we see that all CP methods maintain marginal coverage both with and without the initial TS procedure (the gap is at most 0.1%, i.e., 0.001).
That is, TS calibration does not affect this property, which is consistent with CP theoretical guarantees (Theorem 2.1).

As for the conditional coverage, as indicated by the TopCovGap metric in Table 2, there is no distinct trend observed for the LAC method. On the other hand, in the adaptive CP methods, APS and RAPS, there is a noticeable improvement (TopCovGap decreases), especially when $\displaystyle T^{*}$ is high.
We turn to examine
Table 2, which reports the effect of TS calibration on the prediction set size of the CP methods.
First, we see that for the CIFAR-10, where the models’ accuracy is very high, the effect on AvgSize is minor.
Second, we see that the effect on LAC is negligible also for other datasets.
(Note that while LAC has lower AvgSize than APS and RAPS, its conditional coverage is worse, as shown by TopCovGap in Table 2).
Third,
perhaps the most thought provoking observation,
for APS and RAPS
the TS calibration procedure has led to increase in the mean prediction set size.
Especially, when the value of the optimal temperature $\displaystyle T^{*}$ is high.
For instance, for ResNet50 on CIFAR-100, TS calibration increases AvgSize of APS from 5.31 to 9.14.
This behavior is quite surprising.

Figure: CIFAR100, ResNet50, APS
Refer to caption: extracted/5706552/ICML24/Plots/Sorted_differences_updated/aps_cifar100_resnet50.png

In order to verify that the increase in the mean set size for APS and RAPS is not caused by a small number of extreme outliers,
we “microscopically” analyze the change per sample.
Specifically, for each sample in the validation set, we compare the prediction set size after the CP procedure with and without the initial TS calibration (i.e., set size with TS calibration minus set size without).
Sorting the differences in a descending order yields a staircase-shaped curve.
The smoothed version of this curve, which is obtained after averaging over the 100 trials, is presented in Figure 2 for ResNet50 trained on CIFAR-100, both for APS and for RAPS. Similar behavior is observed for other dataset-model pairs, as displayed by the figures in Appendix  B.5.

In Figure 2, approximately one third of the samples experience a negative impact on the
prediction set size due to the TS calibration. For about half of the samples, there is no change in set size. Only the remaining small minority of samples experience improvement but to a much lesser extent than the harm observed for others. Interestingly, the
existence of samples (though few) where the TS procedure causes a decrease in set size indicates that we cannot make a universal (uniform) statement about the impact of TS on
the set size of arbitrary sample, but rather consider a typical/average case.

### 3.3 TS beyond calibration

The intriguing observations regarding TS calibration — especially, both positively and negatively affecting different aspects of APS and RAPS
— prompt us to explore the effects of TS on CP, beyond calibration, and whether it can be utilized by practitioners.
In Figure 3 we present the average prediction set size, AvgSize, the class-conditional coverage metric, TopCovGap, and the threshold value of the CP methods, $\displaystyle\hat{q}$, for temperatures ranging from 0.3 to 2 with an increment of 0.1.
The reported results are the median-of-means for 100 trials.
We present here three diverse dataset-model pairs, and defer the others to Appendix B.6 due to space limitation.
The appendix also includes
different settings, such as various calibration set sizes and coverage probability levels, as detailed in  3.1.

The trends in Figure 3 generalize the observations in the TS calibration experiments in Section 3.2. For the ImageNet and CIFAR-100 datasets, and the APS and RAPS algorithms, there is a notable increase in AvgSize (top row) accompanied by a decrease in the threshold value $\displaystyle\hat{q}$ (bottom row) as $\displaystyle T$ increases. Note, though, that a decrease in $\displaystyle\hat{q}$ does not
suffice for explaining
larger prediction sets. (A naive example is reducing $\displaystyle\hat{q}$ simply by defining a modified CP score where some constant is subtracted from $\displaystyle s(\mathbf{x},y)$). Additionally, the TopCovGap metric of APS and RAPS (middle row) improves with rising $\displaystyle T$. This reveals that as the temperature $\displaystyle T$ increases/decreases, there is a trade-off between two crucial properties of these CP methods: the size of the prediction set and the proximity to conditional coverage.
In practice, the desired balance between the properties varies depending on the setting and usage of the machine learning model.
Furthermore, our results show that none of the methods LAC/APS/RAPS dominates the others in both AvgSize and TopCovGap, especially when $\displaystyle T$ is set per method.

Our results show the limitation of
any technique for setting $\displaystyle T$ before applying adaptive CP methods that ignores the trade-off.
Nevertheless, the fact that TS enables to easily trade
AvgSize and TopCovGap by increasing/decreasing $\displaystyle T$ before applying these methods, allows us to provide general guidelines for utilizing the trade-off while achieving calibrated outputs.

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/MEAN_SET_SIZE/NO_STD/CP_SET_SIZE/REGULAR/imagenet_resnet152.png

Guideline for practitioners.
We propose a guideline for practitioners that wish to use adaptive CP methods (e.g., due to their better conditional coverage), which is depicted in Figure 4.
Specifically, we suggest to use TS with two different temperature parameters on separate branches: $\displaystyle T^{*}$ that is optimized for TS calibration, and $\displaystyle\hat{T}$ that allows trading the aforementioned properties of APS/RAPS to better fit the task’s requirements.
A limitation is that one does not know in advance what values of the metrics are obtained per value of $\displaystyle\hat{T}$.
However, since we propose to separate the calibration and the CP procedure, the calibration set can also be used to evaluate the CP algorithms without dangering exchangeability. Indeed, in Appendix C, we demonstrate how using a small amount of calibration data we can approximate the curves of AvgSize and TopCovGap vs. $\displaystyle T$ that appear in Figure 3 (which were generated using the entire validation set that is not accessible to the user in practice).
According to the approximate trends, the user can choose $\displaystyle\hat{T}$ that best fit their requirements.
Furthermore, note that the procedure required to produce approximated curves of metrics vs. $\displaystyle T$ is done offline during the calibration phase and its runtime is negligible compared to the offline training of DNNs.

Figure: Figure 4: Guideline for using TS calibration and adaptive CP.
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/SUGGESTION.png

Further simplifying the procedure and potentially adjusting $\displaystyle\hat{T}$ online, akin to a knob that controls the trade-off, requires addresing the fact that the CP threshold $\displaystyle\hat{q}=\hat{q}(T)$ depends on $\displaystyle T$ and needs to be computed via the CP set offline.
Interestingly, Figure 3 (bottom row) shows that for APS and RAPS, $\displaystyle\hat{q}(T)$ is a rather simple monotonically decreasing function, as observed also without averaging over trials (in the sequel we prove this monotonicity).
Thus, potentially, one can calibrate APS/RAPS offline and obtain $\displaystyle\hat{q}(T)$ only for a few values of $\displaystyle T$, and then fit a simple polynomial model that predicts $\displaystyle\hat{q}(T)$ at other values of $\displaystyle T$.
In Appendix C, we show the efficacy of this idea: the performance of RAPS is empirically maintained with interpolated thresholds.

## 4 Theoretical Analysis

In this section, we provide mathematical reasoning for empirical observations regarding the effect of TS on the prediction set size of APS and RAPS presented in Section 3.
Theoretically analyzing our other findings, such as the effect of TS on the conditional coverage, are left for future research.
All the proofs are provided in Appendix A.

### 4.1 TS affects the coverage probability only through misclassified samples

One of our observations is that the effect of TS (even with rather large $\displaystyle T$) on CP methods’ prediction set size is negligible in “easy” settings, such as with CIFAR-10, where the models’ Top-1 accuracy is significantly above $\displaystyle 1-\alpha$.
Indeed, in such cases it is enough to pick the single class that dominates the softmax in order to achieve coverage.
The following proposition shows
that TS affects the coverage probability $\displaystyle P(Y\in C_{\alpha}(X))$ only through misclassified samples in general (not only for models that are “accurate enough”).

###### Proposition 4.1 .

Let $\displaystyle\hat{y}(x)$ estimate the class according to the dominant entry in the post-softmax vector.
Assume that a CP method uses a score that preserves the ranking of the post-softmax vector (the common case).
The marginal coverage probability $\displaystyle P(Y\in C_{\alpha}(X))$ depends on TS only through samples that are misclassified.

The proposition hints that the effect of TS on aspects of CP methods, e.g., prediction set size, which are required for satisfying the marginal coverage property (1), is through misclassified samples in the CP set. This is aligned with our empirical observation of the minor change in on the prediction set sizes when the model is very accurate (Top-1 accuracy above $\displaystyle 1-\alpha$).

###### Proposition 4.1 .

### 4.2 TS with increased T 𝑇 \displaystyle T italic_T decreases the threshold of APS and RAPS

In Section 3.3, we observe
that increasing the temperature monotonically
reduces the threshold of APS and RAPS.
We will prove this theoretically.

Recall the score in the APS method: $\displaystyle s(\mathbf{x},y)=\sum\nolimits_{i=1}^{L_{y}}\hat{\pi}_{(i)}(
\mathbf{x})$, where $\displaystyle\hat{\pi}_{(i)}(\mathbf{x})$ denotes the $\displaystyle i$-th element in a descendingly sorted version of $\displaystyle\hat{\boldsymbol{\pi}}(\mathbf{x})$ and $\displaystyle L_{y}$ is the index that $\displaystyle y$ is permuted to after sorting.
Recall that the RAPS algorithm is based on the same score with an additional regularization term that is not affected by TS.
Let us denote by $\displaystyle s_{T}(\mathbf{x},y)$ the score of the same sample after TS, i.e., using $\displaystyle\hat{\boldsymbol{\pi}}_{T}(\mathbf{x})$. Note that

$$ $\displaystyle s_{T}(\mathbf{x},y)=\sum\nolimits_{i=1}^{L_{y}}\hat{\pi}_{T,(i)} (\mathbf{x})=\sum\nolimits_{i=1}^{L_{y}}[\boldsymbol{\sigma}(\ln{(\hat{ \boldsymbol{\pi}}(\mathbf{x})})/T)]_{(i)}$ $$

where we use the fact that $\displaystyle\hat{\boldsymbol{\pi}}_{T}=\boldsymbol{\sigma}(\ln(\hat{
\boldsymbol{\pi}})/T)$, which follows from the ability to recover the logits $\displaystyle\mathbf{z}(\mathbf{x})=\ln(\hat{\boldsymbol{\pi}}(\mathbf{x}))$ up to a constant $\displaystyle c\mathbf{1}_{C}$, which does not affect the softmax also after scaling by $\displaystyle T$.
Here, $\displaystyle\ln(\cdot)$ operates entry-wise.
In addition, note that TS does not change the ranking of the entries.

We now state a theorem that shows that TS with $\displaystyle T>1$ decreases the cumulative sum of sorted probability vectors, akin to the score used by APS.

###### Theorem 4.2 .

Let $\displaystyle\boldsymbol{\pi}\in\Delta^{C-1}$ (probability vector in $\displaystyle\mathbb{R}^{C}$) such that $\displaystyle\pi_{1}\geq\pi_{2}\geq\ldots\geq\pi_{C}$ (i.e., sorted) and let $\displaystyle T\geq 1$ and $\displaystyle L\in[C]$. Then, we have
$\displaystyle\sum\nolimits_{j=1}^{L}\pi_{j}\geq\sum\nolimits_{j=1}^{L}\pi_{T,j}$,
where $\displaystyle\boldsymbol{\pi}_{T}=\boldsymbol{\sigma}(\ln(\boldsymbol{\pi})/T)$ is the softmax output after applying TS with $\displaystyle T$ on the logits associated with $\displaystyle\boldsymbol{\pi}$.
The inequality is strict, unless $\displaystyle L=C$ or $\displaystyle T=1$ or $\displaystyle\pi_{1}=\ldots=\pi_{C}$.

Note that Theorem 4.2 is universal: it holds for any sorted probability vector.
Denote the threshold obtained by applying the CP method after TS by $\displaystyle\hat{q}_{T}$.
Based on the universality of the theorem, we can establish that increasing the temperature $\displaystyle T$ decreases $\displaystyle\hat{q}_{T}$ for APS and RAPS.

###### Corollary 4.3 .

The threshold value $\displaystyle\hat{q}_{T}$
of APS and RAPS decreases monotonically as the temperature $\displaystyle T$ increases above $\displaystyle 1$.

This corollary motivates learning the map $\displaystyle T\mapsto\hat{q}(T)$, as discussed in Section 3.3.

###### Theorem 4.2 .

###### Corollary 4.3 .

### 4.3 TS with increased T 𝑇 \displaystyle T italic_T tends to increase the prediction set size of APS

Figure: Figure 5: Illustration of TS with $\displaystyle T>1$ on softmax output. Here, TS increases the prediction set size from 2 to 3.
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/ILLUSTRATION.png

In Section 3, we observe that
increasing the temperature typically increases the size of the prediction sets produced by APS and RAPS.
For simplification we consider
APS.

Formally, for a new test sample $\displaystyle\mathbf{x}$ (not from calibration or CP sets)
we denote by $\displaystyle\hat{\boldsymbol{\pi}}$ and $\displaystyle\hat{\boldsymbol{\pi}}_{T}$ the softmax output with and without TS, respectively, after being sorted in descending order. (The relation $\displaystyle\hat{\boldsymbol{\pi}}_{T}=\boldsymbol{\sigma}(\ln(\hat{
\boldsymbol{\pi}})/T)$ still holds.)
We also denote
$\displaystyle L=\min\{l:\sum\nolimits_{i=1}^{l}\hat{\pi}_{i}\geq\hat{q}\}$ , $\displaystyle L_{T}=\min\{l:\sum\nolimits_{i=1}^{l}\hat{\pi}_{T,i}\geq\hat{q}_
{T}\}$ to be the prediction set sizes for this sample according to APS with and without TS, respectively.
Our experiments show that having $\displaystyle T>1$ yields $\displaystyle L_{T}\geq L$ for “typical” $\displaystyle\mathbf{x}$. Specifically, in our TS calibration experiments, we had $\displaystyle T>1$ and we observed that it is more likely that this inequality holds than that it does not.
See Figure 5 for illustration.
Alternatively, we can study the event

$$ $\displaystyle\displaystyle\sum\nolimits_{i=1}^{{\color[rgb]{0,0,0}L}}\hat{\pi} _{i}-\sum\nolimits_{i=1}^{{\color[rgb]{0,0,0}L}}\hat{\pi}_{T,i}\geq\hat{q}- \hat{q}_{T},$ (3) $$

as established in Proposition A.5 (which uses $\displaystyle\hat{q}\geq\hat{q}_{T}$ ensured by Corollary 4.3 for $\displaystyle T>1$).
Namely, TS with $\displaystyle T>1$ affects “typical" samples more than it affects the samples (in the CP set) that determine the thresholds $\displaystyle\hat{q},\hat{q}_{T}$.
Since $\displaystyle 1-\alpha$ is large, the samples that determine $\displaystyle\hat{q},\hat{q}_{T}$ are expected to be harder for classification, e.g., without a dominant entry in their post-softmax vectors.

To simplify the analysis, let us assume that both $\displaystyle\hat{q}$, $\displaystyle\hat{q}_{T}$ are associated with the same sample in the CP set, $\displaystyle\mathbf{x}^{hard}$, for which we can associate the sorted softmax outputs $\displaystyle\boldsymbol{\pi}^{hard}$ and $\displaystyle\boldsymbol{\pi}_{T}^{hard}=\boldsymbol{\sigma}(\ln(\boldsymbol{
\pi}^{hard})/T)$.
With this assumption, studying (3) translates to studying the “gap function”

$$ $\displaystyle\displaystyle g(\boldsymbol{\pi};T,L)=\sum\nolimits_{i=1}^{L}\pi_ {i}-\sum\nolimits_{i=1}^{L}\sigma_{i}(\frac{1}{T}\ln\boldsymbol{\pi}),$ (4) $$

showing that $\displaystyle g(\hat{\boldsymbol{\pi}};T,{\color[rgb]{0,0,0}L})\geq g(
\boldsymbol{\pi}^{hard};T,L^{hard})$.
Note that Theorem 4.2 already teaches us that $\displaystyle g(\boldsymbol{\pi};T,L)\geq 0$ for $\displaystyle T\geq 1$.
However, precise global analysis of $\displaystyle g(\boldsymbol{\pi};T,L)$ appears to be very challenging.
Therefore, we turn to use a local analysis.

Since $\displaystyle\boldsymbol{\pi}^{hard}$ is more dispersed (less decisive) than a “typical” $\displaystyle\hat{\boldsymbol{\pi}}$, which tend to have a dominant first entry, for the analysis we model $\displaystyle\hat{\boldsymbol{\pi}}-\boldsymbol{\pi}^{hard}$ by a prototypical vector $\displaystyle\mathbf{r}$ with a dominant first entry (and such that with small enough $\displaystyle\|\mathbf{r}\|$, $\displaystyle\boldsymbol{\pi}^{hard}+\mathbf{r}$ is still in $\displaystyle\Delta^{C-1}$).
The following theorem establishes values of $\displaystyle T$ that ensure that $\displaystyle\mathbf{r}$ is an ascent direction of $\displaystyle g(\boldsymbol{\pi};T,L)$.

###### Theorem 4.4 .

Let $\displaystyle\boldsymbol{\pi}\in\Delta^{C-1}$ be a probability vector with $\displaystyle\pi_{i}>0$, and mean $\displaystyle\overline{\pi}=\frac{1}{C}\sum\nolimits_{i=1}^{C}\pi_{i}$.
Let $\displaystyle L\in[C-1]$ and $\displaystyle\mathbf{r}=[\delta,-\delta/(C-1),\ldots,-\delta/(C-1)]^{\top}$ with some $\displaystyle\delta>0$. If

$$ $\displaystyle T>\frac{C\sqrt{L}}{(C-L)\pi_{1}}+\frac{\sqrt{L}}{(C-L)}\left\| \left[\pi_{1}^{-1}-\overline{\pi}^{-1},\ldots,\pi_{C}^{-1}-\overline{\pi}^{-1} \right]\right\|_{2}$ $$

then for small enough step $\displaystyle\eta>0$, $\displaystyle g(\boldsymbol{\pi};T,L)$ stated in (4) obeys:
$\displaystyle g(\boldsymbol{\pi}+\eta\mathbf{r};T,L)>g(\boldsymbol{\pi};T,L)$.

Inspecting the effect of $\displaystyle\boldsymbol{\pi}$ on the lower bound on $\displaystyle T$ in Theorem 4.4 provides some insights.
Specifically, we see that the second term in the bound decreases as $\displaystyle\boldsymbol{\pi}$ is closer to the center of the simplex (uniform probability), which can be interpreted as being associated with a hard sample $\displaystyle\boldsymbol{\pi}^{hard}$.
Thus, in such case, even rather small $\displaystyle T>1$ suffices for increasing $\displaystyle g$ when taking a step toward the dominant vertex, $\displaystyle\boldsymbol{\pi}^{hard}+\eta\mathbf{r}$.
Note that $\displaystyle\mathbf{r}$ stated in the theorem is chosen to simplify the analysis, but the statement can be generalized to other instances of $\displaystyle\mathbf{r}$ with dominant first entry.

Even though Theorem 4.4 presents a local analysis of $\displaystyle g(\cdot;T,L)$, it provides a formal reasoning why it is likely that $\displaystyle g(\hat{\boldsymbol{\pi}};T,{\color[rgb]{0,0,0}L})>g(\boldsymbol{
\pi}^{hard};T,{\color[rgb]{0,0,0}L})$.
Adding to this the reasonable assumption that $\displaystyle g(\boldsymbol{\pi}^{hard};T,{\color[rgb]{0,0,0}L})>g(\boldsymbol
{\pi}^{hard};T,L^{hard})$ due to $\displaystyle g(\boldsymbol{\pi}^{hard};T,L^{hard})$ summing over $\displaystyle L^{hard}-{\color[rgb]{0,0,0}L}>0$ additional negative entries of $\displaystyle\boldsymbol{\pi}^{hard}-\boldsymbol{\pi}_{T}^{hard}$ , further explains this having $\displaystyle g(\hat{\boldsymbol{\pi}};T,{\color[rgb]{0,0,0}L})>g(\boldsymbol{
\pi}^{hard};T,L^{hard})$.

###### Theorem 4.4 .

## 5 Conclusion

In this work, we studied the effect the widely used temperature scaling (TS) calibration on the performance of conformal prediction (CP) techniques.
These popular complementary approaches are useful for assessing the reliability of classifiers, in particular those that are based DNNs. Yet, their interplay has not been examined so far.
We conducted an extensive empirical study on the effect of TS, even beyond its calibration application, on CP methods. Among our findings, we discovered that TS enables trading prediction set size and class-conditional coverage performance of adaptive CP methods.
Based on this, we provided practical guidelines for combining these methods with calibration while adjusting them to better fit specific requirements.
We also presented theoretical analysis of the effect of TS on the prediction set sizes of APS and RAPS. We believe that extending the theoretical understanding of our empirical findings is an interesting direction for future research.

## Acknowledgments and Disclosure of Funding

The work is supported by the ISF grant No. 1940/23.

## Appendix A Proofs.

###### Proposition A.1 .

Let $\displaystyle\hat{y}(x)$ estimate the class according to the dominant entry in the post-softmax vector.
Assume that a CP method uses a score that preserves the ranking of the post-softmax vector (the common case).
The marginal coverage probability $\displaystyle P(Y\in C_{\alpha}(X))$ depends on TS only through samples that are misclassified.

###### Proof.

The proof utilizes the law of total expectation (note that $\displaystyle\mathbb{P}\left(Y\in\mathcal{C}_{\alpha}(X)\right)=\mathbb{E}
\left[\mathbb{I}\{Y\in\mathcal{C}_{\alpha}(X)\}\right]$).

We have

$$ $\displaystyle\displaystyle\mathbb{P}\left(Y\in\mathcal{C}_{\alpha}(X)\right)$ $\displaystyle\displaystyle=\int p_{X}(x)\mathbb{P}\left(Y\in\mathcal{C}_{ \alpha}(X)|X=x\right)dx$ $\displaystyle\displaystyle=\int p_{X}(x)\Big{[}\mathbb{P}(\hat{y}(X)=Y|X=x) \mathbb{P}\left(Y\in\mathcal{C}_{\alpha}(X)|X=x,\hat{y}(X)=Y\right)$ $\displaystyle\displaystyle\hskip 56.9055pt+\mathbb{P}(\hat{y}(X)\neq Y|X=x) \mathbb{P}\left(Y\in\mathcal{C}_{\alpha}(X)|X=x,\hat{y}(X)\neq Y\right)\Big{]}dx.$ (5) $$

Now, observe that TS does not change the predicted class, Thus, it does not change $\displaystyle\mathbb{P}(\hat{y}(X)=Y|X=x)$ and $\displaystyle\mathbb{P}(\hat{y}(X)\neq Y|X=x)$.
Moreover, since the CP method preserves the ranking of the post-softmax vector we have $\displaystyle\mathbb{P}\left(Y\in\mathcal{C}_{\alpha}(X)|X=x,\hat{y}(X)=Y
\right)=1$.
Therefore, the only expression in (A) that is affected by TS is $\displaystyle\mathbb{P}\left(Y\in\mathcal{C}_{\alpha}(X)|X=x,\hat{y}(X)\neq Y\right)$, which considers only the misclassification event.

∎

###### Theorem A.2 .

Let $\displaystyle\boldsymbol{\pi}\in\Delta^{C-1}$ (probability vector in $\displaystyle\mathbb{R}^{C}$) such that $\displaystyle\pi_{1}\geq\pi_{2}\geq\ldots\geq\pi_{C}$ (i.e., sorted) and let $\displaystyle T\geq 1$ and $\displaystyle L\in[C]$. Then, we have

$$ $\displaystyle\displaystyle\sum_{j=1}^{L}\pi_{j}\geq\sum_{j=1}^{L}\pi_{T,j},$ $$

where $\displaystyle\boldsymbol{\pi}_{T}=\boldsymbol{\sigma}(\ln(\boldsymbol{\pi})/T)$ is the softmax output after applying TS with $\displaystyle T$ on the logits associated with $\displaystyle\boldsymbol{\pi}$.
The inequality is strict, unless $\displaystyle L=C$ or $\displaystyle T=1$ or $\displaystyle\pi_{1}=\ldots=\pi_{C}$.

###### Proof.

The statement, which is given in the “probability domain" $\displaystyle\boldsymbol{\pi}\in\Delta^{C-1}$, can be equivalently stated for logits $\displaystyle\mathbf{z}\in\mathbb{R}^{C}$.
The reason is that the softmax does no change the ranking and is invertible up to a constant $\displaystyle\boldsymbol{\sigma}(\ln\boldsymbol{\pi}+c\mathbf{1}_{C})=
\boldsymbol{\pi}$.

###### Theorem .

Let $\displaystyle\mathbf{z}\in\mathbb{R}^{C}$ such that $\displaystyle z_{1}\geq z_{2}\geq\ldots\geq z_{C}$ (i.e., sorted) and let $\displaystyle T\geq 1$ and $\displaystyle L\in[C]$. Then, we have

$$ $\displaystyle\displaystyle\sum_{j=1}^{L}\frac{\exp({z_{j})}}{\sum_{c=1}^{C} \exp{(z_{c})}}\geq\sum_{j=1}^{L}\frac{\exp({z_{j}/T)}}{\sum_{c=1}^{C}\exp{(z_{ c}/T)}}.$ (6) $$

The inequality is strict, unless $\displaystyle T=1$ or $\displaystyle z_{1}=\ldots=z_{C}$.

Before we turn to prove the theorem, let us prove an auxiliary lemma.

###### Lemma .

Let $\displaystyle z_{i},z_{j}\in\mathbb{R}$ such that $\displaystyle z_{i}\geq z_{j}$ and let T $\displaystyle\geq 1$. Then, the following holds

$$ $\displaystyle\displaystyle\exp(z_{i})\cdot\exp(z_{j}/T)\geq\exp(z_{i}/T)\cdot \exp(z_{j}).$ $$

The inequality is strict, unless $\displaystyle T=1$ or $\displaystyle z_{i}=z_{j}$.

###### Proof.

Since $\displaystyle z_{i}-z_{j}\geq 0$ and $\displaystyle 1-1/T\geq 0$ we have that

$$ $\displaystyle\exp\left[(z_{i}-z_{j})\left(1-\frac{1}{T}\right)\right]\geq 1,$ $$

where the inequality is strict, unless $\displaystyle T=1$ or $\displaystyle z_{i}=z_{j}$.
Next, observe that

$$ $\displaystyle\displaystyle\exp\left[(z_{i}-z_{j})\left(1-\frac{1}{T}\right)\right]$ $\displaystyle\displaystyle=\exp\left[z_{i}\left(1-\frac{1}{T}\right)-z_{j} \left(1-\frac{1}{T}\right)\right]$ $\displaystyle\displaystyle=\frac{\exp\left(z_{i}+\frac{z_{j}}{T}\right)}{\exp \left(\frac{z_{i}}{T}+z_{j}\right)}$ $\displaystyle\displaystyle=\frac{\exp(z_{i})\cdot\exp(z_{j}/T)}{\exp(z_{i}/T) \cdot\exp(z_{j})}.$ $$

Using the inequality we have $\displaystyle\frac{\exp(z_{i})\cdot\exp(z_{j}/T)}{\exp(z_{i}/T)\cdot\exp(z_{j}
)}\geq 1$, which concludes the proof of the lemma.

∎

Back to the proof of the theorem.

Let $\displaystyle I=\{1,2,\ldots,L\}$ and $\displaystyle J=\{L+1,L+2,\ldots,C\}$.
Because $\displaystyle\mathbf{z}$ is sorted, $\displaystyle\forall i\in I,j\in J$ we have $\displaystyle z_{i}>z_{j}$.
Therefore, according to the auxiliary lemma: $\displaystyle\exp(z_{i})\cdot\exp(z_{j}/T)\geq\exp(z_{i}/T)\cdot\exp(z_{j})$.
Consequently, the following holds:

$$ $\displaystyle\displaystyle\sum_{i=1}^{L}\sum_{j=L+1}^{C}\exp(z_{i})\cdot\exp(z _{j}/T)$ $\displaystyle\displaystyle\geq\sum_{i=1}^{L}\sum_{j=L+1}^{C}\exp(z_{i}/T)\cdot \exp(z_{j})$ $\displaystyle\displaystyle\Updownarrow$ $\displaystyle\displaystyle\sum_{i=1}^{L}\exp(z_{i})\cdot\sum_{j=L+1}^{C}\exp(z _{j}/T)$ $\displaystyle\displaystyle\geq\sum_{i=1}^{L}\exp(z_{i}/T)\cdot\sum_{j=L+1}^{C} \exp(z_{j}).$ $$

Adding $\displaystyle\sum_{i=1}^{L}\exp(z_{i})\cdot\sum_{j=1}^{L}\exp(z_{j}/T)$ to both sides, we get

$$ $\displaystyle\sum_{i=1}^{L}\exp(z_{i})\sum_{j=L+1}^{C}\exp(z_{j}/T)+\sum_{i=1} ^{L}\exp(z_{i})\sum_{j=1}^{L}\exp(z_{j}/T)\,\geq\,\sum_{i=1}^{L}\exp(z_{i}/T) \sum_{j=L+1}^{C}\exp(z_{j})+\sum_{i=1}^{L}\exp(z_{i})\sum_{j=1}^{L}\exp(z_{j}/ T),$ $$

which can be written as

$$ $\displaystyle\displaystyle\sum_{i=1}^{L}\exp(z_{i})\left[\sum_{i=1}^{L}\exp \left(z_{i}/T\right)+\sum_{j=L+1}^{C}\exp\left(z_{j}/T\right)\right]$ $\displaystyle\displaystyle\geq\sum_{j=1}^{L}\exp\left(z_{j}/T\right)\left[\sum _{i=1}^{L}\exp(z_{i})+\sum_{j=L+1}^{C}\exp(z_{j})\right]$ $\displaystyle\displaystyle\Updownarrow$ $\displaystyle\displaystyle\sum_{i=1}^{L}\exp(z_{i})\sum_{j=1}^{C}\exp\left(z_{ j}/T\right)$ $\displaystyle\displaystyle\geq\sum_{i=1}^{L}\exp\left(z_{i}/T\right)\sum_{j=1} ^{C}\exp(z_{j})$ $\displaystyle\displaystyle\Updownarrow$ $\displaystyle\displaystyle\frac{\sum_{i=1}^{L}\exp(z_{i})}{\sum_{j=1}^{C}\exp( z_{j})}$ $\displaystyle\displaystyle\geq\frac{\sum_{i=1}^{L}\exp\left(z_{i}/T\right)}{ \sum_{j=1}^{C}\exp\left(z_{j}/T\right)}$ $\displaystyle\displaystyle\Updownarrow$ $\displaystyle\displaystyle\sum_{j=1}^{L}\frac{\exp({z_{j})}}{\sum_{c=1}^{C} \exp{(z_{c})}}$ $\displaystyle\displaystyle\geq\sum_{j=1}^{L}\frac{\exp({z_{j}/T)}}{\sum_{c=1}^ {C}\exp{(z_{c}/T)}}$ $$

as stated in the theorem.
Note that the inequality is strict unless $\displaystyle L=C$ (both sides equal $\displaystyle 1$) or $\displaystyle T=1$ or $\displaystyle z_{1}=\ldots=z_{C}$ (all the pairs are equal).

∎

###### Corollary A.3 .

The threshold value $\displaystyle\hat{q}$ of APS and RAPS decreases monotonically as the temperature $\displaystyle T$ increases above $\displaystyle 1$.

###### Proof.

Let us start with APS.
Set $\displaystyle T\geq 1$. For each sample $\displaystyle(\mathbf{x},y)$ in the CP set, we get the post softmax vectors $\displaystyle\hat{\boldsymbol{\pi}}_{T}$ and $\displaystyle\hat{\boldsymbol{\pi}}$, with and without TS, respectively.
By Theorem A.2, applied on the sorted vector $\displaystyle\boldsymbol{\pi}=[\hat{\pi}_{(1)},\ldots,\hat{\pi}_{(C)}]^{\top}$ with $\displaystyle L=L_{y}$ (the index that y is permuted to after sorting), we have that

$$ $\displaystyle\displaystyle\sum_{i=1}^{L_{y}}\hat{\pi}_{(i)}(\mathbf{x})\geq \sum_{i=1}^{L_{y}}\hat{\pi}_{T,(i)}(\mathbf{x}).$ (7) $$

That is, the score of APS decreases universally for each sample in the CP set.
This implies that $\displaystyle\hat{q}$, the $\displaystyle\frac{\lceil(n+1)(1-\alpha)\rceil}{n}$ quantile of the scores of the samples of the CP set, decreases as well.

The statement can be extended to monotonic decrease simply but observing that for each $\displaystyle T_{2}\geq T_{1}\geq 1$ we can apply Theorem A.2 with $\displaystyle\boldsymbol{\pi}=[\hat{\pi}_{T_{1},(1)},\ldots,\hat{\pi}_{T_{1},(
C)}]^{\top}$ and $\displaystyle T=T_{2}/T_{1}\geq 1$.

We turn to consider RAPS. In this case, a decrease due to TS in the score of each sample $\displaystyle(\mathbf{x},y)$ in the CP set, i.e.,

$$ $\displaystyle\sum_{i=1}^{L_{y}}\hat{\pi}_{(i)}(\mathbf{x})+\lambda(L_{y}-k_{ reg})_{+}\geq\sum_{i=1}^{L_{y}}\hat{\pi}_{T,(i)}(\mathbf{x})+\lambda(L_{y}-k_{ reg})_{+},$ $$

simply follows from adding $\displaystyle\lambda(L_{y}-k_{reg})_{+}$ to both sides of (7).
The rest of the arguments are exactly as in APS.

∎

###### Theorem A.4 .

Let $\displaystyle\boldsymbol{\pi}\in\Delta^{C-1}$ be a probability vector with $\displaystyle\pi_{i}>0$, and mean $\displaystyle\overline{\pi}=\frac{1}{C}\sum_{i=1}^{C}\pi_{i}$.
Consider the function
$\displaystyle g(\boldsymbol{\pi};T,L)=\sum_{i=1}^{L}\pi_{i}-\sum_{i=1}^{L}
\sigma_{i}(\frac{1}{T}\ln\boldsymbol{\pi})$, where $\displaystyle\boldsymbol{\sigma}(\cdot)$ is the softmax function. Let $\displaystyle L\in[C-1]$ and $\displaystyle\mathbf{r}=[\delta,-\frac{1}{C-1}\delta,\ldots,-\frac{1}{C-1}
\delta]^{\top}$ with some $\displaystyle\delta>0$. If

$$ $\displaystyle T>\frac{C\sqrt{L}}{(C-L)\pi_{1}}+\frac{\sqrt{L}}{(C-L)}\left\| \left[\pi_{1}^{-1}-\overline{\pi}^{-1},\ldots,\pi_{C}^{-1}-\overline{\pi}^{-1} \right]\right\|_{2}$ $$

then for small enough step $\displaystyle\eta>0$, we have:

$$ $\displaystyle g(\boldsymbol{\pi}+\eta\mathbf{r};T,L)>g(\boldsymbol{\pi};T,L).$ $$

###### Proof.

Denote $\displaystyle\boldsymbol{\pi}^{-1}=[1/\pi_{1},\ldots,1/\pi_{C}]^{\top}$.
Denote also $\displaystyle\boldsymbol{\pi}_{T}=\boldsymbol{\sigma}(\frac{1}{T}\ln
\boldsymbol{\pi})$ and $\displaystyle\mathbf{J}_{\boldsymbol{\pi}_{T}}=\mathrm{diag}(\boldsymbol{\pi}_
{T})-\boldsymbol{\pi}_{T}\boldsymbol{\pi}_{T}^{\top}$ (which is the Jacobian of the softmax at the point $\displaystyle\frac{1}{T}\ln\boldsymbol{\pi}$).
Denote by $\displaystyle\mathbf{1}_{1:L}$ the vector in $\displaystyle\mathbb{R}^{C}$ with ones in its first $\displaystyle L$ entries and zeros elsewhere.

Using the chain rule, we have that

$$ $\displaystyle\nabla g(\boldsymbol{\pi};T,L)=\mathbf{1}_{1:L}-\frac{1}{T} \mathrm{diag}(\boldsymbol{\pi}^{-1})\left(\mathrm{diag}(\boldsymbol{\pi}_{T})- \boldsymbol{\pi}_{T}\boldsymbol{\pi}_{T}^{\top}\right)\mathbf{1}_{1:L}=\mathbf {1}_{1:L}-\frac{1}{T}\mathrm{diag}(\boldsymbol{\pi}^{-1})\mathbf{J}_{ \boldsymbol{\pi}_{T}}\mathbf{1}_{1:L}.$ $$

Therefore,

$$ $\displaystyle\displaystyle\mathbf{r}^{\top}\nabla g(\boldsymbol{\pi};T,L)$ $\displaystyle\displaystyle=(1-\frac{L-1}{C-1})\delta-\frac{\delta}{T}\left[ \frac{1}{\pi_{1}},-\frac{1}{(C-1)\pi_{2}},\ldots,-\frac{1}{(C-1)\pi_{C}}\right ]\mathbf{J}_{\boldsymbol{\pi}_{T}}\mathbf{1}_{1:L}$ $\displaystyle\displaystyle=\frac{C-L}{C-1}\delta-\frac{\delta}{T}\left(\left[ \frac{C}{(C-1)\pi_{1}},0,\ldots,0\right]-\frac{1}{(C-1)}\left(\boldsymbol{\pi} ^{-1}\right)^{\top}\right)\mathbf{J}_{\boldsymbol{\pi}_{T}}\mathbf{1}_{1:L}$ $\displaystyle\displaystyle=\frac{C-L}{C-1}\delta-\frac{\delta}{T(C-1)}\left( \left[\frac{C}{\pi_{1}},0,\ldots,0\right]-\left(\boldsymbol{\pi}^{-1}-\frac{1} {\overline{\pi}}\mathbf{1}_{C}\right)^{\top}\right)\mathbf{J}_{\boldsymbol{\pi }_{T}}\mathbf{1}_{1:L}$ $\displaystyle\displaystyle\geq\frac{C-L}{C-1}\delta-\frac{\delta C}{T(C-1)\pi_ {1}}\|\mathbf{J}_{\boldsymbol{\pi}_{T}}\|_{op}\|\mathbf{1}_{1:L}\|_{2}-\frac{ \delta}{T(C-1)}\|\mathbf{J}_{\boldsymbol{\pi}_{T}}\|_{op}\left\|\boldsymbol{ \pi}^{-1}-\frac{1}{\overline{\pi}}\mathbf{1}_{C}\right\|_{2}\|\mathbf{1}_{1:L} \|_{2}$ $\displaystyle\displaystyle\geq\frac{C-L}{C-1}\delta-\frac{\delta C\sqrt{L}}{T( C-1)\pi_{1}}-\frac{\delta\sqrt{L}}{T(C-1)}\left\|\left[\frac{1}{\pi_{1}}-\frac {1}{\overline{\pi}},\ldots,\frac{1}{\pi_{C}}-\frac{1}{\overline{\pi}}\right] \right\|_{2}$ $\displaystyle\displaystyle>0$ $$

where the third equality uses that fact that adding the subtracted vector would simply vanish: $\displaystyle\frac{1}{\overline{\pi}}\mathbf{1}_{C}^{\top}\mathbf{J}_{
\boldsymbol{\pi}_{T}}=\mathbf{0}^{\top}$,
the second inequality uses $\displaystyle\|\mathbf{J}_{\boldsymbol{\pi}_{T}}\|_{op}\leq 1$, as shown below, and the last inequality uses the advertised bound on $\displaystyle T$.

It is left to show that $\displaystyle\|\mathbf{J}_{\boldsymbol{\pi}_{T}}\|_{op}\leq 1$. This follows from the fact that for any $\displaystyle\mathbf{u}\in\mathbb{R}^{C}$ we have

$$ $\displaystyle\mathbf{u}^{\top}\mathbf{J}_{\boldsymbol{\pi}_{T}}\mathbf{u}=\sum _{i=1}^{C}\pi_{T,i}u_{i}^{2}-\left(\sum_{i=1}^{C}\pi_{T,i}u_{i}\right)^{2}\leq \sum_{i=1}^{C}\pi_{T,i}u_{i}^{2}\leq\mathrm{sup}_{i}\left(\pi_{T,i}\right)\sum _{i=1}^{C}u_{i}^{2}\leq\|\mathbf{u}\|_{2}^{2}.$ $$

Namely, the largest eigenvalue of $\displaystyle\mathbf{J}_{\boldsymbol{\pi}_{T}}$ cannot be larger than 1.

To conclude, since $\displaystyle\mathbf{r}^{\top}\nabla g(\boldsymbol{\pi};T,L)>0$, we have that for small enough step $\displaystyle\eta>0$:

$$ $\displaystyle g(\boldsymbol{\pi}+\eta\mathbf{r};T,L)>g(\boldsymbol{\pi};T,L).$ $$

∎

###### Proposition A.5 .

Consider $\displaystyle\hat{\boldsymbol{\pi}},\hat{\boldsymbol{\pi}}_{T}\in\Delta^{C-1}$, and $\displaystyle\hat{q},\hat{q}_{T}\in[0,1]$ such that $\displaystyle\hat{q}\geq\hat{q}_{T}$.
Let $\displaystyle L=\min\{l:\sum_{i=1}^{l}\hat{\pi}_{i}\geq\hat{q}\}$ , $\displaystyle L_{T}=\min\{l:\sum_{i=1}^{l}\hat{\pi}_{T,i}\geq\hat{q}_{T}\}$.
The following holds:

$$ $\displaystyle\forall M\in[L]:\quad\sum_{i=1}^{M}\hat{\pi}_{i}-\sum_{i=1}^{M} \hat{\pi}_{T,i}\geq\hat{q}-\hat{q}_{T}\Longrightarrow L\leq L_{T}.$ $$

###### Proof.

$\displaystyle\forall M\in[L]:\quad\sum_{i=1}^{M}\hat{\pi}_{i}-\sum_{i=1}^{M}
\hat{\pi}_{T,i}\geq\hat{q}-\hat{q}_{T}\iff\forall M\in[L]:\quad\sum_{i=1}^{M}
\hat{\pi}_{i}\geq\hat{q}-\hat{q}_{T}+\sum_{i=1}^{M}\hat{\pi}_{T,i}$

Note that for every $\displaystyle x\leq\hat{q}$ we have $\displaystyle M_{x}:=\min\{l:\sum_{i=1}^{l}\hat{\pi}_{i}\geq x\}\leq L$. For $\displaystyle M_{x}>1$ (i.e., not minimal possible value),
the event implies $\displaystyle\hat{q}-\hat{q}_{T}+\sum_{i=1}^{M_{x}-1}\hat{\pi}_{T,i}\leq\sum_{
i=1}^{M_{x}-1}\hat{\pi}_{i}<x$, This implies that $\displaystyle\min\{l:\hat{q}-\hat{q}_{T}+\sum_{i=1}^{l}\hat{\pi}_{T,i}\geq x\}$ cannot be smaller than $\displaystyle M_{x}$. That is,

$$ $\displaystyle\displaystyle\Longrightarrow\forall x\leq\hat{q}:\quad\min\{l: \sum_{i=1}^{l}\hat{\pi}_{i}\geq x\}\leq\min\{l:\hat{q}-\hat{q}_{T}+\sum_{i=1}^ {l}\hat{\pi}_{T,i}\geq x\}$ $$

Let us pick $\displaystyle x=\hat{q}$:

$$ $\displaystyle\displaystyle\min\{l:\sum_{i=1}^{l}\hat{\pi}_{i}\geq\hat{q}\}\leq \min\{l:\hat{q}-\hat{q}_{T}+\sum_{i=1}^{l}\hat{\pi}_{T,i}\geq\hat{q}\}$ $\displaystyle\displaystyle\iff\min\{l:\sum_{i=1}^{l}\hat{\pi}_{i}\geq\hat{q}\} \leq\min\{l:\sum_{i=1}^{l}\hat{\pi}_{T,i}\geq\hat{q}_{T}\}\iff L\leq L_{T}$ $$

∎

###### Proposition A.6 .

Let $\displaystyle\mathbf{z}\in\mathbb{R}^{C}$ and $\displaystyle\boldsymbol{\sigma}(\cdot)$ be the softmax function.
Consider Shannon’s entropy $\displaystyle H:\Delta^{C-1}\rightarrow\mathbb{R}$, i.e., $\displaystyle H(\boldsymbol{\pi})=-\sum_{i=1}^{C}\pi_{i}\ln(\pi_{i})$.
Unless $\displaystyle\mathbf{z}\propto\mathbf{1}_{C}$ (then $\displaystyle\boldsymbol{\sigma}(\mathbf{z}/T)=\boldsymbol{\sigma}(\mathbf{z})$),
we have that $\displaystyle H(\boldsymbol{\sigma}(\mathbf{z}/T))$ is strictly monotonically increasing as $\displaystyle T$ grows.

###### Proof.

To prove this statement, let us show that the function $\displaystyle f(T)=H(\boldsymbol{\sigma}(\mathbf{z}/T))$ monotonically increases (as $\displaystyle T$ increases, regardless of $\displaystyle\mathbf{z}$).
To achieve this, we need to show that $\displaystyle f^{\prime}(T)=\frac{d}{dT}H(\boldsymbol{\sigma}(\mathbf{z}/T))\geq
0$.

By the chain-rule, $\displaystyle f^{\prime}(T)=\frac{d}{dT}\left(H(\boldsymbol{\sigma}(\mathbf{z}
/T))\right)=\frac{\partial H(\boldsymbol{\sigma})}{\partial\boldsymbol{\sigma}
}\frac{\partial\boldsymbol{\sigma}(\mathbf{z})}{\partial\mathbf{z}}\frac{
\partial}{\partial T}(\mathbf{z}/T)$.
Let us compute each term:

$$ $\displaystyle\displaystyle\frac{\partial H(\boldsymbol{\sigma})}{\partial \sigma_{i}}$ $\displaystyle\displaystyle=-\ln(\sigma_{i})-\frac{1}{\sigma_{i}}\cdot\sigma_{i }=-\ln(\sigma_{i})-1\Longrightarrow\frac{\partial H(\boldsymbol{\sigma})}{ \partial\boldsymbol{\sigma}}=-\ln(\boldsymbol{\sigma})^{\top}-\mathbf{1}_{C}^{\top}$ $\displaystyle\displaystyle\frac{\partial\sigma_{i}(\mathbf{z})}{\partial z_{j}}$ $\displaystyle\displaystyle=\sigma_{i}(\mathbf{z})\cdot(\mathbb{I}\{i=j\}- \sigma_{j}(\mathbf{z}))\Longrightarrow\frac{\partial\boldsymbol{\sigma}( \mathbf{z})}{\partial\mathbf{z}}=\mathrm{diag}(\boldsymbol{\sigma}(\mathbf{z}) )-\boldsymbol{\sigma}(\mathbf{z})\boldsymbol{\sigma}(\mathbf{z})^{\top}$ $\displaystyle\displaystyle\frac{\partial}{\partial T}(\mathbf{z}/T)$ $\displaystyle\displaystyle=-\frac{1}{T^{2}}\mathbf{z}$ $$

where in $\displaystyle\ln(\boldsymbol{\sigma})$ the function operates entry-wise and $\displaystyle\mathbb{I}\{i=j\}$ is the indicator function (equals $\displaystyle 1$ if $\displaystyle i=j$ and $\displaystyle 0$ otherwise).

Next, observe that $\displaystyle\mathbf{1}_{C}^{\top}\left(\mathrm{diag}(\boldsymbol{\sigma})-
\boldsymbol{\sigma}\boldsymbol{\sigma}^{\top}\right)=\boldsymbol{\sigma}^{\top
}-\boldsymbol{\sigma}^{\top}=\mathbf{0}^{\top}$.
Consequently, we get

$$ $\displaystyle\displaystyle\frac{d}{dT}\left(H(\boldsymbol{\sigma}(\mathbf{z}/T ))\right)$ $\displaystyle\displaystyle=\frac{1}{T^{2}}\ln(\boldsymbol{\sigma}(\mathbf{z})) ^{\top}(\mathrm{diag}(\boldsymbol{\sigma}(\mathbf{z}))-\boldsymbol{\sigma}( \mathbf{z})\boldsymbol{\sigma}(\mathbf{z})^{\top})\mathbf{z}$ $\displaystyle\displaystyle=\frac{1}{T^{2}}\left(\mathbf{z}-s(\mathbf{z}) \mathbf{1}_{C}\right)^{\top}(\mathrm{diag}(\boldsymbol{\sigma}(\mathbf{z}))- \boldsymbol{\sigma}(\mathbf{z})\boldsymbol{\sigma}(\mathbf{z})^{\top})\mathbf{z}$ $\displaystyle\displaystyle=\frac{1}{T^{2}}\mathbf{z}^{\top}(\mathrm{diag}( \boldsymbol{\sigma}(\mathbf{z}))-\boldsymbol{\sigma}(\mathbf{z})\boldsymbol{ \sigma}(\mathbf{z})^{\top})\mathbf{z}$ $$

where in the second equality we used $\displaystyle[\ln(\boldsymbol{\sigma}(\mathbf{z}))]_{i}=\ln\left(\frac{\exp(z_
{i})}{\sum_{j=1}^{C}\exp(z_{j})}\right)=z_{i}-s(\mathbf{z})$, where $\displaystyle s(\mathbf{z})=\ln\left(\sum_{j=1}^{C}\exp(z_{j})\right)$.

Therefore, for establishing that $\displaystyle\frac{d}{dT}\left(H(\boldsymbol{\sigma}(\mathbf{z}/T))\right)\geq
0$, we can show that $\displaystyle(\mathrm{diag}(\boldsymbol{\sigma})-\boldsymbol{\sigma}
\boldsymbol{\sigma}^{\top})$ is a positive semi-definite matrix.
Let $\displaystyle\tilde{\sigma}_{i}=\exp(z_{i})$ and notice that $\displaystyle\sigma_{i}=\frac{\tilde{\sigma}_{i}}{\sum_{j=1}^{C}\tilde{\sigma}
_{j}}$.
Indeed, for any $\displaystyle\mathbf{u}\in\mathbb{R}^{C}\setminus\{\mathbf{0}\}$ we have that

$$ $\displaystyle\displaystyle\mathbf{u}^{\top}(\mathrm{diag}(\boldsymbol{\sigma}) -\boldsymbol{\sigma}\boldsymbol{\sigma}^{\top})\mathbf{u}$ $\displaystyle\displaystyle=\sum_{i=1}^{C}u_{i}^{2}\sigma_{i}-\left(\sum_{i=1}^ {C}u_{i}\sigma_{i}\right)^{2}$ $\displaystyle\displaystyle=\frac{\sum_{i=1}^{C}u_{i}^{2}\tilde{\sigma}_{i} \cdot\sum_{j=1}^{C}\tilde{\sigma}_{j}-\left(\sum_{i=1}^{C}u_{i}\tilde{\sigma}_ {i}\right)^{2}}{\left(\sum_{j=1}^{C}\tilde{\sigma}_{j}\right)^{2}}$ $\displaystyle\displaystyle\geq 0,$ $$

where the inequality follows from Cauchy–Schwarz inequality:
$\displaystyle\sum_{i=1}^{C}u_{i}\tilde{\sigma}_{i}=\sum_{i=1}^{C}u_{i}\sqrt{
\tilde{\sigma}_{i}}\sqrt{\tilde{\sigma}_{i}}\leq\sqrt{\sum_{i=1}^{C}u_{i}^{2}
\tilde{\sigma}_{i}}\sqrt{\sum_{j=1}^{C}\tilde{\sigma}_{j}}$.

Cauchy–Schwarz inequality is attained with equality iff $\displaystyle u_{i}\sqrt{\tilde{\sigma}_{i}}=c\sqrt{\tilde{\sigma}_{i}}$ with the same constant $\displaystyle c$ for $\displaystyle i=1,\ldots,C$, i.e., when $\displaystyle\mathbf{u}=c\mathbf{1}_{C}$.
Recalling that
$\displaystyle\frac{d}{dT}\left(H(\boldsymbol{\sigma}(\mathbf{z}/T))\right)=
\frac{1}{T^{2}}\mathbf{z}^{\top}(\mathrm{diag}(\boldsymbol{\sigma})-
\boldsymbol{\sigma}\boldsymbol{\sigma}^{\top})\mathbf{z}$, this implies that $\displaystyle\frac{d}{dT}\left(H(\boldsymbol{\sigma}(\mathbf{z}/T))\right)=0
\iff z_{1}=\ldots=z_{C}$, and otherwise $\displaystyle\frac{d}{dT}\left(H(\boldsymbol{\sigma}(\mathbf{z}/T))\right)>0$.

∎

###### Proposition A.1 .

###### Proof.

###### Theorem A.2 .

###### Proof.

###### Theorem .

###### Lemma .

###### Proof.

###### Corollary A.3 .

###### Proof.

###### Theorem A.4 .

###### Proof.

###### Proposition A.5 .

###### Proof.

###### Proposition A.6 .

###### Proof.

## Appendix B Additional Experimental Details and Results

### B.1 Training details

For ImageNet models, we utilized pretrained models from the TORCHVISION.MODELS sub-package. For full training details, please refer to the following link:

[https://github.com/pytorch/vision/tree/8317295c1d272e0ba7b2ce31e3fd2c048235fc73/references/classification](https://github.com/pytorch/vision/tree/8317295c1d272e0ba7b2ce31e3fd2c048235fc73/references/classification)

For CIFAR-100 and CIFAR-10 models, we use:
Batch size: 128; Epochs: 300; Cross-Entropy loss; Optimizer: SGD; Learning rate: 0.1; Momentum: 0.9; Weight decay: 0.0005.

### B.2 Experiments compute resources

We conducted our experiments using an NVIDIA GeForce GTX 1080 Ti. Given the trained models, each experiment runtime is within a range of minutes.

### B.3 Temperature scaling calibration

As mentioned in Section 2.1, two popular calibration objectives are the Negative Log-Likelihood (NLL) [] and the Expected Calibration Error (ECE) [].

NLL, given by $\displaystyle\mathcal{L}=-\sum\nolimits_{i=1}^{n}\ln(\tilde{\pi}_{y_{i}}(
\mathbf{x}_{i}))$, measures the cross-entropy between the true conditional distribution of data (one-hot vector associated with $\displaystyle y_{i}$)
and $\displaystyle\tilde{\boldsymbol{\pi}}(\mathbf{x}_{i})$.

ECE aims to approximate $\displaystyle\mathbb{E}\left[\left|\mathbb{P}\left(\hat{y}(X)=Y|\tilde{\pi}_{
\hat{y}(X)}(X)=p\right)-p\right|\right]$.
Specifically, the confidence range $\displaystyle[0,1]$ is divided into $\displaystyle L$ equally sized bins $\displaystyle\{B_{l}\}$. Each sample $\displaystyle(\mathbf{x}_{i},y_{i})$ is assigned to a bin $\displaystyle B_{l}$ according to $\displaystyle\tilde{\pi}_{y_{i}}(\mathbf{x}_{i})$.
The objective is given by
$\displaystyle\text{ECE}=\sum\nolimits_{l=1}^{L}\frac{|B_{l}|}{n}\left|\mathrm{
acc}(B_{l})-\mathrm{conf}(B_{l})\right|$,
where $\displaystyle\mathrm{acc}(B_{l})=\frac{1}{|B_{l}|}\sum\nolimits_{i\in B_{l}}
\mathbbm{1}\{\hat{y}(\mathbf{x}_{i})=y_{i}\}$ and $\displaystyle\mathrm{conf}(B_{l})=\frac{1}{|B_{l}|}\sum\nolimits_{i\in B_{l}}
\hat{\pi}_{y_{i}}(\mathbf{x}_{i})$.
Here, $\displaystyle\mathbbm{1}(\cdot)$ denotes the indicator function.

#### B.3.1 ECE vs NLL minimization

Above, we defined the two common minimization objectives for the TS calibration procedure. Throughout the paper, we employed the ECE objective. Here, we justify this choice by demonstrating the proximity of the optimal calibration temperature $\displaystyle T^{*}$ for both objectives.

**Table 3: Optimal Temperature for NLL and ECE objectives**
| Dataset-Model | $\displaystyle T^{*}$ - NLL loss | $\displaystyle T^{*}$ - ECE loss |
| --- | --- | --- |
| CIFAR-100, ResNet50 | 1.438 | 1.524 |
| CIFAR-100, DenseNet121 | 1.380 | 1.469 |
| ImageNet, ResNet152 | 1.207 | 1.227 |
| ImageNet, DenseNet121 | 1.054 | 1.024 |
| CIFAR-10, ResNet50 | 1.683 | 1.761 |
| CIFAR-10, ResNet34 | 1.715 | 1.802 |

Using both objectives, we obtain similar optimal calibration temperatures $\displaystyle T^{*}$, resulting in minor changes to the values in Tables  2 and  2, presented in Section 3.2. Furthermore, in Section 3.3, we examine the effect of TS over a range of temperatures, which naturally includes both optimal temperatures.

### B.4 Metrics definitions

In section 3.1, we use metrics to represent average prediction set size, marginal coverage and conditional coverage. Here, we present the formulas for these metrics. Note that similar metrics have been used in [, ].

We report metrics over the validation set which we denote by $\displaystyle\{(X_{i}^{(val)},Y_{i}^{(val)})\}_{i=1}^{N^{(val)}}$, comprising of the
samples that were not included in the calibration set or CP set. The metrics are as follows.

- •
Average set size (AvgSize) – The mean prediction set size of the CP algorithm:
$\text{AvgSize}=\frac{1}{N^{(val)}}\sum_{i=1}^{N^{(val)}}|C(X_{i}^{(val)})|.$
- •
Marginal coverage gap (MarCovGAP) – The deviation of the marginal coverage from the desired $\displaystyle 1-\alpha$:
$\text{MarCovGap}=\left|\frac{1}{N^{(val)}}\sum_{i=1}^{N^{(val)}}\mathbbm{1}\{Y
_{i}^{(val)}\in C(X_{i}^{(val)})\}-(1-\alpha)\right|.$
- •
Top-5% class-coverage gap (TopCovGap) – The deviation from the desired $\displaystyle 1-\alpha$ coverage, averaged over the 5% of classes with the highest deviation:
$\text{TopCovGap}=\mathrm{Top5}_{y\in[C]}\left|\frac{1}{|I_{y}|}\sum_{i\in I_{y
}}\mathbbm{1}\left\{Y_{i}^{(val)}\in C\left(X_{i}^{(val)}\right)\right\}-(1-
\alpha)\right|,$
where $\displaystyle\mathrm{Top5}$ is an operator that returns the mean of the 5% highest elements in the set and $\displaystyle I_{y}=\{i\in[N^{(val)}]:Y_{i}^{(val)}=y$} is the indices of validation examples with label $\displaystyle y$. We use top-5% classes deviation due to the high variance in the maximal class deviation. For example, in CIFAR-100, the average is computed over the $\displaystyle 5$ classes with the highest deviation from $\displaystyle 1-\alpha$ coverage. Thus, TopCovGap is a class-conditional coverage metric.

#### B.4.1 Additional reliability diagrams

Below, we present reliability diagrams for additional dataset-model pairs. We divided the confidence range into 10 bins and displayed the accuracy for each bin as a histogram. The red bars represent the calibration error for each bin.

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/ICML24/Plots/Reliability_diagrams_updated/imagenet_resnet152_B.png

Figure: ImageNet, DenseNet121
Refer to caption: extracted/5706552/ICML24/Plots/Reliability_diagrams_updated/imagenet_densenet121_B.png

### B.5 The effect of TS calibration on CP methods

As an extension of Section  3.2, we provide additional experiments where we examine the effect of TS calibration on CP methods with different settings of hyper-parameters ($\displaystyle\alpha$ and CP set size). The tables below present prediction set sizes and coverage metrics before and after TS calibration for different CP set sizes and an additional CP coverage probability value.

**Table 4: Prediction Set Size. AvgSize metric along with $\displaystyle T^{*}$ and accuracy for dataset-model pairs using LAC, APS, and RAPS algorithms with $\displaystyle\alpha=0.1$, CP set size $\displaystyle 5\%$, pre- and post-TS calibration.**
|  |  | Accuracy(%) | AvgSize | AvgSize after TS |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset-Model | $\displaystyle T^{*}$ | Top-1 | Top-5 | LAC | APS | RAPS | LAC | APS | RAPS |
| ImageNet, ResNet152 | 1.227 | 78.3 | 94.0 | 1.94 | 7.24 | 3.20 | 1.95 | 10.3 | 4.35 |
| ImageNet, DenseNet121 | 1.024 | 74.4 | 91.9 | 2.70 | 10.1 | 4.71 | 2.77 | 11.2 | 4.91 |
| CIFAR-100, ResNet50 | 1.524 | 80.9 | 95.4 | 1.62 | 5.75 | 2.78 | 1.57 | 9.76 | 4.93 |
| CIFAR-100, DenseNet121 | 1.469 | 76.1 | 93.5 | 2.10 | 4.30 | 2.99 | 2.08 | 6.61 | 4.38 |
| CIFAR-10, ResNet50 | 1.761 | 94.6 | 99.7 | 0.92 | 1.05 | 0.95 | 0.91 | 1.13 | 1.01 |
| CIFAR-10, ResNet34 | 1.802 | 95.3 | 99.8 | 0.91 | 1.03 | 0.94 | 0.93 | 1.11 | 1.05 |

**Table 5: Prediction Set Size. AvgSize metric along with $\displaystyle T^{*}$ and accuracy for dataset-model pairs using LAC, APS, and RAPS algorithms with $\displaystyle\alpha=0.1$, CP set size $\displaystyle 20\%$, pre- and post-TS calibration.**
|  |  | Accuracy(%) | AvgSize | AvgSize after TS |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset-Model | $\displaystyle T^{*}$ | Top-1 | Top-5 | LAC | APS | RAPS | LAC | APS | RAPS |
| ImageNet, ResNet152 | 1.227 | 78.3 | 94.0 | 1.95 | 7.34 | 3.30 | 1.92 | 12.5 | 4.40 |
| ImageNet, DenseNet121 | 1.024 | 74.4 | 91.9 | 2.73 | 13.1 | 4.70 | 2.76 | 13.3 | 4.88 |
| CIFAR-100, ResNet50 | 1.524 | 80.9 | 95.4 | 1.62 | 5.35 | 2.68 | 1.57 | 9.34 | 4.96 |
| CIFAR-100, DenseNet121 | 1.469 | 76.1 | 93.5 | 2.13 | 4.36 | 2.95 | 2.06 | 6.81 | 4.37 |
| CIFAR-10, ResNet50 | 1.761 | 94.6 | 99.7 | 0.91 | 1.04 | 0.98 | 0.91 | 1.13 | 1.05 |
| CIFAR-10, ResNet34 | 1.802 | 95.3 | 99.8 | 0.91 | 1.03 | 0.94 | 0.93 | 1.11 | 1.05 |

**Table 6: Coverage Metrics. MarCovGap and TopCovGap metrics for dataset-model pairs using LAC, APS, and RAPS algorithms with $\displaystyle\alpha=0.1$, CP set size $\displaystyle 5\%$, pre- and post-TS calibration.**
|  | MarCovGap(%) | MarCovGap TS(%) | TopCovGap(%) | TopCovGap TS(%) |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset-Model | LAC | APS | RAPS | LAC | APS | RAPS | LAC | APS | RAPS | LAC | APS | RAPS |
| ImageNet, ResNet152 | 0 | 0 | 0 | 0 | 0.1 | 0 | 23.5 | 15.7 | 16.9 | 24.1 | 13.6 | 15.0 |
| ImageNet, DenseNet121 | 0 | 0.1 | 0 | 0 | 0 | 0.1 | 24.9 | 15.7 | 18 | 25.2 | 14.9 | 17.6 |
| CIFAR-100, ResNet50 | 0.1 | 0 | 0.1 | 0 | 0.1 | 0 | 13.9 | 11.9 | 10.7 | 12.5 | 8.2 | 7.5 |
| CIFAR-100, DenseNet121 | 0 | 0 | 0.1 | 0 | 0 | 0.1 | 11.6 | 9.5 | 9.0 | 11.7 | 7.8 | 7.7 |
| CIFAR-10, ResNet50 | 0 | 0 | 0 | 0 | 0.1 | 0 | 11.1 | 5.0 | 4.8 | 11.2 | 2.4 | 2.6 |
| CIFAR-10, ResNet34 | 0 | 0.1 | 0.1 | 0 | 0 | 0 | 9.5 | 3.0 | 2.8 | 9.1 | 2.2 | 2.2 |

We can see from the above tables that the results for different CP sizes are very similar. The goal of the CP set is to be large enough to represent the rest of the data from the same distribution. In our experiments, we see that even 5% of the validation set is sufficient for this purpose.

**Table 8: Prediction Set Size. AvgSize metric along with $\displaystyle T^{*}$ and accuracy for dataset-model pairs using LAC, APS, and RAPS algorithms with $\displaystyle\alpha=0.05$, CP set size $\displaystyle 10\%$, pre- and post-TS calibration.**
|  |  | Accuracy(%) | AvgSize | AvgSize after TS |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset-Model | $\displaystyle T^{*}$ | Top-1 | Top-5 | LAC | APS | RAPS | LAC | APS | RAPS |
| ImageNet, ResNet152 | 1.227 | 78.3 | 94.0 | 3.28 | 14.9 | 4.10 | 3.22 | 24.1 | 5.1 |
| ImageNet, DenseNet121 | 1.024 | 74.4 | 91.9 | 3.33 | 20.1 | 5.02 | 3.61 | 22.8 | 5.88 |
| CIFAR-100, ResNet50 | 1.524 | 80.9 | 95.4 | 3.97 | 11.1 | 3.98 | 2.21 | 16.2 | 6.8 |
| CIFAR-100, DenseNet121 | 1.469 | 76.1 | 93.5 | 4.89 | 8.81 | 5.01 | 4.23 | 12.16 | 6.1 |
| CIFAR-10, ResNet50 | 1.761 | 94.6 | 99.7 | 1.02 | 1.08 | 1.08 | 1.02 | 1.21 | 1.21 |
| CIFAR-10, ResNet34 | 1.802 | 95.3 | 99.8 | 1.01 | 1.06 | 1.19 | 1.01 | 1.06 | 1.19 |

The increased coverage probability is reflected in both prediction set sizes and the conditional coverage metric. We observe an increase in prediction set sizes compared to Table  2, which is expected due to the stricter coverage probability requirement. Note that the tendency for prediction set sizes to increase with $\displaystyle T$ remains. Regarding the coverage metric TopCovGap, we see an improvement (lower values), which can be explained by the increase in prediction set sizes. Here, the tendency for the metrics to improve as $\displaystyle T$ increases also remains.

In addition to the tables, in section  3.2, we microscopically investigated the effect of TS calibration on PS sizes. Figure 2 represents the sorted differences in prediction set sizes for each sample in the validation set for CIFAR100-ResNet50. Here, in Figure 8, we provide similar figures for additional dataset-model pairs.

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/ICML24/Plots/Sorted_differences_updated/aps_imagenet_resnet152.png

### B.6 TS beyond calibration

As an extension of section  3.3, we provide additional experiments with different settings to examine the effect of TS beyond calibration on CP methods. The figures below present prediction set sizes and conditional coverage metrics for a range of temperatures for additional dataset-model pairs, different CP set sizes and an additional CP coverage probability value. Overall, the temperature $\displaystyle T$ allows to trade off between AvgSize and TopCovGap, as discussed in the paper.

#### B.6.1 Prediction set size

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/MEAN_SET_SIZE/NO_STD/CP_SET_SIZE/REGULAR/imagenet_resnet152.png

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/MEAN_SET_SIZE/NO_STD/CP_SET_SIZE/5_per/imagenet_resnet152.png

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/MEAN_SET_SIZE/NO_STD/ALPHA=0.05/imagenet_resnet152.png

#### B.6.2 TopCovGap metric

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/CONDITIONAL_COVERAGE/MAX_SSCV_CLASSES/NO_STD/REGULAR/imagenet_resnet152.png

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/CONDITIONAL_COVERAGE/MAX_SSCV_CLASSES/NO_STD/ALPHA=0.05/imagenet_resnet152.png

#### B.6.3 CP threshold value q ^ ^ 𝑞 \displaystyle\hat{q} over^ start_ARG italic_q end_ARG

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/QHAT/NO_STD/REGULAR/imagenet_resnet152.png

Figure: ImageNet, ResNet152
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/QHAT/NO_STD/ALPHA=0.05/imagenet_resnet152.png

#### B.6.4 The impact of TS at extremely low temperatures

Figure: Figure 16: Prediction Set Size. Mean prediction set size for LAC, APS and RAPS versus low temperatures, for CIFAR100-DenseNet121.
Refer to caption: extracted/5706552/UPDATED_PAPER_AFTER_REBATTLE/GRAPHS/MEAN_SET_SIZE/NO_STD/LOW_T_EXPLOTION/cifar100_densenet121.png

In our experiments presented in Section 3, we lower bound the temperature range at $\displaystyle T=0.3$. This choice was motivated by the deviation from the desired marginal coverage guarantee observed at extremely small temperatures. Specifically, we observe that for too small $\displaystyle T$ the threshold value reaches maximal value, $\displaystyle\hat{q}\rightarrow 1$, and, presumably due to numerical errors,
this leads to an impractical CP procedure, with significant over-coverage and excessively large prediction set sizes, as demonstrated in
Figure  16 for CIFAR100-DenseNet121, $\displaystyle\alpha=0.1$ and CP set size $\displaystyle 10\%$.

## Appendix C Modeling 𝐪 ^ ⁢ ( T ) ^ 𝐪 𝑇 \displaystyle\hat{\mathbf{q}}(T) over^ start_ARG bold_q end_ARG ( italic_T ) and Approximating the Trade-off via the Calibration Set

Figure: Figure 17: Interpolation illustration. Interpolated threshold value $\displaystyle\hat{q}(T)$ of RAPS as function of temperature, for ResNet152 on ImageNet, with $\displaystyle\alpha=0.1$ and 1 trial of CP set size 10% of the validation set. The red dots represent the anchor points used for interpolation.
Refer to caption: extracted/5706552/NeurIPS24/UPDATES/INTERPOLATION/imagenet_resnet152/illu.png

As discussed in Section 3.3, it is beneficial to explore the trade-off between the prediction set size and the class-conditional coverage via the temperature, $\displaystyle\hat{T}$ when using adaptive CP algorithms. Rather than calibrating APS/RAPS for a dense range of $\displaystyle T$ in order to obtain the associated threshold $\displaystyle\hat{q}$ per $\displaystyle T$, we examine a simple method to reduce computational complexity and potentially modifying $\displaystyle\hat{T}$ online. Our approach leverages the simplicity of the graph depicting the threshold value as a function of temperatures, $\displaystyle\hat{q}=\hat{q}(T)$, as presented in Figure 3.

We propose to select only a small number of anchor temperatures, $\displaystyle\{T_{i}\}$, apply APS/RAPS on them to obtain the thresholds $\displaystyle\{\hat{q}_{i}\}$ and then
employing interpolation to approximate $\displaystyle\hat{q}_{approx}(T)\approx\hat{q}(T)$. This allows users to deploy these CP methods on test samples with their desired temperature using the approximated threshold value without the need to calibrate the CP method on that temperature. We present illustration for this procedure in Figure  17. Note that unlike the curves of the threshold $\displaystyle\hat{q}$ in Figure  3, which are averaged over 100 trials, in practice, the user only has the CP set of a single trial.
Thus, in Figure  17 we present the interpolation procedure
in 1 trial (we still use CP set of size 10% of the validation data). This curve, as well as those of other trials, is similar to the one in Figure  3.

Figure: MarCovGap
Refer to caption: extracted/5706552/NeurIPS24/UPDATES/INTERPOLATION/imagenet_resnet152/trial1/marcovgap.png

Regarding the implementation of the interpolation, we observed that
a low-degree polynomial is sufficient for approximating $\displaystyle\hat{q}(T)$. In the experiment below, we show that a good approximation of $\displaystyle\hat{q}(T)$, satisfying marginal coverage for the entire range of temperatures can be achieved using only 6 anchor points and a polynomial of degree 5. It is important to note that a critical estimation area is at low temperatures, where $\displaystyle\hat{q}\rightarrow 1$, as even slight deviations can lead to significantly different prediction sets which cause the marginal coverage violation. Therefore, it is beneficial to use more anchor points at low temperatures.
In our illustration we chose the following temperatures as anchor points $\displaystyle[0.3,0.4,0.6,1.1,1.5,1.8]$.

As mentioned in the paper, we propose to evaluate the effect of $\displaystyle T$ on the trade-off between the prediction set size and the conditional coverage of adaptive CP (and set $\displaystyle\hat{T}$ accordingly) using the calibration set belonging to the parallel branch in Figure 4, which is independent of computing/modeling the CP threshold.
We examine this approach on RAPS for the ImageNet dataset and ResNet152 model.
Per trial we use a CP set of size 10% of the validation set to compute $\displaystyle\hat{q}(T)$ or $\displaystyle\hat{q}_{\text{approx}}(T)$ and 10% of the validation set to evaluate the resulting RAPS.
Therefore, overall, only 20% of the validation set are used for the procedure — exactly as used in the common practice of performing TS calibration and CP calibration sequentially rather than in parallel.

In Figures 18 we present the marginal coverage gap (MarCovGap) in percentage scale, mean prediction set size (AvgSize) and the class-conditional coverage gap (TopCovGap) for both plain RAPS and “interpolated RAPS" (RAPS with $\displaystyle\hat{q}_{\text{approx}}(T)$) with $\displaystyle\alpha=0.1$ in three runs (3 trials).
In each of the runs, the marginal coverage is preserved and the curves of AvgSize and TopCovGap closely resemble the averaged ones shown in Figure 3, demonstrating the user’s ability to select $\displaystyle\hat{T}$ based on these single-trial graphs generated using 10% of the validation data. Additionally, the negligible gap between the curves associated with $\displaystyle\hat{q}(T)$ and $\displaystyle\hat{q}_{\text{approx}}(T)$ indicates that the interpolation quality is sufficient.

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 8
presentation: 4
questions: I have not much to ask or say. The paper was clear!
A typo/English language check would improve it before the next round.
soundness: 4
strengths: The paper is strong and I recommend acceptance.

I was impressed and surprised by the insights in this paper. Temperature scaling has a huge effect, the experiments bear this out, and the theory provides some explanation as to why, and might be useful to others in the field. (Specifically, the theory about how set size is affected by temperature is fairly general-purpose.)

* The empirical experiments are painstakingly detailed and very scientific.
* The theory is useful and correct.
summary: The paper provides a very detailed theoretical and empirical study of the effect of temperature scaling on prediction set sizes and conditional coverage in conformal prediction. It finds that temperature scaling can (sometimes drastically) increase set sizes for common classification tasks. It explains this phenomenon theoretically and provides guidelines to practitioners about how to set the parameter moving forward.
weaknesses: * The theorems are somewhat weak, and of limited practical value in terms of being applied directly. They seem to be useful mostly for the purpose of post-hoc explanation of why this phenomenon happens.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. While Theorem 4.4 provides valuable theoretical insights, it is hard to understand how to use the theoretical results for estimating $T_{critical}$. I would greatly appreciate it if the authors could provide an explicit expression for computing $\hat{T}_{critical}$.
soundness: 2
strengths: 1. The work is well-writing. Basically, the paper is written in a good manner and I believe readers can easily touch the core idea.  

2. This paper provides a theoretical analysis to show how temperature values influence the properties of prediction sets. With the theoretical results, researchers can understand why temperature scaling can affect the conformal prediction.

3. The authors provide empirical validation of their theoretical framework.
summary: In this paper, the authors investigate the interplay between conformal prediction and calibration. Firstly, the paper empirically shows that while temperature scaling improves the class-conditional coverage of adaptive CP methods. Then, the authors establish a mathematical theory that explains this phenomenon. Finally, the paper offers a guideline to effectively combine adaptive CP with calibration.
weaknesses: 1. The paper presents an inconsistency in its mathematical derivations. In Eq. (3), the analysis is mainly based on the relationship between $\sum_{i=1}^M\pi_i-\sum_{i=1}^M\pi_{T,i}\quad\text{and}\quad{q}-q_T$ (omit \hat for \pi and q due to the tex support),
which represents the difference of accumulated probability and threshold value before and after applying a temperature. Later, in Eq. (5), the problem above is translated to investigate the relationship between 
$$\sum_{i=1}^M\exp(z_i)-\sum_{i=1}^M\exp(z_i/T)\quad\text{and}\quad\sum_{i=1}^M\exp(z_i^q)-\sum_{i=1}^M\exp(z_i^q/T).$$However, based on the definition on $z^q$, we know that if $M$ is not the true label of $z^q$, then $\sum_{i=1}^M\exp(z_i^q/T)\neq\hat{q}_T$. Therefore, it's unclear how the problem in Eq. (3) can be equivalent to the analysis in Eq. (5). 

2. The assumptions in Theorem 4.4 appear to be unreasonable. Theorem 4.4 in the paper states that if $\Delta z>b(T)$, then rising $z_1$ leads to an increase in the set size. However, the assumption that '$\Delta z$ is preserved as $z_1$ increases' (line 458) is not natural for me because counterexamples exist where $\Delta z$ increases as $z_1$ increases. Furthermore, even if we accept the condition that $\Delta z$ remains constant, the paper's claim that '$z^q$ has a larger dominant entry than typical $z$' lacks proper justification.

3. The theoretical bounds and empirical results show inconsistency. The paper reports an empirical critical temperature of $T^{*}=1.524$. However, this value falls between the theoretical temperature ranges $(0,0.813)$ and $(1.25,4.81)$, suggesting a gap between theory and practice. This inconsistency challenges the paper's claim that 'the bounds in Theorem 4.4 do not require unreasonable values of $\Delta z$ and T' (line 463). Moreover, it indicates that using the median of $\Delta z$ to estimate $T_{critical}$ may not be a reliable approach.
    
4. The proposed approach of using $T_{critical}$ to enhance conditional coverage (as proposed in Section 5) has limitations. As discussed in Weaknesses[3], the theorem may fail to provide accurate estimation of $T_{critical}$. Even though an accurate estimation can be achieved, simply applying $T_{critical}$ falls short of achieving group-wise coverage that Mondrian conformal prediction provides. Furthermore, the paper does not present empirical evidence demonstrating how their proposed guideline enhances conformal prediction performance. Overall, these limitations restrict the practical applicability of the theoretical results.


**Minor Comments:**
1. The paper's analysis is limited to Temperature Scaling, while leaving out other important calibration methods such as histogram binning.
2. The mathematical proofs lack clarity. For example, in proof of Theorem 4.1, the first equation (line 750-755) is stated without proper mathematical justification.
3. typo in Section 5: "guidelinse" should be "guidelines".

I would be open to reconsidering my recommendation if these issues could be addressed in the rebuttal.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See above.
soundness: 3
strengths: 1. The paper focuses on an interesting question: the influence of temperature scaling on conformal prediction outcomes, concerning group coverage and band length.
2. Empirical evidence is provided to suggest that TS can detrimentally harm the set size of conformal prediction measures such as APS and RAPS, while simultaneously improving group coverage.
3. The authors demonstrate that TS facilitates a trade-off between set size and group coverage.
4. Theoretical insights into the empirical findings are offered, along with practical guidelines for practitioners.
summary: This paper delves into the impact of Temperature Scaling (TS) on conformal prediction methods. 
Traditionally, researchers have applied TS before conducting conformal prediction on the resulting classifiers. 
The paper argues that while it enhances group coverage, it negatively affects set size. 
I find this paper offers valuable experiments and intriguing insights into the interplay between conformal prediction and temperature scaling, and I recommend an acceptance. My hesitation to give a higher score stems from (a) the paper's inherently limited scope to classification tasks, as regression tasks do not typically encounter this issue; (b) it is somehow intuitive that TS might not be the best choice for the set size, which is not particularly surprising.
weaknesses: have few major concerns with this paper. As previously mentioned, my decision not to assign a higher score is based on:
1. The limited scope of the paper to classification tasks, as regression tasks do not typically present this issue.
2. The somewhat expected nature of the finding that TS might impact set size negatively.

Meta-review: The paper investigates the impact of Temperature Scaling (TS) on Conformal Prediction (CP) methods for deep neural network classifiers. Its key scientific claims and findings include:
TS, typically used for softmax calibration, influences CP methods beyond its calibration role. Specifically, it improves class-conditional coverage for adaptive CP methods like APS and RAPS but can negatively impact prediction set sizes.
The effect of TS on CP exhibits a non-monotonic trend. By tuning the temperature parameter, practitioners can trade off smaller prediction sets against better class-conditional coverage.

The authors provide a theoretical framework explaining the non-monotonic behavior of CP methods under TS. They derive critical temperatures where the trade-off flips and use mathematical bounds to quantify the phenomenon.
The paper offers actionable insights for practitioners.
Extensive empirical results on benchmark datasets (CIFAR-100, ImageNet) show that TS can yield a great reductions in prediction set sizes while maintaining valid coverage (this is quite normal because the coverage is automatic as long as excheangeability is maintained. 


The decision to weakly reject the paper is based on the perception that the core discussion revolves around how Temperature Scaling (TS) serves as a regularization parameter, affecting classifier accuracy, which in turn influences the efficiency (size of prediction sets) in conformal prediction. While TS is recognized as a calibration method, its impact on prediction set sizes essentially reflects its effect on the underlying model’s accuracy. Since conformal prediction inherently maintains marginal coverage regardless of TS, the work is seen as focusing on a fairly indirect and expected outcome of TS. Consequently, the contributions are perceived as incremental, and the paper could benefit from a deeper engagement with and contextualization within the broader literature. Addressing this gap would clarify its novelty and relevance.

Decision: Reject