Test-Time ComputeProcess Verifier백트래킹LLM 추론MCMCVGB

불완전한 검증자 길들이기: 백트래킹이 AI 추론을 구하는 법

AI가 한 단계씩 추론할 때, 불완전한 검증자의 작은 오류가 눈덩이처럼 불어나는 문제를 어떻게 해결할까? 1989년 이론 컴퓨터과학의 아이디어가 2025년 LLM 디코딩에서 부활한 이야기.

코어닷투데이2026-03-2544분

들어가며

낯선 도시에서 내비게이션을 따라 운전하고 있다고 상상해보자. 내비게이션은 매 교차로마다 "좌회전", "직진", "우회전"을 안내한다. 대부분의 안내는 정확하다. 하지만 10번 중 1번 정도 살짝 잘못된 안내를 한다면?

한두 번의 잘못은 별것 아닐 수 있다. 곧 경로를 재탐색해서 바로잡으면 된다. 하지만 내비게이션이 "한번 안내한 경로를 절대 수정하지 않는" 시스템이라면? 첫 번째 잘못된 좌회전이 두 번째 잘못을 낳고, 세 번째 잘못을 낳고… 목적지에서 점점 멀어지는 재앙적 상황이 벌어진다.

2026년 현재, AI 언어 모델이 수학 문제를 풀거나 코드를 작성할 때 정확히 이 상황에 놓여 있다. AI의 추론을 한 단계씩 감시하는 "검증자(verifier)"가 존재하지만, 이 검증자가 완벽하지 않다. 그리고 작은 오류들이 긴 추론 과정에서 눈덩이처럼 불어나는 현상 — 오류 증폭(error amplification) — 이 심각한 문제로 떠올랐다.

MIT, CMU, TTIC, Microsoft의 연구자 7명이 2025년 10월 발표한 논문 "Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking"은 이 문제에 대한 우아한 해법을 제시한다. 놀랍게도 그 핵심 아이디어는 1989년 이론 컴퓨터과학에서 온 것이다.

이 글에서는 왜 이런 문제가 생기는지부터, 어떻게 해결했는지, 그리고 2026년 AI 추론의 미래에 이것이 왜 중요한지를 하나씩 풀어보겠다.

제1장: Test-Time Compute의 시대 — "더 오래 생각하면 더 잘한다"

모델을 키울 것인가, 더 오래 생각하게 할 것인가

2020년대 초반까지 AI의 발전은 비교적 단순한 공식을 따랐다. 모델을 키우면 성능이 좋아진다. GPT-2(1.5B) → GPT-3(175B) → GPT-4로 이어지는 스케일링 법칙은 파라미터 수를 늘리면 더 똑똑한 AI를 만들 수 있음을 증명했다.

하지만 이 공식은 점점 한계에 부딪혔다. 모델을 10배 키워도 성능 향상은 점점 작아지고, 훈련 비용은 기하급수적으로 증가했다. 연구자들은 다른 방향을 모색하기 시작했다.

"모델의 크기를 키우는 대신, 이미 가진 모델에게 더 오래 생각할 시간을 주면 어떨까?"

이것이 Test-Time Compute(추론 시점 연산)** 패러다임의 핵심이다. 2024년 9월 OpenAI가 발표한 o1이 바로 이 아이디어의 대표적 구현이었다. o1은 답을 바로 내놓는 대신, 내부적으로 긴 **"사고 체인(chain of thought)"을 거치며 문제를 깊이 탐색했다. 결과는 극적이었다. 수학 올림피아드, 코딩 경시대회, 과학 추론에서 기존 모델을 크게 앞질렀다.

2025년 1월 DeepSeek이 발표한 DeepSeek-R1 역시 같은 철학을 따랐다. 강화학습을 통해 "더 오래 생각하는" 능력을 학습한 모델이었다.

기존 패러다임 → 모델을 키운다 → 성능 향상 (체감 감소)

새로운 패러다임 → 추론 시간을 늘린다 → 성능 향상 (비용 효율적)

Test-Time Compute를 활용하는 세 가지 방법

추론 시점에 더 많은 연산을 쏟는 방법은 크게 세 가지로 나뉜다.

1. Best-of-N 샘플링. 가장 단순한 방법이다. 같은 질문에 대해 N개의 답을 생성하고, 그중 가장 좋은 것을 고른다. "여러 번 시도해서 제일 나은 걸 택한다"는 직관적인 전략이다. Brown et al. (2024)의 연구에 따르면, 이 단순한 방법만으로도 상당한 성능 향상을 얻을 수 있다.

2. 결과 검증(Outcome Verification). 완성된 답 전체를 평가하는 검증자를 사용한다. 수학 문제라면 최종 답이 맞는지 확인하는 것이다. Best-of-N과 결합하면 — N개 생성 후 검증자가 가장 높은 점수를 준 답을 선택 — 더 강력해진다.

3. 과정 검증(Process Verification). 최종 답이 아니라, 추론의 각 단계를 평가하는 검증자를 사용한다. 수학 풀이의 각 줄이 논리적으로 올바른지, 코드의 각 블록이 적절한지를 중간중간 확인하는 것이다.

이 세 번째 방법이 가장 강력하면서도 가장 까다롭다. 중간 과정을 볼 수 있으니 잘못된 방향으로 빠지는 것을 일찍 감지할 수 있지만, 동시에 중간 평가가 틀릴 가능성이라는 새로운 문제가 생긴다. 이 논문이 다루는 것이 바로 이 세 번째 방법의 근본적 취약점과 해결책이다.

제2장: Process Verifier — 추론의 매 단계를 감시하는 감독관

"결과만 보는 것"과 "과정을 보는 것"의 차이

수학 시험을 채점하는 두 명의 선생님을 떠올려보자.

A 선생님(Outcome Verifier): 최종 답만 본다. 답이 42면 맞고, 아니면 틀렸다. 풀이 과정은 확인하지 않는다.

B 선생님(Process Verifier): 풀이의 매 단계를 확인한다. "1단계에서 방정식 세운 것은 맞네. 2단계 양변에 3을 곱한 것도 맞고. 3단계에서 부호를 잘못 바꿨네 — 여기서부터 다시 해봐."

B 선생님이 더 유용한 것은 분명하다. 학생(= AI 모델)이 어디서 잘못됐는지 알려줄 수 있으니까. 2022년 Uesato et al.과 2024년 Lightman et al.의 연구가 보여준 것이 바로 이것이다. 수학 문제 풀이에서 Process Verifier가 Outcome Verifier보다 더 효과적이라는 것.

Value Function — 검증자의 수학적 정체

이 논문은 Process Verifier를 가치 함수(value function)라는 수학적 프레임워크로 정의한다. 가치 함수의 아이디어는 직관적이다.

"지금까지의 추론 경로가 주어졌을 때, 최종적으로 좋은 결과에 도달할 기대 확률은 얼마인가?"

수학 문제를 풀고 있다고 하자. 3단계까지 풀었는데, 가치 함수가 0.8을 반환한다면 "지금까지의 풀이가 꽤 유망하다"는 뜻이다. 0.1을 반환한다면 "이 방향은 거의 막다른 길이다"는 뜻이다.

수식으로 표현하면, 프롬프트 $x$ 와 지금까지의 부분 응답 $y_{1:h}$ 가 주어졌을 때, 참 가치 함수(true value function)는 다음과 같다:

$V^{\star}_{\text{tilt}}(x, y_{1:h}) := \mathbb{E}^{\pi_{\text{ref}}}[\tau(x, y_{1:H}) \mid y_{1:h}]$

여기서 $\tau$ 는 최종 보상(완성된 답이 얼마나 좋은지), $\pi_{\text{ref}}$ 는 기본 언어 모델이다. 쉽게 말해, "지금 이 경로에서 계속 생성했을 때 좋은 결과가 나올 기대값"이다.

이 가치 함수가 완벽하다면, 매 단계마다 가치가 높은 방향으로 생성을 유도하면 된다. 마치 완벽한 내비게이션처럼, 매 교차로에서 목적지에 더 가까운 길을 정확히 알려주는 것이다.

이상과 현실의 괴리

문제는 이 참 가치 함수 $V^{\star}_{\text{tilt}}$ 를 정확히 아는 것이 거의 불가능하다는 것이다. 왜?

현실적으로 우리가 가진 것은 데이터로부터 학습된 근사 가치 함수 $\hat{V}$ 뿐이다. Monte Carlo 시뮬레이션으로 모아진 데이터에 회귀(regression)를 수행해서 학습한다.

$\hat{V} := \arg\min_{\tilde{V} \in \mathcal{V}} \hat{\mathbb{E}}\left[(V(x, y_{1:h}) - \tau(x, y_{1:H}))^2\right]$

이론적으로는 데이터가 무한히 많으면 $\hat{V}$ 가 $V^{\star}_{\text{tilt}}$ 에 수렴한다. 하지만 현실에는 유한한 데이터, 모델 구조의 한계, 최적화의 한계가 있다. 그래서 $\hat{V}$ 는 항상 불완전하다.

그럼 이 불완전한 $\hat{V}$ 를 그냥 쓰면 안 되나? 작은 오류 정도야 큰 문제가 안 되지 않을까? 이것이 바로 다음 장의 주제다. 그리고 답은, 놀랍게도, "안 된다"이다.

제3장: 오류 증폭 — 작은 실수가 재앙이 되는 순간

Action-Level Rejection Sampling: 순진한 접근법

불완전한 가치 함수 $\hat{V}$ 를 사용하는 가장 자연스러운 방법은 Action-Level Rejection Sampling(ActionLevelRS)이다. 아이디어는 단순하다.

각 단계 $h$ 에서:

기본 모델 $\pi_{\text{ref}}$ 에서 다음 토큰(또는 블록) 후보를 뽑는다.
$\hat{V}$ 를 사용해 그 후보의 가치를 평가한다.
가치에 비례하는 확률로 수락하거나 거절한다.
수락된 후보를 선택하고 다음 단계로 진행한다.

이것은 "매 교차로에서 내비게이션을 참고하되, 가치가 높은 방향을 선호하며 앞으로만 전진하는" 전략이다. 직관적이고 효율적이다. $\hat{V}$ 가 완벽하다면 이 방법은 최적의 결과를 준다.

Example 3.1: 미세한 오류의 파괴력

하지만 논문의 Example 3.1은 충격적인 반례를 보여준다. 설정은 이렇다:

알파벳 {a, b, c}로 길이 $H$ 인 문자열을 생성
보상 함수: 문자열에 'c'가 없으면 보상 1, 있으면 보상 0
참 가치 함수는 정확한 조건부 기대값
근사 가치 함수 $\hat{V}$ 는 단 하나의 편향이 있음: 마지막으로 'a'를 선택한 경우에만 참값보다 $(1+\varepsilon_V)$ 배 과대평가

Example 3.1 — 과대평가의 효과

설정 알파벳 = {a, b, c}, 길이 = H
보상: 'c' 없으면 1, 있으면 0

근사 가치 함수의 편향 마지막 토큰이 'a'일 때만 (1+ε) 배 과대평가
나머지는 정확

결과 ActionLevelRS의 출력 분포와 목표 분포 사이 거리:
Ω(min(ε√H, 1)) — 길이가 길어질수록 오류 폭발

핵심을 풀어보자. $\hat{V}$ 는 'a'를 선택할 때만 살짝 과대평가한다. 고작 $\varepsilon$ 만큼. 하지만 ActionLevelRS는 이 작은 편향을 매 단계 누적한다. 각 단계에서 'a'가 약간 유리해지고, $H$ 단계를 거치면 'a'만 잔뜩 있는 문자열이 과도하게 많이 생성된다.

이것이 오류 증폭(error amplification)이다. 수학적으로, 출력 분포와 목표 분포 사이의 거리가 $\varepsilon\sqrt{H}$ 에 비례한다. $\varepsilon$ 이 아무리 작아도, $H$ 가 크면 오류가 무한히 커진다.

Example 3.2: 한 발짝 늦은 정보의 비극

더 놀라운 것은 Example 3.2다. 여기서는 $\hat{V}$ 에 아무런 "크기" 오류가 없다. 단지 참 가치 함수보다 한 단계 늦게 정보를 반영한다. 즉, $\hat{V}(y_{1:h}) = V^{\star}_{\text{tilt}}(y_{1:h-1})$ 이다.

비유하자면, 내비게이션이 현재 교차로가 아니라 직전 교차로의 정보를 보여주는 것이다. "지금 우회전해야 합니다"라고 안내하는데, 사실 그건 100미터 전 교차로에서 해야 했던 안내다.

이 경우 $\hat{V}$ 는 현재 단계 $y_h$ 에 대한 정보를 전혀 담고 있지 않으므로, ActionLevelRS는 사실상 기본 모델 $\pi_{\text{ref}}$ 에서 무작위로 뽑는 것과 다를 바 없다. 가치 함수가 아무리 정확해도, 타이밍이 맞지 않으면 쓸모없다.

전화게임 비유: 왜 앞으로만 가는 것이 위험한가

