대규모 언어 모델(LLM)은 다양한 영역에서 성공적인 성능을 입증했지만, 유한한 context window에 의해 제약되는 공간 복잡도 관점에서 LLM의 근본적인 계산 능력의 한계는 아직 충분히 탐구되지 않았습니다. 기존 연구들이 주로 NP-hard 문제에 초점을 맞춘 것과 달리, 본 연구는 PSPACE-complete 문제가 LLM의 공간적 추론 능력의 한계를 평가하는 데 더 엄격하고 적합한 기준이 될 수 있다고 주장합니다.
이에 본 연구에서는 PSPACE-complete 문제 중 정규표현식 최소화(Minimization) 및 등가성 판단(Equivalence) task를 활용하여, LLM의 고차원적 추론 능력을 실험적으로 평가하기 위한 새로운 벤치마크 RegexPSPACE를 제안합니다.
Overview 그림
RegexPSPACE 벤치마크는 다음과 같은 체계적인 과정을 통해 구축되었습니다.
RegexPSPACE 벤치마크는 PSPACE-complete 복잡도 클래스에 속하는 두 가지 핵심적인 정규표현식 Task로 구성됩니다.
RegexMin은 주어진 입력 정규표현식에 대해, 기능적으로 완벽히 동일하면서도 가장 짧은 형태의 정규표현식을 찾는 생성(generation) Task입니다. 여기서 길이는 연산자와 문자의 총 개수로 정의됩니다. 이 Task는 등가성 판단(equivalence decision)이 선행되어야 하므로, 동일한 PSPACE-complete 클래스에 속함에도 불구하고 실제로는 훨씬 더 많은 연산을 요구하는 어려운 문제입니다.
RegexEQ는 두 개의 입력 정규표현식이 주어졌을 때, 두 표현식이 동일한 문자열 집합을 인식하는지 여부를 판단하는 이진 결정(binary decision) 문제입니다. 모델은 두 정규표현식이 등가이면 True 아니면 False를 출력해야 합니다. 이 문제 역시 PSPACE-complete로 알려져 있습니다.