Evaluation of Black-Box XAI Approaches for Predictors of Values of Boolean Formulae

Stav Armoni-Friedmann, Hana Chockler, David A. Kelly · 2025

Read Evaluation of Black-Box XAI Approaches for Predictors of Values of Boolean Formulae by Stav Armoni-Friedmann, Hana Chockler, David A. Kelly (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-09982.txt.

Introduction

Stav Armoni-Friedmann and 2 co-authors grade explanation tools for AI in a 2025 paper where the right answer about importance can be computed exactly. Judging an explanation is usually guesswork, since nobody knows which inputs truly drove a prediction. Their test bed sidesteps that fog: models predict values of Boolean formulas, and actual causality supplies a formal yardstick for how much each variable should matter.

Leading black-box explainers are scored against that yardstick, and the authors add a new tool, B-ReX, grown from an earlier system called ReX. On a large suite of random ten-variable formulas B-ReX tracked the causal truth far more closely than its rivals, with a small average divergence. The study gives the explanation field a rare ground truth to argue from.

Catalog record

CREATORStav Armoni-Friedmann, Hana Chockler, David A. Kelly
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-09982

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Evaluation of Black-Box XAI Approaches for Predictors of Values of Boolean Formulae Stav Armoni-Friedmann, Hana Chockler, David A. Kelly Abstract Evaluating explainable AI (XAI) approaches is a challenging task in general, due to the subjectivity of explanations. In this paper, we focus on tabular data and the specific use case of AI models predicting the values of Boolean functions. We extend the previous work in this domain by proposing a formal and precise measure of importance of variables based on actual causality, and we evaluate state-of-the-art XAI tools against this measure. We also present a novel XAI tool b - r e x , based on the existing tool r e x , and demonstrate that it is superior to other black-box XAI tools on a large-scale benchmark. Specifically, b - r e x achieves a Jensen-Shannon divergence of 0.072 ± 0.012 0.072\pm 0.012 on random 10 10 -valued Boolean formulae. † † paperid: 1 1 Introduction AI models are now a primary building block of automated decision support systems. The opacity of some of these models ( e.g. , neural networks) creates demand for explainability techniques, which attempt to provide insight into why a particular input yields a particular observed output. Beyond increasing a user’s confidence in the output, and hence also their trust in the AI model, these insights help to uncover subtle errors that are not detectable from the output alone [ 6 ] . Despite a growing body of work in explainable AI (XAI), evaluating different approaches remains a difficult task due to often very different definition of explanation employed by different XAI tools. Current comparative methods, such as insertion/deletion curves [ 23 ] , sensitivity and infidelity [ 35 ] , and user studies [ 28 ] often work best on a particular subset of XAI approaches. Although these metrics are informative, they require principled inspection to draw conclusions and often fail to capture non-linear features of explanations. As a result of these challenges, evaluating explainability techniques remains an open problem. Tritscher et al. 2020 aim to bridge this gap using synthetic data which have an unambiguous ‘ground truth’; that is, there is a known (and unique) set of features per example which should be included in an explanation. Specifically, they design synthetic datasets that reflect truth tables of hand-crafted Boolean formulae. A feature is considered relevant if it is decisive for the value of its parent node in a formula. For example, in the case of (True \wedge False), it is the ‘False’ which is relevant , as changing its value changes the value of the entire formula. To test XAI tools using these definitions, they train a neural network to 100\% accuracy for each formula, and extract explanations, using various tools, for the outputs of these networks. They then report the proportion of times the result had a ‘perfect’ overlap with the relevant features of each assignment. They only consider a small number of features, so perfection of overlap is limited to that number (the top-k overlap). Reassuringly, most XAI tools performed perfectly on linear formula: less reassuringly, they did not work as well upon the introduction of non-linear operators. Though informative, there remain a number of issues with the importance definition proposed, and methodology employed. Consider the case of (True \lor True); here, either side of the truth an assignment can be changed without affecting the formula’s overall value. However, we argue that they both remain important to the overall classification. Consider also a similar example (False \lor False); here a change to either assignment would change the formula’s overall value. We argue that all values in the above examples are relevant. Furthermore, the use of only a few hand-crafted formulae may introduce bias into results. In this paper, we address the key limitations of the approach in Tritscher et al. 2020 , reproducing and extending their original experiment. Instead of their binary definition of feature relevance, we use the notion of the degree of responsibility Chockler and Halpern 2004 , which is grounded in the theory of actual causality Halpern 2019 . While they count top-k overlap, we measure Jensen Shannon (JS-) divergence Lin 1991 : a symmetrical variant of the Kullback-Liebler divergence Kullback and Leibler 1951 which penalizes mismatches, not just ranking mismatches. In addition, where they use a few hand-crafted formulae – one linear, one nonlinear – we use a large set of randomly generated formulae, making our evaluation more reliable. We present a linear-time algorithm for computing the precise degree of responsibility for read-once Boolean formulae. Unfortunately, the exact computation is not as efficient in the general case, due to the intractability of the problem. We compute the ground-truth responsibilities of features in the value of the formulae in our benchmark set, using the efficient algorithm for read-once formulae and a brute-force exponential-time approach in the general case. The ground truth is used for evaluation. We then present a novel black-box algorithm, b - r e x , based on the existing tool r e x Chockler et al. 2024 . b - r e x is similar to r e x in that it iteratively refines the search space to calculate approximate causal responsibility. However, the domain of application affects the algorithm: r e x is suited to explaining image classifiers, while b - r e x explains tabular data classifiers, and specifically, Boolean formulae classifiers, which implies important differences between the algorithms. Our main contributions are as follows: 1. An exact, ground-truth based, quality metric for evaluating XAI tools for Boolean formulae classifiers. 2. An approximate black-box algorithm, b - r e x , based on the existing r e x tool. 3. A quantitative comparison of popular XAI methods measuring JS-divergence against our exact algorithms; b - r e x performs significantly better than all other tools. The rest of the paper is organized as follows: Section 2 presents related work; Section 3 reviews definitions of causal models and of responsibility; Section 4 details algorithms derived from definitions of responsibility in Boolean formulae; Section 5 presents b - r e x , and Section 6 analyses the experimental results. 2 Related Work There is a large body of work on algorithms for computing an explanation for a given output of a classifier. They can be largely grouped into white-box and black-box methods. In this context, white-box refers to methods which require access to the underlying model. Conversely, black-box methods interact exclusively with a models interface and observer it’s behavior. White-box methods frequently use variations on propagation-based explanation methods to back-propagate a model’s decision to the input layer to determine the weight of each input feature for the decision Springenberg et al. 2015 ; Sundararajan et al. 2017 ; Bach et al. 2015 ; Shrikumar et al. 2017 ; Nam et al. 2020 . g rad c am, a white-box technique which has spawned many variants, only needs one backward pass and propagates the class-specific gradient into the final convolutional layer of a DNN to coarsely highlight important regions of an input image Selvaraju et al. 2017 . Perturbation-based approaches introduce perturbations to the input space. Perturbation methods are typically found in black-box explanation tools. shap

Read the complete text