프로그래밍 가능한 컴퓨터로서의 루프드 트랜스포머

📌 한입 요약
Context — 대형 언어모델은 프롬프트에 예시 몇 개만 넣어도 그 자리에서 새 작업을 푸는 in-context learning(가중치를 바꾸지 않고 입력만으로 학습하는 현상)을 보인다. 트랜스포머가 원리상 무엇이든 계산할 수 있다(Turing complete)는 건 알려져 있었지만, 기존 구성은 치명적 약점이 있었다. 프로그램이 길어질수록 모델 층(layer) 수도 비례해 늘어나야 했던 것 — 100단계 계산엔 100층급 모델이 필요한 식이라, “유한한 고정 모델이 임의 길이 프로그램을 돌린다”는 컴퓨터의 본질과 어긋났다.

Insight — 저자들의 핵심 통찰은 깊이 대신 루프다. 사람이 만든 CPU도 회로는 고정이고 클럭이 명령어를 하나씩 반복 처리하듯, 트랜스포머의 출력을 다시 입력으로 되먹이는 단일 루프(while문처럼 같은 블록을 반복)를 두면 모델 깊이는 “한 명령어를 실행하는 데 드는 상수 깊이”에만 묶이고 프로그램 길이와 무관해진다.

Solution — 이 통찰은 어텐션 역설계로 자연스럽게 이어진다. 저자들은 어텐션 헤드를 분석해 read/write(메모리 특정 위치 읽고 쓰기), 조건분기(if-goto), 프로그램 카운터(다음 실행할 명령 주소를 ±1 이진 위치인코딩으로 추적) 같은 컴퓨터 부품을 손으로 짜 넣고, 이를 SUBLEQ(단 하나의 명령어 “빼고 0 이하면 분기”만으로 튜링 완전한 OISC, 단일명령어 컴퓨터)로 조립한 뒤 더 유연한 FLEQ로 일반화한다.

Evidence — 그 결과 13층 미만의 얕은 looped transformer 하나(Theorem 1)가 프롬프트만 바꿔 범용 컴퓨터·계산기(12층, §7)·역행렬과 power iteration 같은 선형대수(13층, §8)·심지어 신경망의 SGD/역전파를 in-context로(13층, §9) 에뮬레이션한다. SUBLEQ 구성은 9층·2헤드(§5.1)면 충분하며, 함수 라이브러리는 Barron 정리로 시그모이드를 폭 m에 대해 오차 ~1/√m로 근사한다(§6). 결정적 대조는 선행연구다. ICL이 곧 경사하강법이라 본 Akyürek·von Oswald의 구성은 반복 횟수에 비례해 층이 필요했으나, 이 루프 구성은 깊이가 상수다.

Limitations — 가장 중요한 한계는 저자 스스로 명시적으로 경고한다. 이것은 학습된 모델이 아니라 가중치를 일일이 수작업 하드코딩한 존재 증명(existence proof)이다 — “트랜스포머가 이런 능력을 가질 수 있다”는 가능성을 보일 뿐, 경사하강 훈련으로 이런 구조가 실제 출현하는지는 보이지 않는다. 또한 정밀한 ±1 위치인코딩·softmax 온도 λ로 hardmax를 근사하는 구성은 유한 정밀도·노이즈에 얼마나 견디는지 미지수다.

Open Questions — 그렇다면 이렇게 손으로 심을 수 있는 알고리즘적 구조를 표준 사전학습이 실제로 발견하는가? 루프 회수를 늘리면 추론 깊이를 동적으로 키울 수 있다는 발상은 후속 “Looped Transformers” 추론 연구로 이어지는데, 하드코딩 구성과 학습된 행동 사이의 간극을 메우는 것이 다음 과제다. 📎 https://arxiv.org/abs/2301.13196

---

흐름 따라 읽기

논지 흐름(throughline): LLM의 ICL 현상 → 기존 Turing-complete 구성의 한계(깊이가 프로그램 길이에 비례) → 어텐션 역설계 + 루프로 깊이 상수화 → 빌딩블록(§4) → SUBLEQ 9층(§5.1) → FLEQ 일반화(§5.2) → 함수 라이브러리(§6) → 응용 3종: 계산기(§7)·선형대수(§8)·SGD/역전파 ICL(§9) → 결론·열린문제(§10).

Abstract

이 섹션은 논문 전체의 핵심 주장 — 루프에 넣은 얕은 트랜스포머(looped transformer)가 범용 컴퓨터를 에뮬레이션할 수 있다는 테제 — 를 압축해 제시하며, 독자가 읽을 가치를 판단할 수 있도록 목적·방법·결과·결론을 한 단락에 담는다. 저자들은 특정 가중치를 하드코딩(hardcode)하고 출력을 입력으로 되먹이는 루프(loop) 구조를 통해 트랜스포머 네트워크를 범용 컴퓨터로 활용하는 프레임워크를 제시한다. 입력 시퀀스(input sequence)는 ‘펀치카드(punchcard)’ 역할을 하며, 명령어(instruction)와 데이터 읽기/쓰기(read/write)를 위한 메모리를 담는다. 상수 개수의 인코더 레이어(encoder layer)만으로 임베딩 편집 연산(embedding edit operation), 비선형 함수(nonlinear function), 함수 호출(function call), 프로그램 카운터(program counter), 조건 분기(conditional branch) 등 기본 연산 블록을 에뮬레이션할 수 있음을 증명한다. 이 빌딩블록들을 조합해 소규모 명령어 집합 컴퓨터(small instruction-set computer)를 에뮬레이션하고, 결과적으로 반복 알고리즘을 13층 이하의 루프 트랜스포머로 실행 가능한 프로그램으로 변환할 수 있다. 이 프레임워크를 통해 기본 계산기, 기본 선형대수 라이브러리, 역전파(backpropagation)를 활용한 인-컨텍스트 학습(in-context learning, ICL) 알고리즘을 하나의 모델이 프롬프트만 바꿔 실행함을 보인다. 이 연구는 어텐션 메커니즘(attention mechanism)의 다용도성을 강조하며, 심지어 얕은 트랜스포머도 본격적인 범용 프로그램을 실행할 수 있음을 입증한다.

Introduction (§1)

Introduction은 트랜스포머의 ICL(인-컨텍스트 학습) 현상에서 출발해 기존 Turing-complete 구성의 한계를 진단하고, 루프 + 어텐션 역설계라는 본 논문의 해법이 왜 필요한지를 깔때기(funnel) 구조로 정당화하는 역할을 한다. 트랜스포머는 GPT-3(175B 파라미터, Brown et al. [2020])와 PaLM(540B 파라미터, Chowdhery et al. [2022])처럼 수십억 개의 파라미터를 가진 대형 언어 모델(LLM)이 자연어 처리(NLP)에서 최고 성능을 달성했으며, 특히 가중치 업데이트 없이 짧은 프롬프트와 몇 가지 예시만으로 새로운 태스크를 수행하는 ICL 능력을 보인다는 관찰에서 동기가 시작된다. 이미 선행 연구들은 충분한 깊이 또는 재귀 연결(recursive link)이 있으면 트랜스포머가 튜링 머신(Turing Machine)을 시뮬레이션할 수 있음을 보였으나(Pérez et al. [2021], Wei et al. [2022a]), 이 구성들은 특정 알고리즘 태스크를 수행하거나 고수준 프로그래밍 언어를 컴파일하는 방법에 대한 구체적 통찰을 제공하지 못한다. RASP(Restricted Access Sequence Processing Language; Weiss et al. [2021])와 같은 전문화된 언어는 인덱스된 토큰에 대한 선택·집계 명령을 트랜스포머로 매핑할 수 있지만, 모델 크기가 프로그램 크기에 비례해 증가하는 한계를 가진다. ICL=경사하강법(gradient descent) 계열 연구(Akyürek et al. [2022], von Oswald et al. [2022])는 트랜스포머가 추론 시 선형 회귀 모델 학습을 암묵적으로 수행함을 보였지만, 알고리즘 반복 횟수에 비례한 레이어 수를 필요로 하고 소수의 손실 함수와 모델에 한정된다. 본 논문은 어텐션을 역설계(reverse engineering)해 편집 연산, 비선형 함수, 함수 호출, 프로그램 카운터, 조건 분기라는 기본 연산 블록을 만들고, 단일 루프를 통해 출력을 입력으로 되먹이는 방식으로 모델 깊이가 프로그램 길이가 아닌 ‘단일 명령어 실행에 필요한 상수 깊이’에만 의존하도록 한다. 구체적으로 SUBLEQ(A,B,C) — Subtract and branch if Less-than or EQual to zero — 를 일반화한 단일 명령어 FLEQ(mem[c] = fm(mem[a], mem[b]), 조건 분기 포함)를 설계하고, fm은 행렬 곱셈·비선형 함수·다항식 등에서 선택 가능한 함수 집합으로 하드코딩한다.

Theorem 1 (비공식). 13층 미만의 루프 트랜스포머가 범용 컴퓨터(§5), 기본 계산기(§7), 근사 역행렬(approximate matrix inverse)·거듭제곱 반복법(power iteration) 등 수치 선형대수 방법(§8), 신경망 위 SGD를 포함한 ICL 알고리즘(§9)을 에뮬레이션할 수 있는 것이 존재한다.

Table 1 (구성별 층수·헤드 수 요약)

기능	레이어 수	헤드 수	근거
SUBLEQ (OISC)	9	2	Lemma 4
Matrix Inversion (행렬 역행렬)	13	1	Lemma 12
Power Iteration (거듭제곱 반복법)	13	1	Lemma 13
SGD	13	1	Lemma 15

(네트워크 너비(width)는 구현 함수의 복잡도에 따라 O(log(입력 길이) + 임베딩 차원)에서 근사 오차의 다항식 범위로 달라진다.)

저자가 명시한 기여

• 어텐션 역설계를 통해 편집 연산·비선형 함수·함수 호출·프로그램 카운터·조건 분기 등 기본 연산 블록을 구성하고, 단일 루프로 깊이를 상수화함을 증명한다.
• SUBLEQ를 일반화한 FLEQ 단일 명령어 집합 컴퓨터(OISC)를 정의하고, 이를 실행하는 명시적(explicit) 트랜스포머 가중치 행렬을 제공한다.
• 13층 이하 동일 모델이 기본 계산기, 선형대수 라이브러리(전치·곱셈·역행렬·거듭제곱 반복법), 역전파를 활용한 완전연결 신경망 ICL을 프롬프트 교체만으로 실행함을 보인다.
• 특정 알고리즘 태스크 수행에 필요한 최소 트랜스포머 네트워크 크기를 결정하는 기준을 제시한다.

Prior Work (§2)

Prior Work 섹션은 본 논문의 기여를 위치시키기 위해 트랜스포머의 표현력·Turing 완전성 연구, RASP/Tracr 계열 프로그래밍 언어 연구, ICL=경사하강법 계열 연구라는 세 흐름을 검토하며, 각 흐름과 본 논문의 차별점을 명시함으로써 ‘기존 한계 → 본 논문의 해법’이라는 throughline을 강화한다. Turing 완전성 계열(Pérez et al. [2021], Pérez et al. [2019], Wei et al. [2022a])은 트랜스포머가 튜링 머신을 시뮬레이션할 수 있음을 보였으나, Wei et al. [2022a]를 제외하면 고정밀도(high/infinite precision)와 어텐션 레이어 간 재귀(recursion)를 필요로 하며, 특정 알고리즘 태스크를 위한 구성 방법이나 고수준 언어 컴파일에 대한 통찰을 제공하지 않는다. RASP(Weiss et al. [2021])는 트랜스포머 인코더의 기본 구성요소를 단순 프리미티브(primitive)로 매핑하는 도메인 특화 언어(domain-specific language)로, 계수·정렬·Dyck-k 언어 인식 등 다양한 알고리즘을 표현할 수 있지만 프로그램 크기에 따라 모델 크기가 함께 증가한다는 한계가 있다. 이를 확장한 Tracr(Lindner et al. [2023])는 RASP를 활용한 컴파일러를 도입했으나, 언어의 표현력 한계와 Turing 완전성의 불명확성이 지적된다(Weiss et al. [2021], Merrill et al. [2022]). 본 논문은 이와 달리 임의의 비선형 함수 구현과 반복적·비선형 알고리즘 에뮬레이션을 가능하게 하며, 결정적으로 트랜스포머의 깊이가 실행하는 코드 줄 수에 비례하지 않도록 한다. ICL=경사하강법 계열에서 Akyürek et al. [2022]와 von Oswald et al. [2022]는 선형 자기-어텐션(linear self-attention) 한 층이 회귀 손실 위 경사하강법과 동등함을 보이고 하드코딩 가중치 구성을 제시했으나, 알고리즘 반복 횟수에 비례한 레이어 수를 필요로 하고 소수의 손실 함수·모델 클래스에 한정된다. Garg et al. [2022]는 언어를 완전히 제거하고 벡터 임베딩 수준에서 GPT-2가 선형 함수 및 2층 신경망의 ICL을 수행할 수 있음을 실험적으로 보였으며, 이 추상화 수준이 본 논문의 수학적 유도에서도 활용된다. Liu et al. [2022]는 유한 오토마톤(finite automaton) 맥락에서 트랜스포머가 추론 단계 수보다 적은 레이어로 알고리즘 추론을 수행할 수 있는 특정 오토마톤 군이 존재함을 보였으나, 일반적 단축 해법의 존재는 복잡도 클래스 붕괴를 함의하므로 특정 패밀리에 한정된다. 마지막으로 Hutchins et al. [2022], Shen et al. [2022], Dehghani et al. [2018]은 재귀(recursion)를 트랜스포머 아키텍처에 실험적으로 도입한 연구들로, 본 논문과 유사한 방식을 사용하지만 본 논문은 출력을 입력으로 되먹이는 단일 재귀 링크(single recursive link)만을 사용한다는 점에서 구별된다.

Preliminaries (§3)

이 섹션은 논문 전체에서 사용되는 공용 언어를 정립하는 역할을 담당하며, 이후 모든 구성 요소(read/write, 분기, 카운터, OISC)가 의존하는 아키텍처 정의·입력 포맷·실행 모델을 제시한다. 트랜스포머 레이어는 입력 행렬 X ∈ R^(d×n)을 받아 식 (1a)의 어텐션(attention)과 식 (1b)의 ReLU 레이어를 결합한 f(X)를 출력하며, 각 어텐션 헤드는 키(key) K, 쿼리(query) Q, 값(value) V 행렬로 정의된다. 반복 계산은 Algorithm 1인 Looped Transformer로 구현된다. 고정된 가중치 W를 갖는 다층 트랜스포머 TF(W; X)의 출력을 다시 입력으로 되먹임(X ← TF(W; X))하는 단순 루프를 T회 반복하며, 이는 CPU가 클럭 사이클마다 메모리를 읽고 명령어를 한 줄씩 실행하는 방식과 유사하다. 입력 시퀀스 X는 식 (2)에 따라 세 영역으로 명시적으로 분할된다. 스크래치패드(scratchpad, S): CPU 캐시 메모리에 해당하는 임시 작업 공간으로, 모든 연산의 입출력이 이곳에 기록되며 메모리에서 데이터를 복사해 와 가공한 뒤 다시 메모리로 반환한다. 메모리(memory, M): 스칼라·벡터·행렬 형태의 데이터를 저장하는 공간으로, 연산이 필요할 때 스크래치패드로 복사되고 연산 완료 후 갱신된 값이 되돌아온다. 커맨드(commands, C): 메모리 위치 지시자와 연산 지시자를 포함하는 저수준(low-level) 명령어 집합으로, 트랜스포머가 순서대로 복잡한 계산을 수행하도록 안내한다. 각 열(column)에는 위치 인코딩(positional encoding) p_1, …, p_n이 부여되어 데이터 및 명령어를 가리키는 포인터로 사용되며, 이 3분할 포맷은 이후 구성되는 모든 “compute box”가 일관되게 참조하는 메모리 모델의 기반이 된다.

빌딩블록: 범용 계산을 향한 트랜스포머 부품 (§4)

§4 “Building Transformer Blocks”는 §5의 OISC(One Instruction Set Computer, 단일-명령 집합 컴퓨터) 조립에 앞서, 트랜스포머 레이어가 수행할 수 있는 세 가지 기초 연산을 부품 단위로 확립하는 섹션이다. 첫 번째 부품(§4.1)은 이진 위치인코딩(binary positional encoding) 과 이를 기반으로 한 프로그램 카운터(PC)·데이터 포인터로, 열 인덱스 i를 log(n)차원의 ±1 이진 벡터 p_i로 인코딩하여 p_i^T p_i = log(n)이고 i ≠ j이면 p_i^T p_j < log(n)인 내적 분리 성질을 확보하며, 이 성질 덕분에 ReLU 피드포워드 층 하나(Lemma 1, 은닉 뉴런 8d개)만으로 PC를 정수 1씩 증가시킬 수 있다. 두 번째 부품(§4.2)은 read/write 연산으로, 어텐션의 K=Q 행렬을 위치인코딩 행에만 반응하도록 설정해 softmax 온도 λ ≥ 3/log(n) 이상에서 근사-치환행렬(approximate permutation matrix)을 얻고, 이를 통해 메모리→스크래치패드 복사(Lemma 2: read)와 스크래치패드→메모리 기입(Lemma 3: write)을 각각 1층·1헤드·O(log n + d) 폭의 트랜스포머로 구현한다(온도를 무한히 높이면 softmax가 hardmax로 수렴하여 오차 항이 0에 근접). 세 번째 부품(§4.3)은 조건분기(if-goto) 로, if mem[a] ≤ 0 then goto i 형태를 ReLU 수식 (3)(4)로 flag 비트를 계산한 뒤, p_next = 2ReLU(p_{PC+1} − 1·flag) + 2ReLU(p_i − 1·(1−flag)) − 1 공식을 피드포워드 층 3개(트랜스포머 층 2개)로 처리해 구현한다. 세 부품 모두 서로 상호운용 가능하도록 동일한 이진 위치인코딩 체계를 공유하며, 어텐션의 softmax 근사·ReLU 선형 조합·잔차 연결이라는 트랜스포머 고유의 성질을 역설계(reverse-engineer)하여 CPU의 메모리 주소지정·데이터 이동·분기 회로를 단층 수준에서 재현한 것이 핵심이다.

범용 컴퓨터 조립: SUBLEQ → FLEQ (§5)

§5는 이 논문의 핵심 증명부로, looped transformer가 범용 컴퓨터임을 SUBLEQ(빼기-분기 단일 명령어 집합 컴퓨터 명령어)에서 출발해 단계적으로 확립한다. §5.1(Lemma 4)에서는 9층·2헤드 looped transformer가 SUBLEQ 프로그램을 실행할 수 있음을 7단계 구성으로 증명하는데, 각 루프 반복마다 (1) 현재 명령어 cPC를 스크래치패드(scratchpad)로 복사, (2) 피연산자 mem[a]·mem[b] 읽기, (3) 뺄셈 mem[b]−mem[a] 계산(2의 보수(2’s complement) 변환 후 비트 덧셈, 3개 transformer 층), (4) 결과를 메모리 위치 b에 기록, (5) 결과가 0 이하이면 명령어 c로 분기하는 조건 분기(conditional branch) 처리(3개 층), (6) softmax 근사 오차를 ReLU 기반 회로로 제거하는 오차 보정(error correction), (7) cEOF 명령어로 프로그램 종료 및 최종 상태 유지의 순서로 진행된다. §5.2에서는 이를 일반화한 FLEQ(Flexible EQuality instruction)를 도입하는데, SUBLEQ가 뺄셈만 수행하는 것과 달리 FLEQ(a, b, c, m, flag, p, dh, dw)는 M개의 사전 정의된 transformer 기반 함수 블록(function block) 중 하나인 fm을 호출해 mem[c]=fm(mem[a], mem[b])를 실행하고 독립적으로 조건 분기를 수행하므로, 행렬 곱셈·제곱근·활성화 함수 등 임의 반복 알고리즘을 단일 명령어 체계 안에서 표현할 수 있다. Theorem 2는 이 구조가 최대 9+max{l1,…,lM}층, Σhi 헤드로 T개의 FLEQ 명령어를 실행하는 Unified Attention Based Computer를 구성함을 보이고, Corollary 1은 이를 순수 함수 호출과 조건 분기 두 가지 단순 명령어로 분리 가능함을 도출한다. 부록 C는 저자들의 SUBLEQ 변형(메모리와 명령어를 분리한 제한판)이 Turing completeness(튜링 완전성)를 잃지 않음을 Minsky machine(레지스터 기반 범용 계산 모델)으로의 환원(reduction)을 통해 증명하는데, Minsky machine의 add(a) 명령어는 SUBLEQ 한 줄로, sub(a,n) 명령어는 5개의 SUBLEQ 명령어 시퀀스로 변환됨으로써 두 계산 모델의 동등성이 확보된다. 루프 구조가 이 전체 설계에서 결정적 역할을 하는데, 루프 없이 모든 명령어를 직렬로 펼치면 transformer의 깊이가 프로그램 길이에 비례해 커져야 하지만, 루프를 도입하면 transformer 자체의 깊이는 고정(9층 이하)된 채 반복 횟수만 프로그램 복잡도에 비례하여 증가하므로 실용적인 범용 컴퓨터 구성이 가능해진다.

함수 블록 라이브러리 (§6)

§6은 FLEQ 컴퓨터(§5에서 구성한 looped transformer 기반 범용 컴퓨터)에 꽂아 쓸 수 있는 함수 블록(function block) 라이브러리를 제시하며, 이후 섹션의 반복 알고리즘 구성에 핵심적으로 쓰인다. 6.1절은 어텐션(attention) 메커니즘 안에 임의 비선형 함수를 인코딩하는 방법을 다룬다. softmax가 sigmoid(시그모이드, σ(x)=1/(1+e⁻ˣ))처럼 동작하도록 강제하고, 쿼리(query)·값(value) 가중치 행렬에 시그모이드 계수를 저장해 sigmoid의 선형 결합으로 임의 함수를 근사한다. Barron [1993]의 Theorem 3에 따르면, Fourier 적분이 C로 유계(bounded)인 함수 클래스 Γ_{C,B}에 속하는 임의 함수는 m개의 sigmoid 항으로 근사할 때 근사 오차가 O(1/√m)으로 감소한다(τ ≥ m^{1/2} ln m 조건 하). Lemma 5는 이를 FLEQ 템플릿 입출력 형식에 맞게 구체화하여, 3층(layer)·m헤드(head) 어텐션 블록이 인디케이터 벡터(indicator vector) e_j로 선택된 함수 f_j(x)=Σ c_{ji}σ(x^T a_{ji})를 출력함을 보인다. 6.2절은 softmax 선형화(linearization)를 이용해 행렬 전치(transposition)와 행렬 곱셈(multiplication)을 구현한다. 열 벡터 z=[x, C]에 큰 상수 C를 덧붙이면 softmax가 선형적으로 동작한다는 성질을 활용하며, Lemma 6(4층·1헤드)은 d×d 행렬 A의 전치 A^⊤를 오차 ε 이내로 출력하고, Lemma 7(2층·1헤드)은 A^⊤B를 오차 행렬 M(‖M‖≤ε) 이내로 계산한다. 6.3절은 어텐션 기반 네트워크와 완전연결(FC, fully-connected) 네트워크 사이의 깊이 분리(depth separation) 이점을 논증한다. x² 같은 다항식 함수를 ReLU FC망으로 근사하려면 근사 품질 ε에 대해 깊이 O(log(1/ε))가 필요한 반면(Perekrestenko et al., 2018), 어텐션으로는 실질적으로 2층만으로 구현 가능하다. 이 상수 깊이 대 스케일링 깊이(constant vs scaling depth)의 격차는 FLEQ 컴퓨터가 어텐션 블록으로 함수 연산을 효율적으로 수행할 수 있음을 이론적으로 뒷받침한다.

응용 ①: 기본 계산기 (§7)

이 섹션(§7)은 논문 전체 thesis인 “가중치 하드코딩 looped transformer로 범용 컴퓨터를 구성할 수 있다”는 주장을 구체적 응용으로 실증하는 첫 번째 사례로, §5.2에서 정의된 FLEQ 프레임워크 위에 12층(layer) 트랜스포머 계산기를 실제로 구성할 수 있음을 Theorem 4로 공식화한다. 이 계산기는 6개의 transformer-based function block(트랜스포머 구조로 구현된 개별 연산 단위)으로 구성되며, 각각 덧셈(Lemma 8: 3층, 1헤드), 뺄셈(Lemma 9: 3층, 1헤드), 곱셈(Corollary 2: 2층, 1헤드), 퍼센트(Corollary 3: 2층, 1헤드), 역수(Corollary 4: 3층, m헤드, 오차 O(1/√m)), 제곱근(Corollary 5: 3층, m헤드, 오차 O(1/m))을 담당한다. 역수와 제곱근은 각각 Lemma 10과 Lemma 11에서 sigmoid(시그모이드) 함수의 합으로 해당 함수를 균등 근사(uniform approximation)할 수 있음을 보인 뒤, Lemma 5를 통해 트랜스포머 가중치로 인코딩되며, 역수는 피연산자 범위 [Ω̃(1/√m), Õ(e^m)], 제곱근은 [0, O(m²)]에서 보장이 성립한다. Algorithm 3은 복합 수식 √(1/((a+b)−c)·d) / 100을 fadd → fsub → fmul → finv → fsqrt → fperc 여섯 단계로 순차 실행하는 샘플 프로그램으로, 함수 블록들이 메모리 슬롯(mem[·])을 통해 연결되는 입력→출력 체인을 구체적으로 보여 준다. 나아가 저자들은 sigmoid 근사 또는 반복 수치 알고리즘(iterative numerical algorithm, y_{k+1} = g(y_k) 형태)을 이용해 대수·삼각 함수 등 더 다양한 연산으로 계산기를 확장할 수 있음을 논의한다.

응용 ②: 선형대수 (§8)

이 섹션(§8)은 논문의 핵심 주장의 두 번째 수치 응용 사례로서, §6의 행렬 곱셈·전치(transpose) 함수 블록 위에 두 가지 반복 선형대수 알고리즘을 구체적으로 구현한다. 첫째, Newton-Raphson 행렬 역행렬(matrix inversion) 알고리즘(Algorithm 4/5)으로, Lemma 12는 임의의 ε > 0에 대해 13층(layers), 1 헤드(head), 차원 r = O(d)인 transformer가 출력 오차 ε 이내로 Algorithm 4를 에뮬레이션(emulation)함을 증명한다. 둘째, Power Iteration(거듭제곱 반복법) 알고리즘(Algorithm 6/7/8)으로, 지배 고유벡터(dominant eigenvector)를 구하되 정규화(normalization) 단계에서 2차 수렴하는 Newton 역제곱근 알고리즘(Algorithm 7)을 추가로 활용하며, Lemma 13은 동일하게 13층·1 헤드·r = O(d) transformer가 T = O(log 1/ε) 반복으로 오차 ε 이내 결과를 냄을 보인다. Charton(2021)의 학습 기반(learning-based) 접근과 크기를 비교하면, 30×30 행렬 전치 작업 기준으로 본 논문의 구성은 1층·1 헤드·폭(width) 168을 사용하고 Charton(2021)은 1층·8 헤드·폭 256을 사용하여 네트워크 크기가 유사한 수준임을 확인한다. 저자들은 QR 분해(QR decomposition), Gauss-Seidel법, Arnoldi 반복(Arnoldi iteration), Lanczos 알고리즘 등 추가 수치 선형대수 알고리즘도 동일 아키텍처로 구현 가능하다고 언급하며, 이 절이 소규모 선형대수 라이브러리(linear algebra library)를 transformer로 구축할 수 있다는 개념 증명(proof of concept)임을 명시한다.

응용 ③: 추론 시점의 학습 알고리즘 에뮬레이션 (§9)

이 섹션(§9)은 looped transformer가 범용 컴퓨터임을 보이는 세 번째 핵심 응용으로, FLEQ(통합 어텐션 기반 컴퓨터 프레임워크) 위에서 확률적 경사하강법(SGD, Stochastic Gradient Descent)과 역전파(Backpropagation)를 추론 시점에 직접 에뮬레이션함으로써 “트랜스포머가 내부적으로 SGD를 실행하여 문맥 내 학습(ICL, In-Context Learning)을 수행한다”는 선행 가설에 구성적 증거를 제공한다. 선형 모델의 경우 Lemma 14와 Algorithm 9를 통해, **13 layers, 1 head, 차원 O(log(D)+d)**인 트랜스포머가 D개 데이터 포인트에 걸쳐 T회 SGD 반복을 오차 ε 이하로 구현할 수 있음을 증명한다. 이를 2층 비선형 신경망으로 확장한 것이 Lemma 15와 Algorithm 10/11/12이며, 시그모이드(sigmoid) 활성화 함수에 대한 역전파를 서브루틴으로 캡슐화하여 동일한 13층 구조로 SGD를 실현한다. Remark 4는 손실함수가 임의의 f일 때 근사 오차를 제어하려면 일반적으로 poly(TD)개의 어텐션 헤드가 필요하지만, f’(x)가 시그모이드의 합(sum of sigmoids)이면 헤드 수가 해당 시그모이드 개수와 같아져 추가 오차가 사라짐을 밝힌다(Remark 5/6은 활성화 함수 일반화와 포인터 재활용에 관한 구현 상의 트레이드오프를 논의한다). 마지막으로, Algorithm 12의 구성은 임의 깊이의 신경망으로 일반화될 수 있으나, 루프 횟수가 대상 네트워크의 층 수에 비례하여 증가한다는 비용 구조를 명시한다. Akyürek et al. [2022] 및 Garg et al. [2022] 등 선행 연구가 단일 추론 호출과 선형 회귀로 ICL을 제한한 것과 달리, 본 섹션은 looped 구조와 복수 추론 호출을 통해 더 폭넓은 모델 클래스와 높은 정확도를 달성하며, 일반 손실함수와 비선형 모델에 대한 SGD 구현이 가능함을 처음으로 보인다.

결론과 열린 문제 (§10)

이 결론 섹션(§10)은 논문 전체의 핵심 주장 — 가중치를 직접 하드코딩(hardcoding)한 looped transformer가 범용 컴퓨터로 동작함 — 을 집약하고, 실제 대규모 모델에 대한 함의(implication)와 향후 열린 문제를 제시하며 논의를 마무리한다. 저자들은 상수 깊이(constant-depth)의 인코더 레이어만으로 어휘순 연산(lexicographic operations), 비선형 함수, 함수 호출(function call), 프로그램 카운터(program counter), 조건 분기(conditional branch) 등 기본 컴퓨팅 블록을 에뮬레이션할 수 있음을 보였으며, 이를 통해 기본 계산기·선형대수 라이브러리·역전파(backpropagation) 기반 in-context learning 알고리즘까지 구현했다고 요약한다. 이어서, GPT-3 같은 고성능 트랜스포머 모델이 맥락 예시와 지시를 처리할 때 내부적으로 이와 유사한 서브루틴(subroutine)을 활용할 가능성을 제기하되, 본 논문의 구성이 학습(training)과 무관한 수작업 하드코딩임을 명확히 경고한다. 열린 문제로는 (1) 하드코딩 모델과 사전학습(pretrained) 대형 트랜스포머의 융합(fusing), (2) 자연어 입력 명령의 토큰화(tokenization) 방식 탐구, (3) 더 큰 네트워크가 looped transformer의 스킬을 습득하는 모델 증류(model distillation), (4) 입력-출력 쌍 및 내부 표현을 활용한 소형 네트워크의 실험적 검증, (5) 이 설계를 구현·학습하기 쉽게 하는 아키텍처 변경 방향이 나열되어 있으며, 이론적 구성에서 실증 연구로 나아가는 길이 아직 열려 있음을 강조한다.

---

프레임워크 다이어그램

graph TB
    PROMPT["입력 프롬프트 = 펀치카드<br/>Scratchpad + Memory + Commands"] --> TF["고정 가중치 트랜스포머 (13층 이하, 하드코딩)"]
    TF --> OUT["출력 시퀀스"]
    OUT -->|"단일 루프: 출력을 입력으로 되먹임 (CPU 클럭 사이클)"| PROMPT

    subgraph blocks["빌딩블록 (§4)"]
        B1["프로그램 카운터<br/>(이진 위치인코딩, Lemma 1)"]
        B2["read / write<br/>(Lemma 2·3)"]
        B3["조건분기 if-goto"]
    end

    subgraph computer["범용 컴퓨터 (§5)"]
        S1["SUBLEQ OISC<br/>9층·2헤드 (Lemma 4)"]
        S2["FLEQ 일반화<br/>(Theorem 2)"]
    end

    subgraph apps["응용 (§7-9)"]
        A1["계산기 (12층)"]
        A2["선형대수: 역행렬·Power Iteration (13층)"]
        A3["SGD·역전파 ICL (13층)"]
    end

    blocks --> computer
    FN["함수 블록 라이브러리 (§6)<br/>sigmoid 근사·행렬연산"] --> S2
    computer --> apps
    TF -.구현.- computer

관련 연구 비교 매트릭스

선정 근거: 5편 모두 “depth-wise 반복(looping/recurrent-depth)“이라는 공통 축으로 비교 가능하며, 기반 연구(Universal Transformers), 직접 후속 2편(Yang et al., Saunshi et al.), 구조 확장(AlgoFormer), 그리고 실전 SOTA 대안(Geiping et al.)으로 본 논문의 이론적·실용적 위치를 입체적으로 드러낼 수 있다.

