On Temperature Scaling and Conformal Prediction of Deep Classifiers

Thank you for your insightful review. We appreciate your recognition of our extensive empirical study and clear experimental design.

Below, we address your comments on the theoretical analysis point by point.

Theory for conditional coverage.

Our work develops a comprehensive mathematical framework to explain the non-intuitive effects of TS on prediction set sizes in CP. We rigorously formulate conditions for changes in prediction set size and clarify the underlying theoretical reasons for these effects. While extending this analysis to conditional coverage is valuable, it would require an entirely new theoretical framework with different assumptions and tools, making it beyond the scope of this study. Nonetheless, establishing theory for the impact of TS on conditional coverage is indeed a promising direction for future research.

Regarding Proposition 4.3.

Let us clarify the scope of our theoretical analysis and particularly the contribution of Proposition 4.3. This proposition focuses on how TS affects prediction set size of APS. It provides a condition, dependent on the value of $T$, for a decrease or an increase in the prediction set size after applying TS, denoted by $L_T$, compared to the size without applying TS (equivalently, TS with $T=1$), denoted by $L$. It is important to note that this result covers all positive values $T > 0$.

We would like to clarify that this is not the primary finding of our work. Theorem 4.4, along with its implications, specifically addresses this "kink point" of the non-monotone dependency. Theorem 4.4 shows that applying TS with temperature $T$ affects the prediction set size of a sample $z$ based on $\Delta z = z_{(1)} - z_{(2)}$ and a bound $b(T)$. For example, for $T > 1$, if $\Delta z > b_{T>1}(T)$, the prediction set size increases ($L_T \geq L$). Figure 3 reveals a non-monotonic curve for $b(T)$ at $T>1$, and since lower (resp. higher) $b(T)$ implies that more (resp. less) samples obey the condition this provides an explanation to the non-monotonic pattern of the mean prediction set size (AvgSize): it increases for $1 < T < \tilde{T}_c$ and decreases for $T > \tilde{T}_c$ where $\tilde{T}_c$ is the temperature above 1 where $b(T)$ is minimal. This critical temperature $\tilde{T}_c$ decreases with $C$, aligning with empirical results.

We are grateful for your constructive and thorough review of our theoretical work. We appreciate your acknowledgment of our novel analysis, supported by extensive empirical studies and theoretical investigation. We have carefully addressed your comments and suggestions.

Below, we provide a point-by-point response to your comments.

Regarding the proof for Lemma for Theorem 4.1 (A.1)

Thank you for highlighting this issue. You are correct — there was an error and a simple proof will be constructed in the revision based on the monotonic decrease of $\exp(c/t)$ with respect to $t$ when $c>0$. Indeed,

$\\exp(z_{i}/\\tilde{T}) \\cdot \\exp(z_{j}/T) \\geq \\exp(z_{i}/T) \\cdot \\exp(z_{j}/\\tilde{T}) \iff \\exp((z_{i}-z_j)/\\tilde{T}) \\geq \\exp((z_{i}-z_j)/T)$

and since $z_{i}-z_j \geq 0$ we have that this inequality holds as $\tilde{T} \leq T$.

Typo in Proposition 4.3

Thank you for pointing out this typo. Indeed, in the branch $0<T<1$, $M\in\left[L\right]$ should be changed to $M\in\left[L_T\right]$, and in the branch $T>1$, $M\in\left[L_T\right]$ should be changed to $M\in\left[L\right]$. Similarly, in the proof, in lines 685 and 688, $L$ should be replaced with $L_T$ (3 instances).

As for the sum symbol, we intended to save space by using $\\sum_{i}^{M} \\hat{\\pi}_i - \\hat{\\pi}^T_i$, which we read as $\sum_i^{M} \left( \hat{\pi}_i - \hat{\pi}^T_i \right)$, rather than $\\sum_i^M \\hat{\\pi}_i - \\sum_i^M \\hat{\\pi}_i^T$.

In the revision, we will ensure consistent phrasing in the main body of the paper and the appendix.

Explanation for $\pi^q \approx \pi^q_T$ in Line 353.