이 현상을 전화게임(Chinese Whispers)으로 비유할 수 있다. 한 줄로 선 사람들이 메시지를 순서대로 전달한다. 각 사람은 95%의 확률로 메시지를 정확히 전달하고, 5%의 확률로 살짝 왜곡한다.

전달 횟수별 원본 메시지 보존율

5번 전달

~77%

10번 전달

~60%

20번 전달

~36%

50번 전달

~8%

100번 전달

~0.6%

5번 전달하면 77%가 살아남지만, 100번 전달하면 원본이 거의 사라진다. AI의 긴 추론 체인에서 일어나는 오류 증폭이 바로 이것이다. 각 단계의 오류가 작아도, 단계가 쌓이면 결과는 원래 목표에서 완전히 벗어난다.

그리고 기존 ActionLevelRS의 치명적 약점은, 이 전화게임에서 뒤를 돌아볼 수 없다는 것이다. 이전 단계로 돌아가서 "아, 그때 잘못 전달했구나"라고 수정할 방법이 없다.

그런데, 만약 뒤로 돌아갈 수 있다면?

제4장: VGB — 확률적 백트래킹이라는 우아한 해법

핵심 아이디어: 트리 위의 랜덤 워크

논문이 제안하는 알고리즘 VGB(Value-Guided Sampling with Stochastic Backtracking)의 핵심 아이디어는 놀랍도록 간결하다.

"앞으로만 가지 말고, 때때로 뒤로도 가라."

ActionLevelRS를 한 줄만 수정한 것이 VGB다. ActionLevelRS가 트리를 아래로만 내려가는 알고리즘이라면, VGB는 트리 위를 자유롭게 오르내리는 알고리즘이다.

이것을 이해하기 위해, AI의 텍스트 생성 과정을 거대한 나무(tree)로 시각화해보자. 나무의 루트(뿌리)는 빈 상태이고, 각 노드는 지금까지 생성된 부분 응답이며, 잎(leaf)은 완성된 전체 응답이다. 각 노드에서 자식 노드로 가는 것은 "다음 토큰을 하나 추가하는 것"이고, 부모 노드로 올라가는 것은 "마지막 토큰을 삭제하는 것(백트래킹)"이다.

텍스트 생성을 트리로 보기

∅ (빈 상태) 루트 노드

"The"1단계 선택지 A

"A"1단계 선택지 B

"We"1단계 선택지 C

"The cat"2단계 확장

"The dog"2단계 확장

"The ..."2단계 확장

ActionLevelRS는 이 나무를 루트에서 잎까지 한 방향으로만 내려간다. 매 분기점에서 $\hat{V}$ 를 참고해 방향을 고르지만, 한번 내린 결정은 되돌릴 수 없다.

VGB는 다르다. 매 순간, 현재 위치한 노드에서 세 가지 선택지가 있다:

자식 노드로 내려간다 (다음 토큰 추가) — 확률이 $\pi_{\text{ref}}(y_{h+1}) \cdot \hat{V}(y_{1:h}, y_{h+1})$ 에 비례
부모 노드로 올라간다 (마지막 토큰 삭제 = 백트래킹) — 확률이 $\hat{V}(y_{1:h})$ 에 비례
제자리에 머문다 — 확률 1/2 (이것은 정상 분포 수렴을 보장하기 위한 기법)

알고리즘을 직관적으로 이해하기

바둑판을 되돌리는 상황을 생각해보자.

바둑에서 수를 놓다가 "아, 이건 아닌 것 같다"는 직감이 들 때가 있다. 하지만 보통은 돌을 내려놓으면 다시 빼지 못한다(ActionLevelRS). VGB는 "무르기(undo)"가 허용되는 바둑이다. 단, 무르기를 할지 말지도 확률적으로 결정된다.

현재 위치의 가치가 높으면( $\hat{V}$ 가 크면) 백트래킹할 확률도 높다 — 얼핏 역설적으로 보인다. 하지만 이것은 "이 위치가 이미 충분히 좋으니, 한 칸 올라가서 다른 좋은 가능성도 탐색해봐라"라는 뜻이다. 반대로, 자식 노드로 내려갈 확률은 기본 모델의 생성 확률( $\pi_{\text{ref}}$ )과 그 자식의 가치( $\hat{V}$ )를 모두 고려한다.

이 랜덤 워크를 충분히 오래 실행하면, 최종적으로 방문하는 잎(leaf) 노드의 분포가 우리가 원하는 목표 분포 $\pi^{\star}$ 에 수렴한다. $\hat{V}$ 에 오류가 있어도.

왜 백트래킹이 오류 증폭을 막는가

핵심 직관은 이렇다.

ActionLevelRS에서 오류가 증폭되는 이유는, 각 단계의 편향이 한 방향으로만 누적되기 때문이다. $\hat{V}$ 가 'a'를 약간 선호하면, 매 단계에서 'a'가 선택될 확률이 조금씩 높아지고, 그 효과가 계속 쌓인다.

VGB에서는 백트래킹이 이 누적을 자연스럽게 해소한다. 잘못된 방향으로 내려갔더라도, 가치가 낮은 곳에 도달하면 다시 올라와서 다른 경로를 탐색할 수 있다. 마치 미로에서 막다른 길을 만났을 때 되돌아 나와서 다른 길을 시도하는 것과 같다.

수학적으로 더 정확히 말하면, VGB의 랜덤 워크는 정상 분포(stationary distribution)를 가지며, 그 정상 분포가 잎 노드에서 정확히 $\pi^{\star}$ 와 비례한다. 이것은 $\hat{V}$ 가 불완전해도 성립한다 — 단, $\hat{V}$ 가 참값과 비교해 일정한 범위 내의 곱셈 오차를 갖는 조건 하에서.

제5장: Sinclair-Jerrum 랜덤 워크 — 1989년에서 온 열쇠

의외의 기원: 근사적 세기(Approximate Counting) 문제

VGB의 이론적 기반을 이해하려면, 1989년으로 거슬러 올라가야 한다. 이론 컴퓨터과학자 Alistair Sinclair와 Mark Jerrum이 발표한 "Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains"라는 논문은, 전혀 다른 맥락에서 시작됐지만 VGB의 핵심 메커니즘과 놀랍도록 일치하는 아이디어를 담고 있다.

Sinclair-Jerrum이 풀려 했던 문제는 이런 것이다:

"주어진 조건을 만족하는 조합 구조가 몇 개나 있는지 (근사적으로) 세려면, 그 구조들 중에서 균일하게 샘플링할 수 있어야 한다."

예를 들어, 그래프의 매칭(matching) 수를 세거나, 행렬의 퍼머넌트(permanent)를 계산하는 문제다. 이런 문제들은 #P-hard — 정확한 답을 구하는 것이 사실상 불가능 — 하지만, 근사적으로 세는 것은 가능할 수 있다.

Sinclair-Jerrum의 핵심 통찰은:

근사적 세기는 근사적 샘플링으로 환원된다 (counting ↔ sampling)
근사적 샘플링은 적절한 마르코프 체인(Markov chain)이 빠르게 수렴하면 가능하다
수렴 속도는 conductance(전도도)라는 양으로 측정할 수 있다

그들이 설계한 마르코프 체인의 핵심 특성은: 트리 구조 위에서, 노드 사이를 오가며, 결국 원하는 분포에 수렴하는 랜덤 워크. 바로 VGB가 하는 것이다.

36년의 시간을 넘는 연결

근사적 세기 (1989) → 근사적 샘플링 → 트리 위 랜덤 워크

LLM 정렬 (2025) → 분포 샘플링 → 트리 위 랜덤 워크 (VGB)

이 연결이 성립하는 이유를 이해하면 논문의 깊은 구조가 보인다.

Sinclair-Jerrum (1989): "오류 있는 근사적 오라클(counting oracle)을 사용하면서도 올바른 분포에서 샘플링하는 방법을 설계한다."

VGB (2025): "오류 있는 근사적 가치 함수(process verifier)를 사용하면서도 올바른 분포에서 샘플링하는 방법을 설계한다."

두 문제의 구조가 거의 동일하다. 논문의 저자들은 Sinclair-Jerrum의 가치 함수(value functions)가 세기 오라클(counting oracles)의 일반화임을 보이고, VGB가 Sinclair-Jerrum 랜덤 워크의 일반화임을 증명했다. 36년 된 이론적 도구가 현대 AI의 핵심 문제를 푸는 데 정확히 들어맞은 것이다.

이것은 기초 과학과 응용 사이의 관계를 보여주는 아름다운 사례다. 1989년 Sinclair와 Jerrum이 "이것이 언젠가 AI 언어 모델의 디코딩에 쓰일 것"이라고 예상했을 리 없다. 하지만 수학적 구조의 보편성이 36년의 시간을 넘어 연결고리를 만들어냈다.

