디코딩: 온도, top-p, 빔 탐색(Decoding: temperature, top-p and beam search)

언어 모델은 다음 토큰의 확률 분포를 줄 뿐, 무엇을 쓸지는 정하지 않습니다. 분포에서 토큰 하나를 고르고, 그것을 문맥에 붙여 다시 분포를 얻고, 또 고르는 일을 되풀이하는 규칙이 디코딩입니다. 아래는 "오늘 날씨가 정말" 뒤에 올 후보 12개와 모델이 준 점수(로짓⁠, logit⁠) z입니다. 설명을 위해 정한 값입니다. 확률은 소프트맥스⁠(softmax)⁠로 얻습니다.

$$p_i(T) = \frac{e^{z_i/T}}{\sum_j e^{z_j/T}}$$

방식: . 온도 T = , k = , p = .

열 번 뽑기

온도. 로짓을 T로 나누면, T가 작을수록 큰 점수가 더 크게 앞서서 분포가 1등 하나로 몰립니다. T → 0이면 늘 1등만 고르는 탐욕 디코딩⁠(greedy decoding)⁠이 됩니다. T = 1이면 모델의 분포 그대로이고, T가 크면 고른 분포에 가까워집니다. 이름은 물리에서 왔습니다. 에너지가 E인 상태가 온도 T에서 나타날 확률이 $e^{-E/kT}$에 비례한다는 볼츠만 분포⁠(Boltzmann distribution)⁠와 같은 식이고, 로짓이 음의 에너지 구실을 합니다. 이 지수 꼴에는 정확한 이유가 있습니다. '로짓의 기댓값⁠(expected value)⁠ $\sum_i p_i z_i$가 μ'라는 조건만 지키면서 엔트로피⁠(entropy)⁠가 가장 큰 분포를 찾으면 라그랑주 승수법으로 $p_i \propto e^{\beta z_i}$가 나옵니다(최대 엔트로피 원리⁠, principle of maximum entropy⁠). μ가 고른 분포에서의 평균⁠(mean)⁠과 가장 큰 로짓 사이에 있으면 β = 1/T는 양수입니다. 곧 온도를 바꾸는 것은 '평균 점수를 이만큼 지키면서 가장 덜 단정적인 분포'들의 한 줄을 따라 움직이는 것입니다. T를 올리면 엔트로피는 줄곧 늘어납니다($dH/dT = \operatorname{Var}_p(z)/T^3 > 0$, 로짓이 모두 같지만 않다면).

꼬리 자르기. 실제 어휘는 수만 개라서, 하나하나는 가능성이 아주 낮은 토큰들이 모여 무시할 수 없는 몫을 차지합니다. 예를 들어 확률 0.00003짜리 토큰 1만 개를 모으면 0.3입니다. 그대로 뽑으면 평균 열 번에 세 번은 이 꼬리에서 엉뚱한 토큰이 나오고, 한 번 끼어든 엉뚱한 토큰은 뒤의 문맥을 계속 흔듭니다. top-k(2018년 앤절라 팬 등)는 확률이 큰 k개만 남기고, top-p(핵 샘플링⁠(nucleus sampling)⁠, 2019년 아리 홀츠먼 등)는 큰 것부터 더해 누적 확률이 처음으로 p 이상이 되는 가장 작은 집합⁠(set)⁠만 남깁니다. 어느 쪽이든 남은 후보끼리 합이 1이 되도록 다시 나눕니다. top-p는 분포가 뾰족하면 후보를 적게, 평평하면 많이 남기므로 k를 문맥마다 저절로 조절하는 셈입니다.

탐욕 디코딩과 빔 탐색. 번역이나 요약처럼 '가장 그럴듯한 한 문장'을 원할 때는 뽑지 않고 확률이 가장 큰 문장을 찾으려 합니다. 문장의 확률은 조건부 확률⁠(conditional probability)⁠의 곱이므로, 매번 1등 토큰을 고르는 탐욕 디코딩이 가장 확률이 큰 문장을 준다는 보장은 없습니다. 첫 토큰에서 조금 앞선 쪽이 뒤에서 크게 밀릴 수 있기 때문입니다. 빔 탐색은 매 단계 지금까지의 곱이 가장 큰 후보 문장 B개(빔 너비)를 남기고, 각각을 한 토큰씩 늘린 모든 후보 가운데서 다시 B개를 남깁니다. 너비 1은 탐욕 디코딩과 같습니다. 빔 너비:

