NPHardEval 排行榜：通过计算复杂度评估大语言模型推理能力

Hugging Face 推出了 NPHardEval 排行榜，这是一项动态基准，旨在使用计算复杂度类别评估大语言模型（LLMs）的逻辑推理能力。该基准由密歇根大学和罗格斯大学的研究人员开发，NPHardEval 通过在不同复杂度层级的算法题目上测试模型，提供可量化的推理衡量，并每月更新数据集以防止模型过拟合。

基于复杂度的 LLM 评估方法

NPHardEval 通过计算复杂度层次的视角定义逻辑推理，从而对 LLM 的推理范围进行严格且量化的评估。为确保评估聚焦于纯粹的逻辑推理而非算术技能，该基准刻意在题目中排除数值计算。

自动化机制： 该基准使用自动化系统来生成和验证题目。由于这些问题是算法可计算的，LLM 响应的正确性可以在无需人工干预的情况下确定。
动态更新： 由于题目是自动生成的，基准每月刷新一次。这防止模型对静态数据集产生过拟合，并且能够持续生成不同难度层级的新题目。

数据合成与结构

NPHardEval 基准包含 900 道合成题目。这些题目分布在 9 种不同的算法上，每种算法有 10 个难度级别。算法按其复杂度类别进行分类：

P： 3 种算法
NP 完全： 3 种算法
NP 困难： 3 种算法

评估指标

NPHardEval 使用两项具体指标来衡量 LLM 的表现：加权准确率和失败率。

加权准确率 (WA)

加权准确率在考虑任务难度的同时衡量解题精度。10 个难度级别各自分配线性权重（例如，级别 1 的权重为 1，级别 10 的权重为 10）。准确率通过将模型的响应与正确答案比较，或对没有唯一答案的问题检查逐步结果来计算。

使用的公式为：

$W A = \frac{\sum_{i = 1}^{10} (w_{i} \times A_{i})}{\sum_{i = 1}^{10} w_{i}}$

其中 $w_{i}$ 为难度级别 $i$ 的权重，$A_{i}$ 为该级别的准确率。

失败率 (FR)

失败率评估模型未能产生可用结果的频率，特别是识别输出格式无法解析的情况。如果模型的结果在所有端点调用中均无法成功解析，则记录一次失败，每个问题最多尝试 10 次。

使用的公式为：

$F R = \frac{\sum_{i = 1}^{10} F_{i}}{100}$

其中 $F_{i}$ 表示难度级别 $i$ 的失败尝试次数。

实验洞察与模型表现

对基准上 LLM 表现的分析揭示了若干关键趋势：

闭源 vs. 开源： 闭源模型通常优于开源模型，GPT-4 Turbo 被确定为整体表现最佳的模型。
复杂度相关性： 模型通常在较低复杂度的问题（更易的复杂度类别）上表现更好，尽管性能并不总是随复杂度线性下降。例如，Claude 2 在 NP 完全（中等复杂度）问题上表现最佳。
开源优势： 某些开源模型在特定问题上能够超越闭源模型。值得注意的领先开源模型包括 Yi-34b、Qwen-14b、Phi-2 和 Mistral-7b。