論文の概要: Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks

• arxiv url: http://arxiv.org/abs/2601.13392v1
• Date: Mon, 19 Jan 2026 21:00:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:23.060959
• Title: Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks
• Title（参考訳）: メモリ化を超えて - 計算タスクの見当たらない理論に基づくLLM推論のテスト
• Authors: Shlok Shelat, Jay Raval, Souvik Roy, Manas Gaur,
• Abstract要約: 大規模言語モデル(LLM)は、形式的な言語タスクにおいて強力なパフォーマンスを示している。 正規言語を用いた決定論的有限オートマトン (DFA) 構築のためのベンチマークを導入する。 モデルが実際の質問に対して完璧に精度を達成し、タスクに対して84-90%を達成できることを示すが、その精度は目に見えない問題に対して急激に低下する。
• 参考スコア（独自算出の注目度）: 8.210112631285666
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models (LLMs) have demonstrated strong performance on formal language tasks, yet whether this reflects genuine symbolic reasoning or pattern matching on familiar constructions remains unclear. We introduce a benchmark for deterministic finite automata (DFA) construction from regular languages, comprising factual knowledge questions, seen construction problems from public sources, and two types of unseen problems: hand-crafted instances with multiple interacting constraints and systematically generated problems via Arden's theorem. Models achieve perfect accuracy on factual questions and 84-90% on seen tasks. However, accuracy drops sharply on unseen problems (by 30-64%), with failures stemming from systematic misinterpretation of language constraints, incorrect handling of Kleene-star semantics, and a failure to preserve global consistency. We evaluate a three-stage hint protocol that enables correction of shallow errors but does not reliably resolve globally inconsistent or structurally flawed automata. Our analysis across multiple prompting strategies (direct, Chain-of-Thought, Tree-of-Thought) reveals that errors persist regardless of prompting approach, exposing a fundamental gap between LLMs' ability to generate syntactically plausible DFAs and their capacity for semantically correct formal reasoning.
• Abstract（参考訳）: 大規模言語モデル (LLM) は形式的な言語タスクにおいて強い性能を示してきたが、それが真の記号的推論や、よく知られた構成のパターンマッチングを反映しているかどうかは不明だ。 本稿では, 実測知識問題, 公開資料から得られた構築問題, および, 複数の相互作用制約を持つ手作りのインスタンス, アーデンの定理による体系的問題を含む, 正規言語からの決定論的有限オートマトン(DFA)構築のベンチマークを紹介する。 モデルは、実際の質問に対して完全な精度と、見られるタスクに対して84-90%を達成する。 しかし、言語制約の体系的誤解釈、クリーネ星のセマンティクスの誤った処理、グローバルな一貫性の維持の失敗などによって、不明瞭な問題(30-64%)で精度が急激に低下する。 浅いエラーの修正を可能にする3段階のヒントプロトコルの評価を行ったが,不整合性や構造的に欠陥のあるオートマトンをグローバルに解決することはできなかった。 複数のプロンプト戦略(ダイレクト、チェーン・オブ・ソート、トリー・オブ・ソート)をまたいだ分析により、プロンプトアプローチにかかわらずエラーは持続し、LLMが構文的に妥当なDFAを生成する能力と、意味論的に正しい形式的推論能力との間には根本的なギャップがあることが判明した。

関連論文リスト

• Are Language Models Efficient Reasoners? A Perspective from Logic Programming [109.47572890883248]
  現代言語モデル(LM)は、強い推論能力を示すが、標準的な評価は、人間のような推論の重要な側面である効率性を見越しながら、正確性を強調する。 本稿では、論理プログラミングのレンズを用いて、LM推論効率を評価するためのフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-10-29T15:30:31Z)
• ReForm: Reflective Autoformalization with Prospective Bounded Sequence Optimization [73.0780809974414]
  本稿では,意味的整合性評価を自己形式化プロセスに統合する反射的自己形式化手法を提案する。 これにより、モデルが形式的なステートメントを反復的に生成し、セマンティックな忠実さを評価し、自己修正された特定エラーを発生させることができる。 実験の結果、ReFormは最強のベースラインに対して平均22.6ポイントの改善を達成した。
  論文  参考訳（メタデータ） (2025-10-28T16:22:54Z)
• Syntactic Blind Spots: How Misalignment Leads to LLMs Mathematical Errors [11.169118114200307]
  大規模言語モデル(LLM)は、強力な数学的問題解決能力を示すが、しばしば訓練分布から構文的に逸脱する問題に失敗する。 モデルがセマンティックに単純だが、不慣れな方法で言い換えられるような問題に対して、慣れ親しんだ推論戦略を誤って適用する、系統的な障害モード、統語的盲点を識別する。 以上の結果から,多くの推論誤差は概念的困難というよりも構造的不整合に起因することが示唆され,構文認識による介入がこれらの帰納的障害を明らかにし緩和する可能性が示唆された。
  論文  参考訳（メタデータ） (2025-10-02T09:26:26Z)
• Chain-of-Code Collapse: Reasoning Failures in LLMs via Adversarial Prompting in Code Generation [0.3495246564946556]
  大規模言語モデル(LLM)は複雑な推論を必要とするタスクにおいて顕著な成功を収めた。 これらのモデルは本当に理由があるのか、それとも浅い統計パターンを利用するだけなのか? ここでは、意味論的に忠実だが逆向きに構造化された急激な摂動のスイートを導入することで、LCMの推論の堅牢性について検討する。
  論文  参考訳（メタデータ） (2025-06-08T02:43:46Z)
• Don't Take the Premise for Granted: Evaluating the Premise Critique Ability of Large Language Models [11.379764847748378]
  大規模言語モデル(LLM)は、しばしば欠陥や矛盾した前提を受け入れ、非効率な推論と信頼できない出力をもたらす。 このことは、入力前提におけるエラーを積極的に識別し、明示する能力として定義されたLSMのためのtextbfPremise Critique Aabilities を持つことの重要性を強調している。 我々は,3つの難易度に4つのエラータイプを組み込んで設計したtextbfPremise Critique Bench (PCBench) を,多面的評価指標と組み合わせて紹介する。
  論文  参考訳（メタデータ） (2025-05-29T17:49:44Z)
• Uncertainty Quantification for In-Context Learning of Large Language Models [52.891205009620364]
  大規模言語モデル(LLM)の画期的な能力として、文脈内学習が登場している。 両タイプの不確かさを定量化するための新しい定式化法とそれに対応する推定法を提案する。 提案手法は、プラグイン・アンド・プレイ方式でコンテキスト内学習の予測を理解するための教師なしの方法を提供する。
  論文  参考訳（メタデータ） (2024-02-15T18:46:24Z)
• WorldSense: A Synthetic Benchmark for Grounded Reasoning in Large Language Models [35.088946378980914]
  我々は3つの最先端チャットLLM(GPT3.5、GPT4、Llama2-chat)上でベンチマークを実行する。 これらのモデルが3つのオブジェクトでもエラーを発生させることを示す。 エラーは、チェーン・オブ・コンテクストのプロンプトやイン・コンテクストの学習でも継続する。
  論文  参考訳（メタデータ） (2023-11-27T15:38:17Z)
• Decomposing Uncertainty for Large Language Models through Input Clarification Ensembling [69.83976050879318]
  大規模言語モデル(LLM)では、不確実性の原因を特定することが、信頼性、信頼性、解釈可能性を改善するための重要なステップである。 本稿では,LLMのための不確実性分解フレームワークについて述べる。 提案手法は,入力に対する一連の明確化を生成し,それらをLLMに入力し,対応する予測をアンサンブルする。
  論文  参考訳（メタデータ） (2023-11-15T05:58:35Z)
• Simple Linguistic Inferences of Large Language Models (LLMs): Blind Spots and Blinds [59.71218039095155]
  我々は,ほとんどの人間が自明に感じる単純な推論タスクにおいて,言語理解能力を評価する。 我々は, (i) 文法的に特定された含意, (ii) 不確実性のある明らかな副詞を持つ前提, (iii) 単調性含意を目標とする。 モデルはこれらの評価セットに対して中程度から低い性能を示す。
  論文  参考訳（メタデータ） (2023-05-24T06:41:09Z)

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

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