💻 computer science

The Attribution Impossibility: No Feature Ranking Is Faithful, Stable, and Complete Under Collinearity

This paper proves that no feature ranking method can simultaneously achieve faithfulness, stability, and completeness under feature collinearity, characterizing the resulting design space as a strict dichotomy between unstable faithful methods and stable ensemble approaches like DASH, with all findings mechanically verified in Lean 4.

Original authors: Drake Caraker, Bryan Arnold, David Rhoads

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Drake Caraker, Bryan Arnold, David Rhoads

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

The Core Problem: The "Coin Flip" of AI Explanations

Imagine you have a machine learning model (an AI) that predicts whether a loan applicant will pay back their money. You want to know why the AI made a decision. You ask it: "Which feature was most important? Was it their Income or their Debt-to-Income Ratio?"

In the real world, these two numbers are often highly correlated (if you have a high income, you might have a high debt limit). The paper argues that when features are correlated, asking the AI to pick a "winner" is like asking a referee to call a coin flip.

The Big Discovery:
The authors prove mathematically that no single AI model can give you an explanation that is simultaneously:

Faithful: It accurately reflects what that specific model learned.
Stable: It gives the same answer every time you retrain the model.
Complete: It forces a ranking (saying "Income is #1, Debt is #2") even when the data doesn't support a clear winner.

The Catch: You can only pick two.

If you want the explanation to be Faithful and Complete (picking a winner), it won't be Stable. If you retrain the model with a slightly different random seed, the AI might suddenly decide "Debt is #1" and "Income is #2." It's a coin flip.
If you want the explanation to be Stable (always the same), you have to admit you don't know the winner. You must say, "Income and Debt are tied." This sacrifices Completeness (you can't force a ranking).

The "Rashomon" Effect: Many Truths, One Story

The paper uses a concept called the Rashomon Property (named after a famous movie where four people tell different versions of the same crime).

In AI, when features are correlated, there isn't just one "best" model. There are thousands of nearly perfect models that all predict the future equally well. However, these models disagree on how they got there.

Model A says: "I used Income to make the decision."
Model B says: "No, I used Debt."

Both models are equally good at predicting the loan outcome. But because they disagree, any single explanation you get is just a snapshot of one specific model's "opinion." If you retrain the model, you might get Model B's opinion instead of Model A's.

The Solution: The "Dash" Ensemble

Since you can't trust a single model's ranking, the authors propose a solution called Dash (Diversified Aggregation of SHAP).

The Analogy: The Jury
Imagine you are trying to decide who is the best player on a sports team, but the stats are confusing.

The Single Model Approach: You ask one coach. He says, "Player A is the best." You ask him again tomorrow (retraining), and he says, "Player B is the best." You are confused.
The Dash Approach: You ask 25 different coaches (an ensemble of models) and take the average of their opinions.
- If the coaches are split 50/50 between Player A and Player B, the average result is a Tie.
- The Dash method says: "We cannot distinguish between Player A and Player B. They are equally important."

Why this is better:

Honesty: It admits when the data is ambiguous. Instead of lying and picking a winner that changes every day, it reports a tie.
Stability: If you ask the 25 coaches again, they will still say "Tie." The answer is stable.
Pareto Optimality: The paper proves mathematically that this method is the best possible way to handle this trade-off. You can't get a stable, honest answer without accepting ties for ambiguous features.

What About Other Methods?

The paper tested many popular tools (like SHAP, Lasso, Neural Networks) and found they all suffer from this problem when features are correlated.

Gradient Boosting (like XGBoost): The "winner" flips about 50% of the time between retraining runs.
Lasso: It picks one feature and ignores the other completely, but which one it picks is random.
Neural Networks: They are even more unstable than tree-based models.

The paper also notes that Conditional SHAP (a more complex version of the explanation tool) does not fix this problem if the features have the same causal effect. It's still a coin flip.

The "Design Space" Map

The authors mapped out all possible ways to explain AI models. They found there are only two valid paths:

Path A (The Single Model): You get a clear ranking (Complete) that matches the model (Faithful), but it changes every time you retrain (Unstable).
Path B (The Dash Ensemble): You get a stable answer that doesn't change (Stable), but you have to accept ties for correlated features (Incomplete).

