mlsanityData to 7 Oct 2026

Can LLM Graph Reasoning Generalize beyond Pattern Memorization?

arXiv 2406.15992 ↗First posted 23 Jun 2024cs.CLcited by 46

On the map: LLM reasoning → Knowledge- and tool-augmented reasoning

Abstract (arXiv)

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.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning. Builds on 35 of its 51 references that are in the map. First posted on arXiv 23 Jun 2024.

Builds on

35 of 51 references.

Closest ancestors · 6

Same direction, newest first

  1. 2024GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability7 Mar
  2. 2024GraphWiz: An Instruction-Following Language Model for Graph Problems25 Feb
  3. 2024InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference Alignment13 Feb
  4. 2023GraphText: Graph Reasoning in Text Space2 Oct
  5. 2023Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning2 Oct
  6. 2023Can Language Models Solve Graph Problems in Natural Language?17 May

Other references · 29

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  3. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  4. 2023QLoRA: Efficient Finetuning of Quantized LLMscited by 3,355
  5. 2022When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memoriescited by 1,103
  6. 2021Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategiescited by 736
  7. 2024Dolma: an Open Corpus of Three Trillion Tokens for Language Model Pretraining Researchcited by 475
  8. 2023Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak Supervisioncited by 445
  9. 2023RepoCoder: Repository-Level Code Completion Through Iterative Retrieval and Generationcited by 357
  10. 2023Exploring the Potential of Large Language Models (LLMs) in Learning on Graphscited by 271
  11. 2023Language is All a Graph Needscited by 219
  12. 2023GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarkingcited by 209
17 more
  1. 2023LLMRec: Large Language Models with Graph Augmentation for Recommendationcited by 171
  2. 2022Language Models of Code are Few-Shot Commonsense Learnerscited by 160
  3. 2024Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokenscited by 148
  4. 2023Label-free Node Classification on Graphs with Large Language Models (LLMS)cited by 72
  5. 2022Parsel: Algorithmic Reasoning with Language Models by Composing Decompositionscited by 62
  6. 2021ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoningcited by 58
  7. 2023PiVe: Prompting with Iterative Verification Improving Graph-based Generative Capability of LLMscited by 44
  8. 2024DELL: Generating Reactions and Explanations for LLM-Based Misinformation Detectioncited by 41
  9. 2023Disentangled Representation Learning with Large Language Models for Text-Attributed Graphscited by 36
  10. 2024VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Contextcited by 29
  11. 2023GRENADE: Graph-Centric Language Model for Self-Supervised Representation Learning on Text-Attributed Graphscited by 28
  12. 2023TempTabQA: Temporal Question Answering for Semi-Structured Tablescited by 27
  13. 2023TRIGO: Benchmarking Formal Mathematical Proof Reduction for Generative Language Modelscited by 24
  14. 2023Pretraining Language Models with Text-Attributed Heterogeneous Graphscited by 15
  15. 2024FREB-TQA: A Fine-Grained Robustness Evaluation Benchmark for Table Question Answeringcited by 14
  16. 2023Symbolic Planning and Code Generation for Grounded Dialoguecited by 5
  17. 2023Deductive Additivity for Planning of Natural Language Proofscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 12; 2025: 23; 2026: 11.

46 papers.

Sort:

By area:

  1. 2025From System 1 to System 2: A Survey of Reasoning Large Language Modelscited by 319
  2. 2024Multi-Step Reasoning with Large Language Models, a Surveycited by 140
  3. 2024GEM: A Generalizable Ego-Vision Multimodal World Model for Fine-Grained Ego-Motion, Object Dynamics, and Scene Composition Controlcited by 76
  4. 2025UniGraph2: Learning a Unified Embedding Space to Bind Multimodal Graphscited by 47
  5. 2025Is Chain-of-Thought Reasoning of LLMs a Mirage? A Data Distribution Lenscited by 42
  6. 2024Content Moderation by LLM: From Accuracy to Legitimacycited by 30
  7. 2024Model Swarms: Collaborative Search to Adapt LLM Experts via Swarm Intelligencecited by 27
  8. 2024Transformers Struggle to Learn to Searchcited by 19
  9. 2025HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challengescited by 19
  10. 2025GraphEval: A Lightweight Graph-Based LLM Framework for Idea Evaluationcited by 17
  11. 2025GRAVER: Generative Graph Vocabularies for Robust Graph Foundation Models Fine-tuningcited by 13
  12. 2024GCoder: Improving Large Language Model for Generalized Graph Problem Solvingcited by 11
