제5부 추론·서빙(Inference/Serving)

5.3 배칭·speculative decoding·paged attention

5.1이 남긴 문장은 하나였다 — 디코드는 대역폭 바운드라 GPU 연산기가 유휴 상태다. 배치 1로 한 요청만 디코드하면 GPU는 거대한 가중치 행렬을 HBM에서 전부 읽어 와 고작 토큰 하나를 만들고 버린다. 텐서 코어는 수백분의 일도 안 쓰이고, 대부분의 대역폭은 "가중치를 읽어 토큰 하나 뽑고 던지는 데" 손실된다. 이 장은 그 낭비되는 자원을 회수해 처리량으로 바꾸는 서빙 기법들을 원리와 대가로 다룬다. 5.1이 왜 문제인지를 세웠다면, 여기서는 어떻게 고치는지다.

고칠 축이 셋이다. 하나는 시간 축 — 여러 요청을 묶어 가중치 읽기를 나눠 쓰되, 요청 길이가 제각각이라 순진하게 묶으면 대부분이 새므로 연속 배칭으로 토큰 단위로 슬롯을 채운다. 둘은 메모리 축 — KV 캐시를 연속 블록으로 할당하면 단편화로 절반 넘게 버려지므로 PagedAttention으로 OS 페이징처럼 블록 단위로 관리해 낭비와 중복을 없앤다. 셋은 한 시퀀스의 시간 축 — 디코드의 순차성 자체를 투기적 디코딩으로 우회해, 작은 초안 모델이 여러 토큰을 미리 뽑고 큰 모델이 한 번에 검증한다. 여기에 긴 프리필이 디코드를 방해하는 간섭을 다루는 청크 프리필과 프리필/디코드 분리를 더한다. 이 기법들은 서로를 곱하지만 서로의 병목도 바꾸므로, 원리를 정확히 쥔 다음 자기 트래픽으로 실측하는 것 말고 지름길은 없다. 나오는 하드웨어·수락률·낭비율 수치는 개략 규모를 보여 주는 개략 예시이고, 무게는 숫자가 아니라 산식이 가리키는 방향에 있다.

5.3.1 배치가 처리량의 1순위 조정 변수인 이유

디코드 한 스텝에서 GPU가 읽어야 할 바이트는 두 부분이다 — 모델 가중치 전부와, 배치에 든 각 요청의 KV 캐시다. 대역폭 바운드 구간에서 스텝 시간은 이 바이트를 대역폭으로 나눈 값이다. 배치 크기를 $B$로 키우면 결정적인 비대칭이 생긴다. 가중치는 한 번 읽어 $B$개 토큰이 나눠 쓰지만, KV는 요청마다 따로 있어 $B$에 비례해 늘어난다. 가중치 바이트를 $W$, 요청당 KV 바이트를 $K$, 대역폭을 $BW$라 하면 스텝 시간과 처리량은

$$t_{\text{step}}(B) \approx \frac{W + B\,K}{BW}, \qquad \text{처리량}(B) = \frac{B}{t_{\text{step}}(B)} = \frac{B\cdot BW}{W + B\,K}.$$

이 식 하나가 배칭의 이득과 한계를 동시에 말한다. $B$가 작아 $W$가 지배하는 구간에서는 분모가 거의 상수라 처리량이 $B$에 거의 선형으로 오른다 — 가중치를 한 번 읽은 값에 토큰을 더 추가할수록 무비용에 가깝게 처리량이 늘어난다. $B$가 커져 $BK$가 $W$를 넘어서면 분모가 $B$와 함께 자라 이득이 꺾이고, 극한에서 처리량은 $BW/K$로 포화한다. 즉 긴 컨텍스트에서 처리량의 상한을 정하는 것은 연산 능력이 아니라 요청당 KV 크기다.

숫자를 넣자. 5.1의 8B GQA 모델을 가중치 $W=16$ GB, 컨텍스트 2048에 요청당 KV $K\approx0.25$ GB, 대역폭 $BW=3.3$ TB/s인 GPU에서 실행한다 하자.

배치 1에서 64로 키우는 동안 스텝 시간은 4.9 ms에서 9.7 ms로 겨우 두 배 늘었는데 처리량은 32배가 됐다 — 가중치 읽기를 64개 토큰이 나눠 썼기 때문이다. 이것이 배칭이 LLM 서빙 처리량의 1순위 조정 변수인 이유이고, 산술강도(5.1.8)로 말하면 배치를 키워 능선점 쪽으로 미는 것과 같은 동작이다. 동시에 이 표는 두 가지 대가도 보여준다. 첫째, 배치 240에서 스텝 시간이 23 ms까지 올랐다 — 이것이 그대로 그 배치에 실린 모든 요청의 TBT(토큰 간 지연)이므로, 처리량을 사려고 개별 지연을 판 것이다. 둘째, 이론상 상한 $BW/K = 3.3/0.25 \approx 13{,}200$ tok/s에 다가갈수록 이득이 급격히 줄어, 배치를 더 키워도 KV 대역폭에 막힌다. 여기서 두 방향의 처방이 갈린다 — KV를 줄이면($K$↓, GQA·MLA·양자화) 상한 자체가 올라가고, 같은 메모리에 배치를 더 담으면($B$↑) 능선까지 밀 수 있다. 후자가 이 장의 배칭·페이징이 겨냥하는 지점이다.

문제는 "어떻게 $B$개를 묶느냐"다. 위 표는 모든 요청이 같은 길이로 나란히 실행되는 이상을 가정했다. 실제로는 프롬프트 길이도, 생성 길이도 제각각이라 이 이상이 곧바로 붕괴한다.

5.3.2 정적 배칭은 가장 긴 요청에 묶여 대기한다

