초안 작성은 줄이고 검색은 늘리기: Speculative Decoding을 위한 하이브리드 트리 구축

Speculative decoding (SD, 추측적 디코딩)은 초안 작성 후 검증(draft-then-verify) 패러다임을 활용하여 대규모 언어 모델 (LLM)의 추론 속도를 가속화합니다. 수락률 (acceptance rate)을 극대화하기 위해 최근의 방법들은 확장된 초안 트리 (draft trees)를 구축하지만, 이는 불행히도 종단 간 (end-to-end) 속도 향상의 병목 현상이 되는 심각한 VRAM 대역폭 및 연산 오버헤드를 발생시킵니다. 동적 깊이 가지치기 (dynamic-depth pruning)를 통해 미미한 브랜치들을 제거함으로써 이러한 지연 시간을 줄일 수 있지만, 이는 잠재적으로 유효한 후보들까지 버리게 되어 수락률이 밀집 트리 (dense trees)의 상한선에 도달하는 것을 방해합니다.

본 논문에서 우리는 자원 할당에서의 결정적인 기회를 식별했습니다: 밀집된 초안 작성에서 가지치기가 적용된 초안 작성으로 전환되면 상당한 연산 예산 (computational budget)이 확보됩니다. 이러한 파레토 트레이드오프 (Pareto tradeoff)를 깨기 위해, 우리는 가지치기 (pruning)와 검색 (retrieval)을 상호 보완적인 작업으로 결합하는 보상 프레임워크인 Graft를 소개합니다. 가지치기는 검색을 위한 충분한 예산을 제공하며, 검색은 가지치기로 인해 발생하는 커버리지 손실을 보상하고 수락된 길이를 회복합니다. 순차적인 '가지치기 후 접목 (prune-then-graft)' 메커니즘을 채택함으로써, Graft는 예측력이 높은 검색된 토큰들을 가지치기로 인해 생긴 위치에 부착하여, 거의 제로에 가까운 오버헤드로 위상적 간극 (topological gaps)을 채웁니다. Graft는 완전히 별도의 학습이 필요 없는 (training-free) 무손실 (lossless) 방식입니다.

종합적인 평가 결과, Graft는 짧은 문맥 생성 (short-context generation), 긴 문맥 생성 (long-context generation), 대규모 모델을 포함한 실제 배포 환경 전반에서 새로운 파레토 프런티어 (Pareto frontier)를 구축함을 보여줍니다. 짧은 문맥 벤치마크에서 Graft는 최대 5.41배의 속도 향상을 달성했으며, 대규모 Qwen3-235B 모델에서 EAGLE-3 대비 평균 속도 향상을 최대 21.8%까지 개선했습니다. 또한 우리는 Graft를 DFlash 스타일의 블록 초안 작성 (block drafting) 패러다임에 적용하는 예비 탐색을 제공하며, 이를 통해 접목 (grafting) 기술을 자기회귀적 초안 트리 (autoregressive draft trees) 너머로 확장하기 위한 초기 증거와 통찰을 제시합니다.