모델을 바꾸지도 않았고 입력도 같은데, temperature를 0으로 설정했더니 TPS가 눈에 띄게 올랐다는 경험이 있다면 직감은 맞다. "greedy가 빠른 건 당연하지 않나"로 넘기면 이 현상의 절반만 이해한 것이다. 어떤 연산이 줄고, 배치 크기가 커질수록 그 차이가 어떻게 증폭되는지, beam search는 왜 차원이 다른 문제인지를 GPU 커널 수준에서 보면, 디코딩 파라미터가 출력 품질 설정이 아니라 서빙 비용 결정 변수임이 드러난다.
Decode step에서 logit 처리가 놓이는 자리
Autoregressive 디코딩에서 토큰 하나를 생성하는 step을 분해하면:
- Forward pass — attention + FFN 전체. batch × seq_len × hidden_dim 규모의 행렬 연산. step 시간의 대부분.
- lm_head projection — hidden state → logit 벡터. shape:
[batch_size, vocab_size] - Logit 처리 — temperature scaling, top-k/top-p 필터링, sampling
- Embedding lookup — 선택된 token_id → 다음 step 입력
Forward pass가 시간을 압도하기 때문에 logit 처리 비중은 작아 보인다. 문제는 logit 처리 비용이 batch_size × vocab_size에 비례한다는 점이다. Llama-3의 vocab size는 128,256이다. batch=32로 돌리면 logit 텐서는 32 × 128,256 = 약 4.1M 원소이고, fp16으로 잡으면 8MB다. 이 텐서 위에서 무엇을 하느냐가 decode step의 추가 비용을 결정한다.
Greedy Decoding의 실제 연산 비용
Greedy decoding의 연산은 torch.argmax(logits, dim=-1). vocab 전체를 한 번 선형 스캔하는 O(V) reduction이다.
A100 HBM2e의 메모리 대역폭은 약 2 TB/s다. batch=32 고정에서 vocab 크기별로 logit 텐서를 읽는 데 드는 대역폭 소모를 추산하면:
| vocab 크기 | 텐서 크기 (fp16, batch=32) | 대역폭 기준 하한 |
|---|---|---|
| 32,000 (GPT-2 계열) | ~2 MB | ~1 μs |
| 64,000 | ~4 MB | ~2 μs |
| 128,256 (Llama-3) | ~8 MB | ~4 μs |
수 μs가 negligible해 보이지만, 이 연산은 1,000 토큰 생성 시 1,000번 반복된다. 그리고 argmax reduction은 warp 간 partial reduction을 모아야 하는 구조라 실제 커널 시간은 단순 읽기보다 길다. Llama-3처럼 vocab이 128K를 넘는 모델에서 greedy argmax를 "연산 비용 없음"으로 취급하면 오판이다.
Top-p 샘플링의 진짜 비용은 sort다
Top-p(nucleus) 샘플링의 처리 순서:
logits / temperature # element-wise, O(V)
softmax(logits) # O(V)
torch.sort(probs, descending) # O(V log V) ← 병목
torch.cumsum(sorted_probs) # O(V)
mask where cumsum > top_p # O(V)
torch.multinomial(probs) # O(k), k = nucleus 크기
HuggingFace Transformers의 TopPLogitsWarper 구현이 이 순서 그대로다:
sorted_logits, sorted_indices = torch.sort(scores, descending=False)
cumulative_probs = sorted_logits.softmax(dim=-1).cumsum(dim=-1)
sorted_indices_to_remove = cumulative_probs <= (1 - self.top_p)
sorted_indices_to_remove[..., -self.min_tokens_to_keep:] = 0
indices_to_remove = sorted_indices_to_remove.scatter(
1, sorted_indices, sorted_indices_to_remove
)
scores_processed = scores.masked_fill(indices_to_remove, self.filter_value)
temperature 나눗셈, softmax, cumsum, masking은 모두 O(V) 선형이다. sort만 O(V log V). V=128,256이면 log₂V ≈ 17이므로, sort에서 발생하는 비교 연산 횟수가 나머지 단계를 합친 것보다 크다. nucleus sampling을 포함한 cumulative decoding 방법군에서 정렬이 연산 비용을 지배하는 이유가 여기에 있다.
Top-k를 먼저 적용하면 이야기가 달라진다. top-k=50으로 후보를 먼저 자른 뒤 top-p를 적용하면 sort 대상은 50개로 줄어든다. 비교 연산 수가 O(128,256 × 17) ≈ 2.18M에서 O(50 × 6) ≈ 300으로 감소한다. 생성 품질 차이는 크지 않으면서 sampling 경로의 dominant cost를 거의 제거한다.
배치 내 파라미터 이질성이 만드는 추가 비용
continuous batching 환경에서 요청 A가 temperature=0.8, top-p=0.9이고 요청 B가 temperature=0(greedy)라면, 두 요청을 하나의 sampling 커널로 묶을 수 없다. vLLM의 sampler는 SamplingParams를 확인해 greedy path와 random sampling path를 별도로 처리한다. 파라미터가 이질적일수록 커널 실행이 분기되고 GPU 스트림 활용률이 낮아진다.
배치 추론 API에서 디코딩 파라미터를 표준화하는 운영 결정 — temperature=0 고정, 또는 전 요청 동일한 top-k/top-p — 이 throughput에 직접 영향을 준다. 작아 보이는 설정 통일이 서빙 레이어에서 실질적인 차이를 만든다.
Beam Search가 서빙에서 퇴출된 구조적 이유
beam width=B이면 하나의 요청이 B개의 독립 시퀀스를 동시에 유지한다. KV 캐시가 B배로 늘어난다.
Llama-3 8B 기준으로 계산하면 (layers=32, heads=8, head_dim=128, fp16):
시퀀스 하나의 KV 캐시 (seq_len=512)
= 2 (K+V) × 32 (layers) × 512 (seq_len) × 8 (heads) × 128 (head_dim) × 2 (fp16)
= 67,108,864 bytes = 64 MB
| 설정 | 독립 시퀀스 수 | KV 캐시 합계 |
|---|---|---|
| batch=8, greedy | 8 | ~512 MB (0.5 GB) |
| batch=8, beam=4 | 32 | ~2,048 MB (2 GB) |
같은 batch에서 KV 캐시가 4배다. 80GB A100이라도 모델 가중치(약 16GB)와 activation을 제하면 KV 캐시 예산은 제한적이다. beam=4 배치 하나가 greedy 배치 4개를 밀어낸다.
메모리 폭발보다 근본적인 문제는 continuous batching과의 충돌이다. Continuous batching은 시퀀스가 끝나는 즉시 빈 슬롯을 새 요청으로 채운다. Beam search에서는 B개의 beam이 모두 종료될 때까지 슬롯이 점유된다. 동적 슬롯 재활용이 불가능해지고 throughput이 구조적으로 낮아진다.
vLLM 개발팀도 이 충돌을 내부 RFC로 정리했다. GitHub Issue #8306에서 "beam search는 탐색 알고리즘이고 vLLM의 나머지 기능은 샘플링 알고리즘이라 근본적으로 충돌한다"고 명시하며, 투기적 디코딩과 멀티스텝 디코딩에서 beam search를 명시적으로 차단하고 있다. 현재는 vLLM 코어와 분리된 별도 인터페이스(LLM.beam_search)로 이관 중이다.
서빙 SLA별 디코딩 전략 선택
Throughput이 중요한 배치 추론에서는 temperature=0 greedy가 맞다. 연산 복잡도가 가장 낮고 배치 내 모든 요청이 동일 커널 경로를 탄다. vLLM에서 Llama-3 8B를 A100으로 서빙할 때 batch=8 기준 약 195 tok/s가 greedy 또는 단순 sampling 전제의 수치다.
대화형 서비스에서 다양성이 필요하면 top-k=50, top-p=0.9 조합을 쓴다. top-p 단독 대비 sort 비용이 극적으로 낮고, 배치 내 파라미터를 통일하면 커널 분기도 없어진다.
Beam search는 실시간 서빙 경로에 넣지 않는다. 오프라인 평가나 단일 요청 고품질 생성에서만 선택지가 되고, KV 캐시 4배 증가와 continuous batching 슬롯 비효율을 감안하면 서빙 SLA 안에서 쓸 이유가 없다.