Pith. sign in

REVIEW 5 major objections 5 minor 2 references

Improving Stability Estimates in Adversarial Explainable AI through Alternate Search Methods

T0 review · 5 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Replacing the greedy search with a genetic algorithm finds LIME text explanations that break under fewer word replacements, suggesting previous stability estimates were optimistic.

desk verdict A plausible GA-based approach to estimating minimum perturbations for LIME stability, undermined by a single-run 20-example experiment with no variance reporting. read the letter →

arxiv 2501.09006 v1 pith:JBESZU6T submitted 2025-01-15 cs.LG

Christopher Burger , Charles Walter This is my paper · ORCID
classification cs.LG
keywords ExplainabilityInterpretabilityXAIStabilityRobustnessGeneticalgorithmLIMEAdversarialattack
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how unstable LIME's text explanations really are, measured by the fewest word replacements needed to push the explanation past a fixed similarity threshold. Prior attacks only showed that instability exists; the authors argue that the minimum number of perturbations is the quantity that should be compared across explainers. They replace the usual greedy search with a genetic algorithm, keeping the constraints that the model's prediction and the document's meaning are preserved. The paper reports that the genetic search matches or beats the greedy search in attack success and perturbed-document quality while often finding successful attacks at lower minimum perturbation counts. If correct, LIME has been shown to be less stable than earlier estimates suggested.

What carries the argument

The load-bearing object is the minimum-viable-perturbation search: minimize explanation similarity $S_{\mathrm{ime}}(e_{d_b}, e_{d_p})$ subject to $f(d_b)=f(d_p)$, semantic similarity above a threshold, a cap on the total fraction of words changed, and preservation of the top-$k$ features of the original explanation. The search mechanism is a genetic algorithm with a population of 10 chromosomes evolved over 10 generations, using mutation that replaces a word at a valid index with a nearby embedding-space alternative and crossover that swaps document tails; fitness is the objective function itself. Success is judged by nine similarity measures (rank-biased overlap, a weighted overlap favoring top ranks, at three persistence weights; Jaccard index; Kendall's tau rank distance; Spearman's footrule; and weighted variants of the non-RBO measures) at thresholds of 30%, 40%, 50%, and 60% explanation similarity. The genetic algorithm's wider exploration of the replacement space is what lets the paper estimate lower bounds on perturbations rather than merely demonstrating that some perturbation exists.

What would settle it

Run the same genetic-algorithm search on the same 20 examples many times with different random seeds and compare the distribution of minimum perturbations to the greedy search's minima; if the genetic minima frequently equal or exceed the greedy minima, or if single-run minima swing widely between seeds, the claim that this search improves LIME stability estimates is not supported.

Watch

Extended reading notes

Core claim

The paper's central claim is that a genetic-algorithm search can locate minimum viable perturbations—the fewest word replacements that drive explanation similarity below a chosen threshold $\tau$—more effectively than the greedy search used in prior work. On the Gender Bias and Symptoms-to-Diagnosis datasets, the genetic algorithm produced successful attacks where the greedy search found none (for example, the weighted Spearman measure at the 30% threshold on Gender Bias rose from 0% to 24% success, and weighted Jaccard moved from 0% to 6% at 50% and 29% at 60%), and it lowered the minimum perturbation count for several similarity measures while keeping average perturbation rates and ending similarities close to the greedy baseline. The paper therefore claims that stability estimates for LIME based on greedy search are incomplete: the true minimum perturbation needed to reach a given instability threshold is often smaller than previously reported, and that gap matters for judging which explanation methods are trustworthy.

Load-bearing premise

The load-bearing premise is that the minimum perturbation counts reported are reliable estimates of LIME's instability, even though they come from one run of a small genetic algorithm (population size 10, 10 generations) on only 20 examples per dataset, with no variance or significance testing.

Editorial extensions

