論文の概要: Can Transformers Reason Logically? A Study in SAT Solving

• arxiv url: http://arxiv.org/abs/2410.07432v2
• Date: Sat, 08 Feb 2025 02:12:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:26:37.371628
• Title: Can Transformers Reason Logically? A Study in SAT Solving
• Title（参考訳）: トランスフォーマーは論理的に推論できるか?SATソルビングの研究
• Authors: Leyan Pan, Vijay Ganesh, Jacob Abernethy, Chris Esposo, Wenke Lee,
• Abstract要約: 本研究では,デコーダのみのトランスフォーマーの論理的推論能力について,SAT問題の観点から検討する。 我々は,デコーダのみのトランスフォーマーが,Chain-of-Thought (CoT) によるバックトラックとデダクションを用いて,一様でない計算モデルで 3-SAT を決定できることを示す。
• 参考スコア（独自算出の注目度）: 17.15701291424892
• License:
• Abstract: We formally study the logical reasoning capabilities of decoder-only Transformers in the context of the boolean satisfiability (SAT) problem. First, we prove by construction that decoder-only Transformers can decide 3-SAT, in a non-uniform model of computation, using backtracking and deduction via Chain-of-Thought (CoT). %We prove its correctness by showing trace equivalence to the well-known DPLL SAT-solving algorithm. Second, we implement our construction as a PyTorch model with a tool (PARAT) that we designed to empirically demonstrate its correctness and investigate its properties. Third, rather than \textit{programming} a transformer to reason, we evaluate empirically whether it can be \textit{trained} to do so by learning directly from algorithmic traces (``reasoning paths'') from our theoretical construction. The trained models demonstrate strong out-of-distribution generalization on problem sizes seen during training but has limited length generalization, which is consistent with the implications of our theoretical result
• Abstract（参考訳）: 本稿では,復号器のみの変換器の論理的論理的推論能力について,論理的論理的論理的論理的推論能力について,論理的論理的論理的論理的論理的論理的論理的解法(SAT)を用いて研究する。 まず,デコーダのみのトランスフォーマーが,Chain-of-Thought (CoT) によるバックトラックとデダクションを用いて,一様でない計算モデルで 3-SAT を決定できることを示す。 % DPLL SAT-solving アルゴリズムにトレース等価性を示すことにより,その正当性を証明した。 第二に、我々はPyTorchモデルをツール(PARAT)で実装し、その正しさを実証的に証明し、その特性を調査するように設計した。 第3に, 理論的構成からアルゴリズム的トレース (`reasoning paths'') から直接学習することで, 解析が可能であるかどうかを実証的に評価した。 訓練されたモデルは、トレーニング中に見られる問題サイズに強い分布の一般化を示すが、我々の理論的結果に一致する長さの一般化を持つ。

関連論文リスト

• Transformers Provably Solve Parity Efficiently with Chain of Thought [40.78854925996]
  この研究は、複雑な問題を解決するためのトレーニングトランスの最初の理論的解析を提供する。 我々は、基本的な$k$-parity問題を解くために、1層トランスを訓練することを検討する。
  論文  参考訳（メタデータ） (2024-10-11T08:55:17Z)
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis [82.51626700527837]
  チェーン・オブ・シフト(Chain-of-shift, CoT)は、複数の中間ステップを持つ例を用いてクエリを増強することにより、大規模言語モデルの推論能力を実現する効率的な手法である。 CoT の理論的成功にもかかわらず、CoT が成立しても正確な一般化が得られないことを示す。
  論文  参考訳（メタデータ） (2024-10-03T03:12:51Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Learning Reliable Logical Rules with SATNet [7.951021955925275]
  我々は、入力出力の例から基礎となるルールを学習する差別化可能なMaxSATソルバSATNetの上に構築する。 基礎的真理規則に対して有効な検証手法をいくつか導入する。 ストリームトランスフォーメーションとスドク問題に関する実験は、デコードされたルールが信頼性が高いことを示している。
  論文  参考訳（メタデータ） (2023-10-03T15:14:28Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  この研究はまず、変換器がICLを実行するための包括的な統計理論を提供する。 コンテクストにおいて、トランスフォーマーは、幅広い種類の標準機械学習アルゴリズムを実装可能であることを示す。 エンフィングル変換器は、異なるベースICLアルゴリズムを適応的に選択することができる。
  論文  参考訳（メタデータ） (2023-06-07T17:59:31Z)
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective [39.47116013338394]
  CoT(Chain-of-Thought prompting)は,大規模言語モデル(LLM)の性能を劇的に向上させる 我々は、CoTが動的プログラミング(Dynamic Programming)として知られる一般的な意思決定問題に対処できることを示します。
  論文  参考訳（メタデータ） (2023-05-24T17:59:21Z)
• Transformers as Algorithms: Generalization and Implicit Model Selection in In-context Learning [23.677503557659705]
  In-context Learning (ICL) は、トランスフォーマーモデルが一連の例で動作し、オンザフライで推論を行うプロンプトの一種である。 我々は,このトランスモデルを学習アルゴリズムとして扱い,推論時別のターゲットアルゴリズムを実装するためのトレーニングを通じて専門化することができる。 変換器は適応学習アルゴリズムとして機能し、異なる仮説クラス間でモデル選択を行うことができることを示す。
  論文  参考訳（メタデータ） (2023-01-17T18:31:12Z)
• Characterizing Intrinsic Compositionality in Transformers with Tree Projections [72.45375959893218]
  トランスのようなニューラルモデルは、入力の異なる部分間で情報を任意にルーティングすることができる。 3つの異なるタスクに対するトランスフォーマーは、トレーニングの過程でより木のようなものになることを示す。 これらの木はモデル挙動を予測し、より木のようなモデルは構成的一般化のテストにおいてより良く一般化する。
  論文  参考訳（メタデータ） (2022-11-02T17:10:07Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)

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

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