Why Are Linear RNNs More Parallelizable?

이 논문은 선형 RNN(LRNN) 이 비선형 RNN 보다 병렬화가 용이한 이유를 복잡도 클래스 (Log-depth 회로 대 P-완전 문제) 와 오토마타 이론을 통해 이론적으로 규명하고, 다양한 LRNN 변형 간의 정밀한 표현력 차이를 분석하여 표현력과 병렬성 사이의 균형을 잡는 LLM 아키텍처 설계의 기초를 제공합니다.

핵심

1. 핵심 문제: "순서대로 해야 하는가, 동시에 해도 되는가?"

AI 모델 (LLM) 이 긴 문장을 처리할 때 두 가지 방식이 있습니다.

• 기존 방식 (비선형 RNN): 마치 한 명의 요리사가 요리를 하는 것과 같습니다.
  • 첫 번째 재료를 다듬고, 그다음에 두 번째 재료를 다듬고, 그다음에 세 번째...
  • 문제: 요리사가 한 번에 한 가지 일만 할 수 있으므로, 재료가 많으면 시간이 매우 오래 걸립니다. (순차적 처리)
  • 장점: 아주 복잡한 레시피 (수학적 문제) 를 풀 수 있는 뛰어난 두뇌를 가졌습니다.
• 새로운 방식 (선형 RNN & 트랜스포머): 마치 수백 명의 요리사들이 팀을 이루어 일하는 공장과 같습니다.
  • 모든 재료를 동시에 준비하고, 동시에 자르고, 동시에 볶습니다.
  • 장점: 재료가 아무리 많아도 시간이 거의 걸리지 않습니다. (병렬 처리)
  • 단점: 너무 복잡한 레시피는 풀지 못할 수도 있습니다.

질문: "왜 선형 RNN 은 공장처럼 동시에 일할 수 있는데, 기존 비선형 RNN 은 계속 혼자 일해야 할까?"

---

2. 이 논문이 발견한 비밀: "계산의 깊이 (Depth)"

논문은 컴퓨터 이론 (복잡도 이론) 을 이용해 이 차이를 수학적으로 증명했습니다.

🧱 비선형 RNN: "미로 찾기"

• 비유: 비선형 RNN 은 매우 복잡한 미로를 통과하는 것과 같습니다.
• 특징: 앞의 단계를 완전히 해결하지 않으면 다음 단계로 갈 수 없습니다.
• 결과: 이 미로를 해결하려면 컴퓨터가 **매우 깊은 계단 (O(log² n))**을 올라가야 합니다. 계단이 깊을수록 병렬로 일할 수 있는 여지가 적어집니다.
• 위험성: 만약 이 미로가 너무 복잡해지면 (P-완전 문제), 아무리 많은 요리사를 불러도 동시에 일할 수 없습니다. 결국 한 명만 일해야 하는 상황이 됩니다.

🏗️ 선형 RNN: "간단한 사다리"

• 비유: 선형 RNN 은 짧고 평평한 사다리를 오르는 것과 같습니다.
• 특징: 각 단계가 서로 독립적이거나 매우 단순하게 연결되어 있습니다.
• 결과: 이 사다리는 **매우 얕은 계단 (O(log n))**만 있습니다.
• 장점: 얕은 계단이라면 수백 명의 요리사 (프로세서) 가 동시에 올라갈 수 있습니다. 트랜스포머 (Transformer) 와 거의 같은 속도로 병렬 처리가 가능합니다.

핵심 결론: 선형 RNN 은 "계산의 깊이"를 의도적으로 얕게 설계했기 때문에, 공장처럼 동시에 일할 수 있는 것입니다.

---

3. 선형 RNN 안에서도 차이가 있다? (세부 버전 비교)

논문은 선형 RNN 이 모두 똑같은 것은 아니라고 말합니다. 마치 공장 안에도 작업 방식에 따라 능력이 다르듯이요.

