← all posts
AI 2026.05.03 · 9 min read Advanced

Speculative Decoding은 어떻게 분포를 보존하면서 빠른가

Autoregressive 병목의 수학적 구조부터 Rejection Sampling의 Losslessness 증명, Medusa·EAGLE·Lookahead까지 — draft 전략의 설계 철학을 추적한다.

📚 Llm Efficiency Deep Dive 7 / 7
  1. 01 LLM Fine-Tuning의 메모리 문제는 어디서 오는가
  2. 02 LoRA는 왜 저차원 행렬 두 개로 충분한가
  3. 03 LLM Quantization의 설계 철학 — 무엇을 희생하고 무엇을 보호할 것인가
  4. 04 QLoRA는 어떻게 65B 모델을 GPU 한 장에 올렸나
  5. 05 MoE는 왜 같은 연산으로 더 큰 모델처럼 동작하는가
  6. 06 Flash Attention은 어떻게 T² 메모리 장벽을 넘었나
  7. 07 Speculative Decoding은 어떻게 분포를 보존하면서 빠른가

LLM 추론의 병목은 연산 능력 부족이 아니다. GPU가 100배 더 강해도 token 하나를 생성할 때마다 수십 GB의 가중치를 HBM에서 통째로 읽어야 한다 — 이것이 근본 제약이다. 그렇다면 “target 분포를 한 치도 바꾸지 않으면서” 이 병목을 우회할 수 있을까?

병목의 수학적 구조

Autoregressive generation은 구조적으로 순차다. tt번째 token을 생성하려면 반드시 t−1t-1번째 결과가 있어야 한다. TT tokens를 생성하면 TT번의 forward pass가 불가피하다.

각 forward pass는 memory-bound다. Single token input일 때 weight W∈Rd×dW \in \mathbb{R}^{d \times d}를 읽는 비용은 d2⋅2d^2 \cdot 2 bytes (FP16)인 반면 연산은 ≈4d2\approx 4d^2 FLOPs — arithmetic intensity가 2 정도로, GPU의 compute가 쉬는 동안 HBM bandwidth가 bottleneck이 된다.

이로부터 latency lower bound가 따라온다.

Lautoregressive(T)≥T⋅2N2BHBML_{\mathrm{autoregressive}}(T) \geq T \cdot \frac{2N^2}{B_{\mathrm{HBM}}}

여기서 NN은 hidden dimension, BHBM≈2 TB/sB_{\mathrm{HBM}} \approx 2\,\text{TB/s} (A100). 7B 모델(hidden=4096)의 per-token latency lower bound는 약 0.54 ms — T=1000T=1000이면 540 ms 이상이 필연적이다.

KV cache도 압박을 더한다. Batch size BB, sequence length TT, key/value dim dkd_k일 때:

KV cache bytes=2×B×T×dk×2(FP16)\text{KV cache bytes} = 2 \times B \times T \times d_k \times 2 \quad (\text{FP16})

TT에 이차로 증가하므로, 긴 생성일수록 batch size를 줄여야 한다.

Speculative Decoding의 핵심 아이디어

병목을 “우회”하는 아이디어는 단순하다. 작은 draft model qq로 KK개 token을 미리 생성하고, 큰 target model pp로 이 KK개를 한 번의 forward에서 병렬 검증한다. Target의 forward 횟수가 TT에서 T/KT/K로 줄어든다.

기대 speed-up은 다음과 같다.

Speed-up=1+Kαˉ1+Kc\text{Speed-up} = \frac{1 + K \bar{\alpha}}{1 + K c}

αˉ\bar{\alpha}는 평균 acceptance rate, cc는 draft/target 비용 비율. 최적 KK는 K∗≈αˉ/cK^* \approx \sqrt{\bar{\alpha}/c}이다. 예컨대 αˉ=0.6\bar{\alpha} = 0.6, c=0.1c = 0.1이면 K∗≈2.4K^* \approx 2.4 — 실제로는 K=3K = 3 정도가 최적이다.

✎ 트레이드오프

Draft가 target에 가까울수록 αˉ\bar{\alpha}가 높아져 speed-up이 증가한다. 그러나 draft model이 커질수록 cc도 커져 분모도 커진다. 대부분의 실험에서 draft는 target의 5–20% 크기(예: 70B target에 1.3B draft)가 최적점이다.

Losslessness — 분포가 정확히 보존되는 이유

