Lune

EMNLP Findings2024

Can LLM Graph Reasoning Generalize beyond Pattern Memorization?

Yizhuo Zhang, Heng Wang, Shangbin Feng, Zhaoxuan Tan, Xiaochuang Han, Tianxing He, Yulia Tsvetkov

Abstract

Large language models (LLMs) demonstrate great potential for problems with implicit graphical structures, while recent works seek to enhance the graph reasoning capabilities of LLMs through specialized instruction tuning. The resulting "graph LLMs" are evaluated with in-distribution settings only, thus it remains underexplored whether LLMs are learning generalizable graph reasoning skills or merely memorizing patterns in the synthetic training data. To this end, we propose the NLGIFT benchmark, an evaluation suite of LLM graph reasoning generalization: whether LLMs could go beyond semantic, numeric, structural, reasoning patterns in the synthetic training data and improve utility on real-world graph-based tasks. Extensive experiments with two LLMs across four graph reasoning tasks demonstrate that while generalization on simple patterns (semantic, numeric) is somewhat satisfactory, LLMs struggle to generalize across reasoning and real-world patterns, casting doubt on the benefit of synthetic graph tuning for real-world tasks with underlying network structures. We explore three strategies to improve LLM graph reasoning generalization, and we find that while post-training alignment is most promising for real-world tasks, empowering LLM graph reasoning to go beyond pattern memorization remains an open research question. 1 1 Code and data are publicly available at https://github.com/MatthewYZhang/NLGift.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

16 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • QLoRA: Efficient Finetuning of Quantized LLMs cites Training language models to follow instructions with human feedback
  • Direct Preference Optimization: Your Language Model is Secretly a Reward Model cites Training language models to follow instructions with human feedback
  • Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak Supervision cites Training language models to follow instructions with human feedback
  • GraphChain: Large Language Models for Large-scale Graph Analysis via Tool Chaining cites Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers16

  1. GRAVER: Generative Graph Vocabularies for Robust Graph Foundation Models Fine-tuningHaonan Yuan, Qingyun Sun, Junhua Shi, Xingcheng Fu et al.NeurIPS 2025 · 17 citations
  2. GraphChain: Large Language Models for Large-scale Graph Analysis via Tool ChainingChunyu Wei, Wenji Hu, Xingjia Hao, Xin Wang et al.NeurIPS 2025 · 7 citations
  3. GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic TasksHao Xu, Xiangru Jian, Xinjian Zhao, Wei Pang et al.ICLR 2026 · 6 citations
  4. From Sequence to Structure: Uncovering Substructure Reasoning in TransformersXinnan Dai, Kai Yang, Jay Revolinsky, Kai Guo et al.NeurIPS 2025 · 3 citations
  5. EvoGM: Learning to Merge LLMs via Evolutionary Generative OptimizationTao Jiang, Xinmeng Yu, Chenhao Yi, Yiling Wu et al.ICML 2026 · 1 citation

Builds on28

  1. Training language models to follow instructions with human feedbackLong Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida et al.NeurIPS 2022 · 24,707 citations
  2. Direct Preference Optimization: Your Language Model is Secretly a Reward ModelRafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning et al.NeurIPS 2023 · 10,924 citations
  3. QLoRA: Efficient Finetuning of Quantized LLMsTim Dettmers, Artidoro Pagnoni, Ari Holtzman, Luke ZettlemoyerNeurIPS 2023 · 5,863 citations
  4. Reasoning on Graphs: Faithful and Interpretable Large Language Model ReasoningLinhao Luo, Yuan-Fang Li, Gholamreza Haffari, Shirui PanICLR 2024 · 499 citations
  5. Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak SupervisionCollin Burns, Pavel Izmailov, Jan Hendrik Kirchner, Bowen Baker et al.ICML 2024 · 443 citations

Related papers

  1. Generalizable LLM Learning of Graph Synthetic Data with Post-training AlignmentYizhuo Zhang, Heng Wang, Shangbin Feng, Zhaoxuan Tan et al.ACL Findings 2026
  2. Can Language Models Solve Graph Problems in Natural Language?Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan et al.NeurIPS 2023 · 420 citations
  3. Evaluating LLMs on Large-Scale Graph Property Estimation via Random WalksSunil Kumar Maurya, Xin LiuACL 2026
  4. InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference AlignmentJianing Wang, Junda Wu, Yupeng Hou, Yao Liu et al.ACL Findings 2024 · 15 citations
  5. G1: Teaching LLMs to Reason on Graphs with Reinforcement LearningXiaojun Guo, Ang Li, Yifei Wang, Stefanie Jegelka et al.NeurIPS 2025 · 16 citations
Dusk over the sea between two cliffs drawn in fine vertical lines