Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference

이 논문은 입자 필터링 (Sequential Monte Carlo) 알고리즘의 렌즈를 통해 언어 모델 추론 시 다중 샘플을 집계하고 가지치기하는 방법의 정확도 - 비용 트레이드오프를 이론적으로 분석하고 실험적으로 검증하여, 샘플링 오차를 설명하는 기준을 제시하지만 최종 정확도에는 한계가 있음을 밝힙니다.

핵심

🎲 "거부하고, 다시 뽑고, 반복하기": AI 가 더 똑똑하게 생각하게 만드는 비밀

이 논문은 거대 언어 모델 (LLM, 예: 챗봇) 이 복잡한 문제를 풀 때, 어떻게 하면 더 적은 노력으로 더 좋은 답변을 얻을 수 있는지에 대한 연구를 다룹니다. 특히, "한 번에 여러 개의 답을 만들어서 그중에서 가장 좋은 것을 고르는" 방식과 "단계별로 답을 검토하며 나쁜 길을 버리고 좋은 길만 유지하는" 방식의 차이를 수학적으로 분석했습니다.

이 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 배경: AI 는 왜 헷갈릴까? (도전 과제)

AI 가 수학 문제를 풀거나 글을 쓸 때, 단순히 한 번에 정답을 내는 것은 어렵습니다. 그래서 사람들은 다음과 같은 방법을 썼습니다:

• Best-of-N (최고의 N 개 중 고르기): AI 에게 같은 질문을 32 번 던져 32 개의 답을 만들고, 그중 가장 그럴듯한 답 하나만 골라냅니다.
  • 비유: 32 명의 학생에게 같은 문제를 풀게 하고, 가장 점수가 높은 학생의 답만 제출하는 것.
• SMC (Sequential Monte Carlo, 순차적 몬테카를로): 32 명의 학생을 동시에 키우되, 중간에 틀린 학생은 바로 퇴출시키고, 잘하는 학생은 복제해서 더 많은 시간을 투자하게 합니다.
  • 비유: 32 명의 학생이 문제를 풀다가, 중간에 "아, 이 길은 틀렸어!"라고 판단되면 그 학생은 자리에 앉고, "이 길은 유망해!"라는 학생은 친구를 불러와 함께 그 길을 가게 하는 것.

핵심 질문: "과연 이 복잡한 '단계별 검토' 방식이 정말로 더 좋은가? 그리고 왜 작동하는 (또는 작동하지 않는) 걸까?"

---

2. 이 연구의 핵심 발견 (세 가지 통찰)

저자들은 이 과정을 **'입자 필터링 (Particle Filtering)'**이라는 수학적 렌즈로 바라보며 세 가지 중요한 사실을 발견했습니다.

① 성공의 두 가지 조건 (왜 잘 작동할까?)

SMC 가 잘 작동하려면 두 가지 조건이 필요합니다.

1. 길 잃지 않기 (Action-level coverage): AI 가 현재 단계에서 다음 단계로 넘어갈 때, 정답이 될 가능성이 있는 길들을 놓치지 않고 모두 커버해야 합니다.
   • 비유: 탐험대가 지도를 볼 때, 정답이 있는 길이 '이쪽'이라고 했을 때, 그 방향을 완전히 무시하지 않고 충분히 넓은 범위를 탐색해야 한다는 뜻입니다.
2. 나침반의 정확도 (PRM Accuracy): 중간에 "이게 맞을까?"를 판단해주는 **보상 모델 (PRM)**이 어느 정도 정확해야 합니다.
   • 비유: 나침반이 북쪽을 가리키는데, 가끔은 동쪽을 가리키기도 한다면 탐험대는 길을 잃기 쉽습니다. 나침반이 너무 엉망이면 아무리 많은 탐험대 (입자) 를 보내도 소용없습니다.

결론: 이 두 가지 조건이 충족되면, SMC 는 적은 비용으로도 AI 의 실수를 줄일 수 있다는 이론적 보장이 생깁니다.

② 기존 방법보다 더 똑똑한 변형 (SMC-RS)

기존의 SMC 방식에는 한 가지 치명적인 약점이 있었습니다. 나침반이 완벽하지 않아도, 탐험대 (입자) 가 너무 적으면 정답에 도달할 확률이 급격히 떨어집니다.

