論文の概要: Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy

• arxiv url: http://arxiv.org/abs/2604.02709v1
• Date: Fri, 03 Apr 2026 04:06:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-06 17:20:24.316197
• Title: Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy
• Title（参考訳）: チョムスキー階層による大規模言語モデルの形式推論能力の評価
• Authors: Yihong Dong, Xiaoha Jian, Xue Jiang, Xuyuan Guo, Zhiyuan Fan, Jiaru Qian, Kechi Zhang, Jia Li, Zhi Jin, Ge Li,
• Abstract要約: SOTA LLMが形式言語の構造的・階層的複雑性を把握できるかどうかは不明である。 ChomskyBench はchomsky Hierarchy のレンズを通して LLM を体系的に評価するためのベンチマークである。 ChomskyBenchは、各レベルで機能をテストするように設計された、言語認識と生成タスクの包括的なスイートで構成されている。
• 参考スコア（独自算出の注目度）: 62.32144504442516
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The formal reasoning capabilities of LLMs are crucial for advancing automated software engineering. However, existing benchmarks for LLMs lack systematic evaluation based on computation and complexity, leaving a critical gap in understanding their formal reasoning capabilities. Therefore, it is still unknown whether SOTA LLMs can grasp the structured, hierarchical complexity of formal languages as defined by Computation Theory. To address this, we introduce ChomskyBench, a benchmark for systematically evaluating LLMs through the lens of Chomsky Hierarchy. Unlike prior work that uses vectorized classification for neural networks, ChomskyBench is the first to combine full Chomsky Hierarchy coverage, process-trace evaluation via natural language, and deterministic symbolic verifiability. ChomskyBench is composed of a comprehensive suite of language recognition and generation tasks designed to test capabilities at each level. Extensive experiments indicate a clear performance stratification that correlates with the hierarchy's levels of complexity. Our analysis reveals a direct relationship where increasing task difficulty substantially impacts both inference length and performance. Furthermore, we find that while larger models and advanced inference methods offer notable relative gains, they face severe efficiency barriers: achieving practical reliability would require prohibitive computational costs, revealing that current limitations stem from inefficiency rather than absolute capability bounds. A time complexity analysis further indicates that LLMs are significantly less efficient than traditional algorithmic programs for these formal tasks. These results delineate the practical limits of current LLMs, highlight the indispensability of traditional software tools, and provide insights to guide the development of future LLMs with more powerful formal reasoning capabilities.
• Abstract（参考訳）: LLMの正式な推論能力は、自動化されたソフトウェア工学の進歩に不可欠である。 しかし、LLMの既存のベンチマークには計算と複雑性に基づく体系的な評価が欠けており、それらの公式な推論能力を理解する上で重要なギャップが残されている。 したがって、SOTA LLMが計算理論によって定義される形式言語の構造化された階層的複雑性を把握できるかどうかは不明である。 これを解決するために,チョムスキー階層のレンズを用いてLLMを体系的に評価するベンチマークであるチョムスキーベンチを紹介する。 ニューラルネットワークにベクトル化分類を使用した以前の研究とは異なり、チョムスキーベンチは、完全なチョムスキー階層カバレッジ、自然言語によるプロセストレース評価、決定論的シンボリック検証を初めて組み合わせている。 ChomskyBenchは、各レベルで機能をテストするように設計された、言語認識と生成タスクの包括的なスイートで構成されている。 大規模な実験は、階層の複雑さのレベルと相関する明確なパフォーマンスの成層化を示している。 分析の結果,タスクの難易度の増加が推論長と性能の両方に大きな影響を及ぼす直接的な関係が明らかとなった。 さらに、より大規模なモデルや高度な推論手法は、顕著な相対的な利益をもたらすが、それらは深刻な効率の障壁に直面している。 時間複雑性解析により、LLMはこれらのフォーマルなタスクに対する従来のアルゴリズムプログラムよりもはるかに効率が良くないことが示されている。 これらの結果は、現在のLLMの実用的限界を明確にし、従来のソフトウェアツールの欠如を強調し、より強力な形式的推論能力で将来のLLMの開発を導くための洞察を提供する。

関連論文リスト

• Discrete Tokenization for Multimodal LLMs: A Comprehensive Survey [69.45421620616486]
  本研究は、大規模言語モデル(LLM)用に設計された離散トークン化手法の最初の構造的分類と解析である。 古典的および近代的なパラダイムにまたがる8つの代表的なVQ変種を分類し、アルゴリズムの原理を分析し、力学を訓練し、LLMパイプラインとの統合に挑戦する。 コードブックの崩壊、不安定な勾配推定、モダリティ固有の符号化制約など、重要な課題を特定する。
  論文  参考訳（メタデータ） (2025-07-21T10:52:14Z)
• Do LLMs Dream of Discrete Algorithms? [0.7646713951724011]
  大規模言語モデル(LLM)は、人工知能の風景を急速に変化させてきた。 確率的推論への依存は、厳密な論理的推論を必要とする領域における有効性を制限する。 本稿では,論理ベースの推論モジュールでLLMを増強するニューロシンボリックアプローチを提案する。
  論文  参考訳（メタデータ） (2025-06-29T22:03:01Z)
• Computational Reasoning of Large Language Models [51.629694188014064]
  textbfTuring Machine Benchは,Large Language Models(LLM)による推論プロセスの実行能力を評価するベンチマークである。 TMBenchには、自己完結型および知識に依存しない推論、最小主義的な多段階構造、制御可能な難易度、チューリングマシンに基づく理論的基礎の4つの重要な特徴が組み込まれている。
  論文  参考訳（メタデータ） (2025-04-29T13:52:47Z)
• Inductive Learning of Logical Theories with LLMs: An Expressivity-Graded Analysis [9.865771016218549]
  本研究は,Large Language Models(LLM)の機能と限界を分析するための,新しい体系的方法論を提案する。 この分析は、LLM性能に関する特定の推論課題の定量化を可能にする、複雑性グレードのw.r.t.ルール依存構造である。
  論文  参考訳（メタデータ） (2024-08-15T16:41:00Z)
• Designing Algorithms Empowered by Language Models: An Analytical Framework, Case Studies, and Insights [86.06371692309972]
  本研究では,大規模言語モデル(LLM)に基づくアルゴリズムの設計と解析のための分析フレームワークを提案する。 提案する枠組みは頭痛を緩和する試みとして機能する。
  論文  参考訳（メタデータ） (2024-07-20T07:39:07Z)
• LLMs for Relational Reasoning: How Far are We? [8.840750655261251]
  大規模言語モデル(LLM)は、下流タスクで最先端のパフォーマンスを達成することで、多くの領域に革命をもたらした。 近年の取り組みにより,LSMは逐次決定問題の解決に乏しいことが示されている。
  論文  参考訳（メタデータ） (2024-01-17T08:22:52Z)
• Towards LogiGLUE: A Brief Survey and A Benchmark for Analyzing Logical Reasoning Capabilities of Language Models [56.34029644009297]
  大規模言語モデル(LLM)は、形式的知識表現(KR)システムの様々な制限を克服する能力を示した。 LLMは誘導的推論において最も優れているが、誘導的推論では最も効果が低い。 モデルの性能を評価するため,シングルタスクトレーニング,マルチタスクトレーニング,および「チェーンオブ思考」知識蒸留細調整技術について検討した。
  論文  参考訳（メタデータ） (2023-10-02T01:00:50Z)

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

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