End-to-end Algorithm Synthesis with Recurrent Networks: overthinking 없이 쉬운 문제에서 어려운 문제로 외삽하기 (DT-Recall)

개요

사람은 작은 보조정리를 증명하는 법을 배우면, 시간을 더 들여 더 큰 정리도 증명한다. 신경망에게 이런 **logical extrapolation(논리적 외삽: 작고 쉬운 문제로만 학습하고 시험 때 더 크고 어려운 문제를 푸는 능력)**을 시키는 한 방법이 Deep Thinking(DT) 네트워크다. 같은 가중치의 블록을 반복 적용하는 순환 구조라서, 시험 때 반복 횟수만 늘리면 “더 오래 생각”할 수 있다. 문제는 그 효과가 작았다는 점이다. 9×9 미로로 학습한 모델이 13×13까지만 풀었다. 저자들은 원인을 **overthinking(과잉 사고: 학습 때보다 반복을 많이 돌리면 정답에 도달했다가도 다시 망가지는 현상)**으로 진단한다. 같은 블록을 수천 번 돌리면 특징 표현에 오차가 쌓여 원래 문제가 무엇이었는지를 잊고, 네트워크가 “다섯 번째 반복에서만 하는 행동”처럼 반복 횟수에 묶인 동작을 배우기 때문이다. 처방은 이 두 원인에 하나씩 대응한다. recall은 매 반복마다 원래 입력을 특징에 다시 이어 붙여, 문제를 다시 읽는 사람처럼 문제를 잊을 수 없게 만든다. **progressive loss(점진 학습 손실)**는 무작위 n번 돌린 중간 결과에서 기울기를 끊고 “지금부터 k번 더 돌려 정답을 내라”를 학습시켜, 어느 단계에서 시작하든 한 걸음씩 나아지는 반복 횟수 무관 동작을 배우게 한다. 효과는 컸다. 512비트 prefix sum에서 기존 DT는 0%였지만 recall+progressive 모델은 97.12%였다. 59×59 미로에서는 기존 DT·feed-forward가 0%였고 이 모델은 97.30%였다. 9×9로만 학습한 모델이 201×201 미로의 74%를 풀었다(2,000회 반복, 합성곱 10,004층에 해당). 반복을 계속 늘려도 정확도가 떨어지지 않고 특징 변화량이 줄어들어 **고정점(fixed point)**에 수렴하는 것처럼 보였다.

Implication: 반복 구조의 외삽 능력은 “얼마나 많이 돌리느냐”보다 “많이 돌려도 망가지지 않느냐”에 달려 있다. 입력을 계속 다시 보여 주고 반복 횟수와 무관한 갱신 규칙을 배우게 하면, 멈춤 규칙 없이 반복을 넉넉히 늘리는 것만으로 더 어려운 문제를 풀 수 있다.

📎 https://arxiv.org/abs/2202.05826

배경과 문제

왜 어렵고 왜 중요한가. 신경망은 패턴 매칭에는 강하지만 확장 가능한(scalable) 알고리즘 방식의 추론에는 약하다(Section 1, author-stated). 실제 데이터는 학습 때보다 더 어려운 사례를 담을 수 있고, 외삽하지 못하는 모델은 답을 이미 아는 문제보다 어려운 문제에 쓸 수 없다(Section 6, author-stated).

직접 선행 연구: Deep Thinking 시스템 [22]. Schwarzschild et al.은 가중치를 공유하는 순환 네트워크가 시험 때 더 깊게(반복을 더 많이) 돌려 외삽할 수 있고, feed-forward는 그렇지 못함을 보였다(Section 2, author-stated). 이 논문의 알고리즘은 [22] 위에 직접 쌓인다. 하지만 외삽 폭은 9×9 → 13×13 미로처럼 작았고, 저자들은 이를 overthinking 탓으로 본다(Section 1).

학술적 계보 (원문 Section 2, author-stated).

