🤖 machine learning

Computing Actual Causes for Neural Network Predictions under Structured Causal Inputs

This paper proposes a method for computing Halpern-Pearl actual causes for neural network predictions by modeling structured input dependencies via Boolean Structural Causal Models, utilizing bound propagation and branch-and-bound techniques to achieve scalable, complete, and minimal explanations that avoid the spurious results caused by ignoring feature correlations.

Original authors: Jannick Strobel, Muqsit Azeem, Stefan Leue

Published 2026-08-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jannick Strobel, Muqsit Azeem, Stefan Leue

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to figure out why a robot made a specific choice, like deciding to deny a loan application. In the world of Artificial Intelligence, this is called "explainability." Usually, scientists look at the robot's inputs—like income, age, or debt—and ask, "Which of these numbers mattered the most?" They often treat these numbers like independent ingredients in a salad: if you change the lettuce, the tomato stays the same. But in the real world, ingredients are often mixed together. High income might cause high spending, and high spending might cause a negative bank balance. If you ignore these connections, you might blame the negative bank balance for the loan denial, missing the fact that the high spending was the real root cause. This paper tackles the tricky problem of explaining AI decisions when the inputs are tangled up in a web of cause-and-effect relationships, using a framework called "actual causality" to find the true culprits without getting lost in a maze of fake possibilities.

The researchers, Jannick Strobel, Muqsit Azeem, and Stefan Leue from the University of Konstanz, introduce a new method called CausExBaB to solve this puzzle. Think of a neural network (the AI brain) as a complex, black-box vending machine. You put in a set of ingredients (the input data), and it spits out a decision (like "High Risk" or "Low Risk"). The problem is that the ingredients aren't just sitting there; they are connected by a set of rules (a "Structural Causal Model" or SCM) that dictate how they influence each other. For example, in a loan scenario, "High Expenses" might automatically trigger "Negative Cashflow."

If you want to know why the machine said "High Risk," you can't just randomly swap out ingredients. You have to respect the rules. If you change "High Expenses" to "Low Expenses," the machine's internal logic might automatically change "Negative Cashflow" to "Positive Cashflow" as well. The authors' goal was to find the minimal actual causes: the smallest group of ingredients that, if changed (while holding other specific things constant), would flip the machine's decision. It's like asking, "What is the absolute smallest change I can make to the recipe to get a different cake?"

The challenge is that checking every possible combination of changes is like trying to find a needle in a haystack the size of a galaxy. The number of possibilities grows so fast that even supercomputers get stuck. The authors' solution is a clever search strategy called CausExBaB. Instead of checking every single needle one by one, they use a "flashlight" technique. They group huge chunks of the haystack together and use math to prove that a whole section cannot contain the needle. If the math says a group of changes will definitely still result in a "High Risk" decision, they throw that whole group away without looking inside. If the math proves a group will definitely change the decision, they mark it as a winner. Only the confusing, middle-ground groups get split up and checked in more detail. This is like using a metal detector that can tell you if a whole beach is empty of needles, saving you from digging in the sand until you find the exact spot.