제6장: 이론적 보장 — VGB가 실제로 무엇을 약속하는가

Theorem 4.1: 균일 오류 가정 하의 보장

논문의 핵심 정리 중 하나는 다음과 같다.

근사 가치 함수 $\hat{V}$ 가 참 가치 함수 $V^{\star}_{\text{tilt}}$ 에 대해 균일한 곱셈 오차(multiplicative error) $\varepsilon_V$ 를 갖는다고 가정하자:

$\frac{\hat{V}(x, y_{1:h})}{V^{\star}_{\text{tilt}}(x, y_{1:h})} \in [1/(1+\varepsilon_V),\ 1+\varepsilon_V]$

그러면 VGB의 출력 분포 $\hat{\pi}$ 와 목표 분포 $\pi^{\star}$ 사이의 총 변동 거리(Total Variation Distance)가 $\delta$ 이하가 되려면, 랜덤 워크를 약 $\tilde{O}(H^2 \cdot (1+\varepsilon_V)^4 \cdot \log(1/\delta))$ 스텝만 실행하면 된다.

핵심은 $\varepsilon_V$ 에 대한 다항 시간(polynomial) 의존성이다. ActionLevelRS에서는 오류가 $\varepsilon_V\sqrt{H}$ 로 증폭되어 $H$ 가 크면 제어 불가능해지는 반면, VGB에서는 오류가 제어 가능한 범위 내에 머문다.

ActionLevelRS vs VGB — 오류 증폭 비교

ActionLevelRS 출력 오류 ≥ Ω(ε_V√H) — 시퀀스가 길어지면 오류 폭발
Example 3.1, 3.2에서 실패

VGB 출력 오류 ≤ δ (사용자 지정) — 시퀀스 길이와 무관하게 제어 가능
스텝 수 T = Õ(H² · (1+ε_V)⁴ · log(1/δ))로 달성

Theorem 4.2: 더 약한 평균 오류 가정

현실에서는 균일 오차 가정이 너무 강할 수 있다. 학습된 가치 함수는 어떤 경로에서는 정확하고 다른 경로에서는 부정확할 수 있다. 논문은 이를 위해 평균 오차(average-case error) 가정 하에서도 VGB가 잘 작동함을 보인다.

이 더 약한 가정은:

$\mathbb{E}_{y_{1:h} \sim \pi^{\star}(\cdot|x)}\left[\frac{\hat{V}(x, y_{1:h})}{V^{\star}_{\text{tilt}}(x, y_{1:h})}\right] \leq 1 + \varepsilon_V$

즉, $\pi^{\star}$ 분포 하에서 평균적으로 오차가 작으면 된다. 일부 드문 경로에서 오류가 크더라도, 그런 경로가 $\pi^{\star}$ 하에서 드물기만 하면 괜찮다.

이 조건 하에서 VGB는 coverage 보장을 제공한다. 목표 분포 $\pi^{\star}$ 에서 높은 확률을 갖는 응답은 VGB에서도 비슷한 확률로 생성된다는 것이다. 이는 Best-of-N과 결합했을 때 특히 유용하다 — 좋은 응답이 반드시 생성 후보에 포함되기 때문이다.

제7장: 실험 — 이론이 현실에서 작동하는가

합성 실험: ABC 과제와 Parity 과제

논문은 먼저 이론적 예측을 검증하기 위한 합성(synthetic) 실험을 수행한다.

ABC 과제는 앞서 설명한 Example 3.1의 설정이다. 가치 함수를 데이터로부터 학습시킨 뒤, ActionLevelRS와 VGB를 비교했다.

결과는 이론적 예측을 정확히 확인한다. 시퀀스 길이 $H$ 가 증가함에 따라 ActionLevelRS의 오류(KL-divergence)는 계속 커지는 반면, VGB의 오류는 안정적으로 유지된다.

H 증가에 따른 KL-divergence 변화 (N=10000 학습 샘플)

H=5

ActionLevel ≈ VGB

H=7

ActionLevel > VGB

H=9

ActionLevel ≫ VGB

H=11

ActionLevel ≫≫ VGB

Parity 과제는 가치 함수가 특정 위치에서 학습하기 매우 어려운 상황을 테스트한다. 일부 위치에서 가치 함수는 패리티(parity) 함수 — 경사하강법으로 학습하기 악명 높은 함수 — 를 계산해야 한다. 이는 실제 학습된 가치 함수가 체계적으로 지연된 정보만 갖는 상황(Example 3.2와 유사)을 만든다. 여기서도 VGB가 ActionLevelRS보다 적은 계산으로 올바른 답에 도달한다.

언어 모델 실험: Dyck 문법

더 현실적인 실험으로, 논문은 Dyck 문법 생성 과제를 사용한다. Dyck 문법은 균형 잡힌 괄호 문자열을 생성하는 것이다 — 예를 들어 [()]은 유효하지만 [(])은 아니다. 이것은 프로그래밍 언어의 문법 구조, 자연어의 계층적 구조를 모사하는 고전적 테스트베드다.

길이 32의 Dyck 문자열을 생성하는 Transformer 모델을 처음부터 학습시키고, 학습 데이터와 다른 분포(OOD)의 접두사에서 완성하도록 했다. 가치 함수도 데이터로부터 학습했다.

VGB를 Block Best-of-N, Block Rejection Sampling과 비교한 결과:

지표	VGB	기존 방법
정확도-다양성 균형	파레토 프론티어 우위	정확도↑ 시 다양성↓ 트레이드오프
분포 정확도 ( $\ell_1$ 오차)	ActionLevelRS보다 낮음	높은 에폭에서 차이 확대
쿼리 효율	OutcomeLevelRS보다 효율적	더 많은 쿼리 필요

특히 정확도와 다양성의 균형에서 VGB가 두드러진다. 기존 방법들은 정확도를 높이려면 다양성이 떨어지는 트레이드오프를 보이지만, VGB는 정확도도 높으면서 다양한 올바른 응답을 생성한다. 이것은 VGB가 분포적으로 정확한 샘플링을 한다는 이론적 보장의 경험적 확인이다.

코드 생성과 제약 텍스트 생성

코드 생성 과제에서는 Qwen-2.5-0.5B를 기본 모델로, append 함수에 대한 유효한 Python 테스트 케이스를 생성하도록 했다. VGB는 테스트 케이스 길이 분포와 객체 타입 분포에서 ActionLevelRS보다 $\pi^{\star}$ 에 더 가까운 분포를 보였다.

제약 텍스트 생성(Letter Avoidance) 과제는 특히 흥미롭다. "문자 'e'를 사용하지 않고 영어 문장 쓰기"라는 과제에서, VGB는 학습된 가치 함수 없이도 — 보상 함수 $r^{\star}$ 자체를 가치 함수의 근사로 사용하여 — ActionLevelRS(이 경우 locally constrained decoding과 동일)보다 더 자연스러운(coherent) 문장을 생성했다. GPT-4o-mini로 일대일 비교 평가한 결과 VGB의 승률이 일관되게 높았다.

제8장: 2026년의 맥락에서 — 왜 지금 이 연구가 중요한가

에이전트 AI 시대의 핵심 병목

2026년 현재, AI 에이전트가 복잡한 과제를 자율적으로 수행하는 것은 더 이상 미래의 이야기가 아니다. 코드를 작성하고, 데이터를 분석하고, 문서를 작성하는 에이전트들이 실제 업무에 투입되고 있다.

이 에이전트들의 공통점은 긴 추론 체인을 거친다는 것이다. 코드 에이전트는 수십 단계의 함수 호출과 디버깅을 거치고, 연구 에이전트는 여러 소스를 탐색하고 종합한다. 이 긴 체인에서 중간 단계의 검증이 불완전하면 — 그리고 현실에서는 거의 항상 불완전하다 — 최종 결과의 품질이 급격히 저하될 수 있다.

VGB가 제시하는 "필요할 때 뒤로 돌아갈 수 있는" 메커니즘은, 이 에이전트 시대의 핵심 병목을 해결하는 방향을 제시한다.

Test-Time Compute 스케일링의 이론적 기반

o1과 DeepSeek-R1이 보여준 것은 "추론 시간에 더 많이 계산하면 성능이 좋아진다"는 경험적 사실이다. 하지만 왜 좋아지는지, 어떤 알고리즘이 최적인지에 대한 이론적 이해는 아직 초기 단계다.

이 논문의 중요한 기여는, 불완전한 검증자를 사용하는 여러 알고리즘을 통일된 수학적 프레임워크 안에 놓고 비교했다는 것이다. ActionLevelRS, OutcomeLevelRS, Beam Search, 그리고 VGB — 이들의 강점과 약점이 수학적으로 명확해졌다. 이것은 향후 더 나은 test-time compute 전략을 설계하는 기반이 된다.

