본 논문은 이종의 prefill 및 decode 길이를 갖는 LLM 요청을 처리하는 문제를 연구합니다. LLM 서빙에서 prefill 길이는 입력 프롬프트 길이에 해당하며, KV 캐시의 초기 메모리 사용량을 결정합니다. decode 길이는 순차적으로 생성되는 출력 토큰의 수를 나타내며, 각 토큰이 추가될 때마다 KV 캐시 메모리 사용량이 1단위씩 증가합니다. n개의 요청 집합이 주어졌을 때, 총 완료 시간을 최소화하기 위해 요청을 스케줄링하고 처리하는 것을 목표로 합니다. 본 논문은 배치, 배치 제약, 선행 관계, 선형적으로 증가하는 메모리 사용량의 상호 작용으로 인해 이 문제가 NP-hard임을 보입니다. 흔히 사용되는 FCFS 및 SF 스케줄링 전략을 분석하고, 그 경쟁 비율이 메모리 제한에 따라 sublinear하게 증가한다는 것을 증명합니다(이는 메모리 수요가 큰 실제 환경에서는 상당한 단점). 이를 해결하기 위해 시간에 따라 효율적으로 배치를 형성하는 새로운 선택 지표를 기반으로 하는 새로운 알고리즘을 제안하고, 이 알고리즘이 일정한 경쟁 비율을 달성한다는 것을 증명합니다. 마지막으로, 동적 프로그래밍 변형, 지역 탐색 방법 및 LP 기반 스케줄러를 포함한 이 접근 방식에서 영감을 받은 몇 가지 알고리즘 변형을 개발하고 평가하여 포괄적인 시뮬레이션을 통해 표준 기준보다 성능이 우수하고 계산 효율성을 유지함을 보여줍니다.
