Pith. sign in

REVIEW 3 major objections 4 minor 32 references

Optimal Conformal Prediction under Epistemic Uncertainty

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Bernoulli Prediction Sets are the smallest randomized label sets that keep coverage at 1−α for every distribution in a credal set, and conformal risk control restores marginal coverage when the credal set is invalid.

desk verdict Core BPS result is correct and clean, but the conformal risk control part is missing a monotonicity proof and the abstract overpromises a conditional guarantee. read the letter →

arxiv 2505.19033 v2 pith:MISZH27G submitted 2025-05-25 stat.ML cs.LG

Alireza Javanmardi , Soroush H. Zargarbashi , Santo M. A. R. Thies , Willem Waegeman , Aleksandar Bojchevski , Eyke Hüllermeier This is my paper · ORCID
classification stat.MLcs.LG
keywords conformalpredictioncredalsetsepistemicuncertaintyBernoulliconditionalcoverageriskcontrolaleatoricadaptive
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks what conformal prediction should guarantee when the underlying model returns a set of plausible label distributions—a credal set—rather than a single probability vector, so that aleatoric and epistemic uncertainty are distinguished. It introduces Bernoulli Prediction Sets (BPS): each label is included with an optimized probability, chosen by a linear program so that expected coverage is at least 1−α for every distribution inside the credal set. The central claim is that BPS is the smallest randomized prediction set satisfying this conditional-coverage requirement whenever the credal set is valid, and that with a single distribution it reduces exactly to adaptive prediction sets (APS). When validity cannot be assumed, the paper applies conformal risk control to the BPS coverage risk and claims that marginal coverage is preserved; experiments on CIFAR-10 and CIFAR-100 with ensembles, MC dropout, and evidential models indicate better conditional coverage than APS-based baselines at modest set-size cost.

What carries the argument

Bernoulli Prediction Sets (BPS): a randomized prediction set parameterized by $b_i=(b_{i1},\dots,b_{iK})\in[0,1]^K$, where each label is included independently with probability $b_{ij}$. The linear program in Eq. (7) minimizes expected set size $b_i\cdot\mathbf{1}$ subject to one coverage constraint $b_i\cdot\pi_i^{(j)} \ge 1-\alpha$ per vertex of the credal set; linearity transfers the constraint to every convex combination, and the proof of minimality is the feasibility of the LP. The identified fractional-knapsack structure is what connects BPS to APS and what makes the randomization necessary for tractability when multiple constraints are present.

What would settle it

On a fixed calibration set, compute $b_i^\star(\lambda)$ from Eq. (7) over a grid of $\lambda$ values with a deterministic tie-breaking rule and plot each risk $L(x_i,\lambda)=1-b_i^\star(\lambda)\cdot e_{y_i}$; if any risk increases as $\lambda$ increases, the monotonicity condition of conformal risk control is violated, and repeated splits can be used to check whether marginal coverage actually falls below $1-\alpha$. A direct simulation with two classes and credal sets whose LP has multiple optima would settle whether the guarantee holds as stated.

Watch

Extended reading notes

Core claim

The paper's central claim is Proposition 4.1: for a valid credal set $Q_i = \mathrm{Convex}(\pi_i^{(1)},\dots,\pi_i^{(m)})$ that contains the oracle label distribution $p_i$, solving $b_i^\star = \arg\min_{b} b\cdot\mathbf{1}$ subject to $b\cdot\pi_i^{(j)} \ge 1-\alpha$ for all $j$ gives a Bernoulli set $\mathcal{C}_{\mathrm{BPS}}(x_i,b_i^\star)$ that is the smallest randomized prediction set with expected conditional coverage at least $1-\alpha$ for every $p\in Q_i$. Because $p_i\in Q_i$, the true label is covered with the desired probability despite the model's epistemic uncertainty. With $m=1$ the LP becomes a fractional knapsack problem whose optimum matches APS; with multiple constraints the deterministic version is NP-hard, while the randomized LP remains feasible. For invalid credal sets the paper replaces $1-\alpha$ by a calibrated threshold $\lambda$, defines the miscoverage risk $L(x_i,\lambda)=1-b_i^\star\cdot e_{y_i}$, and applies conformal risk control so that marginal coverage is preserved even when conditional coverage cannot be guaranteed.

Load-bearing premise

