LLM 서빙을 위한 기하학 인지형 온라인 스케줄링: 이론적 경계에서 시스템 실무까지

대화형 대규모 언어 모델 (Large Language Model, LLM) 서빙에 대한 폭발적인 수요는 추론 엔진 (inference engines)의 성능 최적화를 위한 핵심 영역으로서 Key-Value 캐시의 동적 메모리 점유율 (memory footprint) 관리를 부각시켰습니다. 현대의 추론 시스템은 주로 최단 작업 우선 (Shortest Job First)과 같은 시간 중심의 스케줄링 휴리스틱 (scheduling heuristics)에 압도적으로 의존합니다. 그러나 이러한 방식의 이론적 최적성은 전통적인 스케줄링 모델링에 뿌리를 두고 있어, LLM 추론 메커니즘 특유의 매우 동적인 2D 시공간적 기하학적 성장 (2D spatio-temporal geometric growth)을 포착하지 못합니다. 이를 해결하기 위해, 우리는 최소 볼륨 우선 (Smallest Volume First, SVF) 알고리즘과 그 매우 효율적인 변형인 1-bit SVF를 도입하여 기하학 인지형 온라인 스케줄링 (geometry-aware online scheduling)을 제안합니다. 이론적으로, 우리는 우리 접근 방식에 대한 엄격한 수학적 토대를 제공합니다. 새로운 증명 방법론을 활용하여, 출력 길이가 알려진 경우 SVF의 최악의 경우 경쟁비 (worst-case competitive ratio, $\text{CR} \le 48 \rightarrow \text{CR} \le 5$)를 개선했습니다. 이 핵심적인 돌파구를 바탕으로, 우리는 다양한 트래픽 시나리오와 정보 가용성에 따라 우리 알고리즘을 분석하는 포괄적인 이론적 분류 체계 (theoretical taxonomy)를 완성했습니다. 실무적으로, 우리는 우리 접근 방식을 vLLM의 플러그 앤 플레이 (plug-and-play) 레이어로 원활하게 통합했습니다. Llama-3.1 모델에 대한 광범위한 평가 결과, 포괄적인 성능 향상을 입증했습니다: SVF는 평균 및 꼬리 지연 시간 (tail latency) 모두에서 강력한 감소를 제공하며, 단 1비트의 정보만을 사용하는 1-bit SVF는 경쟁력 있는 처리량 (throughput)과 지연 시간을 달성합니다. 본 연구는 현대 LLM 배포에서 메모리 제약이 있는 스케줄링 문제를 해결하기 위한 이론적으로 견고하고 경험적으로 증명된 접근 방식을 확립합니다. 향후 연구를 돕기 위해, 우리의 코드는 https://github.com/Aurora-Kl/Geometry-Aware-Online-Scheduling.git 에서 확인할 수 있습니다.