PERTURB: When Can We Trust a Feature Explanation?
In explainable AI, feature explainers such as SHAP and LIME report a single importance score per feature, even when the evidence actually allows a wider range of values. We present PERTURB, to our knowledge the first audit layer for feature explanations. Given what an analyst observes and assumes, it certifies an explanation, says which data to collect next, or proves that more data of the same kind cannot certify it. Its key idea is to perturb the population rather than the input: an explanation is an average of model queries over an unknown population, so bounding it over every population consistent with the evidence is a linear program, and each verdict comes with a certificate or a counterexample population. It needs only queries to a frozen model and applies to any explanation of this form, including interventional SHAP values. Three results follow. First, a model’s structure decides which population tables can verify its explanation: one-feature tables suffice for an additive model, and features that interact need a table of those features together. When the tables fall short, PERTURB computes the exact range the explanation could take. Second, PERTURB verifies SHAP explanations at scale. On U.S. Census data, for a typical person, it certifies the full SHAP ranking from two-feature tables in 46 to 49 of the 50 states and DC, depending on the model. It also catches explanations the evidence does not support, proving that one-feature tables support the full ranking for at most one person in 200. Third, published statistics already verify part of an explanation: from the tables the Census Bureau publishes, PERTURB certifies each model’s response to sex and names the release that would certify more. We give finite-sample certificates for declared, designed and audited evidence. PERTURB separates what the evidence identifies from what it cannot, so a responsible-AI review can tell which explanations to rely on.
Authors
- Xin Heng
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.5281/zenodo.24157158
- Primary Topic
- Explainable Artificial Intelligence (XAI)
- Type
- preprint