On the Computational Hardness of Transformers

이 논문은 SETH(Strong Exponential Time Hypothesis) 와 행렬 곱셈 지수 $\omega$를 기반으로 한 새로운 하한 증명을 통해, 다중 헤드 다중 레이어 트랜스포머를 개별 어텐션 연산보다 더 효율적으로 계산할 수 없음을 보여줌으로써 트랜스포머의 계산적 복잡성에 대한 최초의 비자명한 하한을 확립했습니다.

핵심

이 논문은 현대 인공지능의 핵심인 '트랜스포머 (Transformer)' 모델이 얼마나 계산적으로 무거운지, 그리고 우리가 그 속도를 획기적으로 높일 수 있는 '비밀의 열쇠'가 있는지 연구한 결과입니다.

간단히 말해, **"여러 개의 Attention(주의) 헤드를 한 번에 처리하는 것이, 각각 따로 처리하는 것보다 정말로 더 빠를 수 있을까?"**라는 질문에 대해 **"아니요, 각각 따로 푸는 것이 이미 최선입니다"**라고 결론 내린 연구입니다.

이 복잡한 내용을 일상적인 비유로 쉽게 풀어보겠습니다.

---

🍕 1. 배경: 거대한 피자 가게와 주문 처리

트랜스포머 모델은 거대한 피자 가게라고 상상해 보세요.

• 입력 (Token): 손님이 주문한 피자의 토핑들 (예: 페퍼로니, 버섯, 올리브).
• Attention(주의) 헤드: 각 토핑이 서로 어떻게 어울리는지 분석하는 전문 셰프들입니다. (예: "페퍼로니와 올리브는 잘 어울리네?"라고 판단).
• 레이어 (Layer): 이 셰프들이 여러 번 거쳐 최종 피자를 완성하는 과정입니다.

이 가게에는 **L 개의 층 (Layer)**이 있고, 각 층에는 **H 명의 셰프 (Head)**가 있습니다. 총 L × H 명의 셰프가 동시에 일하는 셈이죠.

🚀 2. 기존의 생각: "함께 하면 더 빠르지 않을까?" (직합 문제)

지금까지 연구자들은 이런 생각을 했습니다.

"셰프들이 100 명이나 있는데, 각각 따로따로 일하면 시간이 너무 걸리지 않을까? 만약 100 명이 함께 일하는 시스템을 만든다면, 각각 일하는 것보다 훨씬 효율적이지 않을까?"

이는 마치 "100 개의 공을 동시에 던지는 것이, 하나씩 던지는 것보다 더 빠를까?"라는 질문과 같습니다. 수학에서는 이를 **'직합 (Direct Sum) 문제'**라고 부릅니다. 어떤 문제들은 함께 풀면 빨라지지만 (예: 100 개의 다항식을 한 번에 계산), 어떤 문제들은 함께 풀어도 소용없습니다.

🛑 3. 이 논문의 결론: "아니요, 따로 하는 게 이미 최고입니다"

이 논문은 **"트랜스포머는 함께 처리해도 속도가 빨라지지 않는다"**라고 증명했습니다.

📌 상황 A: 작은 피자 (작은 임베딩 차원)

피자 크기가 작을 때 (데이터의 특징이 간단할 때), 셰프들이 각각 따로 일하는 데 걸리는 시간은 이미 최적입니다.

• 비유: 100 명의 셰프가 각각 작은 피자를 만들 때, "함께 일하는 특별한 시스템"을 도입한다고 해서 시간이 줄어들지 않습니다. 오히려 각자가 가진 고유한 계산 과정 (수학적 증명에 따르면 3-OV 가설 등) 때문에, 따로따로 계산하는 것이 이론적으로도 더 이상 빨라질 수 없습니다.
• 결론: "각자 일하는 것"이 이미 최고의 속도입니다.

📌 상황 B: 거대한 피자 (큰 임베딩 차원)

피자가 엄청나게 크고 복잡할 때 (데이터의 특징이 매우 방대할 때)는 어떨까요?

