Deadline-Aware Adaptive Prefill Chunking for Efficient Large Language Model Serving

논문 링크

데드라인을 채우는 프리필 청크: SLOWeave — LLM 서빙의 적응형 청킹 스케줄러

TL;DR — 고정된 프리필 청크 크기 대신, 매 반복(iteration)마다 “가장 이른 디코드 데드라인 전에 끝나는 가장 큰 프리필 청크"를 이진 탐색으로 선택하는 온라인 스케줄러 SLOWeave를 제안한다. 25 ms TPOT 목표에서 혼합(mixed) 워크로드 goodput을 최강 고정 청크 대비 39%, 장문(long) 워크로드에서 38% 개선했고, 엄격한 10 ms 목표에서는 각각 3.3배, 2.4배까지 끌어올린다 (근거: Abstract).

핵심 아이디어

LLM을 서빙할 때 프리필(prefill)과 디코드(decode)는 서로 다른 비용 구조를 가진다. 프리필은 프롬프트를 병렬로 처리하며 KV 캐시를 구축하고, 디코드는 그 캐시를 읽으며 토큰을 하나씩 생성한다 (근거: §1). 같은 GPU에서 두 작업을 섞으면 긴 프리필이 활성 디코드의 다음 토큰 생성을 지연시켜 스트리밍 응답에 눈에 띄는 멈춤(pause)이 생긴다.

기존의 청크드 프리필(chunked prefill) 은 프롬프트를 잘게 나눠 디코드와 섞어 실행하지만, 그 청크 크기는 보통 고정이다 (근거: §1). SLOWeave의 핵심 아이디어는 단순하다. 청크 크기를 매 반복마다 “지금 남은 데드라인 여유(slack)“에 맞춰 동적으로 조정하는 것이다. 작게는 디코드 지연을 보호하고, 크게는 프리필 효율을 챙기되, 항상 활성 요청의 다음 토큰 데드라인 안쪽으로 끝나도록 상한을 정한다.

한 문장으로 정리하면: “고정 청크가 데드라인과 여유 사이에서 어느 한쪽만 포착하는 반면, SLOWeave는 정확한 비용 예측만 있으면 데드라인을 지키는 모든 선택 중 프리필 진행을 최대화한다는 국소적 최적성(local maximality)을 증명 가능한 형태로 보장한다.”

배경: 그들이 해결한 문제

프리필–디코드 간섭이라는 고질병

반복 단위(iteration-level) 서빙에서는 매 반복마다 활성 요청이 디코드 토큰을 하나씩 생성하고, 그 사이에 프리필 작업을 끼워 넣는다. 문제는 청크 크기라는 제어 변수가 도입되면서 생긴 트레이드오프다 (근거: §1, §2.2):

• 작은 청크: 디코드 중단 시간이 짧아 지연 시간을 지키지만, 프롬프트를 $\lceil L/C \rceil$ 조각으로 쪼개야 하므로 스케줄링·커널 런치 오버헤드를 그 횟수만큼 반복 지불한다 (근거: §2.2).
• 큰 청크: 오버헤드를 상각하고 첫 토큰(TTFT)을 빨리 만들지만, 활성 요청의 TPOT(Time Per Output Token) 목표를 깨뜨리는 지연 스파이크를 유발한다 (근거: §1).

저자들이 강조하는 핵심 통찰은 적절한 청크 크기가 “고정점"이 아니라 조건부 최적점이라는 점이다 (근거: §2.2):

여기서 $n$ 은 디코드 배치 크기, $L$ 은 프롬프트 길이, $D$ 는 TPOT 목표, $T$ 는 반복 비용 함수, $\lambda$ 는 도착 압력이다. 정적 튜닝은 이 공간의 한 점만 포착할 뿐이다. 게다가 TPOT SLO를 25 ms에서 10 ms로 조이면, 워크로드가 전혀 안 바뀌어도 같은 고정 청크가 데드라인을 넘어가 버린다 (근거: §2.2).

저자들이 보는 SOTA 상태

서빙 시스템 연구는 용량(capacity) 쪽은 크게 발전했다. Orca의 반복 단위 스케줄링, vLLM의 PagedAttention(KV 캐시 단편화 제거), FlashAttention·FlashInfer 같은 IO-aware 커널이 그것이다 (근거: §7). 그러나 저자의 진단은 명확하다: 이 개선들은 “얼마나 많은 프리필 작업을 지연 민감 디코드 반복에 섞을지"는 결정해주지 않는다 (근거: §2.1). 프리필/디코드를 물리적으로 분리하는 DistServe·Splitwise 같은 disaggregation 접근도 있지만, 이는 KV 전송 비용과 별도 용량 계획을 요구한다 (근거: §7). SLOWeave는 이 빈틈 — 동일 디바이스에서 프리필 허용량을 반복 단위로 제어하는 문제 — 을 겨냥한다.

