CodeComplex는 대규모 언어 모델(LLM)이 코드의 시간 복잡도를 얼마나 잘 예측할 수 있는지 평가하는 데 사용되는 데이터셋입니다. 이 데이터셋은 각각 4**,900개의 Java와 Python 코드**로 구성되어 있으며, 각 코드의 시간 복잡도를 예측하는 모델들의 추론 능력을 정밀하게 측정하는 데 중점을 둡니다. CodeComplex는 LLM이 코드를 얼마나 잘 분석하고 예측할 수 있는지를 평가하는 중요한 기준이 되며, 코드의 효율성을 예측하는 데 있어 더욱 신뢰할 수 있는 성능을 가진 모델을 개발하는 데 기여하고자 합니다.
대규모 언어 모델들이 점차 발전함에 따라서, 초창기에는 문장 구조만 지키는 모델에서, 문맥을 가져가는 모델, 이제는 점차 추론까지 할 수 있는 모델들이 개발되고 있습니다. 이러한 상황에서 CodeComplex는 코드의 최악 시간 복잡도를 통해서 대규모 언어 모델들의 추론 능력을 평가하려고 합니다. 또한, 아직까지는 미숙한 LLM들의 추론 능력에 대응하여, LLM들의 추론 능력을 단계적, 계층적으로 평가할 수 있도록 하는 HC(Hierarchy Complexity**)**-score를 소개합니다.
| Complexity Class | Java Codes | Python Codes |
|---|---|---|
| $O(1)$ | 750 | 791 |
| $O(\log n)$ | 779 | 853 |
| $O(n)$ | 765 | 657 |
| $O(n\log n)$ | 601 | 606 |
| $O(n^2)$ | 700 | 669 |
| $O(n^3)$ | 700 | 796 |
| exponential | 605 | 528 |
| Total | 4,900 | 4,900 |
CodeComplex는 Codeforces에 제출된 코드 결과물들을 바탕으로 정제된 데이터셋이며, 해당 코드들의 출처는 Deepmind의 CodeContests 데이터셋으로부터 추출되었습니다. CodeComplex 데이터셋은 7개의 시간 복잡도 클래스로 구축되었으며, 각 클래스 별의 불균형을 해소하기 위해서 각 클래스별로 적어도 500개의 코드를 확보하였습니다. 이는 예전에 존재하였던 공개된 데이터셋인 CoRCoD의 5개 시간 복잡도 클래스를 확장하였고, 데이터의 숫자도 크게 늘린 결과물입니다.
| 특징 | CoRCoD [1] | TASTY [2] | CodeComplex (Ours) |
|---|---|---|---|
| 다중 언어 지원 | ✖ | ✖ | ✔ |
| 데이터 접근성 | ✔ | ✖ | ✔ |
| 충분한 레이블 제공 | ✖ | △ | ✔ |
| 입력 기반 복잡도 판단 | ✖ | ✖ | ✔ |
대규모 언어 모델들은 아직 완벽한 추론 능력을 가지고 있지 않으며, 특히 긴 입력이나 복잡한 문제에서는 성능이 떨어지는 경우가 대다수입니다. 코드의 구문별 시간 복잡도는 잘 추론하지만, 이를 결합해 전체적인 예측을 할 때 오류가 발생하기도 합니다. 이러한 문제를 해결하기 위해, HC-Score는 예측된 시간 복잡도와 실제 시간 복잡도의 차이를 기반으로 점수를 매깁니다. 이 점수는 모델이 얼마나 정확하게 추론할 수 있는지, 특히 계층적 구조를 가진 문제에서의 성능을 평가할 수 있게 합니다.
$$ \mathrm{HC{-}Score(P, R)} = \frac{\sum_{i=1}^N \frac{|p_i - r_i|}{\text{Number of Classes}}}{N} $$
여기서, $p_i$는 예측한 시간 복잡도, $r_i$는 실제 시간 복잡도, 그리고 $N$은 테스트 샘플의 숫자입니다. HC-score는 단순한 정확도 측정을 넘어, 각 추론을 계층적으로 평가함으로써 모델의 세밀한 성능을 평가할 수 있습니다.
$$ \mathrm{HC{-}Score_w(P, R)} = \frac{\sum_{i=1}^N \max(1 - \frac{|p_i - r_i|}{w}, 0)} {N} $$
이 점수는 시간 복잡도와 같이 계층적이고 단계적인 평가가 가능한 문제에서 특히 유용하며, $\mathrm{HC-Score_w}$는 예측이 특정 윈도우 내에 있을 경우에만 점수를 부여하는 방식으로, 오차가 큰 예측을 제외하고 근접한 예측에만 점수를 부여합니다. 이를 통해 모델이 예측한 값이 실제 값과 얼마나 가까운지를 더욱 직관적으로 알 수 있습니다.
데이터셋은 AI의 도움 없이 3명의 전문 인력이 담당하여 레이블을 하였으며, 레이블을 한 이후에 ChatCPT를 반론자로 넣어서 사람의 레이블과 다른 결과에 대해서 재차 확인할 수 있도록 시스템을 갖추었습니다. 이 과정에서 시간복잡도를 계산하기 위해서 input의 형태를 따졌으며, 이에 따라서 시간복잡도를 계산할 수 있도록 하였습니다.
모델들의 성능을 확인해 보면, Fine-tune 전에는 ChatGPT4.0의 성능이 가장 뛰어났습니다. 비슷한 크기(10B 주변)의 모델들끼리 비교해 보자면 Mistral-12B의 성능이 가장 뛰어났습니다. 하나 흥미로운 점은 Qwen2-7B과 Qwen2.5-7B의 성능 차이인데, 정확도와 F1 점수는 Qwen2.5가 더 높았으나, HC 점수로 측정하였을 때는 Qwen2의 성능이 더 뛰어났습니다. 이는 Qwen2가 일부만 추론에 성공하고 해당 결과를 취합하지 못한 경우가 더 많다는 것을 시사합니다.
Fine-tune 이후에는 모델의 크기에 따라서 순위가 결정되는 경향성이 좀 더 강해집니다. Llama3.1-70B 모델이 1등을 차지했고, 그 뒤를 Qwen2.5-14B, Gemma2-27B 등의 모델이 따라갑니다. 여기서도 Qwen2와 Qwen2.5를 비교하자면, Qwen2의 성능이 오히려 Qwen2.5보다 더 좋아졌습니다. 이는 Qwen2.5보다 좋았던 추론 능력이 fine-tune을 통해서 더 정확한 답을 낼 수 있게 된 것이라고 볼 수 있을 것 같습니다. Qwen2.5의 경우 Code의 시간 복잡도를 판단하는 부분에서는 오히려 살짝 떨어졌다고 볼 수 있습니다.