기술 요약: 학습을 통한 추론 (Curriculum II): 구성적 일반화 (Compositional Generalization)

1. 문제 정의

본 논문은 복잡한 문제를 더 단순한 하위 문제들의 해결책으로 결합하여 해결하는 능력인 **구성적 일반화(compositional generalization)**의 이론적 토대를 조사합니다. 이는 인공지능의 사고 사슬(Chain-of-Thought, CoT) 추론의 핵심 메커니즘입니다. 본 연구가 다루는 핵심 질문은 다음과 같습니다: 문제를 부분으로 분해하는 것이 왜, 그리고 언제 직접 해결하는 것보다 더 효율적인 학습을 가능하게 하는가?

이를 위해 저자들은 **세미오토마톤 시뮬레이션(semiautomaton simulation)**을 사용하여 문제를 정식화합니다. 세미오토마톤은 알려지지 않은, 마르코프 성질을 가진 정적 전이 함수 $\pi^*: S \times \Sigma \to S$에 의해 정의됩니다. 초기 상태 $s_0$와 입력 단어 $w_{1:T}$가 주어졌을 때, 목표는 $T$ 단계 후의 최종 상태 $s_T$를 예측하는 것입니다. 중간 상태 $s_{1:T}$는 사고의 사슬(chain of thought)을 구성합니다. 이 모델은 상태 추적, 정규 언어 인식, 모듈러 산술을 포괄합니다.

본 논문은 두 가지 특정 학습 환경을 연구합니다:

1. 대화형 사고 사슬 감독 (Interactive Chain-of-Thought Supervision, iSFT): 학습자는 계산의 임의의 단계 $t$에서 상태를 반환할 수 있는 오라클(oracle)에 접근할 수 있으며, 이때 비용은 1단위입니다. 목표는 낮은 오차를 가진 모델을 학습시키기 위해 필요한 오라클 쿼리 수(쿼리 복잡도)와 훈련 인스턴스 수(샘플 복잡도)를 최소화하는 것입니다.
2. 검증 가능한 보상을 이용한 강화 학습 (Reinforcement Learning with Verifiable Rewards, RLVR): 학습자는 짧은 길이 $B \ll T$의 인스턴스를 일정한 확률로 해결할 수 있는 사전 학습된 "약한" 참조 모델 $\pi_{ref}$와, 최종 상태 추측의 정답 여부를 확인하는 결과 검증기(outcome verifier)에 접근할 수 있습니다. 목표는 긴 호라이즌(horizon)에서 발생하는 성공 확률의 지수적 감소를 극복하고, 길이 $T$의 인스턴스를 효율적으로 해결하도록 참조 모델을 개선하는 것입니다.

2. 방법론

저자들은 긴 시퀀스를 더 짧은 하위 문제로 재귀적으로 분해하고, 이를 해결하는 법을 배운 뒤, 그 해결책들을 결합하는 오토커리큘럼(autocurriculum) 기반 접근 방식을 제안합니다. 이 접근 방식은 **구성(composition)과 부스팅(boosting)**의 템플릿을 활용하는 시리즈의 Part I을 계승합니다.

핵심 알고리즘 구성 요소

• 구성 (Composition): 길이 $\tau$의 인스턴스를 해결하도록 훈련된 모델은 길이 $T$의 인스턴스를 해결하기 위해 $L$번($T = L\tau$인 경우) 구성될 수 있습니다. 그러나 구성 과정에서 오차가 누적되므로, 단거리 모델은 높은 정확도로 훈련되어야 합니다.
• 부스팅 (Boosting): 단거리 하위 문제에서 필요한 높은 정확도를 달키 위해, 저자들은 다중 스케일 부스팅 전략을 사용합니다. 이는 현재의 앙상블이 실패하는 "어려운" 인스턴스에 집중하도록 가중치가 재조정된 분포에서 약한 학습기(weak learners)들을 훈련시키고, 이들을 결합(예: 다수결 투표)하는 과정을 포함합니다.
• 자기 생성 커리큘럼 (Self-Generated Curriculum): 고정된 스케줄 대신, 학습자는 더 미세한 스케일에서 훈련된 모델의 실패를 바탕으로 어떤 하위 문제를 훈련할지 적응적으로 선택합니다.

주요 기술적 혁신

• 역방향 샘플링 (Inverted Sampling): 부스팅 과정에서 발생하는 분포 변화(distribution shift)를 처리하기 위한 핵심적인 기술적 기여입니다. 가중치가 재조정된 주변 분포(marginals)의 혼합물로부터 수행하는 표준 거부 샘플링(rejection sampling)은 비효율적입니다(최악의 경우 $\Omega(L)$개의 샘플 필요). 저자들은 긴 시퀀스 내의 모든 $L$개 하위 인스턴스에 대해 독립적으로 거부 샘플링을 먼저 적용한 다음, 수락된 인스턴스 중 하나를 균등하게 선택하는 역방향 샘플링을 도입했습니다. 이는 학습 알고리즘의 충분한 근사 보장을 유지하면서도 수락 확률을 하위 인스턴스의 수에 비례하도록 만들어 샘플 복잡도를 크게 줄입니다.
• 다중 스케일 재귀 (Multiscale Recursion): 알고리즘(AutoLearn)은 부스팅 + 구성 템플릿을 재귀적으로 적용합니다. 이는 길이 $T$의 인스턴스를 길이 $\tau$의 하위 문제로 분해하고, 이를 다시 길이-1(다음 토큰 예측)에 도달할 때까지 더 작은 단위로 분해합니다. 이를 통해 짧고 쉬운 문제를 해결하는 모델들이 더 어려운 문제를 해결하도록 구성되는 계층 구조를 만듭니다.
• 추측 및 확인 (Guess-and-Check)을 위한 RLVR: 중간 상태 레이블을 직접 얻을 수 없는 RLVR 설정에서, 저자들은 약한 참조 모델과 검증기를 사용하여 대화형 오라클을 시뮬레이션합니다. 각 블록에 대한 롤아웃(rollout)을 생성하고 블록의 최종 상태를 검증함으로써, 중간 상태에 대한 레이블을 효과적으로 생성하여 커리큘럼을 구축합니다.

