Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently

기술 요약: 추론 모델에서 SFT 대비 RLVR의 증명 가능한 이점

문제 정의
본 연구는 왜 검증 가능한 보상을 사용하는 강화 학습(RLVR)이 전문가 시연을 통한 지도 미세 조정(SFT)보다 더 우수한 추론 능력을 발휘하는지에 대한 근본적인 간극을 다룹니다. 경험적 증거는 RLVR 모델이 더 잘 일반화하고 더 강력한 추론 능력을 보여준다는 것을 시사하지만, 이러한 차이를 설명하는 원칙적인 이론적 프레임워크는 부족했습니다.

저자들은 사고 사슬(Chain-of-Thought, CoT) 추론을 특정 멀티그래프(multigraph) 구조 상의 경로 탐색 문제로 모델링합니다. 이 그래프는 소스 노드, $W$개의 서로 다른 경로로 갈라지는 포크(fork) 노드, 그리고 각 브랜치를 따라 $K$개의 순차적인 "다이아몬드" 서브그래프로 구성됩니다. 각 다이아몬드는 $L$개의 병렬 멀티에지(multiedges)를 포함합니다. 추론 작업은 소스에서 특정 타겟 리프 노드로 탐색하는 것입니다. 결정적으로, 이 그래프는 효율적인 탐색을 위해 막다른 길(잘못된 브랜치 진입)을 감지하고, 대안 브랜치를 탐색하기 위해 포크로 효율적으로 되돌아가는(backtracking) 능력이 필요하도록 설계되었습니다.

방법론
본 논문은 사전 훈련된 바이그램(bigram) 모델(세계 모델을 나타냄)에 적용되는 두 가지 사후 훈련 패러다임을 비교하는 동역학적 분석을 제공합니다.

1. 지도 미세 조정 (SFT): 모델은 소스에서 타겟으로 가는 "골든(golden)" 최단 경로 궤적에 대해 훈련됩니다. 이 궤적에는 되돌아가기, 탐색 또는 실패한 시도가 포함되지 않으며, 오직 올바른 전방 경로만을 보여줍니다. 훈련 목적 함수는 표준 교차 엔트로피 손실(cross-entropy loss)입니다.
2. 검증 가능한 보상을 사용하는 강화 학습 (RLVR): 모델은 온-폴리시(on-policy) 롤아웃을 통해 훈련됩니다. 보상 함수는 결과 보상(타겟 도달)과 길이 패널티(길고 비효к적인 경로를 억제하기 위함)를 결합합니다. 모델은 정책 경사(policy gradient) 업데이트, 특히 부호가 있는 경사 흐름(signed gradient flow)의 동역학을 분석하며 학습합니다.

저자들은 특정 에지 상태에 대한 전이 확률의 진화를 분석합니다:

• 전방 상태 (Forward states): 브랜치 내부로 더 깊숙이 이동함.
• 후방 상태 (Backward states): 포크를 향해 뒤로 이동함 (되돌아가기).

그들은 SFT와 RLVR 하에서의 이러한 전이를 제어하는 로짓(logits)에 대한 경사 흐름 동역학을 유도하며, 유한한 시간 내의 수렴 특성을 증명합니다.

주요 기여 및 결과

1. SFT의 되돌아가기 학습 실패:
   저자들은 골든 최단 경로로만 훈련된 SFT가 효율적인 되돌아가기 전략을 학습하는 데 실패함을 증명합니다. 훈련 데이터에 막다른 길이나 후퇴의 필요성이 전혀 노출되지 않기 때문에, 되돌아가기 상태에 대한 전이 확률은 사전 훈련된 균등 값(uniform values)으로 고정되어 있습니다. 모델은 확률 1로 전진하는 법은 배우지만, 브랜치가 잘못되었을 때 효율적으로 후퇴할 메커니즘은 보유하지 못합니다.

