Rewarding Graph Reasoning Process makes LLMs more Generalized Reasoners

• URL: http://arxiv.org/abs/2503.00845v1
• Date: Sun, 02 Mar 2025 10:39:40 GMT
• Title: Rewarding Graph Reasoning Process makes LLMs more Generalized Reasoners
• Authors: Miao Peng, Nuo Chen, Zongrui Suo, Jia Li,
• Abstract summary: Process Reward Models (PRMs) have demonstrated exceptional promise in enhancing reasoning by providing step-wise feedback.<n>We introduce GraphSILO, the largest dataset for graph reasoning problems with fine-grained step-wise labels.<n>We train GraphPRM, the first PRM designed for graph reasoning problems, and evaluate its effectiveness in two key settings.
• Score: 30.195361623027313
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: 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.

Related papers

• Exploring the Potential of Large Language Models as Predictors in Dynamic Text-Attributed Graphs [23.655368505970443]
  We pioneer using large language models (LLMs) for predictive tasks on dynamic graphs. We propose the GraphAgent-Dynamic (GAD) Framework, a multi-agent system that leverages collaborative LLMs. GAD incorporates global and local summary agents to generate domain-specific knowledge, enhancing its transferability across domains.
  arXiv  Detail & Related papers  (2025-03-05T08:28:11Z)
• Graph-Augmented Reasoning: Evolving Step-by-Step Knowledge Graph Retrieval for LLM Reasoning [55.6623318085391]
  Recent large language model (LLM) reasoning suffers from limited domain knowledge, susceptibility to hallucinations, and constrained reasoning depth.<n>This paper presents the first investigation into integrating step-wise knowledge graph retrieval with step-wise reasoning.<n>We propose KG-RAR, a framework centered on process-oriented knowledge graph construction, a hierarchical retrieval strategy, and a universal post-retrieval processing and reward model.
  arXiv  Detail & Related papers  (2025-03-03T15:20:41Z)
• Exploring Graph Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation [26.19182768810174]
  Graph-structured data has become increasingly prevalent across various domains, raising the demand for effective models to handle graph tasks.<n>Traditional graph learning models like Graph Neural Networks (GNNs) have made significant strides, but their capabilities in handling graph data remain limited in certain contexts.<n>In recent years, large language models (LLMs) have emerged as promising candidates for graph tasks, yet most studies focus primarily on performance benchmarks.
  arXiv  Detail & Related papers  (2025-02-26T03:03:46Z)
• Reasoning with Graphs: Structuring Implicit Knowledge to Enhance LLMs Reasoning [73.2950349728376]
  Large language models (LLMs) have demonstrated remarkable success across a wide range of tasks.<n>However, they still encounter challenges in reasoning tasks that require understanding and inferring relationships between pieces of information.<n>This challenge is particularly pronounced in tasks involving multi-step processes, such as logical reasoning and multi-hop question answering.<n>We propose Reasoning with Graphs (RwG) by first constructing explicit graphs from the context.
  arXiv  Detail & Related papers  (2025-01-14T05:18:20Z)
• Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents [27.4884498301785]
  We introduce GraphAgent-Reasoner, a fine-tuning-free framework for explicit and precise graph reasoning. Inspired by distributed graph computation theory, our framework decomposes graph problems into smaller, node-centric tasks that are distributed among multiple agents. Our framework demonstrates the capability to handle real-world graph reasoning applications such as webpage importance analysis.
  arXiv  Detail & Related papers  (2024-10-07T15:34:14Z)
• How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension [53.6373473053431]
  This work introduces a benchmark to assess large language models' capabilities in graph pattern tasks. We have developed a benchmark that evaluates whether LLMs can understand graph patterns based on either terminological or topological descriptions. Our benchmark encompasses both synthetic and real datasets, and a variety of models, with a total of 11 tasks and 7 models.
  arXiv  Detail & Related papers  (2024-10-04T04:48:33Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• MindStar: Enhancing Math Reasoning in Pre-trained LLMs at Inference Time [51.5039731721706]
  MindStar is a purely inference-based searching method for large language models. It formulates reasoning tasks as searching problems and proposes two search ideas to identify the optimal reasoning paths. It significantly enhances the reasoning abilities of open-source models, such as Llama-2-13B and Mistral-7B, and achieves comparable performance to GPT-3.5 and Grok-1.
  arXiv  Detail & Related papers  (2024-05-25T15:07:33Z)
• Exploring the Potential of Large Language Models in Graph Generation [51.046188600990014]
  Graph generation requires large language models (LLMs) to generate graphs with given properties. This paper explores the abilities of LLMs for graph generation with systematical task designs and experiments. Our evaluations demonstrate that LLMs, particularly GPT-4, exhibit preliminary abilities in graph generation tasks.
  arXiv  Detail & Related papers  (2024-03-21T12:37:54Z)
• Can Graph Descriptive Order Affect Solving Graph Problems with LLMs? [38.1577036285387]
  Large language models (LLMs) have achieved significant success in reasoning tasks, including mathematical reasoning and logical deduction. Previous studies have explored LLMs' graph reasoning abilities through various techniques. A critical factor has been mostly overlooked: the prompt sequential order in which graph descriptions are presented to the models.
  arXiv  Detail & Related papers  (2024-02-11T09:46:24Z)
• GraphReason: Enhancing Reasoning Capabilities of Large Language Models through A Graph-Based Verification Approach [0.0]
  Large Language Models (LLMs) have showcased impressive reasoning capabilities. In this paper, we introduce a novel graph-based method to further augment the reasoning capabilities of LLMs.
  arXiv  Detail & Related papers  (2023-08-18T03:12:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.