論文の概要: RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems

• arxiv url: http://arxiv.org/abs/2510.09227v1
• Date: Fri, 10 Oct 2025 10:13:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 00:38:48.692205
• Title: RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems
• Title（参考訳）: RegexPSPACE: PSPACE完全回帰問題に対するLLM推論の評価ベンチマーク
• Authors: Hyundong Jin, Joonghyuk Hahn, Yo-Sub Han,
• Abstract要約: 大規模言語モデル(LLM)は、自然言語処理(NLP)、数学的推論、プログラミングにおいて強い性能を示す。 等価決定(RegexEQ)と最小化(RegexMin)という2つのPSPACE完全正規表現(regex)問題に基礎を置く新しいベンチマークを導入する。 様々なスケールの6LLMと5LRMに対して広範囲に評価を行い、冗長性や繰り返しといった共通の障害パターンを明らかにした。
• 参考スコア（独自算出の注目度）: 9.63813674229442
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 https://github.com/hyundong98/RegexPSPACE .
• Abstract（参考訳）: 大規模言語モデル (LLM) は、自然言語処理(NLP)、数学的推論、プログラミング、そして最近の大規模推論モデル (LRM) において、より明確な推論を強調している。 しかし、その計算限界、特に有限コンテキストウィンドウによって制約される空間複雑性は、いまだに理解されていない。 最近の研究はNP複雑性クラス内の問題に焦点をあてることが多いが、同値決定(RegexEQ)と最小化(RegexMin)という2つのPSPACE完全正規表現(regex)問題に基礎を置く新しいベンチマークを導入することにより、境界を推し進めている。 PSPACE完全問題は、大規模な探索空間探索を必要とするため、計算能力を評価するためのより厳密な標準となっている。 我々は、100万以上のRegexインスタンスのラベル付きデータセットを、ベンチマークを構築するためのサウンドフィルタリングプロセスで構築するために、二重指数空間探索を行う。 様々なスケールの6LLMと5LRMに対して広範囲に評価を行い、冗長性や繰り返しといった共通の障害パターンを明らかにした。 適切に定義された構造と定量的評価指標を用いて、この研究はLLMとLRMの空間的計算限界に関する最初の実証的研究を行い、彼らの高度な推論能力を評価するための新しい枠組みを提供する。 私たちのコードはhttps://github.com/hyundong98/RegexPSPACEで利用可能です。

関連論文リスト

• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• GSM-Infinite: How Do Your LLMs Behave over Infinitely Increasing Context Length and Reasoning Complexity? [37.399561533852506]
  微粒化制御下での難易度と文脈長を無限に低減した算術問題を生成することができる小学校数学問題生成装置を開発した。 複雑性が増大するにつれて、推論性能が一貫したシグマノイドの低下と、体系的な推論スケーリングの傾向が見られます。
  論文  参考訳（メタデータ） (2025-02-07T17:05:25Z)
• Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
  この研究は、正則決定過程(RDP)と呼ばれる非マルコフ環境のクラスにおけるオフライン強化学習(RL)を研究する。 インスは、未来の観測と過去の相互作用からの報酬の未知の依存を実験的に捉えることができる。 多くのアルゴリズムは、まずこの未知の依存関係を自動学習技術を用いて再構築する。
  論文  参考訳（メタデータ） (2024-09-04T14:26:58Z)
• Reliable Reasoning Beyond Natural Language [0.047888359248129786]
  大きな言語モデル(LLM)は、しばしば、確実に柔軟に推論する能力の限界を示す。 本稿では,問題文から全ての関連情報を論理コード文として抽出し,エンコードする手法を提案する。 次に、論理型プログラミング言語(Prolog)を用いて、明示的な推論の反復的な計算を行う。
  論文  参考訳（メタデータ） (2024-07-16T04:34:18Z)
• MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning [63.80739044622555]
  自然言語ナラティブで指定されたソフト推論タスクの言語モデルを評価するデータセットである MuSR を紹介する。 このデータセットには2つの重要な特徴がある。まず、ニューロシンボリック合成-自然生成アルゴリズムによって生成される。 第二に、私たちのデータセットインスタンスは、実世界の推論の領域に対応する無料のテキスト物語です。
  論文  参考訳（メタデータ） (2023-10-24T17:59:20Z)
• Can Large Language Models Understand Real-World Complex Instructions? [54.86632921036983]
  大型言語モデル(LLM)は人間の指示を理解することができるが、複雑な命令には耐えられない。 既存のベンチマークでは、LLMが複雑な命令を理解する能力を評価するには不十分である。 複雑な命令を体系的に追従するLSMの能力を評価するためのベンチマークであるCellOを提案する。
  論文  参考訳（メタデータ） (2023-09-17T04:18:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。