Cactus: Accelerating Auto-Regressive Decoding with Constrained Acceptance Speculative Sampling

이 논문은 검증기 LLM 의 분포와의 제어된 편차를 보장하면서 수락률을 높여 자동회귀 디코딩을 가속화하는 'Cactus'라는 새로운 제약 수용 추측 샘플링 기법을 제안하고 있습니다.

핵심

🐢🐆 문제: 거대한 코끼리와 작은 쥐의 협동

대형 AI 모델 (예: 챗봇) 은 방대한 지식을 가진 거대한 코끼리라고 상상해 보세요. 이 코끼리는 매우 똑똑하지만, 한 마디 (단어) 를 말하려면 무거운 머리를 움직여야 하므로 매우 느립니다.

반면, 작은 AI 모델은 재미있는 쥐처럼 빠르고 가볍지만, 지식이 부족해 가끔 엉뚱한 말을 하기도 합니다.

기존의 **'스페큘레이티브 샘플링 (Speculative Sampling)'**이라는 기술은 이 쥐가 먼저 몇 마디를 빠르게 말해보고, 코끼리가 "아, 그거 맞네!"라고 확인해 주는 방식입니다. 하지만 코끼리는 아주 엄격해서, 쥐가 말한 단어가 100% 정확하지 않으면 (확률이 조금만 낮아도) **"아니야, 다시 해!"**라고 모두 다 부인하고 처음부터 다시 시작합니다. 이 과정에서 코끼리의 엄격한 기준 때문에 속도가 다시 느려지는 경우가 많았습니다.

---

🚫 기존 해결책의 한계: 너무 엄격한 심판관

기존 방법들은 코끼리의 기준을 100% 그대로 따르려다 보니, 쥐가 말한 좋은 아이디어도 "완벽하지 않아서" 버려지는 경우가 많았습니다.
또 다른 방법 (TAS) 은 "아니야, 완벽하지 않아도 괜찮아, 대충 비슷하면 통과시켜!"라고 기준을 낮췄습니다. 하지만 이렇게 기준을 너무 낮추면, 코끼리가 가진 중요한 정보나 뉘앙스가 사라져서 AI 가 엉뚱한 방향으로 말하게 되는 (질 저하) 문제가 생겼습니다.

---

🌵 CACTUS 의 등장: '가시'로 통제된 유연함

이 논문에서 제안한 CACTUS는 이 문제를 해결하기 위해 **'제약된 최적화 (Constrained Optimization)'**라는 수학적 원리를 적용했습니다.

비유로 설명하자면:
CACTUS 는 코끼리에게 이렇게 말합니다.

"코끼리님, 쥐가 말한 단어를 100% 완벽하게 따질 필요는 없어요. 하지만 너무 엉뚱한 길로 빠지지 않도록 '가시 (CACTUS)' 하나만 세워두세요."

이 '가시'는 **허용 가능한 오차 범위 (δ)**를 의미합니다.

1. 유연함: 코끼리가 쥐의 말을 100% 정확하지 않아도, '가시'가 허용하는 범위 내라면 "좋아, 통과!"라고 더 많이 받아줍니다. (속도 향상)
2. 통제: 하지만 그 범위를 넘어서면 (예: 코끼리가 중요하게 생각하는 핵심 정보를 무시하면) "아니야, 여기까지만!"이라고 딱 끊습니다. (품질 유지)

즉, CACTUS 는 "속도는 빠르게 하되, 엉뚱한 길로 빠지지 않도록 가시로 막아주는 지능적인 심판관" 역할을 합니다.

---

🚀 왜 CACTUS 가 특별한가요?

1. 질 떨어지지 않는 속도 향상:
   기존 방법들은 속도를 높이면 AI 가 멍청해지거나 엉뚱한 말을 하는 경우가 많았습니다. 하지만 CACTUS 는 '가시 (제약 조건)' 덕분에 속도는 빨라지면서도 AI 의 답변 품질은 그대로 유지하거나 오히려 더 좋아지기도 했습니다.

2. 학습이 필요 없는 가벼운 방법:
   많은 AI 기술은 새로운 모델을 훈련시키느라 시간과 돈이 많이 듭니다. 하지만 CACTUS 는 기존 모델을 그대로 사용하면서 수학적 규칙만 살짝 바꿔서 적용할 수 있어 매우 가볍고 실용적입니다.

3. 다양한 상황에서 효과:
   수학 문제 풀이, 지시 따르기, 과학 지식 질문 등 다양한 테스트에서 CACTUS 가 기존 방법들보다 더 많은 단어를 빠르게 받아들이면서도 정확한 답변을 내놓았습니다.

