A new paper argues you do not need hundreds of random shuffles to measure which inputs actually move a model's predictions. One well chosen shuffle will do.
Permutation feature importance normally works by randomly scrambling one input column at a time, rerunning the model, and averaging the damage over many repeats, which is slow and gives a different answer every time you run it. The authors replace that Monte Carlo process with a single deterministic permutation chosen to be max-min rank-optimal, cutting the computation from a cost that scales with the number of repeats to one that does not. They prove the method exactly recovers scaled regression coefficients under certain feature distributions and back it up with testing across nearly 200 simulated scenarios, where it shows a better balance of bias and variance in high-dimensional, low-signal data. The paper also adds two extensions: Systemic Feature Importance, which accounts for correlated proxy variables, and Importance Direction, which reports the sign of a feature's effect rather than just its size, both demonstrated on two credit risk case studies.
Feature importance already does real regulatory work in lending, where examiners want to know not just that a model leans on income or zip code, but how much and in which direction. Cutting out both the randomness and the heavy compute cost makes that kind of audit cheap enough to run routinely instead of as a one-off compliance exercise, which matters as banks face growing pressure to document model fairness around protected attributes.
The math checks out for linear and simulated cases. Whether a single perfect shuffle holds up on the messy, nonlinear models banks actually deploy in production is the harder test still ahead.