기술 요약: KV 캐시 메모리 제약 하의 LLM 추론 안정성 분석을 위한 대기행렬 이론적 프레임워크

문제 제기

대규모 언어 모델 (LLM) 의 급속한 채택은 대규모 효율적 추론에 상당한 도전을 제기했습니다. 전통적인 워크로드와 달리, LLM 추론은 연산 처리량과 Key-Value(KV) 캐싱의 메모리 오버헤드라는 이중 병목 현상에 의해 제약받습니다. KV 캐싱은 이전에 생성된 토큰의 표현을 재사용하여 디코딩을 가속화하지만, 상당한 GPU 메모리를 소모하며 종종 주요 용량 제약 요인이 됩니다.

기존 LLM 추론을 위한 대기행렬 모델들은 주로 연산 한계에 초점을 맞추거나 메모리를 정적 제약으로 취급하여, 추론 과정 중 연산과 메모리 증가 간의 역동적인 상호작용을 포착하지 못합니다. 구체적으로, 요청이 프롬프트 (prefill) 단계와 토큰 생성 (decode) 단계를 거치면서 메모리 사용량은 선형적으로 증가합니다. 요청 도착률이 GPU 연산과 사용 가능한 KV 캐시 메모리에 의해 공동 결정되는 시스템의 유효 서비스율을 초과할 경우, 대기열이 무한히 증가하여 시스템 불안정성, 용납할 수 없는 지연 시간, 그리고 저하된 사용자 경험을 초래합니다. 이러한 역동적인 메모리 제약을 명시적으로 통합하여 안정성 조건을 결정하고 GPU 할당을 안내하는 엄밀한 이론적 프레임워크는 부재합니다.

방법론

저자들은 KV 캐시 메모리 제약 ($M$) 을 받는 이산 시간, 작업 보존 (work-conserving) 대기행렬 시스템으로서 LLM 추론을 모델링하는 새로운 대기행렬 이론적 프레임워크를 제안합니다.

1. 시스템 모델

• 요청 구조: 각 요청 $i$는 $s_i$ 크기의 프롬프트와 $o_i$ 길이의 응답으로 구성되며, 결합 분포 $F_{in-out}$에서 샘플링됩니다.
• 처리 단계:
  • 프롬프트 단계: 프롬프트는 고정 크기 청크 ($\hat{s}$) 로 처리됩니다. 프롬프트의 $j$번째 청크에 대한 메모리 사용량은 선형적으로 증가합니다 ($j \times \hat{s}$).
  • 디코드 단계: 토큰이 순차적으로 생성됨에 따라, 각 단계마다 토큰 하나 분량의 KV 캐시만큼 메모리 사용량이 증가합니다. 요청 완료 시 총 메모리 사용량은 $s_i + o_i$에 도달합니다.
• 메모리 제약: 시스템은 모든 시간 $t$에서 $\sum_{i \in S(t)} (c_i^{(t)}\hat{s} + d_i^{(t)}) \le M$을 만족해야 합니다. 여기서 $S(t)$는 활성 요청 집합, $c_i^{(t)}$는 처리된 프롬프트 청크 인덱스, $d_i^{(t)}$는 처리된 출력 토큰 인덱스입니다.
• 스케줄링: 이 프레임워크는 연속 배치 (continuous batching) 와 작업 보존 정책 (예: 선입선출) 을 가정하며, 서버는 용량이 허용될 때마다 다음 우선순위 프롬프트를 처리합니다.

2. 이론적 유도

저자들은 단일 요청에 대한 수명 주기 누적 메모리 사용량 $g(s, o)$를 정의하여, 요청의 전체 서비스 시간 동안 소비된 총 메모리 "면적"을 나타냅니다.
$$g(s, o) := \sum_{k=1}^{s/\hat{s}} k\hat{s} + \sum_{j=1}^{o} (s+j)$$
이를 바탕으로 최대 안정 서비스율 $\mu$를 유도합니다.
$$\mu = \frac{M}{\bar{b} \mathbb{E}_{s,o \sim p(s,o)}[g(s, o)]}$$
여기서 $\bar{b}$는 정규화된 배치 처리 시간입니다.

3. 안정성 분석

LLM 의 조각별 선형 메모리 역학에 맞춰 적응된 리아푸노프 (Lyapunov) 드리프트 논증을 사용하여, 이 논문은 두 가지 핵심 정리를 확립합니다.

• 불안정성: 도착률 $\lambda > \mu$인 경우 시스템은 과부하 상태가 되어 요청 수가 무한히 증가합니다.
• 안정성: $\lambda < \mu(1 - \delta)$인 경우, 여기서 $\delta = \frac{\text{ess sup}(s+o)}{M} \ll 1$은 가장 큰 단일 작업을 수용하기 위해 필요한 메모리 여유분을 나타내며, 시스템은 안정적입니다 (양 재귀 마코프 체인).

주요 기여

1. 새로운 모델링: 이 논문은 KV 캐시에 의해 지배되는 연산 수요와 역동적인 GPU 메모리 제약을 명시적으로 통합한 LLM 추론을 위한 최초의 대기행렬 모델을 소개합니다. 메모리 인식 기능을 추가하고 청크화된 프롬프트 채우기 단계를 통한 스케줄링 설정을 정교화함으로써 기존 모델을 일반화합니다.
2. 엄밀한 안정성 조건: 저자들은 폐쇄형 안정성 및 불안정성 조건을 유도했습니다. 이러한 결과는 확률적 워크로드 하에서 LLM 서비스 시스템이 견딜 수 있는 최대 처리량을 결정하기 위한 원칙적인 기초를 제공합니다.
3. 실증적 검증: 이론적 예측은 실제 GPU 생산 환경 (NVIDIA A100) 에서 광범위한 실험을 통해 검증되었으며, 단일 GPU 및 다중 GPU(데이터 병렬) 구성 모두를 포괄합니다.

실험 결과

저자들은 vLLM 추론 엔진을 사용하여 8-GPU 테스트베드에서 Meta-Llama-3-8B 모델을 통해 실험을 수행했습니다.

• 정확도: 이론적 서비스율 $\mu_{theory}$는 실험적으로 측정된 속도 $\mu_{gpu}$와 밀접하게 일치했습니다. 다양한 프롬프트 - 디코드 (P/D) 비율 (1:1, 2:1, 1:2) 과 실제 세계 데이터셋 (LongBench v2) 에 걸쳐 예측 오차 (절대 백분율 차이) 는 10% 이내 (구체적으로 2.25% 에서 8.38% 사이) 로 유지되었습니다.
• 다중 GPU 확장성: 8-GPU 클러스터 설정에서 이론적 모델은 선형적으로 확장되어 예측된 속도와 관측된 속도 간의 격차가 불과 3.38% 였습니다.
• 안정성 역학: 실험은 $\lambda < \mu$일 때 대기열 길이가 유계로 유지됨 (예: 단일 GPU 의 경우 $\le 5$) 을 확인했으며, 반면 $\lambda > \mu$인 경우 선형적이고 무제한적인 대기열 증가가 발생함을 입증했습니다.

중요성 및 주장

이 논문은 시스템 배포 및 리소스 할당을 위한 강력한 도구를 제공한다고 주장합니다. 추정된 요청 도착률과 유도된 안정 서비스율을 결합함으로써 운영자는 다음을 위해 필요한 클러스터 크기를 계산할 수 있습니다.

• 비용이 많이 드는 과구매 (유휴 GPU) 방지.
• 성능 위반을 초래하는 미흡한 할당 (무제한 대기열 및 지연 시간 급증) 예방.

저자들은 이 프레임워크가 용량 계획에 대한 "원칙적인 기초"를 제공하여 실무자가 용량과 수요를 정량적으로 균형 있게 조정할 수 있게 한다고 강조합니다. 현재 작업은 데이터 병렬 배포에 초점을 맞추고 있지만, 이 프레임워크는 유효 메모리 및 배치 시간 매개변수를 조정함으로써 텐서 병렬 처리로 확장될 수 있다고 언급하며, 파이프라인 병렬 처리 및 분리는 추가 연구가 필요하다고 덧붙였습니다. 결과는 메모리 역학을 대기행렬 모델에 통합하는 것이 현대 LLM 서비스 시스템의 정확한 안정성 분석에 필수적임을 확인시켜 줍니다.