🤖 AI

How Much Backtracking is Enough? Exploring the Interplay of SFT and RL in Enhancing LLM Reasoning

이 논문은 지도 미세 조정 웜업 단계에 백트래킹을 명시적으로 포함하는 것이 대규모 언 언어 모델의 강화 학습을 최적화하는 데 필수적이며, 백트래킹의 최적 깊이는 효과적인 비선형 트리 탐색 추론을 가능하게 하기 위해 작업 난이도에 따라 직접적으로 스케일링된다는 것을 입증한다.

원저자: Hongyi James Cai, Junlin Wang, Xiaoyin Chen, Bhuwan Dhingra

게시일 2026-08-11

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Hongyi James Cai, Junlin Wang, Xiaoyin Chen, Bhuwan Dhingra

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

로봇에게 미로를 푸는 법을 가르치고 있다고 상상해 보세요. 예전 방식이라면 로봇에게 단순히 "벽에 부딪힐 때까지 앞으로 가다가 오른쪽으로 돌아"라고 말했을 것입니다. 이것은 **지도 미세 조정(Supervised Fine-Tuning, SFT)**과 같습니다. 당신이 완벽한 예시를 보여주면, 로봇은 그것을 그대로 따라 하려고 노력하는 것이죠. 하지만 미로가 거대하고 뒤틀린 미궁이라서 무엇이 '옳은' 길인지 명확하지 않다면 어떻게 될까요? 로봇은 막다른 길에 들어서서 계속 전진하다가 결국 갇혀버릴 수도 있습니다.

이를 해결하기 위해 과학자들은 **강화 학습(Reinforcement Learning, RL)**을 사용하기 시작했습니다. 이것은 비디오 게임 코치를 떠올리게 합니다. 로봇이 미로를 풀려고 시도하면, 정답을 맞혔을 때 코치가 하이파이브(보상)를 해줍니다. 실패하면 코치는 "다시 해봐"라고 말합니다. 시간이 흐르면서 로봇은 다양한 경로를 탐색하는 법을 배우며, 때로는 가던 길이 잘못되었다는 것을 깨닫고 되돌아가는(backtracking) 법까지 익히게 됩니다. 최근 우리는 로봇들이 이 작업에 놀라울 정도로 능숙해지는 것을 목격했지만, 연구자들은 한 가지 의문에 빠졌습니다. 도대체 로봇은 어떻게 '되돌아가기'를 배우는 걸까? 그저 운 좋게 맞춘 걸까, 아니면 훈련 과정에 "잠깐, 내가 실수했구나, 다시 돌아가자"라고 말하게 만드는 어떤 비밀스러운 요소가 있는 걸까?" 이 질문은 매우 중요합니다. 만약 우리가 이 두뇌를 훈련하는 완벽한 레시피를 찾아낼 수 있다면, 복잡한 수학이나 논리 퍼즐처럼 훨씬 더 어려운 문제들도 길을 잃지 않고 해결할 수 있게 만들 수 있기 때문입니다.

이 논문인 "얼마나 많은 되돌리기가 필요한가?(How Much Backtracking is Enough?)"는 바로 그 미스터리를 파고듭니다. 듀크 대학교와 Mila의 연구진은 AI가 추론 과제를 수행할 때 찾아야 할 '골디락스(Goldilocks, 너무 과하지도 부족하지도 않은 딱 적당한 상태)' 지점을 찾고자 했습니다. 그들은 다음과 같이 질문했습니다. 강화 학습 게임을 시작하기 전에, AI에게 얼마나 많은 '되돌아가기'(실수를 깨닫고 다른 경로를 시도하기 위해 돌아가는 행위)를 보여주어야 하는가?

그들은 "Arc 1D"(그리드 패턴 찾기) 같은 쉬운 것부터 "Countdown"(숫자를 더해 목표값 만들기) 같은 중간 난이도, 그리고 "Sudoku"(그리드에 숫자 채우기) 같은 매우 어려운 것까지 총 8가지 유형의 논리 게임을 통해 아이디어를 테스트했습니다.

연구 결과는 다음과 같은 재미있는 비유를 통해 설명할 수 있습니다. AI를 훈련시키는 것은 등산객에게 숲을 항해하는 법을 가르치는 것과 같습니다.

"그냥 걷기" 방식 (순수 RL)

먼저, 그들은 등산객(AI)에게 지도도 없고 연습도 없이 그냥 숲으로 보내, 시행착오를 통해 스스로 배우게 했습니다(순수 RL).

결과: 등산객은 직선으로 걷는 법을 배울 수 있었고, 때로는 우연히 해결책을 발견하기도 했습니다. 하지만 정말 울창하고 까다로운 숲(예: 스도쿠)에서는 등산객이 제자리에서 뱅뱅 돌거나 길을 잃고 멈춰버렸습니다. 그들은 막다른 길에 부딪혔을 때 되돌아가는 법을 알아내지 못했습니다.

"지도를 복사하기" 방식 (표준 SFT)

다음으로, 그들은 등산객에게 성공적인 여정이 담긴 지도를 주었습니다(자기 샘플링 SFT). RL 훈련이 시작되기 전에 AI가 스스로 생성한 경로를 바탕으로 연습하게 했습니다.

결과: 이것은 도움이 되었습니다! 등산객은 걷는 법이 조금 더 나아졌습니다. 하지만 가장 어려운 숲에서는 이것만으로 충분하지 않았습니다. 등산객은 여전히 길을 잃었을 때 어떻게 대처해야 하는지 알지 못했습니다. 이는 마치 등산객에게 단순한 경로가 그려진 지도를 준 뒤, 곧바로 정글 속에 떨어뜨려 놓은 것과 같았습니다.

"되돌아가는 법 배우기" 방식 (합성 되돌아가기)

여기서 마법이 일어났습니다. 연구진은 핵심이 단순히 AI에게 '올바른' 경로를 보여주는 것이 아니라, AI가 실수를 저지르고, 그것을 깨닫고, 다시 돌아가는 경로를 보여주는 데 있다는 것을 깨달았습니다. 그들은 AI가 다음의 특정 기술을 연습하도록 강제하는 "합성(synthetic)" 훈련 데이터를 만들었습니다.

경로를 따라 내려간다.
그것이 틀렸음을 깨닫는다.
"잠깐!"이라고 외치며 마지막 안전한 지점으로 되돌아간다.
다른 경로를 시도한다.

그들은 이 연습의 "깊이"를 다르게 하여 테스트했습니다.

쉬운 숲 (Arc 1D): 등산객은 되돌아가는 연습을 전혀 할 필요가 없었습니다. 사실, 되돌아가는 법을 보여주는 것이 오히려 속도를 늦추게 만들었습니다. 가장 좋은 전략은 그냥 완벽하고 곧은 경로를 보여주는 것이었습니다. **'되돌아가기 0회'**가 승자였습니다.
중간 난이도의 숲 (Countdown): 등산객은 딱 한 번의 되돌아가기 연습이 필요했습니다. 계산 결과가 이상해 보이면 멈추고 다른 조합을 시도해야 한다는 것을 배워야 했습니다. 한 번의 되돌아 가기가 최적의 지점이었습니다.
매우 어려운 정글 (Sudoku): 등산객은 다섯 번 이상의 되돌아가기 연습이 필요했습니다. 이 퍼즐들은 너무 복잡해서 해결책을 찾으려면 자신의 작업을 아주 여러 번 되돌릴 준비가 되어 있어야 합니다. 만약 한 번만 되돌아가도록 가르쳤다면, 그들은 여전히 막혀버렸을 것입니다.

핵심 결론

이 논문은 **"하나의 사이즈가 모두에게 맞지는 않는다(one size does not fit all)"**는 사실을 밝혀냈습니다.

쉬운 과제에 대해 AI에게 되돌아가기를 너무 많이 가르치면, 혼란에 빠져 성능이 떨어집니다.
어려운 과제에 대해 되돌아가기를 충분히 가르치지 않으면, 포기하게 됩니다.
"완벽한" 되돌아가기의 양은 퍼즐의 난이도에 전적으로 달려 있습니다.

또한 놀라운 사실을 발견했습니다. 그 과정의 "되돌아가기" 구조만 갖춰져 있다면, 연습용 지도가 틀려도 상관없다는 것입니다. 설령 AI에게 실수가 가득한 경로를 보여주더라도, 그 안에 "잠깐, 다시 돌아가자"라는 단계가 포함되어 있다면, AI는 단순히 직선 경로만 보여줬을 때보다 퍼즐을 더 잘 풀게 됩니다. 이는 아이에게 자전거 타는 완벽한 영상을 보여주는 대신, 직접 넘어지고 다시 일어서는 법을 가르치는 것과 같습니다. 넘어지는 과정에서 회복하는 행위 자체가 근육 기억을 만드는 것입니다.