1. PD 선형 RNN (Permutation-Diagonal):
   • 비유: 규칙적인 조립 라인.
   • 능력: 기본적인 문제 (NC1 클래스) 는 잘 풀지만, 아주 복잡한 수학 문제 (PNC1) 는 풀지 못합니다. 트랜스포머보다 조금 더 똑똑하지만, 여전히 "병렬 처리"에 최적화되어 있습니다.
2. DPLR 선형 RNN (DeltaNet, RWKV-7 등):
   • 비유: 유연한 스마트 공장.
   • 능력: PD 버전보다 더 똑똑합니다. 아주 복잡한 수학 문제 (PNC1 클래스) 도 풀 수 있습니다.
   • 중요한 점: 아직도 병렬 처리가 가능합니다! 복잡한 문제를 풀면서도 공장처럼 동시에 일할 수 있는 '마법'을 부립니다. 이것이 최근 RWKV-7 이나 DeltaNet 이 각광받는 이유입니다.

---

4. 실험 결과: 이론이 현실로 증명되다

저자들은 이 이론을 검증하기 위해 인공적인 미션 (그래프 연결성 문제, 행렬 곱셈) 을 모델들에게 시켰습니다.

• 그래프 연결성 (비선형 RNN 만 가능한 미션):
  • 비선형 RNN (기존 방식) 은 잘 해결했지만, 선형 RNN 과 트랜스포머는 실패했습니다.
  • 이유: 이 문제는 "깊은 미로"를 찾아야 하므로, 순차적으로 생각해야 하는 비선형 RNN 의 두뇌가 필요했기 때문입니다.
• 행렬 곱셈 (선형 RNN 이 가능한 미션):
  • DPLR 선형 RNN (RWKV-7, DeltaNet) 은 이 복잡한 계산을 완벽하게 해결했습니다.
  • 이유: 이 문제는 "얕은 사다리"를 오르는 방식으로도 해결 가능하기 때문입니다.

---

5. 요약: 우리에게 어떤 의미가 있는가?

이 논문은 AI 개발자들에게 다음과 같은 지도를 제시합니다.

1. 속도와 지능의 트레이드오프: "무조건 빠른 것"과 "무조건 똑똑한 것"은 종종 충돌합니다. 비선형 RNN 은 지능이 높지만 느리고, 선형 RNN 은 빠르지만 지능이 제한될 수 있습니다.
2. 최적의 균형점 찾기: 하지만 **DPLR 선형 RNN (RWKV-7, DeltaNet)**은 이 두 마리 토끼를 잡을 수 있는 황금 지점입니다.
   • 트랜스포머만큼 빠르게 병렬 처리가 가능합니다.
   • 동시에 기존 비선형 RNN 에 버금가는 복잡한 계산 능력도 갖추고 있습니다.

마무리 비유:
과거의 AI 는 "한 명의 천재 요리사"가 천천히 요리를 했습니다. 트랜스포머는 "수천 명의 로봇"이 빠르게 요리를 했지만 복잡한 레시피는 못 했습니다. 이제 **선형 RNN (특히 DPLR 버전)**은 "수천 명의 로봇이면서도 천재 요리사처럼 복잡한 레시피도 해내는" 새로운 시대를 열었습니다.

이론적으로 증명된 이 발견은 앞으로 더 빠르고 똑똑한 AI 를 만드는 설계도의 기준이 될 것입니다.

기술 요약

1. 문제 제기 (Problem)

• 배경: 최근 대규모 언어 모델 (LLM) 아키텍처 설계에서 Transformer 의 병렬 처리 능력과 RNN 의 장기 의존성 학습 능력을 결합하려는 시도가 늘고 있습니다. 특히 선형 상태 업데이트를 사용하는 LRNN (예: Mamba, RWKV, DeltaNet) 이 Transformer 와 유사한 병렬 처리 속도를 가지면서도 높은 표현력을 가진다는 점이 주목받고 있습니다.
• 핵심 질문: 기존 연구는 LRNN 이 Transformer 보다 표현력이 높을 수 있음을 보였지만, 왜 비선형 RNN 은 LRNN 과 Transformer 만큼 효율적으로 병렬화할 수 없는지에 대한 명확한 이론적 설명은 부족했습니다.
• 목표: RNN 의 유형 (선형 vs 비선형, 그리고 LRNN 의 하위 유형들) 과 계산 복잡도 클래스 (Complexity Classes) 간의 밀접한 관계를 규명하여, 병렬화의 한계와 표현력의 차이를 수학적으로 증명하는 것.

2. 방법론 (Methodology)

저자는 **회로 복잡도 **(Circuit Complexity)와 **자동자 이론 **(Automata Theory)을 결합하여 RNN 아키텍처를 분석했습니다.

• 계산 모델 정의:
  • 비선형 RNN: ReLU 또는 MLP 게팅 함수를 사용하여 비선형 상태 업데이트를 수행하는 모델.
  • **선형 RNN **(LRNN): 상태 업데이트가 선형 연산 (행렬 곱셈 및 덧셈) 으로만 이루어지는 모델. 구체적으로 DPLR(Diagonal-Plus-Low-Rank, 예: DeltaNet, RWKV-7) 과 PD(Permutation-Diagonal, 예: PD-SSM) 파라미터화를 다룹니다.
  • **정밀도 **(Precision): 계산에 사용되는 숫자의 정밀도를 '로그 정밀도 (log-precision)'와 '다항식 정밀도 (poly-precision)'로 구분하여 분석했습니다.
• 복잡도 클래스 매핑:
  • 각 RNN 모델이 해결할 수 있는 문제들을 NC1, PNC1, L, P 등의 복잡도 클래스에 매핑했습니다.
  • 특히, PNC1 클래스는 로그 깊이 (log-depth)의 산술 회로 (arithmetic circuits) 로 정의되며, 이는 Transformer 가 속한 TC0보다 약간 강력하지만 여전히 효율적으로 병렬화 가능한 범위로 간주됩니다.
• 이론적 증명 및 실험 검증:
  • 이론: 각 RNN 유형이 특정 복잡도 클래스에 속하거나 그 클래스 내의 완전 문제 (complete problem) 를 해결할 수 있음을 증명했습니다.
  • 실험: 합성 작업 (Synthetic Tasks) 인 '정렬된 결정적 그래프 연결성 (Sorted Deterministic Graph Connectivity)'과 '반복 행렬 곱셈 (Iterated Matrix Multiplication)'을 통해 이론적 예측이 실제 학습 성능과 일치하는지 검증했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

A. 비선형 RNN 의 병렬화 한계

• **다항식 정밀도 **(Poly-precision): 비선형 RNN 은 P-complete 문제를 해결할 수 있습니다 (Turing Complete). 이는 NC ≠ P라는 가정 하에, 비선형 RNN 을 로그 다항식 (poly-log) 깊이의 회로로 병렬화하는 것이 불가능함을 의미합니다. 즉, 본질적으로 순차적인 계산을 요구합니다.
• **로그 정밀도 **(Log-precision): 정밀도가 제한된 경우에도 비선형 RNN 은 L-complete 문제를 해결할 수 있습니다. 이는 Transformer (TC0) 나 LRNN 에 비해 회로 깊이가 **Ω(log² n)**으로 커질 수 있음을 의미하며, Transformer 대비 **O(log n)**의 오버헤드가 발생합니다.

B. 선형 RNN (LRNN) 의 높은 병렬성

• PNC1 클래스: 모든 LRNN 은 PNC1 복잡도 클래스에 속합니다. 이는 로그 깊이의 산술 회로로 시뮬레이션 가능함을 의미합니다.
• Transformer 와의 비교: LRNN 은 Transformer (TC0 ⊂ NC1) 와 거의 동일한 수준의 병렬화 효율을 가집니다. 구체적으로, LRNN 을 시뮬레이션하는 회로의 깊이는 *O(log n log n)**으로, Transformer 대비 *O(log n)**의 미미한 오버헤드만 발생합니다. 이는 하드웨어 관점에서 매우 효율적인 병렬 처리가 가능함을 의미합니다.

