Chapter 08

토큰 생성과 디코딩

학습이 끝난 언어 모델이 하는 일은 단 하나, "다음 토큰의 확률 분포"를 내놓는 것이다. 그 분포에서 토큰을 어떻게 고르느냐(디코딩)가 답변의 성격을 바꾸고, 토큰을 하나씩 뽑아야 한다는 사실이 추론 시스템의 비용 구조 전체를 결정한다. 이 장에서는 softmax와 온도에서 출발해 top-k·top-p·min-p·빔 서치를 직접 돌려 보고, prefill과 decode의 차이, KV 캐시와 그 메모리, PagedAttention, 추측 디코딩, 제약 디코딩까지 — 오늘날 LLM 서빙 엔진이 실제로 하는 일을 따라간다.

자기회귀 생성 루프(입력 → 로짓 → 샘플 → 붙이기 → 반복)와 정지 조건을 설명할 수 있다.
온도가 분포의 엔트로피·퍼플렉시티를 어떻게 바꾸는지 계산하고, greedy·top-k·top-p·min-p·반복 패널티의 차이를 안다.
빔 서치가 누적 로그확률을 기준으로 탐색하는 방식과 greedy와의 차이, 한계를 설명할 수 있다.
prefill(계산 바운드)과 decode(메모리 바운드)를 구분하고 TTFT·TPOT·tokens/s를 해석할 수 있다.
KV 캐시가 연산을 O(n²)에서 O(n)으로 줄이는 원리와 그 메모리 크기를 직접 계산할 수 있다.
PagedAttention, 추측 디코딩, 제약 디코딩이 각각 어떤 병목을 푸는지 안다.

자기회귀 생성 루프

7장에서 본 것처럼 언어 모델은 "앞의 토큰들이 주어졌을 때 다음 토큰의 확률"을 학습한다. 문장 전체의 확률은 연쇄법칙으로 이 조건부 확률들의 곱이 된다.

$$P(x_1, \dots, x_n) = \prod_{t=1}^{n} P(x_t \mid x_1, \dots, x_{t-1})$$

여기서 $x_t$는 $t$번째 토큰. 모델은 매 위치에서 어휘 크기 $|V|$만큼의 점수(로짓)를 내놓는다.

그러므로 텍스트를 생성하려면 이 곱을 앞에서부터 하나씩 펼치면 된다. 프롬프트를 넣고, 모델이 마지막 위치에서 내놓는 로짓 벡터 $z \in \mathbb{R}^{|V|}$를 확률로 바꾸고, 거기서 토큰 하나를 고르고, 그 토큰을 입력 끝에 붙여 다시 모델에 넣는다. 이것이 자기회귀 생성(autoregressive generation)이다. 자기 출력이 다음 입력이 되므로 "자기(auto)-회귀(regressive)"라는 이름이 붙었다.

그림 8-1. 자기회귀 생성 루프. 모델은 한 번 호출될 때마다 한 위치의 다음 토큰 분포만 내놓는다. 응답 500토큰을 만들려면 이 루프를 500번 돌아야 한다 — 이것이 LLM 추론이 느리고 비싼 근본 이유다.

루프는 언제 멈출까? 세 가지다. ① 모델이 특수 토큰 EOS(end-of-sequence)를 고르면 멈춘다. 학습 데이터의 문서 끝·대화 턴 끝마다 이 토큰이 붙어 있었으므로 모델은 "이제 끝낼 때"를 확률로 표현할 수 있다(Llama 3의 대화 모델은 <|eot_id|>를 쓴다). ② 사용자가 정한 최대 토큰 수(max_tokens)에 도달하면 강제로 멈춘다. ③ 특정 문자열(예: "\n\nUser:")이 나오면 멈추게 할 수도 있다.

이 구조에서 두 가지 질문이 나온다. 첫째, 분포에서 무엇을 고를 것인가? — 늘 가장 확률이 높은 것을 고를지, 확률에 비례해 뽑을지, 여러 후보를 동시에 탐색할지. 이것이 디코딩 전략이고 출력의 품질과 다양성을 정한다(2~4절). 둘째, 매번 전체 시퀀스를 다시 계산해야 하는가? — 아니다. 이미 계산한 것을 캐시해 재사용할 수 있고, 그 캐시가 서빙 비용의 상당 부분을 차지한다(5~9절).

로짓에서 확률로: softmax와 온도

모델의 마지막 층(LM head)은 은닉 벡터 $h$에 어휘 행렬 $W_U \in \mathbb{R}^{|V| \times d}$를 곱해 로짓 $z = W_U h$를 만든다. Llama 3라면 $|V| = 128{,}256$개의 실수다. 로짓은 아무 범위의 실수이므로 softmax로 확률로 바꾼다. 이때 온도(temperature) $T$로 로짓을 나눈다.

$$p_i = \frac{\exp(z_i / T)}{\sum_{j} \exp(z_j / T)}$$

$T = 1$이면 모델이 학습한 분포 그대로, $T \to 0$이면 최대 로짓 하나에 확률 1(greedy), $T \to \infty$이면 균등 분포에 가까워진다.

