사고 사슬: 디코딩 시점에 P를 회복하기

📍 현재 위치: V부 · 신경 깊이: 사고 사슬과 강화학습 — 13장. 트랜스포머 깊이의 천장은 단일 순전파(forward pass)에 균일 TC⁰이라는 값을 매기고, 그 정리의 가장 조용한 절, 즉 "중간 토큰이 생성되어 되먹임되지 않는다"는 조건 속에 출구 하나를 남겨 두었습니다. 이 장은 그 문을 열고, 그 문을 통과해 들어오는 것이 무엇인지 측정합니다.

사고 사슬(chain of thought, CoT)은 보통 프롬프트 공학(prompt engineering) 아래 분류됩니다: 프롬프트에 단계별로 생각하라는 넛지를 덧붙이면 벤치마크 점수가 올라간다는 식으로요. 이 장은 이론이 그것이 속한다고 말하는 곳, 즉 아키텍처 아래에 그것을 분류합니다. 중간 토큰을 디코딩하고 그것에 주의를 기울이는 트랜스포머는, 한 번의 패스로 답하는 같은 트랜스포머와는 다른 기계입니다. 생성되는 토큰 하나하나가 고정된 층 스택 혼자서는 수행할 수 없었던 순차적 단계를 하나씩 더하기 때문입니다. 스텝과 능력 사이의 교환 비율은 이제 하나의 정리 계열(theorem family)이 되었습니다: 디코딩 예산이 복잡도 클래스의 사다리를 오르며, 다항 예산에서는 그 기계가 정확히 P를 특징짓는데, 이는 추측된 위계가 무너지지 않는 한(TC⁰ = P) 앞 장이 어떤 단일 패스도 닿지 못하는 곳에 두었던 바로 그 클래스입니다. 동반 모듈 cot_steps.py는 이 권의 규율에 따라, 앞 장의 절벽들과 같은 과제와 같은 훈련 대역에서 그 메커니즘을 시연합니다: 단일 합성 연산만으로 훈련된 깊이-1 스텝 네트워크를 평가 시점에 언롤링하면, 고정-깊이 모델의 절벽에서 걸려 넘어지지 않고 그대로 걸어 나갑니다. 그런 다음 이 장은 회복된 깊이가 치르게 만드는 두 가지 청구서, 즉 순차 시간과 취약성을 지불하는데, 둘 다 커밋된 출력으로 인쇄되어 있습니다. 두 번째 청구서가 다음 장 검증기(verifier)들의 첫 논거이기 때문입니다.

쉽게 말하면

여섯 자리 숫자 두 개를 순전히 머릿속으로 곱하는 것과, 연필과 종이를 써서 곱하는 것을 상상해 보십시오. 두 경우 모두 머리는 같은 머리입니다; 종이가 어떤 하나의 정신적 단계를 더 똑똑하게 만들어 주지는 않습니다. 종이가 바꾸는 것은 여러분이 사슬처럼 이어 갈 수 있는 단계의 개수입니다: 각 중간 결과를 적어 두고, 그것을 다시 읽고, 문제가 필요로 하는 만큼 다음의 작은 단계를 밟습니다. 그것이 바로 사고 사슬(chain of thought)입니다. 모델이 머리이고, 디코딩된 토큰이 종이이며, 적고 다시 읽는 그 루프가 얕은 사고자를 긴 계산으로 바꾸어 놓는 것입니다. 다만 그 종이는 두 번 값을 매깁니다. 적어 놓은 한 줄 한 줄마다 시간이 들며, 아무리 많은 손을 더해도 그 시간은 병렬로 나누어 없앨 수 없습니다. 그리고 잘못 옮겨 적은 숫자 하나는 그 뒤의 모든 줄을 소리 없이 오염시킵니다.

이 장에서 다루는 내용

• 루프, 기계적으로 해독하기: 자기회귀적 디코딩(autoregressive decoding)은 출력을 다시 입력으로 되먹임하므로, 언롤링된 계산 그래프는 층수 곱하기 생성된 토큰 수에 비례하는 깊이를 갖습니다; 앞 장의 천장 정리들은 디코딩이 없는 체제만을 한계 짓습니다.
• 사다리, 이 시리즈의 규율로 서술하기: 각 디코딩-스텝 예산을 하나의 복잡도 클래스에 대응시키고, 모든 기호를 해독하며, 출처를 밝히고, 이 장의 실험이 존재하는 이유인 단서까지 포함해 하중을 받치는 단서들을 그대로 인용합니다: 표현력은 학습 가능성이 아니라는 것입니다.
• 격리 실험(isolation experiment): 단일 연산(상태, 토큰 → 다음 상태)만으로 훈련되고 결코 긴 인스턴스를 본 적 없는 스텝 모델을, 평가 시점에 n번 언롤링하여, 깊이가 오직 한 곳, 즉 루프에서만 나올 수 있게 만듭니다.
• 커밋된 정면 대결: n = 2부터 32까지의 길이에 대한 정확도를, 언롤링된 스텝 모델과 앞 장의 최선의 고정-깊이 모델을 나란히 놓고, 그 읽기를 지켜 주는 assert들과 함께 다룹니다.
• 순차 청구서: 정확히 n으로 나오는 장부 열, 루프가 왜 병렬 할인을 전혀 허용하지 않는지, 그리고 그것이 앞 장들의 병렬 차선을 이미 갖춘 배포 환경에 무엇을 뜻하는지를 다룹니다.
• 취약성 전시: 위치 k에 주입된 오염된 중간 상태 하나, 모든 k에서 최종 과제 정확도 0.000을 보여 주는 커밋된 표, 그리고 이 과제에서 잘못된 사고가 결코 치유되지 않는 이유에 대한 두 줄짜리 군론(group theory) 증명을 다룹니다.
• 스크래치패드에서 프론티어까지: 이론이 그 값을 매기기도 전에 루프를 찾아낸 경험적 계보, 그리고 사슬을 이끌어 내는 것이 그 단계들을 인증하는 것은 아니라는 정직한 지적을 다룹니다.

문: 디코딩은 루프이고, 루프는 곧 깊이다

어떤 정리보다 먼저, 메커니즘부터 봅니다. 이것이 순전히 기계적인 사실이기 때문입니다. 트랜스포머는 텍스트를 자기회귀적(autoregressive)으로 생성합니다: 지금까지 적힌 모든 것에 대해 완전한 순전파(forward pass)를 한 번 돌리고, 토큰 하나를 내놓은 다음, 그 토큰을 입력에 이어 붙이고, 다시 돌립니다. $L$을 층의 개수(앞 장에서와 마찬가지로 하나의 아키텍처 상수)라 쓰고, $T$를 모델이 최종 답을 내놓기 전에 생성하는 토큰의 개수라 씁시다. 단일 순전파는 $L$에 비례하는 깊이의 계산입니다: 각 층은 유한하게 많은 수의 의존적 단계를 수행하므로, 각 단계가 그 앞 단계의 출력을 필요로 하는 연산들의 사슬 가운데 가장 긴 것은 어떤 상수 $c$(층당 단계 수를 세는 값)에 대해 길이 $cL$을 가집니다. 이제 생성 과정을 언롤링(unrolling)해 봅시다. $t$번째 패스는 $t-1$번째 패스가 내놓은 토큰을 읽는데, 그 토큰은 패스 $t-1$이 출력 층까지 끝까지 실행되어 표본을 뽑기 전까지는 존재하지 않습니다. 따라서 $T$개의 패스는 전순서(totally ordered)를 이루고 그 어느 둘도 겹칠 수 없으며, 언롤링된 계산 그래프 안에서 가장 긴 의존적 사슬은 그 패스들 전부를 순서대로 통과하는 사슬입니다: 패스 $T$개 곱하기 패스당 단계 $cL$개, 즉 깊이 $\Theta(L \cdot T)$이며, 여기서 $\Theta$는 상수배로 위아래에서 갇혀 있다는 뜻이고, 아래에서 쓰이는 그 한쪽짜리 사촌 $O$는 상수배로 위에서만 갇혀 있다는 뜻입니다. $L$이 고정되어 있으므로, 전체 계산의 깊이는 $T$에 대해 선형으로 자랍니다. 생성된 토큰의 개수는 디코딩 시점에 지출되는 깊이 예산이며, 이는 아키텍처의 고정된 층 개수가 결코 내주지 않았던 것입니다.

이 하나의 관찰이 앞 장 전체를 재편성합니다. 그곳의 천장 정리는 "직접 답을 내놓는 단일 순전파로 실행되는" 트랜스포머를 한계 지었으며, 그 절의 단어 하나하나가 하중을 받치고 있었습니다: TC⁰ 한계(TC⁰은 앞 장의 상수-깊이 문턱 회로(threshold circuit) 클래스입니다)는 $T = 0$인 기계에 대한 한계입니다 [1]. 중간 토큰을 적고 그것을 다시 읽어 들이는 모델은 $T$번 루프를 도는 얕은 스택이며, 이는 곧 추론 시점에 조립되는 깊은 계산이라는 뜻이고, 어떤 고정-깊이 회로 논증도 그것을 전체로서 다루지 못합니다. 이 루프는 또한 중간 상태가 어디에 사는지도 설명해 줍니다. 고정-깊이 패스는 모든 부분 결과를 자신의 활성값(activation) 안에 담아 날라야 하는데, 로그-정밀도 이상화(log-precision idealization)는 일부러 그것을 굶주리게 만듭니다; 디코딩 루프는 그 상태를 토큰으로, 즉 개수에 제한이 없는 이산 기호(discrete symbol)로 외부화합니다. 이는 정확히 1권의 전방향 연쇄기(forward chainer)가 그 상태를 자라나는 사실 집합으로 외부화했던 것과 같습니다. 남은 일은 그 교환의 값을 매기는 것이며, 그것이 바로 사다리입니다.

n번 루프를 도는 얕은 스택은 하나의 깊은 계산입니다: 디코딩 예산은 복잡도 사다리를 오르며, n = 5에서 고정-깊이 모델을 무너뜨렸던 바로 그 과제가, 깊이가 루프 안에 살 때는 n = 32까지 1.000을 유지합니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

사다리: 스텝 예산이 사는 것

이 정리 계열은 앞 장이 층에 값을 매겼던 방식 그대로 디코딩 스텝에 값을 매깁니다. 이전과 같은 이상화된 기계, 즉 상수 개의 층, 다항식으로 유계인 크기, 로그-정밀도 산술을 갖는 트랜스포머를 고정해 두되, 이제는 길이 $n$의 입력에 대해 $t(n)$번의 디코딩 스텝(decode step)을 허용합니다: 답을 확정하기 전에 $t(n)$개의 중간 토큰을 생성할 수 있으며, 그 각각은 입력으로 되먹임됩니다. 여기서 $n$은 토큰 단위의 입력 길이이고, $t(\cdot)$는 미리 고정된 예산 함수, 즉 사다리의 유일한 다이얼입니다. 그 결과들은, 모든 단이 출처를 밝힌 채 다음과 같이 서술됩니다 [1]:

디코딩-스텝 예산 $t(n)$	기계의 능력	주장의 방향
$0$ (단일 패스)	균일 TC⁰뿐	상계(upper bound); 앞 장의 천장
$O(1)$ (상수)	여전히 균일 TC⁰	상계: 유한하게 많은 추가 패스는 상수 깊이로 쌓일 뿐
$O(\log n)$	$\mathsf{L}$(로그공간) 안에 포함됨	상계: 적은 스텝은 적은 것만 사들임
$\Theta(n)$ (선형)	모든 정규 언어(regular language)에 도달 가능	하계(lower bound): $n$번의 스텝은 임의의 유한 오토마타를 실행함
$\mathrm{poly}(n)$	정확히 P	상계와 하계가 만남: 그 특징짓기(characterization)

각 행을 해독해 봅시다. 균일 TC⁰은 앞 장의 상수-깊이 문턱 회로(threshold-circuit) 클래스입니다; 상수 개의 추가 패스는 언롤링된 깊이를 상수배로 늘릴 뿐이고, 상수 곱하기 상수는 상수이므로, 천장은 움직이지 않습니다. $\mathsf{L}$, 즉 로그공간(logspace)은 입력을 읽기 전용으로 읽고 오직 $O(\log n)$ 비트의 작업 메모리만을 쓰는 알고리즘으로 판정 가능한 문제들의 클래스입니다; 그 상계는, 고정된 어휘에서 뽑히므로 $O(1)$개의 기호만큼의 상태 값을 갖는(로그-정밀도 내부 값들은 스텝마다 $O(\log n)$ 비트를 기여합니다) 로그 개수의 토큰 예산이라면, 로그공간 시뮬레이터로 재현될 수 있으므로, 그 기계는 여전히 P보다 훨씬 아래에 있다고 여겨지는 클래스 안에 머문다는 것을 말해 줍니다. 정규 언어(regular language)는 한 번에 기호 하나씩을 읽는, 고정된 유한 상태 집합을 가진 기계인 결정론적 유한 오토마타(deterministic finite automaton, DFA)로 인식되는 언어들입니다; 그 하계는 구성적입니다. 트랜스포머는 디코딩되는 토큰마다 자신의 현재 오토마타 상태를 내놓고 전이 함수를 한 번의 얕은 패스로 적용할 수 있는데, 이것이 정확히 이 장의 실험이 취하는 모양입니다. 그리고 맨 위의 단이 바로 이 장의 제목입니다: 다항 예산이 주어지면 그 이상화된 기계는 정확히 다항-시간 문제들의 클래스인 P를 판정합니다. 각 패스가 다항 크기의 작업이고 패스가 다항 개수만큼 있으므로 상계이며, 다항 개수의 디코딩된 토큰이 다항-시간 튜링 기계의 테이프를 한 단계씩 문맥(context) 안으로 옮겨 적을 수 있으므로 하계입니다 [1]. 1권의 폐쇄 파동들, 2권의 EL 완결, 그리고 P가 자신의 병렬 하위 클래스인 NC로 무너지지 않는 한 앞 장이 어떤 고정 스택보다도 위에 놓았던 P-완전(P-complete) 폐쇄들, 이 모든 것이 기계가 다항 개수의 토큰만큼 소리 내어 생각하도록 허락받는다면 다시 손이 닿는 곳으로 돌아옵니다.