The fallback guarantee for invalid credal sets assumes that increasing the calibration threshold never reduces the probability of covering the true label, but the paper does not prove this monotonicity and the defining optimization can have multiple optimal solutions, so that assumption is load-bearing and unverified.

Editorial extensions

If this is right

  • With a valid credal set, BPS achieves conditional coverage at the nominal level $1-\alpha$ without any calibration data, at the price of the smallest expected set size among randomized sets.
  • When a model provides only one distribution, BPS is exactly APS, so the new method is a strict generalization of the existing first-order optimal conformal method.
  • Sampling $m$ distributions from a second-order distribution yields a valid credal set with probability approaching 1 exponentially fast whenever the oracle distribution has nonzero Tukey depth, so BPS extends to Bayesian and evidential predictors.
  • For invalid credal sets, the calibrated threshold $\lambda_{\mathrm{CP}}$ restores marginal coverage; the conservative choice $\max(\lambda_{\mathrm{CP}},1-\alpha)$ avoids under-covering points whose credal sets are actually valid.
  • Empirically, on CIFAR-10 and CIFAR-100, BPS-based methods match or beat APS-based methods in groupwise worst-case coverage and conditional coverage, with only a small increase in average set size.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct extension suggested by the LP structure is to treat the Bernoulli inclusion probabilities as a splittable resource: the same fractional-knapsack argument could apply to any convex objective over set-valued predictions, not only expected cardinality.
  • The monotonicity gap in the risk-control step could be closed by fixing a canonical tie-breaking rule for the LP and proving, under that rule, that $b_i^\star(\lambda)$ is non-decreasing in coverage; absent that, users should verify monotonicity on their own calibration data.
  • The Tukey-depth sample bound implies a practical per-instance budget: one could choose the number of Monte Carlo samples so that the probability the oracle distribution falls outside the convex hull is below a tolerance, rather than fixing the sample count for all points.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes Bernoulli Prediction Sets (BPS), a conformal prediction method for classification that takes as input a credal set, i.e., a convex hull of first-order probability estimates, rather than a single first-order predictor. The method solves a linear program (Eq. 7) that minimizes expected set size subject to the constraint that the expected coverage is at least 1−α under every distribution in the credal set. The authors prove that BPS is the smallest randomized prediction set with this conditional-coverage property when the credal set is valid (Proposition 4.1), and that for m=1 the method reduces to APS (Proposition 4.2). For the case where credal validity is not guaranteed, the paper proposes calibrating the threshold with conformal risk control (Section 4.2, Algorithm 1) and claims a PAC-style conditional-coverage guarantee. The paper includes experiments on CIFAR-10 and CIFAR-100 with ensembles, MC dropout, and evidential models, and reports coverage and set-size comparisons against APS.

Significance. If the valid-credal-set result is isolated, it is a clean and useful contribution: Proposition 4.1 gives a natural optimality criterion for conformal prediction with imprecise probabilities, and Proposition 4.2 correctly shows that the method generalizes APS. The paper also connects credal-set validity to sampling from second-order distributions via Tukey depth, and the experimental study is broad and relevant. However, the paper's headline claim about calibration without valid credal sets is not established: the application of conformal risk control in Section 4.2 lacks the required monotonicity verification, and the abstract promises a stronger PAC-style conditional guarantee than the marginal expectation bound that conformal risk control actually delivers.

