🤖 machine learning

Breaking the Capability Ceiling of LLM Post-Training by Reintroducing Markov States

이 논문은 LLM 후속 학습에서 '역사 (history) 를 상태 (state) 로 간주'하는 기존 접근법의 한계를 지적하고, 명시적인 마르코프 상태를 도입함으로써 샘플 복잡도를 줄이고 복잡한 논리 퍼즐 등에서의 성능 한계를 돌파할 수 있음을 이론적·실증적으로 증명합니다.

원저자: Yurun Yuan, Tengyang Xie

게시일 2026-03-23

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yurun Yuan, Tengyang Xie

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

🎒 1. 문제: "무거운 가방"을 들고 가는 AI

지금까지 AI 를 더 똑똑하게 만들기 위해 사용하는 방법 (강화 학습) 은 마치 매번 과거의 모든 기억을 가방에 넣고 다니는 사람과 같습니다.

기존 방식 (Action-Sequence): AI 가 문제를 풀 때, "내가 1 분 전에 무엇을 했는지, 2 분 전에 무엇을 했는지, 3 분 전에 무엇을 했는지..." 모든 과거의 행동 기록을 입력으로 받습니다.
문제점: 이 가방은 시간이 지날수록 너무 무거워집니다. AI 는 "지금 내가 어디에 있는지 (현재 상황)"를 파악하는 대신, "과거에 무엇을 했는지"를 기억하는 데 에너지를 다 써버립니다.
결과: AI 는 과거의 패턴을 조금 더 잘 반복할 뿐, **진짜 새로운 아이디어를 찾아내거나 복잡한 문제를 해결하는 데 한계 (Capability Ceiling)**에 부딪힙니다. 마치 무거운 가방을 멘 채로 달리기 경주를 하는 것과 같아서, 아무리 훈련해도 속도가 나지 않습니다.

🔑 2. 해법: "현재 상황"만 기억하는 마법

이 논문은 **"과거의 모든 기록은 버리고, 지금 이 순간의 상태 (Markov State) 만 기억하라"**고 제안합니다.

새로운 방식 (Markov State): AI 는 "내가 과거에 무엇을 했는지"가 아니라, **"지금 이 순간의 보드판 상태는 어떻게 생겼는지?"**만 봅니다.
비유: 체스나 바둑을 칠 때, "내가 100 수 전에 말을 어디에 뒀는지"를 다 기억할 필요가 없습니다. 중요한 건 **"지금 보드판에 말이 어떻게 놓여 있는지"**입니다. 이 '현재의 모습'이 모든 정보를 담고 있기 때문입니다.
효과: AI 는 불필요한 과거의 잡음 (노이즈) 을 버리고, 현재 상황에 집중하게 됩니다. 가방이 가벼워지니, AI 는 훨씬 더 빠르게 배우고, 더 복잡한 미로를 헤쳐 나갈 수 있게 됩니다.

🧩 3. 실험: 퍼즐을 푸는 두 명의 학생

연구자들은 이 아이디어를 검증하기 위해 수두 (Sudoku), 소코반 (Sokoban), 푸토시키 (Futoshiki) 같은 논리 퍼즐 게임을 만들었습니다.

학생 A (기존 방식): 과거의 모든 행동을 기억하며 문제를 풉니다.
- 결과: 간단한 문제는 풀지만, 문제가 조금만 복잡해지거나 길어지면 완전히 멈춰버립니다. (성공률 0% 에 수렴)
학생 B (새로운 방식 - Markov): 현재 보드판 상태만 보고 문제를 풉니다.
- 결과: 학생 A 가 포기한 어려운 문제도 훌륭하게 해결합니다. 특히 훈련 때 보지 못했던 더 어려운 문제 (OOD) 에도 잘 적응합니다.

📉 4. 왜 이렇게 효과가 좋은가요? (데이터 효율성)

이 방식은 배우는 데 필요한 데이터 양도 훨씬 적게 만듭니다.

기존 방식: 모든 가능한 과거의 행동 조합을 다 경험해봐야 하므로, 데이터가 지수함수적으로 (엄청나게) 많이 필요합니다. (예: 10 단계 퍼즐을 풀려면 100 만 번 이상 시도해야 함)
새로운 방식: 현재 상태만 보면 되므로, 데이터 양이 선형적으로 (적게) 증가합니다. (예: 10 단계 퍼즐을 풀면 10 번 정도만 시도해도 됨)
비유: 미로에서 길을 찾을 때, "내가 어디를 잘못 갔는지"를 다 기록하며 헤매는 것보다, **"지금 내가 서 있는 위치"**를 보고 다음 길을 찾는 것이 훨씬 빠르고 효율적입니다.

