Technical Summary: An Embarrassingly Simple Graph Heuristic Reveals Shortcut-Solvable Benchmarks for Sequential Recommendation

Problem Statement

Sequential recommendation aims to predict a user's next interaction based on their historical behavior sequence. While recent research has shifted toward sophisticated generative recommenders that leverage semantic item information (e.g., text, metadata) and advanced architectures (e.g., Transformers, LLMs), these methods are predominantly evaluated on a narrow set of widely used benchmarks, particularly the Amazon Review datasets.

The core problem addressed is whether these dominant benchmarks truly require the advanced modeling capabilities (semantic understanding, long-range dependency modeling, generative reasoning) that modern methods claim to possess. The authors hypothesize that high performance on these benchmarks may not reflect genuine modeling progress but rather the exploitation of "shortcut solvability"—simple signals inherent in the dataset structure that allow trivial methods to outperform complex models.

Methodology

1. The Diagnostic Heuristic: Transition-Graph Heuristic (TGH)

To audit these benchmarks, the authors introduce TGH, an intentionally simple, training-free graph heuristic. TGH relies solely on two signals: collaborative transition structure and item-feature similarity.

• Graph Construction: A directed item-transition graph is built from training sequences, where edges represent observed item-to-item transitions. Edge weights are normalized based on transition frequency.
• Inference Mechanism: Given a user's interaction history, TGH uses only the last one or two items as "anchors."
• Candidate Retrieval: It retrieves candidates from the few-hop neighborhoods (1-hop, 2-hop, 3-hop) of the anchor items in the transition graph.
• Ranking: Candidates are ranked using a scoring function combining:
  1. Feature Similarity: Cosine similarity between the anchor's and candidate's L2-normalized feature embeddings (derived from a shared text encoder, e.g., Flan-T5).
  2. Transition Bonus: A small bonus for direct 1-hop neighbors based on the normalized edge weight.
• Constraints: TGH uses no sequence encoders, no learned user representations, no generative objectives, and no training. It is computationally efficient and deliberately avoids hyperparameter tuning specific to individual datasets.

2. Experimental Setup

• Datasets: The study evaluates TGH on 14 diverse datasets, including the four dominant Amazon Review subsets (Beauty, Sports, Toys, CDs) and ten others (e.g., LastFM, MovieLens-1M, Yelp, MIND, Steam, GoodReads).
• Baselines: TGH is compared against a broad spectrum of models:
  • Collaborative filtering (LightGCN).
  • Graph-based session recommenders (SR-GNN).
  • Traditional sequential models (SASRec, HSTU).
  • Recent generative recommenders (TIGER, LETTER, CoFiRec).
• Diagnostic Baselines: To isolate specific signals, the authors introduce:
  • ID-LAST: Uses only the last item ID.
  • SEM-NN: Uses only semantic feature similarity.
  • ID+SEM: Combines both.
  • History Ablation: Restricts complex models (SASRec, HSTU) to use only the last item (Last-1) to test dependence on long histories.

Key Contributions and Findings

1. Surprising Performance of Simple Heuristics

On the Amazon Review benchmarks, TGH matches or significantly outperforms state-of-the-art baselines.

• Results: On the Sports dataset, TGH achieves a 38.10% relative NDCG@10 improvement over the best competing baseline. On CDs, the improvement is 44.18%.
• Implication: Strong performance on these widely used benchmarks can be achieved without deep sequence modeling or generative capabilities, suggesting the benchmarks may be "shortcut-solvable."

2. Identification of Three Shortcut Structures

The authors identify three structural properties in datasets that enable simple heuristics to succeed:

1. Low-Branching Local Transition Structure: The item-transition graph has a small average out-degree. Recent items lead to a small, informative local candidate space, narrowing the prediction task from the full item universe to a few plausible neighbors.
2. Feature-Smooth Transitions: Items that appear sequentially in user histories tend to have similar semantic features. This allows feature similarity (even without transition data) to serve as a strong ranking signal.
3. Limited Dependence on Long User Histories: For many datasets, the last one or two interactions contain sufficient signal for accurate prediction. Long-range sequential dependencies are not strictly necessary for high performance on these specific benchmarks.

3. Cross-Dataset Generalization and Limitations

• Widespread Shortcut Solvability: Across 14 diverse datasets, TGH remains competitive (ranking best or second-best) on 10 out of 14 datasets.
• Failure Cases: TGH underperforms on datasets like MovieLens-1M, Yelp, and MIND.
  • Reasoning: On MovieLens-1M, the high branching factor (large out-degree) makes local retrieval less effective. On MIND and MovieLens, models show a significant performance drop when restricted to short histories (Last-1), indicating a genuine need for long-context modeling that TGH cannot capture.
• Prediction Overlap: Analysis of prediction sets shows low overlap between TGH and learned models. TGH succeeds on instances solvable by local shortcuts, while learned models capture additional signals (long-range dependencies, complex user behaviors) that TGH misses.

Significance and Claims

The paper argues that the current evaluation landscape in sequential recommendation may be misleading.

• Benchmark Validity: High performance on standard benchmarks (especially Amazon Review) does not necessarily validate the advanced capabilities (semantic understanding, generative reasoning) claimed by new models. These results may simply reflect the exploitation of dataset-specific shortcuts.
• Call for Capability-Aware Evaluation:
  • For Model Designers: Benchmarks should be selected to align with the specific capabilities being claimed. Methods claiming long-context reasoning should be tested on datasets where short-history shortcuts are insufficient.
  • For Benchmark Creators: Datasets should be released with diagnostic analyses (e.g., transition branching, feature smoothness, history dependence) to clarify what signals the benchmark rewards.
• Conclusion: Rather than treating datasets as interchangeable leaderboards, the community should use them as tools to understand when and why different models succeed. The goal is to shift focus from optimizing for shortcut-solvable benchmarks to addressing harder, more realistic recommendation challenges.

The authors maintain a modest stance, clarifying that they do not claim advanced models are ineffective, but rather that the current benchmarks may not be sufficient to demonstrate their benefits. The work serves as a diagnostic audit to encourage more rigorous and transparent evaluation practices.