[논문리뷰] Linformer: Self-Attention with Linear Complexity

Linformer: Self-Attention with Linear Complexity은 기존 Transformer의 Self-Attention 연산 복잡도(O(n²)) 문제를 해결하기 위해 제안된 효율적 어텐션 구조입니다.
핵심 아이디어는 Self-Attention의 Attention Matrix가 저랭크(low-rank) 구조를 가진다는 점에 착안하여, 이를 선형 복잡도(O(n))로 근사하는 것입니다.

 

오늘은 Transformer의 가장 큰 병목으로 꼽히는 Self-Attention의 연산 복잡도 문제를 해결하려는 논문, “Linformer: Self-Attention with Linear Complexity”를 리뷰해보려고 합니다.

Transformer는 NLP뿐만 아니라 비전, 음성, 시계열 등 다양한 분야에서 사실상의 표준 모델이 되었지만, Self-Attention이 가지는 O(n²)의 시간, 메모리 복잡도는 긴 시퀀스를 다룰 때 치명적인 한계로 작용합니다.

 

그렇다면 정말 Attention은 반드시 O(n²)여야 할까요?

Linformer는 이 질문에서 출발합니다.
이 논문은 Attention Matrix가 실제로는 low-rank 구조를 가진다는 가설을 바탕으로, Self-Attention을 선형 복잡도(O(n))로 근사할 수 있는 방법을 제안합니다.

 

이번 글에서는:

• 기존 Self-Attention의 한계
• Linformer의 핵심 아이디어
• 수식 기반 동작 원리
• 실험 결과와 의미
• 그리고 개인적인 인사이트

를 차근차근 정리해보겠습니다.

Efficient Transformer 계열 논문들의 출발점 중 하나라고 할 수 있는 이 논문을 함께 살펴보겠습니다.

1️⃣ Introduction

Transformer 구조의 가장 큰 병목은 Self-Attention에서 발생합니다.

Self-Attention은 입력 시퀀스 길이를 nnn이라 할 때, 모든 토큰 쌍 간의 관계를 계산하기 때문에 시간 및 메모리 복잡도가 O(n²)로 증가합니다.
각 단어는 문장 내 모든 단어와의 관계를 계산한 뒤, 그 정보를 바탕으로 자신의 representation을 업데이트하게 되는데, 이 과정이 시퀀스가 길어질수록 급격한 연산량 증가를 초래합니다.

따라서 긴 문서, 고해상도 이미지 패치, 장기 시계열 데이터 등을 처리할 때 Self-Attention은 심각한 계산 병목이 됩니다.

 

이 논문은 다음과 같은 질문에서 출발합니다.

Self-Attention은 정말 반드시 O(n²) 복잡도를 가져야 할까?

저자들은 Self-Attention 행렬이 실제로는 low-rank 구조를 가진다는 점에 주목합니다.
즉, 전체 attention matrix를 완전하게 계산하지 않더라도, 더 낮은 차원의 표현으로 충분히 근사할 수 있다는 가설입니다.

이를 위해 Linformer는:

• Key(K)와 Value(V)를 각각 학습 가능한 linear projection matrix를 통해 저차원으로 변환
• 기존의 n × n attention 계산을 n × k (k ≪ n) 구조로 축소
• 결과적으로 O(n²) 복잡도를 O(n) 으로 감소

시키는 새로운 Self-Attention 구조를 제안합니다.

 

논문에서는 여러 아키텍처의 연산 복잡도와 Sequential Operation을 비교합니다.

• Recurrent 모델 (RNN)
  이전 시점의 출력이 다음 시점 계산에 반드시 필요 → 순차 연산 O(n)
• Transformer
  각 시점의 연산이 독립적이므로 병렬 처리 가능 → Sequential Operation O(1)
  하지만 Attention 계산은 O(n²)
• Linformer
  병렬 처리 가능 (O(1))
  Attention 계산은 O(n)

즉, Linformer는 Transformer의 처리 장점은 유지하면서도, 연산 복잡도를 선형으로 낮춘 구조라고 볼 수 있습니다.

 

2️⃣ Background – Self-Attention

앞서 살펴본 것처럼, Transformer의 병목은 주로 Self-Attention 연산에서 발생합니다.
Linformer를 이해하기 위해 먼저 기존 Self-Attention 구조를 간단히 정리해보겠습니다.

