Speculative Speculative Decoding

이 논문은 검증 과정 중 드래프트 모델이 검증 결과를 미리 예측하여 준비함으로써 기존 스펙큘레이티브 디코딩의 순차적 병목 현상을 해결하고, 이를 통해 오픈소스 추론 엔진 대비 최대 5 배, 최적화된 스펙큘레이티브 디코딩 대비 최대 2 배의 추론 속도를 달성하는 '사구아로 (Saguaro)' 알고리즘을 제안합니다.

핵심

🍽️ 배경: 왜 AI 는 느릴까요? (기존 방식의 문제)

지금까지 AI 가 글을 쓸 때는 **'한 번에 한 단어씩'**만 썼습니다.

• 주 요리사 (Target Model): 아주 똑똑하지만 느립니다. "다음 단어는 뭐가 좋을까?"라고 고민해서 한 단어를 내면, 그걸 확인하고 다시 다음 단어를 고민합니다.
• 문제: 요리사가 다음 단어를 고르는 동안, 모든 주방이 멈춰서 기다려야 합니다. (순차적 작업의 병목 현상)

🚀 기존 해결책: '추측적 디코딩 (Speculative Decoding)'

이 문제를 해결하기 위해 **'도우미 요리사 (Draft Model)'**를 고용했습니다. 도우미는 느린 주 요리사보다 훨씬 빠릅니다.

1. 도우미: "다음 단어는 아마 '사과'일 거야! 아니, '바나나'일지도!" 하고 3~4 개를 미리 추측해서 준비합니다.
2. 주 요리사: 도우미가 준비한 단어들을 한 번에 확인합니다. "오, '사과'와 '바나나'는 맞네. 근데 그다음은 '오렌지'가 더 맞겠다."
3. 결과: 도우미가 맞춘 단어들은 바로 출력하고, 틀린 건 버립니다.

하지만 여기서도 문제가 생깁니다.
도우미가 다음 단어를 추측하려면, 주 요리사가 지금 단어를 확인하고 끝날 때까지 기다려야 합니다. 도우미는 "주 요리사가 확인 끝날 때까지 나는 쉬어야 해"라고 합니다. 즉, 도우미가 일을 할 때 주 요리사가 일하고, 주 요리사가 일할 때 도우미가 기다리는 비동기 (동시 작업) 가 안 되는 것입니다.

---

🌵 새로운 해결책: '사구아로 (SSD)'의 등장

이 논문은 **"도우미가 기다리는 시간을 아예 없애자!"**고 제안합니다. 바로 **SSD(Speculative Speculative Decoding)**입니다.

🌵 사구아로 (선인장) 의 비유

사구아로 선인장은 가시마다 다른 열매를 맺을 수 있습니다. 이 아이디어를 적용했습니다.

1. 주 요리사가 확인하는 동안, 도우미는 '모든 가능성'을 미리 준비합니다.

   • 주 요리사가 "사과"를 맞췄을 때, 도우미는 "그럼 그다음은 '바나나'일 거야"라고 미리 준비해 둡니다.
   • 주 요리사가 "바나나"를 맞췀을 때, 도우미는 "그럼 그다음은 '오렌지'일 거야"라고 미리 준비해 둡니다.
   • 핵심: 도우미는 주 요리사가 어떤 단어를 맞출지 모든 경우의 수를 미리 계산해 준비해 둡니다.

2. 결과가 나오면 즉시 전달!

   • 주 요리사가 확인을 끝내고 "자, 이번엔 '사과'가 맞았어!"라고 말하면, 도우미는 **"아! 내가 미리 준비해 둔 '바나나'가 있네!"**라고 바로 건네줍니다.
   • 도우미가 다시 계산할 필요가 없습니다. 0 초에 결과를 냅니다.

3. 만약 예상과 다르다면?

   • 주 요리사가 "아니, 이번엔 '포도'였어!"라고 하면, 도우미가 준비한 '바나나'나 '오렌지'는 쓸모가 없습니다.
   • 이때는 도우미가 당황하지 않고, **즉시 (Just-in-time)**로 '포도' 다음 단어를 계산해서 보내면 됩니다. (이걸 '패백 (Fallback)'이라고 합니다.)

---

🎯 사구아로 (Saguaro) 알고리즘의 3 가지 핵심 전략

이론만 좋으면 안 되고, 실제로 잘 작동하게 하려면 3 가지 문제를 해결해야 했습니다.

1. 어떤 경우를 미리 준비할까? (캐시 최적화)

   • 모든 경우를 다 준비할 수는 없습니다 (메모리 부족).
   • 해결: 통계적으로 "가장 자주 나오는 경우"에 집중해서 미리 준비합니다. 마치 식당에서 "손님이 가장 많이 시키는 메뉴"를 미리 준비해 두는 것과 같습니다. (기하급수적 분포 활용)

2. 도우미의 추측을 어떻게 믿을 수 있을까? (샘플링 전략)

   • 도우미가 "바나나"라고 미리 준비했는데, 주 요리사가 "바나나"를 고를 확률이 낮으면 소용없습니다.
   • 해결: 도우미가 추측할 때, 주 요리사가 좋아할 만한 단어의 확률을 살짝 조작해서, 주 요리사가 그 단어를 고를 확률을 높입니다. (도우미가 주 요리사의 취향을 미리 맞춰주는 것)

3. 예상과 달랐을 때 어떻게 할까? (백업 전략)

   • 손님이 많을 때 (배치 크기 증가) 는 예상과 다른 경우가 더 자주 발생합니다.
   • 해결: 손님이 적을 때는 똑똑한 도우미가 미리 준비하고, 손님이 너무 많으면 아주 빠르지만 똑똑하지 않은 도우미가 즉석에서 계산하게 합니다. 상황에 따라 도우미를 바꿔 쓰는 것입니다.

---

🏆 결과: 얼마나 빨라졌나요?

이 기술을 적용한 **사구아로 (Saguaro)**는 기존 방식보다 놀라운 속도를 보여줍니다.

• 기존 AI (한 번에 한 단어): 100 점
• 기존 도우미 방식 (추측적 디코딩): 200 점 (약 2 배 빠름)
• 새로운 사구아로 방식 (SSD): 500 점 (약 5 배 빠름!)

특히, 여러 사람이 동시에 요청을 보낼 때 (대용량 배치) 도 더 강력하게 작동하며, 하드웨어 효율도 좋아졌습니다.

💡 요약

이 논문은 **"AI 가 글을 쓸 때, 다음 단어를 고민하는 시간을 아예 없애버리자"**는 아이디어를 제시합니다.
주 요리사가 확인하는 동안, 도우미가 "만약 A 라면 B 를, 만약 C 라면 D 를" 미리 다 준비해 두었다가, 정답이 나오면 즉시 건네주는 방식입니다. 마치 사구아로 선인장처럼 다양한 가지 (경우의 수) 를 미리 키워두었다가, 필요한 열매를 바로 따서 주는 것입니다.

이로 인해 AI 는 훨씬 더 빠르고 자연스럽게 대화를 이어갈 수 있게 되었습니다.

기술 요약

이 논문은 Speculative Speculative Decoding (SSD, 예측적 예측 디코딩) 을 제안하며, 대규모 언어 모델 (LLM) 의 추론 속도를 획기적으로 향상시키는 새로운 프레임워크를 소개합니다. 저자들은 기존 예측 디코딩 (Speculative Decoding, SD) 의 병목 현상인 '직렬 의존성'을 해결하기 위해, 검증 (Verification) 과정이 진행되는 동안에도 예측 (Drafting) 을 병렬로 수행하는 Saguaro라는 최적화 알고리즘을 개발했습니다.