정적 배칭(static batching)은 요청 $B$개를 모아 하나의 배치로 넣고, 그 배치의 모든 요청이 끝날 때까지 함께 스텝을 밟는다. 생성 길이는 미리 알 수 없고 편차가 크다 — 어떤 답은 20토큰에서 EOS를 만나고, 같은 배치의 다른 답은 500토큰까지 간다. 짧은 요청이 먼저 끝나도 그 슬롯은 배치 전체가 끝날 때까지 빈 채로 스텝을 낭비하고, 배치가 실행되는 동안 새로 도착한 요청은 다음 배치를 기다린다. 정적 배치는 가장 긴 요청의 길이에 배치 전체가 인질처럼 묶인다.

손실이 세 갈래로 난다. 짧은 요청이 끝난 뒤의 슬롯이 배치 종료까지 유휴 상태인 내부 낭비, 진행 중 배치에 합류하지 못해 다음 배치까지 기다리는 새 요청의 큐잉 지연(꼬리 지연·TTFT 악화), 그리고 배치가 진행되며 요청이 하나둘 끝나 실효 배치 크기가 후반으로 갈수록 줄어드는 활용도 저하다. 앞 절의 처리량 식은 배치가 가득 찬 상태를 가정했는데, 정적 배칭은 배치 후반에 이 가정이 깨져 5.3.1의 이득을 절반가량 잃는다. 얼마나 잃는지는 다음 절에서 숫자로 계산한다.

5.3.3 연속 배칭 — 반복 단위로 슬롯을 채운다

연속 배칭(continuous batching)은 원 논문 Orca(Yu et al., 2022)의 용어로 반복 단위 스케줄링(iteration-level scheduling), TensorRT-LLM 용어로 in-flight batching이라 부른다. 발상은 한 문장이다 — 배치를 "요청 단위"가 아니라 "토큰(반복) 단위"로 다시 구성한다. 스케줄러가 매 디코드 스텝마다 실행 중인 요청 집합을 재구성한다. 어떤 요청이 EOS나 길이 한계에 닿으면 그 즉시 슬롯을 비우고, 대기 큐의 새 요청을 그 자리에 채워 넣는다. 배치 전체가 끝나기를 기다리지 않는다.

새 요청은 큐에서 뽑히면 먼저 프리필을 거쳐 KV를 채운 뒤 실행 집합에 합류한다. 그래서 한 배치 안에 프리필 단계 요청과 디코드 단계 요청이 섞일 수 있고, 이 혼합을 어떻게 처리하느냐가 뒤의 청크 프리필로 이어진다. 이득은 정확히 정적 배칭의 두 손실을 되받는다. 끝난 요청의 자리를 즉시 새 요청이 메우니 배치가 항상 가득 찬 상태에 가깝게 유지되고(슬롯 낭비 제거), 새 요청이 다음 배치를 기다릴 필요 없이 빈 슬롯이 생기는 대로 합류한다(큐잉 지연 감소). 5.3.1의 처리량 식에서 실효 $B$를 계속 최대로 유지하는 것이 연속 배칭이 하는 일이다.

연속 배칭이 성립하려면 두 전제가 필요하고, 둘 다 이 장의 뒷부분으로 이어진다. 슬롯을 계속 교체하려면 각 요청의 KV 캐시를 유연하게 할당·해제해야 하는데, 요청마다 길이가 다르고 언제 끝날지 모르는 상태에서 캐시를 연속 블록으로 미리 할당하면 단편화로 슬롯을 못 채운다 — 이것이 PagedAttention이 필요한 이유다(5.3.6). 그리고 실행 집합이 GPU 메모리를 넘치려 하면 스케줄러가 일부 요청을 선점해야 하는데, 그 처리가 다음 절이다. 정적 배칭이 정당한 자리는 길이가 균일한 오프라인 대량 배치(임베딩 생성·오프라인 평가) 정도이고, 생성 길이 편차가 큰 온라인 챗·API 트래픽에서는 연속 배칭이 사실상 기본값이다.

5.3.4 연속 배칭의 이득을 직접 계산한다

"처리량이 여러 배 오른다"는 말을 숫자로 바꿔 보자. 이득의 크기는 생성 길이의 편차가 정한다는 것을 계산이 드러낸다. 배치 크기 8, 요청들의 생성 길이가 절반은 짧고 절반은 길다고 하자 — 4개는 50토큰, 4개는 400토큰(챗 트래픽의 흔한 이봉 분포를 단순화한 것이다).

정적 배칭에서는 8개가 함께 돌다가 가장 긴 400토큰 요청이 끝나야 배치가 끝난다. 그동안 배치가 점유한 슬롯·스텝의 총량은 $8 \times 400 = 3{,}200$ 슬롯-스텝이다. 그중 실제로 토큰을 만든 유효 슬롯-스텝은 각 요청이 생성한 토큰 수의 합, $4\times 50 + 4\times 400 = 1{,}800$이다. 나머지 $3{,}200 - 1{,}800 = 1{,}400$ 슬롯-스텝, 즉

$$\text{활용도} = \frac{1{,}800}{3{,}200} \approx 56\%$$

는 짧은 요청 4개가 50스텝에 끝난 뒤 350스텝 동안 논 것이다. 디코드 스텝 시간이 실린 토큰 수에 거의 무관한(대역폭 바운드) 구간이므로, 이 44%는 그대로 버려진 GPU 시간이다.

연속 배칭은 짧은 요청이 50스텝에 끝나는 즉시 그 슬롯에 새 요청을 넣어 8개 슬롯을 계속 꽉 채운다. 같은 1,800개의 유효 토큰을 만드는 데 필요한 배치 스텝은 $1{,}800 / 8 = 225$스텝뿐이다 — 정적 배칭이 400스텝을 쓴 자리다. 스텝 시간이 두 경우에 거의 같으므로 처리량 배수는

$$\frac{3{,}200}{1{,}800} = \frac{400}{225} \approx 1.78\times.$$

