LLM 투기적 디코딩(Speculative Decoding) 해부: 작은 드래프트 모델의 선행 추측과 리젝션 샘플링(Rejection Sampling) 무손실 병렬 검증 원리

초경량 드래프트 모델(Draft Model)이 민첩하게 후보 토큰 궤적을 선행 투사하고, 대규모 타깃 모델(Target Model)의 거대한 공명 링이 단 한 번의 순방향 연산으로 병렬 검증을 수행하여 골든 보너스 토큰과 함께 무손실 가속 스트림을 방출하는 투기적 디코딩(Speculative Decoding)의 아키텍처를 상징하는 추상 비주얼 아트워크다. 동심원 궤도, 기하학적 다면체 코어, 그리고 무손실 확률 분포 정렬을 상징하는 황금빛 가속 빔을 통해 차세대 초고속 추론 서빙 생태계를 표현했다.

생성형 AI와 대규모 언어 모델(LLM)이 수십억~수천억 파라미터 규모로 거대화되면서, 엔지니어링 현장의 가장 큰 도전 과제는 '단일 요청에 대한 토큰 생성 지연 시간(Time Per Output Token, TPOT)'을 어떻게 단축할 것인가로 귀결되고 있다. 최신 GPU가 수백 테라플롭스(TFLOPS)에 달하는 막강한 텐서 코어 연산력을 갖추었음에도 불구하고, 대화형 챗봇이나 자율형 AI 에이전트 환경에서 LLM의 토큰 생성 속도는 초당 수십 토큰 안팎에 머무르는 경우가 다반사다. 이는 모델의 연산량이 부족해서가 아니라, 매 토큰을 생성할 때마다 거대한 가중치 행렬 전체를 고대역폭 메모리(HBM)에서 SRAM으로 읽어와야 하는 극심한 메모리 대역폭 병목(Memory Bandwidth Bound) 때문이다. Fast Inference from Transformers via Speculative Decoding (Leviathan et al., 2023), vLLM Speculative Decoding Documentation

결론부터 말하면 투기적 디코딩(Speculative Decoding)은 매 토큰 생성 시 발생하는 메모리 대역폭 낭비를 극복하기 위해, 가벼운 초경량 드래프트 모델(Draft Model)이 여러 개의 후보 토큰을 빠르게 연속 생성(Drafting)하고, 거대한 타깃 모델(Target Model)이 단 한 번의 순방향 연산(Single Forward Pass)으로 이를 병렬 검증(Parallel Verification)하는 2단계 가속 추론 기술이다. 특히 Leviathan et al.(2023)과 Chen et al.(2023)이 정립한 리젝션 샘플링(Rejection Sampling) 수학적 판정 공식을 적용하여, 거절된 토큰을 타깃 모델의 수정 잔여 분포(Residual Distribution)로 즉각 교정함으로써 타깃 모델 본래의 출력 확률 분포와 100% 동일한 무손실(Lossless) 품질을 수학적으로 보장한다. 최신 오픈소스 서빙 엔진인 vLLM, SGLang, HuggingFace TGI는 투기적 디코딩을 네이티브 코어로 채택하여 동일 하드웨어 대비 추론 속도를 2배에서 최대 3배까지 비약적으로 향상시켰다.

이 글에서는 LLM 추론이 겪는 근본적인 하드웨어적 병목 현상을 짚어보고, 투기적 디코딩의 3단계 파이프라인(Drafting → Verification → Rejection Sampling)의 내부 아키텍처를 상세히 해부한다. 이어 리젝션 샘플링의 수학적 무손실 증명과 보너스 토큰(Bonus Token) 획득 원리를 살펴보고, 로컬 Python 스크립트로 직접 구현·검증한 5가지 핵심 시나리오와 프로덕션 서빙 클러스터 구축 시 필수 점검 체크리스트를 정리한다.

1. LLM 추론의 근본적 병목: 메모리 대역폭 한계와 순차적 생성의 비효율

LLM의 텍스트 생성 루프는 본질적으로 이전까지 생성된 모든 토큰을 입력받아 다음 단 하나의 토큰을 예측하는 자가회귀(Autoregressive) 순차 생성 방식으로 동작한다.

