Cavity-Calibrated Prediction Sets
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.