Converting Efficiency to Classwise Coverage: Cluster-Frequency Conformal Prediction

Conformal prediction guarantees marginal coverage under exchangeability, but coverage can vary substantially across classes. We propose Cluster-Frequency Conformal Prediction (CFCP), which forms probability vectors from softly pooled cluster-label frequencies, prior smoothing, and a reliability-weighted fallback before standard conformal scoring. Independent final calibration preserves marginal validity. Across seven image and text evaluation settings, including three with long-tailed training and four score families, we examine whether efficient prediction sets provide headroom for classwise coverage. CFCP can achieve smaller prediction sets at matched marginal coverage, motivating comparisons of classwise coverage at equal size budgets. At CFCP's nominal mean set size, paired comparisons favor CFCP in 22 of 28 cells and the selected best baseline in one, with five inconclusive and gains up to 22.47 percentage points. Comparisons averaged over shared size ranges favor CFCP in 24 cells and the baseline in three, with one inconclusive. These results support an empirical classwise coverage-size advantage without establishing classwise coverage guarantees.