C. LRNN 내부의 정밀한 표현력 차이 (Fine-grained Expressivity)

모든 LRNN 이 동일한 것은 아니며, 파라미터화 방식에 따라 표현력에 차이가 있음을 규명했습니다.

1. **DPLR LRNN **(DeltaNet, RWKV-7): PNC1-complete 문제를 해결할 수 있습니다. 이는 반복 행렬 곱셈 (Iterated Matrix Multiplication) 과 같은 복잡한 대수적 구조를 학습할 수 있음을 의미합니다.
2. **PD LRNN **(Permutation-Diagonal): NC1-complete으로 제한됩니다. 이는 DPLR 보다 표현력이 약하며, 결정적 유한 자동자 (Deterministic WFA) 와 동등한 능력을 가집니다.
3. 결론: DPLR 구조가 PD 구조보다 표현력이 높지만, 여전히 P-complete 비선형 RNN 보다는 병렬화 효율이 훨씬 좋습니다.

D. 실험적 검증

• 그래프 연결성 작업: 이론적으로 L-complete 문제인 그래프 연결성 작업에서 비선형 RNN만이 높은 정확도를 보였으며, Transformer 와 LRNN (Mamba, RWKV-7 등) 은 성능이 저하되었습니다. 이는 비선형 RNN 의 순차적 추론 능력을 보여줍니다.
• 행렬 곱셈 작업: PNC1-complete 인 반복 행렬 곱셈 작업에서는 DPLR LRNN(RWKV-7, DeltaNet) 과 비선형 RNN 이 높은 성능을 보였으나, Transformer 와 Mamba 는 학습에 실패했습니다. 이는 DPLR LRNN 이 Transformer 보다 높은 대수적 표현력을 가짐을 입증했습니다.

4. 의의 및 결론 (Significance & Conclusion)

이 논문은 다음과 같은 중요한 통찰을 제공합니다:

1. 이론적 근거 확립: LRNN 이 왜 비선형 RNN 보다 병렬화하기 쉬운지에 대한 엄밀한 복잡도 이론적 근거를 제시했습니다. 비선형 RNN 은 본질적으로 순차적 계산 (P-complete 또는 L-complete) 을 필요로 하지만, LRNN 은 로그 깊이 회로 (PNC1) 로 근사 가능하여 Transformer 와 유사한 병렬 효율을 가집니다.
2. 아키텍처 설계 가이드라인:
   • 병렬성 vs 표현력 트레이드오프: 비선형 RNN 은 높은 표현력을 가지지만 병렬화 비용이 큽니다. LRNN 은 병렬화 효율이 높으면서도 Transformer 보다 높은 표현력 (PNC1) 을 제공합니다.
   • 최적의 아키텍처: DPLR 기반의 LRNN (DeltaNet, RWKV-7 등) 은 Transformer 의 병렬성과 비선형 RNN 의 일부 표현력 사이의 최적 균형을 이룰 수 있는 유망한 후보임을 보여줍니다.
3. 향후 연구 방향: LRNN 의 표현력을 극대화하면서도 병렬성을 유지하는 새로운 아키텍처 설계에 이론적 토대를 마련했습니다. 또한, 합성 작업 (Synthetic Tasks) 을 통해 모델의 추론 능력을 평가하는 새로운 벤치마크의 중요성을 강조했습니다.

요약하자면, 이 연구는 선형 RNN 이 비선형 RNN 의 순차적 병목 현상을 우회하면서도 Transformer 를 능가하는 표현력을 가질 수 있는 수학적 이유를 증명함으로써, 차세대 효율적인 LLM 아키텍처 개발의 방향성을 제시합니다.