Transformers은 RNN이다 — 선형 어텐션으로 빠른 Autoregressive Transformer 만들기

Digest: 표준 Transformer의 softmax self-attention(쿼리-키 유사도에 softmax를 취해 값을 가중 평균)은 시퀀스 길이 N에 대해 O(N²) 메모리/계산을 요구해 긴 문맥과 autoregressive 생성에서 치명적이다. 저자들은 softmax 유사도 $exp (q^{⊤} k)$ 를 양의 커널 $k (q, k) = ϕ (q)^{⊤} ϕ (k)$ (특성 맵 φ 사용, 논문은 elu(x)+1 제안)로 대체하면 분자가 $ϕ (Q) (ϕ (K)^{⊤} V)$ 로 재결합(associativity) 되어 $O (N \cdot d^{2})$ 로 떨어진다는 핵심 통찰을 제시한다. 더 나아가 causal(autoregressive) 어텐션의 누적합 구조를 풀어 쓰면 숨은 상태 $S_{t} = S_{t - 1} + ϕ (k_{t}) v_{t}^{⊤}$ , $z_{t} = z_{t - 1} + ϕ (k_{t})$ 의 RNN 재귀식과 일치함을 증명한다 — 즉 Transformer는 특정 특성 맵을 가진 RNN의 일반화다. 이로써 autoregressive 추론이 토큰당 O(1)(선형 전체 O(N))로 가능해지며, 이미지(CIFAR-10 pixel-level 생성) 및 자동 음성 인식(Speech) 실험에서 softmax Transformer 대비 4000배 이상 빠른 생성(MNIST 이미지 생성 기준, Table 1)을 비슷한 품질로 달성한다. Limitations: 특성 맵 φ 선택이 ad-hoc(elu+1은 positivity 보장용 휴리스틱)이고, softmax의 날카로운 선택성(sharp selection)을 근사하기엔 표현력이 부족해 일부 태스크에서 품질 저하가 있다. Open Questions: 더 나은 φ(Performer의 random features, cosFormer 등 후속)와, RNN 관점이 시사하는 meta-learning/state-space 모델(Mamba, RetNet, RWKV)과의 통합.

섹션별 요약

Introduction

Transformer의 self-attention은 시퀀스 길이 N의 제곱에 비례하는 시간·메모리 복잡도를 가져 긴 문서·이미지 픽셀·음성 같은 장기 시퀀스에 부적합.
Autoregressive 생성에서는 매 스텝마다 과거 전체를 재어텐션하기 때문에 total inference가 O(N²)이 되어 RNN 대비 수천 배 느림.
기여: (1) softmax를 임의의 양의 커널로 일반화, (2) 행렬곱 결합법칙으로 O(N·d²) 선형 어텐션 유도, (3) causal 마스킹을 누적합으로 처리해 Transformer = RNN 등가성 증명.

Methods

