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

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

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 45 of its 76 references that are in the map.
- First posted on arXiv 22 Dec 2023.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 45)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [A Survey of Large Language Models](https://mlsanity.com/paper/2303.18223/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?](https://mlsanity.com/paper/2202.12837/) (2022)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [DROP: A Reading Comprehension Benchmark Requiring Discrete Reasoning Over Paragraphs](https://mlsanity.com/paper/1903.00161/) (2019)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [AlpacaFarm: A Simulation Framework for Methods that Learn from Human Feedback](https://mlsanity.com/paper/2305.14387/) (2023)
- [ChatEval: Towards Better LLM-based Evaluators through Multi-Agent Debate](https://mlsanity.com/paper/2308.07201/) (2023)
- [Towards Reasoning in Large Language Models: A Survey](https://mlsanity.com/paper/2212.10403/) (2022)
- [Textbooks Are All You Need II: phi-1.5 technical report](https://mlsanity.com/paper/2309.05463/) (2023)
- [Are Emergent Abilities of Large Language Models a Mirage?](https://mlsanity.com/paper/2304.15004/) (2023)
- [Larger language models do in-context learning differently](https://mlsanity.com/paper/2303.03846/) (2023)
- [Language Models can Solve Computer Tasks](https://mlsanity.com/paper/2303.17491/) (2023)
- [Mathematical Capabilities of ChatGPT](https://mlsanity.com/paper/2301.13867/) (2023)

## Built on by (most cited first, 30 of 79)

- [Why Language Models Hallucinate](https://mlsanity.com/paper/2509.04664/) (2025)
- [Benchmark Data Contamination of Large Language Models: A Survey](https://mlsanity.com/paper/2406.04244/) (2024)
- [Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systems](https://mlsanity.com/paper/2504.01990/) (2025)
- [Benchmark Self-Evolving: A Multi-Agent Framework for Dynamic LLM Evaluation](https://mlsanity.com/paper/2402.11443/) (2024)
- [MixEval: Deriving Wisdom of the Crowd from LLM Benchmark Mixtures](https://mlsanity.com/paper/2406.06565/) (2024)
- [Evaluating Step-by-step Reasoning Traces: A Survey](https://mlsanity.com/paper/2502.12289/) (2025)
- [Dynamic Evaluation of Large Language Models by Meta Probing Agents](https://mlsanity.com/paper/2402.14865/) (2024)
- [Inference-Time Scaling for Complex Tasks: Where We Stand and What Lies Ahead](https://mlsanity.com/paper/2504.00294/) (2025)
- [Recent Advances in Large Langauge Model Benchmarks against Data Contamination: From Static to Dynamic Evaluation](https://mlsanity.com/paper/2502.17521/) (2025)
- [CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization](https://mlsanity.com/paper/2504.04310/) (2025)
- [Large Language Models as End-to-end Combinatorial Optimization Solvers](https://mlsanity.com/paper/2509.16865/) (2025)
- [RuleArena: A Benchmark for Rule-Guided Reasoning with LLMs in Real-World Scenarios](https://mlsanity.com/paper/2412.08972/) (2024)
- [AlgoTune: Can Language Models Speed Up General-Purpose Numerical Programs?](https://mlsanity.com/paper/2507.15887/) (2025)
- [DataGen: Unified Synthetic Dataset Generation via Large Language Models](https://mlsanity.com/paper/2406.18966/) (2024)
- [FrontierCS: Evolving Challenges for Evolving Intelligence](https://mlsanity.com/paper/2512.15699/) (2025)
- [Disentangling Logic: The Role of Context in Large Language Model Reasoning Capabilities](https://mlsanity.com/paper/2406.02787/) (2024)
- [Dynamic Multimodal Evaluation with Flexible Complexity by Vision-Language Bootstrapping](https://mlsanity.com/paper/2410.08695/) (2024)
- [HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization](https://mlsanity.com/paper/2506.07972/) (2025)
- [BattleAgent: Multi-modal Dynamic Emulation on Historical Battles to Complement Historical Analysis](https://mlsanity.com/paper/2404.15532/) (2024)
- [Transformers Struggle to Learn to Search](https://mlsanity.com/paper/2412.04703/) (2024)
- [Quantifying Generalization Complexity for Large Language Models](https://mlsanity.com/paper/2410.01769/) (2024)
- [A Survey of Large Language Models on Generative Graph Analytics: Query, Learning, and Applications](https://mlsanity.com/paper/2404.14809/) (2024)
- [Raising the Bar: Investigating the Values of Large Language Models via Generative Evolving Testing](https://mlsanity.com/paper/2406.14230/) (2024)
- [SEC-QA: A Systematic Evaluation Corpus for Financial QA](https://mlsanity.com/paper/2406.14394/) (2024)
- [PuzzleBench: A Fully Dynamic Evaluation Framework for Large Multimodal Models on Puzzle Solving](https://mlsanity.com/paper/2504.10885/) (2025)
- [FCoReBench: Can Large Language Models Solve Challenging First-Order Combinatorial Reasoning Problems?](https://mlsanity.com/paper/2402.02611/) (2024)
- [Interactive Speculative Planning: Enhance Agent Efficiency through Co-design of System and User Interface](https://mlsanity.com/paper/2410.00079/) (2024)
- [Can Transformers Reason Logically? A Study in SAT Solving](https://mlsanity.com/paper/2410.07432/) (2024)
- [On Catastrophic Inheritance of Large Foundation Models](https://mlsanity.com/paper/2402.01909/) (2024)
- [Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition](https://mlsanity.com/paper/2504.03930/) (2025)

## Abstract (arXiv)

Complex reasoning ability is one of the most important features of current LLMs, which has also been leveraged to play an integral role in complex decision-making tasks. Therefore, the investigation into the reasoning capabilities of Large Language Models (LLMs) is critical: numerous benchmarks have been established to assess the reasoning abilities of LLMs. However, current benchmarks are inadequate in offering a rigorous evaluation of the full extent of reasoning abilities that LLMs are capable of achieving. They are also prone to the risk of overfitting, as these benchmarks, being publicly accessible and static, allow models to potentially tailor their responses to specific benchmark metrics, thereby inflating their performance. Addressing these limitations, our research introduces a new benchmark, named NPHardEval. This benchmark is designed to evaluate the reasoning abilities of LLMs across a broad spectrum of 900 algorithmic questions, extending up to the NP-Hard complexity class. These questions are meticulously chosen to represent a wide range of complexity class below the NP-hard complexity class, offering a rigorous measure of the reasoning ability of LLMs. Through this study, we shed light on the current state of reasoning in LLMs, providing an objective and rigorous perspective through the comparison of LLMs' performance across complex classes. Moreover, this benchmark is designed with a dynamic update mechanism, where the datapoints are refreshed on a monthly basis. Such regular updates play a crucial role in mitigating the risk of LLMs overfitting to the benchmark, promoting a more accurate and reliable assessment of their reasoning capabilities. The benchmark dataset and code of NPHardEval are available at https://github.com/casmlab/NPHardEval.