“탐색과 학습된 백트래킹으로 ‘생각의 흐름’을 새로 쓰다: AI 추론 학습의 혁신 ‘Diligent Learner’ 리뷰”

안녕하세요, 여러분! 오늘은 최근 나온 아주 흥미로운 논문 한 편을 가지고, 이야기해 보려고 해요. 제목은 “From Reasoning to Super-Intelligence: A Search-Theoretic Perspective”이며,  2025년에 발표란 논문입니다.

---

1. 왜 ‘Chain-of-Thought’ 학습이 어려울까요?

최근 LLM(대형언어모델)들이 ‘Chain-of-Thought(CoT)’ 즉, 생각의 흐름을 따라 문제를 단계적으로 푸는 능력을 갖추면서 많은 주목을 받고 있어요. 하지만, CoT 데이터를 활용해 모델을 잘 학습시키는 이론적 기반은 아직 미흡한 상태입니다.

논문에서는 대표적인 기존 방법들

• Supervised Fine-Tuning(SFT)
• Reinforcement Learning(RL)
• Tree-of-Thoughts(ToT)
• Monte Carlo Tree Search(MCTS)

이런 알고리즘들이 복잡한 문제 앞에서는 성능이 급락하고 실패하는 이유를 ‘배포 드리프트(distribution drift)’, ‘탐색 부족’, ‘지수적 계산 비용’ 등으로 짚어주었어요.

---

2. 기존 방법과 ‘Diligent Learner(성실한 학습자)’의 큰 차이

문제점 기존 방법들 Diligent Learner

배포 드리프트	SFT, RL 기반: 훈련 시 완벽한 데이터를 보고, 테스트 때는 오류 누적 가능성 커져 실패	DFS with backtracking 내장, 학습과 추론 시 분포가 유사하도록 설계
탐색 부족	ToT BFS/DFS, MCTS: 탐색공간 폭발하거나 우수한 rollback 전략 부재	학습 가능한(backtracking 가능한) 탐색 트리 구조 명시적 학습
지수적 시간 복잡도	MCTS 및 RL: 보상 신호 희박해 학습 힘듦	조건부 학습 및 ‘역 커리큘럼’(reverse curriculum)으로 효율적 탐색 가능

 

특히 백트래킹(backtracking)을 명확히 학습하는 점이 기존 ToT-DFS가 항상 부모 노드로 돌아가는 단순한 백트래킹과 완전히 다르죠! 늦게라도 실패 판정을 내리면 과거 여러 단계로 한꺼번에 돌아갈 수 있어, 훨씬 효율적입니다.

---

3. 기술적 뽀인트: ‘아주 약한 조건’으로 증명한 효율적 학습 가능성

이 논문에서 내놓은 ‘CoT 얼러너빌리티(learnability)’를 위한 2가지 충분 조건이 있어요.

1. 생성모델(Generative model)이 올바른 다음 논리 단계를 일정 확률(γ) 이상으로 생성할 수 있을
   – 즉, 완벽한 예측이 아니라 확률적 성공 가능성만 있으면 됩니다.
2. 긴 잘못된 추론이 들어오면, 학습 가능한 방식으로 올바른 단계까지 백트래킹할 수 있을 것
   – 바꾸어 말하면, 실패했을 때 “돌아가서 다른 시도를 해봐야 한다”를 학습해야 합니다.

이 두 가지만 만족하면, ‘Diligent Learner’는 효율적으로 검색 기반 CoT 학습이 가능하다고 엄밀하게 증명합니다.

---

4. 흥미로운 예시: 숫자 곱셈과 최단경로 문제

• 곱셈 문제 →  ‘성실한 학습자’는 이 과정도 이론적으로 뒷받침하죠.
• 순수 SGD 사전학습 모델은 단순히 입력 → 출력 몽땅 한 번에 배우려면 ‘지수적’ 학습 시간이 걸립니다. 하지만 CoT로 곱셈 과정을 쪼개서 가르치면 훨씬 빨리 배웁니다.
• 최단경로 문제 with 그래프 탐색 →  ‘성실한 학습자’는 정확히 어떤 노드로 되돌아갈지 배우고 활용하기 때문에 이러한 문제도 효율적 학습이 가능합니다.
• 이 문제는 탐색과 백트래킹 없이는 제대로 풀기 힘든데, ToT 방식 BFS는 얕은 층만 먼저 답 보고 벽에 부딪히고, DFS는 단순히 부모로만 돌아가서 다시 풀어보고 하기에 결국 탐색 공간이 폭발합니다.