일반화된 어텐션 정의: $V_{i}^{'} = \frac{\sum _{j} sim ( Q _{i} , K _{j} ) V _{j}}{\sum _{j} sim ( Q _{i} , K _{j} )}$ . softmax는 $sim = exp (q^{⊤} k)$ 인 특수 케이스.
커널 특성 맵 도입: $sim (q, k) = ϕ (q)^{⊤} ϕ (k)$ 로 두면 합산 순서를 교환 가능. 논문은 $ϕ (x) = elu (x) + 1$ 사용(양수 보장, 계산 저렴).
Associativity trick: $ϕ (Q) (ϕ (K)^{⊤} V)$ 순서로 계산 — $ϕ (K)^{⊤} V$ 는 $d \times d$ 행렬이라 N에 무관.
Causal masking: 하삼각 마스크를 누적합으로 변환. $S_{i} = \sum_{j \leq i} ϕ (k_{j}) v_{j}^{⊤}$ , $Z_{i} = \sum_{j \leq i} ϕ (k_{j})$ 로 두면 $V_{i}^{'} = ϕ (q_{i})^{⊤} S_{i} / (ϕ (q_{i})^{⊤} Z_{i})$ .
RNN view: 위 누적합을 재귀식 $S_{i} = S_{i - 1} + ϕ (k_{i}) v_{i}^{⊤}$ , $Z_{i} = Z_{i - 1} + ϕ (k_{i})$ 로 읽으면 숨은 상태가 있는 RNN. 추론 시 토큰당 O(d²).
학습: causal의 누적합은 custom CUDA kernel로 선형 시간 병렬 backward 지원.

Complexity Analysis

Softmax attention: 학습/추론 모두 O(N²·d), 메모리 O(N²).
Linear attention: 학습 O(N·d²), 메모리 O(N·d) (또는 O(d²) 상태).
Autoregressive 추론: softmax는 총 O(N²·d), linear는 총 O(N·d²) — d가 고정이면 N 선형.

Results

태스크	모델	메트릭	결과	비교
MNIST 이미지 생성 (autoreg.)	Linear Transformer	bits/dim / 속도	비슷한 품질, ~4000× 빠른 생성	vs softmax Transformer (Table 1)
CIFAR-10 pixel-level 생성	Linear Transformer	bits/dim	softmax와 근접	Reformer 대비 유리
Speech (음성인식, WSJ)	Linear Transformer	PER	biLSTM과 유사, softmax보다 빠름	Table 2

Discussion

한계: φ=elu+1은 휴리스틱 — softmax의 sharp distribution을 근사하기에 표현력이 제한적. 일부 태스크(WMT14 번역 등)에서 품질 gap 존재.
향후: 더 나은 특성 맵(이후 Performer의 FAVOR+, cosFormer의 cos 기반), 학습된 φ, RNN 관점을 활용한 state-space 하이브리드.

Insights

주목할 점: softmax의 “필수성”을 깨뜨린 첫 clean한 증명 — 어떤 양의 커널도 가능.
연결 고리: Performer(2020), RetNet(2023), RWKV(2023), Mamba(2023)의 linear attention family 선조.
시사점: Transformer와 RNN의 이분법은 허상 — 표현력(병렬성) vs 효율성(재귀) trade-off에서 φ가 다이얼 역할.
비판적 코멘트: 속도 이득은 명확하나 언어 모델링 품질 저하는 후속 연구(Performer, RFA)에서 비로소 부분 해결.

Discussion Points

논쟁점: softmax의 sharp selection이 본질적으로 필요한가 vs 단순 계산 아티팩트인가?
검증 필요 가정: 일반적인 Transformer 태스크에서도 linear attention이 충분한가? (Long Range Arena에서는 혼재된 결과)
후속 연구: Choromanski+ (Performer, 2020), Peng+ (Random Feature Attention, 2021), Sun+ (RetNet, 2023).

왜 이 연구를 하는가?

핵심 질문

Transformer의 softmax self-attention을 수학적으로 다시 써서, 시퀀스 길이 N에 대해 선형 시간/메모리로 동작하면서 autoregressive 추론은 RNN처럼 상수 시간 상태 갱신으로 할 수 있는가?

기존 접근법의 한계

한계	설명
O(N²) complexity	softmax가 전체 N×N 유사도 행렬을 요구
Autoregressive 생성 O(N²)	매 토큰마다 과거 K,V 전체 재계산·재어텐션
Sparse/low-rank 근사의 trade-off	Reformer(LSH), Sparse Transformer는 구현 복잡·근사 오차
RNN과의 단절	Transformer와 RNN이 서로 다른 패러다임으로 취급

핵심 통찰

softmax는 양의 유사도 커널의 특수 케이스일 뿐 — 일반 커널 $ϕ (q)^{⊤} ϕ (k)$ 로 바꾸면 행렬곱 결합법칙을 쓸 수 있다.
Causal 마스킹은 prefix sum으로 풀리며, prefix sum은 재귀식 = RNN이다.

방법 (Method)

프레임워크 개요 — softmax vs linear attention

flowchart TB
    subgraph Softmax["Softmax Attention — O(N²·d)"]
        Q1[Q: N×d] --> QK[Q·Kᵀ: N×N]
        K1[K: N×d] --> QK
        QK --> SM[softmax: N×N]
        SM --> AV[·V: N×d]
        V1[V: N×d] --> AV
        AV --> Out1[출력 N×d]
    end

    subgraph Linear["Linear Attention — O(N·d²)"]
        Q2[φ(Q): N×d] --> QS[φ(Q) · S]
        K2[φ(K): N×d] --> KV[φ(K)ᵀ · V: d×d]
        V2[V: N×d] --> KV
        KV --> S[S = φ(K)ᵀV]
        S --> QS
        QS --> Out2[출력 N×d]
    end

    Softmax -.재결합.-> Linear

핵심 구성요소

1) 특성 맵 φ
$ϕ (x) = elu (x) + 1 (양수 보장, 계산 저렴)$

2) 비-causal 선형 어텐션 (재결합)
$V_{i}^{'} = \frac{ϕ ( Q _{i} ) ^{⊤} \sum _{j} ϕ ( K _{j} ) V _{j}^{⊤}}{ϕ ( Q _{i} ) ^{⊤} \sum _{j} ϕ ( K _{j} )} = \frac{ϕ ( Q _{i} ) ^{⊤} ( ϕ ( K ) ^{⊤} V )}{ϕ ( Q _{i} ) ^{⊤} ( ϕ ( K ) ^{⊤} 1 )}$

3) Causal 선형 어텐션 (누적합)
$S_{i} = \sum_{j \leq i} ϕ (K_{j}) V_{j}^{⊤}, Z_{i} = \sum_{j \leq i} ϕ (K_{j})$
$V_{i}^{'} = \frac{ϕ ( Q _{i} ) ^{⊤} S _{i}}{ϕ ( Q _{i} ) ^{⊤} Z _{i}}$

4) RNN 재귀식 (Transformer = RNN)
$S_{i} = S_{i - 1} + ϕ (K_{i}) V_{i}^{⊤}, Z_{i} = Z_{i - 1} + ϕ (K_{i})$
$V_{i}^{'} = \frac{ϕ ( Q _{i} ) ^{⊤} S _{i}}{ϕ ( Q _{i} ) ^{⊤} Z _{i}}$

→ 상태 $S \in R^{d \times d}$ , $Z \in R^{d}$ 만 유지. 토큰당 O(d²).

발견 (Findings)

주요 결과

태스크	모델	품질	속도/메모리
MNIST gen.	softmax Transformer	bpd 기준선	1×
MNIST gen.	Reformer	근접	~수배 개선
MNIST gen.	Linear Transformer	근접 bpd	~4000× 빠른 생성 (Table 1)
CIFAR-10 gen.	Linear Transformer	softmax와 유사	N에 선형
Speech (WSJ)	Linear Transformer	biLSTM급 PER	softmax보다 빠름 (Table 2)

핵심 발견

Autoregressive 생성 속도의 질적 변화: O(N²)→O(N)으로 긴 시퀀스에서 3-4 orders of magnitude 가속.
품질 유지: 이미지/음성에서는 softmax와 대등. 반면 번역 같은 sharp-selection 태스크는 gap 존재.
RNN 관점의 위력: 학습은 병렬(prefix-sum kernel), 추론은 재귀 — 두 패러다임의 장점 결합.

이론적 의의

Transformer와 RNN의 통일

self-attention이 특정 커널을 가진 RNN의 일반화라는 점을 수식으로 보였다. 이후 RetNet·RWKV·Mamba 등 “Transformer-RNN 하이브리드”의 이론적 출발점이 된다.

커널 관점의 어텐션

어텐션을 양의 definite 커널로 재해석함으로써, Nyström·random feature·orthogonal projection 등 커널 문헌의 도구를 attention에 적용할 문을 열었다(Performer의 FAVOR+가 직접적 계승).

Prefix-sum 병렬성

causal attention의 누적합 구조는 scan/prefix-sum 알고리즘의 병렬성을 공유 — 이후 state-space model(S4, Mamba)의 selective scan과 직접 연결된다.

재현성 및 신뢰도 평가

항목	등급	비고
코드 공개	✅	fast-transformers 공식 라이브러리
데이터 공개	✅	MNIST/CIFAR-10/WSJ 표준 벤치
하이퍼파라미터	✅	부록에 layer/head/lr 명시
실험 환경	⚠️	GPU 종류는 있으나 seed 분산 제한적
통계적 신뢰도	⚠️	단일 run 위주, 표준편차 일부 누락
종합 등급	A	코드 품질·영향력 고려 시 매우 높은 재현성

주장별 신뢰도

#	주장	근거	신뢰도
1	Linear attention의 시간 복잡도는 O(N·d²)	수식 유도	🟢
2	Causal linear attention은 RNN과 등가	누적합→재귀식 변환 (수학적 증명)	🟢
3	품질이 softmax와 동등	이미지/음성은 ✅, 번역은 gap (⚠️)	🟡
4	Autoregressive 생성 4000× 가속 (MNIST)	Table 1, 공식 코드	🟢

읽기 난이도: ⭐⭐

Transformer 기본 구조와 커널법 기초(Mercer 정리 수준)를 알면 수식 추종 가능. 누적합→재귀식 부분이 핵심 아이디어.

축	Linear Transformer (본 논문)	Performer (2020)	RetNet (2023)	RWKV (2023)
핵심 접근	φ=elu+1 커널 + 누적합 RNN	FAVOR+ (orthogonal random features)	multi-scale retention + decay γ	time-mixing + channel-mixing RNN
Softmax 근사	간접(양의 커널)	unbiased softmax 근사	명시적 감쇠 weighting	gated RNN
RNN 등가성	✅ 증명 (재귀식)	✅ 유사 도출	✅ parallel/recurrent dual form	✅ 설계 자체가 RNN
긴 문맥 품질	⚠️ sharp 태스크 약함	🟢 softmax와 거의 같음	🟢 언어모델링 SOTA급	🟢 대규모 언어모델에서 검증
학습 병렬성	✅ prefix-sum	✅	✅ parallel form	⚠️ 제약 있음
코드	✅ fast-transformers	✅	✅	✅

원자적 인사이트 (Zettelkasten)

💡 softmax는 양의 커널의 특수 케이스이다

출처: Linear Attention - Transformers are RNNs (Katharopoulos et al., 2020)
유형: 이론적

softmax attention $exp (q^{⊤} k)$ 는 무한차원 gaussian 커널에 대응하는 특성 맵을 갖는다. 따라서 “어떤 양의 커널 $k (q, k) = ϕ (q)^{⊤} ϕ (k)$ “로 대체해도 attention의 정의적 성질(양의 가중 평균)은 보존된다. 이로부터 효율성-정확성 다이얼이 생긴다.

핵심 조건/맥락: 특성 맵이 양수여야 정규화 분모가 양수로 유지됨.
연결: Performer, Mercer 정리
활용 가능성: 도메인별 inductive bias를 φ에 설계해 Attention을 조건화.

💡 Causal masking은 prefix-sum으로 O(N)에 계산된다

출처: Linear Attention - Transformers are RNNs (Katharopoulos et al., 2020)
유형: 방법론적

커널화된 attention의 causal 마스크는 $S_{i} = \sum_{j \leq i} ϕ (k_{j}) v_{j}^{⊤}$ 의 누적합으로 표현되며, 이는 scan 연산이다. GPU scan kernel로 O(N) 병렬 학습이 가능하고 추론은 O(1) 상태 갱신.

핵심 조건/맥락: sim이 결합법칙을 허용하는 내적 형태일 때만 성립.
연결: Mamba의 selective scan, S4의 parallel scan
활용 가능성: 어떤 autoregressive 모델이든 prefix-sum 구조를 발견하면 RNN-Transformer 이중 형식화 가능.

💡 Transformer와 RNN은 동일한 모델 패밀리의 양 끝

출처: Linear Attention - Transformers are RNNs (Katharopoulos et al., 2020)
유형: 연결

같은 $ϕ, Q, K, V$ 파라미터로 학습 시에는 parallel attention, 추론 시에는 재귀 상태 업데이트로 해석할 수 있다. “parallel-train, recurrent-infer” 패턴은 이후 RetNet이 명시화.

핵심 조건/맥락: 커널 내적 형태 attention에 한함 (softmax는 불가).
연결: RetNet dual form, RWKV
활용 가능성: 학습 병렬성과 추론 상수시간을 동시에 얻는 설계 원칙.

💡 Sharp selection은 linear attention의 구조적 약점이다

출처: Linear Attention - Transformers are RNNs (Katharopoulos et al., 2020)
유형: 실패-한계

softmax는 temperature가 낮은 distribution을 자연스럽게 만들어 “특정 토큰 하나에 집중”하는 copy/lookup을 잘 수행한다. 양의 커널 근사는 이 sharp peak를 얕게 만들어 정확 copy·retrieval 품질이 떨어진다.

핵심 조건/맥락: 번역·in-context learning처럼 정확한 토큰 선택이 필요한 태스크.
연결: Performer의 FAVOR+가 일부 완화, cosFormer/Hedgehog가 sharpening 제안
활용 가능성: Sharpness를 파라미터화(예: 학습된 temperature, polynomial φ)하면 정확-효율 trade-off 제어.

💡 상태 크기 $d \times d$ 가 메모리 용량의 한계다