[Paper] LLM 서빙에서 Data-Parallel Load Balancing 병목 현상 해결: 대규모 실용적인 Online Routing

Source: arXiv - 2605.06113v1

개요

대규모 언어 모델(LLM) 서비스를 확장할 때 데이터‑병렬(DP) 부하 불균형이 점점 더 큰 제약이 되고 있다. 모델을 텐서 또는 전문가 병렬성을 사용해 GPU/NPU에 분할하고 이를 다수의 DP 워커에 복제하면, 각 디코드 단계가 가장 느린 워커를 기다려야 하므로 소중한 연산 사이클이 낭비된다. 이 논문은 BalanceRoute를 소개한다. 이는 온라인 라우팅 알고리즘군으로, 들어오는 요청을 DP 워커에 동적으로 할당하여 이 병목 현상을 크게 줄이며 실시간 생성의 100 ms 미만 지연 예산을 준수한다.

주요 기여

• BalanceRoute‑0 (BR‑0) – 요청을 허용했을 때 작업자가 안전 부하 한계 내에 머무를지 과부하 영역으로 들어갈지를 판단하기 위해 조각별 선형 “F‑score”를 사용하는 제로‑예측 라우팅 방식.
• BalanceRoute‑H (BR‑H) – 짧고 일정한 선행 전망 지평선 (H)와 가벼운 종료 분류기를 추가하여 무거운 예측 인프라 없이도 보다 정교한 결정을 가능하게 함.
• Two‑stage decomposition – 라우팅 문제를 빠른 단계별 필터와 더 세밀한 할당으로 나누어 단계별 오버헤드를 수 밀리초 수준으로 유지함.
• Real‑world deployment – 144‑NPU 클러스터에 구현하고, 독점 프로덕션 트레이스와 공개 Azure‑2024 트레이스 모두에서 평가하여 최신 vLLM 베이스라인 대비 일관된 처리량 향상을 보여줌.
• Open‑source‑ready design – 알고리즘은 현재 KV‑cache 크기, 작업자당 토큰 수 등 즉시 사용 가능한 런타임 메트릭에만 의존하므로 기존 서빙 스택에 쉽게 통합할 수 있음.

방법론

1. Problem framing – 저자들은 DP 로드 밸런싱을 온라인 할당 문제로 모델링합니다. 각 들어오는 요청은 스티키 할당을 가지고 (KV 캐시를 이동하는 것이 비용이 많이 듭니다) 디코딩이 진행됨에 따라 증가하는 부하를 가집니다.
2. F‑score formulation – 각 워커에 대해 알고리즘은 “안전 마진”(지연 시간이 디코드 예산 내에 머무는 부하 수준)을 초과할 할당에 대해 강하게 페널티를 부과하는 F‑점수를 계산합니다. 점수는 구간별 선형이며 빠른 평가가 가능합니다.
3. Two‑stage routing
   • Stage 1: 가벼운 필터가 안전 마진을 즉시 초과할 워커를 제외합니다.
   • Stage 2: 남은 후보 중에서 알고리즘은 가장 높은 F‑점수를 가진 워커를 선택합니다 (BR‑H의 경우 가장 높은 horizon‑discounted 점수를 선택).
4. Horizon extension (BR‑H) – 고정된 미래 디코드 단계 수((H))를 미리 살펴봄으로써 라우터는 부하 증가를 예측하고 몇 단계 뒤에 문제가 될 할당을 피할 수 있습니다. 작은 분류기가 요청이 수평선 내에 완료될지를 예측하여 할인된 점수에 반영합니다.
5. Implementation details – 라우팅 로직은 서빙 시스템의 요청 스케줄러 내부에서 실행되며, 각 토큰 생성 후 워커별 부하 카운터를 업데이트합니다. 모든 계산은 정수 기반이며 수백 개의 대기 요청을 처리하더라도 100 ms 미만 디코드 창 안에 들어갑니다.

결과 및 발견

• 독점 프로덕션 트레이스에서 BalanceRoute는 평균 DP 부하 분산을 70 % 감소시키고 전체 처리량을 27 % 향상시켰습니다.
• Azure‑2024 공개 트레이스에서는 개선폭이 더 커서 (분산 58 % 감소, 처리량 35 % 증가), 다양한 요청 패턴에서도 견고함을 확인했습니다.
• 라우팅 오버헤드는 스케줄링 라운드당 1 ms 이하로 유지되어 제한된 디코드 예산을 보존했습니다.

Practical Implications

• Higher utilization of expensive hardware – 모든 DP 워커를 비슷한 부하 수준으로 유지함으로써 클라우드 제공업체와 기업은 동일한 NPU/GPU 군에서 더 많은 추론 처리량을 끌어낼 수 있어, 생성된 토큰당 비용을 낮출 수 있습니다.
• Reduced tail latency – 시스템이 단일 과부하 워커에 멈추지 않기 때문에, 특히 트래픽 급증 시 최종 사용자는 더 부드러운 응답 시간을 경험합니다.
• Plug‑and‑play integration – BalanceRoute는 런타임 부하 카운터와 작은 분류기만 필요하므로, 모델 병렬화 레이어를 재설계하지 않고도 기존 서빙 프레임워크(e.g., vLLM, TensorRT‑LLM, DeepSpeed‑Inference)에 추가할 수 있습니다.
• Scalable to larger clusters – 알고리즘의 단계별 복잡도는 워커 수에 대해 선형이므로, 수백 대의 장치를 갖는 클러스터에도 적합합니다. 이는 LLM API에서 흔한 상황입니다.
• Foundation for adaptive QoS – F‑score를 우선순위나 SLA 가중치와 결합하도록 확장하면 차별화된 서비스 수준을 제공할 수 있습니다(예: 프리미엄 사용자는 덜 부하된 워커로 라우팅됨).

제한 사항 및 향후 연구

• Sticky KV‑cache 가정 – 이 접근법은 KV 캐시를 이동하는 것이 비용이 많이 든다고 가정합니다; 향후 하드웨어 또는 소프트웨어 혁신(예: 빠른 캐시 마이그레이션)이 이 트레이드오프를 바꿀 수 있습니다.
• 고정된 horizon (H) – BR‑H는 일정한 선행 탐색을 사용합니다; 요청 길이 또는 시스템 부하에 기반한 적응형 horizon은 의사결정을 더욱 향상시킬 수 있습니다.
• 디코드 전용 워크로드에 제한 – 이 논문은 토큰 단위 생성에 초점을 맞춥니다; 라우팅 로직을 혼합 인코드‑디코드 또는 배치 단위 추론으로 확장하는 것은 아직 미해결 과제입니다.
• 단일 하드웨어 계열에 대한 평가 – 실험은 144‑NPU 클러스터에서 수행되었습니다; GPU 중심 클러스터나 이종 환경에서 알고리즘을 검증하면 일반성을 강화할 수 있습니다.

전반적으로 BalanceRoute는 LLM 서비스에서 가장 시급한 확장성 문제 중 하나에 대한 실용적이고 낮은 오버헤드의 솔루션을 제공하며, 그 개념은 차세대 추론 플랫폼에서 추가 탐구가 활발히 이뤄질 수 있습니다.

저자

• Tianci Bu
• Yuan Lyu
• Zixi Chen
• Chendong Song
• Hong Liang
• Tsepten Gurung
• Yuwei Fan
• Yinyu Ye
• Zijie Zhou

논문 정보

• arXiv ID: 2605.06113v1
• 분류: cs.DC
• 발표일: 2026년 5월 7일
• PDF: PDF 다운로드