major comments (3)
  1. [Section 4.2, Eq. (9), Algorithm 1] The conformal risk control guarantee stated in Eq. (3) requires the risk function L(x,λ) to be non-decreasing and right-continuous in λ. Here L(x_i,λ)=1−b_i^*(λ)·e_{y_i}, where b_i^*(λ) is a solution of the linear program (7) with threshold 1−λ. The authors do not prove that this risk is non-decreasing, and in fact it need not be, because Eq. (7) can have multiple optimal solutions and different optimal solutions can make a given coordinate increase as λ increases. For example, with K=2 and vertices π^(1)=(0.9,0.1), π^(2)=(0.5,0.5), at threshold 1−λ=0.8 one optimal solution is b=(0.8,0.8), while at threshold 1−λ=0.6 another optimal solution is b=(0.9,0.3); thus the coverage probability for label 1 increases from 0.8 to 0.9 as λ increases from 0.2 to 0.4, so L decreases. An arbitrary LP solver can therefore produce a non-monotone risk, and the invocation of Eq. (3) is not justified. The binary search in Algorithm 1 also implicitly assumes monotonicity. The authors need to fix a tie-breaking rule and prove monotonicity and right-continuity, or use a different calibration argument.
  2. [Abstract and Section 4.2] The abstract claims a 'PAC-style guarantee: with high probability over the data, the achieved conditional coverage is at least the desired level.' The actual argument in Section 4.2 invokes conformal risk control, whose guarantee in Eq. (3) is a finite-sample expectation bound on marginal miscoverage: E[L(x_{n+1},λ*)] ≤ α. This is not a conditional coverage guarantee for each test input, and no high-probability/PAC statement is proved anywhere in the paper. The claim should be corrected to an expected marginal coverage statement, or a separate theorem for the conditional/PAC claim should be provided.
  3. [Section 4.2, Eq. (9)] Even after fixing tie-breaking, the definition of the calibrated threshold is not shown to be equivalent to the conformal risk control quantile in Eq. (3). Eq. (9) defines λCP as the infimum over λ of the set of thresholds for which the summed calibration coverage exceeds a quantile-like bound, but it is not demonstrated that this set is an upper tail of the form {λ: (1/(n+1))ΣL(x_i,λ)+b ≤ α}. Without monotonicity of L, this equivalence can fail, and the meaning of the computed threshold is unclear.
minor comments (4)
  1. [Section 4.2, Algorithm 1] The stopping condition 'until R(λ⋆) ≃ 1−α' is informal; the authors should specify a tolerance and the exact monotone search procedure, especially because the risk function may have flat regions.
  2. [Section 4, after Eq. (7)] The sentence 'only the fractional value bij is set to 1' appears garbled and should be rephrased; the intended statement is likely that at most one coordinate of b is fractional in the one-constraint case.
  3. [Appendix B, Theorem B.1] In the proof of Theorem B.1, the claim that the coefficients α_{i,j} 'can be specified in a constructive way' is not backed by an explicit construction; a complete proof should include this construction or cite a reference for it.
  4. [Figure 1] The figure caption lists APS output as [1.0, 0.5, 1.0], which appears inconsistent with the displayed set sizes and with the surrounding text; the notation should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: BPS optimality is a direct LP consequence and the risk-control step invokes an external theorem.

full rationale

The central claim (Proposition 4.1) is not circular: the LP in Eq. (7) minimizes expected set size subject to b·π^(j) ≥ 1−α at the vertices, and because b·p is linear in p, these vertex constraints imply b·p ≥ 1−α for every p in the convex hull, exactly as the proof shows. Minimality follows from the objective min b·1, which is the expected size of the Bernoulli prediction set; no fitted parameter is relabeled as a prediction. The m=1 reduction to APS (Proposition 4.2) is an explicit equivalence proof, not a renaming of a known result. The risk-control step in Section 4.2 applies the published conformal-risk-control theorem of Angelopoulos et al. [2] with L(xi,λ)=1−b⋆_i·e_yi; this is an external citation, not a self-citation chain, and the guarantee is not asserted as a new first-principles derivation. The self-citation [15] is used only to construct experimental credal-set predictors in Section 6.2 and does not carry the main derivation. The paper does not verify that L(xi,λ) is non-decreasing in λ, which is a correctness gap in the Section 4.2 guarantee, but that is a missing technical assumption, not circular reasoning. No step of the derivation defines its conclusion into its premises, so the circularity score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central conditional-coverage result depends mainly on exchangeability and validity of the credal set. The risk-control extension additionally assumes, without proof, that the LP-defined risk function is monotone in the threshold, which is not guaranteed because Eq. 7 can have multiple optima.

free parameters (1)
  • m: number of first-order samples per input = 5 in experiments
    Used to form the credal set as the convex hull of m distributions; the theoretical claims hold for any m, but the practical validity of credal sets from second-order distributions improves with m, and the paper uses m=5.
