RegexPSPACE: PSPACE-완전 정규 표현식 문제를 통한 LLM 추론 능력 평가 벤치마크

섹션별 상세

기존 LLM 평가가 주로 NP 복잡도 수준의 문제에 집중되어 있어 더 높은 수준의 계산 능력을 측정하기 어렵다는 문제가 있었다. RegexPSPACE는 PSPACE-완전 문제인 정규 표현식의 등가성 결정과 최소화 문제를 도입하여 모델의 논리적 추론과 공간적 계산 용량을 더 엄격하게 검증한다. 이를 통해 모델이 방대한 탐색 공간을 체계적으로 다룰 수 있는지 평가할 수 있는 기반을 마련했다.

근거

PSPACE-완전 문제인 정규 표현식 등가성 결정(RegexEQ)과 최소화(RegexMin)를 기반으로 한 새로운 벤치마크를 도입했다. — Abstract 및 Title 출처

벤치마크 구축을 위해 이중 지수(double-exponential) 공간 탐색 기법을 사용하여 100만 개 이상의 정규 표현식 인스턴스를 생성했다. 생성된 데이터는 엄격한 필터링 과정을 거쳐 정답이 보장된 고품질의 레이블링 데이터셋으로 변환되었다. 이 과정은 단순한 텍스트 생성을 넘어 수학적 구조가 명확한 문제를 통해 모델의 성능을 정량적으로 측정할 수 있게 한다.

근거

이중 지수 공간 탐색을 통해 100만 개 이상의 정규 표현식 인스턴스를 포함하는 데이터셋을 구축했다. — Abstract의 'double-exponential space exploration' 언급

6종의 일반 LLM과 5종의 추론 특화 모델(LRM)을 대상으로 광범위한 평가를 수행하여 모델 규모와 아키텍처에 따른 성능 차이를 분석했다. 평가 결과, 많은 모델이 정답에 도달하지 못하고 불필요한 말을 반복하거나 논리적 흐름을 잃는 실패 패턴을 공통적으로 보였다. 특히 공간 복잡도가 높은 문제일수록 모델의 컨텍스트 유지 능력과 추론 일관성이 급격히 저하됨이 확인됐다.

기술

LLM
LRM
RegexEQ
RegexMin

활용 사례

LLM 추론 능력 벤치마킹
모델의 공간 복잡도 한계 테스트
정규 표현식 최적화 도구 평가

언급된 리소스

논문RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems