트랜스포머가 정확히 얼마나 똑똑한 계산 기계인지, 회로 이론으로 재보는 서베이
트랜스포머가 정확히 얼마나 똑똑한 계산 기계인지, 회로 이론으로 재보는 서베이
이 논문은 오늘날 거의 모든 LLM의 핵심 구조인 트랜스포머가 계산 이론적으로 어떤 능력을 갖는지 정리한 서베이다. 트랜스포머를 병렬 논리 회로(회로 복잡도)와 비교해서, 주의(attention) 방식과 계산 정밀도(precision) 같은 설정에 따라 트랜스포머가 풀 수 있는 문제의 범위가 어떻게 달라지는지 보여준다. 중간 사고 과정을 출력하며 답을 내는 체인 오브 소트(CoT) 방식을 쓰면 그 능력이 크게 확장된다는 점도 정리한다.
METAL MEDIA 해설 도표
트랜스포머가 정확히 얼마나 똑똑한 계산 기계인지, 회로 이론으로 재보는 서베이
- 01트랜스포머를 언어 인식기로 보고, 인코더(문장을 보고 참/거짓 판단)와 디코더(다음 단어를 순차 생성)로 나눠 수학적으로 정의했다.
- 02튜링머신이나 문법 체계(촘스키 위계) 대신 회로 복잡도라는 틀을 썼는데, 트랜스포머가 병렬적이고 층이 고정된 계산을 하기 때문에 논리 게이트로 이루어진 회로와 비교하기가 더 자연스럽기 때문이다.
- 03주의를 딱딱하게(하드 어텐션) 쓰는지 부드럽게(소프트맥스) 쓰는지, 계산에 몇 비트의 정밀도를 쓰는지에 따라 트랜스포머가 흉내낼 수 있는 회로 등급(AC0, TC0)이 달라진다는 기존 결과들을 정리했다.
- 04체인 오브 소트 없이는 트랜스포머의 능력이 대체로 TC0라는 비교적 제한된 등급 안에 갇히지만, 중간 추론 토큰을 충분히 길게 허용하면 LOGSPACE, PTIME까지, 심지어 무제한이면 임의의 튜링머신까지 흉내낼 수 있다는 결과들을 모았다.
- 05이 논문 자체는 새 정리를 증명하기보다, 기존 여러 연구 결과들을 하나의 틀 안에서 비교 정리한 서베이 논문이다.
무엇을 했나
- 트랜스포머를 언어 인식기로 보고, 인코더(문장을 보고 참/거짓 판단)와 디코더(다음 단어를 순차 생성)로 나눠 수학적으로 정의했다.
- 튜링머신이나 문법 체계(촘스키 위계) 대신 회로 복잡도라는 틀을 썼는데, 트랜스포머가 병렬적이고 층이 고정된 계산을 하기 때문에 논리 게이트로 이루어진 회로와 비교하기가 더 자연스럽기 때문이다.
- 주의를 딱딱하게(하드 어텐션) 쓰는지 부드럽게(소프트맥스) 쓰는지, 계산에 몇 비트의 정밀도를 쓰는지에 따라 트랜스포머가 흉내낼 수 있는 회로 등급(AC0, TC0)이 달라진다는 기존 결과들을 정리했다.
- 체인 오브 소트 없이는 트랜스포머의 능력이 대체로 TC0라는 비교적 제한된 등급 안에 갇히지만, 중간 추론 토큰을 충분히 길게 허용하면 LOGSPACE, PTIME까지, 심지어 무제한이면 임의의 튜링머신까지 흉내낼 수 있다는 결과들을 모았다.
- 이 논문 자체는 새 정리를 증명하기보다, 기존 여러 연구 결과들을 하나의 틀 안에서 비교 정리한 서베이 논문이다.
| 𝐲i | =𝐖(O)(∑j=1nαi,j𝐯j), | 𝐯j | =𝐖(V)𝐱j, | αi,∗ | =𝒮(si,∗), | (1) | ||
|---|---|---|---|---|---|---|---|---|
| si,j | =𝐪i⊤𝐤jdkey, | 𝐪i | =𝐖(Q)𝐱i, | 𝐤j | =𝐖(K)𝐱j. | (2) |
| (𝐲1(ℓ),…,𝐲n(ℓ)) | :=∑h=1H𝗌𝖺(h,ℓ)(𝐱1(ℓ−1),…,𝐱n(ℓ−1))+(𝐱1(ℓ−1),…,𝐱n(ℓ−1)), | ||
|---|---|---|---|
| (𝐱1(ℓ),…,𝐱n(ℓ)) | :=(𝖿𝖿(ℓ)(𝐲1(ℓ)),…,𝖿𝖿(ℓ)(𝐲n(ℓ)))+(𝐲1(ℓ),…,𝐲n(ℓ)). |
| F𝒯0(w) | :=w | ||
|---|---|---|---|
| F𝒯i(w) | :=F𝒯i−1(w)⋅F𝒯(F𝒯i−1(w)) for i≥1, |
왜 중요한가
LLM이 왜 어떤 문제는 잘 풀고 어떤 문제는 원리적으로 못 푸는지를 이해하려면, 이런 계산 이론적 한계를 아는 것이 실무적 기대치 설정에 도움이 된다. 특히 체인 오브 소트가 단순한 프롬프트 기법을 넘어 모델의 근본적 계산 능력 자체를 확장한다는 점은 실제 시스템 설계에 시사점을 준다.
이 논문의 용어
- 회로 복잡도(circuit complexity) · AND/OR/NOT 같은 논리 게이트로 이뤄진 회로가 어떤 문제를 얼마나 효율적으로 풀 수 있는지 따지는 이론 분야
- AC0 / TC0 · 깊이가 일정하게 고정된 논리 회로로 풀 수 있는 문제들의 집합. TC0는 다수결(MAJ) 게이트까지 허용해 AC0보다 더 넓은 범위를 포함
- 하드 어텐션 / 소프트맥스 어텐션 · 하드 어텐션은 가장 점수 높은 위치만 보는 방식, 소프트맥스 어텐션은 모든 위치에 확률적 가중치를 주는 실제 LLM의 방식
- 정밀도(precision) · 모델 내부 계산에 사용하는 비트 수. 낮으면 표현력이 떨어지고 로그 수준이면 덧셈 등 더 복잡한 연산이 가능해진다
- 체인 오브 소트(Chain-of-Thought, CoT) · 모델이 최종 답 전에 중간 추론 과정을 토큰으로 출력하고 이를 다시 입력에 이어붙여 계산을 이어가는 방식
최신 논문
- AI 코딩 에이전트에게 과학 소프트웨어 수리를 시켜보니, 절반도 제대로 못 고쳤다AI 코딩 에이전트에게 과학 소프트웨어 수리를 시켜보니, 절반도 제대로 못 고쳤다
- 논문 속 시연이 아니라 실제 서비스에 넣을 수 있는 희소 어텐션 만들기논문 속 시연이 아니라 실제 서비스에 넣을 수 있는 희소 어텐션 만들기
- 고객상담 AI 상담원이 규정을 '한 번의 행동'이 아니라 '전체 절차'로 지키게 만드는 방법고객상담 AI 상담원이 규정을 '한 번의 행동'이 아니라 '전체 절차'로 지키게 만드는 방법
- 로봇 팔에게 사람의 시연 없이 새 일 시키기, 말 잘하는 AI가 대신 가르친다로봇 팔에게 사람의 시연 없이 새 일 시키기, 말 잘하는 AI가 대신 가르친다
- 에이전트 학습용 환경을 새로 만드는 대신, 기존 환경에 '패치 부품'을 씌워 그 에이전트의 약점에 맞게 바꾸는 방법에이전트 학습용 환경을 새로 만드는 대신, 기존 환경에 '패치 부품'을 씌워 그 에이전트의 약점에 맞게 바꾸는 방법
- AI 모델을 '소유'하지 못한 조직은 안전 통제도 절반밖에 못 한다AI 모델을 '소유'하지 못한 조직은 안전 통제도 절반밖에 못 한다
- AI가 선생님 모델을 따라 배우다가, 정답에 다가가는 '좋은 생각'까지 억누르는 문제를 잡아낸다AI가 선생님 모델을 따라 배우다가, 정답에 다가가는 '좋은 생각'까지 억누르는 문제를 잡아낸다
- AI가 특정 사람 말투를 흉내내도록 시켜봤더니, 결국 AI 자신의 말투에서 못 벗어난다AI가 특정 사람 말투를 흉내내도록 시켜봤더니, 결국 AI 자신의 말투에서 못 벗어난다
METAL MEDIA 최신 기사
그림 출처: Phokion Kolaitis et al., arXiv:2608.12671, CC BY 4.0