Pith. sign in

REVIEW 4 major objections 5 minor 36 references

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

T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A formal causality-based benchmark finds black-box B-ReX best approximates true feature importance on Boolean formulae.

desk verdict Potentially useful XAI evaluation framework, but the printed ground-truth algorithm contradicts its own responsibility definition on basic gates; the empirical claims rest on that faulty yardstick. read the letter →

arxiv 2509.09982 v1 pith:IQJL7NBJ submitted 2025-09-12 cs.AI

Stav Armoni-Friedmann , Hana Chockler , David A. Kelly This is my paper · ORCID
classification cs.AI
keywords XAIevaluationcausalresponsibilityBooleanformulaeblack-boxexplainabilityJensen-Shannondivergenceactualcausalityfeatureimportanceread-once
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that the degree of causal responsibility, a measure from actual-causality theory, is a defensible ground truth for feature importance when explaining classifiers of Boolean formulae. It provides exact algorithms for this ground truth — linear-time for read-once formulae, brute-force otherwise — and uses it to benchmark popular XAI tools. It also introduces B-ReX, a black-box explainer that recursively partitions the input space and approximates responsibility from model outputs alone. On randomly generated Boolean formulae, B-ReX reports the lowest Jensen-Shannon divergence from ground truth among all tested tools, with a divergence of 0.072±0.012 on non-monotonic formulae of arity 10. The paper's claim is that objective evaluation of feature-importance explainers is achievable in this setting and that black-box methods can outperform gradient-based or game-theoretic ones on non-monotonic functions.

What carries the argument

The I-operator, which labels each gate of the formula's parse tree as 'Both', 'Either', 'Left', 'Right', or 'Pass' according to which child subtrees are causally relevant; Algorithm 1 (DEPENDS) computes the minimal number of leaf flips needed to change each gate's value; Algorithm 2 (RESPONSIBILITY) propagates an accumulator down the tree and assigns each leaf responsibility 1/(1+ctx). B-ReX's recursive partition-and-refine loop replaces the tree structure with a black-box search over subsets of input blocks.

What would settle it

Evaluate a two-variable formula x1 ∧ x2 on the assignment True, True. Definition 5 gives each variable responsibility 1 (flipping either variable alone changes the output, so the witness is empty). Algorithm 2 as printed classifies the AND gate as 'Both' and returns responsibility 1/2 for each variable. Running the published pseudocode on this case and comparing the output to Definition 5 settles whether the ground truth is correct.

Watch

Extended reading notes

Core claim

The central discovery is a way to make XAI evaluation objective for Boolean-formula classifiers: ground truth is the degree of responsibility, defined as 1/(k+1) where k is the size of the smallest witness making a variable a singleton actual cause of the output. The paper gives a two-pass linear-time algorithm that it claims computes this degree for read-once formulae, and uses brute-force truth-table enumeration for general formulae. Against this ground truth, the paper's B-ReX algorithm — which refines responsibility estimates by recursively partitioning inputs, using only oracle access to the model — achieves a Jensen-Shannon divergence of 0.072 ± 0.012 on 10-variable non-monotonic rando

Load-bearing premise

The whole benchmark rests on the exact ground-truth algorithm returning the true degree of responsibility for every assignment; in particular, the gate-classification rules in the paper must agree with the formal witness-based Definition 5, which requires checking singleton flips before concluding both children are jointly responsible.

Editorial extensions

