# Rewarding Graph Reasoning Process makes LLMs more Generalized Reasoners

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

## Key facts

- Cited by 10 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 34 of its 61 references that are in the map.
- First posted on arXiv 2 Mar 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM alignment / RLHF / preference optimisation / [Process reward models for reasoning](https://mlsanity.com/alignment/process-reward-models-for-reasoning/)

## Builds on (most cited first, 30 of 34)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Are NLP Models really able to Solve Simple Math Word Problems?](https://mlsanity.com/paper/2103.07191/) (2021)
- [WizardMath: Empowering Mathematical Reasoning for Large Language Models via Reinforced Evol-Instruct](https://mlsanity.com/paper/2308.09583/) (2023)
- [MAmmoTH: Building Math Generalist Models through Hybrid Instruction Tuning](https://mlsanity.com/paper/2309.05653/) (2023)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [Fine-Grained Human Feedback Gives Better Rewards for Language Model Training](https://mlsanity.com/paper/2306.01693/) (2023)
- [ProcessBench: Identifying Process Errors in Mathematical Reasoning](https://mlsanity.com/paper/2412.06559/) (2024)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [MathPrompter: Mathematical Reasoning using Large Language Models](https://mlsanity.com/paper/2303.05398/) (2023)
- [Making Large Language Models Better Reasoners with Step-Aware Verifier](https://mlsanity.com/paper/2206.02336/) (2022)
- [GraphGPT: Graph Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2310.13023/) (2023)
- [OVM, Outcome-supervised Value Models for Planning in Mathematical Reasoning](https://mlsanity.com/paper/2311.09724/) (2023)
- [ZeroG: Investigating Cross-dataset Zero-shot Transferability in Graphs](https://mlsanity.com/paper/2402.11235/) (2024)
- [Breaking Language Barriers in Multilingual Mathematical Reasoning: Insights and Observations](https://mlsanity.com/paper/2310.20246/) (2023)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [Can LLM Graph Reasoning Generalize beyond Pattern Memorization?](https://mlsanity.com/paper/2406.15992/) (2024)
- [GLBench: A Comprehensive Benchmark for Graph with Large Language Models](https://mlsanity.com/paper/2407.07457/) (2024)
- [G-Refer: Graph Retrieval-Augmented Large Language Model for Explainable Recommendation](https://mlsanity.com/paper/2502.12586/) (2025)
- [GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2407.02936/) (2024)
- [Pre-trained Language Model with Prompts for Temporal Knowledge Graph Completion](https://mlsanity.com/paper/2305.07912/) (2023)

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

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Can Knowledge-Graph-based Retrieval Augmented Generation Really Retrieve What You Need?](https://mlsanity.com/paper/2510.16582/) (2025)
- [From Sequence to Structure: Uncovering Substructure Reasoning in Transformers](https://mlsanity.com/paper/2507.10435/) (2025)
- [Incentivizing In-depth Reasoning over Long Contexts with Process Advantage Shaping](https://mlsanity.com/paper/2601.12465/) (2026)
- [See or Say Graphs: Agent-Driven Scalable Graph Structure Understanding with Vision-Language Models](https://mlsanity.com/paper/2510.16769/) (2025)
- [Improving LLMs' Generalized Reasoning Abilities by Graph Problems](https://mlsanity.com/paper/2507.17168/) (2025)
- [From Static to Dynamic: Adaptive Monte Carlo Search for Mathematical Process Supervision](https://mlsanity.com/paper/2509.24351/) (2025)
- [Let the Agent Search: Autonomous Exploration Beats Rigid Workflows in Temporal Question Answering](https://mlsanity.com/paper/2603.01853/) (2026)
- [Knowledge-to-Verification: Exploring RLVR for LLMs in Knowledge-Intensive Domains](https://mlsanity.com/paper/2605.18261/) (2026)
- [Are Large Language Models Suitable for Graph Computation? Progress and Prospects](https://mlsanity.com/paper/2606.06865/) (2026)

## Abstract (arXiv)

Despite significant advancements in Large Language Models (LLMs), developing advanced reasoning capabilities in LLMs remains a key challenge. Process Reward Models (PRMs) have demonstrated exceptional promise in enhancing reasoning by providing step-wise feedback, particularly in the context of mathematical reasoning. However, their application to broader reasoning domains remains understudied, largely due to the high costs associated with manually creating step-level supervision. In this work, we explore the potential of PRMs in graph reasoning problems - a domain that demands sophisticated multi-step reasoning and offers opportunities for automated step-level data generation using established graph algorithms. We introduce GraphSILO, the largest dataset for graph reasoning problems with fine-grained step-wise labels, built using automated Task-oriented Trajectories and Monte Carlo Tree Search (MCTS) to generate detailed reasoning steps with step-wise labels. Building upon this dataset, we train GraphPRM, the first PRM designed for graph reasoning problems, and evaluate its effectiveness in two key settings: inference-time scaling and reinforcement learning via Direct Preference Optimization (DPO). Experimental results show that GraphPRM significantly improves LLM performance across 13 graph reasoning tasks, delivering a 9% gain for Qwen2.5-7B and demonstrating transferability to new graph reasoning datasets and new reasoning domains like mathematical problem-solving. Notably, GraphPRM enhances LLM performance on GSM8K and Math500, underscoring the cross-domain applicability of graph-based reasoning rewards. Our findings highlight the potential of PRMs in advancing reasoning across diverse domains, paving the way for more versatile and effective LLMs.