Demystifying Sequential Recommendations: Counterfactual Explanations via Genetic Algorithms

Domiziano Scarcelli, Filippo Betello, Giuseppe Perelli, Fabrizio Silvestri, Gabriele TolomeiarXiv 2025 · arXiv · OpenReview

Introduction

Sequential Recommender Systems (SRSs) have become the backbone of modern digital platforms, from streaming services to e-commerce. By analyzing the chronological order of user interactions, these systems can capture evolving preferences and suggest the most relevant next item. However, as these models grow in complexity—utilizing deep learning architectures like Transformers and RNNs—they increasingly become "black boxes." This lack of transparency makes it difficult for users to trust recommendations and for developers to debug model behavior.

The Challenge of Explainability

The core problem addressed in this research is the lack of interpretable explanations for SRS decisions. The authors propose using counterfactual explanations to bridge this gap. A counterfactual explanation answers a simple yet powerful "what-if" question: "What is the smallest change I could make to my interaction history so that the system would recommend a different item?"

Sequential recommendation models predict the next item based on a history of user interactions.

By identifying the smallest set of actions (e.g., removing a specific purchase or swapping one movie for another) that alters the outcome, counterfactuals provide actionable insights into the model's decision boundaries.

The Complexity of the Search Space

Finding the "optimal" counterfactual—the absolute minimal change—is not trivial. The authors provide a formal mathematical proof that generating these explanations for sequential data is an NP-Complete problem (via reduction from the Vertex Cover problem). This means that as the number of items in a catalog grows, a brute-force search for the best explanation becomes computationally impossible. This finding justifies the need for sophisticated heuristic search methods.

The GECE Framework

To navigate this complex search space, the researchers introduced GECE (GEnetic Counterfactual Explanations). GECE is a specialized genetic algorithm designed specifically for discrete sequences. Unlike traditional genetic algorithms that operate on continuous values, GECE employs three discrete mutation operations:

  1. Replace: Swapping an existing item in the history.
  2. Add: Inserting a new interaction.
  3. Delete: Removing an interaction entirely.
Counterfactual explanations explore 'what-if' scenarios by questioning the model's output.

GECE evolves a population of potential counterfactual sequences using a dual-objective fitness function. It seeks to minimize the Hamming distance (keeping the explanation sparse and similar to the original history) while maximizing Logit Similarity (ensuring the model's internal scores shift toward the desired alternative recommendation). Crucially, GECE is model-agnostic, meaning it can explain any SRS without needing access to its internal gradients or architecture.

Experimental Evaluation

The framework was rigorously tested using three benchmark datasets: MovieLens (100k & 1M) and Steam. These datasets represent diverse domains with thousands of items and millions of interactions. The authors evaluated GECE against several state-of-the-art sequential models, including BERT4Rec, GRU4Rec, and SASRec.

Key Results

  • Perfect Fidelity: In untargeted scenarios, GECE achieved a Model Fidelity@1 of 1.0. This indicates that the algorithm successfully found a valid counterfactual for every single test case across all models and datasets.
  • Interpretability through Sparsity: GECE consistently identified counterfactuals with significantly lower Hamming distances than baseline methods, providing more concise and "human-readable" explanations.
  • Recency Bias Discovery: The experiments highlighted that changes to the most recent items in a user's history have the most significant impact on the next recommendation, confirming the strong recency bias in modern SRS architectures.

Conclusion and Future Directions

This work establishes a robust foundation for explainable sequential recommendations. By proving the NP-Completeness of the problem and providing an efficient genetic algorithm solution, the authors offer a path toward more transparent AI. While the current approach is highly effective, future work will focus on reducing the computational overhead of multiple inference passes and conducting human-centric studies to ensure these mathematical explanations align with user intuition.

Summary updated

Abstract

Sequential Recommender Systems (SRSs) have demonstrated remarkable effectiveness in capturing users' evolving preferences. However, their inherent complexity as "black box" models poses significant challenges for explainability. This work presents the first counterfactual explanation technique specifically developed for SRSs, introducing a novel approach in this space, addressing the key question: What minimal changes in a user's interaction history would lead to different recommendations? To achieve this, we introduce a specialized genetic algorithm tailored for discrete sequences and show that generating counterfactual explanations for sequential data is an NP-Complete problem. We evaluate these approaches across four experimental settings, varying between targeted-untargeted and categorized-uncategorized scenarios, to comprehensively assess their capability in generating meaningful explanations. Using three different datasets and three models, we are able to demonstrate that our methods successfully generate interpretable counterfactual explanation while maintaining model fidelity close to one. Our findings contribute to the growing field of Explainable AI by providing a framework for understanding sequential recommendation decisions through the lens of "what-if" scenarios, ultimately enhancing user trust and system transparency.
BibTeX
@misc{scarcelli2025demystifying,
  author = {Domiziano Scarcelli and Filippo Betello and Giuseppe Perelli and Fabrizio Silvestri and Gabriele Tolomei},
  title = {{Demystifying Sequential Recommendations: Counterfactual Explanations via Genetic Algorithms}},
  year = {2025},
  eprint = {2508.03606},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.03606},
}
Figure