SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity

이 논문은 예측 불가능한 출력 길이와 컴퓨팅 및 메모리 요구 사항의 혼재라는 LLM 추론의 특성을 해결하기 위해, 프롬프트와 과거 결과를 활용한 경량 출력 길이 예측과 불확실성을 고려한 스케줄링 정책을 통해 28.7% 이상의 효율성 향상을 달성한 'SageSched'를 제안합니다.

핵심

🍽️ 문제: 혼잡한 레스토랑의 주방

LLM 이 작동하는 서버는 마치 요리사가 여러 손님의 주문을 동시에 처리하는 주방과 같습니다. 하지만 기존 시스템에는 두 가지 큰 문제가 있었습니다.

1. 예측 불가능한 주문 (불확실성):

   • 손님이 "오늘 날씨 어때?"라고 물으면 3 초 만에 답이 나올 수도 있고, "세계 역사에 대해 10 페이지 분량으로 써줘"라고 하면 10 분이나 걸릴 수도 있습니다.
   • 기존 시스템의 실수: 주방장은 주문이 들어오기 전까지 "이 요리가 얼마나 걸릴지"를 모릅니다. 그래서 그냥 도착한 순서대로 (선착순) 요리를 시작합니다.
   • 결과: 10 분 걸리는 복잡한 요리를 먼저 시작해버리면, 그 뒤에 온 간단한 주문들 (샐러드 등) 은 오랫동안 기다리게 됩니다. 이를 '선두 행렬 차단'이라고 합니다.

2. 두 가지 자원 경쟁 (하이브리드성):

   • 요리를 하려면 **불 (계산 능력)**도 필요하고, **식탁 공간 (메모리)**도 필요합니다.
   • 기존 시스템의 실수: 기존 주방장들은 "요리 시간 (불 사용량)"만 보고 순서를 정했습니다. 하지만 어떤 요리는 시간이 짧아도 식탁을 엄청나게 많이 차지해서 다른 요리를 못 하게 만들기도 합니다.
   • 결과: 식탁이 꽉 차서 더 이상 요리를 못 하는 상황 (메모리 부족) 이 오는데도, 시간만 짧다고 요리를 계속 시켜서 전체 시스템이 멈춰버립니다.

---

🚀 해결책: SageSched (세이지스케드)

이 논문은 위 두 문제를 해결하기 위해 세 가지 똑똑한 전략을 도입했습니다.

1. "과거의 비슷한 주문"을 기억하는 똑똑한 주방장 (예측)

• 기존 방식: AI 모델을 따로 훈련시켜서 "이 주문은 몇 분 걸릴까?"라고 예측하게 했습니다. (무겁고, 틀리기 쉬움)
• SageSched 방식: "지난달에 비슷한 주문을 했을 때, 얼마나 걸렸지?"라고 과거 기록을 뒤져봅니다.
  • 비유: 손님이 "파스타 레시피 알려줘"라고 하면, 주방장은 과거에 비슷한 질문을 한 손님이 5 분 걸렸던 기록을 보고 "아, 이 주문은 대략 5 분 정도 걸리겠구나. 그리고 3 분에서 7 분 사이일 확률이 높겠구나"라고 확률적으로 예측합니다.
  • 장점: AI 를 새로 훈련할 필요도 없고, 매우 빠르고 정확합니다.

2. "불"과 "식탁"을 모두 고려한 비용 계산 (비용 모델링)

• 기존 방식: 요리 시간 (계산 능력) 만 계산했습니다.
• SageSched 방식: 요리 시간 + 식탁 차지하는 공간을 합쳐서 '전체 비용'을 계산합니다.
  • 비유: "시간은 1 분이지만 식탁을 10 개나 차지하는 요리"와 "시간은 5 분이지만 식탁을 1 개만 차지하는 요리"를 비교할 때, 단순히 시간만 보면 안 되고 식탁 공간까지 고려해서 누가 먼저 해야 전체가 더 빨리 끝날지 계산합니다.

3. "기다림의 확률"을 계산하는 지능형 대기열 (스케줄링)

• 기존 방식: 예상 평균 시간을 기준으로 줄을 세웠습니다. (예: 평균 5 분 걸리는 요리를 먼저 시킴)
• SageSched 방식: **기트킨스 지수 (Gittins Index)**라는 수학적 공식을 사용합니다.
  • 비유: 단순히 "평균 5 분"이 아니라, "이 요리는 지금 당장 끝날 확률이 높을까, 아니면 오래 걸릴 확률이 높을까?"를 따집니다.
  • 만약 A 요리는 1 분 안에 끝날 확률이 90% 라면, B 요리는 10 분 걸릴 확률이 90% 라면, 평균이 비슷해도 A 요리를 먼저 시켜서 빨리 끝내는 것이 전체 손님의 만족도 (대기 시간) 를 높입니다.
  • 또한, 요리가 진행되면서 남은 시간이 바뀔 때마다 줄서기 순서를 수시로 다시 정해줍니다.