2. RLVR의 되돌아가기 학습 성공:
   이와 대조적으로, 저자들은 RLVR로 훈련된 모델이 효율적으로 되돌아가는 법을 배운다는 것을 증명합니다. RLVR의 온-폴리시 특성은 모델이 실패한 롤아웃(막다른 길)을 생성하고 경험하도록 강제합니다. 길이 패널티는 길고 헤매는 경로를 명시적으로 패널티를 부여하여, 막다른 길에서 뒤로 이동하는 것이 타겟에 빠르게 도달하기 위해 필요한 행동임을 모델이 학습하도록 유도합니다. 모델은 전방 및 후방 전이 확률이 모두 1에 가까워지는 정책으로 수렴하며, 즉 브랜치를 탐색하고 그것이 타겟이 아니면 즉시 후퇴하는 법을 효과적으로 학습합니다.

3. 추론 시간 계산량의 지수적 격차:
   본 논문은 타겟을 찾는 데 필요한 기대 추론 시간(hitting time)의 차이를 입증합니다:

• RLVR 모델: 기대 시간 $\Theta(WK)$가 소요됩니다. 모델은 브랜치를 순차적으로 탐색하며, 각 브랜치를 $O(K)$ 시간에 탐색하고 실패 시 즉시 후퇴합니다.
• SFT 모델: 기대 시간 $\Theta(WLK)$가 소요됩니다. SFT 모델은 효율적으로 되돌아갈 수 없기 때문에(되돌아가는 에지를 $L$개의 옵션 중 하나인 무작위 보행으로 취급함), 잘못된 브랜치를 벗어나는 데 $O(LK)$ 시간이 걸립니다.
• 이는 그래프의 깊이($K$)에 대해서는 지수적 격차를, 다이아몬드의 브랜칭 팩터($L$)에 대해서는 선형적 격차를 나타냅니다.

4. 추론 궤적의 증류 (Distillation of Reasoning Traces):
   저자들은 RLVR 모델에 의해 생성된(되돌아가기 단계를 포함한) 추론 궤적을 통해 RLVR의 이점을 베이스 모델로 전이할 수 있음을 보여줍니다. 베이스 모델이 이러한 궤적에 대해 미세 조정되면 효율적인 되돌아가기 능력을 상속받아 $\Theta(WK)$의 추론 시간 복잡도를 회복합니다. 이는 핵심 요소가 RL 알고리즘 자체가 아니라, 훈련 세트에 되돌아가기 데이터가 포함되었는지 여부임을 시사합니다.

의의 및 주장
본 논문은 RLVR이 SFT보다 추론 작업에서 우월한 이유가 온-폴리시 탐색을 통한 효율적인 되돌아가기 학습 능력에 있다는 최초의 이론적 증명을 제공한다고 주장합니다. 저자들은 전문가 시연에 대한 SFT가 본질적으로 제한적인데, 그 이유는 "부정적 공간(negative space)"(실패한 경로)에 대한 노출이 부족하여 모델이 오류로부터 효율적으로 회복할 수 없기 때문이라고 설명합니다.

본 연구는 다음을 강조합니다:

• 되돌아가기는 학습 가능한 기술이다: 이는 아키텍처의 내재적 속성이 아니라 훈련 신호에 의해 유도되는 행동입니다.
• 데이터 구성이 중요하다: (RL 탐색이나 증류를 통한) 훈련 데이터에 실패한 시도와 되돌아가기 단계가 포함되는 것은 탐색 복잡도를 줄이는 데 필수적입니다.
• 이론적 근거: 결과는 RLVR이 왜 더 잘 일반화되는지에 대해 경험적 관찰을 넘어, 동역학계(dynamical systems) 관점의 이론적 근거를 제공합니다.

저자들은 증류를 통해 이러한 능력을 전이할 수 있지만, RLVR 프로세스가 효율적인 되돌아가기를 학습하는 데 필요한 데이터를 생성하는 근본적인 메커니즘이라고 결론짓습니다. 이 결과는 복잡한 다단계 과업에서 LLM의 추론 능력을 향상시키기 위해 RLVR을 사용하거나 RL 생성 궤적을 증류하는 것이 유용함을 뒷받침합니다.