論文の概要: Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth

• arxiv url: http://arxiv.org/abs/2602.11175v1
• Date: Mon, 19 Jan 2026 21:53:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-15 14:54:53.726006
• Title: Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth
• Title（参考訳）: 変圧器と共振器を区別するバリアー:深さ・エクサデンス・帯域幅に関する調査
• Authors: Michelle Yuan, Weiyi Sun, Amir H. Rezaeian, Jyotika Singh, Sandip Ghoshal, Yao-Ting Wang, Miguel Ballesteros, Yassine Benajiba,
• Abstract要約: トランスフォーマーは、幅広いシーケンスモデリング応用の基盤となるアーキテクチャとなっている。 しかし、算術、論理推論、アルゴリズム合成といった離散的推論タスクにおける理論上の制限は、依然として重要な開問題である。
• 参考スコア（独自算出の注目度）: 8.621689945201346
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformers have become the foundational architecture for a broad spectrum of sequence modeling applications, underpinning state-of-the-art systems in natural language processing, vision, and beyond. However, their theoretical limitations in discrete reasoning tasks, such as arithmetic, logical inference, and algorithmic composition, remain a critical open problem. In this survey, we synthesize recent studies from three theoretical perspectives: circuit complexity, approximation theory, and communication complexity, to clarify the structural and computational barriers that transformers face when performing symbolic computations. By connecting these established theoretical frameworks, we provide an accessible and unified account of why current transformer architectures struggle to implement exact discrete algorithms, even as they excel at pattern matching and interpolation. We review key definitions, seminal results, and illustrative examples, highlighting challenges such as depth constraints, difficulty approximating discontinuities, and bottlenecks in inter-token communication. Finally, we discuss implications for model design and suggest promising directions for overcoming these foundational limitations.
• Abstract（参考訳）: トランスフォーマーは、自然言語処理、ビジョンなどにおける最先端システムの基盤となる、幅広いシーケンスモデリングアプリケーションの基盤アーキテクチャとなっている。 しかし、算術、論理推論、アルゴリズム合成といった離散的推論タスクにおける理論上の制限は、依然として重要な開問題である。 本稿では,回路複雑性,近似理論,通信複雑性の3つの理論的視点から最近の研究を合成し,シンボリック計算を行う際にトランスフォーマーが直面する構造的および計算的障壁を明らかにする。 これらの確立された理論的枠組みを結合することにより、パターンマッチングや補間に長けていても、現在のトランスフォーマーアーキテクチャが正確な離散アルゴリズムの実装に苦慮している理由を、アクセス可能かつ統一的に説明できる。 我々は,重要な定義,セミナルな結果,図示的な例を概観し,深度制約,不連続性の近似の困難さ,トークン間通信におけるボトルネックなどの課題を強調した。 最後に,モデル設計の意義について考察し,これらの基礎的制約を克服するための有望な方向性を提案する。

関連論文リスト

• Fourier Neural Operators Explained: A Practical Perspective [75.12291469255794]
  フーリエ・ニューラル・オペレータ(FNO)は、そのエレガントなスペクトル定式化により最も影響力があり広く採用されている。 本ガイドは,FNOを多種多様な科学・工学分野に効果的に適用するための,明確かつ信頼性の高い枠組みを確立することを目的とする。
  論文  参考訳（メタデータ） (2025-12-01T08:56:21Z)
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization [53.89723291716722]
  AI推論に関する重要な問題は、モデルが学習した推論パターンを外挿して、より長いチェーン・オブ・シークレット(CoT)で難しいタスクを解決できるかどうかである。 状態追跡問題の代数構造が、学習されたCoTの外挿の度合いをいかに支配するかを数学的に証明する。 定数深度変換器はCoTで$mathsfNC1$-complete問題を確実に学習することを保証する。
  論文  参考訳（メタデータ） (2025-11-10T18:40:24Z)
