트랜스포머 깊이의 천장: TC⁰과 P

📍 현재 위치: V부 · 신경 깊이: 사고 사슬과 강화학습 — 12장. 작업-깊이 트릴레마는 모든 계산에 총 작업량과 피할 수 없는 순차적 깊이라는 두 축으로 값을 매기고, 어느 한쪽을 다른 쪽과 바꾸기를 거부하는 추론 조각들을 찾아냈습니다; 이 장은 그 잣대를 지배적인 신경망 아키텍처에 겨누어 그 깊이 예산을 읽어냅니다.

앞 장은 자신의 법칙이 다른 옷을 입고 다시 나타나리라는 경고로 끝을 맺었는데, 그 첫 번째 옷이 바로 트랜스포머 자신입니다. 트랜스포머는 입력의 모든 위치에 대해 한꺼번에, $L$ 개의 층을 차례로 적용합니다. 그 규모에 관한 모든 것은 너비 안에 삽니다: 더 많은 위치, 더 넓은 임베딩, 더 많은 어텐션 헤드, 층마다 더 많은 매개변수입니다. 자라지 않는 단 하나의 수가 바로 $L$ 입니다. 작업-깊이 장의 어휘로 말하면, 트랜스포머는 엄청난 작업량과 상수 깊이를 지닌 기계이며, 트릴레마는 상수 깊이가 공짜로 얻는 선택이 아니라고 말합니다: 그것은 그 기계가 도대체 어떤 함수를 계산할 수 있는가에 관한 주장입니다. 이 장은 그 주장을 정확하게 만드는 정리 계열을 진술하며, 수입된 이론에 대한 이 시리즈의 규율을 지킵니다: 그 결과들은 로그 정밀도 트랜스포머를 상수 깊이 문턱-회로 클래스 TC⁰ 안에 둡니다. 따라서 TC⁰ 밖에 있는 어떤 문제든, 매개변수 개수가 아무리 많아도 모든 고정 깊이 트랜스포머의 손이 닿지 않는 곳에 있으며, 그 분리 결과들의 지위는 정직하게 밝혀 둘 것입니다. 그런 다음 컴패니언 모듈 depth_ceiling.py는 장난감이 정당하게 내놓을 수 있는 것, 즉 정리가 아니라 메커니즘을 제공합니다: 깊이를 필요로 하는 두 과제의 짧은 사례들로 훈련된 고정 깊이 네트워크는 자신의 훈련 구간 안에서는 일반화되지만 절벽 너머에서는 우연 수준으로 무너지며, 추가된 깊이는 그 절벽을 바깥으로 밀어낼 뿐 결코 없애지는 못합니다.

쉽게 말하면

정확히 세 개의 작업대로 이루어진 공장 조립 라인을 상상해 보십시오. 각 작업대에는 만 명의 노동자가 나란히 설 수 있고, 컨베이어 벨트 위의 모든 제품이 동시에 작업되므로 그 라인은 놀랍도록 빠릅니다. 하지만 제품 하나는 각 작업대를 순서대로 딱 한 번씩만 거칩니다. 네 번째 단계가 세 번째 단계의 결과를 반드시 보아야 하는, 진짜로 네 개의 연속된 단계가 필요한 조리법이라면 한 번의 통과로는 끝낼 수 없으며, 노동자를 더 고용해도 아무것도 바뀌지 않습니다. 첫 번째 작업대의 노동자들은 두 번째와 세 번째 단계가 존재하기도 전에 네 번째 단계를 수행할 수 없기 때문입니다. 그것이 바로 트랜스포머입니다: 작업대는 층이고 노동자는 너비이며, 의존하는 단계의 수가 주문의 크기에 따라 늘어나는 조리법은 인원을 아무리 늘려도 결국 그 라인에 들어맞지 않게 됩니다. 빠져나갈 길은 정확히 두 가지입니다. 주문이 도착하기 전에 작업대를 더 지어 공장을 다시 짓거나(더 많은 깊이), 반쯤 완성된 제품을 라인 둘레로 몇 번이고 다시 돌리는 것입니다(순차적 디코딩). 다음 장은 그 두 번째 길에 관한 이야기입니다.

이 장에서 다루는 내용

기계의 형태: 트랜스포머의 매개변수가 어째서 깊이가 아니라 너비를 사는지, 그리고 앞 장의 작업-깊이 어휘가 "층이 몇 개인가"를 어떻게 "어떤 복잡도 클래스인가"로 바꾸어 놓는지.
밑바닥부터 쌓는 문턱 회로: 불 회로족, 모든 기호가 해독된 AC⁰와 TC⁰ 클래스, "균일하다"는 것이 무엇을 배제하는지, 그리고 계수 게이트로 PARITY를 TC⁰ 안에 넣는 완전한 구성.
규율을 지켜 수입한 천장 정리: 중간 디코딩이 없는 로그 정밀도 트랜스포머는 균일 TC⁰ 안에 놓인다는 것; 정밀한 진술, 출처, 이 권을 넘어서는 증명이 왜 그런지, 그리고 컴패니언이 대신 무엇을 보여 주는지.
어텐션 사다리: 포화 어텐션과 평균화 어텐션은 MAJORITY와 TC⁰에 도달하고, 하드 유일 어텐션은 AC⁰ 안에 머무르며, PARITY가 무조건적으로 그 발판들을 갈라놓으므로, 어텐션의 비선형성 자체가 복잡도의 선택이라는 것.
커밋된 절벽들: 길이 2부터 6까지로 훈련되고 2부터 16까지로 시험된 깊이 1/2/3 네트워크들; 깊이별 정확도 표, 유도된 절벽 통계량, 모든 판독을 지키는 assert들, 그리고 이 장난감이 보여 주는 것과 보여 주지 못하는 것에 대한 정직한 진술.
시리즈 자신의 대상들을 정리하기: 1권의 폐쇄 파동들, 2권의 PTIME-완전 완성, 3권의 역할-사슬 천장, 그리고 이 장의 두 과제를, TC⁰ 선 위와 아래로 나누어 하나의 표에 담습니다.
빠져나가는 두 차선: 지불일 뿐 아키텍처가 아닌 지수적 너비, 그리고 깊이를 시간으로 바꾸는, 다음 장의 정리가 될 순차적 디코딩.

기계의 형태: 깊이 없는 너비

3권의 어텐션 장에서 다룬 아키텍처를 떠올려 봅시다. 트랜스포머 층 하나는 모든 위치의 현재 표현을 받아, 모든 위치 쌍 사이의 어텐션 점수를 계산하고, 그 점수로 값들을 섞은 다음, 각 위치를 작은 피드포워드 신경망에 통과시킵니다. 이 서술 어디에도 위치들 사이의 순차성은 없습니다: 위치 17은 위치 16을 기다리지 않습니다. 유일하게 순차적인 축은 층 색인입니다. 길이 $n$ (토큰의 개수이며, 이 시리즈에서 되풀이되는 크기 매개변수입니다)의 입력은 층 1을 거친 다음 층 2를, 그렇게 층 $L$ 까지 거치는데, $L$ 은 훈련 전에 고정되는 아키텍처 상수로, 보통 수십 개 정도이며 결코 $n$ 의 함수가 아닙니다. 모델을 수백만에서 수천억 매개변수로 키우는 것은 모든 행렬의 너비와 헤드의 개수를 곱해 늘리는 일이지, $L$ 은 기껏해야 작은 상수배로만 늘어납니다. 이 형태는 의도된 것인데, 위치들에 걸친 병렬성이야말로 GPU 장의 하드웨어 위에서 훈련을 다루기 쉽게 만드는 바로 그것이기 때문입니다: 모든 층은 소수의 조밀한 행렬 곱일 뿐이며, 이는 배치 작업 부하로서는 이상적입니다.