There is no Path C. You cannot have a ranking that is always stable, always faithful, and always complete when features are correlated.

Real-World Impact (As Stated in the Paper)

The paper highlights that this isn't just a math problem; it's a practical reality.

Prevalence: In a survey of 77 public datasets, 68% showed this instability. It happens in healthcare, finance, and general data.
Regulatory Risk: If a bank uses an AI to deny a loan, and the reason changes from "Income" to "Debt" just because they retrained the model with a different random seed, that is a compliance risk. The paper suggests that under regulations like the EU AI Act, companies must disclose that their feature rankings are unstable.
The Fix: The paper recommends using the Dash method (averaging 25 models) to get a stable, honest explanation that reports ties where appropriate.

Summary in One Sentence

When AI features are correlated, asking a single model to rank them is like asking a coin to decide a winner; the only honest and stable answer is to admit the coin is fair and report a tie.

Technical Summary: The Attribution Impossibility

1. Problem Statement

The paper addresses a fundamental limitation in Explainable AI (XAI): the reliability of feature importance rankings when input features are collinear. While methods like SHAP (SHapley Additive exPlanations) are widely used to explain model predictions, the authors demonstrate that for collinear features, the ranking of importance is not a stable property of the model-data relationship but a stochastic artifact of the training process.

Specifically, the paper investigates whether a feature ranking can simultaneously satisfy three desiderata:

Faithful: The ranking reflects the specific attributions learned by an individual model instance.
Stable: The ranking is reproducible across different training runs (e.g., different random seeds) of the same model architecture on the same data.
Complete: The ranking provides a strict ordering for every pair of features (no ties).

The central thesis is that under conditions of feature collinearity (correlation $\rho > 0$ ), it is mathematically impossible to satisfy all three conditions simultaneously.

2. Methodology and Theoretical Framework

The Rashomon Property and Impossibility Theorem

The core theoretical contribution is the Attribution Impossibility Theorem (Theorem 5). The proof relies on the Rashomon Property, which posits that for collinear features, there exist multiple near-optimal models (the Rashomon set) that rank symmetric features in opposite orders.

Proof Logic: If a ranking is complete, it must choose an order (e.g., $j \succ k$ ). If it is stable, this order must hold for all models. However, the Rashomon property guarantees the existence of a model where $k \succ j$ . Thus, the ranking cannot be both faithful to that specific model and stable across the set.
Quantitative Bounds: The paper derives quantitative bounds on the severity of this instability for different model classes:
- Gradient Boosting (GBDT): The attribution ratio (dominance of the "first-mover" feature) diverges as $1/(1-\rho^2)$ (or $1/(1-\alpha\rho^2)$ with depth corrections).
- Lasso: The ratio is infinite ( $\infty$ ) for any $\rho > 0$ due to hard selection.
- Neural Networks: Instability is conditional on initialization and training dynamics but follows similar symmetry-breaking patterns.
- Random Forests: Shows bounded violation ( $1 + O(1/\sqrt{T})$ ) due to independent tree training, contrasting with the divergent instability of sequential boosting.

The Symmetric Bayes Dichotomy

The authors generalize this result using the Symmetric Bayes Dichotomy (Theorem 37), a two-families theorem from invariant decision theory. They show that for any symmetric decision problem (where the data distribution is invariant under feature permutations), the achievable set of solutions collapses into exactly two families:

Family A (Single-Model): Faithful and complete, but unstable (unfaithfulness $U = 1/2$ for symmetric pairs).
Family B (Ensemble): Stable and faithful to the population mean, but incomplete (reports ties for symmetric features, $U=0$ ).
There is no third option.

Constructive Resolution: DASH

To resolve the impossibility, the paper proposes DASH (Diversified Aggregation of SHAP). This is an ensemble method that averages SHAP values across $M$ independently trained models.

