기술 요약: CASCADE

문제 정의

대규모 언어 모델(LLM) 서빙 플랫폼은 현재 서비스 수준 목표(SLO)와 유입되는 요청의 이질적인 특성 사이의 근본적인 불일치 문제에 직면해 있습니다. SLO(특히 첫 번째 토큰 생성 시간[TTFT] 및 토큰당 출력 시간[TPOT])는 서비스 수준에서 정의되지만, 개별 요청의 실행 비용은 입력 길이, 생성 길이, 그리고 재사용 가능한 키-값(KV) 캐시 상태의 가용성 차이로 인해 수십 배까지 차이가 납니다.

vLLM과 같은 기존 서빙 시스템은 일반적으로 선입선출(FCFS) 방식이나 단순한 크기 기반 휴리스틱(예: 최단 작업 우선[SJF])을 채택합니다. 이러한 접근 방식은 개별 요청의 "지연 시간 예산(latency budget)"—즉, 요청의 SLO 마감 시점과 예측된 실행 시간 사이의 차이—을 고려하지 못합니다. 결과적으로 다음과 같은 문제가 발생합니다:

1. 헤드 오브 라인(HOL) 블로킹: 긴 컨텍스트를 가진 요청이 짧고 긴급한 요청을 차단하여, 후자의 SLO 위반을 초래합니다.
2. 비효율적인 KV 관리: 시스템은 계산 시간을 절약하기 위해 심층 메모리 계층(예: NVMe)에서 KV 상태를 검색합니다. 그러나 요청하는 작업의 특정 지연 시간 예산을 고려하지 않으면, 이러한 전송 작업이 요청의 남은 SLO 여유 시간을 초과하는 지연을 유발하여 캐시 히트(cache hit)를 SLO 위반으로 바꿀 수 있습니다.
3. 불공정성: 짧은 작업을 우선시하는 정책(SJF)은 긴 컨텍스트 워크로드(예: 코딩 에이전트, 추론 작업)를 체계적으로 기아 상태(starvation)에 빠뜨리는 반면, FCFS는 여유가 있는 요청과 매우 긴급한 요청을 구분하지 못합니다.

기존 스케줄러는 요청 순서 지정과 KV 캐시 관리를 독립적인 문제로 취급하며, 두 작업이 동일한 자원인 '요청당 지연 시간 예산'을 소비한다는 점을 인식하지 못합니다.

방법론: CASCADE 시스템

CASCADE는 통합된 요청당 지연 시간 예산을 사용하여 요청 스케줄링과 다계층 KV 캐시 관리를 공동으로 조정하도록 설계된 LLM 서빙 시스템입니다.

1. 지연 시간 예산 정의 및 추정

CASCADE는 요청 $r$에 대한 지연 시간 예산($B_r$)을 다음과 같이 정의합니다:
$$B_r = S_{TTFT}^{c(r)} - L_r$$
여기서 $S_{TTFT}^{c(r)}$는 클래스 수준의 SLO 목표이고 $L_r$은 예상되는 잔여 서비스 시간입니다.

• 추정: 시스템은 입력 길이, 예측된 출력 길이, 메모리 계층(HBM, DRAM, NVMe) 전반에 걸친 가용 프리픽스(prefix) KV 상태, 그리고 현재 시스템 부하를 모델링하는 TTFT 지연 시간 추정기를 사용합니다.
• 보수성: 신뢰성을 보장하기 위해, 추정기는 실제 부하 및 최대 용량 하에서의 예측 지연 시간을 평균화하고, 추정 오류와 경합을 고려하여 경험적 가드밴드 계수($\gamma$)를 곱해 스케일링합니다.

2. 이중 계층 스케줄링 아키텍처

CASCADE는 계산된 예산에 기반한 이중 계층 큐잉 메커니즘을 활용합니다:

• 계층 1 (양의 예산): $B_r > 0$인 요청은 우선순위 큐에 수락됩니다. 이들은 최소 잔여 예산 우선(Least-Remaining-Budget-First) 순서로 스케줄링됩니다. 이는 입력 크기에 관계없이 마감 시간이 촉박한(남은 예산이 적은) 요청을 여유가 있는 요청보다 우선시함을 보장합니다.
• 계층 2 (음의 예산): $B_r \le 0$인 요청은 보조 큐로 강등됩니다. 이들은 드롭되지 않고 클러스터가 유휴 상태일 때 기회적으로 실행됩니다. 요청의 기아 상태를 방지하기 위해 각 배치(batch)의 일정 비율을 계층 2를 위해 예약하며, 부하가 감소함에 따라 예산이 양수가 되면 다시 계층 1으로 승격됩니다.

3. 예산 인지형 KV 캐시 관리

동일한 지연 시간 예산이 메모리 계층(GPU HBM, CPU DRAM, NVMe) 전반의 메모리 결정을 제어합니다:

• 실행 가능한 복구(Feasible Restoration): 프리픽스 KV 상태가 심층 계층에서 발견될 경우, CASCADE는 이를 복구하는 데 필요한 전송 시간을 계산합니다. 전송이 요청의 남은 예산 내에 들어오는 경우에만 복구를 시작합니다.
• 재계산으로의 폴백(Fallback to Recomputation): 전송 지연이 SLO를 위반할 가능성이 있는 경우, 시스템은 심층 계층에서의 페치를 건너뛰고 GPU에서 프리픽스를 재계산하여 SLO 위반을 방지합니다.
• 선점(Preemption): HBM 메모리 압박이 발생할 때, CASCADE는 잔여 예산이 가장 큰 활성 요청을 선점합니다. 이들은 상당한 여유를 가지고 있으므로, 재실행 오버헤드가 SLO 위반을 일으킬 가능성이 낮기 때문입니다.

4. 구현

CASCADE는 vLLM 서빙 엔진의 확장 기능으로 구현되었습니다. 이는 다계층 KV 블록 배치 및 이동을 위해 LMCache와 통합됩니다. 시스템은 메타데이터(SLO, 추정 지연 시간, 도착 시간)를 기존 요청 객체에 스레딩하고 CPU에서 예산 계산을 수행함으로써 최소한의 오버헤드로 GPU 실행과 중첩(overlap)하여 작동합니다.

주요 기여

1. 지연 시간 예산을 공통 자원으로 식별: 본 논문은 요청 스케줄링과 KV 캐시 이동이 동일한 자원인 '요청당 지연 시간 예산'을 두고 경쟁한다는 점을 밝혀냈습니다. 또한 서비스 마감 시간, 요청 크기, 캐시 상태만으로는 오버헤드를 얼마나 감당할 수 있는지 결정하기에 불충분함을 입증했습니다.
2. 결합 조정 메커니즘: CASCADE는 요청당 지연 시간 예산을 유지 및 업데이트하며, 이를 사용하여 메모리 계층 전반의 KV 복구, 프리페칭(prefetching), 배치 및 재계산을 조율하는 LLM 서빙 시스템을 제시합니다.
3. 공정하고 높은 굿풋(Goodput)을 제공하는 스케줄링: 제안된 예산 기반 스케줄러는 긴 컨텍스트 요청을 체계적으로 기아 상태에 빠뜨리지 않으면서 HOL 블로킹을 줄여, 다양한 요청 클래스 간의 공정성을 보존합니다.
4. 경험적 검증: 시스템은 NVIDIA GB200 NVL72 하드웨어 프로필을 사용하여 세 가지 대규모 모델(Qwen-2.5-72B, Llama-3-70B, Llama-3-405B)에 대해 실제 프로덕션 트레이스로 평가되었습니다.

결과

ChatBot, Tool&Agent, Coder, Reasoning 워크로드를 포함하는 프로덕션 트레이스에 대한 평가는 다음을 보여줍니다:

• 굿풋(Goodput) 향상: CASCADE는 기본 vLLM FCFS 스케줄러 대비 SLO를 충족하는 굿풋을 최대 2.4배 개선합니다.
• SLO 위반 감소: FCFS 대비 SLO 위반을 40% 감소시킵니다.
• 공정성: CASCADE는 다양한 요청 크기 클래스에 대해 높은 Jain's Fairness Index(1.0에 근접)를 유지하는 반이, SJF는 긴 컨텍스트 요청에 심각한 기아 현상을 일으켜 헤비 워크로드에서 공정도를 ~0.6까지 떨어뜨립니다.
• 견고성: 높은 부하와 감소된 클러스터 용량 하에서도 CASCADE는 높은 굿풋과 낮은 위반율을 유지하는 반면, 베이스라인 모델들은 심각한 HOL 블로킹과 큐 축적 문제를 겪습니다.

의의 및 주장

본 논문은 현재 시스템의 SLO 위반의 주된 원인이 계산 능력의 부족이 아니라, HOL 블로킹과 조율되지 않은 KV 캐시 전송으로 인한 '지연 시간 예산의 낭비'라고 주장합니다. 지연 시간 예산을 명시적인 런타임 양으로 만듦으로써, CASCADE는 피할 수 없는 오버헤드(큐잉, 데이터 이동)를 이를 흡수할 수 있는 요청 쪽으로 유도하는 동시에 긴급한 요청을 보호합니다.

저자들은 이 접근 방식이 추가적인 하드웨어나 모델 가중치의 변경 없이도, 다양한 애플리케이션 유형(짧은 채팅 상호작용부터 긴 추론 작업까지)에 대해 엄격하게 지연 시간 SLO를 준수하면서 가속기 활용도와 굿풋을 극대화할 수 있다고 단언합니다. 이 시스템은 스케줄링과 메모리 관리를 연결하여, 이를 각 요청의 긴급성에 의해 구동되는 통합된 최적화 문제로 다룹니다.