Algorithmic Capture, Computational Complexity, and Inductive Bias of Infinite Transformers

Each language version is independently generated for its own context, not a direct translation.

이 논문은 **"인공지능 (특히 트랜스포머 모델) 이 정말로 '알고리즘'을 이해하고 있는가, 아니면 단순히 통계적 패턴을 외우고 있는가?"**라는 근본적인 질문에 답하려는 시도입니다.

저자들은 이 문제를 해결하기 위해 **'알고리즘 포착 (Algorithmic Capture)'**이라는 개념을 정의하고, 무한히 넓은 (이론적으로 완벽한) 인공지능 모델이 어떤 한계를 가지고 있는지 수학적으로 증명했습니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드리겠습니다.

1. 핵심 질문: "진짜 이해" vs "암기"

우리가 아이에게 "2+2=4"를 가르쳤을 때, 아이가 진짜 덧셈의 원리를 이해한 걸까요? 아니면 단순히 "2+2 하면 4 라고 외운 것"일까요?

대형 언어 모델 (LLM) 도 마찬가지입니다. 수학 문제를 풀거나 논리적 추론을 할 때, 모델이 **진짜 알고리즘 (원리)**을 깨달은 것인지, 아니면 단순히 데이터의 통계적 패턴을 외워서 (Interpolation) 정답을 맞춘 것인지 구별하기 어렵습니다.

이 논문은 **"문제 크기가 아무리 커져도 (예: 숫자가 10 개든 100 만 개든) 적은 노력으로 해결할 수 있다면, 그건 진짜 알고리즘을 배운 것이다"**라고 정의합니다. 이를 **'알고리즘 포착 (Grokking)'**이라고 부릅니다.

2. 연구의 방법: "무한한 두뇌"를 시뮬레이션하다

저자들은 실제 AI 모델을 실험하기보다, 이론적으로 무한히 넓은 (Infinite-width) AI 모델을 가정했습니다.

비유: 마치 "만약 우리가 무한한 두뇌와 기억력을 가진 천재를 만든다면, 그 천재가 어떤 문제를 풀 수 있을까?"라고 상상하는 것과 같습니다.
이 천재는 어떤 복잡한 함수든 표현할 수 있지만, 실제로 그 천재가 문제를 풀 때 얼마나 많은 계산 (시간/에너지) 이 필요한지를 분석했습니다.

3. 주요 발견: "천재도 한계가 있다"

연구 결과는 매우 흥미롭습니다.

A. 쉬운 일은 잘하지만, 어려운 일은 못한다

잘하는 일: "문장 속의 특정 단어를 찾아서 복사하기 (Induction)", "숫자 정렬하기 (Sorting)" 같은 작업은 AI 가 잘 해냅니다.
- 비유: 이 천재는 "책장에서 특정 책을 찾아서 가져오기"나 "책장을 정리하기"는 아주 잘합니다.
못하는 일: "그래프에서 A 지점에서 B 지점까지 가장 짧은 길 찾기 (Shortest Path)"나 "최대 유량 찾기 (Max Flow)" 같은 복잡한 문제는 실패합니다.
- 비유: 이 천재는 "미로 찾기"나 "복잡한 도로망에서 최적 경로 찾기"는 아무리 가르쳐도 못 합니다.

B. 그 이유는 "계산 비용"의 한계

왜 그럴까요? AI 가 문제를 풀 때 필요한 **계산 비용 (시간)**에 한계가 있기 때문입니다.

AI 가 문제를 풀 때, 문제의 크기 (T) 가 커지면 계산 비용이 T 의 2~~3 제곱 (T²~~T³) 정도만 증가할 수 있습니다.
하지만 "최단 경로 찾기" 같은 문제는 문제 크기가 커질수록 계산 비용이 훨씬 더 급격히 (T³ 이상) 늘어납니다.
결론: AI 는 계산 비용이 너무 많이 드는 복잡한 알고리즘은 원리상 배울 수 없습니다. 비유하자면, "1 분 안에 100 개의 미로를 풀 수 있는 천재"에게 "100 만 개의 미로를 1 초 만에 푸는 법"을 가르치는 것은 불가능한 것과 같습니다.

4. 실험 결과: "깊은 층 (Deep Layers) 이 답이 아니다"

많은 사람이 "AI 를 더 깊게 (층을 더 많이) 쌓으면 복잡한 문제도 풀 수 있지 않을까?"라고 생각합니다. 하지만 이 논문은 그렇지 않다고 말합니다.

비유: 아무리 두꺼운 두꺼운 책을 쌓아도 (층을 깊게 해도), 그 책에 적힌 '계산 규칙' 자체가 복잡도를 극복하지 못하면, 결국 같은 한계에 부딪힙니다.
실험에서도 40 층이나 되는 매우 깊은 AI 모델을 만들어도 "최단 경로 찾기" 같은 문제는 여전히 실패했습니다.

