Trustworthy Feature Importance Avoids Unrestricted Permutations

Emanuele Borgonovo; Francesco Cappelli; Xuefei Lu; Elmar Plischke; Cynthia Rudin

stat.MLApr 13, 2026

Trustworthy Feature Importance Avoids Unrestricted Permutations

Authors: Emanuele Borgonovo, Francesco Cappelli, Xuefei Lu, Elmar Plischke, Cynthia Rudin

Organizations: Department of Decision Sciences and Bocconi Institute for Data Science and Analytics, Bocconi University, Milan, Italy · Department of Decision Science, Bocconi University, Milan, Italy · SKEMA Business School, Université Côte d’Azur, France · Clausthal University of Technology, Clausthal-Zellerfeld, Germany ·

Abstract

Feature importance methods using unrestricted permutations are flawed due to extrapolation errors; such errors appear in all non-trivial variable importance approaches. We propose three new approaches: conditional model reliance and Knockoffs with Gaussian transformation, and restricted ALE plot designs. Theoretical and numerical results show our strategies reduce/eliminate extrapolation.

Figures & tables

Figure 1: Original (black) and permuted data (red). (Left) with unrestricted permutations; (Middle) with residual imputation without Gaussian transformation; (Right) with residual imputation with Gaussian transformation (our proposed approach).

Figure 2: ALE design (left graph) and Jansen design (right graph) for a correlated case. Legend: $\bullet$ original points; red ( $\circ$ ), new points after varying $X_{1}$ ; blue ( $\circ$ ), new points after varying $X_{2}$ .

Feature	$X_{1}$ , $X_{2}$	$X_{3}$ , $X_{4}$ , $X_{5}$	$X_{6}$	$X_{7}$	$X_{8}$	$X_{9}$	$X_{10}$
$\rho_{X_{1},X_{2}}=0.00$	0.1667	0.1667	0	0.0417	0.1067	0.2400	0.3750
$\rho_{X_{1},X_{2}}=0.90$	0.0332	0.1756	0	0.0438	0.1124	0.2528	0.3950

Table 1: Ground Truth values for

\nu_{j}=2\tau_{j}

in the Hooker test case.

Panel of Figure 3 — Figure 3: Comparison between estimated feature importance and rankings using $\widehat{\nu}_{j}$ (the baseline approach), $\widehat{\nu}_{j}^{\text{GCMR}}$ (ours) and $\widehat{\nu}_{j}^{\text{GKnock}}$ (also ours) for the Hooker test case. The symbol $\circ$ indicates the theoretical rank of the features. Black is ground truth. Each of these lines is the average ranking over 50 replications.

Panel of Figure 4 — Figure 4: Estimates (left subpanels) and ranking (right subpanels) of $\widehat{\tau}_{j}^{\text{ALE}}$ (left) and $\widehat{\kappa}_{j}^{\text{ALE}}$ (right) for the Hooker test case.

Figure 5: Feature importance measures for the Linear Regression, $\nu_{j}$ , $\nu^{\text{GCMR}}$ and $\nu^{\text{GKnock}}$ .

Figure 6: Linear Regression: prediction densities with free permutations of $X_{2}$ (left) and with permutations restricted by GCMR (right, our approach).

Panel of Figure 7 — Figure 7: SHAP results for the Boston Housing case based on the trained linear regression. Panel (a) shows the SHAP values based on the linear regression model. Panel (b) shows the Predictions associated with calculating the SHAPs of TAX.

Panel of Figure 8 — Figure 8: Permutation based importance measures $\nu_{j}$ , and $\nu_{j}^{\text{GCMR}}$ (ours), $\nu_{j}^{\text{GKnock}}$ (also ours) for the neural network.

Feature Attribution

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

See all 230 papers

One Permutation Is All You Need: Fast, Deterministic Feature Importance and Model Stress-Testing
Dec 15, 2025Albert DoradorPerturbation-Based Feature Attribution Algorithmic Auditing
Null importance: Disentangling relevance for interpretable machine learning
Sep 16, 2026Garvesh Raskutti, Kris Sankaran, Jiaxin YeFeature Attribution Interpretable ML
Department of Statistics, University of Wisconsin–Madison
cc-Shapley: Measuring Multivariate Feature Importance Needs Causal Context
Feb 23, 2026Jörg Martin, Stefan HaufeFeature Attribution Shapley Value Attribution
Physikalisch-Technische Bundesanstalt, Berlin, Germany · Technische Universität Berlin, Berlin, Germany · Charité – Universitätsmedizin Berlin, Berlin, Germany

Dec 15, 2025J/K move · Enter open · S save

One Permutation Is All You Need: Fast, Deterministic Feature Importance and Model Stress-Testing

Albert Dorador

Perturbation-Based Feature Attribution Algorithmic Auditing

Open paper AskPDF arXiv

Reliable estimation of feature contributions in machine learning models is essential for transparency, algorithmic fairness, and regulatory compliance. While permutation feature importance is widely used, classical implementations rely on repeated Monte Carlo shuffling, introducing significant computational overhead and stochastic instability. In this paper, we show that replacing

B

random permutations with a single, max-min rank-optimal deterministic permutation maintains or improves correlation with ground-truth importance while eliminating estimation variance and reducing complexity from

O(B \cdot n \cdot p)

O(n \cdot p)

. Under location-scale feature distributions, we formally prove exact recovery of scale-adjusted linear regression coefficients, alongside improved importance estimation under concave model sensitivity. We extend this deterministic framework along two complementary dimensions. First, Systemic Feature Importance (SFI) integrates empirical feature correlations to quantify indirect feature reliance through proxy variables. Second, Importance Direction extends scalar importance to a signed, directional representation by measuring concordance between covariate displacements and output shifts. Extensive empirical validation across nearly 200 simulation scenarios demonstrates superior bias-variance trade-offs in high-dimensional and low signal-to-noise regimes. Finally, two real-world credit risk case studies show how coupling SFI with Importance Direction enables practitioners and regulators to audit models for both the magnitude and net sign of hidden reliance on protected attributes, delivering a principled, transparent, and scalable framework for model governance.

Abstract

Feature Attribution

Explore similar work

One Permutation Is All You Need: Fast, Deterministic Feature Importance and Model Stress-Testing

Null importance: Disentangling relevance for interpretable machine learning

cc-Shapley: Measuring Multivariate Feature Importance Needs Causal Context