This paper presents stability guarantees as a principled method for evaluating feature attribution. It points out the limitations of existing authentication methods, which use overly smoothed classifiers and provide only conservative guarantees. To address this, we introduce "soft stability" and propose a simple, model-independent, and sample-efficient stability authentication algorithm (SCA) that provides non-obvious and interpretable guarantees for all attribution methods. Furthermore, we demonstrate that mild smoothing offers a better trade-off between accuracy and stability, avoiding the excessive trade-offs inherent in existing authentication methods. To account for this phenomenon, we derive novel features for stability under smoothing using Boolean functional analysis. We demonstrate the effectiveness of soft stability in measuring the robustness of explanation methods by evaluating SCA on vision and language tasks.
