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

이 요약은 AI가 원문을 분석해 생성했습니다. 정확한 내용은 원문 기준으로 확인하세요.

TL;DR

최근 대규모 언어 모델(LLM)과 추론 모델(LRM)의 발전에도 불구하고, 유한한 컨텍스트 윈도우 내에서 이들이 도달할 수 있는 공간 복잡도의 한계는 명확히 밝혀지지 않았다. 본 연구는 NP 복잡도 클래스를 넘어 PSPACE-완전 문제인 정규 표현식 등가성 결정(RegexEQ)과 최소화(RegexMin)를 기반으로 한 RegexPSPACE 벤치마크를 소개한다. 이중 지수 공간 탐색을 통해 생성된 100만 개 이상의 인스턴스를 필터링하여 데이터셋을 구축하고, 6종의 LLM과 5종의 LRM을 대상으로 성능을 평가했다. 실험 결과, 모델들은 복잡한 탐색 과정에서 장황한 서술이나 반복적인 오류 패턴을 보이며 계산 용량의 한계를 드러냈다.

배경

정규 표현식(Regular Expression)의 기본 개념, 계산 복잡도 이론(NP, PSPACE-complete)에 대한 이해, LLM 및 LRM(Large Reasoning Models)의 추론 메커니즘 지식

대상 독자

AI 모델 평가 연구자, LLM 추론 알고리즘 개발자, 컴퓨터 이론 및 형식 언어 전공자

의미 / 영향

이 연구는 LLM이 단순한 패턴 매칭을 넘어 복잡한 계산 이론적 문제를 해결할 수 있는지에 대한 중요한 지표를 제시합니다. 특히 PSPACE 수준의 문제를 다룸으로써 향후 모델 아키텍처 설계 시 메모리와 공간 효율성을 어떻게 개선해야 할지에 대한 방향성을 제공합니다.

섹션별 상세

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

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

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

실무 Takeaway

LLM의 추론 능력을 평가할 때 NP 문제를 넘어 PSPACE-완전 문제를 활용함으로써 모델의 실제 계산 한계를 더 정확히 파악할 수 있다.
추론 모델(LRM)이라 할지라도 복잡한 정규 표현식 최소화와 같은 높은 공간 복잡도 문제에서는 반복적인 오류를 범하므로 알고리즘적 사고 개선이 필요하다.
RegexPSPACE 벤치마크는 모델의 컨텍스트 윈도우 활용 능력과 논리적 탐색 효율성을 정량적으로 비교할 수 있는 새로운 표준을 제공한다.

언급된 리소스

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