TailSafe: Decision-Relevant Certification for Long-Tailed Adaptation

Prior correction can improve a long-tailed classifier's overall accuracy while degrading a frequency group. TailSafe determines whether the available evidence justifies executing a correction under baseline-relative overall and group risk budgets. Its key observation is that budget feasibility can be resolved without uniquely recovering the target prior. Frozen logit and prototype witnesses identify compatible environments through mixture-direction concentration. A certification-aware selector anticipates an independent paired-loss audit whose uncertainty adapts to error-change second moments. An intersection–union rule controls erroneous release without a direction-count penalty in the audit threshold. Under label shift, a declared finite prior family, and independent calibration, TailSafe provides finite-sample risk control and protected preservation. An exact ambiguity dual and a nonasymptotic execution bound separate action-relevant prior uncertainty from directional source-evidence requirements. Experiments span ten frozen learners and four image benchmarks. In controlled CIFAR-100-LT deployment, TailSafe achieves a 2.4 percentage-point overall gain with 70% execution and 0.4% test-estimated budget exceedance. Finite-support studies demonstrate useful execution under exactly indistinguishable priors. Code is available at Supplement.