線形アテンションと効率的アテンションの系統

二乗の壁はどこから来るのか

Self-Attention の計算 の核は次の式です。

Attention(Q, K, V) = softmax(QKᵀ / √d) · V

系列長 n、ヘッド次元 d のとき、QKᵀ は n × n のスコア行列になります。これに行方向 softmax をかけ、V を掛けて出力 n × d を得ます。計算量は O(n²·d)、メモリは中間行列ぶんの O(n²)。d が定数なら、二乗の主因は系列長 n です。

問題の本質は softmax が Q と K を分離できない形 にあることです。もし出力が (QKᵀ)V という素の積なら、行列積の結合則で Q(KᵀV) と組み替えられます。KᵀV は d × d なので、系列長について線形になります。ところが間に softmax の指数 exp(qᵢ·kⱼ) が挟まると行ごとの正規化が絡み、この組み替えができません。効率的アテンションの全系統は、この一点をどう回避するかで分類できます。

線形アテンション：カーネル特徴写像で結合則を取り戻す

softmax アテンションの各出力行は次のように書けます。sim(q, k) = exp(q·k / √d) という類似度を重みにした V の加重平均です。

outᵢ = Σⱼ sim(qᵢ, kⱼ) · vⱼ / Σⱼ sim(qᵢ, kⱼ)

ここで指数核 sim(q, k) を、ある特徴写像 φ の内積 φ(q)·φ(k) で置き換えられたとします。すると分子は次のように変形できます。

分子 = Σⱼ (φ(qᵢ)·φ(kⱼ)) vⱼ = φ(qᵢ) · ( Σⱼ φ(kⱼ) vⱼᵀ )

右辺の Σⱼ φ(kⱼ) vⱼᵀ は 全クエリで共通の m × d 行列（m は特徴次元）で、n 本のクエリそれぞれで作り直す必要がありません。分母の Σⱼ φ(kⱼ) も同様に一度だけ計算すれば済みます。計算量は (φ(Q)φ(K)ᵀ)V の O(n²) から φ(Q)(φ(K)ᵀV) の O(n·m·d) へ落ち、n について 線形 になります。これは SVM のカーネルトリック と逆向きの発想で、明示的な特徴写像を与えてカーネルを内積に戻すものです。

標準: (Q Kᵀ) V    → n×n を作る → O(n²·d)
線形: φ(Q) (φ(K)ᵀ V) → m×d 状態を作る → O(n·m·d)

Performer の FAVOR+：指数核を不偏に乱択近似する

Performer はこの φ を 乱択特徴（random features） で構成します。FAVOR+（Fast Attention Via positive Orthogonal Random features）は、exp(q·k) を満たす φ を確率的に作る点が肝です。要点は2つあります。

第一に 正値性（positive features）。素朴な三角関数ベースの乱択特徴は内積の推定値が負になり得て、softmax 重みが負になると数値が破綻します。FAVOR+ は指数関数ベースの正値特徴を使い、推定が常に非負になるよう設計します。これにより exp(q·k) の 不偏推定（期待値が真値に一致）を、分散を抑えつつ得られます。

第二に 直交性（orthogonal features）。乱択射影に使う行をランダムな直交行列から取ると、推定の分散が下がり、少ない特徴次元 m で精度が出ます。m を d·log d 程度に取れば実用的な近似になるとされます。

線形アテンションには副産物があります。Σⱼ φ(kⱼ) vⱼᵀ という m × d 状態を逐次更新していけば、自己回帰生成を再帰（RNN 的な定数メモリ）で回せる ことです。各ステップで n 個の過去 K/V を見直す代わりに、固定サイズの状態を更新するだけで済みます。この「線形アテンション ≒ 状態を持つ再帰」という等価性は、状態空間モデル / Mamba の系譜と深くつながります。

Linformer：スコア行列を低ランクと見なす

別の攻め方が 低ランク射影 です。Linformer は経験的観察に立脚します。学習済み Transformer のアテンション行列 softmax(QKᵀ) は、特異値の大半が小さく 実効ランクが系列長よりずっと低い という観察です。ならば n × n をまるごと持つ必要はありません。

具体的には、K と V を系列方向に 固定次元 k へ線形射影 します（k は n に依存しない定数）。

K' = E·K   (n×d → k×d、E は学習する k×n の射影行列)
V' = F·V   (同上)
out = softmax(Q K'ᵀ / √d) · V'   ← スコア行列は n×k になる

スコア行列が n × k に縮むため、計算量・メモリとも O(n·k·d)、k が定数なら n について 線形 です。softmax 自体は厳密に計算する点が Performer と異なります。近似が入るのは「K・V の系列情報を k 次元に圧縮しても本質を失わない」という低ランク仮定の側です。

疎アテンション：注目先を構造で間引く

三つ目は 疎アテンション。softmax も核近似も変えず、n × n のうち 計算するエントリ自体を限定 します。鍵は「実用上、各トークンが本当に全トークンを見る必要はめったにない」という観察です。

Longformer は3種の注目を組み合わせます。(1) 局所窓：各トークンは前後 w トークンのみ参照（畳み込み的）。(2) 拡張窓（dilated）：窓に飛び飛びの穴を空け、層を重ねて受容野を広げる。(3) 大域トークン：[CLS] など少数の特別トークンだけは全トークンと相互に注目する。局所だけだと遠距離依存が伝わらないため、大域トークンが情報のハブになります。

BigBird はこれに 乱択注目 を加え、(局所窓 ＋ 大域トークン ＋ ランダムな少数リンク) の3点セットにします。乱択リンクを足す理由は理論的で、ランダムグラフは少数の辺で全頂点間の到達距離を短く保てる（小世界性）ため、任意の2トークンが数ホップで届く ことが保証しやすくなります。BigBird はこの構成で、疎アテンションでも完全アテンションと同じ表現能力（チューリング完全性）を理論的に持つことが示されています。

FlashAttention との違い：近似か、等価か

混同を避けるべきが FlashAttention との違いです。FlashAttention はタイル化とオンライン softmax で 計算順序と置き場所だけ を変え、出力は標準 softmax と 数学的に厳密に等価 です。漸近計算量は O(n²) のまま（メモリは O(n) に下げる）で、定数倍とメモリ往復を削ります。

対して本稿の3系統は、漸近計算量そのものを O(n)（近似）へ下げる代わりに、出力が標準と一致しません。レイヤーが違うため両者は競合せず、線形/疎アテンションの内部 softmax を FlashAttention 流に実装する、といった併用も可能です。

まとめ：どの仮定に賭けるかで選ぶ

効率的アテンションの3系統は、いずれも「全トークンの厳密な総当たり softmax」を諦める代わりに線形コストを得ます。違いは 何を犠牲にするか です。

実務では、まず厳密等価な FlashAttention で定数倍を削り切り、それでも系列長が手に負えない領域で初めて近似系を検討するのが安全です。近似を入れるなら、対象タスクの注目が 鋭いのか平坦か・低ランクか高ランクか・局所か大域か を見極め、賭ける仮定が成り立つ系統を選ぶこと。アテンションの数理的な土台は Self-Attention の計算 と Multi-Head Attention、線形アテンションの再帰的等価物は 状態空間モデル / Mamba で押さえると、長文モデリングの選択肢が一枚の地図につながります。