NPHardEval リーダーボード：計算複雑性による LLM 推論の評価

Hugging Face は、計算複雑性クラスを用いて大規模言語モデル（LLM）の論理的推論能力を評価するよう設計された動的ベンチマークである NPHardEval リーダーボードを導入しました。ミシガン大学とラトガース大学の研究者によって開発された NPHardEval は、さまざまな複雑度レベルのアルゴリズム問題でモデルをテストすることで推論を定量的に測定し、データセットを月次で更新してモデルの過学習を防止します。

計算複雑性に基づく LLM 評価アプローチ

NPHardEval は、計算複雑性階層の観点から論理的推論を定義し、LLM の推論範囲を厳密かつ定量的に評価できるようにします。評価が純粋な論理的推論に焦点を当て、算術スキルではなくなるよう、ベンチマークは意図的に質問から数値計算を除外しています。

  • Automated Mechanism: ベンチマークは、質問の生成と検証の両方に自動システムを使用します。問題がアルゴリズム的に計算可能であるため、LLM の応答の正確性は人間の介入なしに判定できます。
  • Dynamic Updates: 質問が自動生成されるため、ベンチマークは毎月更新されます。これにより、モデルが固定データセットに過学習することを防ぎ、さまざまな難易度レベルで新しい質問を継続的に生成できます。

データ合成と構造

NPHardEval ベンチマークは 900 の合成質問で構成されています。これらの質問は 9 つの異なるアルゴリズムに分配され、各アルゴリズムに 10 段階の難易度があります。アルゴリズムはその複雑性クラスに基づいて分類されます：

  • P: 3 つのアルゴリズム
  • NP-complete: 3 つのアルゴリズム
  • NP-hard: 3 つのアルゴリズム

評価指標

NPHardEval は、LLM の性能を測定するために、Weighted Accuracy と Failure Rate の 2 つの指標を使用します。

加重精度 (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 の性能分析から、いくつかの主要な傾向が明らかになりました：

  • Closed-source vs. Open-source: クローズドソースモデルは一般にオープンソースモデルよりも性能が高く、GPT-4 Turbo が全体で最も優れたパフォーマンスを示しました。
  • Complexity Correlation: モデルは通常、複雑度の低い質問（容易な複雑性クラス）でより良い結果を出しますが、複雑度が上がるにつれて性能が必ずしも線形に低下するわけではありません。例として、Claude 2 は NP-complete（中程度の複雑性）質問で最高の性能を示しました。
  • Open-source Strengths: 特定の質問において、オープンソースモデルがクローズドソースモデルを上回ることがあります。代表的な上位オープンソースモデルには Yi-34b、Qwen-14b、Phi-2、Mistral-7b が含まれます。

Sources