두 번째 결과는 실무가 신경 쓰는 단들에서 그 사다리를 더 날카롭게 다듬습니다. 둘 다 소수를 법으로 하는 유한체(finite field) 위에서 정의된 산술식 계산과 선형 방정식 풀이, 그리고 문맥 자유 문법(context-free grammar) 소속 검사(동적 계획법(dynamic programming)으로 풀리는 문제)에 대해서는, 유계-깊이 로그-정밀도 트랜스포머가 TC⁰이 NC¹과 같지 않은 한 단일 패스로는 답을 내놓을 수 없습니다. 여기서 NC¹은 깊이가 $\log n$처럼 자라도 되는, 유계 팬인(fan-in) 게이트로 이루어진 다항 크기 회로들이 푸는 문제들의 클래스, 즉 앞 장 사다리의 다음 단이며, TC⁰이 NC¹에 포함된다는 관계는 엄격하다고 추측될 뿐 증명된 적은 없습니다. 그런데도 고정 크기의 트랜스포머가 자신이 디코딩하는 텍스트 안에서 동적 계획법 표를 칸칸이 채워 가며 다항-길이의 도출 과정을 써내려간다면 바로 그 문제들을 풀며, 같은 구성적 정리는 최장 증가 부분 수열(longest increasing subsequence)과 편집 거리(edit distance) 같은 고전적인 동적 계획법 점화식들도 다룹니다 [2]. 이 분리는 정확히 앞 장이 그러한 분리들이 놓여 있다고 말했던 곳에서 조건부이며, 구성적인 절반은 무조건적입니다: 그 가중치는 실제로 존재하고, 그 사슬이 곧 계산입니다.

이 사다리에는 세 가지 단서가 따라붙으며, 이 시리즈의 규칙은 그것을 각주가 아니라 정리가 서술되는 바로 그 자리에서 서술하는 것입니다. 첫째, 다항-스텝 한정어(poly-step qualifier)입니다: "정확히 P"는 다항 예산에 대한 진술이며, 상수에 대해서는 아무것도 주장되지 않고, 예산 정리는 어떤 문제가 몇 번의 스텝을 필요로 하는지는 말해 주지 않습니다(미해결 부분에서 이 문제로 돌아옵니다). 둘째, 이상화(idealization)입니다: 이 결과들은 로그-정밀도 산술과 이상화된 어텐션(attention)을 가정하는데, 이는 천장 정리가 필요로 했던 것과 같은 가정이므로, 이들은 실제로 배포되는 대상이 아니라 그것의 한 추상화를 한계 짓습니다; 그 증명들은 진정으로 이 권의 범위를 넘어서며, 동반 코드가 실행하는 그 무엇도 어떤 단을 증명하는 것으로 읽혀서는 안 됩니다. 셋째, 그리고 아래의 모든 것에 하중을 지우는 단서입니다: 표현력은 학습 가능성이 아닙니다(expressiveness is not learnability). 모든 단은 가중치가 존재한다고만 주장할 뿐입니다; 어떤 단도 경사 하강법(gradient descent)이 어떤 특정 지도(supervision)로부터 그것을 찾아낸다고는 말하지 않습니다. 앞 장은 그 간극을 한쪽에서 지켜보았습니다. 어떤 모델이 자신의 함수 클래스가 증명 가능하게 감당하는 대역 안에서 실패하는 모습으로요. 이 장의 실험은 그 간극의 반대편에 서도록 설계되어 있습니다: 스텝 함수가 학습 가능하다는 것이 입증될 수 있는 설정을 골라서, 루프가, 오직 루프만이 그 깊이를 공급한다는 것을 보이는 것입니다.

단일 연산을 배우고 n번 언롤링하기: 격리 실험

동반 코드의 설계는 장난감 규모에서 세 번째 단서에 답하며, 그 논리는 코드보다 먼저 서술될 가치가 있습니다. 만약 어떤 모델이 긴 사슬 전체에 대해 종단간(end-to-end)으로 훈련된다면, 그 성공은 두 가지 자원, 즉 가중치가 무엇을 배웠는가와 루프가 무엇을 기여하는가를 뒤섞어 버릴 것입니다. 그래서 이 모듈은 스텝 모델(step model)을 단일 연산만으로 훈련시키며, 한 번의 연산보다 긴 인스턴스는 결코 보여 주지 않고, 모든 깊이를 언롤링을 통해 평가 시점에 만들어 냅니다. 이 과제는 앞 장의 반복 $S_3$ 합성 과제 그대로이며($S_3$는 세 글자의 순열 $3! = 3 \cdot 2 \cdot 1 = 6$개 전부로 이루어진 군이므로, 상태는 언제나 여섯 원소 가운데 하나입니다), 그 생성원(generator)과 레이블은 다시 타이핑하지 않고 depth_ceiling.py에서 가져옵니다(cot_steps.py, 67–76행): 한 인스턴스는 세 글자에 대한 항등원이 아닌 순열 $n$개, $g_1, \ldots, g_n$의 수열이며, 답은 왼쪽 폴드(fold) $p_0 = e$, $p_j = p_{j-1} \circ g_j$ 아래에서의 곱 $p_n$입니다. 여기서 $e$는 항등 순열이고 $\circ$는 오른쪽 인자가 먼저 작용하는 합성입니다. 이 폴드가 깊이를 실어 나르는 매개체입니다: 이 방식으로 $p_n$을 계산하는 것은 서로 의존적인 $n$번의 곱셈입니다.

그 지도(supervision)는 스크래치패드(scratchpad) 방식입니다. 정확히 말하면, 훈련 신호가 최종 답이 아니라 중간 계산의 흔적(trace)이라는 뜻입니다 [3]: 앞 장의 짧은 대역($n = 2$부터 $6$까지)에서 나온 모든 훈련 궤적이 각각의 개별 스텝으로 펼쳐지고, 모델은 오직 (현재 상태, 다음 토큰) → 다음 상태 형태의 쌍만을 봅니다(cot_steps.py, 108–130행):

