기술 요약: LLM 서빙을 위한 기하학 인지형 온라인 스케줄링 (Geometry-Aware Online Scheduling)

문제 정의

대화형 시나리오에서 대규모 언어 모델(LLM)을 배포할 때 직면하는 핵심적인 병목 현상은 키-값(KV) 캐시의 동적인 메모리 점유량 관리입니다. 정적 작업 크기를 다루는 전통적인 스케줄링 문제와 달리, LLM 추론은 고유한 2D 시공간적 기하학적 성장(2D spatio-temporal geometric growth) 특성을 보입니다.

1. 메모리-시간 결합(Memory-Time Coupling): 자기회귀적 디코딩(autoregressive decoding) 과정에서 실행 시간은 메모리 확장과 선형적으로 결합됩니다. 즉, 생성되는 토큰 하나당 KV 캐시의 점유 면적이 증가합니다.
2. 연속 배치 역학(Continuous Batching Dynamics): 현대적인 엔진(예: vLLM)은 연속 배칭을 사용하며, 요청이 완료되거나 새로운 요청이 진입함에 따라 동시 배치 크기가 매 디코딩 단계마다 동적으로 변동합니다.

기존의 스케줄링 휴리스틱은 주로 시간 중심 모델링에 기반한 최단 작업 우선(SJF) 방식에 뿌리를 두고 있습니다. 이러한 방식은 LLM 서빙의 기하학적 실체를 포착하지 못합니다. 최근의 이론적 연구 [10]는 이러한 특정 기하학적 제약 조건 하에서 SJF가 **유계되지 않은 최악의 경쟁비(unbounded worst-case competitive ratio)**를 나타낸다는 것을 입증했으며, 이는 고전적 스케줄링 이론과 현대 LLM 추론의 물리적 실체 사이의 근본적인 간극을 드러냅니다.

방법론

저자들은 우선순위 지표를 1D 실행 시간에서 2D 메모리 부피로 전환하는 기하학 인지형 온라인 스케줄링(Geometry-Aware Online Scheduling) 프레임워크를 제안합니다.

핵심 알고리즘: 최소 부피 우선 (Smallest Volume First, SVF)

SVF는 실행 시간을 독립적으로 고려하는 대신, 요청의 전체 생애 주기 동안 발생하는 메모리 소비의 적분값을 평가합니다. 프롬프트 길이 $s_i$와 출력 길이 $o_i$를 가진 요청 $r_i$에 대해, 부피(Volume) $v_i$는 다음과 같이 정의됩니다:
$$v_i = s_i \cdot o_i + \frac{o_i^2 + o_i}{2}$$
이 공식은 요청이 차지하는 총 "메모리-시간" 면적을 정량화합니다. SVF는 $v_i$를 오름차순으로 정렬하는 엄격한 그리디(greedy) 정책으로 작동합니다. 구현은 요청을 배치하여 출력 길이를 질의하는 백그라운드 예측기와, KV 캐시 용량에 도달할 때까지 가장 높은 우선순위(가장 작은 부피)의 요청을 실행 배치에 수용하는 스케줄러의 두 프로세스로 분리됩니다.

경량 변형: 1-bit SVF

계산 오버헤드를 최소화하기 위해 저자들은 1-bit SVF를 도입했습니다. 이 변형은 정확한 길이 예측 대신, 요청을 "짧음"($m=0$) 또는 "긺"($m=1$)로 분류하는 이진 분류기를 사용합니다.

• 각 클래스에 전역 대리 길이(global proxy length) $O_m$을 할당합니다.
• 대리 부피는 $\hat{v}_i = s_i \cdot O_m + \frac{O_m^2 + O_m}{2}$로 계산됩니다.
• 이 설계는 핵심적인 시공간적 스케줄링 보증을 유지하면서 단 1비트의 정보만을 추출합니다.

이론적 기여

본 논문은 경험적인 시행착오를 넘어 엄밀한 수학적 토대를 제공합니다.