새로운 접근법: SLOWeave

데드라인 모델

활성 요청 $i$ 의 마지막 토큰 완료 시각을 $\ell_i$ 라 하자(방금 프리필을 마쳤다면 프리필 완료 시각). TPOT 목표 $D$ 가 주어지면 다음 토큰 데드라인은 단순히:

스케줄러 시각 $s_t$ 에서의 반복 예산(budget) 은 가장 이른 남은 여유다:

활성 디코드가 없으면($A_t = \varnothing$) 데드라인 제약이 없으므로 TTFT를 가속하기 위해 구현 정의 최대 청크 $C_{\max}$ 를 쓸 수 있다 (근거: §3.1).

적응형 청크 선택

비어 있지 않은 활성 집합에 대해 SLOWeave는 다음을 만족하는 최대 정수 청크를 고른다 (근거: Eq. (1), §3.2):

여기서 $L_t$ 는 가장 오래 대기 중인 프리필의 남은 길이이고, $T(n,c)$ 는 반복 비용 함수다. 단조성(monotonicity) 덕분에 이 최대화는 이진 탐색으로 $O(\log C_{\max})$ 회의 비용 모델 질의로 풀린다 (근거: §3.2, Alg. 1). 핵심은 $T$ 가 특정 함수 형태가 아니라 $c$ 에 대한 단조성만 요구된다는 점이다. 프로파일된 룩업 테이블이든, 회귀 모델이든, 분석적 근사든 아무거나 써도 된다 (근거: §2.1).

안전성과 최대성 (Proposition)

저자가 증명한 정리는 깔끔하다 (근거: §3.3, Proposition 1):

정리. $T(n,c)$ 가 다음 반복 시간을 정확히 예측하고 $c$ 에 대해 비단조 감소하지 않는다고 가정하자. 만약 $T(|A_t|, 0) \le B_t$ 라면, Eq. (1)이 고른 청크는 (i) 모든 활성 요청의 다음 토큰 데드라인 전에 끝나고, (ii) 그 반복에서 데드라인-안전한 다른 어떤 청크보다 적어도 같은 수의 프리필 토큰을 처리한다.

증명은 정의 그 자체다: 구성상 $T(|A_t|, c_t^\star) \le B_t$ 이고 $B_t \le d_i - s_t$ 이므로 (i)가 성립하며, $c' > c_t^\star$ 인 안전한 청크가 존재한다면 최대성 정의에 모순이 되어 (ii)가 성립한다 (근거: §3.3).

예측 오차에 대해서는 마진 $\delta(n,c)$ 을 남겨 $\widehat T(n,c) + \delta(n,c) \le B_t$ 를 검사하면, 단측 예측 오차가 $\delta$ 로 유계인 한 같은 정리가 유지된다. 실전에서는 분위수 회귀(quantile regression)나 P99 잔차 테이블이 그 마진을 제공한다 (근거: §3.3).

작동 원리: 구체적인 예시로 살펴보기

아래는 한 반복에서 스케줄러가 내리는 결정 흐름이다:

  flowchart TD
    A[활성 디코드 A_t<br/>대기 프리필 P] --> B{P가 비어있나?}
    B -- 예 --> Z[디코드 전용 반복<br/>c = 0]
    B -- 아니오 --> C{A_t가 비어있나?}
    C -- 예 --> Z2[최대 청크 프리필<br/>c = min(C_max, L)]
    C -- 아니오 --> D[예산 계산<br/>B = min_i d_i - s]
    D --> E[이진 탐색<br/>T(n, c) + margin <= B 인 최대 c]
    E --> F[프리필 c개 토큰 +<br/>디코드 1토큰 동시 실행]

숫자로 보는 데드라인 채우기

저자의 시뮬레이터가 기본으로 쓰는 단조 비용 모델은 이렇게 생겼다 (근거: §4.1):

• 상수 $0.35$ ms: 스케줄러/커널 오버헤드
• $0.90 + 0.055n$: 디코드 배치 작업(선형)
• $0.40 + 0.006c$: 프리필 작업(선형)

장난감 예시(toy example) 로 동작을 따라가 보자. TPOT 목표 $D = 25$ ms이고, 현재 디코드 배치 $n = 4$, 가장 이른 데드라인까지 남은 예산이 $B_t = 10$ ms라고 하자. 디코드 전용 비용은:

