💻 computer science

Beyond Prediction: Tail-Aware Scheduling for LLM Inference

이 논문은 소프트 우선순위 부스팅(soft priority boosting)과 캐시 인지형 선점(cache-aware preemption)을 사용하여 LLM 추론의 꼬리 지연 시간(tail latency)과 첫 번째 토큰 생성 시간(time-to-first-token)을 크게 단축함으로써, 버스트형 도착(bursty arrivals) 및 GPU 메모리 압박과 같은 까다로운 조건에서도 기존의 예측 기반 정책보다 뛰어난 성능을 보이는 분포 인지형, 예측 불필요 스케줄링 프레임워크를 소개한다.

원저자: Yueying Li, Yuanfan Chen, Jiayang Chen, Esha Choukse, Haoran Qiu, G. Edward Suh, Rodrigo Fonseca, Ziv Scully, Udit Gupta

게시일 2026-06-19

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yueying Li, Yuanfan Chen, Jiayang Chen, Esha Choukse, Haoran Qiu, G. Edward Suh, Rodrigo Fonseca, Ziv Scully, Udit Gupta

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

바쁜 레스토랑 주방을 상상해 보세요. 요리사들(GPU)이 고객들(AI 요청)을 위해 음식을 만들고 있습니다. 어떤 주문은 간단합니다. "그냥 물 한 잔 주세요"(짧은 채팅 메시지). 또 다른 주문은 복잡합니다. "상세한 줄거리가 포함된 50페이지 분량의 소설을 설계해 줘"(긴 추론 작업).

문제는 주방 매니저가 주문이 거의 끝날 때까지 각 주문이 얼마나 걸릴지 알 수 없다는 점입니다. "물 한 잔"이 "코스 요리"로 변할 수도 있습니다. 고객이 계속해서 추가 요청을 할 수 있기 때문입니다.

기존 방식: 미래를 예측하기

현재의 주방 매니저들은 효율성을 높이기 위해 각 주문이 얼마나 걸릴지 예측하려고 노력합니다. 그들은 "최단 작업 우선(Shortest Job First, SJF)"이라는 전략을 사용합니다.

논리: "이 주문은 금방 끝날 것 같으니, 먼저 요리해서 테이블에서 치워버리자."
결함: 만로 매니저가 예측을 틀리면(복잡한 AI 작업에서는 자주 발생합니다), 빠른 주문이 지연되고, 짧을 것이라 예상했던 긴 주문이 영원히 화구를 독점하게 됩니다.
결과: 평균 대기 시간은 괜찮아 보일지 모르지만, 최악의 경우 대기 시간(꼬리 지연 시간, tail latency)은 엉망이 됩니다. 어떤 고객은 몇 초 만에 음식을 받지만, 어떤 고객은 몇 시간 동안 기다려야 합니다. 이는 사용자 경험에 좋지 않습니다.

새로운 방식: "부스트(Boost)" 시스템 (UNIBOOST)

이 논문의 저자들은 예측하는 대신 관찰하는 새로운 매니저를 제안합니다. 그들은 이 시스템을 UNIBOOST라고 부릅니다.

작동 원리는 다음과 같습니다.

1. "소프트 부스트 (Soft Boost)" (수정구슬은 필요 없다)

미래를 예측하는 대신, 새로운 매니저는 모든 주문에 시간이 흐름에 따라 부드럽게 변하는 "우선순위 점수"를 부여합니다.

비유: 놀이기구를 기다리는 사람들의 줄을 상상해 보세요. 새로운 매니저는 "당신은 어디까지 가나요?"라고 묻지 않습니다. 대신 이렇게 말합니다. "기다린 시간이 길어질수록, 당신의 티켓에는 우선순위 '부스트'가 조금씩 더해집니다."
도움이 되는 이유: 짧은 주문은 먼저 도착했기 때문에 빠르게 처리됩니다. 하지만 긴 주문이 한참을 기다리고 있다면, 이 시스템은 그 주문에 부드러운 밀어주기를 하여 끊임없이 밀려드는 새로운 짧은 주문들 뒤에 갇혀버리지 않도록 합니다. 이는 긴 대기 시간을 가진 고객들이 영원히 기다리는 것을 방지합니다.

2. "메모리 가드 (Memory Guard)" (팬을 낭비하지 마라)

AI에서 음식을 요리하려면 많은 메모리(KV 캐시)가 필요합니다. 만약 중간에 요리를 멈추고 새로운 요리로 전환한다면, 방금 준비한 재료를 모두 버리고 처음부터 다시 시작해야 합니다. 이는 비용이 많이 들고 느립니다.