If this is right

  • If the ground-truth computation is correct, the JS-divergence numbers give an objective ranking of XAI tools on Boolean-formula classifiers.
  • B-ReX's superiority on non-monotonic formulae indicates that black-box perturbation search can beat gradient-based and Shapley-based methods when the underlying function is not monotone.
  • The linear-time exact algorithm extends the benchmark to read-once formulae with many variables, where brute-force enumeration would be infeasible.
  • The benchmark can be reused for any new explainer: run it on the random formula suites and compare JSD to the published ground-truth values.
  • The paper's setup with trained neural networks at 100% accuracy suggests the results transfer from formula semantics to learned classifiers, not just symbolic evaluation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The printed I-operator conditions select 'Both' for gates such as AND(True, True), even though each input alone is a but-for cause with an empty witness; under Definition 5 those inputs should receive responsibility 1, while Algorithm 2 as printed gives 1/2. If the implementation follows the pseudocode, the ground truth is mis-computed for this class of assignments, which would shift all JSD compa
  • The paper's causal-independence assumption is acknowledged to be an approximation for non-Boolean tabular data; the benchmark's usefulness outside Boolean formulae depends on how much correlated features distort responsibility estimates.
  • A natural testable extension is to compute ground truth by exhaustive search of all witnesses for small formulae and compare with Algorithm 2's output; the discrepancy, if it exists, would pinpoint how often the 'Both' precedence matters.
  • B-ReX's weighted recursive partitioning could be applied to discrete non-Boolean domains like categorical features with the same oracle-only interface, giving a black-box explainer that does not rely on gradients or game-theoretic value aggregation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes a formal ground truth for evaluating XAI methods on classifiers of Boolean formulae, based on the degree of causal responsibility (Definition 5). It presents exact algorithms for read-once formulae (Algorithms 1 and 2) and a brute-force method for general formulae, plus a new black-box explainer B-ReX (Algorithm 3) that recursively partitions inputs. The evaluation compares B-ReX with several existing explainers on random monotonic and non-monotonic formulae, reporting Jensen–Shannon divergence to the ground truth; the central claim is that B-ReX achieves the lowest JSD (e.g., 0.072 ± 0.012 on arity-10 non-monotonic formulae) and outperforms all other tools.

Significance. If correct, this would be a valuable contribution: it uses the established causal notion of responsibility as an objective yardstick, provides a linear-time exact computation for read-once formulae, and supplies a model-agnostic explainer that is empirically superior on a diverse benchmark. The use of JS divergence rather than top-k overlap is a methodological improvement. However, the correctness of the entire evaluation rests on the exact ground-truth algorithm; as detailed below, that algorithm is flawed for a class of elementary gates, so the reported numbers are not reliable as they stand. The underlying approach is promising and the flaw appears fixable, but the paper currently does not establish its central empirical claim.

major comments (4)
  1. [§4.1, I(gi) definition and Algorithm 2] The I-operator's Both condition is too weak and its cases are not mutually exclusive. For gi = gl ∧ gr with gl=gr=True, the output is True. The Both condition ¬gl∘¬gr ≠ φ holds (False∧False = False ≠ True), and the Either condition also holds (False∧True = False ≠ True and True∧False = False ≠ True). Since Both is listed first, Algorithm 2 adds deps(sibling) to ctx for each child, giving each leaf responsibility 1/2. Definition 5, however, gives an empty witness for each leaf: flipping either child alone flips the output, so k=0 and responsibility is 1. The same misclassification occurs for OR(False,False). Thus Algorithms 1–2 do not compute the degree of responsibility defined in Definition 5 for read-once formulae containing these gates. Theorem 2, asserted without proof, is therefore not established. Please correct the conditions (e.g., require Both to mean that neither single flip ch
  2. [§6, Tables 3–4 and Figure 2] Because the ground truth is wrong for a class of assignments, the JSD values reported for every explainer, including B-ReX, are computed against an invalid measure. It is impossible to determine from the manuscript whether the experiments used the printed pseudocode or an implementation that deviates from it, since no code is released and Theorem 2 is not proved. The headline claim that B-ReX outperforms all other tools is therefore not supported by the current evidence. Please rerun the evaluation with the corrected ground truth and release the implementation, or at least an exact specification of the algorithm used.
  3. [§4.1, Algorithm 1; §4.2] Algorithm 1 assumes every internal node has two children, but the text allows unary NOT gates (I(gi)=Pass, deps(gi)=dj). The pseudocode should handle the unary case explicitly. Additionally, the brute-force general algorithm in §4.2 is not described; please specify how Definition 5 is applied with witness enumeration and prove that the result matches the definition, since this algorithm also feeds the ground truth for non-read-once formulae.
  4. [§5, Algorithm 3 and §6.1] B-ReX depends on a parameter for the number of partitions (called b in the text and m in the partitioning description). The paper neither states the value used in the reported experiments nor studies sensitivity to this parameter. Since the central claim is empirical superiority of B-ReX, the choice of this parameter and its impact on JSD should be documented and justified.
