Beam Search

Beam Search란? 수식 이미지 인식, Image Captioning, VLM에서의 활용

Beam Search란?

Beam Search는 기계 번역, 텍스트 요약, Image Captioning, 수식 이미지 인식과 같이 Sequence를 순차적으로 생성하는 문제에서 좋은 출력 Sequence를 찾기 위해 사용되는 휴리스틱 탐색 방법이다.

Autoregressive 모델은 이전까지 생성된 Token을 조건으로 다음 Token의 확률 분포를 계산하고, 이를 반복하면서 전체 Sequence를 생성한다.

P(y1 | x) P(y2 | x, y1) P(y3 | x, y1, y2) ... P(yn | x, y1, y2, ..., y(n-1))

여기서 중요한 점은 Autoregressive Generation 자체가 Beam Search를 의미하는 것은 아니라는 것이다.

Autoregressive 모델이 다음 Token의 확률 분포를 계산한 뒤, 실제로 어떤 Token을 선택할 것인지는 별도의 Decoding 전략에 의해 결정된다.

Autoregressive Model → Next Token Probability → Decoding Strategy → Output Sequence

Decoding 방법에는 Greedy Search, Beam Search, Top-k Sampling, Top-p Sampling, Temperature Sampling 등이 있다.

핵심 개념

Autoregressive는 이전 Token을 기반으로 다음 Token을 하나씩 생성하는 방식이다.

Beam Search는 그 생성 과정에서 여러 후보 Sequence를 동시에 유지하며 탐색하는 Decoding 전략 중 하나이다.

Greedy Search와 Beam Search

가장 단순한 Decoding 방법인 Greedy Search는 각 단계에서 가장 높은 확률을 가진 Token 하나만 선택한다.

하지만 현재 단계에서 가장 높은 확률의 Token이 전체 Sequence 관점에서도 항상 가장 좋은 선택이라고 보장할 수는 없다.

초반에 선택한 하나의 Token이 이후의 모든 Token 생성에 영향을 주기 때문이다.

Greedy Search

매 단계에서 가장 높은 확률의 Token 하나만 선택한다.

cat : 0.40 ← 선택 dog : 0.35 bird : 0.15 car : 0.10

Beam Search

Beam Size가 2라면 상위 2개의 후보를 유지한다.

Candidate 1 → cat Candidate 2 → dog

이후 Beam Search는 각 후보를 다시 확장하고, 전체 Sequence Score를 계산하여 가능성이 낮은 후보를 제거한다.

Beam Size란?

Beam Search에서 가장 중요한 파라미터 중 하나는 Beam Size이다.

Beam Size는 각 탐색 단계에서 유지하는 최대 후보 Sequence의 개수를 의미한다. 일반적으로 beam size = K라고 표현한다.

• Beam Size가 큰 경우: 더 많은 후보를 탐색할 수 있지만 계산량과 메모리 사용량이 증가한다.
• Beam Size가 작은 경우: 추론 속도는 빨라지지만 좋은 후보를 초기에 제거할 가능성이 높아진다.
• Beam Size = 1: 일반적인 경우 Greedy Search와 같은 방식으로 동작한다.

따라서 Beam Size가 클수록 항상 좋은 것은 아니며, 정확도와 추론 속도를 고려하여 적절한 값을 선택해야 한다.

Beam Search 알고리즘

1.

초기화

탐색은 일반적으로 시작 Token인 SOS (Start Of Sequence) 또는 BOS (Beginning Of Sequence)에서 시작한다.

2.

후보 확장

현재 유지되고 있는 각각의 Sequence에 대해 모델이 다음 Token의 확률 분포를 계산한다.

각 Sequence는 가능한 다음 Token과 결합되어 새로운 후보 Sequence로 확장된다.

3.

Sequence Score 계산

각 후보 Sequence의 점수는 일반적으로 Token별 로그 확률을 누적하여 계산한다.

score(sequence) = log P(y1) + log P(y2 | y1) + log P(y3 | y1, y2) + ...

확률을 직접 곱하는 대신 로그 확률을 사용하면, 매우 작은 확률값이 반복적으로 곱해지면서 발생하는 수치적인 문제를 줄일 수 있다.

4.

상위 후보 선택

생성된 모든 후보 중에서 점수가 높은 상위 K개의 Sequence만 유지한다.

여기서 K가 바로 Beam Size이며, 나머지 후보는 다음 탐색 단계에서 제거된다.

5.

종료 조건 확인

후보 Sequence가 EOS (End Of Sequence)를 생성하면 완성된 Sequence로 간주한다.

• 최대 Sequence 길이에 도달한 경우
• 필요한 개수의 완성된 후보를 확보한 경우
• 모든 유효한 Beam이 EOS에 도달한 경우

6.

최종 결과 선택

탐색이 종료되면 완성된 후보 가운데 가장 높은 Sequence Score를 가진 결과를 최종 출력으로 선택한다.

Greedy Search와 Beam Search 비교

항목	Greedy Search	Beam Search
유지하는 후보 수	1개	K개
탐색 범위	좁음	상대적으로 넓음
추론 속도	빠름	상대적으로 느림
메모리 사용량	적음	Beam Size에 따라 증가
Sequence 탐색 능력	현재 단계의 최선만 선택	여러 후보 경로를 동시에 탐색

수식 이미지 인식에서 Beam Search

수식 이미지 인식(Formula Image Recognition)은 수학 수식 이미지를 입력으로 받아 LaTeX와 같은 Token Sequence로 변환하는 문제이다.

예를 들어 이미지에 다음과 같은 수식이 있다고 가정해보자.

a + b y = ───── c

수식 인식 모델의 최종 출력은 다음과 같은 LaTeX Sequence가 될 수 있다.

y = \frac{a+b}{c}

수식 이미지 인식 모델의 일반적인 구조

Formula Image → Image Encoder → Visual Feature → Decoder → LaTeX Sequence

Encoder는 CNN이나 Vision Transformer 등을 이용하여 이미지의 시각적 특징을 추출한다.

Decoder는 추출된 Feature와 이전까지 생성된 Token을 이용하여 다음 LaTeX Token을 Autoregressive하게 생성한다.

왜 Beam Search가 유용한가?

수식 인식에서는 특정 Token 하나가 잘못 생성되면 전체 LaTeX 구조가 달라질 수 있다.

예를 들어 특정 시점에 모델이 다음과 같은 Token 확률을 출력했다고 가정해보자.

