はじめに：なぜ O(n²) が問題なのか
前のページで学んだように、自己アテンション（Self-Attention）は「すべてのトークンが他のすべてのトークンとの関連性を計算する」仕組みであり、計算量は O(n²) で増大します。この問題を解決するために、過去10年間にわたって多くの研究者がさまざまなアプローチを提案してきました。
- 理論の拡散 ― 過去10年の研究は、全対全の自己注意を回避するため、疎化・低ランク化・カーネル化からSSMに至るまで6つの系統へ分岐した
- 壁時計時間の勝利 ― 計算量 O(n) の近似手法が、GPU上の実測速度や長文タスク品質において、最適化された厳密注意 O(n²) に敗北するという現実が発生
- システム × アルゴリズム ― 現在の主戦場は理論的近似ではなく、IO最適化、KVキャッシュのページング管理、分散並列化といった実装レベルの制約突破へ移行
1. 根源的課題：計算量とメモリの「二乗の呪い」
学習時の壁：O(n²) の行列爆発
自己アテンションの数式は softmax(QKT/√d)V です。系列長が伸びるにつれ、中間注意行列（Q × KT で作られる n × n の行列）の保存と計算で O(n²) のメモリが消費され、破綻します。
100人のクラスで「誰と誰が話したか」を記録する出席表は 100 × 100 = 10,000マスです。1,000人になると 1,000,000マス。10,000人なら1億マスになります。これがO(n²)の行列爆発です。
推論時の壁：KVキャッシュの増殖
KVキャッシュ（Key-Value Cache）は、デコーダ型LLM特有の課題です。テキストを生成するとき、新しいトークンを1つ生成するたびに、過去のすべてのトークンの Key と Value のベクトルを保持し続ける必要があります。
_Wall_page8.png)
学習時は行列の計算量が問題ですが、推論時（実際にユーザーに回答を返す時）はKVキャッシュが VRAM帯域と容量を完全に支配します。長文コンテキストと同時リクエストの掛け合わせにより、メモリの断片化と枯渇がサービングの最大障害になります。
2. 全対全アテンションを代替する6つのアプローチ
O(n²) の壁を越えるために、研究者たちは大きく6つの系統のアプローチを生み出してきました。
_Wall_page4.png)
3. アプローチ A & B：疎化と低ランク近似 ― 「見ない」戦略
(A) 注意の疎化（Sparse Attention）
全対全ではなく、見る相手を限定する戦略です。「すべてのトークンと握手する」のではなく、「近くの人と、遠くの数人だけ握手する」イメージです。
1. 局所窓（Sliding Window）
局所的な文脈に限定し、線形化 O(n) を実現。自分の前後数百トークンだけを参照する「窓」を設定します。
2. ランダム接続（Random）
少数の大域的・ランダムな接続を追加。窓の外の情報も少しだけ拾えるようにすることで、長距離依存を補います。
既存の評価資産が厚く、長文エンコード（検索・要約）では依然として有力な選択肢です。Longformer や BigBird が代表例です。
(B) 低ランク近似（Low-rank Approximation）
n × n の注意行列を、より小さな n × k の行列に圧縮する戦略です。
高解像度の写真（n × n ピクセル）を、画質を少し落としてJPEG（n × k サイズ）に圧縮するようなものです。情報は少し失われますが、ファイルサイズ（計算量）は大幅に削減できます。
仮定が成立するタスクでは強力ですが、圧縮率の選択が性能とコストを大きく左右するため、使いどころの見極めが重要です。Linformer が代表例です。
4. アプローチ C：カーネル化・線形化 ― 「数学的ハック」
カーネル化は、自己アテンションの行列の掛け算の順序を変えることで、O(n²) を O(n) に削減する手法です。
数学的なトリック
通常の自己アテンションでは (Q × KT) × V の順で計算しますが、これだと Q × KT の部分で n × n の行列が作られて O(n²) になります。カーネル化では、近似関数を使って Q × (KT × V) の順に変更し、O(n) を実現します。
_Wall_page6.png)
自己回帰推論をRNN形式で定数メモリ化 O(1) し、計算量 O(n) を達成する華麗な手法です。Performer や Linear Transformer が代表例です。
しかし、複雑な言語タスクにおける「精密な想起」の欠如が課題です。Softmax近似による品質劣化と学習安定性の課題が浮き彫りになっています。理論的には美しいが、実用性に課題が残ります。
5. アプローチ D & E：外部メモリとSSM ― アテンションからの脱却
(D) 再帰・外部メモリ
全コンテキストを同時に計算グラフに乗せることを諦め、必要な時に外部から検索・注入する戦略です。
分散・厳密長文処理（Ring Attention）
近似を捨て、厳密注意のままデバイス間でコンテキストを分割。通信と計算をオーバーラップさせ、単一デバイスの限界を超える数百万トークン級の長文を実用化。
参照の外部化（RETRO / Memorizing Transformers）
必要な時に外部コーパスからkNN検索で情報を注入し、パラメータ増ではなく外部データで知識のボトルネックを補う戦略。Cross-Attention Layerを介して参照します。
(E) 注意以外の演算子：SSM / Mamba
アテンションを完全に捨て去り、状態空間モデル（SSM）という全く異なるアーキテクチャで文脈を処理するアプローチです。
Transformer（全対全）
すべてのトークン間で関連性を計算。計算量 O(n²)。品質は高いが、系列が長くなるとコストが爆発。
SSM / Mamba（状態空間モデル）
固定サイズの「状態ベクトル」を更新しながら処理。計算量は O(n) で推論メモリは O(1)。S4から発展し、入力依存の選択機構を持つ Mamba や、長畳み込みの Hyena が台頭。
Transformerは会議を「全録画」して、後で全映像を見返す人です。SSM/Mambaは会議中に「要約ノート」を取り続け、必要な時にノートだけを見返す人です。ノートのサイズは固定なので、会議がどれだけ長くても対応できますが、細かいディテールは失われる可能性があります。
言語特有タスクにおける限界の検証が進行中です。「昔のトークンを正確に想起する」「遠方の文脈同士を比較する」といった精密な処理において、アテンションの万能性にどこまで迫れるかは現在も厳密に検証中です。
6. アプローチ F：実装最適化 ― ゲームチェンジャー
ここまでのアプローチ A〜E は「O(n²) を理論的に減らす」方向でしたが、アプローチ F は全く異なります。O(n²) のまま、ハードウェア上の実行を極限まで高速化するアプローチです。
FlashAttention：近似の放棄
FlashAttentionは、O(n²) の削減を諦め、代わりにHBMとSRAM間の通信（IO）を極限まで削減する手法です。
_Wall_page9.png)
- 厳密な出力を維持したまま、実測時間（Wall-clock time）で圧倒的勝利
- 現在、PyTorch等に標準統合され「まず最初に入れるべき」デファクトスタンダードに
7. 実践的ソリューション：現代LLMのデファクトスタンダード
GQA / MQA（アーキテクチャ側のハック）
KVキャッシュの肥大化に対抗するため、K（Key）と V（Value）のヘッドをグループ化・共有して容量を激減させる手法です。
| 手法 | Q（Query）ヘッド数 | K/V ヘッド数 | KV容量 | 品質 |
|---|---|---|---|---|
| MHA（Multi-Head Attention） | 多数（例: 32） | 多数（例: 32） | 最大 | 最高 |
| GQA（Grouped-Query Attention） | 多数（例: 32） | 少数（例: 8） | 大幅削減 | ほぼ同等 |
| MQA（Multi-Query Attention） | 多数（例: 32） | 1 | 最小 | やや劣化 |
MHAは「全員が自分専用の辞書を持つ」、GQAは「数人のグループで1冊の辞書を共有」、MQAは「全員で1冊だけの辞書を共有」するイメージです。辞書を共有するほど省メモリですが、同時に引きたい時に少し不便になります。
PagedAttention（システム側のハック）
PagedAttentionは、OSのページング技術をKVキャッシュ管理に応用した手法です。
_Wall_page10.png)
- KVキャッシュを非連続メモリブロックに格納
- 無駄な事前割り当てと断片化を排除
- vLLM等の推論サーバーで標準採用
Mistral等の最新モデルは、GQA + SWA（局所窓）+ PagedAttention を組み合わせることで実用的な長文生成を実現しています。
8. Reality Check：理論と現実のギャップ
LRA（Long Range Arena）や SCROLLS といったベンチマークが明らかにしたのは、理論値と実環境のパフォーマンスに大きなギャップがあるという事実でした。
- 「計算量O(n)」≠「GPU上で高速」 ― メモリ階層やIO通信の非効率さにより、近似手法が厳密注意に実測時間で勝てない事態が発生
- 「長文」≠「理解力の向上」 ― 入力を単に広げても、長文向けモデルが強力な短文ベースラインに推論品質で劣るケースが頻発
- 淘汰の教訓 ― 理論の美しさよりも、ハードウェア実装コストとタスク特性の全体整合性がシビアに問われる時代へ
9. イノベーションの波：過去7年間のトレンド変遷
_Wall_page13.png)
10. 実務への適用ガイド：シナリオ別・最適解マトリックス
| ユースケース | 推奨アプローチ | 代表的な技術 |
|---|---|---|
| 長文エンコード（検索・要約・文書QA） | 局所窓 + 少数グローバル注意 | Longformer, BigBird, ETC |
| 汎用LLMの事前学習 | 厳密注意の極限IO最適化（妥協なし） | FlashAttention-2, PyTorch SDPA |
| LLMの推論サービング（多並列デコード） | KVキャッシュ管理 + 注意ヘッド共有 | PagedAttention (vLLM), GQA, SWA |
| 超長文・フロンティア研究（数百万〜） | 分散厳密処理 または 注意の完全代替 | Ring Attention, Mamba (SSM) |
11. 未解決課題と未来への展望
長距離推論の品質保証
コンテキストを広げても中間情報が消失する「Lost in the middle」問題。複数推論ステップを要する複雑な想起の安定化が依然として課題。
KVキャッシュ圧縮の理論化
システム側でのページングだけでなく、トークン情報を圧縮・破棄（Eviction）する際、精度に与える影響の理論的解明と最適化手法の確立。
現在の最適化はGPUのSRAM/HBM構造に強く依存しています。将来的な専用AIチップ（NPU等）に向けた、アルゴリズムとハードウェアの新たなコデザインの必要性が高まっています。
究極の目標は、推論の品質（自己アテンションの精度）を維持しながら、計算量を O(N) または O(N log N) に近づけること。これが実現して初めて、真の「無限コンテキスト」が物理的に可能になります。
元のスライド一覧
クリックで拡大表示できます
_Wall_page1.png)
_Wall_page2.png)
_Wall_page3.png)
_Wall_page5.png)
_Wall_page7.png)
_Wall_page11.png)
_Wall_page12.png)
_Wall_page14.png)
_Wall_page15.png)