minor comments (5)
  1. [Abstract] 'random 10-valued Boolean formulae' should probably read 'random 10-variable Boolean formulae'.
  2. [§3, Definition 4] The notation 'a variable X∈X and its value x∈x' is confusing because X is used for both the set and an element. Suggest using V or a different symbol for the variable set.
  3. [§4.1] The condition '≠ φ' in the I-operator definition is ambiguous; it should be '≠ the current value of gi' or '≠ v(gi)'.
  4. [Table 5] Table 5 is garbled: the header row and the B-ReX row appear to have missing spaces or values (e.g., 'B-ReX0.992 0.986 10.638'). Please clean up the formatting.
  5. [§2] Typo: 'observer it’s behavior' should be 'observe its behavior'.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: B-ReX is scored against an independently computed responsibility ground truth; self-citations are not load-bearing.

full rationale

The derivation chain is self-contained. Definition 5 (simplified responsibility) is stated as the formal ground-truth measure; Algorithms 1–2 compute it from the syntax and assignment of the Boolean formula, and Section 4.2 uses brute-force truth-table enumeration for general formulae. B-ReX (Algorithm 3) is a black-box approximator that only queries the trained model's output; no B-ReX output or fitted parameter enters the ground-truth computation. Thus the JSD comparison in Tables 3–4 is not equivalent to B-ReX's inputs by construction. The self-citations to [5] and [6] introduce the witness-based definition and the ReX lineage, but the definition is restated in the paper and the equivalence to actual causality is independently supported by Beckers [3]; they are transparent provenance, not load-bearing circularity. One flagged, non-circular risk: Theorem 2 ('The proof is, again, by induction on the structure of φ') gives no rigorous proof, and the printed I-operator in Section 4.1 selects 'Both' for AND(True, True) because ¬gl∧¬gr ≠ φ, which makes Algorithm 2 return 1/2 for each input while Definition 5's empty witness gives responsibility 1. If the implementation follows the pseudocode, the ground truth is incorrect for a class of read-once formulas and the headline comparison would be invalid; this is a correctness gap, not a circular equivalence.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim rests on a chosen philosophical definition of explanation (causal responsibility), an independence assumption, and the correctness of the exact responsibility algorithm. The only tunable method parameter is the partition count in B-ReX. No new physical or mathematical entities are postulated.

free parameters (1)
  • Number of partitions m in B-ReX = not specified
    The partition count and the l1-weighted probabilistic selection are hand-chosen; no sensitivity analysis is reported. Location: Section 5, Algorithm 3.
assumptions (5)
  • domain assumption The modified Halpern-Pearl definition of actual causality is the correct gold standard for variable importance in explanations.
    The entire evaluation uses causal responsibility as ground truth. This is a philosophical choice, not a mathematical theorem. Location: Sections 1-3.
  • domain assumption Feature variables in the Boolean formula are causally independent, so the causal model has depth 2 and Definition 4 is equivalent to Definition 1.
    The paper explicitly notes this might not hold for other data types. Location: Section 3.
  • ad hoc to paper For read-once formulas, the I-operator classification and Algorithms 1-2 correctly compute the degree of responsibility of Definition 5.
    This is the suspect step: the printed conditions for I(gi) select 'Both' for gates where flipping a single child already changes the output, which contradicts Definition 5. Location: Section 4.1.
  • domain assumption Input variables are binary and the classifier accurately represents the Boolean function (trained to 0% loss).
    They train MLPs to 100% accuracy; if the model were inaccurate, explanations would target a different function. Location: Section 6.
  • domain assumption Masking variables to 'Unassigned' follows strong Kleene logic (K3), which defines the semantics of partial assignments in B-ReX.
    The three-valued semantics are a modeling choice for the black-box perturbation. Location: Section 6.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Evaluation of Black-Box XAI Approaches for Predictors of Values of Boolean Formulae." pith.science (2026). https://pith.science/paper/IQJL7NBJ

