LLM을 위한 PSPACE-complete 문제


대규모 언어 모델(LLM)은 다양한 영역에서 성공적인 성능을 입증했지만, 유한한 context window에 의해 제약되는 공간 복잡도 관점에서 LLM의 근본적인 계산 능력의 한계는 아직 충분히 탐구되지 않았습니다. 기존 연구들이 주로 NP-hard 문제에 초점을 맞춘 것과 달리, 본 연구는 PSPACE-complete 문제가 LLM의 공간적 추론 능력의 한계를 평가하는 데 더 엄격하고 적합한 기준이 될 수 있다고 주장합니다.

이에 본 연구에서는 PSPACE-complete 문제 중 정규표현식 최소화(Minimization) 및 등가성 판단(Equivalence) task를 활용하여, LLM의 고차원적 추론 능력을 실험적으로 평가하기 위한 새로운 벤치마크 RegexPSPACE를 제안합니다.

                                                                                  Overview 그림

                                                                              Overview 그림

RegexPSPACE 벤치마크 설계 및 구축


RegexPSPACE 벤치마크는 다음과 같은 체계적인 과정을 통해 구축되었습니다.

  1. 데이터셋 생성 : 특정 깊이까지의 정규표현식 집합을 열거하기 위해 이중 지수 공간 탐색을 수행합니다. 이를 통해 1백만 개 이상의 인스턴스를 포함하는 대규모 데이터셋(Labeled Regex Dataset, LRD)을 생성했습니다.
  2. 정답 라벨링 : LRD의 각 정규표현식에 대해, 기능적으로 동일하면서 가장 짧은 형태를 찾아 정답으로 라벨링합니다. 이 과정은 더 짧은 모든 정규표현식과의 광범위한 등가성 검사를 요구하므로, 전체 프로세스에서 주요 계산 병목 구간에 해당합니다.
  3. 벤치마크 구축 : LRD의 테스트 데이터 중, 필터링 과정을 통해 1,685개의 문제를 선별하여 최종 RegexPSPACE 벤치마크를 구축했습니다.

RegexPSPACE Tasks


RegexPSPACE 벤치마크는 PSPACE-complete 복잡도 클래스에 속하는 두 가지 핵심적인 정규표현식 Task로 구성됩니다.

Regex Minimization (RegexMin)

RegexMin은 주어진 입력 정규표현식에 대해, 기능적으로 완벽히 동일하면서도 가장 짧은 형태의 정규표현식을 찾는 생성(generation) Task입니다. 여기서 길이는 연산자와 문자의 총 개수로 정의됩니다. 이 Task는 등가성 판단(equivalence decision)이 선행되어야 하므로, 동일한 PSPACE-complete 클래스에 속함에도 불구하고 실제로는 훨씬 더 많은 연산을 요구하는 어려운 문제입니다.

Regex Equivalence (RegexEQ)

RegexEQ는 두 개의 입력 정규표현식이 주어졌을 때, 두 표현식이 동일한 문자열 집합을 인식하는지 여부를 판단하는 이진 결정(binary decision) 문제입니다. 모델은 두 정규표현식이 등가이면 True 아니면 False를 출력해야 합니다. 이 문제 역시 PSPACE-complete로 알려져 있습니다.

실험 결과 및 분석