🤖 machine learning

Provably Explaining Neural Additive Models

This paper introduces an efficient, model-specific algorithm for Neural Additive Models (NAMs) that generates provably cardinally-minimal explanations with logarithmic query complexity, overcoming the computational intractability of standard neural networks while outperforming existing methods in both explanation size and computation time.

Original authors: Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Volkan Şahin, Jan Kretinsky, Matthias Althoff, Guy Katz

Published 2026-02-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Volkan Şahin, Jan Kretinsky, Matthias Althoff, Guy Katz

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 have a very smart, but mysterious, black box that makes important decisions—like approving a loan, diagnosing a disease, or identifying a tumor. You ask the box, "Why did you say yes?"

Usually, the box gives you a long, confusing list of reasons: "Well, your income was high, your age was 35, you live in zip code 90210, you have a dog, and you bought coffee on Tuesday." It's hard to know which of those 100+ factors actually mattered.

In the world of Artificial Intelligence, we call these lists explanations. The goal is to find the smallest, most essential list of reasons that, if you kept them the same, the box would still give the same answer, no matter how you changed the other 95 factors.

The Problem: The "Needle in a Haystack" Nightmare

For standard AI models (the kind used in most apps today), finding this tiny, perfect list is a computational nightmare.

The Haystack: Imagine the model has 100 features. To find the perfect list, a computer has to check every possible combination of features.
The Math: With 100 features, there are more combinations than there are atoms in the universe. Even the fastest supercomputers would take longer than the age of the universe to check them all.
The Result: Current methods usually guess. They say, "Here is a list of 10 things that probably explains it." But they can't prove it. In safety-critical fields (like medicine or aviation), "probably" isn't good enough. You need a guarantee.

The Solution: The "Neural Additive Model" (NAM)

The authors of this paper focused on a special type of AI called a Neural Additive Model (NAM).

The Analogy: The Orchestra vs. The Soloist

Standard AI is like a rock band where everyone plays at once. The guitar, drums, and vocals are all mixed together. It's hard to hear what the drummer is doing without the rest of the band.
NAMs are like a classical orchestra where each musician plays a solo, and then a conductor simply adds up their volumes.
- Feature 1 (Income) plays a solo.
- Feature 2 (Age) plays a solo.
- Feature 3 (Debt) plays a solo.
- The final decision is just the sum of these solos.

Because the math is "additive" (just adding things up), the authors realized they could cheat the "Needle in a Haystack" problem.

The Magic Trick: How They Did It

The authors created a two-step algorithm that acts like a super-smart librarian organizing books.

Step 1: The "Importance Sort" (Parallel Processing)
Instead of checking every combination, they look at each "solo" (feature) individually.

They ask: "If I wiggle this feature as much as possible, how much does it shake the final decision?"
They do this for every feature at the same time (using many computer processors in parallel).
They rank the features from "Most Shaky" (Most Important) to "Least Shaky" (Least Important).
Analogy: Imagine you have 100 keys. Instead of trying every key in the lock, you weigh them. You know the heavy ones are more likely to be the right key. You sort them by weight.

Step 2: The "Binary Search" (The Efficient Hunt)
Now that the features are sorted by importance, they don't need to check every combination. They use a Binary Search.

Analogy: You have a phone book sorted alphabetically. To find "Smith," you don't start at page 1. You open the middle. Is "Smith" before or after? You jump to the middle of that half. You keep halving the search space until you find the exact spot.
The algorithm does this with the features. It asks: "If I keep the top 50% of the most important features, is that enough?"
- If yes, try the top 25%.
- If no, try the top 75%.
This allows them to find the absolute smallest list of features in a tiny fraction of the time.

Why This Matters

Proof, Not Guessing: Unlike other methods that guess, this method proves mathematically that the list of features is sufficient. If you change any other feature, the decision won't change.
Speed: They went from a task that would take forever (exponential time) to a task that takes seconds (logarithmic time).
Smaller Explanations: Their method found explanations that were significantly smaller (fewer features) than previous methods.
- Example: On a credit dataset, old methods said, "You need 16 factors to explain this." The new method said, "Actually, only 4 factors were truly necessary."

The "Sampling" Trap

The paper also warns against a common shortcut: Sampling.

The Trap: Some people try to explain AI by just testing random inputs (like throwing darts at a board). "I threw 1,000 darts, and the decision stayed the same, so I'm good!"
The Danger: The AI might have a tiny, hidden "trap" (a sharp peak or valley) that the darts missed. The paper shows that sampling can be dangerously misleading, especially in safety-critical situations. Their method checks the entire range mathematically, so no hidden traps are missed.

The Bottom Line

This paper is a breakthrough because it takes a problem that was previously considered impossible to solve perfectly for complex AI models and solved it for a specific, highly useful type of model (NAMs).

It's like going from trying to find a specific grain of sand on a beach by looking at every grain one by one, to having a magnet that instantly pulls out only the sand that matters. This makes AI not just smarter, but trustworthy and explainable in the real world.

1. Problem Statement

The paper addresses the challenge of generating provable, cardinally-minimal sufficient explanations for neural network predictions.

