Was It Sunday Night or Did You Change? Time-Aware Counterfactual Explanations for Sequential Recommenders

When a recommender suggests something, a user (or an auditor) wants to know why. For recommenders that read a user's history in order, a common answer is a counterfactual explanation: the smallest edit to the history that would have changed the recommendation, for example "had you not watched these two films, you would have been shown something else." Current methods search for such edits by deleting, inserting or replacing items, and they treat the history as a plain ordered list. Human behavior is not plain, though. It repeats daily and weekly, and it also changes over months. So a recommendation might be driven by a real change in taste, or simply by the fact that it is Sunday night and this user always watches comedies then. An explanation that only edits items cannot tell these two causes apart. Searching for item edits is also expensive, because every candidate edit costs a forward pass of the model.

This note proposes treating the explanation search as variable neighborhood search, a classic optimization strategy that tries a sequence of different move types and switches to the next type when the current one stops improving. Here each move type corresponds to a different kind of explanation, and the types are ordered from cheapest to most expensive. The first move type changes only the time at which the recommendation is requested, with time encoded on a circle so that 11:59 PM sits next to 12:01 AM. The second edits recent items, which corresponds to drift in taste. The third edits older items that fell at the same point in the daily or weekly cycle, which corresponds to habit. Only after these does the search fall back to general block edits. The result is two things at once: a sparse counterfactual, and a label saying whether the recommendation is best explained by the clock, by recent drift, or by a recurring habit. Because many requests should be resolved by the cheap one-dimensional time move, the search should also need far fewer model calls.

Core Claim

For sequential recommenders that receive cyclical time features, we claim three things. First, a substantial share of recommendations can be flipped by changing the requested time phase alone. Second, explanations found by searching move types in a fixed, meaningful order are sparser than unordered genetic search under the same budget of model calls. Third, the move type that resolves each case recovers the true cause, cycle or drift, on semi-synthetic data where that cause is known.

The closest prior work is GECE, from Demystifying Sequential Recommendations: Counterfactual Explanations via Genetic Algorithms. That paper proves that finding the minimal counterfactual history edit is NP-complete, solves it with a genetic algorithm using replace, add and delete mutations, reaches Model Fidelity@1 of 1.0 in the untargeted setting on MovieLens and Steam, and finds that recommenders depend heavily on recent items. Our proposal differs from GECE in three ways. It explains models that actually consume timestamps, whereas GECE treats time only as order. It makes the time of the request itself something the explanation can edit. And it replaces undirected mutation with ordered move types whose identity is part of the explanation. GECE's recency finding motivates our second move type. Our hypothesis is that some of that apparent recency effect is really cyclical phase, which GECE could not see.

Research Program

The first step is to build the models that will be explained. We train SASRec-style sequential recommenders in two variants. One variant adds sine and cosine projections of hour-of-day and day-of-week to each interaction and to the query time, the same circle mapping used for time-of-day in Personalized neural language models for real-world query auto completion and for hour and day-of-year in Predicting Fuel Consumption and Flight Delays for Low-Cost Airlines. The other variant uses linearly normalized time. We also train a third variant with learned discrete time-bin embeddings, following Spatio-Temporal Adaptive Embedding Makes Vanilla Transformer SOTA for Traffic Forecasting. Before any explanation work, we check that the time-aware models are competitive at recommendation. This matters because explaining a model that ignores its time inputs would be meaningless.

The second step is the search itself. Following the standard shake-and-descend loop described in A Coevolutionary Variable Neighborhood Search Algorithm for Discrete Multitasking (CoVNS) and Optimization of Water Quality Monitoring Networks Using Metaheuristic Approaches, each run starts at the first move type. If the descent fails, the search widens to the next type. If it improves, the search returns to the first type. The four move types, in order, are:

  1. Shifting the query phase along the daily or weekly circle.
  2. Deleting or replacing items among the most recent interactions.
  3. Editing older interactions that share the query's phase, for example past Sunday evenings for a Sunday-evening request.
  4. Contiguous block deletion and insertion anywhere in the history.

Within each move type, descent is deterministic, in the manner of the variable neighborhood descent used in SVND Enhanced Metaheuristic for Plug-In Hybrid Electric Vehicle Routing Problem. The objective is to minimize edit size, with time-phase shifts given an explicit cost per hour moved, subject to the target recommendation changing. We report which move type resolved each case.

Sparsity alone could reward implausible edits, so moves that would place an interaction at a phase where this user has never been active are penalized.

The third step reduces the number of expensive model calls. Candidates are first screened with a small distilled copy of the recommender, and only the top candidates are scored by the full model. The final counterfactual is always verified on the full model, so fidelity is never traded for speed. The precedent is AttriBoT, which reports a Pearson correlation of about 0.9 between attributions from 1B and 70B models of the same family. We do not assume that correlation transfers to recommenders. We measure how well the small model's ranking of candidates agrees with the full model's, and treat that agreement as an empirical question.