• 문제: 나침반이 조금만 틀려도, 32 명을 보내도 정답을 못 찾을 수 있음.
• 해결책 (SMC-RS): 저자들은 여기에 **'거부 샘플링 (Rejection Sampling)'**이라는 기술을 추가했습니다.
  • 비유: 탐험대들이 길을 가다가 "이 길은 확실히 틀렸어!"라고 판단되면, 아예 그 길로 들어가지 않고 처음부터 다시 시작하거나 다른 길을 선택하게 합니다.
  • 효과: 이 방식을 쓰면 나침반이 완벽하지 않아도 훨씬 적은 인원 (입자) 으로도 정답을 찾을 수 있게 됩니다. 마치 "틀린 길은 아예 들어가지 않겠다"는 원칙을 세운 것 같습니다.

③ 한계: 무한히 좋은 나침반은 없다 (이론적 한계)

하지만 이 방법에도 한계가 있습니다.

• 현실: 나침반 (보상 모델) 이 완벽하지 않고, AI 가 예측할 수 없는 실수를 할 때, 아무리 많은 탐험대를 보내도 정답을 찾기 위해 기하급수적으로 많은 노력이 필요할 수 있습니다.
• 비유: 안개가 자욱한 숲에서 나침반이 고장 났다면, 아무리 많은 사람을 보내도 정답을 찾기 위해 숲 전체를 뒤져야 할 수도 있습니다. 이 경우, 단순히 사람을 더 보내는 것만으로는 해결되지 않습니다.

---

3. 실험 결과: 이론이 현실을 설명할까?

저자들은 이 이론이 실제 AI 에 적용될 때 어떻게 작동하는지 실험했습니다.

• 실험 1 (이론의 예측력): "나침반이 얼마나 정확한가?"와 "탐험대가 길을 잃지 않는가?"를 측정했을 때, 이 두 수치가 SMC 의 성능 (오류율) 을 매우 잘 예측했습니다.
  • 결과: 이론이 맞습니다! 나침반이 정확하고, 길을 잘 커버하면 AI 는 훨씬 잘 풀었습니다.
• 실험 2 (수학 문제 해결): 실제 수학 문제 (AIME, Math500) 를 풀었을 때, SMC 방식이 단순히 여러 답을 고르는 것 (Best-of-N) 보다 대부분의 문제에서 더 높은 정확도를 보였습니다.
  • 흥미로운 점: 하지만 이론이 예측한 대로 "나침반이 정확할수록 성능이 무조건 좋아진다"는 것은 아니었습니다. 때로는 나침반이 조금 더 엄격하게 (틀린 답을 더 많이 걸러내는 방식) 작동할 때, 오히려 성능이 더 좋아지기도 했습니다. 이는 "정확한 분포"보다 "정답을 포함하는 것"이 더 중요할 수 있음을 시사합니다.

---

4. 요약: 이 연구가 우리에게 주는 메시지

1. 무작위 시도는 비효율적이다: AI 에게 답을 100 번 내게 해서 하나를 고르는 것보다, **중간중간 검토하며 나쁜 길을 잘라내는 방식 (SMC)**이 훨씬 효율적입니다.
2. 중요한 것은 '검토'의 질: 이 방식이 잘 작동하려면, "이게 맞을까?"를 판단해주는 **보상 모델 (나침반)**이 어느 정도 신뢰할 수 있어야 합니다.
3. 새로운 알고리즘의 필요성: 기존 방식의 한계를 극복하기 위해, **거부 (Rejection)**를 활용한 새로운 알고리즘 (SMC-RS) 을 제안했습니다. 이는 더 적은 계산 비용으로 더 좋은 결과를 낼 수 있는 길을 열었습니다.
4. 아직 갈 길이 멀다: 나침반이 완전히 고장 난 상황 (매우 부정확한 보상 모델) 에서는, 아무리 많은 자원을 써도 한계가 있을 수 있습니다. 이를 극복하기 위해서는 AI 가 "앞을 내다보는 (Lookahead)" 능력을 키우는 등 새로운 접근법이 필요합니다.

한 줄 요약:

"AI 가 문제를 풀 때, 단순히 많은 답을 내는 것보다 중간중간 '이건 틀렸어'라고 잘라내며 올바른 길만 유지하는 것이 훨씬 효율적이지만, 그 '잘라내는 기준 (나침반)'이 너무 엉망이면 아무리 많은 사람을 보내도 소용없다."

