145편 · 약 11분

Sorted-F: 비균질 프리필·디코드 길이에서 표준 스케줄러의 근사비가 무한대가 되는 이유와 F-메트릭 해법

# Sorted-F: 비균질 프리필·디코드 길이에서 표준 스케줄러의 근사비가 무한대가 되는 이유와 F-메트릭 해법

요약

LLM 서빙 시스템은 매 순간 "어떤 요청을 지금 배치로 묶어 실행할 것인가"를 결정해야 한다. 이 스케줄링 문제는 요청마다 프리필(입력 토큰 수)과 디코드(생성 토큰 수) 길이가 제각각일 때 문제의 본질이 달라진다.

2026년 6월 v4로 갱신된 arXiv 논문 "LLM Serving Optimization with Variable Prefill and Decode Lengths"(arXiv:2508.06133)은 이 상황을 형식화하고 두 가지 중요한 결과를 보인다.

FCFS(선착순), 최단출력우선, 총크기기반 정렬 같은 표준 정책은 근사비가 무한대가 될 수 있다.
Sorted-F 알고리즘은 고정된 KV 캐시 메모리 예산 아래서 상수 인수 근사(constant-factor approximation) 를 보장한다.

저자: Meixuan Wang (Tsinghua University), Yinyu Ye (Stanford University·HKUST), Zijie Zhou (HKUST).

왜 스케줄링이 어려운가: 이중 메모리 동적성

LLM 서빙 요청은 두 단계를 거친다.

프리필(Prefill): 입력 토큰 전체를 한 번에 처리하고 KV 캐시를 생성한다. 입력 길이가 P 토큰이면 처리 후 KV 캐시는 P에 비례한다.
디코드(Decode): 토큰을 한 개씩 자기회귀(autoregressive)로 생성하며 KV 캐시가 한 토큰씩 늘어난다. D 토큰을 생성하면 최종 KV 캐시 크기는 P + D에 비례한다.

서빙 엔진이 고정된 KV 캐시 메모리 예산 M을 가질 때, 이 메모리는 현재 배치에 들어 있는 모든 요청의 누적 KV 캐시 크기를 수용해야 한다. 배치가 실행되는 동안에도 디코드 요청들이 계속 메모리를 소비하므로, 새 프리필 요청을 추가할 여유가 시시각각 변한다.

여기서 비균질 프리필·디코드 길이 문제가 어려워지는 이유가 드러난다. 긴 프리필 요청 하나를 배치에 넣으면 초기에 메모리를 많이 쓰고, 긴 디코드 요청은 배치를 오래 점거해 다른 요청의 입장을 막는다. 두 효과가 겹치면 스케줄러의 결정이 전체 지연에 큰 영향을 준다.

표준 정책의 실패: 근사비가 무한대

논문은 세 가지 직관적인 정책이 최적 대비 임의로 나쁜 결과를 낼 수 있음을 증명한다.

정책	설명	실패 원인
FCFS (선착순)	도착 순서대로 스케줄	긴 프리필이 짧은 디코드를 오래 막음
Shortest Output First	디코드 길이가 짧은 요청 우선	프리필 길이를 무시해 메모리 압박 발생
Total Size Priority	프리필+디코드 합 기준 정렬	혼합 배치의 메모리 동적성을 설명 못 함

직관적 예: 프리필 512 토큰·디코드 2 토큰인 요청 하나와 프리필 8 토큰·디코드 8 토큰인 요청 100개가 동시에 도착했다고 하자. FCFS가 대형 프리필 요청을 먼저 실행하면 100개의 짧은 요청 전체가 대기하게 된다. 최적 스케줄러는 짧은 요청들을 먼저 처리해 전체 지연을 대폭 줄인다. 이 격차는 요청 수가 늘수록 임의로 커진다.

이 문제 자체는 NP-hard임도 증명된다. 최적해를 다항 시간에 구할 수 없으므로 근사 알고리즘이 현실적 대안이다.

F-메트릭과 Sorted-F 알고리즘

F-메트릭이란

Sorted-F의 핵심은 F-메트릭이다. F-메트릭은 특정 요청을 배치에 추가했을 때의 이득(배치 크기 및 처리량 증가)과 비용(이후 디코드 단계에서 해당 요청이 점유하는 메모리) 을 하나의 수치로 요약한다.

직관적으로:

프리필이 짧고 디코드도 짧은 요청은 이득이 크고 비용이 작아 F-메트릭이 높다.
프리필이 짧아도 디코드가 매우 긴 요청은 배치를 오래 점거하므로 F-메트릭이 낮아진다.
프리필이 긴 요청은 초기 메모리 소비가 커서 다른 요청의 입장을 막아 F-메트릭이 낮아진다.

