Continuous Batching과 PagedAttention

 

Introduction

 

구분	직접 구현	vLLM
스케줄링 단위	배치 단위 - 배치 종료까지 대기	iteration(=forward pass 1회) 단위
빈 슬롯 처리	먼저 끝난 요청의 자리가 유휴 상태로 잠김	종료 즉시 새 요청 투입
KV cache 관리	없음 (max_len만큼 연속 할당 가정)	블록 단위 페이징, on-demand 할당
prefill / decode	구분 없음	성격이 다른 워크로드로 구분해 혼합 스케줄링
메모리 부족 시	OOM	preemption 후 재계산

핵심

배칭의 본질은 "요청을 모으는 것"이 아니라 매 forward pass마다 GPU를 놀리지 않도록 스케줄링하는 것
그 전제 조건은 KV cache를 OS의 가상 메모리처럼 다루는 것

 

---

prefill과 decode는 다른 작업

• LLM 추론은 성격이 완전히 다른 두 단계로 구성
• 이 구분 없이는 배칭 최적화의 난점 이해 불가

항목	Prefill	Decode
작업	프롬프트 전체 토큰 forward	직전 토큰 1개 forward
병목	Compute-bound	Memory-bandwidth-bound
출력	마지막 위치에서 토큰 1개	토큰 1개
시간 특성	프롬프트 길이 비례, 길면 수 초	짧고 균일, 수백 회 반복

decode가 memory-bound라는 점이 핵심

• 토큰 1개 생성에 모델 가중치 전체를 HBM에서 읽어야 함
• 배치 크기가 1이든 32든 가중치 로딩 비용은 동일
• 즉 배칭 = 이 비용을 여러 요청이 분담하게 만드는 기법
• 배칭이 throughput을 극적으로 끌어올리는 근본 이유

 

---

Problem 1. Static Batching의 빈 슬롯

상황

• CH3 구현 방식(그림 3-3): 큐에서 요청을 모아 배치 구성 → 배치 전체가 끝나야 다음 배치
• 생성 길이는 요청마다 제각각 (20토큰 vs 800토큰)
• 배치는 가장 긴 요청 기준으로 종료

 

결과

• B·C·D는 일찍 종료되었으나 슬롯은 배치 종료까지 잠김
• 대기 중인 새 요청은 GPU에 여유가 있어도 진입 불가
• SM 사용률 30~40% 수준에 머무는 현상 흔히 관측

active_sequence 리스트가 해당 구조 - 배치 루프 종료 후에야 incoming_queue에서 다음 배치 인출

 

---

Solution 1. Continuous Batching

아이디어

• 스케줄링 단위를 "배치"에서 "forward pass 1회"로 하향
• 매 iteration마다 스케줄러가 재판단
  • 종료된 요청 → 즉시 배치에서 제거, KV 블록 반납
  • 대기 중 요청 → 빈 자리에 즉시 투입

• ref. Orca: A Distributed Serving System for Transformer-Based Generative Models
• 현재 vLLM / SGLang / TensorRT-LLM(in-flight batching) / TGI 등 대부분 프로덕션 엔진의 기본 동작

 

구현 트릭 - padding 제거

• 길이가 다른 시퀀스를 묶으려면 통상 right-padding 필요 → padding 자체가 낭비
• vLLM의 우회 방식
  • 배치 내 모든 시퀀스를 하나의 긴 "super sequence"로 flatten & concat
  • position index와 attention mask로 각 시퀀스가 자기 토큰에만 attend하도록 보장
  • 결과적으로 right-padding 없이 continuous batching 성립

forward pass에서의 continuous batching + paged attention

 

---

Problem 2. KV Cache 메모리 낭비

Why?

• continuous batching이 의미를 가지려면 동시 활성 요청 수(concurrency) 확보 필요
• concurrency의 상한을 결정하는 요인 = KV cache 메모리

 

KV cache의 성질

• 크다 - LLaMA-13B 기준 시퀀스 1개당 최대 1.7GB
• 동적이다 - 길이가 사전 확정되지 않고 생성 중 증가

 

낭비가 발생하는 두 경로

• 과다 예약(over-reservation) - 요청마다 max_model_len(예: 4096)만큼 연속 메모리 선점. 평균 실사용 512토큰이면 87% 유휴
• 외부 단편화(fragmentation) - 요청이 제각각 종료되며 재사용 불가능한 틈 발생

