Test-time adaptation (TTA) is usually evaluated by how much it lowers risk on a target distribution, but a practitioner also needs to know whether a proposed update is worth applying at all. The authors frame this as a certification problem: given a candidate update and a fixed baseline, can we guarantee that the candidate's target excess risk is negative? They derive PAC-Bayesian certificates that bound this excess risk relative to the baseline, rather than providing an absolute risk estimate.
Two certificate types are introduced. A radial certificate uses an MMD ambiguity radius around the empirical target distribution. A direction-sensitive certificate keeps the sign of the empirical RKHS shift, allowing it to certify improvement even when source risk increases. In synthetic experiments, a source-worsening update with target excess risk -0.576 was accepted in all 1,000 repetitions by the directional certificate and never by the radial one; learned finite-state updates with excess risks -0.800 and -0.401 were likewise accepted every time.
On the Covertype dataset, the certificate rejected all updates and blocked geographic-shift adaptations whose unconditional deployment would increase risk by up to 2.75 percentage points in prespecified base libraries, with an exploratory stress test reaching 5.66 points. The authors caution that a feature-quantized CIFAR-10-C and ImageNet-C study was structurally vacuous and is reported only as a diagnostic limitation, not as a practical neural certificate.