이 1.78배가 전부 편차에서 나온다는 점이 핵심이다. 만약 8개가 전부 400토큰으로 균일했다면 유효 슬롯-스텝이 3,200이 되어 활용도 100%, 정적과 연속의 차이가 사라진다. 반대로 편차가 클수록 — 한 요청만 4,000토큰이고 나머지가 50토큰이라면 — 정적 배칭의 활용도는 한 자릿수 퍼센트로 떨어지고 연속 배칭의 이득은 10배를 넘는다. 그래서 실측 보고의 "정적 대비 수 배"라는 수치는 항상 그 워크로드의 길이 분포에 붙은 꼬리표를 달고 읽어야 한다. 균일 길이 배치 작업에서는 연속 배칭이 줄 것이 거의 없고, 자유 형식 챗처럼 길이가 극단적으로 흩어진 트래픽에서 가장 크게 값한다.

5.3.5 선점·스와핑·재계산 — 연속 배칭이 메모리에 부딪힐 때

연속 배칭은 슬롯을 공격적으로 채우다가 필연적으로 장벽에 부딪힌다. 실행 집합에 요청을 계속 넣다 보면 그들의 KV 캐시 합이 GPU에 남은 메모리를 넘치려는 순간이 온다. 디코드는 매 스텝 KV가 토큰 하나씩 자라므로, 지금 다 들어맞던 배치가 몇 스텝 뒤 넘칠 수 있다. 이때 스케줄러는 진행 중인 요청 일부를 선점(preempt)해 자리를 비워야 하고, 선점당한 요청의 KV를 어떻게 처리하느냐에 두 갈래가 있다.

하나는 스와핑(swap) — 그 요청의 KV 블록을 GPU에서 CPU 메모리로 옮겨 두었다가, 자리가 나면 다시 GPU로 불러와 이어서 디코드한다. KV를 보존하니 재계산은 없지만 PCIe를 왕복하는 전송 비용이 든다. 다른 하나는 재계산(recompute) — KV를 단순히 버리고, 나중에 그 요청을 재개할 때 지금까지의 토큰으로 프리필을 다시 실행해 KV를 복원한다. 프리필은 연산 바운드라 짧은 시퀀스에서는 스왑 전송보다 오히려 저렴하고, 긴 시퀀스에서는 $O(L^2)$라 비용이 커진다. 그래서 서빙 엔진은 시퀀스 길이·전송 대역폭에 따라 둘을 고른다. 어느 쪽이든 선점당한 요청은 재개될 때까지 진행이 멈추므로 그 요청의 TBT에 스파이크가 생기고, 메모리 압박이 심한 고부하에서 p99 지연을 튀게 하는 주범이 이 선점이다.

여기서 연속 배칭과 메모리 관리가 한 몸임이 드러난다. 선점이 잦다는 것은 배치를 담을 KV 메모리가 모자란다는 뜻이고, KV 메모리를 낭비 없이 조밀하게 쓸수록 같은 GPU로 더 큰 배치를 선점 없이 굴릴 수 있다. 순진하게 요청마다 최대 길이를 연속으로 예약하는 방식은 바로 이 KV 메모리를 대량으로 버린다.

5.3.6 KV 캐시 단편화 — 연속 할당이 메모리를 반 넘게 버린다

KV 캐시는 요청마다 있고 토큰이 생성될 때마다 자라는데, 얼마나 자랄지 미리 모른다. 순진한 서빙 시스템은 이 불확실성을 가장 게으른 방법으로 처리한다 — 각 요청에 최대 길이만큼의 연속(contiguous) 메모리 전체를 예약한다. 여기서 세 종류의 낭비가 겹친다. 예약 낭비는 미래 토큰을 위해 할당해 뒀지만 아직 안 쓴 자리로, 요청이 끝날 때까지 다른 요청이 못 쓴다. 내부 단편화는 요청이 최대 길이보다 훨씬 짧게 끝나 예약분 대부분이 영영 안 쓰이는 것이다. 외부 단편화는 요청마다 예약 크기가 달라, 요청이 들고 나며 메모리에 자잘한 빈틈이 생겨 총 여유는 충분한데 연속 블록이 없어 새 요청을 못 받는 것이다.

숫자로 재보자. 5.1의 8B GQA 모델은 토큰당 KV가 128 KB다. 최대 컨텍스트 2048토큰을 예약하는데 실제 요청은 평균 300토큰(프롬프트+생성)에서 끝난다고 하자. 요청 하나가

$$\text{예약} = 2048 \times 128\,\text{KB} = 256\,\text{MB}, \qquad \text{실사용} = 300 \times 128\,\text{KB} \approx 37.5\,\text{MB}$$

를 쓰므로, 예약분의 $37.5/256 \approx 15\%$만 실제 토큰에 쓰이고 나머지 85%는 잠긴 채 유휴 상태다. KV에 쓸 수 있는 메모리가 60 GB라면, 순진한 예약으로는 $60\,\text{GB} / 256\,\text{MB} = 234$개 요청밖에 못 담는다 — 그런데 그 234개가 실제로 쓰는 KV는 $234 \times 37.5\,\text{MB} \approx 8.8$ GB뿐이다. 60 GB를 할당해 놓고 8.8 GB어치 일만 시킨 셈이다. 만약 필요한 만큼만 할당한다면 같은 60 GB에 평균 300토큰 길이의 요청을 $60\,\text{GB} / 37.5\,\text{MB} \approx 1{,}600$개 담을 수 있다 — 배치를 거의 7배로 키울 여지가 메모리 낭비에 묻혀 있었던 것이다. 5.3.1에서 봤듯 대역폭 바운드 구간에서 배치는 처리량과 거의 비례하므로, KV 메모리 낭비는 곧 처리량 손실이다.

이 7배는 이상적 상한이라는 점을 정직하게 밝히자 — 실제 생성 길이는 꼬리가 길어 일부 요청이 정말로 2048에 근접하고, 그만큼 평균 낭비가 줄어 실측 이득은 대개 2~4배 수준으로 보고된다. PagedAttention을 제안한 vLLM 논문(Kwon et al., 2023)도 순진한 연속 할당에서 실효 KV 활용이 20~40%대에 그쳤다고 보고했는데, 방향은 이 계산 그대로다. 낭비의 정체는 "미래를 위해 잡아 뒀지만 대부분 안 쓰는 연속 예약"이고, 이를 없애는 방법을 운영체제가 수십 년 전에 이미 알고 있었다.

5.3.7 PagedAttention — OS 페이징을 KV 캐시에 옮기다

운영체제는 프로세스에 연속 물리 메모리 전체를 주지 않는다. 메모리를 고정 크기 페이지로 분할하고, 페이지 테이블이 프로세스의 가상 주소를 흩어진 물리 프레임에 매핑한다. 그래서 프로세스는 연속된 주소 공간을 보는 것처럼 동작하지만 실제 물리 페이지는 아무 데나 흩어져 있어도 되고, 필요할 때 한 페이지씩 붙여 주면 된다. PagedAttention은 이 아이디어를 KV 캐시에 그대로 옮긴다.

KV 캐시를 고정 크기 블록(예컨대 16토큰의 K·V를 담는 단위)으로 분할한다. 각 시퀀스는 논리 블록의 나열로 표현되고, 블록 테이블이 논리 블록을 물리 블록(GPU 메모리의 실제 프레임)에 매핑한다. 물리 블록은 연속일 필요가 없다. 블록은 토큰이 자라 새 블록이 필요할 때 하나씩 on-demand로 할당된다. 그 결과 낭비는 마지막 블록의 안 채운 몇 칸뿐이다 — 내부 단편화가 요청당 최대 1블록 미만으로 줄고, 블록 크기가 균일하므로 어떤 빈 블록에나 들어가 외부 단편화는 원천적으로 사라진다.

앞 절의 낭비가 얼마나 줄었는지 같은 숫자로 확인하자. 블록 크기 16토큰이면, 평균 300토큰 요청의 마지막 블록은 최악의 경우에도 15토큰만 비어 있다 — 요청당 낭비 상한이 $15 \times 128\,\text{KB} \approx 1.9$ MB로, 256 MB를 예약하던 것에 비하면 소멸에 가깝다. 내부 단편화가 예약분의 85%에서 300토큰 기준 5%(2048토큰 기준으로는 0.7%) 미만으로 떨어진다. 5.3.6에서 순진한 방식이 담던 234개 대신 같은 60 GB에 실사용 기준 1,000개 이상을 담을 수 있게 되고, 그 큰 배치가 그대로 처리량이 된다.

대가는 어텐션 커널의 복잡도다. K·V가 연속으로 놓여 있지 않으므로, 어텐션을 계산할 때 커널이 블록 테이블을 따라 흩어진 블록을 모아 읽어야 한다(이것이 PagedAttention 커널이다). 이 간접 참조에 약간의 오버헤드가 있지만, 배치를 키워 얻는 처리량이 그것을 압도한다. 블록 크기는 그 자체로 조정 변수다 — 너무 작으면 블록 테이블 항목과 커널 간접 참조가 늘어 오버헤드가 커지고, 너무 크면 마지막 블록 내부 단편화가 다시 커진다. 16 안팎이 흔한 절충점이다.

5.3.8 블록 공유 — copy-on-write와 프리픽스 공유

블록 매핑의 실제 보너스는 낭비 제거가 아니라 공유다. 논리 블록이 물리 블록을 가리키는 간접 참조 구조 덕에, 여러 시퀀스가 같은 물리 블록을 가리킬 수 있다. 이것은 OS에서 fork한 프로세스들이 같은 물리 페이지를 공유하다가 한쪽이 쓰기를 할 때만 그 페이지를 복사하는 copy-on-write(COW)와 정확히 같은 메커니즘이다.

두 자리에서 이것이 값한다. 하나는 한 프롬프트로 여러 답을 뽑는 경우다 — 병렬 샘플링($n>1$)이나 빔 서치에서 후보들은 같은 프롬프트로 시작하므로 프롬프트 KV가 동일하다. 논리 블록들이 같은 물리 블록을 가리키게 하고 참조 카운트(ref count)로 관리하다가, 어떤 후보가 그 블록에 자기 토큰을 써야 하는 순간에만 그 블록을 복사한다. 프롬프트 KV를 후보 수만큼 중복 저장하지 않으니, 프롬프트가 길고 후보가 많을수록 메모리가 크게 준다. 다른 하나는 여러 요청이 같은 접두부로 시작하는 경우다 — 같은 시스템 프롬프트, 같은 few-shot 예시, 같은 문서 프리픽스로 시작하는 요청들이 그 공통 프리픽스의 KV 블록을 공유하면, 프리필을 다시 하지 않고 메모리도 한 벌만 쓴다. 이것이 프리픽스 캐시의 토대다. SGLang의 RadixAttention은 이 공유를 접두어 트리로 일반화해, 도착하는 요청들의 프리픽스를 트리에 삽입해 최대한 겹치는 부분까지 KV를 재사용한다. 프리픽스 캐시를 언제 어떻게 투입하고 라우팅에 어떻게 연계하는지의 실무 설계는 롱컨텍스트·캐시 재사용을 다루는 5.6의 몫이다.

여기까지가 현대 LLM 서버의 두 기둥이다. 연속 배칭이 시간 축에서 슬롯을 토큰 단위로 채우고, PagedAttention이 메모리 축에서 KV를 블록으로 조각내 낭비와 중복을 없앤다. 둘이 함께 있어야 "배치를 크게, 꽉 채워, 오래" 유지할 수 있다. 다음 세 절은 완전히 다른 축을 공격한다 — 배치가 여러 요청을 가로질러 가중치 읽기를 나눴다면, 이번엔 한 시퀀스의 시간 축을 가로질러 나눈다.

