Continuous Batching과 PagedAttention

Continuous Batching과 PagedAttention

LLM 서버에 요청이 쌓이는데도 GPU를 충분히 활용하지 못하는 경우가 있습니다. 기존의 고정된 batch에서는 길이가 다른 요청을 함께 실행하면 먼저 끝난 요청의 자리가 비어도 그 자리에 새 요청을 바로 넣기 어렵고, 생성 길이가 긴 요청이 남을수록 batch가 점점 작아질 수 있습니다.

Continuous Batching은 이 문제를 스케줄링에서 해결합니다. 요청 전체가 끝날 때까지 batch를 고정하지 않고 generation iteration마다 완료된 요청을 빼고 새로운 요청을 넣어, 실행 중인 batch를 계속 채웁니다.

하지만 동시에 처리할 요청을 늘리려면 또 다른 문제가 생깁니다. 각 요청의 KV cache는 생성 길이에 따라 계속 커지는데, 이를 요청마다 큰 연속 메모리 공간으로 관리하면 fragmentation과 과도한 예약 때문에 GPU 메모리가 낭비될 수 있습니다. PagedAttention은 KV cache를 고정 크기 block으로 나누고 필요할 때 할당해 이 문제를 줄입니다.

둘은 자주 함께 소개되지만 하나는 batch의 시간을 관리하고, 다른 하나는 KV cache의 공간을 관리합니다. Continuous Batching이 빈 실행 자리를 빠르게 다시 채운다면, PagedAttention은 메모리를 효율적으로 써 더 많은 요청을 동시에 실행할 여지를 만듭니다.

각 기법이 어떤 낭비를 제거하는지 따로 살펴보고, 마지막에는 논문과 serving framework에서 인용되는 throughput 향상 수치를 어떻게 읽어야 하는지 봅니다. 같은 2×, 10×라는 숫자라도 비교 대상, 요청 길이, 동시 요청 수, latency 제약과 하드웨어가 다르면 의미가 크게 달라집니다.

---

1장. 기존 방식이 비효율적인 이유

고정된 request-level batching의 낭비. 생성 길이가 서로 다른 요청을 batch membership을 바꾸지 않은 채 끝까지 묶으면 먼저 끝난 sequence의 자리를 즉시 재사용하지 못할 수 있습니다. 초기 LLM serving 시스템이 겪던 대표적인 문제입니다.

요청 A  ████████████████████  (200 토큰)
요청 B  ████                  (40 토큰)  → 이후 자리 낭비
요청 C  ██████                (60 토큰)  → 이후 자리 낭비
요청 D  ███                   (30 토큰)  → 이후 자리 낭비
        └────────────────────┘
         A 가 끝날 때까지 대기

고정 batch라면 긴 요청이 남아 있는 동안 먼저 끝난 sequence가 차지하던 slot을 새 요청으로 채우지 못해 GPU utilization이 떨어질 수 있습니다.

초기 serving 구현은 요청별 KV cache를 연속된 큰 영역으로 예약하거나 growth를 다루는 과정에서 reservation과 내부/외부 fragmentation이 생길 수 있었습니다. 모든 시스템이 반드시 “최대 길이 전체를 미리 할당”하는 것은 아니지만, vLLM 논문이 겨냥한 핵심 병목은 이런 동적 KV cache의 비효율적 메모리 관리였습니다.

vLLM 논문의 진단. 아래 인용은 원문 의미를 살린 번역입니다.

각 요청의 KV 캐시 메모리가 거대하고 동적으로 늘고 줄어든다. 비효율적으로 관리하면 단편화와 중복 복제로 크게 낭비되어 배치 크기가 제한된다.

배치 크기가 제한된다는 것이 핵심입니다. 메모리 낭비가 곧 처리량 손실입니다.

두 축이 나눠 풉니다. Continuous/iteration-level batching은 generation iteration마다 active sequence 집합을 갱신해 끝난 요청의 자리에 대기 요청을 투입합니다. PagedAttention은 KV cache를 고정 크기 block으로 나눠 non-contiguous physical memory에 배치하고 block table로 논리 순서를 연결합니다.