• 비유: 이때는 셰프들이 피자를 만들 때 **거대한 매트릭스 (수학적 표)**를 계산해야 합니다. 이 논문은 "여러 개의 매트릭스를 한 번에 계산하는 것"이 "각각 따로 계산하는 것"과 동일한 난이도임을 증명했습니다.
• 핵심 도구: 연구자들은 **'바우 - 스트라센 정리 (Baur-Strassen theorem)'**라는 강력한 도구를 사용했습니다. 이는 마치 "요리 과정의 모든 단계에서 나오는 부산물 (기울기/미분) 을 이용하면, 원래 요리를 만드는 과정이 얼마나 복잡한지 역추적할 수 있다"는 원리입니다.
• 결과: 이 도구를 통해 "여러 개의 매트릭스 곱셈을 한 번에 처리하는 마법"은 존재하지 않으며, 각각 따로 계산하는 것이 수학적으로도 가장 효율적인 방법임을 증명했습니다.

💡 4. 왜 이 연구가 중요한가요?

1. 기대감 조절: 많은 사람들이 "트랜스포머를 더 빠르게 만드는 새로운 알고리즘"을 기다리고 있습니다. 하지만 이 논문은 **"단순히 여러 개를 묶어서 처리하는 방식으로는 속도를 획기적으로 높일 수 없다"**고 말합니다. 즉, 우리가 원하는 '마법의 속도 향상'은 존재하지 않을 가능성이 높습니다.
2. 방향 전환: 이제 우리는 "여러 개를 묶는 것"이 아니라, Attention 메커니즘 자체를 근본적으로 바꾸거나, 하드웨어를 최적화하는 등 다른 길을 찾아야 함을 시사합니다.
3. 이론적 승리: 컴퓨터 과학 이론에서 "여러 문제를 동시에 풀면 더 빠를까?"라는 오래된 질문에 대해, 트랜스포머라는 현대 AI 의 핵심 모델에 대해 명확한 '아니요'를 답한 첫 번째 연구 중 하나입니다.

🎯 요약

이 논문은 **"트랜스포머 모델은 여러 개의 Attention 헤드를 동시에 처리한다고 해서 속도가 빨라지지 않는다"**고 말합니다.

• 작은 데이터든, 큰 데이터든 각각 따로 계산하는 것이 이미 이론적으로 가능한 가장 빠른 방법입니다.
• 우리는 더 이상 "함께 하면 빠르겠지?"라는 기대를 버리고, 각각의 계산을 더 효율적으로 만드는 다른 방법을 찾아야 합니다.

마치 **"100 명의 요리사가 함께 일한다고 해서 100 개의 요리를 만드는 시간이 줄어들지 않는다"**는 것을 수학적으로 증명해낸 셈입니다. 이제 우리는 각 요리사의 기술을 더 높이는 데 집중해야 할 때입니다.

기술 요약

이 논문은 트랜스포머 (Transformer) 아키텍처의 계산적 난이도 (Computational Hardness) 에 대한 이론적 분석을 다룹니다. 저자들은 다중 헤드 (Multi-head) 와 다중 레이어 (Multi-layer) 를 가진 트랜스포머를 계산할 때, 각 어텐션 헤드를 독립적으로 계산하는 단순한 알고리즘이 본질적으로 최적임을 증명했습니다. 즉, 여러 개의 동일한 문제를 동시에 해결함으로써 계산 비용을 줄일 수 있다는 '직접 합 (Direct Sum)' 문제가 트랜스포머의 경우 성립하지 않음을 보여줍니다.

다음은 논문의 주요 내용을 기술적으로 요약한 것입니다.

1. 연구 문제 (Problem)