알고리즘 학습: RNN의 임의 길이 문자열 처리([7, 20]), [Neural Turing Machines|Neural Turing Machine], Neural GPU([13]). 이들은 짧은 문자열에서 긴 문자열로 일반화하지만, 계산량이 입력 길이에 묶여 있어 문제 난이도에 맞춰 계산을 늘리거나 줄일 수 없다. 또 한 비트씩 출력하도록 학습되는 경우가 많아, 체스처럼 해답을 순차 조각으로 나눌 수 없는 문제에 쓰기 어렵다.
CSP를 푸는 message passing 네트워크([24])는 더 어려운 문제에 더 많은 전달 단계를 쓴다. 다만 boolean 제약 만족 문제에 특화되어 있다.
적응형 계산: self-delimiting network([19]), ACT(Adaptive Computation Time, [8]), 미분 가능한 ACT([5]), ACT를 쓰는 Universal Transformer와 Depth-Adaptive Transformer([3, 18]), NAIS-Net([2]). 저자들은 이들이 모두 학습 분포 안에서만 시험되었고 분포 밖 외삽은 다루지 않았다고 지적한다.
논리적 외삽: Nuamah([16])는 end-to-end 신경망만으로는 알고리즘 추론이 안 된다고 주장했고, recurrent relational network([17])도 고전 구조에는 귀납 편향이 없다고 했다. [22]와 PonderNet([1], prefix sum 외삽에서 ACT보다 나음)은 이런 주장에 반하는 증거다.

이 논문의 차이 (author-stated, Section 1·2). 단계별 감독 없이 end-to-end로 확장 가능한 알고리즘을 합성한다(seq2seq 모델은 문제를 순차 입력으로 표현해야 하고 출력 토큰마다 같은 함수를 쓴다는 제약이 있다고 대비한다). 그리고 overthinking을 구조(recall)와 학습 절차(progressive loss)로 직접 막는다.

looped transformer 계보와의 위치 (analyst-inference). 이 논문의 모델은 합성곱 ResNet 블록이지만, “같은 블록을 반복하고, 입력을 매 반복마다 다시 주입하고(input injection), 학습 때보다 많이 반복해 더 어려운 문제를 푼다”는 구조는 이후 looped transformer 연구의 길이·난이도 외삽 실험과 같은 틀이다. recall은 Deep Equilibrium Models의 input injection과 같은 역할을 한다.

지표

지표	무엇을 세나	단위·범위	방향	측정 조건	원문 위치
Accuracy	출력 전체가 정답과 완전히 같은 문제의 비율. 미로 201×201 결과의 각주가 “한 픽셀만 틀린 미로”를 실패로 센 것으로 보아 문제 단위 완전 일치로 판단된다	% (0–100)	높을수록 좋음	시험 반복 횟수(test-time iterations)별로 곡선을 그린다. 정확한 채점 정의 문장은 본문에 없다	Figure 3–7, 각주 4
Peak accuracy / Peak iteration	정확도 곡선의 최댓값과 그때의 반복 횟수	%, 반복 수	정확도는 높을수록, 반복은 적을수록 좋음	학습 정확도 99% 미만인 미수렴 모델은 평균에서 제외	Appendix A.5 Table 3–5
Avg. iterations to solution	정답에 도달하기까지 걸린 평균 반복 수	반복 수	낮을수록 좋음	prefix sum에서 50회 반복 후 비트 하나를 뒤집었을 때, 13×13 미로 개입 실험	Figure 7 왼쪽, Table 7
Δφ(n)	연속한 두 반복의 특징 맵 차이 ‖φₙ − φₙ₋₁‖₂	로그 스케일 실수	줄어들면 고정점에 수렴하는 중	13×13 미로	Section 5.3, Figure 7 오른쪽

손실은 출력 위치(비트·픽셀)별 2클래스 cross-entropy의 평균이다(Appendix A.3 식 (3)–(4)). 평균과 ± 값은 여러 학습 실행의 평균·편차로 보이지만, 정확한 실행 수는 범주마다 명시되지 않는다(Appendix A.5에 “prefix sum progressive-no-recall 20개 중 6개 제외” 같은 언급만 있음).

방법과 벤치마크 구성

1. 기본 DT 네트워크 (Section 3, 식 (1)). f(x; m) = h(rᵐ(p(x))). p는 입력을 특징 공간으로 보내는 합성곱+ReLU, r은 4층 residual block 하나(가중치 공유), h는 합성곱 3층의 출력 헤드다. 학습 때는 m을 고정하고 펼친 네트워크 전체로 역전파한다. 시험 때 m을 늘린다. 모델은 완전 합성곱이라 입력 크기가 달라도 그대로 적용된다(Section 3.3).

