論文の概要: When Do Transformers Learn Heuristics for Graph Connectivity?

• arxiv url: http://arxiv.org/abs/2510.19753v1
• Date: Wed, 22 Oct 2025 16:43:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:16.145896
• Title: When Do Transformers Learn Heuristics for Graph Connectivity?
• Title（参考訳）: トランスフォーマーはグラフ接続性のヒューリスティックスを学ぶか?
• Authors: Qilin Ye, Deqing Fu, Robin Jia, Vatsal Sharan,
• Abstract要約: 我々は、直径が$3Lのグラフに対して、$L$層モデルで解く能力があることを証明した。 トレーニングの力学を解析し、学習した戦略が、ほとんどのトレーニングインスタンスがこのモデルのキャパシティ内にあるかどうかにかかっていることを示す。
• 参考スコア（独自算出の注目度）: 33.73385470817422
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformers often fail to learn generalizable algorithms, instead relying on brittle heuristics. Using graph connectivity as a testbed, we explain this phenomenon both theoretically and empirically. We consider a simplified Transformer architecture, the disentangled Transformer, and prove that an $L$-layer model has capacity to solve for graphs with diameters up to exactly $3^L$, implementing an algorithm equivalent to computing powers of the adjacency matrix. We analyze the training-dynamics, and show that the learned strategy hinges on whether most training instances are within this model capacity. Within-capacity graphs (diameter $\leq 3^L$) drive the learning of a correct algorithmic solution while beyond-capacity graphs drive the learning of a simple heuristic based on node degrees. Finally, we empirically demonstrate that restricting training data within a model's capacity leads to both standard and disentangled transformers learning the exact algorithm rather than the degree-based heuristic.
• Abstract（参考訳）: トランスフォーマーはしばしば、不安定なヒューリスティックに頼らず、一般化可能なアルゴリズムを学ばない。 グラフ接続をテストベッドとして使用し、理論的にも経験的にもこの現象を説明する。 我々は, 単純化されたトランスフォーマーアーキテクチャ, アンタングル型トランスフォーマーを考察し, 共役行列の計算能力に匹敵するアルゴリズムを実装した, 直径が3^L$のグラフに対して, L$層モデルで解く能力があることを証明した。 トレーニングの力学を解析し、学習した戦略が、ほとんどのトレーニングインスタンスがこのモデルのキャパシティ内にあるかどうかにかかっていることを示す。 容量内グラフ (diameter $\leq 3^L$) は正しいアルゴリズム解の学習を駆動し、容量外グラフはノード次数に基づく単純なヒューリスティックの学習を駆動する。 最後に、モデルのキャパシティ内でのトレーニングデータ制限が、次数に基づくヒューリスティックではなく、正確なアルゴリズムを学習する標準トランスフォーマーと非整合トランスフォーマーの両方につながることを実証的に示す。

関連論文リスト

• Graph Transformers Dream of Electric Flow [72.06286909236827]
  グラフデータに適用された線形変換器は、正準問題を解くアルゴリズムを実装可能であることを示す。 提案手法は,各アルゴリズムを実装するための明示的な重み設定を示し,基礎となるアルゴリズムの誤差によって構築したトランスフォーマーの誤差を限定する。 我々の研究は、グラフデータのためのTransformerの内部処理を解明するための最初のステップです。
  論文  参考訳（メタデータ） (2024-10-22T05:11:45Z)
• Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning? [69.4145579827826]
  収束ランドスケープの勾配非性アルゴリズムにもかかわらず、回帰損失に高速な流れを示す。 この設定における多層トランスの理論的解析はこれが初めてである。
  論文  参考訳（メタデータ） (2024-10-10T18:29:05Z)
• Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysis [63.66763657191476]
  低ランク計算としての効率的な数値学習と推論アルゴリズムはトランスフォーマーに基づく適応学習に優れた性能を持つことを示す。 我々は、等級モデルが適応性を改善しながら一般化にどのように影響するかを分析する。 適切なマグニチュードベースのテストは,テストパフォーマンスに多少依存している,と結論付けています。
  論文  参考訳（メタデータ） (2024-06-24T23:00:58Z)
• Understanding Transformer Reasoning Capabilities via Graph Algorithms [25.08208816144745]
  我々は、トランスフォーマースケーリングレギュレーションがアルゴリズムの様々なクラスを完璧に解けるかを検討する。 その結果、トランスフォーマーは多くのグラフ推論タスクで優れており、特殊なグラフニューラルネットワークよりも優れています。
  論文  参考訳（メタデータ） (2024-05-28T18:31:14Z)
• Transformers learn in-context by gradient descent [58.24152335931036]
  自己回帰目標におけるトランスフォーマーの訓練は、勾配に基づくメタラーニングの定式化と密接に関連している。 トレーニングされたトランスフォーマーがメザ最適化器となる方法,すなわち,前方通過における勾配降下によるモデル学習方法を示す。
  論文  参考訳（メタデータ） (2022-12-15T09:21:21Z)

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

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