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

The gist The authors show that by replacing multiple random permutations with a single, deterministic, and optimal permutation, they achieve a method that retains the core principles of permutation-based importance while being non-random, faster, and more stable.

What is Variable Importance (VI)

There are at least three different notions of VI each one trying to answer a different question<ref:2512.13892#pg2> Population VI: “how important is this feature in the true population model?”<ref:2512.13892#pg2> Model class VI: “how important or replaceable is this feature in a model like this?”<ref:2512.13892#pg2> Model instance VI: “how much does this specific fitted model rely on this feature?”<ref:2512.13892#pg2> Classical permutation methods are some of the most popular VI methods among practitioners for several reasons including conceptual simplicity and intuitive appeal<ref:2512.13892#pg4>. However, there are at least four aspects of traditional permutation methods for direct VI estimation that can still be improved<ref:2512.13892#pg4>. These aspects include Randomness, Estimator variance, Improvable efficiency, and Evaluation metric<ref:2512.13892#pg4>.

One Optimal Permutation is Worth a Thousand Random Ones

The paper proposes replacing B random permutations by a single, deterministic and optimal permutation<ref:2512.13892#pg5>. This optimality criterion means that it perturbs all ranks of a given feature as much as possible and as evenly as possible<ref:2512.13892#pg5>. Given a sample size of n observations per feature, this goal is achieved by shifting the ranks of the feature at hand by ⌊n/2⌋ (modulo n)<ref:2512.13892#pg5>. The cyclic shift permutation πk(j) = (j + k) mod n with k = ⌊n/2⌋ satisfies m(πk) = ⌊n/2⌋, attaining the maximal possible value of the objective function<ref:2512.13892#pg5>. Proposition 1 proves that for any permutation π, m(π) ≤ ⌊n/2⌋<ref:2512.13892#pg5>. Proposition 2 shows that the single deterministic permutation wins in MSE for a given feature whenever its excess absolute bias relative to the Monte Carlo estimator is smaller than the Monte Carlo estimator’s standard error σj/√B<ref:2512.13892#pg7>.

Direct Variable Importance (DVI)

