RNN이 Transformer에 밀린 이유, 그리고 Mamba가 돌아온 이유

RNN은 순차적으로 작동한다. GPU는 병렬적으로 작동한다. 이 둘이 만나면 무슨 일이 벌어지는가? 그리고 왜 2023년, 선형 재귀를 앞세운 Mamba가 다시 RNN-like 구조로 돌아왔는가?

순차 의존의 벽

RNN의 forward pass는 다음 점화식으로 정의된다.

$$h_t = f(h_{t-1}, x_t)$$

$h_t$를 계산하려면 $h_{t-1}$이 반드시 먼저 완료되어야 한다. 이 의존 사슬의 깊이는 정확히 $T$ — 시퀀스 길이. GPU가 수만 개의 코어를 가지고 있어도, 매 스텝 하나의 연산만 통과할 수 있다.

GPU utilization의 관점에서 이 문제는 치명적이다. H100의 약 16K 코어에서 $T = 1000$의 RNN을 돌리면, 스텝당 utilization은 100%에 가깝지만 wall-clock 시간은 $T$에 선형으로 늘어난다. 사실상 코어를 단 하나씩 쓰는 것과 다름없다.

Transformer의 답: $O(T^2)$ 비용으로 완전 병렬화

Self-attention은 모든 $(i, j)$ 쌍의 유사도를 동시에 계산한다.

$$\text{Attention}(Q, K, V) = \text{softmax}\!\left(\frac{QK^\top}{\sqrt{d_k}}\right) V$$

$T \times T$ attention matrix의 모든 entry가 독립적으로 계산 가능하다. 거대한 행렬곱 하나가 GPU 코어 전체를 채운다. Critical path는 행렬곱 내부의 reduction tree에 해당하므로 $O(\log T)$다.

Vaswani 2017의 실측값이 이를 뒷받침한다. WMT’14 En→De 학습에서 Google NMT(LSTM 기반)는 8 GPU로 16일, Transformer-Big은 동일 하드웨어로 3.5일 — 약 5배 빠르면서 BLEU도 높았다.

대가는 명확하다. $O(T^2)$ 메모리. $T = 10{,}000$이면 한 레이어의 attention matrix 하나가 400 MB(fp32)를 차지한다. $T = 100{,}000$이면 40 GB — 단일 레이어에서.

CNN의 우회로: WaveNet과 TCN

Transformer 이전에도 RNN의 sequential 한계를 우회하려는 시도가 있었다. WaveNet(van den Oord 2016)은 causal dilated convolution으로 이를 달성했다.

$$y_t = \sum_{i=0}^{k-1} w_i \cdot x_{t - d \cdot i}$$

dilation rate $d$를 $1, 2, 4, \ldots, 2^{L-1}$로 쌓으면, $L$개 레이어로 $O(2^L)$의 receptive field를 만든다. $L = 10, k = 2$이면 RF = 1024. 각 레이어 내의 모든 출력 위치는 독립적으로 계산되므로 critical path는 레이어 수 $L = \log_2 T$에 불과하다.

Bai 2018의 TCN(Temporal Convolutional Network)은 이를 일반화해 sequential MNIST, adding problem 등 다양한 벤치마크에서 LSTM을 능가했다. 그러나 receptive field가 architecture로 고정된다는 본질적 한계가 있다. 더 긴 의존성이 필요하면 레이어를 추가해야 하고, Transformer의 전역 attention과 달리 RF 밖의 토큰은 직접 볼 수 없다.

Linear Attention: 결합법칙의 이동

Transformer의 $O(T^2)$ 문제를 다른 방향에서 공격한 것이 Katharopoulos 2020의 linear attention이다. 핵심 아이디어는 softmax를 kernel feature map으로 근사한 뒤 연산 순서를 바꾸는 것이다.

$$\text{Attn} = \underbrace{\phi(Q) \underbrace{(\phi(K)^\top V)}_{\in \mathbb{R}^{d \times d}}}_{\text{$O(Td^2)$ 전체}}$$