The paragraph in lines 332-357 analyzes the structure of the "quantile sample" of APS. Figure 2 shows a strong correlation between the samples' scores and $\Delta z = z_{(1)} - z_{(2)}$ (the difference between the largest and second largest entries of the logits vector), both with and without temperature scaling. Since the quantile sample corresponds to a high score ($1 - \alpha$ quantile of all scores), it consistently has a large $\Delta z$. As evidenced in Figure 2, the $1 - \alpha = 0.9$ quantile sample had $\Delta z^q \approx 11$. According to the relation $\pi_i \propto \exp{z_i}$, this implies $\pi^q_{(1)} \gg \pi^q_{(2)}$, specifically, after some approximations we get $\frac{\pi^q_{(1)}}{\pi^q_{(2)}} \propto 10^4$. Similarly, when temperature scaling calibration was applied, the $1 - \alpha = 0.9$ quantile sample again resulted in $\Delta z_T^q \approx 11$, leading to $\pi_{T,(1)}^{q} \gg \pi_{T,(2)}^{q}$. Thus, due to the overwhelmingly dominant entry in both quantile samples, we have that $\pi_{(1)}^{q}$ and $\pi_{T,(1)}^{q}$ are nearly 1, and the associated sorted softmax vectors obey $\pi^q \approx \pi^q_T$.

Following this comment, to further illustrate the strong similarity between sorted $\pi^{q}$ and $\pi^{q}_T$, we will add in the revised version concrete examples for these vectors for several dataset-model pairs. For example, the first 5 elements in $\pi^{q}$ and $\pi^{q}_T$ (after sorting) for ImageNet-ViT (with $T = T^*$ optimal for calibration):

$\pi^q[:5] = [9.9697e-01, 4.9439e-04, 2.1028e-04, 2.0065e-04, 1.6687e-04]$

$\pi^{q}_T[:5] = [9.9755e-01, 7.6261e-04, 8.7435e-05, 7.8683e-05, 7.6373e-05]$

Regarding the bound in Theorem 4.4.

Thank you for pointing out this typo. Indeed, there is a factor of $\frac{T}{T+1}$ in the $T>1$ branch of Theorem 4.4 and not $\frac{T-1}{T+1}$. The same correction applies to lines 787 and 828 in the proof.

We emphasize that the proof remains valid except for the final line of each branch (787, 828), where $T-1$ was mistakenly written instead of $T$ in the numerator of the bound. This will be fixed. After this minor correction, the bounds are still aligned with the empirical trends.

The complete substitution of $A$ from line 756 into the inequality in line 782, detailed in the following link: https://postimg.cc/hXXHxKNq confirms the correctness of $\max \left( \frac{T}{T-1}\ln(4T),\frac{T}{T+1}\ln(4T(C-1)^2) \right)$ for the branch $T>1$.

Following this comment, we will include this substitution explicitly in the revised version.

Thank you for your thoughtful review and valuable suggestions. We appreciate your recognition of our comprehensive experiments and clear presentation.

Below, we provide a point-by-point response to your comments.

Improving readability of the figures.

Following this comment, in the revision we will make every effort to improve the readability of the figures. The extra page allowed in the final version will provide additional space to further enhance readability.

Practicality of the proposed theory.

The primary aim of our theoretical study is to provide mathematical reasoning for the surprising empirical behavior that we discovered. We believe that addressing the "why" question behind non-intuitive results is of high scientific importance.

That being said, our theory also provides practical implications. For example, if a practitioner cares only about AvgSize and wants to use APS/RAPS, the $0<T<1$ branch of our theory suggests that they pick small $T$ (which is aligned with the empirical observations). Conversely, practitioners can leverage the $T>1$ branch of our theory, where monotonicity in CP properties breaks. Specifically, it justifies defining a finite range for tuning $T$ to balance prediction set sizes and class-conditional coverage, as discussed in Section 5. We refer the reviewer to Appendix C, where we demonstrate how a small calibration dataset can approximate the curves for AvgSize and TopCovGap versus $T$ (shown in Figure 1). Based on these approximate trends, users can select an optimal $\hat{T}$ that aligns with their needs. Additionally, in Appendix D, we highlight the advantages of this approach over existing methods.

Applicability to other domains.

Our work deals with temperature scaling and conformal prediction applied to multiclass classification. We used image classification datasets (ImageNet, CIFAR-100, CIFAR-10) as they are the benchmark datasets in the related literature. Nevertheless, we expect our findings to be beneficial to classification tasks in domains other than images.

In particular, the practical relevance of our paper lies in empowering users to effectively apply CP in multiclass classification, based on their specific needs, by following our proposed guidelines. The applications extend to domains other than images where CP has been used, such as medical diagnosis [1],[2] and NLP [3],[4].

[1] Lu, Charles, et al (2021). "Fair conformal predictors for applications in medical imaging." Proceedings of the AAAI Conference on Artificial Intelligence.

