기술 요약: LLM 추론 및 AI 에이전트를 위한 처리량 최적화 스케줄링 알고리즘

문제 정의

대형 언어 모델 (LLM) 과 AI 에이전트에 대한 수요가 증가함에 따라 추론 시스템의 효율성을 최적화하는 것이 필수적입니다. 상당한 엔지니어링 노력이 시스템 수준의 개선에 집중되어 왔지만, 스케줄링 알고리즘을 평가하기 위한 통합된 수학적 모델링 및 대기행렬 이론적 프레임워크는 부족합니다. 구체적으로, 이 논문은 다음과 같은 근본적인 질문에 답합니다: LLM 추론 시스템의 최대 처리량률은 무엇이며, 어떤 클래스의 스케줄링 알고리즘이 이 한계에 도달할 수 있는가?

LLM 추론은 고전적인 대기행렬 시스템과 비교하여 고유한 도전 과제를 제시합니다:

1. 이중 단계 처리: 요청은 입력 토큰을 처리하여 KV 캐시를 구축하는 계산 병목(prefill) 단계를 거친 후, 메모리 I/O 병목인 디코드 (autoregressive token generation) 단계를 거칩니다.
2. 배칭 제약: GPU 활용도를 극대화하기 위해 요청을 배칭합니다. 그러나 prefill 토큰과 decode 토큰을 혼합하면 간섭이 발생하며, 하드웨어는 토큰 예산 ($b_{max}$) 과 종종 배치 크기 ($k_{max}$) 제약을 부과합니다.
3. AI 에이전트 워크로드: 현대 애플리케이션은 복잡한 에이전트 작업을 처리하는 LLM 서버 네트워크를 포함하며, 이는 방향성 비순환 그래프 (DAG) 위상, 포크 - 조인 (fork-join) 패턴, 또는 순환 라우팅을 따를 수 있습니다.

기존 시스템은 다양한 전략 (예: FasterTransformer, vLLM, Orca, Sarathi-Serve) 을 채택하며, 서로 다른 우선순위 (prefill 우선 vs decode 우선) 와 배칭 기능 (혼합 vs 분리) 을 가지고 있습니다. 실무자들은 현재 시스템 선택을 위해 비용이 많이 들고 워크로드에 특화된 벤치마킹에 의존하고 있으며, 안정성이나 처리량 최적화에 대한 이론적 보장은 부족합니다.

방법론

저자들은 LLM 추론 시스템을 모델링하기 위한 엄격한 대기행렬 이론적 프레임워크를 개발했습니다.

1. 확률적 모델링

• 기본 모델: 시스템은 두 클래스의 배치 서비스 대기행렬을 나타내는 이산 시간 마르코프 체인 (DTMC) 으로 모델링됩니다.
  • 클래스: 요청은 prefill 대기열 또는 decode 대기열 중 하나에 존재합니다.
  • 배칭: 서버는 토큰 예산 $b_{max}$에 따라 두 대기열에서 토큰 배치를 동시에 처리합니다.
  • 비대칭성: 단일 요청의 prefill 토큰은 대량으로 처리될 수 있지만, decode 토큰은 엄격하게 순차적 (배치당 요청당 하나) 입니다.
• 처리 시간 모델: 실증적 추적을 활용하여 배치 처리 시간 $t_b$는 토큰 부하 $b$에 의존하는 구간별 상수 함수로 근사됩니다:
  $$t_b = c + a \cdot \lceil b/b_0 \rceil$$
  여기서 $c$는 기본 비용이고, $a$는 $b_0$개의 토큰 블록당 한계 비용입니다. 이 모델은 LLM 추론에서 선형 계층 계산의 지배력을 포착합니다.

2. 분석적 프레임워크

• 유체 한계 (Fluid-Limit) 기법: 저자들은 안정성을 분석하기 위해 유체 한계 프레임워크 (Dai 1995, Stolyar 1995) 를 사용합니다. 특정 조건 하에서 스케일링된 확률 과정이 결정론적 유체 모델로 수렴함을 증명합니다.
• 안정성 정의: 시간이 무한대에 접근함에 따라 처리되지 않은 토큰의 총수가 발산하지 않으면 시스템이 안정적 (양수 재귀적) 입니다.
• 스케줄링 클래스: 분석은 가능한 경우 배치를 용량 $b_{max}$까지 채우는 작업 보존 (work-conserving) 알고리즘에 초점을 맞추며, 혼합 배칭의 복잡성을 처리하기 위해 K-FCFS 조건 (제한된 오버테이킹을 가진 선착순) 을 도입합니다.

3. 확장

프레임워크는 다음과 같이 확장됩니다:

• 병렬 서버: 부하 분산 (무작위 또는 가장 짧은 대기열 Join) 을 가진 시스템.
• 다중 클래스 네트워크: 여러 요청 클래스 (예: 다른 에이전트 단계) 를 처리하는 단일 서버.
• 네트워크 위상: DAG 라우팅 및 포크 - 조인 동기화를 가진 다중 서버 네트워크.
• 순환 라우팅: 피드백 루프가 있는 네트워크 분석 (Rybko–Stolyar 유형).
• 배치 크기 제약: 토큰 예산 ($b_{max}$) 과 최대 배치 크기 ($k_{max}$) 모두로 제약된 시스템 분석.

주요 기여 및 결과

1. 작업 보존 스케줄링의 처리량 최적성

이 논문은 근본적인 설계 원칙을 확립합니다: 단일 서버 LLM 추론 및 DAG 또는 포크 - 조인 위상을 가진 네트워크의 경우 작업 보존 스케줄링 알고리즘이 최대 처리량을 달성합니다.

