# FFT의 반격: Self-Attention에 대한 효율적인 대안

> Clean Markdown view of GeekNews topic #19460. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=19460](https://news.hada.io/topic?id=19460)
- GeekNews Markdown: [https://news.hada.io/topic/19460.md](https://news.hada.io/topic/19460.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-02-27T09:58:01+09:00
- Updated: 2025-02-27T09:58:01+09:00
- Original source: [arxiv.org](https://arxiv.org/abs/2502.18394)
- Points: 3
- Comments: 1

## Topic Body

- 기존 **Self-Attention** 메커니즘은 **O(n²)** 의 복잡도를 가지며, 긴 시퀀스에 대한 확장성이 제한적임  
- 본 논문에서는 **Fast Fourier Transform(FFT)** 을 활용한 **FFTNet**을 제안함  
- FFTNet은 **O(n log n)** 의 시간 복잡도로 글로벌 토큰 혼합을 수행  
- 주파수 도메인에서 학습 가능한 **스펙트럴 필터**와 **modReLU 활성화 함수**를 도입하여 중요한 주파수 성분을 강조함  
- Long Range Arena(LRA) 및 ImageNet 벤치마크 실험에서 기존 Self-Attention 및 고정된 Fourier 변환 모델보다 우수한 성능을 보임  
  
### 관련 연구  
- **Self-Attention의 복잡도** : Transformer 모델은 **O(n²)** 의 연산량이 필요하여 긴 시퀀스 처리에 비효율적임  
- **Fourier 기반 접근법** : **FNet**과 같은 모델은 **고정된 Fourier 변환**을 활용하여 연산량을 줄였으나, 입력 적응성이 부족함  
- **선형, 희소 및 저차원 근사 기법** : Performer, Linformer, BigBird 등의 연구가 **Self-Attention의 연산을 근사**하는 방법을 제안함  
- **직교 행렬 분해 기법** : **직교 변환(DFT 포함)** 을 활용하면 모델 학습 안정성이 향상됨  
- **적응형 스펙트럴 필터링** : FFT 기반 변환에 **학습 가능한 필터**를 추가하여 기존 방식보다 **더 유연하고 표현력이 높음**  
  
### FFTNet: 적응형 스펙트럴 필터링 기법  
#### 동기  
- Self-Attention은 **O(n²)** 의 복잡도를 가지며 긴 시퀀스에서 비효율적임  
- FFT는 **O(n log n)** 으로 동작하며 글로벌 상호작용을 효율적으로 인코딩 가능  
  
#### 방법론  
- **Fourier 변환 (FFT 적용)**  
   - 입력 시퀀스를 주파수 도메인으로 변환하여 **전역적 의존성**을 효율적으로 캡처  
- **적응형 스펙트럴 필터 적용**  
   - **전역 컨텍스트 벡터**를 활용하여 학습 가능한 필터를 생성하고, 중요한 주파수 대역을 동적으로 강조  
- **modReLU 비선형 활성화**  
   - 복소수 주파수 도메인에서 ReLU 기반 활성화 적용하여 표현력을 증가  
- **역 Fourier 변환 (IFFT)**  
   - 변환된 데이터에 대해 필터링 및 활성화를 적용한 후 다시 시간 도메인으로 변환  
  
### FFTNet의 이론적 근거  
- **O(n log n)의 연산량**으로 글로벌 토큰 혼합 가능  
- **적응형 Attention**: 주파수 도메인에서 학습 가능한 필터가 주어진 입력에 따라 주파수를 조정  
- **비선형 활성화의 표현력 강화**: modReLU 적용으로 단순 선형 변환을 넘어선 고차원 패턴 학습 가능  
- **Parseval's theorem 기반 안정성 보장**: 신호의 에너지를 보존하여 정보 손실을 최소화  
  
### 실험 결과  
#### Long Range Arena (LRA) 벤치마크  
- FFTNet은 Transformer 및 FNet보다 전반적으로 더 높은 정확도를 기록함  
- 특히 ListOps, Text, Retrieval, Image, Pathfinder 태스크에서 더 좋은 성능을 보이며, 평균적으로 가장 높은 점수를 기록함  
- Transformer는 일부 태스크에서 높은 성능을 보였으나, 장기적인 의존성을 처리하는 데 한계를 가짐  
- FNet은 FFT를 활용하지만, 고정된 변환 방식이 적응성이 부족하여 전반적으로 낮은 성능을 보임  
- 특히 Path-X 태스크에서는 Transformer가 메모리 초과(OOM)로 실패한 반면, FFTNet은 안정적인 성능을 보였음  
  
#### ImageNet 분류 실험  
- FFTNet 기반 Vision Transformer(FFTNetViT)는 기존 ViT와 유사한 정확도를 유지하면서 연산량(FLOPs)을 크게 줄이는 데 성공함  
- Base 모델의 경우, FFTNetViT는 ViT보다 약 38% 적은 FLOPs를 사용하면서도 정확도가 소폭 증가함  
- Large 및 Huge 모델에서도 FFTNetViT는 ViT 대비 낮은 연산량으로 유사한 성능을 유지함  
- 이를 통해 FFTNetViT가 높은 계산 효율성을 제공한다는 점을 확인할 수 있음  
  
#### Ablation Study (구성 요소별 중요도 분석)  
- FFTNet의 다양한 요소를 제거하며 모델의 성능에 미치는 영향을 분석함  
- FFTNet의 주요 구성 요소를 제거할수록 정확도가 감소하는 경향을 보임  
  - **스펙트럴 게이팅 제거**: 특정 주파수를 강조하는 기능이 사라지면서 정확도가 소폭 하락함  
  - **적응형 모듈 제거**: 입력에 따라 필터를 동적으로 조정하는 기능이 사라져 정확도가 더 낮아짐  
  - **FFT 대신 합성곱 사용**: 글로벌 정보를 효율적으로 혼합하는 기능이 사라져 가장 큰 성능 저하가 발생함  
- 이를 통해 FFTNet의 각 요소가 성능 향상에 중요한 역할을 한다는 점을 확인할 수 있음  
  
### 결론  
- **FFTNet은 Self-Attention보다 연산 효율성이 뛰어난 대안**임  
- 주파수 도메인에서 **적응형 스펙트럴 필터와 modReLU**를 결합하여 강력한 표현력을 제공  
- 실험 결과, **LRA 및 ImageNet에서 기존 Self-Attention 모델보다 성능 및 효율성 우수**  
- **O(n log n) 복잡도를 유지하면서도 Self-Attention 수준의 성능을 제공**하여 긴 시퀀스 처리에 유리함  
- FFTNet을 기반으로 한 Vision Transformer(FFTNetViT)도 낮은 FLOPs로 ViT와 비슷한 성능 달성  
  
* **코드 저장소**: [GitHub 링크](https://github.com/jacobfa/fft)

## Comments



### Comment 35187

- Author: neo
- Created: 2025-02-27T09:58:01+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=43182325) 
* 기본적으로 컨볼루션 정리를 활용함: 직접 공간에서의 비싼 컨볼루션이 상호 공간에서는 간단한 곱셈이 됨
  * 데이터에 컨볼루션 연산이 있을 때, 이를 곱셈으로 바꾸기 위해 켤레 도메인으로 변환함
  * 즉, 데이터에 자연스러운 도메인에서 작업함

* Google은 2022년에 "FNet: Mixing Tokens with Fourier Transforms"라는 아이디어를 소개함
  * 나중에 그들의 TPU가 대부분의 시나리오에서 FFT보다 행렬 곱셈에서 더 빠르다는 것을 발견함

* Fourier 변환은 "토큰" 차원에서 수행됨. 그러나 많은 응용에서 이 차원은 의미가 없음
  * 그래서 변환기는 순열 불변 데이터를 처리하는 데 훌륭한 옵션임
  * 덜 알려진 유한 그룹에 대한 Fourier 변환을 사용한 추가 실험을 보고 싶음
  * 이것이 LLMs의 다음 큰 것이 된다면, 추론 엔진(vLLM, llama.cpp 등)이 이를 통합하기 얼마나 쉬울지 궁금함

* 수학이 너무 어려워서 이해하기 힘듦. 누군가 이게 주의 메커니즘과 어떻게 동등한지, 어떤 주파수를 말하는지, 토큰 간의 위치 관계를 어떻게 인코딩하는지 기본 영어로 설명해 줄 수 있는지 궁금함

* 이 프레임워크에 인과 마스킹을 어떻게 맞출 수 있을지 모르겠음. 위치 임베딩에 대한 언급도 없어서 비교되는 자기 주의 구현이 비인과적 NoPE인 것 같음
  * 결과가 최첨단에 가까웠다면 아마 저자가 언급했을 것임

* 몇 년 전 이미 O(n log n) 전체 컨텍스트 혼합을 시연한 Hyena Operator에 대한 언급이 없음

* 텔레메트리 시대에 클라우드 텔레메트리에 FFT를 적용하여 드라마를 유발하기 전 에피사이클과 준안정 시스템을 찾아내지 않는 것은 큰 실수라고 생각함
  * "SLA는 서비스 배포 후 23-25분 후에 가장 위반될 가능성이 높음. 왜 그런지 궁금함... 아, 안돼."

* 주파수 도메인에서 사물을 보는 것이 왜 도움이 되는지에 대한 직관을 가진 사람이 있는지 궁금함
  * DC 항은 이해할 수 있지만 입력 데이터가 다른 주파수가 의미 있을 만큼 주기적이라고 기대하지 않음

* 빅 O 표기법을 어느 정도 이해하지만, 컴퓨터나 전기 공학과 관련된 대부분의 것처럼 이것도 이해하기 어려움
  * 수학에 매우 약한 사람으로서 이런 것을 이해하거나 배울 수 있는 사람들을 부러워함
  * FFT에 대해 아는 것은 신호를 변화시키고, 어떤 신호 처리에 사용되며, 과거에 핵 폭발을 감지하는 데 중요한 역할을 했다는 것임

* 주의가 왜 필요한지 이해하지 못함. 완전 연결 레이어도 모든 입력에 "주의"할 수 있음
  * 매우 작은 데이터셋(0 - 500 토큰)에서는 주의가 훈련을 더 오래 걸리게 하고 결과를 나쁘게 만듦
  * 더 큰 데이터셋에서 이점이 나타나는 것 같음
  * AI 초보자로서 개인 AI 프로젝트를 하고 있어 정확한 참고 자료는 아님