기술 요약: 하이브리드 및 순환형 LLM 서빙을 위한 희소 접두어 캐싱

1. 문제 제기

기존 대규모 언어 모델 (LLM) 서빙 시스템은 공유 접두어의 모든 토큰에 대한 키/값 (KV) 상태를 저장하여 불필요한 프리필 (prefill) 계산을 방지하는 밀집형 접두어 캐싱에 크게 의존합니다. 이 접근 방식은 트랜스포머 아키텍처의 표준입니다. 그러나 **상태 공간 모델 (SSM)**과 하이브리드 아키텍처(어텐션과 순환 계층을 결합) 는 구조적 비대칭성을 보입니다. 즉, 순환 계층은 $h_t = F(h_{t-1}, x_t)$로 상태를 진화시키므로, 전체 중간 상태의 이력을 필요로 하는 대신 단일 저장된 상태 $h_c$에서 계산을 재개할 수 있습니다.

순환 상태에 대한 토큰 단위의 밀집형 캐싱은 종종 불필요하며 비용이 과도하게 듭니다. Qwen-3.5 와 같은 모델의 경우, 헤드당 순환 상태는 $d_{head}^2$로 확장되는 반면, 어텐션 KV 저장소는 선형적으로 확장됩니다. 결과적으로 모든 토큰의 순환 상태를 저장하는 것은 어텐션 KV 캐시보다 훨씬 많은 메모리를 소모하지만, 희소 체크포인트 집합을 저장하는 것보다 추가적인 이점을 제공하지는 않습니다.

해결된 핵심 문제는 다음과 같습니다: 길이가 $N$인 접두어에 대해 $M$개의 체크포인트 슬롯이라는 메모리 예산이 주어졌을 때, 미래 요청 겹침 깊이의 특정 분포 하에서 기대 재계산 비용을 최소화하기 위해 체크포인트를 어디에 배치해야 하는가? 이 최적화 문제는 캐시 허용/제거 정책과 구별되며, 단일 유지 항목 내에서 어떤 토큰을 체크포인트로 지정하여 부분 접두어 겹침에 대한 유틸리티를 극대화하는 데 초점을 맞춥니다.

2. 방법론

이론적 형식화

저자들은 이 문제를 선형 상의 일측 가중 k-중앙값 문제로 형식화했습니다.

• $C = \{c_1, \dots, c_M\}$를 체크포인트 위치의 집합이라 합시다.
• 깊이 $t$까지 접두어와 겹치는 요청에 대해, 가장 깊게 재사용 가능한 체크포인트는 $\ell(t; C) = \max(\{0\} \cup \{c \in C : c \le t\})$입니다.
• 비용은 재계산해야 하는 토큰 수입니다: $r(t; C) = t - \ell(t; C)$.
• 목표는 겹침 깊이 분포 $T$와 확률 $p_t$가 주어졌을 때 기대 재계산 비용 $E[r(T; C)]$을 최소화하는 것입니다.

알고리즘적 접근

1. 최적 균형 배치 (균일/최악의 경우): 저자들은 균일한 겹침 분포 하에서 또는 최악의 시나리오에서 균형 잡힌 간격(고르게 분포된 체크포인트) 이 최적임을 증명했습니다.
2. 분포 인식 동적 계획법 (DP): 비균일한 실제 세계 겹침 분포의 경우, 저자들은 정확한 $O(NM)$ 동적 계획법 알고리즘을 유도했습니다.
   • 점화식은 다음과 같습니다: $dp[m, j] = \min_{1 \le s \le j} (dp[m-1, s-1] + w(s, j))$. 여기서 $w(s, j)$는 깊이가 $s \dots j$인 경우 $s$를 가장 깊은 체크포인트로 사용할 때의 비용입니다.
   • 이는 접두어 합의 단조성을 활용하는 **단조 볼록 껍질 기법 (monotone convex hull trick)**을 사용하여 효율적으로 해결됩니다.
3. 분포 드리프트 처리: 실제 겹침 분포는 알려져 있지 않으며 역사적 데이터에서 추정되어야 하므로, 본 논문은 가치 함수가 겹침 분포에 대해 **리프시츠 연속 (Lipschitz continuous)**임을 보장하는 이론적 보장 (Lemma 1 및 Theorem 3) 을 제공합니다. 이는 경험적 히스토그램 (또는 드리프트 분포를 위한 지수 가중 히스토그램) 을 사용하면 유계 하위 최적성을 가진 거의 최적의 일정을 산출함을 보장합니다.

구현 전략

