Skip to content
Book Open access

Cavity-Calibrated Prediction Sets

Nov 2026 · Proceedings of the 35th ACM International Conference on Information and Knowledge Management · 0 citations · 33 references

TL;DR

Cavity-Calibrated Prediction Sets (CCPS) are introduced, which prove distribution-free marginal and joint coverage guarantees and establish a correlation-decay condition under which cavity scores converge to true leave-one-out scores.

Abstract

Conformal prediction equips black-box classifiers with finite-sample, distribution-free coverage guarantees, but its standard application to structured outputs over probabilistic graphical models is hampered by two issues: per-node nonconformity scores derived from approximate beliefs are inflated by self-reinforcing local potentials, and a naive Bonferroni correction over N output variables produces prediction sets that grow with the size of the graph. We introduce Cavity-Calibrated Prediction Sets (CCPS), a framework that addresses both. From a single loopy belief-propagation pass we extract self-cavity beliefs b icav ∝ bi / ϕi that approximate exact leave-one-out scores at O(NL) amortized cost, recovering a Θ ( N ) speed-up over jackknife+. A two-level structured Bonferroni correction allocates significance across a proper graph colouring, recovering a factor-χ' tightening of the joint coverage bound. We prove distribution-free marginal and joint coverage guarantees and establish a correlation-decay condition under which cavity scores converge to true leave-one-out scores. Across seven primary benchmarks --- CoNLL-2003 and OntoNotes 5.0 for NER, Pascal VOC, ADE20K and Cityscapes for segmentation, plus SensorNet and Ising synthetic graphs --- evaluated over 20 calibration seeds at α=0.10, CCPS reduces mean prediction-set size by 34-58% relative to naive split-conformal and by 23-37% relative to RCPS while maintaining empirical joint coverage at or above the nominal level (all reductions p<0.001 under paired Wilcoxon with Holm--Bonferroni correction). On small Ising grids where exact leave-one-out is tractable, cavity scores rank-correlate with the exact LOO scores at Spearman ρ ≥ 0.985 in the sub-critical regime, and CCPS matches structured jackknife+ in tightness while running roughly 1 500× faster on a 32 × 32 grid.

Read PDF

Similar papers

Review Open access Oct 2026

Conformal Prediction for Distribution-Free Uncertainty in Machine Learning Models

A point prediction says nothing about how far it might be wrong. Conformal prediction repairs that with very little machinery: hold out some labelled data, score how badly the model misses on it, and widen each new prediction by a quantile of those scores. The resulting set contains the true label with a chosen probabi...

Mini T. V. · 0 citations

Sharp training-conditional coverage for conformal prediction under covariate shift

Weighted split conformal prediction reweights calibration scores by the likelihood ratio between the test and training covariate distributions and guarantees marginal coverage under covariate shift. We study its coverage conditional on the calibration data. An elementary argument, based on a single concentration inequa...

Mehrdad Pournaderi · 1 citation
#machine learning Preprint Nov 2026

Conformal Prediction for Distribution-to-Distribution Regression

This work proposes a new conformal framework that operates in an orthogonal basis space, producing interpretable prediction sets while preserving coverage guarantees and develops an adaptive variant with asymptotic conditional coverage under mild assumptions.

Trung-Khang Tran, T. A. Hoang, Viet Anh Khoa Tran et al. · 0 citations

SLP-ProbHard: Probabilistic Hard-Constrained Learning via Structural Latent Parameterization

SLP-ProbHard is introduced, a cross-family, representation-centered framework for probabilistic hard-constrained learning when explicit structural parameterizations are available, and how feasible coordinates and maps affect stochastic dimension, dependence, calibration, expressiveness, and computation is studied.

W. Bekele, M. D'Oria · 0 citations
Preprint Oct 2026

CoCoNet: Convex Conformal Network for Multi-Dimensional Uncertainty Regions

Conformal prediction (CP) provides distribution-free coverage guarantees under exchangeability, but the efficiency of its prediction regions depends critically on the choice of the conformity score. This is particularly important in multivariate regression, where dependencies across output dimensions induce complex joi...

Alireza Moradi, Thomas Bruys, P. van Hentenryck et al. · 0 citations
#machine learning Preprint Nov 2026

A Black-Box Reduction from Regret to Multi-Level Coverage

Online Conformal Prediction (OCP) sequentially constructs prediction sets whose average empirical coverage converges to a target level over time, for arbitrary, potentially adversarial datasets. In the multi-level setting, prediction sets are produced at $d$ coverage levels at once. Prior work argued for the use of onl...

Tuo Liu, Edgar Dobriban, Francesco Orabona · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.