Transformer 구조를 이해하다 보면 꼭 마주하게 되는 질문이 있습니다.
바로 "Attention Layer는 얼마나 연산량이 많을까?", "MLP는 상대적으로 가볍나?" 하는 궁금증입니다.
이 글에서는 MLP, Linear Layer, Self-Attention Layer의 시간 복잡도(time complexity)를 비교하고,
왜 Attention이 자주 연산량의 병목이 되는지 이해해보겠습니다.

---

1. MLP (Multi-Layer Perceptron)

Transformer의 MLP는 각 토큰에 독립적으로 적용되는 구조입니다.

구조:

• Input (d 차원)
  → Linear(d, d_ff)
  → Activation (GELU or ReLU)
  → Linear(d_ff, d)
  → Output (d 차원)

시간 복잡도:

• 한 토큰 기준:

  $O(d × d_{ff})$

• 전체 시퀀스(N개 토큰):

  $O(N × d × d_{ff})$

  d_ff는 출력 차원이 아니라, MLP 내부의 중간(hidden) 차원입니다.
  예: BERT-base에서 d=768, d_ff=3072

---

2. Linear Layer

Transformer의 Linear Layer는 단일 선형 변환입니다.
각 토큰을 독립적으로 처리하며, 매우 단순한 구조입니다.

시간 복잡도:

• 전체 시퀀스 기준:

  $O(N × d × d_{out})$

---

3. Self-Attention Layer

Self-Attention은 모든 토큰 쌍의 상호작용을 계산해야 합니다.

연산 흐름:

• $Q, K, V$ 생성: $O(N × d × d)$
• Attention Score 계산 ($QK^t$): $O(N^2 × d)$
• Softmax 후 weighted sum: $O(N^2 × d)$
• Multi-head & 최종 출력 결합: $O(N × d × d)$

총 시간 복잡도:

이 복잡도는 시퀀스 길이 N이 길어질수록 빠르게 증가합니다.

---

4. 연산량 비교 요약

항목	시간 복잡도	특징
Linear Layer	O(N × d × d_out)	독립적인 토큰 처리
MLP	O(N × d × d_ff)	중간 차원 확장 후 축소
Attention	O(N² × d)	모든 토큰 쌍 간 상호작용

---

5. 왜 Attention이 연산량 병목인가?

실제로는 Attention 연산이 더 무겁습니다:

• Q, K, V 각각 생성 (3배)
• 보통 multi-head (8~12개 이상)
• Softmax 등 추가 연산 포함
• 메모리 사용량도 훨씬 큼

예시 비교 (N=512, d=768):

항목	이론 연산량 대략치
Linear Layer	≈ 3 × 10⁸
Attention	≈ 2 × 10⁸ × head 수

따라서 실제로는 Attention Layer가 Linear보다 2~5배 이상 연산량이 많고 메모리도 많이 차지합니다.

---