축	본 논문 (Giannou et al., 2023)	Universal Transformers (Dehghani et al., 2019) [base]	Looped → Learning Algorithms (Yang et al., 2023) [direct]	AlgoFormer (Gao et al., 2024) [direct-확장]	Reasoning w/ Latent Thoughts (Saunshi et al., 2025) [direct-후속]	Recurrent Depth (Geiping et al., 2025) [alternative/sota]
핵심 접근	가중치를 해석적으로 하드코딩한 looped transformer로 범용 컴퓨터 구성 (역설계)	층간 가중치 공유 + ACT halting을 학습으로 최적화하는 보편적 재귀 모델	looped 아키텍처를 gradient descent 기반 ICL 알고리즘 학습에 적용	pre/loop/post 세 단계로 분리된 알고리즘 구조 프레임워크	looped 모델의 추론 귀납편향을 1B LM 사전학습으로 실증 + CoT 시뮬레이션 이론	recurrent block을 테스트타임 임의 깊이로 unroll하는 3.5B 실전 사전학습
문제 정의	”고정 파라미터 transformer가 임의 프로그램을 에뮬레이션할 수 있는가?” (표현력 증명)	“단일 가중치 집합으로 가변 깊이 추론이 가능한가?” (범용성 + 효율)	“looped 구조가 적은 파라미터로 ICL 학습 알고리즘을 유도하는가?” (귀납편향)	“전통 알고리즘 구조를 transformer 설계에 명시적으로 이식할 수 있는가?” (아키텍처 설계)	“looping이 다단계 추론(CoT)을 내재화하는가?” (이론+실증)	“테스트타임 추가 연산(더 많은 loop)이 성능을 향상시키는가?” (스케일링)
데이터	없음 (구성적 증명, 합성 회로)	WMT EN-DE, LM1B, bAbI, MNIST 등 벤치마크	회귀·분류 ICL 합성 데이터셋	언어 모델링 / NLP 벤치마크	합성 추론 과제 + Pile 1B 사전학습	사전학습 코퍼스 3.5B 파라미터 규모, 수학·코딩·추론 벤치마크
핵심 메트릭	이론적: 13층 이하로 SUBLEQ → FLEQ → 선형대수·역전파 에뮬레이션 성공 (층 수 상수)	BLEU +0.9 (WMT), bAbI 정확도 향상; ACT 적응 깊이	표준 transformer 대비 파라미터 10% 미만으로 동등 ICL 성능	NLP 태스크에서 표준 transformer 대비 효율·성능 개선 (정량 수치 미상)	looped LM이 iso-flop 기준선 대비 추론 벤치마크 우위; CoT 시뮬레이션 이론 정립	3.5B 모델에서 테스트타임 루프 증가시 수학·코딩 성능 단조 향상
확장성	층 수 고정(≤13), 루프 횟수만 증가 → 프로그램 길이에 독립적 상수 깊이	학습 시 가변 깊이, ACT로 동적 halting → 입력 복잡도에 적응	파라미터 효율 우수, 루프 수 조정으로 ICL 난이도에 적응	pre/post 단계 분리로 모듈형 확장 가능; 루프 블록만 반복	사전학습 규모 1B, 루프 수로 추론 깊이 조절	테스트타임 루프 임의 확장 가능 (3.5B), 실전 스케일 검증
한계	[저자 인정] 실제 학습 없음, 구성적 증명만; 노이즈·양자화 없는 이상적 산술 가정. [독자 식별] 실용 모델로의 전환 경로 미제시, 입력 레지스터 포맷 수동 설계 필요	[저자 인정] ACT overhead; 매우 긴 의존성에서 한계. [독자 식별] 범용 계산 표현력 하한 미증명	[독자 식별] 이론 보장 부재, 제한적 태스크 범위	[독자 식별] 이론적 표현력 분석 없음, 구현 세부 미공개	[저자 인정] 사전학습 비용 높음. [독자 식별] 루프 수 선택 기준 불명확	[저자 인정] 학습 불안정성; 테스트타임 계산 비용. [독자 식별] looping이 실제 알고리즘 에뮬레이션인지 불분명
코드 공개	❌ (구성적 증명, 코드 미제공)	✅ (tensor2tensor)	미상	미상	❌ (비공개)	✅ (seal-rg/recurrent-pretraining)

본 논문의 차별점 요약

본 논문은 looped transformer가 “프로그램 길이에 무관한 상수 깊이(≤13층)“만으로 SUBLEQ·FLEQ를 포함한 임의 알고리즘을 에뮬레이션할 수 있음을 최초로 구성적으로 증명했다는 점에서, 이전 연구들과 근본적으로 다르다. Universal Transformers나 Geiping et al.은 루프/깊이 증가가 표현력을 높인다는 경험적·적응적 접근에 머무는 반면, 본 논문은 가중치를 역설계로 하드코딩함으로써 “어떤 계산이 몇 층으로 가능한가”에 대한 엄밀한 구성적 상계를 제시한다. 또한 Yang et al.·Saunshi et al.·AlgoFormer가 학습된 looped 모델의 귀납편향을 다루는 데 비해, 본 논문은 학습을 전혀 사용하지 않고 특정 연산 원시(read/write·조건분기·프로그램 카운터)만으로 범용 컴퓨터를 조립하는 모듈형 구성 원리를 확립함으로써, 이후 looped 모델 해석 및 설계 연구의 이론적 기반이 된다.

---

원자적 인사이트 (Zettelkasten)

💡 루프가 트랜스포머의 깊이를 프로그램 길이에서 분리한다

출처: Giannou et al., 2023 (본 노트)
유형: 이론적

트랜스포머의 표현력을 “더 깊게”가 아니라 “같은 블록을 더 많이 반복”으로 확보할 수 있다는 발상이다. 출력을 입력으로 되먹이는 단일 루프를 두면, 필요한 모델 깊이는 “한 명령어 실행에 드는 상수 깊이”로 고정되고 실행할 프로그램의 길이와 무관해진다. 이는 회로는 고정이고 클럭이 명령을 반복 처리하는 실제 CPU의 구조와 정확히 대응한다.

핵심 조건/맥락: 가중치를 수작업 하드코딩한 구성에서 성립. 13층 미만 looped transformer가 범용 컴퓨터를 에뮬레이션(Theorem 1). 학습으로 이 구조가 출현함을 보인 것은 아님.
연결: Reasoning with Latent Thoughts - On the Power of Looped Transformers
활용 가능성: 추론 시 루프 횟수를 동적으로 늘려 “생각의 깊이”를 조절하는 아키텍처, 파라미터 효율적 추론 모델 설계의 이론적 근거.

💡 단일 명령어(SUBLEQ)만으로 어텐션을 범용 컴퓨터로 환원한다

출처: Giannou et al., 2023 (본 노트)
유형: 방법론적

복잡한 명령어 집합 대신, “빼고 결과가 0 이하면 분기하라”는 단 하나의 명령어(SUBLEQ)만으로도 튜링 완전하다는 OISC 이론을 트랜스포머에 옮긴 것이 핵심 트릭이다. 어텐션 헤드를 역설계해 read/write·조건분기·프로그램 카운터를 만들면, 이 최소 명령어 컴퓨터가 9층·2헤드(§5.1)라는 극히 얕은 구성으로 조립된다. 이후 FLEQ로 일반화해 함수 호출까지 유연하게 확장한다.