def harvest_steps(rng: np.random.Generator) -> tuple[np.ndarray, np.ndarray]:
    """Single-step supervision from the SAME short band depth_ceiling trains
    on (n = 2..6), decomposed scratchpad-style (Nye et al. 2021): each
    trajectory p_0 = e, p_j = p_{j-1} ∘ g_j is unfolded into its steps

        x = [one-hot(p_{j-1}) ; one-hot(g_j)]  →  y = p_j ,

    so the net only ever sees ONE composition at a time.  Returns (X, y)
    with X of shape (Σ_n STEP_PER_LEN·n, 12) and y the new-state ids."""
    Xs, ys = [], []
    for n in TRAIN_LENGTHS:
        elems = sample_s3(n, STEP_PER_LEN, rng)
        # p_0 = e (the identity, element id 0) for every trajectory.
        state = np.zeros(len(elems), dtype=np.int64)
        for j in range(n):
            g = elems[:, j]
            # p_j = p_{j-1} ∘ g_j  via the Cayley table.
            nxt = MUL[state, g]
            Xs.append(np.concatenate([one_hot(state, 6), one_hot(g, 6)],
                                     axis=1))
            ys.append(nxt)
            state = nxt
    return np.vstack(Xs), np.concatenate(ys)

스텝 모델 자체는 이 권에서 일부러 가장 약한 기계로 만들어졌습니다: tanh(쌍곡탄젠트 활성화 함수)를 쓰는 폭 24짜리 은닉층을 하나만 가진 다층 퍼셉트론(multilayer perceptron, MLP)으로, 입력 차원은 12(상태와 토큰 각각에 대한 6-방향 원-핫 벡터 두 개인데, 원-핫(one-hot) 벡터란 인코딩된 id의 위치에서만 1이고 나머지는 모두 0인 벡터입니다), 출력 차원은 6이며, 앞 장의 엔진, 즉 그곳에서 중심 유한 차분(central finite difference)에 맞대어 인증받았던 바로 그 손으로 유도한 역전파(backpropagation)로, 확률적 경사 하강법(stochastic gradient descent, SGD)과 모멘텀(momentum)과 고정된 시드를 써서 훈련됩니다(cot_steps.py, 133–141행; 엔진은 depth_ceiling.py, 227–248행). 깊이 1이 바로 핵심입니다. 이 네트워크가 한 번의 패스로 계산할 수 있는 것은 무엇이든 유계이고 상수-깊이인 함수입니다; 이것을 언롤링해서 깊이-$n$ 문제를 푼다면, 그 깊이는 입증 가능하게 루프에서 온 것입니다.

스텝 모델이 배워야 하는 것에 대해서는 깔끔한 기호적 해석도 있으며, 이는 이 실험을 사다리의 선형 단과 이어 줍니다. 곱이 주어진 원소와 같아지는 $S_3$ 위의 단어들의 집합은 하나의 정규 언어(regular language)입니다: 상태가 군의 원소들이고 전이 함수가 $\delta(p, g) = p \circ g$인 6-상태 DFA가 그것을 판정하며, 그 전이 함수가 정확히 스텝 모델이 훈련받는 그 단일 연산입니다. 스텝 모델을 언롤링하는 것은 곧 그 오토마타를 실행하는 것, 즉 입력 기호 하나당 디코딩된 토큰 하나를 실행하는 것이며, 이는 축소판 규모에서 사다리의 $\Theta(n)$ 단이 갖는 구성적 내용입니다 [1]. 그 오토마타가 유한하므로, 여기서는 설계상 학습 가능성이 문제가 되지 않습니다: 이 스텝 함수는 정확히 30개의 도달 가능한 입력 쌍(6개의 상태 곱하기 항등원이 아닌 5개의 토큰)을 가지며, 이 모듈은 학습된 함수를 그 30개 쌍 전부에 대해 실제 케일리 표(Cayley table), 즉 모든 상태 $p$와 토큰 $g$에 대해 항목 $p \circ g$를 하나씩 담은 그 군의 완전한 곱셈표와 맞대어 검사합니다(cot_steps.py, 144–153행). 그 커밋된 결과는 어떤 언롤링이든 의미를 갖는 것으로 허락되기 전에 먼저 인쇄됩니다:

[2] the step model — depth-bounded per step, trained on steps only
    architecture: 12 → 24 (tanh) → 6; ONE hidden layer (depth 1)
    supervision : 10000 single steps (p_(j-1), g_j) → p_j, harvested from
                  trajectories of the SAME short band n = 2..6 (scratchpad-style)
    learned transition table vs ground-truth Cayley table: 1.000 on all 30
    reachable (state, non-identity token) pairs — the automaton, learned

이 하니스(harness)는 그 줄을 하나의 전제 조건으로 격상시킵니다: assert table_acc == 1.0(cot_steps.py, 249–251행). 언롤링 자체가 이 장 전체의 메커니즘입니다(cot_steps.py, 158–184행; 아래 발췌는 오염 인자들을 생략하며, 이는 취약성 절로 미루어집니다):

    count, n = elems.shape
    state = np.zeros(count, dtype=np.int64)
    steps_used = 0
    for j in range(1, n + 1):
        X = np.concatenate([one_hot(state, 6), one_hot(elems[:, j - 1], 6)],
                           axis=1)
        state = forward(params, X)[-1].argmax(axis=1)
        steps_used += 1

argmax 줄을 디코딩 스텝으로 읽으십시오. 네트워크의 연속적인 로짓(logit), 즉 클래스마다 하나씩 나오는 가공되지 않은 실수 출력 점수가 하나의 이산적인 클래스, 즉 새 상태로 뭉개지고, 그 뒤에 있는 활성값이 아니라 바로 그 기호가 다음 패스를 위한 원-핫 입력으로 다시 인코딩됩니다. 이것이 사고 사슬이라는 읽기를 문자 그대로 만든 것입니다: 중간 결과가 토큰으로 적히고 다시 읽히는데, 정확히 스크래치패드 항목 하나이며, 패스와 패스 사이를 건너가는 것은 그 밖에 아무것도 없습니다. 상태는 네트워크가 아니라 종이 위에 삽니다.

정면 대결: 루프가 깊이를 나른다

상대는 이 과제에서 앞 장의 가장 강력한 고정-깊이 모델, 즉 깊이-3 MLP이며, 동일한 프로토콜(같은 생성원 시드, 같은 하이퍼파라미터, 같은 훈련 대역 $n = 2$부터 $6$까지; cot_steps.py, 189–198행)로 다시 훈련됩니다. 따라서 이 비교에서 지는 모델은 허수아비가 아니라, 커밋된 절벽 표들 뒤에 있는 바로 그 모델입니다. 두 경쟁자 모두 공유된 새 인스턴스, 즉 하나의 시드가 고정된 스트림에서 뽑힌 길이당 400개씩의 인스턴스에 대해 평가됩니다(cot_steps.py, 253–265행). 커밋된 표가 이 장의 척추입니다:

