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

📄 arXiv: 2312.14890v4 📥 PDF

作者: Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, Yongfeng Zhang

分类: cs.AI, cs.CC, cs.CL, cs.LG

发布日期: 2023-12-22 (更新: 2024-02-12)

备注: 23 pages, 7 figures, 2 tables

🔗 代码/项目: GITHUB

💡 一句话要点

NPHardEval：通过复杂度类动态评估大语言模型的推理能力

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 推理能力 NP-Hard 动态基准 复杂度类

📋 核心要点

  1. 现有LLM推理能力评估基准存在覆盖范围不足和易过拟合的问题，无法准确衡量LLM的真实推理能力。
  2. NPHardEval基准通过包含NP-Hard复杂度类问题，并采用动态更新机制，旨在更全面、客观地评估LLM的推理能力。
  3. 该研究通过比较LLM在不同复杂度类问题上的表现，揭示了当前LLM推理能力的现状，并提供了一个更可靠的评估框架。

📝 摘要（中文）

当前大语言模型(LLM)最重要的特征之一是其复杂的推理能力，这种能力在复杂的决策任务中发挥着不可或缺的作用。因此，对LLM的推理能力进行研究至关重要：已经建立了许多基准来评估LLM的推理能力。然而，目前的基准在严格评估LLM能够达到的推理能力的全部范围方面是不够的。它们也容易出现过拟合的风险，因为这些基准是公开可访问和静态的，这使得模型有可能根据特定的基准指标来调整它们的响应，从而夸大它们的性能。为了解决这些局限性，我们的研究引入了一个新的基准，名为NPHardEval。该基准旨在评估LLM在900个算法问题上的推理能力，这些问题扩展到NP-Hard复杂度类。这些问题经过精心挑选，代表了NP-hard复杂度类以下的各种复杂度类，为LLM的推理能力提供了严格的衡量标准。通过这项研究，我们阐明了LLM推理的现状，通过比较LLM在复杂类上的性能，提供了一个客观和严格的视角。此外，该基准采用动态更新机制设计，其中数据点每月刷新一次。这种定期更新在降低LLM对基准的过拟合风险方面起着至关重要的作用，从而促进了对其推理能力更准确和可靠的评估。NPHardEval的基准数据集和代码可在https://github.com/casmlab/NPHardEval获取。

🔬 方法详解

问题定义：现有的大语言模型推理能力评估基准存在两个主要问题。一是覆盖范围有限，无法充分评估模型在不同复杂度问题上的表现，特别是NP-Hard级别的问题。二是静态数据集容易导致模型过拟合，模型可能会针对特定基准进行优化，从而虚报其真实性能。因此，需要一个更全面、更动态的基准来准确评估LLM的推理能力。

核心思路：NPHardEval的核心思路是通过引入NP-Hard复杂度类的问题来扩展评估范围，并采用动态更新机制来防止过拟合。通过包含各种复杂度级别的问题，可以更全面地了解LLM在不同难度下的推理能力。动态更新机制通过定期更换数据集，迫使模型学习更通用的推理策略，而不是简单地记忆特定问题的答案。

技术框架：NPHardEval基准主要包含以下几个部分：1) 一个包含900个算法问题的题库，这些问题涵盖了从P到NP-Hard的各种复杂度类。2) 一个数据生成模块，用于定期生成新的问题实例，以实现动态更新。3) 一个评估模块，用于运行LLM并评估其在不同复杂度问题上的性能。4) 一个在线平台，用于发布基准数据、评估结果和相关代码。

关键创新：NPHardEval的关键创新在于其动态更新机制和对NP-Hard复杂度问题的覆盖。与传统的静态基准相比，动态更新机制可以有效防止模型过拟合，并提供更可靠的性能评估。对NP-Hard复杂度问题的覆盖可以更全面地评估LLM的推理能力，并揭示其在解决复杂问题方面的局限性。

关键设计：NPHardEval的动态更新机制采用每月刷新的策略，确保数据集的多样性和新鲜度。问题的生成过程经过精心设计，以保证不同复杂度类问题的分布均匀，并避免出现过于简单或过于困难的问题。评估指标包括准确率、召回率和F1值，用于综合评估LLM在不同复杂度问题上的性能。

📊 实验亮点

NPHardEval基准测试了多个LLM在不同复杂度类问题上的性能，结果表明，现有LLM在NP-Hard问题上的表现远低于在P类问题上的表现，这表明LLM在解决复杂推理问题方面仍有很大的提升空间。动态更新机制有效降低了模型过拟合的风险，提供了更可靠的性能评估。

🎯 应用场景

NPHardEval可用于评估和比较不同LLM的推理能力，帮助研究人员了解LLM在解决复杂问题方面的优势和局限性。该基准还可以用于指导LLM的训练和优化，提高其在实际应用中的性能，例如智能决策、自动化推理和复杂问题求解等领域。

📄 摘要（原文）

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.