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

Albert Dorador

stat.MLDec 15, 2025

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

Authors: Albert Dorador

Abstract

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)$ to $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.

Figures & tables

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.953 ± 0.008	0.941 ± 0.012	0.900 ± 0.037	0.910 ± 0.035
Max score diff	0.082 ± 0.019	0.093 ± 0.020	0.095 ± 0.024	0.091 ± 0.024
Time (ms)	24.9 ± 13.7	19.4 ± 10.7	17.1 ± 5.3	98.4 ± 32.4

Table 1 : Linear regression regime. Global mean results across 48 scenarios with varying sample size, dimensionality, noise level, feature correlation and choice of ground-truth regression model.

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.953 ± 0.007	0.941 ± 0.008	0.899 ± 0.036	0.910 ± 0.034
Max score diff	0.154 ± 0.019	0.176 ± 0.021	0.173 ± 0.021	0.168 ± 0.023
Time (ms)	25.3 ± 13.9	19.7 ± 11.0	17.0 ± 5.1	98.2 ± 31.8

Table 2 : Nonlinear regression regime. Global mean results across 48 scenarios with varying sample size, dimensionality, noise level, feature correlation and choice of ground-truth regression model.

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.962 ± 0.010	0.947 ± 0.018	0.868 ± 0.052	0.882 ± 0.051
Max score diff	0.066 ± 0.019	0.067 ± 0.018	0.088 ± 0.026	0.083 ± 0.029
Time (ms)	27.1 ± 14.7	21.2 ± 11.5	26.2 ± 8.0	189.1 ± 60.4

Table 3 : Classification (linear response). Global mean results across 48 scenarios with varying sample size, dimensionality, noise level, feature correlation and choice of ground-truth classifier.

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.953 ± 0.009	0.942 ± 0.013	0.863 ± 0.047	0.879 ± 0.045
Max score diff	0.153 ± 0.021	0.162 ± 0.020	0.173 ± 0.022	0.168 ± 0.023
Time (ms)	27.0 ± 14.6	20.9 ± 11.4	26.0 ± 7.8	185.1 ± 57.3

Table 4 : Classification (nonlinear response). Global mean results across 48 scenarios with varying sample size, dimensionality, noise level, feature correlation and choice of ground-truth classifier.

Metric	Lasso Regression	Linear Regression	RF
$R^{2}$	0.49 ± 0.10	0.49 ± 0.10	0.46 ± 0.08
MAE	0.048 ± 0.002	0.048 ± 0.002	0.048 ± 0.002
Nonzero coefficients	11.8 ± 0.2	12.0 ± 0.0	N/A

Table 5 : Forecasting out-of-fold average primary model results with two standard error bands in the Boston HMDA dataset

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor.	0.997 ± 0.001	0.997 ± 0.001	0.996 ± 0.001	0.996 ± 0.001
Max score diff.	0.272 ± 0.014	0.273 ± 0.015	0.271 ± 0.020	0.270 ± 0.019
Mean score diff.	0.045 ± 0.001	0.045 ± 0.002	0.045 ± 0.003	0.045 ± 0.003
Time (ms)	0.79 ± 0.01	0.63 ± 0.01	3.64 ± 0.11	21.42 ± 0.20

Table 6 : Results of different FI methods under

\ell_{1}

-regularized linear regression primary estimator – Boston HMDA dataset

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor.	0.997 ± 0.001	0.997 ± 0.001	0.996 ± 0.001	0.996 ± 0.001
Max score diff.	0.279 ± 0.019	0.279 ± 0.019	0.278 ± 0.023	0.277 ± 0.023
Mean score diff.	0.046 ± 0.003	0.047 ± 0.003	0.046 ± 0.004	0.046 ± 0.004
Time (ms)	0.69 ± 0.01	0.61 ± 0.01	3.50 ± 0.06	21.31 ± 0.28

Table 7 : Results of different FI methods under an unregularized primary linear model – Boston HMDA dataset

Figure 2 : Spearman correlation in the Boston HMDA test dataset (empirical tolerance threshold: 0.09, FDR significance level: 0.05)

Figure 3 : Oriented Systemic Feature Importance scores of Lasso regression with black excluded from the model (Boston HMDA dataset)