결국, 저자들은 AI가 복잡한 추론에 진정으로 똑똑해지려면, 단순히 정답을 보여주는 것을 넘어 실수로부터 회복하는 법을 가르쳐야 한다고 제안합니다. 과제의 난이도에 맞춰 "되돌아가기" 노브를 조절함으로써, 우리는 훨씬 더 높은 수준의 지능을 끌어낼 수 있으며, 이를 통해 작은 모델조차도 이전에는 거대하고 강력한 컴퓨터가 필요했던 퍼즐들을 해결할 수 있게 만들 수 있습니다.

기술 요약: 백트래킹은 얼마나 충분한가? LLM 추론 향상을 위한 SFT와 RL의 상호작용 탐구

문제 정의

DeepSeek-R1 및 OpenAI의 o1과 같은 최근의 대규모 언어 모델(LLM)의 발전은, 강화 학습(RL)이 확장된 사고 체인(Chain of Thought, CoT)을 통해 탐색 전략을 내재화함으로써 추론 능력을 크게 향상시킬 수 있음을 보여준다. 하지만 백트래킹(이전의 추론 단계를 명시적으로 수정하는 것)은 이러한 개선의 핵심 메커니즘으로 널리 인식되고 있음에도 불구하고, 그 정확한 역학 관계는 여전히 잘 알려져 있지 않다. 특히, 지도 미세 조정(SFT) 웜업이 백트래킹을 최적화하기 위해 RL과 어떻게 상호작용하는지, 표준적인 자기 샘플링(self-sampled) CoT 웜업이 복잡한 작업에 충분한지, 그리고 문제 난이도에 따른 최적의 백트래킹 빈도 또는 깊이는 무엇인지가 불분명하다. 기존의 접근 방식들은 종로가 없는 "콜드 스타트(cold-start)" RL이나 단순한 자기 샘플링 CoT에 의존하는 경우가 많으며, 저자들은 이것이 수도쿠(Sudoku)와 같이 조합론적으로 복잡한 작업에서 정체 현상을 겪는다고 주장한다.

방법론

저자들은 Qwen2.5 및 Llama3.2 모델을 사용하여 8가지 추론 작업(Countdown, Sudoku, Arc 1D, Advanced Geometry, Color Cube Rotation, List Functions, Zebra Puzzles, Self Reference)에 걸쳐 통제된 실험을 수행한다. 이 연구는 서로 다른 SFT 웜업 전략이 후속 RL 훈련에 미치는 영향을 격리하여 분석한다:

베이스라인 비교: 저자들은 "순수 RL(Pure RL)"(SFT 웜업 없음)과 "콜드 스타트 RL(Cold-start RL)"(기본 모델의 자기 샘서플링된 CoT를 웜업으로 사용)을 비교한다. 또한, 올바른 궤적(trajectories)에서 유도된 웜업과 잘못된 궤적에서 유도된 웜업을 추가로 구분한다.
합성 백트래킹 데이터셋: 백트래킹을 체계적으로 연구하기 위해, 저자들은 조절 가능한 백트래킹 깊이( $k$ $k$ )를 가진 세 가지 대표 작업(Countdown, Arc 1D, Sudoku)에 대한 합성 데이터셋을 구축한다.
- Countdown 및 Sudoku의 경우, 연산 트리 또는 그리드 채우기를 생성하기 위해 깊이 우선 탐색(DFS) 솔버를 사용하여, 명시적인 "우회(detours)"(잘못된 분기)와 그에 따른 회복(백트래킹)이 포함된 궤적을 생성한다.
- Arc 1D의 경우, 수작업으로 제작된 변환 함수를 이용한 휴리스틱 탐색을 사용하여 유사한 백트래킹 패턴을 생성한다.
- 저자들은 $k$ -백트래킹 궤적을 모델이 오류 발생 후 유효한 상태로 돌아오는 $k$ 번의 명시적 회복 이벤트가 포함된 것으로 정의한다.
훈련 파이프라인: 모델은 먼저 이러한 합성 또는 자기 샘플링된 데이터셋에 대해 SFT 훈련을 거친 후, 규칙 기반 보상(형식 정확도 + 정확한 정답 일치)을 사용하는 RL 훈련(PPO 또는 GRPO 활용)을 받는다.
절제 연구(Ablation Studies): 저자들은 프롬프트와 완료 문(completions)을 섞어서(shuffling) RL이 의미론적 노이즈(semantic noise)와 구문적 구조(syntactic structure)에 대해 갖는 민감도를 분석한다.

주요 기여

