기술적 요약: LLM 서빙은 휴리스틱이 아닌 수학적 최적화와 알고리즘적 기반이 필요하다

1. 문제 제기

본 논문은 대규모 언어 모델 (LLM) 추론 서빙이 고전적 분산 시스템에서 계승된 일반적 휴리스틱의 능력을 넘어섰다고 주장한다. 현대 서빙 프레임워크 (예: vLLM, SGLang) 가 연속 배치, 페이지드 어텐션, 프리필 - 디코드 분리 등의 중요한 아키텍처 혁신을 이루었음에도 불구하고, 그 핵심 알고리즘 의사결정 과정은 여전히 단순하고 범용적인 정책에 뿌리를 두고 있다.

핵심 문제는 구조적 불일치에 있다: LLM 추론은 일반적 휴리스틱이 활용하지 못하는 고유한 특성을 지니며, 이는 다음과 같다:

• 위상 비대칭성: 연산 병목 (compute-bound) 인 프리필 (prefill) 위상과 메모리 대역폭 병목 (memory-bandwidth-bound) 인 디코드 위상.
• 동적 리소스 소비: 생성된 토큰이 늘어날수록 KV 캐시 메모리가 단조 증가하며, 최종 크기는 생성이 완료될 때까지 알 수 없다.
• 고착된 할당 (Sticky Assignments): 한 번 요청이 워커로 라우팅되면 KV 캐시 전송 비용으로 인해 마이그레이션이 극도로 비싸다.
• 배리어 동기화: 데이터 병렬 또는 전문가 병렬 환경에서 가장 느린 워커 (종종 KV 캐시 크기에 의해 결정됨) 가 전체 배치의 지연 시간을 좌우한다.

현재 관행은 Join-Shortest-Queue, Round-Robin, First-In-First-Out (FIFO) 스케줄링, Least-Recently-Used (LRU) 교체와 같은 휴리스틱에 의존한다. 본 논문은 이러한 정책들이 LLM 워크로드의 특정 제약을 무시하여 다양하거나 적대적인 조건에서 예측 불가능한 성능을 초래하고 근본적인 성능 한계를 도출하는 것을 방해한다고 주장한다.

2. 방법론 및 제안된 프레임워크

본 논문은 경험적 휴리스틱 튜닝에서 수학적 최적화와 알고리즘적 기반으로의 전환을 옹호한다. 제안된 방법론은 다음과 같다:

1. 형식적 모델링: 라우팅, 스케줄링, 캐싱, 용량 계획과 같은 서빙 의사결정을 엄격한 수학적 프로그램 (예: 선형 계획법, 정수 계획법, 대기 행렬 이론) 으로 재구성한다.
2. 구조적 분석: 이러한 모델로부터 이중 변수, 안정성 조건, 경쟁 비율 (competitive ratios) 과 같은 이론적 통찰을 도출하여 시스템의 근본적 한계를 이해한다.
3. 알고리즘 설계: 계산적으로 가능한 경우 이러한 프로그램을 직접 해결하거나, 구조적 통찰을 활용하여 증명 가능한 성능 보장을 갖춘 실용적 근사 알고리즘을 설계한다.

본 논문은 항공 수익 관리와의 역사적 유사점을 제시한다. 여기서 선형 계획법은 실시간으로 모든 예약을 해결하기 위해 사용된 것이 아니라, 단순하고 빠르며 최적성 조건에 기반한 "입찰가 (bid-price)" 제어 정책을 도출하는 데 사용되었다.

3. 주요 기여 및 대표적 예시

본 논문은 원칙에 기반한 최적화가 현재 휴리스틱보다 우수한 대안을 제공하는 네 가지 핵심 병목 영역을 식별하며, 이는 신흥 연구에 의해 뒷받침된다:

A. 전문가 라우팅 및 부하 분산 (MoE)

• 현재 상태: 토큰 분포를 GPU 간에 균형 있게 맞추기 위해 훈련 중 보조 손실 함수 또는 반응적 휴리스틱 (예: 무작위 노이즈, 전문가 선택) 에 의존한다.
• 최적화 접근법: 부하 분산을 제약 조건이 있는 할당 문제로 공식화한다.
• 예시: DeepSeek 의 LPLB 시스템은 배치별 토큰 재분배를 선형 계획법 (LP) 으로 재구성한다. 이는 중복된 전문가 복제본의 용량 제약 하에서 GPU 당 최대 부하를 최소화한다.
• 결과: LP 는 내장된 GPU 솔버를 통해 약 100µs 내에 해결되어, 보조 손실의 간섭 그라디언트 없이 최적의 토큰 균형을 달성한다.

B. 데이터 병렬성에서의 요청 라우팅

• 현재 상태: KV 캐시 할당의 "고착" 특성과 디코드 단계의 불확실한 지속 시간을 무시하는 상태 비저장 (stateless) 디스패치 정책 (Round-Robin, Power-of-Two-Choices) 을 사용한다.
• 최적화 접근법: 배리어 동기화 제약이 포함된 온라인 정수 최적화 문제로 라우팅을 모델링한다.
• 예시: Chen et al. (2026) 은 "Balance-Future" 원칙을 제안한다. 전체 디코드 길이를 예측하는 대신 (이는 어렵다), 알고리즘은 짧은 시간 범위의 예측을 사용하여 미리보기 (lookahead) 창 동안 누적된 불균형을 최소화한다.
• 결과: 이론적 분석은 이 알고리즘이 적대적인 도착 시퀀스에서도 기본 정책에 비해 장기 평균 불균형을 $\Omega(\sqrt{B} \log G)$ 배 감소시킨다는 것을 증명한다.

C. 스케줄링 및 용량 계획

• 현재 상태: 대기 행렬 깊이에 기반한 워커 수 조정이 포함된 반응적 오토스케일링과 FCFS 스케줄링에 의존한다.
• 최적화 접근법: 폐쇄형 안정성 조건을 도출하기 위해 대기 행렬 이론을 적용하고, 입문 제어 (admission control) 를 위해 조합 최적화를 적용한다.
• 예시: Anonymous (2025) 는 연산 및 메모리 제약을 모두 고려한 안정성 조건을 유도하여 운영자가 배포 전에 최소 플릿 크기를 계산할 수 있게 한다. Jaillet et al. (2025) 은 LP 완화 (relaxations) 를 통해 하한을 설정하여 온라인 스케줄링 알고리즘을 벤치마크한다.
• 결과: 선제적 용량 계획은 런타임 불안정성을 방지하며, 특정 가정 하의 최적 스케줄링 정책 (예: Shortest-Job-First) 은 근사적으로 최적임이 증명될 수 있다.

D. 캐싱 및 교체

• 현재 상태: 이질적인 멀티모달 임베딩 크기와 재계산 비용의 변동을 무시하는 LRU 교체를 사용한다.
• 최적화 접근법: 히트율 최대화 문제가 아닌 비용 최소화 문제로 캐싱을 공식화한다.
• 예시: Zhu et al. (2023) 은 단위 크기당 비용에 접근 확률을 곱한 항목을 점수화하는 Least Expected Cost (LEC) 알고리즘을 도입한다.
• 결과: 이 접근법은 정보 이론이 허용하는 속도로 최적의 비용에 수렴하는 최적의 후회 (regret) 를 달성하며, 멀티모달 시나리오에서 최대 50 배의 비용 감소를 입증한다.

4. 결과 및 의의

본 논문은 단일 새로운 시스템을 제시하는 것이 아니라, 신흥 연구를 종합하여 원칙에 기반한 방법이 휴리스틱의 성능을 능가하거나 일치시키면서 휴리스틱이 제공할 수 없는 보장을 제공함을 입증한다.

주요 의의 주장:

1. 강건성: 증명 가능한 최악의 경우 한계 (예: 경쟁 비율) 를 가진 알고리즘은 평균 벤치마크에만 튜닝된 휴리스틱과 달리 적대적 워크로드나 분포 변화 하에서도 신뢰성을 보장한다.
2. 용량 계획: 이론적 분석은 폐쇄형 안정성 조건을 제공하여 배포 전 정밀한 리소스 할당을 가능하게 하고, 반응적 스케일링을 대체한다.
3. 엔지니어링 가이드: 최적 알고리즘을 직접 배포할 수 없더라도, 그 구조적 통찰 (예: 어떤 제약이 결합되는지) 은 효율적이고 강건한 휴리스틱 설계에 지침을 제공한다.
4. 새로운 연구 프론티어: LLM 서빙은 고전적 분산 시스템을 넘어 전용 알고리즘 연구가 필요한 새로운 문제 클래스 (예: 증가하는 메모리 제약이 있는 스케줄링, 고착된 할당이 있는 온라인 할당) 를 도입한다.

본 논문은 학제 간 참여를 촉구하며 마무리한다: 시스템 연구자는 근본적 한계를 발견하기 위해 최적화 이론을 이해해야 하며, 알고리즘 연구자는 이론적 모델이 실제 영향으로 전환되도록 시스템 제약에 참여해야 한다. 궁극적인 목표는 LLM 서빙을 위한 알고리즘 설계를 견고한 연구 프론티어로 취급하여, 해당 분야를 임시방편적 엔지니어링에서 수학적으로 기반을 둔 최적화로 전환하는 것이다.