---

🏆 결과: 얼마나 빨라졌나요?

이 새로운 시스템 (SageSched) 을 테스트해 본 결과, 기존 시스템들보다 최종 답변이 나오는 시간 (TTLT) 을 28.7% 이상 단축시켰습니다.

• 간단한 비유: 기존에는 100 분 걸리던 대기열이, SageSched 를 쓰면 70 분 정도로 줄어든 셈입니다.
• 핵심: "무엇을 먼저 할지"를 단순히 순서대로가 아니라, **불확실한 미래 (얼마나 걸릴지 모른다는 점)**와 **제한된 자원 (메모리와 계산 능력)**을 모두 고려해서 가장 현명하게 결정했기 때문입니다.

💡 한 줄 요약

"SageSched 는 AI 가 여러 사람의 질문을 처리할 때, '과거 기록'을 보고 '예상 시간'을 유추하고, '식탁 공간'까지 고려해서 가장 똑똑하게 줄을 서게 만들어, 모든 사람이 더 빨리 답을 받을 수 있게 해주는 똑똑한 주방장입니다."

기술 요약

1. 문제 정의 (Problem)

대규모 언어 모델 (LLM) 추론 작업의 스케줄링은 사용자 경험 (특히 마지막 토큰 도달 시간, TTLT) 을 최적화하는 데 필수적이지만, 기존 방식은 다음과 같은 두 가지 고유한 특성으로 인해 비효율적입니다.

• 수요의 불확실성 (Demand Uncertainty): LLM 은 자기회귀 (auto-regressive) 방식으로 동작하므로, 입력 프롬프트가 주어졌을 때 출력 토큰의 길이가 사전에 결정되지 않습니다. 기존 OS 나 빅데이터 워크로드는 안정적인 자원 요구량을 가지지만, LLM 은 실행이 완료될 때까지 최종 길이를 알 수 없습니다.
• 하이브리드성 (Hybridity): LLM 추론은 연산 (Compute) 과 메모리 (Memory) 자원을 모두 집약적으로 사용합니다. 특히 KVCache(Key-Value Cache) 를 GPU 메모리에 유지해야 하므로, 메모리 부족이 병목이 될 수 있습니다. 기존 스케줄러들은 주로 연산 비용 (출력 길이) 만 고려하여 메모리 병목 상황을 간과합니다.
• 기존 방식의 한계:
  • FCFS (First-Come-First-Served): vLLM 등 주요 프레임워크에서 사용되지만, 선두에 긴 작업이 오면 후속 작업이 대기하는 'Head-of-Line Blocking'을 유발합니다.
  • 예측 기반 SJF (Shortest Job First): 출력 길이를 예측하여 짧은 작업을 먼저 처리하려는 시도 (SSJF, TRAIL 등) 가 있으나, 단일 값 (Mean) 을 예측하는 방식은 불확실성 분포 정보를 무시하며, 예측 모델 자체의 학습/추론 오버헤드가 크고 정확도가 낮습니다. 또한, 출력 길이만 고려하여 메모리 비용을 무시합니다.

2. 제안 방법론: SageSched

저자들은 수요의 불확실성과 하이브리드성을 효과적으로 처리하기 위해 SageSched를 제안합니다. 이는 세 가지 핵심 기술로 구성됩니다.

가. 시맨틱 인식 기반 히스토리 예측기 (Semantic-aware History-based Predictor)

• 개념: 무거운 예측 모델 (Fine-tuned BERT 등) 을 훈련하여 단일 길이를 예측하는 대신, 유사한 프롬프트를 가진 과거 실행 기록을 참조하여 **출력 길이의 분포 (Distribution)**를 예측합니다.
• 작동 원리:
  1. 최근 처리된 요청들의 프롬프트와 출력 길이를 기록합니다.
  2. 새로운 요청이 들어오면, 프롬프트 임베딩의 코사인 유사도 (Cosine Similarity) 를 계산하여 유사한 과거 요청들을 찾습니다.
  3. 유사한 요청들의 출력 길이 분포를 해당 요청의 예측 분포로 사용합니다.
• 장점: 별도의 모델 학습 (Training) 이 불필요하여 경량화되었으며, 단일 값이 아닌 분포 정보를 제공하여 불확실성을 정량화합니다.

나. 자원 바운드 기반 비용 모델링 (Resource-bound-based Cost Modeling)

• 개념: 출력 토큰 수만 고려하는 기존 방식 대신, **연산 (Compute)**과 메모리 (Memory) 자원을 모두 고려한 통합 비용 모델을 제시합니다.
• 작동 원리:
  • 메모리 병목 (Memory-bound) 상황: KVCache 공간 점유율이 핵심입니다. 입력 길이 ($I$) 와 출력 길이 ($O$) 를 모두 고려하여 누적된 KVCache 사용량을 비용으로 계산합니다.
  • 연산 병목 (Compute-bound) 상황: 총 연산량을 비용으로 계산합니다.
  • 통합 모델: 두 경우 모두 비용 함수가 $C \propto \frac{O^2}{2} + IO$ 형태를 공유함을 발견했습니다. 이를 통해 병목 상황에 관계없이 일관된 비용 모델 ($C = \frac{O^2}{2} + IO$) 을 적용할 수 있습니다.

