論文の概要: Indexing: the Beginning and the End

• arxiv url: http://arxiv.org/abs/2607.22361v1
• Date: Fri, 24 Jul 2026 14:42:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-27 20:58:57.155322
• Title: Indexing: the Beginning and the End
• Title（参考訳）: インデックス:開始と終了
• Abstract要約: インデクシングプリミティブのレンズを用いて,現代のディープラーニングアーキテクチャにおける情報ボトルネックについて検討する。 このプリミティブでは、入力は$n$ビットと、インデックスと呼ばれる1つの整数$i$から$n$で構成されている。 因果複雑性の低いアーキテクチャは、インデックスが現れるとき、任意の一定の数の層においてインデックス化プリミティブを解くことができないことを示す。
• 参考スコア（独自算出の注目度）: 45.94629852512322
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study information bottlenecks in modern deep-learning architectures -- RNNs, softmax transformers, linear-attention transformers and state-space models -- through the lens of the indexing primitive. In this primitive, the input consists of $n$ bits and one integer $i$ from $1$ to $n$ called the index, and the output equals the value of the $i$-th bit. We introduce causal complexity for masked architectures. We show that architectures with low causal complexity cannot solve the indexing primitive in any constant number of layers when the index appears at the end of the input. In particular, this limitation applies to low-parameter RNNs, SSMs and masked linear-attention transformers. In contrast, small softmax transformers can solve it in one layer, while non-masked linear-attention transformers can solve it in 2, which separates them from their masked counterparts. In turn, when the index appears at the beginning, we show that small RNNs are capable of solving this task in 1 layer, while all the other architectures require 2. All our impossibility results are unconditional and apply even to models that employ infinite-precision real arithmetic. Moreover, experiments for up to $n=64$ qualitatively align with our theory: configurations with low-parameter theoretical solutions learn the indexing task easily, while configurations that do not admit such theoretical solutions struggle to learn as the sequence length grows.
• Abstract（参考訳）: インデクシングプリミティブのレンズを通じて、現代のディープラーニングアーキテクチャ(RNN、ソフトマックストランスフォーマー、リニアアテンショントランスフォーマー、ステートスペースモデル)における情報ボトルネックについて検討する。 このプリミティブでは、入力は$n$ビットと、インデックスと呼ばれる$$$から$n$までの整数$i$で構成され、出力は$i$-th bitの値と等しい。 マスキングアーキテクチャに因果複雑性を導入する。 因果複雑性の低いアーキテクチャでは、インデックスが入力の最後に現れるとき、任意の一定の数の層でインデックス化プリミティブを解くことはできないことを示す。 特に、この制限は、低パラメータRNN、SSM、マスク付きリニアアテンショントランスにも適用される。 対照的に、小さなソフトマックス変圧器は1層で解けるが、非マス付きリニアアテンション変圧器は2層で解ける。 すると、インデックスが最初に現れると、小さなRNNが1層でこのタスクを解くことができるのに対し、他のすべてのアーキテクチャは2。 不可能な結果はすべて無条件であり、無限精度実算術を用いるモデルにも当てはまる。 さらに、最大$n=64$の実験は、我々の理論と定性的に一致している: 低パラメータ理論解を持つ構成は、索引付け課題を学習しやすく、一方、そのような理論解を認めない構成は、列長が大きくなるにつれて学習するのに苦労する。

関連論文リスト

• Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
  Implicit Chain-of-Thought (ICoT) は、隠れた状態の中で中間段階を内部化するモデルを訓練する。 Log-ICoTはシンキングトークンを一度に削除し、$k$のリニアから対数へのステージ数を削減します。 多層変圧器の実験により理論が確認され、より深い層に段階的に推論がどのように吸収されるかが可視化される。
  論文  参考訳（メタデータ） (2026-05-27T15:17:06Z)
• InfoFlow: A Framework for Multi-Layer Transformer Analysis [28.731784494689276]
  多層変圧器は単層変圧器と基本的に異なる近似能力を有する。 我々は多層トランスフォーマーのためのフレームワークInfoFlowを提案する。
  論文  参考訳（メタデータ） (2026-05-18T06:38:39Z)
• When Attention Beats Fourier: Multi-Scale Transformers for PDE Solving on Irregular Domains [0.0]
  msatは複素幾何学問題に対する最先端の一般化を実現する。 textbfMulti-Scale Attention Transformer (msat)は、ソリューション履歴をトークンシーケンスとしてエンコードし、エンドツーエンドにトレーニングする。
  論文  参考訳（メタデータ） (2026-05-08T15:23:13Z)
• Provably Learning Attention with Queries [15.606567893781367]
  出力にブラックボックスアクセスを持つトランスフォーマーに基づくシーケンスモデルを学習する際の問題点について検討する。 この設定では、学習者は任意のベクトル列でオラクルを適応的にクエリし、対応する実数値出力を観察することができる。
  論文  参考訳（メタデータ） (2026-01-23T16:28:22Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  我々は,2層変換器が$n$-gramのマルコフ連鎖データ上でICLを実行するためにどのように訓練されているかを検討する。 クロスエントロピー ICL 損失に対する勾配流が極限モデルに収束することを証明する。
  論文  参考訳（メタデータ） (2024-09-09T18:10:26Z)
• Separations in the Representational Capabilities of Transformers and Recurrent Architectures [27.783705012503237]
  我々は,トランスフォーマーとRNNの表現能力の違いを,実践的妥当性のいくつかのタスクで分析する。 対数幅の一層変換器がインデックス検索を行うのに対し、RNNは線形サイズを隠蔽する必要があることを示す。 また、ログサイズの2層トランスは、最寄りのアルゴリズムをフォワードパスで実装できることを示す。
  論文  参考訳（メタデータ） (2024-06-13T17:31:30Z)
• Transformers as Support Vector Machines [54.642793677472724]
  自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。 勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。 これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
  論文  参考訳（メタデータ） (2023-08-31T17:57:50Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。 また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
  論文  参考訳（メタデータ） (2020-06-08T18:30:12Z)

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

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