アテンション変種の系統と計算量マップ

変種が乱立した理由：最適化する軸が違う

アテンション変種が数十も生まれたのは、皆が同じ問題を解いているからではありません。最適化する軸が違うから並立します。混乱の元はここにあり、まず軸を分けることが地図化の第一歩です。

Self-Attention の計算 の素朴な実装は、系列長 n・ヘッド次元 d に対して n × n のスコア行列を作ります。ここから派生する不満は三種類あり、それぞれ別の変種群を生みました。

この三軸は直交します。漸近を下げても HBM 往復は残るし、HBM 往復を消しても KV キャッシュ帯域は別問題です。だから三系統は競合せず重ねて使える――これが地図全体を貫く原則です。

基準：full アテンションの計算量

すべての変種は full からの差分で測れます。まず基準を固定します。

S = Q · Kᵀ / √d_k     # n×n スコア行列。時間 O(n²·d)
P = softmax(S)        # 行ごとに正規化。中間メモリ O(n²)
O = P · V             # 出力 n×d。時間 O(n²·d)

時間計算量は O(n²·d)、中間メモリは O(n²)。n が数千を超えると、この二乗項が時間・メモリ双方の支配項になります。変種はこの二乗をどう扱うかで分岐します。

漸近を下げる三系統：疎・低ランク・線形

漸近計算量そのものを下げる系統は、n × n の全結合をどう間引くかで分かれます。詳細は 線形・効率的アテンションの系統 に譲り、ここでは分岐の骨格だけ示します。

• 疎（sparse）：各クエリが見る列を、局所窓＋大域トークン＋乱択に限定する。Longformer・BigBird がこれ。n × n のうち固定本数だけ計算し O(n) 近傍へ。代償は窓設計に依存する到達性――遠い依存が窓外なら拾えない。
• 低ランク（low-rank）：K・V を系列方向に固定次元 k へ射影し、スコア行列を n × k にする。Linformer がこれ。代償は系列の相関が低ランクに乗るという仮定。
• 線形（linear）：softmax の指数核をカーネル特徴写像 φ で近似し、計算順序を (φ(Q)φ(K)ᵀ)V から φ(Q)(φ(K)ᵀV) へ組み替えて O(n) 化する。Performer がこれ。代償は softmax の非線形性の喪失。

三者に共通するのは、近似と引き換えに漸近を下げる点です。出力は full と一致しません。だから「精度の代償をどこから取るか」が選定基準になります。

別レイヤー：FlashAttention は近似しない

ここで軸が切り替わります。FlashAttention は full と出力が厳密に等価で、漸近時間も O(n²·d) のまま。下げるのは中間メモリの実体化と HBM 往復だけです。

for each Q ブロック:
    for each K,V ブロック (SRAM に載せる):
        部分スコアを計算し、オンライン softmax で出力を逐次更新
    出力ブロックだけ HBM に書き戻す   # n×n は一度も実体化しない

タイル化とオンライン softmax で中間 n × n を SRAM 上で消費し、HBM には出力 n × d だけを書きます。追加メモリは O(n²) から O(n) へ落ち、memory-bound だった処理が解放されて実測 2〜4 倍前後。近似がないので既存モデルへ無改造で差し替えられ、疎・線形系とは別レイヤーとして併用できます。

さらに別レイヤー：GQA/MQA は帯域を削る

三つ目の軸は推論時のメモリ帯域です。GQA/MQA は計算量を一切下げません。攻めるのは KV キャッシュ の読み出し量です。

自己回帰の Decode は1トークンずつ進み、毎ステップ KV キャッシュ全体を HBM から読みます。これは帯域律速です。MQA は全 Query ヘッドで K/V を1組に共有し、GQA はグループ単位で共有する中間案。Query ヘッド h・グループ g なら、KV キャッシュと読み出し帯域は約 g/h に縮みます。

年代と分岐：系統樹を文章で

おおまかな時系列で分岐を辿ると、軸が一つずつ追加されてきた歴史が見えます。

• 2017 Transformer：full アテンション。O(n²·d)。これが基準。
• 2019 Sparse Transformer：疎パターンで漸近を下げる最初の波（漸近の軸が開く）。
• 2019 MQA：K/V を1組に共有し Decode 帯域を削る最初の提案（帯域の軸が開く）。
• 2020 Linformer（低ランク）・Performer（線形）・Longformer/BigBird（疎）：漸近を下げる三系統が出揃う。
• 2022 FlashAttention：近似なしで HBM 往復を消す IO-aware 設計（実機入出力の軸が確立）。
• 2023 GQA：MQA の品質劣化を抑える中間案。Llama 2 70B が採用し主流化。
• 2023〜 SSM/Mamba：アテンションを線形再帰で置換し O(n) を狙う、漸近系統の発展形。

並べると、各年の新顔は前の手を否定したのではなく、新しい軸を足したことが分かります。だから現代の長文 LLM は単一の勝者を選ばず、軸ごとに重ねます。

まとめ：三軸で重ねて選ぶ

選定の指針は明快です。まず精度を一切落とさず効く FlashAttention を入れ、Decode 帯域が苦しければ GQA を重ね、それでも長文の漸近が壁なら精度の代償を見極めて 疎/線形系 や SSM を検討する。