Q, K, V의 구성

Self-Attention에서는 입력 임베딩으로부터 다음 세 가지 행렬을 생성합니다.

• Q (Query)
• K (Key)
• V (Value)

각 행렬의 크기는 다음과 같습니다.

Q : n x d
K : n x d
V : n x d

여기서
n = sequence length (토큰 개수)
d = embedding dimension

Context Mapping Matrix P

Self-Attention의 핵심 연산은 다음과 같습니다.

P = softmax( (Q K^T) / sqrt(d_k) )

여기서

Q K^T : (n x d) x (d x n) = n x n
따라서 P의 크기 역시 n x n 입니다.

이 행렬 P는 각 토큰이 다른 모든 토큰에 얼마나 집중하는지를 나타내는 Attention Matrix입니다.

 

그 다음 최종 출력은 다음과 같이 계산됩니다.

Attention(Q, K, V) = P V

여기서

P : n x n
V : n x d

결과는 n x d 가 됩니다.

왜 O(n²) 복잡도가 발생하는가?

핵심 병목은 Q K^T 연산입니다.

Q : n x d
K^T : d x n

행렬 곱 결과는 n x n 이 되고, 모든 토큰 쌍에 대해 유사도를 계산해야 합니다.

즉,

연산 복잡도: O(n²)
메모리 복잡도: O(n²)

시퀀스 길이가 2배가 되면 연산량은 4배로 증가합니다.

이 부분이 Transformer가 긴 시퀀스에서 비효율적인 이유입니다.

이 논문의 문제 정의

Linformer는 바로 이 Context Mapping Matrix P를 병목의 원인으로 봅니다.

• P는 n x n 크기
• 계산 비용이 O(n²)
• 메모리 사용량도 O(n²)

따라서,

"이 n x n Attention Matrix를 굳이 그대로 계산할 필요가 있을까?"

라는 질문에서 출발합니다.

그리고 이 논문은 Self-Attention이 실제로는 low-rank 구조를 가지며, 이를 더 작은 차원으로 근사할 수 있음을 보입니다.

 

3️⃣ Background – SVD와 Low-Rank Approximation

Linformer의 핵심 아이디어는 Low-Rank Approximation입니다.
이를 이해하기 위해 먼저 SVD(Singular Value Decomposition) 개념을 간단히 정리해보겠습니다.

Singular Value Decomposition (SVD)

임의의 행렬 A (크기: m x n)는 다음과 같이 분해할 수 있습니다.

A = U Σ V^T

여기서,

• U : m x m 크기의 직교 행렬
• Σ : m x n 크기의 대각 행렬 (특이값 포함)
• V^T : n x n 크기의 직교 행렬

즉, 하나의 행렬 A를 세 개의 행렬로 분해할 수 있으며,
이 분해를 통해 행렬의 중요한 구조적 성분을 파악할 수 있습니다.

Low-Rank Approximation

SVD에서 중요한 점은 모든 특이값을 사용할 필요가 없다는 것입니다.

A = sum(i=1 to r) σ_i u_i v_i^T

여기서 r은 rank(A)입니다.

하지만 상위 k개의 특이값(σ_1, ..., σ_k)만 사용해도 원래 행렬 A를 상당히 정확하게 근사할 수 있습니다.

이를 Low-Rank Approximation이라고 합니다.

즉,

A ≈ A' = sum(i=1 to k) σ_i u_i v_i^T

또는 행렬 형태로 쓰면,

A' = U_k Σ_k V_k^T

왜 계산량이 줄어드는가?

기존 행렬 A의 크기는 m x n 입니다. 즉, 저장해야 할 원소 수는 m x n 개입니다.

하지만 rank-k 근사를 하면 필요한 원소 수는 다음과 같습니다.

U_k : m x k
Σ_k : k
V_k : k x n

총 필요한 원소 수는

(m x k) + k + (k x n)
= k(m + n + 1)

만약 k가 m, n보다 훨씬 작다면, 이는 m x n보다 훨씬 작은 값이 됩니다.

즉,

m x n → k(m + n + 1)

으로 줄어들게 됩니다.

Linformer와의 연결

Linformer는 바로 이 아이디어를 Attention Matrix에 적용합니다.