산술 강도(Arithmetic Intensity)의 극단적 저하: 입력 프롬프트를 한 번에 병렬 처리하는 프리필(Prefill) 단계와 달리, 디코딩(Decoding) 단계에서는 배치 크기가 작을 때 토큰 1개를 생성하기 위해 모델의 모든 가중치 파라미터를 메모리(HBM)에서 프로세서 코어(SRAM)로 한 번씩 로드해야 한다. 예를 들어 FP16 정밀도의 70B 모델은 140GB의 가중치를 갖는다. 토큰 단 1개를 뽑기 위해 GPU는 140GB의 데이터를 메모리 버스를 통해 읽어와야 하므로, 연산량 대비 메모리 전송량(FLOPs / Byte)이 극도로 낮아져 GPU 연산 유닛의 95% 이상이 유휴(Idle) 상태로 메모리 전송을 기다리게 된다.

직렬 연산의 벽: 100개의 토큰으로 구성된 답변을 생성하려면 최소 100회의 순차적인 GPU 커널 런칭과 140GB × 100회 = 14TB에 달하는 가중치 로딩이 강제된다. 이는 하드웨어의 클럭 속도를 높이지 않는 한 지연 시간을 단축할 수 없는 근본적인 병목이다.

GEMV(Matrix-Vector) vs GEMM(Matrix-Matrix): 단일 토큰 디코딩은 가중치 행렬과 단일 벡터의 곱(GEMV)이지만, 만약 여러 토큰을 동시에 검증할 수 있다면 행렬과 행렬의 곱(GEMM)으로 변환된다. GPU 텐서 코어는 GEMM 연산에서 수십 배 높은 하드웨어 효율을 발휘한다.

투기적 디코딩은 "어차피 대형 모델이 단일 토큰을 처리하나 연속된 $K$ 개의 토큰을 한 번에 검증하나 소요되는 HBM 가중치 로딩 시간은 거의 동일하다"는 하드웨어적 특성에서 출발한 혁신이다.

Speculative Decoding의 3단계 실행 파이프라인 아키텍처 다이어그램이다. 초경량 드래프트 모델(M_draft)이 K개의 후보 토큰을 빠르게 순차 생성하고, 대규모 타깃 모델(M_target)이 단 한 번의 병렬 순방향 연산으로 이를 채점한 뒤, 리젝션 샘플러가 수학적 무손실 검증을 수행하고 공짜 보너스 토큰까지 방출하는 전체 워크플로를 도식화했다.

2. 투기적 디코딩의 핵심 파이프라인: 선행 추측과 병렬 검증

투기적 디코딩은 드래프트 모델(Draft Model, $M_{\text{draft}}$ )과 타깃 모델(Target Model, $M_{\text{target}}$ )의 이중 구조로 실행된다.

1) Phase 1: 경량 드래프트 모델의 K-토큰 선행 생성 (Drafting Phase)

메인 서비스에 배포된 거대 모델(예: Llama-3-70B)에 비해 파라미터 크기가 1/10~1/70 수준에 불과한 작은 자매 모델(예: Llama-3-8B 또는 1B)을 드래프트 모델로 지정한다.

드래프트 모델은 메모리 사용량이 매우 작기 때문에, 자가회귀 루프를 고속으로 돌며 $K$ 개(통상 $K = 3 \sim 5$ )의 후보 토큰 시퀀스 $[x_1, x_2, \dots, x_K]$ 와 각 토큰의 생성 확률 분포 $q(x)$ 를 신속하게 뽑아낸다.

드래프트 모델의 생성은 비록 품질이 대형 모델에 비해 떨어질 수 있지만, 흔히 사용되는 관용구, 조사, 문법적 연결어, 코드 구조 등 쉬운 토큰 구간에서는 대형 모델과 매우 높은 일치율(수락률 $\alpha \approx 70\sim 85\%$ )을 보인다.

2) Phase 2: 대규모 타깃 모델의 단일 병렬 순방향 연산 (Parallel Verification Phase)

타깃 모델은 드래프트 모델이 제안한 $K$ 개의 후보 토큰 시퀀스를 현재 컨텍스트 뒤에 덧붙여 단 한 번의 순방향 연산(Single Forward Pass)으로 병렬 처리한다.

인과적 어텐션 마스크(Causal Attention Mask) 구조 덕분에 타깃 모델은 $[x_1, x_2, \dots, x_K]$ 의 모든 위치에 대한 다음 토큰 로짓 및 확률 분포 $p_1, p_2, \dots, p_K$ 를 동시에 획득한다.

하드웨어 가속의 핵심: $K$ 개의 토큰을 평가하는 데 드는 GPU 시간은 토큰 1개를 순방향 연산하는 시간과 거의 차이가 없다(가중치 행렬 로딩 오버헤드가 지배적이기 때문). 즉, $K$ 번의 GPU 호출을 단 1번으로 압축한 것이다.

3) Phase 3: 리젝션 샘플러 판정과 보너스 토큰(Bonus Token) 획득

타깃 모델이 계산한 확률 $p(x)$ 와 드래프트 모델의 확률 $q(x)$ 를 토큰 순서대로 대조하며 검증을 수행한다.

첫 번째 토큰 $x_1$ 부터 순서대로 수락 여부를 판정한다.

만약 $x_1, x_2, \dots, x_i$ 까지 수락되다가 $x_{i+1}$ 에서 거절되면, $x_{i+1}$ 이후의 모든 드래프트 토큰은 즉시 폐기된다. 대신 거절된 위치 $x_{i+1}$ 은 타깃 모델의 수정 잔여 분포에서 새롭게 샘플링된 대체 토큰으로 채워진다.

보너스 토큰(Bonus Token): 만약 제안된 $K$ 개의 후보 토큰이 모두 수락(All Accepted)되는 경우, 타깃 모델은 $K$ 번째 위치의 출력을 통해 계산해 둔 $K+1$ 번째 토큰의 확률 분포에서 추가 토큰 1개를 공짜(Free)로 샘플링하여 붙인다. 즉, 단 1회의 타깃 모델 순방향 패스로 무려 $K+1$ 개의 토큰이 한꺼번에 확정되는 놀라운 가속이 일어난다.

Rejection Sampling의 수학적 확률 공간 분할 및 무손실 복구 메커니즘 다이어그램이다. 타깃 확률 p(x)와 드래프트 확률 q(x)의 비율에 따른 수락 조건 min(1, p/q)과 거절 시 잔여 질량 max(0, p-q)를 재정규화한 p'(x) 분포가 결합되어, 최종 출력 토큰 분포가 타깃 모델 본래의 분포와 수학적으로 완벽히 일치함을 도식화했다.

3. 리젝션 샘플링(Rejection Sampling)의 수학적 원리와 무손실 증명

투기적 디코딩이 단순한 근사(Approximation)나 휴리스틱이 아닌 엄밀한 컴퓨터 과학적 성취로 인정받는 이유는 타깃 모델 단독으로 디코딩했을 때와 최종 출력 텍스트의 확률 분포가 100% 동일(Lossless)하다는 수학적 정리가 증명되어 있기 때문이다.

1) 수락 판정 규칙 (Acceptance Criterion)

드래프트 모델이 토큰 $x$ 를 확률 $q(x)$ 로 샘플링하여 제안했고, 타깃 모델이 동일 컨텍스트에서 해당 토큰 $x$ 에 부여한 확률이 $p(x)$ 일 때, 수락 확률 $\alpha(x)$ 는 다음과 같이 정의된다.

$ $\alpha(x) = \min\left(1, \frac{p(x)}{q(x)}\right)$$

$p(x) \ge q(x)$ 인 경우: 타깃 모델이 해당 토큰을 드래프트 모델보다 더 선호하거나 동등하게 평가한 경우다. 수락 확률은 정확히 $1.0(100\%)$ 이 되며, 아무런 난수 비교 없이 무조건 수락된다.

$p(x) < q(x)$ 인 경우: 드래프트 모델이 과대평가한 경우다. 균등 난수 $r \sim U(0, 1)$ 을 추출하여 $r < \frac{p(x)}{q(x)}$ 이면 수락하고, 그렇지 않으면 거절한다.

2) 거절 시 수정 잔여 분포 (Residual Distribution $p'(x)$ )

토큰 $x$ 가 거절되었을 때, 단순히 타깃 모델의 전체 분포 $p(x)$ 에서 다시 뽑는 것이 아니라, 드래프트 모델이 깎아먹은 확률 질량을 정밀하게 보정하는 잔여 분포 $p'(x)$ 에서 대체 토큰을 샘플링한다.

$ $p'(x) = \frac{\max(0, p(x) - q(x))}{\sum_{y \in \mathcal{V}} \max(0, p(y) - q(y))}$$

이미 드래프트 단계에서 $q(x) > p(x)$ 로 과도하게 제안되었던 토큰들은 $\max(0, p(x) - q(x)) = 0$ 이 되므로 잔여 분포에서 확률이 완전히 $0$ 으로 소멸한다.

반대로 타깃 모델 $p(x)$ 가 드래프트 모델 $q(x)$ 보다 더 높게 평가했던 '소외된 정답 후보들'에게만 잔여 확률 질량이 재분배된다.

3) 무손실(Lossless) 수렴의 수학적 증명

