# NPG-Muse: Scaling Long Chain-of-Thought Reasoning with NP-Hard Graph Problems

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 21 of its 48 references that are in the map.
- First posted on arXiv 28 Aug 2025.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [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)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Scaling Relationship on Learning Mathematical Reasoning with Large Language Models](https://mlsanity.com/paper/2308.01825/) (2023)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs](https://mlsanity.com/paper/2503.01307/) (2025)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [Evaluating the Performance of Large Language Models on GAOKAO Benchmark](https://mlsanity.com/paper/2305.12474/) (2023)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Models](https://mlsanity.com/paper/2508.02120/) (2025)
- [GraphWiz: An Instruction-Following Language Model for Graph Problems](https://mlsanity.com/paper/2402.16029/) (2024)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)

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

- [Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems](https://mlsanity.com/paper/2602.06319/) (2026)
- [Call Neighbours Yourself: Graph Walks with Destination-Conditioned On-Policy Self-Distillation](https://mlsanity.com/paper/2608.29588/) (2026)
- [Structured In-context Environment Scaling for Large Language Model Reasoning](https://mlsanity.com/paper/2509.23330/) (2025)
- [Are Large Language Models Suitable for Graph Computation? Progress and Prospects](https://mlsanity.com/paper/2606.06865/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

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 the 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. The resulting NPG-Muse-series models exhibit substantially enhanced Long CoT reasoning capabilities, achieving consistent gains across mathematics, coding, logical, and graph reasoning benchmarks. NPG-Muse-7B even 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 LLM post-training. Our implementation is available at https://github.com/littlewyy/NPG-Muse.