Speed-up만으로는 부족하다. “근사”라면 downstream 품질이 흔들린다. Speculative decoding의 진짜 강점은 target 분포를 수학적으로 보존한다는 점이다.

정리 1 · Rejection Sampling Losslessness (Leviathan et al. 2023)

다음 알고리즘으로 샘플링한 xx는 정확히 분포 p(x)p(x)를 따른다: (1) x∼qx \sim q, (2) U∼Unif(0,1)U \sim \mathrm{Unif}(0,1), (3) U<α(x):=min⁡(1,p(x)/q(x))U < \alpha(x) := \min(1, p(x)/q(x))이면 accept, (4) 아니면 r(x)∝(p(x)−q(x))+r(x) \propto (p(x) - q(x))_+에서 resample.

▷ 증명

전체 확률을 accept 항과 reject 항으로 분해한다.

Accept 기여: min⁡(q(x),p(x))\min(q(x), p(x))

Reject 후 resample 기여: reject mass Mreject=1−∑xmin⁡(q(x),p(x))M_{\mathrm{reject}} = 1 - \sum_x \min(q(x), p(x))에 잔여 분포 r(x)r(x)를 곱한다.

Pr⁡(X=x)=min⁡(q(x),p(x))+Mreject⋅(p(x)−q(x))+∑y(p(y)−q(y))+\Pr(X = x) = \min(q(x), p(x)) + M_{\mathrm{reject}} \cdot \frac{(p(x)-q(x))_+}{\sum_y (p(y)-q(y))_+}

핵심 항등식 min⁡(a,b)+(a−b)+=a\min(a, b) + (a - b)_+ = a를 적용하면:

=min⁡(q(x),p(x))+(p(x)−q(x))+=p(x)□= \min(q(x), p(x)) + (p(x) - q(x))_+ = p(x) \quad \square
∎

따름정리로, rejection rate는 정확히 total variation distance와 같다: Pr⁡(reject)=DTV(p,q)\Pr(\text{reject}) = D_{\mathrm{TV}}(p, q). Draft가 target에 가까울수록 TV distance가 작아지고 acceptance rate가 올라간다 — 이것이 더 좋은 draft를 만드는 동기다.

Draft 전략의 진화

Losslessness가 보장되면 남은 질문은 “어떻게 더 좋은 draft를 만드는가”다. 세 가지 방향이 존재한다.

Medusa: Target model의 중간 layer hidden state hth_t에 KK개의 경량 decoding head를 추가한다. 외부 모델 없이 target 자체의 feature를 재사용하므로 draft cost가 극히 낮고, 같은 feature space에서 예측하므로 αˉ≈75–80%\bar{\alpha} \approx 75\text{–}80\%로 높다. Tree-structured verification으로 여러 분기를 병렬 탐색하면 effective speed-up은 2.5–3×.

EAGLE: Token 확률을 직접 예측하는 대신 hidden state를 예측한다. Feature space는 semantically similar tokens가 가깝게 배치되어 있어, feature distance가 작으면 logit도 비슷하다 — smooth geometry를 활용해 αˉ≈82%\bar{\alpha} \approx 82\%까지 달성한다. 단, target별 distillation 학습이 필요하다.

Lookahead: N-gram cache를 사전통계에서 구축하고, 현재 context의 마지막 n−1n-1 tokens로 후보를 lookup한다. 학습이 전혀 필요 없다. αˉ≈55%\bar{\alpha} \approx 55\%로 낮지만 배포 즉시 적용 가능하다.

정리

  • Autoregressive generation의 bottleneck은 compute가 아닌 HBM bandwidth다. Per-token latency lower bound는 T⋅2N2/BHBMT \cdot 2N^2 / B_{\mathrm{HBM}}이다.
  • Speculative decoding은 small draft + parallel verify로 target forward 횟수를 줄이면서, rejection sampling으로 분포를 수학적으로 보존한다.
  • Losslessness의 핵심 항등식: min⁡(q(x),p(x))+(p(x)−q(x))+=p(x)\min(q(x), p(x)) + (p(x) - q(x))_+ = p(x).
  • Draft 전략은 training overhead와 acceptance rate의 trade-off다 — Medusa/EAGLE은 높은 acceptance를 위해 학습을 투자하고, Lookahead는 즉시성을 위해 acceptance를 양보한다.

분포를 바꾸지 않고 속도를 2–3배 높이는 것 — 이것이 speculative decoding이 “근사”가 아닌 이유다.

REF
REF
# speculative-decoding # autoregressive # rejection-sampling # llm-efficiency