  Interpretability is essential for machine learning models to be trusted and
deployed in critical domains. However, existing methods for interpreting text
models are often complex, lack mathematical foundations, and their performance
is not guaranteed. In this paper, we propose FRED (Faithful and Robust
Explainer for textual Documents), a novel method for interpreting predictions
over text. FRED offers three key insights to explain a model prediction: (1) it
identifies the minimal set of words in a document whose removal has the
strongest influence on the prediction, (2) it assigns an importance score to
each token, reflecting its influence on the model's output, and (3) it provides
counterfactual explanations by generating examples similar to the original
document, but leading to a different prediction. We establish the reliability
of FRED through formal definitions and theoretical analyses on interpretable
classifiers. Additionally, our empirical evaluation against state-of-the-art
methods demonstrates the effectiveness of FRED in providing insights into text
models.