[3] head-to-head on shared fresh instances, n = 2..32 (400 per length)
    fixed depth-3 = depth_ceiling's best S_3 model, retrained on its exact
    protocol; '—' marks lengths its 16-slot input window cannot ingest
        n   fixed depth-3   unrolled step   serial rounds (fixed/step)
        2       1.000           1.000            3 /  2
        3       1.000           1.000            3 /  3
        4       0.990           1.000            3 /  4
        5       0.777           1.000            3 /  5   ← fixed-depth cliff
        6       0.485           1.000            3 /  6   ← training horizon
        7       0.085           1.000            3 /  7
        8       0.133           1.000            3 /  8
        9       0.175           1.000            3 /  9
       10       0.177           1.000            3 / 10
       11       0.165           1.000            3 / 11
       12       0.165           1.000            3 / 12
       13       0.152           1.000            3 / 13
       14       0.177           1.000            3 / 14
       15       0.175           1.000            3 / 15
       16       0.185           1.000            3 / 16
       17         —             1.000            3 / 17   ← past the fixed net's input window
       18         —             1.000            3 / 18

이 행들은 $n = 32$까지 변함없이 이어집니다: 언롤링된 스텝 모델은 모든 길이에서 1.000을 기록하는 반면, 고정 모델은 아예 열이 없는데, 16개 원소보다 긴 인스턴스는 그 입력 인코딩에 들어맞지 않기 때문입니다. 고정 모델의 행들은 새 인스턴스 위에서 앞 장의 이야기를 그대로 재현합니다: $n = 4$까지의 숙달, $n = 5$에서의 절벽, 그리고 6분의 1 확률 $1/6 \approx 0.167$에 대비되는 0.159의 꼬리 정확도($n = 7$부터 $16$까지의 평균 정확도)입니다. 하니스는 이 모든 것을 산문이 아니라 코드로 지킵니다: 고정 모델은 $n = 2$에서 강해야 하고, 훈련 지평(training horizon) 즈음이나 그 이전에 절벽에 부딪혀야 하고, 그 너머에서는 확률 수준으로 무너져야 하며, 그런 다음 이 장의 논지인 두 가지 주장이 이어집니다(cot_steps.py, 278–283행):

    min_step = min(step_acc.values())
    assert min_step >= 0.95, \
        f"unrolled step model fell below 0.95 (min {min_step:.3f})"
    for n in range(TRAIN_MAX + 2, SLOTS + 1):  # n = 8..16: horizon+2 .. window end
        assert step_acc[n] - fixed_acc[n] >= 0.5, \
            f"step model does not dominate the fixed net at n={n}"

그 계약은 길이 2부터 32까지 모든 곳에서의 0.95 바닥과, 훈련 지평에서 둘을 지난 지점부터 두 모델 모두 측정 가능한 모든 길이($n = 8$부터 $16$까지)에서의 최소 0.5 우위 마진입니다; 커밋된 실행은 둘 다 여유 있게 통과하며, 요약 줄에는 step_min_acc=1.000이라고 나옵니다. 이 표가 그럴 자격이 있으므로 한 문단만 더 읽어 봅시다. 고정 모델은 전체 $n$-겹 합성을 단 세 번의 결합 라운드 안에 표현해야 했는데, 이는 필요한 깊이가 어떤 상수도 넘어 자라나는, 전체 입력에 대한 함수입니다; 짧은 인스턴스로부터의 경사 하강법은 짧은 대역에 대한 해를 찾았을 뿐 그 너머에 대해서는 아무것도 찾지 못했으며, 이는 정확히 앞 장이 진단했던 그 메커니즘입니다. 스텝 모델은 그런 함수를 요구받은 적이 결코 없습니다. 그것의 각 패스는 유계 깊이, 고정 크기의 문제, 즉 케일리 표 조회 하나만을 풀며, 이는 그 훈련 분포가 남김없이 덮어 두었던 것(도달 가능한 30개 쌍 전부, 정확하게 학습됨)이므로, 인스턴스가 아무리 길어져도 어떤 패스도 결코 분포 바깥으로 나가지 않습니다. 합성은 가중치가 아니라 상태, 즉 스텝에서 스텝으로 건네지는 디코딩된 토큰 안에서 일어납니다. 길이는 가중치가 인코딩해야 했던 성질이었던 적이 결코 없으므로 길이 일반화는 공짜이며, 평가 시점의 구조적 행위인 루프가 그 전부를 나릅니다. 이것이 사다리의 교훈을 표 하나로 담은 것입니다: 인스턴스당이 아니라 스텝당으로 지출된 동일한 매개변수가, 그 기계를 다른 단으로 옮겨 놓았습니다.

순차 청구서

이제 두 가지 대가 가운데 첫 번째를 봅니다. 이는 표의 마지막 열에 인쇄되어 있습니다. 언롤링된 모델의 serial rounds 항목은 길이 $n$에서 정확히 $n$을 기록합니다: 이 모듈은 모든 순전파를 하나하나 세고, 하니스는 그 개수가 어떤 할인도 없이 인스턴스 길이와 같다는 것을 단언합니다(cot_steps.py, 285–287행). 커밋된 장부는 그 거래의 양쪽 모두를 서술합니다:

[4] the cost ledger — what the recovered depth costs
    fixed net : 3 serial rounds at EVERY length (parallel across the input),
                but chance beyond its cliff (mean acc n=7..16: 0.159, chance 0.167)
    step net  : accuracy ≥ 1.000 at every n = 2..32, but the ledger column is
                exactly n — Θ(n) serial time, NO parallel speedup: the
                loop that buys the depth is the serial cost.  That is the
                CoT trade [Merrill & Sabharwal, ICLR 2024].

병렬 할인이 전혀 없는 이유는, 애초에 이 루프를 깊게 만들었던 것과 같은 의존성 논증입니다. 이는 작업-깊이 트릴레마가 세 번째 옷을 입고 다시 나타나는 것이므로 풀어서 말할 가치가 있습니다. 스텝 $j$는 스텝 $j-1$의 디코딩된 상태가 존재하기 전까지는 시작될 수 없습니다; $n$개의 스텝은 하나의 의존적 사슬을 이루므로, 얼마나 많은 프로세서를 쓸 수 있든 상관없이 계산의 폭(span)은 $\Theta(n)$입니다. 벽시계 디코딩 지연은 $n$에 비례합니다(이 모듈은 초 단위가 아니라 스텝 개수를 커밋하는데, 초는 기계에 관한 사실이고 스텝 개수는 프로토콜에 관한 사실이기 때문입니다. 다만 각 라운드는 순전파 하나이므로, 그 비례 관계는 구성상 정확합니다). 깊이는 트릴레마가 병렬 하드웨어로는 살 수 없다고 말했던 바로 그 하나의 자원이었으며, 사고 사슬은 그 법칙을 반박하지 않습니다; 오히려 그것을 따르며, 그 깊이의 바닥값을 순차 시간으로, 단위당 토큰 하나씩으로 지불합니다. 배포에서의 귀결은 곧바로 따라옵니다. 고정-깊이 패스는 모든 길이에 상수 라운드로 답하며 자신의 절벽 너머에서는 틀리고; 루프는 어디서나 옳으며 토큰 단위로 값을 치릅니다. 추론의 조각이 얕거나 병렬화 가능한 곳, 즉 앞 장들의 차선인 구체화와 재작성, 제곱 커널, 배치화된 고정점은 순차적 디코딩 없이 답을 내놓으며, 처리량이 결정적인 시스템이라면 그것들을 사야 합니다. 디코딩 루프는 범용 차선이며, P에 도달하는 유일한 차선이고, 그 계량기는 그 루프의 매 스텝마다 돌아갑니다.

