# 1. Self-Attention 機制的基礎與瓶頸
## 1.1. Self-Attention 的定義

Self-Attention 是 Transformer 架構中的核心模組，其目的是計算序列中每個位置對其他位置的關注程度，並據此加權組合輸入表示。

其數學形式為：

$b^1 = \sum_{i=1}^{N} \alpha'_{1,i} v^i = \sum_{i=1}^{N} \frac{\exp(q^1 \cdot k^i)}{\sum_{j=1}^{N} \exp(q^1 \cdot k^j)} v^i$。

其中，$q^1$ 為第一個位置的 query 向量，$k^i$ 為第 $i$ 個位置的 key 向量，$v^i$ 為第 $i$ 個位置的 value 向量，$\alpha'_{1,i}$ 為經 softmax 正規化後的注意力權重。

## 1.2. Attention Matrix 與計算流程

若序列長度為 $N$，則需對每對 query-key 組合計算內積，形成大小為 $N \times N$ 的 Attention 矩陣：

$A = QK^T$。

整體 Self-Attention 計算流程為：

$O = \text{softmax}(QK^T)V$。

其中，$Q \in \mathbb{R}^{N \times d}$ 為query 矩陣，$K \in \mathbb{R}^{N \times d}$ 為key 矩陣，$V \in \mathbb{R}^{N \times d'}$ 為value 矩陣，$O \in \mathbb{R}^{N \times d'}$ 為最終輸出。

## 1.3. 時間與空間複雜度分析

Self-Attention 的運算與儲存成本為二次方級數，具體複雜度如下：

$QK^T$：$O(N^2 d)$。

