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

Haoyu Han, Li Ma, Hanbing Wang, Bingheng Li, Daochen Zha, Chun How Tan, Huiji Gao, Xin Liu, Stephanie Moyerman, Sanjeev Katariya, Hui Liu, Jiliang Tang Michigan State University, Airbnb, Inc. {hanhaoy1, mali13, wangh137, libinghe, liuhui7, tangjili}@msu.edu {daochen.zha, chunhow.tan, huiji.gao, xin.liu}@airbnb.com {stephanie.moyerman, sanjeev.katariya}@airbnb.com · 2026

Read An Embarrassingly Simple Graph Heuristic Reveals Shortcut-Solvable Benchmarks for Sequential Recommendation by Haoyu Han, Li Ma, Hanbing Wang, Bingheng Li, Daochen Zha, Chun How Tan, Huiji Gao, Xin Liu, Stephanie Moyerman, Sanjeev Katariya, Hui Liu, Jiliang Tang Michigan State University, Airbnb, Inc. {hanhaoy1, mali13, wangh137, libinghe, liuhui7, tangjili}@msu.edu {daochen.zha, chunhow.tan, huiji.gao, xin.liu}@airbnb.com {stephanie.moyerman, sanjeev.katariya}@airbnb.com (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07125.txt.

Introduction

Haoyu Han and eleven co-authors audit recommendation benchmarks with a deliberately simple graph trick. Starting from only a user's last one or two items, their heuristic walks a small item-transition graph and ranks candidates by feature similarity. It uses no sequence encoder, no generative training, and no learned model at all.

Despite that simplicity, the heuristic matched or beat many modern systems on major datasets, with large gains on two Amazon categories. The authors trace the effect to shortcut structures in the data, such as predictable local transitions. Across fourteen datasets, the heuristic stayed competitive on ten, warning that strong benchmark scores need not show advanced modeling.

Catalog record

CREATORHaoyu Han, Li Ma, Hanbing Wang, Bingheng Li, Daochen Zha, Chun How Tan, Huiji Gao, Xin Liu, Stephanie Moyerman, Sanjeev Katariya, Hui Liu, Jiliang Tang Michigan State University, Airbnb, Inc. {hanhaoy1, mali13, wangh137, libinghe, liuhui7, tangjili}@msu.edu {daochen.zha, chunhow.tan, huiji.gao, xin.liu}@airbnb.com {stephanie.moyerman, sanjeev.katariya}@airbnb.com
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07125

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Embarrassingly Simple Graph Heuristic Reveals Shortcut-Solvable Benchmarks for Sequential Recommendation Haoyu Han, Li Ma, Hanbing Wang, Bingheng Li, Daochen Zha, Chun How Tan, Huiji Gao, Xin Liu, Stephanie Moyerman, Sanjeev Katariya, Hui Liu, Jiliang Tang Michigan State University, Airbnb, Inc. {hanhaoy1, mali13, wangh137, libinghe, liuhui7, tangjili}@msu.edu {daochen.zha, chunhow.tan, huiji.gao, xin.liu}@airbnb.com {stephanie.moyerman, sanjeev.katariya}@airbnb.com Abstract Sequential recommendation is a central task in recommender systems, and recent research has increasingly shifted toward generative recommenders that leverage both sequential patterns and semantic item information. However, these methods are often evaluated on a small set of widely used benchmarks. This raises a natural question: do these benchmarks actually require the advanced modeling capabilities of modern generative recommenders? We conduct a benchmark audit using an intentionally simple graph heuristic: starting from only the last one or two interacted items, it retrieves candidates from a few-hop item-transition graph and ranks them with item-feature similarity. Surprisingly, despite its simplicity, this heuristic matches or outperforms a broad set of modern baselines on a variety of popular sequential recommendation benchmarks. For example, it achieves relative NDCG@10 improvements of 38.10% and 44.18% over the best competing baseline on the widely used Amazon Review Sports and CDs datasets, respectively. We further show that this phenomenon is not merely an artifact of a particular heuristic, but reflects shortcut solvability in existing benchmarks. Specifically, we identify three shortcut structures that could make next-item prediction easier than expected: low-branching local transition structure, feature-smooth transitions, and limited dependence on long user histories. These shortcuts need not appear simultaneously. Depending on the dataset, even one or two strong shortcut signals can make simple local retrieval highly competitive, while weakening the relevant signals allows more sophisticated models to show clearer benefits. Our broader evaluation across 14 diverse datasets further shows that model rankings change substantially with dataset properties, while the simple graph heuristic remains competitive on 10 out of 14 datasets. These findings suggest that strong performance on several standard sequential recommendation benchmarks may not faithfully reflect whether recent methods achieve the advanced modeling capabilities they aim to demonstrate. Rather than treating datasets as interchangeable leaderboards, we argue for more careful dataset selection and dataset-level diagnostic analysis when using benchmarks to support claims about the benefits of new recommendation models. 1 Introduction Sequential recommendation has long been a fundamental problem in recommender systems, where the goal is to infer a user’s next interaction from past behaviors 2 ; 34 ; 7 . Early studies mainly relied on collaborative filtering 19 ; 6 and Markov-chain models 20 ; 12 , while later neural methods introduced recurrent networks 14 ; 40 , graph-based recommenders 13 ; 48 , and attention-based sequence encoders 52 ; 51 . Recently, however, the field has seen a rapid rise of generative recommendation methods 36 ; 44 ; 16 . These generative methods reformulate recommendation as generation or retrieval over discrete item identifiers, semantic IDs, or textual item representations 10 ; 21 . As a result, item-side information has become increasingly central: many recent models rely on item text, metadata, semantic embeddings, or LLM-generated representations to construct item codes, prompts, or prediction targets 46 ; 16 ; 22 . Figure 1 : The proportion of surveyed sequential recommendation papers utilizing each dataset. Along with this methodological shift, evaluation practice has also become strikingly concentrated. We analyze dataset usage across 94 recent generative-recommendation papers, detailed in Appendix A . As shown in Figure 1 , Amazon Review datasets 32 dominate recent evaluations, while other datasets are used much less frequently. This dominance is understandable: Amazon Review datasets provide rich item-side metadata, such as titles, categories, brands, prices, reviews, and other textual fields, which can be naturally processed by text encoders or LLM-based generators 4 ; 42 for semantic and generative recommendation. However, this concentration creates a critical question: what do these dominant benchmarks actually measure? High performance on these datasets is often taken as evidence that a model better captures user preferences, sequential dynamics, semantic structure, long-range dependencies, or generative reasoning. But this interpretation relies on an implicit assumption: the benchmark truly requires these advanced capabilities. If the same benchmark can be solved by a much simpler signal, then the comparison may be less informative than it appears. Strong performance may reflect dataset-specific shortcuts rather than genuinely advanced sequential modeling. In this work, we uncover such shortcuts. We revisit widely used sequential recommendation benchmarks through an intentionally simple graph heuristic. Given only the training sequences, we construct an item-transition graph from observed item-to-item transitions. At test time, the heuristic looks only at the user’s last one or two interacted items, retrieves candidates from their few-hop neighborhoods in the transition graph, and ranks them by item-feature similarity with a small direct-edge bonus. It has no deep sequence encoder, no generative objective, no learned user representations, and no training, making it simple and computationally efficient. Despite its simplicity, this heuristic outperforms a broad set of strong baselines on the Amazon Review benchmarks, including traditional sequential models, graph-based recommenders, transformer-based recommenders, and recent generative recommenders. This result suggests that strong performance on these datasets may be achievable through much simpler signals than expected . Therefore, relying only on these datasets may not faithfully reflect the advanced modeling capabilities that recent methods aim to demonstrate. To understand why this happens, we identify three shortcut structures that potentially help explain this phenomenon: low-branching local transition structure, where recent items have small but useful transition neighborhoods; feature-smooth transitions, where transition-connected items are close in feature space; and limited dependence on long user histories, where the last one or two interactions already provide enough signal for next-item prediction. We then ask whether this phenomenon is unique to Amazon Review benchmarks or reflects a broader issue in sequential recommendation evaluation. To answer this question, we evaluate the same baselines across 14 datasets with diverse transition structures, feature signals, and history dependencies. The simple heuristic remains competitive on 10 of them, suggesting that shortcut-solvable structures are widespread in existing benchmarks . At the same time, the heuristic is not universally superior: when the relevant shortcut signals are weakened, more sophisticated models can show clearer benefits. These results suggest two cautions for the community. For model designers, we encourage benchmark choices to be aligned with the capabilities being claimed. Methods that claim improved semantic understanding, generative modeling, or long-context reasoning should ideally be evaluated on datasets where simple local-transition, feature-similarity, or short-history shortcuts are insufficient. For dataset and benchmark creators, dataset releases would benefit from accompanying diagnostic analyses of transition structure, feature smoothness, history dependence, and other relevant properties. Such diagnostics can help clarify what a dataset actually measures and reduce the risk that future evaluations mistake shortcut-solvable performance for genuine modeling progress. 2 Related Work Sequential recommendation. Sequential recommendation aims to predict the next item a user will interact with given a historical interaction sequence. Early approaches often combine collaborative filtering with sequential transition modeling ( 20 ) . For example, matrix factorization ( 26 ) learns user and item representations from historical interactions, while Markov-chain-based methods model short-term item-to-item transitions 37 . Later neural methods introduce more expressive sequence encoders to capture user dynamics. GRU4Rec 14 uses recurrent neural networks to model session-level

Read the complete text