온도가 하는 일은 로짓 사이의 간격을 늘리거나 줄이는 것이다. 두 후보의 확률비는 $p_i / p_j = \exp((z_i - z_j)/T)$이므로 로짓 차이가 2일 때 $T = 1$이면 약 7.4배, $T = 0.5$이면 약 55배, $T = 2$이면 약 2.7배가 된다. 또 모든 로짓에 같은 상수를 더해도 확률은 변하지 않는다(분자·분모에 같은 $e^{c/T}$가 곱해짐). 그래서 실제 구현은 수치 안정성을 위해 최대 로짓을 빼고 계산한다.

분포가 얼마나 "퍼져" 있는지는 엔트로피로 잰다. 엔트로피를 지수로 올린 값이 퍼플렉시티(perplexity)인데, "모델이 사실상 몇 개의 후보 중에서 고민하는가"로 읽을 수 있다. 균등한 $k$개 후보면 퍼플렉시티는 정확히 $k$다.

$$H(p) = -\sum_i p_i \log_2 p_i \ \ [\text{bit}], \qquad \mathrm{PPL} = 2^{H(p)}$$

SIMULATOR

온도와 분포

온도 T

왼쪽 막대(로짓)를 좌우로 끌어 값을 바꾼다. 오른쪽 막대는 그 결과로 계산된 확률이다.

최댓값 확률—

엔트로피—

퍼플렉시티—

누적 90%에 필요한 후보—

"오늘 저녁에는 ___" 다음에 올 후보 14개에 손으로 붙인 교육용 로짓이다. 해볼 것: ① T를 0.1로 내리면 1등 확률이 거의 1이 되고 퍼플렉시티가 1에 가까워진다(greedy와 같음). ② T를 3으로 올리면 '우주로', '양자역학을' 같은 엉뚱한 후보도 수 %를 얻는다 — 높은 온도가 왜 "창의적이지만 횡설수설"하는지 보인다. ③ '모든 로짓 +1'을 눌러도 확률이 전혀 변하지 않음을 확인하자(softmax의 이동 불변성). ④ 2등 막대를 1등과 같게 끌어 올리면 두 후보가 정확히 반반이 되고 엔트로피가 1비트 늘어난다.

실무에서의 온도

코드 생성·사실 질의·추출처럼 정답이 하나인 작업은 $T = 0$~$0.3$, 일반 대화는 $0.7$~$1.0$, 브레인스토밍·창작은 $1.0$ 이상을 쓰는 경우가 많다. API에서 $T = 0$은 보통 greedy로 처리되지만, GPU 병렬 연산의 부동소수 합산 순서 차이 등으로 출력이 완전히 결정적이지 않을 수 있다.

디코딩 전략: greedy에서 min-p까지

분포 $p$가 주어졌을 때 토큰을 고르는 방법은 크게 둘이다. 가장 그럴듯한 것을 고르는 결정적 탐색(greedy, 빔 서치)과 확률에 따라 뽑는 확률적 샘플링이다.

Greedy와 순수 샘플링의 문제

Greedy 디코딩은 매 스텝 $\arg\max_i p_i$를 고른다. 단순하고 재현 가능하지만, 긴 생성에서는 같은 구절을 반복하는 고리에 쉽게 빠진다("나는 커피를 마시고 책을 읽고 커피를 마시고…"). 한 번 고리에 들어가면 반복된 문맥이 다시 그 반복을 강화하기 때문이다. 반대로 $T = 1$로 분포 전체에서 순수 샘플링하면, 확률이 낮은 수만 개 꼬리 토큰의 확률을 모두 합한 값이 무시할 수 없을 만큼 커서 가끔 엉뚱한 토큰이 뽑히고, 한 번 엇나가면 문장 전체가 무너진다. Holtzman 등(2019)은 이를 "신경망 텍스트의 퇴화(degeneration)"라 불렀다. 그래서 실전 샘플링은 거의 항상 꼬리를 잘라 낸 뒤 샘플링한다.

그림 8-2. 같은 설정이 두 종류의 분포에서 남기는 후보(진한 막대). top-k는 분포 모양과 상관없이 개수를 고정하므로 뾰족할 때는 너무 많이, 평평할 때는 너무 적게 남긴다. top-p와 min-p는 분포의 모양에 따라 남길 후보 수가 저절로 바뀐다.

꼬리 자르기 세 가지

Top-k 샘플링: 확률 상위 $k$개만 남기고 나머지를 0으로 만든 뒤 재정규화한다(Fan 등, 2018). 간단하지만 $k$가 분포 모양과 무관하게 고정이라는 약점이 있다.
Top-p (nucleus) 샘플링: 확률이 큰 순서로 더해 누적합이 처음으로 $p$ 이상이 되는 최소 집합 $V^{(p)}$만 남긴다(Holtzman 등, 2019). 분포가 뾰족하면 1~2개, 평평하면 수십 개가 남는다. 현재 가장 널리 쓰는 기본값이다($p = 0.9$~$0.95$).
Min-p 샘플링: 1등 확률에 비례하는 문턱 $p_{\min} \cdot p_{\max}$보다 작은 후보를 버린다(Nguyen 등, 2024). 1등이 확신에 차 있으면 문턱이 높아지고, 확신이 없으면 낮아진다. 높은 온도와 함께 써도 문장이 잘 무너지지 않는다는 보고가 있어 오픈소스 추론 엔진에 빠르게 퍼졌다.

$$V^{(p)} = \text{가장 작은 } S \subseteq V \ \text{ s.t. } \sum_{i \in S} p_i \ge p, \qquad V^{\min} = \{\, i : p_i \ge p_{\min} \cdot \max_j p_j \,\}$$

반복 패널티

이미 나온 토큰을 덜 고르게 하는 장치도 있다. CTRL(Keskar 등, 2019)의 반복 패널티(repetition penalty) $\theta$는 이미 등장한 토큰의 로짓이 양수면 $\theta$로 나누고 음수면 $\theta$를 곱해 어느 쪽이든 작아지게 만든다($\theta \approx 1.1$~$1.3$). OpenAI API의 frequency/presence penalty는 등장 횟수에 비례한 값이나 고정값을 로짓에서 빼는 변형이다. 너무 세게 걸면 "은", "을" 같은 조사까지 못 쓰게 되어 문장이 이상해진다.

이들은 보통 반복 패널티 → 온도 → top-k → top-p → min-p → 재정규화 → 샘플링 순서로 이어 붙인 파이프라인으로 구현된다(엔진마다 순서가 조금씩 다르다). 아래 실험실이 정확히 이 순서로 계산한다.

SIMULATOR

샘플링 실험실: 작은 n-gram 언어 모델로 진짜 생성하기

첫 단어

모델 · 방식

온도 T top-k (0 = 끔) top-p min-p 반복 패널티 θ

생성 결과 (EOS = 마침표, 최대 14토큰)

20번 샘플링 결과 (같은 설정, 서로 다른 난수) — 숫자는 같은 문장이 나온 횟수

'20번 샘플링'을 누르면 여기에 표시된다.

후보 → 남은 후보—

고른 토큰 확률—

누적 log₂ 확률—

다양성 (서로 다른 결과)—

교육용으로 만든 한국어 문장 34개로 단어 2-gram/3-gram 카운트를 센 작은 언어 모델이다(3-gram은 2-gram과 0.7:0.3으로 보간). 막대 위쪽 얇은 선은 원래 분포(T, 패널티 적용 후), 진한 막대는 자르기·재정규화 후 실제 샘플링 확률, 회색은 잘린 후보(이유 표시)다. 해볼 것: ① greedy로 '나는'을 끝까지 생성하면 2-gram은 "…마시고 책을 읽고 영화를 본다"처럼 길게 이어 붙인다. 3-gram으로 바꾸면 문맥이 길어져 결과가 달라진다. ② 샘플링·T = 2에서 '20번 샘플링'을 누르면 다양성이 크게 오르지만 "고양이가 아침에 비가 온다" 같은 어색한 조합도 나온다. 여기에 top-p = 0.5나 min-p = 0.3을 걸면 다양성은 조금 줄고 문장은 깔끔해진다. ③ top-k = 1은 greedy와 같다. ④ '나는'·2-gram·greedy에서 반복 패널티를 2.0으로 올리면 이미 쓴 단어(을/를 붙은 목적어 등)가 회피되어 경로가 바뀐다.

빔 서치: 여러 경로를 동시에

Greedy는 매 스텝 지역적으로 최선을 고르지만, 그 선택들의 곱이 전체적으로 최선이라는 보장은 없다. 첫 단어에서 2등을 골랐다면 그 뒤로 훨씬 확실한 문장이 이어질 수도 있다. 정말로 확률이 가장 높은 문장 $\arg\max_{x} \prod_t P(x_t \mid x_{<t})$를 찾으려면 $|V|^n$개를 모두 봐야 하므로 불가능하다. 빔 서치(beam search)는 그 절충이다. 매 스텝 현재 살아 있는 $B$개의 부분 문장(빔)을 각각 확장해 후보를 만들고, 누적 로그확률이 가장 높은 $B$개만 남긴다.

$$\text{score}(x_{1:t}) = \sum_{s=1}^{t} \log P(x_s \mid x_{<s}), \qquad \text{길이 정규화: } \frac{\text{score}}{t^{\alpha}}$$

로그확률은 항상 음수이므로 문장이 길수록 점수가 불리하다. 번역 시스템은 $\alpha \approx 0.6$~$1$의 길이 정규화로 짧은 문장 편향을 보정한다.

$B = 1$이면 greedy와 같다. 빔 서치는 기계 번역·음성 인식처럼 "입력에 대해 정답이 거의 하나"인 작업에서 큰 효과를 보였다. 그러나 열린 대화나 창작에서는 확률이 가장 높은 문장이 오히려 밋밋하고 반복적이라는 것이 알려져(Holtzman 등, 2019) 오늘날 챗봇은 대부분 샘플링을 쓴다. 비용도 $B$배다.

SIMULATOR

빔 서치 트리

빔 폭 B

첫 단어

모델

각 빔은 상위 3개 후보로 확장한다. 진한 테두리는 살아남은 빔, 흐린 것은 버려진 후보, 굵은 선은 최종 최고 점수 경로다. 숫자는 누적 log₂ 확률.

빔 서치 결과—

greedy 결과 (B=1)—

점수 차이 (log₂)—

샘플링 실험실과 같은 장난감 모델(T = 1 원분포)에서 깊이 4까지 탐색한다. 마침표(EOS)로 끝난 빔은 더 확장하지 않고 점수 그대로 다음 단계에 남는다. 해볼 것: ① '나는'·2-gram에서 B = 1(greedy)은 첫 단어로 확률이 가장 높은 '아침에'를 고르지만 B = 2부터는 "저녁에 영화를 본다 ."처럼 첫 스텝 2등에서 출발한 경로가 전체 점수에서 이긴다. ② B를 4로 올려도 결과가 바뀌지 않는 첫 단어를 찾아보자 — 이미 최적 경로를 찾았다는 뜻이다. ③ '나는'·3-gram에서 B = 3 → 4로 넓히면 결과가 또 바뀐다 — 빔이 좁으면 나중에 최고가 될 경로를 일찍 버린다. ④ 마침표로 끝난 짧은 빔이 아직 끝나지 않은 긴 빔과 같은 기준으로 경쟁한다는 점에서, 길이 정규화가 왜 필요한지 생각해 보자.

Prefill과 Decode: 두 얼굴의 추론

생성 요청 하나는 성격이 전혀 다른 두 단계로 나뉜다. Prefill(프리필)은 프롬프트 전체를 모델에 한 번에 통과시키는 단계다. 프롬프트의 토큰들은 이미 다 알고 있으므로, 5장의 인과 마스크를 건 채 수천 개 위치를 병렬로 계산할 수 있다. 커다란 행렬-행렬 곱(GEMM)이 되어 GPU의 연산 유닛을 꽉 채운다. 이 단계의 끝에서 첫 번째 출력 토큰이 나온다.

Decode(디코드)는 그 뒤로 토큰을 하나씩 만드는 단계다. 매 스텝 새 토큰 단 하나를 입력으로 모델 전체를 통과시킨다. 행렬-벡터 곱(GEMV)이 되어 가중치 하나를 메모리에서 읽어 와 곱셈·덧셈 한 번(2 FLOP)만 하고 버린다. 연산 유닛은 대부분 놀고, 시간은 거의 전부 가중치와 KV 캐시를 HBM에서 읽어 오는 데 쓰인다.

그림 8-3. 요청 하나의 시간축. 사용자는 TTFT 동안 빈 화면을 보고, 그 뒤로 TPOT 간격으로 토큰이 흘러나온다(스트리밍). TTFT는 주로 프롬프트 길이와 연산 성능이, TPOT은 주로 메모리 대역폭이 결정한다.

서빙 성능은 보통 세 숫자로 말한다. TTFT(Time To First Token)는 요청부터 첫 토큰까지의 시간이고, TPOT(Time Per Output Token)은 이후 토큰 사이 간격이며, 처리량(throughput, tokens/s)은 GPU 한 대가 모든 요청을 합쳐 초당 만드는 토큰 수다. 사람이 읽는 속도는 대략 초당 5~10토큰이므로 대화형 서비스는 TPOT 수십 ms면 충분히 쾌적하다.

숫자로 보기: Llama 3 8B on H100

모델 파라미터를 $N$이라 하면 토큰 하나를 통과시키는 데 약 $2N$ FLOP이 든다(곱셈 + 덧셈, 6장). Llama 3 8B($N \approx 8.03\text{B}$)는 토큰당 약 16 GFLOP이다. BF16 가중치는 $8.03\text{B} \times 2\,\text{B} \approx 16.1$ GB다. H100 SXM(BF16 dense 약 989 TFLOPS, HBM3 약 3.35 TB/s)에서 이상적으로 계산하면 다음과 같다.

단계	병목	이상적 계산	결과
Prefill 2,000토큰	연산	2,000 × 16 GFLOP ÷ 989 TFLOPS	≈ 32 ms (실제는 MFU 40~60%로 약 2배)
Decode 1스텝, 배치 1	메모리	16.1 GB ÷ 3.35 TB/s	≈ 4.8 ms → 최대 약 210 tokens/s
Decode 1스텝, 배치 64	메모리(아직)	가중치는 한 번 읽어 64개 요청이 공유	≈ 5 ms + KV 읽기 → 약 64배 처리량

핵심은 산술 강도(arithmetic intensity, FLOP/byte)다. 배치 $b$인 decode는 2바이트 가중치 하나를 읽어 $2b$ FLOP을 하므로 강도가 약 $b$다. H100이 연산과 메모리를 둘 다 꽉 채우는 지점(능선)은 989 / 3.35 ≈ 295 FLOP/byte이므로, 배치 1의 decode는 연산 능력의 1%도 못 쓴다. 그래서 서빙 엔진은 여러 사용자의 요청을 한 스텝에 묶는 연속 배칭(continuous batching)으로 배치를 키운다. 요청마다 길이가 달라 끝나는 시점이 제각각이므로, 스텝 단위로 끝난 요청을 빼고 새 요청을 끼워 넣는다(Orca, 2022). 배치를 키우는 데 걸림돌이 바로 다음 절의 KV 캐시 메모리다.

KV 캐시: 이미 계산한 것은 다시 계산하지 않는다

어텐션에서 위치 $t$의 출력은 자기 쿼리 $q_t$와 이전 모든 위치의 키·값 $k_1..k_t,\ v_1..v_t$로 계산된다. 인과 마스크 덕분에 과거 위치의 $k_s, v_s$는 나중에 들어오는 토큰과 무관하게 한 번 정해지면 절대 바뀌지 않는다. 그렇다면 매 스텝 전체 시퀀스를 다시 넣을 이유가 없다. 각 층의 $K, V$를 GPU 메모리에 쌓아 두고(KV 캐시), 새 토큰 하나에 대해서만 $q, k, v$를 계산해 캐시에 $k, v$를 덧붙이고, $q$로 캐시 전체를 읽어 어텐션하면 된다.

그림 8-4. KV 캐시를 쓰는 decode 스텝. 새 토큰에 대해서만 프로젝션과 FFN을 계산하고, 과거 위치의 K, V는 캐시에서 읽기만 한다. 대가는 메모리다 — 캐시는 시퀀스 길이에 비례해 계속 자란다.

캐시가 없으면 $t$번째 스텝에서 길이 $t$짜리 시퀀스 전체를 다시 통과시켜야 하므로, $n$개 토큰을 생성하는 누적 비용은 $\sum_{t=1}^{n} t = n(n+1)/2 = O(n^2)$개 "토큰-순전파"가 된다(어텐션 자체까지 치면 $O(n^3)$). 캐시를 쓰면 스텝마다 토큰 1개만 통과시키므로 $O(n)$이다(어텐션의 캐시 읽기는 여전히 스텝당 $O(t)$로 누적 $O(n^2)$이지만, 프로젝션·FFN에 비해 훨씬 가볍다).

SIMULATOR

KV 캐시 애니메이션: 재계산 vs 재사용

프롬프트 길이 P 생성할 토큰 수 n

현재 스텝—

이번 스텝 계산 (없음 / 캐시)—

누적 계산 (없음 / 캐시)—

절감 배수—

한 칸 = 한 위치의 K, V를 한 층에서 계산하는 일("토큰-순전파" 1단위). 스텝 0은 prefill(두 방식 모두 P칸 계산)이다. 해볼 것: ① 재생하면서 위쪽 줄(캐시 없음)은 매 스텝 모든 칸이 다시 빨갛게 계산되고, 아래쪽 줄(캐시)은 새 칸 하나만 계산되는 것을 보자. ② 그래프에서 '캐시 없음'은 포물선(O(n²)), '캐시'는 직선(O(n))이다. n = 28, P = 12면 절감 배수가 약 19배다. ③ 실제 대화에서는 P가 수천, n이 수백이므로 절감은 수백~수천 배에 이른다 — KV 캐시 없이 실용적인 LLM 서빙은 불가능하다.

KV 캐시는 얼마나 클까

캐시에는 층마다, KV 헤드마다, 위치마다 $k$와 $v$ 벡터(각각 $d_\text{head}$차원)가 들어간다. 그러므로 크기는 단순한 곱이다.

$$\text{KV 바이트} = 2 \times L \times H_{kv} \times d_{\text{head}} \times s \times b \times (\text{원소당 바이트})$$

2 = K와 V, $L$ = 층 수, $H_{kv}$ = KV 헤드 수, $s$ = 시퀀스 길이, $b$ = 배치(동시 요청 수).

Llama 3 8B는 32층, KV 헤드 8개, $d_\text{head} = 128$이다. FP16/BF16(2바이트)이면 토큰 하나당 $2 \times 32 \times 8 \times 128 \times 2 = 131{,}072$ B = 128 KiB이고, 128k(131,072) 토큰 컨텍스트 하나를 꽉 채우면 $128\ \text{KiB} \times 131{,}072 = \mathbf{16\ GiB}$ — 모델 가중치(약 15 GiB)와 맞먹는다. 같은 구조에서 쿼리 헤드 32개마다 KV 헤드를 따로 두는 MHA였다면 4배인 512 KiB/토큰이 된다. 5장의 GQA(Grouped-Query Attention)가 쿼리 헤드 4개당 KV 헤드 1개를 공유하게 만든 이유가 바로 이 메모리다. 극단적으로 KV 헤드를 1개만 두면 MQA(Multi-Query Attention)다.

모델	층	Q / KV 헤드	d_head	KV/토큰 (FP16)	8k 토큰 1개
GPT-2 small (MHA)	12	12 / 12	64	36 KiB	288 MiB
Llama 2 7B (MHA)	32	32 / 32	128	512 KiB	4 GiB
Llama 3 8B (GQA)	32	32 / 8	128	128 KiB	1 GiB
Llama 3 70B (GQA)	80	64 / 8	128	320 KiB	2.5 GiB

SIMULATOR

KV 캐시 메모리 계산기

프리셋

어텐션 종류

KV 정밀도

시퀀스 길이 s 배치 b

가중치는 BF16(2바이트/파라미터) 고정. 세로 점선은 H100 80 GB.

구조 (L / H_kv / d_head)—

토큰당 KV—

KV 캐시 전체—

가중치 + KV—

해볼 것: ① 기본값(Llama 3 8B·GQA·FP16)에서 s를 128k(2¹⁷)로 올리면 KV가 정확히 16 GiB가 된다. ② 같은 상태에서 MHA로 바꾸면 64 GiB — 128k 컨텍스트 하나만으로 H100 한 장을 거의 채운다. ③ s = 8k, 배치 64에서 KV가 가중치의 몇 배인지 보자. 동시 사용자를 늘리면 메모리는 가중치보다 KV가 지배한다. ④ FP8 KV 캐시는 메모리를 절반으로, INT4는 1/4로 줄인다(9장). 70B는 BF16 가중치만 141 GB라 H100 두 장 이상이 필요하다.

PagedAttention: KV 캐시의 가상 메모리

KV 캐시는 크기도 문제지만 얼마나 커질지 미리 모른다는 점이 더 골치 아프다. 응답이 10토큰에서 끝날지 2,000토큰까지 갈지는 생성해 봐야 안다. 초기 서빙 시스템은 요청마다 최대 길이만큼의 연속된 메모리를 미리 예약했다. 그러면 ① 예약했지만 끝내 쓰지 않는 공간(내부 단편화), ② 요청이 끝나고 생긴 구멍들이 너무 작아 새 요청의 연속 공간으로 못 쓰는 공간(외부 단편화)이 생긴다. vLLM 논문(Kwon 등, 2023)은 기존 시스템에서 KV 캐시 메모리의 60~80%가 이렇게 낭비된다고 측정했다.

PagedAttention은 운영체제의 가상 메모리 페이징을 그대로 가져온다. KV 캐시를 고정 크기 블록(예: 16토큰)으로 나누고, 각 요청은 논리적으로 연속된 블록 목록인 블록 테이블만 가진다. 물리 블록은 메모리 어디에 흩어져 있어도 되고, 토큰이 블록을 다 채울 때마다 빈 블록 하나를 새로 받는다. 낭비는 요청마다 마지막 블록의 빈 칸뿐이다(평균 블록 크기의 절반). 어텐션 커널은 블록 테이블을 따라가며 흩어진 블록에서 K, V를 모아 읽는다.

그림 8-5. PagedAttention. 요청의 논리 블록은 블록 테이블을 통해 아무 물리 블록에나 매핑된다. 같은 프롬프트를 공유하는 여러 요청(병렬 샘플링, 빔 서치, 공통 시스템 프롬프트)은 같은 물리 블록을 가리키고, 수정할 때만 복사한다(copy-on-write).

SIMULATOR

메모리 단편화: 연속 할당 vs 페이지 할당

연속 할당 예약 길이

블록 크기 (토큰)

요청 도착률 (스텝당)

페이지 할당 쪽 블록 테이블 (처음 4개 요청)

—

실행 중 요청 (연속 / 페이지)—

대기열 (연속 / 페이지)—

할당분 중 낭비 (연속 / 페이지)—

완료 요청 (연속 / 페이지)—

KV 메모리 1,024토큰 분량을 한 칸 = 1토큰으로 그렸다. 같은 요청 흐름(최종 길이 16~예약 길이 사이 무작위, 스텝마다 8토큰씩 생성)이 두 방식에 똑같이 들어간다. 진한 칸은 실제 KV가 든 칸, 연한 칸은 예약·할당됐지만 비어 있는 칸이다. 해볼 것: ① 재생해서 연속 할당 쪽에 연한 띠(예약만 해 둔 공간)가 넓게 깔리고 대기열이 쌓이는 것을 보자. ② 같은 시간 동안 페이지 할당이 동시에 더 많은 요청을 돌리고 더 많이 완료한다 — 이것이 vLLM이 처리량을 2~4배 올린 원리다. ③ 블록 크기를 32로 키우면 마지막 블록의 빈칸이 늘어 낭비가 조금 오르지만, 블록 테이블이 짧아져 커널 효율이 좋아진다. vLLM의 기본값은 16이다.

추측 디코딩: 작은 모델이 쓰고, 큰 모델이 검토한다

decode가 메모리 바운드라는 사실은 거꾸로 기회이기도 하다. 가중치를 한 번 읽어 오는 동안 토큰 1개를 계산하든 5개를 계산하든 시간이 거의 같다. 문제는 다음 토큰을 모르니 여러 개를 동시에 계산할 수 없다는 것이다. 추측 디코딩(speculative decoding)은 작고 빠른 드래프트 모델로 다음 $k$개 토큰을 미리 "추측"하고, 큰 타깃 모델은 그 $k$개 위치를 prefill처럼 한 번에 병렬로 검증한다(Leviathan 등 / Chen 등, 2023).

그림 8-6. 추측 디코딩 한 라운드. 드래프트가 맞힌 앞부분은 그대로 받고, 처음 틀린 위치에서는 타깃이 직접 고른 토큰으로 바꾼 뒤 나머지를 버린다. 운이 나빠도 라운드마다 최소 1토큰은 생긴다.

수용 규칙이 영리하다. 드래프트 분포 $q$에서 뽑은 토큰 $x$를 확률 $\min(1, p(x)/q(x))$로 받아들이고, 거절하면 $\max(0, p - q)$를 정규화한 분포에서 다시 뽑는다. 이렇게 하면 최종 출력의 분포가 타깃 모델만으로 샘플링한 것과 수학적으로 정확히 같다. 품질 손실 없이 속도만 얻는 것이다. 토큰마다 수용될 확률을 $\alpha$라 하고 독립이라 가정하면, 라운드당 기대 생성 토큰 수와 속도 향상은 다음과 같다.

$$\mathbb{E}[\text{토큰/라운드}] = \sum_{i=0}^{k} \alpha^i = \frac{1-\alpha^{k+1}}{1-\alpha}, \qquad \text{속도 향상} = \frac{1-\alpha^{k+1}}{(1-\alpha)(k c + 1)}$$

$c$ = 드래프트 1스텝 비용 / 타깃 1스텝 비용. 타깃의 병렬 검증 1회 비용을 일반 decode 1스텝과 같다고 본다(메모리 바운드이므로).

SIMULATOR

추측 디코딩: 이론 vs 몬테카를로

수용률 α 드래프트 길이 k 드래프트 비용비 c

기대 토큰/라운드 (이론)—

몬테카를로 평균—

속도 향상 (이론 / MC)—

최적 k—

위 그래프: k에 따른 속도 향상(실선 = 이론, 점 = 몬테카를로). 아래: 최근 몬테카를로 라운드 12개(초록 = 수용, 빨강 = 거절 후 타깃이 교체, 보라 = 전부 수용 시 보너스). 해볼 것: ① α = 0.8, c = 0.05에서 k = 4에서 약 2.8배, 최적 k는 8 부근(약 3.1배)이며 그 근처에서는 곡선이 매우 평평함을 확인하자. ② α를 0.5로 낮추면 k를 늘려도 이득이 금방 포화되고, 너무 크면 오히려 손해다. ③ c를 0.3(드래프트가 그리 작지 않음)으로 올리면 최적 k가 3으로 줄고 속도 향상이 약 1.5배에 그친다 — 드래프트는 작고 타깃과 '말투'가 비슷해야 한다. ④ 몬테카를로 점이 실선 위에 잘 올라앉는지 보자.

실전에서 $\alpha$는 작업에 따라 크게 다르다. 코드나 정형화된 텍스트처럼 예측 가능한 부분이 많으면 0.8 이상, 창작이면 낮다. 드래프트로 별도 소형 모델(예: Llama 3 8B에 1B급) 대신 타깃 모델에 예측 헤드를 몇 개 덧붙이거나(Medusa, EAGLE), 프롬프트에 이미 있는 n-gram을 그대로 복사해 제안하는(prompt lookup) 변형도 널리 쓰인다.

구조화 출력과 제약 디코딩

LLM 출력을 프로그램이 받아 쓰려면 형식이 정확해야 한다. "JSON으로 답해"라고 프롬프트에 써도 모델은 가끔 "네, 여기 JSON입니다:"로 시작하거나 따옴표를 빼먹는다. 제약 디코딩(constrained decoding)은 이 문제를 디코딩 단계에서 원천 차단한다. 원하는 형식을 문법(정규식, JSON 스키마, 문맥 자유 문법)으로 적어 두고, 매 스텝 지금까지의 출력 뒤에 붙였을 때 문법을 깨는 토큰의 로짓을 $-\infty$로 마스킹한다. softmax 후 그 토큰들의 확률은 정확히 0이 되므로, 어떤 샘플링 설정에서도 문법에 맞는 출력만 나온다.

$$\tilde z_i = \begin{cases} z_i & i \in \text{Allowed}(\text{state}) \\ -\infty & \text{otherwise} \end{cases}, \qquad p = \mathrm{softmax}(\tilde z / T)$$

