Average Attention Transformers and Arithmetic Circuits

技術的サマリー：平均アテンション・トランスフォーマーと算術回路

問題提起
トランスフォーマーの表現力に関する既存の理論的分析は、主に有限アルファベット上の決定問題に焦点を当てており、トランスフォーマーをブール回路クラス（例：$AC^0$、$TC^0$）や論理形式と比較するものに限られていた。これらの結果は言語認識に限定される。本論文は、実数または有理数のベクトル上で動作するシーケンス・ツー・シーケンス関数としてのトランスフォーマーの計算能力に関する理解の欠落を埋めることを目的としている。著者らは、トランスフォーマーエンコーダーの表現力を特徴づけるため、加法、乗法、および符号関数などの演算を用いて半環上で関数を計算する算術回路と直接比較することを目指す。

手法
著者らは、Hao ら（2022 年）に基づく一般化されたトランスフォーマーモデルを任意の半環上で動作するように適応させた。主要な手法上の選択は以下の通りである：

1. モデル定義: 標準的なフィードフォワードネットワークを算術回路に置き換え、アテンション機構が「平均ハードアテンション」（最大アテンション・スコアを持つすべてのベクトルに注目する）を利用する「平均アテンション回路トランスフォーマー」を定義する。
2. 回路ファミリー: 一定の深さと多項式サイズの 3 つの算術回路ファミリーのクラスを分析する：
   • $FNC^0_R$: 有界ファンイン。
   • $FSAC^0_R$: 半無界ファンイン（無界な加法、2 項乗法）。
   • $FAC^0_R$: 無界ファンイン（無界な加法と乗法）。
     これらのクラスは、不連続な演算を処理するために sign 関数で拡張される。
3. シミュレーション構成:
   • 回路からトランスフォーマーへ: 回路をシミュレートするため、著者らは回路のグラフ構造（ゲートとエッジ）をベクトルのシーケンスにエンコードする。各ベクトルはエッジまたはゲートを表し、先行者/後継者のインデックス、ゲートタイプ、および値を含む。
   • アテンション機構: 索引の一致に基づいてベクトルが先行者に注目することを可能にする特定のアテンション関数（$f^{att}_E$ および $f^{att}_V$）を設計する。
   • プーリングと活性化: 先行者からの値を集約するために平均ハードアテンション・プーリングを利用する。重要なのは、ベクトルにエンコードされたゲートタイプに基づいて適切な演算（加法、乗法、または恒等演算）を選択する活性化関数を構築することである。
   • スケーリングの処理: 平均アテンションは結果を $1/k$（$k$ は注目するベクトルの数）でスケーリングするため、構成には先行者を数え、出力を再スケーリングして正しい算術値を回復するメカニズムが含まれる。

主要な結果
本論文は、これらの特定のトランスフォーマーの計算能力と算術回路クラスとの間の正確な対応関係を確立する：

1. 上限: 任意の半環 $R$ に対して、平均アテンション回路トランスフォーマーによって計算される関数は、クラス $FSAC^0_R[\text{sign}]$ に含まれる。これは、活性化関数が同じ回路クラスに制限されている限り、標準的なトランスフォーマー（典型的な平均アテンションを使用するもの）についても成り立つ。
2. 下限（シミュレーション）: 基礎となる半環 $R$ が有理数（$\mathbb{Q}$）の $\mathbb{Z}$-順序環拡張である場合、深さ $K$ の $FSAC^0_R[\text{sign}]$ 回路ファミリーの任意のものに対して、そのファミリー全体をシミュレートできる $2K$ 層のトランスフォーマーが存在する。
   • このシミュレーションは、平均アテンションを使用する無界ファンイン回路で機能する。
   • 半無界ファンイン回路の場合、構成は標準的なドット積アテンションを使用するように適応可能である。
   • 有界ファンイン回路の場合、構成はさらに制限され、左端または右端のハードアテンションを使用できる。
3. 特定の定理:
   • 定理 4.5: 次元 7 で $2K$ 層のトランスフォーマーは、$\mathbb{Q}$ の $\mathbb{Z}$-順序拡張である $R$ に対して、深さ $\le K$ の任意の無界ファンイン $R$-回路をシミュレートできる。
   • 定理 4.11: 次元 9 で $2K$ 層のトランスフォーマーは、任意の $FSAC^0_R[\text{sign}]$-回路をシミュレートできる。

意義と主張
著者らは、機械学習理論と代数的計算の分野を架け橋にすることで、トランスフォーマーの表現力に関する新たな視点を提供すると主張している。

• 理論的同等性: 平均アテンション・トランスフォーマーは、無界な加法、2 項乗法、および符号ゲートを持つ一定深さの算術回路のクラス（$FSAC^0_R[\text{sign}]$）と計算的に同等であることを実証する。
• 限界: 本論文は、この同等性がトランスフォーマーが算術回路（または同等の関数）を活性化関数として使用することに依存していることを明示的に指摘している。フィードフォワードネットワークを備えた標準的なトランスフォーマーは、シミュレーションに必要な 2 つの任意の入力の乗算を本質的に実行できないため、これらの回路をシミュレートできない。
• 非一様性: 著者らは、トランスフォーマーが特定の回路ファミリーをシミュレートできるとしても、これは $FSAC^0_R[\text{sign}]$ のすべての関数が単一のトランスフォーマーによって計算されることを意味しないことを明確にする。なぜなら、回路ファミリーは計算の非一様モデルだからである。
• 将来の可能性: 本論文は、代数的計算における理論的進歩が機械学習理論に、またその逆もまた然りである利益をもたらす可能性を示唆しており、理論的結果が実用的な発展を刺激する可能性があるとしているが、具体的な応用は提案されていない。

この研究は、2026 年 5 月にハノーバー・ライプニッツ大学理論計算科学研究所からプレプリントとして発表されたものである。