추측 디코딩과 EAGLE (Speculative Decoding and EAGLE)

프런티어(frontier) 거대 언어 모델(LLM)이 토큰(token) 하나를 생성하려면 수십억 개의 파라미터(parameter) 전체에 대한 순전파(forward pass)가 한 번 필요합니다. 그런데 그 순전파는 엄청나게 과잉으로 설계(over-provisioned)되어 있습니다. 대부분의 경우 훨씬 작은 모델이 다음 3-5개 토큰을 정확히 추측할 수 있고, 큰 모델은 그 추측(guess)을 *검증(verify)*하기만 하면 됩니다. 추측이 맞으면 순전파 한 번의 비용으로 토큰 5개를 얻는 셈입니다. 추측 디코딩(Speculative decoding, Leviathan et al. 2023)은 이를 정확한(exact) 방식으로 만들어 냈고, EAGLE-3(2025)은 검증 한 번당 약 4.5개 토큰까지 채택률(acceptance rate)을 끌어올렸습니다. 출력 분포(output distribution)는 그대로 유지한 채로 4-5배 속도 향상(speedup)을 달성했습니다.

유형: Build 언어: Python (numpy 사용) 선수 지식: Phase 10 Lesson 12 (Inference Optimization), Phase 10 Lesson 04 (Pre-training Mini-GPT) 예상 시간: 약 75분

문제

H100에서 70B 급 모델의 디코딩 처리량(decode throughput)은 보통 초당 40-80 토큰 수준입니다. 토큰 하나를 만들 때마다 HBM에서 모델 가중치(weight) 전체를 읽어 들이는 순전파가 통째로 필요합니다. 출력 결과를 바꾸지 않고 모델을 더 작게 만들 수도 없고, 메모리 한계를 넘어 배치 크기(batch size)를 키울 수도 없습니다. 막다른 길처럼 보입니다. 단, 순전파 한 번에 토큰을 하나보다 더 많이 뽑아내는 길을 찾아낼 수 있다면 이야기가 달라집니다.

자기회귀(autoregressive) 생성은 본질적으로 순차적으로 보입니다. x_{t+1} = sample(p(· | x_{1:t}))이기 때문입니다. 하지만 이 안에는 동시성(concurrency)을 활용할 여지가 있습니다. 값싼 예측기(predictor)가 "다음 4개 토큰은 아마 [a, b, c, d]일 것"이라고 말해 줄 수 있다면, 큰 모델의 순전파 단 한 번으로 다섯 위치를 모두 검증한 뒤 가장 길게 일치하는 접두사(prefix)를 채택(accept)할 수 있습니다.

Leviathan, Kalai, Matias(2023, "Fast Inference from Transformers via Speculative Decoding")는 타깃 모델(target model)의 샘플링 분포(sampling distribution)를 그대로 보존하는 영리한 채택/거절(accept/reject) 규칙을 통해 이것을 정확하게 만들었습니다. 같은 출력 분포를 2-4배 빠르게 얻을 수 있습니다.

개념

두 모델 구성(Two-Model Setup)

• 타깃 모델(Target model) M_p: 실제로 우리가 표본(sample)을 얻고 싶은 크고 느린 고품질 모델입니다. 분포는 p(x)입니다.
• 드래프트 모델(Draft model) M_q: 작고 빠르지만 품질은 떨어지는 모델입니다. 분포는 q(x)이고, 보통 타깃보다 5-30배 작습니다.

각 스텝(step)마다 다음을 수행합니다.

1. 드래프트 모델이 자기회귀 방식으로 K개 토큰을 제안합니다. x_1, x_2, ..., x_K ~ q.
2. 타깃 모델이 K+1개 위치 전체에 대해 순전파 한 번을 병렬로 실행하고, 각 제안된 토큰에 대한 p(x_k)를 계산합니다.
3. 아래의 수정된 거절 샘플링(modified rejection-sampling) 규칙을 사용해 왼쪽에서 오른쪽으로 토큰을 채택/거절합니다. 가장 길게 일치하는 접두사를 채택합니다.
4. 토큰 중 하나라도 거절되면 보정된 분포(corrected distribution)에서 대체 토큰(replacement)을 샘플링하고 거기서 멈춥니다. 전부 채택되면 p(· | x_1...x_K)에서 보너스 토큰(bonus token) 하나를 추가로 샘플링합니다.

드래프트가 타깃과 완전히 일치하면 타깃 순전파 한 번당 K+1개 토큰을 얻습니다. 드래프트가 첫 번째 위치에서 틀리면 한 개의 토큰만 얻습니다.

정확성 규칙(The Exactness Rule)

추측 디코딩은 분포상 p에서 샘플링하는 것과 증명 가능하게 동등(provably equivalent) 합니다. 거절 규칙은 다음과 같습니다.

