NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes

Assessing the true reasoning capabilities of large language models has become increasingly challenging because static, publicly available benchmarks allow models to memorize answers or overfit to evaluation metrics. This can lead organizations to overestimate model competencies on complex, real-world tasks. The article addresses this issue by introducing NPHardEval, an automated and dynamically refreshed benchmark designed to measure large language model reasoning against established computational complexity classes.

The benchmark establishes a rigorous evaluation framework featuring nine distinct algorithmic reasoning tasks structured across three complexity classes: polynomial time, NP-complete, and NP-hard. Each task contains 100 problem instances distributed over 10 escalating levels of difficulty, for a total of 900 questions per evaluation cycle. To prevent memorization and benchmark hacking, the system uses an automated data synthesis and verification pipeline that refreshes the questions monthly, testing 12 prominent commercial and open-source models under both zero-shot and few-shot conditions.

The evaluation revealed several critical findings regarding model performance and robustness. First, reasoning performance degrades sharply as problem complexity increases; models achieved modest average weighted accuracies of 0.24 in polynomial-time and 0.25 in NP-complete tasks, but collapsed to an average of 0.02 on NP-hard tasks. Second, closed-source models consistently outperformed open-source models in both reasoning accuracy and adherence to formatting, with GPT-4 Turbo leading across most tasks. Third, few-shot prompting revealed that closed-source models demonstrated generalized algorithmic learning across varying prompt difficulties, whereas open-source models showed high performance variability, suggesting pattern mimicry rather than genuine rule internalization. Finally, fine-tuning experiments demonstrated that training open-source models on past benchmark versions improved performance only on simple, same-difficulty polynomial problems, while failing or degrading performance on more complex tasks and harder problem instances.

These findings have direct operational implications for organizations deploying artificial intelligence in decision-critical workflows such as logistics, resource scheduling, and combinatorial optimization. Leaders cannot assume that strong conversational proficiency translates into complex problem-solving abilities. Relying on current models for complex optimization carries significant operational risk, as even top-tier systems struggle to solve higher-order algorithmic challenges.

Organizations should treat conversational AI models as non-authoritative when addressing complex planning and optimization tasks, pairing them with classical algorithmic solvers rather than relying on pure model generation. For research and evaluation teams, adopting dynamic, frequently updated benchmarks is essential to prevent inflated performance metrics caused by data contamination. Future work should explore iterative self-correction mechanisms and collaborative multi-agent systems to enhance underlying model reasoning. Users must remain cautious, however, as the current benchmark uses a linear difficulty weighting scheme that may simplify real-world complexity, and rapid foundational model updates require ongoing re-evaluation.