본 논문은 대규모 언어 모델(LLM) 추론 스케줄링을 최적화하여 총 대기 시간을 최소화하는 문제를 연구합니다. LLM 추론은 온라인 및 다중 작업 서비스 프로세스이며, 사전 훈련된 LLM이 입력 요청을 처리하고 순차적으로 출력 토큰을 생성하는 과정에서 많은 에너지를 소모합니다. 따라서 많은 프롬프트 요청이 도착하는 상황에서 스케줄링 효율을 개선하고 전력 소비를 줄이는 것이 중요합니다. LLM 추론 스케줄링의 주요 과제는 프롬프트 길이는 도착 시 알 수 있지만, 메모리 사용량과 처리 시간에 중대한 영향을 미치는 출력 길이는 알 수 없다는 점입니다. 이러한 불확실성을 해결하기 위해 본 논문에서는 머신 러닝을 활용하여 출력 길이를 예측하는 알고리즘을 제안합니다. 각 요청에 대한 예측은 구간 분류(최소-최대 범위)를 제공한다고 가정합니다. 보수적인 알고리즘 $\mathcal{A}{\max}$는 예측된 출력 길이의 상한을 기반으로 요청을 스케줄링하여 메모리 오버플로를 방지합니다. 하지만 이 방법은 지나치게 보수적이어서 예측 정확도가 감소하면 과대 추정으로 인해 성능이 크게 저하됩니다. 이러한 한계를 극복하기 위해 본 논문에서는 예측된 하한을 초기 출력 길이로 처리하고 추론 중에 이 추정치를 동적으로 개선하는 적응형 알고리즘 $\mathcal{A}{\min}$을 제안합니다. $\mathcal{A}{\min}$이 로그 스케일 경쟁 비율을 달성함을 증명하고, 수치 시뮬레이션을 통해 $\mathcal{A}{\min}$이 실제 시나리오에서 효율성과 강건성을 보여주는 것을 증명합니다. 또한 $\mathcal{A}_{\min}$은 예측 구간의 하한에만 의존하는데, 출력 길이의 상한을 정확하게 예측하는 것이 일반적으로 더 어렵기 때문에 이는 장점입니다.
