| Item | Details | |------|---------| | Paper | The Attribution Impossibility: No Feature Ranking Is Faithful, Stable, and Complete Under Collinearity | | Authors | Drake Caraker, Bryan Arnold, David Rhoads | | arXiv ID | 2605.21492 | | Dates | Submitted April 8, 2026; revised May 21, 2026 | | Categories | cs.LG / cs.AI / cs.LO / stat.ML | | Core finding | 305 Lean 4 theorems formally prove that under feature collinearity, no attribution ranking can be simultaneously faithful, stable, and complete. 68% of surveyed public datasets are affected. SHAP-based fairness auditing under collinearity is systematically unreliable. |
1. The Value of Proving Impossibility
The most elegant theorems in mathematics are impossibility proofs: angles cannot be trisected with compass and straightedge, general quintic equations have no solution by radicals, the halting problem is undecidable. Their shared value: they tell you to stop trying—the direction itself is wrong.
Drake Caraker, Bryan Arnold, and David Rhoads did exactly this for explainable AI (XAI). Using 305 Lean 4 theorems derived from 16 axioms with zero sorry, they mechanically verified a harsh conclusion:
When features are collinear, no feature attribution ranking can simultaneously satisfy three basic properties: faithfulness, stability, and completeness.
This is not "nobody has found one yet." It is a proven "never will exist."
2. The Three Properties
- Faithfulness: the attribution must tell the truth—if the model relies on feature A more than B, A must rank above B, always.
- Stability: running on the same data twice should give the same ranking.
- Completeness: attribution values must sum to the model's total prediction.
- For gradient boosting, attribution variance diverges as 1/(1-ρ²), where ρ is the correlation coefficient; as ρ→1, variance→∞.
- For Lasso, divergence is infinite—attribution for perfectly collinear features is theoretically indeterminate.
- Random forests are most robust: variance converges under collinearity, at the cost of completeness.
- A credit model says "credit score is the top rejection factor," but income and credit score are highly correlated—the ranking is effectively random.
- A medical model says "blood pressure is the top risk factor," but it correlates with age and weight.
- A hiring algorithm ranks education first, though it correlates with parental education.
- Scope of collinearity: the proofs center on pairwise linear correlation; higher-order and nonlinear collinearity are not covered and may require extending the Lean 4 framework.
- DASH cost: training multiple models is impractical for expensive models (e.g., large language models); cheaper alternatives like inference-time attribution perturbation are not discussed.
- Impact gap: 68% instability does not quantify how often instability leads to consequential decision errors—minor rank fluctuation and full rank reversal differ greatly in severity.
- Conditional SHAP: the paper shows that even conditional SHAP cannot escape the impossibility when features have identical causal effects—a condition rarely verifiable in real data.
The core proof: when two features are highly correlated, you can have at most two of the three. A "feature importance ranking" under collinearity is no more reliable than a coin flip.
3. Why Collinearity Kills Attribution
Example: predicting house prices with feature A = number of bedrooms and feature B = floor area, which are highly correlated. The model's internal computation does not separate A's contribution from B's—credit can be freely shuffled between them without changing the prediction.
The paper quantifies this:
4. 68% of Datasets Are Affected
A survey of 77 public datasets found 68% exhibit significant attribution instability. Consequences in practice:
The paper further shows that using SHAP directly in fairness audits to identify which features cause discrimination is systematically unreliable—the model can shift blame to a scapegoat feature correlated with the true source.
5. A Dichotomy of the Design Space
Only two classes of attribution methods exist:
1. Faithful-complete methods (e.g., classic SHAP): correct and complete, but unstable—rankings of collinear features flip with up to 50% probability. 2. Ensemble methods (e.g., the paper's DASH): sacrifice completeness for stability by aggregating attributions across models/samples.
There is no third class. This is a mathematical proof, not a philosophical claim.
6. DASH: A Pragmatic Response
DASH (Diversified Aggregation of SHAP) trains N slightly different models (different seeds, training subsets) and averages their SHAP values. It is proven Pareto-optimal among unbiased aggregation methods and achieves the Cramér–Rao variance lower bound, with an exact formula for the required ensemble size N.
Honesty note: DASH does not resolve the impossibility—it tames its effects. For perfectly collinear features, DASH truthfully reports a tie rather than picking one at random. That is closer to reality than SHAP's point estimate, but still does not answer "which one matters more."
7. Honest Boundaries
Conclusion
Like the uncertainty principle in physics, this impossibility is structural, not a limitation of tools. It is not that SHAP is poorly written or undersampled—the geometry of the problem forbids faithfulness, stability, and completeness simultaneously.
Practical takeaway for data scientists: if you are using SHAP to explain a model with highly correlated features, be honest—part of your ranking is randomly chosen from overlapping information, and that part should not enter any serious decision.