The Label Complexity of Useful Class-Conditional Prediction Sets under Distribution Shift

Prediction sets can make deployed classifiers safer by returning several plausible labels when a single prediction is uncertain. Their value depends on classwise reliability: average coverage can meet its target while rare or difficult classes fail repeatedly. This concern is sharper after distribution shift, when calibration labels come from a source environment but reliability is needed on the target. We ask what labeled source data and unlabeled target inputs reveal about class-conditional prediction sets, and when target labels are necessary. Under unrestricted joint shift, two target laws can produce the same observable data while requiring different classwise thresholds; any label-free rule covering both must enlarge its sets on one law. We give a labeled target audit that estimates the missing quantiles with a simultaneous guarantee. Probability-scale error is invariant to increasing score transformations, and threshold recovery follows under local regularity. At fixed confidence, achieving threshold tolerance varepsilon with fixed, nonadaptive class-stratified labeled pairs has total complexity Theta(Kvarepsilon-2log K), or Theta(varepsilon-2log K) labels per class under equal allocation. Class imbalance creates a separate acquisition cost; for foreground class probabilities of order 1/K, the mixed-stream label complexity is also Theta(Kvarepsilon-2log K) at fixed confidence. Experiments on action-recognition and image shifts show that marginal coverage can conceal severe class failures and that source classwise calibration depends on the shift. The results connect the information available at deployment to the target labels needed for useful class-conditional prediction.