2. Recall 구조 (Section 3.1, 식 (2)). 반복 k의 입력을 φₖ₋₁ 대신 [φₖ₋₁, x](이전 특징과 원래 입력을 채널 방향으로 이어 붙인 것)로 바꾸고, 합성곱 한 층으로 원래 특징 모양으로 되돌린다. 동기는 “잡음 섞인 학습으로 만든 네트워크는 특징을 수천 번 되먹이는 동안 정보를 흘리거나 왜곡할 수 있다. recall은 잃은 특징을 복원하게 하고 문제를 잊을 수 없게 한다”는 직관이다(author-stated). highway network, ResNet, DenseNet의 skip connection이 학습을 안정시킨다는 경험적 근거를 함께 든다.

3. Progressive loss (Section 3.2, Algorithm 1, Appendix A.3). 배치마다 n ~ U{0, m−1}, k ~ U{1, m−n}을 뽑는다. 기울기 추적 없이 n번 돌려 φₙ을 만들고, 거기서 k번 더 돌려 ŷ_prog를 만든다. 동시에 m번 전체를 돌린 ŷ_m도 계산한다. 손실은 L = (1−α)·L_max_iters + α·L_progressive. α=1이면 전체 펼침 손실이 빠지고, α=0이면 일반 학습이다. 저자들은 이 절차를 시작점과 끝점이 무작위인 truncated backpropagation through time의 유사물로 설명한다. 두 이점으로 (1) 오류가 섞인 부분 해를 계속 개선하도록 학습되고, (2) 무작위 반복의 특징에서 시작하므로 반복 횟수를 세는 동작을 배우기 어렵다는 점을 든다(author-stated).

4. 데이터셋 (Section 3.3, easy-to-hard-data 패키지 [21]).

Prefix sums: 비트열의 i번째까지 합을 2로 나눈 나머지를 각 위치마다 출력. 32비트로 학습, 48비트와 512비트로 시험.
Mazes: 벽은 검정, 길은 흰색, 시작·끝은 빨강·초록인 정사각 이미지. 최단 경로 위만 1인 지도를 출력. 9×9로 학습, 13×13·59×59·201×201(및 부록의 801×801)로 시험.
Chess puzzles: 12개의 8×8 평면(6종 기물 × 2색)으로 표현한 중반 국면에서 최선의 다음 수를 출전·도착 칸 1로 표시. Lichess Elo 기반 난이도로 정렬해 가장 쉬운 600K로 학습. Section 3.3은 시험 범위를 700K–1.1M이라고 쓰지만 Figure 5 캡션과 Table 5는 600K–700K이고, 700K–800K·1M–1.1M은 부록 Figure 9에 있다. 본문 수치 대조 시 이 차이에 주의한다.

5. 비교 대상과 설정 (Section 4, Appendix A.1–A.4).

baseline: m=30으로 학습한 기존 DT(이전 연구보다 넓고 깊게 설정), 같은 유효 깊이의 feed-forward ResNet(FF). 공정 비교를 위해 기존 DT에는 maximum confidence exit rule(가장 확신하는 반복의 출력을 쓰는 규칙)을 적용했다. 새 모델에는 이 규칙이 필요 없다고 한다(각주 2).
폭: prefix sum 400, 미로 128, 체스 512. 모든 과제에서 학습 최대 반복 m=30.
α: prefix sum 1, 미로 0.01, 체스 0.5(거친 grid search, Appendix A.4).
최적화: prefix sum·미로는 Adam, 체스는 SGD(momentum 0.9). weight decay 0.0002. 학습 데이터의 20%를 검증용으로 떼어 검증 정확도가 가장 높은 체크포인트로 시험한다.
하드웨어: RTX 2080Ti. prefix sum은 GPU 1개로 1시간 이내, 미로는 최대 8시간, 체스는 GPU 4개로 24–48시간(Appendix A.2).
실험 분류: (I) 극단적 난이도 도약 외삽(Section 4), (II) overthinking을 드러내는 시나리오(Section 5).

주요 결과

