🤖 machine learning

Indexing: the Beginning and the End

本論文は、インデックスが入力の末尾に現れる場合に、RNNや線形アテンション・トランスフォーマーのようなマスクされたディープラーニング・アーキテクチャがインデックス・プリミティブを解く上で根本的な限界を持つ一方で、ソフトマックスおよび非マスク線形アテンション・トランスフォーマーはそれを効率的に解けることを示すために「因果的複雑性（causal complexity）」という概念を導入しており、この理論的な分離は実証的な実験によって裏付けられている。

原著者： Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

公開日 2026-07-27

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、物語を読み、その内容に関する質問に答えることができる超スマートなロボットを作ろうとしていると想像してみてください。これは人工知能の世界、具体的には「ディープラーニング（深層学習）」と呼ばれる分野であり、コンピュータが膨大な量のデータを見ることでパターンを学習していく世界です。長い間、この仕事において最も人気のあるロボットは「Transformer（トランスフォーマー）」と呼ばれていました。彼らは、本全体を瞬時にめくって特定の事実を見つけ出すことができる、非常に優秀な司書のような存在です。しかし、一つ問題があります。本が長くなればなるほど、司書はどんどん動作が遅くなり、それを作るには多大なエネルギーと費用が必要になるのです。

これを解決するために、科学者たちは新しいタイプのロボットを発明しました。例えば「RNN」のように（人間と同じように物語を一語ずつ読む）、あるいは「SSM」のように（物語全体を一度に、しかし非常に効率的な方法で読み取ろうとする）といったものです。誰もが問いかけている大きな疑問は、「これらの新しい、より速いロボットたちは、古い、遅いロボットたちと同じくらい賢いのか、それとも隠れた弱点を持っているのか？」ということです。この答えを見つけるために、研究者たちは単に推測するのではなく、ロボットに小さくてトリッキーなパズルを解かせます。これらのパズルは、AIの世界における「算数の宿題」のようなものです。もしロボットが単純な宿題さえ解けないのであれば、それはそのロボットの脳に根本的な限界があることを証明することになります。

「Indexing: the Beginning and the End（インデキシング：始まりと終わり）」と題されたこの論文は、「インデキシング」と呼ばれる非常に具体的で単純なパズルを用いて、これら異なるロボットの構造（アーキテクチャ）の脳をテストしています。このパズルは、一見すると非常に簡単です。 $n$ 個のビット（0と1の文字列）のリストと、どのビットを選ぶべきかを示す数字 $i$ があると想像してください。目標は、単にその特定のビットの値を出力することです。それは、64個のライトスイッチが並んだ列を渡され、数字の「17」を提示されて、「17番目のスイッチはオンですか、それともオフですか？」と聞かれるようなものです。

研究者のアレクサンダー・コザチンスキー、ビセンテ・オパゾ、フェリペ・ウルティアは、ロボットが情報をどのように見るかによって、すべてが変わることを発見しました。彼らは、一部のロボットはこのタスクに非常に速い一方で、他のロボットは、どれほど多くの「思考」の層（レイヤー）を重ねても決して乗り越えられない壁に突き当たることを発見しました。

ここでひねりがあります。この論文は、特定のタイプのロボット（具体的には、情報の処理が「因果的（コーザル）」または「マスク（遮蔽）」された方法で行われるもの、つまり、自分より「後」にあるものを見ることはできず、自分より「前」にあるものしか見ることができないもの）にとって、ビットのリストが長く、インデックス番号が最後に現れる場合、このパズルを解くことは数学的に不可能であることを証明しています。それはまるで、ロボットに長い行列の人々を見せ、「全員の顔を覚えておいてください」と頼んだ後、最後に「42番目の人の名前を教えてください」とささやくようなものです。論文は、RNN、Mamba、およびマスクされた線形アテンションを持つトランスフォーマーといったロボットには「メモリのボトルネック」が存在することを示しています。彼らは、インデックスが到着したときに、その特定のビットを記憶できるほど十分に情報を圧縮することができないのです。著者らは、ロボットが無限の精度（つまり、丸め誤差によって混乱しないこと）を持っている場合でも成立する厳密な数学を用いて、これを証明しました。

しかし、もしシナリオを逆転させれば、物語は変わります。もしインデックス番号がリストの「最初」に現れた場合（ロボットに対して、行列の人々を見せる前に「42番目の人を覚えておいて」と伝える場合）、RNNはスーパーヒーローになります。彼らはこれをたった一ステップで解くことができますが、他のロボット（有名なTransformerを含む）は、それを理解するために少なくとも二ステップを必要とします。

著者たちは単に数学を行っただけでなく、実際のモデルを用いた実験も行いました。彼らは、最大64ビットのリストを用いてこれらのロボットを訓練しました。その結果は、彼らの理論と完璧に一致しました。数学が「失敗するはずだ」と示したロボット（長いリストの最後でビットを探そうとする因果的なもの）は、リストが長くなるにつれて一貫して諦めてしまいました。一方で、数学が「成功するはずだ」と示したロボットは、このタスクを容易に学習しました。

