Machine Learning

Speculative Decoding 도입 전에 확인해야 할 것들

VESSL AI

|2026년 10월 2일|19분 소요

TL;DR

decode는 memory-bound입니다. 70B 모델 기준으로 42ms짜리 memory 읽기 안에 compute는 0.14ms만 들어 있습니다.
speculative decoding의 speedup은 parameter 세 개(acceptance rate, drafter의 상대 비용, speculation 길이)와 상한 하나로 정리됩니다.
이 기법은 compute를 써서 latency를 줄입니다. 고정된 load에서는 이득이지만 saturation 상태에서는 비용입니다.
같은 구성이 operating point에 따라 2.33배에서 1.16배까지 달라집니다. operating point 없이 인용된 speedup은 표의 cell 하나일 뿐입니다.

decode에서 GPU는 왜 대부분 기다리고 있을까요?

Autoregressive 생성은 forward pass 한 번에 token을 하나씩만 만듭니다:

x_i \sim p(\,\cdot \mid x_{<i}), \qquad i = 1, 2, \dots, N

token $N$ 개를 만들려면 pass $N$ 번이 순서대로 필요하다는 뜻인데, 문제는 연산량이 아니라 이 순차 의존성입니다.

bf16으로 올린 70B 모델의 decode step 하나를 보면, token 하나를 만들기 위해 HBM에서 weight 약 140 GB를 읽어야 합니다. 3.35 TB/s인 H100 기준으로 약 42 ms, 초당 24 token 정도입니다. 반면 같은 pass의 연산량은 $2P = 1.4 \times 10^{11}$ FLOPs로, peak 989 TFLOP/s 기준 0.14 ms에 불과합니다. 42 ms짜리 memory 읽기 안에 compute는 0.14 ms만 들어 있는 셈입니다.

즉 decode는 2~3 orders of magnitude 차이로 memory-bound이고, GPU는 대부분의 시간을 기다리면서 보냅니다.

Roofline: memory roof와 compute roof 기준으로 decode, speculation, prefill이 위치한 지점

draft로 뽑은 token $\gamma$ 개를 forward pass 한 번으로 검증하면 position은 $\gamma+1$ 개가 되고, weight 읽기량은 그대로인 채 arithmetic intensity만 그만큼 올라갑니다. memory-bound 구간에서는 이것이 거의 공짜이고, 이 글의 나머지 내용은 전부 이 사실 하나에서 출발합니다.

대부분의 가속 기법은 step 하나를 싸게 만드는 쪽입니다. quantization과 sparsity는 weight당 byte 수를 줄이고, batch를 키우면 weight 읽기 비용이 여러 요청으로 나눠지고, 더 좋은 kernel은 상수 항을 깎습니다. 하지만 어느 것도 순차 실행 구조 자체는 건드리지 않습니다.

speculation은 접근이 다릅니다. 순차 의존성 자체를 공격하는 데다, 위 기법들 중 유일하게 정확한 lossless가 가능하기 때문입니다.

알고리즘

구조는 간단합니다. 싼 drafter가 token $\gamma$ 개를 제안하면, target이 forward pass 한 번으로 $\gamma+1$ 개 position을 한꺼번에 검사하고, 유효한 가장 긴 prefix만 확정합니다.

# one speculative cycle
#   prefix x[:i], speculation length gamma
#   M_t = target, M_d = drafter

# --- draft phase: gamma sequential cheap steps ---
for j in range(gamma):
    q[i+j]  = M_d(prefix=x[:i] + draft[:j])
    draft[j] = sample(q[i+j])

# --- verify phase: ONE target pass over gamma+1 positions ---
p[i : i+gamma+1] = M_t(x[:i] + draft, causal_mask=True)

r = uniform(0, 1, size=gamma)
n = first_index_where(r > p[i+j][draft[j]] / q[i+j][draft[j]])   # or gamma

emit(draft[:n])                                   # n accepted tokens
if n < gamma:
    emit(sample(normalize(relu(p[i+n] - q[i+n]))))  # corrected token
else:
    emit(sample(p[i+gamma]))                        # free bonus token

truncate_kv_cache(to=len_emitted)

여기서 두 가지를 눈여겨볼 필요가 있습니다. 먼저 $\gamma$ 개의 ratio test는 target pass 한 번 뒤에 전부 병렬로 실행되기 때문에 verification에는 순차 의존성이 없는데, 사실 이것이 이 알고리즘의 핵심입니다. 그리고 rejection이 나더라도 수정된 token 하나는 반드시 나오므로 $\tau \geq 1$ 이고, speculation 때문에 생성이 멈추는 일은 없습니다.

아이디어 자체는 CPU의 branch prediction에서 왔지만, 실무에서는 두 가지 차이가 중요합니다. CPU의 misprediction이 정확성 문제라면 LLM의 rejection은 통계 문제라서, draft로 뽑힌 token이 텍스트로는 완전히 자연스러워도 분포가 맞지 않으면 거절됩니다. 검사 기준이 정확성이 아니라 분포의 일치이기 때문입니다. 또 하나, CPU의 pipeline flush는 원래 싸지만 LLM의 rollback이 싼 것은 KV cache가 append-only이기 때문인데, 이 전제는 recurrent-state layer나 linear-attention layer에서는 깨집니다.

acceptance rule

drafter에서 $x \sim q$ 를 뽑고, 확률 $\min\!\big(1, \tfrac{p(x)}{q(x)}\big)$ 로 받아들입니다. 거절되면 정규화한 residual에서 대체 token을 뽑습니다:

p'(x) = \frac{\max\big(0,\; p(x) - q(x)\big)}{\sum_{u \in \mathcal{V}} \max\big(0,\; p(u) - q(u)\big)}

직관적으로 보면 $q$ 는 어떤 token에는 확률을 너무 많이 주고 어떤 token에는 너무 적게 주는데, ratio test가 그 초과분을 제거하고 residual이 부족분을 다시 채우는 구조입니다.

Theorem (losslessness). 최종 출력 token은 정확히 $p$ 를 따릅니다.

증명. $\beta = \sum_u \min(p(u), q(u))$ 로 둡니다. acceptance 경로의 기여는 $q(x)\min\!\big(1, \tfrac{p(x)}{q(x)}\big) = \min(p(x), q(x))$ 이고, rejection 경로의 기여는 $(1-\beta)\,p'(x)$ 인데 정규화 상수가 정확히 $1 - \beta$ 라서 $\max(0, p(x) - q(x))$ 가 됩니다. 두 경로를 더하면:

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

이 증명이 $q$ 의 어떤 성질도 사용하지 않는다는 점이 중요합니다. 이 사실 하나가 design space 전체를 열어줍니다. n-gram table이든 suffix automaton이든 diffusion 모델이든, 양자화한 네트워크나 layer 절반을 건너뛴 target까지도 전부 drafter가 될 수 있고, 전부 lossless이며, 정확성 증명은 그대로입니다.

그래서 drafter를 개선하는 일은 전부 효율 개선입니다. lossless 계열 안에는 품질 trade-off라는 것이 존재하지 않습니다.

acceptance rate에는 closed form도 있습니다:

\alpha \;=\; \mathbb{E}_{x \sim q}\!\left[\min\!\left(1, \frac{p(x)}{q(x)}\right)\right] \;=\; \sum_{u \in \mathcal{V}} \min\big(p(u), q(u)\big) \;=\; 1 - D_{TV}(p, q)

Leviathan et al. (2023)의 이 항등식은 system 질문(fast path가 얼마나 자주 실행되는가)을 통계 질문(두 분포가 $L_1$ 에서 얼마나 가까운가)으로 바꿔놓습니다. 원 논문은 이 거리를 $D_{LK}$ 라는 자체 표기로 부르고, prefix 하나에 대한 acceptance 확률과 그 기댓값을 다른 기호로 구분합니다. 덕분에 drafter 학습은 optimal objective가 알려진, 잘 정의된 최적화 문제가 되고, 이 글의 나머지도 감이 아니라 계산으로 진행할 수 있습니다.

자주 틀리는 corollary가 두 개 있습니다. top-1 일치율은 temperature 0이 아닌 한 $\alpha$ 가 아닙니다. 그리고 $\alpha$ 는 원래 position마다 다른 값이라서, 어딘가에서 인용된 숫자 하나는 명시되지 않은 context 조합에 대한 평균일 뿐입니다.

speedup을 결정하는 방정식

acceptance가 i.i.d. $\text{Bernoulli}(\alpha)$ 라 가정하고 drafter의 상대 비용을 $c = T_{\text{draft}} / (\gamma \, T_{\text{target}})$ 로 정의하면, 여기서 $T_{\text{draft}}$ 는 draft step 하나가 아니라 token $\gamma$ 개를 뽑는 draft 단계 전체의 시간입니다. cycle당 기대 token 수는 truncated geometric으로 떨어집니다:

\mathbb{E}[\tau] = \sum_{k=0}^{\gamma} \alpha^k = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha}

cycle 하나의 비용이 $(c\gamma + 1)\,T_{\text{target}}$ 이니, 둘을 나누면 speedup 방정식이 나옵니다. 이것도 같은 논문에 있습니다:

\boxed{\;S(\gamma) \;=\; \frac{\mathbb{E}[\tau]}{c\gamma + 1} \;=\; \frac{1 - \alpha^{\gamma+1}}{(1 - \alpha)\,(c\gamma + 1)}\;}

parameter는 $\alpha$ , $c$ , $\gamma$ 세 개뿐입니다. 그리고 speculative decoding 논문 대부분은 다음 네 항 중 하나를 움직이는 것으로 정리됩니다:

Lever	하는 일	예시
$\alpha \uparrow$	drafter의 분포 $q$ 를 target의 분포 $p$ 에 가깝게 만들어서 accept 확률을 올립니다.	EAGLE, DistillSpec, MTP
$c \downarrow$	target 대비 draft 비용을 낮춰서 cycle당 overhead를 줄입니다.	FR-Spec, MagicDec, parallel drafter
$\gamma$ 재배분	같은 draft budget을 chain 대신 tree 같은 다른 구조에 씁니다.	SpecInfer, Sequoia, EAGLE-2
rule 변경	accept 판정 기준 자체를 완화합니다. lossless 보장은 포기합니다.	typical acceptance, Judge, SpecTr

하나씩 풀어보면 이렇습니다. 첫 번째 lever는 drafter를 더 정확하게 만드는 것입니다. $\alpha = 1 - D_{TV}(p, q)$ 이므로 drafter의 분포가 target의 분포에 가까울수록 draft가 받아들여질 확률이 올라갑니다. 두 번째는 drafter를 더 싸게 만드는 것입니다. 같은 $\alpha$ 라도 draft에 드는 시간이 줄면 cycle당 비용이 내려가서 speedup이 커집니다. 세 번째는 draft budget은 그대로 두고 구조를 바꾸는 것으로, token $\gamma$ 개를 일렬로 뽑는 대신 tree 형태로 여러 후보를 뽑는 방식입니다. 아래에서 따로 다룹니다. 마지막은 accept 판정 기준 자체를 바꾸는 것인데, lossless 보장을 포기하는 대가가 따릅니다.

여기서 결론이 세 개 나옵니다.

상한이 있고, 그 상한은 $c$ 가 정합니다.

S \;\le\; \min\left\{\frac{1}{c},\; \frac{1}{1-\alpha}\right\}

drafter가 싸지 않으면 아무리 정확해도 소용없다는 뜻입니다. 단 $1/c$ 쪽은 $c \le 1$ 을 전제하는데, drafter라고 부를 만한 것이라면 항상 성립합니다.

speedup은 자동이 아닙니다. $\gamma = 1$ 에서 $S = (1+\alpha)/(c+1)$ 이라, $\alpha > c$ 가 아니면 speculation은 오히려 느립니다. target의 절반 비용인 drafter라면 절반 이상은 맞혀야 본전인 셈입니다.

$\alpha$ 와 $c$ 는 묶여 있습니다. 최적 $\gamma$ 가 $\alpha$ 와 함께 커지고 $c$ 와 함께 작아지기 때문에, 둘을 따로 조정할 수는 없습니다.

여러 acceptance rate에서 speculation length에 따른 speedup 곡선

이 그림에서 읽을 점은 두 가지입니다. $\alpha$ 가 커질수록 peak가 오른쪽으로 이동한다는 것, 그리고 곡선이 꽤 평평하다는 것입니다. $\alpha = 0.8$ 이고 $c = 0.05$ 일 때는 $\gamma$ 가 6에서 11 사이 어디에 있든 최적값의 3% 이내입니다. 그래서 $\gamma$ 를 정확히 맞추는 것보다 $\alpha$ 와 $c$ 를 제대로 만드는 것이 훨씬 중요하고, adaptive- $\gamma$ scheduler의 가치도 $\gamma^\star$ 를 정밀하게 찾는 데 있는 것이 아니라 $\gamma$ 가 지나치게 큰 구간을 피하게 해주는 데 있습니다.

$\partial S / \partial \gamma = 0$ 을 풀면 다음 조건이 나오는데,

\alpha^{\gamma+1}\big(c - (c\gamma + 1)\ln \alpha\big) = c

좌변이 $\gamma$ 에 대해 strictly decreasing이라 $S$ 는 unimodal입니다. $\gamma$ 를 탐욕(greedy) 방식으로 탐색하는 scheduler 입장에서는 좋은 소식입니다.

acceptance rate / draft cost 평면에서의 최대 speedup과 iso-speedup contour

이 그림이 상한을 구체적으로 보여줍니다. $\alpha$ 축을 따라 이동해서 얻는 것보다 $c$ 축을 따라 내려가서 얻는 것이 크고, $\alpha = c$ 선 아래에서는 어떤 $\gamma$ 를 골라도 소용없습니다.

실제 도달점이 상한에서 얼마나 떨어져 있는지도 봐야 합니다. $c = 0.05$ 면 상한은 $1/c = 20$ 이지만, $\alpha = 0.95$ 를 달성해도 최대 $6.6$ ( $\gamma^\star \approx 21$ )이고 $\alpha = 0.8$ 이면 $3.1$ 에 그칩니다. 상한은 어디까지나 bound이지 목표가 아닙니다.

$\gamma$ 재배분: chain 대신 tree

다음 주제로 넘어가기 전에 lever 하나만 더 보겠습니다. $\gamma$ 재배분이란 scalar $\gamma$ 를 구조로 바꾸는 것을 말합니다. token $\gamma$ 개짜리 chain 하나 대신 후보 continuation들의 tree를 draft로 뽑고, 각 branch가 자기 조상 node만 참조하도록(causal) mask를 걸어 target pass 한 번으로 여러 chain을 검증하는 방식입니다. budget은 그대로 두고 쓰는 구조만 바꾸는 것입니다.

tree 모양을 고르는 데는 깔끔한 답이 있습니다. 각 node를 survival probability $a_v$ , 즉 그 node까지 도달하고 accept까지 될 확률로 평가해서 전체에서 top- $n$ 을 고르면 됩니다. $a_v$ 는 root에서 내려갈수록 감소만 하므로, 동점일 때 얕은 쪽을 먼저 고르기만 하면 이 greedy 선택은 prefix-closed이고, 짧은 귀납법으로 고정 budget에서 optimal임을 보일 수 있습니다. 같은 논리가 tree node, block 안의 draft position, batch 안의 request라는 세 가지 index set에서 그대로 반복되는데, 명제 하나가 tree 구성과 draft 길이 선택, batch scheduling까지 전부 커버하는 이유가 여기에 있습니다. 다만 이 명제가 정하는 건 주어진 budget을 어떻게 쓰느냐이지, budget을 얼마로 잡느냐가 아닙니다.

speculation은 왜 compute를 더 쓸까요?

$S(\gamma)$ 는 wall-clock 기준의 명제라서, 추가로 검증하는 token이 공짜라는 가정이 깔려 있습니다. 이 가정은 memory-bound 구간에서만 성립합니다.

Leviathan et al.은 같은 논문에서 두 번째 theorem을 제시하는데, 이번에는 wall-clock 시간이 아니라 연산량 기준입니다. drafter의 연산량 비율을 $\hat{c}$ 라 하면 전체 연산량의 기대 증가율이 다음과 같습니다:

\frac{(1 - \alpha)(\gamma\hat{c} + \gamma + 1)}{1 - \alpha^{\gamma+1}} \;>\; 1

speculative decoding은 아끼는 것보다 많은 compute를 쓰는 기법입니다. compute를 소모해서 latency를 줄이는 구조인 것입니다.

그래서 고정된 load에서 time-to-token을 최적화하는 상황이라면 $S(\gamma)$ 가 기준이고 speculation은 이득이지만, saturation 상태에서 초당 token 수를 최적화하는 상황이라면 위 식이 기준이고 speculation은 비용입니다. 두 해석 모두 맞습니다. 둘 중 하나만 보고하는 benchmark로는 도입 여부를 판단할 수 없다는 것이 문제일 뿐입니다.

production에서도 그대로 나타납니다. DeepSeek의 hardware retrospective에는 MTP가 throughput을 약간 떨어뜨리는 대신 end-to-end latency를 크게 개선했다는 기록이 있는데, 연산량 theorem이 대규모 환경에서 관측된 사례라고 볼 수 있습니다.

VESSL AI가 측정한 것

VESSL AI는 GLM-5.2, MiniMax-M3 등 여러 오픈소스 모델을 VESSL Cloud에서 speculative decoding을 적용해 production으로 서빙하고 있는데, 돌아오는 숫자는 drafter보다 측정 지점에 더 크게 좌우됩니다.

예를 하나 보겠습니다. Solar-Open2-250B에 DSpark drafter를 붙인 구성을 일반 autoregressive decoding과 비교해서, 여섯 개 operating point에서 각각 3회씩 측정했을 때입니다.

여섯 개 operating point에서의 speedup, context와 concurrency 두 축을 따라 감소

축이 두 개인데 효과는 곱으로 작용합니다. concurrency를 1에서 8로 올리면 약 26%를 잃고, context를 8~16K에서 80~128K로 늘리면 약 31%를 잃어서, 둘이 겹치면 2.33×가 1.16×까지 내려갑니다.

왼쪽 위 cell과 오른쪽 아래 cell 사이에서 drafter는 아무것도 바뀌지 않았습니다. 두 숫자 모두 정확한 측정값인데, 실제 배포 환경을 설명하는 것은 둘 중 하나뿐입니다.

같은 기법이 조건에 따라 빨라지기도, 느려지기도 합니다

같은 drafter 계열을 GLM-5.2에 붙이면 single-stream 요청에서 2.99×가 나옵니다. mean accepted length 4.44로 모델 내장 MTP head의 1.93보다 높습니다. 그런데 concurrency를 64로 올리면 acceptance는 유지되는데 speedup이 따라오지 못합니다. load가 일정 수준을 넘으면 추가 verification 연산이 아낀 pass보다 비싸지기 때문입니다.

앞에서 본 두 번째 theorem이 production에서 이렇게 나타납니다. speculation은 compute를 소모해서 latency를 줄이는 기법이라, compute가 가장 부족한 자원인 상황에서는 소모할 것 자체가 없는 것입니다.

측정에 사용한 drafter, DSpark

위 측정에 등장한 drafter가 DSpark입니다. DeepSeek-AI가 베이징대와 함께 발표하고 자사 서빙 스택에 적용한 방식이고, Solar-Open2-250B와 GLM-5.2에 붙인 것도 각 target에 맞춰 학습한 같은 계열입니다.

DSpark는 parallel drafter입니다. token $\gamma$ 개를 하나씩 순서대로 뽑는 대신 forward pass 한 번으로 draft block 전체를 채우는데, 이 backbone은 DSpark가 새로 만든 것이 아니라 DFlash에서 가져온 것입니다. draft가 pass 하나로 끝나므로 $c$ 가 작아지고, 앞의 방정식에서 본 대로 상한 $1/c$ 가 올라갑니다.

parallel draft의 약점은 position들이 서로를 보지 못한다는 점입니다. 각 position이 자기 앞 token이 실제로 무엇으로 뽑혔는지 모른 채 독립적으로 예측하기 때문에, target이 여러 continuation 사이에서 고민하는 구간에서는 앞뒤가 맞지 않는 조합이 나와 acceptance가 떨어집니다. DSpark는 여기에 가벼운 sequential 보정을 얹어서 직전 token에 따라 각 position의 logits를 조정합니다. 보정 비용이 embedding lookup 수준이라 $c$ 는 거의 그대로인데, block 안의 일관성이 복원되면서 $\alpha$ 가 올라갑니다.

마지막 조각은 scheduling입니다. DSpark는 position마다 draft가 거기까지 살아남을 확률을 함께 예측하고, batch 안의 모든 요청에 대해 이 확률이 높은 순서로 verification 예산을 배분합니다. $\gamma$ 가 고정 hyperparameter가 아니라 요청마다, 그리고 load에 따라 정해지는 값이 되는 것입니다. 위에서 본 것처럼 speedup이 operating point에 따라 크게 달라지기 때문에, production에서는 이 조각이 drafter 자체만큼 중요합니다.

정리

speculative decoding은 parameter 세 개와 상한이 있는 방정식 하나로 정리됩니다. 자신의 $\alpha$ 와 $c$ , 그리고 실제로 서빙하는 load를 알고 있다면, 새 논문의 abstract만 읽고도 네 항 중 무엇을 움직이는지 파악해서 코드를 쓰기 전에 이득을 추정할 수 있습니다.

그리고 operating point 없이 인용된 speedup은 결과가 아니라 표의 cell 하나일 뿐입니다.

남은 질문은 $c$ 로 전부 되갚지 않으면서 $\alpha$ 를 올리는 방법입니다. 모든 drafter architecture가 이 질문에 대한 각자의 답이고, 차이는 주로 drafter가 추측을 확정하기 전에 무엇을 볼 수 있느냐에 있습니다.