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

Feature ranking methods cannot simultaneously satisfy three desirable properties when data features are correlated: faithfulness (accurately reflecting model behavior), stability (producing consistent rankings across similar datasets), and completeness (ranking all features). This is a mathematical impossibility, not a limitation of current techniques—meaning no future method can overcome this fundamental constraint.

In real-world datasets, attribution instability is widespread: 68% of 77 public datasets examined showed significant instability in feature importance rankings, meaning the same model could produce substantially different feature rankings depending on minor variations in the data. This has serious implications for using feature importance to audit AI systems for bias or fairness.

SHAP-based audits for detecting discriminatory AI may be unreliable under collinearity: The paper proves that SHAP-based methods commonly used to audit whether AI systems discriminate based on protected characteristics (like race or gender) can produce misleading results when correlated features are present, potentially giving false confidence that a system is fair when it may not be.

The paper identifies only two viable approaches: either accept unstable rankings that flip like coin flips for correlated features, or use ensemble methods like DASH that honestly report when features are interchangeable rather than forcing a false ranking. The authors prove DASH is mathematically optimal among ensemble approaches.

These findings are formally verified with machine-checked mathematics: The impossibility theorem and design space characterization were proven using Lean 4 formal verification (305 theorems), providing unusually high confidence in the results compared to typical research papers.