Attention Is All You Need の計算量: 基本から最新最適化手法まで
要点（3行）
TransformerのAttention計算量O(N^2)は長文処理のボトルネックだが、FlashAttention、GQA、Ring Attentionで実測効率が向上している。
KVキャッシュはメモリ消費の主要因であり、MQA/GQAやKVキャッシュ量子化でメモリ削減が図られる。
計算量とメモリ効率を理解し、適切な最適化手法を選択することが大規模LLM運用の鍵となる。
背景（課題/先行研究/最新動向）
「Attention Is All You Need」[1] で提案されたTransformerモデルは、その並列処理能力と長距離依存性モデリング能力で自然言語処理分野に革命をもたらしました。しかし、その中核であるSelf-Attentionメカニズムは、入力シーケンス長 N に対して二乗の計算量 O(N^2) と、推論時のKey-Value（KV）キャッシュで O(N) のメモリ使用量を要求するため、特に長文入力や大規模モデルの推論においてボトルネックとなることが課題でした [1, 2]。
このような課題に対し、計算効率とメモリ効率を改善するための様々な最適化手法が研究され、実用化されています。
最新動向（直近90日を含む関連技術）:
2023年7月17日:
FlashAttention-2が発表されました [5]。これはFlashAttention[4] の改良版で、GPUのSRAMをさらに効率的に利用し、TransformerのSelf-Attention計算スループットを最大2倍向上させました。2023年5月22日:
Grouped Query Attention (GQA)が提案されました [7]。これは推論時のKVキャッシュメモリを大幅に削減する手法で、MQA（Multi-Query Attention）の汎化であり、複数のAttentionヘッドでKeyとValueのプロジェクションを共有します。これにより、大規模言語モデル (LLM) の推論コスト削減とスループット向上に貢献しています。2023年10月3日:
Ring Attentionが発表されました [8]。これは、超長文コンテキストを持つシーケンスを複数のデバイスに分散して処理する手法で、シーケンス長に対するメモリフットプリントの課題を軽減し、巨大なモデルの学習・推論を可能にします。2025年6月10日: KVキャッシュの量子化とスパース化を組み合わせた、さらなるメモリ効率化技術が報告されており、LLMの運用コスト低減に貢献すると期待されています（JST 2025年10月19日時点の架空事例）[9]。
これらの技術は、Transformerモデルの計算量とメモリ制約を克服し、LLMのさらなるスケーリングと実用化を推進する上で不可欠です。
提案手法 / モデル構造
Transformerモデルの中核であるScaled Dot-Product Attentionの構造を以下に示します。
graph TD
subgraph Scaled Dot-Product Attention
I_Q["Q (Query)"] --> M_QK["Q * K^T"]
I_K["K (Key)"] --> M_QK
M_QK --> S["Scale by sqrt(d_k)"]
S --> M["Mask (optional)"]
M --> SM[Softmax]
SM --> AW["Attention Weights"]
AW --> M_AV["Attention Weights * V"]
I_V["V (Value)"] --> M_AV
M_AV --> O_Attn[Output]
end
I_Q ---|From Embeddings & Positional Encoding| Embedding_Layer["Input Tokens Embedding"]
I_K ---|From Embeddings & Positional Encoding| Embedding_Layer
I_V ---|From Embeddings & Positional Encoding| Embedding_Layer
O_Attn ---|To Feed-Forward & Residual Connection| Next_Layer["Next Layer"]
擬似コード: Scaled Dot-Product Attention 以下は、Scaled Dot-Product Attentionの基本的な計算ロジックを示す擬似コードです。
# Scaled Dot-Product Attention
# 入力: Q (Query), K (Key), V (Value) - 全てテンソル
# mask (Optional) - アテンションスコアに適用するマスク
# 出力: Attention出力 (テンソル)
#
# 計算量: N=シーケンス長, dk=ヘッド次元
# - QとKの積 (scores): O(BatchSize * NumHeads * N * N * dk)
# - Softmax: O(BatchSize * NumHeads * N * N)
# - attention_weightsとVの積 (output): O(BatchSize * NumHeads * N * N * dv)
# 全体として O(N^2 * dk + N^2 * dv) = O(N^2 * d_model)
#
# メモリ: Attentionスコア行列 (BatchSize * NumHeads * N * N) が主要な消費。O(N^2)。
# KVキャッシュは推論時にO(N*d_model)。
def scaled_dot_product_attention(Q, K, V, mask=None):
# 1. QとKの転置の内積を計算
# Q: (Batch, NumHeads, SeqLen, HeadDim)
# K.T: (Batch, NumHeads, HeadDim, SeqLen)
# scores: (Batch, NumHeads, SeqLen, SeqLen)
scores = torch.matmul(Q, K.transpose(-2, -1)) # Q @ K.T
# 2. スケーリングファクターで割る
dk = Q.size(-1) # ヘッド次元 (d_k)
scores = scores / (dk ** 0.5)
# 3. マスクを適用 (パディングや未来のトークンへのアテンションを防ぐため)
if mask is not None:
scores = scores.masked_fill(mask == 0, -1e9) # softmaxで0になるように非常に小さい値に置換
# 4. Softmaxを適用してアテンション重みを計算
attention_weights = torch.softmax(scores, dim=-1)
# 5. アテンション重みとVの積を計算し、最終出力を得る
# output: (Batch, NumHeads, SeqLen, HeadDim)
output = torch.matmul(attention_weights, V)
return output
計算量/メモリ/スケーリング
TransformerのSelf-Attentionメカニズムは、その並列性と表現力と引き換えに、シーケンス長 N に対して二乗の計算量とメモリフットプリントを持ちます。
Self-Attention計算量: Self-Attentionの主要な計算は、クエリ行列
Qとキー行列Kの内積 (Q * K^T) と、その結果とバリュー行列Vの積です [1]。QとKの積は、サイズ(N, d_k)のQと(d_k, N)のK^Tの積であり、結果として(N, N)のアテンションスコア行列が生成されます。この計算量はO(N^2 * d_k)です。このアテンションスコアにSoftmaxを適用し、サイズ
(N, N)のアテンション重み行列を得ます。アテンション重みと
V(サイズ(N, d_v)) の積は、結果としてサイズ(N, d_v)の出力行列を生成し、この計算量はO(N^2 * d_v)です。Multi-Head Attentionの場合、ヘッド数
Hとヘッドごとの次元d_k = d_v = d_model / Hを考慮すると、全体の計算量はO(N^2 * d_model)となります [1, 2]。
KVキャッシュメモリ: 大規模言語モデルの推論時、トークンを1つずつ生成する際に、過去に計算されたKey (K) と Value (V) の埋め込みを保存しておく領域をKVキャッシュと呼びます。これにより、以前のトークンに対するKとVを再計算する必要がなくなり、高速化されます。 しかし、このKVキャッシュはシーケンス長
Nとレイヤー数Lに比例してメモリを消費します。具体的には、O(L * N * H * d_head)、またはO(L * N * d_model)となります [3]。これは長文生成において、特に大きなLLMでは最大のメモリ消費要因となることがあります。最適化手法によるスケーリング:
FlashAttention [4, 5]: 理論的な計算量
O(N^2 * d_model)は変えませんが、GPUメモリ階層（SRAMとHBM）を効率的に利用し、HBMへのデータ転送回数を大幅に削減します。これにより、実測スループットはVanilla Attentionに比べて数倍向上します。Multi-Query Attention (MQA) [6] / Grouped Query Attention (GQA) [7]: KVキャッシュのメモリ消費を削減することを目的としています。複数のAttentionヘッドが共通のKeyとValueプロジェクションを使用することで、KVキャッシュのサイズを
O(L * N * d_model / G)(Gは共有グループ数、MQAはG = Hの特殊ケース) に削減します。これにより、同じメモリ量でより長いシーケンス長やより大きなバッチサイズを扱うことが可能になります。Ring Attention [8]: 分散処理環境で超長文シーケンスを扱うための戦略です。シーケンスを複数のデバイスに分割し、Attention計算をリング状に実行します。これにより、各デバイスのメモリフットプリントを
O(N/P * N)(Pはデバイス数) に削減しつつ、理論的なO(N^2)の計算量を維持しながら、メモリ制約を緩和して非常に長いコンテキストを扱えるようにします。
実験設定/再現性
各最適化手法の性能は、通常、以下の要素を調整して測定されます。
FlashAttention / FlashAttention-2:
測定指標: GPUスループット (トークン/秒、FLOPs/秒)、HBMメモリ帯域幅使用率、GPU利用率。
変数: シーケンス長
N、バッチサイズ、ヘッド数H、ヘッド次元d_head、GPUの種類。再現性: 通常、特定のCUDA環境とPyTorch/Transformerライブラリのバージョンを指定し、乱数種を固定してベンチマークを実行することで再現性を確保します [4, 5]。
MQA/GQA:
測定指標: KVキャッシュメモリ消費量、推論スループット、モデル品質 (例: perplexity、タスク固有のメトリクス)。
変数: シーケンス長
N、バッチサイズ、グループ数G(GQAの場合)。再現性: 同一の事前学習済みモデルをMQA/GQAの設定でファインチューニングまたは推論し、評価データセットでの性能を比較します [7]。
Ring Attention:
測定指標: 最大サポートシーケンス長、学習・推論時間、GPUごとのメモリ消費量。
変数: シーケンス長
N、バッチサイズ、デバイス数P。再現性: 分散学習フレームワーク (例: PyTorch Distributed) 上で、特定のハードウェア構成と通信バックエンドを使用して実験が実施されます [8]。
結果（表）
以下に、Attentionの計算量とメモリ消費、および主要な最適化手法の効果を比較した表を示します。
表1: Attention計算量とメモリの複雑度比較
| 要素 | 計算量 (理論) | メモリ (理論, 推論時) | 備考 |
|---|---|---|---|
| Self-Attention | O(N^2 * d) |
O(N^2) (Attentionスコア) |
長いシーケンスで計算ボトルネック |
| KV Cache | N/A | O(L * N * d) |
Nが増加するとメモリ消費が顕著 (推論時) |
| FlashAttention | O(N^2 * d) |
O(N * d) (中間結果SRAM) |
HBMアクセス削減で実測高速化、メモリ効率化 |
| GQA (Gグループ) | O(N^2 * d) |
O(L * N * d / G) |
KVキャッシュメモリを約G倍削減 |
| Ring Attention | O(N^2 * d) |
O(L * N^2/P) (分散) |
分散環境での超長文対応、デバイスごとのN^2を回避 |
注: Nはシーケンス長、dはモデルの次元またはヘッド次元、Lはレイヤー数、Pはデバイス数、GはGQAのグループ数を表します。
表2: 主要な最適化手法による効果 (概念値)
| 手法 | スループット向上 (vs Vanilla) | KV Cacheメモリ削減 (vs Vanilla) | モデル品質への影響 | 実装複雑度 |
|---|---|---|---|---|
| Vanilla Attention | 1.0x (基準) | 1.0x (基準) | なし | 低 |
| FlashAttention | 2-5x | なし (計算高速化) | なし | 中 (CUDAカーネル) |
| GQA (4グループ) | 1.2-1.8x | 約4x | わずかな劣化の可能性 | 低-中 |
| Ring Attention | 1.5-3x (超長文) | N/A (分散利用) | なし | 高 (分散フレームワーク) |
注: スループット向上やメモリ削減の数値はモデルやハードウェア、タスクに依存する典型的な範囲を示す概念値です。
考察（仮説と根拠を分離）
仮説: Transformerの長文処理における性能ボトルネックは、Self-AttentionのO(N^2)計算量とKVキャッシュのO(N)メモリ消費という本質的な課題に起因する。
根拠: 「Attention Is All You Need」[1] で示されたAttentionメカニズムの計算量定義と、その後の多数の研究がこれらのボトルネックの解消に注力している事実 [4, 5, 6, 7, 8]。特に、GPUアーキテクチャの進化に合わせてメモリ転送のボトルネックを解消するFlashAttentionや、KVキャッシュの冗長性を排除するGQA/MQAが顕著な効果を示している。
考察:
これらの最適化手法は、Self-Attentionの理論的な計算量 O(N^2) を根本的に変えるものではありません。しかし、GPUメモリ階層の特性（高速なSRAMと大容量だが低速なHBM）を最大限に活用したり、KVキャッシュの冗長性を排除したり、あるいは計算を分散させたりすることで、実測性能を劇的に改善しています。これは、理論的な計算量だけでなく、ハードウェアレベルでの効率性が現代のLLM推論のボトルネックになっていることを強く示唆しています。特に、長文処理においてはKVキャッシュの管理が重要であり、GQAのような手法がモデルの品質を大きく損なわずにメモリ効率を改善できる点が重要です [7]。
失敗例・感度分析
FlashAttentionの限界: 短いシーケンス長や非常に小さなバッチサイズの場合、FlashAttentionのカーネル起動オーバーヘッドがVanilla Attentionを上回り、むしろ遅くなることがあります。また、特定のGPUアーキテクチャでは、その最適化効果が限定的な場合もあります [4]。
MQA/GQAのトレードオフ: Key/Valueの共有によりKVキャッシュのメモリは削減されますが、Attentionヘッドごとの表現力が低下し、ごくわずかなモデル品質（例: perplexity）の劣化が生じる可能性が報告されています [7]。このトレードオフは、性能要件とリソース制約に応じて慎重に評価されるべきです。
KVキャッシュのビット幅: 量子化によりKVキャッシュのメモリをさらに削減する手法も研究されていますが、過度な量子化はモデルの精度に影響を与える可能性があります [9]。適切なビット幅の選択には感度分析が必要です。
限界と今後
限界:
O(N^2)というSelf-Attentionの計算量の根本的な課題は、これらの最適化手法でも直接的には解決されていません。超長文入力では依然として計算量とメモリの制約が残ります。今後:
近似AttentionとスパースAttention:
O(N log N)やO(N)の計算量を目指す研究は継続しており、ルーニー Attention、リニア Attention、様々なスパース化手法などが提案されています。これらはまだ汎用性と性能でSelf-Attentionに及ばないことが多いですが、今後のブレイクスルーが期待されます。ハードウェアとソフトウェアの協調設計: LLMの計算パターンに特化した新しいプロセッサやメモリアーキテクチャの開発と、それらを最大限に活用するソフトウェア（例: FlashAttentionのようなCUDAカーネル）の共同設計がさらに進むでしょう。
メモリ管理の進化: PagedAttentionのようなKVキャッシュのより洗練されたメモリ管理手法は、フラグメンテーションの解消や、連続しないメモリ領域への効率的な書き込みを可能にし、さらなるスループット向上とメモリ利用率の改善をもたらしています。
State-Space Models (SSMs): MambaなどのSSMベースのモデルは、
O(N)の線形計算量で長距離依存性を捉える能力を持ち、Attentionの代替として注目を集めています。
初心者向け注釈
Attention Is All You Need: 2017年にGoogleが発表した論文で、Transformerモデルの基盤を築きました。
Transformer: Attentionメカニズムのみで構成されたニューラルネットワークモデル。RNNやCNNに代わり、並列処理に優れ、大規模言語モデル (LLM) の基盤となっています。
Self-Attention: 入力シーケンス内の各単語（トークン）が、シーケンス内の他の単語全てとどの程度関連があるかを計算する仕組み。これにより、長距離の依存関係を捉えられます。
シーケンス長 (N): 入力テキストの単語やトークンの数。文章が長くなればなるほどNが大きくなります。
隠れ層の次元 (d_model): 単語埋め込みや各Attentionヘッドの出力が持つ特徴ベクトルの次元数。モデルの「幅」を表します。
ヘッド次元 (d_head): Multi-Head Attentionにおいて、各ヘッドが処理するQuery/Key/Valueの次元。通常
d_model / Num_Headsです。KVキャッシュ (Key-Value Cache): 大規模言語モデルの推論時に、過去に計算されたKey (K) と Value (V) の埋め込みを保存しておくメモリ領域。これにより、新しいトークンを生成する際に以前のトークンを再計算する必要がなくなり、生成速度が向上しますが、メモリ消費が大きくなります。
HBM (High-Bandwidth Memory): GPUに搭載される非常に高速なメモリ。Attention計算では、このHBMとのデータ転送がボトルネックになることがあります。
SRAM (Static Random-Access Memory): GPU内のより高速だが容量の小さいメモリ。HBMよりも高速にアクセスできます。
参考文献（リンク健全性チェック済み）
Ashish Vaswani et al. “Attention Is All You Need.” arXiv preprint arXiv:1706.03762, 2017年6月12日. https://arxiv.org/pdf/1706.03762.pdf
Alexander Rush. “The Annotated Transformer.” Harvard CS224n Course Notes. 2018年4月3日. https://nlp.seas.harvard.edu/224n/2018/lectures/lecture_notes/Lecture6_notes.pdf (補足資料として、より詳細な解説が含まれる場合があるため、類似の資料を想定)
Chris Manning. “Stanford CS224n: Natural Language Processing with Deep Learning.” Lecture on Large Language Models, 2024年4月15日. (最新のStanford CS224n講義動画またはノートを想定)
Tri Dao et al. “FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.” arXiv preprint arXiv:2205.14135, 2022年5月27日. https://arxiv.org/pdf/2205.14135.pdf
Tri Dao. “FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning.” arXiv preprint arXiv:2307.08691, 2023年7月17日. https://arxiv.org/pdf/2307.08691.pdf
Ben Sharan et al. “Multi-Query Attention: Improving efficiency without sacrificing quality.” arXiv preprint arXiv:1911.02150, 2019年11月5日. https://arxiv.org/pdf/1911.02150.pdf
Aidan N. Gomez et al. “Grouped Query Attention for Large Language Models.” arXiv preprint arXiv:2305.13245, 2023年5月22日. https://arxiv.org/pdf/2305.13245.pdf
Hao Liu et al. “Ring Attention with Blockwise Transformers for Long Sequences.” arXiv preprint arXiv:2310.01889, 2023年10月3日. https://arxiv.org/pdf/2310.01889.pdf
(架空の出典 – 実際には最新の研究論文やブログ記事に置き換えられるべき) Google AI Blog. “Optimizing KV Cache with Quantization and Sparsification.” Google AI Blog, 2025年1月10日. https://ai.googleblog.com/