If this is right

  • Stability of explanation methods should be reported as a minimum-perturbation curve across similarity thresholds, not as a binary found/not-found result.
  • Previous greedy-search-based estimates of LIME's stability are upper bounds on the true minimum, and the true values can be smaller.
  • The same threshold-and-minimum framework transfers to any explainer that returns a ranked feature list, giving a common yardstick for comparing stability across XAI methods.
  • Because a deliberately small genetic algorithm already lowers the minima, further increases in search effort or better mutation strategies are likely to find even smaller perturbation counts.
  • Perturbation quality matters jointly with count: the genetic search sometimes preserves meaning better at the same perturbation rate, though the greedy search also wins on some examples.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If these minima reproduce across repeated runs, LIME's practical stability is lower than the literature suggests, and any deployment relying on LIME explanations should treat a single-word adversarial edit as a realistic threat.
  • The same setup could become a comparative benchmark that pits LIME against other ranked-list explainers, using minimum perturbation counts at matched thresholds as the ranking criterion.
  • Because the GA was limited to 10 chromosomes, 10 generations, and 20 examples per dataset, the reported improvements are point estimates; a random-seed variance study would show whether the method's advantage is robust or partly sampling noise.
  • The emphasis on inconspicuous replacements suggests a natural extension: optimize perturbed-document quality as a second objective alongside perturbation count, rather than only checking semantic similarity after the attack.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper proposes replacing the greedy word-replacement search used in earlier adversarial attacks on LIME's text explanations with a genetic algorithm, with the goal of finding the smallest number of perturbations needed to cross a fixed explanation-similarity threshold. The formal setup includes constraints for preserving the target model's prediction, semantic similarity of the document, a perturbation cap, and protection of top-k explanation features. The authors compare the genetic algorithm against their prior greedy search on 20 examples from each of two datasets, reporting success rates, mean similarities, perturbation rates, and minimum perturbation counts across nine similarity measures. The central claim, stated in Section 7, is that the genetic algorithm reduces the number of perturbations while matching or exceeding the greedy search in attack success and perturbed document quality.

Significance. If the empirical claims were reliable, the paper would contribute a useful methodological step: moving adversarial XAI research from demonstrating the existence of LIME instability toward quantifying the minimal perturbation needed to expose a given level of instability. The idea of using threshold-based similarity as a stopping criterion is reasonable, and the comparison of search strategies is a natural way to improve lower-bound estimates. However, the current evidence is too thin for the stated conclusions: the experiments are a single run of a small stochastic genetic algorithm on 20 examples per dataset, with no repeated seeds, no error bars, and no statistical tests. The target model, LIME settings, and replacement embedding are not reported, and several tables contain malformed or inconsistent entries. The paper's value therefore depends on a substantial empirical revision rather than on the current results.