Baselines

The naive reference point is a recency heuristic: delete the most recent items one at a time until the recommendation changes. GECE's recency-bias finding suggests this simple rule will often succeed. If our method does not produce smaller edits than this rule, it has no reason to exist.

The strongest simple competitor is greedy leave-one-out deletion. It scores each history item by how much removing it lowers the recommended item's logit, then removes items in that order until the recommendation flips. It costs one pass per item plus the deletions, and on easy cases it probably comes close to minimal.

The strongest existing method is GECE (Demystifying Sequential Recommendations). Its reported result is Model Fidelity@1 = 1.0 (untargeted) on MovieLens-100k, MovieLens-1M and Steam. The file gives no numerical Hamming distances for it, so we will rerun GECE ourselves rather than quote a sparsity figure.

All search methods will be run under the same rules. Each gets an identical cap on full-model forward passes, chosen at several budgets. Each runs on the same trained recommenders and the same test users. Each gets the same hyperparameter tuning trials on a validation split. GECE will also be given our time-phase move as an extra mutation, so it is not handicapped by lacking that move. Beating these baselines means that, at matched fidelity and matched budget, our method produces significantly smaller edits, measured as Hamming distance plus the phase-shift cost. Separately, our method must reach equal sparsity with fewer forward passes.

Three ablations isolate the key ingredients. The first randomizes the order of the move types, which tests whether the ordering matters. The second removes the time-phase move. The third swaps the cyclical recommender for the linear-time one, which tests whether circle geometry, rather than mere access to time, produces the phase explanations.

To check that our recommenders are competitive, we use CoDeR as an accuracy reference. CoDeR reports Recall@20 = 54.180 on Diginetica. We do not need to match that number, only to be in a range showing the time-aware model is a serious recommender.

Why not just…?

Why not just give GECE more generations? This is plausible for sparsity alone. Undirected mutation can also find small edits if it is given enough calls. The matched-budget curves will settle this question. If GECE equipped with the phase mutation matches our sparsity at every budget, the claim about move ordering fails. What would remain is the cause label, which GECE does not produce, so the ablation with random move-type order is the real test.

Why not just run greedy leave-one-out deletion? This is a serious threat on short histories, where greedy removal is often nearly optimal. Our expected advantage lies in cases where single items have small individual effects but jointly flip the recommendation, and in cases resolved by time alone, which greedy item deletion cannot express. We will report results separately by history length and by which move type resolved each case. If greedy deletion ties our method everywhere outside the time-phase cases, we will say that the contribution reduces to the time-phase move.

Why not just ablate the time features and skip search? Setting the query time to other phases and checking whether the recommendation changes is exactly our first move type, and it is cheap. If nearly every case is resolved there, the full search is unnecessary, and the simpler finding is itself the result. The search earns its place only for the remaining cases, where explanations mix cycle, drift and habit. We will report what fraction of cases falls in that remainder.

Why not just use an amortized explainer such as LXR? Learning Counterfactual Explanations for Recommender Systems trains a network that outputs an explanation mask in one pass. However, it was built for non-sequential models, it requires a differentiable recommender, and it outputs item masks rather than time edits. Our recommenders are differentiable, so a sequential adaptation of LXR is feasible, and we will include one as a latency reference. We expect it to be faster but less sparse and less often valid. The file contains no reported LXR result on sequential data. The speed of amortization is real: CF-VAE in Explaining a machine learning decision to physicians via counterfactuals reports 0.001 seconds against 0.37 seconds for optimization. If adapted LXR comes within a small margin of our sparsity, amortization is the better engineering choice.

Why not keep linear time? The linear-time ablation answers this directly. If phase explanations appear equally often and equally sparse under linear time, the circle mapping does not matter for this purpose.

Proposed Experiments

The datasets are those with real timestamps. MovieLens-1M and Steam are used for comparability with GECE. One caveat applies to both: MovieLens records when a rating was given and Steam records when a review was written, neither of which is consumption time, so their daily cycles may be weak. Diginetica and Tmall provide session timestamps. TaFeng has day-level dates only, so only the weekly cycle is available there.

The metrics are fidelity (the share of cases where the target recommendation flips), edit cost, full-model forward passes and wall-clock time per explanation, a plausibility score (the share of edits placed at phases where the user has been active before), and agreement between the small screening model and the full model.

The decisive check is semi-synthetic. On Diginetica and Steam histories, we inject a known signal into some users and train the recommender on the result. Some users receive a planted weekly habit, such as a genre chosen only on a fixed weekday. Others receive a planted drift, a permanent genre switch at a chosen date. We then measure whether the move type that resolves each explanation matches the planted cause, against chance and against the random-order ablation. If cause recovery is no better than chance, or if the linear-time recommender recovers causes equally well, the central claim is false.

A second decisive check returns to GECE's recency finding on real data. We measure how much of the recency effect disappears once the time-phase move is available.