Informative Perturbation Selection for Uncertainty-Aware Post-hoc Explanations

Sumedha Chugh; Ranjitha Prasad; Nazreen Shah

cs.LGMar 16, 2026

Informative Perturbation Selection for Uncertainty-Aware Post-hoc Explanations

Authors: Sumedha Chugh, Ranjitha Prasad, Nazreen Shah

Organizations: Indraprastha Institute of Information Technology Delhi, India

Abstract

Trust and ethical concerns due to the widespread deployment of opaque machine learning (ML) models motivating the need for reliable model explanations. Post-hoc model-agnostic explanation methods addresses this challenge by learning a surrogate model that approximates the behavior of the deployed black-box ML model in the locality of a sample of interest. In post-hoc scenarios, neither the underlying model parameters nor the training are available, and hence, this local neighborhood must be constructed by generating perturbed inputs in the neighborhood of the sample of interest, and its corresponding model predictions. We propose Expected Active Gain for Local Explanations (EAGLE), a post-hoc model-agnostic explanation framework that formulates perturbation selection as an information-theoretic active learning problem. By adaptively sampling perturbations that maximize the expected information gain, EAGLE efficiently learns a linear surrogate explainable model while producing feature importance scores along with the uncertainty/confidence estimates. Theoretically, we establish that cumulative information gain scales as $\mathcal{O}(d \log t)$ , where $d$ is the feature dimension and $t$ represents the number of samples, and that the sample complexity grows linearly with $d$ and logarithmically with the confidence parameter $1/δ$ . Empirical results on tabular and image datasets corroborate our theoretical findings and demonstrate that EAGLE improves explanation reproducibility across runs, achieves higher neighborhood stability, and improves perturbation sample quality as compared to state-of-the-art baselines such as Tilia, US-LIME, GLIME and BayesLIME.

Figures & tables

Figure 1: Perturbation strategies on the make_moons [ 19 ] dataset (

n=100

). Existing methods either sample in the vicinity of the instance disregarding the regions of epistemic uncertainty (LIME, BayLIME), are constrained excessively close the instance of interest (GLIME), or fail to adapt to the locality and only focus on predictive variance (Focus Sampling/BayesLIME). In contrast, EAGLE (ours) selects perturbations that respect both locality and regions of high epistemic uncertainty while covering both sides of the decision boundary, resulting in a compact and informative neighborhood.

Method	Tabular Datasets				Image Datasets
Method	COMPAS	GERMAN	ADULT	MAGIC	MNIST	ImageNet
LIME	$0.772_{\pm 0.110}$	$0.645_{\pm 0.108}$	$0.669_{\pm 0.045}$	$0.647_{\pm 0.092}$	$0.733_{\pm 0.152}$	$0.704_{\pm 0.137}$
GLIME	$0.635_{\pm 0.082}$	$0.546_{\pm 0.111}$	$0.559_{\pm 0.107}$	$0.624_{\pm 0.080}$	$0.519_{\pm 0.290}$	$\mathbf{0.920_{\pm 0.08}}$
Tilia	$\mathbf{0.834_{\pm 0.077}}$	$0.721_{\pm 0.068}$	$0.783_{\pm 0.045}$	$0.647_{\pm 0.092}$	$0.733_{\pm 0.178}$	$0.734_{\pm 0.142}$
US-LIME	$0.525_{\pm 0.077}$	$0.400_{\pm 0.150}$	$0.419_{\pm 0.106}$	$0.587_{\pm 0.118}$	$0.749_{\pm 0.151}$	$0.760_{\pm 0.148}$
UnRAvEL	$0.501_{\pm 0.055}$	$0.332_{\pm 0.121}$	$0.276_{\pm 0.084}$	$0.427_{\pm 0.051}$	$0.148_{\pm 0.035}$	$0.099_{\pm 0.034}$

Table 1: Explanation stability (Jaccard Similarity

\uparrow

). Mean over 50 instances (standard deviation in subscript, best in bold , second-best underlined ).

Figure 2: Active sampling convergence behaviour: EAGLE consistently improves both

D

-efficiency and cumulative information gain, leading to higher AUCC across datasets.

Dataset	BayesLIME@500	EAGLE @	Saving	BayesLIME@500	EAGLE @	Saving	BayesLIME	EAGLE
	D-efficiency $\uparrow$			CCM $\uparrow$			Runtime(s) $\downarrow$