• 정리 2: 단일 서버의 경우, 도착 부하 $\lambda(m_p + m_d)$가 최대 처리율 $b_{max}/t_{b_{max}}$보다 작으면, 모든 작업 보존 K-FCFS 알고리즘이 시스템을 안정화합니다. 반대로, 부하가 이 임계값을 초과하면 어떤 알고리즘 하에서도 시스템은 불안정합니다.
• 함의: 이는 이론적 상한 ($b_{max}/t_{b_{max}}$) 을 제공하며, 산업계가 작업 보존 스케줄러로 전환하는 것을 검증합니다.

2. 기존 시스템 평가

실제 알고리즘에 이론적 프레임워크를 적용하면 명확한 분류가 도출됩니다:

• 처리량 최적 (작업 보존):
  • Orca: prefill 우선순위를 가진 혼합 배칭 (prefill + decode) 을 지원합니다.
  • Sarathi-Serve: decode 우선순위와 혼합 배칭을 지원하는 청크화된 prefill 을 지원합니다.
  • 최신 vLLM (청크화된 prefill 포함): 작업 보존적입니다.
• 비최적/불안정 (비작업 보존):
  • FasterTransformer: 디코드를 우선시하지만 혼합 배칭을 금지합니다. prefill 요청이 대기 중이더라도 디코드 요청이 배치를 채우기에 충분하지 않으면 GPU 를 유휴 상태로 둡니다.
  • Vanilla vLLM: prefill 을 우선시하지만 혼합 배칭을 금지합니다. prefill 전용 배치를 처리하는 동안 decode 요청이 대기하게 됩니다.
• 실험적 검증: 실제 추적을 통해 비작업 보존 알고리즘 (FasterTransformer, vanilla vLLM) 은 작업 보존 알고리즘 (Sarathi-Serve, Orca) 이 안정적으로 유지되는 중간 부하 하에서도 불안정 (대기열 폭주) 됨이 확인되었습니다.

3. AI 에이전트 워크로드 및 네트워크 위상

• DAG 및 포크 - 조인: 이 논문은 각 서버에서 부하 조건이 성립하는 경우, DAG 또는 포크 - 조인 위상으로 배열된 LLM 서버 네트워크의 경우에도 작업 보존 스케줄링이 처리량 최적임을 증명합니다.
• 순환 라우팅 (Rybko–Stolyar 반례): 저자들은 순환 라우팅이 있는 네트워크의 경우 작업 보존 스케줄링만으로는 불충분함을 보여줍니다. 총 부하가 용량 미만일지라도 작업 보존 정책 하에서 특정 우선순위 할당이 불안정을 초래하는 두 서버 네트워크를 구성합니다. 이는 순환 위상에서 신중한 우선순위 설계나 비작업 보존 정책 (예: 백프레셔) 의 필요성을 강조합니다.

4. 배치 크기 제약의 영향

최대 배치 크기 제약 ($k_{max}$) 이 토큰 예산 ($b_{max}$) 과 함께 부과될 때:

• 안정성 영역은 단순한 스칼라 임계값이 아닌 $(\lambda_{prefill}, \lambda_{decode})$ 평면에서 2 차원 볼록 껍질이 됩니다.
• 반직관적 발견: 특정 영역 (특히 혼합 배치를 포함하는 안정성 영역의 꼭짓점 근처) 에서, 항상 $b_{max}$까지 채우는 엄격한 작업 보존 알고리즘은 시스템을 안정화하지 못할 수 있습니다. 최적의 안정성은 prefill 및 decode 토큰의 처리 속도를 균형 있게 맞추기 위해 더 낮은 토큰 부하 (예: $b_0$) 에서 작동해야 할 수 있습니다. 이는 엄격한 배치 크기 제약 하에서는 적응형 스케줄링 전략이 필요함을 시사합니다.

중요성 및 주장

이 논문은 LLM 추론 스케줄링에 대한 최초의 엄격한 대기행렬 이론적 기초를 제공한다고 주장합니다. 그 중요성은 다음과 같습니다:

1. 설계 원칙: "작업 보존"을 실무자를 위한 핵심 설계 원칙으로 식별하여, Sarathi-Serve 및 Orca 와 같은 알고리즘이 처리량 최적임을 이론적으로 보장하고, FasterTransformer 및 vanilla vLLM 과 같은 비혼합 배칭 접근법을 경고합니다.
2. 커뮤니티 간 연결: LLM 의 고유한 이중 단계 및 배칭 특성을 포착하는 공식 모델을 제공함으로써 대기행렬 이론 커뮤니티가 LLM 시스템에 기여하는 장벽을 낮춥니다.
3. AI 에이전트 지침: 안정성 분석을 AI 에이전트 워크로드로 확장하여, DAG 위상은 견고하지만 순환 위상은 단순한 작업 보존 정책보다 더 정교한 스케줄링이 필요함을 밝힙니다.
4. 미묘한 제약: 배치 크기 제한과 같은 실제 제약이 안정성 영역을 근본적으로 변경할 수 있음을 밝혀, "배치를 채우는 것"이 항상 최적이라는 가정에 도전합니다.

저자들은 그들의 작업이 처리량 최적성을 위한 기준선을 확립하지만, 향후 연구는 지연 시간 최적화, 더 풍부한 처리 시간 모델 (어텐션 계층 포함), 그리고 복잡한 제약 및 네트워크 위상을 위한 적응형 알고리즘 설계에 초점을 맞춰야 한다고 결론지었습니다.