추측 디코딩 — 초안 작성, 검증, 반복

자기회귀 디코딩(Autoregressive decoding)은 직렬(serial)입니다. 각 토큰(token)은 이전 토큰을 기다립니다. 추측 디코딩(Speculative decoding)은 이 사슬(chain)을 끊습니다. 저렴한 모델이 N개의 토큰을 초안 작성(draft)하고, 비싼 모델이 한 번의 순전파(forward pass)로 N개를 모두 검증(verify)합니다. 초안이 맞으면 큰 모델의 순전파 한 번으로 N번 생성한 효과를 얻습니다.

유형: Build 언어: Python 선수 지식: Phase 7 · 07 (GPT — 인과적 언어모델링), Phase 7 · 12 (KV 캐시, Flash Attention과 추론 최적화) 예상 시간: 약 60분

문제

70B 대형 언어 모델(LLM)이 H100에서 토큰 하나를 샘플링(sampling)하는 데 약 30ms가 걸린다고 합시다. 3B 초안 모델(draft model)은 약 3ms가 걸립니다. 3B 모델이 5개 토큰을 미리 초안 작성하고 70B 모델을 한 번만 실행해 5개를 모두 검증하면, 최대 5개의 수락된 토큰(accepted token)에 5×3 + 30 = 45 ms를 씁니다. 단순 직선 생성(straight-line generation)의 5×30 = 150 ms보다 훨씬 빠릅니다. 이것이 추측 디코딩의 핵심 제안입니다. 초안 모델을 위한 GPU 메모리를 조금 더 쓰고, 디코딩 지연 시간(decode latency)을 2-4배 낮춥니다.

중요한 요령은 분포(distribution)를 보존해야 한다는 점입니다. Leviathan et al. (2023)과 Chen et al.이 동시에 소개한 추측 샘플링(Speculative sampling)은 출력 시퀀스(output sequence)가 큰 모델이 혼자 생성했을 때와 동일한 분포(identically distributed) 를 따르도록 보장합니다. 품질 절충(quality tradeoff)은 없습니다. 더 빠를 뿐입니다.

2026년 추론(inference)에는 네 가지 초안-검증기(draft-verifier) 계열이 지배적입니다.

1. 기본 추측 방식(Vanilla speculative, Leviathan 2023). 별도 초안 모델(예: Llama 3 1B)과 검증기(verifier, 예: Llama 3 70B)를 사용합니다.
2. 메두사(Medusa, Cai 2024). 검증기 위에 여러 디코딩 헤드(decoding head)를 달아 t+1..t+k 위치를 병렬로 예측합니다. 별도 초안 모델이 없습니다.
3. EAGLE 계열(EAGLE family, Li 2024, 2025). 검증기의 은닉 상태(hidden state)를 재사용하는 경량 초안 모델입니다. 기본 추측 방식보다 수락률(acceptance rate)이 가깝고, 일반적으로 3-4배 가속을 보입니다.
4. 룩어헤드 디코딩(Lookahead decoding, Fu 2024). 야코비 반복(Jacobi iteration)을 사용하는 자기 추측(self-speculation) 방식입니다. 초안 모델이 전혀 필요 없습니다. 널리 쓰이는 주류 방식은 아니지만 의존성이 없습니다.

2026년의 프로덕션 추론 스택(production inference stack)은 추측 디코딩을 기본 기능으로 제공합니다. vLLM, TensorRT-LLM, SGLang, llama.cpp는 모두 최소한 기본 추측 방식과 EAGLE-2를 지원합니다.

개념

핵심 알고리즘(Core algorithm)

검증기 M_q와 더 저렴한 초안 모델 M_p가 주어졌다고 합시다.

1. 이미 디코딩된 접두사(prefix) x_1..x_k가 있습니다.
2. 초안 작성(Draft): M_p를 사용해 d_{k+1}, d_{k+2}, ..., d_{k+N}을 자기회귀적으로 제안하고, 초안 확률(draft probability) p_1..p_N을 기록합니다.
3. 병렬 검증(Verify in parallel): M_q를 x_1..x_k, d_{k+1}, ..., d_{k+N}에 한 번 실행해 k+1..k+N+1 위치의 검증기 확률(verifier probability) q_1..q_{N+1}을 얻습니다.
4. 초안 토큰을 왼쪽에서 오른쪽으로 수락/거절(accept/reject): 각 i에 대해 min(1, q_i(d_i) / p_i(d_i)) 확률로 수락합니다.
5. 첫 번째 거절(rejection)이 위치 j에서 발생하면, 잔차 분포(residual distribution) (q_j - p_j)_+를 정규화(normalize)해 t_j를 샘플링합니다. j 뒤의 모든 초안은 버립니다.
6. N개가 모두 수락되면 q_{N+1}에서 보너스 토큰(bonus token) 하나를 더 샘플링합니다.

잔차 분포 요령이 출력 분포를 정확히 검증기와 같게 유지하는 수학적 통찰입니다.

속도 향상을 결정하는 것(What determines speedup)

α를 초안 토큰별 기대 수락률(expected acceptance rate), c를 초안-검증기 비용 비율(draft-to-verifier cost ratio)이라고 합시다. 단계마다 다음 차이가 생깁니다.

• 순진한 생성(naive generation)은 토큰마다 큰 모델 호출(big-model call) 하나가 필요합니다.
• 추측 생성(speculative generation)은 α가 높을 때 검증기 호출 하나로 (1 - α^{N+1}) / (1 - α) ≈ 1/(1-α)개의 토큰을 생성합니다.

경험 법칙(rule of thumb)으로 α = 0.75, N = 5라면 큰 모델 호출이 약 3배 줄어듭니다. 초안 비용은 5번의 저렴한 호출입니다. 전체 벽시계 시간(wall-clock)은 약 2.5배 줄어듭니다.

α는 다음 요인에 따라 달라집니다.

• 초안 모델이 검증기를 얼마나 잘 근사(approximate)하는지. 같은 계열 / 같은 학습 데이터는 α를 크게 높입니다.
• 디코딩 전략(decoding strategy). 탐욕적 초안(greedy draft)과 탐욕적 검증기(greedy verifier)는 α가 높습니다. 온도 샘플링(temperature sampling)은 맞추기 더 어렵고 수락률이 떨어집니다.
• 작업 유형(task type). 코드(code)와 구조화 출력(structured output)은 예측 가능하므로 더 많이 수락됩니다. 자유 형식 창작 글쓰기(free-form creative writing)는 덜 수락됩니다.

메두사(Medusa) — 초안 모델 없는 초안

메두사는 초안 모델을 검증기의 추가 출력 헤드(extra output head)로 대체합니다. 위치 t에서 다음과 같은 구조를 둡니다.

공유 몸통(shared trunk) -> 은닉 상태(hidden) h_t
    ├── head_0: t+1 위치의 토큰 예측 (표준 LM head)
    ├── head_1: t+2 위치의 토큰 예측
    ├── head_2: t+3 위치의 토큰 예측
    ├── head_3: t+4 위치의 토큰 예측

각 헤드는 자기만의 로짓(logits)을 출력합니다. 추론에서는 각 헤드에서 후보 시퀀스(candidate sequence)를 샘플링하고, 모든 후보 이어쓰기(candidate continuation)를 한 번에 고려하는 트리 어텐션(tree-attention) 방식으로 한 번의 순전파에서 검증합니다.

장점은 두 번째 모델이 필요 없다는 것입니다. 단점은 학습 가능한 파라미터(trainable parameter)가 늘고, 약 10억 토큰 규모의 지도 미세조정(supervised fine-tuning) 단계가 필요하며, 좋은 초안 모델을 쓰는 기본 추측 방식보다 수락률이 조금 낮을 수 있다는 점입니다.

EAGLE — 은닉 상태를 재사용하는 더 나은 초안

EAGLE-1/2/3(Li et al., 2024-2025)는 초안 모델을 보통 1개 층의 작은 트랜스포머(tiny transformer)로 만들고, 검증기의 마지막 층 은닉 상태(last-layer hidden state)를 입력으로 받게 합니다. 초안 모델이 검증기의 특징 표현(feature representation)을 보기 때문에, 예측이 검증기의 출력 분포(output distribution)와 강하게 상관(correlate)됩니다. 수락률은 기본 방식의 약 0.6에서 0.85 이상으로 올라갈 수 있습니다.

EAGLE-3(2025)는 후보 이어쓰기에 대한 트리 탐색(tree search)을 추가했습니다. vLLM과 SGLang은 Llama 3/4와 Qwen 3에서 EAGLE-2/3를 기본 추측 경로(default spec pathway)로 제공합니다.

KV 캐시 처리(KV cache dance)

검증은 N개의 초안 토큰을 검증기에 한 번에 넣습니다. 그러면 검증기의 KV 캐시(KV cache)가 N개 엔트리(entry)만큼 늘어납니다. 일부 초안이 거절되면 캐시를 수락된 접두사 길이(accepted prefix length)로 되돌려야 합니다.

프로덕션 구현(vLLM의 --speculative-model, TensorRT-LLM의 LookaheadDecoder)은 스크래치 KV 버퍼(scratch KV buffer)로 이를 처리합니다. 먼저 쓰고(write), 수락이 확정되면 커밋(commit)합니다. 개념적으로 어렵지는 않지만 구현은 꽤 까다롭습니다.

직접 만들기

code/main.py에서는 핵심 추측 샘플링 알고리즘(core speculative-sampling algorithm)을 구현합니다. 거절 단계(rejection step)와 잔차 분포를 포함합니다.

• "큰 모델(big model)"은 손으로 작성한 분포 위의 결정적 소프트맥스(deterministic-softmax)입니다. 이를 통해 수락 수학을 해석적으로 확인할 수 있습니다.
• "초안 모델(draft model)"은 큰 모델 분포를 교란(perturbation)한 것입니다.
• 수락/거절 루프(acceptance / rejection loop)가 직접 샘플링(direct sampling)과 같은 주변 분포(marginal distribution)를 만드는지 확인합니다.

Step 1: 거절 단계(Rejection step)

def accept_or_reject(q_prob, p_prob, draft_token, u):
    ratio = q_prob / p_prob if p_prob > 0 else float("inf")
    return u < min(1.0, ratio)

u는 균등 난수(uniform random number)입니다. q_prob은 초안 토큰(drafted token)에 대한 검증기 확률이고, p_prob은 초안 모델의 확률입니다. Leviathan 정리(Leviathan theorem)는 이 베르누이 결정(Bernoulli decision)과 거절 시 잔차 샘플링(residual sampling)이 검증기의 분포를 정확히 보존한다고 말합니다.

Step 2: 잔차 분포(Residual distribution)

def residual_dist(q, p):
    raw = [max(0.0, qi - pi) for qi, pi in zip(q, p)]
    s = sum(raw)
    return [r / s for r in raw]

q에서 p를 원소별(element-wise)로 빼고, 음수는 0으로 잘라낸(clamp) 뒤 다시 정규화(renormalize)합니다. 거절이 발생하면 이 분포에서 샘플링합니다.

Step 3: 한 번의 추측 단계(One speculative step)

def spec_step(prefix, q_model, p_model, N, rng):
    drafts = []
    p_probs = []
    ctx = list(prefix)
    for _ in range(N):
        p_dist = p_model(ctx)
        d = sample(p_dist, rng)
        drafts.append(d)
        p_probs.append(p_dist[d])
        ctx.append(d)

    q_dists = [q_model(prefix + drafts[:i]) for i in range(N + 1)]

    for i, d in enumerate(drafts):
        u = rng.random()
        q_prob = q_dists[i][d]
        p_prob = p_probs[i]
        if u < min(1.0, q_prob / p_prob if p_prob > 0 else float("inf")):
            prefix = prefix + [d]
        else:
            res = residual_dist(q_dists[i], p_model(prefix))
            prefix = prefix + [sample(res, rng)]
            return prefix
    prefix = prefix + [sample(q_dists[N], rng)]
    return prefix

초안 5개가 모두 수락되면 보너스 토큰 1개까지 더해 검증기 순전파 한 번으로 토큰 6개를 만든 셈입니다. 현재 code/main.py는 학습용 단순화를 위해 q와 p가 호출 동안 고정된 버전도 함께 보여줍니다.

Step 4: 수락률 측정(Measure acceptance rate)

초안 품질(draft quality) 수준을 바꿔 가며 추측 단계를 10,000번 실행합니다. 초안과 검증기 사이의 KL 발산(KL divergence)이 커질수록 수락률이 떨어지는 단조 관계(monotone relationship)를 볼 수 있어야 합니다.

Step 5: 분포 동등성 검증(Verify distribution equivalence)

경험적으로는 추측 루프가 만든 토큰 히스토그램(histogram)과 검증기에서 직접 샘플링한 히스토그램을 비교합니다. 카이제곱 검정(chi-square test)이 샘플링 오차(sampling error) 범위 안에 있으면 Leviathan 정리를 실제로 확인한 것입니다.

사용해보기

프로덕션 예시입니다.

# EAGLE을 사용하는 vLLM
vllm serve meta-llama/Llama-3.1-70B-Instruct \
    --speculative-model /models/llama-3.1-eagle-70b \
    --speculative-draft-tensor-parallel-size 1 \
    --num-speculative-tokens 5

# 기본 초안 모델을 사용하는 vLLM
vllm serve meta-llama/Llama-3.1-70B-Instruct \
    --speculative-model meta-llama/Llama-3.2-1B-Instruct \
    --num-speculative-tokens 5

2026년 중반 기준 TensorRT-LLM은 가장 빠른 메두사 경로(Medusa path)를 제공합니다. faster-whisper는 작은 초안 모델을 사용해 Whisper-large의 추측 디코딩을 감쌉니다.

초안 고르기(Picking a draft):

추측 디코딩을 쓰지 말아야 하는 경우(When NOT to spec-decode):

• 1-5개 토큰만 생성하는 단일 시퀀스(single-sequence generation). 오버헤드(overhead)가 지배합니다.
• 매우 창의적이거나 높은 온도(high-temperature) 샘플링. α가 떨어집니다.
• 메모리가 제한된 배포(memory-constrained deployment). 초안 모델이 VRAM을 추가로 사용합니다.

산출물 만들기

outputs/skill-spec-decode-picker.md를 봅니다. 이 스킬(skill)은 새로운 추론 워크로드(inference workload)에 맞는 추측 디코딩 전략, 즉 기본 방식 / 메두사 / EAGLE / 룩어헤드와 조정 파라미터(tuning parameter)인 N, 초안 온도(draft temperature)를 고릅니다.

연습문제

1. 쉬움. code/main.py를 실행합니다. 50,000개 토큰에서 추측 토큰 분포가 검증기의 직접 샘플링 분포와 카이제곱 p값 p > 0.05 수준으로 맞는지 확인합니다.
2. 중간. α = 0.5, 0.7, 0.85에 대해 N에 따른 속도 향상, 즉 큰 모델 순전파당 토큰 수(tokens per big-model forward)를 그립니다. 각 α에서 최적의 N을 찾습니다. 힌트: 검증 호출당 기대 토큰 수는 (1 - α^{N+1}) / (1 - α)입니다.
3. 어려움. Lesson 14의 Capstone GPT에 t+2, t+3, t+4를 예측하는 추가 LM 헤드(extra LM head) 3개를 달아 작은 메두사(tiny Medusa)를 구현합니다. tinyshakespeare로 공동 다중 헤드 손실(joint multi-head loss)을 사용해 학습하고, 같은 모델을 잘라 만든 기본 초안(vanilla draft)과 수락률을 비교합니다.
4. 어려움. 롤백(rollback)을 구현합니다. 10개 토큰 접두사 KV 캐시에서 5개의 초안 토큰을 넣고, 위치 3에서 거절이 발생한다고 시뮬레이션합니다. 다음 반복에서 캐시 읽기(cache read)가 "접두사 + 처음 2개의 수락된 초안"과 정확히 일치하는지 확인합니다.

핵심 용어

더 읽을거리

• Leviathan, Kalman, Matias (2023). Fast Inference from Transformers via Speculative Decoding - 핵심 알고리즘과 동등성 정리(equivalence theorem)를 다룹니다.
• Chen et al. (2023). Accelerating Large Language Model Decoding with Speculative Sampling - 동시에 제안된 접근이며, 베르누이 거절(Bernoulli-rejection) 증명이 깔끔합니다.
• Cai et al. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads - 메두사 논문이며 트리 어텐션 검증(tree-attention verification)을 다룹니다.
• Li et al. (2024). EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty - EAGLE-1 논문이며 은닉 상태 조건부 초안(hidden-state-conditioned draft)을 다룹니다.
• Li et al. (2024). EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees - EAGLE-2 논문이며 동적 트리 깊이(dynamic tree depth)를 다룹니다.
• Li et al. (2025). EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test - EAGLE-3 논문입니다.
• Fu et al. (2024). Break the Sequential Dependency of LLM Inference Using Lookahead Decoding - 초안 모델이 없는 룩어헤드 접근입니다.
• vLLM docs — Speculative Decoding - 네 가지 전략이 연결된 대표적인 프로덕션 참고 문서입니다.
• SafeAILab / EAGLE reference implementation - EAGLE-1/2/3의 참조 구현(reference implementation)입니다.