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

• URL: http://arxiv.org/abs/2312.14890v4
• Date: Mon, 12 Feb 2024 17:30:25 GMT
• Title: NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes
• Authors: Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, Yongfeng Zhang
• Abstract summary: NPHardEval is designed to evaluate the reasoning abilities of Large Language Models (LLMs) across a broad spectrum of 900 questions. It is meticulously chosen to represent a wide range of complexity class below the NP-hard complexity class. It is designed with a dynamic update mechanism, where the datapoints are refreshed on a monthly basis.
• Score: 32.154637177467684
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• CounterBench: A Benchmark for Counterfactuals Reasoning in Large Language Models [5.409370027524351]
  We evaluate the performance of large language models (LLMs) in counterfactual reasoning. We introduce a new benchmark dataset, CounterBench, comprising 1K counterfactual reasoning questions.
  arXiv  Detail & Related papers  (2025-02-16T06:19:37Z)
• Satori: Reinforcement Learning with Chain-of-Action-Thought Enhances LLM Reasoning via Autoregressive Search [57.28671084993782]
  Large language models (LLMs) have demonstrated remarkable reasoning capabilities across diverse domains. Recent studies have shown that increasing test-time computation enhances LLMs' reasoning capabilities. We propose a two-stage training paradigm: 1) a small-scale format tuning stage to internalize the COAT reasoning format and 2) a large-scale self-improvement stage leveraging reinforcement learning.
  arXiv  Detail & Related papers  (2025-02-04T17:26:58Z)
• ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning [92.76959707441954]
  We introduce ZebraLogic, a comprehensive evaluation framework for assessing LLM reasoning performance. ZebraLogic enables the generation of puzzles with controllable and quantifiable complexity. Our results reveal a significant decline in accuracy as problem complexity grows.
  arXiv  Detail & Related papers  (2025-02-03T06:44:49Z)
• Leveraging Online Olympiad-Level Math Problems for LLMs Training and Contamination-Resistant Evaluation [55.21013307734612]
  AoPS-Instruct is a dataset of more than 600,000 high-quality QA pairs. LiveAoPSBench is an evolving evaluation set with timestamps, derived from the latest forum data. Our work presents a scalable approach to creating and maintaining large-scale, high-quality datasets for advanced math reasoning.
  arXiv  Detail & Related papers  (2025-01-24T06:39:38Z)
• CARL-GT: Evaluating Causal Reasoning Capabilities of Large Language Models [18.975064947089805]
  Causal reasoning capabilities are essential for large language models (LLMs) in a wide range of applications, such as education and healthcare. We provide a benchmark, named by CARL-GT, which evaluates CAusal Reasoning capabilities of large Language models using Graphs and Tabular data.
  arXiv  Detail & Related papers  (2024-12-23T20:34:32Z)
• Are Your LLMs Capable of Stable Reasoning? [38.03049704515947]
  Large Language Models (LLMs) have demonstrated remarkable progress in complex reasoning tasks. However, a significant discrepancy persists between benchmark performances and real-world applications. We introduce G-Pass@k, a novel evaluation metric that provides a continuous assessment of model performance. We present LiveMathBench, a dynamic benchmark comprising challenging, contemporary mathematical problems.
  arXiv  Detail & Related papers  (2024-12-17T18:12:47Z)
• DARG: Dynamic Evaluation of Large Language Models via Adaptive Reasoning Graph [70.79413606968814]
  We introduce Dynamic Evaluation of LLMs via Adaptive Reasoning Graph Evolvement (DARG) to dynamically extend current benchmarks with controlled complexity and diversity. Specifically, we first extract the reasoning graphs of data points in current benchmarks and then perturb the reasoning graphs to generate novel testing data. Such newly generated test samples can have different levels of complexity while maintaining linguistic diversity similar to the original benchmarks.
  arXiv  Detail & Related papers  (2024-06-25T04:27:53Z)
• Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning [53.6472920229013]
  Large Language Models (LLMs) have demonstrated impressive capability in many natural language tasks. LLMs are prone to produce errors, hallucinations and inconsistent statements when performing multi-step reasoning. We introduce Q*, a framework for guiding LLMs decoding process with deliberative planning.
  arXiv  Detail & Related papers  (2024-06-20T13:08:09Z)
• Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoning [20.066249913943405]
  Large language models (LLMs) have showcased remarkable reasoning capabilities, yet they remain susceptible to errors. We introduce novel synthetic datasets specifically designed to assess LLM temporal reasoning abilities in various scenarios. Our findings provide valuable insights into the strengths and weaknesses of current LLMs in temporal reasoning tasks.
  arXiv  Detail & Related papers  (2024-06-13T14:31:19Z)
• LLMs for Relational Reasoning: How Far are We? [8.840750655261251]
  Large language models (LLMs) have revolutionized many areas by achieving state-of-the-art performance on downstream tasks. Recent efforts have demonstrated that the LLMs are poor at solving sequential decision-making problems.
  arXiv  Detail & Related papers  (2024-01-17T08:22:52Z)
• TRACE: A Comprehensive Benchmark for Continual Learning in Large Language Models [52.734140807634624]
  Aligned large language models (LLMs) demonstrate exceptional capabilities in task-solving, following instructions, and ensuring safety. Existing continual learning benchmarks lack sufficient challenge for leading aligned LLMs. We introduce TRACE, a novel benchmark designed to evaluate continual learning in LLMs.
  arXiv  Detail & Related papers  (2023-10-10T16:38:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.