💡 5. 결론: AI 의 미래를 여는 열쇠

이 논문은 AI 가 진정한 "지능"을 갖추기 위해서는 과거의 기록에 매몰되지 않고, 현재 상황을 명확하게 파악하는 능력이 필요하다고 말합니다.

코드 작성: 과거의 수정 기록이 아니라, 현재 코드와 로그를 보고 다음 행동을 결정합니다.
수학 증명: 과거의 추론 과정이 아니라, 현재 증명된 정리들을 바탕으로 다음 단계를 밟습니다.

한 줄 요약:

"AI 가 더 똑똑해지려면, 과거의 무거운 가방을 내려놓고 '지금 이 순간'에 집중하는 법을 배워야 합니다."

이 연구는 AI 가 단순한 패턴 반복을 넘어, 진짜로 새로운 것을 발견하고 복잡한 문제를 해결하는 **진정한 인공지능 (AGI)**으로 발전하는 데 중요한 이정표가 될 것입니다.

1. 문제 정의 (Problem Statement)

대형 언어 모델 (LLM) 의 사후 학습 (Post-training) 및 정렬 (Alignment) 을 위한 표준 패러다임으로 강화 학습 (RL) 이 자리 잡았으나, 최근 연구들은 RL 이 LLM 에게서 **지속적인 "능력 천장 (Capability Ceiling)"**에 직면해 있음을 시사합니다.

현재의 한계: 기존의 LLM RL 접근법은 '과거의 행동 시퀀스 (Action Sequence)' 전체를 상태 (State) 로 간주합니다. 즉, 모델은 모든 이전 토큰의 연결된 역사 (History) 를 입력으로 받아 다음 행동을 예측합니다.
발생하는 문제: 이 방식은 RL 이 기존 사전 학습 (Pre-training) 모델이 이미 가진 패턴을 정제 (Refine) 하는 데 그치게 만듭니다. AlphaZero 와 같은 고전적인 RL 시스템이 인간을 초월한 새로운 전략을 발견한 것과 달리, LLM 의 RL 은 새로운 추론 경로를 발견하기보다 기존 해답 공간 내에서만 탐색을 강화하는 데 그칩니다.
근본 원인: 고전적인 RL 은 최적의 의사결정에 필요한 모든 정보를 압축한 Markov 상태에 의존하는 반면, LLM 은 노이즈가 많고 무한히 확장되는 '행동 역사'에 의존합니다. 이로 인해 샘플 복잡도 (Sample Complexity) 가 기하급수적으로 증가하고, 진정한 새로운 능력의 발견이 계산적으로 불가능해집니다.

2. 방법론 (Methodology)

이 논문은 LLM 사후 학습의 근본적인 구조적 병목 현상을 해결하기 위해 고전 RL 의 핵심 원리인 **명시적인 Markov 상태 (Explicit Markov States)**를 LLM 학습 파이프라인에 재도입합니다.

Markov 상태 재정의:
- 기존 (Action-Sequence): $s_h = (x, y_1, \dots, y_{h-1})$ (모든 이전 토큰의 연결)
- 제안 (Markovian): $s_{h+1} = P(s_h, a_h)$ (현재 상태와 행동에 의해 결정되는 다음 상태)
- 모델은 행동 $a_h$ 를 생성한 후, 이를 현재 상태 $s_h$ 와 결합하여 상태 전이 함수 $P$ 를 통해 다음 상태 $s_{h+1}$ 를 계산하고, 이를 다음 단계의 입력으로 사용합니다.
구현 방식:
- 상태 전이 모델 (State Transition Model): 환경의 동역학을 학습하거나 규칙 기반 (Rule-based) 으로 구현하여, 모델이 직접 상태 전이를 추론하지 않고 외부에서 명확한 상태 정보를 제공받도록 합니다.
- 학습 알고리즘: GRPO (Group Relative Policy Optimization) 와 같은 기존 RL 알고리즘을 사용하되, 입력 데이터의 구조를 '행동 시퀀스'에서 'Markov 상태'로 변경하여 학습합니다.
- 실험 환경: Sudoku, Sokoban, Futoshiki 와 같은 논리 퍼즐 (Reasoning-Gym) 을 사용하여, 각 단계에서 보드 상태가 완전히 관측 가능한 Markov 상태를 가지는 환경을 구성했습니다.

