Graph-R1: Unleashing LLM Reasoning with NP-Hard Graph Problems

📄 arXiv: 2508.20373v1 📥 PDF

作者: Yuyao Wang, Bowen Liu, Jianheng Tang, Nuo Chen, Yuhan Li, Qifan Zhang, Jia Li

分类: cs.CL, cs.AI, cs.LG

发布日期: 2025-08-28

🔗 代码/项目: GITHUB

💡 一句话要点

Graph-R1：利用NP-hard图问题提升LLM的推理能力

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 长链思维 NP-hard问题 图推理 强化学习

📋 核心要点

  1. 现有RLLM依赖于昂贵的人工标注数据集进行长链思维训练，缺乏可扩展性。
  2. 提出利用NP-hard图问题作为合成训练数据，其内在复杂性天然适合训练深度推理能力。
  3. Graph-R1模型在数学、编码等任务上表现出强大的泛化能力，并在NP-hard图问题上超越了QwQ-32B。

📝 摘要（中文）

推理大型语言模型(RLLMs)最近在复杂的推理任务上取得了显著进展，这主要归功于它们的长链思维(Long CoT)能力。然而，开发这些Long CoT行为在很大程度上依赖于使用高质量数据集进行后训练，这些数据集通常成本高昂且由人工策划(例如，数学和代码)，使得可扩展的替代方案未被探索。在这项工作中，我们引入NP-hard (NPH)图问题作为一种新的合成训练语料库，因为它们本质上需要深度推理、广泛探索和反思策略，这些都是Long CoT推理的核心特征。在此基础上，我们开发了一个两阶段的后训练框架：(i)在拒绝采样的NPH图实例上进行Long CoT监督微调(SFT)，这大大提高了推理深度，以及(ii)使用细粒度奖励设计的强化学习(RL)，这提高了推理效率。我们的旗舰模型Graph-R1-7B在数学、编码、STEM和逻辑方面表现出强大的泛化能力，并且在NPH图问题的准确性和推理效率方面都超过了QwQ-32B。这些结果表明，NPH图问题是推进LLM中Long CoT推理的一种有效且可扩展的资源，为LLM后训练开辟了一个新的领域。我们的实现可在https://github.com/Graph-Reasoner/Graph-R1获得，模型和数据集托管在我们的Hugging Face集合HKUST-DSAIL/Graph-R1中。

🔬 方法详解

问题定义：现有大型语言模型（LLM）的推理能力，特别是长链思维（Long CoT）能力，依赖于高质量但昂贵的人工标注数据集进行训练。这限制了模型的可扩展性和泛化能力。因此，需要一种更有效、更可扩展的方法来训练LLM的推理能力，尤其是在需要深度推理和探索的复杂问题上。

核心思路：论文的核心思路是利用NP-hard图问题作为一种新的合成训练语料库。NP-hard图问题具有内在的复杂性，需要深度推理、广泛探索和反思策略，这些都是Long CoT推理的关键特征。通过在这些问题上训练LLM，可以有效地提高其推理能力，而无需依赖大量人工标注数据。

技术框架：该论文提出了一个两阶段的后训练框架。第一阶段是Long CoT监督微调（SFT），在拒绝采样的NP-hard图实例上进行训练，以提高推理深度。第二阶段是强化学习（RL），使用细粒度的奖励设计，以提高推理效率。整体流程是先通过SFT提升推理能力，再通过RL优化推理效率。

关键创新：该论文最重要的技术创新点在于将NP-hard图问题引入作为LLM推理能力训练的合成数据。与传统的数学或代码数据集相比，NP-hard图问题更具挑战性，能够更好地激发LLM的深度推理能力。此外，两阶段的训练框架，即SFT和RL的结合，也能够有效地提高LLM的推理深度和效率。

关键设计：在SFT阶段，使用了拒绝采样来选择合适的NP-hard图实例，以确保训练数据的质量。在RL阶段，设计了细粒度的奖励函数，以鼓励LLM进行更有效的推理。具体的参数设置和网络结构细节在论文中没有详细描述，但可以推测使用了标准的Transformer架构，并针对NP-hard图问题进行了优化。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

Graph-R1-7B模型在NP-hard图问题上超越了QwQ-32B，证明了该方法的有效性。此外，Graph-R1在数学、编码、STEM和逻辑等多个领域都表现出强大的泛化能力，表明NP-hard图问题作为训练数据可以有效提升LLM的通用推理能力。具体的性能数据和提升幅度在论文中进行了详细的展示。

🎯 应用场景

该研究成果可应用于各种需要复杂推理和决策的领域，例如智能规划、资源优化、自动代码生成、以及科学发现等。通过提升LLM在NP-hard问题上的解决能力，可以推动人工智能在更广泛领域的应用，并为解决现实世界中的复杂问题提供新的思路。

📄 摘要（原文）

Reasoning Large Language Models (RLLMs) have recently achieved remarkable progress on complex reasoning tasks, largely enabled by their long chain-of-thought (Long CoT) capabilities. However, developing these Long CoT behaviors relies heavily on post-training with high-quality datasets, which are typically costly and human-curated (e.g., mathematics and code), leaving scalable alternatives unexplored. In this work, we introduce NP-hard (NPH) graph problems as a novel synthetic training corpus, as they inherently require deep reasoning, extensive exploration, and reflective strategies, which are core characteristics of Long CoT reasoning. Building on this insight, we develop a two-stage post-training framework: (i) Long CoT Supervised Fine-Tuning (SFT) on rejection-sampled NPH graph instances, which substantially enhances reasoning depth, and (ii) Reinforcement Learning (RL) with a fine-grained reward design, which sharpens reasoning efficiency. Our flagship model, Graph-R1-7B, demonstrates strong generalization across mathematics, coding, STEM, and logic, and surpasses QwQ-32B on NPH graph problems in both accuracy and reasoning efficiency. These results position NPH graph problems as an effective and scalable resource for advancing Long CoT reasoning in LLMs, opening a new frontier for LLM post-training. Our implementation is available at https://github.com/Graph-Reasoner/Graph-R1, with models and datasets hosted in our Hugging Face collection HKUST-DSAIL/Graph-R1.