(vLLM 논문(Kwon et al., SOSP '23) 측정치: 기존 시스템은 KV cache 메모리의 60~80%를 낭비)

 

---

Solution 2. PagedAttention

아이디어

• KV cache를 OS의 가상 메모리처럼 취급

OS 가상 메모리	PagedAttention
Page	KV block (기본 16토큰)
Byte	Token
Process	Sequence(요청)
Page table	Block table
Physical frame	GPU HBM 물리 블록

동작

• 시퀀스의 논리 블록은 연속, 실제 물리 블록은 GPU 메모리 상에 비연속 배치 허용
• 둘 사이 매핑을 block table이 관리
• 물리 블록은 토큰 생성에 따라 on-demand 할당

KV cache의 블록 분할 - 메모리 공간상 연속일 필요 없음

논리 블록이 block table을 통해 비연속 물리 블록에 매핑되는 과정 

효과

1. 낭비가 마지막 블록에만 국한 → 전체 낭비율 4% 미만 (60~80% → 4%)
2. 동시 배치 가능 시퀀스 수 증가 → continuous batching이 실효를 발휘
3. 메모리 공유가 부수 효과로 획득
   • 여러 시퀀스가 동일 물리 블록 참조 가능
   • reference count + Copy-on-Write로 안전성 보장
   • parallel sampling / beam search 메모리 최대 55% 절감

다중 출력 샘플링 요청의 블록 공유

가장 중요한 지점

• Q. 비연속 메모리에 흩어진 K/V로 attention 계산이 가능한가
• A. block table을 인식하는 커스텀 attention 커널 사용
  • 커널이 계산 전 block table을 참조, 물리 블록을 논리 순서대로 접근
  • "페이징"이 커널 레벨에서 투명하게 처리되어 상위 로직에는 여전히 연속으로 보임
• PagedAttention이 단순 메모리 관리 기법이 아니라 "attention 알고리즘"으로 불리는 이유임

 

---

vLLM 스케줄러의 매 스텝 동작

• CH3의 Workload manager에 대응하는 영역
• vLLM V1 엔진 step()은 3단계 구성

엔진 루프

 

설계 포인트 1 - decode 우선, prefill/decode 혼합

• V1 스케줄러는 한 스텝 내에서 prefill과 decode를 혼합 처리 (V0는 택일만 가능)
• 이미 응답을 기다리는 사용자(running 큐) 우선 - UX 관점에서 합리적 선택

 

설계 포인트 2 - allocate_slots, 블록 할당의 단일 관문

1. 필요 블록 수 계산 - ceil(new_tokens / 16)
2. 가용성 확인 - 부족 시 조기 종료
3. free_block_queue(doubly linked list) 선두에서 n개 인출 → req_to_blocks에 기록

 

KV cache 블록 리스트

설계 포인트 3 - Preemption

• 블록 부족 시 OOM으로 종료하지 않고 우선순위 낮은 요청을 evict → 블록 회수 → 이후 재계산(recompute)
• 트래픽 스파이크 상황에서 서비스 생존을 보장하는 장치
• 인프라 관점 시사점: K8s의 Pod eviction / preemption과 동일한 패턴. 자원이 유한하고 워크로드가 동적일 때 등장하는 보편적 해법

 

---

Chunked Prefill

• 문제 - 긴 프롬프트 하나가 엔진 스텝을 독점하면 나머지 요청의 TTFT가 전부 지연
• 해법 - prefill을 청크로 분할해 여러 스텝에 분산 실행
• 구현 - 스텝당 신규 토큰 수에 상한 설정. 나머지는 기존 인덱싱 로직이 처리
• 파라미터 - long_prefill_token_threshold, max_num_batched_tokens
• 트레이드오프 - TTFT p95 개선, 단 긴 프롬프트의 총 처리 시간은 증가

Chunked prefill

Prefix Caching

• 문제 - 시스템 프롬프트 등 공유 프리픽스를 매 요청마다 재계산
• 동작
  1. 프롬프트를 16토큰 청크로 분할 후 각각 해시 (이전 블록 해시 + 현재 토큰 + 메타데이터 결합 → 체인 구조)
  2. cached_block_hash_to_block에서 최장 캐시 히트 탐색
  3. 히트 블록은 재계산 없이 재사용
• 범위 - prefill만 가속, decode는 개선 없음
• 기본값 - vLLM에서 기본 활성화
• 효과가 큰 워크로드 - 멀티턴 대화, 공통 시스템 프롬프트

캐시된 KV 블록 재사용

 

Disaggregated P/D

• 발상 - prefill과 decode의 성능 프로파일이 다르므로 인스턴스 자체를 분리
• 구성 - N개 prefill 인스턴스가 KV를 KV cache 서비스에 write, M개 decode 인스턴스가 read
• 효과 - 길고 버스티한 prefill을 안정적인 decode로부터 격리 → TTFT와 ITL을 각각 독립 제어

Disaggregated Prefill/Decode

멀티 모델 서빙 - 비용 최적화 vs 지연 최적화 논의와 동일한 축이나, 분리 기준이 "모델 단위"가 아닌 "요청의 단계 단위" 라는 점이 차이가 있음

 

 

구현	vLLM 대응	vLLM 추가 수행
API server (FastAPI/SSE)	OpenAIServingChat/Completion + AsyncLLM	OpenAI 호환 스펙, asyncio 태스크 분리
Workload manager	Scheduler (FCFS / priority)	iteration-level 스케줄링, token budget, preemption
incoming_queue	waiting 큐	우선순위 힙 지원
active_sequence	running 큐	매 스텝 재구성
sequence_map	req_to_blocks + InputBatch	요청 → KV 블록 매핑까지 관리
요청별 EventQueue (SSE)	output_queue + output 스레드	ZMQ 소켓 기반 프로세스 간 전달
Model executor	UniProc / MultiProcExecutor	TP/PP 분산 실행 추상화
-	KV cache manager	핵심 차이 지점
-	CUDA Graph capture	커널 런치 오버헤드 제거

 

• 직접 만든 뼈대는 구조적으로 정확함
• 아래 두 가지가 제외됨
  1. KV cache를 자원으로 인식·관리하는 레이어
  2. 스케줄링 단위를 iteration으로 내리는 것

 

---

운영 관점 - 측정 지표와 튜닝

지표

지표	정의	관심 주체
TTFT (Time To First Token)	요청 제출 ~ 첫 토큰 수신	사용자 체감 반응성
ITL (Inter-Token Latency)	연속한 두 토큰 사이 간격	스트리밍 부드러움
TPOT (Time Per Output Token)	요청 내 ITL 평균	상동
E2E Latency	TTFT + 전체 ITL 합	전체 응답 시간
Throughput	초당 처리 토큰/요청 수	인프라 비용
Goodput	SLO 만족 요청만 집계한 throughput	실제 판단 기준

 

Goodput을 강조하는 이유

• throughput만 보면 "p99 TTFT 10초인데 tokens/sec는 최고"인 구성을 최적으로 오판
• SLO를 먼저 정의하고, 이를 만족한 트래픽만 집계하는 것이 타당
• 대규모 디바이스 플릿 운영에서 성공률·SLA를 보는 방식과 동일한 사고

TTFT / ITL / E2E latency

 

Latency와 Throughput의 상충 - Roofline 모델

• 배치 크기 B가 decode 스텝에 미치는 영향으로 설명
  • B ↓ (→1) - 스텝당 작업량 감소로 ITL 하락, 단 가중치 로딩 비용 단독 부담 → throughput 저하
  • B ↑ - 가중치 I/O가 여러 토큰에 amortize되어 throughput 상승, 대신 스텝당 FLOPs 증가로 ITL 상승
• 포화 배치 크기 B_sat 기준
  • B_sat 이하 - HBM 대역폭 지배, 스텝 시간 거의 평탄 (토큰 1개나 10개나 유사)
  • B_sat 초과 - compute-bound 전환, 스텝 시간이 B에 비례 증가

 

Roofline 성능 모델

B_sat까지는 배치를 키워도 지연시간 증가 없이 처리량만 상승. 즉 공짜 구간이 존재하며, 튜닝의 1차 목표는 이 구간을 찾는 것

 

주요 튜닝 파라미터

파라미터	역할	주의점
gpu_memory_utilization	KV cache pool 크기 결정	높일수록 concurrency 상승, 가변 배치에서 OOM 위험
max_num_batched_tokens	스텝당 토큰 예산	throughput/TTFT 트레이드오프의 주 조절 손잡이
max_model_len	컨텍스트 상한	실제 유즈케이스에 맞춰 하향할수록 유리
block_size	KV 블록당 토큰 수 (기본 16)	롱컨텍스트 시 상향 검토
long_prefill_token_threshold	chunked prefill 활성화	TTFT p95가 병목일 때
enable_prefix_caching	기본 활성화	공유 프리픽스 부재 시 해싱 오버헤드만 발생

 

벤치마킹

• CLI: vllm bench {serve,latency,throughput}
• serve - Poisson/Gamma 분포로 요청 도착 간격을 샘플링해 실 트래픽 시뮬레이션. 부하 테스트에 적합
• throughput - QPS=∞로 일괄 투입하는 모드. 성격이 다르므로 혼동 주의

 

 

한계

• 롱컨텍스트 starvation - 수만 토큰 prefill 하나가 chunked prefill 적용 후에도 클러스터를 수 초간 점유 가능
• Constrained decoding 비용 - JSON 스키마·정규식 제약 적용 시 일부 배칭 최적화가 비활성화되는 느린 경로로 진입 (structured output 주제와 직결)
• Multi-LoRA 스케줄링 공정성 - 어댑터 간 스케줄링이 fairness-aware하지 않아, 특정 LoRA의 버스티 트래픽이 타 어댑터의 지연 스파이크 유발 가능

 

---

Summary

모델 서빙의 성능은 결국 "유한한 GPU 메모리를 자원으로 보고, 매 iteration마다 스케줄링하는 문제"로 환원

• PagedAttention - 그 자원을 페이징 가능한 형태로 전환
• Continuous Batching - 그 자원 위에서 스케줄링 주기를 최소 단위로 하향

나머지(chunked prefill, prefix caching, disaggregated P/D) - 전부 이 두 축의 변주

 

프레임워크 선택 기준

• CH3의 문제의식(오픈소스 서빙 프레임워크가 너무 많아 선택이 어려움)에 대한 답
• 어떤 프레임워크를 보든 아래 두 가지만 먼저 확인
  1. KV cache를 어떻게 관리하는가
  2. 스케줄링 단위가 무엇인가
• 나머지는 대체로 구현 디테일

 

---

Ref

• vLLM Blog (2023)
• vLLM Blog - Inside vLLM
• github.com/vllm-project/vllm
• github.com/LMCache/LMCache