COMPAS	9.623	390	22%	0.604	70	86%	14.56	8.16
GERMAN	3.705	340	32%	0.653	180	64%	23.63	15.61
ADULT	3.724	310	38%	0.662	240	52%	17.27	10.46
MAGIC	7.050	310	38%	0.579	110	78%	31.29	26.72
MNIST	3.094	380	24%	0.648	60	88%	3.36	0.69

Table 2: Query savings achieved by EAGLE over BayesLIME across tabular and image datasets. BayesLIME@500 reports the value attained by BayesLIME at

n{=}500

queries; EAGLE @ gives the budget at which EAGLE reaches the same quality. The final columns report wall-clock runtime per explanation at

n{=}500

queries.

Figure 3: Hyperparameter sensitivity of EAGLE , reporting D-efficiency (solid) and CCM (dashed). (a) Prior precision

\lambda/d

: the default

\lambda{=}d

balances posterior concentration and explanation consistency. (b) Pool size

|\mathcal{P}|

: EAGLE maintains strong performance across all pool sizes, requiring no careful tuning. (c) Superpixel count: EAGLE adapts effectively to increasing dimensionality on both MNIST and ImageNet.

Method	Category	Runtime(s) on COMPAS
Method	Category	$N{=}50$	$N{=}100$	$N{=}200$	$N{=}500$
LIME	LIME-based	${0.028}\pm 0.001$	${0.038}\pm 0.001$	${0.056}\pm 0.003$	${0.113}\pm 0.003$
BayLIME	LIME-based	$0.029\pm 0.002$	$0.039\pm 0.001$	$0.058\pm 0.003$	$0.139\pm 0.022$
GLIME	LIME-based	$0.032\pm 0.001$	$0.045\pm 0.004$	$0.079\pm 0.004$	$0.160\pm 0.012$
DLIME	LIME-based	$0.020\pm 0.003$	$0.023\pm 0.003$	$0.029\pm 0.004$	$0.044\pm 0.004$
Tilia	LIME-based	$0.041\pm 0.001$	$0.061\pm 0.004$	$0.095\pm 0.010$	$0.241\pm 0.017$

Table 3: Wall-clock runtime (seconds, mean

\pm

std) per explanation on the COMPAS dataset across sample budgets

N\in\{50,100,200,500\}

Figure 4: Convergence of A-efficiency as a function of perturbation budget across tabular datasets. EAGLE consistently achieves higher A-efficiency with fewer perturbations compared to BayesLIME and BayLIME, indicating more informative perturbation selection.

Figure 5: Empirical cumulative distribution functions (ECDF) of A-efficiency at

n{=}500

across test instances. Curves further to the right indicate higher information gain. EAGLE consistently dominates the baselines across all datasets.

Figure 6: Convergence of D-efficiency (solid lines) and cumulative information gain (CIG, dashed lines) as a function of perturbation budget

n

across tabular datasets. Results are averaged over test instances. EAGLE consistently achieves higher efficiency with fewer perturbations compared to the baselines.

Figure 7: Empirical cumulative distribution functions (ECDF) of D-efficiency at

n=500

across test instances for all tabular datasets. Curves further to the right indicate higher efficiency. EAGLE consistently dominates the baselines.

Figure 8: Per-feature attribution estimates with

90\%

credible intervals (shaded regions), sorted by magnitude, for a randomly selected instance from the German Credit and Adult Income datasets. EAGLE consistently achieves the tightest credible intervals across features, indicating lower uncertainty in its explanations compared to BayesLIME and BayLIME

Figure 9: Visualization of explanations obtained using EAGLE for text spam detection dataset. Green highlights positive contributions toward the SPAM prediction, red indicates negative contributions, and border thickness represents attribution uncertainty.

Perturbation-Based Feature Attribution

Perturbation-based feature attribution explains model predictions by altering inputs and measuring how those changes affect outputs.

See all 39 papers

Mar 31, 2026

Uncertainty Gating for Cost-Aware Explainable Artificial Intelligence

Post-hoc explanation methods are widely used to interpret black-box predictions, but their generation is often computationally expensive and their reliability is not guaranteed. We propose epistemic uncertainty as a low-cost proxy for explanation reliability: high epistemic uncertainty identifies regions where the decision boundary is poorly defined and where explanations become unstable and unfaithful. This insight enables two complementary use cases:

improving worst-case explanations' (routing samples to cheap or expensive XAI methods based on expected explanation reliability), and

