# On Guaranteed Optimal Robust Explanations for NLP Models

arXiv: https://arxiv.org/abs/2105.03640 · HTML: https://mlsanity.com/paper/2105.03640/

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 69 references that are in the map.
- First posted on arXiv 8 May 2021.

## Builds on (most cited first, 25 of 25)

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Generating Natural Language Adversarial Examples](https://mlsanity.com/paper/1804.07998/) (2018)
- [Adversarial Training Methods for Semi-Supervised Text Classification](https://mlsanity.com/paper/1605.07725/) (2016)
- [Visualizing and Understanding Neural Models in NLP](https://mlsanity.com/paper/1506.01066/) (2015)
- [Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/1909.00986/) (2019)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Reachability Analysis of Deep Neural Networks with Provable Guarantees](https://mlsanity.com/paper/1805.02242/) (2018)
- [Interpreting CNNs via Decision Trees](https://mlsanity.com/paper/1802.00121/) (2018)
- [Explaining Recurrent Neural Network Predictions in Sentiment Analysis](https://mlsanity.com/paper/1706.07206/) (2017)
- [Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation](https://mlsanity.com/paper/1909.01492/) (2019)
- [Hierarchical interpretations for neural network predictions](https://mlsanity.com/paper/1806.05337/) (2018)
- [Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks](https://mlsanity.com/paper/2006.12834/) (2020)
- [Falling Rule Lists](https://mlsanity.com/paper/1411.5899/) (2014)
- [Improving the Interpretability of Deep Neural Networks with Knowledge Distillation](https://mlsanity.com/paper/1812.10924/) (2018)
- [Explaining Predictions of Non-Linear Classifiers in NLP](https://mlsanity.com/paper/1606.07298/) (2016)
- [POPQORN: Quantifying Robustness of Recurrent Neural Networks](https://mlsanity.com/paper/1905.07387/) (2019)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [Three Modern Roles for Logic in AI](https://mlsanity.com/paper/2004.08599/) (2020)
- [Assessing Robustness of Text Classification through Maximal Safe Radius Computation](https://mlsanity.com/paper/2010.02004/) (2020)
- [Unsupervised Learning of Neural Networks to Explain Neural Networks](https://mlsanity.com/paper/1805.07468/) (2018)

## Built on by (most cited first, 30 of 54)

- [Marabou 2.0: A Versatile Formal Analyzer of Neural Networks](https://mlsanity.com/paper/2401.14461/) (2024)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [Adversarial attacks and defenses in explainable artificial intelligence: A survey](https://mlsanity.com/paper/2306.06123/) (2023)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks](https://mlsanity.com/paper/2210.13915/) (2022)
- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [VeriX: Towards Verified Explainability of Deep Neural Networks](https://mlsanity.com/paper/2212.01051/) (2022)
- [Robust Explanation Constraints for Neural Networks](https://mlsanity.com/paper/2212.08507/) (2022)
- [Formally Explaining Neural Networks within Reactive Systems](https://mlsanity.com/paper/2308.00143/) (2023)
- [Eliminating The Impossible, Whatever Remains Must Be True](https://mlsanity.com/paper/2206.09551/) (2022)
- [Feature Necessity & Relevancy in ML Classifier Explanations](https://mlsanity.com/paper/2210.15675/) (2022)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)
- [The King is Naked: on the Notion of Robustness for Natural Language Processing](https://mlsanity.com/paper/2112.07605/) (2021)
- [Delivering Inflated Explanations](https://mlsanity.com/paper/2306.15272/) (2023)
- [Fooling Explanations in Text Classifiers](https://mlsanity.com/paper/2206.03178/) (2022)
- [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025)
- [Efficient Explanations With Relevant Sets](https://mlsanity.com/paper/2106.00546/) (2021)
- [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [On Formal Feature Attribution and Its Approximation](https://mlsanity.com/paper/2307.03380/) (2023)
- [Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation](https://mlsanity.com/paper/2408.03915/) (2024)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [Efficient Explanations for Knowledge Compilation Languages](https://mlsanity.com/paper/2107.01654/) (2021)
- [Language Models as a Service: Overview of a New Paradigm and its Challenges](https://mlsanity.com/paper/2309.16573/) (2023)
- [Provably Precise, Succinct and Efficient Explanations for Decision Trees](https://mlsanity.com/paper/2205.09569/) (2022)
- [A Cross Attention Approach to Diagnostic Explainability using Clinical Practice Guidelines for Depression](https://mlsanity.com/paper/2311.13852/) (2023)
- [When to Trust AI: Advances and Challenges for Certification of Neural Networks](https://mlsanity.com/paper/2309.11196/) (2023)
- [Learning with Imbalanced Noisy Data by Preventing Bias in Sample Selection](https://mlsanity.com/paper/2402.11242/) (2024)
- [On Computing Relevant Features for Explaining NBCs](https://mlsanity.com/paper/2207.04748/) (2022)

## Abstract (arXiv)

We build on abduction-based explanations for ma-chine learning and develop a method for computing local explanations for neural network models in natural language processing (NLP). Our explanations comprise a subset of the words of the in-put text that satisfies two key features: optimality w.r.t. a user-defined cost function, such as the length of explanation, and robustness, in that they ensure prediction invariance for any bounded perturbation in the embedding space of the left out words. We present two solution algorithms, respectively based on implicit hitting sets and maximum universal subsets, introducing a number of algorithmic improvements to speed up convergence of hard instances. We show how our method can be con-figured with different perturbation sets in the em-bedded space and used to detect bias in predictions by enforcing include/exclude constraints on biased terms, as well as to enhance existing heuristic-based NLP explanation frameworks such as Anchors. We evaluate our framework on three widely used sentiment analysis tasks and texts of up to100words from SST, Twitter and IMDB datasets,demonstrating the effectiveness of the derived explanations.