Michigan 대학과 Rutgers 대학이 자동 생성 및 월간 업데이트 벤치마크로 LLM의 추론 능력을 NP-Hard 복잡도 클래스 기준으로 측정하는 NPHardEval 리더보드 공개

Context

기존 LLM 평가 벤치마크는 모델이 문제에 과적합되기 쉽고, 일반화된 추론 능력을 정량적으로 측정하기 어려운 한계가 있었다. 추론 능력 평가가 수치 계산과 같은 LLM의 약점에 의해 왜곡되거나 수동 검증이 필요한 문제도 있었다.

Technical Solution

• 복잡도 클래스 기반 평가 체계 도입: 계산 복잡도 이론의 P, NP-Complete, NP-Hard 3개 클래스와 10개 난이도 레벨로 구성된 900개 질문으로 추론 능력을 계층적으로 측정
• 자동 생성 및 검증 메커니즘 구현: 알고리즘 기반 질문이므로 인간 개입 없이 자동으로 정답 검증 가능하게 설계
• 월간 동적 업데이트 체계 운영: 매월 새로운 질문을 자동 생성하여 벤치마크를 갱신하고 모델 과적합 방지
• 수치 계산 제외 전략: 순수 논리 추론 능력 평가에 집중하기 위해 의도적으로 수치 계산 문제 제거
• 가중 정확도(WA) 메트릭 도입: 난이도별 가중치를 1~10으로 선형 증가시켜 (난이도 1 = 가중치 1, 난이도 10 = 가중치 10) 어려운 문제의 성능을 더 높게 반영
• 실패율(FR) 메트릭 추가: 각 난이도당 최대 10회 시도에서 파싱 불가능한 결과를 추적하여 모델의 안정성 평가

Impact

벤치마크에 포함된 9개 알고리즘 × 10개 난이도 × 100개 질문 = 900개의 검증 포인트를 통해 GPT-4 Turbo가 전체 성능 최고를 기록했고, 일부 오픈소스 모델(Yi-34b, Qwen-14b, Phi-2, Mistral-7b)이 특정 문제에서 폐소스 모델을 능가함을 확인했다.

Key Takeaway

추론 능력 평가는 이론적 복잡도 분류와 자동화된 검증 메커니즘을 결합하면 인간 개입과 과적합 위험을 제거하면서도 정량적 측정이 가능하다. 동적 벤치마킹 전략은 지속적인 모델 개선 평가에서 신뢰성을 확보하는 핵심 설계 원칙이다.