$T \times T$ matrix가 사라지고 $d \times d$ matrix만 남는다. 더 중요한 것은, causal linear attention이 정확히 RNN의 update rule로 환원된다는 점이다.

$$S_t = S_{t-1} + \phi(k_t) v_t^\top, \quad \text{output}_t = \phi(q_t) S_t$$

inference 시 KV-cache 대신 $d \times d$ 상태 하나만 유지하면 된다. GPT-3 규모(96레이어, 96헤드, $d=128$)에서 $T = 2048$ 기준 KV-cache는 약 19 GB지만, linear attention 상태는 약 0.6 GB다.

RWKV(Peng 2023)는 이 정신을 LLM 스케일로 밀어붙였다. time-decay 파라미터 $w$와 bonus $u$로 gating을 추가한 RWKV-14B는 비슷한 규모의 GPT 계열과 경쟁력 있는 벤치마크를 보여줬다.

표현력의 대가는 있다. Linear attention은 $d_\phi$-rank 근사 — softmax attention이 가능한 sharp, sparse한 attention pattern을 표현하기 어렵다. in-context learning에서 Transformer 대비 약함이 경험적으로 관찰된다.

Mamba: 선택적 상태 공간과 병렬 스캔

S4(Gu 2022)는 제어이론의 연속 상태 공간 모델을 deep learning에 도입했다.

$$\dot{x}(t) = Ax(t) + Bu(t), \quad y(t) = Cx(t)$$

이를 이산화하면($\Delta$ 샘플링):

$$\bar{A} = \exp(\Delta A), \quad \bar{B} = (\bar{A} - I)A^{-1}B$$ $$x_t = \bar{A} x_{t-1} + \bar{B} u_t, \quad y_t = C x_t$$

S4의 $A$는 input-independent — 모든 토큰에 같은 dynamics. Mamba(Gu & Dao 2023)의 핵심 혁신은 이를 selective로 만드는 것이다.

$$\Delta_t, B_t, C_t = f(x_t)$$

입력에 따라 dynamics가 바뀐다. $A_t \approx I$이면 과거 상태를 보존(long memory), $A_t \approx 0$이면 리셋(forget). attention의 content-dependent selection과 기능적으로 동등한 효과를 $O(T)$에 달성한다.

학습 시에는 병렬 스캔(Blelloch 1990)으로 $O(\log T)$ depth를 실현한다. 선형 재귀

$$h_t = A h_{t-1} + B u_t$$

는 결합법칙을 만족하는 이항 연산의 prefix sum으로 볼 수 있다. up-sweep(쌍별 reduction) → down-sweep(전파)의 트리 구조로 $O(T)$ work, $O(\log T)$ depth.

LRA(Long Range Arena) benchmark의 Path-X task — 16K 토큰 시퀀스에서 두 점이 같은 연결 경로에 있는지 판별 — 에서 vanilla Transformer, linear attention, 심지어 S4조차 랜덤 수준(50%)에 머물렀다. Mamba가 처음으로 의미 있는 성능(~70-80%)을 기록했다.

정리

• RNN의 sequential bottleneck은 $h_t = f(h_{t-1}, x_t)$의 의존 사슬에서 온다. GPU의 수천 코어가 있어도 한 번에 하나의 스텝만 통과한다.
• Transformer는 $O(T^2)$ 비용을 지불하고 완전 병렬화를 달성했다. 2017년 이후 NLP의 표준이 된 이유는 더 좋은 알고리즘이 아니라 더 잘 맞는 하드웨어 활용이었다.
• Linear attention과 RWKV는 kernel 근사로 $O(T)$ inference를 달성했지만 표현력의 trade-off를 피하지 못했다.
• Mamba는 선형 재귀 + 선택적 dynamics + parallel scan의 조합으로 “RNN의 효율성과 Transformer의 품질”을 처음으로 동시에 달성했다. sequential dependency의 근본 원인이 재귀가 아닌 비선형성이었다는 통찰이 핵심이다.
• 현재 추세는 단일 아키텍처의 지배가 아니라 Mamba + Transformer 레이어의 hybrid(Jamba 등)다. 아키텍처 다양성이 새로운 norm이다.