PagedAttention vs 전통적인 KV Cache: vLLM이 LLM 추론을 위해 GPU 메모리를 재발명한 방법

메모리 파편화(Memory Fragmentation), 페이지 기반 메모리 관리(Paged Memory Management), 그리고 왜 PagedAttention이 기존의 KV cache 구현보다 최대 24배 높은 처리량(Throughput)을 제공할 수 있는지에 대한 심층 분석입니다.

LLM 추론(Inference) 과정에서 생성되는 모든 토큰은 조용히 GPU 메모리를 소모합니다. 전통적인 KV 캐싱(KV Caching) 방식에서는 메모리의 상당 부분이 사용되지 않거나 회수되지 않은 채 낭비됩니다. vLLM의 PagedAttention은 운영체제(OS)의 수십 년 된 아이디어를 빌려와 이 문제를 해결했습니다. 이것이 정확히 어떻게 작동하며 왜 중요한지 설명하겠습니다.

목차

1. KV Cache란 무엇이며 왜 존재하는가?
2. 문제점: 전통적인 KV Cache와 메모리 파편화(Memory Fragmentation)
3. OS 가상 메모리(Virtual Memory)로부터의 영감 — vLLM의 통찰
4. PagedAttention: 작동 원리
5. 메모리 파편화: 전후 비교
6. 처리량(Throughput) 이득: 수치 및 벤치마크
7. 트레이드오프(Trade-offs) 및 한계
8. 누가 이것에 관심을 가져야 하는가?
9. 핵심 요약

섹션 1 — KV Cache란 무엇이며 왜 존재하는가?

다룰 내용:

• 자기회귀 디코딩(Autoregressive Decoding) 과정에서 각 새로운 토큰은 이전의 모든 토큰을 참조(Attend)합니다.
• 캐싱이 없는 경우: 매 단계마다 모든 과거 토큰에 대해 키(Key)/값(Value)을 재계산 → $O(n^2)$의 계산 비용 발생
• KV cache를 사용하는 경우: 레이어(Layer)당, 토큰당 키/값 텐서(Key/Value Tensors)를 GPU 메모리에 저장 → 어텐션(Attention) 비용을 분할 amortize 함
• KV cache 크기 공식: $2 \times \text{num_layers} \times \text{num_heads} \times \text{head_dim} \times \text{seq_len} \times \text{batch_size} \times \text{dtype_bytes}$

포함할 코드 스니펫:

# 대략적인 KV cache 크기 추정
num_layers = 32 # LLaMA-2 7B
num_heads = 32
...

전달할 핵심 통찰:

KV cache는 있으면 좋은 기능이 아니라, 합리적인 속도로 LLM을 서비스하기 위해 필수적인 요소입니다. 하지만 전통적인 할당 방식은 매우 비효율적입니다.

섹션 2 — 문제점: 전통적인 KV Cache와 메모리 파편화(Memory Fragmentation)

다룰 내용:

사전 할당(Pre-allocation) 문제:

• 기존 프레임워크(Traditional frameworks)는 _최대 가능한 시퀀스 길이(maximum possible sequence length)_를 기준으로 시퀀스당 연속적인 GPU 메모리 블록을 사전 할당(Pre-allocate)합니다.
• max_seq_len=2048인 요청은 단 50개의 토큰만 생성하더라도 2048개의 슬롯을 할당받습니다.
• 낭비되는 메모리 = (max_seq_len - actual_len) × per_token_kv_size

세 가지 유형의 파편화(Fragmentation):

세 가지 유형의 파편화(Three types of fragmentation)

실제적인 결과:

• GPU 사용률이 80%로 표시되더라도, 실제로 유용한 KV 데이터를 담고 있는 비중은 30~40%에 불과합니다.
• 메모리가 "존재"함에도 불구하고 더 많은 시퀀스를 수용할 수 없기 때문에 배치(Batching) 처리가 불가능해집니다.
• 부하가 걸릴 때 높은 지연 시간(Latency) 발생 → 계산(Computation)이 아닌 대기열(Queuing)이 병목 현상(Bottleneck)이 됩니다.

다이어그램 제안:

전통적인 KV 캐시(Traditional KV Cache)

섹션 3 — 운영체제(OS) 가상 메모리로부터의 영감: vLLM의 통찰

다룰 내용:

• vLLM 팀(Kwon et al., 2023)은 운영체제(OS)가 **페이징(Paging)**을 통해 RAM을 관리하는 방식과 직접적인 평행 이론을 도출했습니다.
• OS 페이징에서: 물리적 RAM은 고정된 크기의 "프레임(Frames)"으로 나뉩니다. 프로세스는 페이지 테이블(Page table)을 통해 프레임에 매핑된 "페이지(Pages)"를 할당받습니다.
• 물리 메모리는 비연속적(Non-contiguous)일 수 있지만, 가상 주소 공간(Virtual address space)은 프로세스에게 연속적인 것처럼 보입니다.
• 핵심적인 OS의 통찰: 실제로 필요할 때까지 메모리를 할당하지 마라 (요구 페이징 (Demand paging))

비유 표:

비유 표 (The analogy table)

인용할 만한 문구:

vLLM 논문은 PagedAttention을 “OS의 가상 메모리처럼 페이징(paging)을 통해 KV 캐시를 관리하는 방식”으로 설명합니다. — Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, 2023.

섹션 4 — PagedAttention: 작동 원리

다룰 내용:

블록 기반 KV 캐시 (Block-based KV cache):

• GPU 메모리는 고정된 크기의 KV 블록 (KV blocks) (예: 블록당 16개 토큰)으로 나뉩니다.
• 각 블록은 모든 레이어에 걸쳐 정확히 block_size만큼의 토큰에 대한 키/값(key/value) 텐서를 보유합니다.
• **블록 테이블 (block table)**은 페이지 테이블(page table)처럼 각 시퀀스를 물리적 블록 인덱스 목록에 매핑합니다.

할당 라이프사이클 (Allocation lifecycle):

1. 요청 도착 → 할당된 블록 없음
2. 첫 번째 block_size 토큰 생성 → 하나의 블록 할당
3. 다음 block_size 토큰 생성 → 두 번째 블록 할당 (물리적으로 비연속적일 수 있음)
4. 요청 완료 → 블록 즉시 해제 및 풀(pool)로 반환

프롬프트 공유 (Copy-on-write):

• 동일한 접두사(prefix, 예: 시스템 프롬프트)를 가진 여러 요청은 동일한 물리적 KV 블록을 공유할 수 있습니다.
• 경로가 갈라질 때(빔 서치 분기, 병렬 샘플링 등), 블록이 복사됩니다 — 이는 Copy-on-write(쓰기 시 복사) 의미론을 따릅니다.
• 공유 시스템 프롬프트를 사용하는 트래픽이 높은 배포 환경에서 막대한 메모리 절감 효과를 제공합니다.

코드 스니펫 (단순화된 블록 테이블 개념):

from dataclasses import dataclass, field
from typing import List, Optional

...

섹션 5 — 메모리 파편화: 전후 비교

다룰 내용:

전통적인 시스템의 낭비 분석 (전형적인 사례):

• 내부 파편화 (Internal fragmentation): ~20–30% (시퀀스 내 사용되지 않는 예약된 슬롯)
• 외부 파편화 (External fragmentation): ~10–15% (시퀀스 할당 사이의 간격)
• 유효 활용도 (Effective utilization): 최선의 경우에도 종종 60–70% 수준

PagedAttention의 낭비 프로필:

• 내부 파편화 (Internal fragmentation): 각 시퀀스의 마지막 블록 내에서만 발생 → 시퀀스당 최대 block_size - 1개의 토큰 낭비
• 외부 파편화 (External fragmentation): 거의 0에 가까움 — 모든 블록은 동일한 크기이며, 풀(pool)은 균질(homogeneous)합니다.
• 유효 활용도 (Effective utilization): 통상적으로 90–96%

파편화 비교 다이어그램 (Fragmentation comparison diagram):

파편화 비교 다이어그램 (Fragmentation comparision diagram)

섹션 6 — 처리량 이득: 수치 및 벤치마크 (Throughput Gains: Numbers and Benchmarks)

다룰 내용:

vLLM 논문 (Kwon et al., 2023) 기준:

• vLLM은 동일한 하드웨어에서 HuggingFace Transformers 대비 **2~4배 더 높은 처리량 (throughput)**을 달성합니다.
• PagedAttention이 없는 연속 배치(continuous batching) 베이스라인인 Orca 대비: 최대 1.7배 더 높은 처리량을 기록합니다.
• 긴 시퀀스(sequence)와 높은 요청률(request rates) 환경에서는 단순 구현(naive implementations) 대비 이득이 최대 24배에 달할 수 있습니다.

처리량이 향상되는 이유:

1. 더 높은 GPU 메모리 활용도 (Higher GPU memory utilization) → 배치 내에 동시에 더 많은 시퀀스를 포함할 수 있음
2. 대기 시간 감소 (Less queuing) → GPU가 메모리를 기다리며 멈춰 있는 대신 계속 바쁘게 작동함
3. 프롬프트 공유 (Prompt sharing) → 시스템 프롬프트 KV(Key-Value)가 한 번만 계산되어 N개의 요청에 걸쳐 공유됨
4. 더 빠른 선점 (Faster preemption) → 메모리 부족(OOM, Out-of-Memory) 발생 시, 전체 시퀀스가 아닌 개별 블록(block)을 스왑(swap)함

처리량 표 (vLLM 논문 수치 기반 대표 예시):

처리량 표 (Throughput table)

참고: 실제 수치는 모델 크기, GPU 유형, 시퀀스 길이 분포 및 요청 도착 패턴에 따라 달라집니다. 항상 자신의 워크로드(workload)에서 벤치마크를 수행하십시오.

코드 스니펫 — vLLM으로 처리량 측정하기:

from vllm import LLM, SamplingParams
import time

...

섹션 7 — 트레이드오프 및 한계 (Trade-offs and Limitations)

다룰 내용 (균형 잡힌 시각, Medium 독자들은 정직함을 선호합니다):

얻는 것 (What you gain):

• 극적으로 높아진 메모리 활용도
• 훨씬 더 나은 배치 동시성 (batch concurrency) → 대규모 환경에서 더 낮은 지연 시간 (latency)
• 최신 vLLM 버전에서 기본적으로 제공되는 접두사 캐싱 (Prefix caching)

**포기하거나 감수하는 것 (What you trade or accept):

• 블록 테이블 오버헤드 (Block table overhead): 소량의 CPU 측 메모리 사용 + 어텐션 (Attention) 단계당 조회 비용 발생
• 블록 크기 튜닝 (Block size tuning): 너무 작으면 → 과도한 블록 테이블 관리 비용 발생; 너무 크면 → 내부 단편화 (Internal fragmentation)가 다시 나타남
• 어텐션 커널 복잡도 (Attention kernel complexity): 표준 Flash Attention은 페이지화된 KV (Paged KV)를 기본적으로 지원하지 않음; vLLM은 커스텀 CUDA 커널을 제공함
• 연산량에 대한 마법 같은 해결책은 아님 (Not a magic fix for compute): PagedAttention은 메모리 병목 현상을 해결함 — 만약 연산 제한 (Compute-bound) 상황이라면 (긴 컨텍스트, 거대 모델), 이득은 더 작음
• 프리필 (Prefill) 단계에는 영향 없음: PagedAttention은 주로 디코드 (Decode) 단계에 도움을 줌; 프리필은 여전히 전체 프롬프트를 순차적으로 처리함

