TLDR: NP-ENGINE is a novel framework designed to train and evaluate Large Language Models (LLMs) on challenging NP-hard optimization problems. It features a unique pipeline with a controllable instance generator, a rule-based verifier, and a heuristic solver to provide verifiable rewards. A model named QWEN2.5-7B-NP, trained using NP-ENGINE, significantly outperforms GPT-4o on these optimization tasks and demonstrates enhanced generalization across various reasoning and non-reasoning domains.
Large Language Models (LLMs) have made incredible strides in various reasoning tasks, from mathematics and coding to logic and puzzles. These advancements are often attributed to sophisticated training methods like Reinforcement Learning with Verifiable Rewards (RLVR), which uses clear, objective signals to guide model improvement.
However, a significant challenge remains: LLMs often struggle with more complex optimization problems, particularly those classified as NP-hard. These problems involve intricate combinatorial constraints and vast solution spaces, demanding not just feasible answers but truly optimal ones. Existing research on LLMs tackling NP-hard problems has primarily focused on evaluation and often lacks the fine-grained control over difficulty or the precise optimal solutions needed for effective RLVR training.
To address this crucial gap, researchers have introduced NP-ENGINE, a groundbreaking framework designed to train and evaluate LLMs on NP-hard problems. This comprehensive system covers 10 distinct tasks across five key domains: Graph Clustering, Resource Scheduling, Graph Partitioning, Subset Selection, and Path Planning. Each task within NP-ENGINE is equipped with three essential components:
The NP-ENGINE Pipeline
A controllable instance generator: This component creates problem instances with tunable difficulty levels, allowing for scalable and diverse training data.
A rule-based verifier: This automatically checks the correctness of the LLM’s solutions, providing objective feedback.
A heuristic solver: This generates approximate optimal solutions, serving as a reliable ground truth for evaluating the LLM’s performance.
This innovative generator-verifier-heuristic pipeline enables scalable and verifiable RLVR training, structured with hierarchical difficulties, meaning models can learn from simpler problems before tackling more complex ones.
Accompanying NP-ENGINE is NP-BENCH, a specialized benchmark derived from NP-ENGINE-DATA. NP-BENCH is specifically designed to assess LLMs’ ability to handle NP-hard level reasoning, focusing not only on whether a solution is feasible but also on its overall quality. It uses two key metrics: Success Rate (SR) to measure feasibility and Average Ratio (AR) to compare the model’s solution quality against a heuristic baseline.
A notable achievement of this research is QWEN2.5-7B-NP, a model trained using a zero-RLVR approach with curriculum learning on Qwen2.5-7B-Instruct. This model has demonstrated remarkable performance, significantly outperforming GPT-4o on NP-BENCH and achieving state-of-the-art results for its model size. For instance, its overall Success Rate jumped from 29.6% to 93.1%, and its Average Ratio increased from 14.6% to 46.6%.
Also Read:
- Structure-R1: Enhancing LLM Reasoning with Dynamic Knowledge Structures
- LLM-Powered Agents for Solving Routing Challenges
Training for Deeper Reasoning
The training strategy, termed NP-RL, is structured to foster advanced optimization reasoning. It involves defining verifiable rewards that encourage correct formatting, feasibility, and optimality. Curriculum learning is employed to gradually increase task difficulty, ensuring the model masters foundational skills before moving to more complex problems. Furthermore, a multi-stage RL approach exposes the model to all 10 tasks simultaneously, promoting generalizable reasoning skills across diverse problem types.
Beyond its impressive in-domain performance, QWEN2.5-7B-NP also exhibits strong out-of-domain (OOD) generalization. This means that training on NP-ENGINE-DATA improves the model’s performance on other reasoning tasks (like logic, puzzles, math, and knowledge) and even non-reasoning tasks such as instruction following. The researchers observed a positive correlation: increasing the diversity of training tasks leads to better OOD generalization, offering new insights into the scaling laws of RLVR.
In conclusion, NP-ENGINE represents a significant step forward in empowering LLMs with sophisticated optimization reasoning capabilities. By providing a robust framework for generating, verifying, and evaluating solutions to NP-hard problems, this work paves the way for LLMs to tackle some of the most challenging computational tasks. You can find more details about this research in the full paper: NP-ENGINE: EMPOWERING OPTIMIZATION REASONING IN LARGE LANGUAGE MODELS WITH VERIFIABLE SYNTHETIC NP PROBLEMS.
