← Back to Blog

Linformer: Self-Attention with Linear Complexity

research > papers

2026-02-112 min read

#paper-review #research #notes #linformer #rank

Paper Link

기존 self-attention

head=Attention⁡(Q,K,V)=softmax⁡(QKTd)V⏟P∈Rn×n\text{head} = \operatorname{Attention}(Q,K,V) = \underbrace{\operatorname{softmax}\left(\frac{QK^T}{\sqrt{d}}\right)V}_{P \in \mathbb{R}^{n\times n}}

Transformer and Self-Attention

P=softmax⁡(QKTd)P = \operatorname{softmax}\left(\frac{QK^T}{\sqrt{d}} \right) P≈UΣVT, rank≈k≪nP \approx U\Sigma V^T,\ \text{rank} \approx k \ll n

위 수식이 성립하면 n×nn \times n 과정이 필요 없다.

PV≈(UΣ)(VTV)PV \approx (U\Sigma)(V^TV)

Key/Value 길이를 축소하자

Query는 그대로 두고, Key/Value를 시퀀스 차원에서 선형 투영한다.

K′=EK(k×d)V′=FV(k×d)\begin{align} K^\prime &= EK\quad(k \times d)\\ V^\prime &= FV\quad(k \times d) \end{align}

일반적인 linear projection

일반적으로 생각하는 linear projection은 feature 공간으로 투영한다.

x∈Rd→Wx∈Rd′x \in \mathbb{R}^d \rightarrow Wx \in \mathbb{R}^{d^\prime}

Linformer linear projection

원래 Key/Value 구조
K∈Rn×dK \in \mathbb{R}^{n \times d}

각 feature 차원마다 길이 nn 짜리 신호가 있음.

시퀀스 압축
K′=EKwhereE∈Rk×nK^\prime = EK\quad\text{where}\quad E\in \mathbb{R}^{k\times n}

결과

K′∈Rk×dK^\prime \in \mathbb{R}^{k \times d} MultiHead(Q,K,V)=Concat(head1,head2,…,headh)WO(1)\text{MultiHead}(Q,K,V) = \text{Concat}(\text{head}_1, \text{head}_2, \dots, \text{head}_h)W^O \tag{1} headi=Attention(QWiQ,KWiK,VWiV)=softmax[QWiQ(KWiK)Tdk]VWiV(2)\text{head}_i = \text{Attention}(QW^Q_i, KW^K_i, VW^V_i) = \text{softmax}\left[\frac{QW^Q_i(KW^K_i)^T}{\sqrt{d_k}} \right]VW^V_i \tag{2}

where WiQ,WiK∈Rdm×dk,WiV∈Rdm×dv,WO∈Rhdv×dm\text{where}\ W^Q_i, W^K_i \in \mathbb{R}^{d_m \times d_k}, W^V_i \in \mathbb{R}^{d_m\times d_v}, W^O \in \mathbb{R}^{hd_v\times d_m}

여기서 우리는 행렬 EE 를 알면 되는데 이를 신경망으로 학습시키면 된다.