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

Drake Caraker; Bryan Arnold; David Rhoads

cs.LGApr 8, 2026

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

Authors: Drake Caraker, Bryan Arnold, David Rhoads

Organizations: Independent Researchers

Abstract

No feature ranking can be simultaneously faithful, stable, and complete when features are collinear. For collinear pairs, ranking reduces to a coin flip. We prove this impossibility, quantify it for four model classes, resolve it via ensemble averaging (DASH), and machine-verify it with 305 Lean 4 theorems. We characterize the complete attribution design space: exactly two families of methods exist -- faithful-complete methods (unstable, with rankings that flip up to 50% of the time) and ensemble methods like DASH (stable, reporting ties for symmetric features) -- and no method lies outside this dichotomy. The impossibility is quantitative: the attribution ratio diverges as 1/(1-rho^2) for gradient boosting, is infinite for Lasso, and converges for random forests. DASH (Diversified Aggregation of SHAP) is provably Pareto-optimal among unbiased aggregations, achieving the Cramer-Rao variance bound with a tight ensemble size formula. In a survey of 77 public datasets, 68% exhibit attribution instability. Switching to conditional SHAP does not escape the impossibility when features have equal causal effects. The framework includes practical diagnostics -- a Z-test workflow and single-model screening tool -- and has direct consequences for fairness auditing: SHAP-based proxy discrimination audits are provably unreliable under collinearity. The design space theorem, diagnostics, and impossibility are mechanically verified in Lean 4 (305 theorems from 16 axioms, 0 sorry) -- to our knowledge, the first formally verified impossibility in explainable AI.

Figures & tables

Figure 1: The Attribution Impossibility. No feature ranking can be simultaneously faithful, stable, and complete under collinearity. Faithful, Stable, Complete: Pick Two. Family

\mathcal{A}

(single-model) is faithful and complete but rankings flip up to 50% of the time. Family

\mathcal{B}

( Dash ensemble) is stable with zero unfaithfulness but reports ties for symmetric features (sacrificing completeness). No third option exists.

Axiom	Lean 4 name	Justification
First-mover surjectivity	firstMover_surjective	DGP symmetry: each feature can be first-mover
Split count (first-mover)	splitCount_firstMover	Gaussian conditioning (Lemma 14 )
Split count (non-first-mover)	splitCount_nonFirstMover	Residual signal after first-mover absorbs $\rho$ -component
Global proportionality	proportionality_global	Uniform contribution model with constant $c$ across models
Cross-group symmetry	splitCount_crossGroup_symmetric	DGP symmetry: equal split counts when first-mover elsewhere
Cross-group stability	splitCount_crossGroup_stable	Changing first-mover within a group does not affect other groups

Table 1: Complete axiom inventory (16 total: 6 type/constant, 6 property, 2 measure, 2 query).

	$\rho{=}0.3$	$\rho{=}0.5$	$\rho{=}0.7$	$\rho{=}0.9$	$\rho{=}0.95$	Fitted $\alpha$
Depth 1 (stumps)	1.28	1.32	1.42	1.99	2.16	$0.60\ (\approx 2/\pi)$
Depth 3	1.19	1.26	1.24	1.30	1.32	$0.30$
Depth 6	1.65	1.67	1.74	1.90	2.03	$0.60$
Depth 10	2.23	2.25	2.28	2.49	2.62	—
Theory ( $\alpha{=}1$ )	1.10	1.33	1.96	5.26	10.26	$1.00$

Table 2: Within-group split count ratio by depth and

\rho