작업-깊이 장은 이 형태에 대해 던져야 할 올바른 질문을 우리에게 건네줍니다. 층 하나는 유한한 개수의 의존 단계(점수 계산, 정규화, 혼합, 피드포워드 패스)를 수행하므로, 각 단계가 그 앞 단계의 결과를 필요로 하는 연산 사슬 중 가장 긴 것의 길이는 $L$ 에 비례합니다: 즉 $n$ 에 대해 상수입니다. 층 하나당 작업량은 어텐션 점수만으로도 $n^2$ 자릿수에 이를 만큼 막대하며, 얼마든지 자유롭게 자랍니다. 그래서 트랜스포머는 앞 장이 그린 지도의 극단적인 한 모서리, 즉 최대 작업량과 상수 깊이를 차지합니다. 트릴레마가 준 교훈은 어떤 문제들은 그 모서리에 살기를 거부한다는 것이었는데, 그 문제들이 요구하는 깊이가 입력 크기에 따라 자라기 때문입니다. 이 장이 정확히 답하는 질문은 이렇습니다: 어떤 문제들인가? 상수 깊이는 정확히 무엇을 사 주는가? 그 답은 하나의 회로 클래스이며, 그것에 이름을 붙이는 정리가 바로 이 장의 제목이 말하는 천장입니다 [1].

문턱 회로: 상수 깊이의 화폐

정리를 진술하려면 그 어휘가 필요하며, 이를 밑바닥부터 쌓아 올립니다. 불 회로(Boolean circuit)는 게이트들로 이루어진 방향성 비순환 그래프입니다: 입력 노드는 입력의 비트 $x_1, \ldots, x_n$ 을 실어 나르고, 내부 게이트는 자신에게 들어오는 배선들의 함수를 계산하며, 하나로 지정된 게이트가 출력입니다. 회로의 크기(size)는 게이트의 개수이고, 깊이(depth)는 입력에서 출력까지 가장 긴 경로의 길이로, 앞 장의 의존 사슬 개수에 대응하는 회로판 개념입니다. 하나의 회로는 입력 개수가 고정되어 있으므로, 임의 길이의 입력에 대한 함수를 계산하려면 회로족(circuit family)을 씁니다: 입력 길이 $n$ 마다 하나씩의 회로 $C_n$ 을 두는 것이며, 아래첨자 $n$ 은 그 회로가 다루는 길이를 가리킵니다.

여기서 중요한 상수-깊이 클래스는 두 가지입니다. AC⁰는 상수(모든 $n$ 에 대해 같은 깊이 상한) 깊이와 다항(어떤 고정된 상수 지수 $c$ 에 대해 $C_n$ 의 게이트 수가 많아야 $n^c$ 만큼 자라는 것) 크기를 갖는 회로족으로 풀리는 문제들의 클래스이며, NOT 게이트와 무제한 팬인(unbounded fan-in)을 갖는 AND/OR 게이트를 씁니다. 여기서 무제한 팬인이란 하나의 AND나 OR가 한꺼번에 몇 개의 배선이든 읽어들일 수 있다는 뜻입니다. TC⁰는 상수 깊이와 다항 크기는 그대로 유지하면서 게이트 종류를 하나 더 더한 것으로, 바로 문턱 게이트(threshold gate)입니다: 문턱값 $\theta$ (게이트의 정수 매개변수)에 대해, 게이트 $\mathrm{Th}_{\ge \theta}$ 는 자신의 입력 배선 중 적어도 $\theta$ 개가 1을 나를 때 정확히 1을 출력합니다. 기호로 쓰면, $m$ 개 입력 비트의 보통 정수 합을 $\sum_{i=1}^{m} x_i$ 로 나타낼 때,

\mathrm{Th}_{\ge \theta}(x_1, \ldots, x_m) = 1 \quad \text{exactly when} \quad \sum_{i=1}^{m} x_i \ge \theta.

문턱 게이트는 셀 수 있지만, AND/OR 게이트는 전부-혹은-하나만을 검출할 수 있을 뿐입니다. 특수한 경우인 $\theta = \lceil m/2 \rceil$ (천장 괄호 $\lceil \cdot \rceil$ 는 다음 정수로 올림합니다)가 바로 MAJORITY 게이트이며, 입력의 절반 이상이 1일 때 발화합니다. 그리고 MAJORITY는 그 클래스에 대해 완전합니다. 즉 문턱 게이트를 MAJORITY 게이트로 바꿔도 TC⁰는 달라지지 않는다는 뜻입니다. 진지한 진술이라면 어디에나 하나의 수식어가 더 등장합니다: 균일(uniform)입니다. 회로족은 $n$ 마다 다른 대상이므로, 아무 제약이 없다면 그 족은 계산 불가능한 지식을 배선 안에 몰래 실어 나를 수 있습니다. 길이마다 하나씩 하드코딩된 답을 심어 두는 식으로 말입니다. 어떤 족이 균일하다는 것은, 하나의 단순한 알고리즘(로그 공간이 표준적인 선택입니다)이 $n$ 을 받아 $C_n$ 의 서술을 출력해 줄 때를 말합니다. 균일성은 "회로족이 존재한다"는 진술을 "하나의 유한한 조리법이 그 전부를 짓는다"는 진술로 바꾸어 놓는데, 이것이야말로 가중치가 고정된 하나의 트랜스포머가 실제로 하는 일입니다.

문턱 게이트가 무엇을 사 주는지 보려면, 완전한 구성 하나를 살펴볼 만한데, 이것만큼은 이 장이 직접 소유하는 것이기 때문입니다. PARITY는 $n$ 개의 비트에 대한 함수로, 그중 홀수 개가 1일 때 정확히 1을 출력합니다. 두 개의 문턱 게이트로 정확히- $k$ 검출기를 만들어 봅시다: 입력에서 1의 개수를 $m$ 이라 하면,

E_k(x) = \mathrm{Th}_{\ge k}(x) \wedge \neg\, \mathrm{Th}_{\ge k+1}(x),

여기서 $\wedge$ 는 AND, $\neg$ 는 NOT입니다. 정의에 맞추어 확인해 봅시다: $\mathrm{Th}_{\ge k}$ 는 정확히 $m \ge k$ 일 때 발화하고, $\neg\,\mathrm{Th}_{\ge k+1}$ 은 정확히 $m \le k$ 일 때 발화하므로, 그 논리곱은 정확히 $m \ge k$ 와 $m \le k$ 가 함께 성립할 때, 즉 정확히 $m = k$ 일 때 발화합니다. 이제 무제한 팬인 OR로 홀수 개수들에 대해 합해 봅시다(아래의 기호 $\bigvee$ 는 나열된 모든 경우에 대한 OR입니다):

\mathrm{PARITY}(x) = \bigvee_{k \text{ odd},\; 1 \le k \le n} E_k(x).

그 논리합의 항들은 서로 배타적이므로(개수 $m$ 은 하나의 값만을 가집니다), 이 OR는 정확합니다. 자원을 세어 봅시다: 첫 번째 층에 문턱 게이트가 많아야 $n + 1$ 개, 두 번째 층에 AND/NOT 쌍이 많아야 $n$ 개, 세 번째 층에 OR 하나, 즉 모든 $n$ 에 대해 크기는 $n$ 에 선형이고 깊이는 3입니다. 그러므로 PARITY는 TC⁰ 안에 있으며, 그 회로는 직접 그려 볼 수 있습니다. 이 구성을 마음에 담아 두시기 바랍니다. 이 장에서 가장 깊이 있는 무조건적 사실은, 문턱 게이트가 없다면 이것이 불가능하다는 것이기 때문입니다: 상수 깊이·다항 크기의 어떤 AND/OR/NOT 회로족도 PARITY를 계산할 수 없습니다. 그 분리 결과는 두 절 뒤, 사다리가 그것을 필요로 하는 곳에서 출처와 함께 다시 나옵니다. 알려진 포함 사슬은, 각 클래스가 더 많은 깊이를 허용하는 순서로,

\mathrm{AC}^0 \subseteq \mathrm{TC}^0 \subseteq \mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \mathrm{P},

로 쓰이며, 여기서 $\subseteq$ 는 "~에 포함된다"는 뜻이고, NC¹과 NC²는 (팬인이 유계인 게이트로) 깊이가 각각 $\log n$ 과 $\log^2 n$ 만큼 자라도록 허용된 클래스이며, P는 다항 시간으로, 앞 장들의 완성 절차들이 사는 곳입니다. 이 포함 관계들 가운데 어느 것이 진부분집합인지는 대부분 알려져 있지 않습니다. 이 장이 무조건적으로 쓰는 단 하나의 엄격한 포함은 첫 번째 것뿐이며, TC⁰ 오른쪽에 있는 모든 것은 추측일 뿐이고, 무게가 실릴 때마다 그렇게 표시해 둘 것입니다.

규율을 지켜 수입한 천장 정리

해독할 용어를 하나만 더 거치면 정리를 진술할 수 있습니다. 트랜스포머는 길이 $n$ 의 입력에 대한 순전파 안의 모든 수(활성값, 어텐션 점수, 부분합)가 $O(\log n)$ 비트로, 즉 어떤 고정된 상수 $c$ 에 대해 많아야 $c \log_2 n$ 비트로 저장될 때 로그 정밀도(log-precision)를 갖는다고 합니다. 그 귀결을 해독해 봅시다: $c \log_2 n$ 비트는 많아야 $2^{c \log_2 n} = n^c$ 개의 값을 구별할 수 있으므로, 모든 중간 수량은 다항식 개수만큼의 가능성 안에서만 움직입니다. 이는 실무를 정직하게 이상화한 것으로, 16비트나 32비트 부동소수점은 실제 문맥 길이에 대해 $\log_2 n$ 을 넉넉히 웃도는 상수이며, 이 가정이야말로 활성값 하나가 무한정한 양의 정보를 숨기지 못하도록 지켜 줍니다.

정리 [1]: 층의 개수가 고정되어 있고, 크기가 다항식으로 제한되며, 로그 정밀도 산술을 쓰는 어떤 트랜스포머든, 그것이 답을 곧바로 내놓는 단 한 번의 순전파로만 실행된다면(중간 토큰을 생성해 되먹이는 일이 없다면), 로그공간-균일(logspace-uniform) TC⁰ 안의 언어들만을 인식합니다.

이 문장의 모든 한정어에는 무게가 실려 있습니다. "어떤 트랜스포머든"은 그 한계가 아키텍처적임을 뜻합니다: 즉 가중치를 어떻게 설정하든 성립하므로, 아무리 오래 훈련해도 그 어떤 훈련 실행도 그것을 벗어날 수 없습니다. "층의 개수가 고정되어 있고"는 상수 깊이가 들어오는 지점입니다. "중간 토큰이 없다면"은 다음 장이 열어젖힐 탈출구를 남겨 둡니다. 그 증명은 진정으로 이 권의 범위를 넘어서지만, 그 윤곽은 정직한 한 문단으로 말할 수 있습니다: 로그 정밀도 값들 아래에서는 오가는 서로 다른 수가 다항식 개수만큼만 있고, 층 하나가 그 수들에 대해 수행하는 산술, 즉 $n$ 개 수의 반복 덧셈, 곱셈, 그리고 소프트맥스 정규화 안의 나눗셈은 모두 고전적인 TC⁰의 기본 연산이어서 상수 깊이 문턱 회로로 계산할 수 있습니다. 그러므로 층 하나하나가 상수 깊이로 흉내 낼 수 있고, $L$ 개의 층이 쌓이면 상수의 $L$ 배가 되는데 이는 여전히 상수이며, 신중한 균일성 논증은 하나의 로그 공간 알고리즘이 그 흉내 내는 회로족 전체를 뽑아낼 수 있음을 확인해 줍니다 [1]. 이 장의 컴패니언이 보여 주는 것은 그 논증이 아니며, 이 권의 어떤 것도 그것을 증명하는 것으로 읽혀서는 안 됩니다. 컴패니언이 보여 주는 것은 그 정리가 형식화하는 메커니즘을, 지켜볼 수 있을 만큼 작은 모델 위에서 보여 주는 것입니다.

어텐션 사다리: 아키텍처의 선택이 곧 복잡도의 선택

TC⁰ 천장은 사다리의 한 발판일 뿐이며, 그 사다리의 교훈은 두 개의 추가 결과를 들일 만한 가치가 있습니다. 회로 클래스가 단 하나의 아키텍처 다이얼, 곧 어텐션의 비선형성이 그 점수를 가지고 무엇을 하는가에 어떻게 반응하는지를 보여 주기 때문입니다.

포화 어텐션은 TC⁰와 MAJORITY에 도달합니다. 포화 어텐션(saturated attention)은 소프트맥스의 영도 극한(zero-temperature limit)입니다: 어텐션 가중치가 최대 점수를 달성한 위치들에 걸쳐 균등하게 퍼지는데, 이는 점수들이 뚜렷하게 갈라질 때 실제 헤드가 가까이 다가가는 바로 그 평균화 거동입니다. 포화 어텐션과 부동소수점 활성값을 갖는 트랜스포머는 TC⁰ 안에 놓이며, 평균화 어텐션(averaging attention)은 MAJORITY를 직접 계산하는데, 여러 위치에 대한 평균을 문턱값과 비교하는 것이 정확히 개수를 문턱값과 비교하는 것이기 때문입니다 [2]. 평균화는 곧 셈이고, 셈은 곧 문턱 게이트입니다.

하드 유일 어텐션은 AC⁰ 안에 머무릅니다. 하드 유일 어텐션(hard unique attention)은 정확히 하나의 위치에만 주목하는데, 이는 동점을 위치로 가르는 argmax입니다. 이로부터 지어진 트랜스포머(UHAT와 GUHAT 계열, 곧 유일 하드 어텐션 트랜스포머와 그 일반화 변형)는 AC⁰ 안의 언어들만을 인식합니다 [3]: 헤드마다 증인 하나를 고르는 것은 존재론적 행위이며, 이는 무제한 팬인 AND/OR 회로가 흉내 낼 수 있는 것이고, 셈은 결코 일어나지 않습니다.

PARITY는 무조건적으로 그 발판들을 갈라놓습니다. PARITY는 AC⁰ 안에 있지 않습니다: 상수 깊이·다항 크기의 어떤 AND/OR/NOT 회로족도 그것을 계산할 수 없으며, 이는 복잡도 이론에서 추측이 전혀 필요 없는 몇 안 되는 하한 결과 가운데 하나입니다 [4]. MAJORITY 역시 AC⁰ 안에 있지 않은데, MAJORITY 게이트를 쓸 수 있는 상수 깊이 회로가 패리티를 계산하기 때문입니다(한 절 앞의 그 구성입니다). 그래서 패리티의 불가능성은 곧 MAJORITY의 불가능성으로 그대로 옮겨 갑니다. 따라서 이 두 발판은 진정으로 서로 다른 층입니다: 하드 어텐션 트랜스포머는 모든 길이에서 비트를 2로 나눈 나머지조차 증명 가능하게 셀 수 없는 반면, 포화 어텐션 트랜스포머는 그보다 엄격히 한 단계 위에 자리하여 셀 수는 있지만, 천장 정리에 의해 그 이상은 갈 수 없습니다. 폭넓은 한 조사 연구는 훨씬 더 많은 변종을 이 사다리 위에 지도로 그려 내며, 위치 인코딩, 정밀도 체계, 마스킹 각각이 그 클래스를 움직입니다 [5]. 이 시리즈에서 중요한 것은 이 읽기입니다: 어텐션 안의 비선형성은 곧 복잡도-클래스의 선택이다. argmax 선택과 평균화 가운데 무엇을 고를지는 하이퍼파라미터 하나를 조정하는 일이 아닙니다. 그것은 그 아키텍처가 도대체 셈을 할 수 있는지 없는지를 결정하는 일입니다.

상수 깊이 형태, 그것에 값을 매기는 회로-클래스 사다리, 그리고 훈련된 모델 위에서 그 메커니즘을 보여 주는 커밋된 길이-일반화 절벽들. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

천장이 배제하는 것: 시리즈 자신의 대상들을 정리하기

이 장에 제목을 준 따름정리는 이제 하나의 포함 관계 추적일 뿐입니다. 고정 깊이 로그 정밀도 트랜스포머가 P-완전(P-complete) 문제, 즉 모든 다항 시간 문제가 로그 공간으로 환원되는 문제를 결정했다고 해 봅시다; 앞 장의 데이터로그 폐쇄와 2권의 EL 완성이 그 대표적인 사례입니다. 정리에 의해 그 문제는 로그공간-균일 TC⁰ 안에 놓일 것이고, 균일 TC⁰는 로그 공간 그 자체 안에 들어 있습니다(로그 공간 기계는 상수 깊이 회로를 그때그때 지어서 평가할 수 있습니다). 이 환원들을 합성하면 P 전체가 로그 공간 안에, 따라서 NC² 안에 들어가게 되고(고전적인 시뮬레이션입니다: 로그 공간 기계는 다항식 개수의 구성만을 가지므로, 그 구성 그래프 위의 도달 가능성은 깊이 $\log^2 n$ 의 회로로 계산할 수 있습니다), TC⁰에서 P에 이르는 사슬 전체가 그 가장 아래 발판으로 무너져 내릴 것입니다: 곧 P = NC, 모든 다항 시간 계산이 다중로그 깊이로 병렬화될 수 있다는 것입니다. 그 붕괴는 정확히 앞 장이 표시해 둔, 믿기지는 않지만 아직 반증되지도 않은 가능성입니다. 그러므로 정확한 진술은 조건부이고 정직합니다: 그 계층 구조가 무너지지 않는 한, 어떤 크기의 고정 깊이 트랜스포머도 모든 입력 길이에서 P-완전 문제를 결정할 수 없습니다. 이 장이 기대는 두 분리 결과의 지위를 대조해 봅시다: PARITY가 AC⁰ 밖에 있다는 것은 아무 조건도 없는 정리입니다 [4]; TC⁰가 P보다 엄격히 작다는 것(사실 TC⁰가 NC¹보다도 엄격히 작다는 것)은 보편적으로 믿어지지만 결코 증명되지 않은 추측입니다. 이 시리즈의 규칙은 매번 어느 쪽이 어느 쪽인지 밝히는 것입니다.

천장에 값을 매기고 나면, 이 시리즈 자신의 계산들이 저절로 정리됩니다. 아래 각 행은 독자가 이미 실행해 본 대상이며, 클래스 열은 그 문제가 사는 곳을, 판정 열은 고정 깊이 트랜스포머가 원리적으로 모든 입력 규모에서 그것을 표현할 수 있는지를 묻습니다.

계산(시리즈 안에서 사는 곳)	복잡도의 집	TC⁰ 천장 아래에 있는가?
차수 세기, MAJORITY 방식 집계(3권의 어텐션 풀링)	TC⁰	안: 셈은 곧 문턱 게이트입니다.
$n$ 비트의 PARITY(이 장의 과제)	TC⁰, AC⁰ 밖 [4]	TC⁰ 안이지만 하드-어텐션 발판보다 위입니다.
반복된 $S_3$ 합성(이 장의 과제)	TC⁰ 안, 무조건적: 가해군의 단어 문제는 ACC⁰ ⊆ TC⁰ 안에 있으며, ACC⁰는 AC⁰에 모듈러 계수 게이트를 더한 클래스입니다(배링턴–테리앙 [6])	함수족으로서는 안: 분리의 증인이 아니라 메커니즘 시험대입니다.
반복된 $S_5$ 합성	NC¹-완전(배링턴의 정리 [7])	TC⁰ = NC¹이 아닌 한 밖.
도달 가능성, 원자적-포섭 폐쇄(2권; 앞 장의 제곱 커널)	NL-완전(NL은 비결정론적 로그 공간으로, 방향 그래프 도달 가능성이 사는 곳), NC² 안	TC⁰가 NL을 통째로 삼키지 않는 한 밖.
23개 사실 지식 베이스(KB) 위의 1권 전방 연쇄 폐쇄( $D = 3$ 파동)	고정된 KB에 대해서는 상수 깊이	안: 고정된 사례는 고정된 깊이만 있으면 됩니다.
KB가 자랄 때의 데이터로그/EL 완성(2권; 트릴레마 장)	P-완전	P = NC가 아닌 한 밖.
메시지 전달에 의한 역할-사슬 공리 검사(3권의 천장)	세 개의 변수가 필요, C²(3권 천장의 2-변수 계수 논리)를 넘어섬	그래프 신경망(GNN)에 대응하는 것: 그 자신만의 고정-라운드 천장.

두 행은 잠시 멈추어 볼 만합니다. 1권의 폐쇄가 $D = 3$ 파동으로 끝난 것은 학계 KB가 23개의 사실이기 때문이며, 고정 깊이 네트워크는 진정으로 어떤 고정된 파동 수든 표현할 수 있는데, 이것이 바로 작은 벤치마크가 이 이론에 대한 반증처럼 느껴지곤 하는 이유입니다. 천장은 그 족(family)을 옭아맵니다: KB가 자라면 필요한 파동 수도 자라고, 어떤 상수 $L$ 도 그 전부를 감당하지 못합니다. 그리고 $S_3$ 행은 의도적인 정직함의 전시물입니다. 군론은 가환적인 조각들로부터 쌓아 올릴 수 있는 군을 가해군(solvable group)이라고 부릅니다(이는 전문 용어로, 이 장 앞부분에서 문제가 회로족으로 '풀린다'고 말할 때의 일상적 의미와는 다릅니다); $S_3$ 는 가해군이고 $S_5$ 는 아닙니다. 이 성질이 그 행을 확정합니다: 가해군의 단어 문제(word problem), 즉 반복된 곱의 이름을 대는 과제는 배링턴–테리앙의 미세 구조 정리에 의해 무조건적으로 TC⁰ 안에 있으므로 [6], $S_3$ 는 결코 그 분리의 증인이 될 수 없습니다. 반면 비가해군인 $S_5$ 의 경우, 반복 합성은 배링턴의 정리에 의해 NC¹-완전이므로 [7], 추측된 분리가 실패하지 않는 한 TC⁰ 밖에 있습니다. 그럼에도 컴패니언은 $S_3$ 를 선택했으며, 그 모듈의 독스트링은 그 이유를 미리 밝혀 둡니다(depth_ceiling.py, 30–38행): 이 실험에 필요한 것은 클래스 분리가 아니라 깊이 손잡이(depth knob), 즉 필요한 의존 연산 사슬이 사례의 길이에 따라 자라는 과제입니다. 두 과제 모두 정확히 그 성질을 지니며, 어느 실험도 그 이상으로 팔리지는 않을 것입니다.

장난감이 정직하게 보여 줄 수 있는 것

수입된 이론에 대한 이 시리즈의 규칙은 컴패니언 코드에 대해서도 하나의 따름정리를 갖는데, 이 모듈은 숫자를 단 하나라도 찍기 전에 그것을 산문으로 먼저 수행합니다(depth_ceiling.py, 59–66행): 인용된 정리들은 로그 정밀도 트랜스포머의 표현력(expressiveness), 즉 고정 깊이 네트워크가 도대체 어떤 함수를 표현할 수 있는가에 값을 매기며; 훈련된 작은 MLP(multilayer perceptron, 다층 퍼셉트론, 완전 연결 층들을 쌓은 것)는 그 천장의 경험적 그림자, 즉 위치가 깊이에 따라 자라는 길이-일반화 절벽을 보여 줄 뿐, 회로-클래스 분리 그 자체를 보여 주지는 않습니다. 유한한 실험은 예증할 뿐, 증명하지 않습니다. 방금 표에 기록했듯 두 과제 모두 TC⁰ 안에 있기도 하므로, 이 실험실이 도려내는 것은 그 정리들이 형식화하는 메커니즘입니다: 비선형성을 $L$ 번 거치는 네트워크는 정보를 결합할 기회를 $L$ 번 가지며, 그 사례들이 갈수록 많은 의존적 결합 단계를 필요로 하는 과제는 결국 어떤 고정된 $L$ 에서든 떨어져 나갈 수밖에 없습니다. 적어도 짧은 훈련 사례들로부터 경사 하강법이 실제로 찾아내는 해에 대해서는 그렇습니다. 실행 자체도 그 첫 동작으로 똑같은 면책 조항을 찍어 내며, 아래 블록은 의역이 아니라 커밋된 출력 그대로입니다:

[1] the theory ladder (imported results, cited, never re-proved here)
    unique/generalized hard attention (UHAT/GUHAT) ⊆ AC⁰  [Hao, Angluin & Frank, TACL 2022]
      (averaging hard attention, AHAT, computes MAJORITY ∉ AC⁰: it sits in TC⁰)
    PARITY ∉ AC⁰                                          [Furst, Saxe & Sipser 1984; Håstad 1986]
    saturated attention ⊆ TC⁰                             [Merrill, Sabharwal & Smith, TACL 2022]
    log-precision transformers ⊆ uniform TC⁰              [Merrill & Sabharwal, TACL 2023]
    no CoT: only TC⁰  /  poly-step CoT: P                 [Merrill & Sabharwal, ICLR 2024]
    (theorems about transformer expressiveness; the MLPs below are the lab analogue)

과제 하나: 반복된 $S_3$ 합성, 합성이 깊이를 실어 나르기 때문입니다. $S_3$ 는 3개 문자에 대한 대칭군(symmetric group)입니다: $(0, 1, 2)$ 의 여섯 가지 순열을 사전식 순서로 나열해 원소 0이 항등원이 되도록 하고, 합성은 $(\sigma_a \circ \sigma_b)(x) = \sigma_a(\sigma_b(x))$ 로, 오른쪽 인수가 먼저 작용합니다(depth_ceiling.py, 90–102행). 길이 $n$ 의 사례는 16개의 입력 슬롯 가운데 처음 $n$ 개에 균등 무작위로 뽑은 비항등원소를 써넣고 나머지는 항등원으로 채운 다음, 그 곱을 묻는 6가지 분류 문제입니다(105–138행). 왜 합성이 깊이를 실어 나르는 것일까요? 그 정의상의 평가 자체가, 각 단계가 앞 단계의 결과를 소비하는 사슬이기 때문입니다. 이 모듈은 정확히 그 좌측 폴드(left fold)로 레이블을 계산합니다(111–117행):

def s3_product(elems: np.ndarray) -> np.ndarray:
    """Row-wise product of a (count, n) matrix of element ids, folded left to
    right through the Cayley table: p_0 = e;  p_j = p_{j-1} ∘ g_j."""
    prod = np.zeros(len(elems), dtype=np.int64)
    for j in range(elems.shape[1]):
        prod = MUL[prod, elems[:, j]]
    return prod

그 폴드는 $n$ 개의 자명하지 않은 인수에 대해 $n - 1$ 번의 의존적 곱셈입니다: 즉 깊이가 $n$ 에 선형입니다. 결합법칙은 더 영리한 스케줄로 다시 묶는 것을 허용하는데, 이는 앞 장의 균형 트리가 합을 다시 묶었던 것과 정확히 같습니다: 인접한 인수들을 짝짓고 모든 짝을 한꺼번에 곱하면 $\lceil n/2 \rceil$ 개의 인수가 남고, 이를 반복합니다; $t$ 라운드 뒤에는 많아야 $\lceil n / 2^t \rceil$ 개의 인수가 살아남으므로, $t = \lceil \log_2 n \rceil$ 라운드 뒤에는 하나만 남습니다. $n$ 에 로그인 깊이가 군 곱셈으로 지어진 스케줄들의 바닥이며, 상수 개수의 결합 라운드로 네트워크가 계산하는 $n$ 의 어떤 함수든 이 두 스케줄을 모두 앞질러야 합니다. 더 나아가 PARITY는 이 함수족 안에 내장되며, 그 내장은 모듈이 가정하지 않고 단언하는 두 줄짜리 유도입니다. $\tau$ 를 문자 0과 1을 맞바꾸고 2는 그대로 두는 전치(transposition)라고 합시다. 그것을 자기 자신과 합성하면 모든 문자가 제자리로 돌아오므로 $\tau \circ \tau = e$ , 곧 항등원입니다; 귀납법에 의해, $\tau$ 의 $n$ 개 사본의 곱은 $n$ 이 짝수이면 $e$ (인수들을 짝지으면 됩니다)이고 $n$ 이 홀수이면 $\tau$ 입니다(짝짓기에서 인수 하나가 살아남습니다). $n$ 개 전치의 곱을 말할 수 있는 사람은 누구든 $n \bmod 2$ 를 계산한 것입니다. 하니스는 어떤 훈련도 돌리기 전에 군의 표를 빠짐없이 검사합니다: 결합법칙, 역원, 비가환성, 그리고 이 위수-2 항등식까지(depth_ceiling.py, 332–343행).

과제 둘: 가중치 슬라이스 위의 PARITY, 고전적인 증인. 길이 $n$ 의 사례는 16비트 문자열의 균등 무작위 위치에 정확히 $n$ 개의 1을 놓고 $n \bmod 2$ 를 묻습니다: 이는 $\{0,1\}^{16}$ 의 해밍 무게- $n$ 슬라이스 위의 PARITY이며(141–161행), 바로 이 함수가 무조건적인 AC⁰ 하한이 다루는 그 함수입니다 [4]. 여기서는 깊이 손잡이와 클래스 증인이 일치하며, 레이블은 모든 비트에 의존합니다: 어느 것 하나를 뒤집어도 답이 뒤집힙니다.

커밋된 시연 사례들은 두 인코딩 모두를 구체적으로 보여 줍니다(실제 출력):

[2] the two task families — the depth knob is the length n
    S_3 as image words (0 is the identity): 0:012  1:021  2:102  3:120  4:201  5:210
    iterated composition, n=4:  201 ∘ 210 ∘ 021 ∘ 210  =  021   (class 1; rightmost factor acts first)
    weight-slice parity, n=5:   0110011001000000   →  parity 1 (odd number of ones)

실험실 모델들. 훈련되는 대상은 깊이 1, 2, 3의 MLP이며, 여기서 깊이는 고정된 너비의 tanh(쌍곡탄젠트) 은닉층 개수를 셉니다. 그 위에는 소프트맥스 교차 엔트로피 헤드가 있습니다; 모든 그래디언트는 손으로 유도되는데, 이는 이 시리즈가 1권에서 지었던 것과 같은 $\delta$ -재귀이며, loss_and_grads에서 구현되고(depth_ceiling.py, 191–224행), 헤비볼 모멘텀을 갖는 미니배치 확률적 경사 하강법(SGD)으로 훈련됩니다(227–248행). loss_and_grads의 독스트링이 기록해 둔 두 공식을 해독해 봅시다. 훈련 손실을 $\mathcal{L}$ 로 쓰고(독스트링은 그것을 $L$ 로 쓰지만, 이 장은 $L$ 을 층 개수를 위해 남겨 둡니다), $z$ 는 소프트맥스 이전 점수, $P$ 는 예측된 클래스 확률의 행렬(여기서는 행렬이지, 복잡도 클래스 P가 아닙니다), $Y$ 는 원-핫 참 레이블, $B$ 는 배치 크기, $l$ 은 층 색인, $W_l$ 은 층 $l$ 의 가중치 행렬이고 $W_l^\top$ 은 그 전치, $a_{l-1}$ 은 앞 층의 활성값, $\odot$ 은 성분별 곱, $\delta_l$ 은 층 $l$ 에 도착하는 오차 신호라고 하면: 소프트맥스 소거는 $\partial \mathcal{L}/\partial z = (P - Y)/B$ 로, tanh 역방향 규칙은 $\delta_{l-1} = (\delta_l W_l^\top) \odot (1 - a_{l-1}^2)$ 로 읽힙니다. 이 실험이 무언가를 의미한다고 인정받으려면 먼저 그 산술이 인증되어야 합니다: 이제 $\theta$ 는 네트워크의 평탄화된 매개변수 벡터를 가리키고(문턱 게이트의 정수 매개변수와는 무관한, 이 글자의 두 번째 쓰임입니다) $h$ 는 작은 탐침 걸음일 때, float64로 된 작은 깊이-3 네트워크의 모든 해석적 편미분이 중심 유한차분 $(\mathcal{L}(\theta + h) - \mathcal{L}(\theta - h))/(2h)$ 과 대조되며, 커밋된 실행에서 가장 나쁜 상대 오차는 $2.1 \times 10^{-11}$ 로, $10^{-6}$ 에서 assert로 지켜집니다(256–279행과 346–347행). 그 절벽들이 무엇을 뜻하든, 적어도 역전파 버그는 아닙니다.

프로토콜. 훈련은 오직 짧은 사례, $n = 2$ 부터 $6$ 까지만을 봅니다(패리티는 길이마다 600개, $S_3$ 는 2000개); 평가는 $n = 2$ 부터 $16$ 까지 모든 길이에서 새로 뽑은 사례들을, 길이마다 400개씩 씁니다(83–86행, 287–292행, 295–303행). 통제는 암묵적으로 남겨 두지 않고 코드 안에 명시되어 있습니다: 하나의 과제족 안에서는 하나의 프로토콜 딕셔너리가 은닉 너비(패리티는 32, $S_3$ 는 40), 학습률, 에폭 수, 배치 크기, 그리고 데이터와 모델 시드 둘 다를 고정하며, 세 모델 사이에서 오직 깊이만 달라집니다. 다만 하나의 정직한 단서가 있습니다: 각 모델의 난수 시드는 그 과제의 고정된 모델 시드에 깊이를 더한 값인데(depth_ceiling.py, 284–292행과 358행), 크기가 다른 아키텍처들은 어차피 하나의 초기화를 공유할 수 없기 때문입니다. 이 모듈에는 너비를 훑는 실험이 없으므로, 다가올 격차를 다른 모든 것은 같다는 근거 위에서 깊이 탓으로 돌립니다: 과제마다 세 모델, $L$ 과 그것이 정하는 시드 오프셋을 뺀 모든 것이 동일합니다.

커밋된 절벽들, 신중하게 읽기

그 행들 자체를 읽기 전에, 정확도-대-길이 행 하나하나를 하나의 통계량으로 압축해 봅시다. 우연 정확도를 $c$ 라 할 때(패리티의 두 클래스에 대해서는 $c = 1/2$ , $S_3$ 의 여섯 클래스에 대해서는 $c = 1/6 \approx 0.167$ ), 절벽 위치(cliff position)를, 완벽과 우연의 정확히 중간인 중점 $(1 + c)/2$ 이상을 길이 2부터 $n$ 까지 모든 길이에서 유지하는 가장 큰 $n$ 으로 정의합니다(depth_ceiling.py, 306–316행):

def cliff_length(accs: dict[int, float], chance: float) -> int:
    """The cliff position: the largest n such that accuracy stays at or above
    the midpoint (1 + chance)/2 — halfway between perfect and chance — at
    EVERY length 2..n.  Returns 1 if even n = 2 is below the midpoint."""
    midpoint = (1.0 + chance) / 2.0
    last = 1
    for n in EVAL_LENGTHS:
        if accs[n] < midpoint:
            break
        last = n
    return last

그 중점은 패리티에 대해 $0.750$ , $S_3$ 에 대해 $(1 + 1/6)/2 = 7/12 \approx 0.583$ 입니다. " $n$ 까지 모든 길이"라는 조항이 중요합니다: 한 번 떨어졌다가 회복한 행은 그 회복을 인정받지 못하는데, $n = 4$ 에서 이미 실패한 모델은 그 시점에 이미 과제에서 떨어져 나간 것이기 때문입니다. 아래에 두 커밋된 표를 그대로 옮깁니다; 세로 막대는 훈련 지평 $n = 6$ 을 표시합니다:

[4] PARITY on weight slices (chance 0.500, cliff midpoint 0.750)
      accuracy vs length; '|' marks the training horizon n = 6
        n:      2    3    4    5    6 |    7    8    9   10   11   12   13   14   15   16   train  cliff
  depth 1  1.00 0.97 0.58 0.45 0.87 | 0.08 0.98 0.00 1.00 0.00 1.00 0.00 1.00 0.00 1.00   0.900      3
  depth 2  1.00 1.00 1.00 1.00 1.00 | 0.00 1.00 0.00 1.00 0.00 1.00 0.00 1.00 0.00 1.00   1.000      6
  depth 3  1.00 1.00 1.00 1.00 1.00 | 0.00 1.00 0.00 1.00 0.00 1.00 0.00 1.00 0.00 1.00   1.000      6

[5] iterated S_3 composition (chance 0.167, cliff midpoint 0.583)
      accuracy vs length; '|' marks the training horizon n = 6
        n:      2    3    4    5    6 |    7    8    9   10   11   12   13   14   15   16   train  cliff
  depth 1  1.00 1.00 0.96 0.64 0.47 | 0.10 0.17 0.15 0.14 0.17 0.18 0.19 0.17 0.16 0.20   0.883      5
  depth 2  1.00 1.00 0.98 0.80 0.47 | 0.12 0.17 0.18 0.15 0.12 0.17 0.17 0.17 0.16 0.17   0.995      5
  depth 3  1.00 1.00 0.99 0.81 0.52 | 0.12 0.20 0.16 0.19 0.16 0.14 0.16 0.13 0.15 0.14   0.985      5

먼저 패리티 표를 읽되, 훈련 구간 안에서부터 시작해 봅시다. 깊이 1은 자신의 구간조차 끝내 익히지 못합니다: 정확도가 $n = 4$ 에서 $0.58$ 로, $n = 5$ 에서 $0.45$ 로 떨어지는데, 둘 다 중점 $0.750$ 아래이므로 그 절벽은 훈련받은 길이 안쪽인 $n = 3$ 에 놓입니다. 너비 32짜리 tanh 층 하나로는 훈련 중에 본 깊이-5 의존 구조조차 담아낼 수 없었던 것입니다. 깊이 2와 3은 전체 구간에서 완벽하며, 절벽은 지평 $n = 6$ 에 있습니다. 그 격차, 곧 깊이 1의 절벽 3 대 깊이 2의 절벽 6은 이 실험에서 가장 깔끔한 문장이며, 이는 산문이 아니라 코드로 지켜집니다: 하니스는 깊이 1의 절벽이 $n = 4$ 이하라는 것, 깊이 2가 정확히 그 지평에 도달한다는 것, 그리고 깊이 2가 깊이 1을 엄격히 앞질러 일반화한다는 것을 단언하며(depth_ceiling.py, 389–394행), 두 과제 모두에서 절벽 위치가 깊이에 따라 결코 줄어들지 않는다는 일반적인 단조성 주장도 함께 단언합니다(383–385행).

지평 너머에서는 패리티 행들이 $0.00$ 과 $1.00$ 사이를 오가는데, 이 패턴은 그저 바라보기보다 유도해 볼 가치가 있습니다. 정직한 붕괴 통계량이 무엇이어야 하는지를 그것이 결정하기 때문입니다. 무게- $n$ 슬라이스 위에서는, 주어진 길이의 모든 시험 사례가 같은 레이블 $n \bmod 2$ 를 가집니다. 훈련 분포에서 멀리 밀려난 네트워크는 포화되어 거의 상수인 클래스로 답하며, 상수 답은 참 레이블이 우연히 그것과 맞아떨어지는 길이에서는 정확도 1을, 그렇지 않은 길이에서는 0을 얻는데, 이는 $n$ 에 따라 번갈아 나타납니다. 그래서 그 너머에서는 길이별 정확도만으로는 아무 정보도 주지 못합니다: $n = 10$ 에서의 $1.00$ 은 일반화가 아니라, 하루에 두 번은 달력과 맞아떨어지는 멈춘 시계일 뿐입니다. 정직한 진술은 꼬리 길이 $n = 7$ 부터 $16$ 까지에 대한 평균인데, 이는 홀수 다섯 개와 짝수 다섯 개를 담고 있으므로 상수-답 모델은 정확히 우연 수준인 $0.5$ 로 평균됩니다. 커밋된 꼬리 값은 깊이 1, 2, 3에 대해 각각 $0.506$ , $0.500$ , $0.500$ 이며, 하니스는 모든 꼬리가 우연 수준에서 $0.12$ 이내에 있다는 것과, 동시에 모든 모델이 길이 2에서 $0.90$ 이상을, 자신의 훈련 집합에서 $0.80$ 이상을 익혔다는 것을 단언합니다(370–382행): 그 붕괴는 실재하며, 그것은 짧은 버전의 과제를 증명 가능하게 학습해 낸 모델의 붕괴입니다.

$S_3$ 표는 같은 이야기를 다른 억양으로 들려줍니다. 세 깊이 모두 $n = 5$ 에서 절벽을 맞습니다. 이 규모에서는 그 위치가 동률입니다. 하지만 깊이는 정확히 이론이 그래야 한다고 말하는 지점, 곧 가장 깊게 훈련된 길이에서 여전히 눈에 보입니다: $n = 5$ 에서의 정확도는 깊이 1에서 2, 3으로 가면서 $0.64 \to 0.80 \to 0.81$ 로 올라가며, 이는 적어도 5포인트의 개선을 요구하는 assert들로 지켜지는 엄격한 상승입니다(397–401행). 지평 너머에서 그 꼬리들은 우연 수준 $0.167$ 에 대해 각각 $0.162$ , $0.157$ , $0.155$ 입니다: 여섯 갈래 우연이며, 번갈음 인공물도 없이 곧바른 붕괴입니다. 그리고 두 표의 어느 행에도 $n = 6$ 너머에 절벽이 있는 경우는 없습니다. 요약 줄은 이 장이 인용한 모든 숫자를 커밋합니다:

SUMMARY depth_ceiling: parity_cliffs=3/6/6 s3_cliffs=5/5/5 parity_tail=0.506/0.500/0.500 s3_n5=0.64/0.80/0.81 fd_gap=2.1e-11

이제 이 장에서 가장 중요한 문단인 읽기의 규율입니다. 이 장의 정리들은 하나의 함수 부류(function class)에 관한 진술입니다: 그것들은 어떤 고정 깊이 아키텍처든, 모든 가중치 설정에 걸쳐, 모든 입력 길이에서 표현할 수 있는 입력-출력 사상이 무엇인지를 한계 짓습니다. 위의 표들은 특정한 훈련 실행에 관한 진술입니다: 세 개의 시드, 두 개의 과제, 짧은 사례들로부터의 경사 하강법입니다. 이 두 종류의 진술은 여기서 같은 방향을 가리키며, 바로 그렇기 때문에 이 짝지음이 유익합니다. 하지만 어느 쪽도 다른 쪽을 함의하지 않습니다. 이 절벽들은 하한을 증명할 수 없습니다(두 과제 모두 TC⁰ 안에 있으며, 더 넓거나 더 잘 훈련된 고정 깊이 모델이라면 어떤 특정 절벽이든 더 바깥으로 밀어낼 수 있을 것입니다); 그리고 그 정리들은 절벽의 위치를 예측하지 않았습니다(회로 복잡도의 어떤 것도 16슬롯 패리티에서 깊이 1이 $n = 4$ 에서 실패한다고 말하지 않습니다). 이 장난감이 보여 주는 것은 그 정리들을 물리게 만드는 메커니즘입니다: 상수 개수의 결합 라운드는 실재하는 자원이고, 모델은 그것을 써 버리며, 사례들이 모델이 가진 것보다 더 많은 라운드를 요구할 때 성능은 완만하게 저하되지 않고 절벽에서 떨어집니다. 이 정리들이 보여 주는 것은, 그 장난감 너머, 함수족의 규모에서는 아무리 훈련해도 부족한 라운드를 사 올 수 없다는 것입니다. 이 두 과학을 분리해 두면 둘 다 유용합니다; 그것들을 뒤섞으면, 벤치마크가 개선되었다는 이유로 하한을 무시하거나, 하한이 존재한다는 이유로 벤치마크를 무시하게 될 것입니다.

빠져나가는 두 차선과 그 대가

이 장의 어떤 것도 고정 깊이 네트워크가 유계인 길이에서 어려운 과제를 근사할 수 없다고는 말하지 않으며, 그 탈출 경로는 정확히 공장 비유가 예견했던 그 두 가지입니다.

첫 번째 차선: 너비와 정밀도로 지불하기. 길이 $n$ 의 입력에 대한 모든 함수는 깊이 2, 크기가 $n$ 에 지수적인 회로로 계산할 수 있습니다(만족하는 입력마다 게이트 하나씩을 두고 그것들에 대해 논리합을 취하면 됩니다). 그러므로 너비가 길이에 따라 지수적으로 폭발하는 고정 깊이 네트워크족은 어떤 절벽이든 암기로 뛰어넘을 수 있습니다. 이는 지불이지 아키텍처가 아닙니다: AC⁰와 TC⁰의 다항 크기 조건이야말로 그것들을 실현 가능한(feasible) 병렬성의 모형으로 만들어 주는 것이며, 토큰 하나가 늘 때마다 하드웨어를 두 배로 늘리는 해법은 천장을 이긴 것이 아니라 실현 가능성을 포기한 것입니다. 이 차선이 중요한 이유는 그것이 벤치마크 주장을 가늠하는 잣대가 되기 때문입니다; 길이 16까지 풀어내는 고정 깊이 모델은 이 차선이 쓰는 방식으로 너비를 쓰고 있는 것일 수 있으며, 유일한 시험 방법은 $n$ 을 계속 키워 보는 것뿐입니다.

두 번째 차선: 디코딩으로 시간을 지불하기. 그 정리에서 가장 조용한 조항은 "중간 토큰이 없다면"이었습니다. 트랜스포머가 토큰을 생성해 되먹인다고 해 봅시다. 그러면 생성된 토큰 하나하나가 지금까지 생성된 모든 것을 입력에 포함하는 새로운 순전파가 되며, 이는 순차적 사슬, 곧 깊이가 시간으로 바뀐 것, 즉 공장이 제품을 라인 둘레로 다시 돌려보내는 것입니다. 이 모듈이 출력하는 사다리에는 이미 그 목적지가 담겨 있는데, 위에 인용한 커밋된 출력에서 그대로 옮기면: 사고 사슬이 없으면 오직 TC⁰뿐이고, 다항식 개수만큼 생성된 중간 단계가 있으면 정확히 P입니다. 다음 장은 이 장의 규율을 지키며 그 정리를 진술하고, 그 컴패니언 cot_steps.py는 이 모듈의 $S_3$ 과제 장치와 MLP 엔진을 변경 없이 그대로 임포트하여(depth_ceiling.py, 64–66행), 층 대신 단계를 씀으로써 위 표 안의 $S_3$ 절벽을 깨뜨립니다. 그 절벽에 매달린 이야기는 정밀합니다: 같은 과제, 같은 훈련 구간, 그리고 지평에서 떨어지지 않고 걸어 나가는 모델입니다.

미해결 부분

이론의 이상화와 실제 배포된 모델 사이의 간극은 실재하고, 양방향적이며, 열려 있습니다. 그 정리들은 로그 정밀도, 균일성, 그리고 깔끔한 어텐션 극한(포화된 평균화나 하드 argmax)을 가정합니다; 배포된 모델은 모든 것이 유한하고, 그 어느 극한도 아닌 학습된 어텐션 패턴을 가지며, 그 깔끔한 진술이 다루도록 확장되어야 할 위치 인코딩을 갖고, 그 정리들이 전혀 언급하지 않는 훈련 절차를 거칩니다. 그 간극 안에서, 경험적인 길이 일반화는 때로 이 천장을 무심코 읽었을 때 시사되는 비관보다 나은 성과를 내는데, 알맞은 스크래치패드 형식, 위치 구성, 커리큘럼이 특정 과제족에서 절벽을 인상적으로 멀리 밀어내기도 합니다. 그러나 때로는 그보다 못한 성과를 내기도 하는데, 함수 부류가 증명 가능하게 감당하는 길이에서조차 모델이 실패하기도 합니다. 이 장의 깊이-1 패리티 모델이, 충분한 너비의 은닉층 하나짜리 네트워크라면 $n \le 6$ 에서 완벽하게 표현할 수 있는 과제에서 자신의 훈련 구간 안쪽에서조차 실패했던 것과 꼭 같습니다. 이 두 가지 예측 실패는 같은 뿌리를 갖습니다: 표현력 이론은 어떤 해가 존재하는지를 한계 짓지만, 경사 하강법이 어떤 해를 찾아내는지에 대해서는 아무 말도 하지 않습니다. 훈련된-해 부류, 즉 현실적인 데이터로부터 최적화가 실제로 도달하는 함수 부류의 부분집합을 특징짓고, 따라서 배포 가능한 규모에서 이 천장이 실질적으로 어떤 모델들을 옭아매는지를 미리 말하는 것은 열린 문제이며, 오늘날 회로 복잡도와 학습 동역학은 어휘는 공유하지만 정리는 전혀 공유하지 않는 서로 다른 과학입니다.

왜 중요한가

이 장은 이 시리즈의 두 문화가 신경 쪽의 안마당에서 마주치는 자리입니다. 1권과 2권은 그 정확성 증명이 도출 깊이에 대한 귀납법인 추론기들을 지었습니다: 폐쇄가 존재하는 것은 파동 $k+1$ 이 파동 $k$ 를 확장하기 때문입니다. 3권은 메시지 전달에 대한 천장으로 끝을 맺었습니다; 이 장은 이제 대부분의 기계 추론을 중개하는 그 아키텍처에 대해 같은 모양의 결과를 내놓으며, 어떤 벤치마크를 돌리기도 전에 다음을 설명해 줍니다: 짧은 논리적 추론을 완벽하게 해내는 고정 깊이 모델이 왜 깊이에서 떨어져 나가는지, 매개변수 개수가 왜 그것을 구하지 못하는지, 그리고 그 실패가 왜 완만한 경사가 아니라 절벽으로 찾아오는지 말입니다. 신경-기호 프로젝트에게 이 정리 계열은 거의 하나의 설계 지침서에 가깝습니다: 여러분의 시스템이 수행해야 할 추론이 규모에서 P-완전이라면, 깊이는 층의 스택이 아닌 다른 어딘가에 살아야 합니다. 도구로 호출되는 기호 엔진 안에, 네트워크를 둘러싼 고정점 루프 안에(앞 장의 절단된 커널이 바로 그것이며, 이는 또한 SATORI의 고정- $L$ 형태이기도 합니다), 또는 다음 장이 분석할 디코딩 루프 안에 말입니다. 그리고 독자 자신의 연구를 위해서는, 이 장의 마지막 규율이야말로 전이 가능한 것입니다: "그 부류는 할 수 없다"와 "이번 실행은 하지 못했다"를 여러분의 노트에서 서로 다른 칸에 적어 두십시오. 이 둘을 어느 방향으로든 흐려 버리는 논문이야말로 $n$ 을 바꾸면 그 주장이 살아남지 못하는 논문이기 때문입니다.

핵심 용어

회로족/크기/깊이: 입력 길이마다 하나씩인 불 회로 $C_n$ ; 게이트 개수와 입력에서 출력까지 가장 긴 경로; 깊이는 앞 장의 의존 사슬 길이에 대응하는 회로판 개념입니다.
AC⁰: 무제한 팬인을 갖는 AND/OR와 NOT 게이트로 이루어진, 상수 깊이·다항 크기 회로들의 클래스; 하드 유일 어텐션이 사는 곳; 증명 가능하게 PARITY를 계산할 수 없습니다.
문턱 게이트/MAJORITY: 입력 중 적어도 $\theta$ 개가 1일 때 발화하는 게이트; MAJORITY는 $\theta = \lceil m/2 \rceil$ 인 경우입니다; 셈을 하는 게이트입니다.
TC⁰: AC⁰에 문턱 게이트를 더한 것; 로그 정밀도 고정 깊이 트랜스포머를 담는 클래스; 정확히- $k$ 구성을 통해 PARITY를 포함합니다.
균일성: 하나의 단순한 알고리즘이 회로족 전체를 뽑아낸다는 요구 조건으로, 그 족을 하드코딩된 답들의 무한한 표가 아니라 하나의 유한한 조리법으로 만들어 줍니다.
로그 정밀도: 순전파 안의 모든 값이 입력 길이 $n$ 에서 $O(\log n)$ 비트를 지니며, 따라서 다항식 개수만큼의 가능성 안에서 움직입니다.
천장 정리: 중간 디코딩이 없는 고정 깊이·다항 크기·로그 정밀도 트랜스포머는, 어떤 가중치 설정에서든, 로그공간-균일 TC⁰ 언어들만을 인식합니다.
절벽 위치: $n$ 까지 모든 길이에서 정확도가 완벽-우연 중점 이상을 유지하는 가장 큰 $n$ ; 이 모듈의 커밋된 절벽은 깊이 1/2/3에 대해 3/6/6(패리티)과 5/5/5( $S_3$ )입니다.
함수 부류 대 훈련 실행: 아키텍처가 표현할 수 있는 것(정리, 모든 가중치, 모든 길이)과 하나의 최적화가 찾아낸 것(실험, 하나의 시드, 하나의 구간)을 분리하는 규율; 장난감은 첫 번째를 예증할 뿐이며, 두 번째만을 측정할 수 있습니다.

이 장이 이끄는 곳

천장 정리는 문 하나를 명시적으로 열어 두었습니다: 그것은 단 한 번의 순전파로 답하는 트랜스포머를 한계 짓지만, 먼저 스스로에게 말을 거는 트랜스포머에 대해서는 아무 말도 하지 않습니다. 다음 장 사고 사슬: 디코딩 시점에 P를 회복하기는 같은 규율을 지키며 그 문을 통과합니다. 그 장은 사다리 정리(로그만큼의 생성 단계는 거의 사 주지 못하지만, 다항식만큼의 단계는 정확히 P에 도달한다는 것)를 진술하며, 그 컴패니언 cot_steps.py는 이 장의 반복된 $S_3$ 과제를 디코딩 루프로 다시 실행해 그 절벽이 사라지는 것을 지켜보는데, 이제 그 대가는 트릴레마가 유일하게 남아 있다고 말했던 그 화폐, 곧 시간으로 매겨집니다.

컴패니언 코드: examples/frontier/depth_ceiling.py는 두 과제족을 모두 생성하고, 중심 유한차분과 대조해 인증된 손으로 유도한 역전파로 깊이-1/2/3 MLP들을 훈련시키며(커밋된 오차 2.1e-11), 정확도-대-길이 표를 출력하고, 이 장의 정성적 주장들을 단언합니다: 훈련 구간 완전 습득, 지평 너머의 우연 수준 꼬리, 깊이에 따른 절벽 단조성, 패리티 격차(깊이 1은 n = 4 이하, 곧 구간 안쪽에서 절벽을 맞고, 깊이 2는 지평 n = 6에 도달), 그리고 n = 5에서 깊이 1보다 적어도 5포인트 높은 S₃ 정확도(커밋된 값은 0.64 → 0.80 → 0.81)입니다. 이 장의 모든 숫자를 재현하려면 python3 examples/frontier/depth_ceiling.py를 실행하십시오; 두 번 실행해도 바이트 단위로 동일한 출력이 나옵니다.

이 장에서 다루는 내용​

기계의 형태: 깊이 없는 너비​

문턱 회로: 상수 깊이의 화폐​

규율을 지켜 수입한 천장 정리​

어텐션 사다리: 아키텍처의 선택이 곧 복잡도의 선택​

천장이 배제하는 것: 시리즈 자신의 대상들을 정리하기​

장난감이 정직하게 보여 줄 수 있는 것​

커밋된 절벽들, 신중하게 읽기​

빠져나가는 두 차선과 그 대가​

미해결 부분​

왜 중요한가​

핵심 용어​

이 장이 이끄는 곳​