최종적으로 시스템에서 토큰 $x$ 가 방출될 전체 확률 $P_{\text{final}}(x)$ 는 (1) 드래프트 토큰으로 제안되어 수락될 확률과 (2) 거절된 후 잔여 분포 $p'(x)$ 에서 선택될 확률의 합이다.

$ $P_{\text{final}}(x) = q(x) \cdot \alpha(x) + \left(1 - \sum_{y \in \mathcal{V}} q(y) \alpha(y)\right) \cdot p'(x)$$

여기서 $q(x) \alpha(x) = q(x) \min\left(1, \frac{p(x)}{q(x)}\right) = \min(p(x), q(x))$ 이다.

또한 전체 거절 확률은 $1 - \sum_y \min(p(y), q(y)) = \sum_y (p(y) - \min(p(y), q(y))) = \sum_y \max(0, p(y) - q(y))$ 이다.

이를 잔여 분포 식의 분모와 약분하면 다음과 같은 아름다운 항등식이 유도된다.

$ $P_{\text{final}}(x) = \min(p(x), q(x)) + \max(0, p(x) - q(x)) = p(x)$$

결과적으로 투기적 디코딩을 거쳐 샘플링된 모든 토큰의 확률 분포는 거대 타깃 모델 $p(x)$ 단독으로 샘플링한 것과 완벽히 일치(Strictly Lossless)한다. 환각이 증가하거나 문장이 조잡해지는 어떠한 정밀도 손실도 이론적으로 발생하지 않는다.

4. 기존 순차 디코딩 vs 투기적 디코딩 아키텍처 비교

두 디코딩 방식의 시스템 및 성능 차이를 비교하면 다음과 같다.

비교 항목	1. 표준 자가회귀 순차 디코딩 (Standard Autoregressive)	2. 투기적 디코딩 (Speculative Decoding, Draft+Target)
출력 품질 보장	타깃 모델 기준 100% 원본	리젝션 샘플링 기반 수학적 100% 무손실 동등성 보장
토큰당 타깃 GPU 호출	토큰 1개당 타깃 모델 Forward Pass 1회 강제	K개 토큰 묶음당 타깃 Forward Pass 1회 (최대 K+1개 생성)
하드웨어 연산 형태	극단적 GEMV (메모리 대역폭 병목, GPU 연산기 90%+ 유휴)	GEMM 변환 (배치 텐서 연산으로 GPU 텐서 코어 활용도 극대화)
생성 속도 (TPOT 가속비)	기준 속도 (1.0x)	2.0x ~ 3.2x 속도 향상 (수락률 α에 따라 결정)
메모리 요구사항	타깃 모델 가중치 + KV 캐시	타깃 모델 + 소형 드래프트 모델 가중치 (추가 VRAM 5~10% 소요)
서빙 엔진 지원	모든 추론 프레임워크 기본 지원	vLLM, SGLang, HuggingFace TGI, TensorRT-LLM 네이티브 지원

5. 로컬 Python으로 검증하는 Speculative Decoding 및 리젝션 샘플링 시뮬레이션