비유로 보면 static batching은 버스입니다. 정원이 다 찰 때까지 기다리고 모두 내릴 때까지 기다립니다. Continuous Batching은 합승 택시라서 자리가 비는 즉시 새 손님을 태우고, PagedAttention은 좌석을 작은 칸으로 쪼개 필요한 만큼만 배정하는 좌석 관리입니다.

---

2장. 어떻게 동작하나

① 스케줄러가 매 디코드 스텝마다 배치를 갱신
   끝난 요청 제거, 대기 요청 투입

② 각 요청의 KV 캐시는 페이지 블록으로 필요할 때 할당
   연속된 메모리 공간이 필요 없음

③ 가능한 범위에서 active batch를 계속 채워 GPU 유휴 시간을 줄이고 처리량을 높임

핵심은 request completion 단위가 아니라 generation iteration 단위로 scheduling decision을 갱신할 수 있다는 것입니다. 실제 최신 엔진은 prefill chunking, priority, preemption 같은 정책까지 함께 사용하므로 “항상 모든 토큰 뒤에 배치를 완전히 다시 만든다”는 구현 세부로 고정해 이해할 필요는 없습니다.

---

3장. 두 축을 나눠 보면

iteration-level 스케줄링. Orca가 2022년에 제안했습니다. 기존에는 요청 단위로 배치를 고정해 길이 차이만큼 낭비가 났는데, Orca가 토큰 단위로 스케줄을 옮겨 그 낭비를 제거했습니다.

PagedAttention의 메모리 관리. KV 캐시를 고정 크기 페이지로 나누고 논리 주소와 물리 주소를 매핑하는 블록 테이블로 관리합니다. 아래도 논문 표현을 의미를 살려 옮긴 것입니다.

운영체제의 고전적 가상 메모리와 페이징 기법에서 영감을 받은 어텐션 알고리즘

발상이 그대로 OS입니다. 프로세스가 연속된 물리 메모리를 안 써도 되듯 요청도 연속된 KV 공간을 안 써도 됩니다.

논문이 밝힌 두 이득.

vLLM은 (1) KV 캐시 메모리의 거의 제로에 가까운 낭비와 (2) 요청 내부와 요청 간 KV 캐시의 유연한 공유를 달성한다.

Block 단위 관리 덕분에 여러 sequence가 KV block을 공유하는 구현도 가능해집니다. vLLM의 prefix caching은 현재 block hash 기반 cache lookup과 재사용으로 구현되며, PagedAttention의 block abstraction과 잘 맞지만 “PagedAttention을 쓰면 prefix caching이 자동으로 켜진다”는 뜻은 아닙니다.

---

4장. 수치를 어떻게 읽나

기준선에 따라 완전히 다릅니다. 이 글에서 가장 조심해야 할 부분입니다.

SOSP 2023 논문은 FasterTransformer와 Orca 대비 2~4배를 동일한 지연 수준에서 보고합니다.

vLLM 블로그는 다릅니다. LLaMA-7B on A10G와 LLaMA-13B on A100 40GB에서 ShareGPT 데이터셋으로 입출력 길이를 샘플링한 설정입니다.

시나리오	HF 대비	TGI 대비
요청당 출력 1개	14 ~ 24배	2.2 ~ 2.5배
요청당 병렬 출력 3개	8.5 ~ 15배	3.3 ~ 3.5배

왜 이렇게 벌어지나. 2023년 블로그의 Hugging Face baseline은 범용 transformers generation 경로였고, 전문 serving engine과 scheduling/memory management 수준이 달랐습니다. Orca는 이미 iteration-level scheduling을 갖춘 더 강한 baseline이므로 vLLM 논문에서 격차가 작아집니다. 이 수치를 오늘의 transformers, TGI, SGLang, TensorRT-LLM 성능 차이로 재사용하면 안 됩니다.

인용할 때 지킬 것. 24배만 떼어 쓰면 오해를 만듭니다. 무엇 대비인지, 어느 시나리오인지 반드시 함께 씁니다.

그리고 24배와 3.5배를 한 쌍처럼 쓰면 안 됩니다. 24배는 출력 1개 시나리오이고 3.5배는 출력 3개 시나리오라, 서로 다른 실험의 최댓값을 붙여 놓은 것이 됩니다.