3. 주요 기여 (Key Contributions)

능력 천장 돌파 (Breaking the Capability Ceiling):
- 복잡한 논리 퍼즐 벤치마크에서 Markov 상태를 사용하는 모델은 전통적인 RL 사후 학습 (행동 시퀀스 기반) 의 성능 한계를 일관되게 돌파했습니다. 특히 행동 시퀀스 모델이 거의 0% 에 가까운 성능을 보였던 난이도 높은 작업 (Sokoban, Futoshiki) 에서 Markov 모델은 높은 성공률을 기록했습니다.
강건한 일반화 (Robust Generalization):
- Markov 모델은 훈련 데이터보다 구조적 복잡도나 탐색 깊이가 더 높은 분포 외 (OOD, Out-of-Distribution) 데이터에서도 우수한 일반화 성능을 보였습니다. 이는 모델이 불필요한 역사적 노이즈에 의존하지 않고 문제의 본질적인 상태에 집중했기 때문입니다.
샘플 효율성 보장 (Sample Efficiency Guarantees):
- 이론적 분석을 통해 Markov 기반 학습이 표준 행동 시퀀스 기반 학습에 비해 지수적으로 낮은 샘플 복잡도를 가진다는 것을 증명했습니다. 행동 시퀀스 방식은 상태 공간이 $O(|A|^H)$ 로 기하급수적으로 커지는 반면, Markov 방식은 $O(H)$ 로 선형적으로만 증가하여 학습 효율이 극대화됩니다.

4. 실험 결과 (Results)

성능 비교 (Table 1, Table 2):
- Qwen3-4B 기준: Sudoku 에서 92.3% (시퀀스) vs 97.1% (Markov), Sokoban 에서 2.5% vs 76.1%, Futoshiki 에서 0.2% vs 75.0% 로 압도적인 차이를 보였습니다.
- Pass@k 분석: 행동 시퀀스 모델은 SFT (Supervised Fine-Tuning) 기반의 Pass@k 성능을 유지하거나 약간 개선하는 데 그쳤으나, Markov 모델은 베이스 모델의 한계를 깨고 Pass@k 를 지속적으로 확장했습니다.
수렴 속도: Markov 모델은 더 적은 학습 단계에서 더 높은 보상에 도달하여, 샘플 효율성이 높음을 실험적으로 입증했습니다 (Figure 5).
상태 의존성 분석: 상태 - 행동 시퀀스 모델 (State-Action-Seq) 이 현재 상태와 과거 역사를 모두 입력받음에도 불구하고, 실제 학습된 정책은 현재 상태에만 의존하고 있음을 확인했습니다. 과거 역사는 불필요한 노이즈로 작용하여 학습을 방해할 수 있음을 시사합니다.

5. 의의 및 결론 (Significance & Conclusion)

패러다임의 전환: 이 연구는 LLM 의 강화 학습이 단순히 "역사 (History) 를 상태 (State) 로 간주"하는 방식을 넘어, 구조화된 Markovian 표현으로 전환해야 함을 강력히 주장합니다.
개방형 능력 성장: Markov 상태의 도입은 LLM 이 기존 지식의 범위를 벗어나 진정한 새로운 추론 능력과 개방형 발견 (Open-ended Discovery) 을 가능하게 하는 열쇠가 될 수 있습니다.
실제 적용 가능성: 코드 디버깅 (현재 코드베이스 상태), 수학적 증명 (정립된 보조정리 집합), 반복적 응답 정제 (최신 초안) 등 다양한 실제 시나리오에서 상태 전이 메커니즘을 명시적으로 모델링함으로써 복잡한 장기 계획 (Long-horizon) 과 추론 과제를 해결할 수 있는 길을 제시합니다.

요약하자면, 이 논문은 LLM 의 RL 기반 사후 학습이 겪는 성능 한계의 근본 원인이 '상태 표현의 부재'에 있음을 규명하고, 명시적인 Markov 상태를 도입함으로써 샘플 효율성과 일반화 능력을 획기적으로 개선할 수 있음을 이론적, 실험적으로 증명했습니다.