では、教訓は何でしょうか？それは、一つのロボットが他のあらゆる面で「優れている」ということではありません。むしろ、この論文は、異なるアーキテクチャにはそれぞれ異なる「スーパーパワー」と「クリプトナイト（弱点）」があることを明らかにしています。ロボットが情報をどのように処理するか――左から右へ読むのか、すべてを一度に見るのか、あるいは過去を要約しようとするのか――によって、どのパズルを解くことができ、どのパズルによって永遠に立ち往生してしまうのかが決定されるのです。これは、科学者がAIの根本的な限界を理解する助けとなり、次世代のスマートな機械を構築する際に、それらが何ができて、何ができないのかを正確に把握できるようにしてくれるのです。

技術要約：インデキシング（Indexing）の始まりと終わり

問題提起

本論文は、インデキシング・プリミティブ（indexing primitive）という観点から、現代的なディープラーニング・アーキテクチャ（具体的には、リカレントニューラルネットワーク（RNN）、Softmax Transformer、線形アテンション（Linear-Attention）Transformer、および状態空間モデル（SSM））の表現力と情報ボトルネックを調査するものである。

インデキシング・タスクは次のように定義される： $n$ 個のビット $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ のシーケンスと、インデックス $i \in \{1, \dots, n\}$ が与えられたとき、モデルは $i$ 番目のビット $\sigma_i$ を出力しなければならない。著者らは、異なるアーキテクチャの限界を探るために、2つの特定のバリエーションを分析している：

右側インデキシング (Right-Hand Indexing: RHI): インデックス $i$ が入力シーケンスの最後（ビットの後）に現れる。モデルは、先行する $n$ ビットから処理された情報に基づいて $\sigma_i$ を取り出す必要がある。
左側インデキシング (Left-Hand Indexing: LHI): インデックス $i$ が入力シーケンスの最初（ビットの前）に現れる。モデルは、インデックス情報をシーケンスを通じて運び、最後に $\sigma_i$ を取り出す必要がある。

本研究は、「小さな」アーキテクチャ、すなわち $o(1)$ のパラメータを持つもの（シーケンス長 $n$ に対してパラメータ数が一定）であり、かつ無限精度の実数演算が可能な可能性のあるアーキテクチャに焦点を当てている。

手法

著者らは、**因果的複雑性（causal complexity）とVC次元（VC dimension）**に基づく理論的枠組みを用いて、無条件の下界を導出している。

因果的複雑性

因果的（マスクされた）アーキテクチャ（出力 $k$ が入力 $1 $から$ k $にのみ依存する場合）において、著者らは**因果的複雑性**という概念を導入した。これは、入力の履歴（$ x_1, \dots, x_{k-1} $）を、どの程度の次元$ s $まで圧縮できるか（「指紋」関数を介して）を測定するものである。この圧縮された表現と現在の入力$ x_k $から、低い算術複雑性で$ k$ 番目の出力を計算できる必要がある。

重要な洞察: アーキテクチャが低い因果的複雑性（具体的には $o(1)$ ）を持つ場合、情報が即座にアクセス可能でない場合に、必要な過去の情報を圧縮して保持することができない。

理論的ツール

VC次元: 著者らは Kozachinskiy et al. (2025) の手法を応用し、モデルがインデキシング・タスクを解く場合、関連する概念クラスのVC次元は少なくとも $n$ 以上であることを示す。
算術複雑性: 層によって計算される関数（指数関数、算術演算、条件分岐を含む）の算術複雑性を利用して、VC次元を制限する。
無条件の下界: 以前の研究が限定された精度を前提としていたのに対し、これらの結果は無限精度の実数を使用するモデルに対しても成立する。

実験による検証

理論的知見は、 $n \in \{8, 16, 32, 64\}$ のシーケンス長におけるバイナリ・インデキシング・タスクを用いた実験を通じて検証されている。著者らは以下を比較している：

Softmax および線形アテンション Transformer のフル版および因果的（Causal）バリアント。
RNN（具体的には GRU）。
SSM（具体的には Mamba）。
すべてのモデルは、 $n$ が増加するにつれて学習ダイナミクスを観察するために、固定されたハイパーパラメータを用いてゼロから訓練されている。

主な貢献と結果

1. 右側インデキシング (インデックスが最後にある場合)

このシナリオでは、モデルはインデックスを見る前に $n$ 個のビットすべてを処理する。タスクを解くためには、モデルは $n$ ビットの文字列全体を、インデックス・トークンによって処理可能なほど小さな状態へと圧縮しなければならない。