핵심 조건/맥락: SUBLEQ의 튜링 완전성은 Minsky machine 환원으로 증명(부록 C). 명령어를 최소화할수록 트랜스포머 블록 설계가 단순해진다는 역설적 이점.
연결: Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
활용 가능성: 신경망에 명시적 알고리즘을 “컴파일”해 넣는 neural compilation 연구, 트랜스포머 해석가능성(어떤 회로가 어떤 연산을 수행하는지) 분석의 청사진.

💡 존재 증명과 학습 가능성은 별개다 — 하드코딩의 의도적 한계

출처: Giannou et al., 2023 (본 노트)
유형: 실패-한계

저자들이 직접 강조하는 메타적 인사이트다. 이 논문은 트랜스포머가 범용 계산 능력을 “가질 수 있다”는 존재 증명일 뿐, 표준 사전학습이 그런 구조를 실제로 발견하는지는 전혀 보이지 않는다. 가중치를 손으로 심었기 때문이다. 능력의 상한(capability)과 학습 가능성(learnability)을 혼동하지 말라는 경고로, 이론적 표현력 결과 전반을 읽는 올바른 렌즈를 제공한다.

핵심 조건/맥락: 모든 결과가 manual weight construction. 정밀 위치인코딩·softmax 온도 근사의 유한정밀도 견고성도 미검증.
연결: A Theoretical Understanding of Self-Correction through In-Context Alignment
활용 가능성: 표현력 정리를 해석할 때의 비판적 기준선, “이론상 가능 vs 훈련으로 출현”의 간극을 메우는 후속 실증 연구 설계.

핵심 용어 정리

용어	설명
Looped Transformer	출력을 다시 입력으로 되먹이는 단일 루프 안에 넣어 같은 트랜스포머 블록을 반복 실행시키는 구조. 깊이를 늘리지 않고 표현력을 확보한다.
In-context learning (ICL)	가중치를 갱신하지 않고 프롬프트에 주어진 예시만으로 새 작업을 수행하는 능력.
OISC / SUBLEQ	One Instruction Set Computer. 단 하나의 명령어만 가진 컴퓨터. SUBLEQ는 “빼고 결과가 0 이하면 지정 주소로 분기”라는 명령 하나로 튜링 완전한 대표적 OISC.
FLEQ	SUBLEQ를 일반화해 함수 호출까지 다룰 수 있게 확장한 명령어. 함수 라이브러리(§6)와 결합해 유연한 프로그램 구성을 가능하게 한다.
프로그램 카운터 (program counter)	다음에 실행할 명령어의 메모리 주소를 추적하는 레지스터. 본 구성에서는 ±1 값의 이진 위치인코딩으로 표현된다.
위치인코딩 (positional encoding, ±1 이진)	시퀀스 내 위치 정보를 모델에 주입하는 벡터. 여기서는 ±1만으로 이진 주소를 표현해 read/write와 분기의 좌표 역할을 한다.
조건분기 (conditional branching, if-goto)	조건이 참일 때 프로그램 실행 흐름을 다른 주소로 점프시키는 제어 구조. 어텐션과 ReLU로 구현된다.
Turing completeness	충분한 메모리만 있으면 어떤 계산도 수행할 수 있는 계산 모델의 성질. SUBLEQ가 이를 만족함이 Minsky machine 환원으로 증명된다(부록 C).
softmax 온도 λ / hardmax 근사	softmax에 큰 온도 계수 λ를 곱해 가장 큰 값에만 거의 1을 몰아주는 hardmax(최댓값 선택)처럼 동작시키는 기법. 결정론적 read/write·분기를 구현하는 데 쓰인다.
Barron 정리	적절한 매끄러움 조건을 가진 함수를, 폭 m인 1층 신경망(시그모이드)으로 근사할 때 오차가 약 1/√m로 줄어든다는 근사 이론. §6 함수 라이브러리의 토대.
Depth separation	얕은 신경망으로는 효율적으로 표현 못 하지만 깊은 망으로는 가능한 함수가 존재함을 보이는 결과. 어텐션이 FC망 대비 갖는 상수 깊이 이점의 근거.
Existence proof (구성적 증명)	“그런 대상이 존재한다”를 실제로 하나 만들어 보이는 증명. 본 논문은 수작업 하드코딩으로 능력의 존재를 보일 뿐, 학습 가능성은 다루지 않는다.

관련 연구

• Reasoning with Latent Thoughts - On the Power of Looped Transformers — 본 논문의 “깊이 상수화” 루프 발상을 추론 능력 관점으로 잇는 직접 후속 연구. 하드코딩 존재증명에서 학습된 추론으로의 다리.
• Chain-of-Thought Prompting Elicits Reasoning in Large Language Models — 프롬프트만으로 다단계 계산을 유도한다는 점에서, 명시적 알고리즘 실행(본 논문)과 자연어 추론 유도(CoT)의 대조 축.
• A Theoretical Understanding of Self-Correction through In-Context Alignment — ICL을 이론적으로 분해한다는 공통 결, “이론상 가능 vs 훈련으로 출현”의 간극을 함께 비추는 자매 연구.
• Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling — 루프/반복(순환) 구조로 깊이를 대체한다는 발상의 RNN 계보 비교점.

태그

paper #2023 transformer in-context-learning turing-completeness looped-transformer theory

---

BibTeX

@inproceedings{giannou2023,
  title={Looped Transformers as Programmable Computers},
  author={Giannou, Angeliki and Rajput, Shashank and Sohn, Jy-yong and Lee, Kangwook and Lee, Jason D. and Papailiopoulos, Dimitris},
  booktitle={Proceedings of the 40th International Conference on Machine Learning},
  series={Proceedings of Machine Learning Research},
  volume={202},
  year={2023},
  url={https://arxiv.org/abs/2301.13196},
  eprint={2301.13196},
  archivePrefix={arXiv}
}