시점도 다릅니다. 이 수치는 2023년의 당시 구현을 비교한 결과입니다. 이후 여러 serving engine이 dynamic/continuous batching, block 기반 KV 관리, prefix caching 등 비슷한 목표의 최적화를 각자 발전시켰기 때문에 당시의 배수를 현재 제품 간 성능 차이로 옮기면 안 됩니다. 현재 성능은 자기 workload와 같은 version에서 직접 비교해야 합니다.

---

5장. 처리량과 지연의 트레이드오프

동시 처리량을 늘리면 GPU utilization이 좋아져 throughput이 오를 수 있지만, queueing과 resource sharing이 커지면 개별 요청의 TTFT·TPOT·tail latency가 나빠질 수도 있습니다. 반대로 더 효율적인 batching이 같은 부하에서 queue를 줄여 latency까지 좋아지는 구간도 있으므로 항상 한쪽이 오르면 다른 쪽이 내려가는 고정 관계는 아닙니다.

무엇을 최적화할지 먼저 정해야 합니다. 더 많은 동시 sequence는 throughput을 높일 수 있지만 queueing과 resource sharing 때문에 TTFT/TPOT/tail latency가 나빠질 수 있습니다. Speculative decoding, efficient attention kernel, prefill/decode 분리 같은 기법도 서로 다른 latency 구간을 건드리므로 단일 “지연 최적화 목록”으로 묶기보다 실제 TTFT·TPOT를 따로 측정해야 합니다.

논문이 붙인 조건도 있습니다. 아래는 의미를 살린 번역입니다.

개선은 더 긴 시퀀스, 더 큰 모델, 더 복잡한 디코딩 알고리즘에서 더 두드러진다.

짧은 요청 위주면 이득이 작고 긴 컨텍스트와 큰 모델일수록 이득이 크다는 뜻입니다.

---

6장. 발전 흐름

시기	발전
2022	Orca. iteration-level 배칭 제안 (OSDI 2022)
2023-06	vLLM 공개. PagedAttention과 Continuous Batching 결합
2023	PagedAttention 논문 SOSP 2023
2024 이후	여러 LLM serving engine이 dynamic batching, KV cache 관리, prefix reuse, 분산 스케줄을 각자 발전

Iteration-level/continuous batching과 block 기반 KV management의 아이디어는 여러 현대 serving engine에 널리 퍼졌습니다. 다만 엔진마다 scheduler, KV allocator, prefix cache의 구현과 기본 활성화 여부가 다르므로 설정을 확인해야 합니다.

---

7장. 실무

튜닝 지점. Scheduler의 동시 sequence/token budget은 throughput과 latency를 직접 맞바꿉니다. KV block size도 내부 단편화와 metadata/kernel 효율 사이의 trade-off가 있지만, “짧은 요청이면 작은 block, 긴 요청이면 큰 block” 하나로 최적값을 결정할 수는 없습니다. 엔진이 지원하는 값과 workload를 실제 측정해야 합니다.

하이브리드 모델의 차이. Full attention은 토큰 수에 따라 커지는 KV cache를, sliding-window attention은 제한된 최근 KV를, Mamba/일부 recurrent linear attention은 별도의 recurrent state를 가질 수 있습니다. 최신 vLLM은 이런 조합을 위해 Hybrid KV Cache Manager를 두고 layer type별 cache requirement를 관리합니다.

따라서 hybrid 모델에서는 모든 layer가 동일한 PagedAttention KV block을 쓰는 것이 아니라 attention/state 종류별로 cache semantics가 달라집니다.

지표를 나눠 봅니다.

지표	뜻
처리량	초당 총 토큰 수
TTFT	첫 토큰까지 걸린 시간
TPOT	토큰당 생성 시간
p99 지연	꼬리 지연

Continuous batching은 유휴 slot을 줄여 throughput을 높이는 데 유리하지만, 높은 부하에서는 queueing·scheduling 때문에 p99 latency가 나빠질 수도 있습니다. 반대로 같은 throughput 목표에서 더 효율적으로 처리해 latency가 좋아지는 구간도 있어, 방향을 고정해서 말하기보다 load curve로 측정해야 합니다.