For each drafted token x_t:
    r ~ Uniform(0, 1)
    if r < p(x_t) / q(x_t):
        accept x_t
    else:
        sample replacement from residual: (p - q)+ / ||(p - q)+||_1
        stop

여기서 (p - q)+는 두 분포의 점별(pointwise) 차이에서 양수 부분만 취한 값입니다. 드래프트와 타깃이 거의 일치하면(p ≈ q) 채택률은 1에 가깝습니다. 두 분포가 어긋날 때는 잔여 분포(residual distribution)가 전체 표본이 여전히 정확히 p를 따르도록 구성됩니다.

그리디(greedy) 경우. 온도(temperature)가 0인 샘플링에서는 argmax(p) == x_t만 확인하면 됩니다. 같으면 채택하고, 다르면 argmax(p)를 출력한 뒤 멈춥니다.

기대 속도 향상(Expected Speedup)

드래프트 모델의 토큰 단위 채택률을 α라고 하면, 타깃 순전파 한 번당 기대되는 토큰 수는 다음과 같습니다.

E[tokens] = (1 - α^{K+1}) / (1 - α)        # K = draft length, α in [0, 1]

α = 0.8, K = 4인 경우 (1 - 0.8^5)/(1 - 0.8) = 3.36으로, 순전파 한 번당 3.36개의 토큰을 얻습니다. 타깃 순전파 한 번의 비용은 대략 cost_q * K + cost_p로, 드래프트 스텝 K번과 타깃 검증 한 번의 합입니다. cost_p >> cost_q * K라면 처리량 측면의 속도 향상 비율은 3.36× / 1 = 3.36×이 됩니다.

여기서 실질적으로 조절 가능한 파라미터는 α 하나뿐이며, 이는 전적으로 드래프트와 타깃 사이의 정합도(draft-target alignment)에 달려 있습니다. 결국 좋은 드래프트가 모든 것을 좌우합니다.

드래프트 학습: 증류(Distillation)

작은 모델을 무작위로 학습해 드래프트로 쓰면 성능이 형편없습니다. 표준적인 방법은 타깃에서 증류하는 것입니다.

1. 작은 아키텍처(architecture)를 고릅니다. 70B 타깃에는 약 1B, 7B 타깃에는 약 500M 정도가 적절합니다.
2. 큰 텍스트 말뭉치(text corpus)에서 타깃 모델을 돌려 다음 토큰 분포(next-token distribution)를 저장해 둡니다.
3. 정답 토큰(ground-truth token)이 아니라 타깃 분포에 대한 KL 발산(KL divergence) 손실로 드래프트를 학습합니다.

그 결과 α는 보통 코드(coding) 작업에서 0.6-0.8, 자연어 대화(natural-language chat)에서 0.7-0.85 정도가 나옵니다. 운영 환경(production)에서는 2-3배 속도 향상이 일반적입니다.

EAGLE: 트리 드래프팅(tree drafting)과 피처 재사용(feature reuse)

Li, Wei, Zhang, Zhang(2024, "EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty")은 표준 추측 디코딩의 두 가지 비효율을 지적했습니다.

1. 드래프트는 K번의 순차적 스텝을 수행하고, 각 스텝마다 전체 스택(full-stack)을 통과합니다. 하지만 드래프트는 가장 최근 검증에서 타깃이 계산한 피처(feature), 즉 히든 스테이트(hidden state)를 재사용할 수 있습니다. 타깃은 이미 풍부한 표현(representation)을 계산해 두었는데도 드래프트가 그것을 처음부터 다시 만들어내고 있는 셈입니다.
2. 드래프트는 일직선의 토큰 열(linear chain)을 출력합니다. 만약 드래프트가 후보들의 트리(tree), 즉 각 노드(node)에 여러 추측이 달린 구조를 출력할 수 있다면, 타깃의 단 한 번의 순전파로 트리 어텐션 마스크(tree attention mask)를 사용해 여러 후보 경로를 병렬 검증하고 가장 긴 채택 분기(accepted branch)를 선택할 수 있습니다.

EAGLE-1의 변화는 다음과 같습니다.

• 드래프트 입력 = 원시 토큰(raw token)이 아니라 위치 t에서 타깃의 최종 히든 스테이트(final hidden state).
• 드래프트 아키텍처 = 별도의 작은 모델이 아니라 트랜스포머 디코더 레이어(transformer decoder layer) 한 개.
• 출력 = 깊이(depth)별 후보 K = 4-8개, 깊이 4-6인 트리.

EAGLE-2(2024)는 동적인 트리 위상(dynamic tree topology)을 추가합니다. 드래프트가 불확실한 부분에서는 트리가 옆으로 넓게 자라고, 확신이 있는 부분에서는 좁게 유지됩니다. 검증 비용을 늘리지 않으면서 실효 채택률 α_effective를 끌어올립니다.

EAGLE-3(Li et al. 2025, "EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test")은 최상위 레이어 피처에 고정되는 의존성(fixed top-layer feature dependency)을 없애고, 새로운 "시험 시점 시뮬레이션 손실(test-time simulation loss)"로 드래프트를 학습합니다. 교사 강요(teacher forcing)된 학습 분포가 아니라 타깃의 시험 시점(test-time) 분포에 맞춰진 출력으로 드래프트를 학습하는 것입니다. 그 결과 채택률은 EAGLE-2의 0.75에서 EAGLE-3의 0.82로 오르고, 검증 한 번당 평균 토큰 수는 3.0에서 4.5로 증가합니다.

트리 어텐션 검증(Tree Attention Verification)

드래프트가 트리를 출력하면, 타깃 모델은 트리 어텐션 마스크를 사용해 단 한 번의 순전파로 이를 검증합니다. 단순한 일직선이 아니라 트리 위상을 인코딩한 인과(causal) 마스크입니다. 각 토큰은 트리에서 자기 조상(ancestor) 노드에만 어텐션을 보냅니다. 검증 패스는 여전히 순전파 한 번, 행렬곱(matmul) 한 번이며, 위상을 표현한 마스크는 KV 캐시(KV cache) 항목 몇 개를 더 쓰는 정도의 추가 비용만 발생합니다.

        root
       /    \
      a      b
     / \    / \
    c  d   e   f

a, b가 서로 경쟁하는 첫 번째 토큰 후보이고 c, d, e, f가 두 번째 토큰 후보라면, 여섯 개 위치가 모두 순전파 한 번으로 검증됩니다. 출력은 채택된 경로(accepted path) 중에서 가장 긴 접두사입니다.

이기는 경우와 그렇지 못한 경우

이기는 경우:

• 예측 가능한 텍스트가 등장하는 채팅(chat)이나 문장 완성(completion). 코드, 일상 영어, 정형화된 출력(structured output)처럼 α가 높은 영역입니다.
• 디코딩 중 GPU 연산 자원이 남아도는 환경(메모리 바운드(memory-bound) 단계). 트리 드래프팅이 남는 FLOP을 활용합니다.

지는 경우 / 이득이 없는 경우:

• 매우 확률적인 출력(highly stochastic output). 높은 온도로 진행되는 창작(creative writing)에서는 α가 1/|vocab|에 가까워집니다.
• 동시성이 매우 높은 배치 서빙(batch serving). 이미 배치가 FLOP을 가득 채우고 있어 트리 검증이 끼어들 여유가 거의 없습니다.
• 매우 작은 타깃 모델. 드래프트가 타깃보다 충분히 작지 않은 경우입니다.

운영 환경의 팀들은 보통 채팅에서 2-3배, 코드 생성에서 3-5배의 실시간 속도 향상(wall-clock speedup)을 보고하며, 창작 글쓰기에서는 이득이 거의 0에 수렴한다고 보고합니다.

직접 만들기

code/main.py는 다음을 포함합니다.

• 정확한 거절 규칙을 구현하고 타깃 분포가 보존되는지 검증하는 참조 구현 speculative_decode(target, draft, prompt, K, temperature). 평이한 타깃 샘플링과 비교했을 때 경험적 KL이 0.01 미만이어야 합니다.
• top-p 분기를 사용해 깊이 K인 트리를 만드는 EAGLE 스타일 트리 드래프터(drafter).
• 검증기에 필요한 올바른 인과 패턴을 만드는 트리 어텐션 마스크 생성기(builder).
• 작은 언어 모델(LM)에서 두 방식을 함께 돌리는 채택률 측정 하니스(harness). GPT-2-medium 타깃에서 GPT-2-small 드래프트를 증류합니다.

def speculative_step(p_target, q_draft, K, temperature=1.0):
    """추측 디코딩 한 라운드. 채택된 토큰 리스트를 반환합니다."""
    # 1. K개 토큰을 드래프트합니다.
    draft_tokens = []
    q_probs = []
    state = draft_state_init()
    for _ in range(K):
        probs = softmax(q_draft(state) / temperature)
        t = np.random.choice(len(probs), p=probs)
        draft_tokens.append(t)
        q_probs.append(probs[t])
        state = draft_step(state, t)

    # 2. 타깃이 드래프트된 모든 위치 + 추가 한 개 위치에서 p를 계산합니다.
    p_probs_all = target_forward_batched(p_target, draft_tokens, temperature)

    # 3. 왼쪽에서 오른쪽으로 채택/거절합니다.
    accepted = []
    for k, tok in enumerate(draft_tokens):
        r = np.random.uniform()
        if r < p_probs_all[k][tok] / q_probs[k]:
            accepted.append(tok)
        else:
            residual = np.maximum(p_probs_all[k] - q_probs[k], 0)
            residual /= residual.sum()
            accepted.append(np.random.choice(len(residual), p=residual))
            return accepted
    # 4. K개가 모두 채택되면 타깃에서 보너스 토큰을 샘플링합니다.
    accepted.append(np.random.choice(len(p_probs_all[-1]), p=p_probs_all[-1]))
    return accepted

사용해보기

• vLLM과 SGLang은 추측 디코딩을 1급(first-class) 기능으로 지원합니다. 플래그(flag)는 --speculative_model, --num_speculative_tokens이며, EAGLE-2/3은 --spec_decoding_algorithm eagle 플래그로 사용할 수 있습니다.
• NVIDIA TensorRT-LLM은 Medusa와 EAGLE 트리를 네이티브(native)로 지원합니다.
• 참고용 드래프트 모델(Reference draft models): Qwen/Qwen3-0.6B-spec(Qwen3-32B용 드래프트), meta-llama/Llama-3.2-1B-Instruct-spec(70B용 드래프트).
• Medusa 헤드(Medusa heads)(Cai et al. 2024, "Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads"): 별도의 드래프트 모델을 두는 대신 타깃 모델 자체에 K개의 병렬 예측 헤드(parallel prediction head)를 붙입니다. 배포는 더 단순하지만, 채택률은 EAGLE보다 약간 낮습니다.

산출물 만들기

이 강의는 outputs/skill-speculative-tuning.md를 만듭니다. 타깃 모델의 작업 부하(workload)를 프로파일링한 뒤 드래프트 모델, K(드래프트 길이), 트리 폭(tree width), 온도, 그리고 평이한 디코딩으로 되돌아갈(fall back) 시점을 결정하는 스킬(skill)입니다.

연습문제

1. 쉬움 — 정확한 거절 규칙을 구현하고 경험적으로 검증합니다. speculative_decode와 평이한 타깃 샘플링으로 각각 1만 개의 표본을 생성하고, 두 출력 분포 사이의 전변동 거리(TV distance)를 계산합니다. 0.01 미만이어야 합니다.

2. 쉬움 — 속도 향상 공식을 계산합니다. α와 K를 고정한 채 타깃 순전파 한 번당 기대 토큰 수를 그래프로 그립니다. α ∈ {0.5, 0.7, 0.9}에 대해 최적의 K를 찾습니다.

3. 중간 — 작은 드래프트를 학습합니다. 124M 파라미터의 GPT-2 타깃을 가져와 KL 손실로 1억 토큰 분량의 데이터에서 30M 파라미터의 GPT-2 드래프트를 증류합니다. 검증용으로 남겨둔 텍스트에서 α를 측정합니다. 기댓값은 0.6-0.7입니다.

4. 어려움 — EAGLE 스타일 트리 드래프팅을 구현합니다. 일직선 체인 대신, 드래프트가 깊이마다 상위 3개 분기를 출력하게 합니다. 트리 어텐션 마스크를 만들고, 타깃이 가장 긴 정답 분기를 채택하는지 확인합니다.

5. 어려움 — 실패 모드를 측정합니다. temperature=1.5(높은 확률성)로 추측 디코딩을 실행합니다. α가 무너지고 드래프트 오버헤드(overhead) 때문에 평이한 디코딩보다 오히려 느려지는 것을 보입니다.

핵심 용어

더 읽을거리

• Leviathan, Kalai, Matias, 2023 — "Fast Inference from Transformers via Speculative Decoding" — 정확한 거절 규칙과 이론적 속도 향상 분석을 다룹니다.
• Chen, Borgeaud, Irving et al., 2023 — "Accelerating Large Language Model Decoding with Speculative Sampling" — DeepMind에서 동시기에 발표한 추측 샘플링 논문입니다.
• Cai, Li, Geng, Wang, Wang, Zhu, Dao, 2024 — "Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads" — 드래프트 모델의 대안인 병렬 헤드 접근입니다.
• Li, Wei, Zhang, Zhang, 2024 — "EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty" — 피처 재사용과 트리 드래프팅을 제안합니다.
• Li et al., 2024 — "EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees" — 동적 트리 위상을 도입합니다.
• Li et al., 2025 — "EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test" — 학습 시점과 시험 시점 분포의 일치를 다룹니다.
• Fu, Haotian, Peng et al., 2024 — "Break the Sequential Dependency of LLM Inference Using Lookahead Decoding" — 드래프트 모델이 필요 없는 대안으로 자코비/룩어헤드 디코딩(Jacobi/lookahead decoding)을 제시합니다.