• A Mathematical Explanation of Transformers for Large Language Models and GPTs [6.245431127481903]
  本稿では,トランスフォーマーを構造化積分微分方程式の離散化として解釈する新しい連続フレームワークを提案する。 この定式化の中で、自己注意機構は非局所積分作用素として自然に現れる。 提案手法は, 連続領域にトランスフォーマー演算全体を埋め込むことにより, 従来の理論的解析を超えて拡張する。
  論文  参考訳（メタデータ） (2025-10-05T01:16:08Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  シンボルレベルのプリコーディングにおいて,推論の複雑さの低いエンドツーエンドディープラーニング(DL)フレームワークを提案する。 提案手法は,従来の手法よりも約80倍の高速化を実現しつつ,SLPの大幅な性能向上を達成できることを示す。
  論文  参考訳（メタデータ） (2025-10-02T15:15:50Z)
• On the Existence of Universal Simulators of Attention [17.01811978811789]
  注意出力と基礎となる基本行列を同一に再現し、RASPを介してアクティベーション操作を行う方法を提案する。 我々の証明は、これまで学習によってのみ近似することが知られていたアルゴリズムによって達成可能なデータ非依存の解の存在を初めて示すものである。
  論文  参考訳（メタデータ） (2025-06-23T15:15:25Z)
• Propositional Logic for Probing Generalization in Neural Networks [3.6037930269014633]
  本稿では,3つの重要なニューラルネットワーク(Transformers, Graph Convolution Networks, LSTMs)の,命題論理に根ざした制御タスクにおける一般化挙動について検討する。 構造バイアスを導入しなければ,Transformerはネゲーションを構成的に適用できないことがわかった。 本研究は,論理演算子の体系的表現を学習する標準的なアーキテクチャの能力において,永続的な限界を浮き彫りにするものである。
  論文  参考訳（メタデータ） (2025-06-10T16:46:05Z)
• Complexity Control Facilitates Reasoning-Based Compositional Generalization in Transformers [10.206921909332006]
  本研究では,コンポジションタスクにおけるトランスフォーマーの振舞いのメカニズムについて検討する。 複雑性制御戦略は,分布外(推論に基づく解)を一般化するプリミティブレベルのルールを学習するか,あるいは記憶されたマッピング(メモリベースの解)にのみ依存するかに影響を及ぼす。
  論文  参考訳（メタデータ） (2025-01-15T02:54:52Z)
• The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
  我々は古典的およびパラメータ化された計算複雑性理論を用いて回路発見を研究する。 私たちの発見は、難しい複雑さの風景を明らかにします。 このフレームワークは、解釈可能性クエリの範囲と限界を理解するのに役立ちます。
  論文  参考訳（メタデータ） (2024-10-10T15:22:48Z)
• Hierarchical Invariance for Robust and Interpretable Vision Tasks at Larger Scales [54.78115855552886]
  本稿では、畳み込みニューラルネットワーク(CNN)のような階層型アーキテクチャを用いて、オーバーコンプリート不変量を構築する方法を示す。 オーバーコンプリート性により、そのタスクはニューラルアーキテクチャサーチ(NAS)のような方法で適応的に形成される。 大規模で頑健で解釈可能な視覚タスクの場合、階層的不変表現は伝統的なCNNや不変量に対する効果的な代替物とみなすことができる。
  論文  参考訳（メタデータ） (2024-02-23T16:50:07Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  3つの代表的構成課題にまたがる変圧器大言語モデルの限界について検討する。 これらのタスクは、問題をサブステップに分割し、これらのステップを正確な答えに合成する必要があります。 実験結果から,多段階合成推論を線形化部分グラフマッチングに還元することにより,トランスフォーマーLLMが構成課題を解くことが示唆された。
  論文  参考訳（メタデータ） (2023-05-29T23:24:14Z)
• Query Structure Modeling for Inductive Logical Reasoning Over Knowledge Graphs [67.043747188954]
  KGに対する帰納的論理的推論のための構造モデル付きテキスト符号化フレームワークを提案する。 線形化されたクエリ構造とエンティティを、事前訓練された言語モデルを使ってエンコードして、回答を見つける。 2つの帰納的論理推論データセットと3つの帰納的推論データセットについて実験を行った。
  論文  参考訳（メタデータ） (2023-05-23T01:25:29Z)

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

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