cs.AI · 2604.15898 Copy arXiv ID · Apr 17, 2026 Save Towards Rigorous Explainability by Feature Attribution Authors: Olivier Létoffé , Xuanxiang Huang , Joao Marques-Silva
Organizations: IRIT, University of Toulouse France · Nanyang Technological University, Singapore · ICREA & Univ. Lleida, Spain
Abstract For around a decade, non-symbolic methods have been the option of choice when explaining complex machine learning (ML) models. Unfortunately, such methods lack rigor and can mislead human decision-makers. In high-stakes uses of ML, the lack of rigor is especially problematic. One prime example of provable lack of rigor is the adoption of Shapley values in explainable artificial intelligence (XAI), with the tool SHAP being a ubiquitous example. This paper overviews the ongoing efforts towards using rigorous symbolic methods of XAI as an alternative to non-rigorous non-symbolic approaches, concretely for assigning relative feature importance.
Explore similar work Jun 23, 2026 · Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola Shapley Value Interpretable Models
May 14, 2026 · Lanxin Xiang, Liang Shi, Youhui Ye +3 Shapley Value Resampling
Aug 11, 2026 · Seungeun Lee, Joao Fonseca, Julia Stoyanovich Shapley Value
Jun 23, 2026 · cs.AI J/K move · Enter open · S save
Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, UBA · Instituto de Ciencias de la Computación (ICC), CONICET
We address the problem of explainability in machine learning models through feature attribution methods. In particular, we consider a variant of Shapley values known as Asymmetric Shapley Values (ASV), which enables the incorporation of causal knowledge into model-agnostic explanations through the use of a causal graph. We show that in certain contexts in which the computation of SHAP is
# P \#P # P -hard, the exact computation of ASV can be done in polynomial time. To extend this algorithmic result, we introduce a notion of equivalence classes over the topological orderings of the underlying causal graph, which is useful to reduce the time to compute ASV. In particular, we present a polynomial-time algorithm (in the number of equivalence classes) to compute it whenever the causal graph is a rooted directed tree. Finally, we develop an algorithm for approximating ASV in arbitrary causal DAGs which relies on a procedure to sample topological orderings uniformly at random. To implement this sampling mechanism we leverage known algorithms as well as simpler alternatives. Our experimental results demonstrate the practical viability of the proposed approach in realistic causal structures.