Elamur Research⌕
☰
home / papers / 2026 / Generalization in Graph Reasoning: A Systematic Comparison of LLM Training Approaches

Generalization in Graph Reasoning: A Systematic Comparison of LLM Training Approaches

Paper · 2026 · Sola Shirai, Kavitha Srinivas, Julian Dolby et al.

Summary

The paper asks which training strategy actually helps LLMs reason over graphs in a way that transfers beyond the training setting. The IBM authors built a controlled benchmark of eight GraphQA-inspired tasks. Answer distributions are balanced so that the random-chance baseline is known exactly. Graphs use integer node IDs, incidence-list edges and randomly assigned word labels. Models are trained on four tasks and then tested on four related but unseen tasks. Testing also covers larger graphs (up to 140 nodes) and new shapes such as trees, cycles and edge-labeled graphs.

Using mainly Phi-4-mini, they compare:

  • Graph Tokens and Graph Tokens + Text,
  • SFT with LoRA,
  • P-Tuning,
  • GRPO (with DAPO) under two reward variants.

Main results:

  • Graph-encoder fusion breaks down out of distribution.
  • SFT with programmatically generated reasoning traces and prompt tuning generalize most reliably to new structures.
  • RL is inconsistent and highly sensitive to small reward changes.
  • No method wins on every dimension, and the picture holds for the larger Phi-4.

This matters because it tempers claims that RL or multimodal graph encoders solve LLM graph reasoning. It also shows that comparing against chance is essential.

Key points

  • Task split: Training uses Node Count, Node Degree, and DFS/BFS reachability. Generalization testing uses Edge Existence, Edge Count, Cycle Check and Shortest Path, with no further training.
  • Graph Tokens collapse: They often fall below random chance on unseen sizes or shapes. For example, on cycle graphs they score .293 BFS accuracy versus a .500 baseline, while SFT reaches .834.
  • Long paths on cycle graphs: The base model drops to chance at roughly 40–50 nodes. SFT keeps performance above chance up to about 100 nodes.
  • RL fragility on Phi-4: GRPO-S gains were mostly negative, largely because the model kept generating steps without answering within the output limit. GRPO-A gave at best no improvement on OOD tasks.
  • Scope and benchmark critique:
    • Experiments were limited to models trainable on 80GB GPUs, from Phi-4-mini (4B) up to Qwen3 32B.
    • The authors note that GraphWiz's reported zero-shot transfer was actually at chance level.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🔬IBM Research - Thomas J. Watson Research CenterYorktown Heights · United States53 works · 49,193 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,320 worksReasoning · 1,426 works

Cite

Cite as Sola Shirai, Kavitha Srinivas, Julian Dolby, Michael Katz, Shirin Sohrabi and Horst Samulowitz. 2026. Generalization in Graph Reasoning: A Systematic Comparison of LLM Training Approaches. Proceedings of the First Workshop on Structured Understanding, Retrieval, and Generation in the LLM Era (SURGeLLM 2026).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.surgellm-1.18

