Research map / Large language models / Instruction and fine-tuning

$\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning

NeurIPS 2025 · Large language models › Instruction and fine-tuning · approach: Fine-tuning for reasoning data · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Applies GRPO reinforcement learning with rule-based rewards to Qwen2.5-Instruct models on 50 synthetic graph-theoretic tasks (ERDOS, 100k train), showing gains in graph reasoning that transfer to other graph benchmarks and general math.

Problem

LLMs perform poorly on graph reasoning tasks, and prior approaches (graph foundation model pretraining, instruction or preference tuning on graph data) suffer from scarce large-scale graph data and poor generalization.

Approach

Use verifiable rule-based rewards (value match, Jaccard index, algorithmic verifiers) on a large set of synthetic graph-theoretic tasks generated from real-world subgraphs, training LLMs with GRPO, optionally after a short rejection-sampling CoT SFT warm-up.

Key results

• G1-3B reaches 59.76% average accuracy on ERDOS vs 22.72% for Qwen2.5-3B-Instruct and 47.16% for Qwen2.5-72B-Instruct.
• G1-7B reaches 66.16% average on ERDOS, close to o3-mini (64.90%), and 57.11% on GraphWiz versus 51.86% for DeepSeek-R1-Distill-Qwen-7B.
• G1-Zero-32B improves ERDOS average from 47.10% to 75.06% and MATH from 76.80% to 80.80%.

Measured effects reported in the paper

Surprising findings

• Direct-SFT on answers alone is a surprisingly strong baseline, outperforming larger open models on ERDOS, though it gives no gain from 3B to 7B.
• RL directly from the base model (G1-Zero-3B) achieves strong performance without any SFT warm-up, though SFT warm-up helps on the hardest tasks.

Limitations

• GRPO is sample-inefficient and needs extensive rollouts on hard NP-hard tasks; dynamic difficulty scheduling is suggested.
• Context window limits prevent evaluation on graphs with thousands of nodes.
• Generalization to domain-specific applications (e.g., molecular property prediction) and other structured data (tabular, time-series) is untested.

Experimental setup

Datasets: ERDOS (synthetic graph-theoretic tasks from real-world Network Repository subgraphs) GraphWiz GraphArena Cora PubMed GSM8K MATH500 MMLU-Pro

Benchmarks: ERDOS GraphWiz GraphArena Cora node classification PubMed node classification Cora link prediction PubMed link prediction GSM8K MATH500 MMLU-Pro

Metrics: accuracy Jaccard-based reward/accuracy standard deviation over seeds

Baselines: GPT-4o-mini OpenAI o3-mini Qwen2.5-72B-Instruct Llama-3.1-70B-Instruct DeepSeek-R1-Distill-Qwen-7B GraphWiz-7B-RFT GraphWiz-7B-DPO Direct-SFT CoT-SFT GPT-4o

Builds on: GRPO DeepSeek-R1 Qwen2.5-Instruct NetworkX vLLM

Closest papers by meaning

• Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.90)
• RL Squeezes, SFT Expands: A Comparative Study of Reasoning LLMs (ICLR 2026 · similarity 0.90)
• General-Reasoner: Advancing LLM Reasoning Across All Domains (NeurIPS 2025 · similarity 0.89)
• Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Properties (NeurIPS 2025 · similarity 0.89)
• Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models (ICML 2025 · similarity 0.89)
• RL of Thoughts: Navigating LLM Reasoning with Inference-time Reinforcement Learning (ICLR 2026 · similarity 0.89)