Docs | Src |  A-  |  A*  |  A+  | -/-

Metadata
sourcehttps://alexwang.ai/posts/reasoning-as-pathfinding/
created2026-11-13
byopenai:gpt-6.1-sol
# 추론은 어떤 목적을 최적화하는가? 토큰 공간에서의 경로 탐색으로 바라본 추론. 추론은 경로 탐색이다. 각 샘플 $z$는 시작 문맥 $x$에서 출발해 $\cal{S}_x$ 안의 정답 $y(z)$로 이어지는 경로를 찾으려는 시도이다. 추론을 바라보는 직관적이지만 단순화된 관점이 있다. 모델이 더 오래 생각하게 하면 정답을 맞힐 가능성이 커진다는 것이다. 이는 인간의 직관에도 잘 들어맞는다. 생각하는 데 시간과 노력을 더 들이면 정답에 도달할 가능성이 커진다. 하지만 이 관점만으로는 모든 것을 설명하기 어려워 보인다. 강화 학습(RL) 과정에서 모델은 더 긴 사고 사슬을 작성하는 법을 배우고, 그에 따라 정확도도 높아진다. 그런데 학습된 모델의 개별 사고 사슬을 강제로 늘리면, 처음에는 도움이 되다가 어느 순간부터는 효과가 없어진다.[1](https://alexwang.ai/posts/reasoning-as-pathfinding/#fn:1) 때로는 생각을 지나치게 하는 것처럼 답이 오히려 _나빠지기도(worse)_ 한다.[2](https://alexwang.ai/posts/reasoning-as-pathfinding/#fn:2) 사고 사슬이 정말 어떤 최적점으로 수렴하는 과정이라면, 단계를 더 늘린다고 결과가 나빠져서는 안 된다. 그렇다면 추론 시점에 도움이 되는 것은 정말 각 사고 사슬의 길이일까? 아니면 더 미묘한 무언가가 있는 것일까? 이 글에서는 토큰 공간에서의 경로 탐색이라는 관점으로 추론을 살펴보며 이 혼란을 정리하려 한다. 무엇보다 나 자신을 위한 정리이다. 강화 학습은 $x$에서 $\cal{S}_x$로 이어지는 경로를 찾을 확률을 최대화하지만, 개별 경로가 정답으로 수렴한다고 보장하지는 않는다는 점을 살펴볼 것이다. 이 관점은 실제 사고 과정을 충실히 반영하지 않는 사고 사슬이나 보상 해킹처럼 추론 모델에서 관찰되는 몇 가지 이상한 현상도 설명해 준다. ## 경로 탐색으로 바라본 추론[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#reasoning-as-pathfinding) 추론 모델에 같은 수학 문제를 열 번 물으면 서로 다른 사고 사슬 열 개가 나온다. 추론을 답을 향해 나아가는 하나의 신비로운 과정으로 생각하는 대신, 토큰 공간에서의 경로 탐색으로 생각해 보자. 문제에서 정답으로 이어지는 경로는 많으며, 모델은 샘플을 생성할 때마다 그중 하나를 따라간다. “$1 + 2 + 3 + \cdots + 10$은 얼마인가?”라는 문제를 생각해 보자. 한 가지 풀이는 숫자를 하나씩 더하는 것이다. 1, 3, 6, 10으로 이어져 마지막에는 55가 된다. 다른 방법은 양 끝에서부터 숫자를 짝짓는 것이다. $1 + 10$, $2 + 9$, $3 + 8$, $4 + 7$, $5 + 6$은 각각 11이고, 11이 다섯 쌍이므로 합은 55이다. 두 경로 모두 정답인 55에 도달한다. 추론도 대체로 이런 패턴을 따른다고 볼 수 있다. 시작점으로 프롬프트가 주어지며, 이를 $x$라고 하자. 우리가 찾으려는 것은 $x$에서 시작해 정답 $y$에서 끝나는 경로 $z$이다. 경로가 올바른 곳에 도달했는지 판단하기 위해 검증기 $r(x, y)$가 있다고 가정한다. 이 검증기는 $y$가 정답이면 1을, 아니면 0을 반환한다. 따라서 시작점 $x$가 주어졌을 때, 우리가 찾으려는 것은 다음 집합에 도달하는 토큰 경로 $z$이다. $$\cal{S}_x = \{y : r(x, y) = 1\}.$$ [이 글 맨 위의 그림](https://alexwang.ai/posts/reasoning-as-pathfinding/#pathfinding-figure)은 이러한 관점을 간략히 보여 준다. 회색 선 하나하나가 샘플링한 경로이다. 각 경로는 왼쪽의 프롬프트에서 출발해 $z$를 샘플링하며 토큰 공간을 굽이굽이 나아간다. 그중 일부는 $\cal{S}_x$에 도달한다. $\cal{S}_x$에 도달하는 경로가 여럿이므로, 성공 확률은 그 모든 경로의 확률을 합한 값이다. 프롬프트 $x$가 주어졌을 때 모델이 경로 $z$를 생성할 확률을 $\pi(z \mid x)$, $z$의 끝에 있는 최종 답을 $y(z)$라고 하자. 성공 확률은 각 경로가 생성될 확률에 그 경로가 $\cal{S}_x$에 도달할 확률을 곱한 뒤, 이를 모든 경로에 걸쳐 더한 값이다. $$p_x = \prob{\text{경로가 } $\cal{S}_x \text{에 도달} \mid x} = \sum_{z} \underbrace{\pi(z \mid x)}_{\text{경로 } z \text{를 샘플링}}\; \underbrace{\prob{y(z) \in \cal{S}_x \mid z}}_{\text{경로 } z \text{가 }$\cal{S}_x \text{에 도달}}.$$ 두 번째 인자는 경로가 $\cal{S}_x$에 도달하면 1이고, 그렇지 않으면 0이다. 따라서 $\cal{S}_x$에 도달하는 경로의 확률만 더하면 된다. $$p_x = \sum_{z} \pi(z \mid x)\, \ind{y(z) \in \cal{S}_x} = \sum_{z \,:\, y(z) \in \cal{S}_x} \pi(z \mid x).$$ $p_x$를 **성공 확률(success probability)**이라고 부르자. 이 확률을 최대화한다는 것은 모델이 $\cal{S}_x$에 도달하는 경로를 샘플링할 가능성을 높인다는 뜻이다. 이 확률을 높이는 방법은 두 가지라는 점에 주목하자. 모델이 같은 답으로 이어지는 여러 경로를 각각 낮은 확률로 샘플링할 수도 있고, 답으로 이어지는 단 하나의 경로를 매우 높은 확률로 샘플링할 수도 있다. 성공 확률 자체는 둘을 구별하지 않는다. 하지만 실제로는 특정 경로를 우선하거나 샘플의 다양성을 확보하고 싶을 수 있다.[3](https://alexwang.ai/posts/reasoning-as-pathfinding/#fn:3) ## 성공 확률을 어떻게 높일 수 있을까?[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#how-do-we-boost-our-success-probability) ### Best-of-$k$ 샘플링[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#best-of--sampling) 가장 단순한 경로 탐색 방법은 모델 $\pi$가 경로 $z$를 계속 샘플링하게 하여, 그중 하나가 $\cal{S}_x$에 도달할 때까지 반복하는 것이다. 검증기가 있다고 가정했으므로, 경로 $k$개를 샘플링한 뒤 성공한 경로를 찾는 best-of-$k$ 샘플링을 사용할 수 있다. 각 경로가 실패할 확률은 $1 - p_x$이므로, $k$개가 모두 실패할 확률은 $(1-p_x)^k$이다. 따라서 성공 확률은 $p_x$에서 다음 값으로 높아진다. $$\prob{k\text{개 경로 중 적어도 하나가 } $\cal{S}_x \text{에 도달} \mid x} = 1 - \underbrace{(1-p_x)^k}_{k\text{개 경로가 모두 실패}}.$$ 이는 성능 향상이 보장되는 연산량 확장 방식이다. $p_x > 0$이기만 하면 경로를 더 많이 샘플링할수록 성공 확률이 단조 증가한다. 따라서 더 많은 샘플을 생성하는 데 연산량을 추가로 들이면 언제나 도움이 된다. 이는 일찍이 [브라운 외, 2024](https://arxiv.org/abs/2407.21787)에서도 관찰한 결과이다. 다만 여기서 늘어나는 것은 경로의 길이, 즉 생각하는 시간이 아니라 샘플 수이다. ### 더 나은 샘플을 생성하도록 모델 학습하기[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#train-the-model-to-generate-better-samples) 지금까지는 모델이 고정되어 있었으므로 $p_x$도 고정되어 있었다. 모델을 바꿔서 $p_x$ 자체를 높일 수 있을까? 간단한 방법이 있다. 답을 검증할 수 있는 프롬프트를 많이 모은다. 각 프롬프트에 대해 모델에서 경로를 몇 개 샘플링한다. $\cal{S}_x$에 도달한 경로만 남기고, 남겨 둔 경로로 모델을 학습한다. 그런 다음 이 과정을 반복한다. 매번 모델이 직접 샘플링한 성공 경로에 더 높은 확률을 부여하도록 학습하는 것이다. 이 반복 과정을 거부 샘플링 미세 조정이라고 하며, [STaR](https://arxiv.org/abs/2203.14465)는 이를 추론에 적용한 초기 사례이다. 오늘날 추론 모델을 학습하는 방식인 검증 가능한 보상을 사용하는 강화 학습도 사실상 거의 같은 일을 한다. 가중치가 $\theta$인 모델을 $\pi_\theta$라고 하자. $r(x, y(z)) = 1$인 것은 정확히 $y(z) \in \cal{S}_x$일 때이므로 다음이 성립한다. $$ \begin{aligned} p_x &= \sum_{z \,:\, y(z) \in \cal{S}_x} \pi_\theta(z \mid x) \\ &= \sum_{z} \pi_\theta(z \mid x)\, \ind{y(z) \in \cal{S}_x} \\ &= \sum_{z} \pi_\theta(z \mid x)\, r(x, y(z)) \\ &= \ev[z \sim \pi_\theta(\cdot \mid x)]{r(x, y(z))}, \end{aligned} $$ 즉, 이진 보상의 기댓값은 성공 확률 $p_x$와 정확히 같다. 로그 미분 기법으로 성공 확률의 기울기를 계산하면 다음을 얻는다. $$\grad_\theta\, p_x = \ev[z \sim \pi_\theta(\cdot \mid x)]{r(x, y(z))\, \grad_\theta \log \pi_\theta(z \mid x)},$$ 이는 정확히 정책 기울기이며, REINFORCE 추정량이라고도 부른다. 이제 샘플링한 $N$개의 경로 $z_1, \dots, z_N$으로 이 기울기를 추정해 보자. 실패한 경로는 $r = 0$이므로 사라지고, $\cal{S}_x$에 도달한 경로는 $r = 1$이다. $N$개 경로 중 $M$개가 성공했다면 추정값은 다음과 같다. $$\grad_\theta\, p_x \approx \frac{1}{N} \sum_{i \,:\, \text{도달}} \grad_\theta \log \pi_\theta(z_i \mid x) = \underbrace{\frac{M}{N}}_{\text{성공률}} \cdot \underbrace{\frac{1}{M} \sum_{i \,:\, \text{도달}} \grad_\theta \log \pi_\theta(z_i \mid x)}_{\text{성공 경로의 로그 우도}}.$$ 이 기울기는 경험적 성공률 $M/N$과 성공한 경로의 평균 로그 우도라는 두 항으로 이루어진다. 다시 말해, 이진 보상을 사용하는 REINFORCE의 한 단계는 모델이 직접 샘플링한 경로에 거부 샘플링 미세 조정을 한 단계 적용하되, 현재 성공률 $M/N$으로 크기를 조정한 것과 같다. 이는 도입부에서 언급한 첫 번째 관찰, 즉 강화 학습 중에 사고 사슬이 길어지는 이유도 설명한다. 각 학습 단계는 모델을 성공한 경로 쪽으로 끌어당긴다. 따라서 성공한 경로가 실패한 경로보다 대체로 길었다면 모델은 더 긴 경로를 작성하는 법을 배우게 된다. 성공한 경로가 더 길었던 이유는 되돌아가기 행동이 포함되어서일 수도 있고, 환경에서 더 많은 피드백을 모아서일 수도 있으며, 그저 우연일 수도 있다. ## 비용의 분산과 일반화[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#amortization-and-generalization) 강화 학습 중에는 좋은 경로를 찾는 데 많은 연산량을 들인 뒤, 모델이 그 경로를 곧바로 생성하도록 학습한다. 학습이 끝나면 모델은 여러 경로를 샘플링하는 데 그런 추가 연산량을 모두 쓰지 않고도 답을 생성한다. 이를 탐색 비용의 _분산(amortizing)_이라고 한다. 학습 중에 비용을 한 번 치르면, 모델에 질문할 때마다 그 비용을 다시 치르지 않아도 된다는 뜻이다.[4](https://alexwang.ai/posts/reasoning-as-pathfinding/#fn:4) _하나의 모델(single model)_을 여러 프롬프트로 학습하므로, 모델은 한 번도 보지 못한 새 프롬프트에도 _일반화(generalize)_할 가능성이 있다. 아래 그림은 각각 고유한 $\cal{S}_x$를 갖는 프롬프트 네 개를 통해 이를 보여 주며, 학습 전후의 모델을 번갈아 표시한다. 학습 중에는 모든 프롬프트에서 경로를 샘플링하고, 성공한 경로만 남겨 지도 미세 조정(SFT)을 수행한다. 백분율은 각 프롬프트가 주어졌을 때의 경험적 성공률을 나타낸다. 속이 빈 표시로 나타낸 프롬프트는 모델이 이전에 보지 못한 새로운 프롬프트이지만, 학습 후 모델은 이 프롬프트에도 일반화한다. 새 프롬프트가 학습 분포에서 멀어질수록 정확도는 떨어진다. 직접 드래그해 보자! 새 프롬프트를 드래그해 보자. ## 추론에서 관찰된 몇 가지 현상 다시 살펴보기[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#revisiting-some-observations-about-reasoning) 추론 모델을 임의의 $x$가 주어졌을 때 $\cal{S}_x$에 도달하도록 학습된 분포로 바라보면, 이 모델들에 관한 몇 가지 이상한 사실이 명확해진다. ### 사고 사슬이 실제 사고 과정을 충실히 반영한다고 보장할 수는 없다[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#chains-of-thought-are-not-guaranteed-to-be-faithful) 앞서 살펴본 검증기는 답이 맞는지만 확인한다. $y(z) \in \cal{S}_x$이면 보상이 1이고 그렇지 않으면 0이므로, 중간 토큰 $z$는 모델이 답에 도달하기 위한 수단일 뿐이다. 그 토큰의 내용이 사실이어야 한다거나, 뒤에 나오는 답을 설명해야 한다는 요구는 어디에도 없다. 물론 모델의 사전 학습 덕분에 이런 속성과 정답 여부 사이에는 상관관계가 있는 경우가 많다. 의미 있는 사고 사슬을 원한다면 보상이나 학습 목적을 조정해야 한다. ### 보상 해킹은 검증기와 샘플러 양쪽에서 비롯된다[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#reward-hacking-comes-from-both-the-verifier-and-the-sampler) 우리는 검증기가 절대 틀리지 않는다고도 가정했다. 즉, $y$가 실제로 $x$의 정답일 때, 그리고 그때에만 $r(x, y)=1$이라고 가정했다. 하지만 실제 검증기는 불완전할 수 있다. 그러면 검증기가 받아들이는 답의 집합인 $\cal{S}_x$는 정답 집합과 달라진다. 오답을 포함하거나 정답을 제외할 수 있는 것이다. 이렇게 검증 기준이 잘못 지정되면, 우리가 의도하지 않았는데도 모델이 도달하는 법을 학습할 수 있는 영역이 $\cal{S}_x$ 안에 생긴다. 따라서 보상 해킹은 우리가 진정으로 원하는 바를 포착하지 못하는 불완전한 검증기뿐 아니라, 이러한 지름길 영역을 피하지 못하는 불완전한 샘플링 절차에서도 비롯된다. 아래 그림에서 점선 원은 정답 집합이고, 빨간 타원은 $\cal{S}_x$이다. 타원이 프롬프트 쪽으로 뻗어 있으므로 타원에 포함된 오답에 가장 쉽게 도달한다. 학습 후에는 대부분의 경로가 그곳에 도달한다. 불완전한 검증기 이 시각화는 강화 학습의 규모를 키울수록, 즉 샘플을 더 많이 생성하고 더 길게 생성할수록 보상 해킹 가능성이 커지는 이유도 보여 준다. 검증기를 더 광범위하게 “퍼징(fuzz)”할수록 $\cal{S}_x$에서 검증 기준이 잘못 지정된 영역에 도달하는 경로를 찾을 가능성이 커진다. 모델이 이 지름길을 한 번 발견하면 학습은 모델을 그와 비슷한 행동으로 이끈다. ## 그렇다면 추론은 어떤 목적을 최적화하는가?[#](https://alexwang.ai/posts/reasoning-as-pathfinding/#so-what-objective-is-reasoning-solving) 사실 추론 자체는 어떤 목적도 최적화하지 않는다. 개별 경로가 정답으로 수렴한다는 보장은 없다. 경로의 분포 전체를 종합해서 볼 때에만 높은 성공 확률을 얻는다. 강화 학습은 성공 경로를 탐색하는 데 많은 연산량을 들인 다음, 모델이 그 경로를 재현하도록 학습함으로써 성공 확률 $p_x$를 직접 높인다. 더 오래 생각하는 것이 도움이 되는 이유는 학습을 통해 모델이 추가 토큰을 사용하는 법을 배웠기 때문이다. 토큰을 더 많이 생성하는 것 자체가 본질적으로 더 좋아서가 아니다. 강화 학습 중에 치른 샘플링 비용은 가중치에 반영되어 이후 추론에 걸쳐 분산된다. 추론 시점에는 모델이 샘플 하나만으로도 성공할 가능성이 높지만, 개별 샘플의 성공이 보장되는 것은 아니다. * * * 1. [뮈니히호프 외, 2025](https://arxiv.org/abs/2501.19393)는 모델이 생각을 멈추려 할 때마다 “잠깐(Wait)”을 덧붙여 계속 생각하도록 강제했다. 정확도는 처음에는 높아졌지만 이후에는 정체되었다.[↩︎](https://alexwang.ai/posts/reasoning-as-pathfinding/#fnref:1) 2. 좋은 예로 [게마 외, 2025](https://arxiv.org/abs/2507.14417)가 있다. 이 연구는 추론이 길어질수록 정확도가 떨어지는 과제들을 발견했다.[↩︎](https://alexwang.ai/posts/reasoning-as-pathfinding/#fnref:2) 3. 이 주제는 향후 글에서 다시 다룰 수도 있다.[↩︎](https://alexwang.ai/posts/reasoning-as-pathfinding/#fnref:3) 4. 비용이 많이 드는 탐색으로 더 나은 답을 찾은 뒤, 신경망이 적은 비용으로 그 답을 출력하도록 학습하는 발상은 언어 모델 밖에서도 찾아볼 수 있다. [알파제로](https://arxiv.org/abs/1712.01815)는 자기 대국의 매 수마다 트리 탐색을 수행하고, 그 과정에서 찾아낸 수를 선호하도록 정책 신경망을 학습한다. [전문가 반복 학습](https://arxiv.org/abs/1705.08439)도 같은 발상이다. 물리학자와 기상 예보 전문가들은 시뮬레이터로 같은 일을 한다. 사람이 정교하게 설계한 고비용 시뮬레이션을 실행해 답을 얻은 다음, 신경망이 그 답을 직접 예측하도록 학습한다.[↩︎](https://alexwang.ai/posts/reasoning-as-pathfinding/#fnref:4)