Definition 1 defines the estimated direct importance of a variable as d k:= 1/nq Σ i=1 n d(fM i(X) − fM i(Xk'))<ref:2512.13892#pg8>. This is defined as the expected immediate change in prediction after the signal in a feature is (largely) removed by permuting its values<ref:2512.13892#pg8>. The authors use mean absolute error (MAE, the default) or MSE and normalize final direct scores to sum to one<ref:2512.13892#pg8>.

Empirical Simulation Setup

The empirical simulation setup considered 192 individual scenarios in total, with varying sample size n, dimensionality p, noise level σε (Gaussian standard deviation), feature correlation ρ and choice of ground-truth linear/nonlinear regression or classification model, each repeated 50 times<ref:2512.13892#pg10>. The data-generating process is conceptually consistent across linear/nonlinear and regression/classification scenarios<ref:2512.13892#pg10>. Correlated features were designed using a block covariance matrix with stronger correlation among informative features (ρ = 0.3)<ref:2512.13892#pg11>.

Systemic Variable Importance (SVI)

Definition 2 defines the estimated systemic importance score s k of the k-th variable xk as the model prediction disruption that occurs when xk is permuted, and this perturbation is propagated to all other covariates<ref:2512.13892#pg17>. The propagation rule states that when the j-th feature, xj, is perturbed (permuted) to x'j, the permuted value of any other feature xk (k!= j) in the permuted data matrix X' is simultaneously updated according to the following rule: x'k ← x'k + cor(xk, xj) × (x'j − xj)<ref:2512.13892#pg17>. The final normalized systemic importance score sk is calculated as s raw k / Σ k=1 p s raw j<ref:2512.13892#pg18>. This score can be decomposed into its direct importance score (d k) and its indirect importance score (i k), where sk = d k + i k<ref:2512.13892#pg19>.

Results and Conclusions

The proposed methods are on average at least as accurate as Breiman-style VI methods across nearly 200 scenarios, while substantially more so in the more challenging scenarios tested<ref:2512.13892#pg5>. The authors confirm that their DVI method is strictly deterministic and reproducible, which is an essential property for model auditing, validation, and regulatory compliance<ref:2512.13892#pg7>. Furthermore, the SVI method reveals how models may indirectly rely on protected characteristics through correlation networks<ref:2512.13892#pg21>. In summary, this work introduces a unified, model-agnostic framework for both explaining model behavior and assessing its vulnerabilities<ref:2512.13892#pg5>. The authors offer practitioners and regulators a tool that is faster, more transparent, and better aligned with the systemic nature of model risk<ref:2512.13892#pg7>.

B Stability Across Repeated Independent Runs

The deterministic framework is designed to yield the exact same scores (and, hence, rankings) every single time it is run<ref:2512.13892#pg29>. In stark contrast, both classical baselines employing one or even ten repetitions yielded very unstable rankings for the top 5 features<ref:2512.13892#pg5>. The authors confirm that only their proposed methods (either with optimal or sub-optimal permutation) recovered the ground-truth top 5 components<ref:2512.13892#pg5>.

Additional Figures and Plots

The paper includes additional figures illustrating performance across various settings, such as Figure 3: Performance of different variable importance methods in linear regression with uncorrelated features and linear response under varying sample size, dimensionality and noise<ref:2512.13892#pg31>. The results confirm that our proposed single-permutation methods are similarly accurate in idealized conditions while the gap widens significantly in favor of our methods in more challenging (yet realistic) conditions<ref:2512.13892#pg5>. The analysis also shows that the systemic importance method allowed them to audit the sparse fitted model and confirm that it indeed does not rely to any meaningful extent on a protected attribute like sex or marital status<ref:2512.13892#pg24>.

Counterfactual Analysis With the trust-free Python Library

Figure 19 illustrates the direct counterfactual effect on prediction of variable black for observation number 35. This demonstrates that their proposed methods achieve a similar or slightly higher correlation with those scores compared to the classical baseline methods (around 0.98 in all cases). The authors also show that the direct counterfactual effect on prediction of black indeed typically is about 1% (see Figure 19 in Appendix D).

References

The paper cites numerous works including Breiman's foundational papers, Fisher et al., and specific contributions related to ghost variables and sparse models. The references include A. Alonso and J.M. Carb´o, R. W. Bostic, L. Breiman, P. Delicado and D. Pe˜na, A Dorador, A Fisher et al., N F¨oge et al., G Hooker et al., J Lei et al., W.-Y Loh and P Zhou, N Meinshausen, A Munnell et al., L S Shapley, C Strobl et al., and others. The references include A. Alonso and J.M. Carb´o, R. W.

1. Bold header: Deterministic Variable Importance (DVI) for Model Auditing

The improved system can provide scores that are strictly deterministic and reproducible – an essential property for model auditing, validation, and regulatory compliance by replacing multiple random permutations with a single, deterministic, and optimal permutation. This allows practitioners to assess fairness by using the method to audit models for hidden reliance on protected attributes (e.g., gender or race), enabling regulators and practitioners to assess fairness and systemic risk in a principled and computationally efficient manner.

2. Bold header: Systemic Variable Importance (SVI) for Contagion Risk Assessment

The system can quantify model vulnerability to correlated covariate corruption by calculating the expected disruption to model predictions when a single feature is perturbed and that perturbation is allowed to propagate to other covariates according to their empirical correlations. This allows for the detection of model risk where features are not used directly but rely on the sensitive attribute via proxy variables, such as in credit risk forecasting.

3. Bold header: Enhanced Stress-Testing and Regulatory Compliance

The framework enables a shift from traditional sensitivity analysis to a more robust assessment of model degradation, specifically by accounting for network effects and contagion risk. This allows regulators to move beyond classical sensitivity analyses that treat input changes in isolation to understand how correlated features amplify or dampen the importance of an original feature.

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 times n times p) to O(n times 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.