Test-Time Feature Alignment Under Uncertain Correspondence

Feature alignment can improve a frozen classifier's accuracy under test-time distribution shift without establishing whether shifted examples recover the predictions made on their clean counterparts. This work asks whether prediction recovery can be assessed without knowing which shifted example corresponds to which clean example. It introduces an assignment framework that considers possible matchings subject to a cost constraint. With unpaired features, the framework bounds prediction disagreement relative to a baseline matching. Independent paired calibration provides simultaneous recovery-error bounds for a new batch drawn under the same conditions as the calibration batches. These bounds can certify that one method better recovers clean predictions than another without identifying the true matching. Across natural ImageNet shifts and ImageNet-C, substantial ambiguity remains despite accuracy gains. In paired ImageNet-C experiments, every certified ordering agreed with the hidden pairs. A randomized-cost control preserved observed coverage but could no longer distinguish methods, showing that coverage alone does not guarantee informative bounds.