3. 주요 기여 및 결과

설정 I: iSFT (대화형 감독)

본 논문은 세미오토마톤을 아초다항식(subpolynomial) 쿼리 및 샘플 복잡도로 학습하는 AutoLearn 알고리즘을 제시합니다.

• 결과: 쿼리 및 샘플 복잡도는 $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$로 상한이 결정됩니다.
• 비교: 이는 직접적인 시뮬레이션 방식에 내재된 $\Omega(T)$ 장벽을 깨뜨립니다.
  • 전체 CoT 감독 (Full CoT Supervision): 모든 상태를 레이블링하기 위해 인스턴스당 $\Omega(T)$개의 쿼리가 필요합니다.
  • 엔드 투 엔드 피드백 (End-to-End Feedback): 중간 단계의 근거(grounding) 없이 최종 상태로부터 일반화할 수 없기 때문에 $\Omega(T)$의 샘플 복잡도가 필요합니다.
• 메커니즘: 적응적으로 하위 문제를 선택하고 역방향 샘플링을 사용하여 분포 변화를 관리함으로써, AutoLearn은 $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$의 복잡도를 달성하여 $T$에 대해 아초다항식의 복잡도를 실현합니다.

설정 II: RLVR (검증 가능한 보상)

본 논문은 약한 참조 모델 $\pi_{ref}$를 블록 수준의 역량($B$)에서 전체 길이의 역량($T$)으로 개선하는 AutoLearn.RL을 제시합니다.

• 결론: 알고리즘은 전체 길이 $T$가 아닌, 짧은 블록 길이 $B$에서의 참조 모델의 커버리지(coverage)에 의해 결정되는 비용으로 길이 $T$ 인스턴스에 대한 높은 정확도를 달성합니다.
• 커버리지 확장: 표준 RLVR 방식은 참조 모델이 길이 $T$에서 비자명한 커버리지를 가져야 하는데, 모델이 길이 $B$에서만 커버리지를 가질 경우 이는 매우 희박합니다 (즉, $C^{(T)}_{seq} \approx (C^{(B)}_{seq})^{T/B}$). AutoLearn.RL은 이 요구 사항을 길이 $B$에서의 커버리지로 낮춥니다.
• 복잡도:
  • 샘플 복잡도: $\tilde{\mathcal{O}}(d/\varepsilon)$.
  • 쿼리 복잡도: $\tilde{\mathcal{O}}(d/\varepsilon) + \tilde{\mathcal{O}}(\frac{T}{B} \cdot d C^{(B)}_{ans} + d C^{(B)}_{seq})$.
  • 계산 비용: $\tilde{\mathcal{O}}(dT/\varepsilon) + \tilde{\mathcal{O}}(dT C^{(B)}_{ans} + dB C^{(B)}_{seq})$.
• 의의: "번인(burn-in)" 비용은 짧은 스케일 $B$에서의 커버리지에 의존하므로, 길이 $T$에서의 유효 커버리지가 지수적으로 작은 값에서 상수로 확장될 수 있게 합니다.

4. 의의 및 주장

본 논문은 구성(composition)과 자기 생성 커리큘럼의 결려가 비-커리큘럼 베이스라인에 비해 초다항식적(superpolynomial) 감소를 달성할 수 있다고 주장합니다.

• 이론적 토대: 문제를 분해하는 것이 왜 도움이 되는지에 대한 엄밀한 이론적 프레임워크를 제공합니다. 즉, 구성을 통해 모델이 정확도 요구 사항과 시퀀스 길이 사이의 절충(trade-off)을 할 수 있게 하며, 부스팅은 하위 문제에 대한 필요한 정확도를 보장합니다.
• 효율성: 결과는 세미오토마톤 시뮬레이션과 같은 작업에서 학습이 $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ 복잡도로 달성될 수 있음을 보여주며, 이는 표준 접근 방식의 선형 $\Omega(T)$ 복잡도보다 획기적인 개선입니다.
• 일반화: 학습자가 스스로 문제를 설계하는 오토커리큘럼이 단순히 휴리스틱이 아니라, 장기 호라이즌 추론의 통계적 및 계산적 장벽을 극복하기 위한 정당한 메커니즘임을 이론적으로 입증합니다.
• 한계 및 향-후 과제: 저자들은 모델 클래스를 마르코프 모델로 제한(전체 히스토리 어텐션을 사용하는 트랜스포머 제외)하고 결정론적 전이를 가정하는 등의 단순화를 인정합니다. 이러한 결과를 비-마르코프 모델 및 확률적 전이로 확장하는 것이 향후 중요한 연구 방향임을 밝힙니다. 또한, 현재 결과가 $T$에 대해 아초다항식 의존성을 달성했지만, 다항 로그(polylogarithmic) 의존성을 달성하는 것은 유한한 실수 경계(finite mistake bounds)와 같은 더 강력한 가정이 필요할 수 있는 미해결 과제로 남겨두었습니다.

요약하자면, 본 논문은 구성적 일반화가 적응형 커리큘럼에 의해 유도되고 역방향 샘플링과 같은 기술에 의해 뒷받침될 때, 직접 학습 방법으로는 다루기 힘든 복잡한 순차적 작업을 학습하기 위한 효율적인 경로를 제공함을 입증합니다.