# NP-Engine: Empowering Optimization Reasoning in Large Language Models with Verifiable Synthetic NP Problems

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 24 references that are in the map.
- First posted on arXiv 18 Oct 2025.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)

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

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [DeepMath-103K: A Large-Scale, Challenging, Decontaminated, and Verifiable Mathematical Dataset for Advancing Reasoning](https://mlsanity.com/paper/2504.11456/) (2025)
- [Logic-RL: Unleashing LLM Reasoning with Rule-Based Reinforcement Learning](https://mlsanity.com/paper/2502.14768/) (2025)
- [FrontierMath: A Benchmark for Evaluating Advanced Mathematical Reasoning in AI](https://mlsanity.com/paper/2411.04872/) (2024)
- [ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning](https://mlsanity.com/paper/2502.01100/) (2025)
- [Qwen2.5-1M Technical Report](https://mlsanity.com/paper/2501.15383/) (2025)
- [Seed1.5-Thinking: Advancing Superb Reasoning Models with Reinforcement Learning](https://mlsanity.com/paper/2504.13914/) (2025)
- [KodCode: A Diverse, Challenging, and Verifiable Synthetic Dataset for Coding](https://mlsanity.com/paper/2503.02951/) (2025)
- [Big-Math: A Large-Scale, High-Quality Math Dataset for Reinforcement Learning in Language Models](https://mlsanity.com/paper/2502.17387/) (2025)
- [KOR-Bench: Benchmarking Language Models on Knowledge-Orthogonal Reasoning Tasks](https://mlsanity.com/paper/2410.06526/) (2024)
- [Enigmata: Scaling Logical Reasoning in Large Language Models with Synthetic Verifiable Puzzles](https://mlsanity.com/paper/2505.19914/) (2025)
- [MetaSpatial: Reinforcing 3D Spatial Reasoning in VLMs for the Metaverse](https://mlsanity.com/paper/2503.18470/) (2025)
- [InternBootcamp: Boosting LLM Reasoning with Verifiable Task Scaling](https://mlsanity.com/paper/2508.08636/) (2025)
- [ICPC-Eval: Probing the Frontiers of LLM Reasoning with Competitive Programming Contests](https://mlsanity.com/paper/2506.04894/) (2025)
- [OPT-BENCH: Evaluating LLM Agent on Large-Scale Search Spaces Optimization Problems](https://mlsanity.com/paper/2506.10764/) (2025)
- [ReasoningWeekly: A General Knowledge and Verbal Reasoning Challenge for Large Language Models](https://mlsanity.com/paper/2502.01584/) (2025)
- [Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs](https://mlsanity.com/paper/2504.11239/) (2025)
- [Navigating the Labyrinth: Evaluating LLMs' Ability to Reason About Search Problems](https://mlsanity.com/paper/2406.12172/) (2024)

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

- [FrontierCS: Evolving Challenges for Evolving Intelligence](https://mlsanity.com/paper/2512.15699/) (2025)
- [What and When to Distill: Selective Hindsight Distillation for Multi-Turn Agents](https://mlsanity.com/paper/2605.19447/) (2026)
- [SPPO: Sequence-Level PPO for Long-Horizon Reasoning Tasks](https://mlsanity.com/paper/2604.08865/) (2026)
- [Beyond Mode Collapse: Distribution Matching for Diverse Reasoning](https://mlsanity.com/paper/2605.19461/) (2026)
- [OPT-Engine: Benchmarking the Limits of LLMs in Optimization Modeling via Complexity Scaling](https://mlsanity.com/paper/2601.19924/) (2026)
- [OPT-BENCH: Evaluating the Iterative Self-Optimization of LLM Agents in Large-Scale Search Spaces](https://mlsanity.com/paper/2605.08904/) (2026)
- [TL-GRPO: Turn-Level RL for Reasoning-Guided Iterative Optimization](https://mlsanity.com/paper/2601.16480/) (2026)
- [COINBench: Moving Beyond Individual Perspectives to Collective Intent Understanding](https://mlsanity.com/paper/2603.21329/) (2026)
- [MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs](https://mlsanity.com/paper/2605.08498/) (2026)
- [Beyond the Current Observation: Evaluating Multimodal Large Language Models in Controllable Non-Markov Games](https://mlsanity.com/paper/2606.19338/) (2026)
- [Reinforcement Learning without Ground-Truth Solutions can Improve LLMs](https://mlsanity.com/paper/2606.27369/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have shown strong reasoning capabilities, with models like OpenAI's O-series and DeepSeek R1 excelling at tasks such as mathematics, coding, logic, and puzzles through Reinforcement Learning with Verifiable Rewards (RLVR). However, their ability to solve more complex optimization problems - particularly NP-hard tasks - remains underexplored. To bridge this gap, we propose NP-ENGINE, the first comprehensive framework for training and evaluating LLMs on NP-hard problems. NP-ENGINE covers 10 tasks across five domains, each equipped with (i) a controllable instance generator, (ii) a rule-based verifier, and (iii) a heuristic solver that provides approximate optimal solutions as ground truth. This generator-verifier-heuristic pipeline enables scalable and verifiable RLVR training under hierarchical difficulties. We also introduce NP-BENCH, a benchmark derived from NP-ENGINE-DATA, specifically designed to evaluate LLMs' ability to tackle NP-hard level reasoning problems, focusing not only on feasibility but also on solution quality. Additionally, we present QWEN2.5-7B-NP, a model trained via zero-RLVR with curriculum learning on Qwen2.5-7B-Instruct, which significantly outperforms GPT-4o on NP-BENCH and achieves SOTA performance with the same model size. Beyond in-domain tasks, we demonstrate that RLVR training on NP-ENGINE-DATA enables strong out-of-domain (OOD) generalization to reasoning tasks (logic, puzzles, math, and knowledge), as well as non-reasoning tasks such as instruction following. We also observe a scaling trend: increasing task diversity improves OOD generalization. These findings suggest that task-rich RLVR training is a promising direction for advancing LLM's reasoning ability, revealing new insights into the scaling laws of RLVR.