NPH ard E val: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes (2024)

Abstract: Complex reasoning ability is one of the most important features of Large Language Models (LLMs). Numerous benchmarks have been established to assess the reasoning abilities of LLMs. However, they are inadequate in offering a rigorous evaluation and prone to the risk of overfitting, as these publicly accessible and static benchmarks allow models to potentially tailor their responses to specific benchmark metrics, thereby inflating their performance. Addressing these limitations, we introduce a new benchmark NPHardEval. It contains a broad spectrum of 900 algorithmic questions belonging up to the NP-Hard complexity class, offering a rigorous measure of the reasoning ability of LLMs utilizing computational complexity. 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.

## introduction the advancement of llms has ushered in a transformative era in ai research @xcite . one major advantage of llm is its strong reasoning capabilities @xcite . a range of benchmarks have been developed to assess the performance of llms in reasoning tasks @xcite @xcite @xcite . despite these efforts, these benchmarks are not without their shortcomings. firstly, they often fail to accurately characterize or classify the reasoning abilities of llms, leaving a gap in understanding the full extent of what llms can and cannot do. secondly, there is a pronounced risk of models becoming overly specialized to these benchmarks, which may lead to an overestimation of their capabilities @xcite . lastly, the reliance on manual evaluation methods in some instances has proven to be inefficient, ineffective, and lacking in standardization @xcite . addressing the identified limitations and queries within the current benchmarking landscape, this paper introduces a novel benchmark, nphardeval, which surpasses existing benchmarks in three critical aspects. firstly, nphardeval incorporates the established principles of computational complexity classes, offering a more rigorous and quantitative framework for assessing the reasoning capabilities of large language models. the benchmark is meticulously crafted, featuring nine reasoning tasks meticulously selected across three complexity classes-polynomial-time complexity, np-complete complexity, and np-hard complexity-as delineated in @xcite . each class contains 100 instances, distributed over ten distinct levels of difficulty, enabling a comprehensive and measurable evaluation of llms' reasoning abilities. secondly, nphardeval benefits from an end-to-end automated framework for both task generation and results verification. this automation leverages mature algorithms for well-known tasks within the benchmark, facilitating the periodic update of data points on a monthly basis. such a dynamic update mechanism significantly diminishes the risk of model overfitting, thereby maintaining the benchmark's stringency and applicability over time. lastly, the benchmark's reliance on automatic verification for task solutions enhances the accuracy and reliability of evaluations, obviating the need for labor-intensive manual verification. this approach not only streamlines the evaluation process but also presents a theoretically intriguing opportunity to explore llms' proficiency in navigating the computational complexity hierarchy, with a particular focus on np-hard and npcomplete problems @xcite . ## experimental setting this section presents the experiment setting to answer the three research questions. our approach assessed 12 distinct llms, with a dichotomy between five proprietary (closed-source) models and five open-source models, including gpt 4 turbo, claude 2, gpt 3.5 turbo, claude instant 1.2, palm 2, vicuna-13b, yi-34b, mistral-7b, mpt-30b, phi-1.5, phi-2, and qwen-14b. ## conclusion we present a novel benchmark, nphardeval, designed to rigorously evaluate llms' reasoning capabilities across a spectrum of complex tasks, up to the complexity class of np-hard. by eschewing standard qa formats in favor of complex, logicoriented problems, this benchmark aims to provide a more accurate measure of a model's reasoning prowess. this approach is crucial for developing llms capable of handling sophisticated, real-world tasks that demand high-level cognitive processing, steering the evaluation of llms from potentially "useful" to fundamentally "logical".