$B_t = 10$ ms가 넉넉하므로 프리필을 섞을 여지가 있다. 이진 탐색으로 $T(4, c) \le 10$ 을 만족하는 최대 $c$ 를 찾는다. $c = 1000$ 이면:

아직 여유가 있으니 더 키운다. $c = 1400$ 이면:

데드라인을 넘으므로 불가. 최종적으로 약 $c \approx 1350$ 부근에서 수렴한다. 고정 청크 1024는 이 여유를 남기고, 고정 청크 2048은 넘어간다. SLOWeave는 남은 여유를 딱 데드라인까지 채우는 유일한 정책이다.

디코드 배치가 40으로 커지면 이야기가 달라진다. $T(40, 0) = 0.35 + 3.10 = 3.45$ ms에, 프리필 한 토큰당 $0.006$ ms씩 더 붙는다. 같은 $B_t = 10$ ms에서 채울 수 있는 청크는 훨씬 작아지고, 극단적으로 과부하가 걸리면 디코드 전용 반복으로 자동 폴백한다 (근거: §3.2, Alg. 1).

복잡도와 통합 표면

• 직접 구현은 활성 집합 스캔 1회 + 이진 탐색 → $O(|A| + \log C_{\max})$ / 반복, 가장 이른 데드라인을 힙으로 유지하면 $O(\log |A| + \log C_{\max})$ (근거: §3.2).
• vLLM 스타일 런타임에서 SLOWeave는 “활성 시퀀스 그룹 형성 후, 토큰 예산 할당 전“에 호출되며, 기존 토큰 예산을 고정값 대신 상한으로 바꾸는 것이 전부다. PagedAttention과 모델 커널은 의미론적으로 건드리지 않는다 (근거: §5.1, Fig. 1, Tab. 1).

성능 검증: 주요 결과

시뮬레이션 — 25 ms TPOT에서의 메인 비교

4개 워크로드(chat/mixed/long/bursty) × 5 시드 평균, 25 ms TPOT 목표에서의 goodput(req/s)은 다음과 같다 (근거: Tab. 3, Fig. 4):

대응하는 결합 SLO 달성률(TTFT와 요청 내 P99 TPOT를 동시에 만족한 비율, %)은 (근거: Fig. 4):

세 가지를 짚어보자:

1. Chat 워크로드는 무승부다. 프롬프트가 짧아(중앙값 256 토큰, 근거: §4.2) 비제약 full prefill이 이미 데드라인 안에 들어오므로, 적응성이 패널티를 만들지 않는다 (근거: §6.1).
2. Mixed는 full prefill의 완전한 붕괴를 보여준다. Full은 P99 TTFT가 Fixed-1024보다 낮지만(1364 vs 2101 ms) P99 TPOT가 48.5 ms로 목표 25 ms를 훌쩍 넘겨, 단 6.9% 의 요청만 양쪽 SLO를 만족한다. SLOWeave는 두 실패 모드 사이에서 여유를 가져다 쓴다 (근거: §6.1, Tab. 3).
3. Long에서 Fixed-256은 TTFT가 20초를 넘는다. TPOT는 지키지만 반복 오버헤드를 계속 지불해 첫 토큰이 폭발한다. Full은 P99 TPOT 61 ms로 사실상 전멸(0.1%)이다 (근거: §6.1, Tab. 3).

TPOT 목표를 조이면 차이는 벌어진다

정책을 전혀 재튜닝하지 않고 목표만 10/25/50 ms로 바꾼 결과, SLOWeave의 goodput을 “워크로드·목표별로 따로 고른 최강 정적 정책” 대비 배수로 나타내면 (근거: Tab. 4, Fig. 4):

두 가지 구조가 읽힌다. 첫째, 목표가 엄격할수록 고정 청크의 단점이 증폭된다 — 10 ms에서 Fixed-1024는 “줄어들지 못하고” goodput이 1.06 req/s로 박살 나는 반면 SLOWeave는 35.7 req/s를 낸다 (근거: §6.2). 둘째, 50 ms Mixed에서 full prefill과 동률(60.5 vs 60.4 req/s) 인데, 이는 완전한 프롬프트가 여유 안에 들어오면 Eq. (1)이 자연스럽게 full prefill로 수렴하기 때문이다. 즉 SLOWeave는 “보수적 청킹 ↔ full prefill” 사이를 별도 운영 모드 없이 보간한다 (근거: §6.2).

GPU 런타임 — 실제 하드웨어에서도 성립

8×A100-80GB / 8×H100-80GB 단일 노드에서 측정한 end-to-end 결과 (goodput req/s, 괄호는 SLO 달성률, 근거: Tab. 2, Fig. 3):

주목할 점은 에너지 효율까지 함께 좋아진다는 것이다. SLO를 만족한 요청당 줄 단위로 보면, A100/8B mixed에서 Default 18.7 J/유효요청 → SLOWeave 12.4 J/유효요청로 낮아진다 (근거: Tab. 2). 70B-TP8 long에서도 92.6 → 58.5 J/유효요청다. 데드라인을 넘겨 버려진(또는 재시도된) 연산이 줄어들면서 “유효 요청당” 에너지가 개선되는 것이다.

gain의 근원은 어디인가

두 가지 결합 효과가 있다 (근거: §6.3): (1) 디코드가 적을 때 청크를 늘려 고정 0.4 ms 프리필 오버헤드를 상각하고, (2) 디코드 배치가 커지면 청크를 줄여 결합 반복을 데드라인에 붙인다. 고정 청크는 이 트레이드오프의 기껏해야 한쪽 면만 포착한다. Tab. 3에서 Fixed-256/1024의 P99 TPOT가 모든 워크로드에서 25 ms를 크게 밑도는 반면, SLOWeave는 mixed/long을 약 25 ms 부근까지 끌어올려 그 여유를 프리필 조기 완료와 goodput으로 전환한다 (근거: §6.3).

우리의 관점: 강점, 한계, 그리고 이 연구가 중요한 이유

강점 — “좁게, 그러나 증명 가능하게”

SLOWeave의 가장 큰 미덕은 의도된 협소함이다. 모델 가중치도, 어텐션 커널도, KV 캐시 레이아웃도 바꾸지 않는다 (근거: §1, Fig. 1). 기존 런타임의 토큰 예산을 상한으로 재해석하는 것만으로 붙일 수 있고, 이는 disaggregation·모델 병렬성·메모리 관리와 직교(orthogonal) 한다 (근거: §7). 그 위에 국소 안전성·최대성 정리를 얹어, “왜 안전한가"를 휴리스틱이 아니라 단조 비용 모델 하나로 증명했다. 엔지니어 입장에서 이 조합 — 변경 표면 최소화 + 정당성 보증 — 은 실무 도입 문턱을 크게 낮춘다.

둘째, 재현성과 독립성을 강하게 신경 썼다. 시뮬레이터·비용 파라미터·워크로드 생성기·raw run·집계 코드를 함께 공개해, 하드웨어 의존 효과와 스케줄링 트렌드를 분리해 검증한다 (근거: §1, §5.2). 통계 프로토콜도 정직하다: 수백만 개의 상관된 토큰 간격을 독립 관측처럼 다루는 “거짓 정밀도"를 피하고, 요청 단위 집계 후 시드 평균을 보고한다 (근거: §4.4).

한계 — 저자가 인정한 것과, 우리가 보는 것

저자는 명시적으로 다음을 인정한다 (근거: Limitations):

• 평가가 유한한 모델·가속기·트레이스·SLO 목표에 한정된다. 실제 반복 비용은 커널 경계, TP 통신, 메모리 압박, prefix-cache 히트로 비평활(non-smooth) 할 수 있고, 이에 대한 보정 드리프트 연구는 부족하다.
• 현재 컨트롤러는 공유 TPOT 목표 + 반복당 프리필 1개를 가정한다. 다중 테넌트 우선순위는 earliest-deadline 공식이 뒷받침하지만, starvation과 admission control은 별도 연구가 필요하다.
• 선점 비용과 KV 전송을 모델링하지 않았고, 다중 노드 KV 전송·지역 간 서빙은 측정하지 않았다.

우리가 덧붙일 수 있는 잠재적 우려는 세 가지다. 첫째, 모든 것이 비용 예측기 $\widehat T$ 의 품질에 달려 있다는 점이다. 정리는 “예측이 정확할 때"의 조건부 명제다. 커널 전환이 급격한 실제 하드웨어에서 단조 P99 룩업 테이블이 그 전환을 얼마나 잘 포착하는지 — 논문도 인정하듯 — 가 가장 취약한 지점이다 (근거: §5.2, Limitations). 둘째, TTFT SLO와 TPOT SLO의 결합 최적화가 암묵적으로 “goodput 극대화"로 수렴하지만, 반복당 프리필 1개 제한은 프리필 대기 큐가 길 때 TTFT를 후순위로 미룰 수 있다(가장 오래된 요청 우선 선택이 이를 완화하나, 근본 한계는 아니다) (근거: §3.4, §3.5). 셋째, 과부하 상태에서의 기아(starvation) 는 공개적으로 인정된 공백이다. work-conserving 정책은 임의 도착률과 데드라인을 동시에 만족할 수 없으며, 논문은 aging 임계값으로 “유계 데드라인 위반"을 허용하되 이를 명시적 SLO 예외로 기록하는 절충안을 제시한다 (근거: §3.4). 이는 정직하지만, 실제 운영에서 그 예외가 사용자에게 보이는 순간부터 SLO라는 개념 자체가 흔들린다.

이 연구가 중요한 이유

LLM 서빙은 이제 “토큰을 얼마나 빨리"에서 “SLO를 지키면서 얼마나 많이“로 축이 이동했다. 그런데 대부분의 시스템 연구는 용량(더 큰 배치, 더 빠른 커널, 더 나은 메모리)을 키우는 데 집중했고, “한 반복 안에서 프리필을 얼마나 섞을지"라는 미세한 제어 변수는 고정 상수로 남아 있었다. SLOWeave는 이 변수를 1차 시민(control variable) 으로 승격시키고, 그것이 단순한 이진 탐색 하나로 최적화 가능하며, 그 최적성이 증명 가능함을 보였다. “적응형 청크 사이징"이 독립된 서빙 프리미티브로서 가치가 있다는 분리 실험(isolation) 을 제공한 점이 이 논문의 기여다 (근거: Abstract, §6.3).

다음 단계는?: 앞으로의 길

저자가 제시하는 방향은 크게 세 갈래다 (근거: Limitations, §3.4, §3.5):

1. 비용 예측의 견고화 — 커널 경계·TP 통신·prefix-cache 히트가 만드는 비평활성을 잡는 보정, 그리고 모델/하드웨어 업데이트에 따른 드리프트 정량화가 1순위다.
2. 이질적 SLO·다중 테넌트 확장 — 논문은 이미 $D_i$ 를 요청별로 달리 쓰면 10 ms 인터랙티브 스트림과 50 ms 배치 요청을 같은 컨트롤러로 보호할 수 있다고 주장한다 (근거: §3.5). 이를 실증하고, 우선순위별 예측 마진 $\delta_i$ 의 설계를 정교화하는 것이 자연스러운 후속이다.
3. 프리필 다중 배치(multi-prefill knapsack) — 현재는 반복당 프리필 1개지만, Eq. (1)을 벡터로 확장하면 작은 knapsack 문제가 된다. first-fit이 로그 검색을 유지할 수 있다는 저자의 언급(§3.3)은 실용적 힌트다.

우리가 더 제안하고 싶은 방향은 admission control과의 결합이다. SLOWeave가 “데드라인 안에서 최대 진행"을 보장하더라도, 도착률 자체가 수용 한계를 넘으면 어떤 정책도 안전하지 않다 (근거: §3.2). 따라서 반복 단위 컨트롤러(SLOWeave) + 요청 단위 admission controller의 공동 설계 — 예를 들어 예측된 decode-only 비용이 $D$ 에 근접하면 도착을 거부/리다이렉트하는 기존 제안(§3.4)을 강화학습이나 온라인 최적화로 닫는 연구 — 가 다음 단계로 유망하다. 아울러, TTFT와 TPOT를 단일 스칼라 goodput이 아니라 파레토 곡면으로 바라보는 평가 방법론도 가치 있을 것이다. 현재 goodput은 두 SLO를 만족했는지의 이진 판정이지만, “얼마나 근접하게 위반했는지"의 정도를 반영하는 연속 지표가 정책 간 미세한 차이를 더 잘 드러낼 수 있다.

논문 원문의 표

arXiv e-print 의 LaTeX 원본에서 기계적으로 옮긴 표입니다. 숫자는 논문의 값이며 모델을 거치지 않았습니다.

표 1. Implementation surface for an iteration-level GPU runtime.

표 2. Measured GPU runtime results. Latencies are P99 values, and a request contributes to goodput only when it satisfies both the TTFT\xspace and TPOT\xspace SLOs.

표 3. Mean results over five seeds at the 25 ms TPOT\xspace SLO. Latencies are milliseconds and goodput is requests/s. The best fixed baseline depends on the workload; SLOWeave\xspace matches the easy chat case and leads on mixed, long, and bursty traffic.

표 4. SLOWeave\xspace goodput relative to the strongest static policy separately selected for each workload and TPOT\xspace target.