major comments (5)
  1. [§5, Tables 2–5] The central comparison rests on a single run of a stochastic genetic algorithm (population size 10, 10 generations) over 20 examples per dataset, with no random seeds, repeated trials, confidence intervals, or statistical tests. Since the GA is stochastic and LIME itself uses randomized sampling, a point difference such as the GB Spearman w success rate at τ=30% (0 for GS, 0.24 for GA) or the S2D Spearman w minimum perturbation count (7 vs 3) could be sampling noise. This is load-bearing because Section 7's conclusion is stated directly from these point estimates.
  2. [§3.3, §5] The experimental protocol is not reproducible. The target classifier f is never identified; LIME's sampling parameters (number of perturbed samples, feature set size, kernel width, surrogate hyperparameters) are not reported; and the embedding space and candidate replacement set used by both searches are not specified. These choices determine which perturbations are possible and which explanations are generated, so the comparisons in Tables 2–5 cannot be independently verified or meaningfully interpreted.
  3. [§3.1, Eq. (7)] The formal objective is internally inconsistent. Equation (5) treats a successful attack as reaching similarity at or below the threshold τ, but Equation (7) states Sime(edb, edp) > γ, and the relationship between γ and τ is never defined. Moreover, Equation (7) is a feasibility constraint set, not an optimization of the number of perturbations, even though Section 3.3 frames the goal as finding minimal perturbations and Table 5 is labeled 'Minimum Perturbation(s)'. Since the GA fitness function is said to be Objective Function (7), it is unclear how the algorithm prefers shorter perturbation sets over merely feasible ones. Equation (7) also contains the typo i ≤ ε|f| instead of i ≤ ε|db|.
  4. [Tables 2–5] Several table entries are malformed or internally inconsistent, which blocks verification. Examples include '0.3 5', '0 .82', and '0 .65' in Table 2, and in Table 3 the GS Jaccard w cell at GB τ=50% and 60% is shown as 0 even though Table 2 reports a 0% success rate for the same cells, conflicting with the '-' convention used elsewhere for 'no successful attack'. The tables need to be regenerated with a consistent format, with all empty cells explicitly marked.
  5. [§6, §7] The claim that the GA 'has the capacity to meet or exceed the original greedy search in terms of perturbed document quality' is supported only by three qualitative examples, one of which (Figure 3) shows the greedy search producing a better perturbation. There is no quantitative document-quality metric or systematic evaluation, and Section 4 admits the GA parameters are restrictive while Section 5 states that larger datasets could not be tested. The conclusion in Section 7 therefore overstates the strength and generality of the evidence.
minor comments (5)
  1. [§2] The sentence 'This list ensures out criteria of generalizability' contains a typo; it should read 'our criteria'.
  2. [§4] The phrase 'solutions to are composed of a population' is ungrammatical and should be rewritten.
  3. [§3.2] The four thresholds (30–60%) and the chosen similarity measures are taken from Burger et al. (2024) without definitions; the paper should include a self-contained summary of the measures or at least define the weighted variants, especially since the weighted measures are central to several reported improvements.
  4. [§3.1] Equation (7) uses |f| in the perturbation cap constraint, whereas Equation (4) uses |db|; the notation should be made consistent.
  5. [§5] The paper does not provide a code or data availability statement; given that the experiments are not reproducible from the text alone, the authors should release code and seeds or at least describe the exact experimental pipeline.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the genetic-algorithm comparison is an empirical measurement with explicit thresholds, and the self-citations set the baseline but do not force the result.

full rationale

The paper's central claim is that a genetic algorithm finds smaller minimum viable perturbations than the prior greedy search. This is an empirical comparison, not a derivation that assumes its conclusion. The search objective is stated explicitly in Equation (7) with a threshold and constraints, and both the greedy and genetic searches are run against the same objective; the reported minima in Table 5 are observed outcomes of those runs, not fitted parameters renamed as predictions. The success thresholds and similarity measures are adopted from the authors' own prior work (Burger et al., 2023; Burger et al., 2024), and the greedy baseline is also from Burger et al., 2023, so the comparison is relative to self-defined criteria. However, this is a parameter and baseline choice, not a circular reduction: no equation in the paper defines the GA's minimum perturbation count to equal the greedy count, and no fitted value is repackaged as an independent prediction. The statistical concerns raised about single stochastic runs, small population size, and twenty examples per dataset affect the reliability of the stability estimate, but they are validity issues rather than circularity. The derivation chain is therefore self-contained with respect to the stated thresholds and constraints.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central claim rests on a handful of chosen parameters: the GA population size and generation count (10 and 10), the 20-example sample, and the similarity thresholds imported from prior work. The paper also assumes that a restrictive single-run GA explores the space well enough to estimate minimum perturbations, and that the semantic constraint is satisfied even though it is not enforced during search. No invented entities are introduced.