assumptions (4)
  • standard math Calibration and test data are exchangeable.
    Stated in Section 2 as the only assumption required for conformal prediction; used for all CP guarantees in the paper.
  • domain assumption For each input xi, labels are drawn from a fixed oracle distribution pi = p(y|xi).
    Section 2 assumes this generative model; conditional coverage is defined with respect to pi.
  • domain assumption Valid credal sets satisfy pi ∈ Qi = Convex({pi^(j)}).
    Definition 1 is the premise of Prop 4.1 and the conditional coverage guarantee; it is acknowledged as strong and tested only synthetically or via probabilistic validity.
  • ad hoc to paper The risk function L(xi,λ)=1−b⋆i·e_yi satisfies the monotonicity and right-continuity conditions of conformal risk control.
    Invoked in Section 4.2 and Algorithm 1, but not proved; LP optima are non-unique, so the function may not be well-defined.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Conformal Prediction under Epistemic Uncertainty." pith.science (2026). https://pith.science/paper/MISZH27G

@misc{pith2026250519033,
  author       = {Pith},
  title        = {Pith review of: Optimal Conformal Prediction under Epistemic Uncertainty},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MISZH27G}},
  note         = {Machine review of arXiv:2505.19033}
}
read the original abstract

Conformal prediction (CP) is a widely used frequentist framework to quantify uncertainty by constructing prediction sets with user-specified marginal coverage guarantees. In practice, CP is typically applied on top of probabilistic classifiers, which are able to express aleatoric but not epistemic uncertainty. In this paper, we consider the question of how to optimally employ CP on top of a more expressive formalism, namely credal sets, which can express both aleatoric and epistemic uncertainty. More specifically, we propose probabilistic Bernoulli prediction sets (BPS) and derive a variant that achieves conditional coverage for valid credal sets while remaining minimal in expected size. We then address the more realistic scenario in which the validity of the credal sets is not guaranteed. Assuming access to calibration data with ground-truth distributions over labels, we apply conformal risk control to BPS and derive a PAC-style guarantee: with high probability over the data, the achieved conditional coverage is at least the desired level. We validate our theoretical findings empirically over various datasets.

Figures

Figures reproduced from arXiv: 2505.19033 by the authors.