5.3.9 투기적 디코딩 — 순차 디코드의 사슬을 끊는다

디코드가 느린 근본 이유는 순차성이다. 토큰 $t$를 만들어야 $t{+}1$을 만들 수 있고, 매 토큰마다 거대한 target 모델을 forward 한 번씩 실행해야 하는데, 그 forward는 대역폭 바운드라 GPU가 유휴 상태다. 투기적 디코딩(speculative decoding)은 이 낭비를 노린다 — 저렴하고 빠른 초안(draft) 모델로 다음 $\gamma$개 토큰을 추측해 뽑고, 그 $\gamma$개를 큰 target 모델이 한 번의 forward로 병렬 검증한다. 초안이 맞은 만큼을 한꺼번에 수락하면, target forward 한 번에 여러 토큰이 확정된다.

왜 이것이 이득인가 하는 지점이 5.1의 대역폭 논리에 정확히 걸린다. target이 토큰 1개를 디코드하든 $\gamma{+}1$개 위치를 병렬 검증하든, 모델 가중치를 읽는 비용은 똑같다. 대역폭 바운드 구간에서 "몇 개 위치를 보느냐"는 스텝 시간에 거의 영향이 없기 때문이다(연산은 늘지만 어차피 연산기는 유휴 상태에 있었다). 배칭이 여러 요청을 가로질러 가중치 읽기를 나눴다면, 투기적 디코딩은 한 시퀀스의 여러 시점을 가로질러 그 한 번의 읽기를 나눈다. 그래서 배치가 작아 GPU가 놀 때(저부하·대화형 단일 요청) 이득이 가장 크다.

핵심은 검증이 초안을 "대충 맞으면 통과"시키는 근사가 아니라는 것이다. 거부된 지점부터는 초안을 버리고 target이 직접 뽑은 토큰으로 대체하므로, 초안이 아무리 틀려도 매 반복 최소 1토큰은 target 분포로 확정된다 — 즉 투기적 디코딩은 최악의 경우에도 순수 디코드보다 느려질지언정 품질은 정확히 같다. 왜 정확히 같은지가 다음 절의 수학이다.

5.3.10 왜 품질이 깎이지 않나 — 분포를 보존하는 rejection sampling

투기적 디코딩의 가장 중요한 성질은 출력 분포가 target 단독 디코딩과 정확히 같다는 것이다. 이것은 근사가 아니라 수학적 등식이고, 검증 단계를 speculative sampling이라 불리는 수정된 rejection sampling(Leviathan et al. 2023 · Chen et al. 2023)으로 설계한 결과다.

토큰 하나를 보자. target 분포를 $p(x)$, 초안 분포를 $q(x)$라 하고, 초안이 뽑은 토큰 $\tilde{x}\sim q$를 이렇게 처리한다. 먼저 확률

$$\min\!\left(1,\ \frac{p(\tilde{x})}{q(\tilde{x})}\right)$$

로 $\tilde{x}$를 수락한다. 초안이 이 토큰을 target보다 덜 선호했으면($q<p$) 비율이 1을 넘어 무조건 수락이고, 초안이 과대 선호했으면($q>p$) 그 초과분만큼의 확률로만 수락한다. 나머지 확률로는 거부하고, 잔차 분포

$$p'(x) = \operatorname{norm}\big(\max(0,\ p(x) - q(x))\big)$$

에서 대체 토큰을 뽑는다. 이 두 규칙을 거친 최종 토큰이 정확히 $p$를 따른다는 것을 직접 확인할 수 있다. 어떤 토큰 $x$가 최종적으로 방출되는 경로는 둘이다 — 초안이 $x$를 제안하고 수락되거나, 초안이 거부된 뒤 잔차에서 $x$가 뽑히거나. 첫 경로의 확률은

$$q(x)\cdot\min\!\left(1,\frac{p(x)}{q(x)}\right) = \min\big(q(x),\,p(x)\big).$$

거부가 일어날 총확률은 $\sum_x\big(q(x)-\min(q(x),p(x))\big) = \sum_x \max(0,\,q(x)-p(x))$이고, $\sum_x p = \sum_x q = 1$이므로 이 값은 잔차의 정규화 상수 $\sum_x \max(0,\,p(x)-q(x))$와 같다. 그래서 둘째 경로의 확률 $P(\text{거부})\cdot p'(x)$에서 정규화 상수가 상쇄되어 정확히 $\max(0,\,p(x)-q(x))$가 남는다. 두 경로를 더하면

$$\min\big(q(x),p(x)\big) + \max\big(0,\,p(x)-q(x)\big) = p(x)$$

가 된다 — $p\ge q$면 $\min=q,\ \max=p-q$라 합이 $p$이고, $p<q$면 $\min=p,\ \max=0$이라 역시 $p$다. 어느 경우든 방출 확률이 정확히 $p(x)$다. 직관으로 말하면 수락 규칙이 초안이 과대추정한 만큼을 깎고, 거부 시 잔차 $p-q$의 양(+)의 부분에서 정확히 그만큼을 보충해 초안의 편향을 상쇄한다.

그래서 greedy 디코딩이면 target의 argmax와 일치하는 토큰만 통과해 target 단독 greedy와 토큰 단위로 동일하고, 샘플링이면 각 토큰이 정확히 $p$에서 뽑힌 것과 분포적으로 동일하다. 이 점이 양자화(5.2)와 결정적으로 다르다 — 양자화는 정밀도를 낮춰 품질을 조금 지불하지만, 투기적 디코딩은 원리상 품질 중립이고 속도만 바꾼다. 단, "완전 무손실"은 같은 확률 연산을 정확히 한다는 이론적 성질이라는 점은 정직하게 밝혀야 한다. 실무에서는 초안·target의 부동소수점 비결정성, 커널 차이, 다른 배치와 섞일 때의 수치 차이로 비트 단위 동일까지 보장되지는 않는다. 그러나 그것은 구현의 미세 오차이지, "초안이 대충 맞으면 통과시키는" 품질 저하형 근사와는 범주가 다르다.

5.3.11 수락률과 기대 가속 — 식을 유도한다

가속의 크기는 수락률 $\alpha$가 정한다 — 초안 토큰이 검증을 통과할 평균 확률이다. $\alpha$는 초안이 target과 얼마나 닮았는지, 그리고 태스크·온도에 달렸다. 분석을 위해 각 초안 토큰이 독립적으로 확률 $\alpha$로 수락된다고 가정하자(단순화이고, 실제로는 앞 토큰이 거부되면 뒤가 무의미해지는 상관이 있다).

초안을 $\gamma$개 제안하면 앞에서부터 연속으로 수락되는 개수 $N$은 첫 거부에서 멈춘다. 앞의 $j$개가 모두 수락돼야 $N\ge j$이므로 $P(N\ge j)=\alpha^{j}$이고($j\le\gamma$),

$$\mathbb{E}[N] = \sum_{j=1}^{\gamma}P(N\ge j) = \sum_{j=1}^{\gamma}\alpha^{j} = \frac{\alpha(1-\alpha^{\gamma})}{1-\alpha}.$$

여기에 target이 거부 지점에서(또는 $\gamma$개를 전부 수락한 경우 그다음에서) 항상 1개를 보정·생성하므로, target forward 한 번당 확정되는 토큰 수는 $\mathbb{E}[N]+1$이다. 이 $+1$을 넣어 정리하면

$$\mathbb{E}[\text{토큰/forward}] = 1 + \frac{\alpha(1-\alpha^{\gamma})}{1-\alpha} = \frac{(1-\alpha)+\alpha-\alpha^{\gamma+1}}{1-\alpha} = \frac{1-\alpha^{\gamma+1}}{1-\alpha}.$$

이 식이 투기적 디코딩의 핵심이다. 초안 비용을 무시하면 이 값이 곧 처리량 배수의 개략이다. 두 극한이 식의 성격을 드러낸다.

$$\gamma\to\infty \ \Rightarrow\ \frac{1}{1-\alpha}\ \ (\text{천장}),\qquad \alpha\to 1 \ \Rightarrow\ \gamma+1\ \ (\text{전부 수락}).$$

$\alpha=0.9$면 아무리 $\gamma$를 키워도 상한이 $1/(1-0.9)=10$배다 — 수락률이 낮으면 초안을 아무리 길게 뽑아도 금세 첫 거부에 막혀 이득이 포화한다는 뜻이다. 이제 초안 비용을 넣자. 초안 forward 한 번이 target forward의 $c$배 시간이라면(예컨대 초안이 target의 10분의 1 크기면 $c\approx0.1$), 한 반복의 비용은 target 검증 1회 + 초안 $\gamma$회 $\approx(1+\gamma c)$ target-forward다. 그러면

$$\text{실제 가속} \approx \frac{1-\alpha^{\gamma+1}}{(1-\alpha)\,(1+\gamma c)}.$$

여기에 $\gamma$의 딜레마가 있다. $\gamma$를 키우면 분자(수락 이득)는 $1/(1-\alpha)$로 포화하는데 분모의 초안 비용 $\gamma c$는 선형으로 계속 는다. 그래서 어느 지점을 넘으면 $\gamma$를 더 키우는 것이 오히려 불리하고, 최적 $\gamma$가 존재한다. $\alpha$가 높을수록(초안이 좋을수록) 포화가 늦게 와서 최적 $\gamma$도 커진다. 이 최적점을 다음 절에서 실제 숫자로 찾는다.

5.3.12 기대 가속을 직접 계산한다

$\alpha=0.8$, $\gamma=4$, 초안이 target의 $c=0.1$배 비용이라 하자. 먼저 초안 비용을 무시한 이상적 토큰/forward는

$$\frac{1-0.8^{5}}{1-0.8} = \frac{1-0.32768}{0.2} = \frac{0.67232}{0.2} \approx 3.36.$$

target forward 한 번에 평균 3.36토큰이 확정된다 — 초안이 무비용이라면 약 3.4배 처리량이다. 초안 비용을 반영하면

$$\frac{3.36}{1+\gamma c} = \frac{3.36}{1+4(0.1)} = \frac{3.36}{1.4} \approx 2.4\times.$$

이제 이 $\gamma=4$가 최적인지 확인하자. 같은 $\alpha=0.8$, $c=0.1$에서 $\gamma$를 바꿔 가며 실제 가속을 계산하면 $\gamma=3$에서 2.27배, $\gamma=4$에서 2.40배, $\gamma=5$에서 2.46배, $\gamma=6$에서 2.47배, $\gamma=7$에서 2.45배로, 6 근처에서 정점에 이르고 다시 내려간다. 초안이 이 정도로 좋으면($\alpha=0.8$) $\gamma$를 4에서 6으로 높여 약간 더 짜낼 수 있지만, 8까지 밀면 초안 비용이 이득을 잠식하기 시작한다. 초안이 나쁘면 최적 $\gamma$는 더 작아진다.

수락률이 전부라는 것을 한 표로 보자. 초안 비용을 뺀 이상적 토큰/forward를 $\alpha$와 $\gamma$로 늘어놓으면

읽는 법은 이렇다. $\alpha=0.5$면 $\gamma$를 8까지 키워도 2배가 상한이라 초안이 나쁘면 길게 뽑아 봐야 소용없다. $\alpha=0.9$라야 큰 $\gamma$가 보답해 6배 넘게 간다. 그리고 이 표는 초안 비용을 뺀 값이라, 실제로는 전부 $(1+\gamma c)$로 더 나눠야 하므로 맹목적으로 $\gamma$를 키우면 오히려 불리하다. 그래서 실무의 두 조정 변수는 $\alpha$를 높이는 것(초안을 target과 더 닮게 — 다음 절의 변형들이 이것을 노린다)과 $\gamma$를 태스크에 맞게 튜닝하는 것이다.