$\text{softmax}(QK^T) V$：$O(N^2 d')$。

整體時間與空間複雜度為：

$O\left((d + d')N^2\right)$。

## 1.4. 實際應用與限制

Self-Attention 可靈活建模長距依賴，並廣泛應用於語言與影像模型。然而，當序列長度 $N$ 增大時，其 $O(N^2)$ 的成本將造成訓練與推論上的瓶頸。因此，各種近似與替代機制陸續被提出。

# 2. 提升效率的經典變體
## 2.1. Local Attention / Truncated Attention
在完整 Self-Attention 中，每個位置需與所有位置互動，造成 $O(N^2)$ 複雜度。Local Attention 限制每個位置只與鄰近範圍內的若干位置互動，超出範圍的權重設為 0：

1.原 Attention 矩陣大小為 $N \times N$

2.限制互動範圍為 $w$ 時，每列最多保留 $w$ 項，其餘設為 0

優點：

1.計算與儲存複雜度降為 $O(Nw)$，其中 $w \ll N$

2.適用於鄰近資訊為主的任務（如語音、影像）

## 2.2. Stride Attention
Stride Attention 每隔固定距離取一個位置做注意力互動，例如每 $s$ 個 key 做一次 attention：

1.降低注意力密度，提高計算效率
2.可與 Local Attention 結合交錯使用

其 Attention 矩陣具有規律性稀疏結構，可視為類似卷積的滑動視窗抽樣。
## 2.3. Global Attention
在序列中加入少數 global tokens，例如 $g$，並令其與所有其他 token 互相注意：

1.$g$ attend 所有 token 並收集全域資訊

2.所有 token 也 attend $g$ 以獲得全域上下文

此機制讓全域資訊透過少量節點傳播，並降低 $O(N^2)$ 的互動需求。
## 2.4. Skip Some Calculations with Human Knowledge
觀察 Self-Attention 中許多位置之間的關聯性極小，可視為近乎無關：

1.對 attention matrix 中小於閾值的項目直接設為 0

2.僅保留對結果有顯著影響的注意力路徑

這種稀疏化策略在不影響準確率的前提下大幅減少計算量。
## 2.5. Multi-head Patterns
在 Multi-head Attention 中，每個 head 可以採用不同的注意力模式：

1.一個 head 使用 Local Attention

2.一個 head 使用 Stride Attention

3.一個 head 使用 Global Attention

這種設計擁有「專精 + 多樣」的結構，增強模型捕捉多尺度依賴的能力。

# 3. 基於知識與結構的稀疏注意力
## 3.1. Clustering-based Attention（Reformer）
傳統 Self-Attention 計算所有 $q_i \cdot k_j$，為降低計算量，可將相似的 $q$ 和 $k$ 分群，只在同群內進行注意力運算。Reformer 模型提出使用 LSH（Locality-Sensitive Hashing）進行分群，使每個 query 只 attend 同群中的 key：

1.Attention 僅在子集合中計算，複雜度由 $O(N^2)$ 降至 $O(N \log N)$

2.分群過程為近似運算，可接受一定誤差

## 3.2. Learnable Patterns（Sinkhorn Sorting）
與手動設計注意力遮罩不同，Learnable Pattern 透過模型自動學習注意力結構：

1.使用 Sinkhorn Network 對序列進行軟排序（soft permutation）

2.學得之排序可用來指引稀疏注意力的配置

優點：

1.遮罩結構具備可學性，可動態調整

2.結合 differentiable sorting 機制，支援端到端訓練

## 3.3. Representative Key（Linformer）
觀察發現 Attention Matrix $A = QK^T$ 在實務中為低秩矩陣。Linformer 利用此性質對 $K$ 和 $V$ 進行線性壓縮：學習投影矩陣 $E \in \mathbb{R}^{k \times N}$，將 $K$ 和 $V$ 壓縮至 $k$ 維

改寫公式如下：

$A = QK^T \approx Q (EK)^T$。

$O = \text{softmax}(QK^T) V \approx \text{softmax}(Q (EK)^T) (EV)$。

其中，$k \ll N$，故能將計算與記憶體複雜度降為 $O(Nk)$。

這一類方法強調以結構或可學方式對 Attention Matrix 進行 sparsification，核心理念為：

1.不需對所有位置計算關聯性

2.保留資訊傳遞關鍵路徑即可維持性能

3.同時可達成時間與記憶體效率的大幅提升

# 4. 重構計算順序的線性注意力
## 4.1. 傳統計算順序的複雜度瓶頸
在標準 Self-Attention 中，計算 Attention Matrix 需耗費大量計算與記憶體：

$O = \text{softmax}(QK^T)V$。

此處 Attention Matrix 的大小為 $N \times N$，當序列長度 $N$ 趨大時，複雜度為：

$O((d + d')N^2)$。

為克服此問題，可透過調整矩陣乘法順序以降低成本。
## 4.2. 改變乘法順序的重構方法
線性注意力的基本概念為將 softmax 前的內積計算順序改寫為：

$O \approx (V K^T) Q$。

此處將原本先計 $QK^T$ 的順序，改為先計 $VK^T$。優點為：

1.無需建構完整 $N \times N$ 的中間矩陣

2.若不含 softmax，則可實現計算複雜度為 $O(d' d N)$ 的線性縮放

## 4.3. Kernel Approximation — Performer 模型
Performer 引入正定核函數 $\phi(\cdot)$，以近似 softmax 的 exponent dot product：

$\exp(q \cdot k) \approx \phi(q)^T \phi(k)$。

可將注意力輸出改寫為：

$O(q) = \frac{\sum_{i=1}^{N} \phi(q)^T \phi(k^i) v^i}{\sum_{j=1}^{N} \phi(q)^T \phi(k^j)}$。

透過重新排列與合併項，進一步轉換為：

$O(q) = \frac{\phi(q)^T \left( \sum_{i=1}^{N} \phi(k^i) v^i \right)}{\phi(q)^T \left( \sum_{i=1}^{N} \phi(k^i) \right)}$。

## 4.4. 預先計算共享記憶向量
為了提升效率，將以下兩項提前計算：

$S = \sum_{i=1}^{N} \phi(k^i) v^i$。
$Z = \sum_{i=1}^{N} \phi(k^i)$。

則每個輸出可表為：

$O(q) = \frac{\phi(q)^T S}{\phi(q)^T Z}$。

優點：

1.對所有 query 可共用 $S$ 與 $Z$

2.計算複雜度為 $O(Nd + dN_q)$，其中 $d$ 為投影維度，$N_q$ 為 query 數

## 4.5. 時間與空間效率比較
| 方法 | 複雜度 | 儲存需求 |
| ------------ | ------------ | ---------- |
| 原始 Attention | $O(N^2 d)$ |$O(N^2)$ |
| 線性 Attention | $O(Nd)$ | $O(Nd)$ |

# 5. 結構簡化：捨棄 query 和 key
## 5.1. Synthesizer — Attention 不一定需要 $q$ 與 $k$
傳統 Attention 依賴 $q \cdot k^T$ 進行相似度計算。然而，Synthesizer 模型質疑此假設，並提出：

為何 Attention 權重 $\alpha_{i,j}$ 必須來自 $q_i \cdot k_j$？
是否可以直接生成（synthesize）注意力矩陣本身？

Synthesizer 的基本想法：
將注意力矩陣視為可訓練的參數，或透過神經網路學出來，而非內積計算。

$\alpha = \text{Synthesizer}(X)$。

其中 $\alpha \in \mathbb{R}^{N \times N}$ 可能來自：

1.一個前饋神經網路輸出

2.固定參數模板

3.位置編碼的線性變換

優點：

1.無需計算 $q$ 與 $k$

2.可直接控制注意力結構

3.減少計算量與參數量

Synthesizer 的核心精神是：「關注結構可由學習主動生成，而非被動計算」
## 5.2. Attention Matrix 的完全解耦設計
與傳統 self-attention 的全矩陣計算不同，Synthesizer 中的 $\alpha_{i,j}$：

1.可為學習型常數矩陣

2.可為相對位置函數的結果

3.可透過 token 本身產生（而非 inner product）

這表示：

$b^i = \sum_{j=1}^{N} \alpha_{i,j} v^j \quad \text{。但 } \alpha_{i,j} \text{ 並非由 } q^i \cdot k^j \text{ 決定}$。

理論觀點與結論：

1.Synthesizer 擴展了 Self-Attention 的設計空間

2.計算更快、控制性更高

3.雖略降精度，但可在速度與資源有限場景中應用

# 6. 完全去注意力：Attention-free 架構
## 6.1. FNet — 使用傅立葉變換取代 Attention
FNet 提出以傅立葉轉換（Fourier Transform）取代 Attention 機制，用於混合序列中不同位置的資訊。核心操作：對輸入序列 $X \in \mathbb{R}^{N \times d}$ 應用雙維傅立葉轉換：

$X' = \text{Re}(\mathcal{F}_\text{row}(\mathcal{F}_\text{col}(X)))$。

其中，$\mathcal{F}_\text{col}$ 為對每一列進行傅立葉轉換（即跨時間位置），$\mathcal{F}_\text{row}$ 為對每一行進行傅立葉轉換（即跨特徵維度），$\text{Re}(\cdot)$ 為取實部作為輸出（忽略虛部）。

特點：

1.完全不使用 attention 或權重計算

2.操作為固定變換，無需額外學習參數

3.複雜度為 $O(N \log N)$，顯著快於 $O(N^2)$ 的 Self-Attention

## 6.2. gMLP / MLP-Mixer — 全 MLP 架構替代 Attention
MLP-Mixer 架構，將序列處理分為兩個子模組：

1.Token-mixing MLP：在時間維度上打散與混合位置資訊

2.Channel-mixing MLP：在通道維度上處理特徵抽取

對於輸入 $X \in \mathbb{R}^{N \times d}$，使用如下形式：

$Y = \text{MLP}_\text{channel}(\text{MLP}_\text{token}(X))$。

gMLP 改進引入 gating 機制，稱為 Spatial Gating Unit，用來控制位置間的交互：

$Y = U \odot \sigma(V W)$。

其中，$U, V$ 為經過線性投影後的中間張量，$W$ 為位置混合參數，$\odot$ 為逐元素乘法。

優點：

1.完全使用 MLP 模組

2.易於部署於高效硬體（如 TPU）

3.計算流程線性，無注意力矩陣開銷

## 6.3. 設計觀點與啟示

1.Attention 並非序列建模的唯一選擇

2.固定變換（如 Fourier）與位置感知 MLP 皆可取代其效果

3.在資源有限、推論延遲敏感場景下為良好選擇

# 7. Attention 設計策略總覽與比較
## 7.1. 各類 Attention 優化策略分類
| 策略類別 | 代表方法／模型 | 核心思路 |
| ------------------ | ---------------------------------- | ---------------------------------- |
| Human Knowledge | Local Attention, Big Bird | 透過人為設定稀疏結構（局部、全域、隨機） |
| Clustering | Reformer | 使用哈希或分群，將計算限制於同群內 |
| Learnable Pattern | Sinkhorn Sorting Network | 學習出排序後再施加稀疏遮罩 |
| Representative Key | Linformer | 壓縮 Key/Value，低秩近似 Attention Matrix |
| 改變計算順序（線性注意力） | Performer, Linear Transformer | 重新排列乘法順序，結合核函數實現線性計算 |
| 全新架構（無 attention） | Synthesizer, FNet, gMLP, MLP-Mixer | 完全捨棄 query-key 機制，以其他方式混合資訊 |

## 7.2. 模型效能與效率比較（LRA Benchmark）
根據 Long Range Arena（LRA）基準測試，各方法在處理長序列任務時的精度與推論速度分布如下：

1.Transformer / Big Bird：精度高，但推論速度慢，計算與記憶體開銷大

2.Performer / Linformer：維持良好準確率，並顯著提升推理速度

3.Synthesizer / FNet / MLP-Mixer：精度略低，但擁有最佳速度與資源效率

此比較顯示，不同應用場景下可依據精度需求與資源限制進行選擇。

## 7.3. 技術總結
1.若需保持精度：Big Bird、Performer 為較佳選擇

2.若需極速運算：FNet、gMLP 更具優勢

3.若需模型簡化：Synthesizer 提供靈活結構替代方案

4.任務特化設計：可結合多種策略（如 global + local）

在未來的注意力設計中，「可擴展性」與「架構靈活性」將成為主流趨勢，模型是否仍需 Attention，將不再是唯一選項。