Mechanism: By averaging, DASH cancels out the random "first-mover" bias inherent in individual models, converging to the population expectation.
Optimality: DASH is proven to be Pareto-optimal among unbiased aggregations. It achieves the Cramér–Rao variance bound ( $\sigma^2/M$ ) for ranking stability.
Trade-off: DASH sacrifices within-group completeness (it reports ties for symmetric features) to gain stability and between-group faithfulness.

Formal Verification

A significant portion of the methodology involves mechanical verification using Lean 4.

The authors formalized the entire theoretical framework, including the impossibility theorem, quantitative bounds, and the DASH optimality proof.
The formalization consists of 305 type-checked theorems across 54 files with 0 sorry (no unproven assumptions).
The process involved 16 axioms (14 domain-specific, 2 for query complexity). Notably, the core impossibility theorem requires zero behavioral axioms, relying solely on the Rashomon property.
The formalization process itself identified two logical inconsistencies and one type mismatch in the original informal axiom system.

3. Key Results and Empirical Validation

Empirical Findings

The paper validates the theory across 77 public datasets and multiple model implementations (XGBoost, LightGBM, CatBoost, Neural Networks).

Prevalence: In a survey of 77 datasets, 68% exhibited attribution instability (flip rate > 10%) for correlated feature pairs. For high-dimensional datasets ( $P \ge 20$ ), this rate rises to 93%.
Flip Rates: For highly correlated pairs ( $\rho \approx 0.9$ ) with similar importance, the flip rate approaches the theoretical maximum of 50% (a coin flip) across retraining seeds.
DASH Efficacy: Ensemble averaging with $M \ge 25$ models reduces the flip rate to below 1%, effectively resolving the instability.
Diagnostics: The paper introduces a Multi-Model Z-Test and a Single-Model Screen (based on split frequencies) to detect unstable pairs. The Z-test shows a strong negative correlation ( $r \approx -0.89$ ) with observed flip rates.

Specific Model Class Behaviors

GBDT: Shows divergent instability. The "first-mover" feature absorbs the signal, leaving residual signal for others, creating a large attribution gap that flips based on which feature is selected first.
Lasso: Exhibits infinite instability as it selects exactly one feature from a correlated group.
Neural Networks: Show high instability (87% of pairs unstable on Breast Cancer data), driven by the larger Rashomon set and KernelSHAP variance.
Random Forests: Show significantly lower instability due to the lack of sequential residual sharing.

Extensions

Conditional Attribution: The paper proves that switching to conditional SHAP does not escape the impossibility if the causal effects of the features are equal ( $\beta_j = \beta_k$ ).
Fairness Audits: The authors demonstrate that proxy discrimination audits based on single-model SHAP are provably unreliable under collinearity, as the conclusion (which feature is the proxy) is a coin flip.
Causal Identification: The instability mirrors the difficulty of causal identification under collinearity, with sample complexity diverging as $1/(1-\rho)^2$ .

4. Significance and Claims

The paper claims to provide the first formally verified impossibility result in Explainable AI. Its significance is framed in three dimensions:

Mathematical Necessity: The instability is not an engineering failure (e.g., poor hyperparameters or bugs) but a mathematical inevitability arising from the geometry of the loss landscape and the Rashomon set. The paper reframes the problem from "how to fix SHAP" to "what is achievable given the constraints."
Design Space Characterization: By defining the Attribution Design Space, the paper establishes that practitioners must choose between stability and completeness. There is no "free lunch" where a single model provides a stable, faithful, and complete ranking.
Regulatory and Practical Impact:
- EU AI Act Compliance: The paper argues that attribution instability constitutes a "known and foreseeable circumstance" under Article 13(3)(b)(ii) of the EU AI Act. Providers must disclose this instability rather than presenting arbitrary rankings as facts.
- Fairness: Single-model fairness audits are deemed unreliable for correlated features, potentially leading to false positives or negatives in proxy discrimination detection.
- Actionable Toolkit: The paper provides a concrete workflow (Screen $\to$ Z-Test $\to$ DASH) and a formula for the minimum ensemble size ( $M_{min}$ ) required to achieve a desired stability level.

The authors conclude that the field must move away from the "single-model paradigm" for explanations in the presence of collinearity and adopt ensemble-based approaches like DASH to provide honest, stable, and defensible explanations.