Online Linear Programming for Multi-Objective Routing in LLM Serving

기술 요약: LLM 서빙을 위한 다중 목적 라우팅용 온라인 선형 계획법 (Online Linear Programming)

1. 문제 정의

본 논문은 대규모 언어 모델(LLM) 서빙 시스템에서 발생하는 온라인 요청 라우팅(online request routing) 문제를 다룹니다. 이러한 시스템에서는 유입되는 요청을 엄격한 제약 조건 하에 병렬 디코드 워커(parallel decode workers)로 분배해야 합니다:

• 시간 결합 제약 (Time-Coupled Constraints): 요청은 전체 디코드 기간 동안 자원(배치 슬롯 및 KV-캐시 메모리)을 지속적으로 소비합니다. 시간 $t$에 수락된 요청은 완료될 때까지 용량을 점유하며, 이는 복잡하고 시간 의존적인 자원 할당 문제를 생성합니다.
• 다중 목적 트레이드오프 (Multi-Objective Trade-offs): 시스템은 처리량(throughput), 종단 간 지연 시간(EEL), 첫 토큰 시간(TTFT), 꼬리 지연 시간(tail latency, 예: 99백분위수)을 포함한 상충하는 서비스 수준 목표(SLO) 사이의 균형을 맞춰야 합니다. 이러한 목적들은 서로 대립하는 경우가 많습니다. 예를 들어, 공격적인 배칭을 통해 처리량을 극대화하면 종종 지연 시간이 악화됩니다.
• 기존 휴리스틱의 한계: 기존의 프로덕션 시스템(예: vLLM)과 시뮬레이터(예: Vidur)는 Round-Robin, Join-Shortest-Queue (LOR), 또는 Power-of-$d$ 선택과 같은 휴리스틱에 의존합니다. 이러한 방법들은 명시적인 최적화 목적이 부족하고, SLO 트레이드오프에 대한 제어 능력이 제한적이며, LLM 디코드 길이의 이질적이고 불확실한 특성을 고려하지 못합니다.

2. 방법론

저자들은 LLM 라우팅을 온라인 선형 계획법(OLP) 문제로 정식화하고, 연산 효율적인 제어 정책을 도출하기 위해 운영 연구(operations research) 기법을 활용하는 프레임워크를 제안합니다.

A. 수학적 정식화

• 모델: 시스템은 병렬 디코드 장치들과 함께 이산 시간 지평(discrete time horizon) 상에서 모델링됩니다. 요청은 알려진 프리필(prefill) 발자국과 예측된(그러나 부정확할 수 있는) 디코드 길리를 가지고 순차적으로 도착합니다.
• 제약 조건: 정식화는 장치당 시간 단계별로 두 가지 핵심 제약 조건을 강제합니다:
  1. 배치 크기 (Batch Size): 활성 요청의 최대 수 ($B$).
  2. KV-캐시 용량 (KV-Cache Capacity): 활성 요청을 위한 최대 메모리 예산 ($M$).
• 목적 함수: 저자들은 각 라우팅 결정 $(j, g, k)$ (시간 $k$에 요청 $j$를 장치 $g$에 할당)에 대한 선형 보상 함수를 정의합니다. 이 보상은 다음의 가중 합계입니다:
  • 처리량 (처리된 토큰 수).
  • 음의 지연 시간 (EEL 및 TTFT 최소화).
  • 초당 쿼리 수 (QPS).
  • 꼬리 지표 (특정 지연 범위를 충족하는 요청에 대한 지시 함수(indicator rewards)를 통해 모델링됨).
  • 핵심 통찰: 꼬리 지연 시간과 같은 집계 지표는 지시 함수를 사용하여 개별 요청 인센티브로 분해되며, 이를 통해 선형 프레임워크 내에서 최적화가 가능해집니다.

B. 알고리즘 설계: 입찰 가격 제어 (Bid-Price Control)

매 밀리초마다 전체 OLP를 푸는 것은 계산적으로 불가능합니다. 대신, 저자들은 LP 쌍대성(duality)에 기반한 입찰 가격 제어(Bid-Price Control) 정책을 도출합니다.

1. 쌍대 변수 (Dual Variables/Shadow Prices): 쌍대 변수 $p_i$는 특정 시간과 장치에서의 자원(배치 슬롯 및 KV-캐시)의 "그림자 가격" 또는 기회 비용을 나타냅니다. 높은 그림자 가격은 예상되는 혼잡을 나타냅니다.
2. 의사 결정 규칙: 요청의 SLO 가중 혜택이 부과된 자원 비용(현재의 그림자 가격과 자원 사용 벡터의 내적으로 계산됨)을 초과하는 경우에만 요청을 수락합니다.
3. 온라인 학습 (SAA): 도착 및 예측의 확률적 특성을 처리하기 위해, 그림자 가격은 표본 평균 근사(Sample-Average Approximation, SAA) 방식을 사용하여 온라인으로 학습됩니다. 쌍대 목적 함수는 관찰된 행동의 이력을 바탕으로 최소화됩니다.
4. 효율적인 업데이트: 밀리초 단위의 결정 지연 시간을 충족하기 위해, 저자들은 **웜 스타트된 투영 미니 배치 경사 하강법(warm-started, projected mini-batch gradient descent)**을 채택합니다. 매 단계마다 처음부터 쌍대 문제를 푸는 대신, 알고리즘은 소량의 과거 데이터를 기반으로 가격 벡터를 점진적으로 업데이트합니다. 이는 예측 가능한 런타임(CPU에서 주기당 1~2ms)을 보장합니다.

3. 주요 기여

1. 다중 목적 최적화 프레임워크: 시간 결합된 배치 및 KV-캐시 제약 조건이 있는 OLP로 LLM 라우팅을 정식화한 최초의 프레임워크입니다. 이는 집계된 SLO(꼬리 지연 시간 포함)를 온라인 최적화에 적합한 개별 요청 보상으로 분해합니다.
2. 효율적인 입찰 가격 알고리즘: 매 단계마다 전체 LP를 풀지 않고도 진화하는 쌍대 그림자 가격을 온라인으로 추적하는 계산 가능한 정책을 제공하며, LLM 서빙의 엄격한 지연 시간 요구 사항을 충족합니다.
3. 해석 가능한 트레이드오프 제어: 이 프레임워크는 운영자에게 성능을 파레토 프런티어(Pareto frontier)를 따라 체계적으로 이동시킬 수 있는 투명한 "노브(knobs, 조절 손잡이)"인 목적 가중치를 제공합니다. 또한 그림자 가격은 배치 슬롯과 KV-캐시 중 무엇이 현재 병목 현상인지 식별하는 진단 도구로도 기능합니다.

4. 실험 결과

저자들은 자신들의 라우터를 Vidur 시뮬레이터에 통합하여 다양한 워크로드(실제 LMSYS-Chat-1M 데이터 및 합성 P/D 비율) 하에서 표준 베이스라인(Round-Robin, LOR, Random, Power-of-2)과 비교 평가했습니다.

• 성능 향상: 제안된 방법은 여러 SLO 체제에서 베이스라인 대비 상당한 개선을 보여주었습니다.
  • 노이즈가 있는 예측 시나리오(20% 오차)에서, 알고리즘은 Round-Robin 대비 평균 EEL을 45.75% 감소시키고 P95 EEL을 42.49% 감소시켰습니다.
  • 꼬리 지연 시간 지표(P99 EEL 및 TTFT)에서도 휴리스틱보다 월등한 성능을 보였습니다.
• 강건성 (Robustness): 정책은 불완전한 디코드 길이 예측 환경에서도 효과적이었는데, 이는 온라인 가격 업데이트가 추정 오차에 적응하기 때문입니다.
• 적응성: 비정상적 워크로드(갑작스러운 부하 급증) 상황에서도, 라우터는 이력 업데이트를 위한 롤링 윈도우 메커니즘을 사용하여 빠르게 적응하며 우수한 성능을 유지했습니다.
• 가중치 튜닝: 실험을 통해 목적 가중치를 조정함으로써 운영자가 특정 지표(예: 평균 지연 시간 최소화 vs. 엄격한 꼬리 지연 시간 제어)를 우선시할 수 있음을 확인했습니다.

5. 의의 및 주장

본 논문은 과학 기반의 최적화 접근 방식이 LLM 서빙의 휴리스틱 기반 라우팅보다 우수하다고 주장합니다.

• 커뮤니티 간의 가교: 본 연구는 운영 연구 커뮤니티(온라인 자원 할당, 입찰 가격 제어)와 LLM 시스템 커뮤니티 사이의 원칙적인 가교를 구축합니다.
• 시스템 설계 통찰: 이 프레임워크는 그림자 가격를 사용하여 자원 병목(배치 vs. 메모리)을 진단하고, 과부하 시 SLO 인식 입실 제어(admission control)를 가능하게 하는 구조적 통찰을 제공합니다.
• 실제 적용 가능성: 실제 프로덕션 통합은 향후 과제로 남겨두었으나, 결과는 최적화 기반 라우팅이 밀리초 규모에서 실행 가능하며, 임의적인 튜닝이 아닌 체계적인 정책 설계를 위한 토대를 제공함을 입증합니다.

저자들은 서빙 엔진(예: vLLM)과의 통합, 선점(preemption) 처리, 분산 환경에서의 협업과 같은 과제를 언급하며 즉각적인 프로덕션 배포에 대해서는 신중한 태도를 취하고 있습니다. 그러나 이 프레ver임워크가 운영 연구와 머신러닝 시스템의 접점에서 미래 연구를 위한 필수적인 기초를 제공한다고 주장합니다.