이 나무에서 탐욕 디코딩(너비 1)은 첫 단계의 0.5를 따라가 0.5 × 0.4 × 0.6 = 0.12를 얻습니다. 너비 2는 '책을 읽고'(0.4 × 0.9 = 0.36)를 살려 0.162를 찾지만, 둘째 단계에서 셋째로 밀린 '빵을 샀다'(0.175)를 버립니다. 너비 3에서야 모든 문장 가운데 가장 큰 0.175를 찾습니다. 너비를 늘리면 대개 나아지지만, 너비가 모든 후보를 담을 만큼 크지 않은 한 최선을 보장하지는 않습니다.

그러면 전부 살펴보면 되지 않을까요? 어휘가 5만 개이고 길이가 20이면 후보 문장은 $50000^{20} \approx 10^{94}$개입니다. 은닉 마르코프 모델⁠(hidden Markov model)⁠에서는 비터비 알고리즘⁠(Viterbi algorithm)⁠이 가장 그럴듯한 상태 열을 정확히 찾습니다. 다음 단계가 지금 상태 하나(몇십 가지)에만 달려 있어서, 동적 계획법⁠(dynamic programming)⁠으로 겹치는 계산을 한 번씩만 할 수 있기 때문입니다. 트랜스포머⁠(transformer)⁠의 '상태'는 앞의 토큰 전체라서, 서로 다른 두 접두어가 같은 상태로 합쳐지는 일이 없습니다. 동적 계획법이 아낄 겹치는 계산이 없으니, 정확한 탐색은 최악의 경우 후보를 거의 다 살펴야 합니다. 그래서 보통은 빔 탐색 같은 근사에 기댑니다. 매 단계 눈앞의 최선을 고르는 욕심쟁이 알고리즘⁠(greedy algorithm)⁠이 전체 최선을 놓치는 전형적인 경우이고, 후보를 몇 개만 남기고 가지를 치는 것은 게임 트리⁠(game tree)⁠ 탐색과 닮았습니다.

더 곤란한 사실도 있습니다. 확률이 가장 큰 문장이 가장 좋은 문장은 아닐 수 있습니다. 확률의 곱은 토큰이 늘 때마다 1보다 작은 수를 곱하므로 짧은 문장을 편애하고(그래서 흔히 길이로 나눠 보정합니다), 같은 말을 되풀이하는 문장이 높은 확률을 받기도 합니다. 2019년 펠릭스 스탈베르크와 빌 번은 한 기계 번역⁠(machine translation)⁠ 모델에서 가지치기를 곁들인 정확한 탐색으로 확률이 가장 큰 번역을 찾았더니, 절반이 넘는 문장에서 빈 번역이 1등이었다고 보고했습니다. 그들은 빔 탐색이 잘 되는 것이 어느 정도는 탐색이 부정확한 덕분이라고 해석했습니다. 모델의 결함을 디코딩 규칙이 가려 주는 셈입니다.

반대로 T = 1에서 자르지 않고 한 토큰씩 뽑으면, 곱셈 규칙 덕분에 문장 전체가 모델의 결합 분포⁠(joint distribution)⁠ $q(x_1, \dots, x_n)$에서 정확히 뽑힙니다. 온도와 자르기는 이 분포를 일부러 바꾸는 선택입니다. 한 가지 짚어 둘 점은, 토큰마다 온도 T를 적용하는 것이 문장 전체의 분포를 $q(x)^{1/T}$에 비례하게 만드는 것과 같지 않다는 것입니다. 토큰마다 다시 나누는 정규화 상수가 문맥마다 달라서입니다. 어떤 규칙이 '좋은' 글을 주는지는 과제마다 실험으로 정합니다.

이어지는 곳. 온도가 있는 소프트맥스는 어텐션⁠(attention)⁠의 가중치⁠(weight)⁠에도, 인간 피드백 강화 학습⁠(reinforcement learning)⁠의 최적 정책 $\pi^\ast \propto \pi_{\text{ref}}\,e^{r/\beta}$에도 같은 모양으로 나옵니다. 그 지수 꼴의 뿌리는 최대 엔트로피 원리이고, 분포가 얼마나 퍼졌는지는 엔트로피로 잽니다. 무작위로 뽑아 문장을 만드는 것은 몬테카를로 방법⁠(Monte Carlo method)⁠처럼 분포에서 표본⁠(sample)⁠을 얻는 일이고, 정확한 최선을 찾는 길이 막힌 이유는 동적 계획법이 기대는 겹치는 부분 문제⁠(overlapping subproblems)⁠가 없기 때문입니다. 디코딩이 고르는 것은 토큰 번호이고, 번호를 글로 되돌리는 사전은 토큰화가 정합니다. 같은 질문에 온도를 올려 풀이를 여러 번 뽑은 뒤 최종 답을 다수결로 고르는 방법(자기 일관성⁠(self-consistency)⁠, 2022년)은 답할 때 계산을 더 써서 정확도를 올리는 흔한 방법이고, 이 방향은 추론 모델에서 이어집니다.