PSPACE完全正規表現問題によるLLM推論評価ベンチマーク
PSPACE正規表現で検証す大規模言語モデル（LLM）の推論能力は注目されているが、有限なコンテキストウィンドウに起因する計算上の空間的限界は未解明である。
本研究は、NPクラスを越えたより厳密な評価基準として、PSPACE完全な「正規表現の同値性決定」と「最小化」という2つの問題を導入した。
これにより、100万以上のインスタンスを含む新しいベンチマークが構築され、LLMとLRMの空間的計算能力が徹底的に評価された。
評価の結果、モデルは冗長性や繰り返しといった共通の失敗パターンを示しており、LLMの計算資源に関する初の経験的フレームワークを提供する。
大規模言語モデル（LLM）の性能向上は目覚ましいものがありますが、その計算能力の限界、特に「空間的複雑性」については十分な研究がなされていませんでした。この度、研究者らがLLMの真の推論能力を測るための新しいベンチマーク「RegexPSPACE」を発表しました。これは、LLMが非常に高度な計算能力を要求される、正規表現（Regex）の複雑な問題に挑むことを目的としています。
PSPACE完全問題という厳密な評価基準
従来のLLMの評価は、多くがNPクラス（非決定性多項式時間）などの比較的扱いやすい問題に集中していました。しかし、本研究では、より計算能力の限界を厳しく試す「PSPACE完全」の問題を基盤としています。PSPACE完全問題とは、解を導出するためには膨大な探索空間を必要とする、非常に困難な計算問題群です。この基準を用いることで、LLMの単なる知識の検索ではなく、真の計算能力を測ることを目指しています。
正規表現の難問：RegexEQとRegexMin
ベンチマークの具体的な内容は、2つの正規表現の問題に焦点を当てています。一つは「等価性判定（RegexEQ）」、もう一つは「最小化（RegexMin）」です。これらは、正規表現同士が同じパターンを表現しているか、あるいは表現を最もシンプルな形にできるかを判断する問題です。研究チームは、これらの問題を解決するために二重指数関数的な探索（double-exponential space exploration）を行い、100万件以上のインスタンスからベンチマークを構築したとのことです。
LLMの共通の失敗パターンとその示唆
6種類のLLMと5種類のLRM（大規模推論モデル）を用いて広範な評価が実施されました。その結果、LLMが共通して「冗長性（verbosity）」や「繰り返し（repetition）」といった形で失敗するパターンが見つかったと報告されています。これは、モデルが高度な推論を行う際、計算リソースやコンテキストウィンドウの制約により、論理的な効率性を維持するのが難しい状況を示唆していると考えられます。
結論
RegexPSPACEの登場は、LLMやLRMの「空間的計算上の限界」を実証的に調査する最初の試みとなりました。この新しい評価フレームワークは、AIモデルの高度な推論能力を定量的に評価するための、重要な道筋を示すものと見られています。
原文の冒頭を表示（英語・3段落のみ）
View PDF
HTML (experimental)
Abstract:Large language models (LLMs) show strong performance across natural language processing (NLP), mathematical reasoning, and programming, and recent large reasoning models (LRMs) further emphasize explicit reasoning. Yet their computational limits, particularly spatial complexity constrained by finite context windows, remain poorly understood. While recent works often focus on problems within the NP complexity class, we push the boundary by introducing a novel benchmark grounded in two PSPACE-complete regular expression (regex) problems: equivalence decision (RegexEQ) and minimization (RegexMin). PSPACE-complete problems serve as a more rigorous standard for assessing computational capacity, as their solutions require massive search space exploration. We perform a double-exponential space exploration to construct a labeled dataset of over a million regex instances with a sound filtering process to build the benchmark. We conduct extensive evaluations on 6 LLMs and 5 LRMs of varying scales, revealing common failure patterns such as verbosity and repetition. With its well-defined structure and quantitative evaluation metrics, this work presents the first empirical investigation into the spatial computational limitations of LLMs and LRMs, offering a new framework for evaluating their advanced reasoning capabilities. Our code is available at this https URL .
※ 著作権に配慮し、引用は冒頭3段落までです。続きは元記事をご覧ください。