LLM 추론 스케줄링의 핵심 긴장
LLM 추론은 근본적으로 다른 두 계산 단계로 이루어진다. 프리필(Prefill)은 입력 프롬프트 전체를 한 번에 병렬 처리해 첫 번째 토큰을 만든다. 지표는 TTFT(Time to First Token)다. 디코드(Decode)는 토큰을 하나씩 자기회귀적으로 생성한다. 지표는 TBT(Time Between Tokens)다.
두 단계는 서로 다른 자원 특성을 갖는다. 프리필은 compute-bound이며 배치를 길게 묶을수록 GPU 활용률이 올라간다. 디코드는 memory-bandwidth-bound이며 KV 캐시 크기가 클수록 배치 처리에 부담이 커진다. 하나의 GPU 위에서 두 단계를 함께 실행하면 목표가 충돌한다. 프리필을 위해 긴 배치를 묶으면 디코드 지연이 늘고, 디코드를 우선하면 TTFT가 증가한다.
기존 스케줄러들은 이 긴장을 경험적으로 해결해왔다. Sarathi-Serve는 청크드 프리필로 디코드 방해를 줄였고, vLLM 연속 배칭은 디코드 우선 스케줄링으로 TBT 안정성을 높였다. 그러나 어떤 스케줄링이 이론적으로 최적인지, SLO를 명시적으로 보장하는 방법이 무엇인지는 미답으로 남아 있었다.
arXiv:2508.01002 "Optimal Scheduling Algorithms for LLM Inference: Theory and Practice"는 이 두 가지 물음에 동시에 답한다. ACM SIGMETRICS 2026에서 발표된 이 논문(Bari, Hegde, de Veciana, UT Austin)은 LLM 추론 스케줄링을 큐잉 이론으로 분석해 처리량 최적 조건을 증명하고, 실전 SLO 제약 아래에서 동작하는 SLAI 스케줄러를 제안한다.
이론 토대: 최적 타일링
논문은 프리필-디코드 스케줄링을 타일링(Tiling) 문제로 정식화한다. 타일은 하나의 스케줄링 라운드에 포함될 프리필 이터레이션과 디코드 이터레이션의 조합이다. 타일 크기와 비율을 어떻게 정하느냐에 따라 GPU 활용률과 지연이 결정된다.
세 가지 극단적 전략이 있다.
- 순수 분리(Disaggregation): 프리필 노드와 디코드 노드를 물리적으로 분리. 각 단계를 독립 최적화할 수 있지만 KV 캐시 전송 오버헤드가 생긴다.
- 순수 통합(Aggregation): 프리필과 디코드를 같은 GPU에서 번갈아 실행. KV 전송은 없지만 두 단계가 서로 방해한다.
- 혼합 타일링: 타일마다 프리필·디코드 이터레이션 비율을 조정. 이론적으로 가장 유연하지만 최적 비율을 구하는 방법이 필요하다.
논문이 증명하는 핵심 결과는 최적 타일링이 두 단계의 처리 속도(service rate)를 맞추는 비율로 결정된다는 것이다. 이 비율에서 벗어나면 한 쪽 큐가 무한히 쌓이거나 GPU가 낭비된다.
RAD 스케줄러: 처리량 최적성 증명
RAD(Resource-Aware Dynamic) 스케줄러는 논문의 이론적 핵심이다. RAD는 두 원칙을 결합한다.
최적 타일링: 각 스케줄링 라운드에서 프리필과 디코드 이터레이션을 최적 비율로 구성한다. 이 비율은 두 단계의 처리 속도를 맞추는 값으로 이론적으로 도출된다. 비율이 어긋나면 한 쪽 큐가 쌓이거나 GPU가 낭비된다.
동적 자원 배분: 시스템의 실시간 상태—프리필 큐 길이, 디코드 큐 길이, 현재 처리 중인 배치 크기—를 보고 타일 구성을 조정한다. 정적 비율을 고정하지 않는다는 의미다.
논문이 증명하는 결과: 이 두 원칙을 결합한 RAD는 약한 조건 아래에서 처리량 최적성(throughput optimality)을 달성한다. 처리량 최적성이란, 시스템이 처리 가능한 모든 도달률(arrival rate)에 대해 큐가 안정 상태를 유지함을 뜻한다. 즉, 어떤 경쟁 스케줄러도 RAD보다 더 넓은 도달률 집합을 안정적으로 처리할 수 없다.
SLAI 스케줄러: SLO를 실전에서 보장하는 방법
RAD가 처리량 최적성이라는 이론적 토대를 제공하지만, 실제 서빙에서는 SLO 제약이 따른다. 채팅 서비스에서 TBT가 임계값을 넘으면 사용자가 생성이 멈췄다고 느낀다.
SLAI(SLO-Aware LLM Inference) 스케줄러는 RAD 위에 두 가지 실전 메커니즘을 추가한다.
디코드 우선순위 조정: SLAI는 각 디코드 요청의 마지막 TBT를 실시간으로 측정한다. TBT 마감에 임박한 요청(남은 시간이 임계값 미만)을 이번 타일에 반드시 포함시킨다. TBT SLO 위반을 사전에 방지하는 방식이다.
프리필 LPL 정렬: 프리필 큐에서 짧은 프롬프트를 먼저 처리한다(Least Processing time Last의 반대). 짧은 프롬프트는 처리 시간이 짧으므로 단위 타일에서 더 많은 요청이 프리필을 완료한다. 전체 분포에서 중앙값 TTFT가 줄어드는 이유다.
두 메커니즘은 서로 충돌하지 않는다. TBT 마감에 임박한 디코드 요청을 먼저 채운 뒤, 남은 슬롯에 짧은 프롬프트 순으로 프리필을 배치한다.
실험 결과
논문은 openchat_shareGPT4 데이터셋, Mistral-7B 모델, NVIDIA RTX ADA 6000 GPU에서 Sarathi-Serve와 비교했다.
| 지표 | 조건 | SLAI 결과 |
|---|---|---|
| 중앙값 TTFT | TBT SLO 충족 유지 | −53% |
| 최대 서빙 용량 | TTFT ≤ 0.5s 제약 | +26% |
중앙값 TTFT 53% 감소는 LPL 정렬 효과다. 짧은 프롬프트를 먼저 처리하면 대기 시간 분포가 왼쪽으로 이동한다. 26% 용량 증가는 TTFT 제약을 유지하면서 더 많은 요청을 안정적으로 받을 수 있다는 의미다.
운영자 관점
SLAI는 현재 독립 연구 구현이며 vLLM·SGLang 메인라인에 직접 통합되지는 않았다. 그러나 이 논문이 제시하는 원칙들은 오늘 당장 적용 가능하다.
LPL 정렬은 바로 적용할 수 있다. 들어오는 요청의 프롬프트 길이를 알 수 있다면, 짧은 프롬프트를 먼저 처리하도록 큐를 구성하는 것만으로 중앙값 TTFT를 의미 있게 줄일 수 있다.
TBT 측정은 기존 도구로 가능하다. vLLM의 generation 통계, OpenTelemetry 계측으로 각 요청의 TBT를 추적할 수 있다. TBT 마감 임박 요청을 우선하는 로직은 애플리케이션 계층 프록시에서도 구현할 수 있다.
처리량 최적성 프레임워크의 활용: RAD가 증명하는 처리량 최적성은 이론적 상한이다. 기존 경험적 스케줄러들이 이 상한에 얼마나 근접해 있는지 검증하는 기준으로 이 논문의 프레임워크를 쓸 수 있다.
프리필-디코드 분리 서빙과의 관계: ai-frontier/23에서 다룬 P/D 분리 서빙(vLLM 0.25+ Disaggregated Prefill/Decode)은 두 단계를 물리적으로 분리한다. RAD·SLAI는 단일 인스턴스 내 스케줄링을 다루는 보완적 접근이다. P/D 분리 환경에서도 각 노드 내 스케줄링에 SLAI 원칙을 적용할 수 있다.
References
- https://arxiv.org/abs/2508.01002
- https://dl.acm.org/doi/abs/10.1145/3771574
- https://dl.acm.org/doi/10.1145/3801489.3806878
- https://users.ece.utexas.edu/~gustavo/papers/BHD25j.pdf
- https://arxiv.org/abs/2504.07347
- https://arxiv.org/abs/2504.11320