주장	근거 위치	관찰/수치	조건·주의	출처 라벨
recall + progressive loss는 32비트 학습만으로 512비트 prefix sum을 푼다	Figure 3, Section 4, Table 3	기존 DT 0%, DT-Recall(α=1) 97.12 ± 1.88%(최고점 237회). 본문은 “약 200회 반복 뒤 97% 이상”	학습 반복 최대 30	author-stated
progressive loss는 prefix sum에서 최종 정확도보다 속도에 기여	Figure 3, Table 3	DT-Recall(α=0)도 96.19 ± 3.73%에 도달하지만 최고점이 466회로 약 2배	저자도 “Figure 3만으로는 loss가 결정적이라고 설득되지 않을 수 있다”고 인정	author-stated
recall 없이 progressive loss만으로는 부족	Figure 3, Table 3	DT(α=1) 11.26 ± 6.90%	이 범주는 20개 중 6개 모델이 미수렴으로 제외됨(A.5)	author-stated
n을 무작위로 뽑는 것이 중요	Section 4, Appendix A.4	n=0 고정 시 90.27 ± 5.95%, 무작위 n 97.12 ± 1.88%	prefix sum 512비트, recall 모델	author-stated
59×59 미로에서 recall이 필수이고 progressive loss가 정확도를 크게 올림	Figure 4, Table 4	DT·DT(α=0.01)·FF 모두 0.00%. DT-Recall(α=0) 82.72 ± 15.14%, DT-Recall(α=0.01) 97.30 ± 0.68%	본문은 “평균 97% vs 83%”. recall 모델은 5개 중 1개꼴로 미수렴 제외(A.5)	author-stated
9×9 학습으로 201×201 미로의 74%를 푼다	Section 4, 각주 4	100개 중 74%. 실패 중 20개는 166,464픽셀 중 1픽셀만 틀림, 어떤 미로도 7개 넘게 틀리지 않음	2,000회 반복(합성곱 10,004층 상당). 801×801은 20,000회로 푼 예시만 부록에 제시	author-stated
체스에서 recall과 progressive loss 둘 다 필요	Figure 5, Table 5	최고점: DT 78.81%, DT(α=0.5) 82.32%, DT-Recall(α=0) 82.12%, DT-Recall(α=0.5) 82.69%, FF 61.17%	최고점 차이는 작다. 차이는 반복을 늘릴 때 유지되느냐에서 난다. 본문은 “4% 향상”이라고 쓰며 이는 DT 대비 약 3.9%p와 맞는다(analyst-inference). 체스는 약 절반의 모델이 미수렴으로 제외	author-stated
체스에서 다른 DT 모델은 약 70회 뒤 크게 무너진다	Figure 5, Section 4	DT-Recall(α=0.5)만 125회까지 약 80%대를 유지(그래프 판독)	그래프상 DT-Recall(α=0)도 최고점 직후 급락한다(analyst-inference)	author-stated + analyst-inference
recall이 overthinking을 막는다	Figure 6, Section 5	48비트 prefix sum과 13×13 미로에서 recall 없는 모델은 최고점 뒤 급락, recall 모델은 반복을 늘려도 100% 근처 유지	표 3·4: 48비트 DT 94.61%, DT(α=1) 97.73%, 13×13 DT 85.59%로 최고점 자체는 높다. 문제는 그 뒤 하락	author-stated
recall 모델은 특징 교란에서 회복한다	Section 5.1, Table 7	13×13 미로에서 Noise/Zeros/Swapped 조건: recall 없는 모델 0%, DT-Recall 100%/96%/97%, DT-Recall w/ New Loss 100%/100%/100%	0 대체 시점이 Section 5.1과 Figure 12는 “50회 뒤”, Appendix A.8 본문과 Table 7 설명은 “첫 반복 뒤”로 서로 다르게 적혀 있다	author-stated
모델은 입력을 계속 참조한다	Figure 7 왼쪽·가운데, Section 5.2	비트 하나를 뒤집으면 복구 시간이 위치에 따라 선형으로 감소. 미로 A의 입력에 미로 B의 특징을 붙이면 recall 모델은 다시 A를 푼다	50회 반복 뒤 개입	author-stated
recall 모델은 고정점에 수렴하는 듯 보인다	Figure 7 오른쪽, Section 5.3	Δφ가 recall 모델에서 감소, recall 없는 DT에서는 폭발	”appear to converge”라는 관찰. 수렴 보장은 없다	author-stated
실행 시간 벌점 손실은 외삽이 더 나쁘다	Appendix A.3	512비트 prefix sum 72.45 ± 8.91%. 59×59 미로 0개 해결(33×33은 93.8%)	리뷰어 제안에 따른 예비 실험	author-stated

