Paper deep dive
Informative Perturbation Selection for Uncertainty-Aware Post-hoc Explanations
Sumedha Chugh, Ranjitha Prasad, Nazreen Shah
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/22/2026, 5:16:13 AM
Summary
The paper introduces EAGLE (Expected Active Gain for Local Explanations), a post-hoc model-agnostic explanation framework that uses an information-theoretic active learning approach to select perturbations. By maximizing expected information gain, EAGLE efficiently learns a linear Bayesian surrogate model, providing both feature importance scores and uncertainty estimates. The authors provide theoretical guarantees on cumulative information gain and sample complexity, demonstrating superior explanation stability and neighborhood fidelity compared to baselines like LIME, BayesLIME, and GLIME.
Entities (6)
Relation Signals (3)
EAGLE → implements → Active Learning
confidence 95% · EAGLE framework, which leverages an expected information gain active learning criterion
EAGLE → uses → Bayesian Linear Regression
confidence 95% · For the linear Bayesian surrogate formulation, we propose a novel acquisition function
EAGLE → outperforms → LIME
confidence 90% · EAGLE improves explanation reproducibility across runs... as compared to state-of-the-art baselines such as Tilia, US-LIME, GLIME and BayesLIME.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 \emph{Expected Active Gain for Local Explanations} (\texttt{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, \texttt{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/\delta$. Empirical results on tabular and image datasets corroborate our theoretical findings and demonstrate that \texttt{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.
Tags
Links
- Source: https://arxiv.org/abs/2603.14894v2
- Canonical: https://arxiv.org/abs/2603.14894v2
Trouble viewing inline? Open PDF directly →
Full Text
84,115 characters extracted from source content.
Expand or collapse full text
11institutetext: Ïndraprastha Institute of Information Technology Delhi (IIIT-Delhi)"‘11email: sumedhac@iiitd.ac.in Informative Perturbation Selection for Uncertainty-Aware Post-hoc Explanations Sumedha Chugh(✉) Ranjitha Prasad Nazreen Shah 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 (dlogt)O(d 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/δ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. 1 Introduction Explainable AI (XAI) seeks to make predictions interpretable, a goal reinforced by regulations such as the EU AI Act and GDPR [GDPR]. Due to the growing complexity of modern systems and the use of pre-trained models, post-hoc approaches are often preferred for their broader applicability and scalability [posthoc]. Popular post-hoc model-agnostic approaches such as LIME [lime], US-LIME [uslime], BayLIME [zhao2021baylime] and GLIME [GLIME2023] explain complex model predictions by fitting local surrogate models using constraints or prior assumption in sampling strategies. Explanations provided using surrogate-based methods are statistical estimates, and hence, uncertainty naturally arises due to (a) finite perturbation samples, (b) randomness in sampling methods used, (c) surrogate model approximation error and (d) noise that arises in model predictions. Consequently, explanations may vary significantly across instantiations and fail to capture the local behavior of the black-box models. Hence, explanations without measures of confidence alongside may be misleading. This motivates the need for principled Bayesian approaches that explicitly quantify uncertainty in local explanations [zhao2021baylime, slack2021reliable]. Among Bayesian approaches, UnRAvEL [unravel] utilizes Bayesian optimization for perturbation sampling via acquisition functions that balance exploration and exploitation, but this strategy can introduce sampling bias due to repeated selection of points close to the local instance. Several papers in literature employ Bayesian linear regression as the surrogate model as this framework naturally captures uncertainty in feature importance through posterior distributions while being computationally tractable and interpretable. BayesLIME [slack2021reliable] uses the posterior distributions over feature importance and selects perturbations based on predictive variance as a proxy for uncertainty in local predictions, making it one of the few methods that leverages uncertainty for perturbation selection. However, the sampling strategy in BayesLIME is heuristic and does not explicitly incorporate locality information when evaluating candidate perturbations. This raises a natural question - Can we derive principled sample-efficient perturbation selection strategies that directly minimize explanation uncertainty while preserving locality, leading to improved local fidelity? A principled approach to improving local explanation stability requires distinguishing between two fundamentally different sources of uncertainty, aleatoric and epistemic [NIPS2017_7141]. For perturbation-based post-hoc explanation methods, sampling driven by aleatoric noise is ineffective as it only captures irreducible variability in data instead of reducing the epistemic uncertainty of the surrogate model used to obtain feature attributions. This motivates the use of active learning which focuses on selecting maximally informative samples in regions of high epistemic uncertainty [rethinkingunc, activele]. Contributions: We propose the Expected Active Gain for Local Explanations (EAGLE) framework, which leverages an expected information gain active learning criterion to guide perturbation selection toward maximally informative regions. In particular, for the linear Bayesian surrogate formulation, we propose a novel acquisition function, which selects perturbations that maximize the expected reduction in posterior uncertainty over the explanation coefficients while retaining locality information during perturbation selection, ensuring that sampling remains focused on the neighborhood of the instance of interest. Based on the posterior covariance matrix of the Gaussian surrogate model, we provide a theoretical analysis of the proposed acquisition strategy. In particular, (a) we characterize the growth rate of the cumulative information gain and (b) derive high-probability bounds on the estimation error of the explanation weights. This analysis leads to sample complexity guarantees for the proposed approach. We provide empirical results that validate the theoretical findings and demonstrate the practical effectiveness of EAGLE. Experiments on image datasets such as MNIST, ImageNet, together with tabular datasets including COMPAS, German Credit, Adult Income, and Magic (Gamma Telescope), demonstrate that EAGLE improves sampling quality and enhances explanation stability as compared to the state of the art baselines, based on metrics such as Jaccard similarity, D-efficiency and Cumulative information gain.These results empirically corroborate our theoretical analysis, which establishes information gain bounds and sample complexity guarantees for the proposed acquisition strategy. Figure 1: Perturbation strategies on the make_moons dataset (n=100n=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. 2 Related Works Perturbations based local post-hoc explainers: Perturbations based local post-hoc explainers obtain instance level interpretations by generating samples in the neighborhood of a target input and fitting a simple, interpretable model on the resulting surrogate dataset. Popular linear surrogate methods include LIME [lime] and DLIME [dlime] which learns a sparse linear surrogate under a proximity based kernel weighting. While these methods promise simplicity and flexibility, they rely on random perturbation generation based on several design choices on kernel width, sampling distributions, etc. This results in instability as explanations can vary across runs, even for the same instance and model [alvarez2018robustness]. GLIME partially solved the issue of instability by constraining sampling to a specific predefined region [GLIME2023]. Subsequent work such as Tilia [tilia] moved away from linear surrogate models to decision trees in order to provide structured explanations. Notably, these methods output a single attribution vector as a point estimate; they do not explicitly quantify uncertainty or provide any notions of explanation reliability. Stable Local Explanations via Guided Sampling: Several works in literature have focused on improving the stability and fidelity of local explanations by controlling the random perturbation strategy. For instance, GLIME [GLIME2023] extends LIME by sampling directly from a locality focused distribution to achieve faster convergence and consistent explanations. US-LIME [uslime] improves LIME by selecting perturbations that are both close to the decision boundary (via uncertainty sampling) and close to the target instance. BayLIME [zhao2021baylime] uses priors over feature attributions for stability, without considering them for perturbation selection. UnRAvEL [unravel] uses a Gaussian process (GP) within a Bayesian optimization (BO) surrogate and a novel acquisition to trade off local fidelity and information gain. While these methods collectively demonstrate that informative or constrained sampling improves stability of explanations, they rely on heuristics or fixed sampling criteria and hence, they do not eliminate instability. Bayesian Approaches for Uncertainty Quantification: Knowing how much to trust an explanation is as important as the explanation itself. With this view in mind, many post hoc explainers augment feature importance values with uncertainty/confidence estimates. Among Bayesian approaches, UnRAvEL [unravel] utilizes Bayesian optimization for perturbation sampling. A well-known approach is Focused Sampling or BayesLIME [slack2021reliable] which provides credible intervals for each feature’s contribution, and in particular, proposes to sample perturbations with high posterior predictive variance. Novelty: The proposed EAGLE framework leverages a information-theoretic acquisition strategy to maximize the expected information gain in the samples, leading to the reduction in uncertainty in the surrogate explanation model. This strategy lets EAGLE prioritize sample queries that naturally target regions where the surrogate epistemic uncertainty is high, enabling the method to explore informative areas of the perturbation space. To the best of the authors’ knowledge, this is the first principled framework in the literature. Based on the complexity of data and model, theoretical guarantees help in choosing adequate number of queries to ensure sufficient growth of the cumulative information gain and ensure upper bounds on the estimation error of the explanation weights. 3 Problem Setting and Bayesian Surrogate Modeling Let fb:ℝd→[0,1]f_b:R^d→[0,1] denote a black-box classifier that outputs a label yiy_i for input i∈ℝdx_i ^d. The goal of post-hoc model agnostic explainer is to explain the prediction y0=fb(0)y_0=f_b(x_0) for a particular instance 0x_0. A set of N perturbations around 0x_0, denoted by =ii=1NZ=\z_i\_i=1^N where i∈ℝdz_i ^d with their black-box predictions fb(i)f_b(z_i) is employed to develop an interpretable surrogate model fef_e. To enforce locality, iz_i is assigned a proximity weight π0(i) _x_0(z_i) based on its distance from 0x_0. Subsequently, fef_e is trained by minimizing the locality-aware weighted loss ℒ(fe,fb,π0)=∑i=1Nπ0(i)(fb(i)−fe(i))2. (f_e,f_b, _x_0)= _i=1^N _x_0(z_i)\, (f_b(z_i)-f_e(z_i) )^2. (1) Finally, the explanation is represented by feature importance scores ϕ∈ℝd φ ^d derived from fef_e. A popular example is LIME, where fef_e is linear and ϕ φ corresponds to the coefficients of the linear model [lime]. Bayesian Surrogate Formulation: Uncertainty-aware approaches [slack2021reliable] model the surrogate fef_e using Bayesian linear regression as: fe(i) f_e(z_i) =i⊤ϕ+ϵi,ϵi∼(0,σ2π0(i)), =z_i φ+ _i, _i \! (0, σ^2 _x_0(z_i) ), (2) where ϕ∈ℝd φ ^d are regression coefficients representing feature contributions. Following prior work, we define a locality weighting function π0() _x_0(z) controlling the size of the local neighborhood around the instance of interest 0x_0. Specifically, the locality weight π0(i) _x_0(z_i) ensures that perturbations closer to 0x_0 are modeled with higher precision, while allowing larger variance for distant points. Placing conjugate priors on ϕ φ and σ2σ^2 where ϕ∣σ2∼(0,σ2d) φ σ^2 (0,σ^2I_d), and σ2∼Inv-χ2(n0,σ02)σ^2 -χ^2(n_0, _0^2), we obtain posterior distributions as ϕ∣σ2,,∼(ϕ^,ϕσ2),σ2∣,∼Scaled-Inv-χ2(n0+N,n0σ02+s2n0+N), φ σ^2,Z,y ( φ,V_ φσ^2), σ^2 ,y -Inv-χ^2\! (n_0+N,\; n_0 _0^2+s^2n_0+N ), where =[y1,…,yN]⊤y=[y_1,…,y_N] denotes the vector of black-box responses for the perturbations ii=1N∈\z_i\_i=1^N , with yi=fb(i)y_i=f_b(z_i). Equivalently, the likelihood can be written in terms of the weighted design matrix ∈ℝN×dZ ^N× d, whose rows correspond to perturbations i∈z_i , together with the diagonal weight matrix =diag(Π0())W=diag\! ( _x_0(Z) ). Here, Π0() _x_0(Z) denotes the vector of locality kernel evaluations applied row wise to Z. Further, the posterior mean is given by ϕ^=ϕ⊤ φ=V_ φ\,Z Wy, where ϕ _ φ =(⊤+d)−1s2=(−ϕ^)⊤(−ϕ^)+ϕ^⊤ϕ^. = (Z WZ+I_d )^-1 s^2=(y-Z φ) W(y-Z φ)+ φ φ. (3) The posterior mean ϕ φ serves as the local feature importance scores. The posterior predictive distribution for a new perturbation iz_i is a Student-t given as y^(i)∣,∼tν=n0+N(ϕ^⊤i,(1+i⊤ϕi)s2), y(z_i) ,y t_ν=n_0+N\! ( φ z_i,\; (1+z_i V_ φz_i )s^2 ), (4) whose variance is given as var(y^(i))=((iTϕi+1)s2)ν−2var( y(z_i))=((z_i^TV_ φz_i+1)s^2) ν-2, where n0n_0 is a prior parameter. In [slack2021reliable], the authors use the predictive variance, var(y^(i))var( y(z_i)) as a proxy for local model uncertainty. 4 Proposed Approach: EAGLE We introduce the Expected Active Gain for Local Explanations (EAGLE) framework which adopts an active learning strategy to iteratively select the next sample perturbation ⋆z from a candidate pool P by maximizing an acquisition function (;fe)A(z;f_e), which quantifies the informativeness of a candidate perturbation z for improving the surrogate model fef_e: ⋆=argmax∈E(;fe). = _z A_E(z;f_e). (5) We instantiate the EAGLE acquisition function using an information-theoretic criterion that maximizes the expected information gain in the parameters as: E(;fe)=y∣,[H(ϕ∣)−H(ϕ∣∪(,y))], _E(z;f_e)=E_y ,z [H ( φ )-H ( φ ∪\(z,y)\ ) ], (6) i.e.., E(;fe)A_E(z;f_e) selects the sample z that result in maximum expected reduction in entropy of the surrogate parameters ϕ φ. In the supplementary, we derive the acquisition function E(;fe)A_E(Z;f_e), which characterizes the expected information gain of a set of perturbations in Z. Using such an acquisition function is complex, it is not directly suitable for sequential (greedy) or batch sample selection. In the following lemma, we provide the acquisition function under single-step greedy approach to maximize the predictive variance. Theorem 4.1 Consider a Bayesian linear surrogate model given in (2) and the posterior covariance in (3). Let the EAGLE-based acquisition function be defined as in (6). Then, under single-step greedy acquisition, maximizing E()A_E(z) over a candidate pool is equivalent, up to additive and multiplicative constants independent of z, to the following: argmaxE(;fe)=argmaxπ0()⊤ϕ. _zA_E(z;f_e)= _z\; _x_0(z)\ z V_ φz. (7) Theorem 4.1 shows that, for a Bayesian linear surrogate model, maximizing the expected information gain used in the EAGLE framework is equivalent to selecting the perturbations that maximize the locality-weighted posterior uncertainty. 5 Theoretical Analysis: EAGLE In this section, we analyze the sample complexity of weighted expected information gain driven perturbation selection and characterize the rate at which uncertainty in the surrogate explanation decreases. We consider a Bayesian linear regression surrogate defined in (2) over a set of perturbations =[1,…,N]Z=[z_1,…,z_N], where the surrogate prediction at a perturbation z is given by y^()=⊤ϕ y(z)=z φ. Further, let ϕ⋆∈ℝd φ ^d denote the true (unknown) importance vector representing the ground-truth local explanation. We assume predictions pertaining to the t-th query sample are generated according to the linear model yt=t⊤ϕ⋆+εt,εt∼(0,σ2), y_t=z_t φ + _t, _t (0,σ^2), (8) and that perturbations satisfy the boundedness condition ‖t‖2≤1\|z_t\|_2≤ 1 for all t. From the previous section, we know that under this model, the posterior precision matrix for the perturbations in Z is given by ϕV_ φ. Here, we introduce a notation to represent the covariance matrix for after t perturbations as ϕ,tV_ φ,t. From (3), the covariance matrix updated for the t-th sample is given as ϕ,t−1=ϕ,t−1−1+π0()tt⊤V^-1_ φ,t=V_ φ,t-1^-1+ _x_0(z)\,z_tz_t , where tz_t refers to the sample obtained using EA_E as in (7). Expanding ϕ,t−1−1V_ φ,t-1^-1 recursively and using ϕ,0=V_ φ,0=I, we obtain ϕ,t−1=+∑s=1tπ0(s)ss⊤. _ φ,t^-1=I+ _s=1^t _x_0(z_s)\,z_sz_s . (9) This formulation allows us to analyze how weighted EIG-based sampling reduces uncertainty in the explanation parameters and induces concentration of the posterior mean around the ground-truth importance vector ϕ⋆ φ . Algorithm 1 EAGLE: Expected Active Gain for Local Explanations 1:Black-box fbf_b, instance 0x_0, seed S, batch size B, pool size A, budget N 2:Generate S seed perturbations =1,…,SZ=\z_1,…,z_S\ around 0x_0 3:Query ←[fb(1),…,fb(S)]⊤y←[f_b(z_1),…,f_b(z_S)] 4:Fit surrogate: ϕ^,ϕ←BLR(,,π0) φ,V_ φ (Z,y, _x_0) ⊳ Eq. (3) 5:for t=S+1t=S+1 to N in batches of B do 6: Draw candidate pool ←AP← A perturbations near 0x_0 7: for each ∈z do 8: a()←π0()⋅⊤ϕa(z)← _x_0(z)·z V_ φ\,z ⊳ Eq. (7) 9: end for 10: Select the top B candidates: ℬ←argtopBa()B _B\;a(z) ⊳ Greedy selection 11: Query fbf_b on ℬB; update ←∪ℬZ , ←[;fb(ℬ)]y←[y;f_b(B)] 12: Refit surrogate: ϕ^,ϕ←BLR(,,π0) φ,V_ φ (Z,y, _x_0) 13:end for 14:return ϕ φ, ϕV_ φ Lemma 1 Given Bayesian linear regression surrogate in (2), the set of perturbations Z with corresponding predictions, y^() y(z), ϕ,0=∈ℝd×dV_ φ,0=I ^d× d and posterior covariance after t queries given by (9), assuming ‖t‖2≤1\|z_t\|_2≤ 1 and 0≤π0(t)≤10≤ _x_0(z_t)≤ 1 for all t≥1t≥ 1, expected information gain acquisition obtained in (7) leads to ∑s=1tπ0(s)s⊤ϕ,s−1s≤ 2dlog(1+td). _s=1^t _x_0(z_s)\,z_s V_ φ,s-1z_s\;≤\;2d \! (1+ td ). Remark: From the above lemma, we infer that as t increases, the information matrix ϕ,t−1V_ φ,t^-1 grows monotonically (since each summand is positive semidefinite), and consequently the covariance ϕ,tV_ φ,t shrinks, reflecting reduced uncertainty. Since the determinant satisfies |ϕ,t|=∏i=1dλi(ϕ,t)|V_ φ,t|= _i=1^d _i(V_ φ,t), the determinant of the posterior matrix measures the volume of the confidence ellipsoid. Hence log|ϕ,0|−log|ϕ,t|=log|ϕ,0||ϕ,t| |V_ φ,0|- |V_ φ,t|= |V_ φ,0||V_ φ,t|, quantifies the total reduction in uncertainty volume. In the sequel, we plot D-efficiency, which is proportional to te uncertainty volume. Note that ∑s=1tπ0(s)s⊤ϕ,s−1s _s=1^t _x_0(z_s)\,z_s V_ φ,s-1z_s represents the contribution of the t samples towards reduction in uncertainty. Further, this bound demonstrates that even when queries are chosen using EA_E to maximize information gain, the total accumulated information grows only logarithmically in t; this is the diminishing returns phenomenon where early queries substantially reduce uncertainty, while later queries contribute lesser. The multiplicative factor d indicates that the total information gain scales with the number of independent directions. Since d is fixed and as t→∞t→∞, we have ∑s=1tπ0(s)s⊤ϕ,s−1s=(dlogt) _s=1^t _x_0(z_s)\,z_s V_ φ,s-1z_s=O(d t). Theorem 5.1 Given the source linear model in (8), ϕ⋆∈ℝd φ ^d as the true (unknown) importance vector and t:=∑s=1tπ0(s)ss⊤S_t:= _s=1^t _x_0(z_s)z_sz_s , then for any δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, ‖ϕ^t−ϕ⋆‖ϕ,t−1≤σd+2dlog1δ+2log1δ+‖ϕ⋆‖Vϕ,t−1.\| φ_t- φ \|_V_ φ,t^-1≤σ d+2 d 1δ+2 1δ+\| φ \|_V_ φ,t^-1. (10) Corollary 1(Sample Complexity for ℓ2 _2-Accuracy) Under the assumptions of Theoremm 5.1, suppose that minimum eigen value of tS_t represented as λmin(t)≥κtfor some κ>0 _ (S_t)≥κ t some κ>0. Then for any ν>0ν>0 and δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, ‖ϕ^t−ϕ⋆‖2≤ν\| φ_t- φ \|_2≤ν whenever t≥1κ((βδ+‖ϕ⋆‖2)2ν2−1), t≥ 1κ ( ( _δ+\| φ \|_2)^2ν^2-1 ), (11) where βδ=σd+2dlog1δ+2log1δ _δ=σ d+2 d 1δ+2 1δ. Sample Complexity: From the corollary we obtained the sufficient condition on the number of sample queries t as a function of data and the model performance. In (11), ignoring the negligible constant term −1-1 for large t, and noting that 2dlog1δ≤d+log1δ2 d 1δ≤ d+ 1δ, we have βδ2=(d+log1δ) _δ^2=O\! (d+ 1δ ). If ‖ϕ⋆‖2\| φ \|_2 is treated as a fixed constant independent of t, then (βδ+‖ϕ⋆‖2)2=(d+log1δ)( _δ+\| φ \|_2)^2=O\! (d+ 1δ ). Substituting this into the lower bound on t gives t=(d+log(1/δ)κν2).t=O\! ( d+ (1/δ)κν^2 ). The result above states that, the required number of queries under EA_E acquisition function grows linearly with the dimension d, logarithmically with the confidence parameter 1/δ1/δ, and quadratically with the inverse accuracy 1/ν21/ν^2. Thus, achieving higher precision demands a quadratic increase in samples, while increasing confidence only incurs a mild logarithmic penalty. Relationship to Existing Local Surrogate Methods: Perturbation-based explanation methods primarily differ in how they generate samples in the neighborhood of 0x_0, and the explainer they employ. LIME generates perturbations ∼p()z p(z) independently from a predefined distribution and fits a locally weighted linear surrogate by minimizing ∑i=1nπ0(i)(f(i)−i⊤)2 _i=1^n _x_0(z_i) (f(z_i)-z_i w )^2, where π0() _x_0(z) is a locality kernel assigning higher weights to perturbations closer to 0x_0. In this formulation, perturbations are sampled independently of their informativeness. GLIME, which generalizes several methods such as ALIME, DLIME, etc, modifies this procedure by absorbing the kernel weight into the sampling distribution; by sampling perturbations from a local distribution proportional to the kernel, ∼q()∝πx0()z q(z) _x_0(z). While this improves stability, perturbations are still drawn i.i.d. from a fixed distribution, i.e., the sampling process does not adapt to the information contained in previously observed perturbations. Uncertainty Sampling LIME (US-LIME) extends the perturbation strategy of LIME then selects samples that are both close to the instance and near the black-box decision boundary using an uncertainty-sampling criterion based on class probabilities. Unlike LIME-based methods that employ linear surrogates, Tilia uses a decision tree surrogate to capture nonlinear feature interactions. However, for all of the above methods, perturbations are still generated from a predefined distribution around 0x_0 with heuristic or self-defined notions of uncertainty. Another family of explainers is the model-agnostic post-hoc Bayesian explainers, such as BayLIME and BayesLIME, which extend the LIME framework by modeling the importance weights as random variables and performing Bayesian linear regression to obtain posterior uncertainty over these weights. The details of modeling in BayesLIME are as given in Sec. 3. BayesLIME relies on a heuristic, namely the variance of the predictions var(y^())var( y(z)) for subsampling from a randomly sampled pool around 0x_0. In particular, given the perturbations in Z, the locality kernel π(⋅) _x(·) influences the surrogate model only through the weights assigned to the already observed perturbations via VϕV_φ and s2s^2. When evaluating a new candidate perturbation z, BayesLIME considers the predictive variance which in turn does not consist of the locality information of the current sample z, via π() _x(z). Hence, BayesLIME’s acquisition strategy is not locality-aware when choosing new perturbations. The quantity Tϕz^TV_ φz, common to both BayesLIME and EAGLE, is the squared Euclidean norm of z in the geometry induced by ϕV_ φ. Intuitively, this quantity measures how strongly the candidate perturbation lies in directions where the posterior covariance of the explanation parameters are large. The variable s2s^2 is a global scaling factor, and does not contain any information regarding the locality. In contrast, EAGLE is a principled approach where we derived the novel acquisition function as argmaxπ0()⊤ϕ _z _x_0(z)\,z V_ φz. Here, the quadratic term ⊤ϕz V_ φz plays the same role as in BayesLIME. However, the distinguishing factor is the term π0() _x_0(z) which enforces locality around the instance being explained. Intuitively, this rule prioritizes perturbations that both lie close to 0x_0 and provide maximal information about uncertain directions of the surrogate parameters. In addition, the principled derivation of EAGLE allows us to establish theoretical guarantees regarding information gain and sample complexity. 6 Experiments We empirically evaluate the proposed EAGLE framework to evaluate whether the information gain–based acquisition strategy of EAGLE improves perturbation sampling by reducing surrogate uncertainty. We compare against existing perturbation-based explanation methods across tabular and image datasets Datasets: We evaluate our EAGLE framework across six datasets spanning tabular and image modalities, chosen to reflect a range of feature dimensionalities, decision boundaries, and application domains. Tabular Datasets: We consider four widely used tabular benchmarks, (a) COMPAS is a dataset containing demographic and criminal history features used to predict two-year recidivism risk [COMPAS], (b) German Credit dataset consists of features encoding financial and personal attributes, used to classify applicants as good or bad credit risks [german], (c) Adult Income dataset contains records from the 19941994 U.S. Census, with the task of predicting whether an individual’s annual income exceeds a certain threshold based on demographic and employment features [adult], and (d) Magic (Gamma Telescope) dataset comprises features derived from Monte Carlo simulations of high energy gamma particles, used to distinguish gamma signal events from hadronic background [magic]. These four datasets vary in size, feature count, and class balance, providing a comprehensive benchmark for evaluating explanation stability and faithfulness in the tabular setting. Image Datasets: We additionally evaluate EAGLE on two image classification tasks to assess its applicability to high dimensional inputs, where explanations operate over interpretable superpixel regions. The two datasets are as follows: (a) MNIST is a dataset of 28×28 grayscale handwritten digit images [mnist], and (b) ImageNet (224×224 images) is drawn from the ILSVRC-2012 challenge and presents a substantially more challenging setting with high-resolution natural images [ImageNet]. The ImageNet experiments test EAGLE’s scalability to realistic image classification scenarios where the number of superpixel features and the complexity of the decision boundary are significantly higher than in MNIST. Experimental Setup: For all tabular datasets, we train a Random Forest classifier with 100100 estimators as the black-box model, using an 80/2080/20 train-test split with standard scaling applied to the features. It achieves test accuracy of 83.7%,71.5%,83.1%83.7\%,71.5\%,83.1\%, and 86.8%86.8\% on COMPAS, German Credit, Adult Income, and Magic, respectively. For image datasets, we segment each input into superpixel regions using SLIC [slic]. ImageNet images are segmented into 5050 superpixels for natural images, while simpler MNIST images are segmented into 2020 superpixels. For MNIST, we use a Convolutional Neural Network (CNN) with two layers, achieving 99.15%99.15\% test accuracy. For ImageNet, we use a pretrained VGG-16 model (torchvision), achieving an accuracy of 93%93\%. The acquisition process begins with S=10S=10 seed perturbations, after which samples are selected in batches of B=10B=10 from a candidate pool of A=1000A=1000, up to a total budget of N=500N=500 queries. We evaluate 50 test instances (samples of interest) per dataset. The Bayesian linear regression surrogate uses prior with precision λ=dλ=d, scaling the regularization strength with the input dimensionality. The kernel width is set to 0.75d0.75 d, where d is the number of input features, following the standard LIME configuration. Baselines: We compare our approach against several perturbation-based local explanation methods and their variants that differ in perturbation generation strategies and surrogate modeling approaches. In particular, we evaluate our proposed acquisition function within the EAGLE framework and compare it against the following baselines. LIME [lime](2016): generates local explanations by sampling perturbations around an instance and fitting a locality-weighted sparse linear surrogate model. GLIME [GLIME2023](2023): improves LIME by generating perturbations using a kernel-based sampling strategy that preserves feature dependencies in the data distribution. BayLIME [zhao2021baylime](2021) extends LIME by employing a Bayesian linear model and prior for uncertainty in feature importance estimates. DLIME [dlime](2021) improves explanation stability by generating perturbations from clusters learned from the dataset rather than random sampling. US-LIME [uslime](2024) models uncertainty in the perturbation process to produce more reliable local explanations. Tilia [tilia](2025) replaces the linear surrogate with a shallow decision tree to better capture nonlinear local decision boundaries. BayesLIME [slack2021reliable](2021) Also called Focus Sampling selects perturbations that are most informative for improving the Bayesian surrogate model. UnRAvEL [unravel](2022) selects perturbations using GP based BO to maximize the relevance of sampled instances for local surrogate training. 6.1 Comparison with Baselines Explanation Stability: A stable explanation method should produce consistent feature attributions across independent runs on the same instance. To evaluate this, we measure the pairwise overlap between the top-55 features selected across repeated explanations using Jaccard similarity. Given two feature sets SiS_i and SjS_j of size k, Jaccard(i,j)=|Si∩Sj||Si∪Sj|,Jaccard(i,j)= |S_i∩ S_j||S_i∪ S_j|, averaged over all pairs of runs and all test instances. A Jaccard score of 11 indicates that every run identifies the same top features, while lower values indicate instability in the explanation. In Table 1, we compare the stability performance of EAGLE against the baseline explanation methods across tabular and image datasets. EAGLE consistently achieves the highest or near-highest stability across most datasets, demonstrating the effectiveness of the proposed strategy. On tabular datasets, EAGLE significantly outperforms existing methods such as LIME, BayLIME, and GLIME. On image datasets, EAGLE also provides the most stable explanations, outperforming perturbation-based baselines by a substantial margin. While some baselines such as Tilia and US-LIME achieve competitive results on specific datasets, their performance varies considerably across tasks, indicating limited robustness. In contrast, EAGLE maintains consistently strong performance across both tabular and image domains. Note that DLIME is not evaluated on image datasets because its clustering-based neighborhood construction does not directly extend to high-dimensional image inputs. Table 1: Explanation stability (Jaccard Similarity ↑ ). Mean over 50 instances (standard deviation in subscript, best in bold, second-best underlined). Method Tabular Datasets Image Datasets COMPAS GERMAN ADULT MAGIC MNIST ImageNet LIME 0.772±0.1100.772_± 0.110 0.645±0.1080.645_± 0.108 0.669±0.0450.669_± 0.045 0.647±0.0920.647_± 0.092 0.733±0.1520.733_± 0.152 0.704±0.1370.704_± 0.137 GLIME 0.635±0.0820.635_± 0.082 0.546±0.1110.546_± 0.111 0.559±0.1070.559_± 0.107 0.624±0.0800.624_± 0.080 0.519±0.2900.519_± 0.290 0.920±0.080.920_± 0.08 Tilia 0.834±0.0770.834_± 0.077 0.721±0.0680.721_± 0.068 0.783±0.0450.783_± 0.045 0.647±0.0920.647_± 0.092 0.733±0.1780.733_± 0.178 0.734±0.1420.734_± 0.142 US-LIME 0.525±0.0770.525_± 0.077 0.400±0.1500.400_± 0.150 0.419±0.1060.419_± 0.106 0.587±0.1180.587_± 0.118 0.749±0.1510.749_± 0.151 0.760±0.1480.760_± 0.148 UnRAvEL 0.501±0.0550.501_± 0.055 0.332±0.1210.332_± 0.121 0.276±0.0840.276_± 0.084 0.427±0.0510.427_± 0.051 0.148±0.0350.148_± 0.035 0.099±0.0340.099_± 0.034 DLIME 0.409±0.0330.409_± 0.033 0.121±0.0620.121_± 0.062 0.155±0.0240.155_± 0.024 0.352±0.0260.352_± 0.026 – – BayesLIME 0.770±0.0970.770_± 0.097 0.631±0.0740.631_± 0.074 0.674±0.1100.674_± 0.110 0.617±0.0960.617_± 0.096 0.765±0.1300.765± 0.130 0.755±0.0150.755± 0.015 BayLIME 0.779±0.1050.779_± 0.105 0.678±0.1040.678_± 0.104 0.663±0.0450.663_± 0.045 0.648±0.0930.648_± 0.093 0.720±0.1550.720_± 0.155 0.739±0.1870.739_± 0.187 EAGLE(Ours) 0.802±0.118¯ 0.802_± 0.118 0.775±0.1320.775_± 0.132 0.822±0.1510.822_± 0.151 0.785±0.0820.785_± 0.082 0.861±0.1030.861_± 0.103 0.825±0.1070.825_± 0.107 Figure 2: Active sampling convergence behaviour: EAGLE consistently improves both D-efficiency and cumulative information gain, leading to higher AUCC across datasets. Evaluation of Sampling Quality: We assess how efficiently each perturbation strategy extracts information from the black-box model, comparing EAGLE’s acquisition functions against existing Bayesian post-hoc explanation methods using two complementary metrics. D-efficiency defined as (|V0||Vt|)1/d ( |V_0||V_t| )^1/d, measures the reduction in volume of the posterior covariance ellipsoid relative to the prior [atkinson2007]. This aligns with theory (Lemma 1), as it measures the amount of information gain as query samples are accrued. Higher D-efficiency indicates that the selected perturbations shrink uncertainty more uniformly across all surrogate coefficient directions. This metric is invariant under reparametrization, making it a robust choice for comparing acquisition strategies. While D-efficiency captures the geometric reduction in posterior uncertainty, it does not reflect the absolute amount of information gained. We complement this metric with cumulative information gain (CIG) which quantifies the total differential entropy reduction over the perturbation budget [chaloner1995]. In the leftmost plot in Fig. 2, we observe that D-efficiency increases linearly (for Adult dataset), justifying the logarithmic behavior (across t), as predicted by Lemma 1. EAGLE exhibits a steeper convergence trajectory from the earliest acquisition steps, attaining a D-efficiency approximately 1.5×1.5× that of BayesLIME and BayLIME at n=500n=500. This faster growth reflects that perturbations selected by EAGLE reduce the posterior covariance more efficiently per query alongside per-step entropy as confirmed by the CIG curve (plots for all datasets are provided in the supplementary material). 6.2 Ablation Study In this section, we investigate the sensitivity of EAGLE to key design choices. We first evaluate sample efficiency by measuring the query budget at which EAGLE matches the performance of BayesLIME (Section 3), using it as a baseline since both methods share the same BLR surrogate, isolating the effect of the acquisition strategy. We then ablate on prior precision, candidate pool size, and superpixel granularity. We use D-efficiency the Comprehensive Consistency Metric (CCM) [BELIEF2025], defined as CCM=(1−ASFE)×ARS,CCM=(1-ASFE)×ARS, which combines sign-flip entropy, given as ASFE (Average Sign Flip Entropy) and rank similarity given as ARS (Average Rank Similarity) across independent runs. A CCM close to 1 indicates stable explanations under a given configuration. Sample Efficiency: We quantify the sample efficiency of EAGLE by measuring the crossover budget, the number of queries at which EAGLE first matches the D-efficiency and CCM that Focused Sampling attains at its full budget of N=500N=500. Table 2 reports the sample efficiency of the proposed approach relative to BayesLIME across five datasets under two complementary metrics. For D-efficiency, EAGLE matches or exceeds FS@500 on every test instance across all datasets, requiring only 310-390 queries to achieve equivalent design quality, yielding savings of 22% to 38%. For CCM, crossover occurs in the large majority of instances, with savings ranging from 52% to 88%, this confirms how aggressively our method concentrates the posterior, in much lower run times. D-efficiency ↑ CCM ↑ Runtime(s)↓ Dataset BayesLIME@500 EAGLE@ Saving BayesLIME@500 EAGLE@ Saving BayesLIME EAGLE 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 ImageNet 2.448 390 22% 0.816 200 60% 34.73 7.08 Table 2: Query savings achieved by EAGLE over BayesLIME across tabular and image datasets. BayesLIME@500 reports the value attained by BayesLIME at n=500n=500 queries; EAGLE@ gives the budget at which EAGLE reaches the same quality. The final columns report wall-clock runtime per explanation at n=500n=500 queries. Hyperparameter Sensitivity: We ablate three key hyperparameters of EAGLE: (1) the prior precision λ, (2) the candidate pool size P, and (3) the number of superpixel segments d. The prior precision controls regularization strength in the Bayesian linear surrogate, directly influencing the posterior covariance VϕV_φ from which acquisition scores are derived. For tabular datasets, we vary λ/d∈0.01,0.1,1,10,100λ/d∈\0.01,0.1,1,10,100\ and pool size ∈100,250,500,1000,2000P∈\100,250,500,1000,2000\, holding all other parameters at their default values. For image datasets, the number of superpixel segments determines the resolution at which EAGLE explains the black-box prediction; fewer segments yield coarse, region-level attributions, while more segments produce finer explanations at the cost of a high dimensional surrogate. We vary the number of SLIC segments over 10,15,20,30,40,45\10,15,20,30,40,45\ with a fixed perturbation budget of N=500N=500. Figure 3(a) shows that D-efficiency increases monotonically with λ across all tabular datasets, as stronger prior regularization concentrates the posterior. CCM improves up to λ/d≈10λ/d≈ 10, where regularization stabilizes feature rankings, then declines at λ/d=100λ/d=100 for COMPAS, Adult Income and Magic as over-regularization collapses coefficient magnitudes, reducing meaningful differentiation between features. The default setting λ=dλ=d provides a favorable trade-off between posterior concentration and explanation consistency. In Figure 3(b), both D-efficiency and CCM remain stable across all candidate pool sizes; this robustness shows that EAGLE does not require large candidate pools to achieve good performance, reducing computational overhead. Figure 3(c) shows that D-efficiency decreases with superpixel count on both image datasets, consistent with the (dlogt)O(d t) scaling established in Lemma 1. CCM for ImageNet stabilizes at higher superpixel counts (d>20d>20) as the underlying images are visually complex, giving the surrogate enough structure to learn consistent attributions. In contrast, MNIST CCM degrades beyond d=20d=20 since the small 28×2828× 28 images lack sufficient structure for fine-grained superpixels, leading to noisy attributions. Figure 3: Hyperparameter sensitivity of EAGLE, reporting D-efficiency (solid) and CCM (dashed). (a) Prior precision λ/dλ/d: the default λ=dλ=d balances posterior concentration and explanation consistency. (b) Pool size |||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. Runtime comparison: In Table 3, we compare the runtime of different explanation methods as the sampling budget increases. LIME-based methods are the fastest due to their simple perturbation and linear surrogate framework. However, their explanations are often unstable and sensitive to sampling variations, making them less reliable despite the low computational cost. In contrast, EAGLE improves explanation reliability while maintaining competitive runtime. Compared to BayesLIME, EAGLE consistently achieves lower runtime across all budgets. For example, at N=500N=500, EAGLE requires 8.168.16 seconds on average, while BayesLIME takes 14.5614.56 seconds. These results show that the proposed sampling strategy improves efficiency while producing more reliable explanations with only a modest increase in computational cost. Experiments run on AMD Ryzen Threadripper 3960X (24-core, 48-thread) CPU. Each cell reports mean± over 5 instances × 5 repeats. Method Category Runtime(s) on COMPAS N=50N=50 N=100N=100 N=200N=200 N=500N=500 LIME LIME-based 0.028±0.0010.028± 0.001 0.038±0.0010.038± 0.001 0.056±0.0030.056± 0.003 0.113±0.0030.113± 0.003 BayLIME LIME-based 0.029±0.0020.029± 0.002 0.039±0.0010.039± 0.001 0.058±0.0030.058± 0.003 0.139±0.0220.139± 0.022 GLIME LIME-based 0.032±0.0010.032± 0.001 0.045±0.0040.045± 0.004 0.079±0.0040.079± 0.004 0.160±0.0120.160± 0.012 DLIME LIME-based 0.020±0.0030.020± 0.003 0.023±0.0030.023± 0.003 0.029±0.0040.029± 0.004 0.044±0.0040.044± 0.004 Tilia LIME-based 0.041±0.0010.041± 0.001 0.061±0.0040.061± 0.004 0.095±0.0100.095± 0.010 0.241±0.0170.241± 0.017 US-LIME LIME-based 0.234±0.0250.234± 0.025 0.389±0.0310.389± 0.031 0.714±0.0550.714± 0.055 1.653±0.1061.653± 0.106 BayesLIME Bayesian Active 1.047±0.1491.047± 0.149 2.520±0.2182.520± 0.218 5.189±0.4155.189± 0.415 14.562±0.83814.562± 0.838 EAGLE (ours) Bayesian Active 0.651±0.0590.651± 0.059 1.386±0.0691.386± 0.069 3.195±0.0953.195± 0.095 8.160±0.1888.160± 0.188 UnRAvEL BO+GP 68.420±23.94168.420± 23.941 73.026±28.84473.026± 28.844 85.330±38.90485.330± 38.904 102.286±10.256102.286± 10.256 Table 3: Wall-clock runtime (seconds, mean ± std) per explanation on the COMPAS dataset across sample budgets N∈50,100,200,500N∈\50,100,200,500\. 7 Conclusions We introduce EAGLE, an active learning framework that selects informative perturbations using information-theoretic acquisition functions and estimates confidence in feature attributions through Bayesian surrogate modeling. We provide theoretical bounds on the information gain and establish high-probability guarantees on the estimation error of explanation weights, leading to sample complexity bounds. Empirically, EAGLE consistently improves explanation stability and sampling efficiency across datasets, achieving stronger Jaccard similarity and faster information gain convergence compared to existing perturbation-based baselines. These results mark an important milestone in developing mathematically grounded active learning methods for reliable post-hoc explainability of black-box models. References Supplementary Material 1 Additional Theoretical Results Lemma 1 and Proof: Consider a Bayesian linear surrogate model given in (2) where the posterior covariance is given by (3). Let the EAGLE-based acquisition function be defined as the marginal expected reduction in entropy of the surrogate parameters ϕ φ obtained by querying a candidate perturbation z, E()=y∣,[H(p(ϕ∣))−H(p(ϕ∣∪()))].A_E(z)=E_y ,Z [H (p( φ ) )-H (p( φ ∪\(z)\) ) ]. Then, under single-step greedy acquisition, maximizing E()A_E(z) over a candidate pool is equivalent, up to additive and multiplicative constants independent of z, to maximizing the predictive variance, argmaxE()=argmaxπ0()⊤ϕ. _zA_E(z)= _z\; _x_0(z)\ z V_ φz. Proof Augmenting the current perturbation set Z with a single candidate perturbation z, yielding the augmented set +=∪Z^+=Z∪\z\. Substituting the definition of the acquisition function yields EIG() _EIG(z) =y∣,[H(p(ϕ∣,))−H(p(ϕ∣+,+))], =E_y ,Z [H (p( φ ,y) )-H (p( φ ^+,y^+) ) ], (12) Under the linear–Gaussian surrogate model, the posterior covariance update depends only on the queried perturbation z and not on the predictions y, which allows the expectation over y to be restated as: y∣,[H(p(ϕ∣+,+))]=H(p(ϕ∣+)).E_y ,Z [H (p( φ ^+,y^+) ) ]=H (p( φ ^+) ). Using the result in Thm. 1.1, the information gain for a single perturbation simplifies to E()=12log|ϕ|−12log|ϕ+()|, _E(z)= 12 _ φ - 12 _ φ^+(z) , (13) expressing the acquisition function as the reduction in log-volume of the posterior covariance. In the weighted surrogate formulation, each perturbation z is associated with a locality weight π0() _x_0(z). Consequently, the posterior precision update after querying a new perturbation is given by the weighted update ϕ−1+π0()⊤.V_ φ^-1+ _x_0(z)\,zz . (14) Accordingly, the posterior covariance after querying z is ϕ+()=(ϕ−1+π0()⊤)−1.V_ φ^+(z)= (V_ φ^-1+ _x_0(z)\,zz )^-1. (15) Using the identity |−1|=||−1 ^-1 = ^-1, we obtain |ϕ+()|=|ϕ−1+π0()⊤|−1. _ φ^+(z) = _ φ^-1+ _x_0(z)\,zz ^-1. (16) The matrix determinant lemma states that for an invertible matrix A and vectors ,u,v, |+⊤|=||(1+⊤−1). +uv = (1+v A^-1u ). Using the above identity in (16) yields |ϕ−1+π0()⊤|=|ϕ−1|(1+π0()⊤ϕ). _ φ^-1+ _x_0(z)\,zz = _ φ^-1 (1+ _x_0(z)\,z V_ φz ). (17) Substituting (17) into (16) we obtain |ϕ+()|=|ϕ|1+π0()⊤ϕ. _ φ^+(z) = _ φ 1+ _x_0(z)\,z V_ φz. (18) Substituting (18) into the expression for acquisition function leads to the weighted expected information gain acquisition function given as E()=12log(1+π0()⊤ϕ).A_E(z)= 12 (1+ _x_0(z)\,z V_ φz ). (19) Since the logarithm is a strictly monotonically increasing function, the ordering of candidate perturbations induced by the EIG acquisition function is preserved by its argument. Using (19), the EIG acquisition function is therefore equivalently written as E()=argmaxπ0()⊤ϕ.A_E(z)= _z\; _x_0(z)\,z V_ φz. (20) □ Theorem 2 and proof Consider a Bayesian linear regression surrogate in (2), the set of perturbations Z with corresponding predictions, y^() y(z), ϕ,0=∈ℝd×dV_ φ,0=I ^d× d and posterior covariance after t queries given by (9). Assuming ‖t‖2≤1\|z_t\|_2≤ 1 and 0≤π0(t)≤10≤ _x_0(z_t)≤ 1 for all t≥1t≥ 1, expected information gain based acquisition as obtained in (7) leads to ∑s=1tπ0(s)s⊤ϕ,s−1s≤ 2dlog(1+td). _s=1^t _x_0(z_s)\,z_s V_ φ,s-1z_s\;≤\;2d \! (1+ td ). Proof From (7), in the t-th step the perturbations are selected greedily by maximizing weighted expected information gain as t=argmaxπ0()⊤ϕ,t−1.z_t= _z\; _x_0(z)\,z V_ φ,t-1z. Using the identity ϕ,t−1=(ϕ,t−1−1+π0(t)tt⊤)V^-1_ φ,t= (V^-1_ φ,t-1+ _x_0(z_t)\,z_tz_t ), and using the matrix determinant lemma, we obtain the following: |ϕ,t|=|ϕ,t−1|1+π0(t)t⊤ϕ,t−1t, |V_ φ,t|= |V_ φ,t-1|1+ _x_0(z_t)z_t V_ φ,t-1z_t, (21) where |⋅||·| represents the determinant operator. Taking logarithm on both sides and rearranging log|ϕ,t−1|−log|ϕ,t|=log(1+π0(t)t⊤ϕ,t−1t). |V_ φ,t-1|- |V_ φ,t|= (1+ _x_0(z_t)z_t V_ φ,t-1z_t ). Telescoping from s=1s=1 to t, log|ϕ,0|−log|ϕ,t|=∑s=1tlog(1+π0(s)s⊤ϕ,s−1s). |V_ φ,0|- |V_ φ,t|= _s=1^t (1+ _x_0(z_s)z_s V_ φ,s-1z_s ). Using the inequality log(1+x)≥x1+x (1+x)≥ x1+x for x≥0x≥ 0, and the fact that s⊤ϕ,s−1s≤1z_s V_ φ,s-1z_s≤ 1 since ‖s‖2≤1\|z_s\|_2≤ 1 and ϕ,s−1⪯V_ φ,s-1 , we obtain log|ϕ,0|−log|ϕ,t|≥12∑s=1tπ0(s)s⊤ϕ,s−1s. |V_ φ,0|- |V_ φ,t|\;≥\; 12 _s=1^t _x_0(z_s)z_s V_ φ,s-1z_s. (22) Since ϕ,0=V_ φ,0=I, |ϕ,0|=1|V_ φ,0|=1 and hence log|ϕ,0|=0 |V_ φ,0|=0. This leads to log|ϕ,0|−log|ϕ,t|=log|ϕ,t−1| |V_ φ,0|- |V_ φ,t|= |V_ φ,t^-1|. Let λ1,…,λd _1,…, _d be the eigenvalues of ϕ,t−1V_ φ,t^-1. Using |ϕ,t−1|=∏i=1dλi|V_ φ,t^-1|= _i=1^d _i and the AM-GM inequality, we have that |ϕ,t−1|=∏i=1dλi≤(1d∑i=1dλi)d=(Tr(ϕ,t−1)d)d. |V_ φ,t^-1|= _i=1^d _i≤ ( 1d _i=1^d _i )^d= ( Tr(V_ φ,t^-1)d )^d. (23) Taking logarithms, log|ϕ,t−1|≤dlog(Tr(ϕ,t−1)d). |V_ φ,t^-1|≤ d ( Tr(V_ φ,t^-1)d ). (24) We now bound the trace of the posterior precision matrix in order to arrive at the final result. Since ϕ,t−1=+∑s=1tπ0(s)ss⊤V_ φ,t^-1=I+ _s=1^t _x_0(z_s)z_sz_s , taking traces gives Tr(ϕ,t−1)=d+∑s=1tπ0(s)‖s‖22. (V_ φ,t^-1)=d+ _s=1^t _x_0(z_s)\|z_s\|_2^2. (25) Since ‖s‖2≤1\|z_s\|_2≤ 1 and π0(s)≤1 _x_0(z_s)≤ 1, we have Tr(ϕ,t−1)≤d+tTr(V_ φ,t^-1)≤ d+t. Substituting into (24), we obtain −log|ϕ,t|=log|ϕ,t−1|≤dlog(d+td)=dlog(1+td). - |V_ φ,t|= |V_ φ,t^-1|≤ d ( d+td )=d (1+ td ). (26) Substituting the above in (22), we obtain 12∑s=1tπ0(s)s⊤ϕ,s−1s≤log|ϕ,0|−log|ϕ,t|≤dlog(1+td), 12 _s=1^t _x_0(z_s)\,z_s V_ φ,s-1z_s≤ |V_ φ,0|- |V_ φ,t|≤ d (1+ td ), (27) and hence, ∑s=1tπ0(s)s⊤ϕ,s−1s≤ 2dlog(1+td) _s=1^t _x_0(z_s)\,z_s V_ φ,s-1z_s\;≤\;2d (1+ td ). As t→∞t→∞ implies log(1+td)=O(logt) \! (1+ td )=O( t), we conclude ∑s=1tπ0(s)s⊤s−1s=O(dlogt). _s=1^t _x_0(z_s)\,z_s V_s-1z_s=O(d t). □ Theorem 1 and Proof Consider the source linear model in (8), ϕ⋆∈ℝd φ ^d denote the true (unknown) importance vector and let t=∑s=1tπ0(s)ss⊤,ϕ,t=(+t)−1,S_t= _s=1^t _x_0(z_s)z_sz_s , _ φ,t=(I+S_t)^-1, and the posterior mean after t samples is given as ϕ^t=ϕ,t∑s=1tsys φ_t=V_ φ,t _s=1^tz_sy_s. Then for any δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, ‖ϕ^t−ϕ⋆‖ϕ,t−1≤σd+2dlog1δ+2log1δ+‖ϕ⋆‖Vϕ,t−1.\| φ_t- φ \|_V_ φ,t^-1≤σ d+2 d 1δ+2 1δ+\| φ \|_V_ φ,t^-1. (28) Proof Given tS_t, the posterior mean after t samples is given as ϕ^t=ϕ,t∑s=1tsys φ_t=V_ φ,t _s=1^tz_sy_s. First, we define the noise-weighted design vector t=∑s=1tπ0(s)εss ξ_t= _s=1^t _x_0(z_s) _sz_s. Since the εs _s are independent Gaussian variables, we have that t∼(,σ2t). ξ_t (0,σ^2S_t ). From the definition of the estimator, we have ϕ^t=ϕ,t(tϕ⋆+t). φ_t=V_ φ,t (S_t φ + ξ_t ). Since ϕ,tt=−ϕ,tV_ φ,tS_t=I-V_ φ,t, we obtain ϕ^t−ϕ⋆=ϕ,tt−ϕ,tϕ⋆. φ_t- φ =V_ φ,t ξ_t-V_ φ,t φ . We define ϕ,t−1V_ φ,t^-1-norm for any vector x as ‖x‖ϕ,t−1=x⊤ϕ,t−1x\|x\|_V_ φ,t^-1= x V_ φ,t^-1x. Since ϕ,t≻0V_ φ,t 0, this defines a valid norm. We apply the triangle inequality; since ∥⋅∥ϕ,t−1\|·\|_V_ φ,t^-1 is a norm, the triangle inequality applied on the expression above leads to ‖ϕ^t−ϕ⋆‖ϕ,t−1=‖ϕ,tt−ϕ,tϕ⋆‖ϕ,t−1≤‖ϕ,tt‖ϕ,t−1+‖ϕ,tϕ⋆‖ϕ,t−1.\| φ_t- φ \|_V_ φ,t^-1=\|V_ φ,t ξ_t-V_ φ,t φ \|_V_ φ,t^-1≤\|V_ φ,t ξ_t\|_V_ φ,t^-1+\|V_ φ,t φ \|_V_ φ,t^-1. Since, for any vector x, ‖ϕ,t‖ϕ,t−1=‖ϕ,t\|V_ φ,tx\|_V_ φ,t^-1=\|x\|_V_ φ,t, we simplify the above as ‖ϕ^t−ϕ⋆‖ϕ,t−1≤‖ϕ,tt‖ϕ,t−1+‖ϕ⋆‖ϕ,t. \| φ_t- φ \|_V_ φ,t^-1≤\|V_ φ,t ξ_t\|_V_ φ,t^-1+\| φ \|_V_ φ,t. (29) Using ϕ,t=(+t)−1⪯t−1V_ φ,t=(I+S_t)^-1 _t^-1, we have ‖ϕ,tt‖ϕ,t−12=t⊤ϕ,tt≤t⊤t−1t. \|V_ φ,t ξ_t\|_V_ φ,t^-1^2= ξ_t V_ φ,t ξ_t≤ ξ_t S_t^-1 ξ_t. (30) Let t=t−1/2tu_t=S_t^-1/2 ξ_t. Then t∼(0,σ2d)u_t (0,σ^2I_d), and t⊤t−1t=t⊤t ξ_t S_t^-1 ξ_t=u_t u_t. Evidently, 1σ2t⊤t∼χd2 1σ^2u_t u_t χ^2_d, where χd2χ^2_d refers to Chi-square distribution with d degrees of freedom. Applying the Laurent-Massart inequality (Lemma 1 in [laurentmassart]) we have with probability at least 1−δ1-δ, t⊤t≤σ2(d+2dlog1δ+2log1δ).u_t u_t≤σ^2 (d+2 d 1δ+2 1δ ). Substituting the above in (29), we obtain the final result. □ Corollary 1 and Proof Under the assumptions of Theorem 1, suppose that λmin(t)≥κtfor some κ>0 _ (S_t)≥κ t some κ>0. Then for any ε>0 >0 and δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, ‖ϕ^t−ϕ⋆‖2≤ν\| φ_t- φ \|_2≤ν whenever t≥1κ((βδ+‖ϕ⋆‖2)2ν2−1),t≥ 1κ ( ( _δ+\| φ \|_2)^2ν^2-1 ), where βδ=σd+2dlog1δ+2log1δ _δ=σ d+2 d 1δ+2 1δ. Proof From Theorem 1, with probability at least 1−δ1-δ, ‖ϕ^t−ϕ⋆‖ϕ,t−1≤βδ+‖ϕ⋆‖2.\| φ_t- φ \|_V_ φ,t^-1≤ _δ+\| φ \|_2. For the symmetric matrix ϕ,t≻V_ φ,t , we have ϕ,t⪯λmax(ϕ,t)V_ φ,t _max(V_ φ,t)I, and hence, λmax(ϕ,t)ϕ,t−1⪰ _max(V_ φ,t)V_ φ,t^-1 . Then, for any vector x, ‖22=⊤≤λmax(ϕ,t)⊤ϕ,t−1=λmax(ϕ,t)‖ϕ,t−12.\|x\|_2^2=x x≤ _ (V_ φ,t)\,x V_ φ,t^-1x= _ (V_ φ,t)\,\|x\|_V_ φ,t^-1^2. Hence, ‖ϕ^t−ϕ⋆‖2≤λmax(ϕ,t)‖ϕ^t−ϕ⋆‖ϕ,t−1\| φ_t- φ \|_2≤ _ (V_ φ,t)\,\| φ_t- φ \|_V_ φ,t^-1. Since ϕ,t=(+t)−1V_ φ,t=(I+S_t)^-1, we have λmax(ϕ,t)=1λmin(+t) _ (V_ φ,t)= 1 _ (I+S_t). Further ‖ϕ⋆‖Vϕ,t−1≤‖ϕ⋆‖2\| φ \|_V_ φ,t^-1≤\| φ \|_2 since ϕ,t−1≺V_ φ,t^-1 . Hence, ‖ϕ^t−ϕ⋆‖2≤βδ+‖ϕ⋆‖2λmin(+t). \| φ_t- φ \|_2≤ _δ+\| φ \|_2 _ (I+S_t). (31) Using λmin(t)≥κtfor some κ>0 _ (S_t)≥κ t some κ>0, we have λmin(+t)≥1+κt _ (I+S_t)≥ 1+κ t. Hence, ‖ϕ^t−ϕ⋆‖2≤βδ+‖ϕ⋆‖21+κt. \| φ_t- φ \|_2≤ _δ+\| φ \|_2 1+κ t. (32) For ‖ϕ^t−ϕ⋆‖2≤ν\| φ_t- φ \|_2≤ν to hold, a sufficient condition is βδ+‖ϕ⋆‖21+κt≤ε. _δ+\| φ \|_2 1+κ t≤ . Solving for t, we obtain t≥1κ((βδ+‖ϕ⋆‖2)2ε2−1).t≥ 1κ ( ( _δ+\| φ \|_2)^2 ^2-1 ). 1.1 Proof of Theorem 3 Lemma 2(Prior distribution of ϕ φ) Let ϕ∣σ2∼(,σ2d) φ σ^2 (0,\,σ^2I_d) and σ2∼Scaled-Inv-χ2(n0,σ02)σ^2 -Inv-χ^2(n_0,\, _0^2). Then the marginal prior obtained by integrating out σ2σ^2 is a multivariate Student-t: p(ϕ)=∫p(ϕ∣σ2)p(σ2)σ2=Tn0(,σ02d). p( φ)\;=\; p( φ σ^2)\,p(σ^2)\,dσ^2\;=\;T_n_0\! (0,\; _0^2\,I_d ). Proof The conditional distribution is p(ϕ∣σ2) p( φ σ^2) =(2π)−d/2(σ2)−d/2exp(−12σ2ϕ⊤ϕ), =(2π)^-d/2\,(σ^2)^-d/2\, \! (- 12σ^2\, φ φ ), (33) and the prior on the noise variance is p(σ2) p(σ^2) =(n0σ02/2)n0/2Γ(n0/2)(σ2)−(1+n0/2)exp(−n0σ022σ2). = (n_0 _0^2/2)^n_0/2 (n_0/2)\;(σ^2)^-(1+n_0/2)\; \! (- n_0 _0^22σ^2 ). (34) Multiplying (33) and (34) and collecting terms in σ2σ^2: p(ϕ∣σ2)p(σ2) p( φ σ^2)\,p(σ^2) =C(σ2)−(1+(n0+d)/2)exp(−A2σ2), =C\;(σ^2)^-(1+(n_0+d)/2)\; \! (- A2σ^2 ), where A=ϕ⊤ϕ+n0σ02A= φ φ+n_0 _0^2 and C collects all factors independent of σ2σ^2. To integrate out σ2σ^2, substitute u=A/(2σ2)u=A/(2σ^2), so that dσ2=−Au−2/2dudσ^2=-A\,u^-2/2\;du. Then p(ϕ) p( φ) =∫0∞C(A2u)−(1+(n0+d)/2)e−uA2u−2u∝A−(n0+d)/2. = _0^∞C\; ( A2u )^-(1+(n_0+d)/2)e^-u\; A2\,u^-2\;du\; \;A^-(n_0+d)/2. The integral over u is a Gamma integral and evaluates to a constant. Substituting back A=ϕ⊤ϕ+n0σ02A= φ φ+n_0 _0^2: p(ϕ) p( φ) ∝(ϕ⊤ϕ+n0σ02)−(n0+d)/2=(1+ϕ⊤ϕn0σ02)−(n0+d)/2⋅(n0σ02)−(n0+d)/2. \; \; ( φ φ+n_0 _0^2 )^-(n_0+d)/2\;=\; (1+ φ φn_0 _0^2 )^-(n_0+d)/2·(n_0 _0^2)^-(n_0+d)/2. (35) Recognising (35) as the kernel of a d-dimensional Student-t with n0n_0 degrees of freedom, location 0, and scale matrix σ02d _0^2\,I_d, we conclude p(ϕ)=Tn0(,σ02d)p( φ)=T_n_0(0,\; _0^2\,I_d). Lemma 3(Posterior distribution of ϕ φ) Given the Bayesian linear surrogate in (2) with perturbations Z and black-box responses =[y1,…,yN]⊤y=[y_1,…,y_N] , the posterior obtained by marginalizing σ2σ^2 is a multivariate Student-t: p(ϕ∣,) p( φ ,y) =∫p(ϕ∣σ2,,)p(σ2∣,)σ2=Tn0+N(ϕ^,ν1n0+Nϕ), = p( φ σ^2,Z,y)\;p(σ^2 ,y)\;dσ^2\;=\;T_n_0+N\! ( φ,\; _1n_0+N\,V_ φ ), (36) where ν1=n0σ02+s2 _1=n_0 _0^2+s^2, and ϕ φ, ϕV_ φ, s2s^2 are defined in (3). The conditional distributions are ϕ∣σ2,, φ σ^2,Z,y ∼(ϕ^,σ2ϕ), \! ( φ,\;σ^2\,V_ φ ), (37) σ2∣, σ^2 ,y ∼Scaled-Inv-χ2(n0+N,ν1n0+N). -Inv-χ^2\! (n_0+N,\; _1n_0+N ). (38) Proof The conditional posterior (37) gives p(ϕ∣σ2,,) p( φ σ^2,Z,y) =(2π)−d/2det(σ2ϕ)−1/2exp(−12σ2(ϕ−ϕ^)⊤ϕ−1(ϕ−ϕ^)), =(2π)^-d/2\, (σ^2V_ φ)^-1/2\; \! (- 12σ^2\,( φ- φ) V_ φ^-1( φ- φ) ), (39) and the marginal posterior on σ2σ^2 (38) gives p(σ2∣,) p(σ^2 ,y) =(ν1/2)(n0+N)/2Γ((n0+N)/2)(σ2)−(1+(n0+N)/2)exp(−ν12σ2). = ( _1/2)^(n_0+N)/2 \! ((n_0+N)/2 )\;(σ^2)^-(1+(n_0+N)/2)\; \! (- _12σ^2 ). (40) Multiplying (39) and (40) and collecting powers of σ2σ^2: p(ϕ∣σ2,,)p(σ2∣,) p( φ σ^2,Z,y)\;p(σ^2 ,y) =C1(σ2)−(1+(n0+N+d)/2)exp(−A12σ2), =C_1\;(σ^2)^-(1+(n_0+N+d)/2)\; \! (- A_12σ^2 ), (41) where A1=(ϕ−ϕ^)⊤ϕ−1(ϕ−ϕ^)+ν1A_1=( φ- φ) V_ φ^-1( φ- φ)+ _1 and C1C_1 absorbs all factors independent of σ2σ^2. Substituting u=A1/(2σ2)u=A_1/(2σ^2) and integrating out σ2σ^2 (identical change-of-variables as in Lemma 2): p(ϕ∣,) p( φ ,y) =∫0∞C1(A12u)−(1+(n0+N+d)/2)e−uA12u−2u∝A1−(n0+N+d)/2. = _0^∞C_1\; ( A_12u )^-(1+(n_0+N+d)/2)e^-u\; A_12\,u^-2\;du\; \;A_1^-(n_0+N+d)/2. (42) Substituting back: p(ϕ∣,) p( φ ,y) ∝(1+1ν1(ϕ−ϕ^)⊤ϕ−1(ϕ−ϕ^))−(n0+N+d)/2. \; \; (1+ 1 _1\,( φ- φ) V_ φ^-1( φ- φ) )^-(n_0+N+d)/2. (43) Expression (43) is the kernel of a d-dimensional Student-t with n0+Nn_0+N degrees of freedom, location ϕ φ, and scale matrix ν1n0+Nϕ _1n_0+N\,V_ φ. Hence p(ϕ∣,)=Tn0+N(ϕ^,ν1n0+Nϕ)p( φ ,y)=T_n_0+N\! ( φ,\; _1n_0+N\,V_ φ ). Theorem 1.1 Given a Bayesian linear regression surrogate and a set of perturbations =[z1,…,zN]Z=[z_1,…,z_N] with corresponding predictions y, the expected information gain over the surrogate importance parameters ϕ φ is given by (;fe)=12log|ϕ|+log1−log2, (Z;f_e)= 12 _ φ + _1- _2, (44) where ϕV_ φ and the weight matrix ϕ φ are defined as in Section 3, r1=12(n0+N)r_1= 12(n_0+N), and ν1=n0σ02+s2 _1=n_0 _0^2+s^2. The constants 1C_1 and 2C_2 are given by 1 _1 =(πν1)r1/2Γ(r1/2)B(r12,ν12)+ν1+r12[ψ(ν1+r12)−ψ(ν12)], = (π _1)^r_1/2 (r_1/2)\,B\! ( r_12, _12 )+ _1+r_12 [ψ\! ( _1+r_12 )-ψ\! ( _12 ) ], 2 _2 =(n0σ02π)n0/2Γ(n0/2)B(n02,n0σ022)+n02[ψ(n02)−ψ(n0σ022)]. = (n_0 _0^2π)^n_0/2 (n_0/2)\,B\! ( n_02, n_0 _0^22 )+ n_02 [ψ\! ( n_02 )-ψ\! ( n_0 _0^22 ) ]. Proof The expected information gain is defined as (;fe) (Z;\,f_e) =p(∣)[H[p(ϕ)]−H[p(ϕ∣,)]]. =E_p(y )\! [H[p( φ)]-H[p( φ ,y)] ]. (45) Let ∼Tν(,)x _ν( μ,\, ) be a d-dimensional Student-t with ν degrees of freedom, location μ, and scale matrix . Its differential entropy is H[] [x] =12log||+log[(νπ)d/2Γ(d/2)B(d2,ν2)+ν+d2(ψ(ν+d2)−ψ(ν2))]. = 12 + \! [ (νπ)^d/2 (d/2)\,B\! ( d2,\, ν2 )+ ν+d2\, (ψ\! ( ν+d2 )-ψ\! ( ν2 ) ) ]. (46) From Lemma 2, p(ϕ)=Tn0(,σ02d)p( φ)=T_n_0(0,\; _0^2\,I_d). Applying (46) with ν=n0ν=n_0 and =σ02d = _0^2\,I_d: H[p(ϕ)] [p( φ)] =d2logσ02+log[(n0π)d/2Γ(d/2)B(d2,n02)+n0+d2(ψ(n0+d2)−ψ(n02))]. = d2 _0^2+ \! [ (n_0π)^d/2 (d/2)\,B\! ( d2,\, n_02 )+ n_0+d2\, (ψ\! ( n_0+d2 )-ψ\! ( n_02 ) ) ]. (47) Since n0n_0 and σ02 _0^2 are fixed hyperparameters, we write H[p(ϕ)]=d2logσ02+log2H[p( φ)]= d2 _0^2+ _2. From Lemma 3, p(ϕ∣,)=Tn0+N(ϕ^,ν1n0+Nϕ)p( φ ,y)=T_n_0+N\! ( φ,\; _1n_0+N\,V_ φ ) with ν1=n0σ02+s2 _1=n_0 _0^2+s^2. Applying (46) with ν=n0+Nν=n_0+N and =ν1n0+Nϕ = _1n_0+N\,V_ φ: H[p(ϕ∣,)] [p( φ ,y)] =12log|ν1n0+Nϕ|+log[((n0+N)π)d/2Γ(d/2)B(d2,n0+N2) = 12 \! _1n_0+N\,V_ φ + \! [ ((n_0+N)π)^d/2 (d/2)\,B\! ( d2,\, n_0+N2 ) +n0+N+d2(ψ(n0+N+d2)−ψ(n0+N2))] + n_0+N+d2\, (ψ\! ( n_0+N+d2 )-ψ\! ( n_0+N2 ) ) ] =12log|ϕ|+d2log(ν1n0+N)+log1′, = 12 _ φ + d2 \! ( _1n_0+N )+ _1 , (48) where 1′C_1 denotes the bracketed expression evaluated at ν=n0+Nν=n_0+N. We absorb the scaling into log1 _1. The log|ϕ| _ φ term depends on Z but not on y, and hence, it passes through the expectation in (45). Substituting Steps 2 and 3 into (45): (;fe) (Z;\,f_e) =p(∣)[H[p(ϕ)]−H[p(ϕ∣,)]] =E_p(y )\! [H[p( φ)]-H[p( φ ,y)] ] =(d2logσ02+log2)−(12log|ϕ|+d2log(ν1n0+N)+log1) = ( d2 _0^2+ _2 )- ( 12 _ φ + d2 \! ( _1n_0+N )+ _1 ) =−12log|ϕ|+log2−log1+d2logσ02−d2log(ν1n0+N). =-\, 12 _ φ + _2- _1+ d2 _0^2- d2 \! ( _1n_0+N ). (49) The last two scalar terms depend only on fixed hyperparameters and the data-dependent quantity ν1 _1. In the main text these are absorbed into the constants 1C_1 and 2C_2, yielding the stated result. □ 2 Additional Experimental Results 2.1 Sampling Quality A-efficiency is defined as Tr(V0)/Tr(Vt)Tr(V_0)/Tr(V_t), captures the reduction in total marginal variance of the surrogate coefficients. While D-efficiency summarizes the joint posterior volume, A-optimality seeks to minimize the trace of the inverse of the information matrix, resulting in minimizing the average variance of the estimates of the regression coefficients. This makes A-efficiency particularly sensitive to individual poorly estimated features, flagging acquisition strategies that leave some coefficients under-constrained even when the overall posterior volume is small. Higher values indicate greater average precision across all coefficient estimates. EAGLE achieves consistently higher A-efficiency than both baselines across all datasets, with the gap widening over the perturbation budget. The ECDF plots in Fig. 5 confirm that at n=500n=500, nearly all test instances under EAGLE attain higher CIG than the best instances under BayesLIME or BayLIME, indicating that the improvement is uniform across instances rather than driven by a few outliers. 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 cumulative information gain (CIG) at n=500n=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=500n=500 across test instances for all tabular datasets. Curves further to the right indicate higher efficiency. EAGLE consistently dominates the baselines. Figure 8: Empirical cumulative distribution functions (ECDF) of cumulative information gain (CIG) at n=500n=500 across test instances. EAGLE achieves higher cumulative information gain across datasets, reflecting more informative perturbation selection. 2.2 Uncertainty in Explanations While Jaccard similarity measures whether explanations are consistent across runs, it treats all feature attributions equally regardless of how confident the model is in each estimate. For an explainer to be trustworthy, it must also convey which attributions are reliable and which remain uncertain. Bayesian surrogate methods uniquely provide this through posterior credible intervals. Credible interval width (90%90\%) reports the mean width of the 90%90\% credible intervals across all surrogate coefficients as shown in figures 9 and and 10. Narrow intervals indicate confident separation of important features from unimportant ones, while wide and overlapping intervals indicate that attributions are poorly estimated, making it difficult to distinguish genuinely important features from noise. Figure 9 shows per-feature attributions with 90%90\% credible intervals for randomly chosen instances from the German Credit and Adult Income datasets, where EAGLE consistently achieves the tightest intervals across all features, indicating that its acquisition strategy concentrates posterior more effectively than the baselines. Figure 10 illustrates EAGLE on a spam classification task, where each word’s color intensity encodes the magnitude of its attribution (green for positive, red for negative contribution toward SPAM) and border thickness encodes the 90%90\% credible interval width. Together, these results confirm that EAGLE’s information gain driven sampling not only improves point estimate stability (Table 1) but also yields tighter uncertainty quantification across modalities. Figure 9: Per-feature attribution estimates with 90%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 10: 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.