recalling high-quality explanations' (deferring explanation generation for uncertain samples under constrained budget). Across four tabular datasets, five diverse architectures, and four XAI methods, we observe a strong negative correlation between epistemic uncertainty and explanation stability. Further analysis shows that epistemic uncertainty distinguishes not only stable from unstable explanations, but also faithful from unfaithful ones. Experiments on image classification confirm that our findings generalize beyond tabular data.

Georgii Mikriukov, Grégoire Montavon, Marina M. -C. Höhne

Leibniz Institute for Agricultural Engineering and Bioeconomy (ATB), Potsdam, Germany · BIFOLD – Berlin Institute for the Foundations of Learning and Data, Berlin, Germany · Charité – Universitätsmedizin Berlin, Berlin, Germany +1

Explainable Artificial Intelligence Explainability Evaluation Epistemic Uncertainty Cost-Aware Inference

Ask PDF

Oct 1, 2026

MEA: A Reward-Driven Multi-Agent System for Faithful Model Explanations

Recent years have seen the employment of a plethora of machine learning (ML) models in high-stakes domains, but they remain largely opaque to the practitioners who act on their predictions. While post-hoc explanation methods offer a lens into this model behavior, wielding them effectively demands expertise most domain experts lack: navigating high-dimensional outputs, selecting the best explanations, and synthesizing evidence across disparate tools. To this end, we present MEA, a multi-agent framework that removes the explanation knowledge barrier entirely: a Proposer agent selects and configures explanation tools based on the question and modality, while an Actor agent is optimized end-to-end against faithfulness, transforming the outputs into natural language explanations grounded in model behavior across tabular, text, and vision modalities. Further, we introduce diverse question types spanning feature attribution, counterfactual reasoning, and spurious feature detection, each paired with a perturbation-based faithfulness metric. We find that frontier LLMs systematically produce unfaithful explanations. By optimizing against faithfulness rewards augmented with a modality-adaptive penalty, MEA consistently outperforms post hoc explainers, agentic, and closed-source baselines across six datasets, with reward-driven optimization yielding faithfulness gains of +28% (tabular), +21% (text), and +34% (vision) over the untrained backbone. More broadly, our findings suggest that AI agents themselves can serve as a scalable, adaptable interface to ML explainability, opening a path toward natural-language explainability that generalizes beyond the fixed, single-purpose tools that have long defined the field.

Yuyang Cheng, Raghav Kaushik Ravi, Srivarshinee Sridhar +3

University of Virginia · Vellore Institute of Technology · Indian Institute of Technology, Patna

Explainable Artificial Intelligence Faithfulness of Language Model Explanations Multi-Agent LLMs Explainability Evaluation

Ask PDF

May 26, 2026

Evaluating Local Explainability Metrics for Machine Learning Models on Tabular Data

Despite the wide use of explainability techniques to attempt to understand the behavior of Artificial Intelligence (AI), the generated explanations may not always be reliable. An explanation can appear plausible to humans but fail to capture the internal reasoning of a model, particularly when dealing with complex tabular data. This paper studies the trustworthiness of local explainability techniques when applied to complex tabular classification tasks, considering evaluated metrics for three main properties: faithfulness to the model's predictions, robustness to input data variations, and complexity of the explanation itself. A benchmark was performed for Local Interpretable Model-Agnostic Explanations (LIME), Kernel SHapley Additive exPlanations (SHAP), and Feature Ablation techniques, across 32 datasets and different types of machine learning models. Model performance ranges were analyzed to identify two groups: consensus-correct, which are samples that all models predicted correctly, and consensus-wrong, samples that all models predicted incorrectly. The obtained results demonstrate that that the explanations are not always correlated with a model's predictive performance. Instead, dataset complexity and feature distributions seem to be the main factors affecting explanation quality and reliability.

Tomás Pereira, João Vitorino, Eva Maia +1

GECAD, ISEP, Polytechnic of Porto, Porto, Portugal

Feature Attribution Explainable Artificial Intelligence Tabular Classification Tabular ML Explainability Evaluation

Ask PDF

Abstract

Perturbation-Based Feature Attribution

Explore similar work

Uncertainty Gating for Cost-Aware Explainable Artificial Intelligence

MEA: A Reward-Driven Multi-Agent System for Faithful Model Explanations

Evaluating Local Explainability Metrics for Machine Learning Models on Tabular Data