@misc{pith2026250909982,
  author       = {Pith},
  title        = {Pith review of: Evaluation of Black-Box XAI Approaches for Predictors of Values of Boolean Formulae},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IQJL7NBJ}},
  note         = {Machine review of arXiv:2509.09982}
}
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-ReX, based on the existing tool ReX, and demonstrate that it is superior to other black-box XAI tools on a large-scale benchmark. Specifically, B-ReX achieves a Jensen-Shannon divergence of 0.072 $\pm$ 0.012 on random 10-valued Boolean formulae

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 3 linked inside Pith

  1. [1]

    S. Bach, A. Binder, G. Montavon, F. Klauschen, K.-R. Müller, and W. Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation.PLOS One, 10(7), 2015. 2

    2015

  2. [2]

    S. Beckers. Causal sufficiency and actual causation.Journal of Philo- sophical Logic, 50:1341–1374, 2021. 2

    2021

  3. [3]

    S. Beckers. Causal explanations and XAI. In1st Conference on Causal Learning and Reasoning, CLeaR 2022, Sequoia Conference Center, Eu- reka, CA, USA, 11-13 April, 2022, volume 177 ofProceedings of Ma- chine Learning Research, pages 90–109. PMLR, 2022. 3

    2022

  4. [4]

    Chockler and J

    H. Chockler and J. Y . Halpern. Responsibility and blame: A structural- model approach.J. Artif. Intell. Res., 22:93–115, 2004. 1

    2004

  5. [5]

    Chockler and J

    H. Chockler and J. Y . Halpern. Explaining image classifiers, 2024. 2, 3

    2024

  6. [6]

    Chockler, D

    H. Chockler, D. A. Kelly, D. Kroening, and Y . Sun. Causal explanations for image classifiers, 2024. URL https://arxiv.org/abs/2411.08875. 1, 2, 3

    arXiv 2024

  7. [7]

    Darwiche and A

    A. Darwiche and A. Hirth. On the (complete) reasons behind decisions. J. Log. Lang. Inf., 32(1):63–88, 2023. 2

    2023

  8. [8]

    Eiter and T

    T. Eiter and T. Lukasiewicz. Causes and explanations in the structural- model approach: Tractable cases.Artificial Intelligence, 170:542–580,