(

\eta{=}1.0

Model class	Ratio	Scaling with $T$	Mechanism
Gradient boosting	$1/(1-\alpha\rho^{2})$	Increases with $\rho$	Sequential residuals
Lasso	$\infty$	Constant	Hard selection
Neural network	Model-dependent	Architecture-dependent	Init. symmetry breaking
Random forest 3 3 3 The RF bound is informal. The GBDT and Lasso bounds are Lean-verified; the NN bound is conditional on the dominance hypothesis.	$1+O(1/\sqrt{T})$	$\to 1$ as $T\to\infty$	Independent trees

Table 3: Attribution ratio bounds by model class.

T

denotes the number of boosting rounds (or trees),

\rho

the within-group correlation.

Method	$\rho=0.5$	$\rho=0.7$	$\rho=0.9$	Pairs resolved
Single model	16.0% [13.8, 18.1]	16.4% [14.3, 18.5]	18.7% [16.4, 21.1]	40/40
Bootstrap SHAP	16.2% [13.8, 18.2]	16.1% [14.2, 18.0]	18.8% [16.4, 21.4]	40/40
Subsampled SHAP	16.3% [13.8, 18.5]	16.1% [14.2, 17.9]	18.8% [16.5, 21.3]	40/40
Dash ( $M{=}25$ )	3.8% [2.8, 4.9]	3.1% [2.4, 3.9]	3.7% [2.7, 4.7]	40/40
CI SHAP	0.2% [0.1, 0.4]	0.8% [0.6, 1.1]	3.1% [2.1, 4.6]	$\sim$ 22/40

Table 4: Flip rate comparison: Dash vs. alternative stabilization methods. Synthetic Gaussian data (

P{=}10

m{=}5

N{=}1000

, 20 within-group feature pairs). 95% bootstrap CIs in brackets.

Figure 2: Left: Within-group information lost by Dash (

\log_{2}m!

bits per group, independent of

M

and

\rho

). Right: Between-group information per pair as a function of

M

. Dash sharpens between-group rankings with increasing

M

. At high

\rho

(

\geq 0.9

), convergence requires larger

M

Figure 3: The Attribution Design Space. Family

\mathcal{A}

(single-model methods): faithful and complete but unstable (

U{=}1/2

). Family

\mathcal{B}

( Dash ensemble): stable with ties (

U{=}0

S

increasing with

M

). The ideal point

(S{=}1,U{=}0,C{=}\text{complete})

is infeasible. There is no third option.

$\rho\backslash\Delta\beta$	0.0	0.1	0.2	0.3	0.5	0.7	1.0
0.50	50	19	0	0	0	0	0
0.70	53	19	0	0	0	0	0
0.80	52	44	19	10	0	0	0
0.90	50	50	48	40	40	19	0
0.95	50	50	50	48	44	40	27
0.99	50	50	50	50	50	48	48

Table 5: Flip rate (%) as a function of

\rho

and causal effect difference

\Delta\beta

Figure 4: Flip rate as a function of $(\rho,\Delta\beta)$ . The impossibility region (dark) expands with $\rho$ . At $\rho\geq 0.95$ , instability persists for all $\Delta\beta\leq 1$ .

Figure 5: Left: Multi-model Z-test statistic vs. flip rate on Breast Cancer (

r=-0.89

). Pairs below

z=1.96

(dashed) have unreliable rankings. Right: Single-model screen split-frequency diagnostic (

r=-0.78

). Both diagnostics predict which pairs are unstable.

Figure 6: Universal SNR calibration across 6 datasets (1,325 feature pairs). The theoretical

\Phi(-\text{SNR})

curve is conservative at low SNR and exact at diagnostic thresholds. All 228 pairs with

\text{SNR}>1.96

have flip rate

<5\%

Experiment	Configuration
Synthetic (main text)	$P{=}20$ , $L{=}4$ groups of $m{=}5$ , $N{=}2{,}000$ , $T{=}100$ , $\eta{=}0.1$ , 50 seeds, $\rho\in\{0.1,0.3,0.5,0.7,0.9,0.95\}$
Validation (depth $\times\rho$ )	$P{=}10$ , $L{=}2$ groups of $m{=}5$ , $N{=}2{,}000$ , $T{=}100$ , $\eta{=}1.0$ , 30 seeds, depths $\{1,3,6,10\}$ , $\rho\in\{0.3,0.5,0.7,0.9,0.95\}$
Breast Cancer	30 features, 569 samples, $T{=}100$ , depth ${=}6$ , $\eta{=}0.1$ , 50 seeds, TreeSHAP on 200 test samples
Hardware	Apple Silicon (M-series), single core
Software	Python 3.9.6, XGBoost 2.1.4, SHAP 0.49.1, NumPy 2.0.2
Compute	Synthetic: ${<}5$ min; Validation: ${<}30$ min; Breast Cancer: ${<}10$ min

Table 6: Experimental configurations.

Panel of Figure 7 — Figure 7: Empirical validation on synthetic Gaussian data ( $P=20$ , $L=4$ , $m=5$ , $T=100$ , 50 seeds).

Figure 8: SHAP ranking instability on Breast Cancer. Highly correlated pairs with similar importance (e.g., worst perimeter

\leftrightarrow

worst area,

|\rho|{=}0.98

, flip rate 48%) exhibit near-maximal instability. 50 XGBoost models.

Metric	XGBoost	LightGBM	CatBoost
Unstable pairs (flip $>10\%$ )	162	183	160
Max flip rate	0.500	0.500	0.500
Z-test correlation $r(Z,\text{flip})$	$-0.898$	$-0.901$	$-0.892$

Table 7: Attribution instability across three GBDT implementations on Breast Cancer (50 models each).

Dataset	$P$	Pairs	Unstable	$r(Z,\text{flip})$	Screen prec.
Breast Cancer	30	435	168	$-0.89$	0.94
California Housing	8	28	1	$-0.99$	—
Diabetes	10	45	15	$-0.89$	0.50
Wine	13	78	24	$-0.81$	1.00
Heart Disease	13	78	27	$-0.91$	1.00
Credit-g	20	190	47	$-0.90$	0.67

Table 8: Multi-model Z-test and single-model screen diagnostic generality across 11 datasets.

Figure 9: Multi-model Z-test statistic vs. flip rate across four datasets (Breast Cancer, Ames, Digits, Adult). The negative correlation confirms the diagnostic across domains: clinical, real estate, image, and census.

File	Section	Key Result
Defs.lean	§ 2	14 axioms + derived theorems
Trilemma.lean	Thm. 5	attribution_impossibility
Iterative.lean	§ 3.3	iterative_impossibility
General.lean	§ 4.1	gbdt_impossibility
SplitGap.lean	Lem. 14	split_gap_exact
Ratio.lean	Thm. 15	ratio_tendsto_atTop

Table 9: Lean file cross-reference (54 files, 305 theorems, 16 axioms).

Result	Stability?	Quantitative?	Resolution?	Formal?
Bilodeau et al. (2024)	No	No	No	No
Huang et al. (2024)	No	No	No	No
Srinivas et al. (2019)	No	No	No	No
Rao (2025)	No	No	No	No
Laberge et al. (2023)	Empirical	No	No	No
Herren & Hahn (2023)	Inference	No	No	No

Table 10: Positioning relative to prior attribution impossibility results. These criteria reflect the specific contributions of the present work; each prior result makes distinct contributions not captured by this comparison.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Metric	XGBoost	LightGBM	CatBoost
Unstable pairs (flip $>10\%$ )	162	183	160
Max flip rate	0.500	0.500	0.500
Z-test correlation $r(Z,\text{flip})$	$-0.898$	$-0.901$	$-0.892$
Screen precision	0.26	0.20	—
Dash max flip ( $M{=}25$ )	0.48	0.48	0.48

Appendix

Table 11: Full cross-implementation comparison on Breast Cancer (50 models each).

Experiment	Key finding	Script
Monte Carlo flip rate	$\Phi(-\text{SNR})$ validated to $<$ 1.3% error	monte_carlo_flip_rate.py
Hyperparameter sweep	Min flip 38.7% at $\rho{=}0.5$ ; never 0%	hyperparameter_sensitivity.py
Class imbalance	1:5+ imbalance $\to$ 100% pairs unstable	class_imbalance_instability.py
Missing data	MCAR/MAR/MNAR all compound instability	missing_data_instability.py
Longitudinal drift	Spearman degrades 1.0 $\to$ 0.18 over 31 rounds	longitudinal_retraining.py
Adversarial configs	All 108 configs hit 0.500 ceiling at $\rho{=}0.9$	adversarial_max_instability.py

Appendix

Table 12: Summary of additional experiments.

Feature Attribution

Feature attribution estimates which input features or internal components contribute to a model’s predictions.

See all 231 papers

Mar 22, 2026

First-Mover Bias in Gradient Boosting Explanations: Mechanism, Detection, and Resolution

We identify first-mover bias -- path-dependent concentration of SHAP feature importance from sequential residual fitting in gradient boosting -- as a mechanistic contributor to attribution instability under multicollinearity. Scaling up a single model amplifies this effect: a Large Single Model matching our method's total tree count produces the poorest attribution reproducibility of any approach tested. We show that model independence largely neutralizes first-mover bias. Both DASH (Diversified Aggregation of SHAP) and simple seed-averaging (Stochastic Retrain) restore stability by breaking the sequential dependency chain. At rho=0.9, both achieve stability ~0.977, while Single Best degrades to 0.958 and LSM to 0.938. On Breast Cancer, DASH improves stability from 0.376 to 0.925 (+0.549), outperforming Stochastic Retrain by +0.063. Under nonlinear DGPs, the advantage emerges at rho>=0.7. DASH provides two diagnostic tools -- the Feature Stability Index and Importance-Stability Plot -- that detect first-mover bias without ground truth. A crossed ANOVA with formal F-statistics confirms the mechanism: DASH shifts variance from model-dominated (40.6%) to data-dominated (73.6%). Software at https://github.com/DrakeCaraker/dash-shap

Drake Caraker, Bryan Arnold, David Rhoads

Independent Researchers

SHAP Feature Attribution Gradient-Boosted Decision Trees Ensemble Learning

Ask PDF

May 14, 2026

RoSHAP: A Distributional Framework and Robust Metric for Stable Feature Attribution

Feature attribution analysis is critical for interpreting machine learning models and supporting reliable data-driven decisions. However, feature attribution measures often exhibit stochastic variation: different train--test splits, random seeds, or model-fitting procedures can produce substantially different attribution values and feature rankings. This paper proposes a framework for incorporating stochastic nature of feature attribution and a robust attribution metric, RoSHAP, for stable feature ranking based on the SHAP metric. The proposed framework models the distribution of feature attribution scores and estimates it through bootstrap resampling and kernel density estimation. We show that, under mild regularity conditions, the aggregated feature attribution score is asymptotically Gaussian, which greatly reduces the computational cost of distribution estimation. The RoSHAP summarizes the distribution of SHAP into a robust feature-ranking criterion that simultaneously rewards features that are active, strong, and stable. Through simulations and real-data experiments, the proposed framework and RoSHAP outperform standard single-run attribution measures in identifying signal features. In addition, models built using RoSHAP-selected features achieve predictive performance comparable to full-feature models while using substantially fewer predictors. The proposed RoSHAP approach improves the stability and interpretability of machine learning models, enabling reliable and consistent insights for analysis.

Lanxin Xiang, Liang Shi, Youhui Ye +3

Department of Statistics Virginia Tech · Department of Statistics Virginia Tech Transportation Institute · Department of Computer Science Virginia Tech

Feature Attribution Shapley Value Attribution Feature Selection

Ask PDF

Feb 28, 2026

A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

In this paper, we provide a theoretically grounded and computationally efficient alternative to SHAP. To this end, we study feature attribution through the lens of cooperative game theory by formulating a class of XAI--TU games. Building on this formulation, we investigate equal-surplus-type and proportional-allocation-type attribution rules and propose a low-cost attribution rule, ESENSC_rev2, constructed by combining two polynomial-time closed-form rules while ensuring the null-player property in the XAI--TU domain. Extensive experiments on tabular prediction tasks demonstrate that ESENSC_rev2 closely approximates exact SHAP while substantially improving scalability as the number of features increases. These empirical results indicate that equal-surplus-type attribution rules can achieve favorable trade-offs between computational cost and approximation accuracy in high-dimensional explainability settings. To provide theoretical foundations for these findings, we establish an axiomatic characterization showing that ESENSC_rev2 is uniquely determined by efficiency, the null-player axiom, a restricted differential marginality principle, an intermediate inessential-game property, and axioms that reduce computational requirements. Our results suggest that axiomatically justified and computationally efficient attribution rules can serve as practical and theoretically principled substitutes for SHAP-based approximations in modern explainability pipelines.

Kazuhiro Hiraki, Shinichi Ishihara, Takumi Kongo +1

International Monetary Fund · Independent Researcher · Fukuoka University +1

Feature Attribution Shapley Value Attribution

Ask PDF

Abstract

Feature Attribution

Explore similar work

First-Mover Bias in Gradient Boosting Explanations: Mechanism, Detection, and Resolution

RoSHAP: A Distributional Framework and Robust Metric for Stable Feature Attribution

A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution