NPHardEval 리더보드: 계산 복잡성을 통한 LLM 추론 평가

Hugging Face는 계산 복잡도 클래스를 사용하여 대형 언어 모델(LLM)의 논리적 추론 능력을 평가하도록 설계된 동적 벤치마크인 NPHardEval 리더보드를 도입했습니다. 미시간 대학교와 러트거스 대학교 연구원들이 개발한 NPHardEval는 다양한 복잡도 수준의 알고리즘 질문을 통해 모델을 테스트함으로써 추론을 정량적으로 측정하고, 데이터셋을 매월 업데이트하여 모델 과적합을 방지합니다.

복잡도 기반 LLM 평가 접근법

NPHardEval는 계산 복잡도 계층을 통해 논리적 추론을 정의하여 LLM의 추론 범위를 엄밀하고 정량적으로 평가할 수 있게 합니다. 평가가 순수한 논리적 추론에 초점을 맞추고 산술 능력에 의존하지 않도록, 이 벤치마크는 질문에서 수치 계산을 의도적으로 제외합니다.

두 가지 주요 전략이 NPHardEval를 기존 벤치마크와 구별합니다:

자동화 메커니즘: 이 벤치마크는 질문을 생성하고 검증하는 자동화 시스템을 사용합니다. 문제들이 알고리즘적으로 계산 가능하기 때문에 LLM 응답의 정확성을 인간 개입 없이 판단할 수 있습니다.
동적 업데이트: 질문이 자동으로 생성되므로 벤치마크는 매월 새롭게 업데이트됩니다. 이는 모델이 정적 데이터셋에 과적합되는 것을 방지하고, 다양한 난이도 수준에서 새로운 질문을 지속적으로 생성할 수 있게 합니다.

데이터 합성 및 구조

NPHardEval 벤치마크는 900개의 합성 질문으로 구성됩니다. 이 질문들은 9개의 서로 다른 알고리즘에 걸쳐 배분되며, 각 알고리즘마다 10개의 난이도 수준이 있습니다. 알고리즘은 복잡도 클래스에 따라 다음과 같이 구분됩니다:

P: 3개 알고리즘
NP-complete: 3개 알고리즘
NP-hard: 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-complete(중간 복잡도) 질문에서 최고의 성능을 보였습니다.
오픈소스 강점: 특정 질문에서는 일부 오픈소스 모델이 폐쇄형 모델보다 뛰어난 성능을 발휘할 수 있습니다. 주목할 만한 선두 오픈소스 모델로는 Yi-34b, Qwen-14b, Phi-2, 그리고 Mistral-7b가 있습니다.