Explanation Multiplicity in SHAP: Characterization and Assessment

SHAP explanations are widely used in high-stakes settings to justify decisions, yet they can differ substantially across repeated runs, even when the model, the input instance, and the prediction are held fixed. Prior work has documented disagreement *between* explanation methods; we show that substantial disagreement arises even *within* SHAP across reruns of the same estimator on the same trained model and instance. We call this phenomenon *explanation multiplicity* and develop an evaluation methodology for characterizing it under deployment-realistic computational budgets, combining a dual-seed protocol that disentangles model-induced from explainer-induced variability, a hierarchy of magnitude-, rank-, and set-based metrics, and randomized Dirichlet and Mallows null models that calibrate when observed disagreement exceeds chance. Across multiple datasets, model classes, and sampling strategies, we find that explanation multiplicity is pervasive and persists even for high-confidence predictions. The dominant source depends on the data regime: model-induced variability dominates in small-data settings, while explainer-induced variability dominates at scale. Commonly used $\ell_2$ distance is largely insensitive to this instability, while rank-based metrics reveal severe reordering of top-ranked features. Improved sampling methods such as CTE do not eliminate rank-level multiplicity, and deterministic alternatives such as K-Means achieve stability only by targeting a different estimand that diverges sharply from Shapley values defined against the empirical training distribution. Practitioners should treat single-run SHAP outputs as realizations of a distribution rather than as authoritative artifacts.