스케줄러는 요청이 들어오는 순간 하나를 모른다. 이 요청이 토큰을 몇 개 생성할 것인가.
입력 길이는 안다. 프롬프트가 이미 있으니 prefill에 필요한 KV 캐시 블록 수를 계산할 수 있다. 문제는 decode다. 모델이 EOS를 뱉어야 비로소 출력 길이가 확정되는데, 스케줄러는 그 전에 KV 캐시 메모리를 잡고, 배치를 구성하고, 처리 순서를 결정해야 한다. 이 비대칭이 LLM 서빙 처리량 손실의 구조적 원인이다. 스케줄러 알고리즘을 아무리 정교하게 만들어도, 출력 길이를 알기 전엔 최적 배치를 꾸릴 수 없다.
스케줄러가 배치를 꾸릴 때 무엇을 모르는가
Orca (Yu et al., OSDI 2022)가 iteration-level scheduling을 도입하면서 LLM 서빙의 패러다임이 바뀌었다. 기존 정적 배칭(static batching)은 배치 안의 모든 요청이 완료될 때까지 기다렸다. 이 문제를 수치로 보면 실감이 온다.
배치 크기 32를 가정하자. 31개 요청이 100 토큰에서 완료되고, 1개가 2000 토큰까지 진행되는 상황이다. decode 스텝 하나당 T ms가 걸린다면:
- 정적 배칭: 배치 전체가 2000 스텝을 기다린다. 31개 짧은 요청의 TPOT(Time Per Output Token) = 2000T / 100 = 20T ms. 배치 평균 TPOT = (31 × 20T + 1 × T) / 32 ≈ 19.4T ms.
- 균일한 배치 (모두 100 토큰): TPOT = T ms.
스트래글러 하나가 배치 평균 TPOT을 20배 가까이 끌어올린다. Orca의 iteration-level scheduling이 정확히 이 문제를 겨냥했다. 매 스텝마다 완료된 요청을 내보내고 새 요청을 채운다. step 100에서 31개가 나가고 31개가 합류하면, 스트래글러 1개가 남아 있어도 GPU는 32개 요청을 계속 처리한다.
그런데 continuous batching이 이 문제를 완전히 해결하지는 않는다. 스트래글러의 KV 캐시가 step 2000까지 GPU 메모리를 점유한다는 사실은 변하지 않는다. step 100에서 31개 슬롯이 비어도, 그 빈 슬롯은 스트래글러가 쓰고 남은 메모리에서 나온다. 스트래글러가 살아있는 동안 KV 캐시 블록들이 계속 묶이고, 실효 배치 크기 상한이 낮아진다.
출력 길이 편차가 처리량을 갉아먹는 세 경로
조기 완료 낭비. 평균보다 훨씬 짧게 끝나는 요청들은 슬롯을 빨리 비운다. 대기열에 새 요청이 있다면 즉시 채울 수 있으니 트래픽이 충분할 때는 문제가 아니다. 하지만 도착 속도가 낮거나 피크가 지난 직후 대기열이 비어 있는 구간에서는, 이 빠른 완료가 GPU 활용률 저하로 이어진다. 출력 길이 분포의 분산이 클수록 짧은 요청이 슬롯을 조기 반납하는 사건이 잦아진다.
스트래글러의 메모리 점거. 출력 길이 분포의 꼬리(p95, p99)가 두꺼울수록 매 순간 배치 안에 아주 긴 요청이 섞일 확률이 높다. 이 요청이 KV 캐시를 오래 점유할수록 신규 요청을 받을 수 있는 여유 메모리가 준다. GPU 코어가 놀지 않아도 메모리가 병목이 되어 실효 배치 밀도가 떨어진다. 처리량 손실이 알고리즘 문제가 아니라 메모리 배분 문제에서 발생하는 케이스다.
보수적 배치 크기. 스케줄러가 출력 길이 분포를 모르면 OOM을 피하기 위해 배치 크기를 낮게 잡는다. vLLM의 max_num_scheduled_tokens가 이 제어 장치인데, 운영자가 안전 마진을 크게 잡을수록 GPU가 처리할 수 있는 양보다 적게 배치를 꾸리게 된다. 이 보수성이 throughput을 직접 깎는다. 분산이 큰 워크로드일수록 적절한 마진 설정이 어려워지고, 운영자는 결국 더 낮은 값으로 도망친다.
서빙 프레임워크들이 이 불확실성을 어떻게 다루는가
vLLM의 접근은 reactive다. 요청 수신 시점에 max_tokens 기반으로 KV 캐시 블록을 미리 예약하지 않는다. decode 스텝마다 필요한 블록을 하나씩 할당하다가, GPU 메모리가 부족해지면 실행 중인 요청 중 일부를 preemption해서 waiting queue로 되돌린다. preemption된 요청은 KV 캐시를 다시 계산해야 하므로 비용이 생긴다. max_num_scheduled_tokens 파라미터가 배치당 허용 토큰 수 상한을 설정해 proactive하게 OOM을 막는 역할을 하는데, 이 값의 설정이 실질적인 처리량을 좌우한다.
Sarathi-Serve (OSDI 2024)는 출력 길이 분산보다 prefill과 decode 간 간섭 문제를 공략했다. 긴 prefill 계산이 진행 중인 decode 스텝을 멈추게 하는 "prefill stall"을 chunked prefill로 해결한다. prefill 계산을 작은 chunk로 나눠 decode 스텝 사이에 끼워 넣어 stall을 제거하는 방식이다. Mistral-7B, A100 단일 GPU에서 vLLM 대비 2.6배 serving capacity를 확보했고, 전체 모델·하드웨어 조합에서 최대 5.6배 개선을 보였다. 출력 길이 분산 자체에 대한 직접적 답은 아니지만, decode 배치가 stall 없이 유지되면 스트래글러의 영향이 일부 완화된다.
SGLang의 radix attention은 KV 캐시 접두사 재사용에 특화돼 있다. 동일한 시스템 프롬프트나 few-shot 예시를 공유하는 요청들의 메모리 효율을 높이는 접근으로, 접두사 캐시 히트율이 높은 서비스에선 의미 있는 개선이 나오지만 출력 길이 분산 문제를 구조적으로 다루지는 않는다.
출력 길이 예측을 앞단에 붙이면 얼마나 달라지는가
스케줄러가 출력 길이 분포를 미리 알 수 있다면 두 가지가 달라진다. 메모리 예약을 정밀하게 잡을 수 있고, 비슷한 길이의 요청끼리 같은 배치에 묶어 straggler 효과를 줄일 수 있다.
Zheng et al. (2023)의 "Response Length Perception and Sequence Scheduling"은 LLM 자체를 활용해 응답 길이를 예측하고 비슷한 길이의 요청을 micro-batch로 묶었다. 결과로 86% throughput 개선을 보였다. 분포가 균질한 배치에서는 straggler가 생기기 어렵고, GPU 자원이 낭비 없이 배치 전체에 분배된다.
Fu et al. (2024)의 "Efficient LLM Scheduling by Learning to Rank"는 정확한 길이 예측 대신 상대 순위를 예측하는 방향을 택했다. "이 배치 안에서 가장 긴 요청이 어느 것인가"를 맞히는 문제는 정확한 토큰 수를 맞히는 것보다 훨씬 쉽다. 이 방식으로 shortest-job-first(SJF) 스케줄링에 근사하면서, chatbot 서빙에서 2.8배 지연 감소, 합성 데이터 생성에서 6.5배 처리량 향상을 달성했다.
S3(Jin et al.)는 DistilBERT 기반 경량 분류기를 앞단에 배치해 각 요청을 short / medium / long 버킷으로 분류하고 버킷별로 배치를 구성한다. 정확한 길이가 아니라 대략의 범주만 알아도 균질한 배치의 이점을 얻을 수 있다는 실용적 관찰이다.
예측 오류의 방향이 중요하다. over-prediction(실제보다 길다고 예측)은 예약한 KV 캐시 블록 일부가 사용되지 않고 반납된다. 슬롯이 낭비되지만 시스템은 안전하다. under-prediction(실제보다 짧다고 예측)은 꽉 채운 배치가 실제로 더 많은 메모리를 요구하면서 OOM이나 preemption이 발생한다. 두 오류의 비용이 비대칭이므로, 예측기를 보정할 때 약간의 over-prediction 편향을 허용하는 것이 안전하다.
예측 기반 접근 전체에 공통된 트레이드오프도 있다. 예측 모델 inference latency가 요청 처리 파이프라인에 추가된다. LLM을 예측기로 쓰면 inference 한 번이 더 들어가고, DistilBERT 수준의 경량 모델이라도 추론 파이프라인에 hop이 하나 더 생긴다. 트래픽 패턴이 바뀌면 분류기를 재학습해야 하고, 그 유지 비용도 운영 부담으로 쌓인다.
운영에서 당장 할 수 있는 것
출력 길이 예측 모델 없이도 분포를 통제하는 방법이 있다.
max_new_tokens 캡이 가장 직접적이다. 분포의 꼬리를 잘라내면 straggler 발생 확률이 줄어들고 배치 예측 가능성이 높아진다. 단점은 실제 생성이 중단될 수 있다는 것 — QA나 짧은 요약 태스크는 상관없지만 코드 생성이나 긴 문서 작업은 결과 품질이 훼손된다.
요청 유형별 라우팅이 더 실용적인 경우가 많다. QA, 짧은 대화, 코드 생성, 문서 요약은 출력 길이 분포가 서로 다르다. 이 유형들을 같은 배치에 섞으면 변동계수(CV)가 높아진다. 유형별로 분리된 큐나 서빙 엔드포인트를 두면, 각 배치 안의 길이 분포가 훨씬 균질해지고 예측 모델 없이도 배치 품질을 높일 수 있다.
SLA 설계에서도 출력 길이 가정을 명시해야 한다. "TPOT 50ms 이하"라는 목표가 어떤 출력 길이 분포를 가정하는지 문서에 남기지 않으면, 실측 트래픽에서 SLA 달성률이 예상과 다르게 나온다. 특히 p99 출력 길이가 평균의 10배 이상인 태스크 유형에서 이 문제가 반복된다.