\frac : 0.45 ( : 0.40 \sqrt : 0.15

Greedy Search는 가장 높은 확률을 가진 \frac만 선택한다.

그러나 이후의 Token까지 고려하면 (로 시작하는 Sequence의 전체 점수가 더 높아질 가능성도 있다.

Beam Search는 여러 후보를 동시에 유지하기 때문에 이러한 가능성을 조금 더 넓게 탐색할 수 있다.

수식 인식에서의 적용 과정

1.

이미지 Feature 추출

수식 이미지를 Encoder에 입력하여 문자, 수학 기호, 공간적 배치 등의 특징을 추출한다.

2.

첫 번째 Token 예측

Decoder는 BOS 또는 SOS를 입력으로 받아 첫 번째 LaTeX Token의 확률 분포를 계산한다.

3.

상위 후보 Sequence 유지

가장 높은 점수를 가진 K개의 LaTeX 후보 Sequence를 유지한다.

4.

후보 Sequence 확장

각각의 후보에 새로운 Token을 추가하고 누적 Sequence Score를 다시 계산한다.

5.

최종 LaTeX 선택

EOS에 도달한 후보 중 가장 높은 점수를 가진 LaTeX Sequence를 최종 결과로 선택한다.

생성될 수 있는 후보 예시

Candidate 1 \frac{a+b}{c} Candidate 2 \frac{a+6}{c} Candidate 3 \frac{\alpha+b}{c}

수식 이미지에는 b와 6, a와 \alpha처럼 형태가 비슷한 문자나 수학 기호가 많이 존재한다.

또한 분수, 첨자, 제곱근, 행렬처럼 2차원 구조를 1차원의 LaTeX Token Sequence로 표현해야 하기 때문에 Token 간 장기적인 의존 관계가 중요하다.

• 비슷한 형태의 문자와 기호를 구분해야 한다.
• LaTeX 문법 구조가 길고 복잡할 수 있다.
• 중괄호의 열고 닫음과 같은 장기 의존 관계가 존재한다.
• 2차원 수식 구조를 1차원 Sequence로 변환해야 한다.
• 초기 Token 오류가 이후 전체 Sequence에 영향을 줄 수 있다.

Image Captioning에서 Beam Search

Image Captioning은 이미지를 입력받아 이미지의 내용을 설명하는 자연어 문장을 생성하는 Task이다.

Image → Vision Encoder → Visual Feature → Language Decoder → Caption

예를 들어 강아지가 공원에서 뛰고 있는 이미지가 입력되었다면, 모델은 다음과 같이 여러 Caption 후보를 생성할 수 있다.

Candidate 1 A dog is running in the park. Candidate 2 A dog is playing outside. Candidate 3 A brown dog is running on the grass.

Greedy Search는 각 단계에서 가장 높은 확률의 단어 하나만 선택하기 때문에, 초반에 선택한 단어가 이후 문장 구조에 큰 영향을 줄 수 있다.

Beam Search는 여러 Caption 후보를 유지하면서 전체 문장의 Sequence Score를 비교할 수 있다.

간단한 예시

현재까지 다음과 같은 문장이 생성되었다고 가정해보자.

A dog is

모델은 다음 Token에 대해 아래와 같은 확률을 출력할 수 있다.

running : 0.40 playing : 0.35 standing : 0.15 walking : 0.10

Beam Size가 2라면 다음 두 후보를 유지할 수 있다.

A dog is running A dog is playing

이후 두 Sequence를 각각 계속 확장하면서 전체 문장 단위의 점수를 비교하여 최종 Caption을 선택한다.

VLM에서 Beam Search

VLM(Vision-Language Model)은 이미지와 자연어 정보를 함께 처리하여 텍스트 형태의 결과를 생성할 수 있는 모델이다.

많은 생성형 VLM 역시 Language Model과 마찬가지로 출력 Token을 Autoregressive하게 생성한다.

Image + Prompt → VLM → Text Sequence

P(y1 | image, prompt) P(y2 | image, prompt, y1) P(y3 | image, prompt, y1, y2) ...

따라서 VLM에서도 Greedy Search, Beam Search, Top-k Sampling, Top-p Sampling 등 다양한 Decoding 방법을 적용할 수 있다.

VLM에서 적용할 수 있는 Task

• Image Captioning: 이미지 내용을 설명하는 여러 문장 후보를 탐색한다.
• Visual Question Answering: 이미지와 질문을 기반으로 답변 Sequence를 생성한다.
• Document Understanding: 문서 이미지를 분석하여 Text 또는 구조화된 출력을 생성한다.
• OCR / Formula Recognition: 이미지 속 문자나 수식을 Token Sequence로 변환한다.
• Chart / Table Understanding: 표와 차트를 분석하여 설명이나 구조화된 정보를 생성한다.

VLM에서는 항상 Beam Search를 사용하는가?

그렇지는 않다. Autoregressive 방식으로 Token을 생성한다고 해서 대부분의 모델이 Beam Search를 사용하는 것은 아니다.

정답 Sequence가 비교적 명확한 OCR, 수식 인식, 번역 등의 문제에서는 Beam Search가 유용할 수 있다.

반면 자유로운 이미지 설명, 대화, 창의적인 문장 생성처럼 다양한 표현이 필요한 Task에서는 Sampling 기반 Decoding이 더 적합할 수 있다.

Task 특성	주로 고려할 수 있는 Decoding
정답 형태가 비교적 명확함	Greedy Search / Beam Search
정확한 구조 생성이 중요함	Beam Search / Constrained Decoding
자연스러운 대화 생성	Top-p / Top-k / Temperature Sampling
출력 다양성이 중요함	Sampling 계열

Sequence Score와 Length Penalty

기본 Beam Search에서는 일반적으로 각 Token의 로그 확률을 누적하여 Sequence Score를 계산한다.

그러나 로그 확률은 대부분 음수이기 때문에 Sequence가 길어질수록 누적 점수가 낮아지는 경향이 있다.

이로 인해 상대적으로 짧은 Sequence가 유리해질 수 있으며, 이를 완화하기 위해 Length Penalty 또는 길이 정규화를 적용하기도 한다.

normalized_score = sequence_score / length_penalty

특히 번역이나 Image Captioning처럼 출력 길이가 다양하게 나타나는 문제에서는 Sequence 길이에 대한 보정이 중요한 요소가 될 수 있다.

Beam Search의 장점과 단점

장점

• Greedy Search보다 넓은 후보 공간을 탐색할 수 있다.
• 완전 탐색보다 훨씬 적은 계산량으로 탐색할 수 있다.
• 초기 Token 선택 오류의 영향을 어느 정도 완화할 수 있다.
• 전체 Sequence Score를 고려하여 결과를 선택할 수 있다.
• 수식 인식, OCR, 번역 등 구조적인 출력 문제에 활용하기 좋다.

단점

• Beam Size가 증가할수록 연산량이 증가한다.
• 여러 Sequence를 유지해야 하므로 메모리 사용량이 증가한다.
• Beam Size가 크다고 항상 더 좋은 결과가 나오는 것은 아니다.
• 비슷한 후보들이 Beam을 차지해 다양성이 낮아질 수 있다.
• 실시간 서비스에서는 추론 속도에 부담이 될 수 있다.

Task별 Beam Search 활용

Task	입력	출력	Beam Search 역할
Machine Translation	문장	번역 문장	여러 번역 Sequence 탐색
Text Summarization	긴 Text	요약 문장	여러 요약 후보 비교
Image Captioning	이미지	설명 문장	여러 Caption 후보 비교
Formula Recognition	수식 이미지	LaTeX	여러 LaTeX Sequence 탐색
OCR	문자 이미지	Text	여러 문자 Sequence 탐색
VLM	Image + Prompt	Text	출력 특성에 따라 Beam Search 적용 가능

정리

Beam Search는 Autoregressive 모델이 Token을 생성할 때 사용할 수 있는 여러 Decoding 전략 중 하나이다.

Greedy Search처럼 하나의 후보만 선택하지 않고 여러 Sequence를 동시에 유지하기 때문에, 전체 Sequence 관점에서 더 좋은 결과를 탐색할 가능성이 있다.

특히 수식 이미지 인식에서는 하나의 잘못된 Token이 이후 LaTeX 구조 전체에 영향을 줄 수 있기 때문에 Beam Search가 효과적인 Decoding 방법이 될 수 있다.

Image Captioning에서도 여러 문장 후보를 비교할 수 있으며, VLM에서도 출력이 Autoregressive하게 생성된다면 Beam Search를 적용할 수 있다.

다만 모든 Autoregressive 모델이 Beam Search를 사용하는 것은 아니다. 대화형 LLM이나 자유로운 생성형 VLM처럼 다양성과 자연스러운 표현이 중요한 Task에서는 Top-p, Top-k, Temperature Sampling과 같은 Sampling 기반 방법이 더 적합할 수 있다.

핵심 요약

• Autoregressive: 이전 Token을 기반으로 다음 Token을 순차적으로 생성하는 방식
• Greedy Search: 각 단계에서 가장 높은 확률의 Token 하나를 선택
• Beam Search: 각 단계에서 상위 K개의 Sequence를 유지하면서 탐색
• Beam Size 증가: 탐색 범위가 넓어지지만 계산량과 메모리 사용량도 증가
• Formula Recognition: 여러 LaTeX 후보를 비교하여 더 적절한 수식 Sequence를 탐색
• Image Captioning: 여러 Caption 후보의 전체 Sequence Score를 비교
• VLM: Task 특성에 따라 Beam Search 또는 Sampling 기반 Decoding을 선택