트랜스포머는 자연어 처리 및 컴퓨터 비전 등 다양한 분야에서 혁신을 이끌었으나, 계산 비용이 매우 높습니다. 특히 입력 길이 $N$에 대해 어텐션 메커니즘의 복잡도는 $O(N^2)$으로 2 차적으로 증가합니다.
기존 연구들은 단일 어텐션 헤드의 계산 복잡도에 대한 하한선 (Lower Bound) 을 제시했으나, $L$개의 레이어와 $H$개의 헤드를 가진 전체 트랜스포머를 계산할 때, 각 헤드를 독립적으로 계산하는 방식 ($L \times H$번의 계산) 보다 더 효율적인 방법이 존재할 수 있는지 여부는 명확하지 않았습니다. 이는 이론 컴퓨터 과학의 '직접 합 (Direct Sum)' 문제와 관련이 있습니다.

핵심 질문: $L$개의 레이어와 $H$개의 헤드를 가진 트랜스포머를 계산하는 것이, $LH$개의 어텐션 헤드를 독립적으로 계산하는 것보다 더 효율적으로 수행될 수 있는가?

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

저자들은 두 가지 주요 시나리오 (작은 임베딩 차원과 큰 임베딩 차원) 에 대해 트랜스포머 계산의 하한선을 증명했습니다.

A. 작은 임베딩 차원 (Small Embedding Dimension, $m = N^{o(1)}$)

• 가정: 3-OV 가설 (3 Orthogonal Vectors Hypothesis) 또는 강한 지수 시간 가설 (SETH) 을 기반으로 합니다.
• 결과: $L$개의 레이어와 $H$개의 헤드를 가진 트랜스포머를 계산하는 데 필요한 시간은 하한선 $LHN^{2-o(1)}$입니다.
• 의미: 이는 각 어텐션 헤드를 독립적으로 계산하는 단순한 알고리즘의 시간 복잡도 $O(LHN^2)$과 거의 일치합니다. 즉, 어텐션 헤드를 병렬로 처리한다고 해서 계산 복잡도가 획기적으로 줄어들지 않습니다.
• 증명 방법: 3-OV 문제를 트랜스포머의 입력으로 매핑하여, 트랜스포머가 3-OV 문제를 해결할 수 있음을 보였습니다. 구체적으로, $A, B, C$ 세 집합의 벡터들 중 직교하는 3-튜플이 존재하는지 여부를 트랜스포머의 출력으로 판별하도록 설계했습니다.

B. 큰 임베딩 차원 (Large Embedding Dimension, $m = N$)

• 가정: 행렬 곱셈 지수 $\omega$ (현재 약 2.373) 를 사용합니다. 별도의 복잡도 가설 없이 순수 대수적 회로 (Arithmetic Circuit) 모델을 기반으로 합니다.
• 결과: 확장된 대수적 회로 (Extended Arithmetic Circuit, eAC) 모델에서 $L$층 $H$헤드 트랜스포머를 계산하는 회로의 크기는 하한선 $LHN^{\omega-o(1)}$입니다.
• 의미: 행렬 곱셈을 빠르게 수행하는 알고리즘 (Fast Matrix Multiplication) 을 사용하는 것 외에는 트랜스포머 계산 속도를 획기적으로 개선할 수 없음을 의미합니다.
• 증명 방법:
  1. 비정규화 어텐션 (Denormalized Attention): Softmax 대신 요소별 지수 함수 (exp) 를 사용하는 변형 어텐션을 정의하여 행렬 곱셈과 직접적인 연결을 용이하게 했습니다.
  2. 바우 - 스트라센 정리 (Baur-Strassen Theorem) 의 확장: 이 정리는 함수를 계산하는 회로가 존재하면, 그 함수의 모든 편미분 (Partial Derivatives) 을 거의 동일한 크기의 회로로 계산할 수 있음을 보장합니다. 저자들은 이를 확장된 대수적 회로 (exp, ln 게이트 포함) 로 일반화했습니다.
  3. 미분을 통한 역추적: 트랜스포머의 출력을 특정 보조 변수에 대해 미분함으로써, 트랜스포머 내부에서 $LH$개의 독립적인 행렬 곱셈 ($A_k B_k^\top$) 을 추출해낼 수 있음을 보였습니다.
  4. 하한선 도출: $LH$개의 독립적인 행렬 곱셈을 계산하는 데 필요한 회로 크기는 $LHN^{\omega-o(1)}$이므로, 이를 계산하는 트랜스포머 회로도 최소한 이만큼 커야 함을 증명했습니다.

