Abstract
Counterfactual explanations are essential for making AI models interpretable, yet generating them for text remains challenging due to the rigidity of generative models. We present TCE-SEARCH, a search-based framework that treats counterfactual generation as an optimization problem. Unlike generative approaches, TCE-SEARCH is model-agnostic, requires no retraining for new constraints, and supports any user-defined distance metric. Our evaluation across eight datasets demonstrates that TCE-SEARCH produces more precise and human-plausible explanations than current state-of-the-art models.
Introduction
In Explainable AI (XAI), counterfactuals provide intuitive "what-if" scenarios (e.g., "If your income were higher, your loan would be approved"). In natural language processing, current methods often rely on generative models like GPT or T5. However, these models are often "white-box" dependent and rigid; changing user requirements, such as a preference for syntactic over semantic similarity, typically necessitates costly retraining.
TCE-SEARCH addresses these limitations by reframing counterfactual generation as a heuristic search problem. It acts as a "plug-and-play" solution compatible with any black-box text classifier and adaptable to diverse user constraints without further training.
Methodology
TCE-SEARCH explores the modification space of an original text to find the minimal change required to flip a classifier's prediction.
Search Strategy
The framework utilizes a variation of Weighted-A search. It balances the cost (distance from the original text) with a heuristic (proximity to a label flip). A key advantage is its anytime property*, allowing the system to return the best-found solution at any point during the search, which is vital for interactive use.
Modification Operators
To navigate the search space efficiently, TCE-SEARCH employs several operators:
- Mask Filling: Uses Masked Language Models (e.g., DistilBERT) for context-aware word replacement.
- Differentiating Words Banks (DWB): A novel statistical operator that prioritizes words strongly associated with the target class, significantly narrowing the search space.
- Domain-Specific Operators: Includes WordNet-based antonym replacement for sentiment tasks.
- Plausibility Filtering: A fine-tuned GPT-2 model calculates a "plausibility ratio" to ensure generated text remains natural and coherent.
Experimental Results
The framework was rigorously tested on eight datasets spanning sentiment analysis (Yelp, Amazon, SST, Airline), topic classification (Science, Genre, AGNews), and spam detection.
Performance and Flexibility
TCE-SEARCH consistently outperformed baselines like MiCE, Polyjuice, and Tailor. It achieved superior proximity across Levenshtein, Cosine, and Syntactic distance metrics. Notably, the framework proved truly model-agnostic, maintaining high performance across various classifiers including Random Forests and SVMs.
Human Evaluation
A human study revealed that TCE-SEARCH produces highly plausible counterfactuals. Participants rated the plausibility of generated text at 3.33/5.0, nearly matching original human-written text (3.66/5.0), with no statistically significant difference between the two.
Conclusion and Future Work
TCE-SEARCH demonstrates that search-based methods offer superior flexibility and precision over generative models for textual counterfactuals. While search is computationally more intensive than a single generative pass, the "anytime" capability and statistical guidance from DWB mitigate this overhead. Future research will focus on more complex structural rephrasing beyond word-level edits and investigating the practical utility of these explanations in real-world human-AI decision-making.
Summary updated