Title: New Definitions and Evaluations for Saliency Methods: Staying Intrinsic and Sound. Abstract:   Saliency methods seek to provide human-interpretable explanations for the output of machine learning model on a given input. A plethora of saliency methods exist, as well as an extensive literature on their justifications/criticisms/evaluations. This paper focuses on heat maps based saliency methods that often provide explanations that look best to humans. It tries to introduce methods and evaluations for masked-based saliency methods that are {\em intrinsic} --- use just the training dataset and the trained net, and do not use separately trained nets, distractor distributions, human evaluations or annotations. Since a mask can be seen as a "certificate" justifying the net's answer, we introduce notions of {\em completeness} and {\em soundness} (the latter being the new contribution) motivated by logical proof systems. These notions allow a new evaluation of  saliency methods, that experimentally provides a novel and stronger justification for several heuristic tricks in the field (T.V. regularization, upscaling). 