3. 방법론 (Methodology)

1. 모델 정의:

   • 작은 차원: 3-OV 가설을 사용하여 조건부 하한선 (Conditional Lower Bound) 을 증명합니다. Hardmax 어텐션을 Softmax 로 근사화할 수 있음을 이용하여 실제 트랜스포머 모델에 적용합니다.
   • 큰 차원: 확장된 대수적 회로 (Extended Arithmetic Circuit, eAC) 모델을 도입합니다. 이는 표준 대수적 회로 (+, -, *, /) 에 지수 (exp) 와 로그 (ln) 게이트를 추가한 것으로, 트랜스포머의 Softmax 연산을 모델링하는 데 필수적입니다.

2. 증명 전략:

   • 작은 차원: 3-OV 인스턴스를 트랜스포머의 입력으로 인코딩합니다. 특정 어텐션 헤드가 직교하는 벡터 쌍을 감지하면 출력 값이 달라지도록 설계하여, 트랜스포머의 총합을 통해 3-OV 문제의 해를 구할 수 있음을 보입니다.
   • 큰 차원:
     • Baur-Strassen 정리의 활용: 트랜스포머가 행렬 곱셈의 합을 계산한다고 가정할 때, 이 합을 구성하는 개별 행렬 곱셈의 항들을 편미분을 통해 추출해냅니다.
     • 다항식 차수 제한: exp 와 ln 게이트가 포함된 회로라도, 낮은 차수의 함수 (예: 2 차 다항식인 행렬 곱셈) 를 계산할 때는 표준 대수적 회로와 동등한 능력을 가진다는 것을 증명하여, 행렬 곱셈의 하한선을 트랜스포머 하한선으로 연결합니다.

4. 의의 및 시사점 (Significance)

• 이론적 한계 규명: 트랜스포머의 계산 복잡도에 대한 첫 번째 비자명한 (Non-trivial) 하한선을 제시했습니다. 이는 트랜스포머가 단순히 어텐션 헤드를 여러 개 쌓은 것이 아니라, 계산적으로 매우 강력한 모델임을 반증하는 것이 아니라, 오히려 그 계산 비용이 본질적으로 피할 수 없음을 보여줍니다.
• 알고리즘 개발 방향: "직접 합" 문제가 트랜스포머에서는 성립하지 않으므로, $LH$개의 헤드를 독립적으로 계산하는 단순한 방식이 이미 최적에 가깝다는 결론을 내립니다. 따라서 트랜스포머의 계산 속도를 획기적으로 높이기 위해서는 어텐션 메커니즘 자체를 근사하거나 (Subquadratic approximation), 하드웨어 최적화 (FlashAttention 등) 에 집중해야 함을 시사합니다.
• 새로운 증명 도구: Baur-Strassen 정리를 신경망 (트랜스포머) 의 하한선 증명에 적용한 것은 새로운 기술적 기여입니다. 이는 미분 가능한 회로 모델의 구조적 특성을 활용하여 계산 복잡도를 분석하는 새로운 패러다임을 제시합니다.

5. 결론

이 논문은 트랜스포머 아키텍처의 계산적 효율성에 대한 근본적인 질문을 던지고, "여러 개의 어텐션 헤드를 동시에 계산하는 것이 개별 계산보다 효율적인가?"라는 질문에 대해 부정적인 답변을 제시합니다. 작은 임베딩 차원에서는 3-OV 가설 하에서 $O(LHN^2)$, 큰 임베딩 차원에서는 행렬 곱셈 지수 $\omega$ 하에서 $O(LHN^\omega)$가 본질적으로 최적임을 증명함으로써, 트랜스포머의 계산 복잡도 연구에 중요한 이정표를 세웠습니다.