Sorted-F 절차

정렬: 대기 중인 요청들을 F-메트릭 내림차순으로 정렬한다.
배치 구성: 메모리 예산 M을 초과하지 않는 범위에서 F-메트릭이 높은 요청부터 배치에 추가한다.
실행 후 반복: 해당 배치를 실행하고, 남은 요청으로 다음 배치를 구성한다.

Sorted-F는 이 과정에서 상수 인수 근사를 달성한다. 최적해의 상수 K배 이내에서 전체 종단 지연을 유지함이 이론적으로 증명된다.

추가 구현체 스펙트럼

논문은 실용적 필요에 따라 여러 변형을 함께 제시한다.

구현체	대상 환경	특징
정확 동적 프로그래밍(DP)	소규모 인스턴스	최적해 도출, 지수 시간 복잡도
Local-Search	중규모	배치 구성 탐색을 반복 개선
Greedy 휴리스틱	대규모 실용	선형 시간, Sorted-F의 실용 근사
LP-guided 변형	처리량 기준	LP 완화로 배치 경계 유도
Receding-Horizon 변형	온라인 환경 근사	일정 구간 앞만 내다보는 슬라이딩 윈도

배치 구성 구조 다이어그램

FCFS (선착순)

대기열 (도착 순서)

P=512
D=3
①

P=48
D=10
②

P=32
D=6
③

P=256
D=5
④

↓ 순서대로 선택

배치 1: ① (P=512·D=3)
메모리 조기 소진 → ②③④ 대기

⚠ 짧은 요청 3개 추가 지연

Sorted-F

F-메트릭 계산 후 정렬

P=48
D=10
F↑ 최고

P=32
D=6
F↑

P=256
D=5
F↓

P=512
D=3
F↓ 최저

↓ 예산 M 내에서 F 순으로 채움

배치 1: F↑ 두 요청 묶음
메모리 효율·짧은 요청 먼저

↓ 상수 인수 근사 보장

KV 캐시 메모리 예산 아래 혼합 배치 스케줄링: FCFS vs Sorted-F

평가: 이기종 워크로드에서의 결과

논문은 다음 두 가지 워크로드를 혼합해 실험했다.

단답형 대화(Short Conversation): 프리필 수십 토큰, 디코드 수십~수백 토큰
장문 요약(Long-Doc Summarization): 프리필 수천 토큰, 디코드 수백 토큰

이 혼합 환경에서 Sorted-F와 그 변형들이 FCFS·최단출력우선 대비 일관적으로 낮은 종단 지연을 달성했다. 소규모 인스턴스에서 정확 DP 결과가 LP 완화 하한에 근접함을 보여, F-메트릭 기반 배치 구성의 유효성을 뒷받침한다.

운영 함의

어떤 워크로드에서 차이가 나는가

프리필·디코드 길이 분포가 균질하다면 — 예를 들어 모든 요청이 비슷한 길이의 대화라면 — FCFS도 실용적으로 충분하다. 차이가 두드러지는 상황은 다음과 같다.

RAG + 챗 혼합 서빙: RAG 요청은 검색 문서를 포함해 프리필이 수천 토큰이지만, 일반 챗은 수십 토큰이다. 이 혼합을 FCFS로 서빙하면 RAG 요청이 챗 요청을 블로킹한다.
요약 + 분류 혼합: 긴 문서 요약(장 프리필·중간 디코드)과 짧은 레이블 분류(단 프리필·단 디코드)가 섞일 때.
KV 캐시 타이트 운영: 메모리 예산을 빡빡하게 설정할수록(GPU 점유율을 높이기 위해) 스케줄러 선택의 영향이 커진다.

온라인 설정에서의 한계

이 논문의 이론적 분석은 오프라인 모델 — 요청이 이미 모두 도착해 있다는 가정 — 에 기초한다. 실제 서빙은 요청이 연속적으로 도착하는 온라인 설정이다. Receding-Horizon 변형이 이 간극을 일부 줄이지만, 온라인 설정의 이론적 보장은 별도 연구 과제로 남아 있다.

Open Questions

논문 v4(2026-06-28) 갱신에서 v1 대비 알고리즘이나 결과가 어떻게 달라졌는지 공개된 세부 정보가 부족하다.
온라인 설정(요청이 점진적으로 도착)에서 Sorted-F 계열의 이론적 보장이 어느 수준까지 성립하는지 열린 문제다.
vLLM, SGLang 등 실제 프로덕션 서빙 엔진에 F-메트릭 기반 스케줄러가 구현된 사례가 아직 보고되지 않았다.