테스트 타임 스케일링 이론 분석: 백트래킹 알고리즘 VGB가 검증자 오차를 넘어서는 방법

핵심 메시지

• 논문은 테스트 타임 정렬을 KL 규제 보상 최대화로 쓰고, 그 최적 정책이 사전학습 모델 분포에 보상의 지수항을 곱해 정규화한 분포와 같다는 점을 이용해 문제를 샘플링 문제로 환원한다.
• 프로세스 보상 모델이 참값을 곱셈 오차 안에서 근사한다고 가정하면, 액션 단위 리젝션 샘플링의 결과 정책은 최적 정책과의 거리가 오차와 컨텍스트 길이의 제곱근을 곱한 값 아래로 내려갈 수 없다는 하한이 나온다.
• 제안 알고리즘 VGB는 생성 트리에서 다음 토큰으로 전진하기만 하지 않고 확률적으로 앞 단계로 되돌아가며, 절반의 확률로는 제자리에 머문다. 다음 토큰들의 가치가 낮을 때 되돌아갈 확률이 커진다.
• 완성된 답변에 대한 평가만은 정확하다는 가정이 더해지면, 스텝 수를 늘리는 대가로 최적 정책과의 거리를 원하는 만큼 작게 줄일 수 있다는 보장이 나온다.
• 발표자는 이론적 기법 자체는 견고하지만 스텝 수가 컨텍스트 길이의 제곱 규모로 붙어, 수십만에서 100만 토큰을 다루는 지금의 모델에는 아직 실용적이지 않다고 평가한다.

쉽게 이해하기

테스트 타임 스케일링은 보상 모델을 두고 추론 시점의 계산량을 늘려 답변 품질을 끌어올리는 기법이며, 답을 끝까지 만든 뒤 전체를 평가하는 방식뿐 아니라 중간 단계마다 점수를 주는 프로세스 보상 모델을 쓰는 경우도 많다. 여러 실험 연구에서 이 프로세스 보상 모델이 중간 상태의 기대 보상을 잘 근사하지 못하면 오차가 누적돼 정답에서 멀어진다는 관측이 나왔고, 발표에서 다루는 논문은 그 문제를 이론적 관점에서 파고든다. 논문은 사전학습 모델에서 너무 멀어지지 않도록 발산 항으로 규제한 보상 최대화 목적을 세운 뒤, 이를 최대화하는 최적 정책이 사전학습 분포에 보상을 지수화한 항을 곱한 값에 비례한다는 사실을 증명한다. 그래서 정렬 문제는 그 최적 분포에 가까운 분포에서 생성을 뽑는 샘플링 문제로 바뀌며, 부분 생성 이후 참조 정책으로 끝까지 이어 갔을 때 얻는 값의 평균이 이상적인 가치 함수이고 실제로는 이를 근사하도록 학습한 프로세스 보상 모델을 쓴다.

비교 대상이 되는 베이스라인은 리젝션 샘플링 두 가지다. 전체 답변을 통째로 뽑아 통과할 때까지 되풀이하는 아웃컴 단위 방식은 필요한 샘플 수가 훨씬 많아 성능이 나쁘다고 알려져 있어, 논문은 토큰마다 통과 여부를 따지는 액션 단위 방식과 비교한다. 더 단순한 베스트 오브 엔은 과최적화 문제가 알려져 있어 베이스라인으로 삼지 않는다. 저자들은 상태가 하나이고 행동이 셋인 인위적 예시를 만들어, 검증자 오차가 있으면 결과 정책과 최적 정책 사이 거리가 오차에 길이의 제곱근을 곱한 값 아래로 줄어들 수 없음을 보인다. 답변이 길어질수록 오차가 증폭된다는 관찰을 수식으로 못 박은 셈이다.

VGB는 생성 과정을 트리로 보고, 현재 부분 생성 지점에서 세 가지 선택을 확률적으로 섞는다. 절반의 확률로는 제자리에 머물고, 나머지는 앞 단계로 되돌아가거나 다음 토큰으로 전진한다. 다음 토큰들의 가치가 상대적으로 낮을 때 되돌아갈 확률이 커지므로, 좋지 않은 경로에 들어섰을 때 한 발 물러나 다시 뽑는 수정이 가능해진다. 제자리 확률을 두는 이유는 성능이 아니라 수학적 안전장치다. 전진과 후진만 오가면 마르코프 체인이 홀짝 깊이를 왕복하는 주기 구조를 갖게 되어 정상 분포로 수렴하지 않기 때문이다.

보장에는 중간 평가는 부정확해도 완성된 생성에 대한 평가는 정확하다는 가정이 추가된다. 완성된 답이 조건을 지켰는지는 대체로 정확히 매길 수 있으니 무리한 가정은 아니다. 이 조건에서 충분한 스텝을 돌리면 마지막에 잎 노드에서 멈출 확률이 길이에 반비례하는 정도로 확보되고, 그 횟수만큼 반복하면 거의 확실하게 완성 답을 얻는다. 무엇보다 최적 정책과의 거리를 원하는 만큼 작게 잡아도 스텝 수를 그만큼 늘리면 달성할 수 있어, 검증자 오차에 갇혀 있던 베이스라인의 한계를 넘는다. 증명은 이론 컴퓨터과학의 기존 아이디어를 일반화해 최적 분포로 수렴하는 마르코프 체인을 구성하는 방식으로, 발표자는 이를 MCMC의 일종으로 볼 수 있다고 설명한다.

실험은 세 과제다. 앞서 하한을 보인 세 행동짜리 과제에서는 오차 발산이 실제로 관측되어, 액션 단위 방식은 길이가 늘어날수록 오차가 커지는데 VGB는 낮게 유지된다. 괄호 짝을 맞춰 나머지를 채우는 과제에서는 학습 분포와 테스트 분포의 괄호 비율을 다르게 두고 정확도와 다양성을 함께 재는데, VGB의 파레토 경계가 블록 단위 베스트 오브 엔이나 블록 리젝션 샘플링보다 유리하게 나온다. 특정 알파벳을 쓰지 않는 32토큰 영어 문장 생성 과제에서는 작은 사전학습 모델을 쓰고 가치 함수의 강도를 여러 값으로 바꿔 비교했는데, 승률과 정규화 로그확률 모두 VGB가 앞섰다.

주요 인사이트

• 오차가 누적된다는 실험적 관찰을 하한 정리로 바꿔 놓은 것이 이 논문의 중심 기여다. 토큰 단위로 아무리 촘촘히 걸러도 검증자에 오차가 있는 한, 답변이 길어질수록 최적 정책에서 멀어지는 폭이 커진다.
• 되돌아가기를 확률적으로 섞는다는 발상은 결국 원하는 분포로 수렴하는 마르코프 체인을 설계하는 문제로 귀결된다. 전진만 하는 알고리즘은 한 번 잘못 든 길을 되돌릴 수단이 없다.
• 제자리에 머무는 확률은 튜닝 트릭이 아니라 수렴을 위한 필수 장치다. 주기 구조를 가진 체인은 정상 분포로 수렴하지 않는다는 성질을 피하기 위한 조치다.
• 중간 점수는 틀려도 최종 답변 채점은 정확하다는 가정은 실무 감각과 잘 맞는다. 조건을 지켰는지 검사할 수 있는 과제라면 이 가정 위에서 이론적 보장을 세울 수 있다.
• 평가 지표에 정확도와 함께 다양성이 들어간 점도 눈에 띈다. 발표자는 없던 결과를 찾아내는 탐색이 가능해지려면 답변의 다양성이 확보돼야 한다는 점에서 최근 이 지표가 주목받는다고 본다.

자주 묻는 질문

관련 AI 소식