비유: 요리사가 거대한 케이크를 굽는 도중이라고 상상해 보세요. 이때 매니저가 "멈춰! 대신 쿠키를 구워!"라고 외친다면, 요리사는 케이크 반죽을 팬에서 긁어내고, 팬을 씻고, 다시 쿠키를 시작해야 합니다. 그리고 다시 케이크로 돌아가려면 팬을 또 씻어야 합니다.
해결책: 새로운 매니저는 "메모리 가드"를 사용합니다. 그들은 이렇게 말합니다. "일단 케이크를 만들기 시작했다면, 작업을 전환하기 전에 적어도 케이크의 '한 조각'은 완성해야 한다." 이는 주방이 너무 자주 작업을 전환하여 시간을 낭비하는 것을 방지합니다.

3. "적응형 온도 조절기 (Adaptive Thermostat)"

주방의 조건은 변합니다. 때로는 작은 주문들이 몰려오기도 하고, 때로는 몇 개의 거대한 주문이 들어오기도 합니다.

비유: 매니저는 사람들이 실제로 얼마나 오래 기다리는지 관찰하는 스마트 온도 조절기를 가지고 있습니다. 줄이 너무 길어지면, 매니저는 가장 오래 기다린 사람들을 돕기 위해 "부스트" 설정을 더 공격적으로 자동 조정합니다. 수정구슬 없이도 실시간으로 학습하는 것입니다.

결과

이 논문은 실제 데이터(코딩 작업 및 채팅 대화 등)를 사용하여 이 새로운 시스템을 기존의 "예측형" 시스템들과 테스트했습니다.

기존 시스템들: 작업량이 급증할 때(bursty), "예측형" 시스템들은 실패했습니다. 최악의 경우 대기 시간(P99)이 엄청나게 늘어났습니다.
새로운 시스템 (UNIBOOST): 이 시스템은 단순히 평균 대기 시간을 개선했을 뿐만 아니라, 최악의 대기 시간을 획기적으로 줄였습니다.
- "완벽한 예측" 시스템과 비교했을 때 최악의 대기 시간(P99)을 **35%에서 50%**까지 단축했습니다.
- 첫 번째 토큰이 나타나는 시간(TTFT)을 34%에서 47% 더 빠르게 만들었습니다.

핵심 요약

이 논문은 AI 작업이 얼마나 걸릴지 예측하려는 시도는 취약하며 자주 틀린다는 점을 주장합니다. 대신, 작업을 너무 자주 전환하여 메모리를 낭비하지 않으면서, 작업이 얼마나 오래 기다렸는지에 따라 반응하는 시스템이 모두에게 훨씬 더 공정하고 빠른 경험을 만들어냅니다. 이것은 목적지를 예측하는 것이 아니라, 줄의 흐름을 관리하는 것에 관한 문제입니다.

기술 요약: 예측을 넘어: LLM 추론을 위한 테일 인식 스케줄링 (Beyond Prediction: Tail-Aware Scheduling for LLM Inference)

1. 문제 정의

대규모 언어 모델(LLM) 서빙은 요청 길이의 극심한 가변성을 관리하는 데 있어 결정적인 과제에 직면해 있습니다. 특히 다단계 생성, 자기 성찰(self-reflection), 적응형 종료(adaptive termination)를 보이는 추론 증강 모델의 부상으로 인해 이러한 가변성은 더욱 심화되고 있습니다. 이러한 가변성은 크기 기반 스케줄링 정책(예: Shortest Job First - SJF, 또는 Shortest Remaining Processing Time - SRPT)을 취약하게 만듭니다.

현재의 최첨단 스케줄러들은 출력 길이 또는 남은 토큰 수를 예측하여 SJF/SRPT를 근사화하려고 시도합니다. 그러나 본 논문은 이러한 접근 방식에서 세 가지 근본적인 문제를 식별합니다:

