論文の概要: The Impossibility of Inverse Permutation Learning in Transformer Models

• arxiv url: http://arxiv.org/abs/2509.24125v1
• Date: Sun, 28 Sep 2025 23:48:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:19.647507
• Title: The Impossibility of Inverse Permutation Learning in Transformer Models
• Title（参考訳）: 変圧器モデルにおける逆置換学習の不可能性
• Authors: Rohan Alur, Chris Hays, Manish Raghavan, Devavrat Shah,
• Abstract要約: 復号器のみの変圧器における逆置換学習の問題について検討する。 任意の深さのデコーダのみの変換器では、このタスクを学習できないことを示す。 これは、チェーン・オブ・シントが推し進める、あるいはより一般的には中間思考のトークンが推論を可能にする別のメカニズムを示唆するかもしれない。
• 参考スコア（独自算出の注目度）: 15.463427361201914
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this technical note, we study the problem of inverse permutation learning in decoder-only transformers. Given a permutation and a string to which that permutation has been applied, the model is tasked with producing the original (``canonical'') string. We argue that this task models a natural robustness property across a variety of reasoning tasks, including long-context retrieval, multiple choice QA and in-context learning. Our primary contribution is an impossibility result: we show that an arbitrary depth, decoder-only transformer cannot learn this task. This result concerns the expressive capacity of decoder-only transformer models and is agnostic to training dynamics or sample complexity. We give a pair of alternative constructions under which inverse permutation learning is feasible. The first of these highlights the fundamental role of the causal attention mask, and reveals a gap between the expressivity of encoder-decoder transformers and the more popular decoder-only architecture. The latter result is more surprising: we show that simply padding the input with ``scratch tokens" yields a construction under which inverse permutation learning is possible. We conjecture that this may suggest an alternative mechanism by which chain-of-thought prompting or, more generally, intermediate ``thinking'' tokens can enable reasoning in large language models, even when these tokens encode no meaningful semantic information (e.g., the results of intermediate computations).
• Abstract（参考訳）: 本稿では,デコーダのみの変換器における逆置換学習の問題について検討する。 置換と、その置換が適用される文字列が与えられた場合、モデルは元の( ``canonical'')文字列を生成する。 このタスクは、長文検索、複数選択QA、テキスト内学習など、様々な推論タスクにまたがる自然な頑健性特性をモデル化する。 任意の深さのデコーダのみの変換器では、このタスクを学べないことを示す。 この結果はデコーダのみのトランスモデルの表現能力に関係しており、ダイナミックスやサンプルの複雑さのトレーニングには依存しない。 逆置換学習が実現可能な一対の代替構成を与える。 第一に、因果注意マスクの基本的な役割を強調し、エンコーダ・デコーダ変換器の表現性と、より一般的なデコーダのみのアーキテクチャとのギャップを明らかにする。 入力を ``scratch tokens' でパディングするだけで、逆置換学習が可能な構造が得られることを示す。 これらのトークンが意味のある意味情報(例えば、中間計算の結果)を符号化していない場合でも、チェーン・オブ・シークレットのプロンプトや、あるいはより一般的には、中間の ‘thinking' トークンが大きな言語モデルでの推論を可能にするメカニズムが提案されるかもしれない。

関連論文リスト

• On the Existence of Universal Simulators of Attention [17.01811978811789]
  注意出力と基礎となる基本行列を同一に再現し、RASPを介してアクティベーション操作を行う方法を提案する。 我々の証明は、これまで学習によってのみ近似することが知られていたアルゴリズムによって達成可能なデータ非依存の解の存在を初めて示すものである。
  論文  参考訳（メタデータ） (2025-06-23T15:15:25Z)
• Algorithmic Capabilities of Random Transformers [49.73113518329544]
  埋め込み層のみを最適化したランダムトランスフォーマーによって、どのような関数が学習できるかを検討する。 これらのランダムなトランスフォーマーは、幅広い意味のあるアルゴリズムタスクを実行することができる。 以上の結果から,これらのモデルが訓練される前にも,アルゴリズム能力がトランスフォーマに存在することが示唆された。
  論文  参考訳（メタデータ） (2024-10-06T06:04:23Z)
• Transformers need glasses! Information over-squashing in language tasks [18.81066657470662]
  復号器のみの変換器における情報伝達について検討する。 変換器への入力の特定のシーケンスは、最終的なトークンにおいて任意にクローズな表現が得られることを示す。 また,デコーダのみのトランスフォーマー言語モデルでは,入力中の特定のトークンに対する感度が低下することを示す。
  論文  参考訳（メタデータ） (2024-06-06T17:14:44Z)
• GEC-DePenD: Non-Autoregressive Grammatical Error Correction with Decoupled Permutation and Decoding [52.14832976759585]
  文法的誤り訂正(GEC)は、通常自己回帰的なシーケンス・ツー・シーケンスモデルで解決される重要なNLPタスクである。 本稿では, アーキテクチャを置換ネットワークに分離する, GEC に対する非自己回帰的アプローチを提案する。 GECの既知の非自己回帰手法よりもネットワークが向上することを示す。
  論文  参考訳（メタデータ） (2023-11-14T14:24:36Z)
• The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
  実際には、トランスフォーマーは「思考の連鎖」や「スクラッチパッド」を使用することで改善できる。 答えはYESであるが、増加量は中間生成量に大きく依存する。 また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置することが示唆された。
  論文  参考訳（メタデータ） (2023-10-11T22:35:18Z)
• Mapping of attention mechanisms to a generalized Potts model [50.91742043564049]
  ニューラルネットワークのトレーニングは、いわゆる擬似様相法によって逆ポッツ問題を解くのと全く同じであることを示す。 また、レプリカ法を用いてモデルシナリオにおける自己意図の一般化誤差を解析的に計算する。
  論文  参考訳（メタデータ） (2023-04-14T16:32:56Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  我々は、訓練データから高品質な生成順序を純粋に検出する、教師なし並列化可能な学習装置を開発した。 エンコーダを非因果的注意を持つトランスフォーマーとして実装し、1つのフォワードパスで置換を出力する。 言語モデリングタスクにおける経験的結果から,我々の手法は文脈認識であり,一定の順序と競合する,あるいはより優れた順序を見つけることができる。
  論文  参考訳（メタデータ） (2021-10-27T16:08:09Z)
• Thinking Like Transformers [64.96770952820691]
  本稿では,プログラミング言語の形式で変換器エンコーダの計算モデルを提案する。 RASPは、トランスフォーマーによって確実に学習できるタスクの解決策をプログラムするのにどのように使えるかを示す。 ヒストグラム、ソート、ダイク言語のためのRASPプログラムを提供する。
  論文  参考訳（メタデータ） (2021-06-13T13:04:46Z)
• Autoencoding Variational Autoencoder [56.05008520271406]
  我々は,この行動が学習表現に与える影響と,自己整合性の概念を導入することでそれを修正する結果について検討する。 自己整合性アプローチで訓練されたエンコーダは、敵攻撃による入力の摂動に対して頑健な(無神経な)表現につながることを示す。
  論文  参考訳（メタデータ） (2020-12-07T14:16:14Z)

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

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