• 체크포인팅: 시스템은 희소 위치에서 정확한 순환 상태를 저장합니다. 캐시 히트가 발생하면 시스템은 가장 깊게 저장된 체크포인트에서 재개하고 접미사를 정확하게 재계산합니다.
• 정확성: 순환 업데이트가 결정론적이므로, 체크포인트에서 재개하고 접미사를 재생성하면 전체 프리필과 비트 단위로 동일한 출력을 생성합니다.
• 하이브리드 통합: 하이브리드 모델의 경우, 이 방법은 전체 어텐션 KV 캐시 (밀집형) 를 저장하지만 순환 계층에만 희소 체크포인팅을 적용합니다.

3. 주요 기여

1. 이론적 최적성: 균일 겹침 및 최악의 경우 조건 하에서 균형 간격이 최적임을 증명 (Theorem 1).
2. 정확한 알고리즘: 희소 접두어 캐싱을 가중 k-중앙값 문제로 형식화하고 정확한 $O(NM)$ 동적 계획법 솔루션을 제공 (Theorem 2).
3. 강건성 보장: 최적 일정이 분포 오지정 하에서 안정적임을 입증. 하위 최적성은 경험적 및 실제 겹침 분포 간의 총변동 거리 (total variation distance) 로 제한되며 (Theorem 3), 지수 재가중치를 사용하여 분포 드리프트가 있는 시나리오로 확장됨 (Theorem 4).
4. 실증적 검증: QuALITY, NarrativeQA, System Prompts 와 같은 실제 데이터셋에서 방법을 검증하여 고정 예산 기준 대비 일관된 개선을 보임.

4. 실험 결과

데이터셋 및 설정

• 데이터셋:
  • QuALITY: 여러 질문이 포함된 단일 문서 (전체 길이 근처에서 높은 겹침).
  • NarrativeQA: 광범위한 멀티모달 겹침을 가진 유사한 구조.
  • System Prompts: 사용자 쿼리와 결합된 실제 시스템 프롬프트 (짧은 길이에서 겹침 집중).
• 기준: "No Cache", "KV Only", "Balanced"(균등 간격), "Block"(고정 블록 크기), "Logarithmic", "$\sqrt{L}$-spaced" 전략과 비교.
• 하드웨어: Qwen-3.5-0.8B 모델로 NVIDIA RTX 2080 Super 에서 프로토타입 실행.

발견 사항

• 토큰 절감: DP 최적 일정은 순환 작업 감소율 측면에서 결정론적 기준 (Balanced, Block, Logarithmic) 을 일관되게 우세하게 수행합니다.
• 저예산 이점: 성능 격차는 겹침 분포가 가장 비균일한 낮은 체크포인트 예산에서 가장 큽니다. 예를 들어, System Prompts(겹침이 짧은 경우) 에서 DP 방법은 발산 피크 근처에 체크포인트를 밀집하게 배치하여, 더 적은 체크포인트로 블록 캐싱과 동일한 실행 시간을 달성합니다.
• 월클록 시간: QuALITY 및 System Prompts 에서 DP 유도 일정은 대표적 계층 그룹에서 측정 가능한 월클록 속도 향상을 제공합니다. 실행 시간 감소는 저장된 토큰 수와 선형적으로 상관관계가 있습니다.
• 오버헤드: CPU 에서 GPU 로 체크포인트를 로드하는 오버헤드는 감소된 재계산으로 얻은 절감량에 비해 작아 순 실행 시간 개선을 가져옵니다.

5. 중요성 및 주장

본 논문은 희소 접두어 캐싱이 이전에 사용 불가능했던 하이브리드 및 순환형 LLM 서빙을 위한 새로운 설계 지점을 열어준다고 주장합니다.

• 메모리/계산 트레이드오프: 상태가 정확하게 추출 및 복원될 수 있는 아키텍처의 경우, 밀집형 KV 캐싱이 제공할 수 없는 메모리 사용량과 재계산 간의 트레이드오프를 제공합니다.
• 정확성: 근사적 KV 압축 기술과 달리, 이 방법은 순환 계산 커널을 변경하지 않고 정확한 출력을 유지합니다.
• 적용 가능성: 요청이 상당하지만 동일하지 않은 접두어를 공유하는 워크로드 (예: 다른 질문을 가진 RAG, 다양한 시스템 프롬프트) 에 가장 유익합니다. 엄격한 순차 추가만 있는 채팅 워크로드 (마지막 상태만 충분함) 에는 추가 이점을 제공하지 않지만, 그러한 경우에도 오버헤드가 발생하지는 않습니다.
• 향후 작업: 저자들은 효율적인 상태 추출/복원 API 가 프로덕션 런타임에 필요하다는 엔지니어링적 과제와 이 배치 전략을 허용/제거 정책 (예: Marconi et al.) 과 통합해야 한다는 점을 인정합니다. 또한 현재 단일 접두어 이론을 일반 접두어 트리로 확장할 수 있음을 지적합니다.