Self-Attention에서 계산되는 P는 P = softmax(Q K^T / sqrt(d_k)) 이며, 이 P의 크기는 n x n 입니다.

Linformer는 이 Attention Matrix가 실제로는 low-rank 구조를 가진다고 가정합니다.
따라서 전체 n x n 행렬을 직접 계산하지 않고, 더 작은 차원의 행렬로 근사할 수 있다고 주장합니다.

즉, "Attention 행렬을 완전하게 계산하지 않아도 된다" 는 것이 Linformer의 출발점입니다.

 

 

4️⃣ Self-Attention is Low-Rank

앞서 SVD와 Low-Rank Approximation 개념을 살펴봤다면,
이제 중요한 질문이 남습니다.

그렇다면 실제 Self-Attention 행렬도 Low-Rank 구조를 가지는가?

Linformer의 저자들은 단순한 가정에 그치지 않고,
Self-Attention의 Context Mapping Matrix P가 실제로 low-rank 특성을 가지는지 실험적으로 검증합니다.

실험 설정

저자들은 사전학습된 Transformer 모델을 사용하여 각 레이어에서 생성되는 Attention Matrix의 특이값 분포를 분석했습니다.

사용한 모델은 다음과 같습니다.

• RoBERTa-base (12-layer Transformer)
• RoBERTa-large (24-layer Transformer)

즉, 비교적 작은 모델과 큰 모델 모두에서 실험을 진행하여 결과의 일반성을 확인하고자 했습니다.

사용 데이터셋

실험에는 서로 다른 성격의 두 가지 태스크가 사용되었습니다.

1. Wiki103
   • Masked Language Modeling (MLM) task
   • 대규모 언어 모델링 데이터셋
2. IMDB
   • Sentiment classification task
   • 문장 단위 분류 문제

즉, 언어 모델링과 문장 분류라는 서로 다른 태스크 환경에서도 Attention Matrix의 구조적 특성이 유지되는지를 확인한 것입니다.

핵심 결과

실험 결과, Attention Matrix P의 특이값은 빠르게 감소하는 경향을 보였습니다.

이는 다음을 의미합니다.

• 전체 n x n 행렬이 실제로는 소수의 주요 특이값에 의해 대부분의 정보가 설명될 수 있음
• 즉, Self-Attention은 실질적으로 low-rank 구조를 가진다

이 실험 결과가 바로 Linformer의 핵심 가정을 뒷받침합니다.

 

5️⃣ Self-Attention은 실제로 Low-Rank인가?

앞서 저자들은 Self-Attention의 Context Mapping Matrix P가 low-rank 구조를 가질 것이라고 가정했습니다.

그렇다면 이 가정은 실제로 성립할까요?

이를 확인하기 위해 저자들은 실험적으로 P의 랭크 특성을 분석했습니다.

실험 방법

각 layer와 head에서 생성되는 Attention Matrix P에 대해 SVD를 적용했습니다.

그리고,

• 총 10,000개 문장에 대해
• 각 layer와 head별로
• SVD의 특이값을 구한 뒤
• Normalized Cumulative Eigenvalue(정규화된 누적 특이값 합)를 계산했습니다.

예를 들어, RoBERTa-base 모델은

• 12개의 layer
• 각 layer마다 16개의 head

를 가지므로, 총 12 x 16개의 Attention Matrix P에 대해 각각 SVD를 수행하고, 10,000개 문장에 대해 평균을 낸 결과를 그래프로 나타낸 것입니다.

그래프 해석

• x축: eigenvalue index
  → 상위 몇 개의 특이값을 사용하는지를 의미
  → 즉, low-rank 근사에서의 k 값과 대응
• y축: normalized cumulative eigenvalue
  → 상위 k개의 특이값만 사용했을 때
  원래 Attention Matrix P의 정보를 얼마나 복원할 수 있는지를 의미

즉, x축이 128일 때 y축이 0.9라면, 상위 128개의 특이값만 사용해도 원래 P의 정보를 약 90% 복원할 수 있다는 뜻입니다.

핵심 결과

그래프를 보면 특이값이 매우 빠르게 누적됩니다.

특히, 상위 128개의 특이값만 사용해도 전체 Attention Matrix P의 약 90% 이상을 설명할 수 있습니다.

