When we ask a post-hoc explanation method like LIME or SHAP why a machine learning model made a specific prediction, we expect a definitive, reproducible answer. We treat the explanation as a window into the model's internal logic. However, a growing body of research reveals that these explanations are often moving targets. If you run an explanation algorithm multiple times on the same input, or if you retrain the model using a different random seed, the resulting feature importance rankings can change dramatically.
This phenomenon—known as explanation multiplicity or stochastic explanation variance—undermines the reliability of explainable AI (XAI). To build truly trustworthy systems, we must understand why this instability happens and how researchers are working to fix it.
The Two Sources of Explanation Instability
To understand why explanations vary, we must disentangle where the randomness originates. As characterized by Hyunseung Hwang et al. in Explanation Multiplicity in SHAP: Characterization and Assessment, explanation variance stems from two distinct sources: the stochastic nature of the explanation algorithm itself, and the inherent randomness of model training.
Total Explanation Variance
├── Explainer-Induced Variance (Sampling Noise)
└── Model-Induced Variance (Training Randomness)
1. Explainer-Induced Variance (Sampling Noise)
Many popular local explanation methods are model-agnostic: they treat the underlying model as a black box and probe it by generating a random neighborhood of perturbed inputs. For instance, Elvio G. Amparore et al. demonstrate in To trust or not to trust an explanation: using LEAF to evaluate local linear XAI methods that this random neighborhood generation introduces severe stochastic jitter. If the explainer does not draw enough samples to accurately map the local decision boundary, repeated evaluations of the exact same data point will yield completely different feature importance rankings.
2. Model-Induced Variance (Training Randomness)
Even if an explanation method is perfectly deterministic, it can still produce unstable results if the underlying model is sensitive to training randomness. Deep neural networks are highly non-convex and are optimized using stochastic gradient descent, meaning that random weight initializations and mini-batch orderings cause models to land in different local minima.
Fabian Eitel et al. highlighted this issue in Testing the Robustness of Attribution Methods for Convolutional Neural Networks in MRI-Based Alzheimer's Disease Classification, showing that retraining the same network architecture on identical data can cause feature attribution methods to yield wildly inconsistent visual heatmaps. Similarly, Dylan Slack et al. found in On the Lack of Robust Interpretability of Neural Text Classifiers that two neural text classifiers differing only by their initial random seed frequently produce conflicting feature importance rankings, proving that an explanation can be a byproduct of optimization chance rather than generalized data patterns.
Why Sampling Introduces Jitter
To build intuition for explainer-induced variance, consider how game-theoretic frameworks like Shapley values operate. To calculate the exact contribution of a single feature, an algorithm must evaluate how the model's prediction changes across every possible combination of all other features. This requires an exponential number of model evaluations ($2^M$ for $M$ features), which quickly becomes computationally intractable.
To bypass this bottleneck, approximation methods like KernelSHAP rely on Monte Carlo sampling, randomly selecting a subset of feature coalitions to estimate the true Shapley values. As noted by Wangxuan Fan et al. in SIM-Shapley: A Stable and Computationally Efficient Approach to Shapley Value Approximation, when the number of samples is limited, this sampling process suffers from high internal variance. The features chosen in one random draw may differ significantly from the next, causing the estimated importance scores to fluctuate across separate runs.
This instability creates a severe vulnerability. Christopher Burger et al. demonstrated in "Are Your Explanations Reliable?" Investigating the Stability of LIME in Explaining Text Classifiers by Marrying XAI and Adversarial Attack that an adversarial attack can exploit this underlying sampling variance. By introducing minor, imperceptible tweaks to a text input, they could drastically alter LIME's feature attributions while keeping the model's actual prediction unchanged.
Algorithmic Solutions for Stabilization
To mitigate this variance and ensure that explanations reflect true model logic rather than stochastic noise, researchers have developed several distinct stabilization paradigms.
Variance Reduction via Control Variates
Instead of simply drawing more random samples—which is computationally expensive—we can use statistical variance reduction techniques. Jeremy Goldwasser et al. introduce this concept to game-theoretic XAI in Stabilizing Estimates of Shapley Values with Control Variates. By using local Taylor expansions of the model as a "control variate" (an easily computable approximation that correlates with the target function), they anchor the sampling process, reducing the variance of Shapley estimates by up to 90% without requiring additional model passes.
Amortized Explanation Models
Another way to eliminate sampling noise entirely is to replace inference-time sampling with a deterministic model. Chenghao Yang et al. pursue this in Efficient Shapley Values Estimation by Amortization for Text Classification by training a separate, dedicated neural network to directly predict the Shapley values of input tokens. This amortized approach bypasses the need to sample feature coalitions at runtime, delivering completely deterministic and stable explanations at a fraction of the computational cost.
Traditional Sampling: Input ──> [ Random Perturbations ] ──> [ Statistical Estimation ] ──> Unstable Explanation
Amortized Approach: Input ──> [ Trained Explainer NN ] ───────────────────────────────> Deterministic Explanation
Smoothing and Dimensionality Reduction
For gradient-based explanations (like saliency maps), instability often manifests as highly localized, brittle pixel noise. Zhuorui Ye et al. provide a rigorous theoretical analysis of this in Gaussian Smoothing in Saliency Maps: The Stability-Fidelity Trade-Off in Neural Network Interpretability, proving that adding Gaussian noise to inputs and averaging their gradients (SmoothGrad) mathematically stabilizes attribution maps across different model training runs. However, they reveal an inherent trade-off: this smoothing acts as a low-pass filter, increasing explanation stability at the cost of fidelity to the model's original, exact local gradients.
To achieve stability without sacrificing clarity, Shizhan Gong et al. propose a structural approach in A Super-pixel-based Approach to the Stable Interpretation of Neural Networks. By grouping raw inputs into semantically meaningful "super-pixels," they reduce the effective dimensionality of the input space, providing a mathematical guarantee of algorithmic stability while maintaining clear interpretability.
Hypothesis Testing Frameworks
When evaluating data attribution (determining which training examples most influenced a prediction), training randomness makes single-point estimates highly unreliable. To resolve this, Subhodip Panda et al. developed f-INE: A Hypothesis Testing Framework for Estimating Influence under Training Randomness. Instead of treating influence as a fixed scalar, their framework frames influence estimation as a statistical hypothesis test, allowing practitioners to compute stable, reproducible data-influence scores that account for training variance within a single run.
Even when designing inherently interpretable architectures to avoid post-hoc tools altogether, randomness remains a challenge. For instance, Liren Shan shows in Near-Optimal Algorithms for Explainable k-Medians and k-Means that the randomized construction of human-readable decision trees can introduce high structural variance across different runs, emphasizing that managing stochasticity is a fundamental requirement across all facets of explainable machine learning.