기술 요약: 정확도와 비용을 넘어: 동적 워크로드를 위한 지연 시간 인지형 LLM 쿼리 라우팅

문제 정의

현대의 언어 쿼리 라우터는 서로 다른 대규모 언어 모델(LLM) 인스턴스에 쿼리를 할당함으로써 응답 품질(정확도)과 금전적 비용 사이의 트레이드오프를 최적화합니다. 그러나 기존의 라우터들은 대체로 **지연 시간에 무관(latency-agnostic)**합니다. 이들은 정확도 및 비용 예측 모델을 기반으로 모델을 선택하지만, 특정 모델 인스턴스에서 쿼리가 경험하게 될 생성 지연 시간은 무시합니다.

실제로 지연 시간은 라운드 로빈(round-robin), 최단 큐 조인(join-the-shortest-queue)과 같은 시스템 수준의 부하 분산 정책에 의해 결정되는데, 이러한 정책들은 모델의 정확도나 추론 비용을 고려하지 않습니다. 반대로, 시스템 수준의 지연 시간 최적화는 고정된 쿼리-모델 할당을 가정하며 정확도-비용 트레이드오프를 무시합니다. 이로 인해 간극이 발생합니다. 즉, 현재의 라우터는 과부하된 인스턴스로 쿼리를 라우팅하여 긴 큐잉 지연을 유발하고 서비스 수준 목표(SLO)를 위반할 수 있는 반면, 시스템 수준의 최적화 도구는 모델 풀의 이질적인 정확도-비용 역량을 활용할 수 없습니다.

핵심 과제는 **생성 지연 시간이 비결정적(non-deterministic)**이며 다음 요소들에 의존한다는 점입니다:

1. 하드웨어 사양 및 모델 아키텍처.
2. 인스턴스의 현재 워크로드 구성 (프리필(prefill) 대 디코드(decode) 단계).
3. 서빙 프레임워크(예: vLLM, Sarathi-Serve)의 배치 및 스케줄링 정책.

새로 들어오는 쿼리의 **첫 번째 토큰 생성 시간(TTFT)**을 정확하게 추정하는 것은 어렵습니다. 왜냐에는 새로운 쿼리를 기존의 상주 시퀀스들과 어떻게 배치(batching)할 것인지 시뮬레이션해야 하며, 이 과정에서 프리필(연산 집약적)과 디코드(메모리 집약적) 간의 간섭을 모두 고려해야 하기 때문입니다.

방법론

저자들은 정확도, 비용, 지연 시간을 공동으로 최적화하는 라우팅 프레임워크를 제안합니다. 이 시스템은 세 가지 주요 구성 요소로 이루어져 있습니다.

1. 라우팅 목적 함수

라우터는 TTFT 제약 조건($\tau_i$)을 만족하면서 정확도-비용 효용(utility, $\hat{U}_{i,j}$)을 극대화하도록 모델 인스턴스 $m(i)$를 선택합니다.

• 효용: $\hat{U}_{i,j}(\lambda) = \hat{acc}_{i,j} - \lambda \cdot \hat{cost}_{i,j}$, 여기서 $\lambda$는 품질과 비용의 균형을 맞춥니다.
• 제약 조건: 선택된 인스턴스는 $\hat{L}^{ttft}_{i,j}(t) \leq \tau_i$를 만족해야 합니다. 만약 제약 조건을 만족하는 인스턴스가 없다면, 라우터는 추정 지연 시간이 가장 짧은 인스턴스를 선택합니다.
• 평가: 성능은 지연 시간 제약을 충족한 쿼리의 효용을 평균 내는 OnTimeUtility를 통해 측정됩니다 (제약을 위반한 경우 효용을 0으로 처리).

2. 서빙 프레임워크 시뮬레이션(SFS) 지연 시간 추정기

실시간 실행 없이 TTFT를 정확하게 예측하기 위해, 저자들은 서빙 프레임워크의 동작을 시뮬레이션하는 경량 추정기를 설계했습니다.

• 입력: 추정기는 현재 모델 인스턴스의 상태(상주 요청 세트 $R_j(t)$, 남은 프리필 토큰 수, 예측된 디코드 길이 포함)를 사용합니다.
• 시뮬레이션 과정:
  1. 새 쿼리와 모든 상주 쿼리를 포함하는 확장된 워크로드를 구성합니다.
  2. 결정론적으로 서빙 프레임워크의 연속 배치(continuous batching) 및 스케줄링 정책을 시뮬레이션하여 토큰 배치를 형성합니다.
  3. 새 쿼리가 첫 번째 디코드 토큰을 생성할 때까지 이 배치들을 반복 수행합니다.
• 토큰-배치 처리 시간 모델: 저커널(low-level kernel)을 직접 시뮬레이션하는 대신, 추정기는 보정된 선형 모델(식 9)을 사용하여 각 토큰 배치의 시간을 예측합니다. 이 모델은 다음을 고려합니다:
  • 고정 오버헤드.
  • 토큰 단위의 밀집 레이어(dense-layer) 연산 (배치 크기에 비례).
  • 어텐션 연산 및 KV 캐시 읽기 (디코드 시 컨텍스트 길이에 비례).
  • 프리필 어텐션 비용 (프리필 청크 내에서 이차 함수적으로 증가).
• 출력: 첫 번째 디코드 토큰까지 시뮬레이션된 모든 배치의 예측 처리 시간의 합이 TTFT 추정치가 됩니다.

3. 평균 사례 추정 (실시간 데이터가 없는 경우)

실시간 워크로드 스냅샷을 사용할 수 없는 시나리오(예: 제3자 클라우드로 라우팅하는 경우)를 위해, 저자들은 제한된 프로세서 공유(Limited Processor Sharing, LPS) 모델을 사용하는 큐잉 이론적 추상화를 제안합니다. 이는 인스턴스를 최대 $k$개의 동시 쿼리를 공유하는 서버로 모델링하고, 나머지는 FIFO 큐에서 대기하도록 합니다. 이를 통해 도착률과 서비스 용량을 기반으로 평균 대기 시간을 추정할 수 있습니다.

주요 기여

1. 공동 최적화 프레임워크: 본 논문은 라우터가 세 가지 지표를 동시에 기반으로 의사결정을 내리도록 설계함으로써, 정확도-비용 라우팅과 시스템 수준의 지연 시간 최적화 사이의 간극을 메웁니다.
2. 경량 SFS 추정기: 저자들은 자기 회귀적(autoregressive) 토큰 배치 처리를 시뮬레이션하는 새로운 지연 시간 추정기를 도입했습니다. 이는 전체 실행 없이도 프리필과 디코드 워크로드, 그리고 서빙 프레임워크 정책(예: 청크형 프리필) 간의 복잡한 상호작용을 포착합니다.
3. 높은 정확도 및 낮은 오버헤드: SFS 추정기는 TTFT 예측에 대해 5% 미만의 평균 절대 백분율 오차(MAPE)를 달-성하며, 테스트 시 오버헤드는 약 0.14 ms(1밀리초 미만)로 매우 낮아 라우팅의 핵심 경로에서 사용하기 적합합니다.
4. 강건성(Robustness): 본 프레임워크는 표준 포아송 도착(Poisson arrivals) 및 변동성이 큰 마르코프 변조 포아송 프로세스(MMPP) 도착 환경 모두에서 평가되었으며, 일관된 성능 향상을 입증했습니다.

실험 결과

저자들은 H100 GPU에 vLLM 서빙 프레임워크로 배포된 세 가지 Qwen3 모델(0.6B, 8B, 32B)을 사용하여 접근 방식을 평가했습니다. 이들은 SFS 기반 라우터를 다음 세 가지 베이스라인과 비교했습니다:

• 라운드 로빈(Round Robin): 워크로드를 무시하고 순환적으로 할당.
• 최단 큐(Shortest Queue): 요청 수가 가장 적은 인스턴스에 할당 (지연 시간에 집중하나 정확도에는 무관함).
• 지연 시간 무관(Latency-Agnostic): 지연 시간을 무시하고 효용을 극대화.

주요 결과:

• 효용 개선: 제안된 방법은 동일한 지연 시간 제약을 유지하면서 표준 부하 분산 베이스라인(예: 최단 큐) 대비 정확도-비용 효용을 최대 40% 향상시켰습니다.
• OnTimeUtility: 다양한 쿼리 도착률에 걸쳐, SFS 라우터는 최상의 베이스라인보다 **33% 더 높은 OnTimeUtility 곡선 아래 면적(AUC)**을 달성했습니다.
• 트레이드오프 제어: 라그랑주 완화(Lagrangian relaxation)의 지연 시간 페널티 파라미터 $\delta$를 조절함으로써, 라우터는 효용과 지연 시간 사이의 제어 가능한 트레이드오프 곡선을 제공하며, 이러한 균형을 효과적으로 맞추지 못하는 베이스라인들을 능가합니다.
• 추정기 성능: 디코드 간섭을 무시하는 처리량 기반 베이스라인은 85%의 MAPE를 보인 반면, SFS 추정기는 이를 **5%**로 낮추어 전체 서빙 프레임워크 역학을 시뮬레이션하는 것의 필요성을 입증했습니다.

의의 및 주장

본 논문은 동적인 워크로드 환경에서 효율적인 LLM 배포를 위해 정확도, 비용, 지연 시간의 공동 최적화가 필수적이라고 주장합니다. 저자들은 기존의 라우터들이 지연 시간을 모델 선택과 별개의 시스템 수준 문제로 취급하기 때문에 최적의 자원 활용을 방해하고 SLO를 위반한다고 설명합니다.

경량 시뮬레이션 기반 지연 시간 추정기를 라우팅 결정에 직접 통합함으로써, 제안된 프레임워크는 강력한 정확도-비용 성능을 유지하면서도 과부하된 인스턴스를 피할 수 있습니다. 이 연구는 "스마트 라우팅"(정확도/비용)과 "부하 분산"(지연 시간)이라는 이전에 분리되어 있던 목표를 효과적으로 통합하여, 지연 제약을 희생하지 않고도 상당한 효용 증대(최대 40%)를 달 수 있음을 보여줍니다. 저자들은 이를 쿼리 워크로드가 동적이고 SLO가 엄격한 실제 배포 환경을 위한 실질적인 솔루션으로 제시합니다.