@inproceedings{shirai2026generalization,
  title = {{Generalization in Graph Reasoning: A Systematic Comparison of LLM Training Approaches}},
  author = {Sola Shirai, Kavitha Srinivas, Julian Dolby, Michael Katz, Shirin Sohrabi and Horst Samulowitz},
  booktitle = {Proceedings of the First Workshop on Structured Understanding, Retrieval, and Generation in the LLM Era (SURGeLLM 2026)},
  year = {2026},
  doi = {10.18653/v1/2026.surgellm-1.18},
  url = {https://doi.org/10.18653/v1/2026.surgellm-1.18}
}

References

37 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. 2024. How far can transformers reason? the globality barrier and inductive scratchpad. In Advances in Neural Information Processing Systems, volume 37, pages 27850–27895. Curran Associates, Inc. find
  2. Abdelrahman Abouelenin, Atabak Ashfaq, Adam Atkinson, Hany Awadalla, Nguyen Bach, Jianmin Bao, Alon Benhaim, Martin Cai, Vishrav Chaudhary, Congcong Chen, et al. 2025. Phi-4-mini technical report: Compact yet powerful multimodal language models via mixture-of-loras. arXiv preprint arXiv:2503.01743.
  3. Simon A Aytes, Jinheon Baek, and Sung Ju Hwang. 2025. Sketch-of-thought: Efficient llm reasoning with adaptive cognitive-inspired sketching. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 24307– 24331.
  4. Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. Science, 286(5439):509–512. find
  5. Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. 2003. Directed scale-free graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, page 132–139, USA. Society for Industrial and Applied Mathematics. find
  6. Runjin Chen, Tong Zhao, Ajay Jaiswal, Neil Shah, and Zhangyang Wang. 2024b. Llaga: large language and graph assistant. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org. find
  7. Zhaoling Chen, Robert Tang, Gangda Deng, Fang Wu, Jialong Wu, Zhiwei Jiang, Viktor Prasanna, Arman Cohan, and Xingyao Wang. 2025. Locagent: Graph-guided llm agents for code localization. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers…
  8. Xinnan Dai, Qihao Wen, Yifei Shen, Hongzhi Wen, Dongsheng Li, Jiliang Tang, and Caihua Shan. 2024. Revisiting the graph reasoning ability of large language models: Case studies in translation, connectivity and shortest path. arXiv preprint arXiv:2408.09529. — [arXiv:2408.09529](https://arxiv.org/abs/2408.09529) find
  9. Mohnish Dubey, Debayan Banerjee, Abdelrahman Abdelkawi, and Jens Lehmann. 2019. Lc-quad 2.0: A large dataset for complex question answering over wikidata and dbpedia. In International semantic web conference, pages 69–78. Springer. find
  10. Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan Larson. 2024. From local to global: A graph rag approach to query-focused summarization. ArXiv, abs/2404.16130. find
  11. P. Erdös and A. Rényi. 1959. On random graphs i. Publicationes Mathematicae Debrecen, 6:290. find
  12. Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. 2024. Talk like a graph: Encoding graphs for large language models. In International conference on learning representations, volume 2024, pages 43909– 43934. find
  13. Xiaojun Guo, Ang Li, Yifei Wang, Stefanie Jegelka, and Yisen Wang. 2025. G1: Teaching llms to reason on graphs with reinforcement learning. arXiv preprint arXiv:2505.18499. — [arXiv:2505.18499](https://arxiv.org/abs/2505.18499) find
  14. Zirui Guo, Lianghao Xia, Yanhua Yu, Yuling Wang, Kangkang Lu, Zhiyong Huang, and Chao Huang. 2024. Graphedit: Large language models for graph structure learning. arXiv preprint arXiv:2402.15183. — [arXiv:2402.15183](https://arxiv.org/abs/2402.15183) find
  15. Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiang Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. 2025. Graphllm: Boosting graph reasoning ability of large language model. IEEE Transactions on Big Data. find
  16. Nuo Chen, Yuhan Li, Jianheng Tang, and Jia Li. 2024a. Graphwiz: An instruction-following language model for graph computational problems. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, page 353–364, New York, NY, USA. Association for Computing Machi… find
  17. Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. 1983. Stochastic blockmodels: First steps. Social Networks, 5(2):109–137. find
  18. Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, and Weizhu Chen. 2021. Lora: Low-rank adaptation of large language models. CoRR, abs/2106.09685.
  19. Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. 2022. Lora: Low-rank adaptation of large language models. ICLR, 1(2):3.
  20. Yixin Ji, Kaixin Wu, Juntao Li, Wei Chen, Mingjie Zhong, Xu Jia, and Min Zhang. 2024. Retrieval and reasoning on KGs: Integrate knowledge graphs into large language models for complex question answering. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 7598–7610, Miami… find
  21. Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. 2024. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’24, page 491–500,… find
  22. Lecheng Kong, Jiarui Feng, Hao Liu, Chengsong Huang, Jiaxin Huang, Yixin Chen, and Muhan Zhang. 2024. Gofa: A generative one-for-all model for joint graph language modeling. arXiv preprint arXiv:2407.09709. — [arXiv:2407.09709](https://arxiv.org/abs/2407.09709) find
  23. Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. 2023. Can language models solve graph problems in natural language? Advances in Neural Information Processing Systems, 36:30840–30861. find
  24. Chang Liu and Bo Wu. 2023. Evaluating large language models on graphs: Performance insights and comparative analysis. arXiv preprint arXiv:2308.11224. — [arXiv:2308.11224](https://arxiv.org/abs/2308.11224) find
  25. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837.
  26. Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Tam, Zhengxiao Du, Zhilin Yang, and Jie Tang. 2022. P-tuning: Prompt tuning can be comparable to fine-tuning across scales and tasks. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 61–6…
  27. Xiao Liu, Yanan Zheng, Zhengxiao Du, Ming Ding, Yujie Qian, Zhilin Yang, and Jie Tang. 2024. Gpt understands, too. AI Open, 5:208–215. find
  28. Miao Peng, Nuo Chen, Zongrui Suo, and Jia Li. 2025. Rewarding graph reasoning process makes llms more generalized reasoners. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, KDD ’25, page 2257–2268, New York, NY, USA. Association for Computing Machinery. find
  29. Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. 2024. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.05862. — [arXiv:2402.05862](https://arxiv.org/abs/2402.05862) find
  30. Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. 2024. Understanding transformer reasoning capabilities via graph algorithms. Advances in Neural Information Processing Systems, 37:78320–78370. find
  31. Abulhair Saparov and He He. 2023. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. In The Eleventh International Conference on Learning Representations.
  32. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. 2024. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300.
  33. Hao Xu, Xiangru Jian, Xinjian Zhao, Wei Pang, Chao Zhang, Suyuchen Wang, Qixin Zhang, Zhengyuan Dong, Joao Monteiro, Bang Liu, et al. 2025. Graphomni: A comprehensive and extendable benchmark framework for large language models on graph-theoretic tasks. arXiv preprint arXiv:2504.12764. — [arXiv:2504.12764](https://arxiv.org/abs/2504.12764) find
  34. Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. 2024. Language is all a graph needs. In Findings of the Association for Computational Linguistics: EACL 2024, pages 1955–1973, St. Julian’s, Malta. Association for Computational Linguistics. find
  35. Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, YuYue, Weinan Dai, Tiantian Fan, Gaohong Liu, Juncai Liu, LingJun Liu, Xin Liu, Haibin Lin, Zhiqi Lin, Bole Ma, Guangming Sheng, Yuxuan Tong, Chi Zhang, Mofan Zhang, Ru Zhang, Wang Zhang, Hang Zhu, Jinhua Zhu, Jiaze Chen, Jiangjie Chen,… — DAPO: An Open-Source LLM Reinforcement Learning System at Scale
  36. Yizhuo Zhang, Heng Wang, Shangbin Feng, Zhaoxuan Tan, Xiaochuang Han, Tianxing He, and Yulia Tsvetkov. 2024. Can LLM graph reasoning generalize beyond pattern memorization? In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 2289–2305, Miami, Florida, USA. Association for… find
  37. Xi Zhu, Haochen Xue, Ziwei Zhao, Wujiang Xu, Jingyuan Huang, Minghao Guo, Qifan Wang, Kaixiong Zhou, Imran Razzak, and Yongfeng Zhang. 2025. Llm as gnn: Graph vocabulary learning for text-attributed graph foundation models. arXiv preprint arXiv:2503.03313. — [arXiv:2503.03313](https://arxiv.org/abs/2503.03313) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shirai-2026-generalization-graph-reasoning-systematic-comparison/