Metric	$\ell_{1}$ -Logistic	Logistic	RF
ROC-AUC	0.73 ± 0.03	0.79 ± 0.03	0.79 ± 0.03
Nonzero coef.	2.2 ± 0.4	20 ± 0.0	N/A

Table 8 : Forecasting out-of-fold average primary model results with two standard error bands in the German credit dataset

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor.	0.996 ± 0.002	0.997 ± 0.002	0.999 ± 0.001	0.998 ± 0.001
Max score diff.	0.072 ± 0.025	0.069 ± 0.024	0.035 ± 0.020	0.044 ± 0.021
Mean score diff.	0.007 ± 0.003	0.007 ± 0.002	0.003 ± 0.002	0.004 ± 0.002
Time (ms)	1.26 ± 0.03	1.14 ± 0.06	8.79 ± 0.09	65.05 ± 0.44

Table 9 : Results of different FI methods under an

\ell_{1}

-regularized logistic regression primary estimator – German Credit dataset

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor.	0.875 ± 0.015	0.900 ± 0.013	0.806 ± 0.036	0.773 ± 0.077
Max score diff.	0.255 ± 0.031	0.200 ± 0.025	0.196 ± 0.053	0.196 ± 0.031
Mean score diff.	0.029 ± 0.002	0.025 ± 0.002	0.035 ± 0.004	0.036 ± 0.003
Time (ms)	1.19 ± 0.03	1.10 ± 0.03	8.73 ± 0.17	64.19 ± 0.70

Table 10 : Results of different FI methods under an unregularized logistic regression primary model – German Credit dataset

Figure 4 : Spearman correlation in the German Credit test dataset (empirical tolerance threshold: 0.13, FDR significance level: 0.05)

Figure 5 : Oriented Systemic Feature Importance scores of Lasso regression with Sex-Marital_status excluded from the model (German Credit dataset)

Appendix figures & tables26 assets

Supplementary material from the paper’s appendix.

Appendix

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.996 ± 0.002	0.992 ± 0.004	0.900 ± 0.037	0.910 ± 0.035
Max score diff	0.007 ± 0.002	0.011 ± 0.003	0.095 ± 0.024	0.091 ± 0.024
Time (ms)	25.0 ± 13.7	19.3 ± 10.7	17.9 ± 5.4	104.8 ± 33.1

Appendix

Table 11 : Linear regression regime. Global results across 48 scenarios with varying sample size, dimensionality, noise level, feature correlation and choice of ground-truth regression model

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.997 ± 0.001	0.993 ± 0.003	0.899 ± 0.036	0.910 ± 0.034
Max score diff	0.013 ± 0.004	0.015 ± 0.005	0.173 ± 0.021	0.168 ± 0.023
Time (ms)	24.1 ± 13.2	18.7 ± 10.3	17.3 ± 5.2	101.9 ± 32.0

Appendix

Table 12 : Nonlinear regression regime. Global results across 48 scenarios with varying sample size, dimensionality, noise level, feature correlation and choice of ground-truth regression model

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.991 ± 0.004	0.982 ± 0.008	0.838 ± 0.070	0.867 ± 0.071
Max score diff	0.017 ± 0.006	0.019 ± 0.005	0.079 ± 0.021	0.076 ± 0.026
Time (ms)	26.7 ± 14.4	20.8 ± 11.3	20.1 ± 6.2	126.6 ± 41.6

Appendix

Table 13 : Classification (linear response). Global results across 48 scenarios with varying sample size, dimensionality, noise level, feature correlation and choice of ground-truth classifier

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.995 ± 0.002	0.987 ± 0.009	0.798 ± 0.070	0.837 ± 0.064
Max score diff	0.018 ± 0.004	0.020 ± 0.005	0.165 ± 0.033	0.156 ± 0.029
Time (ms)	26.4 ± 14.3	20.8 ± 11.3	20.0 ± 6.2	125.6 ± 41.6

Appendix