$\alpha$가 태스크·온도에 크게 의존한다는 점이 실무에서 가장 자주 문제를 일으킨다. 코드·정형 텍스트처럼 다음 토큰이 뻔한 출력은 $\alpha$가 높아 가속이 크고, 창의적이거나 온도를 높인 생성은 $\alpha$가 낮아 이득이 줄거나 심지어 초안 비용 때문에 순수 디코드보다 느려질 수 있다. "N배 빠름"이라는 수치는 항상 어떤 태스크·온도·초안기의 조건에서 나온 것인지 물어야 한다.

5.3.13 초안을 어디서 얻나 — 투기적 디코딩의 변형들

앞 절이 보여준 대로 이득은 $\alpha$를 높이고 초안 비용 $c$를 낮추는 데서 온다. 그래서 투기적 디코딩의 설계 공간은 대부분 "어떤 초안기를 어떻게 마련하나"로 수렴한다. 별도의 작은 모델을 초안으로 두는 것이 표준이지만, 그러려면 같은 토크나이저의 작은 사전학습 모델을 따로 갖춰야 하고, target과 분포가 덜 맞으면 $\alpha$가 낮으며, 두 모델을 함께 로드해 VRAM과 배포 파이프라인을 이중으로 관리해야 한다. 이 부담을 덜려는 여러 변형이 나왔고, 모두 여전히 진화 중이라 구체 가속 수치는 조건 의존이다.

self-speculative(자기 투기)는 별도 모델 없이 target 자신을 초안으로 쓴다. 일부 층을 건너뛰거나(layer skip) 중간 층에서 조기 종료(early exit)한 얕은 통과로 초안을 만들고, 전체 통과로 검증한다(Draft&Verify·LayerSkip 계열). 모델이 하나뿐이라 관리가 단순하고 분포도 자연히 가깝다. Medusa는 target 위에 여러 개의 예측 헤드를 붙여 다음 여러 토큰의 후보를 병렬로 뽑고, 여러 후보 조합을 트리 어텐션으로 한 번에 검증한다 — 별도 초안 모델 없이 헤드만 추가 학습하면 된다. EAGLE은 토큰이 아니라 특징(은닉 상태) 수준에서 자기회귀로 초안을 만들고 직전에 샘플링된 토큰까지 입력에 넣어 초안 정확도, 즉 $\alpha$를 높인다(EAGLE-2/3는 동적 초안 트리 등으로 더 발전시켜 높은 가속을 보고한다). lookahead decoding은 초안 모델 자체를 없애고 Jacobi 반복으로 여러 n-gram을 병렬 생성·검증해 순차 의존을 해소한다 — 더 많은 FLOPs를 써서 스텝 수를 줄이는 교환이다. prompt lookup / n-gram은 초안을 입력이나 이미 생성한 출력에서 그대로 복사한다. 요약·편집·RAG처럼 입력과 출력이 많이 겹치는 태스크에서는 복사한 초안의 $\alpha$가 높으면서 초안 비용이 거의 0이라, 모델을 하나도 더 붙이지 않고 값싸게 큰 이득을 본다.

이들을 관통하는 공통 도구가 트리 검증(tree attention)이다. 초안을 하나의 직선이 아니라 여러 갈래 후보의 트리로 만들어 한 번의 forward로 동시에 검증하면, 어느 한 갈래가 target과 맞을 확률이 올라 유효 수락 길이가 늘어난다 — 앞 절 분석에서 $\alpha$의 효과를 키우는 것과 같다.

한 가지 상호작용을 반드시 기억해야 한다. 투기적 디코딩의 "병렬 검증은 공짜"라는 전제는 GPU가 유휴 상태에 있을 때, 즉 배치가 작아 대역폭 바운드일 때만 성립한다. 배치가 이미 커서 GPU가 연산 바운드에 가까우면, 여러 위치를 병렬 검증하는 추가 연산과 초안·트리의 비용이 더는 무비용이 아니라 순부담이 된다. 그래서 큰 배치에서는 투기적 디코딩의 이득이 줄거나 사라지고, 오히려 느려질 수도 있다. 연속 배칭·PagedAttention과 결합하는 실서비스에서는 부하에 따라 투기적 디코딩을 켜고 끄는 적응형 운영이 흔하고, 그 임계점은 반드시 자기 트래픽으로 측정해야 한다.

5.3.14 긴 프리필이 디코드를 막는다

지금까지의 기법은 디코드를 겨냥했다. 마지막 문제는 프리필과 디코드가 한 GPU에서 섞일 때 생긴다. 둘은 성질이 정반대다.

연속 배칭에서 새 요청의 프리필이 진행 중인 디코드와 한 배치에 섞이면 문제가 된다. 프리필은 부하가 크고 오래 걸리는 스텝이라, 그 스텝이 실행되는 동안 같은 배치의 디코드 요청들은 다음 토큰을 못 낸다 — 사용자 눈에는 스트리밍이 뚝뚝 끊기는 TBT 스파이크로 나타난다. 긴 컨텍스트 요청 하나가 들어오면 그 수만 토큰 길이의 프리필이 그 순간 함께 실행되는 다른 모든 사용자의 디코드를 지연시킨다. 5.1.9에서 이 간섭의 동기를 세웠고, 이를 다루는 두 접근이 청크 프리필과 disaggregation이다.

5.3.15 청크 프리필 — 프리필을 잘게 분할해 삽입한다

청크 프리필(chunked prefill, Sarathi 계열 Agrawal et al. 2023)의 발상은 긴 프리필을 고정 크기 청크로 분할해 한 반복에 한 청크씩만 처리하고, 남는 연산 여유에 다른 요청의 디코드 토큰을 함께 실어(piggyback) 배치를 채우는 것이다.

