Recurrent Reasoning on Symbolic Puzzles with Sequence Models

기술 요약: 시퀀스 모델을 이용한 기호적 퍼즐의 재귀적 추론

문제 정의
대규모 언어 모델(LLM)은 기호 및 알고리즘 작업에서 외견상 숙련된 모습을 보이기도 하지만, 이러한 성능은 종종 문제가 길어지거나, 난이도가 높아지거나, 훈련 분포에서 약간 벗어날 때 나타나는 취약한 동작을 은폐한다. 현재의 추론 벤치마크는 유효한 최종 답안을 생성하는 것보다 솔루션 과정의 견고성, 최소성, 그리고 안정성을 우선시하는 경향이 있다. 본 논문은 알고리즘 문제의 경우, 정답성(correctness)이란 단순히 그럴듯한 종착점을 만드는 것이 아니라, 유효한 중간 행동을 반복적으로 선택하고, 불법적인 전이를 피하며, 긴 호라이즌(horizon) 동안 일관성을 유지하는 능력을 의미한다고 주장한다. 저자들은 알고리즘적 추론이 얕은 패턴 매칭과 진정한 견고성을 구분할 수 있는 핵심적인 설정이라고 상정한다.

방법론: RecurrReason 벤치마크
이러한 한계를 해결하기 위해, 저자들은 네 가지 재귀적 논리 퍼즐로 구성된 난이도 제어 벤치마크인 RecurrReason을 도입한다:

1. 블록 월드 (Block World): 스택 내의 블록들을 재배치함.
2. 체커 점프 (Checkers Jumping): 선형 보드 위에서 빨간색과 파란색 체커의 위치를 바꿈.
3. 하노이의 탑 (Tower of Hanoi): 크기 제약 조건에 따라 디스크를 페그(peg) 사이로 이동함.
4. 강 건너기 (River Crossing): 안전 제약 조건을 준수하며 행위자-에이전트 쌍을 강 너머로 운반함.

이 벤치마크는 다음과 같은 특성을 갖도록 구축되었다:

• 확장 가능한 난이도: 각 퍼즐은 $N \in \{1, \dots, 10\}$인 단일 정수에 의해 매개변수화된다.
• 최적 궤적: 모든 인스턴스는 너비 우선 탐색(BFS)을 사용하여 최적의 궤적을 생성하며, 총 10,817개의 고유한 퍼즐과 285,933개의 이동(move)을 포함한다.
• 태스크 정식화: 태스크는 "다음 단계 예측" 문제로 프레임화된다. 모델은 현재 상태($s_t$)와 목표 상태($g$)를 전달받고 다음 상태($s_{t+1}$)를 예측해야 한다. 평가는 정답 중간 상태 없이 자기회귀적 롤아웃(autoregressive rollouts)을 통해 이루어진다.
• 평가 프로토콜: 모델은 $N=1$부터 $7$까지의 인스턴스로 학습되며, 홀드아웃(held-out) 인-데이터스트리션(in-distribution) 인스턴스($N=1$부터 $7$) 및 아웃-오브-데이터스트리션(OOD) 인스턴스($N=8$부터 $10$)에서 평가된다. 평가지표는 궤적 성공률, 이동의 적법성, 그리고 최적성 격차(optimality gap)를 포함한다.

실험 설정
본 연구는 일관된 데이터 분할 및 훈련 조건(scratch, zero-shot, fine-tuned) 하에서 두 가지 트랜스포머 계열을 벤치마킹한다:

1. T5 스타일 (Encoder-Decoder): 60M 파라미터 모델(T5-small)로, 인코더는 결합된 상태와 목표에 대해 양방향 어텐션을 계산하여 목표를 매 단계마다 "제1순위" 조건화 신호로 만든다.
2. GPT-2 스타일 (Decoder-Only): 인과적 마스크(causal mask)를 사용하는 124M 파라미터 모델(GPT-2)로, 이는 현재 상태 토큰이 (시퀀스 뒤에 등장하는) 목표 토큰을 어텐션하는 것을 방지하여 목표 지향적 계획을 위한 구조적 병목을 생성한다.

주요 결과
실험 결과, 퍼즐의 구조가 모델의 규모나 사전 학습보다 학습 가능성에 더 강력한 결정 요인임이 드러났다:

