NP-Engine: Empowering Optimization Reasoning in Large Language Models with Verifiable Synthetic NP Problems
Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen, Tongji University, Shanghai AI Lab, Zhejiang University, Fudan University https://github.com/OliverLeeXZ/NP-Engine · 2025
Read NP-Engine: Empowering Optimization Reasoning in Large Language Models with Verifiable Synthetic NP Problems by Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen, Tongji University, Shanghai AI Lab, Zhejiang University, Fudan University https://github.com/OliverLeeXZ/NP-Engine (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16476.txt.
Introduction
Xiaozhe Li leads six co-authors in a 2025 study on hard puzzle-like tasks for language models. NP-hard tasks are ones where good answers are hard to find but easy to check. Their frame, NP-Engine, trains and tests models on ten such tasks from five fields. Each task has a maker for new cases and a rule-based checker.
A rough solver gives near-best answers to train against. Their test set, NP-Bench, scores both if an answer works and how good it is. A model they trained beat GPT-4o on the bench at the same size class. Training on these tasks also helped on logic, maths, and plain tasks. Rich task mixes may be a strong path for training.
Catalog record
| CREATOR | Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen, Tongji University, Shanghai AI Lab, Zhejiang University, Fudan University https://github.com/OliverLeeXZ/NP-Engine |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-16476
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
NP-Engine: Empowering Optimization Reasoning in Large Language Models with Verifiable Synthetic NP Problems Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen, Tongji University, Shanghai AI Lab, Zhejiang University, Fudan University https://github.com/OliverLeeXZ/NP-Engine Abstract 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. 1 1 footnotetext: * Work done during an internship in Shanghai AI Laboratory. † represents Corresponding authors. 1 Introduction Large Language Models (LLMs) have made significant advancements in complex reasoning tasks such as mathematics He et al. 2025 , coding Liu & Zhang 2025 , logic Xie et al. 2025 , and puzzles Chen et al. 2025 ; Ma et al. 2024 , showcasing the effectiveness of the Reinforcement Learning with Verifiable Rewards (RLVR) paradigm Xu et al. 2025b ; Albalak et al. 2025 . RLVR leverages high-quality, verifiable reward signals to guide model optimization, thereby enhancing LLMs’ reasoning abilities OpenAI 2024 ; Guo et al. 2025 ; Google 2025 ; Anthropic 2025 . Despite significant advances, most existing research on reasoning in logic, mathematics, and puzzles focuses primarily on producing the “correct” answer, emphasizing solution accuracy. This emphasis overlooks solution quality, particularly in tasks that require not just feasible answers but optimal solutions. This gap highlights a crucial aspect of reasoning ability, referred to as optimization reasoning Li et al. 2025b . To comprehensively evaluate the optimization capabilities of LLMs, we focus on utilizing LLMs to solve NP-hard problems, which involve complex combinatorial constraints and large problem spaces, posing significant optimization challenges. Since obtaining the optimal solution is computationally intractable in polynomial time, achieving better solutions requires the model to engage in advanced reasoning, iterative trial-and-error, the generation of initial feasible solutions, and continuous self-reflection and optimization. Recent works, such as NPHardEval Fan et al. 2024 and NPPC Yang et al. 2025b , have explored LLMs’ performance on NP-hard problems. However, these studies are primarily focused on evaluation and suffer from limitations, such as insufficient control over difficulty levels and scalability or reliance on coarse metrics, which restrict their applicability in RLVR. Specifically, they do not offer the fine-grained optimal solutions necessary for generating high-quality reward signals, posing a significant challenge for integrating LLMs with RLVR in NP-level optimization tasks. To address this gap, we propose NP-Engine , a unified framework for training and evaluating LLMs on NP-level optimization tasks using RLVR. NP-Engine includes 10 tasks across five domains, each featuring: (i) a scalable generator that produces instances with tunable difficulty, (ii) a rule-based verifier for automatic evaluation, and (iii) a heuristic algorithm that generates approximate optimal solutions. This generator-verifier-heuristic pipeline facilitates scalable RLVR training and allows for a fine-grained analysis of LLM performance. To assess optimization capabilities, we introduce NP-Bench , a benchmark that categorizes the 10 tasks into five primary categories, each containing 100 problems. Additionally, we design two metrics—Success Rate (SR) and Average Ratio (AR)—to evaluate the feasibility and optimality of the LLM’s solutions. We also develop Qwen2.5-7B-NP , trained on Qwen2.5-7B-Instruct using zero-shot RLVR with curriculum learning strategies. Qwen2.5-7B-NP significantly outperforms GPT-4o on NP-Bench , achieving SOTA SR across all LLMs and the highest AR among LLMs of the same size. Additionally, we evaluate the out-of-distribution (OOD) generalization of Qwen2.5-7B-NP on diverse reasoning tasks (logic, math, puzzles, knowledge) as well as non-reasoning tasks (instruction-following). Our results reveal that increasing task diversity enhances OOD performance, offering new insights into the scaling laws of RLVR for complex reasoning tasks. Our contributions are summarized as follows: • We introduce NP-Engine , a scalable framework that generates near-infinite and hierarchically difficult NP-hard problems within the RLVR paradigm, empowering LLMs’ optimization reasoning abilities. NP-Engine enables Qwen2.5-7B-Instruct to significantly outperform GPT-4o in optimization reasoning tasks using only 5K training examples. • We propose NP-Bench , a benchmark consisting of 10 NP-level tasks spanning five categories: Graph Clustering, Resource Scheduling, Graph Partitioning, Subset Selection, and Path Planning. NP-Bench provides instances with varying difficulty levels and evaluates both the feasibility and quality of solutions. • Through extensive experiments, we demonstrate that training on NP-Engine-Data enables Qwen2.5-7B-NP to generalize to both reasoning and non-reasoning OOD tasks. We also observe a positive correlation between task diversity and cross-task generalization performance, offering new insights into the scaling behavior of RLVR-based training. 2 NP-Engine-Data : The Optimization Reasoning Dataset 2.1 NP Problem Categories Figure 1: Overview of the NP-Engine-Data : 10 NP-hard level tasks across five categories (graph clustering, resource scheduling, graph partitioning, subset selection, and path planning), designed to improve and evaluate optimization reasoning capabilities in LLMs. As shown in Figure 1 , NP-Engine-Data comprises ten NP tasks of five main categories, including: Graph Clustering. Select vertex sets under strict adjacency constraints to optimize structural objectives, requiring graph structural understanding and reasoning ability. Canonical problems include Maximum Clique , Maximum Independent Set , and Graph Coloring , focusing on dense-substructure clustering, mutual exclusivity, and chromatic feasibility. Resource Scheduling. Assign activities to limited resources while avoiding conflicts and maximizing a global objective. The Meeting Scheduling task explores temporal feasibility, capacity limits, attendance constraints, and multi-constraint optimization. Graph Partitioning. Partition a graph into (near-)equal parts while minimizing cut cost. Balanced Minimum Bisection balances partition constraints with inter-part edge weights, emphasizing cut minimization under cardinality constraints. Subset Selection. Choose subsets under combinatorial constraints to optimize coverage or sum/weight limits. Representative tasks such as Subset Sum , Set Cover , and Knapsack involve discrete feasibility checks and value–weight trade-offs. Path Planning. Find short tours or feasible cycles visiting all nodes under specific distance metrics. The Traveling Salesman Problem and Hamiltonian Cycle test global optimization of permutations, path construction, and cycle feasibility. 2.2 NP-Engine-Data Construction We outline a four-stage data construction pipeline for NP-Engine-Data : (I) Task Collection and Design; (II) Auto Task Generator and Verifier Development; (III) Heuristic Algorithm Construction; (IV) Task Difficulty Definition. Stage I: Task Collection and Design.