잘못된 사고 하나는 결코 치유되지 않는다

두 번째 대가는 이 장의 정직한 핵심이며, 이 과제에서는 측정되기도 전에 유도될 수 있습니다. 사슬이 한 번 오염되었다고 합시다: 스텝 $k$ 이후 그 상태가 참인 접두사 곱 $p_k$가 아니라 다른 어떤 원소 $q \ne p_k$이고, 그 뒤로는 디코딩이 올바르게 계속된다고 합시다. 나머지 모든 것과 같은 순서로 폴드된, 남은 토큰들의 곱을 $s = g_{k+1} \circ \cdots \circ g_n$이라 씁시다. 합성의 결합법칙(associativity)에 의해, 참인 답은 그 접두사를 거쳐 인수분해됩니다: $p_n = (p_k \circ g_{k+1}) \circ \cdots \circ g_n = p_k \circ s$. 오염된 실행은 잘못된 상태에서 시작해 같은 올바른 스텝들을 실행하므로 $q \circ s$에서 끝납니다. 이 둘이 일치할 수 있을까요? 각각의 오른쪽에 $s$의 역순열(inverse permutation)인 $s^{-1}$을 합성해 봅시다. 만약 $q \circ s = p_k \circ s$라면 $(q \circ s) \circ s^{-1} = (p_k \circ s) \circ s^{-1}$이고; 결합법칙으로 다시 묶으면 $q \circ (s \circ s^{-1}) = p_k \circ (s \circ s^{-1})$이므로 $q \circ e = p_k \circ e$, 따라서 $q = p_k$가 되어 $q \ne p_k$라는 가정과 모순됩니다. 따라서 "오른쪽에 $s$를 합성하기"라는 사상(map)은 단사(injective)입니다: 서로 다른 입력은 서로 다른 출력으로 갑니다. 그리고 원소 6개짜리 군에서 자기 자신으로 가는 단사 사상은 6개의 원소를 서로 다른 6개의 출력으로 보내는데, 그것이 곧 여섯 원소 전부이므로, 이 사상은 전단사(bijection), 즉 군과 자기 자신 사이의 완전한 짝짓기입니다. 그러므로 스텝 $k$에서의 잘못된 상태는 $k$가 무엇이든 오염이 무엇이든 상관없이 정확히 확률 1로 스텝 $n$에서의 잘못된 답으로 사상됩니다. 오차는 사슬을 따라가며 줄어들지 않습니다; 오차는 사슬을 타고 그대로 실려 갑니다.

이 모듈은 정확히 이 실험을 무대에 올립니다. 지정된 위치에서 디코딩된 상태를 균등 무작위의 잘못된 원소로 교체하고(클래스 id에 1부터 5까지의 균등한 오프셋을 6을 법으로 더하는데, 이는 나머지 다섯 개의 id를 똑같은 확률로 때립니다; cot_steps.py, 167–183행), 그 뒤로도 계속 디코딩합니다. 학습된 스텝 함수가 30개의 도달 가능한 쌍 전부에서 케일리 표와 일치하므로, 남은 스텝들은 실제로 정확한 오른쪽-곱셈이며, 위 유도는 이상적인 모델뿐 아니라 훈련된 모델에도 그대로 적용됩니다. 길이 $n = 16$에서의 커밋된 전시물은 다음과 같습니다:

[5] wrong-step propagation — the fragility of serial reasoning
    inject ONE corrupted intermediate state (uniform wrong element) at n = 16:
    corruption position sweep (seed fixed): end-task accuracy after corrupting
      after step:      2      5      8     11     14
      accuracy  :  0.000  0.000  0.000  0.000  0.000
    over seeds (corrupt after step 8; clean = same instances, no corruption):
      seed   clean acc   error persists to the end
         0     1.000              1.000
         1     1.000              1.000
         2     1.000              1.000
         3     1.000              1.000
         4     1.000              1.000
      mean persistence 1.000: right-multiplying by the remaining
      suffix is a bijection of S_3, so one wrong thought NEVER heals —
      a serial chain is only as sound as its weakest verified step

이 두 표를 맞대어 읽어 봅시다. 위치 스윕은 오염이 어디서든 똑같이 치명적이라고 말합니다: 이르든, 중간이든, 늦든, 최종 과제 정확도는 0.000인데, 그 전단사 논증이 위치와 무관하기 때문입니다. 시드별 표는 더 허술한 실험이라면 뭉개 버렸을 두 양을 분리해 냅니다: 같은 인스턴스들이 오염 없이는 1.000으로 디코딩되고, 오염된 실행들은 지속률(persistence) 1.000으로 틀리게 끝나는데, 이는 오차가 최종 답까지 살아남는 오염된 사슬의 비율입니다. 하니스는 모든 시드에서 오염 없는 정확도 최소 0.95와 나란히 지속률 최소 0.95를 요구하며(cot_steps.py, 311–314행), 커밋된 실행은 둘 다 포화시킵니다.