표준 웜업의 한계: 본 연구는 자기 샘플링된 CoT 웜업이 순수 RL보다 약간의 향상을 제공하긴 하지만, 기본 모델이 충분한 올바른 초기화 데이터를 생성할 수 없는 수도쿠와 같은 어려운 조합론적 작업에서는 효과적으로 확장되지 못함을 입증한다.
조절 가능한 하이퍼파라미터로서의 백트래킹: 저자들은 백트래킹이 선형 생성에서 비선형 트리 탐색으로 전환하기 위한 핵심 연산자임을 확립한다. 그들은 최적의 백트래킹 깊이가 작업에 따라 달라짐을 보여준다:
- Arc 1D (쉬움): 제로 백트래킹(최적의 데몬스트레이션)이 가장 좋다.
- Countdown (중간): 정확히 1회의 백트래킹이 최적이다.
- Sudoku (어려움): 안정적이고 효과적인 RL 훈련을 위해 5회 이상의 백트래킹이 필요하다.
합성 데이터의 효능: 보정된 백트래킹 깊이를 가진 합성 SFT 데이터로 구성된 "백트래킹 중심" 훈련 레시피는, 모델이 기본 추론 능력을 뛰어넘도록 지속적으로 밀어올리며 특정 작업에서 더 큰 사전 훈련된 추론 모델(예: QwQ-32B)을 능가한다.
잘못된 궤적에 대한 강건성: 저자들은 RL이 의미론적으로는 틀렸지만 형식적으로는 정렬된 Co트를 포함하는 웜업으로부터도 여전히 이득을 얻을 수 있음을 발견하였으며, 이는 구문적 스캐폴딩(탐색과 회복의 구조)이 RL 미세 조정을 위한 프라이밍(priming)으로서 충분하다는 것을 시사한다. 반대로, RL은 섞인(의미론적으로 일관성 없는) 데이터에 매우 민감하며, 이 경우 훈련이 정체된다.

결과

성능 향상: 수도쿠(Sudoku)에서 5회의 백트래킹으로 RL을 초기화했을 때, Qwen2.5-3B의 정확도는 14.4%(제로 백트래킹)에서 28.9%로, Qwen2.5-7B는 11.8%에서 32.1%로 향상되었다. 이 결과는 수도쿠에서 0.0%를 기록한 QwQ-32B 베이스라인을 넘어섰다.
작업별 최적화:
- Countdown: 1회 백트래킹 웜업이 가장 높은 보상과 최종 정확도(Qwen2.5-3B 기준 최대 69.7%)를 기록했으며, 이는 제로 백트래킹 및 고빈도 백트래킹 구성보다 우수한 성능을 보였다.
- Arc 1D: 제로 백트래킹(최적) 궤적이 가장 좋은 성능을 보였으며, 백트래킹은 오히려 성능을 저하시켰다.
일반화: 한 작업(예: Advanced Geometry)에 대한 훈련이 관련 작업(예: Zebra Puzzles)으로의 일반화를 유도했으나, 고도의 조합론적 문제에 대해서는 제한적이었다.
토큰 효율성: 연구는 합성 백트래킹 데이터셋이 더 길지만, 순수 RL이나 잘못된 콜드 스타트 시나리오에서 관찰되는 정체 현상과 비교하여 더 효율적인 RL 수렴을 가능하게 한다고 언급한다.

의의 및 주장

본 논문은 원칙적인 백트래킹이 복잡한 작업에 대한 LLM의 추론 능력을 향상시키는 데 필수적이라고 주장한다. 저자들은 백트래킹이 트리 탐색을 위한 일반적인 연산자로 작-용하여, 모델이 단순히 선형적으로 생성하는 것을 넘어 결함이 있는 부분 해법을 감지하고 회복할 수 있게 한다고 상정한다.

저자들은 효과적인 RL을 위한 "레시피"가 단순히 긴 CoT를 만드는 것이 아니라, 작업 난이도에 맞춰 적절한 수의 백트래킹을 포함하는 합성 SFT 데이터를 만드는 것이라고 주장한다. 이 접근 방식은 순수 RL이나 표준 웜업이 발견하지 못하는 탐색 전략을 모델이 내재화할 수 있도록 한다. 이 연구는 SFT와 RL 사이의 상호작용이 단순히 데이터의 양에 관한 것이 아니라, 웜업 단계에서 제공되는 추론 궤적의 구조에 관한 것임을 시사한다. 백트래킹 빈도를 하이퍼파라미터로 취급함으로써, 저자들은 LLM의 선형 생성과 효과적인 트리 탐색 사이의 간극을 메우고 탐색 동작을 최적화할 수 있는 제어 가능한 수단을 제공한다.