연결되는 세 가지 물줄기

논문의 저자들이 특히 강조하는 것은, 이 연구가 서로 멀어 보이는 세 분야를 연결한다는 것이다:

VGB가 연결하는 세 가지 연구 전통

이론 컴퓨터과학 근사적 세기, MCMC, Sinclair-Jerrum (1989~)

강화학습 / 의사결정 가치 함수, KL 정규화, 정렬(alignment)

LLM 디코딩 / 생성 Process Verifier, 백트래킹, Test-time compute

VGB 세 분야의 도구와 통찰을 통합하는 알고리즘

이런 분야 간 연결은 종종 가장 생산적인 연구 방향을 열어준다. 한 분야에서 40년간 축적된 도구와 통찰이 다른 분야의 난제를 푸는 데 활용될 수 있기 때문이다.

제9장: 열린 질문들과 미래 방향

아직 풀리지 않은 문제들

논문은 VGB의 한계와 향후 연구 방향도 솔직하게 논의한다.

1. 계산 비용. VGB는 $\tilde{O}(H^2)$ 스텝이 필요하다. 시퀀스 길이 $H$ 에 대해 이차적인 의존성은 실용적으로 부담이 될 수 있다. $\tilde{O}(H^2)$ 가 근본적 하한인지, 아니면 $\tilde{O}(H)$ 까지 줄일 수 있는지는 열린 문제다.

2. 학습과 추론의 연결. 논문은 비완전한 가치 함수 $\hat{V}$ 가 "이미 주어져 있다"고 가정한다. 하지만 $\hat{V}$ 를 어떻게 학습하느냐에 따라 VGB의 성능이 크게 달라질 수 있다. VGB에 최적화된 가치 함수 학습 방법은 무엇인가?

3. 실용적 구현. 대규모 언어 모델에서 VGB를 효율적으로 구현하는 것은 공학적 도전이다. 특히 토큰 단위로 백트래킹하면 각 스텝마다 모델을 호출해야 하므로, 대형 모델에서의 wall-clock time이 문제가 될 수 있다.

더 넓은 전망

이 연구가 가리키는 더 큰 방향은 "추론 시점의 알고리즘 설계가 AI 시스템의 성능을 결정하는 핵심 요소"라는 것이다.

지금까지 AI 연구의 주된 노력은 더 좋은 모델을 학습하는 데 집중됐다. 더 좋은 데이터, 더 큰 규모, 더 정교한 학습 알고리즘. 하지만 VGB가 보여주듯, 같은 모델과 같은 검증자를 사용하더라도 추론 알고리즘에 따라 결과가 극적으로 달라질 수 있다.

미로를 탐색하는 두 사람을 상상해보자. 한 명은 불완전한 지도를 들고 앞으로만 걸어간다. 다른 한 명은 같은 불완전한 지도를 들었지만, 막다른 길을 만나면 되돌아와서 다른 길을 시도한다. 두 사람의 지도 정확도는 같다. 하지만 결과는 완전히 다르다.

마치며

이 논문의 메시지를 한 문장으로 압축하면 이렇다:

불완전한 검증자의 작은 오류는 앞으로만 가는 알고리즘에서 재앙적으로 증폭되지만, 확률적 백트래킹을 도입하면 수학적으로 증명 가능한 방식으로 이를 억제할 수 있다.

1989년 Sinclair와 Jerrum이 근사적 세기 문제를 위해 설계한 랜덤 워크가, 36년 후 LLM의 추론 품질을 높이는 핵심 도구로 부활했다는 것은 기초 이론의 힘을 보여주는 아름다운 사례다.

2026년 현재, AI 시스템은 점점 더 긴 추론 체인을 통해 복잡한 과제를 해결하고 있다. 이 체인이 길어질수록, 중간 검증의 불완전성은 더 큰 문제가 된다. VGB는 이 문제에 대한 최초의 이론적으로 건전한(provably sound) 해법을 제시한다.

"실수했으면 돌아가서 고치면 된다"는 상식적인 직관을, 수학적으로 엄밀하게 구현하고, 그것이 실제로 작동함을 증명한 것 — 이것이 이 논문의 핵심 기여다.

참고 논문: Dhruv Rohatgi, Abhishek Shetty, Donya Saless, Yuchen Li, Ankur Moitra, Andrej Risteski, Dylan J. Foster. "Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking." arXiv:2510.03149, October 2025.