---

5. 기존 연구와 차별점: 학습이냐 탐색이냐, 그리고 분포 드리프트 극복

연구 토큰별 정확성 가정 탐색 내장 여부 분포 드리프트 해소 학습 방식

Malach et al. (2023)	완전 결정론적	X	X	SFT
Yao et al. (2023) ToT	약간 희미함	일부 (BFS, DFS)	X	프롬프트 + BFS/DFS
Kim et al. (2025) ASTRO	MCTS로 일부 검색 생성	포함	제한적	MCTS + RL
Xi et al. (2024) R3	단계적 커리큘럼	X	일부	Reverse Curriculum + RL
본 논문 ‘Diligent Learner’	확률적 생성(γ-GPAC)	완전 내장 + 학습 백트래킹	완전 극복	탐색+백트래킹 명시+역커리큘럼

기존 논문들은 토큰 단위 결정론적 예측을 가정하거나, 탐색을 제대로 내장하지 못하고, 분포 드리프트 문제에 취약했어요.

반면, ‘Diligent Learner’는 ‘생성 확률만 있으면 된다(γ-GPAC learnability)’로 이론적 기준을 완화해 더욱 현실 데이터와 유사한 조건에서 ‘탐색과 백트래킹’을 명확히 내장하고, ‘역 커리큘럼’을 통해 매우 어려운 문제에서도 학습 가능함을 보였습니다.

---

6. 마무리 – AI 추론 학습의 새로운 길

이번 논문이 보여준 점은 매우 간단한데요, 바로 “추론 과정은 단순한 순차예측이 아니라, 탐색(Search)과 실패 인지(Failure detection), 그리고 학습된 백트래킹(Backtracking)의 조합이어야 한다!” 라는 것입니다. 그리고 그렇게 하는 게 수학적으로 증명도 되어 있고, 실제 어려운 문제에 필요하다는 거죠.

ML 커뮤니티에서 ‘Chain-of-Thought’라고 하면 그냥 일련의 텍스트 단계들을 예측하는 것 같지만, 실제로는 그 안에 복잡한 ‘트리 탐색’과 ‘포기 및 되돌아감’이 있어야만 진짜 학습이 가능하다는 엄정한 메시지를 담고 있습니다.

게다가, 곱셈, 그래프 최단경로 같은 고전적 문제를 풀 수 있다는 점은, 앞으로 언어모델들이 좀 더 인간 지능에 가까운 ‘초지능’ 단계로 넘어가는 데 중요한 기술적 밑거름이 될 것 같습니다.

---

[좀 더 깊이 탐구하고 싶은 분들을 위한 팁]

• ‘Diligent Learner’는 SFT 이후 후보 생성 → 보상에 따른 백트래킹 → 다시 SFT 반복의 구조를 가집니다.
• ‘백트래킹 대상 노드’ 선택까지 학습하는 게 정말 핵심! DFS, BFS, MCTS와 다른 점이에요.
• 논문 부록에서는 ‘곱셈 어려움 증명’ 위해 ‘푸리에 변환’과 ‘Parseval’s inequality’ 일반화 등 독특한 수학적 접근법도 볼 수 있어요.

---

혹시 AI 추론 학습에 관심 있고, ‘왜 GPT-4 같은 LLM도 가끔 엉뚱한 답을 내는지’ 궁금했다면 이번 논문은 정말 꼭 읽어볼 가치가 있다고 감히 말씀드리고 싶어요!

추론 학습의 다음 단계, 그리고 인공지능의 초지능 시대에 대한 귀중한 단초가 될 것이라 확신합니다.

---

읽어주셔서 감사합니다 😊

궁금한 점이나 의견 있으시면 댓글로 나눠주세요!