1. 강화된 최악 사례 경계 (버스트 도착 모델):

   • 출력 길이를 알고 있는 SVF의 경우, 버스트 도착 모델 하에서 저자들은 최악의 경쟁비(CR)가 CR $\le$ 5임을 증명했습니다. 이는 기존 문헌 [10]에서 발견된 CR $\le$ 48보다 크게 개선된 수치입니다.
   • 이 증명은 새로운 "거시적 인증(macroscopic certificate)" 방법론을 활용하며, 모든 차단된 단계(blocked step)가 활성 메모리 질량(active memory mass) $> M/2$를 의미함을 보여줌으로써 알고리즘의 대기 시간을 최적 오프라인 스케줄의 하한선과 직접 연결합니다.
   • 1-bit SVF의 경우, 경쟁비가 최대 모델 길이 $T$에 대해 $O(T)$로 제한됨을 보여, 최소한의 정보만으로도 극한의 부하 상황에서 시스템이 안정적으로 유지됨을 증명했습니다.

2. 확률적 경계 (포아송 도착 모델):

   • 포아송 도착 프로세스 하에서 본 논문은 기대 경쟁비를 도출합니다.
   • SVF는 $E[CR] \le 1 + \frac{4}{(1-\mu)(1-\rho)}$를 달성하며, 여기서 $\mu$는 길이의 기하학적 분포와 관련이 있고 $\rho$는 시스템 이용률과 관련이 있습니다.
   • 1-bit SVF의 성능 저하는 "부피 왜곡 페널티(volumetric distortion penalty)" $\epsilon$에 의해 지배되며, 이는 분류 임계값에 따라 지수적으로 감소하여 장기적인 안정성을 보장합니다.

실험 결과

이 접근 방식은 vLLM 내에 플러그 앤 플레이(plug-and-play) 레이어로 구현되었으며, Llama-3.1-8B 및 Llama-3.1-70B 모델을 사용하여 LMSYS-Chat 및 LongBench 워크로드에 대해 평가되었습니다.

• 지연 시간 감소: SVF는 모든 벤치마크에서 평균 및 꼬리(P95) 지연 시간 모두에서 일관되게 가장 낮은 수치를 기록하며, 메모리 집약적인 시나리오(LongBench)에서 FCFS, SJF, 심지어 완벽한 미래 길이 정보를 가진 Oracle-SJF보다 우수한 성능을 보였습니다.
• 처리량: SVF는 SJF보다 높은 처리량을 유지했습니다. 1-bit SVF는 경쟁력 있는 처리량과 지연 시간을 달성했으며, 종종 꼬리 지연 시간 지표에서 SJF를 능가했습니다.
• 오버헤드: 예측 오버헤드는 무시할 만한 수준이었습니다. 전체 길이 예측기는 엔드 투 엔드 지연 시간의 최대 **0.06%**만을 소비했으며, 1-bit 분류기는 **$\le$ 0.01%**를 소비했습니다.
• 공정성: 긴 작업을 굶기는(starve) 고전적 그리디 휴리스틱과 달리, SVF의 기하학 인지형 그리디 방식은 유계된 KV 캐시 메모리를 빠르게 해제함으로써 글로벌 헤드-오브-라인(head-of-line) 블로킹을 타파하고 큰 요청에 대한 공정성을 개선합니다.

의의 및 주장

본 논문은 현대 LLM 배포에서 메모리 제약 스케줄링 문제를 해결하기 위한 이론적으로 건실하고 경험적으로 증명된 접근 방식을 확립했다고 주장합니다. 주요 의의는 다음과 같습니다:

1. 패러다임 전환: 이 연구는 분야를 레거시 1D 시간 중심 휴리스틱에서 2D 기하학 인지형 우선순위 지정으로 이동시켜, 고전적 스케줄링 이론과 LLM 추론 메커니즘 사이의 근본적인 불일치를 해결합니다.
2. 이론적 발전: 경쟁비를 48에서 5로 좁히고 새로운 증명 방법론을 도입함으로써, 임의의 적대적 워크로드 분포에서도 유효한 보편적 구조적 보증을 제공합니다.
3. 실용적 생존 가능성: "플러그 앤 플레이" 방식의 스케줄러와 극도로 효율적인 1-bit 변형의 결면은, 엄밀한 수학적 최적화가 과도한 오버헤드 없이 고성능 추론 엔진에 원활하게 통합될 수 있음을 입증합니다.

저자들은 이러한 기하학 인지형 접근 방식이 시스템 효율성을 최적화할 뿐만 아니라, 대규모 추론에 필요한 계산 자원과 탄소 발자국을 줄임으로써 지속 가능한 AI 배포에 대한 시사점을 제공한다고 결론짓습니다.