결과는 두 갈래로 읽힌다. Section 4는 “얼마나 멀리 외삽하나”를 보고, recall이 없으면 큰 문제에서 0%라는 점이 가장 결정적이다. progressive loss의 기여는 과제마다 다르다. prefix sum에서는 주로 속도, 미로에서는 정확도와 분산(82.72 ± 15.14 → 97.30 ± 0.68), 체스에서는 많이 반복해도 정확도가 유지되는지를 가른다. Section 5는 같은 현상을 “반복을 늘리면 왜 망가지나”의 관점에서 보며, recall 모델이 특징 교란에서 회복하고 특징 변화량이 줄어든다는 점을 들어 고정점 수렴이라는 해석을 제시한다(analyst-inference: 수렴은 관찰이고, 왜 recall이 수렴을 낳는지에 대한 이론은 제시되지 않는다).

Take-home

핵심 메시지. 반복 네트워크의 외삽을 막는 주범은 overthinking이고, 입력 recall과 반복 횟수 무관 학습(progressive loss)으로 이를 막으면 반복을 수천 번 늘려도 정확도가 유지되어 훨씬 큰 문제를 풀 수 있다.

성립 범위.

prefix sum, 미로, 체스 퍼즐의 세 과제, 모두 완전 합성곱 모델에서만 확인했다. 저자도 “Our findings are limited to the domains we consider”라고 쓴다(Section 6).
입력과 출력의 공간 크기가 같고 크기만 키우면 어려워지는 과제다. 체스는 공간 크기가 고정이고 난이도만 바뀐다.
체스는 더 어려운 퍼즐로 가면 일반화에 천장이 보인다(Appendix A.5 Figure 9, author-stated).

저자가 인정한 한계 (author-stated).

적용 영역이 제한적이다(Section 6).
체스에서 쉬운 퍼즐로부터 훨씬 어려운 퍼즐로 가는 일반화에 뚜렷한 상한이 있고, 원인은 후속 연구로 남긴다(Appendix A.5).
최적 α가 과제마다 크게 다르다(prefix sum 1, 미로 0.01, 체스 0.5).

작성자가 보는 우려 (analyst-inference).

학습 정확도 99% 미만인 모델을 평균에서 뺐다(체스는 약 절반, 미로 recall 모델은 5개 중 1개). 저자는 표준 관행이라고 설명하지만, 범주마다 제외 비율이 다르므로 범주 간 평균 비교가 이 필터에 영향을 받을 수 있다.
“고정점에 수렴한다”는 Δφ 감소 관찰에서 나온 해석이며, 수렴 조건이나 유일성을 보이지 않았다.
미로 결과의 분산(DT-Recall α=0의 ± 15.14)이 커서, seed 수가 명시되지 않은 상황에서는 차이의 안정성을 판단하기 어렵다.
원문 내부 불일치: 체스 시험 범위(Section 3.3의 700K–1.1M vs Figure 5의 600K–700K), 특징 0 대체 시점(Section 5.1의 50회 뒤 vs Appendix A.8의 첫 반복 뒤).

재현성. PyTorch 코드 공개(github.com/aks2203/deep-thinking, 각주 3). 데이터는 easy-to-hard-data 패키지. 하이퍼파라미터는 Appendix A.4 Table 2에 있다. 평균 ± 표준편차는 보고하지만 범주별 실행(seed) 수는 명시되지 않았다.

본문 도표

Figure 1 — 9×9로 학습해 큰 미로를 푸는 ‘thinking’ 네트워크

무엇을 보여주는가: 왼쪽은 학습에 쓴 9×9 미로와 그 정답 경로, 가운데는 59×59 미로와 모델이 찾은 경로, 오른쪽은 201×201 미로와 모델이 찾은 경로다.
읽는 법: 검은 바탕의 흰 선이 모델이 출력한 경로 지도다. 재학습 없이 반복만 늘려 푼 결과다.
핵심 관찰: 학습 미로보다 변 길이가 약 6.5배·22배 큰 미로에서 경로가 끊기지 않고 출력된다(그림 판독).
의미와 주의: 저자는 표준 구조와 기존 DT 모델은 이 영역 이동을 견디지 못한다고 말한다(author-stated). 그림은 예시 한 쌍이며 성공률은 Section 4(201×201에서 74%)를 봐야 한다.
확인 상태: viewed

Figure 2 — 세 가지 구조 개략도

