NPHardEval Leaderboard: Evaluating LLM Reasoning via Computational Complexity

Hugging Face has introduced the NPHardEval leaderboard, a dynamic benchmark designed to evaluate the logical reasoning capabilities of Large Language Models (LLMs) using computational complexity classes. Developed by researchers from the University of Michigan and Rutgers University, NPHardEval provides a quantifiable measure of reasoning by testing models on algorithmic questions across various complexity levels, updating its dataset monthly to prevent model overfitting.

A Complexity-Based Approach to LLM Evaluation

NPHardEval defines logical reasoning through the lens of computational complexity hierarchy, allowing for a rigorous and quantitative assessment of an LLM's reasoning extent. To ensure the evaluation focuses on pure logical reasoning rather than arithmetic skills, the benchmark deliberately excludes numerical computation from its questions.

Two primary strategies distinguish NPHardEval from traditional benchmarks:

  • Automated Mechanism: The benchmark uses an automated system to both generate and verify questions. Because the problems are algorithmically computable, the correctness of LLM responses can be determined without human intervention.
  • Dynamic Updates: Because questions are generated automatically, the benchmark is refreshed monthly. This prevents models from overfitting to a static dataset and allows for the continuous generation of novel questions across varying difficulty levels.

Data Synthesis and Structure

The NPHardEval benchmark consists of 900 synthesized questions. These questions are distributed across 9 different algorithms, with 10 difficulty levels for each algorithm. The algorithms are categorized by their complexity class:

  • P: 3 algorithms
  • NP-complete: 3 algorithms
  • NP-hard: 3 algorithms

Evaluation Metrics

NPHardEval employs two specific metrics to measure LLM performance: Weighted Accuracy and Failure Rate.

Weighted Accuracy (WA)

Weighted Accuracy measures problem-solving precision while accounting for the difficulty of the task. Each of the 10 difficulty levels is assigned a linear weight (e.g., level 1 has a weight of 1, level 10 has a weight of 10). Accuracy is calculated by comparing the model's response to a correct answer or by checking step-by-step results for problems without a single answer.

The formula used is:

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

Where $w_{i}$ is the weight of difficulty level $i$ and $A_{i}$ is the accuracy at that level.

Failure Rate (FR)

Failure Rate assesses how often a model fails to produce a usable result, specifically identifying instances where the output format cannot be parsed. A failure is recorded if the model's result cannot be successfully parsed across all endpoint calls, with a maximum of 10 attempts per problem.

The formula used is:

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

Where $F_{i}$ denotes the number of failed attempts at difficulty level $i$.

Experimental Insights and Model Performance

Analysis of LLM performance across the benchmark reveals several key trends:

  • Closed-source vs. Open-source: Closed-source models generally outperform open-source models, with GPT-4 Turbo identified as the top overall performer.
  • Complexity Correlation: Models typically perform better on less complex questions (easier complexity classes), though performance does not always decrease linearly as complexity increases. For example, Claude 2 demonstrated the best performance on NP-complete (middle-complexity) questions.
  • Open-source Strengths: Certain open-source models can outperform closed-source models on specific questions. Notable leading open-source models include Yi-34b, Qwen-14b, Phi-2, and Mistral-7b.

Sources