이제 설계상의 귀결에 이름을 붙여 주는 대조를 봅시다. 절벽을 지난 고정-깊이 모델 역시 틀리지만, 산만하게 틀립니다: 각 인스턴스는 독립적으로 확률 수준 근처(0.159의 꼬리)에 떨어지고, 오차가 올라탈 사슬이 없으므로 오차는 전파되지 않으며, 어떤 한 인스턴스에서 틀렸다는 것은 다음 인스턴스에 대해 아무것도 말해 주지 않습니다. 순차 기계는 그 위험 프로필을 뒤집습니다. 그 실패는 산만하지 않고 집중되어 있습니다: 단 하나의 스텝 하나하나가 전체 계산에 대한 단일 실패점입니다. 그 산술은 한 줄이면 됩니다: $n$-스텝 사슬의 각 스텝이 확률 $\varepsilon$으로 독립적으로 오류를 낸다면, 각 스텝은 확률 $1 - \varepsilon$으로 올바르므로, 독립성에 의해 사슬 전체가 오류 없이 실행될 확률은 $(1 - \varepsilon) \times \cdots \times (1 - \varepsilon) = (1 - \varepsilon)^n$인데, 이는 정확히 루프가 도달하려고 사들인 그 $n$에 대해 지수적으로 감쇠하는 양입니다. 이 무오류-사슬 확률은 최종 과제 정확도의 상한이 아니라 하한입니다. 두 개의 오류가 우연히 상쇄될 수도 있기 때문입니다; 전단사 논증이 덧붙이는 것은, 끝까지 살아남는 오류 하나는 확률 1로 치명적이므로 그런 상쇄만이 유일한 구조 수단이라는 사실입니다. 우리의 축소판은 모든 도달 가능한 쌍에서 $\varepsilon = 0$인 온화한 구석에 앉아 있으며, 그래서 오염 주입이 인위적일 수밖에 없었습니다; 자유 형식의 텍스트로 추론하는 배포된 모델은 포화시킬 30개짜리 표도, 정확성 인증서도 갖고 있지 않으므로, 그 $\varepsilon$은 알려져 있지 않고 그 사슬은 깁니다. 순차 추론은 모든 중간 스텝에 위험을 집중시키며, 루프 안의 그 무엇도 그 종이를 검사하지 않습니다. 그 문장이 다음 장의 검증기들의 첫 논거이며, 이 권이 사고 사슬을 공짜 점심으로 취급하기를 거부하는 이유입니다: 루프는 깊이를 사들이고, 공격 표면을 팝니다.

스크래치패드에서 프론티어까지

경험적 계보는 이론이 그 값을 매기기도 전에 이 루프를 찾아냈으며, 역사 한 문단이면 그 공로를 바로잡아 줍니다. 스크래치패드 훈련은, 답을 내놓기 전에 자신의 중간 계산을 텍스트로 내놓도록 가르친 고정된 언어 모델이, 같은 모델이 직접 시도했을 때는 실패했던 다단계 산술과 프로그램 흔적을 실행해 낼 수 있음을 보였습니다; 그 지도는 흔적 그 자체였으며, 이는 정확히 이 장의 스텝 수집이 취하는 모양입니다 [3]. 그다음 사고 사슬 프롬프팅(chain-of-thought prompting)은 충분한 규모에서는 그 흔적을 아예 훈련시킬 필요조차 없음을 보였습니다: 프롬프트 안의 몇 개의 예시 풀이만으로도 단계별 디코딩을 이끌어 낼 수 있고, 다단계 추론 벤치마크 점수가 뛰어오르는데, 이 루프를 유명하게 만든 창발적(emergent) 이득이었습니다 [4]. 이론은 그 뒤에 도착해 둘 다를 소급적으로 설명했습니다: 단일-패스 기계는 병렬성 트레이드오프에 의해 균일 TC⁰에 갇혀 있으므로 [5], 그 단보다 위에 있는 과제들은 스텝 없이는 반드시 실패해야 하며, 디코딩 예산은 정확히 그 천장이 값을 매기는, 부재중인 자원이므로, 스텝을 더하는 것은 요령이 아니라 클래스의 변화입니다 [1]. 이 권이 갚아야 할 정직한 지적은 이것입니다: 프롬프팅은 루프를 이끌어 낼 뿐, 그 단계들을 인증하지는 않습니다. 우리 축소판의 디코딩된 상태는 구성상 그 자체가 계산이며, 모든 도달 가능한 쌍에서 케일리 표에 맞대어 검증됩니다. 자유 형식의 근거 설명(rationale)에는 그런 동일성이 없습니다: 루프는 답을 만들어 내는 계산이 아닌 그럴듯한 텍스트를 디코딩할 수 있으며, I부의 충실성 장은 정확히 진술된 추론과 실효적인 추론 사이의 그 간극을 측정했습니다. 이 정리들은 사슬이 계산할 수 있는 것을 한계 지을 뿐입니다; 어떤 특정한 사슬이 실제로 그렇게 계산했는지에 대해서는 아무것도 말하지 않습니다.

아직 풀리지 않은 부분

사다리의 단들은 깔끔하지만, 그 사이의 땅은 대부분 지도가 그려져 있지 않으며, 이 장 자신의 숫자들이 구체적으로 보여 주는 세 방향에서 그렇습니다. 첫째, 스텝 효율성(step efficiency)입니다. 맨 위 단의 특징짓기는 다항식이며, "다항식"은 느슨한 말입니다: 주어진 문제에 대해 충분한 최소 디코딩 예산은 일반적으로 알려져 있지 않고, 알려진 단들은 서로 멀리 떨어져 있습니다. 우리의 과제는 그 오토마타를 $n$번의 스텝으로 실행했지만, 그 군은 결합법칙을 만족하므로 균형 잡힌 재묶음(regrouping)은 그 곱을 $O(\log n)$번의 의존적 곱셈으로 계산합니다; 디코더가 그런 일정을 내놓도록 훈련될 수 있는지, 그리고 어떤 문제들에 대해 로그 또는 준선형(sublinear) 예산이 애초에 충분한지는, 양쪽 어느 쪽에서도 딱 떨어지는 답이 거의 없는 채로 $O(\log n)$ 단과 $\Theta(n)$ 단 사이에 놓여 있습니다. 둘째, 적응적 예산(adaptive budget)입니다. 여기서는 모든 것이 $t(n)$을 미리 고정해 두었습니다; 추론 시스템이라면 인스턴스가 어려운 곳에는 스텝을 쓰고 쉬운 곳에서는 일찍 빠져나와야 할 텐데, 이는 이 권이 계속해서 마주치는 애니타임(anytime) 문제가 이제 디코딩 시점에 나타난 것이며, 절약된 스텝들이 무엇을 바꿀 수 없었는지에 대한 보증과 함께, 사슬에 대한 원칙적이고 학습된 조기 종료(early-exit)는 아직 존재하지 않습니다. 셋째, 이 실험이 관통하기보다는 그 둘레를 두르도록 설계된 간극입니다: 어떤 스텝 함수가 어떤 지도로부터 학습 가능한가입니다. 우리의 스텝 함수는 30개의 도달 가능한 입력을 가졌고 우리는 그 전부를 지도했습니다; 배포된 모델의 암묵적인 스텝 함수에는 그런 표가 없고, 그 흔적 형식은 고정되어 있지 않고 발견되는 것이며, 스크래치패드 방식의 흔적 지도가 언제 정확하고 합성 가능한 스텝을 내놓는지, 아니면 작은 오차들이 복리로 쌓여 무오류-사슬 확률을 취약성 절이 유도한 $(1-\varepsilon)^n$의 비율로 무너뜨리는 스텝을 내놓는지를 예측해 줄 이론은, 표현력과 학습 동역학이라는, 앞 장을 마무리 지었던 바로 그 잃어버린 다리를 가진 두 과학 사이의 열린 땅으로 남아 있습니다.

왜 중요한가