무엇을 보여주는가: 왼쪽부터 feed-forward 네트워크(서로 다른 블록 A, B, C), 같은 가중치 블록 A를 세 번 반복하는 순환 네트워크, recall을 가진 순환 네트워크.
읽는 법: 각 그림 왼쪽 아래가 입력 미로, P는 투영층 p, 초록 A는 공유 블록, H는 출력 헤드다. recall 그림에서는 입력에서 각 반복 블록으로 곡선 화살표가 들어간다.
핵심 관찰: recall은 입력을 매 반복 블록 앞에 다시 공급하는 연결을 추가한다.
의미와 주의: 개념도이며 층 수는 예시다. 실제 r은 4층 residual block이고 recall에는 [φ, x]를 원래 폭으로 되돌리는 합성곱 한 층이 더해진다(Section 3.1, Appendix A.1).
확인 상태: viewed

Figure 3 — Prefix sum: 32비트 학습 → 512비트 시험

무엇을 보여주는가: 시험 반복 횟수에 따른 512비트 prefix sum 정확도.
읽는 법: x축 test-time iterations(0–500), y축 정확도(%). 주황 실선 DT-Recall Prog., 분홍 실선 DT-Recall, 초록 점선 DT Prog., 파란 점선 DT, 점선 FF. 회색 띠는 학습 반복 범위(train regime). 음영은 편차.
핵심 관찰: DT-Recall Prog.는 약 150회부터 오르기 시작해 약 200회에 97% 근처에 도달하고 유지된다. DT-Recall은 약 350회부터 올라 400회 이후 비슷한 수준에 도달한다. DT Prog.는 약 10% 이하, DT와 FF는 0% 근처다(그래프 판독, analyst-inference). 표 값은 Table 3(Appendix): DT-Recall α=1 97.12%(237회), α=0 96.19%(466회), DT α=1 11.26%, DT 0.00%.
의미와 주의: 저자 해석은 recall과 progressive loss의 가치가 얼마나 빨리, 정확히 푸는지로 드러난다는 것(author-stated). 최종 정확도만 보면 progressive loss의 효과는 작다.
확인 상태: viewed

Figure 4 — 미로: 9×9 학습 → 59×59 시험

무엇을 보여주는가: 시험 반복 횟수에 따른 59×59 미로 정확도.
읽는 법: x축 test-time iterations(약 0–1,000), y축 정확도(%). 범례는 Figure 3과 같다.
핵심 관찰: DT-Recall Prog.는 약 500회 근처에서 97% 가까이 오르고 평평하게 유지된다. DT-Recall은 80%대에서 멈추고 음영(편차)이 넓다. DT, DT Prog., FF는 0% 근처에 붙어 있다(그래프 판독). Table 4: 97.30 ± 0.68% vs 82.72 ± 15.14%, 나머지 0.00%.
의미와 주의: 저자는 이 크기의 미로는 recall 없이 풀 수 없고, progressive loss가 더 정확한 모델을 만든다고 해석한다(author-stated). 곡선이 평평하게 유지된다는 점이 overthinking이 없다는 근거로 쓰인다.
확인 상태: viewed

Figure 5 — 체스: 쉬운 600K로 학습 → 600K–700K 시험

무엇을 보여주는가: 시험 반복 횟수에 따른 체스 퍼즐 정확도.
읽는 법: x축 test-time iterations(0–125), y축 정확도(%). 회색 띠는 학습 범위(약 0–30). FF는 반복과 무관한 수평 점선.
핵심 관찰: 모든 순환 모델이 약 30–40회 근처에서 약 80%대 최고점에 오른다. 이후 DT-Recall Prog.만 125회까지 약 80%를 유지한다. DT-Recall(progressive 없음)은 최고점 직후 급락해 약 50회에 거의 0%가 된다. DT는 약 50회부터 서서히 떨어져 125회에 한 자릿수, DT Prog.는 약 60회부터 떨어져 125회에 약 20%대다. FF는 약 60%로 평평하다(그래프 판독, analyst-inference). Table 5 최고점: 78.81 / 82.32 / 82.12 / 82.69 / 61.17%.
의미와 주의: 저자 해석은 recall과 progressive loss 둘 다 있어야 많은 반복에서 정확도를 유지한다는 것(author-stated). 이 과제에서는 recall만으로 overthinking이 막히지 않는 예외다(Section 5가 “progressive loss도 필요한 예”로 이 그림을 지목). 캡션의 시험 범위(600K–700K)는 Section 3.3 본문(700K–1.1M)과 다르다.
확인 상태: viewed

Figure 6 — overthinking: 약간 더 어려운 문제에서