低因果的複雑性アーキテクチャにおける不可能性: 著者らは、 $o(1)$ $o (1)$ の因果的複雑性を持つ定数個（ $O(1)$ $O (1)$ ）の層を持つモデルは、RHIを解くことができないことを証明している。
- 影響を受けるアーキテクチャ: 小規模なRNN、SSM（例：Mamba）、およびマスクされた線形アテンション・トランスフォーマーはすべて $o(1)$ の因果的複雑性を持つ。したがって、これらは無限精度であっても、定数個の層ではRHIを解くことができない。
- 実験による確認: このカテゴリのモデル（1層および多層の因果的線形アテンション、GRU、Mamba）は、 $n$ が増大するにつれてRHIの学習に一貫して失敗し、 $n=64$ で成功率0%に達する。
高因果的複雑性アーキテクチャにおける可能性:
- Softmax Transformer: $O(1)$ のパラメータを持つ単一の層でRHIを解くことができる。これは、グローバルなアテンションを可能にするsoftmaxメカニズムによる高い因果的複雑性に起因する。
- フル・リニアアテンション (Full Linear-Attention): $O(1)$ のパラメータを持つ2層でRHIを解くことができる。
- 実験による確認: これらの構成は、 $n=64$ でも高い成功率を示し、容易にタスクを学習する。

2. 左側インデキシング (インデックスが最初にある場合)

このシナリオでは、インデックスが最初に処理され、該当するビットの位置まで運ばれなければならない。

RNNの優位性: 小規模なRNNは、 $O(1)$ のパラメータを持つ単一の層でLHIを解くことができる。これらは、インデックス $i$ を保持し、 $i$ 番目のビットに遭遇したときに特定の座標を更新できる隠れ状態を自然に維持する。
その他のアーキテクチャの限界:
- SSM および線形アテンション: 1層のSSMも、1層の線形アテンション（マスクあり/なし共に）も、 $o(1)$ のパラメータではLHIを解くことができない。SSMの線形な更新ルールは、情報の取り出しを妨げるような混合（mixing）を避けつつ、インデックスによって決定された特定の位置にビット値を「書き込む」ことを防いでしまう。
- Softmax Transformer: 1層のSoftmax Transformerも、 $o(1)$ のパラメータではLHIに失敗する。
深さによる解決: すべてのアーキテクチャ（SSM、線形アテンション、Softmax Transformerを含む）は、 $O(1)$ のパラメータを持つ2層を与えられればLHIを解くことができる。第1層がインデックスを伝播させ、第2層がビットを取り出す。
実験による確認: 1層のGRUはすべての長さで成功する。1層のMambaおよび線形アテンション・モデルは $n \ge 16$ で失敗する。2層バージョンはすべてのアーキテクチャで成功する。

最小必要層数の要約表

アーキテクチャ	左側インデキシング (LHI)	右側インデキシング (RHI)
フル Softmax	2	1
因果的 Softmax	2	1
フル線形アテンション	2	2
因果的線形アテンション	2	$\omega(1)$ (不可能)
SSM (例: Mamba)	2	$\omega(1)$ (不可能)
RNN	1	$\omega(1)$ (不可能)

(注: $\omega(1)$ は、必要な層の数が定数によって抑えられないこと、すなわち $n$ と共に増大することを意味する。)

意義と主張

本論文は、SSM、RNN、およびマスクされた線形アテンション・トランスフォーマーを含む、低因果的複雑性を持つクラスのアーキテクチャに対する、初のマルチレイヤー・無限精度の下界を提供すると主張している。

アーキテクチャの分離: インデキシング・プリミティブは、アーキテクチャ間の根本的な分離を明らかにする。Softmax Transformerやフル・リニアアテンション・モデルはRHIを効率的に解ける一方で、マスクされたバリアントやSSMは解けない。これは、情報ボトルネックを克服するためのグローバル・アテンション・メカニズムの具体的な役割を浮き彫りにしている。
線形性の役割: 本結果は、SSMの効率性の源としてしばしば称賛される線形な更新ルールが、単一ステップでの非線形な選択的書き込みが求められるLHIタスクにおいては、むしろ足かせとなることを示唆している。
理論と実践の一致: 実験は、理論的な不可能（漸近的下界）が有限の訓練設定においても定性的に現れることを示している。理論的な解が存在する構成はタスクをロバストに学習するが、解を持たない構成は、たとえ小さな $n$ で成功したとしても、シーケンス長が増加すると苦戦する。
謙虚な姿勢: 著者らは、訓練の失敗は不可能性の証明ではなく、また小さな $n$ での成功が漸近的下界と矛盾するものでもないことを明示している。しかし、彼らの理論的下界と経験的パフォーマンスの間の強い相関関係は、因果的複雑性が、取り出し（retrieval）タスクにおける学習可能性の堅牢な予測因子であることを示唆している。

本研究は、トランスフォーマーの表現力に関する分析（これまで関数合成やインダクション・ヘッドに焦点が当てられてきた）を、現代的で効率的な代替モデルへと拡張し、特定の情報取り出しシナリオにおけるそれらの限界に対して厳密な数学的正当性を与えている。