Context: While post-hoc explanation methods (e.g., LIME, SHAP) exist, they are often heuristic and lack formal guarantees. Formal methods using neural network verification can provide guarantees but are computationally intractable for standard neural networks.
The Core Difficulty: Finding a cardinally-minimal explanation (the smallest subset of features $S$ such that fixing $S$ guarantees the prediction remains unchanged, regardless of how other features vary within a perturbation radius) is NP-hard. For general neural networks, this requires an exponential number of verification queries ( $O(2^n)$ ), making it infeasible even for small models.
Current Limitations: Existing provable methods typically settle for subset-minimal explanations (where no proper subset is sufficient), which are easier to compute ( $O(n)$ queries) but often larger and less informative than cardinally-minimal ones. Furthermore, standard sampling-based interpretations for interpretable models like Neural Additive Models (NAMs) can be misleading due to missed extrema in continuous functions.

2. Methodology

The authors propose a novel, model-specific algorithm for Neural Additive Models (NAMs). NAMs are defined as $f(x) = \beta_0 + \sum_{i=1}^k f_i(x_i)$ , where each $f_i$ is a univariate neural network. The algorithm exploits this additive structure to reduce complexity from exponential to logarithmic.

The approach consists of two main stages:

Stage 1: Parallel Interval Importance Sorting

Goal: Establish a total ordering of features based on their "importance" (i.e., the magnitude of their potential impact on flipping the prediction).
Mechanism:
- For each feature $i$ , the algorithm computes bounds $[l_i, u_i]$ on the minimum (or maximum) value of the univariate component $f_i(x_i)$ within the perturbation region $B_{\epsilon_p}(x_i)$ .
- This is done using parallelized binary search with a neural network verifier (specifically $\alpha$ - $\beta$ -CROWN) on each univariate component $f_i$ .
- The algorithm iteratively refines these bounds until they are non-overlapping, allowing for a strict sorting of features by their potential to change the output.
Complexity: This stage requires $O(\frac{n}{p} \log(\frac{\text{range}}{\xi}))$ parallel verification queries, where $p$ is the number of processors and $\xi$ is the separation gap between feature importance values.

Stage 2: Logarithmic Feature Selection

Goal: Identify the cardinally-minimal sufficient subset using the sorted order from Stage 1.
Mechanism:
- Unlike general networks where feature order is arbitrary, the sorted order in NAMs guarantees that if a subset of the top- $k$ features is sufficient, then any subset containing them is also sufficient.
- The algorithm performs a binary search over the sorted list of features to find the smallest $k$ such that the set of the top $k$ features constitutes a sufficient explanation.
- It verifies sufficiency for the candidate set $\{F[1], \dots, F[m]\}$ and adjusts the search range accordingly.
Complexity: This stage requires only $O(\log n)$ verification queries on the full model $f$ .

3. Key Contributions

First Provable Cardinally-Minimal Explanations for NAMs: The paper presents the first algorithm capable of generating explanations that are both provably sufficient and cardinally-minimal for Neural Additive Models.
Complexity Reduction: The method reduces the worst-case complexity of finding cardinally-minimal explanations from exponential ( $O(2^n)$ ) for general networks to logarithmic ( $O(\log n)$ ) for NAMs (after a parallel preprocessing step).
Superiority over Subset-Minimal Methods: The algorithm outperforms existing methods designed for the weaker "subset-minimal" task. It produces significantly smaller explanations (closer to the global optimum) and does so faster, despite solving a harder problem.
Formal Guarantees vs. Sampling: The authors demonstrate that standard sampling-based interpretations for NAMs can yield misleading results (failing to detect extrema that flip the classification), whereas their formal verification approach guarantees correctness.
Theoretical Bounds: The paper provides formal proofs (Propositions 1-4, Theorems 1-2) establishing the correctness of the sorting logic and the query complexity bounds, including analysis of edge cases where feature importance gaps ( $\xi_i$ ) are small.

4. Experimental Results

The authors evaluated their algorithm on three real-world datasets (Breast Cancer, CREDIT, FICO HELOC) using the state-of-the-art verifier $\alpha$ - $\beta$ -CROWN.

Explanation Size: The proposed method generated significantly smaller explanations than baseline greedy subset-minimal approaches.
- Example (Breast Cancer): Ours (4.00) vs. Lexicographic (16.58) vs. Sensitivity (16.27).
- Example (CREDIT): Ours (3.76) vs. Lexicographic (12.42).
Computation Time: Despite solving a harder task, the new method was substantially faster.
- Example (Breast Cancer): Ours (35.6s) vs. Lexicographic (634.9s).
- Example (CREDIT): Ours (132.7s) vs. Lexicographic (473.6s).
Sampling Comparison: When compared to purely sampling-based methods, the proposed method achieved 100% sufficiency (verified by the verifier), whereas sampling-based methods achieved only ~25-31% sufficiency, often producing explanations that failed under rigorous verification.
Scalability: The parallelization of the sorting phase (Stage 1) showed significant speedups with increased CPU cores, while the binary search phase (Stage 2) remained efficient regardless of parallelization.

5. Significance

Bridging the Gap: This work bridges the gap between the need for interpretability (via NAMs) and the need for safety guarantees (via formal verification). It proves that specific architectural constraints (additivity) can make formally verifiable explanations tractable at scale.
Safety-Critical Applications: By providing explanations that are provably minimal and sufficient, the method is highly valuable for safety-critical domains (e.g., healthcare, finance) where heuristic explanations are insufficient and sampling methods are unreliable.
Future Directions: The paper suggests that designing models that balance high expressivity with efficient provable explanations is a viable path forward for trustworthy AI, with NAMs serving as a successful proof-of-concept.

In summary, the paper demonstrates that by leveraging the specific structure of Neural Additive Models, it is possible to overcome the computational barriers of formal XAI, delivering explanations that are both smaller (more concise) and faster to compute than current state-of-the-art methods for general neural networks.