• 블록 월드 성공: 미세 조정된 사전 학습 T5 모델은 97.27%의 검증 정확도와 81.00%의 OOD 정확도를 달ید했다. 이러한 성공은 퍼즐의 국소적 전이 함수(스택의 상단만 확인하는 $O(1)$ 복잡도), 선형 솔루션 길이 성장($L(N) = O(N)$), 그리고 조밀한 훈련 신호 덕분이다.
• 기타 퍼즐에서의 실패:
  • 강 건너기: 모든 조건에서 모든 모델이 0.00%의 점수를 기록했다. 이 퍼즐은 매 단계마다 전역적 제약 검증($O(N)$)을 요구하며 조합적인 행동 공간을 가지고 있어, 모든 아키텍처를 좌절시켰다.
  • 하노이의 탑: 모델들은 최대 11.11%의 검증 정확도(오직 사소한 $N=1$ 케이스에서만)를 기록했으며, OOD에서는 0.00%를 기록했다. 지수적인 솔루션 길이($2^N - 1$)가 오차 누적(compounding errors)을 일으켜 $N=1$ 이상의 일반화를 방해한다.
  • 체커 점프: 모델들은 최대 1.11%의 검증 정확도를 기록했으며, 시작 상태가 목표 상태와 동일한 사소한 인스턴스만을 해결했다. 이차적인 솔루션 길이와 데드엔드(dead-ends)를 피해야 하는 필요성이 극복 불가능한 것으로 판명되었다.
• 아키텍처 vs 규모: 더 작은 T5 모델(60M)이 더 큰 GPT-2 모델(124M)을 유의미하게 압도했다. 저자들은 이를 인코더-디코더 아키텍처가 목표에 대해 양방향으로 어텐션할 수 있는 능력 때문으로 보며, 반면 디코더 전용 모델의 인과적 마스크는 계획을 위한 구조적 병목을 만든다고 설명한다.
• 사전 학습 전이: 사전 학습의 이점은 국소적 구조의 전이 함수를 가진 퍼즐(블록 월드)에서만 관찰되었다. 전역적 제약이 필요한 퍼즐(강 건너기)이나 재귀적 분해가 필요한 퍼즐(하노이의 탑)에는 전이 효과가 없었다.

실패 모드 분석
저자들은 퍼즐 구조와 상관관계가 있는 특정 실패 모드를 식별했다:

• 무효한 이동 (Invalid Moves): 전역적 제약이 있는 퍼즐(하노이의 탑, 강 건너기)에서 지배적인 실패 원인으로, 제약 조건의 일반화 실패를 나타낸다.
• 루프 (Loops): 디코더 전용 모델의 블록 월드에서의 주요 실패 모드로, 목표 지향적 선택 없이 부분적인 규칙 학습만 이루어졌음을 시사한다.
• 조기 중단 (Premature Stops): 하노이의 탑에서 GPT-2에서 관찰되었으며, 훈련 데이터 내의 중단 토큰(stop tokens)의 통계적 과대표집과 연관되어 있다.

의의 및 주장
본 논문은 아키텍처의 귀납적 편향(inductive biases)이 규모보다 중요하다고 주장한다. 구체적으로:

1. 구조적 결정론: 퍼즐의 학습 가능성은 세 가지 구조적 속성인 전이 국소성(transition locality), 행동 공간 크기, 그리고 솔루션 길이 성장으로 결정된다. 저자들은 성공 확률이 솔루션 길이에 따라 지수적으로 감소함을 보여주는 오차 누적 모델을 정식화한다 ($P \approx e^{-\epsilon L(N)}$).
2. 목표 조건화: 양방향 목표 조건화(T5와 같이)는 목표 지향적 계획에 필수적이며, 인과적 어텐션(GPT-2와 같이)은 더 큰 파라미터 수를 가졌음에도 불구하고 효과적인 계획을 방해하는 구조적 병목을 만든다.
3. 사전 학습의 한계: 사전 학습은 국소적으로 분해 가능한 구조를 가진 작업에만 전이되는 계층적 귀납적 편향을 부여한다. 이는 전역적 제약이나 재귀적 깊이를 다루는 능력을 본질적으로 갖추어 주지 못한다.
4. 향후 방향: 결과는 LLM의 신뢰할 수 있는 다단계 추론을 위해서는 단순히 모델 크기를 키우는 것이 아니라, 아키텍처 탐색 능력이나 명시적인 기호적 제약 검사가 필요함을 시사한다.

저자들은 결론적으로 RecurrReason이 길이 일반화, 목표 조건부 계획, 그리고 체계적인 알고리즘적 추론을 위한 아키텍처 요구 사항에 관한 향후 연구를 위한 통제된 테스트베드를 제공한다고 밝히고 있다.