  Performance estimation under covariate shift is a crucial component of safe
AI model deployment, especially for sensitive use-cases. Recently, several
solutions were proposed to tackle this problem, most leveraging model
predictions or softmax confidence to derive accuracy estimates. However, under
dataset shifts, confidence scores may become ill-calibrated if samples are too
far from the training distribution. In this work, we show that taking into
account distances of test samples to their expected training distribution can
significantly improve performance estimation under covariate shift. Precisely,
we introduce a "distance-check" to flag samples that lie too far from the
expected distribution, to avoid relying on their untrustworthy model outputs in
the accuracy estimation step. We demonstrate the effectiveness of this method
on 13 image classification tasks, across a wide-range of natural and synthetic
distribution shifts and hundreds of models, with a median relative MAE
improvement of 27% over the best baseline across all tasks, and SOTA
performance on 10 out of 13 tasks. Our code is publicly available at
https://github.com/melanibe/distance_matters_performance_estimation.