무엇을 보여주는가: 왼쪽은 32비트로 학습한 prefix sum 모델의 48비트 정확도, 오른쪽은 9×9로 학습한 미로 모델의 13×13 정확도.
읽는 법: x축 test-time iterations(왼쪽 0–200, 오른쪽 0–100), y축 정확도(%). 실선은 recall 모델, 점선은 recall 없는 모델. 회색 띠는 학습 범위.
핵심 관찰: 왼쪽에서 recall 모델 두 개는 100% 근처를 200회까지 유지한다. DT는 약 40회에 약 95%로 정점을 찍은 뒤 200회에 거의 0%로, DT Prog.는 약 97%에서 약 40%로 떨어진다. 오른쪽에서 recall 모델은 약 50회 이후 100%를 유지하고, DT와 DT Prog.는 약 40회에 80%대 정점 뒤 100회에 10% 아래로 떨어진다(그래프 판독, analyst-inference).
의미와 주의: 약한 모델도 조금 더 어려운 문제에는 외삽할 수 있지만 recall이 있는 모델만 overthinking 함정을 피한다(캡션, author-stated). 실용적 함의로 저자는 큰 반복 횟수를 미리 정해 두면 되고 멈출 시점을 정교하게 고를 필요가 없다고 말한다(Section 5).
확인 상태: viewed

Figure 7 — 교란 복구와 고정점 수렴

무엇을 보여주는가: 왼쪽은 prefix sum에서 50회 뒤 비트 하나를 뒤집었을 때 다시 정답에 이르기까지의 평균 반복 수, 가운데는 13×13 미로에서 50회 뒤 특징을 다른 미로의 것으로 바꿨을 때의 정확도, 오른쪽은 13×13 미로에서 반복마다의 특징 변화량 Δφ.
읽는 법: 왼쪽 x축 뒤집은 비트 위치(0–40), y축 Avg. Iters To Solution. 가운데 x축 반복(0–150), y축 정확도, “Features swapped”와 “Solutions recovered” 화살표 표시. 오른쪽 x축 반복, y축 Δφ(로그, 10⁻⁶–10¹⁰).
핵심 관찰: 왼쪽에서 복구 반복 수는 위치가 뒤로 갈수록 선형으로 줄고(DT-Recall 약 32 → 약 5, DT-Recall Prog. 약 21 → 약 5), progressive 모델이 더 빨리 복구한다. 가운데에서 교체 직후 정확도가 0%로 떨어졌다가 약 100회 근처에서 recall 모델이 다시 거의 100%로 회복한다. 오른쪽에서 DT는 Δφ가 약 10¹⁰ 이상으로, DT Prog.는 약 10⁴ 수준으로 커지고, recall 모델 두 개는 약 10⁻⁵까지 줄어든다(그래프 판독, analyst-inference).
의미와 주의: 저자 해석은 네트워크가 계속 입력과 현재 해를 비교하며, recall 모델은 수렴하고 recall 없는 DT는 폭발한다는 것(Section 5.2–5.3, author-stated). 왼쪽 패널에는 recall 없는 모델이 나오지 않는다. 뒤의 비트일수록 바뀌는 출력 비트가 적다는 설명이 선형 감소의 이유로 제시된다.
확인 상태: viewed

Wiki 연결

Deep Equilibrium Models — 반복을 고정점으로 정의하고 입력을 매 반복 주입하는 선행 아이디어. 이 논문의 recall과 “고정점 수렴” 해석이 같은 축에 있다.
Fixed-Point Reasoners - Stable and Adaptive Deep Looped Transformers — overthinking 없이 많이 반복하고 고정점 수렴을 멈춤 기준으로 삼는 looped transformer 후속 계보.
Reasoning with Latent Thoughts - On the Power of Looped Transformers — 반복 블록으로 깊이를 대신하는 looped 모델의 추론·외삽 분석.
Less is More - Recursive Reasoning with Tiny Networks — 작은 네트워크를 재귀 반복하고 일부 단계만 역전파해 퍼즐을 푸는 설계로, progressive loss의 “기울기를 끊은 부분 반복 학습”과 비교해 읽을 만하다(analyst-inference).

BibTeX

@inproceedings{bansal2022endtoend,
  title     = {End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking},
  author    = {Bansal, Arpit and Schwarzschild, Avi and Borgnia, Eitan and Emam, Zeyad and Huang, Furong and Goldblum, Micah and Goldstein, Tom},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year      = {2022},
  eprint    = {2202.05826},
  archivePrefix = {arXiv}
}