The paper proves that this method is both sound (it never lies) and complete (it finds every single valid answer). In their tests, they created fake worlds with up to 28 variables and search spaces containing up to 2.3 × 10¹³ (that's 23 trillion) possible combinations. While older methods like "brute force" (checking everything) or "ILP" (using complex math solvers) gave up and timed out after 180 seconds, CausExBaB found all the answers in a fraction of that time, often under 35 seconds for the largest graphs.

One of the most interesting findings comes from a real-world case study involving the U.S. Supplemental Nutrition Assistance Program (SNAP). The team built a causal model based on the actual government regulations for who qualifies for food assistance. They found that if you ignore the rules connecting the variables (treating them as independent), you get a massive list of "causes" for why a household was flagged for a review. In fact, ignoring the connections more than doubled the number of reported causes. Worse, 14.9% of those extra causes were "spurious"—fake explanations that looked right only because the model didn't know the rules. For instance, the model might blame a specific income number, but in reality, that number was just a side effect of a different rule. By respecting the causal web, CausExBaB cut through the noise to find the true, minimal reasons.

The authors also discovered that in their synthetic tests, about 68.7% of the cases had more than one minimal cause. This means that often, there isn't just one single reason for an AI's decision; there might be two or three completely different, independent paths that lead to the same result. Finding just one of them would be like blaming a car crash only on the rain, when the driver was also speeding. CausExBaB finds all of them.

In short, this paper doesn't just give a faster way to explain AI; it gives a truer way. It shows that when inputs are connected, ignoring those connections leads to misleading, bloated, and sometimes completely wrong explanations. By using their new algorithm, we can get a clear, minimal, and mathematically guaranteed list of the real reasons behind an AI's choices, even in the most complex and tangled scenarios. The authors suggest that this approach could be a game-changer for auditing AI systems in high-stakes fields like finance and healthcare, where understanding the real cause is a matter of trust and fairness.

Technical Summary: Computing Actual Causes for Neural Network Predictions under Structured Causal Inputs

Problem Statement
Explaining neural network (NN) predictions is a central challenge in trustworthy AI. Existing explanation methods, such as feature attribution or minimal sufficient sets, typically treat input features as independent. This assumption fails when inputs exhibit structured causal dependencies (e.g., medical findings constraining diagnoses or expenses influencing cash flow). Ignoring these dependencies can lead to misleading or spurious counterfactual explanations, where root causes are obscured or changes are proposed that are impossible under the domain's causal structure. Furthermore, explanations for a single prediction are often not unique; multiple minimal sets of variables may independently cause the same outcome, yet many methods return only a single witness.

The paper addresses the problem of computing Halpern–Pearl (HP) actual causes for NN predictions where the input space is constrained by a Structural Causal Model (SCM). The goal is to identify all minimal sets of features whose values, if changed under an appropriate contingency (holding other variables fixed), would alter the prediction, while strictly respecting the causal dependencies defined by the SCM.

Methodology: CausExBaB
The authors propose CausExBaB, a sound and complete algorithm that computes all minimal HP actual causes and their minimum-cardinality witness contingencies. The approach avoids the intractability of exhaustive enumeration by combining Interval Bound Propagation (IBP) with Branch-and-Bound (BaB) techniques over regions of the input space.

Formalization: The problem is framed as finding sets of variables $\vec{X}$ (causes) and $\vec{W}$ (contingencies) satisfying the modified HP definition:
- AC1: The cause and outcome hold in the actual context.
- AC2: There exists a contingency $\vec{W}$ such that intervening on $\vec{X}$ changes the outcome.
- AC3: The cause set $\vec{X}$ is minimal.
  The SCM models feature dependencies using Boolean structural equations, while the NN maps these variables to a prediction.
Region-Based Search: Instead of enumerating individual interventions and contingencies, CausExBaB groups them into regions of SCM-consistent inputs. Variables are assigned roles: cause (fixed to counterfactual values), contingency (fixed to actual values), natural (follows structural equations), or undecided.
Bound Propagation: The algorithm propagates sound bounds through the Boolean SCM and the NN.
- SCM Propagation: Boolean structural equations are relaxed into multilinear functions (e.g., $AND(a,b) = ab$, $OR(a,b) = a+b-ab$) that are exact on Boolean inputs. This allows the computation of tight interval bounds for endogenous variables based on the roles of their parents.
- NN Propagation: These feature bounds are propagated through the NN using IBP to obtain sound output bounds $[\ell, h]$ .
Branch-and-Bound Pruning:
- If the output bound $[\ell, h]$ is entirely within the acceptance set $S$ (the outcome holds for all inputs in the region), the region is pruned (no contingency can falsify the outcome).
- If $[\ell, h]$ is entirely disjoint from $S$ (the outcome is falsified for all inputs), the region is confirmed as a witness for causality.
- If the bounds are inconclusive, the region is refined by splitting an undecided variable into two sub-regions (resolving it as either natural or contingency) and recursing.
Minimality and Completeness: The algorithm enumerates candidate cause sets by increasing size. It prunes any candidate that is a superset of an already-found cause, ensuring minimality (AC3). It continues searching after finding the first witness contingency to ensure the returned contingency has the minimum cardinality.

Key Contributions

Formalization: The authors formalize NN explanation under structured input dependencies as the computation of HP actual causes over SCM-constrained inputs.
Algorithm: They introduce CausExBaB, a sound and complete algorithm that returns all minimal actual causes and minimum-cardinality witness contingencies. It supports restricting the search to causes of size at most $k_{max}$ while preserving guarantees within that bound.
Scalability: The method scales to SCMs with up to 28 nodes and search spaces of up to $2.3 \times 10^{13}$ candidate (cause, contingency) pairs within a 180-second budget, significantly outperforming brute-force, ILP-based, and heuristic search baselines.
Empirical Validation: Through synthetic benchmarks and a case study on the U.S. Supplemental Nutrition Assistance Program (SNAP), the authors demonstrate that ignoring input dependencies inflates the number of reported causes and introduces spurious explanations.

Experimental Results

Synthetic Benchmarks: CausExBaB substantially outperforms brute-force enumeration (BF), Integer Linear Programming (ILP), and heuristic search (ACI).
- On graphs with 28 nodes, CausExBaB completes all runs with a median runtime of 34.5s, whereas BF times out at 22 nodes and ILP fails at 10 nodes.
- In 68.7% of instances, multiple minimal causes exist, highlighting the necessity of an algorithm that returns the full set rather than a single witness.
Case Study (SNAP): Applied to a model flagging households for benefit-error reviews based on federal regulations:
- CausExBaB found a median of 23 minimal causes per instance in 4.6 seconds.
- Baselines (ILP, ACI) timed out on 3/11 and 10/11 instances, respectively.
- Impact of Dependencies: Treating inputs as independent (ignoring the SCM) more than doubled the median number of reported causes (from 23 to 50). Crucially, 14.9% of the causes found under the independence assumption were spurious when verified against the true SCM, demonstrating that ignoring causal structure leads to invalid explanations.

Significance and Claims
The paper claims that CausExBaB provides formal guarantees of completeness (finding all minimal causes), minimality (of both causes and contingencies), and soundness (all reported causes are valid under the SCM). It argues that existing methods either lack these guarantees or fail to scale to realistic problem sizes. The work highlights that accounting for structured causal dependencies is not merely an optimization but a necessity for correctness, as ignoring them can produce a majority of explanations that are either non-minimal or entirely spurious. The authors position this as a step toward trustworthy AI where explanations are grounded in the actual causal mechanisms of the domain rather than statistical correlations alone.

Technical Summary: Computing Actual Causes for Neural Network Predictions under Structured Causal Inputs

More like this