투기적 디코딩의 핵심 수학적 메커니즘인 결정론적 수락 조건( $p \ge q$ ), 확률적 기각 판정( $p < q$ ), 잔여 분포( $p'(x)$ ) 정규화 및 질량 보존, $K$ 개 연속 통과 시 보너스 토큰 획득, 그리고 5만 회 몬테카를로 시뮬레이션을 통한 무손실 분포 일치성을 완벽히 재현한 로컬 Python 검증 스크립트(test_speculative_decoding.py)를 작성하여 실행했다.

직접 실행해 확인한 5가지 검증 시나리오

로컬 터미널 환경에서 위 검증 스크립트를 직접 실행하여 5가지 시나리오가 모두 정상 통과(ALL 5 SPECULATIVE DECODING VERIFICATION CHECKS PASSED SUCCESSFULLY!)함을 확인했다.

타깃 확률 우위 시 결정론적 100% 수락 검증 (Case 1): 타깃 확률( $p=0.5$ )이 드래프트 확률( $q=0.3$ )보다 큰 경우 비율이 $1.67 \ge 1.0$ 이 되어 어떠한 난수 값(0.01~0.9999)에서도 100% 확률로 수락됨을 확인했다.

타깃 확률 열위 시 임계치 기반 리젝션 정밀도 검증 (Case 2): $p=0.4, q=0.8$ 로 비율이 $0.5$ 인 상황에서 $\text{rand}=0.49$ 일 때 정확히 수락되고, $\text{rand}=0.51$ 일 때 정확히 거절됨을 확인했다.

잔여 분포 $p'(x)$ 정규화 및 질량 보존 검증 (Case 3): 거절 시 계산된 잔여 분포의 총합이 정확히 $1.000000$ 으로 정규화되며, 드래프트 확률이 더 높았던 어휘 인덱스의 잔여 확률 질량이 수학적으로 정확히 $0.0$ 으로 소거됨을 확인했다.

$K$ 개 드래프트 전체 수락 시 보너스 토큰(Bonus Token) 획득 검증 (Case 4): $K=3$ 개의 후보 토큰("the", "cat", "sat")이 모두 통과했을 때, 추가 Forward Pass 없이 타깃 모델의 $K+1$ 번째 예측 토큰("mat")이 보너스로 결합되어 총 4개의 토큰이 단 1회의 검증 스텝에서 동시 확정됨을 입증했다.

50,000회 몬테카를로 시뮬레이션을 통한 무손실(Lossless) 수렴 증명 (Case 5): 드래프트 모델과 타깃 모델의 확률 분포가 극단적으로 어긋난 조건( $Q$ 와 $P$ 의 괴리)에서도, 투기적 디코딩을 거쳐 샘플링된 토큰 빈도 분포가 타깃 모델 직접 샘플링 결과와 최대 오차 $0.0029$ 이내로 완벽히 일치하여 수학적 무손실성(Lossless Equivalence)을 실험적으로 증명했다.

6. 프로덕션 LLM 서빙 도입 및 성능 최적화 체크리스트

드래프트 모델 크기와 후보 수 $K$ 의 경제적 스윗스팟 도출:

후보 수 $K$ 를 무작정 늘린다고 속도가 계속 빨라지지 않는다. $K$ 가 너무 크면 드래프트 생성 시간 오버헤드가 커지고 후반부 토큰 거절률이 높아져 오히려 전체 처리량이 저하된다. 일반적인 자연어 태스크에서는 $K = 3 \sim 5$ , 코드 생성 등 결정론적 성향이 강한 태스크에서는 $K = 5 \sim 7$ 이 최적의 수락률-지연시간 균형점이다.

동일 토크나이저 패밀리 매칭 및 이종 어휘 교집합(Token-Level Intersection):

드래프트 모델과 타깃 모델은 동일한 토크나이저(BPE/SentencePiece) 어휘 사전을 공유하는 것이 가장 이상적이다(예: Llama-3-8B 드래프트 + Llama-3-70B 타깃). 만약 토크나이저가 다른 이종 모델을 조합해야 한다면 vLLM의 use_heterogeneous_vocab 기능처럼 어휘 ID 간의 교집합 매핑 테이블을 구성해야 한다.

KV 캐시 롤백(Rollback) 및 페이징 메모리 오버헤드 관리:

타깃 모델은 $K$ 개의 후보 토큰을 검증하기 위해 해당 토큰들의 Key-Value 텐서를 캐시에 적재한다. 만약 $i$ 번째 토큰에서 거절이 발생하면 $i+1$ 부터 $K$ 까지의 미사용 KV 캐시 블록을 즉시 해제(Rollback)해야 한다. PagedAttention 메모리 풀과 연동하여 블록 반환 누수가 생기지 않도록 관리해야 한다.

배치 서빙(Continuous Batching) 환경에서의 동적 $K$ 조율:

동시 동적 배치가 수십 개 이상 몰리는 고부하 서빙 환경에서는 GPU가 이미 GEMM 병렬화 한계에 도달해 있으므로 투기적 디코딩의 가속비가 감소할 수 있다. 요청 큐의 부하도에 따라 $K$ 값을 동적으로 축소하거나 비활성화하는 적응형 스케줄링(Adaptive Speculation)을 적용해야 한다.

모델 프리 대안 기법 검토 (Prompt Lookup & Medusa):

별도의 드래프트 모델을 VRAM에 띄울 메모리 여유가 없다면, 프롬프트 본문에서 반복되는 n-gram 문자열을 후보 토큰으로 추출하는 Prompt Lookup Decoding이나, 타깃 모델의 마지막 히든 스테이트 위에 여러 개의 단일 레이어 헤드를 얹는 Medusa / EAGLE 아키텍처를 도입하여 추가 VRAM 비용 없이 투기 가속을 달성할 수 있다.