구현의 난점은 속도와 토큰 경계다. 토큰은 문법 기호와 일치하지 않는다({"가 한 토큰일 수도 있다). Outlines, XGrammar, llama.cpp의 GBNF 같은 라이브러리는 문법을 유한 상태 기계나 푸시다운 오토마타로 컴파일하고, 상태별 허용 토큰 마스크를 미리 계산해 두어 스텝당 오버헤드를 마이크로초 수준으로 줄인다. OpenAI·Anthropic 등의 API가 제공하는 "구조화 출력(structured outputs)"도 같은 원리다.

SIMULATOR

JSON 형태 강제하기

어휘 (작은 숫자 = 모델 로짓 → 마스킹 후 확률). 초록 = 문법상 허용, 취소선 = 마스킹(−∞). 칩을 눌러 직접 고를 수도 있다.

출력

제약 디코딩 켜기 (JSON 스키마)

스키마: {"이름": 문자열, "나이": 숫자} — 키 순서 자유, 두 키 모두 필수, 중복 금지.

문법 상태—

허용 토큰 수—

JSON.parse 결과—

교육용으로 손으로 만든 "말 많은" 장난감 모델이다(로짓은 직전 토큰에 따라 정해진 표에서 나온다). 해볼 것: ① 제약을 끄고 '끝까지'를 누르면 "네, 물론 JSON 입니다 {…"처럼 서두를 붙이고, "나이"에도 "철수"를 넣어 JSON.parse가 실패하거나 스키마를 어긴다. ② 제약을 켜면 같은 모델이 첫 토큰부터 {만 고를 수 있고, "나이" 다음에는 숫자 토큰만 허용된다. ③ 제약을 켠 채 칩을 눌러 키 순서를 바꿔 보자("나이"를 먼저) — 문법 상태가 따라가며 남은 키만 허용한다.

핵심 정리

LLM은 한 번 호출에 다음 토큰 분포 하나만 내놓는다. 생성은 "로짓 → 확률 → 고르기 → 붙이기"를 EOS·max_tokens까지 반복하는 자기회귀 루프다.
온도 $T$는 로짓을 나눠 분포의 날카로움을 조절한다. $T \to 0$은 greedy, 큰 $T$는 균등에 가깝다. 엔트로피와 퍼플렉시티 $2^H$로 퍼짐을 잰다.
실전 샘플링은 꼬리를 자른다: top-k(개수 고정), top-p(누적 확률), min-p(1등 대비 비율). 반복 패널티는 이미 나온 토큰의 로짓을 깎는다.
빔 서치는 누적 로그확률 상위 $B$개 경로를 유지해 greedy보다 높은 확률의 문장을 찾지만, 열린 생성에서는 밋밋해지기 쉽고 비용이 $B$배다.
Prefill은 병렬·계산 바운드(TTFT 결정), decode는 순차·메모리 바운드(TPOT 결정)다. 배치를 키워 산술 강도를 올리는 것이 처리량의 핵심이다.
KV 캐시는 재계산을 없애 생성 비용을 $O(n^2)$에서 $O(n)$으로 줄인다. 크기는 $2 L H_{kv} d_\text{head} s b \times$바이트 — Llama 3 8B는 토큰당 128 KiB, 128k 컨텍스트에 16 GiB다. GQA·MQA·KV 양자화가 이를 줄인다.
PagedAttention은 KV 캐시를 고정 크기 블록과 블록 테이블로 관리해 단편화 낭비를 거의 없애고 동시 처리 요청 수를 늘린다.
추측 디코딩은 드래프트 $k$개를 타깃이 병렬 검증해 라운드당 $(1-\alpha^{k+1})/(1-\alpha)$개 토큰을 얻으며, 출력 분포는 타깃과 동일하다. 제약 디코딩은 문법 밖 토큰을 $-\infty$로 마스킹해 형식을 보장한다.

확인 퀴즈

1. 두 후보의 로짓이 각각 3과 1이다. 온도 $T = 0.5$에서 두 후보의 확률비 $p_1/p_2$는?

확률비는 $\exp((z_1 - z_2)/T) = \exp(2 / 0.5) = e^4$다. 온도를 낮추면 로짓 차이가 확대되어 1등 쏠림이 강해진다. 나머지 후보와 상관없이 두 후보 사이 비율은 이 값으로 정해진다.

2. 다음 중 top-p(nucleus) 샘플링의 특징으로 옳은 것은?

top-p는 누적 확률이 p에 도달하는 최소 집합을 남기므로 남는 개수가 분포 모양에 적응한다. 개수 고정은 top-k, 1등 대비 비율은 min-p의 정의다.

3. 배치 1에서 Llama 3 8B(BF16 약 16 GB)를 H100(약 3.35 TB/s)으로 decode할 때 토큰 생성 속도의 이론적 상한에 가장 가까운 것은?

decode 스텝마다 가중치 전체를 HBM에서 읽어야 하므로 16 GB ÷ 3.35 TB/s ≈ 4.8 ms/토큰, 즉 약 210 tokens/s가 상한이다(KV 캐시 읽기를 더하면 더 느리다). 60,000 tokens/s는 연산 바운드인 prefill의 이상적 처리 속도에 가깝다.

4. Llama 3 70B(80층, KV 헤드 8, d_head 128)의 FP16 KV 캐시는 토큰당 몇 바이트인가?

$2 \times 80 \times 8 \times 128 \times 2 = 327{,}680$ B = 320 KiB. 8k 토큰이면 2.5 GiB, 128k 토큰이면 40 GiB다. 쿼리 헤드 64개가 모두 KV를 가졌다면(MHA) 8배인 2.5 MiB/토큰이었을 것이다.

5. 추측 디코딩에서 수용률 α = 0.75, 드래프트 길이 k = 3일 때 라운드당 기대 생성 토큰 수는?

$(1 - 0.75^4)/(1 - 0.75) = (1 - 0.3164)/0.25 \approx 2.73$. 타깃 1회 호출로 평균 2.73토큰을 얻으므로, 드래프트 비용비 c = 0.05라면 속도 향상은 2.73 / 1.15 ≈ 2.4배다.

6. PagedAttention이 연속 할당 방식보다 메모리를 덜 낭비하는 주된 이유는?

블록 단위 지연 할당 덕분에 내부 단편화는 마지막 블록의 빈칸으로 줄고, 블록 테이블로 흩어진 블록을 이어 쓰므로 외부 단편화도 없다. 최대 길이 예약은 오히려 낭비의 원인이다.