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

• arxiv url: http://arxiv.org/abs/2410.07432v1
• Date: Wed, 9 Oct 2024 21:01:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 17:06:37.667634
• Title: Can Transformers Reason Logically? A Study in SAT Solving
• Title（参考訳）: トランスフォーマーは論理的に推論できるか?SATソルビングの研究
• Authors: Leyan Pan, Vijay Ganesh, Jacob Abernethy, Chris Esposo, Wenke Lee,
• Abstract要約: 本研究では, LLMの論理的推論能力について, ブール満足度問題(SAT)の文脈で検討する。 まず,Chain-of-Thought (CoT) によるバックトラックとデダクションを用いてSATを解くデコーダのみの変換器を構築する。 我々は、よく知られたDPLL SAT-solvingアルゴリズムにトレース等価性を示すことによって、その正当性を証明した。
• 参考スコア（独自算出の注目度）: 17.15701291424892
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We theoretically and empirically study the logical reasoning capabilities of LLMs in the context of the Boolean satisfiability (SAT) problem. First, we construct a decoder-only Transformer that can solve SAT 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, to support the implementation of this abstract construction, we design a compiler $\texttt{PARAT}$ that takes as input a procedural specification and outputs a transformer model implementing this specification. 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") of the DPLL algorithm.
• Abstract（参考訳）: 本研究では, LLMの論理的推論能力について, ブール充足可能性(SAT)問題の観点から理論的, 実験的に検討した。 まず,Chain-of-Thought (CoT) によるバックトラックとデダクションを用いてSATを解くデコーダのみの変換器を構築する。 我々は、よく知られたDPLL SAT-solvingアルゴリズムにトレース等価性を示すことによって、その正当性を証明した。 第二に、この抽象的な構成の実装をサポートするために、手続き仕様を入力として取り込んだコンパイラ $\texttt{PARAT}$ を設計し、この仕様を実装したトランスフォーマーモデルを出力する。 第3に、$\textit{ programsming}$ a transformer to reasonというよりは、DPLLアルゴリズムのアルゴリズムトレース(推論パス)から直接学習することで、$\textit{trained}$が可能であるかどうかを経験的に評価する。

関連論文リスト

• Self-Satisfied: An end-to-end framework for SAT generation and prediction [0.7340017786387768]
  高速SAT問題生成のためのハードウェアアクセラレーションアルゴリズムと幾何SAT符号化を導入する。 これらの進歩により、何千もの変数と数万の節でSAT問題へのアプローチをスケールできます。 私たちの研究の基本的な側面は、SATデータの本質と、機械学習モデルのトレーニングに適合する可能性に関するものです。
  論文  参考訳（メタデータ） (2024-10-18T22:25:54Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  2種類のランダムな$n$-gram LMを学習するトランスフォーマーの能力について検討する。 例えば、$n$-gram LMに対する古典的な推定手法として、add-$lambda$ smoothing outperform transformerがある。
  論文  参考訳（メタデータ） (2024-10-03T21:21:02Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  分解硬度(d硬度)の概念を導入する。 d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
  論文  参考訳（メタデータ） (2023-12-16T12:44:36Z)
• Learning Reliable Logical Rules with SATNet [7.951021955925275]
  我々は、入力出力の例から基礎となるルールを学習する差別化可能なMaxSATソルバSATNetの上に構築する。 基礎的真理規則に対して有効な検証手法をいくつか導入する。 ストリームトランスフォーメーションとスドク問題に関する実験は、デコードされたルールが信頼性が高いことを示している。
  論文  参考訳（メタデータ） (2023-10-03T15:14:28Z)
• Tracr: Compiled Transformers as a Laboratory for Interpretability [15.76027393879609]
  人間の読みやすいプログラムをデコーダのみのトランスフォーマーモデルに"コンパイル"する方法を示す。 コンパイラであるTrcrは、既知の構造を持つモデルを生成する。 マルチステップアルゴリズムを実行する変換器の「重ね合わせ」について検討する。
  論文  参考訳（メタデータ） (2023-01-12T14:59:19Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)

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

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