이는 매우 중요한 결과입니다.

왜냐하면,

• 원래 P는 n x n 크기의 행렬
• 하지만 실제로는 소수의 주요 성분에 의해 대부분의 정보가 결정됨
• 즉, P는 실질적으로 low-rank 구조를 가진다는 것

을 의미하기 때문입니다.

이러한 실험 결과는 Linformer의 핵심 가정을 강하게 뒷받침합니다.

"Self-Attention을 완전한 n x n 행렬로 계산할 필요가 없다."

→ 상위 k개의 성분만으로도 충분하다.
→ 따라서 더 작은 차원으로 projection해도 정보 손실이 크지 않다.

이제 자연스럽게 다음 질문으로 이어집니다.

그렇다면, 어떻게 K와 V를 줄여서 Attention 계산을 O(n)으로 만들 수 있을까?

6️⃣ Layer별 Low-Rank 특성 분석 (Heatmap)

앞선 그래프가 전체적인 특이값 분포를 보여줬다면, 이번 결과는 이를 layer와 head 단위로 더 세밀하게 분석한 heatmap입니다.

각 layer와 head에서 생성되는 Attention Matrix P에 대해 SVD를 적용한 뒤,

• 전체 512개의 singular value 중
• 상위 128개만 사용했을 때
• 원래 P의 정보를 얼마나 복원할 수 있는지

를 heatmap으로 시각화한 결과입니다.

즉, "상위 128개의 singular value만으로 해당 layer·head의 Attention Matrix를 얼마나 설명할 수 있는가?" 를 보여주는 그래프입니다.

그래프 해석

• x축: Head index
• y축: Layer index
• 색상 값: 상위 128개의 singular value로 복원 가능한 정보 비율

색이 밝을수록 (예: 0.96에 가까울수록)

→ 소수의 singular value가 대부분의 정보를 설명
→ 더 강한 low-rank 특성

을 의미합니다.

관찰 결과

상위 layer (layer index 10~11)

• 대부분 노란색에 가까움(상위 128개의 singular value만으로 90% 이상 복원 가능)

이는 상위 layer에서 Attention Matrix의 정보가 소수의 큰 singular value에 집중되어 있다는 뜻입니다.

즉, 상위 layer로 갈수록 Attention Matrix의 rank가 더 낮아지는 경향을 보입니다.

하위 layer (layer index 0~1)

• 상대적으로 보라색에 가까움(더 많은 singular value가 필요)

이는 하위 layer에서는 정보가 더 넓게 분산되어 있고, Attention Matrix가 full-rank에 더 가깝다는 의미입니다.

무엇을 의미하는가?

이 결과는 매우 흥미로운 인사이트를 제공합니다.

• 모델이 깊어질수록 Attention Matrix는 점점 더 단순해지고 정보가 소수의 중요한 차원에 집중되는 경향을 보입니다.

즉, 초기 layer는 다양한 정보를 넓게 조합하고, 깊은 layer로 갈수록 더 구조화된 표현을 형성한다는 해석이 가능합니다.

Linformer 관점에서의 의미

이 결과는 Linformer의 핵심 가정을 다시 한 번 뒷받침합니다.

특히 상위 layer에서는

• Attention Matrix가 매우 강한 low-rank 특성을 가지므로 projection 기반 근사를 적용해도 정보 손실이 크지 않다

는 것을 시사합니다.

7️⃣ 이론적 근거: Low-Rank 근사의 오차 보장

앞선 실험을 통해 Self-Attention의 Context Mapping Matrix P가 실제로 low-rank 특성을 가진다는 것을 확인했습니다.

그렇다면 다음 질문이 자연스럽게 이어집니다.

P를 low-rank로 근사했을 때, 실제 Self-Attention 결과는 얼마나 정확하게 유지될까?

논문에서는 이에 대한 이론적 보장을 제시합니다.

핵심 아이디어

원래 Self-Attention 결과는 다음과 같은 형태입니다.

Output = P W^T 

여기서 P는 n x n 크기의 Attention Matrix입니다.

이제 P를 low-rank 근사한 행렬 P̃ (P-tilde)로 대체한다고 가정하면, 근사된 결과는 다음과 같습니다.

Approx Output = P̃ W^T 

논문에서는 다음과 같은 확률적 보장을 제시합니다.