---

💡 결론: 더 빠르고 똑똑한 AI 의 미래

CACTUS 는 거대한 AI 모델이 무겁게 움직이는 것을 막아주는 **'가볍고 똑똑한 가속기'**입니다. 마치 코끼리가 쥐의 빠른 발걸음을 따라가되, 엉뚱한 길로 빠지지 않도록 가시로 길을 안내하는 것과 같습니다.

이 기술이 널리 쓰인다면, 우리는 더 빠르고 저렴하면서도 똑똑한 AI를 일상에서 더 쉽게 사용할 수 있게 될 것입니다. AI 가 "생각"하는 속도가 빨라지면, 우리도 더 많은 일을 빠르게 해결할 수 있게 되겠죠! 🌵⚡

기술 요약

CACTUS: 제약된 수용 (Constrained Acceptance) 을 통한 자기회귀 디코딩 가속화

이 논문은 ICLR 2026 에 발표된 **"CACTUS: ACCELERATING AUTO-REGRESSIVE DECODING WITH CONSTRAINED ACCEPTANCE SPECULATIVE SAMPLING"**으로, 대형 언어 모델 (LLM) 의 추론 속도를 높이기 위한 새로운 Speculative Sampling (SpS) 기법을 제안합니다.

1. 문제 정의 (Problem)

대형 언어 모델 (LLM) 은 매 토큰 생성 시 수천억 개의 파라미터를 가진 모델을 메모리에서 로드하고 순전파 (forward pass) 를 수행해야 하므로, 메모리 병목 현상으로 인해 추론 속도가 느립니다. 이를 해결하기 위해 **Speculative Sampling (SpS)**이 제안되었습니다. SpS 는 작은 '드래프트 모델 (draft model)'이 여러 개의 후보 토큰을 제안하고, 큰 '검증자 모델 (verifier model)'이 이를 병렬로 검증하는 방식입니다.

하지만 기존 SpS 의 한계는 다음과 같습니다:

• 과도한 엄격성: SpS 는 검증자 모델의 분포와 정확히 일치해야만 토큰을 수용합니다. 이로 인해 검증자 모델이 낮은 확률을 가지더라도 올바른 토큰이 거부될 수 있습니다.
• 기존 해결책의 문제점 (TAS): 'Typical Acceptance Sampling (TAS)'은 엔트로피 기반 휴리스틱을 사용하여 더 많은 토큰을 수용하려 하지만, 이는 검증자 모델의 분포를 왜곡시킵니다. 특히 검증자 모델이 중요한 정보를 인코딩하고 있을 때, TAS 는 의미적 편향 (semantic drift) 을 일으켜 출력 품질을 저하시킬 수 있습니다.

2. 방법론 (Methodology)

저자들은 Speculative Sampling 을 제약 최적화 (Constrained Optimization) 문제로 재정의하고, 이를 해결하는 Cactus (Constrained Acceptance Speculative Sampling) 알고리즘을 제안합니다.

2.1. 제약 최적화 프레임워크

목표 분포 $h$를 검증자 모델의 분포 $q$와 드래프트 모델의 분포 $p$ 사이에서 동적으로 선택하는 문제를 다음과 같이 설정합니다:

• 목적 함수: 수용률 (Acceptance Rate) 을 최대화 ($\min\{h(n)/p(n), 1\}$).
• 제약 조건: 목표 분포 $h$와 검증자 분포 $q$ 사이의 발산 (Divergence) 을 $\delta$ 이하로 제한 ($D_f(h \| q) \le \delta$).

이 프레임워크는 검증자의 분포를 완전히 따르거나 (SpS), 임의로 왜곡하는 (TAS) 것이 아니라, 허용 가능한 범위 내에서 분포를 변형하여 수용률을 높이는 균형을 찾습니다.

2.2. Cactus 알고리즘의 핵심

• KL 발산 사용: Cactus 는 $f$-divergence 중 **KL 발산 (Kullback-Leibler Divergence)**을 거리 측정 지표로 사용합니다. 이는 TAS 가 사용하는 교차 엔트로피 (Cross-Entropy) 와 달리, 분포의 전체적인 형태를 보존하면서도 확률 밀도를 조절할 수 있게 합니다.
• 해의 유도: 최적의 분포 $h$는 드래프트된 토큰 $n$의 확률에 작은 '보너스'를 더하고, 나머지 토큰의 확률을 비례하여 줄이는 형태로 도출됩니다.
  • $h(n) = \gamma^*$ (드래프트 토큰의 확률 증가)
  • $h(i) = \frac{1-\gamma^*}{1-q(n)}q(i)$ (기타 토큰 확률 조정)
