요약
투기 디코딩(Speculative Decoding)은 LLM 서빙 처리량을 크게 높이는 방법이다. 드래프트 모델이 여러 후보 토큰을 먼저 생성하고 원본 모델이 한 번의 병렬 검증으로 수락·거절을 결정한다. 이를 트리 구조로 확장하면 더 많은 후보 경로를 동시에 검증할 수 있어 "트리 투기(Tree Speculation)"라 불린다.
그런데 최근 Transformer에 선형 순환(Linear Recurrence) 레이어를 혼합한 하이브리드-어텐션 LLM이 주류로 부상했다. Jamba, Zamba2, Falcon Mamba, RWKV-6 등이 대표적이다. 이 모델들은 Transformer의 KV 캐시 대신 행렬 형태의 순환 상태(Recurrent State)를 사용하는 레이어를 포함한다. 문제는 기존 트리 투기 시스템이 전통적인 KV 캐시 구조를 전제하고 설계되었다는 점이다.
Bole(arXiv:2608.01651)은 이 문제를 정면으로 다룬다. 하이브리드 모델에서 트리 투기를 실행하려면 드래프트 트리의 각 분기마다 순환 상태를 독립적으로 유지해야 한다. 나이브한 구현은 모든 드래프트 노드의 상태를 직렬로 순회하며 개별 상태 행렬을 유지하므로, 트리 크기에 비례해 메모리와 연산 시간이 폭발적으로 증가한다.
Bole는 선형 어텐션의 순환을 트리 구조 닫힘 형식(Tree-Structured Closed Form)으로 변환해 모든 드래프트 노드의 검증을 병렬화하고, 상태 업데이트를 토큰 수준 인수(Token-Level Factor)로 인코딩해 전이 메모리를 82–99% 줄인다. SGLang에 통합된 약 6.2 kLoC Python·Triton 구현으로 AR 디코딩 대비 최대 4.72× 오프라인 처리량을 달성한다.
- arXiv:2608.01651 · 2026년 8월 3일 공개
- SGLang 기반 구현 · 4개 하이브리드 모델 · 2개 GPU 플랫폼 평가
배경: 하이브리드-어텐션 LLM이란
Transformer + 선형 순환의 결합
순수 Transformer는 입력 전체에 대해 어텐션을 계산하므로 KV 캐시 크기가 시퀀스 길이에 비례해 증가한다. 긴 컨텍스트에서 메모리와 대역폭이 병목이 된다.
선형 순환 모델(SSM, State Space Model)은 고정 크기의 순환 상태를 토큰마다 업데이트하며 시퀀스를 처리한다. 메모리 사용량이 시퀀스 길이에 무관하지만, 임의 토큰 위치에 대한 무작위 접근이 어렵다.
하이브리드-어텐션 LLM은 이 두 구조를 레이어 단위로 혼합한다. 예를 들어 Jamba는 매 4번째 레이어만 Mamba-2 순환 레이어로 교체하고 나머지는 Transformer 어텐션을 유지한다. 이렇게 하면 단기 정밀도(Attention)와 장기 컨텍스트 비용 효율성(Linear Recurrence)을 동시에 확보할 수 있다.
| 특성 | 순수 Transformer | 순수 SSM | 하이브리드 |
|---|---|---|---|
| 상태 표현 | KV 캐시 (시퀀스 길이×히든) | 순환 상태 행렬 (히든×히든) | 레이어별로 다름 |
| 긴 컨텍스트 비용 | O(n²) | O(n) | O(n)에 가까움 |
| 임의 위치 접근 | 가능 | 불가 | 어텐션 레이어에서만 가능 |
| 투기 디코딩 호환성 | 기존 시스템 지원 | 별도 처리 필요 | Bole 이전에는 미지원 |
트리 투기 디코딩의 기본 원리
일반 자기회귀(AR) 디코딩은 토큰 하나를 생성할 때마다 전체 모델을 한 번씩 실행한다. 투기 디코딩은 이 과정을 두 단계로 분리한다.
- 드래프트 단계: 경량 드래프트 모델이 K개의 후보 토큰을 자기회귀로 순차 생성한다.
- 검증 단계: 원본 모델(Target)이 K+1개 위치를 한 번의 순전파로 검증한다.
드래프트 모델이 옳으면 K개 토큰이 한 번의 원본 모델 실행으로 생성되므로 처리량이 향상된다.
트리 투기는 드래프트를 선형 체인 대신 트리 구조로 확장한다. 각 드래프트 단계에서 top-k 후보를 분기로 전개해 여러 가설 경로를 동시에 유지한다.
Bole의 핵심 기술
1. 트리 구조 닫힘 형식 (Tree-Structured Closed Form)
선형 어텐션(Linear Attention)의 순환 업데이트는 다음 구조를 가진다.
h_{t+1} = S_t × h_t + u_t여기서 S_t는 토큰 t에서의 게이팅 행렬(Gating Matrix), u_t는 토큰 의존적인 업데이트 항이다. 이 관계를 전개하면:
h_k = S_{k-1} × S_{k-2} × ... × S_1 × h_0 + (...수렴 급수...)즉, 상태 h_k는 루트에서 현재 노드까지의 요인 행렬(Factor Matrix) 체인의 곱으로 표현된다. 이것이 닫힘 형식이다.
Bole는 이 닫힘 형식을 트리에 적용한다. 트리의 각 노드는 부모로부터 누적된 요인 체인을 가진다. 레벨 단위로 내려가면서 행렬 곱을 병렬로 계산하면 모든 드래프트 노드의 상태를 직렬 순회 없이 얻을 수 있다.
결과적으로 N개 드래프트 노드의 선형 어텐션 검증이 병렬 트리 행렬 곱 연산으로 바뀐다. 이 병렬 커널을 Triton으로 구현해 3.4–7.7× 선형 어텐션 트리 검증 가속을 달성한다.
2. 토큰 수준 인수 인코딩 (Token-Level Factor Encoding)
나이브한 구현의 두 번째 문제는 메모리다. 트리 내 모든 노드에 대해 완전한 상태 행렬을 유지하면 전이 메모리(Transient Memory)가 노드 수 × 상태 행렬 크기로 증가한다.
Bole는 상태 행렬 자체 대신 토큰 하나가 기여하는 요인 행렬만 저장한다. 부모-자식 관계는 요인 행렬의 곱으로 즉시 재구성할 수 있으므로, 완전한 상태를 항상 메모리에 유지할 필요가 없다.
저장: (S_{i}, u_{i}) — 각 노드의 토큰 요인 (작은 행렬)
복원: h_k = Chain(S_k, ..., S_1) × h_0 + (누적 업데이트)검증 후 수락된 토큰 경로의 상태만 최종 복원한다. 이 방식으로 전이 상태 메모리를 82–99% 절감한다.
3. 배치 단위 검증 예산 보정 (Batch-Wide Verification Budget)
트리 투기의 효율은 드래프트 트리의 크기(너비×깊이)에 민감하다. 너무 넓으면 검증 비용이 수락 토큰 수를 초과하고, 너무 좁으면 처리량 이득이 줄어든다.
하이브리드 모델에서는 전통 Transformer보다 트리 크기의 영향이 더 복잡하다. 선형 어텐션 레이어의 병렬화 이득이 트리 크기에 따라 비선형적으로 변하기 때문이다.
Bole는 SGLang의 스케줄러에 배치 단위 예산 보정 루프를 추가한다. 서빙 시 실측된 수락률(Acceptance Rate)과 검증 지연을 모니터링하고, 현재 워크로드에 최적인 트리 너비/깊이를 적응적으로 선택한다.
기존 접근법과 비교
왜 기존 트리 투기 시스템이 하이브리드 모델에서 실패하는가
기존 SpecInfer, Medusa, EAGLE 등의 시스템은 KV 캐시 기반 Transformer를 전제한다.
KV 캐시는 공유가 자연스럽다. 트리의 모든 분기가 공통 접두사까지의 KV를 공유하므로, 접두사 이후 각 분기의 고유 KV만 추가하면 된다. 이 구조 덕분에 트리 전체를 단일 배치 순전파로 검증할 수 있다.
순환 상태는 다르다. 각 토큰을 처리할 때마다 전체 상태 행렬이 업데이트되므로, 분기점 이후 각 드래프트 경로는 서로 다른 상태 이력을 가진다. 나이브한 구현은 이를 해결하기 위해 분기마다 순환 레이어를 직렬 순회하며 별도 상태를 유지한다.
| 문제 | 나이브한 하이브리드 트리 투기 | Bole |
|---|---|---|
| 검증 방식 | 드래프트 노드 수만큼 직렬 순회 | 트리 구조 닫힘 형식으로 병렬화 |
| 전이 메모리 | 노드 수 × 전체 상태 행렬 크기 | 노드 수 × 토큰 요인 (작음) |
| GPU 커널 | 루프 기반, SIMT 비효율 | 배치 병렬 Triton 커널 |
| 처리량 | AR 기준 제한적 향상 | AR 대비 최대 4.72× |
STree(NeurIPS 2025)와의 차이
NeurIPS 2025에서 발표된 STree도 SSM 계열 모델의 트리 투기를 다뤘다. STree는 순환 상태를 선형 시간 복잡도로 재계산하는 방법을 제안한다.
Bole는 STree 대비 두 가지 개선을 추가한다. 첫째, 닫힘 형식이 기존 재계산 방식보다 더 빠른 Triton 병렬 커널을 가능하게 한다. 둘째, 토큰 수준 인수 인코딩으로 재계산이 필요한 범위를 최소화하고 GPU 메모리 압박을 크게 줄인다. 실측 결과에서 Bole는 STree를 포함한 기존 기준선 대비 최대 2.03× 추가 처리량을 달성한다.
평가 결과 상세
Bole의 평가는 4개 하이브리드-어텐션 모델과 2개 GPU 플랫폼에서 이루어졌다.
처리량 비교
| 조건 | 기준 (AR 디코딩) | 기존 트리 투기 | Bole | Bole 이득 |
|---|---|---|---|---|
| 오프라인 (배치 크기 ≥ 1) | 1× | ~1.5–2× | 최대 4.72× | AR 대비 |
| 오프라인 최강 기준선 대비 | — | 1× | 최대 2.03× | 기준선 대비 |
| 선형 어텐션 검증 단독 | 1× | ~0.8–1.2× | 3.4–7.7× | 직렬 대비 |
메모리 절감
순환 상태를 전이 메모리로 유지할 때:
- 나이브한 구현: 트리 크기 16일 때 순환 상태 행렬 16개 전체를 GPU HBM에 유지
- Bole: 토큰 요인만 저장, 수락 후 단일 경로만 복원 → 전이 메모리 82–99% 절감
이 절감이 실질적으로 의미하는 바는 KV 캐시에 사용 가능한 HBM이 늘어난다는 것이다. 특히 배치 크기가 클 때 메모리 제약이 완화되어 처리량 이득으로 직결된다.
운영 시사점
언제 하이브리드 모델 + Bole가 유리한가
LLM 서빙 인프라 관점에서 하이브리드 모델은 다음 상황에서 검토 가치가 있다.
- 긴 컨텍스트 워크로드: 100K+ 토큰 시퀀스에서 순수 Transformer의 KV 캐시 비용이 부담이 될 때. 하이브리드 모델은 선형 어텐션 레이어에서 KV 캐시가 없으므로 메모리 사용량이 낮다.
- 처리량 우선 서빙: 배치 크기를 키워 GPU 효율을 높이고 싶을 때. Bole의 트리 투기로 추가 처리량 이득을 얻을 수 있다.
- KV 캐시 용량 한계: 동시 요청이 많아 GPU HBM이 KV 캐시로 포화될 때. 하이브리드 모델은 선형 어텐션 레이어의 상태가 상대적으로 작다.
SGLang 통합 체크리스트
Bole는 SGLang에 통합된 형태로 제공된다. 기존 SGLang 환경에서 하이브리드 모델 서빙 시 확인 항목:
□ 모델 아키텍처: 선형 어텐션 레이어(Mamba/SSM) + Transformer 혼합 확인
□ SGLang 버전: Bole 통합 버전 이상 사용 (커밋 기준으로 릴리스 노트 확인)
□ 드래프트 모델: 동일 하이브리드 구조의 경량 모델 준비 필요
□ 트리 예산: 초기 배포 시 기본값으로 시작, 워크로드 수락률 측정 후 조정
□ 메모리 모니터링: torch.cuda.memory_allocated() 기준 전이 메모리 추적
□ 벤치마킹: ShareGPT/LMSYS 트레이스 기준 처리량 AR 대비 측정하이브리드 모델 트리 투기의 제약
Bole는 하이브리드 모델의 트리 투기를 가능하게 하지만, 현실적인 제약도 있다.
드래프트 모델 가용성: 트리 투기에는 드래프트 모델이 필요하다. 하이브리드 모델의 경량 버전이 공개되지 않은 경우 EAGLE 방식의 드래프트 헤드 훈련이 필요하다.
선형 어텐션 레이어 비율: 모델 내 선형 어텐션 레이어가 많을수록 Bole의 병렬화 이득이 크다. 레이어 비율이 낮으면 Transformer 기반 기존 트리 투기와 큰 차이가 없을 수 있다.
Triton 커널 지원 GPU: Bole의 병렬 검증 커널은 Triton으로 구현된다. NVIDIA A100·H100·H200·B200 계열에서 검증되었으며 AMD ROCm 환경에서는 별도 이식이 필요하다.
요점 정리
Bole는 하이브리드-어텐션 LLM에서 트리 투기 디코딩이 작동하지 않았던 근본 원인을 해결했다. 선형 어텐션의 순환 구조가 트리 분기마다 독립 상태를 요구하여 병렬화를 막는다는 것이 문제였고, 닫힘 형식 변환으로 이를 병렬화 가능한 행렬 연산으로 바꿨다.
세 가지 기여가 결합될 때 효과가 극대화된다. 트리 닫힘 형식이 검증 속도를 높이고, 토큰 수준 인수 인코딩이 메모리를 절감해 더 큰 배치를 허용하며, 검증 예산 보정이 이 두 이점을 실제 워크로드에 맞게 조율한다.
하이브리드 LLM이 긴 컨텍스트 서빙의 주류가 되면 Bole 계열의 접근은 필수 인프라가 된다. 순수 Transformer에서만 동작하는 투기 디코딩 시스템은 이 전환에서 뒤처질 수 있다.
References
- arXiv:2608.01651 — "Bole: Efficient Tree Speculation for Hybrid-Attention Language Models" (2026-08-03)
- arXiv:2505.14969 — "STree: Speculative Tree Decoding for Hybrid State-Space Models" (NeurIPS 2025)
- SGLang 공식 문서 및 저장소: https://sgl-project.github.io
- arXiv:2401.15077 — "EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty" (EAGLE-1)
- arXiv:2406.16858 — "EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees"
- arXiv:2606.10493 — "Serving MoE at Consumer-Grade: Stream-Loading for Cloud-SLO on RTX 5090" (OSDI 2026)
- arXiv:2605.12460 — "Multi-Stream LLMs: Parallel I/O via Multiple Streams" (May 2026)