REVIEW 3 major objections 5 minor 27 references
Enhancing Conformal Prediction via Class Similarity
T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read Adding a small out-of-group penalty to any conformal prediction score reduces both the average number of semantic groups and the average size of prediction sets, and the paper proves the condition under which the size reduction holds.
desk verdict A useful penalty-based CP method with a solid local derivative analysis; the finite-sample gap between theory and experiments is real but not disqualifying. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The mechanism is the 'out-of-group penalty' added to a conformal score: s_λ(x,y) = s(x,y) + λ d(y, ŷ(x)), with d=0 inside the predicted class's group and d=1 outside (or the soft model-specific penalty 1 − cosine-similarity of class means). The penalty cannot raise the conformal quantile by more than λ, so any out-of-group label admitted at level λ was already admitted at level 0—out-of-group inclusions can only be removed. The derivative identity of Theorem 4.5 then supplies the surprising part: the net change in expected set size at small λ is governed by the imbalance p₁n₀ vs p₀n₁, converting a coherence penalty into an efficiency boost.
What would settle it
On a dataset with a large calibration set, measure average set size for very small λ and check the sign of its slope at λ=0 against the predicted sign a p₁n₀ − b p₀n₁; in particular, construct a near-symmetric partition (p₁n₀ ≈ p₀n₁, a≈b) where Theorem 4.5 predicts a near-zero or positive slope, and test whether the empirical slope follows—if the set size decreases regardless of the sign, the mechanism is not the derived imbalance.
Extended reading notes
Core claim
Theorem 4.5 states that for the penalized score s_λ(x,y)=s(x,y)+λ·d(y,ŷ(x)), where d is 1 for classes outside the predicted class's group, the derivative of expected prediction-set size at λ=0 has the sign of a·p₁·n₀ − b·p₀·n₁. Here p₀ and p₁ are the probabilities that the true label lies inside or outside the predicted class's group, n₀ and n₁ the average numbers of in-group and out-of-group classes, and a,b density factors at the original quantile. Since n₁ ≫ n₀ and classifiers rarely place the true label outside the predicted class's group, the derivative is usually negative, so a small penalty reduces average set size for any CP score. The analysis also motivates a model-specific penalty
Load-bearing premise
The proof that the penalty shrinks average set size relies on an idealized infinite calibration set (so the threshold is the exact statistical quantile), plus the empirical imbalance p₁n₀ ≪ p₀n₁; in real finite-sample experiments that guarantee does not strictly apply.
Editorial extensions
If this is right
- Any conformal prediction score (LAC, RAPS, SAPS) can be improved post-training by the penalty without touching the model or the coverage guarantee.
- Datasets with no human semantic classes can still be boosted using the model's own embedding similarities (MS-CS), making the tool broadly applicable.
- Users who want coherent prediction sets—e.g., diseases requiring similar treatment—get fewer distinct groups in the set at the same target coverage.
- Tuning λ on a small validation split (10% of the data) suffices to hit the improving regime, so the method is cheap to deploy.
Reading between the lines
- The reduction condition p₁n₀ ≪ p₀n₁ suggests the benefit grows as groups get smaller and the classifier more accurate; on low-accuracy classifiers or with very coarse groups the sign could reverse, so the method is not universal.
- The same derivative argument should extend to penalties based on any distance function (not just binary groups or cosine similarity), implying a family of 'similarity-weighted' CP scores; a natural test is whether a learned metric beats cosine similarity.
- Because the theory assumes an infinite calibration set, its finite-sample behavior is an open question—one could check whether the small-λ improvement persists under heavy calibration noise or whether quantile randomness dominates.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes to modify any conformal score function by adding a class-similarity penalty: s_λ(x,y)=s(x,y)+λ d(y, ŷ(x)). For a known semantic partition, d is binary (0 if same group, 1 otherwise), yielding the model-agnostic method MA-CS; for the model-specific variant MS-CS, d is 1 minus the cosine similarity between class means in the penultimate feature space. The authors prove (Proposition 4.2, Corollary 4.3) that the penalty cannot add out-of-group labels and that the set of represented superclasses does not expand. Their main theoretical result (Theorem 4.5, proof in Supp. A.1) states that, under Assumptions 1–3, the sign of the derivative d/dλ E[|C_λ(X)|] at λ=0 equals sign(a p_1 n_0 − b p_0 n_1). They argue that this is typically negative, so a small penalty reduces average set size for any underlying score function. Experiments on CIFAR-100, Living-17, and Mini-ImageNet with LAC, RAPS, and SAPS show consistent reductions in both average set size and number of superclasses for both MA-CS and MS-CS.
Significance. If the claims held as stated, the contribution would be significant: a simple, post-hoc modification that improves both semantic coherence and efficiency of essentially any conformal predictor. The empirical evidence is encouraging and consistently reproduced across datasets, models, and score functions (e.g., Table 1 reports size reductions of roughly 30% for RAPS on CIFAR-100/ResNet34, with modest standard deviations over 100 trials), and the coverage tables confirm that marginal coverage is maintained. The derivative calculation leading to Theorem 4.5 is nontrivial and correct under the stated assumptions, and the ablation against MA-Diag (Supp. D) shows that the specific similarity matrix matters. However, the central theoretical guarantee is conditional in two ways that the abstract and Figure 1 do not convey: it relies on a population (infinite-calibration) quantile, and it requires a sign inequality involving unverified density factors. The model-specific variant, which the paper ultimately advertises as the widely applicable tool, has no theoretical support beyond analogy to the binary case. These gaps do not negate the empirical findings, but they mean the advertised claim
major comments (3)
- [Section 4, Assumption 1 vs. Section 6] Assumption 1 states that C_λ(X) is based on the statistical quantile q_λ of the CDF of s_λ(X,Y), i.e., an infinite/large calibration set. The experimental protocol in Section 6 splits the 20% calibration set into two equal halves, so q̂ is computed from roughly 10% of the validation data. For finite n, the empirical quantile is a step function in λ and the derivative d/dλ E[|C_λ|] does not exist; Theorem 4.5 therefore does not apply to the setting actually evaluated. The abstract and Figure 1 caption claim reduction 'regardless of the baseline score function' without this caveat. Please either qualify the claims to make the Assumption-1 condition explicit, or provide a finite-sample analysis (e.g., a concentration bound on the empirical derivative, or an empirical verification that the sign condition holds with the finite-sample quantile).
- [Section 4, Theorem 4.5 and Discussion] The theorem only yields sign(dE/dλ)=sign(a p_1 n_0 − b p_0 n_1). The paper's conclusion that adding the penalty reduces set size requires this expression to be negative, i.e., a p_1 n_0 < b p_0 n_1. The Discussion asserts 'we can expect' p_1 n_0 ≪ p_0 n_1 and a≈b, but no experiment or computation verifies a, b, p_0, p_1, or the inequality itself. Since this is the pivotal condition for the advertised 'any score function' result, the authors should either estimate these quantities from calibration data and report the sign of the theoretical derivative, or explicitly restate the theorem as a conditional result. The current wording in the Introduction ('Surprisingly, we show mathematically... reduce the average set size... for any score function') is stronger than what is proven.
- [Section 4, Theorem 4.5 vs. Section 6.2] The derivative result is local at λ=0. The proposed method tunes λ over a pre-defined range and selects the value that minimizes size on the λ-evaluation split. Figure 2 shows that size initially decreases and then increases with λ, so the improvement achieved at the tuned λ is not covered by the derivative theorem. The paper should clearly separate the proven small-λ statement from the empirical observation that the tuning procedure finds a beneficial λ. As written, the conclusion that the method 'reduces the average prediction set size' for the tuned model overstates the theory.
minor comments (5)
- [Theorem 4.5] The notation q_0 is used in the proof and discussion but not explicitly defined in the theorem statement. Please define q_0 := q_λ at λ=0 for clarity.
- [Figure 1 caption] The caption says 'We show that our regularization reduces the average prediction set size, regardless of the baseline score function.' This should be qualified to 'for sufficiently small λ under Assumptions 1–3 and when the sign condition in Theorem 4.5 is negative.'
- [Section 6] The description of the calibration split could be clearer: the reader must infer that 'splitting the calibration set into two equal size sets' means 10% of the validation data for q̂-calibration and 10% for λ-evaluation. A short algorithmic description or diagram would help.
- [Supp. B.2] In the RAPS definition, the uniform random variable u is used but not defined at that point; add 'u ∼ U[0,1]' in the definition for completeness.
- [Section 6.1] The sentence 'our methods—MA-CS and MS-CS—consistently achieve the best performance on both metrics across all dataset–model pairs and all CP methods' is immediately followed by a paragraph showing AIR achieves lower #Superclasses in several cases. Consider rewording to 'best among the methods that do not sacrifice size' or explicitly 'excluding AIR' in the same sentence.
Circularity Check
No significant circularity: the main theorem is derived from explicit distributional assumptions, and the empirical lambda tuning is standard held-out model selection.
full rationale
The paper's derivation chain is self-contained. Lemma 4.1 and Proposition 4.2 follow directly from the definition s_lambda(x,y)=s(x,y)+lambda*d(y,hat y(x)) and from monotonicity of quantiles; no conclusion is assumed. Theorem 4.5 is obtained by differentiating the identity F_lambda(q_lambda)=1-alpha with respect to lambda and differentiating the expression for E[|C_lambda(X)|] written in terms of the defined quasi-CDFs; the sign condition a*p1*n0 - b*p0*n1 is an explicit input condition, not a restatement of the desired reduction. The empirical selection of lambda on a held-out lambda-evaluation subset and reporting test-set size on a disjoint test set is standard model selection, not a fitted parameter renamed as a prediction. The self-citations (e.g., [4], [20]) appear only for background definitions and neural-collapse motivation and do not support any load-bearing step. The only notable caveat is that Assumption 1 assumes a statistical/population quantile, which the authors explicitly acknowledge 'essentially reflects having a large calibration set'; this is a finite-sample gap between theory and experiments, not a circular dependency, and therefore does not raise the circularity score.
Assumptions & free parameters
free parameters (2)
- λ (regularization strength for MA-CS and MS-CS) =
tuned per dataset/model/score on a calibration split; e.g., 0.28 for CIFAR-100 ResNet50 RAPS (Fig. 2)
- λ_SAPS for SAPS score =
≈0.08 per model-dataset pair
assumptions (5)
- domain assumption Calibration and test samples are exchangeable (CP's only distributional assumption).
- ad hoc to paper Assumption 1: prediction sets use the statistical quantile q_λ of the CDF of s_λ, i.e., an infinitely large calibration set.
- ad hoc to paper Assumptions 2-3: conditional CDFs F_z and size-biased quasi-CDFs are absolutely continuous.
- domain assumption Sign condition p_1 n_0 << p_0 n_1 (and a≈b or b not much smaller than a) holds in practice.
- domain assumption Neural collapse: within-class deep features concentrate around class means, so cosine similarity between class means reflects useful class similarity.
Cite this review
Pith. "Pith review of Enhancing Conformal Prediction via Class Similarity." pith.science (2026). https://pith.science/paper/DUQWGN2C
@misc{pith2026251119359,
author = {Pith},
title = {Pith review of: Enhancing Conformal Prediction via Class Similarity},
year = {2026},
howpublished = {\url{https://pith.science/paper/DUQWGN2C}},
note = {Machine review of arXiv:2511.19359}
}
read the original abstract
Conformal Prediction (CP) has emerged as a powerful statistical framework for high-stakes classification applications. Instead of predicting a single class, CP generates a prediction set, guaranteed to include the true label with a pre-specified probability. The performance of different CP methods is typically assessed by their average prediction set size. In setups where the classes can be partitioned into semantic groups, e.g., diseases that require similar treatment, users can benefit from prediction sets that are not only small on average, but also contain a small number of semantically different groups. This paper begins by addressing this problem and ultimately offers a widely applicable tool for boosting any CP method on any dataset. First, given a class partition, we propose augmenting the CP score function with a term that penalizes predictions with out-of-group errors. We theoretically analyze this strategy and prove its advantages for group-related metrics. Surprisingly, we show mathematically that, for common class partitions, it can also reduce the average set size of any CP score function. Our analysis reveals the class-similarity factors behind this improvement and motivates a variant that can further reduce prediction set size by leveraging the model's embeddings, without requiring any human semantic partition. Finally, we present an extensive empirical study, encompassing prominent CP methods, multiple models, and several datasets, which demonstrates that our class-similarity-based approach consistently enhances CP methods.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Anastasios N Angelopoulos and Stephen Bates. A gentle in- troduction to conformal prediction and distribution-free un- certainty quantification.arXiv preprint arXiv:2107.07511,
-
[2]
Uncertainty sets for image clas- sifiers using conformal prediction
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image clas- sifiers using conformal prediction. InInternational Confer- ence on Learning Representations, 2021. 1, 2, 6
2021
-
[3]
Konstantina Bairaktari, Jiayun Wu, and Zhiwei Steven Wu. Kandinsky conformal prediction: Beyond class- and covariate-conditional coverage.arXiv preprint arXiv:2502.17264, 2025. 2
arXiv 2025
-
[4]
On temperature scaling and conformal prediction of deep classifiers
Lahav Dabah and Tom Tirer. On temperature scaling and conformal prediction of deep classifiers. InForty-second In- ternational Conference on Machine Learning, 2025. 1
2025
-
[5]
Imagenet: A large-scale hierarchical image database
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009. 6
2009
-
[6]
Class-conditional conformal prediction with many classes.Advances in Neu- ral Information Processing Systems, 36, 2023
Tiffany Ding, Anastasios Angelopoulos, Stephen Bates, Michael Jordan, and Ryan J Tibshirani. Class-conditional conformal prediction with many classes.Advances in Neu- ral Information Processing Systems, 36, 2023. 2, 6
2023
-
[7]
Hierarchical se- lective classification.Advances in Neural Information Pro- cessing Systems, 37:111047–111073, 2024
Shani Goren, Ido Galil, and Ran El-Yaniv. Hierarchical se- lective classification.Advances in Neural Information Pro- cessing Systems, 37:111047–111073, 2024. 2, 6
2024
-
[8]
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. InProceed- ings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016. 6
2016
Show all 27 references
-
[9]
Hierarchical conformal classification.arXiv preprint arXiv:2508.13288,
Floris den Hengst, In `es Blin, Majid Mohammadi, Syed Iht- esham Hussain Shah, and Taraneh Younesian. Hierarchical conformal classification.arXiv preprint arXiv:2508.13288,
-
[10]
Conformal prediction for deep clas- sifier via label ranking
Jianguo Huang, Huajun Xi, Linjun Zhang, Huaxiu Yao, Yue Qiu, and Hongxin Wei. Conformal prediction for deep clas- sifier via label ranking. InInternational Conference on Ma- chine Learning, pages 20331–20347. PMLR, 2024. 1, 2, 6
2024
-
[11]
Learning multiple layers of features from tiny images
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. 6
2009
-
[12]
Trustworthy clinical AI solutions: A unified review of uncertainty quantification in deep learning models for medical image analysis.Artif
Benjamin Lambert, Florence Forbes, Senan Doyle, Har- monie Dehaene, and Michel Dojat. Trustworthy clinical AI solutions: A unified review of uncertainty quantification in deep learning models for medical image analysis.Artif. In- tell. Medicine, 150:102830, 2024. 1
2024
-
[13]
Formal verification and control with conformal prediction.arXiv preprint arXiv:2409.00536, 2024
Lars Lindemann, Yiqi Zhao, Xinyi Yu, George J Pap- pas, and Jyotirmoy V Deshmukh. Formal verification and control with conformal prediction.arXiv preprint arXiv:2409.00536, 2024. 1
2024 arXiv
-
[14]
Conformal pre- diction in hierarchical classification.arXiv preprint arXiv:2501.19038, 2025
Thomas Mortier, Alireza Javanmardi, Yusuf Sale, Eyke H¨ullermeier, and Willem Waegeman. Conformal pre- diction in hierarchical classification.arXiv preprint arXiv:2501.19038, 2025. 2
2025 arXiv
-
[15]
Inductive confidence machines for re- gression
Harris Papadopoulos, Kostas Proedrou, V olodya V ovk, and Alex Gammerman. Inductive confidence machines for re- gression. InMachine Learning: ECML 2002: 13th European Conference on Machine Learning Helsinki, Finland, Au- gust 19–23, 2002 Proceedings 13, pages 345–356. Springer,
2002
-
[16]
Prevalence of neural collapse during the terminal phase of deep learning training.Proceedings of the National Academy of Sciences, 117(40):24652–24663, 2020
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training.Proceedings of the National Academy of Sciences, 117(40):24652–24663, 2020. 6
2020
-
[17]
Clas- sification with valid and adaptive coverage.Advances in Neural Information Processing Systems, 33:3581–3591,
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Clas- sification with valid and adaptive coverage.Advances in Neural Information Processing Systems, 33:3581–3591,
-
[18]
Least ambiguous set-valued classifiers with bounded error levels
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525): 223–234, 2019. 1, 2, 6
2019
-
[19]
Breeds: Benchmarks for subpopulation shift.arXiv preprint arXiv:2008.04859, 2020
Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopulation shift.arXiv preprint arXiv:2008.04859, 2020. 6
2008 arXiv
-
[20]
Per- turbation analysis of neural collapse
Tom Tirer, Haoxiang Huang, and Jonathan Niles-Weed. Per- turbation analysis of neural collapse. InInternational Con- ference on Machine Learning, pages 34301–34329. PMLR,
-
[21]
Matching networks for one shot learning.Ad- vances in neural information processing systems, 29, 2016
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning.Ad- vances in neural information processing systems, 29, 2016. 6
2016
-
[22]
Conditional validity of inductive conformal predictors
Vladimir V ovk. Conditional validity of inductive conformal predictors. InAsian conference on machine learning, pages 475–490. PMLR, 2012. 2, 6
2012
-
[23]
Machine-learning applications of algorithmic randomness
V olodya V ovk, Alexander Gammerman, and Craig Saunders. Machine-learning applications of algorithmic randomness. InProceedings of the Sixteenth International Conference on Machine Learning, pages 444–453, 1999. 1, 3
1999
-
[24]
Algorithmic learning in a random world
Vladimir V ovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer, 2005. 1, 3
2005
-
[25]
Are neurons ac- tually collapsed? on the fine-grained structure in neural rep- resentations
Yongyi Yang, Jacob Steinhardt, and Wei Hu. Are neurons ac- tually collapsed? on the fine-grained structure in neural rep- resentations. InInternational Conference on Machine Learn- ing, pages 39453–39487. PMLR, 2023. 6
2023
-
[26]
Conformal structured prediction.arXiv preprint arXiv:2410.06296,
Botong Zhang, Shuo Li, and Osbert Bastani. Conformal structured prediction.arXiv preprint arXiv:2410.06296,
-
[2024]
Proofs and Additional Derivations A.1
2 9 A. Proofs and Additional Derivations A.1. Proof of Theorem 4.5 From the definition ofs λ(x, y), for any fixedx, the size of the penalized conformal set can be written as |Cλ(x)|= X y∈Y0(x) I{s(x, y)≤q λ}+ X y∈Y1(x) I{s(x, y)≤q λ −λ} =n 0(x) ˆF x 0 (qλ) +n1(x) ˆF x 1 (qλ −λ...
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.