블록 크기 민감도 (Block size sensitivity):

# 블록 크기 대비 대략적인 내부 단편화 (Internal fragmentation)
def max_waste_fraction(block_size, avg_seq_len):
    # 최악의 경우: 마지막 블록이 거의 비어 있음
...

vLLM은 실용적인 최적 지점(Sweet spot)으로 block_size=16을 기본값으로 사용합니다.

섹션 8 — 누가 이것에 관심을 가져야 하는가?

대상 독자 안내:

프로덕션 환경에서 LLM을 서빙하고 있다면:

• 이것은 동시 부하 상황에서의 처리량 (Throughput)을 위한 가장 영향력 있는 단일 인프라 변화입니다.
• vLLM 또는 그에 상응하는 기술(SGLang, 페이지 캐시를 지원하는 TensorRT-LLM)로 전환하십시오.

HuggingFace Transformers를 기반으로 구축하고 있다면:

• 연구/단일 사용자 용도로는 훌륭하지만, 고동시성 (High-concurrency) 서빙을 위해 설계되지는 않았습니다.
• model.generate()의 KV 캐시는 연속적인 사전 할당 (Contiguous pre-allocation)을 사용합니다 — 단일 요청에는 괜찮지만, 규모가 커지면 단편화가 심해집니다.

파인튜닝 (Fine-tuning) 또는 평가 (Evaluation)를 수행하고 있다면:

• PagedAttention은 서빙 (Serving) 최적화입니다; 학습 중에는 일반적으로 스텝 간에 동일한 방식으로 KV를 캐싱하지 않습니다.
• 하지만 파인튜닝한 모델을 배포할 때를 대비해 이해해 두는 것이 유용합니다.

vLLM/SGLang 소스 코드를 읽고 있다면:

• BlockSpaceManager, BlockAllocator, 그리고 Scheduler가 공부해야 할 핵심 클래스입니다.
• 블록 테이블은 모델의 포워드 패스 (Forward pass) 내부가 아니라, 스케줄러 (Scheduler) 내에서 시퀀스별로 유지됩니다.

섹션 9 — 핵심 요약

• 전통적인 KV 캐시 (Traditional KV cache)는 최대 길이 (max length)를 기준으로 시퀀스당 연속적인 메모리 (contiguous memory)를 사전 할당합니다 $\rightarrow$ 일반적으로 30–40%의 낭비가 발생합니다.
• 메모리 파편화 (Memory fragmentation) — 내부 (internal), 외부 (external), 그리고 예약 (reservation) 파편화 — 는 단순한 (naive) LLM 서빙에서 낮은 GPU 활용도 (utilization)와 저조한 배치 (batching) 성능의 근본 원인입니다.
• PagedAttention은 운영체제 (OS)의 가상 메모리 페이징 (virtual memory paging) 방식을 차용합니다: 고정된 크기의 블록 (fixed-size blocks), 온디맨드 할당 (on-demand allocation), 연속적인 버퍼 대신 블록 테이블 (block tables)을 사용합니다.
• 결과: 90–96%의 메모리 활용도 (memory utilization) 를 달성하여, 배치당 더 많은 시퀀스를 처리할 수 있게 하며 처리량 (throughput)을 극적으로 높입니다.
• vLLM은 워크로드와 비교 대상 (baseline)에 따라 2–24배의 처리량 (throughput) 향상을 입증했습니다.
• 주요 트레이드오프 (Key trade-offs): 커스텀 CUDA 커널 (custom CUDA kernels)이 필요하며, 블록 크기 (block size) 튜닝이 중요합니다. 연산 제한적 (compute-bound) 워크로드에서는 이점이 상대적으로 적습니다.
• **프롬프트 공유 (Prompt sharing, copy-on-write)**는 과소평가된 보너스입니다: 공유된 접두사 (shared prefixes)는 한 번만 계산되고 여러 번 참조됩니다.