• P̃ W^T 와 P W^T 의 차이는 ε × ||P W^T|| 보다 작을 확률이 1 - o(1)에 가깝다

여기서

• ε는 매우 작은 값
• 1 - o(1)은 거의 1에 가까운 확률

을 의미합니다.

즉, low-rank 근사를 사용하더라도 Self-Attention 결과의 오차는 매우 작으며 높은 확률로 정확한 근사가 가능하다는 뜻입니다.

하지만 SVD를 직접 쓰는 것은 비현실적

이론적으로는 P를 SVD로 분해하고 상위 k개 성분만 남겨 매번 Attention을 계산하면 되지만, 실제 모델 학습 및 추론 과정에서는 모든 Self-Attention step마다 매번 SVD를 수행해야 하고 이는 오히려 연산량을 크게 증가시킵니다.

즉, 이론적으로는 가능하지만 실제 구현에는 적합하지 않습니다.

Linear Self-Attention

저자들은 다음과 같은 아이디어를 사용합니다.

• SVD가 보여준 핵심은 "P는 low-rank로 근사 가능하다"는 점
• 그렇다면 굳이 SVD를 직접 계산할 필요는 없다
• 대신, 저차원 projection을 통해 같은 효과를 얻을 수 있다

즉, SVD와 유사하게 차원을 줄이면서도 추가적인 고비용 연산 없이 계산 가능한 방법을 제안합니다.

그것이 바로 Linear Projection 기반 Self-Attention, 즉 Linformer의 핵심 구조입니다.

9️⃣ Linformer의 핵심 아이디어

Linformer의 아이디어는 생각보다 단순합니다.

Self-Attention의 병목은 n x n 크기의 Attention Matrix P를 계산해야 한다는 점이었습니다.

Linformer는 Key(K)와 Value(V)를 먼저 저차원(k 차원)으로 projection한 뒤 Attention을 계산합니다.

기존 Self-Attention 복습

기존 Attention은 다음과 같습니다.

Attention(Q, K, V) = softmax( (Q W^Q · (K W^K)^T) / sqrt(d_k) ) · (V W^V)

여기서

• QW^Q : n x d_k
• KW^K : n x d_k
• VW^V : n x d_k

따라서 (QW^Q)(KW^K)^T → n x n 
복잡도는 O(n²)

Linformer의 변화

Linformer는 각 head마다 두 개의 projection matrix를 추가합니다.

• E_i : k x n (Key용 projection matrix)
• F_i : k x n (Value용 projection matrix)

여기서 k는 n보다 훨씬 작은 값입니다. (k << n)

Key projection

원래 Key:

K W^K → n x d_k

Linformer에서는 먼저 E_i를 곱합니다.

E_i (K W^K) → (k x n)(n x d_k) = k x d_k

즉, n x d_k → k x d_k 로 차원이 줄어듭니다.

Value projection

마찬가지로, 

F_i (V W^V) → (k x n)(n x d_k) = k x d_k

Value 역시 n x d_k → k x d_k 로 압축됩니다.

변경된 Attention 식

이제 Attention은 다음과 같이 계산됩니다.

Attention(Q, K, V)
= softmax( (Q W^Q · (E_i K W^K)^T) / sqrt(d_k) ) · (F_i V W^V)

차원을 보면:

• QW^Q : n x d_k
• (E_i K W^K)^T : d_k x k

→ Attention score matrix : n x k 즉, 더 이상 n x n이 아닙니다.

복잡도 변화

기존: (QW^Q)(KW^K)^T → n x n
복잡도: O(n²)

Linformer: (QW^Q)((E_i K W^K)^T) → n x k
복잡도: O(nk)

k가 n보다 훨씬 작다면, O(nk) ≈ O(n) 이 됩니다.

직관적으로 이해하면

기존 Transformer는 "모든 토큰이 모든 토큰을 본다" 는 구조였다면,

Linformer는 "모든 토큰이 n개를 직접 보는 대신, k개의 압축된 대표 정보만 본다" 는 구조입니다.

그리고 앞선 실험에서 확인했듯, Attention Matrix는 실제로 low-rank 특성을 가지기 때문에 이러한 압축이 성능을 크게 떨어뜨리지 않습니다.

 

계속 이어서 작성중...