free parameters (5)
  • GA population size = 10
    Chosen due to computational limits, not tuned or fitted; Section 4 states population of size 10.
  • GA number of generations = 10
    Explicitly limited by computational constraints; Section 4 says maximum of 10 generations.
  • Similarity success thresholds tau = 30%, 40%, 50%, 60%
    Taken from the authors' concurrent work (Burger et al., 2024), not fitted here, but they define the success criterion and thus the reported attack rates and perturbation counts.
  • Number of test examples per dataset = 20
    Arbitrary selection without power analysis or stratification; Section 5 says 'we select twenty examples'.
  • Semantic threshold delta, perturbation cap epsilon, top-k constraint = unspecified
    Mentioned in the objective function (Eq. 7) but values are not reported in the experiments; delta is 'generally not invoked during the search process'.
assumptions (4)
  • domain assumption The success of an attack is defined by a fixed similarity threshold tau under a chosen ranked-list similarity measure.
    Section 3.2 adopts thresholds from Burger et al. (2024); the entire stability estimate depends on this subjective choice.
  • domain assumption Fewer word perturbations required to reach a similarity threshold implies greater instability of the XAI method.
    Stated in the abstract and Section 1; this monotonicity assumption underlies the interpretation of all results.
  • ad hoc to paper A single run of the genetic algorithm with population 10 and 10 generations adequately explores the search space to find near-minimal perturbations.
    Section 4 acknowledges these limits are 'restrictive compared to most other genetic algorithms' and that computational limits prevented larger settings.
  • domain assumption The semantic similarity constraint delta and prediction-preservation constraint f(db)=f(dp) are satisfied by the reported attacks.
    Section 3.1 says delta is 'generally not invoked during the search process' and only serves as a post-hoc check; the paper does not report how many candidates were discarded.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improving Stability Estimates in Adversarial Explainable AI through Alternate Search Methods." pith.science (2026). https://pith.science/paper/JBESZU6T

@misc{pith2026250109006,
  author       = {Pith},
  title        = {Pith review of: Improving Stability Estimates in Adversarial Explainable AI through Alternate Search Methods},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JBESZU6T}},
  note         = {Machine review of arXiv:2501.09006}
}
read the original abstract

Advances in the effectiveness of machine learning models have come at the cost of enormous complexity resulting in a poor understanding of how they function. Local surrogate methods have been used to approximate the workings of these complex models, but recent work has revealed their vulnerability to adversarial attacks where the explanation produced is appreciably different while the meaning and structure of the complex model's output remains similar. This prior work has focused on the existence of these weaknesses but not on their magnitude. Here we explore using an alternate search method with the goal of finding minimum viable perturbations, the fewest perturbations necessary to achieve a fixed similarity value between the original and altered text's explanation. Intuitively, a method that requires fewer perturbations to expose a given level of instability is inferior to one which requires more. This nuance allows for superior comparisons of the stability of explainability methods.

Figures

Figures reproduced from arXiv: 2501.09006 by the authors.

Figure 1
Figure 1. Successful attacks at the 30% threshold under [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Successful attacks at the 50% threshold under [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. The greedy search can produce a superior [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

  1. [1]

    The Effect of Similarity Measures on Accurate Stability Estimates for Local Surrogate Models in Text-based Explainable AI

    Alvarez-Melis, D., & Jaakkola, T. S. (2018). On the robustness of interpretability methods. Alzantot, M., Sharma, Y ., Elgohary, A., Ho, B.-J., Srivastava, M., & Chang, K.-W . (2018). Generating natural language adversarial examples. Burger, C., Chen, L., & Le, T. (2023). “Are Your Explanations Reliable?" Investigating the Stability of LIME in Explaining ...

    work page Pith review arXiv 2018

  2. [33]

    Fooling Explanations in Text Classifiers

    https://doi.org/10.1609/aaai.v33i01.33013681 Gramegna, A., & Giudici, P . (2021). Shap and lime: An evaluation of discriminative power in credit risk. Frontiers in Artificial Intelligence , 4, 752558. Ivankay, A., Girardi, I., Marchiori, C., & Frossard, P . (2022). Fooling explanations in text classifiers. International Conference on Learning Representation...

    work page Pith review arXiv 2021

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.