기술 요약: BlendServe

문제 정의

오프라인 배치 추론은 모델 평가 및 데이터 큐레이션과 같이 지연 시간(latency)에 민감하지 않은 대규모 언어 모델(LLM) 작업을 위한 비용 효율적인 솔루션으로 부상했습니다. 낮은 지연 시간을 우선시하는 온라인 추론과 달리, 오프라인 추론은 완화된 시간 창 내에서 처리량(초당 토큰 수)을 극대화하는 것을 목표로 합니다.

Chunked prefill(Sarathi-Serve)이나 연산자 수준의 오버래핑(NanoFlow, Orion)과 같은 기존의 처리량 최적화 기술은 단일 배치 내부에서 컴퓨트(compute)와 메모리 자원의 균형을 맞추는 데 집중합니다. 그러나 이러한 접근 방식은 애플리케이션의 다양성이 증가함에 따라 수익 체감의 법칙에 직면하게 됩니다. 현대의 LLM 워크로드는 매우 상이한 자원 요구 사항을 보입니다:

• 컴퓨트 집약적(Compute-intensive): 입력 시퀀스는 길지만 출력은 짧은 작업(예: 문서 요약, MMLU와 같은 벤치마크)은 GPU 컴퓨트 유닛을 포화시키는 반면 메모리 대역폭은 충분히 활용하지 못합니다.
• 메모리 집약적(Memory-intensive): 출력 시퀀스가 긴 작업(예: 비디오 생성, 추론)은 자기회귀 디코드(autoregressive decode) 단계에서 메모리 대역폭을 포화시키는 반면 컴퓨트 유닛은 충분히 활용하지 못합니다.

배치가 주로 한 가지 유형의 요청으로 구성될 때 하드웨어 자원은 불균형해지며, 이는 처리량을 제한합니다. 또한, 자원 오버랩을 극대화하기 위해 단순히 요청 순서를 재정렬하는 것은 프리픽스 공유(prefix sharing), 즉 공통된 프리픽스를 가진 요청들을 그룹화하여 중복 계산을 피하는 기술과 충돌할 수 있습니다. 프리픽스 공유를 극대화하는 순서(일반적으로 프리픽스 트리에 대한 깊이 우선 탐색, DFS)는 자원 오버랩을 극대화하는 순서와 달리 프리픽스 지역성(locality)을 파괴할 수 있습니다.

방법론: BlendServe

BlendServe는 **자원 인식 배치(resource-aware batching)**와 프리픽스 공유를 조화시켜 오프라인 추론 처리량을 극대화하도록 설계된 서빙 시스템입니다. 이 시스템의 핵심 설계는 세 가지 주요 구성 요소로 이루어집니다.

1. 성능 모델링 및 컴퓨트 밀도

BlendServe는 **컴퓨트 밀도($\rho$)**라는 지표를 도입하며, 이는 요청에 대한 메모리 집약적 연산 시간 대비 컴퓨트 집약적 연산의 비율로 정의됩니다.

• 요청 레벨: $\rho(r) = \frac{\text{Comp}(r)}{\text{Mem}(r)}$. 높은 $\rho$는 컴퓨트 집약적 워크로드를 나타내며, 낮은 $\rho$는 메모리 집약적 워크로드를 나타냅니다.
• 배치 레벨: 시스템은 전체 실행 시간 $T$를 컴퓨트 시간($T_{comp}$), 메모리 시간($T_{mem}$), 그리고 프리픽스 공유 비율($s$)의 함수로 모델링합니다. 목표는 중복 계산을 최소화하면서 컴퓨트 및 메모리 연산의 오버랩을 극대화하여 $T$를 최소화하는 것입니다.
• 출력 추정: 자기회귀 생성에서는 출력 길이를 알 수 없으므로, BlendServe는 워밍업(warm-up) 단계 동안 샘플링 전략을 사용합니다. 프롬프트의 의미론과 태스크 유형을 기반으로 출력 길이 분포를 추론하며, 샘플링된 요청을 사용하여 동일한 프리픽스 서브트리 내의 미샘플링된 요청의 밀도를 추정합니다.

2. 자원 인식 프리픽스 트리 (Resource-Aware Prefix Tree)

프리픽스 공유와 자원 오버랩 사이의 트레이드오프를 관리하기 위해, BlendServe는 자원 인식 프리픽스 트리를 구축합니다.

• 구조: 노드가 공유된 프롬프트 세그먼트를 나타내는 SGLang과 같은 시스템에서 사용되는 Trie 구조를 기반으로 합니다.
• 강화: 각 노드는 해당 서브트리에 속한 모든 요청의 컴퓨트 밀도 정보를 포함하도록 주석이 달립니다.
• 정렬 및 분할: 시스템은 각 레이어의 노드를 컴퓨트 밀도에 따라 정렬하여, 컴퓨트 집약적인 노드는 왼쪽에, 메모리 집약적인 노드는 오른쪽에 배치합니다. 전역적 순서를 방해하는 이상치(outlier)를 처리하기 위해 조건부 노드 분할(conditional node splitting) 기술이 사용됩니다. 노드의 밀도가 인접 노드와 크게 다를 경우, 해당 노드를 분할하고 재배치합니다. 이는 더 나은 자원 균형을 달성하기 위해 작은 프리픽스 세그먼트를 재계산하는 통제된 비용을 발생시킵니 다.

3. 듀얼 스캐닝 알고리즘 (Dual Scanning Algorithm)

최종 요청 스케줄을 생성하기 위해, BlendServe는 듀얼 스캐닝 알고리즘을 채택합니다.

• 메커니즘: 알고리즘은 정렬된 프리픽스 트리의 왼쪽(컴퓨트 집약적) 끝과 오른쪽(메모리 집약적) 끝에서 동시에 스캔을 수행합니다 트리의 루트와 일치하는 목표 전역 컴퓨트 밀도($\rho_{target}$)를 달려 맞추기 위해 필요한 메모리 파티션($M_L$ 및 $M_R$)을 동적으로 계산합니다. 양 끝에서 요청을 선택하여 이 파티션들을 채움으로써, 각 배치가 컴퓨트 집약적 요청과 메모리 집약적 요청의 균형 잡힌 혼합을 갖도록 보장합니다.
• 결과: 이 접근 방식은 프리픽스 구조(높은 프리픽스 공유 유지)를 보존하면서도 요청을 인터리빙(interleaving)하여 하드웨어 자원 오버랩을 극대화합니다.

4. 분산 배포

BlendServe는 데이터 병렬성(DP) 및 **텐서 병렬성(TP)**을 지원합니다.

• DP에서는 중앙 집중식 프리픽스 트리가 서로 다른 랭크(rank)에 할당되는 서브트리로 분해되어 균형 잡힌 워크로드를 보장합니다.
• TP에서는 시스템이 기존 파이프라인 전략과 통합되어 통신 오버헤드를 계산과 오버랩시키며, 대규모 배포에 대한 호환성을 유지합니다.

주요 기여

1. 워크로드 다양성 분석: 다양한 LLM 애플리케이션(채팅, 코딩, 비디오 생성)이 어떻게 상충하는 자원 요구 사항(컴퓨트 vs 메모리)을 생성하여 기존 배치 전략을 제한하는지에 대한 상세한 특성 분석을 제공합니다.
2. 자원 인식 프리픽스 트리: 프리픽스 구조를 보존하면서 컴퓨트 밀도를 인코딩하는 새로운 데이터 구조를 제안하여, 시스템이 프리픽스 공유와 자원 오버랩을 동시에 고려할 수 있게 합니다.
3. 듀얼 스캐닝 알고리즘: 정렬된 프리픽스 트리를 양 끝에서 스캔하여 배치를 구성하는 휴리스틱 스케줄링 알고리즘을 통해, 프리픽스 공유를 희생하지 않고 요청 유형을 효과적으로 혼합하여 자원 오버랩을 극대화합니다.
4. 프로토타입 및 평가: NanoFlow와 SGLang을 기반으로 구현된 풀 프로토타입을 통해 Llama-3-8B/70B, Qwen-2.5, DeepSeek 등 다양한 모델과 합성 워크로드에 대해 평가를 완료했습니다.

실험 결과

저자들은 BlendServe를 산업 표준 베이스라인(vLLM, SGLang) 및 최첨단 처리량 지향 시스템(NanoFlow)과 비교 평가했습니다.

• 처리량 향상:
  • vLLM 및 SGLang과 비교했을 때, BlendServe는 최대 1.44배의 처리량 향상을 달성했습니다.
  • 현재 최고 수준인 NanoFlow와 비교했을 때, BlendServe는 평균 20.84% 더 높은 처리량을 제공합니다.
• 최적성 격차 (Optimality Gap): BlendServe는 이론적 최적 처리량의 평균 86.55%(특정 설정에서는 최대 90%)에 도달하였으며, 이는 완벽한 자원 오버랩과 프리픽스 공유가 가능할 때의 한계치에 효과적으로 근접하고 있음을 입증합니다.
• 자원 활용도: 컴퓨트 및 메모리 사용량 시각화를 통해, Blend-Serve는 추론 단계 전반에 걸쳐 안정적이고 균형 잡힌 자원 활용을 유지하는 반면, NanoFlow-DFS와 같은 베이스라인은 상당한 변동과 자원 저활용 구간을 보임을 확인했습니다.
• 프리픽스 공유: 요청을 자원 균형을 위해 재정렬했음에도 불구하고, BlendServe는 표준 DFS 탐색이 달성할 수 있는 최대 프리픽스 공유 비율의 **97%**를 유지합니다.
• 확장성: 시스템은 데이터 병렬성(DP)에 따라 거의 선형적인 스케일링을 보여주며, 다양한 모델 크기(7B ~ 72B)와 하드웨어 구성에서도 효과적임을 입증했습니다.

의의 및 주장

본 논문은 BlendServe가 오프라인 배치 추론을 위해 특별히 최적화된 최초의 서빙 시스템으로서, 전통적으로 상충 관계에 있던 두 가지 목표인 자원 오버랩과 프리픽스 공유를 성공적으로 조화시켰다고 주장합니다.

저자들은 LLM 애플리케이션이 다양해짐에 따라 배치 내의 자원 요구 사항이 균일하다는 가정이 더 이상 유효하지 않다고 강조합니다. 오프라인 추론의 완화된 지연 시간 제약을 활용하여 요청 순서를 재정렬함으로써, BlendServe는 이전의 인트라 배치(intra-batch) 최적화 기술이 달성할 수 없었던 상당한 처리량 이득을 실현합니다. 이 시스템은 프리픽스 캐싱의 효율성을 희생하지 않으면서도 최적의 처리량(90%)에 도달할 수 있음을 보여주며, 비용 효율적이고 고처리량인 LLM 추론을 위한 강력한 솔루션을 제공합니다.