# G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning

arXiv: https://arxiv.org/abs/2505.18499 · HTML: https://mlsanity.com/paper/2505.18499/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 20 of its 57 references that are in the map.
- First posted on arXiv 24 May 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement](https://mlsanity.com/paper/2409.12122/) (2024)
- [SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training](https://mlsanity.com/paper/2501.17161/) (2025)
- [Scaling Relationship on Learning Mathematical Reasoning with Large Language Models](https://mlsanity.com/paper/2308.01825/) (2023)
- [When More is Less: Understanding Chain-of-Thought Length in LLMs](https://mlsanity.com/paper/2502.07266/) (2025)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets](https://mlsanity.com/paper/2406.16176/) (2024)
- [Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation](https://mlsanity.com/paper/2502.18771/) (2025)
- [GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic Tasks](https://mlsanity.com/paper/2504.12764/) (2025)

## Built on by (most cited first, 14 of 14)

- [A Survey of Context Engineering for Large Language Models](https://mlsanity.com/paper/2507.13334/) (2025)
- [Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners](https://mlsanity.com/paper/2511.10234/) (2025)
- [Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective](https://mlsanity.com/paper/2509.22613/) (2025)
- [GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning](https://mlsanity.com/paper/2603.01410/) (2026)
- [Finding and Reactivating Post-Trained LLMs' Hidden Safety Mechanisms](https://mlsanity.com/paper/2604.00012/) (2026)
- [Self-Exploring Language Models for Explainable Link Forecasting on Temporal Graphs via Reinforcement Learning](https://mlsanity.com/paper/2509.00975/) (2025)
- [Can RL Teach Long-Horizon Reasoning to LLMs? Expressiveness Is Key](https://mlsanity.com/paper/2605.06638/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)
- [Learning to Approximate Uniform Facility Location via Graph Neural Networks](https://mlsanity.com/paper/2602.13155/) (2026)
- [ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning](https://mlsanity.com/paper/2608.18242/) (2026)
- [GRAIN: Bridging Name and Narrative Shifts in Real-World Graph Reasoning through Invariance-Rewarded Agentic RL](https://mlsanity.com/paper/2608.27142/) (2026)
- [Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMs](https://mlsanity.com/paper/2608.30437/) (2026)
- [ZeroGAR: Benchmarking the Adversarial Robustness of Zero-Shot Graph Models](https://mlsanity.com/paper/2609.33314/) (2026)
- [GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics](https://mlsanity.com/paper/2609.38798/) (2026)

## Abstract (arXiv)

Although Large Language Models (LLMs) have demonstrated remarkable progress, their proficiency in graph-related tasks remains notably limited, hindering the development of truly general-purpose models. Previous attempts, including pretraining graph foundation models or employing supervised fine-tuning, often face challenges such as the scarcity of large-scale, universally represented graph data. We introduce G1, a simple yet effective approach demonstrating that Reinforcement Learning (RL) on synthetic graph-theoretic tasks can significantly scale LLMs' graph reasoning abilities. To enable RL training, we curate Erd~os, the largest graph reasoning dataset to date comprising 50 diverse graph-theoretic tasks of varying difficulty levels, 100k training data and 5k test data, all drived from real-world graphs. With RL on Erd~os, G1 obtains substantial improvements in graph reasoning, where our finetuned 3B model even outperforms Qwen2.5-72B-Instruct (24x size). RL-trained models also show strong zero-shot generalization to unseen tasks, domains, and graph encoding schemes, including other graph-theoretic benchmarks as well as real-world node classification and link prediction tasks, without compromising general reasoning abilities. Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph-theoretic tasks, which combines the strengths of pretrained LLM capabilities with abundant, automatically generated synthetic data, suggesting that LLMs possess graph understanding abilities that RL can elicit successfully. Our implementation is open-sourced at https://github.com/PKU-ML/G1, with models and datasets hosted on Hugging Face collections https://huggingface.co/collections/PKU-ML/g1-683d659e992794fc99618cf2 for broader accessibility.