다. 불확실성 인식 스케줄링 정책 (Uncertainty-aware Scheduling Policy)

• 개념: 각 요청의 비용이 단일 값이 아닌 '분포'로 주어질 때, 최적의 대기열 순서를 결정하기 위해 Gittins Index를 활용합니다.
• 작동 원리:
  • 다중 암 밴딧 (Multi-armed Bandit) 문제와 유사하게, 비용 분포를 기반으로 각 요청의 Gittins Index 를 계산합니다.
  • Gittins Index는 주어진 자원 할당량 ($\Delta$) 내에서 작업을 완료할 확률과 예상 비용을 고려한 '최소 평균 비용' 지표입니다. 이 지수가 낮은 요청을 우선 처리합니다.
  • 동적 갱신: 요청이 실행되는 동안 남은 비용 분포가 변하므로, 특정 구간 (Bucket) 경계에서 Gittins Index 를 주기적으로 갱신하여 스케줄링의 적시성을 보장합니다.

3. 주요 기여 (Key Contributions)

1. 문제 식별: LLM 워크로드의 불확실성과 하이브리드성 (연산/메모리 동시 요구) 이 기존 스케줄러의 비효율성을 초래함을 실험을 통해 규명했습니다.
2. SageSched 설계:
   • 학습 불필요한 경량 시맨틱 기반 히스토리 예측기 (분포 예측).
   • 연산과 메모리를 모두 고려한 통합 비용 모델.
   • 불확실성 분포를 활용한 Gittins Index 기반 스케줄링.
3. 성능 검증: 테스트베드 실험 및 대규모 시뮬레이션을 통해 기존 최첨단 (SOTA) 스케줄러 대비 평균 TTLT 를 28.7% 이상 개선함을 입증했습니다.

4. 실험 결과 (Results)

• 실험 환경: Llama3.1-8B (A40 GPU), Qwen3-32B (H800 GPU) 모델 사용. SharedGPT, Alpaca, Document-Write 등 다양한 실제 워크로드 데이터셋 적용.
• 성능 비교:
  • TTLT (Time-to-Last-Token): SageSched 는 FCFS, FastServe, SSJF, TRAIL 등 기존 기법 대비 최대 28.7% 향상된 성능을 보였습니다. 특히 작업 부하가 높은 환경에서 개선 폭이 큽니다.
  • TTFT (Time-to-First-Token): Head-of-Line Blocking 을 효과적으로 완화하여 TTFT 도 개선되었습니다.
  • 데이터셋별 분석: Alpaca(요약) 데이터셋처럼 입력 길이가 길고 비용 모델링이 어려운 경우에도 SageSched 가 가장 우수한 성능을 발휘했습니다.
• 구성 요소별 분석:
  • 예측기: 시맨틱 기반 히스토리 예측기가 LLM 기반 예측기보다 정확도가 높고 오버헤드가 낮음 (예측 지연 < 0.5ms).
  • 비용 모델: 단순 출력 길이 기반 모델보다 자원 바운드 기반 모델이 TTLT 를 크게 개선.
  • 스케줄링: Gittins Index 기반 정책이 평균값 (Mean) 기반 정책보다 우수하며, 예측 오차 (Noise) 가 있더라도 강건함.
• 확장성 (Scalability): 64 개 GPU 노드까지 확장 시, 스케줄링 및 예측 오버헤드가 선형적으로 증가하지만 전체 작업 시간 (수 초~수 분) 대비 무시할 수준 (약 100ms) 이었습니다.

5. 의의 및 결론 (Significance)

SageSched 는 LLM 서비스의 핵심 병목 현상인 불확실한 출력 길이와 **복합적인 자원 요구 (연산 + 메모리)**를 동시에 해결하는 최초의 체계적인 스케줄링 솔루션입니다.

• 실용성: 별도의 모델 학습 없이 기존 프레임워크 (vLLM 등) 위에 쉽게 통합 가능하며, 경량화된 예측과 정확한 비용 모델링을 통해 실시간 스케줄링 오버헤드를 최소화합니다.
• 이론적 기여: LLM 스케줄링 문제를 다중 암 밴딧 문제로 접근하여 Gittins Index 를 적용함으로써, 불확실성이 존재하는 환경에서 이론적으로 최적의 대기열 성능을 달성할 수 있음을 보였습니다.
• 미래 영향: LLM 서비스의 대규모 배포 시 사용자 경험 (지연 시간) 을 획기적으로 개선하고, GPU 자원의 효율적 활용을 통해 운영 비용을 절감할 수 있는 중요한 기반 기술로 평가됩니다.