Title: Soundness and Completeness: An Algorithmic Perspective on Evaluation of Feature Attribution. Abstract: Feature attribution is a fundamental approach to explaining neural networks by quantifying the importance of input features for a model's prediction. Although a variety of feature attribution methods have been proposed, there is little consensus on the assessment of attribution methods. In this study, we empirically show the limitations of \emph{order-based} and \emph{model-retraining} metrics. To overcome the limitations and enable evaluation with higher granularity, we propose a novel method to evaluate the \emph{completeness} and \emph{soundness} of feature attribution methods. Our proposed evaluation metrics are mathematically grounded on algorithm theory and require no knowledge of "ground truth" informative features. We validate our proposed metrics by conducting experiments on synthetic and real-world datasets. Lastly, we use the proposed metrics to benchmark a wide range of feature attribution methods. Our evaluation results provide an innovative perspective on comparing feature attribution methods. Code is in the supplementary material. 