Table 14 : Classification (nonlinear response). Global results across 48 scenarios with varying sample size, dimensionality, noise level, feature correlation and choice of ground-truth classifier

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.952 ± 0.005	0.956 ± 0.004	0.943 ± 0.011	0.944 ± 0.011
Max score diff	0.225 ± 0.016	0.219 ± 0.015	0.472 ± 0.047	0.471 ± 0.045
Mean score diff	0.045 ± 0.003	0.044 ± 0.002	0.079 ± 0.008	0.079 ± 0.007
Time (ms)	1.60 ± 0.03	1.45 ± 0.03	5.06 ± 0.11	33.84 ± 0.91

Appendix

Table 15 : Results of different FI methods under an

\ell_{1}

-regularized linear regression primary estimator with default scoring metrics – Boston HMDA dataset

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.997 ± 0.000	0.998 ± 0.000	0.999 ± 0.000	0.999 ± 0.000
Max score diff	0.185 ± 0.012	0.190 ± 0.015	0.074 ± 0.026	0.073 ± 0.025
Mean score diff	0.031 ± 0.002	0.032 ± 0.002	0.013 ± 0.004	0.013 ± 0.004
Time (ms)	0.49 ± 0.03	0.39 ± 0.01	5.80 ± 0.15	42.03 ± 0.99

Appendix

Table 16 : Results of different FI methods under an unregularized primary linear model with default scoring metrics – Boston HMDA dataset

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	1.000 ± 0.000	1.000 ± 0.000	0.996 ± 0.002	0.996 ± 0.002
Max score diff	0.022 ± 0.010	0.013 ± 0.008	0.077 ± 0.028	0.077 ± 0.028
Mean score diff	0.002 ± 0.001	0.001 ± 0.001	0.008 ± 0.003	0.008 ± 0.003
Time (ms)	0.82 ± 0.04	0.67 ± 0.01	5.07 ± 0.10	32.56 ± 0.40

Appendix

Table 17 : Results of different FI methods under an

\ell_{1}

-regularized logistic regression primary estimator with default scoring metrics – German Credit dataset

Metric	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
Ground-truth cor	0.930 ± 0.014	0.935 ± 0.017	0.682 ± 0.082	0.658 ± 0.148
Max score diff	0.060 ± 0.009	0.045 ± 0.005	0.180 ± 0.073	0.191 ± 0.096
Mean score diff	0.012 ± 0.001	0.010 ± 0.001	0.042 ± 0.011	0.042 ± 0.013
Time (ms)	0.75 ± 0.01	0.66 ± 0.01	4.95 ± 0.08	32.48 ± 0.22

Appendix

Table 18 : Results of different FI methods under an unregularized logistic regression primary model – German Credit dataset

Top 5 indices	DFI-Opt	DFI-Approx	Breiman (B=1)	Breiman (B=10)
$[0,11,6,3,1]$	10	0	0	0
$[0,11,6,3,4]$	0	10	0	0
$[0,11,1,3,6]$	0	0	0	6
$[0,11,1,3,2]$	0	0	3	4
$[0,11,3,1,6]$	0	0	2	0
$[0,11,6,1,3]$	0	0	1	0

Appendix

Table 19 : Top 5 features across 10 independent runs. Ground truth:

[0,11,6,3,1]

– Boston HMDA.

Top 5 indices	DFI-Opt	DFI-Approx	Breiman (B=10)
$[0,3,2,1,5]$	10	10	0
$[0,2,1,3,5]$	0	0	4
$[0,1,2,3,5]$	0	0	2
$[0,1,3,2,5]$	0	0	1
$[0,1,2,7,5]$	0	0	1
$[0,2,1,5,3]$	0	0	1

Appendix

Table 20 : Top 5 features across 10 independent runs. Ground truth:

[0,3,2,1,5]

– German Credit.

Figure 6 : Performance of different variable importance methods in linear regression with uncorrelated features and linear response under varying sample size, dimensionality and noise

Figure 7 : Performance of different variable importance methods in $\ell_{1}$ -linear regression with uncorrelated features and linear response under varying sample size, dimensionality and noise

Figure 8 : Performance of different variable importance methods in linear regression with correlated features and linear response under varying sample size, dimensionality and noise

Figure 9 : Performance of different variable importance methods in $\ell_{1}$ -linear regression with correlated features and linear response under varying sample size, dimensionality and noise

Figure 10 : Performance of different variable importance methods in linear regression with uncorrelated features and nonlinear response under varying sample size, dimensionality and noise