• 근사 해 (Approximation): 정확한 해를 구하는 방정식은 초월 함수를 포함하여 폐쇄형 해가 없으므로, 2 차 테일러 급수 전개를 통해 효율적인 근사 해를 구합니다.
• 보장: Cactus 는 이론적으로 전체 알고리즘의 분포가 검증자 분포로부터 $\delta$ 이하로만 발산함을 보장합니다. 이는 TAS 가 분포를 무작위로 왜곡하는 것과 대조적입니다.

2.3. TAS 와의 비교

• TAS: 교차 엔트로피를 최소화하려다 분포를 결정론적 (deterministic) 으로 붕괴시켜 엔트로피를 0 으로 만듭니다. 이는 검증자가 가진 풍부한 정보 (고엔트로피) 를 잃게 만듭니다.
• Cactus: KL 발산을 제어하여 분포의 형태를 유지하면서 수용률만 높입니다. 따라서 검증자가 가진 중요한 정보 손실을 방지합니다.

3. 주요 기여 (Key Contributions)

1. 이론적 재정의: Speculative Sampling 을 제약 최적화 문제로 공식화하여, 수용률과 분포 발산 사이의 균형을 수학적으로 증명했습니다.
2. 새로운 알고리즘 (Cactus): 훈련이 필요 없는 (training-free), 계산 비용이 적은 새로운 수용 규칙을 제안했습니다. 이는 검증자 모델의 확률 분포를 수정하여 드래프트 토큰의 수용 가능성을 높입니다.
3. 분산 제어 보장: Cactus 는 검증자 모델과의 분산 (divergence) 을 엄격하게 제어하여, TAS 의 품질 저하 문제를 해결하면서도 높은 처리량을 달성합니다.

4. 실험 결과 (Results)

저자들은 Qwen 3 시리즈 (0.6B, 1.7B, 8B, 14B, 32B) 를 포함한 다양한 모델과 Gemma, DeepSeek R1, LLaMA 등 여러 아키텍처에서 실험을 수행했습니다.

• 벤치마크: GSM8K (수학), IFEval (지시 준수), GPQA (과학 지식) 등 다양한 태스크에서 평가했습니다.
• 수용률 및 처리량: Cactus 는 SpS 와 TAS 모두보다 **높은 평균 수용 길이 (Average Accepted Length, AL)**를 기록했습니다. 예를 들어, Qwen 3 14B + 0.6B 설정에서 GPQA 태스크의 AL 은 SpS(3.37) 와 TAS(4.99) 대비 Cactus(5.16) 가 더 높았습니다.
• 정확도 유지: TAS 는 GPQA 와 같은 까다로운 벤치마크에서 정확도가 떨어지는 반면, Cactus 는 수용률을 높이면서도 검증자 모델과 유사하거나 더 높은 정확도를 유지했습니다.
  • 예: Qwen 3 14B + 0.6B 기준, GPQA 에서 SpS(39.39), TAS(38.89) 대비 Cactus(43.43) 로 정확도가 오히려 향상되었습니다.
• 실제 속도 향상: A100 GPU 환경에서의 실험 결과, Cactus 는 SpS 대비 약 1.9 배의 속도 향상을 보였으며, 이는 TAS 보다도 우월한 성능이었습니다.
• 확장성: 32B 모델과 같은 더 큰 모델에서도 Cactus 의 효과는 일관되게 유지되었습니다.

5. 의의 및 결론 (Significance)

이 논문은 LLM 추론 가속화 분야에서 중요한 이론적, 실용적 기여를 합니다.

• 이론적 엄밀성: 단순히 휴리스틱을 적용하는 것을 넘어, 분포 이론과 최적화를 기반으로 한 엄밀한 프레임워크를 제시했습니다.
• 실용성: 추가적인 모델 훈련 없이, 기존 SpS/TS 파이프라인에 쉽게 통합할 수 있는 경량화된 방법론을 제공합니다.
• 품질과 속도의 균형: 기존 방법들이 겪던 "속도 향상 vs. 품질 저하"의 트레이드오프를 해결하여, 높은 처리량과 높은 출력 품질을 동시에 달성할 수 있음을 입증했습니다.

결론적으로, Cactus 는 대규모 언어 모델의 배포 비용을 줄이고 실시간 추론 효율성을 높이는 데 있어 강력한 솔루션이 될 것으로 기대됩니다.