Show all 36 references
  1. [9]

    Glymour and F

    C. Glymour and F. Wimberly. Actual causes and thought experiments. In J. Campbell, M. O’Rourke, and H. Silverstein, editors,Causation and Explanation, pages 43–67. MIT Press, Cambridge, MA, 2007. 2

    2007

  2. [10]

    N. Hall. Structural equations and causation.Philosophical Studies, 132: 109–136, 2007. 2

    2007

  3. [11]

    J. Y . Halpern.Actual Causality. The MIT Press, 2019. 1, 2

    2019

  4. [12]

    J. Y . Halpern and J. Pearl. Causes and explanations: a structural-model approach. Part I: causes.British Journal for Philosophy of Science, 56 (4):843–887, 2005. 2

    2005

  5. [13]

    Hitchcock

    C. Hitchcock. The intransitivity of causation revealed in equations and graphs.Journal of Philosophy, XCVIII(6):273–299, 2001. 2

    2001

  6. [14]

    Hitchcock

    C. Hitchcock. Prevention, preemption, and the principle of sufficient reason.Philosophical Review, 116:495–532, 2007. 2

    2007

  7. [15]

    Ibrahim, S

    A. Ibrahim, S. Rehwald, and A. Pretschner. Efficiently checking actual causality with SAT solving.CoRR, abs/1904.13101, 2019. URL http: //arxiv.org/abs/1904.13101. 2

    1904 arXiv

  8. [16]

    Ignatiev, N

    A. Ignatiev, N. Narodytska, and J. Marques-Silva. Abduction-based explanations for machine learning models. InThe Thirty-Third AAAI Conference on Artificial Intelligence, AAAI, pages 1511–1519. AAAI Press, 2019. 2

    2019

  9. [17]

    Kokhlikyan, V

    N. Kokhlikyan, V . Miglani, M. Martin, E. Wang, B. Alsallakh, J. Reynolds, A. Melnikov, N. Kliushkina, C. Araya, S. Yan, and O. Reblitz-Richardson. Captum: A unified and generic model inter- pretability library for pytorch, 2020. URL https://arxiv.org/abs/2009. 07896. 6

    2020

  10. [18]

    Kullback and R

    S. Kullback and R. A. Leibler. On Information and Sufficiency.The Annals of Mathematical Statistics, 22(1):79 – 86, 1951. doi: 10.1214/ aoms/1177729694. URL https://doi.org/10.1214/aoms/1177729694. 1

    1951

  11. [19]

    J. Lin. Divergence measures based on the shannon entropy.IEEE Transactions on Information Theory, 37:145–151, 1991. doi: 10.1109/ 18.61115. 1, 5

    1991

  12. [20]

    S. M. Lundberg and S.-I. Lee. A unified approach to interpreting model predictions. InAdvances in Neural Information Processing Systems (NeurIPS), volume 30, pages 4765–4774, 2017. 2

    2017

  13. [21]

    Marques-Silva and A

    J. Marques-Silva and A. Ignatiev. Delivering trustworthy AI through formal XAI. InThirty-Sixth AAAI Conference on Artificial Intelligence, AAAI, pages 12342–12350. AAAI Press, 2022. 2

    2022

  14. [22]

    W.-J. Nam, S. Gur, J. Choi, L. Wolf, and S.-W. Lee. Relative attributing propagation: Interpreting the comparative contributions of individual units in deep neural networks. InAAAI Conference on Artificial Intelli- gence, volume 34, pages 2501–2508, 2020. 2

    2020

  15. [23]

    Petsiuk, A

    V . Petsiuk, A. Das, and K. Saenko. RISE: randomized input sampling for explanation of black-box models. InBritish Machine Vision Conference (BMVC). BMV A Press, 2018. 1

    2018

  16. [24]

    Priest.An Introduction to Non-Classical Logic: From If to Is

    G. Priest.An Introduction to Non-Classical Logic: From If to Is. Cam- bridge University Press, 2 edition, 2008. 6

    2008

  17. [25]

    Why should I trust you?

    M. T. Ribeiro, S. Singh, and C. Guestrin. “Why should I trust you?” Explaining the predictions of any classifier. InKnowledge Discovery and Data Mining (KDD), pages 1135–1144. ACM, 2016. 2

    2016

  18. [26]

    M. T. Ribeiro, S. Singh, and C. Guestrin. Anchors: High-precision model- agnostic explanations. InProceedings of the Thirty-Second AAAI Con- ference on Artificial Intelligence, (AAAI-18), pages 1527–1535. AAAI Press, 2018. 2

    2018

  19. [27]

    R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra. Grad-CAM: Visual explanations from deep networks via gradient-based localization. InInternational Conference on Computer Vision (ICCV), pages 618–626. IEEE, 2017. 2

    2017

  20. [28]

    Shitole, F

    V . Shitole, F. Li, M. Kahng, P. Tadepalli, and A. Fern. One explanation is not enough: Structured attention graphs for image classification. In Neural Information Processing Systems (NeurIPS), pages 11352–11363,

  21. [29]

    Shrikumar, P

    A. Shrikumar, P. Greenside, and A. Kundaje. Learning important features through propagating activation differences. InInternational Conference on Machine Learning (ICML), volume 70, pages 3145–3153. PMLR,

  22. [30]

    J. T. Springenberg, A. Dosovitskiy, T. Brox, and M. A. Riedmiller. Striv- ing for simplicity: The all convolutional net. InICLR (Workshop Track),

  23. [31]

    Sundararajan, A

    M. Sundararajan, A. Taly, and Q. Yan. Axiomatic attribution for deep networks. InInternational Conference on Machine Learning, pages 3319–3328. PMLR, 2017. 2

    2017

  24. [32]

    Tritscher, M

    J. Tritscher, M. Ring, D. Schlr, L. Hettinger, and A. Hotho. Evaluation of post-hoc xai approaches through synthetic tabular data. InFoundations of Intelligent Systems, pages 422–430. Springer International Publishing,

  25. [33]

    B. Weslake. A partial theory of actual causation.British Journal for the Philosophy of Science, 2015. To appear. 2

    2015

  26. [34]

    Woodward.Making Things Happen: A Theory of Causal Explanation

    J. Woodward.Making Things Happen: A Theory of Causal Explanation. Oxford University Press, Oxford, U.K., 2003. 2

    2003

  27. [35]

    Yeh, C.-Y

    C.-K. Yeh, C.-Y . Hsieh, A. Suggala, D. Inouye, and P. Ravikumar. On the (in)fidelity and sensitivity of explanations. 12 2019. 1

    2019

  28. [2015]

    URL http://arxiv.org/abs/1412.6806. 2

    arXiv

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.