[2] Vazquez, J., Facelli, J. C. (2022). "Conformal Prediction in Clinical Medical Sciences." Journal of healthcare informatics research,

[3] Kumar, Bhawesh, et al (2023). "Conformal prediction with large language models for multi-choice question answering." ICML 2023.

[4] Campos, Margarida, et al (2024). "Conformal prediction for natural language processing: A survey."

Thank you for your thorough and insightful review. We are pleased that you recognized the extensive empirical evaluation of our experimental design.

Below, we carefully respond to all of your comments.

Regarding the technical assumption

The core of this technical assumption is the strong similarity between the softmax vectors of the "quantile samples" associated with $\hat{q}$ and $\hat{q}_T$, as discussed in the paragraph in lines 332-357.

Due to the limitation of characters, we refer you to the response "Explanation for $\pi^q \approx \pi^q_T$ in Line $353$" to Reviewer 8jYt, where we explain and illustrate the proximity between $\pi^q$ and $\pi^q_T$. To highlight the strong similarity, in the revised version we will include concrete examples of these vectors for various dataset-model pairs.

Given that $\pi^q \approx \pi^q_T$, we believe that it is reasonable to make the theoretical derivation tractable by the technical assumption that $\hat{q}$ and $\hat{q}_T$ correspond to the same sample. We do not claim that it holds in every possible setting. Nevertheless, the fact that our theory provides insights that are aligned with the empirical behavior along many models and datasets serves as a justification for this technical assumption.

Metrics for class-conditional coverage

Evaluating conditional coverage across groups using the worst-case coverage metric is both informative and relevant, as demonstrated by previous works, e.g., (Gibbs et al., 2023). Our TopCovGap metric is averaged over the worst 5% due to high variance observed when considering only the single worst-case coverage, as explained in Appendix B.4.

Following your comment, we will report also the AvgCovGap metric that has been used in (Ding et al., 2023) (denoted CovGap there). For example, we present in https://postimg.cc/1fCkf8CH this metric for the three dataset-model pairs shown in Figure 1. Notably, this metric exhibits similar behavior to TopCovGap, displaying a comparable trend of achieving a minimum at temperatures $T>1$.

Missing references

We thank you for bringing these related papers to our attention. Both papers will be cited and discussed in the revised version.

Paper [1] (arXiv preprint) is a concurrent work (our paper was uploaded to arXiv at the same time). The TS results in [1] are only a small subset of our results. They do not consider conditional coverage and use a limited range of T, which masks the non-monotonic effect on the prediction set size of APS and RAPS. Moreover, they also do not compare APS and RAPS to LAC. On the other hand, our paper provides a complete picture of the effect of TS with a wide range of temperatures on both the prediction set size and the class-conditional coverage of APS, RAPS, and LAC. This complete picture teaches practitioners that tuning the temperature for APS and RAPS introduces a trade-off effect (overlooked in [1]), and we provide a practical way to control it.

Paper [2] presents important theoretical results on prediction sets and calibration, which are indeed related to our work. Note though, that [2] is limited to binary classification and do not provide explanation to the fact that calibration (e.g., TS calibration) affects CP methods differently and in a non-monotonic way, as empirically shown and analyzed in our paper.

Practical utility of the findings

Our work investigates the effect of TS on CP as a function of temperature $T$. Through our analysis, we identify a trade-off between two essential properties of adaptive CP methods: mean prediction set size and proximity to conditional coverage. Our guidelines, introduced in Section 5, enable practitioners to navigate this trade-off effectively, which is a novel contribution to the CP literature. The guidelines are further explored in Appendix C and D.

Appendix C demonstrates how, with a limited amount of calibration data, users can approximate the curves in Figure 1. Based on these trends, they can select an appropriate $\hat{T}$ that aligns best with their objectives. For instance, a practitioner working with CIFAR100-ResNet50 who prioritizes prediction set size can achieve over a 50% reduction in the AvgSize of APS using our guidelines.

Appendix D further illustrates the practical relevance of our findings. Specifically, we show that applying TS at the temperature corresponding to the minimum of the approximated TopCovGap curve, followed by RAPS, outperforms Mondrian CP (Vovk, 2012) in both TopCovGap and AvgSize metrics.

Regarding the runtime

In the revised version we will discuss more about the runtime of the proposed guidance. We would like to emphasize that this procedure is done offline during the calibration phase and its runtime is within a range of minutes.

Improving readability

We will include the definitions of the reported metrics (currently appear in the appendix) in the main body of the revised version leveraging the extra page allowed in the final version.