두 가지가 좋아진다. 한 반복의 작업량이 청크 크기로 균일한 상한을 갖게 되어, 아무리 긴 프롬프트라도 디코드 스텝이 청크 하나 시간 이상 밀리지 않는다 — TBT 스파이크가 사라진다. 그리고 프리필(연산 바운드)과 디코드(대역폭 바운드)를 한 배치에 섞으면 서로 놀던 자원을 메워 GPU 활용도가 오른다. 프리필이 연산기를 쓰는 동안 디코드가 대역폭을 쓰니 궁합이 좋다. 대가는 두 가지다. 프리필을 분할하면 뒤 청크가 앞 청크의 KV에 다시 어텐션해야 해서 재접근이 늘고 커널 효율이 통짜 프리필보다 조금 떨어져, TTFT가 소폭 증가할 수 있다. 그래서 청크 크기가 그대로 조정 변수가 된다 — 작게 하면 TBT는 매끄럽지만 TTFT와 오버헤드가 늘고, 크게 하면 반대다. 결국 TTFT(첫 토큰)와 TBT(토큰 간)의 SLA를 비교 평가해 정하는 값이고, 활성화 여부·청크 크기·연속 배칭과의 결합 방식은 서빙 엔진과 버전마다 다르다(5.4).

청크 프리필은 한 인스턴스 안에서 프리필과 디코드를 시간적으로 인터리브해 간섭을 줄이는, 어디서나 켜 볼 만한 저비용 완화책이다. 규모가 더 커져 TTFT와 TBT를 동시에 빡세게 맞춰야 할 때 꺼내는 더 근본적인 카드가 다음 절이다.

5.3.16 프리필/디코드 분리 — disaggregated serving

더 근본적인 접근은 프리필과 디코드를 아예 다른 GPU 풀에서 실행하는 것이다(disaggregated serving, DistServe·Splitwise 계열). 성질이 반대인 두 국면을 한 GPU에서 시분할하면 서로 간섭하고 각자에 최적화하기 어렵다는 문제의식이다. 요청은 프리필 노드에서 프롬프트를 처리해 KV 캐시를 만든 뒤, 그 KV를 디코드 노드로 전송하고, 디코드 노드가 토큰 생성을 이어받는다.

이렇게 나누면 각 풀을 독립적으로 최적화할 수 있다. 프리필 노드는 TTFT를, 디코드 노드는 TBT·처리량을 목표로 배치 전략·병렬화·심지어 하드웨어를 따로 고르고, 프리필의 연산 부하가 디코드의 TBT를 교란하지 않으며, 부하에 따라 두 풀을 각각 오토스케일할 수 있다(5.5). 대가는 KV 캐시 전송이다. 프리필이 만든 KV는 수 GB에 이를 수 있고(5.1.4의 산식대로 길이·배치에 선형), 그것을 노드 간에 옮겨야 하므로 인터커넥트 대역폭이 관건이고 전송 지연이 TTFT에 더해진다. 그래서 disaggregation은 고대역폭 인터커넥트가 있고 트래픽이 커서 두 풀을 각각 꽉 채울 수 있는 대규모 서빙에서 값한다. 소규모·저트래픽에서는 노드를 분할하는 것이 오히려 활용도를 낮춘다.

둘은 배타적 선택이 아니라 층위가 다른 대응이다. 청크 프리필은 한 인스턴스 안의 저비용 완화이고, disaggregation은 규모가 커진 뒤의 아키텍처 결정이다. 실제로 대규모 시스템은 disaggregation 위에서 각 풀이 내부적으로 청크 프리필과 연속 배칭을 쓰기도 한다.

5.3.17 무엇을 개선하고 무엇을 지불하나

이 장의 기법들을 지연·처리량·메모리 중 무엇을 개선하고 무엇을 지불하는지로 모으면 이렇다.

표를 관통하는 원리는 하나다. 이 장의 모든 기법은 디코드가 대역폭 바운드라 유휴 자원을 각기 다른 축에서 메운다 — 배칭은 여러 요청을 가로질러, 투기적 디코딩은 한 시퀀스의 시간을 가로질러, 청크 프리필은 프리필과 디코드를 섞어 놀던 연산기와 대역폭을 서로 채운다. PagedAttention은 KV 메모리 낭비를 없애 그 배칭을 더 크게 가능하게 하는, 다른 기법들의 토대다.

그러나 지연 개선과 처리량 개선은 같은 것이 아니고, 부하에 따라 반대로 움직이기까지 한다. 투기적 디코딩은 배치가 작은 저부하 대화형에서 한 요청의 TBT를 줄이는 데 강하지만 큰 배치에서는 약해지고, 연속 배칭·PagedAttention은 다부하 API에서 전체 처리량을 높이는 데 강하다. 그래서 기법을 고르기 전에 목표 SLA — TTFT·TBT·처리량 중 무엇을 어디까지 — 를 먼저 명시해야 한다. 연속 배칭과 PagedAttention은 온라인 서빙의 표준 기본 조합이고, 투기적 디코딩은 저부하 지연 절감, 청크 프리필과 분리는 프리필 간섭 대응이다. 그리고 이들은 곱해지지만 서로의 병목을 바꾼다 — 투기적 디코딩이 배치 크기를 바꾸고, 그것이 PagedAttention의 메모리 압박을 바꾸며, 양자화(5.2)와 GQA(1.6)가 다시 KV 크기를 바꿔 전체 균형을 교란한다. 어느 것이 어디서 이득인지는 부하·워크로드 의존이라, 이론은 방향을 주고 값은 프로파일링이 준다.

이제 이 원리들을 실제로 구현하고 조합한 도구를 고를 차례다. 다음 장은 연속 배칭·PagedAttention·투기적 디코딩·청크 프리필을 저마다 다르게 담은 서빙 프레임워크들 — vLLM·TGI·TensorRT-LLM·SGLang — 이 무엇을 잘하고 어떻게 다른지, 자기 워크로드에 무엇을 고를지를 다룬다(5.4).