이 연구는 AI 를 더 똑똑하게 만드는 '인공지능의 사고 과정'을 수학적으로 이해하고, 더 효율적인 알고리즘을 설계하는 데 중요한 이정표가 되었습니다.

기술 요약

이 논문은 "Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference" (거부, 재샘플링, 반복: 언어 모델 추론에서의 병렬 추론 이해) 으로, 대규모 언어 모델 (LLM) 의 추론 시간 (Inference-time) 개입 방법, 특히 입력 reward 모델 (Process Reward Model, PRM) 을 활용한 병렬 생성 및 가지치기 (Pruning) 전략을 체계적으로 분석하고 이론적 근거를 제시합니다.

저자들은 기존에 경험적 (Ad-hoc) 으로 사용되던 방법들을 입자 필터링 (Particle Filtering) 알고리즘, 특히 순차 몬테카를로 (Sequential Monte Carlo, SMC) 의 관점에서 수학적으로 규명하고, 그 성공 조건과 한계를 규명했습니다.

주요 내용은 다음과 같습니다.

---

1. 문제 정의 (Problem)

• 배경: LLM 의 추론 성능을 향상시키기 위해 여러 개의 생성 시나리오를 병렬로 생성하고, 이를 집계하거나 불필요한 경로를 제거하는 방법 (예: Best-of-N, SMC 등) 이 널리 사용되고 있습니다.
• 한계: 이러한 방법들이 왜 작동하는지에 대한 통일된 이론적 프레임워크가 부족합니다. 특히, PRM 이 완벽하지 않을 때 (Imperfect PRM) 이러한 알고리즘이 얼마나 정확한 샘플링을 보장할 수 있는지에 대한 비점근적 (Non-asymptotic) 분석이 부재했습니다.
• 목표: 주어진 PRM 평가 횟수 내에서 목표 분포 (높은 보상과 관련된 분포) 를 얼마나 정확하게 샘플링할 수 있는지 이론적으로 규명하고, 알고리즘 설계에 대한 지침을 제공하는 것입니다.

2. 방법론 (Methodology)

저자들은 LLM 생성을 마르코프 체인으로 모델링하고, 목표 분포 $\pi^*$ 를 기준 분포 $\pi_{ref}$ 와 보상 함수 $r^*$ 를 통해 정의된 틸팅 (Tilted) 분포로 설정했습니다.

• PRM (Process Reward Model): 완전한 보상 함수 $V^*$ 대신, 부분 생성에 대한 예상 보상을 추정하는 근사 함수 $\hat{V}$ 를 사용합니다.
• SMC (Sequential Monte Carlo): 여러 개의 '입자 (부분 생성)'를 유지하며, PRM 점수에 따라 가중치를 부여하고 (Resample), 낮은 점수의 경로를 제거 (Prune) 하는 알고리즘을 분석 대상으로 삼았습니다.
• 이론적 분석 도구:
  • Action-level Coverage: 기준 분포와 목표 분포의 조건부 확률 비율이 유계 (Bounded) 인지를 분석.
  • $\chi^2$-Divergence: PRM 의 오차가 생성된 분포 $\hat{\pi}$ 와 목표 분포 $\pi^*$ 사이의 거리 (발산) 에 미치는 영향을 분석.

3. 주요 기여 (Key Contributions)

1) SMC 성공을 위한 간단한 기준 제시 (Theoretical Criteria)

SMC 가 목표 분포를 효과적으로 근사하기 위해 필요한 두 가지 핵심 조건을 도출했습니다.

• 조건 1 (Bounded Action-level Coverage): 각 단계에서 기준 분포와 목표 분포의 조건부 확률 비율이 유계여야 함 ($C_{act}$).
• 조건 2 (Bounded $\chi^2$-Divergence): PRM 에 의해 유도된 분포 $\hat{\pi}_h$ 와 실제 목표 분포 $\pi^*_h$ 사이의 $\chi^2$ 발산이 유계여야 함 ($C_{\chi^2}$).
• 결과: 이 두 조건 하에서 $N$ 개의 입자를 가진 SMC 의 총변동 거리 (Total Variation Distance) 오차는 $O(\sqrt{H^2 C_{act} (C_{\chi^2}+1) / N})$ 로 수렴함을 증명했습니다. 이는 기존 순차적 알고리즘 (Backtracking) 보다 병렬 실행 시간 ($O(H)$ vs $O(H^2)$) 에서 우월함을 보입니다.

2) SMC 의 한계 극복 및 개선 알고리즘 제안

• SMC-RS (Sequential Monte Carlo with Rejection Sampling): 기존 SMC 는 PRM 이 완벽하더라도 ($\hat{V}=V^*$) 오차가 $O(H/\sqrt{N})$ 으로 감소하는 근본적인 한계가 있었습니다. 저자들은 **거부 샘플링 (Rejection Sampling)**을 결합한 SMC-RS 알고리즘을 제안했습니다.
  • 이 알고리즘은 입자 간의 간섭을 줄여, PRM 이 완벽할 때 단일 입자 ($N=1$) 만으로도 정확한 샘플링이 가능하게 합니다.
  • PRM 에 중대한 꼬리 분포 (Heavy-tailed) 오차가 있더라도 견딜 수 있는 이론적 보장을 제공합니다.

3) 입자 필터링의 근본적 한계 (Fundamental Limits)

• 비관적 (Myopic) 방법의 하한: PRM 이 불완전한 경우, 미래 정보를 보지 못하는 (Myopic) 모든 입자 필터링 알고리즘은 오차를 피하기 위해 입자 수 $N$ 이 $H$ (시계열 길이) 에 대해 최소 $\Omega(\log H / \log \log H)$ 이상이어야 함을 증명했습니다. 즉, 완벽한 정확도를 위해선 **Lookahead(선제적 정보)**가 필요할 수 있음을 시사합니다.

4. 실험 결과 (Empirical Results)

• 이론적 예측의 검증:
  • 프롬프트 스위칭 (Prompt-switching) 태스크: PRM 의 정확도 ($\chi^2$-divergence) 와 Action-level coverage 가 SMC 의 샘플링 오차와 강한 상관관계를 가짐을 실험적으로 확인했습니다 (그림 2).
  • 입자 수 증가 효과: 입자 수 $N$ 이 증가할수록 SMC 의 성능이 개선되며, Sequential Importance Sampling (SIS) 및 Best-of-N 보다 우월함을 보였습니다 (그림 3).
• 수학 추론 태스크 (Math Reasoning):
  • AIME 및 Math500 벤치마크: SMC 가 Best-of-N 보다 대부분의 문제에서 더 높은 정확도를 보였습니다 (그림 1).
  • PRM 정확도와 성능의 역설: 이론적으로는 PRM 오차 ($\chi^2$-divergence) 가 작을수록 성능이 좋아야 하지만, 실제 수학 문제에서는 PRM 오차가 큰 경우 (높은 온도 파라미터) 오히려 성능이 더 좋은 경향을 보였습니다. 이는 PRM 이 단순히 분포를 정확히 근사하는 것보다 **잘못된 경로를 효과적으로 제거 (Mode Coverage)**하는 능력이 더 중요할 수 있음을 시사합니다.

5. 의의 및 결론 (Significance)

1. 이론적 토대 마련: LLM 추론 시간 개입 (Inference-time interventions) 에 대한 첫 번째 체계적인 이론적 분석을 제공하여, 왜 SMC 와 같은 병렬 방법이 작동하는지 설명했습니다.
2. 알고리즘 개선: 기존 SMC 의 근본적 한계를 극복하고, PRM 이 불완전한 상황에서도 견고한 성능을 내는 SMC-RS 알고리즘을 제안했습니다.
3. 실무적 통찰: PRM 의 정확도뿐만 아니라 'Action-level Coverage'와 같은 구조적 특성이 알고리즘 성능에 결정적임을 보여주었습니다. 또한, 수학 문제와 같은 복잡한 태스크에서는 분포 근사보다 **모드 커버리지 (Mode Coverage)**가 더 중요할 수 있음을 발견하여, 향후 PRM 설계 및 알고리즘 개선 방향을 제시했습니다.

결론적으로, 이 논문은 LLM 의 추론 확장 (Inference-time scaling) 을 위한 방법론을 경험적 시도에서 수학적 엄밀성을 갖춘 과학적 접근으로 전환하는 중요한 이정표입니다.