다음은 논문의 주요 내용을 기술적으로 요약한 것입니다.

---

1. 문제 정의 (Problem)

• 기존 SD 의 한계: 표준 예측 디코딩 (Speculative Decoding) 은 빠른 '드래프트 모델 (Draft Model)'이 토큰을 예측하고, 느린 '타겟 모델 (Target Model)'이 이를 병렬로 검증하는 방식입니다. 그러나 이 방식은 검증이 완료될 때까지 다음 예측을 시작할 수 없는 직렬 의존성 (Sequential Dependence) 이 존재합니다. 즉, 타겟 모델이 검증하는 동안 드래프트 모델은 유휴 상태 (Idle) 로 대기해야 하므로 하드웨어의 병렬 계산 능력을 완전히 활용하지 못합니다.
• 목표: 예측 (Drafting) 과 검증 (Verification) 사이의 직렬 의존성을 제거하여, 두 작업을 완전히 병렬화하고 대기 시간을 최소화하는 것입니다.

2. 방법론: SSD 프레임워크 및 Saguaro 알고리즘

저자들은 Speculative Speculative Decoding (SSD) 을 제안합니다. 이는 검증이 진행되는 동안 드래프트 모델이 가능한 모든 검증 결과 (Verification Outcomes) 를 미리 예측하고, 이에 대한 예측 토큰 시퀀스를 준비해 두는 방식입니다.

핵심 메커니즘

1. 비동기 병렬 실행: 타겟 모델이 현재 라운드의 토큰을 검증하는 동안, 별도의 하드웨어 (드래프트 GPU) 에서 다음 라운드를 위한 예측을 수행합니다.
2. 예측 캐시 (Speculation Cache): 드래프트 모델은 검증 결과 (몇 개의 토큰이 승인될지, 그리고 보너스 토큰은 무엇인지) 의 가능한 경우의 수를 예측합니다. 각 가능한 결과에 대해 미리 토큰 시퀀스를 생성하여 '캐시'에 저장합니다.
3. 캐시 히트 (Cache Hit): 실제 검증 결과가 캐시에 미리 준비된 결과 중 하나와 일치하면, 즉시 해당 토큰을 반환하여 드래프트 오버헤드를 완전히 제거합니다.
4. 캐시 미스 (Cache Miss) 처리: 만약 예상치 못한 결과가 나오면, 백업 드래프트 모델 (Backup Speculator) 을 사용하여 즉시 대응하거나 기존 SD 방식대로 동기화하여 손실 없는 (Lossless) 디코딩을 보장합니다.

Saguaro 의 3 가지 핵심 최적화

SSD 의 성능을 극대화하기 위해 저자들은 세 가지 주요 과제를 해결하는 Saguaro 알고리즘을 제안했습니다.

• 1. 검증 결과 예측 및 캐시 구성 (Geometric Fan-Out):

  • 가능한 모든 검증 결과 (약 $(K+1)V$ 개) 를 모두 예측하는 것은 불가능합니다. 따라서 제한된 계산 예산 내에서 가장 확률이 높은 결과들을 선택해야 합니다.
  • Theorem 12에 기반하여, 검증된 시퀀스 길이가 기하급수적으로 감소하는 분포를 따름을 관찰하고, 이를 반영한 기하급수적 팬아웃 (Geometric Fan-Out) 전략을 도입했습니다. 즉, 긴 시퀀스가 승인될 확률이 낮으므로, 짧은 시퀀스 길이에 더 많은 보너스 토큰 후보를 할당하여 캐시 히트율을 극대화합니다.

• 2. Saguaro 샘플링 (잔여 분포 제어):

  • 보너스 토큰은 주로 '잔여 분포 (Residual Distribution, $r(\cdot) \propto \max(p_{target} - p_{draft}, 0)$)'에서 샘플링됩니다. 이는 예측하기 어렵습니다.
  • Saguaro Sampling은 드래프트 모델의 확률 분포를 의도적으로 왜곡하여 (캐시에 있는 토큰들의 확률을 낮춤), 결과적으로 잔여 분포가 캐시에 있는 토큰들에 집중되도록 만듭니다.
  • 이는 캐시 히트율 (Cache Hit Rate) 과 수용율 (Acceptance Rate) 사이의 트레이드오프를 조절하는 하이퍼파라미터 ($C$) 를 통해 최적화합니다.

• 3. 캐시 미스 처리 전략 (배치 크기 기반 적응):

  • Theorem 17에 따르면, 최적의 백업 전략은 배치 크기 (Batch Size) 에 따라 달라집니다.
  • 작은 배치: 드래프트 모델이 검증보다 느릴 수 있으므로, 고품질 (느리지만 정확한) 드래프트 모델을 백업으로 사용하여 지연을 최소화합니다.
  • 큰 배치: 캐시 미스가 빈번하게 발생하면 전체 배치가 백업 모델의 지연에 막히게 됩니다. 이때는 저지연 (Fast) 백업 모델 (예: 랜덤 토큰 또는 매우 빠른 비신경망 모델) 을 사용하여 전체 처리량을 유지합니다.

3. 주요 결과 (Results)

실험은 Llama-3.1-70B (타겟) 와 Llama-3.2-1B (드래프트) 모델을 사용하여 H100 GPU 환경에서 수행되었습니다.

• 속도 향상:
  • 최적화된 기존 예측 디코딩 (SD) 대비 최대 2 배 빠른 추론 속도를 달성했습니다.
  • 표준 자기회귀 (Autoregressive, AR) 디코딩 대비 최대 5 배 빠른 속도를 기록했습니다.
  • 평균적으로 4.7 배 (Llama-3) 의 속도 향상을 보였습니다.
• 처리량 - 지연 시간 파레토 프론티어 (Pareto Frontier):
  • SSD 는 지연 시간 (Latency) 을 줄이는 동시에 처리량 (Throughput) 을 증가시켜, 기존 방법들이 도달하지 못했던 새로운 파레토 프론티어를 형성했습니다.
  • 특히 작은 배치 크기에서 가장 큰 이점을 보였으나, 큰 배치에서도 Saguaro 의 적응형 백업 전략 덕분에 SD 보다 20% 이상 우세했습니다.
• 데이터셋: 수학 (GSM8k), 코드 (HumanEval), 대화 (Alpaca, UltraFeedback) 등 다양한 도메인에서 일관된 성능 향상을 입증했습니다.

4. 의의 및 결론 (Significance)

• 병렬화의 새로운 차원: 기존 예측 디코딩이 '토큰 단위'의 병렬화를 시도했다면, SSD 는 '검증 과정'과 '예측 과정' 자체를 병렬화하여 하드웨어의 유휴 자원을 극도로 활용합니다.
• 하드웨어 효율성: 추가적인 GPU (드래프트 모델용) 를 사용하지만, 전체적인 지연 시간 감소와 처리량 증가로 인해 장치당 효율성이 오히려 향상됩니다.
• 확장성: Saguaro 는 EAGLE, 토큰 트리 (Token Tree) 기반 예측 디코딩 등 다른 최신 기법들과 결합하여 추가적인 성능 향상을 이룰 수 있는 유연한 프레임워크를 제공합니다.
• 실용성: 오픈소스 추론 엔진 (vLLM, SGLang) 대비 압도적인 성능 우위를 보여주어, 실제 LLM 서비스의 지연 시간 단축에 혁신적인 기여를 할 것으로 기대됩니다.

요약하자면, 이 논문은 SSD라는 새로운 패러다임을 통해 LLM 추론의 병목 현상을 해결하고, Saguaro 알고리즘을 통해 이론적 최적화와 실용적 성능을 모두 달성한 획기적인 연구입니다.