---

8장. 온디바이스에서의 차이

동시 요청이 적으면 이득이 작아집니다. Continuous batching의 주된 이점은 여러 active request 사이의 빈 slot을 재사용하는 것이므로 단일 사용자·단일 요청 중심 환경에서는 서버만큼 큰 효과가 나기 어렵습니다. 다만 로컬 앱도 background task나 여러 세션을 동시에 처리하면 의미가 생길 수 있습니다.

KV 메모리 문제는 남습니다. 긴 단일 요청도 KV cache가 커지므로 block 기반 할당 아이디어가 도움 될 수 있습니다. 그러나 단일 sequence만 있을 때는 request 간 fragmentation과 sharing 이득이 줄어들어, 단순 contiguous/ring/sliding cache가 더 적합한 엔진도 있습니다.

온디바이스에서는 동시성뿐 아니라 메모리 용량·대역폭, quantization, prompt/decode 길이, CPU/GPU/NPU 배치 방식 같은 제약이 크게 작용합니다. Speculative decoding도 가능한 선택지 중 하나입니다. 서버에서 효과가 큰 scheduling 기법을 로컬 환경에 그대로 적용하기보다 실제 동시 요청 수와 hardware bottleneck을 먼저 봐야 합니다.

---

9장. 정리

Continuous Batching은 스케줄이고 PagedAttention은 메모리입니다. 다른 문제를 풀고 함께 써야 큰 효과가 납니다.

수치는 기준선에 따라 2배에서 24배까지 갈립니다. 무엇 대비인지 없이 인용하면 안 됩니다.

처리량과 지연 사이에는 흔히 trade-off가 생기지만 방향과 크기는 부하와 scheduler에 달려 있습니다. 그래서 throughput만이 아니라 TTFT·TPOT·tail latency를 함께 측정해야 합니다.

Continuous batching의 직접 목표는 active slots를 효율적으로 채우는 scheduling이고, 결과적인 latency 변화는 부하와 정책에 달려 있습니다. PagedAttention은 attention의 수학적 score 식을 새로 만드는 기법이라기보다 KV cache의 block addressing과 이를 읽는 attention kernel을 결합한 메모리 관리 방식입니다. 온디바이스에서도 동시 요청이 적으면 continuous batching의 이득이 작지만 항상 0이라고 단정할 수는 없습니다.

---

용어 정리

용어	한 줄 뜻
static batching	요청을 묶어 한꺼번에 처리하고 모두 끝날 때까지 기다리는 방식
Continuous Batching	generation iteration 사이에서 active request 집합을 동적으로 갱신해 빈 slot을 재사용하는 방식
iteration-level 스케줄링	요청 전체가 끝날 때까지 batch를 고정하지 않고 generation iteration 단위로 scheduling하는 것
PagedAttention	KV cache를 고정 크기 block으로 비연속 배치하고 block table을 통해 attention이 접근하게 하는 메모리 관리/attention 구현
블록 테이블	논리 KV 주소를 물리 블록에 매핑하는 표
단편화	메모리가 조각나 실제로 못 쓰는 공간이 생기는 현상
KV 캐시 공유	같은 앞부분을 쓰는 요청들이 페이지를 함께 참조하는 것
prefix caching	공통 프롬프트 앞부분을 재사용하는 최적화
처리량	단위 시간당 처리한 총 토큰 수
TTFT	첫 토큰이 나오기까지 걸린 시간
TPOT	토큰 하나를 생성하는 데 걸리는 시간

참고자료

• Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022)

• Efficient Memory Management for LLM Serving with PagedAttention (vLLM, SOSP 2023, arXiv 2309.06180). Figure 3 이 예약, 내부 단편화, 외부 단편화 세 가지 메모리 낭비를 보여주고 Figure 5 가 PagedAttention 알고리즘, Figure 6 이 블록 테이블 변환이다. Figure 8 에서 10 이 프롬프트 공유와 copy-on-write 예시다. ar5iv

• vLLM 블로그, "vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention" (2023-06-20)

• vLLM 공식 문서

• vllm-project/vllm GitHub

• vLLM Hybrid KV Cache Manager

• vLLM Automatic Prefix Caching