Research map / Label-efficient and robust learning / Recognition and long-tail

A General Search-Based Framework for Generating Textual Counterfactual Explanations

AAAI 2024 · Label-efficient and robust learning › Recognition and long-tail · approach: Post-hoc explanation analysis

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes TCE-Search, a model-agnostic, domain-agnostic anytime weighted-A* search framework that generates textual counterfactual explanations for text classifiers and adapts to changed distance functions without retraining.

Problem

Textual counterfactual explanations are usually produced by generative language models trained for a fixed loss, so changing user requirements (distance, confidence, time budget) requires costly retraining; they also often depend on differentiable black boxes.

Approach

Model the counterfactual generation as a search over texts (initial state = classified text, goal = text in target class with confidence above threshold), using MLM mask-filling, a novel differentiating-words-bank operator, optional WordNet antonym operator, a GPT-2 loss-ratio plausibility filter, and an iteratively relaxed weighted-A* anytime loop; the user distance is the cost function, so no re

Key results

• On 256-word sentiment datasets, TCE-Search reached lower Levenshtein distance than MiCE on Airline (0.257 vs 0.269) and SST (0.207 vs 0.256) and much lower cosine/syntactic distances, though MiCE had lower Levenshtein on Yelp (0.266 vs 0.56) and Amazon (0.32 vs 0.448).
• On single-sentence datasets, TCE-Search achieved Levenshtein distances of 0.085-0.266 versus 0.562-0.818 for Polyjuice and Tailor, with all differences statistically significant.
• Human raters scored original texts 3.66 and counterfactuals 3.33 on a 1-5 movie-review plausibility scale, a difference that was not statistically significant.

Measured effects reported in the paper

Surprising findings

• On 256-word Yelp and Amazon, MiCE achieved lower Levenshtein distance than TCE-Search, contrary to the general trend in the paper.
• Removing the WordNet antonym operator had no significant effect on performance.

Limitations

• Evaluation focuses on binary text classification with mostly random forest black boxes; utility of explanations to humans is not yet studied.
• Baselines were augmented and compared with differing expensive-call budgets (MiCE used roughly 1080 EC vs 2000 for TCE-Search), so comparison is not budget-matched.
• Not all datasets are won on every metric; MiCE has lower Levenshtein distance on some 256-word datasets.

Experimental setup

Datasets: Yelp Amazon SST Science Genre AGNews Airline Spam

Benchmarks: Yelp Amazon SST Science Genre AGnews Airline Spam

Metrics: normalized Levenshtein distance normalized cosine distance normalized syntactic tree distance LM loss ratio (plausibility) human plausibility rating

Baselines: MiCE Polyjuice Tailor

Builds on: weighted A* MiCE Polyjuice Tailor DistilBERT

Closest papers by meaning

• Faithful Explanations of Black-box NLP Models Using LLM-generated Counterfactuals (ICLR 2024 · similarity 0.88)
• NOMATTERXAI: Generating “No Matter What” Alterfactual Examples for Explaining Black-Box Text Classification Models (AAAI 2025 · similarity 0.88)
• Robust Stochastic Graph Generator for Counterfactual Explanations (AAAI 2024 · similarity 0.86)
• DiCoFlex: Model-Agnostic Diverse Counterfactuals with Flexible Control (NeurIPS 2025 · similarity 0.86)
• Counterfactual Maps: What They Are and How to Find Them (NeurIPS 2026 · similarity 0.86)
• Generating Likely Counterfactuals Using Sum-Product Networks (ICLR 2025 · similarity 0.86)