예측의 취약성 (Prediction Fragility): 출력 길이 예측은 토큰 생성의 높은 가변성(확률성 및 비결정론적 특성)으로 인해 본질적으로 어렵습니다. 이로 인해 정책이 분포 변화(distribution shifts)와 돌발적인 유입(bursty arrivals) 상황에서 매우 취able해집니다.
지표 불일치 (Metric Mismatch): 평균 지연 시간(예: 평균 TTFT/TBT)에 최적화된 정책은 종종 열악한 테일 레이턴시(P90–P99) 성능을 보입니다. LLM 서빙에서 사용자 경험은 서비스 수준 목표(SLO)의 구속 조건이 되는 경우가 많은 테일 레이턴시(Time-To-Last-Token, TTLT)에 의해 결정됩니다.
메모리 결합 역학 (Memory-Coupled Dynamics): 고전적인 큐와 달리, LLM 추론은 상태 유지(stateful) 방식입니다. 요청들은 디코딩 과정에서 거대한 키-값(KV) 캐시를 축적합니다. 짧은 작업을 우선시하기 위한 나이브한 선점(preemption)은 값비싼 캐시 제거, 재계산, 그리고 "스래싱(thrashing)"을 유발하여, 큐잉 지연을 줄임에도 불구하고 오히려 테일 레이턴시를 증가시킬 수 있습니다.

본 논문이 제기하는 핵심 질문은 "스케줄러가 테일 레이턴시를 최적화하기 위해 명시적인 작업 길이 예측이 반드시 필요한가?"입니다. 저자들은 예측 없이도 가능한, 분포 인식형(distribution-aware) 접근 방식을 제안하며 예측이 필요하지 않다고 주장합니다.

2. 방법론: UNIBOOST

본 논문은 명시적인 길이 예측 대신 경량화된 통계적 신호에 의해 구동되는 "소프트" 우선순위 부스팅(soft priority boosting)을 사용하는 분포 인식형, 예측 불필요(prediction-free) 스케줄링 프레임워크인 UNIBOOST를 소개합니다. 이 설계는 스케줄링과 캐시 인식 선점(cache-aware preemption)의 공동 최적화로 구성되며, 네 단계로 구조화되어 있습니다.

1단계: Strawman (DISTBOOST)

초기 접근 방식은 프리필(prefill) 단계와 디코딩(decode) 단계를 별개의 문제로 취급합니다. 이는 프리필 요청에 대해 큐잉 이론에서 영감을 받은 $\gamma$ -Boost 우선순위 함수를 사용하지만, 디코딩 큐를 우선시합니다. 이 방식은 디코딩의 테일 지표를 개선하지만, 프리필 요청이 장시간 실행되는 디코딩 작업에 의해 기아 상태(starvation)에 빠지는 헤드 오브 라인(Head-of-Line, HoL) 블로킹 문제를 겪습니다.

2단계: 통합 우선순위화 (UNIBOOST-BASE)

HoL 블로킹을 해결하기 위해, 저자들은 프리필과 디코딩 큐를 단일 우선순위 공간으로 통합합니다.

우선순위 점수: 요청은 $\phi_i(t) = a_i - b_\gamma(\tilde{w}_i(t))$ 를 기준으로 점수가 매겨집니다. 여기서 $a_i$ 는 도착 시간이고, $\tilde{w}_i(t)$ 는 유효 작업량(획득한 작업량과 프리필 길이 중 최댓값)입니다.
부스트 함수: $b_\gamma(w) = \frac{1}{\gamma} \log(\frac{1}{1 - e^{-\gamma w}})$ 입니다. 이 함수는 클래식한 SRPT의 가혹한 선점을 피하면서, 획득한 서비스가 적은 요청에 "소프트"한 우선순위 부스트를 제공합니다.
메커니즘: 스케줄러는 최소 점수를 가진 요청을 선택하며, 진동을 방이자 히스테리시스(hysteresis) 파라미터에 의해 제어되는 범위 내에서 단계 간 선점을 허용합니다.

3단계: MEMGUARD를 통한 안정성 확보 (KV-Aware Hysteresis)

KV-캐시 제거 및 재계산의 높은 비용을 완화하기 위해, 저자들은 MEMGUARD를 도입합니다.

양자화된 우선순위: 우선순위를 연속적으로 업데이트하는 대신, 시스템은 획득한 작업량 지표( $\hat{w}_i$ )를 기하학적 양자화(예: $k, 2k, 4k...$ 임계값)를 사용하여 이산화합니다.
최소 실행 단위 (Minimum Run): 일단 요청이 할당되면, 해당 요청의 획득 작업량이 다음 양자화 임계값을 넘을 때까지 제거될 수 없습니다. 이는 KV 이동 비용을 분할 amortize하고, 작업 길이에 대한 로그 단위의 제한된 선점 기회만을 허용합니다.

4단계: 적응형 파라미터 추정 ( $\gamma$ -Ada)

부스트 파라미터 $\gamma$ 는 테일 동작에 큰 영향을 미칩니다. 정적인 $\gamma$ 는 가변적인 부하 상황에서 최적이 아닙니다.

온라인 추정: 시스템은 관측된 응답 시간 분포의 상위 테일(P95와 P99 사이)에 로그-선형 기울기를 피팅함으로써 유효 테일 기울기( $\gamma_{eff}$ )를 추정합니다.
적응: 스케줄러는 $\gamma$ 를 동적으로 조정하여 FCFS(테일 보호)와 LAS(평균 최적화) 사이를 보간하며, 명시적인 예측 없이도 워크로드 변화에 적응합니다.

3. 주요 기여

예측 불필요한 테일 최적화: 명시적인 작업 길이 예측 없이도 테일 레이턴시를 최적화할 수 있음을 입증했습니다. 대신, 경량화된 통계적 신호와 소프트 부스팅만으로 충분함을 보여줍니다.
스케줄링과 제거의 공동 설계: 스케줄링 결정과 KV-캐시 관리를 결합하여 최적화하는 프레임워크를 도입했습니다. 부스트 기반 스케줄링을 제거 인식 실행 제어(MEMGUARD)와 결합함으로써, 캐시 스래싱으로 인한 성능 저하를 방지합니다.
분포 변화에 대한 강건성: 복잡한 모델 학습이나 예측 없이도 다양한 워크로드(헤비 테일 vs 라이트 테일, 추론형 vs 채팅형)에 적응합니다.
이론적 근거: 큐잉 이론의 $\gamma$ -Boost 정책을 LLM 추론의 특정 제약 조건(상태 유지, 메모리 결합)에 맞게 변형하였습니다.

4. 실험 결과

NVIDIA A100 GPU 환경에서 Llama-3-8B, CodeLlama-34B, Qwen-72B 모델을 사용하여 실제 운영 및 오픈 소스 트레이스(Azure, ShareGPT, S1K)를 통해 평가했습니다.

테일 레이턴시 감소: UNIBOOST는 완벽한 길이 예측을 수행하는 TRAIL+(SRPT 기반)보다 P99 TTLT를 최대 35~50% 낮게 달성했습니다. 또한 다양한 워크로드에서 P99 TTFT를 34~47% 감소시켰습니다.
처리량 (Throughput): 이 방법은 돌발적인 부하 상황에서 베이스라인 대비 1.01~1.12배 향상된 처리량을 보여줍니다.
SLO 달성: UNIBOOST는 SJF 기반 접근 방식과 비교했을 때, 99% 달성률을 유지하면서도 TTFT에 대해 2.9~8.7배 더 엄격한 SLO를 견딜 수 있게 합니다.
절제 연구 (Ablation Studies):
- 통합 우선순위(2단계)를 제거하면 프리필 기아가 발생합니다.
- MEMGUARD(3단계)를 제거하면 KV 스래싱으로 인해 심각한 테일 레이턴시 급증이 발생합니다.
- 적응형 $\gamma$ (4단계)를 제거하면 부하 변화에 대한 강건성이 떨어집니다.
비교: 이 방법은 vLLM의 Sarathi(청크 프리필), LTR(학습 기반 랭킹 SJF), TRAIL(예측 기반 SRPT)을 포함한 최첨단 베이스라인들을 능가하며, 특히 예측이 가장 불확실한 추론 중심 워크로드에서 뛰어난 성능을 보입니다.

5. 의의 및 주장

본 논문은 UNIBOOST가 온라인 LLM 서빙을 위한 강력한 대안을 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

예측으로부터의 분리: 예측 품질이 저하되기 쉬운 추론 중심 및 가변 길이 워크로드의 주요 병목인 길이 예측에 대한 의존성을 제거합니다.
전체론적 최적화: "평균 vs 테일"의 트레이드오프와 "스케줄링 vs 메모리"의 트레이드오프를 동시에 해결하여, 예측 품질이 저하되는 상황에서도 효과적인 솔루션을 제공합니다.
실용성: vLLM이나 SGLang과 같은 기존의 컨티뉴어스 배칭(continuous-batching) 스택에 쉽게 통합할 수 있으며, 복잡한 ML 모델 대신 경량화된 런타임 통계에 의존합니다.

저자들은 차세대 LLM 서빙, 특히 가변 길이 추론 능력이 강화되는 모델들의 경우, 분포 인식 및 제거를 고려한 스케줄링이 필수적이라고 결론짓습니다.