Figure 11 : Performance of different variable importance methods in $\ell_{1}$ -linear regression with uncorrelated features and nonlinear response under varying sample size, dimensionality and noise

Figure 12 : Performance of different variable importance methods in linear regression with correlated features and nonlinear response under varying sample size, dimensionality and noise

Figure 13 : Performance of different variable importance methods in $\ell_{1}$ -linear regression with correlated features and nonlinear response under varying sample size, dimensionality and noise

Figure 14 : Performance of different variable importance methods in logistic regression with uncorrelated features and linear (binarized) response under varying sample size, dimensionality and noise

Figure 15 : Performance of different variable importance methods in $\ell_{1}$ -logistic regression with uncorrelated features and linear (binarized) response under varying sample size, dimensionality and noise

Figure 16 : Performance of different variable importance methods in logistic regression with correlated features and linear (binarized) response under varying sample size, dimensionality and noise

Figure 17 : Performance of different variable importance methods in $\ell_{1}$ -logistic regression with correlated features and linear (binarized) response under varying sample size, dimensionality and noise

Figure 18 : Performance of different variable importance methods in logistic regression with uncorrelated features and nonlinear (binarized) response under varying sample size, dimensionality and noise

Figure 19 : Performance of different variable importance methods in $\ell_{1}$ -logistic regression with uncorrelated features and nonlinear (binarized) response under varying sample size, dimensionality and noise

Figure 20 : Performance of different variable importance methods in logistic regression with correlated features and nonlinear (binarized) response under varying sample size, dimensionality and noise

Figure 21 : Performance of different variable importance methods in $\ell_{1}$ -logistic regression with correlated features and nonlinear (binarized) response under varying sample size, dimensionality and noise

Explore similar work

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
CID: Measuring Feature Importance Through Counterfactual Distributions
Nov 19, 2025Eddie Conti, Álvaro Parafita, Axel BrandoFeature Attribution Explainability Evaluation
TAIES Group, HPES Lab, Barcelona Supercomputing Center (BSC)
Model-Agnostic FDR Control via Group Gaussian Mirror and Permutation SHAP
Aug 2, 2026Jiaan Han, Junxiao Chen, Yanzhe FuFDR Control Feature Selection
Columbia Business School Columbia University · Department of Statistics University of Hong Kong

Sep 16, 2026, stat.MLJ/K move · Enter open · S save

Null importance: Disentangling relevance for interpretable machine learning

Garvesh Raskutti, Kris Sankaran, Jiaxin Ye

Department of Statistics, University of Wisconsin–Madison

Feature Attribution Interpretable ML

Open paper AskPDF arXiv

Feature importance is central to interpretable machine learning, but the term "importance" encompasses several fundamentally different notions of relevance. We develop a unified perspective based on null importance: a population-level characterization of when a feature is irrelevant under a specified notion of relevance. We consider standard notions of null importance arising from marginal and conditional statistical relevance, predictive risk, functional invariance, and causal effects, and show how these notions answer different scientific questions. We illustrate the framework in two applications in which the distinction is particularly consequential: algorithmic fairness, where common fairness criteria correspond to different notions of null importance, and genomic perturbation modeling, where different notions of relevance lead to different conclusions about what a prediction model has learned. The framework connects three aspects of feature analysis: the scientific question defining relevance, the data and model assumptions that shape how different null notions relate, and the methods used to assess importance. We establish sufficient conditions under which null notions coincide and give counterexamples showing how they diverge when those conditions fail. We then characterize which nulls different method families target and when their zero-importance statistics identify those targets. Finally, simulations spanning feature dependence, redundancy, nonlinearity, hidden features and other standard phenomena, along with case studies on image and multiomics data, provide empirical evidence for these theoretical distinctions and their practical consequences. Taken together, these results provide a common statistical language for relating scientific questions, data-generating assumptions, and algorithms, and clarify the conclusions that feature-importance analyses can support.

Abstract

Explore similar work

Null importance: Disentangling relevance for interpretable machine learning

CID: Measuring Feature Importance Through Counterfactual Distributions

Model-Agnostic FDR Control via Group Gaussian Mirror and Permutation SHAP