34 more
  1. 2025Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigationcited by 11
  2. 2025Rewarding Graph Reasoning Process makes LLMs more Generalized Reasonerscited by 10
  3. 2024Varying Shades of Wrong: Aligning LLMs with Wrong Answers Onlycited by 9
  4. 2025GraphThought: Graph Combinatorial Optimization with Thought Generationcited by 9
  5. 2024Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimizationcited by 8
  6. 2025Model Generalization on Text Attribute Graphs: Principles with Large Language Modelscited by 8
  7. 2025A Tool for In-depth Analysis of Code Execution Reasoning of Large Language Modelscited by 6
  8. 2025Experience-Evolving Multi-Turn Tool-Use Agent with Hybrid Episodic-Procedural Memorycited by 6
  9. 2026MultiDocFusion: Hierarchical and Multimodal Chunking Pipeline for Enhanced RAG on Long Industrial Documentscited by 6
  10. 2025Can GRPO Help LLMs Transcend Their Pretraining Origin?cited by 5
  11. 2025Large Language Models Meet Text-Attributed Graphs: A Survey of Integration Frameworks and Applicationscited by 5
  12. 2025GraphChain: Large Language Models for Large-scale Graph Analysis via Tool Chainingcited by 5
  13. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  14. 2025Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignmentcited by 3
  15. 2024Do LLMs Have the Generalization Ability in Conducting Causal Inference?cited by 2
  16. 2024Neuron-Level Differentiation of Memorization and Generalization in Large Language Modelscited by 2
  17. 2026Evaluating Relational Reasoning in LLMs with RELcited by 2
  18. 2024Synergizing LLMs and Knowledge Graphs: A Novel Approach to Software Repository-Related Question Answeringcited by 1
  19. 2025From Test-taking to Cognitive Scaffolding: A Pedagogical Diagnostic Benchmark for LLMs on English Standardized Testscited by 1
  20. 2025Improving LLMs' Generalized Reasoning Abilities by Graph Problemscited by 1
  21. 2026Can Large Language Models Generalize Procedures Across Representations?cited by 1
  22. 2026Aligning LLMs with Graph Neural Solvers for Combinatorial Optimizationcited by 1
  23. 2024A Decade of Deep Learning: A Survey on The Magnificent Sevencited by 0
  24. 2025Transformers Can Learn Connectivity in Some Graphs but Not Otherscited by 0
  25. 2025CGoT: A Novel Inference Mechanism for Embodied Multi-Agent Systems Using Composable Graphs of Thoughtscited by 0
  26. 2025Building Specialized Software-Assistant ChatBot with Graph-Based Retrieval-Augmented Generationcited by 0
  27. 2025Factors That Support Grounded Responses in LLM Conversations: A Rapid Reviewcited by 0
  28. 2026Out-of-Distribution Generalization in Graph Foundation Modelscited by 0
  29. 2026BLEG: LLM Functions as Powerful fMRI Graph-Enhancer for Brain Network Analysiscited by 0
  30. 2026Generalization in LLM Problem Solving: The Case of the Shortest Pathcited by 0
  31. 2026M3DocDep: Multi-modal, Multi-page, Multi-document Dependency Chunking with Large Vision-Language Modelscited by 0
  32. 2026The Sword, Shield, and Achilles' Heel: Characterizing the Linguistic Inductive Bias of Large Language Models for Spatial Reasoning in Navigation Planningcited by 0
  33. 2026Are Large Language Models Suitable for Graph Computation? Progress and Prospectscited by 0
  34. 2026RFCLLM: Evaluating LLMs' Reasoning Ability of Network Protocol State Machinescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Less is More: Learning Graph Tasks with Just LLMs
  2. 2025Rethinking and Benchmarking Large Language Models for Graph Reasoning
  3. 2024Can LLMs perform structured graph reasoning?
  4. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Model
  5. 2025G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning
  6. 2026Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models
  7. 2025Learn to Think: Bootstrapping LLM Reasoning Capability Through Graph Representation Learning
  8. 2023Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis