# 출력 길이 불확실성이 있는 LLM 추론 스케줄링: A_min과 A_max로 예측 오류를 흡수하는 방법
요약
LLM 추론 시스템에서 스케줄러는 매 순간 "지금 어떤 요청을 배치에 넣을 것인가"를 결정한다. 프롬프트 길이는 요청 도착 즉시 알 수 있지만, 출력 길이는 생성이 끝날 때까지 알 수 없다. 짧은 답이 나올 것 같았는데 긴 추론이 나오거나, 반대로 긴 답을 예상했는데 두 문장으로 끝나는 경우가 빈번하다.
이 불확실성이 스케줄링 품질에 직접 영향을 미친다. 출력 길이를 잘못 추정하면 KV 캐시 메모리가 부족해 요청을 강제 퇴거(eviction)하거나, 반대로 여유 공간이 충분한데도 새 요청을 배치에 넣지 못해 GPU를 놀린다.
Zixi Chen, Yinyu Ye, Zijie Zhou(2025)의 논문 "Adaptively Robust LLM Inference Optimization under Prediction Uncertainty"(arXiv:2508.14544)은 이 문제를 형식화하고 두 알고리즘을 제안한다.
- A_max: 예측 구간의 상한값을 사용하는 보수적 알고리즘. 메모리 오버플로를 방지하지만 배치 크기가 줄어든다.
- A_min: 예측 구간의 하한값으로 시작해 실행 중에 동적으로 재조정하는 적응형 알고리즘. O(log(d_max/d_min)) 경쟁 비율을 달성한다.
수치 시뮬레이션에서 A_min은 정답(hindsight)을 아는 최적 스케줄러와 거의 동일한 성능을 보인다.
왜 출력 길이가 스케줄링을 어렵게 만드는가
KV 캐시의 이중 메모리 동적성
LLM 추론은 두 단계로 나뉜다.
- 프리필(Prefill): 입력 P 토큰을 한 번에 처리하고 크기 P에 비례하는 KV 캐시를 생성한다.
- 디코드(Decode): 토큰을 한 개씩 자기회귀(autoregressive)로 생성하며 KV 캐시가 한 토큰씩 늘어난다. D 토큰을 생성하면 최종 KV 캐시 크기는 P + D에 비례한다.
스케줄러는 고정된 KV 캐시 메모리 예산 M 안에서 여러 요청을 동시에 처리해야 한다. 어떤 요청의 출력 길이 D가 길면 해당 요청이 메모리를 오랜 시간 점유해 다른 요청의 진입을 막는다.
출력 길이를 모를 때의 딜레마
| 상황 | 결과 |
|---|---|
| D를 과소 추정 | 배치에 더 많은 요청 → 실제 D가 길면 메모리 오버플로 → 퇴거 발생 |
| D를 과대 추정 | 새 요청을 조기에 차단 → 배치가 비어 GPU 활용률 저하 |
| 정확한 추정 | 최적 배치 구성 → 현실에서는 불가능 |
이 딜레마는 FCFS(선착순), 최단 출력 우선(Shortest Output First), 전체 크기 기반 정렬 같은 표준 정책이 근사비(approximation ratio)가 이론적으로 무한대가 될 수 있는 이유다.
구간 예측: [d_min, d_max] 기반 ML
논문의 핵심 전제는 ML 모델이 각 요청의 출력 길이에 대해 구간 예측을 제공한다는 것이다. 즉 정확한 D 값이 아니라 [d_min, d_max] 범위가 주어진다.
현재 LLM 서빙 시스템에서 출력 길이 예측기를 도입하는 흐름이 이미 있다. vLLM의 prefill scheduler나 외부 predictor 모듈이 대표 사례다. 논문은 이 예측기가 완벽하지 않을 때(실제 D가 [d_min, d_max]를 벗어날 가능성 포함) 어떻게 스케줄링해야 하는지를 다룬다.
구간 정보의 의미:
d_min은 예측 하한. 예측기가 "최소한 이 길이만큼은 생성된다"고 추정하는 값.d_max는 예측 상한. "이 길이를 넘어서 생성되는 것은 드물다"고 추정하는 값.- 구간 비율
d_max / d_min이 작을수록(예: 2~4배) 예측이 정밀하다.
A_max: 보수적 알고리즘
A_max는 각 요청의 예상 KV 캐시를 P + d_max로 계산해 배치를 구성한다. 실제 출력 길이 D가 d_max보다 짧으면 메모리를 실제보다 더 많이 예약한 셈이다.
장점:
- 메모리 오버플로가 발생하지 않는다.
- 배치 내 모든 요청이 퇴거 없이 완료된다.
단점:
- 배치 크기가 줄어든다. 실제 메모리 사용량보다 큰 공간을 예약하므로, 동시에 처리할 수 있는 요청 수가 적어진다.
- 예측 구간이 넓을수록(d_max가 d_min에 비해 훨씬 클수록) 비효율이 커진다.
A_max는 정확성(메모리 안전)이 효율보다 중요한 환경, 예를 들어 퇴거 비용이 매우 높거나 SLA 위반이 치명적인 경우에 유리하다.
A_min: 적응형 알고리즘
A_min은 A_max와 반대 방향에서 시작한다. 요청의 예상 KV 캐시를 P + d_min으로 낙관적으로 추정해 배치에 가능한 한 많은 요청을 넣는다.
실행 중 실제 출력 토큰이 늘어나면서 KV 캐시가 d_min을 초과하면 A_min은 동적 재조정을 수행한다.
A_min 동적 재조정 흐름:
1. 배치 구성 시: P + d_min 기준으로 요청 추가
2. 디코드 진행 중: 실제 KV 캐시 크기 추적
3. 임계치 초과 감지: 일부 요청의 KV 캐시가 d_min 초과
4. 재조정: 초과 비율에 따라 새 프리필 요청 진입 차단 또는 일부 요청 지연
5. 완료 후 재개: 완료된 요청이 메모리를 해제하면 새 요청 진입경쟁 비율 분석:
A_min은 O(log(d_max / d_min)) 경쟁 비율을 달성한다. 구간 비율이 작을수록 최적 스케줄러에 더 가까워진다.
| d_max / d_min | 경쟁 비율 상수 |
|---|---|
| 2 | O(log 2) ≈ 1 |
| 8 | O(log 8) ≈ 3 |
| 64 | O(log 64) ≈ 6 |
A_max 기반 경쟁 비율 분석보다 A_min이 유리한 이유는 상한보다 하한을 예측하기 쉽기 때문이기도 하다. 실제 서빙 환경에서 "최소 N 토큰"은 "최대 N 토큰"보다 ML 모델이 더 안정적으로 예측하는 경향이 있다.
수치 시뮬레이션 결과
논문의 수치 실험에서 A_min은 정답을 사전에 알고 최적 배치를 구성하는 힌드사이트 스케줄러(hindsight scheduler) 와 거의 동일한 총 지연을 달성한다. 실험 설정은 다음과 같다.
- 입력: 다양한 P, D 분포(짧은 입력-긴 출력, 긴 입력-짧은 출력 혼합)
- 메모리 예산 M: GPU HBM을 모사하는 고정 한계
- 예측기: d_min, d_max로 실제 D를 높은 확률로 포함하는 구간 생성
주요 결과:
| 알고리즘 | 총 지연 (정규화) | 메모리 오버플로 횟수 | 배치 활용률 |
|---|---|---|---|
| 힌드사이트(최적) | 1.00 | 0 | 높음 |
| A_min | 1.05 ~ 1.12 | 0 ~ 소수 | 높음 |
| A_max | 1.25 ~ 1.60 | 0 | 낮음 |
| FCFS | 1.80 ~ 3.5+ | 있음 | 중간 |
A_min은 힌드사이트 대비 5~12% 수준의 초과 지연을 보이며, 이는 실용적으로 허용 가능한 수준이다.
운영 함의
기존 스케줄러에 통합하는 방법
A_min은 기존 vLLM, SGLang 등의 연속 배치(continuous batching) 스케줄러 위에 구간 예측 레이어를 추가하는 방식으로 통합할 수 있다.
- 예측기 도입: 요청 도착 시 프롬프트를 경량 분류 모델에 통과시켜 [d_min, d_max] 구간 생성
- 예약 로직 교체: 기존 고정 최대 길이(max_new_tokens) 기반 메모리 예약을 d_min 기반으로 교체
- 동적 체크포인트: 디코드 루프마다 실제 KV 캐시 크기를 확인해 재조정 여부 판단
예측 구간 폭의 영향
구간 비율 d_max/d_min은 예측기 정밀도에 달려 있다. 운영 환경에서 이 비율을 측정해두면 알고리즘 선택 기준이 된다.
- 비율 < 4: A_min 경쟁 비율이 O(log 4) ≈ 2, 대부분의 환경에서 충분
- 비율 4~16: A_min은 여전히 유효하지만 재조정 빈도 증가
- 비율 > 16: 예측기를 개선하거나 A_max와 혼합 정책 고려
Sorted-F와의 관계
직전 챕터에서 다룬 Sorted-F(arXiv:2508.06133)는 출력 길이를 알고 있다는 전제에서 스케줄링 근사 알고리즘을 설계했다. A_min은 출력 길이를 모른다는 전제에서 출발해 예측 불확실성을 흡수하는 방법을 설계한다. 두 연구는 같은 그룹(Yinyu Ye, Zijie Zhou 공통 저자)에서 나온 보완 관계다.
실용적으로는:
- Sorted-F 방식으로 F-메트릭을 계산할 때 D의 점 추정 대신 [d_min, d_max] 구간을 활용하는 통합 접근이 자연스럽다.
Open question
- 실제 프로덕션 서빙 엔진(vLLM, SGLang)에서 A_min의 재조정 체크포인트 비용은 얼마인가?
- 구간 예측기를 어떤 아키텍처로 구성할 때 d_max/d_min 비율이 실용적 수준(≤8)으로 유지되는가?
- Prefill-Decode 분리(Disaggregated PD) 환경에서 A_min의 동적 재조정은 P-node와 D-node 중 어느 쪽이 주도해야 하는가?
References
- https://arxiv.org/abs/2508.14544
- https://www.semanticscholar.org/paper/Adaptively-Robust-LLM-Inference-Optimization-under-Chen-Ye/f806006463bea829cdc1111f10db05da3f599e35
- https://www.themoonlight.io/en/review/adaptively-robust-llm-inference-optimization-under-prediction-uncertainty
- https://arxiv.org/abs/2508.06133
- https://arxiv.org/html/2606.22327