Figure 1
Figure 1. Comparison of BPS (ours) and APS [23] in terms of conditional coverage, given a second￾order prediction (i.e., a credal set with vertices shown as black circles). BPS uses the vertices as input, while APS, requiring a single distribution, is applied to the mean of the credal set (the blue square π = [0.5, 0.2, 0.3]). The output of each method is shown as the probability of including each label in the set for a nomin… view at source ↗
Figure 2
Figure 2. Comparison of BPS vs. APS at nominal coverage [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Comparing coverage of BPS and APS across various levels of epistemic and aleatoric [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Coverage and set size comparison of the baselines for the synthetic example of the APS [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 24 canonical work pages

  1. [1]

    Angelopoulos, S

    A. Angelopoulos, S. Bates, J. Malik, and M. I. Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009.14193, 2020

    arXiv 2009

  2. [2]

    A. N. Angelopoulos, S. Bates, A. Fisch, L. Lei, and T. Schuster. Conformal risk control. arXiv preprint arXiv:2208.02814, 2022

    arXiv 2022

  3. [3]

    A. N. Angelopoulos, R. F. Barber, and S. Bates. Theoretical foundations of conformal prediction,

    work page

  4. [4]

    Blundell, J

    C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra. Weight uncertainty in neural network. In International conference on machine learning, pages 1613–1622. PMLR, 2015

    work page 2015

  5. [5]

    Epistemic Uncertainty in Conformal Scores: A Unified Approach

    L. Cabezas, V . S. Santos, T. R. Ramos, and R. Izbicki. Epistemic uncertainty in conformal scores: A unified approach. arXiv preprint arXiv:2502.06995, 2025

    work page Pith review arXiv 2025

  6. [6]

    Caprio, S

    M. Caprio, S. Dutta, K. J. Jang, V . Lin, R. Ivanov, O. Sokolsky, and I. Lee. Credal bayesian deep learning. Transactions on Machine Learning Research, 2024

    work page 2024

  7. [7]

    Caprio, M

    M. Caprio, M. Sultana, E. Elia, and F. Cuzzolin. Credal learning theory. In The Thirty- eighth Annual Conference on Neural Information Processing Systems , 2024. URL https: //openreview.net/forum?id=AH5KwUSsln

    work page 2024

  8. [8]

    Daxberger, A

    E. Daxberger, A. Kristiadi, A. Immer, R. Eschenhagen, M. Bauer, and P. Hennig. Laplace redux-effortless bayesian deep learning. Advances in neural information processing systems, 2021

    work page 2021

Show all 32 references
  1. [9]

    Gal and Z

    Y . Gal and Z. Ghahramani. Dropout as a bayesian approximation: Representing model uncer- tainty in deep learning. In international conference on machine learning, pages 1050–1059. PMLR, 2016

    2016

  2. [10]

    C. Guo, G. Pleiss, Y . Sun, and K. Q. Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321–1330. PMLR, 2017

    2017

  3. [11]

    Hayakawa, T

    S. Hayakawa, T. Lyons, and H. Oberhauser. Estimating the probability that a given vector is in the convex hull of a random sample. Probability Theory and Related Fields, 185(3):705–746, 2023

    2023

  4. [12]

    K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770– 778, 2016

    2016

  5. [13]

    S. C. Hora. Aleatory and epistemic uncertainty in probability elicitation with an example from hazardous waste management. Reliability Engineering & System Safety, 54, 1996

    1996

  6. [14]

    Hüllermeier and W

    E. Hüllermeier and W. Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine learning, 2021

    2021

  7. [15]

    Javanmardi, D

    A. Javanmardi, D. Stutz, and E. Hüllermeier. Conformalized credal set predictors. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024. URL https://openreview.net/forum?id=vBah12uVbD

    2024

  8. [16]

    Karimi and R

    H. Karimi and R. Samavi. Evidential uncertainty sets in deep classifiers using conformal prediction. In Proceedings of the Thirteenth Symposium on Conformal and Probabilistic Predic- tion with Applications, 2024. URL https://proceedings.mlr.press/v230/karimi24a. html

    2024

  9. [17]

    D. P. Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. 10

    2014 arXiv

  10. [18]

    Krizhevsky, G

    A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009

    2009

  11. [19]

    Lakshminarayanan, A

    B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017

    2017

  12. [20]

    J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 2018

    2018

  13. [21]

    R. M. Neal. Bayesian learning for neural networks. Springer Science & Business Media, 2012

    2012

  14. [22]

    J. C. Peterson, R. M. Battleday, T. L. Griffiths, and O. Russakovsky. Human uncertainty makes classification more robust. In Proceedings of the IEEE/CVF international conference on computer vision, pages 9617–9626, 2019

    2019

  15. [23]

    Romano, M

    Y . Romano, M. Sesia, and E. Candes. Classification with valid and adaptive coverage.Advances in neural information processing systems, 33:3581–3591, 2020

    2020

  16. [24]

    Rossellini, R

    R. Rossellini, R. F. Barber, and R. Willett. Integrating uncertainty awareness into conformalized quantile regression. In International Conference on Artificial Intelligence and Statistics, 2024

    2024

  17. [25]

    Sadinle, J

    M. Sadinle, J. Lei, and L. Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 2019

    2019

  18. [26]

    Sensoy, L

    M. Sensoy, L. Kaplan, and M. Kandemir. Evidential deep learning to quantify classification uncertainty. Advances in neural information processing systems, 31, 2018

    2018

  19. [27]

    J. W. Tukey. Mathematics and the picturing of data. InProceedings of the international congress of mathematicians, volume 2, pages 523–531. Vancouver, 1975

    1975

  20. [28]

    V ovk, A

    V . V ovk, A. Gammerman, and G. Shafer.Algorithmic Learning in a Random World. Springer Nature, 2022

    2022

  21. [29]

    P. Walley. Statistical reasoning with imprecise probabilities, volume 42. Springer, 1991

    1991

  22. [30]

    K. Wang, F. Cuzzolin, K. Shariatmadar, D. Moens, H. Hallez, et al. Credal deep ensembles for uncertainty quantification. Advances in Neural Information Processing Systems, 2024

    2024

  23. [31]

    Zaffalon

    M. Zaffalon. The naive credal classifier. Journal of statistical planning and inference, 2002. 11 A Proofs Proposition 3.1 Proof. Since pi ∈ Qi ⊆ Q′ i, the solution to optimization in Equation (5) with Q′ i is also feasible for the same optimization with Qi. Therefore, |C| ≤ |...

    2002

  24. [2024]

    URL https://arxiv.org/abs/2411.11824

    arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.