# Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations arXiv: https://arxiv.org/abs/2501.06078 ยท HTML: https://mlsanity.com/paper/2501.06078/ ## Key facts - Cited by 10 papers in the map (data through 14 Oct 2026). - Builds on 29 of its 64 references that are in the map. - First posted on arXiv 10 Jan 2025. ## Builds on (most cited first, 29 of 29) - [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019) - [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018) - [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016) - [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018) - [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018) - [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020) - [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020) - [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020) - [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022) - [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021) - [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021) - [When Large Language Models Meet Vector Databases: A Survey](https://mlsanity.com/paper/2402.01763/) (2024) - [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021) - [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022) - [On the computation of counterfactual explanations -- A survey](https://mlsanity.com/paper/1911.07749/) (2019) - [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021) - [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) - [From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back](https://mlsanity.com/paper/1412.4311/) (2014) - [Efficient Explanations With Relevant Sets](https://mlsanity.com/paper/2106.00546/) (2021) - [Causes for Query Answers from Databases: Datalog Abduction, View-Updates, and Integrity Constraints](https://mlsanity.com/paper/1611.01711/) (2016) - [Provably Precise, Succinct and Efficient Explanations for Decision Trees](https://mlsanity.com/paper/2205.09569/) (2022) - [On the Complexity of Counterfactual Reasoning](https://mlsanity.com/paper/2211.13447/) (2022) - [Explainable Data-Driven Optimization: From Context to Decision and Back Again](https://mlsanity.com/paper/2301.10074/) (2023) - [Finding Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2110.06163/) (2021) - [Certifiable Robustness for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2201.04770/) (2022) - [Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation](https://mlsanity.com/paper/2411.17603/) (2024) - [New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins](https://mlsanity.com/paper/1907.01129/) (2019) - [Reducing Nearest Neighbor Training Sets Optimally and Exactly](https://mlsanity.com/paper/2302.02132/) (2023) ## Built on by (most cited first, 10 of 10) - [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025) - [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025) - [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025) - [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026) - [Database Views as Explanations for Relational Deep Learning](https://mlsanity.com/paper/2509.09482/) (2025) - [Uncovering Bugs in Formal Explainers: A Case Study with PyXAI](https://mlsanity.com/paper/2511.03169/) (2025) - [Explaining Necessary Truths](https://mlsanity.com/paper/2502.11251/) (2025) - [Efficient & Correct Predictive Equivalence for Decision Trees](https://mlsanity.com/paper/2509.17774/) (2025) - [On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI](https://mlsanity.com/paper/2601.09455/) (2026) - [Towards Rigorous Explainability by Feature Attribution](https://mlsanity.com/paper/2604.15898/) (2026) ## Abstract (arXiv) Despite the wide use of k-Nearest Neighbors as classification models, their explainability properties remain poorly understood from a theoretical perspective. While nearest neighbors classifiers offer interpretability from a ``data perspective'', in which the classification of an input vector barx is explained by identifying the vectors barv1, ldots, barvk in the training set that determine the classification of barx, we argue that such explanations can be impractical in high-dimensional applications, where each vector has hundreds or thousands of features and it is not clear what their relative importance is. Hence, we focus on understanding nearest neighbor classifications through a ``feature perspective'', in which the goal is to identify how the values of the features in barx affect its classification. Concretely, we study abductive explanations such as ``minimum sufficient reasons'', which correspond to sets of features in barx that are enough to guarantee its classification, and counterfactual explanations based on the minimum distance feature changes one would have to perform in barx to change its classification. We present a detailed landscape of positive and negative complexity results for counterfactual and abductive explanations, distinguishing between discrete and continuous feature spaces, and considering the impact of the choice of distance function involved. Finally, we show that despite some negative complexity results, Integer Quadratic Programming and SAT solving allow for computing explanations in practice.