5. 요약: AI 의 본질적인 성향 (Inductive Bias)

이 논문의 핵심 메시지는 다음과 같습니다.

"AI 는 무한한 표현력을 가졌지만, 본질적으로 '간단하고 효율적인' 알고리즘만 배우도록 설계되어 있다."

쉬운 알고리즘 (정렬, 복사 등): AI 가 쉽게 포착하고 일반화합니다.
복잡한 알고리즘 (최단 경로 등): 계산 비용이 너무 비싸기 때문에 AI 가 배우지 못합니다.

6. 이 연구가 우리에게 주는 교훈

이 연구는 AI 가 "모든 것을 할 수 있는 만능 천재"가 아니라, 특정한 종류의 문제 (효율적인 알고리즘) 에만 특화된 존재임을 보여줍니다.

현실적인 기대: AI 가 수학이나 논리 문제를 푼다고 해서 인간처럼 '이해'를 했다고 생각하면 안 됩니다. 계산 비용이 허용되는 범위 내에서만 '패턴'을 찾아낼 뿐입니다.
미래의 방향: 더 복잡한 문제를 풀게 하려면 단순히 모델을 키우는 것이 아니라, AI 의 구조를 알고리즘의 특성에 맞게 바꿔주거나 (예: 그래프 신경망 등), 계산 비용을 줄이는 새로운 방법을 찾아야 합니다.

한 줄 요약:

"AI 는 '간단한 규칙'은 금방 깨우치지만, '계산이 너무 복잡한 미로'는 아무리 가르쳐도 풀지 못한다. AI 는 천재지만, 계산 비용이라는 '지갑'이 얇기 때문이다."

Each language version is independently generated for its own context, not a direct translation.

1. 연구 배경 및 문제 제기

문제: 대규모 언어 모델 (LLM) 이 복잡한 알고리즘 (예: 정렬, 최단 경로 찾기 등) 을 진정으로 이해하고 임의의 입력 크기 (problem size, $T$ ) 에 대해 일반화할 수 있는지, 아니면 훈련 데이터의 패턴을 단순히 외우는지에 대한 논쟁이 지속되어 왔습니다.
한계: 기존 연구들은 주로 특정 크기의 데이터셋에서 성능을 평가하거나, "그로킹 (grokking, 과적합 후 갑자기 일반화되는 현상)"과 같은 현상을 관찰하는 데 그쳤습니다. 그러나 이는 통계적 보간과 진정한 알고리즘 학습을 구분하기 어렵게 만들었습니다.
목표: 알고리즘 학습을 엄밀하게 정의하고, 무한 폭 트랜스포머의 추론 시간 (inference-time) 계산 복잡도를 분석하여, 어떤 복잡도의 알고리즘을 학습할 수 있는지 이론적 상한을 규명하는 것입니다.

2. 핵심 정의: 알고리즘적 포획 (Algorithmic Capture)

저자들은 신경망이 알고리즘을 "포획"했다는 것을 다음과 같이 엄밀하게 정의합니다.

정의: 신경망이 문제 크기 $T$ 가 임의로 커지더라도, 통제 가능한 오차로 일반화할 수 있어야 합니다.
샘플 적응 (Sample Adaptation):
1. 초기 훈련: 크기 $T_0$ 까지의 데이터 $P_0$ 개로 학습.
2. 미세 조정 (Fine-tuning): 더 큰 크기 $T > T_0$ 로 확장할 때, $O(\log(T/T_0))$ 만큼의 로그arithmic한 추가 데이터만으로도 목표 정확도를 달성해야 함.
의미: 만약 로그 수준의 데이터만으로도 새로운 크기의 문제를 해결할 수 있다면, 이는 알고리즘의 논리를 학습한 것이며 단순한 통계적 보간이 아님을 의미합니다.

3. 방법론: 무한 폭 트랜스포머와 NTK

가정: 유한한 깊이의 트랜스포머를 **무한 폭 (infinite-width)**으로 가정하여 분석합니다. 이는 표현력 (expressivity) 의 한계를 제거하고, 순수하게 **유도 편향 (inductive bias)**과 학습 역학에 집중하기 위함입니다.
NTK (Neural Tangent Kernel) 접근: 무한 폭 극한에서 신경망은 커널 회귀 (Kernel Regression) 로 수렴합니다. 저자들은 이 커널 예측기 (kernel predictor) 의 추론 시간 계산 복잡도를 분석합니다.
두 가지 영역 (Regimes):
1. Lazy Regime (NTK/NNGP): 가중치가 거의 변하지 않는 영역.
2. Rich Regime (Mean-Field): 특징 학습 (feature learning) 이 일어나는 영역.

4. 주요 결과 및 발견

A. 계산 복잡도 상한 (Upper Bounds on Complexity)

