언어 모델 (Language Model)이나 번역 디코더 (Translation Decoder)가 텍스트를 작성할 때, 모델은 결코 완성된 문장을 한 번에 건네주지 않습니다. 모델은 오직 한 가지만을 제공합니다. 즉, 지금까지 작성된 모든 내용을 바탕으로 한 다음 토큰 (Token)의 확률입니다. 이를 전체 문장으로 만드는 것은 매 단계마다 당신이 내려야 하는 결정이며, 그 결정을 어떻게 내리느냐에 따라 출력 결과가 완전히 달라집니다.

오늘 (나의 DeepLearningFromZero 시리즈 25일 차) 저는 실제 확률 트리 (Probability Tree)에서 이러한 결정들이 어떻게 이루어지는지 직접 확인할 수 있도록, 작고 완전히 상호작용 가능한 빔 서치 (Beam Search) 시각화 도구를 만들었습니다.

여기에서 직접 체험해 보세요: https://dev48v.infy.uk/dl/day25-beam-search.html

디코딩 (Decoding)은 탐색 문제이다

완성된 문장의 확률은 각 단계별 확률들의 곱입니다. 문제는 가능한 문장의 수가 어휘 사전 크기 (Vocabulary Size)의 길이를 거듭제곱한 값, 즉 수십억, 수조 개에 달한다는 점입니다. 이 모든 문장의 점수를 매겨서 가장 좋은 것을 고를 수는 없습니다. 따라서 디코딩은 각 노드 (Node)가 부분 문장이고 각 가지 (Branch)가 가능한 다음 단어인 거대한 트리 (Tree)를 통과하는 일종의 탐색 (Search) 과정입니다.

탐욕적 방식 (Greedy): 빠르지만 근시안적이다

가장 단순한 탐색은 탐욕적 방식 (Greedy)입니다. 매 단계에서 단 하나의 가장 높은 확률을 가진 토큰을 선택하고 절대 뒤를 돌아보지 않습니다. 이 방식은 빠르고 추가적인 메모리가 필요하지 않습니다. 하지만 근시안적입니다. 지금 당장 가장 좋아 보이는 단어가 모든 후속 문장을 평범하게 만드는 막다른 길로 이어질 수 있는 반면, 지금은 약간 덜 좋아 보이는 단어가 훨씬 더 나은 문장을 열어줄 수도 있습니다. 탐욕적 방식은 각 단계에서 결정을 확정 지으며, 초기에 저지른 실수를 결코 되돌릴 수 없습니다.

데모에서 빔 너비 (Beam Width)를 k = 1로 설정해 보세요 (이것이 정확히 탐욕적 방식입니다). 모델이 가장 가능성 높은 첫 단어를 잡은 뒤, 더 넓은 탐색을 통해 찾아낸 문장보다 점수가 낮은 문장에 갇히게 되는 과정을 지켜보십시오.

빔 서치 (Beam Search): 상위 k개를 유지하라

빔 서치 (Beam Search)는 단 하나의 조절 장치인 빔 너비 (Beam Width) k를 통해 탐욕적 방식을 일반화합니다. 하나의 부분 문장만 유지하는 대신, 매 단계마다 가장 좋은 k개의 문장을 유지합니다. 각 반복 (Iteration)은 세 가지 동작으로 이루어집니다:

1. 확장 (Expand) — 살아남은 모든 가설 (Hypothesis)을 가능한 모든 다음 토큰 (Token)으로 확장합니다.
2. 점수 계산 (Score) — 각 후보 (Candidate)에 대해 부모의 누적 점수에 새로운 토큰의 로그 확률 (Log-probability)을 더합니다.
3. 가지치기 (Prune) — 모든 후보를 정렬하여 상위 k개만 유지하고 나머지는 버립니다.

문장 종료 (End-of-sequence) 토큰을 생성하는 모든 가설은 완료된 것으로 간주하여 따로 분류합니다. 빔 (Beam)이 빌 때까지 이 과정을 반복합니다. k = 1이면 탐욕적 (Greedy) 방식이 되며, k가 전체 어휘 (Vocabulary) 크기에 가까워질수록 가장 확률이 높은 문장을 찾는 것이 보장되는 전수 조사 (Exhaustive search)에 가까워집니다. 실제 번역에서는 k = 4에서 10 정도의 작은 빔을 사용하는데, 이는 비용은 계속 상승하는 반면 성능 향상은 빠르게 정체되기 때문입니다.

왜 로그 확률 (Log-probabilities)인가?

점수 계산에는 확률의 생으로 된 곱 (Raw product)이 아니라, 경로를 따라 로그 p를 합산한 **누적 로그 확률 (Cumulative log-probability)**을 사용합니다. 1보다 작은 수들을 여러 번 곱하면 아주 짧은 시퀀스가 아닌 이상 부동 소수점 (Floating point) 연산에서 언더플로 (Underflow)가 발생하여 0이 되어버립니다. 로그를 취하면 이 취약한 곱셈을 안정적인 덧셈으로 바꿀 수 있으며, 로그 함수는 단조 증가 (Monotonic) 함수이므로 순위는 변하지 않습니다. 즉, 가장 가능성 높은 문장은 여전히 가장 높은 점수를 갖게 됩니다. 데모의 모든 박스는 이 누적 합계를 보여줍니다.

빔 서치는 휴리스틱 (Heuristic)이지 보장이 아니다

빔 폭이 넓을수록 항상 단 하나의 가장 확률 높은 문장을 반환할 것이라고 생각하기 쉽습니다. 하지만 k가 전체 어휘 크기와 같지 않은 한 그렇지 않습니다. 만약 실제 최적의 문장이 약해 보이는 토큰들로 시작한다면, 그 문장의 강력한 결말이 나타나기도 전에 접두사 (Prefix) 단계에서 가지치기 될 수 있습니다. 빔 서치는 제한된 폭을 가진 최선 우선 탐색 (Best-first search)입니다. 탐욕적 방식보다는 훨씬 낫지만, 여전히 근사치 (Approximation)입니다.

짧은 시퀀스 편향 (Short-sequence bias), 그리고 해결 방법

여기에 미묘한 함정이 있습니다. 토큰이 추가될 때마다 음의 로그 확률 (negative log-probability)이 더해지기 때문에, 긴 문장은 거의 항상 짧은 문장보다 점수가 낮게 나옵니다. 따라서 빔 서치 (Beam search)는 문장 종료 토큰 (end-of-sequence token)을 선호하게 되어 결과물이 짧게 끊기는 현상이 발생합니다. 표준적인 해결책은 **길이 정규화 (length normalization)**입니다. 최종 점수를 길이에 $\alpha$ 승을 한 값(보통 0.6에서 0.7 사이)으로 나누는 방식입니다. 데모에서 이 기능을 켜고 더 길고 잘 구성된 문장이 짧은 문장을 추월하는 것을 확인해 보세요. 승자가 실제로 뒤바뀔 것입니다.

빔 (Beam) vs 샘플링 (Sampling)

빔 (Beam)은 결정론적 (deterministic)이며 가장 확률이 높은 텍스트를 쫓습니다. 이는 정답이 존재하는 상황에서 원하는 방식입니다. 하지만 개방형 글쓰기 (open-ended writing)의 경우, 가장 확률이 높은 다음 내용은 종종 단조롭거나 반복적일 수 있습니다. **샘플링 (Sampling)**은 이와 반대로 동작합니다. 확률을 최대화하는 대신, 온도 (temperature) 및 top-k / top-p (nucleus)에 의해 형성된 분포로부터 다음 토큰을 추출합니다. 그 결과는 다양하고 창의적이지만, 문맥에서 벗어날 위험이 있습니다.

경험 법칙 (rule of thumb)은 다음과 같습니다. 번역, 요약, 음성 인식 (speech-to-text) 및 코드에는 **빔 (beam)**을 사용하고, 챗봇, 이야기 쓰기 및 브레인스토밍에는 **샘플링 (sampling)**을 사용하세요. 현대의 채팅 모델은 샘플링을 사용하고, Google Translate는 빔을 사용합니다. 최대 가능도 (Maximum likelihood)가 곧 최상의 품질을 의미하는 것은 아닙니다.

이 시각화 도구는 스크립트된 확률 트리 (probability tree) 상에서 실제 로그 확률 (log-prob) 계산과 실제 top-k 가지치기 (pruning)를 수행하며, 단계별 설명과 처음부터 구현한 Python 구현체를 제공합니다. 확인해 보세요:

https://dev48v.infy.uk/dl/day25-beam-search.html