이 시리즈에게 이 장은 1권에서 열렸던 하나의 루프를 닫습니다. 전방향 연쇄기는 자라나는 사실 집합 위에서 얕은 규칙-적용 스텝을 반복함으로써 자신의 폐쇄를 계산했습니다; 2권의 EL 완결과 이 권의 고정점 커널들도 같은 모양을 갖습니다. 유계인 루프 안에 있는 유한한 스텝, 그리고 외부의 기호적 저장소에 사는 상태입니다. 사고 사슬은 신경 아키텍처가 디코딩 시점에 그 모양을 재발견한 것입니다: 토큰 스트림이 사실 집합이고, 순전파가 규칙 적용이며, 사다리 정리는 그 모양이 다항인 모든 것을 회복한다고 말해 주는 허가증입니다. 이는 신경-기호(neuro-symbolic) 시스템을 위한 설계 질문을, "모델이 단계별로 추론해야 하는가"보다 더 날카롭게 만듭니다. 이 장이 독자로 하여금 어떤 CoT 주장에 대해서든 물을 수 있게 해 주는 질문들은 정량적입니다: 이 과제는 어느 단을 필요로 하는가, 배포 시점에 그 예산은 어떤 순차 청구서를 함의하는가, 그리고 $(1-\varepsilon)^n$ 사슬-생존 확률이 복리로 쌓이게 될 스텝당 오류율 $\varepsilon$은 얼마인가입니다. 그리고 이 장은 다음 장에게 그 문제 진술을 측정된 형태로 건네줍니다: 루프의 모든 스텝은 검증되지 않은 단일 실패점이며, 우리의 커밋된 전시물은 스텝들이 검사 가능한 과제에서 잘못된 사고 하나가 확률 1로 치명적임을 보여 주며, 프론티어의 답, 즉 디코딩 루프를 감싸는 보상 신호와 검증기 관문(verifier gate)이 V부가 다음으로 향하는 곳입니다. 독자 자신의 연구를 위해서는, 이 격리 설계가 재사용 가능한 도구입니다: 어떤 메커니즘과 그것의 학습된 근사가 뒤엉켜 있을 때는, 학습 가능한 부분이 증명 가능하게 포화되는 설정을 찾아내어, 그 메커니즘이 나머지를 홀로 나르게 하십시오.

핵심 용어

• 자기회귀적 디코딩(Autoregressive decoding): 반복되는 순전파를 통한 생성으로, 각 패스는 토큰 하나를 내놓고 그것을 다음 패스의 입력에 이어붙입니다; 고정된 스택을 하나의 깊은 계산으로 만드는 루프입니다.
• 사고 사슬(Chain of thought, CoT): 답 이전에 디코딩되는 중간 토큰들; 구조적으로는, 생성된 토큰 하나당 하나의 순차적 스텝이라는 디코딩 시점의 깊이 예산입니다.
• 디코딩-스텝 예산(Decode-step budget) $t(n)$: 길이 $n$의 입력에 허용되는 중간 토큰의 개수; 사다리의 다이얼로서, $O(1)$은 TC⁰ 너머로는 아무것도 사들이지 못하고, $O(\log n)$은 로그공간 안에 머물며, $\Theta(n)$은 모든 정규 언어에 도달하고, $\mathrm{poly}(n)$은 정확히 P를 특징짓습니다.
• 스텝 모델(Step model): (상태, 토큰)을 다음 상태로 사상하는 동반 코드의 깊이-1 네트워크로, 단일 연산만으로 훈련됩니다; 이 과제의 6-상태 오토마타에 대한 학습된 전이 함수이며, 30개의 도달 가능한 쌍 전부에서 정확합니다.
• 언롤링(Unrolling): 평가 시점에 스텝 모델을 $n$번 적용하며, 각 argmax 출력을 다음 입력으로 다시 인코딩하는 것; 정확히 $n$번의 순차 라운드로 깊이를 나르는 루프입니다.
• 순차 라운드(Serial rounds): 커밋된 비용 장부의 항목으로, 인스턴스 길이와 같다고 단언됩니다; 작업-깊이 트릴레마의 깊이 바닥값이 병렬 할인 없이 디코딩 시간으로 지불된 것입니다.
• 지속률(Persistence): 오차가 최종 답까지 살아남는 오염된 사슬의 비율; 1.000으로 커밋되며, 남은 접미사와의 오른쪽 합성이 잘못된 상태를 결코 옳은 답으로 사상하지 않는다는 전단사 논증과 일치합니다.
• 표현력 대 학습 가능성(Expressiveness versus learnability): 사다리는 가중치가 존재한다고 주장할 뿐입니다; 훈련이 그것을 찾아낸다고는 말하지 않으며, 이것이 동반 코드가 루프에 그 깊이의 공로를 돌리기 전에 학습 가능한 부분(30개 쌍짜리 스텝 표)을 포화시켜 두는 이유입니다.

다음으로 이어지는 것

루프는 P를 되사 왔고, 이 장이 인쇄한 두 가지 통화로 그 값을 치렀습니다: 하나의 예산인 시간, 그리고 모델 안에 어떤 상대방도 없는 하나의 부채인 취약성입니다. 디코딩된 사슬의 모든 스텝은 검증되지 않은 주장이며, 커밋된 전시물은 잘못된 주장 하나가 얼마의 대가를 치르는지 보여 주었습니다. 다음 장인 강화학습과 검증기 관문 추론은 그 상대방을 짓습니다: 검사를 통과하는 사슬을 향해 루프를 훈련시키는 보상 신호, 그리고 잘못된 사고가 끝까지 실려 가도록 내버려두기를 거부하는 검증기 관문(verifier gate)입니다. 1권과 2권의 기호적 엔진들이, 바로 이 장이 가능하게 만든 그 순차 계산들을 위한 검사 기계 장치로 되돌아옵니다.

---

동반 코드: examples/frontier/cot_steps.py는 짧은 대역에서 수집한 단일-연산 지도로 깊이-1 스텝 모델을 훈련시키고, 학습된 전이 함수를 30개의 도달 가능한 쌍 전부에서 케일리 표에 맞대어 검증하며, 앞 장의 깊이-3 상대를 그 정확한 프로토콜로 다시 훈련시키고, n = 2..32에 걸친 공유 정면 대결을 실행하고, 순차-라운드 장부를 인쇄하며, 오염 전시물을 무대에 올립니다. 이 장에서 인용된 모든 주장은 assert로 지켜집니다(스텝-모델 바닥 0.95, n = 8..16에서의 우위 0.5, 사용된 스텝 수 = n, 시드별 지속률 0.95). 이 코드는 과제 생성기와 인증된 MLP 엔진을 examples/frontier/depth_ceiling.py에서 가져오며, 아무것도 다시 타이핑하지 않습니다. 모든 숫자를 재현하려면 python3 examples/frontier/cot_steps.py를 실행하십시오; 두 번의 실행은 바이트 단위까지 동일한 출력을 인쇄합니다.