무한 폭 트랜스포머가 학습할 수 있는 함수의 복잡도는 추론 시 필요한 계산량에 의해 제한됩니다.

Lazy Regime (NTK): 커널 평가 비용은 $O(P \cdot N_{MC} \cdot T^3)$ $O (P \cdot N_{M C} \cdot T^{3})$ 입니다. 여기서 $P$ $P$ 는 데이터 수, $N_{MC}$ $N_{M C}$ 는 몬테카를로 샘플 수, $T$ $T$ 는 시퀀스 길이입니다.
- 결과: 트랜스포머는 $O(T^{3+\epsilon})$ 복잡도 이하의 알고리즘만 포획할 수 있습니다.
Rich Regime (Feature Learning): 특징 학습이 일어나더라도, 트랜스포머가 수렴하는 무한 폭 극한에서의 복잡도는 $O(T^{2+\epsilon})$ 로 더욱 엄격해집니다.
- 이는 특징 학습이 샘플 복잡도 (학습에 필요한 데이터 양) 에는 영향을 주지만, **추론 복잡도 (inference complexity)**에는 근본적인 변화를 주지 못함을 시사합니다.

B. 효율적 다항 시간 휴리스틱 스킴 (EPTHS)

저자들은 트랜스포머가 학습할 수 있는 알고리즘 클래스를 **EPTHS (Efficient Polynomial Time Heuristic Scheme)**로 정의합니다. 이는 평균적인 경우 (average-case) 에 다항 시간 내에 해결 가능한 알고리즘을 의미합니다.

결론: 트랜스포머는 EPTHS 클래스 내에서도 복잡도가 $O(T^2)$ 또는 $O(T^3)$ 을 초과하는 알고리즘은 학습할 수 없습니다. 즉, 낮은 복잡도의 알고리즘에 대한 유도 편향을 가집니다.

C. 실험적 검증 (성공 vs 실패)

이론적 예측을 검증하기 위해 다양한 알고리즘 태스크에 대한 실험을 수행했습니다.

성공한 사례 (포획됨):
- Induction Head (유도 헤드): 이전 토큰을 찾아 다음 토큰을 복사하는 작업. 복잡도가 낮아 트랜스포머가 성공적으로 학습.
- Sorting (정렬): 입력 리스트를 정렬하는 작업. $O(T^2)$ 복잡도 수준으로, 트랜스포머가 로그 수준의 데이터로 일반화 성공.
실패한 사례 (포획되지 않음):
- Shortest Path Problem (SPP, 최단 경로): 그래프에서 두 노드 간 최단 경로 찾기. 평균 복잡도가 $O(T \log T)$ 로 낮지만, 트랜스포머는 심층 구조 (40 레이어) 를 사용해도 일반화에 실패.
- MinCut/MaxFlow (최소 컷/최대 유량): 복잡도 $O(T^3)$ 수준. 트랜스포머가 학습하지 못함.
- 해석: SPP 의 경우 이론적으로는 학습 가능해야 하지만, 실제 실험에서는 실패했습니다. 이는 트랜스포머의 유도 편향이 단순히 계산 복잡도뿐만 아니라 알고리즘의 구조적 특성에도 민감함을 시사합니다.

5. 논의 및 의의

통계적 보간 vs 알고리즘 학습: 이 연구는 LLM 이 모든 것을 "이해"하는 것이 아니라, 낮은 계산 복잡도를 가진 알고리즘에 대해만 진정한 일반화 능력을 보인다는 것을 이론적으로 증명했습니다.
유도 편향의 한계: 트랜스포머는 무한한 표현력을 가지더라도, 학습 과정에서 발생하는 유도 편향으로 인해 고차원적인 알고리즘 (예: 복잡한 그래프 알고리즘) 을 학습하는 데 본질적인 한계가 있습니다.
미래 연구 방향:
- SPP 와 같이 이론적으로는 가능해야 함에도 실패한 사례에 대한 추가적인 유도 편향 분석 필요.
- 더 깊은 네트워크나 재귀적 아키텍처에서의 복잡도 분석 확장.
- 커널 평가의 "브루트 포스" 방식이 지나치게 보수적일 수 있으므로, 더 정교한 커널 근사 방법 탐구.

요약

이 논문은 **"트랜스포머는 알고리즘을 학습할 수 있는가?"**라는 질문에 대해, **"복잡도가 $O(T^2)$ ~ $O(T^3)$ 이하인 단순한 알고리즘은 학습 가능하지만, 그 이상의 복잡도나 특정 구조적 특성을 가진 알고리즘은 학습하지 못한다"**는 명확한 이론적 경계를 제시했습니다. 이는 LLM 의 알고리즘적 추론 능력에 대한 이해를 통계적 패턴 매칭을 넘어 계산 복잡도 이론의 관점에서 정립했다는 점에서 중요한 의의를 가집니다.