언제 초안이 수락되는가? Speculative Decoding에서의 수락 이론

Speculative decoding (추측적 디코딩)은 빠른 drafter (초안 생성기)를 사용하여 후보 토큰을 제안하고, 이를 더 큰 target model (대상 모델)이 검증함으로써 언어 모델의 추론을 가속화합니다. 기존 이론은 주로 target distribution (대상 분포)으로부터 정확하게 샘ся링하는 것을 목표로 하는 stochastic (확률적), distribution-preserving (분포 보존) 설정에 대해 연구해 왔습니다. 이와 대조적으로, 많은 실제 시스템은 greedy decoding (탐욕적 디코딩), 완화된 수락 규칙 (relaxed acceptance rules), 또는 tree-based (트리 기반) 후보 집합을 사용하며, 여기서의 성공은 정확한 분포적 일치보다는 local ranking (지역적 순위) 및 threshold (임계값) 이벤트에 의해 결정됩니다. 우리는 이러한 체제(regimes)를 위한 이론을 개발합니다. 우리는 많은 일반적인 수락 기준들이 target distribution의 lower level sets (하위 레벨 집합)로 특징지어질 수 있는 rejection regions (거부 영역)을 가지고 있음을 확인했습니다. 이를 위해, 우리는 거부를 위해 필요한 정확한 KL divergence (KL 발산)를 규명하여 정확한 certificates (증명서)를 제공하며, strict greedy decoding (엄격한 탐욕적 디코딩), additive (가산적) 및 multiplicative (승법적) 완화된 수락, top-(m) 완화된 기준, 그리고 entropy-thresholded (엔트로피 임계값 기반) 수락에 대해 날카로운 margin-based (마진 기반) 경계(bounds)를 도출합니다. 그런 다음 이 프레임워크를 greedy tree decoding (탐욕적 트리 디코딩)으로 확장하여, target greedy token (대상 탐욕적 토큰)이 drafter의 top-(m) 후보들에 의해 계속 커버되는 경우에 대한 정확한 certificate 및 margin-only certificate를 유도합니다. 마지막으로, 우리는 Qwen3 모델에서 결과적인 certificate들을 평가하며, 완화된 기준과 트리 기반 기준이 특히 target model distribution margin (대상 모델 분포 마진)이 낮은 디코딩 단계에서 certified acceptance (증명된 수락) 영역을 실질적으로 확장함을 보여줍니다. 이러한 결과는 실제 추론 시스템에서 흔히 발생하는 deterministic (결정론적) local acceptance (지역적 수락) 이벤트를 특징지음으로써, speculative decoding에 대한 기존의 distribution-preserving (분포 보존) 분석을 보완합니다.