LLM 서빙을 위한 기하학 인지 온라인 스케줄링: 이론적 경계에서 시스템 구현까지
Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice
한국어 초록
대화형 대규모 언어 모델(LLM) 서빙이 급격히 증가함에 따라 동적 키-값(KV) 캐시 풋프린트의 효율적인 관리가 추론 성능에 점점 더 중요해지고 있습니다. 최신 추론 시스템은 최단 작업 우선(Shortest Job First)과 같은 시간 중심의 스케줄링 휴리스틱에 압도적으로 의존하고 있습니다. 그러나 이러한 방식의 고전적 보장은 전통적인 스케줄링 모델링에 기반을 두고 있어, LLM 추론 메커니즘 특유의 고도로 동적인 2차원 시공간 기하학적 증가를 포착하지 못합니다. 이를 해결하기 위해 본 논문에서는 최소 볼륨 우선(Smallest Volume First, SVF) 알고리즘과 그 고효율 변형인 1-bit SVF를 도입하여 기하학 인지 온라인 스케줄링을 제안합니다. 새로운 볼륨 인증서(volume-certificate) 증명을 통해, 고동시성 LLM 서빙 환경에서 SVF의 최악 조건 근사비가 \textbf{3}에 근접함을 규명하였으며, 이는 기존 최선의 상수인 48을 대폭 개선한 결과입니다. 이러한 핵심적 돌파구를 바탕으로, 다양한 트래픽 시나리오와 정보 가용성에 걸쳐 알고리즘을 분석하는 포괄적인 이론적 분류 체계를 완성했습니다. 시스템 구현 측면에서는 본 접근법을 vLLM의 플러그 앤 플레이 계층으로 매끄럽게 통합했습니다. Llama-3.1 모델을 대상으로 한 광범위한 평가는 종합적인 성능 향상을 입증합니다. SVF는 평균 지연 시간과 꼬리 지연 시간(tail latency)을 모두 크게 단축하며, 1-bit SVF는 단 1비트의 정보만으로도 경쟁력 있는 처리량과 지연 시간을 달성합니다. 본 연구는 최신 LLM 배포 환경에서 메모리 제약적 스케줄링 문제를 해결하기 위한 이론적으로 건실하고 실증적으로 검증된 접근법을 제시합니다. 향후 연구를 촉진하기 위해 코드는 https://github.com/Li-Beverly-Kong/Geometry-Aware-Online-Scheduling.git 에 공개되어 있습니다.
원문 초록
The rapid growth of interactive Large Language Model serving has made efficient management of dynamic Key-Value cache footprints increasingly important for inference performance. Modern inference systems overwhelmingly rely on time-centric scheduling heuristics, such as Shortest Job First. However, their classical guarantees are rooted in traditional scheduling modeling, failing to capture the highly dynamic, 2D spatio-temporal geometric growth specific to LLM inference mechanisms. To resolve this, we propose the geometry-aware online scheduling by introducing the Smallest Volume First (SVF) algorithm and its highly efficient variant, 1-bit SVF. Via a novel volume-certificate proof, we establish a worst-case approximation ratio for SVF that approaches \textbf{3} in the high-concurrency regime of LLM serving, substantially improving upon the prior best constant of 48. Building upon this core breakthrough, we complete a comprehensive theoretical taxonomy analyzing our algorithms across different traffic scenarios and information availability. Practically, we seamlessly integrate our approach as a plug-and-play layer in vLLM. Extensive evaluations on Llama-3.1 models demonstrate comprehensive performance gains: SVF delivers strong reductions in both average and tail latency, while 1-bit SVF, with merely a single bit of information, achieves competitive throughput and latency. This work establishes a theoretically sound and empirically proven approach for resolving memory-constrained scheduling in modern LLM deployments. To facilitate future research, our code is available at https://github.com/Li-Beverly-Kong/Geometry-Aware-Online-Scheduling.git.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.22327v3
- arXiv:2606.22327v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Crossflow: 에이전트 LLM 서빙을 위한 Prefill-Decode 탄력성
Crossflow: Prefill-Decode Elasticity for Agentic LLM Serving
서빙 용량 수요가 학습을 넘어서면서 서빙 효율이 점점 더 중요해진다. Prefill-decode(P/D) 분리는 두 단계의 특화와 격리를 통해 서빙 효율을 높인다. 이러한 이점은 정적 분할에 기반하지만, 단계별 수요는 정적이지 않다. 대규모 LLM 플릿에서 캐시되지 않은 입력 대 출력 토큰 비율은 분 단위 시간 척도에서 피크 대 평균 비가 최대 4.7배에 이르는 것을 관찰했고, 공개 에이전트 트레이스에서는 시간당 비율이 하루 안에서 중앙값 24.5배 범위에 걸치는 반면, 레플리카 재할당에는 수십 분이 걸린다. 에이전트 트래픽은 이러한 불일치를 더욱 심화시킨다. 각 풀을 95백분위수로 크기를 잡으면 클러스터 용량의 최대 17%가 미사용으로 남고, 그보다 작게 잡으면 동일한 불균형이 대기와 실현되지 못한 처리량으로 전환된다. 노드 역할을 바꾸지 않고 이 경계를 탄력적으로 만드는 Crossflow를 제안한다. 각 디코드 노드는 로컬 prefill 연산, KV 용량, 전송 작업, 예상 출력을 한정하는 단기·철회 가능한 lease를 공개한다. 공개 및 내부 트레이스에서 Crossflow는 정적 P/D 대비 기하평균 토큰 처리량을 16.2–17.4% 향상시키고, 고부하에서는 최대 43.4%까지 개선하며, 평가한 모든 지점에서 평균 TTFT를 줄인다.
효율적인 대규모 언어 모델 서빙을 향하여: 시스템 인식 KV 캐시 최적화 서베이
Towards Efficient Large Language Model Serving: A Survey on System-Aware KV Cache Optimization
대규모 언어 모델(LLM)의 빠른 발전에도 불구하고, LLM 모델 서빙 시스템은 여전히 메모리 집약적이고 비용이 많이 든다. 자기회귀 디코딩(autoregressive decoding) 과정에서 KV 텐서를 저장하는 키-값(KV) 캐시는 저지연, 고처리량 LLM 추론 서빙을 가능하게 하는 핵심 요소이다. 본 서베이에서는 LLM 서빙을 위한 시스템 인식 KV 인프라(sKis)에 초점을 맞춘다. 시스템 동작 관점에서 최근 연구를 재검토하며, 기존 연구를 세 가지 차원으로 정리한다: 실행 및 스케줄링(시간적), 배치 및 마이그레이션(공간적), 표현 및 보존(구조적). 나아가, 교차 동작 공동 설계 친화성과 동작-목표 연관성을 분석하여 향후 연구 기회를 조명한다. 본 연구는 빠르게 발전하는 분야를 체계화함으로써 현대 LLM 모델 서빙 인프라에서 KV 캐시 설계를 이해하고 혁신하기 위한 토대를 마련한다.
SMetric: 균형 잡힌 세션 중심 스케줄링으로 에이전트 서빙을 위한 LLM 스케줄링 재고
SMetric: Rethink LLM Scheduling for Serving Agents with Balanced Session-centric Scheduling
LLM 스케줄링은 서빙에 있어 매우 중요하지만, 기존 설계가 에이전틱 서빙--인간 대신 에이전트가 LLM 요청을 발행하는 환경--에 얼마나 잘 부합하는지는 여전히 불분명하다. 이로 인해 워크로드는 두 가지 방식으로 변화한다: (1) 에이전트는 완전한 응답에 대해서만 행동하므로 클러스터의 초당 토큰 수(TPS)가 주요 목표가 되고 토큰당 지연 시간 요건은 완화되지만 제거되지는 않는다; (2) 요청들 간에 KV$ 재사용이 상당 부분 공유되는데, BAILIAN의 프로덕션 트레이스에서는 요청 토큰의 80% 이상이 재사용되는 반면 채팅에서는 54-62%에 그친다. 본 논문은 먼저 두 가지 실제 트레이스를 대상으로 에이전트를 위한 요청 스케줄링에 대한 체계적인 연구를 기여한다. 우리는 KV$ 재사용을 높이기 위해 기존 스케줄러들이 KV$를 캐시한 인스턴스로 요청을 과도하게 라우팅하여, 일부 인스턴스에 과부하가 걸리고 나머지는 유휴 상태로 남아 TPS가 제한된다는 것을 발견한다. 이에 우리는 두 가지 핵심 통찰을 제시한다: (1) 글로벌 계층 KV$ 저장소 덕분에 로드 밸런싱이 KV$ 재사용을 전부 희생할 필요가 없으며, (2) 워크로드의 세션 내 지역성을 활용하면 소수의 요청--각 에이전트 세션의 첫 번째 요청--만 균형을 맞추는 것으로도 로컬 인스턴스의 대부분의 KV$ 재사용을 희생하지 않고 클러스터 전체의 균형을 유지할 수 있다. SMETRIC은 이러한 통찰을 균형 잡힌 세션 중심 스케줄링으로 실현한다: 각 세션의 첫 번째 요청은 순전히 로드 밸런싱을 위해 라우팅하고 후속 요청은 캐시 인식 방식으로 처리함으로써, 글로벌 계층에 대한 수요를 낮게 유지하면서 로드 밸런싱과 로컬 재사용을 모두 보존한다. 스케줄링 메트릭으로 세션 턴 정보를 사용하는 것은 의도적이다: 이는 사용자 입력만으로 효율적이고 정확하게 도출되므로 스케줄러는 간결하고 상태 비저장(stateless) 방식을 유지한다. SMETRIC은 글로벌 저장소를 갖춘 프리필-디코드 코로케이션 환경에서 최신 스케줄러 대비 클러스터 TPS를 10-16% 향상시키고, 분리(disaggregation) 환경에서 프리필 TPS를 2-34% 향상시키며, 토큰당 지연 시간도 함께 개선한다.
PEEK: 대규모 언어 모델 서빙을 위한 예측적 큐 정보 기반 KV 캐시 관리
PEEK: Predictive Queue-Informed KV Cache Management for LLM Serving
본 논문에서는 온라인(스트리밍) 및 오프라인(배치) 대규모 언어 모델(LLM) 서빙 모두를 위한 경량 스케줄링 및 제거 프레임워크인 PEEK를 소개하며, 이 논문은 온라인 환경에 초점을 맞춘다. PEEK는 대기 큐에 대해 점진적 래딕스 트리를 유지하여 기존 엔진에서는 드러나지 않는 접두 문맥 공유 클러스터를 노출한다. 오버헤드가 낮은 이중 탐색(dual-walk)은 트리를 엔진의 접두 문맥 캐시와 대조하여 대기 중인 모든 요청에 대해 최장 접두 문맥 매칭을 도출하며, PEEK는 클러스터 선두 요청을 먼저 수용하여 이후 요청들이 새로 캐시된 접두 문맥을 상속받도록 하고, 공동 설계된 제거 훅(eviction hook)이 대기 중인 요청의 상위 블록을 보호하며, 다중 레인 스트라이드 스케줄러가 기아 현상을 억제한다. SGLang 및 vLLM에서 최대 4×H100(DP=2, TP=2)을 사용하는 5가지 워크로드에 대해, PEEK는 각 엔진의 가장 강력한 기본 기준선(SGLang/vLLM) 대비 캐시 히트 최대 3.0×/2.6×, TTFT 7.9×/7.1×, E2E 6.7×/5.5×, 처리량 3.6×/4.5× 향상을 달성하며, 활용 가능한 접두 문맥 구조가 없는 워크로드에서는 기준선과 노이즈 범위 내에서 동등한 성능을 보인다. KV 캐시 부하와 추론 병렬성이 확장될수록 성능 향상은 유지된다.
HERALD: High-Throughput Block Diffusion LLM Inference via CPU-GPU Cooperative KV Cache Retrieval
PReCache: 저랭크 사전 계산 및 중립적 재구성을 통한 다중 LoRA 에이전트를 위한 효율적인 KV 캐시 공유
PReCache: Efficient KV Cache Sharing for Multi-LoRA Agents via Low-Rank Precomputation and Neutral Reconstruction
다중 LoRA(Multi-LoRA) 에이전트 시스템은 공통 백본 모델(backbone model)을 공유함으로써 효율적인 역할 특화(role specialization)를 가능하게 합니다. 그러나 장기 궤적(long-horizon) 태스크에서는 각 에이전트가 증가하는 공유 궤적을 반복적으로 처리하고 자체 KV 캐시를 구축하므로 상당한 메모리 및 연산 중복이 발생합니다. 기존의 KV 캐시 공유 방법들은 이러한 반복적인 프리필(prefill)을 줄이지만, 추가적인 학습(training)이나 아키텍처 제약을 요구하거나 상당한 양의 모델 연산을 그대로 남겨둡니다. 또한 캐시를 직접 재사용하면 현재 에이전트가 이전 에이전트의 어댑터에 의해 생성된 캐시 상태에 의존하게 되어 자체 LoRA에 인코딩된 역할별 고유 동작이 약화됩니다. 본 논문에서는 사전학습된 가중치로 계산된 베이스 캐시를 공유하고 에이전트별 소형 저랭크(LR, low-rank) 캐시를 사전 계산하는 두 가지 설계(PreLRShared 및 ReBaseShared)를 갖춘 학습이 필요 없는(training-free) KV 캐시 공유 프레임워크인 PReCache를 제시합니다. 반복적인 프리필을 제거하기 위해 PreLRShared는 공유 컨텍스트가 처음 처리될 때 각 에이전트의 LR 캐시를 사전 계산하여, 현재 에이전트가 이전 에이전트가 처리한 컨텍스트를 재처리하지 않고도 자체 LR 캐시를 사용할 수 있도록 합니다. 공유 정확도를 향상하기 위해 ReBaseShared는 어댑터가 없는 은닉 상태(hidden states)로부터 공유 베이스 캐시를 재구성하여 이전 에이전트의 어댑터 표현으로 인해 발생하는 잔여 오차를 줄입니다. 재구성 비용을 최소화하기 위해 단일 스트림 추론과 동시 서빙에 맞춘 두 가지 추론(inference) 방식을 제안하며, 이는 각각 각 에이전트의 턴 이후 또는 실행과 병행하여 동일한 재구성을 수행합니다. 다양한 모델과 에이전트 벤치마크에 걸쳐 PreLRShared는 KV 캐시 공유가 없는 추론 대비 최대 3.1배의 TTFT(Time to First Token) 속도 향상과 2.3배의 요청당 처리량 개선을 달성합니다. ReBaseShared는 평가된 캐시 공유 방법 중 전반적으로 정확도를 가장 잘 보존하며, 캐시 공유가 없는 추론 대비 평균 하락폭이 1.1점에 불과합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.