트랜스포머 LLM 튜링 완전성 논쟁: 생각의 사슬이 언어 모델을 확률적 튜링 기계로 만드는 이유

핵심 메시지

• 생각의 사슬로 중간 단계를 출력할 수 있는 트랜스포머 디코더와 순환신경망은 확률적 튜링 기계를 시뮬레이션할 수 있다는 것이 이 연구의 결론이다.
• 같은 트랜스포머라도 인코더와 디코더의 표현력은 전혀 다르다. 한 번에 답을 내야 하는 인코더는 고정 크기 논리 회로에 가까워 정규 언어조차 인식하지 못한다.
• 생각의 사슬이 이론적으로 중요한 이유는 모델이 답을 내기 전에 계산 단계를 토큰으로 적어 둘 수 있게 해주기 때문이다. 이 임시 메모가 튜링 기계의 상태 정보 역할을 한다.
• 이론적으로 존재한다는 것과 학습으로 찾을 수 있다는 것은 다른 문제다. 증명은 성긴 가중치를 직접 설계해 넣지만, 경사하강법은 촘촘한 가중치 공간을 헤맨다.
• 이런 이론이 실용적인 이유는 상한과 하한을 알려주기 때문이다. 상한이 낮은 구조라면 그 능력을 찾는 노력을 멈춰야 하고, 모델이 할 수 있다고 말할 때 의심해야 한다.

쉽게 이해하기

이번 회차는 AI 커피 브레이크의 첫 영상 팟캐스트로, 취리히연방공대에서 형식 언어와 계산 이론을 연구하는 박사과정생 프란츠 노박이 손님으로 나왔다. 진행자는 다른 팟캐스트에서 '트랜스포머는 튜링 기계와 동등하지 않다'는 말을 계속 들어왔는데, 학회 튜토리얼에서 그 반대되는 주장을 접하고 혼란스러웠다고 털어놓는다. 대담의 목표는 어떤 가정 아래에서 그런 주장이 성립하는지를 정리하는 것이다.

출발점은 촘스키 위계다. 가장 아래에는 유한 상태 오토마타가 인식하는 정규 언어가 있다. 문자열에 1이 짝수 개 있는지 같은 문제가 여기 속한다. 한 단계 위는 문맥 자유 언어로, 괄호가 짝을 이루는지 확인하려면 열린 괄호를 기억해야 하므로 정규 언어의 범위를 벗어난다. 그다음이 문맥 의존 언어이고, 같은 문자열이 두 번 반복되는지 판정하려면 앞부분 전체를 기억해야 한다는 점에서 문맥 자유 언어보다 강하다. 맨 위에는 튜링 기계로 생성할 수 있는 계산 가능한 언어가 있다. 사람의 언어는 대체로 문맥 의존 언어로 보지만 이 역시 논쟁거리다.

손님은 튜링 완전성이라는 말부터 정리한다. 엄밀한 의미의 튜링 완전성은 무한한 메모리와 무한한 시간을 전제하므로, 현실에 존재하는 어떤 기계도 튜링 완전하지 않다. 노트북조차 메모리 한계에 부딪히면 디스크를 붙이거나 클라우드를 써야 한다. 일상적으로 튜링 완전하다고 말할 때 뜻하는 바는 고정된 명령 집합으로 입력 크기와 상관없이 알고리즘을 실행할 수 있다는 것이다.

핵심은 인코더와 디코더의 차이다. 트랜스포머 인코더는 고정된 문맥 창을 받아 한 번에 답을 내놓아야 한다. 이렇게 한 단계로 답을 내는 구조는 고정 크기의 논리 회로와 동등하고, 표현력이 매우 약해 유한 상태 오토마타만큼도 되지 못한다. 즉 정규 언어도 인식하지 못한다. 반면 디코더는 이미 생성한 내용을 바탕으로 한 토큰씩 이어 붙이고 문맥도 함께 늘어난다. 계산에 쓸 수 있는 단계 수가 유연해지는 것이 결정적이다. 순환신경망도 은닉 표현을 반복해서 갱신한다는 점에서 비슷한 성질을 갖는다.

연구의 계보는 이렇다. 순환신경망이 튜링 기계를 표현할 수 있다는 1992년 결과가 있었지만, 무한 정밀도의 숫자를 저장할 수 있어야 한다는 조건이 붙었다. 무한히 정밀하거나 무한히 넓거나 둘 중 하나가 필요했던 셈이다. 2021년에는 하드 어텐션을 쓰는 인코더-디코더 구조가 튜링 기계를 흉내 낼 수 있다는 연구가 나왔는데, 이 구조는 튜링 기계의 테이프 상태를 그대로 출력해야 했다. 노박과 동료들은 이 부분이 언어 모델답지 않다고 보고, 상태 정보를 어휘 안의 토큰으로 적어 두는 생각의 사슬로 대체했다. 구분 기호 이후에 진짜 답을 내놓게 하면 되기 때문이다. 나아가 언어 모델은 형식적으로 문자열이 아니라 문자열 위의 확률 분포이므로, 생각의 사슬을 갖춘 트랜스포머와 순환신경망은 임의의 분포를 표현할 수 있는 확률적 튜링 기계를 시뮬레이션한다는 것까지 보였다.

그렇다면 이런 모델을 실제로 학습시킬 수 있을까. 손님의 답은 회의적이다. 증명에서는 원하는 가중치를 알고 있으니 그대로 적어 넣으면 되지만, 학습은 조금씩 가까워지는 방식이라 사정이 다르다. 튜링 기계 같은 계산은 이산적·기호적이어서 1만 자짜리 문자열에서 비트 하나만 뒤집혀도 정답이 바뀐다. 해답 공간이 매끄럽지 않으니 경사 기반 방법으로 찾기가 지극히 어렵다. 2014년 신경 튜링 기계나 메모리를 붙인 트랜스포머 같은 시도가 있었지만 널리 자리 잡지는 못했다. 진행자는 증명이 성긴 행렬을 가정하는 데 비해 학습은 촘촘한 행렬에서 시작한다는 점을 지적하고, 손님은 성긴 구조는 정규화로 유도할 수 있지만 '잘못된 성김'에서 '올바른 성김'으로 옮겨 가는 것이 진짜 문제라고 답한다.

주요 인사이트

• '트랜스포머는 튜링 완전하다'는 문장은 가정을 빼고 말하면 오해를 부른다. 어떤 구조를, 어떤 정밀도로, 몇 단계의 계산을 허용하고 말하는지에 따라 답이 완전히 달라진다.
• 생각의 사슬은 성능을 올리는 요령 정도로 여겨지기 쉽지만, 계산 이론의 관점에서는 모델이 쓸 수 있는 계산 단계와 임시 기억을 늘려주는 구조적 장치다.
• 인코더가 정규 언어조차 인식하지 못한다는 대목은 '한 번에 답하기'가 얼마나 큰 제약인지를 보여준다. 답을 내기 전에 단계를 밟을 수 있는지가 표현력을 가른다.
• 이론과 학습 가능성 사이의 간극이 이 대담의 진짜 주제다. 올바른 가중치가 존재한다는 것과 경사하강법으로 그 가중치에 도달한다는 것은 전혀 다른 이야기다.
• 손님은 하나의 언어 모델이 모든 것을 풀게 하기보다, 자연스러운 언어를 담당하는 모델이 정리 증명기 같은 외부 프로그램을 호출하는 방향이 낫다고 본다. 오늘날의 도구 호출 설계와 맞닿는 관점이다.

자주 묻는 질문

관련 AI 소식