LLM Serving Optimization with Variable Prefill and Decode Lengths

기술 요약: 가변적 프리필(Prefill) 및 디코드(Decode) 길이를 고려한 LLM 서빙 최적화

문제 정의
본 논문은 고정된 키-값(KV) 캐시 메모리 예산을 가진 단일 컴퓨팅 워커에서의 대규모 언어 모델(LLM) 추론을 위한 오프라인 스케줄링 문제를 다룹로다. 시스템은 $t=0$ 시점에 동시에 도착하는 $n$개의 요청 백로그를 처리합니다. 각 요청 $i$는 이질적인 프롬프트 길이(프리필 크기, $s_i$)와 응답 길이(디코드 크기, $o_i$)의 특성을 가집니다.

핵심 과제는 자기회귀적 디코딩(autoregressive decoding) 과정 중 발생하는 동적인 메모리 소비량에서 비롯됩니다. 프리필 단계는 $s_i$에 비례하는 메모리를 소비하는 반면, 디코드 단계는 생성되는 토큰마다 메모리 사용량이 선형적으로 증가합니다($j$번째 토큰에 대해 $s_i + j$). 결과적으로, 워커가 처리할 수 있는 동시 요청 수는 활성 요청들의 생성 진행 상태에 따라 동적으로 변동합니다. 목표는 임의의 타임스텝에서 집계된 메모리 사용량이 용량 $M$을 초과하지 않아야 한다는 제약 조건 하에, 총 종단 간 지연 시간(Total End-to-End Latency, TEL, 모든 요청의 완료 시간의 합)을 최소화하는 것입니다.

본 논문은 선행 연구(Jaillet et al., 2025)에서 발견된 균일한 입력 크기 가정을 완화하여, 짧은 대화형 프롬프트와 긴 문서 요약 작업이 혼합된 현실적인 시나리오를 고려합니다.

이론적 발견 및 과제
본 논문은 균일한 입력 크기 가정을 완화하는 것이 스케줄링 문제의 복잡성을 근본적으로 변화시킨다는 점을 입증합니다:

1. NP-난해성(NP-Hardness): 이질적인 $s_i$와 $o_i$를 가진 일반화된 스케줄링 문제는 제한된 3-파티션(3-Partition) 문제로의 환원을 통해 NP-난해임을 증명하였습니다.
2. 표준 휴리스틱의 실패: FCFS(First-Come-First-Served), MC-SF(Shortest-Output-First), 그리고 총 크기 기반 우선순위 지정(Total-Size-Based prioritization)을 포함한 표준 정책들은 이러한 이질적 환경에서 유계되지 않은 근사 비율(unbounded approximation ratios)을 갖는 것으로 나타났습니다. 구체적으로, 입력은 크지만 출력은 작은 요청은 일시적으로 상당한 메모리를 소비할 수 있는 반면, 입력은 작지만 출력이 긴 요청은 장기간 메모리를 점유할 수 있어, 단순한 휴리스틱으로는 해결할 수 없는 트레이드오프를 생성합니다.

방법론: Sorted-F 알고리즘
이러한 과제를 해결하기 위해 저자들은 상수 인자 근사 보장(constant-factor approximation guarantee)을 달성하도록 설계된 스케줄링 알고리즘인 Sorted-F를 제안합니다. 이 알고리즘은 두 단계로 작동합니다:

1. 배치 구성 (Phase 1): 알고리즘은 순서가 있는 리스트를 형성하기 위해 실행 가능한 요청 배치를 반복적으로 선택합니다. 선택은 요청 집합 $X$에 대해 다음과 같이 정의된 새로운 품질 지표 $F(X)$에 의해 유도됩니다:
   $$F(X) = \frac{\sum_{r_i \in X} o_i}{|X|^2}$$
   이 지표는 배치 크기($|X|$)와 집계된 다운스트림 디코드 비용($\sum o_i$) 사이의 균형을 맞춥니다. $F(X)$를 최소화하는 것은 "처리량 밀도"(평균 디코드 시간당 완료되는 요청 수)를 최대화하는 것과 같습니다. 선택된 각 배치 내에서 요청들은 비내림차순 출력 길이에 따라 정렬됩니다.
2. 실행 (Phase 2): 시스템은 이산 타임스텝에 따라 스케줄을 실행하며, 연속 배칭(continuous batching)과 프리필/디코드 혼합을 활용하여 메모리 실행 가능 제약 조건을 만족하는 한 순서 리스트로부터 요청을 현재 배치로 수용합니다.

근사 보장
저자들은 Sorted-F가 최적의 오프라인 스케줄 대비 최대 48의 상수 근사 비율을 달라는 것을 증명했습니다. 이 증명은 Sorted-F 스케줄과 최적 스케줄을 비교 가능한 형태로 변환하는 일련의 구조적 변환(분리, 그룹화, 정렬)을 포함하며, 각 단계에서의 지연 시간 증가가 상수 인자에 의해 제한됨을 보여줍니다.

실제 구현
Phase 1에서 요구되는 조합 최적화가 큰 $n$에 대해 계산적으로 비용이 많이 들다는 점을 인식하여, 본 논문은 세 가지 실용적인 솔버를 제안합니다:

• 정밀 동적 계획법 (Exact Dynamic Programming): $O(n^2 M)$ 복잡도로 작은 인스턴스($n \le 100$)에 대해 정확한 해를 제공합니다.
• 로컬 스왑 탐색 (Local Swap Search): 중간 규모($n \le 500$)를 위한 휴리스틱으로, 쌍별 교환(pairwise exchanges, $O(n^2)$)을 통해 초기 그리디 해를 반복적으로 개선합니다.
• 분위수 그리디 선택 (Quantile Greedy Selection): 대규모 시스템($n \ge 1000$)을 위한 선형 시간 휴리스틱으로, 통계적 샘플링을 사용하여 이상치를 필터링하고 용량을 그리디하게 채웁니다.

또한, 요청의 순서를 정하기 위해 문제의 선형 계획법(LP) 완화 해를 활용하는 휴리스틱인 Sorted-LP와, 추론 중 출력 길이 예측의 불확실성을 처리하기 위해 추정치를 동적으로 정교화하는 적응형 변형인 Sorted-F+Amin을 도입합니다.

실험 결과
혼합 워크로드(LMSYS-Chat 데이터셋과 Arxiv 롱 도큐먼트 요약을 결합)에 대한 수치 실험 결과는 다음과 같습니다:

• 지연 시간 감소: Sorted-F(Local Swap Search 사용)는 FCFS, MC-SF, LP 가이드 베이스라인보다 일관되게 우수한 성능을 보였습니다. 2000개의 요청이 있는 80/20 단기/장기 혼합 환경에서, Sorted-F는 FCFS 대비 4.87배, MC-SF 대비 2.09배 평균 지연 시간을 감소시켰습니다.
• 최적성 갭 (Optimality Gap): 다룰 수 있는 인스턴스에서 Sorted-F와 LP 완화 하한값 사이의 경험적 갭은 작았으며(약 1.03–1.09), 이는 알고리즘이 느슨한 이론적 경계에도 불구하고 실제로는 최적에 가깝게 작동함을 시사합니다.
• 워크로드 민감도: Sorted-F의 이점은 메모리가 구속 조건이 되는 이질적이고 과부하된 영역에서 가장 두드러집니다. 균일하거나 부하가 적은 영역에서는 그 이점이 줄어듭니다.
• 온라인 성능: 포아송 도착(Poisson arrivals) 하에서 테스트된 재귀적 지평(receding-horizon) 변형(Sorted-F-Online)은 과부하된 온라인 영역에서 MC-SF 및 FCFS보다 상당한 개선을 보였으나, 안정적이고 저지연인 영역에서는 이점이 적었습니다.

의의 및 주장
본 논문은 가변적인 프리필 길이가 단순한 모델링의 세부 사항이 아니라, 표준 스케줄링 휴리스틱을 무력화하고 문제를 NP-난해로 만드는 근본적인 요인이라고 주장합니다. 주요 기여는 이질적인 입력/출력 제약 조건 하에서 LLM 스케줄링에 대한 최초의 상수 인자 근사 보장을 제공하는 Sorted-F 알고리즘입니다. 이 연구는 이론적 스케줄링 한계와 실제 LLM 서빙 사이의 간극을 메우며, 출력 길이에 대한 완벽한 예측 없이도 혼합 워크로드 시나리오에서 지연 시간을 크게 줄일 수 있는 확장 가능한 메모리 인식 프레임워크를 제공합니다. 저자들은 이론적 경계는 48이지만, 경험적 결과는 알고-리즘이 현실적인 설정에서 최적해에 훨씬 더 가깝다는 것을 보여준다고 강조합니다.