PagedAttention - vLLM을 이용한 대규모 언어 모델 서빙의 효율적 메모리 관리
Digest: LLM(대규모 언어 모델) 서빙의 진짜 병목은 연산이 아니라 KV 캐시(key/value cache, 과거 토큰의 attention state를 저장한 버퍼) 메모리다. 기존 시스템(FasterTransformer, Orca 등)은 한 시퀀스의 KV 캐시를 연속된(contiguous) 메모리 블록으로 미리 잡아 두기 때문에, 실제 생성 길이가 예약량보다 짧으면 내부 단편화, 서로 다른 시퀀스 사이에는 외부 단편화, 그리고 아직 쓰지 않은 슬롯에 대한 예약(reservation) 낭비가 누적된다. 저자들의 핵심 통찰은 “KV 캐시의 할당 패턴이 OS의 가상 메모리 페이징과 구조적으로 동일하다”는 관찰이다. 이로부터 PagedAttention(KV 캐시를 고정 크기 블록 단위로 쪼개 비연속 저장을 허용하는 attention 커널)과 vLLM(블록 테이블·Copy-on-Write·연속 배칭을 결합한 서빙 엔진)이 자연스럽게 따라온다. 결과적으로 동일한 지연 제약에서 처리량이 FasterTransformer·Orca 대비 2~4배(Figure 1, Table/Section 7) 향상되며, 긴 시퀀스·큰 모델·빔 서치와 병렬 샘플링처럼 KV 공유가 가능한 워크로드에서 이득이 더 커진다. 한계로는 비연속 접근에 따른 커널 구현 복잡도, 블록 크기의 민감성(너무 작으면 GPU 커널 효율↓, 너무 크면 단편화↑), 그리고 페이지 교체·스와핑 전략이 단순 FIFO/재계산에 머문다는 점이 있다. 열린 질문으로는 (1) 멀티 테넌트 환경에서 페이지 공유의 보안 경계, (2) 장기 세션을 위한 디스크/호스트 메모리 계층 페이징, (3) MoE·state-space 모델로의 일반화 등이 남아 있다.
섹션별 요약
Introduction
- LLM 서빙은 경제적으로 매우 비싸며 GPU 메모리가 실질적 병목.
- 기존 엔진은 요청별 KV 캐시를 최대 길이 기준 연속 메모리로 예약 → 60~80%가 낭비(Figure 2).
- 저자 기여: (1) KV 캐시 관리의 문제를 메모리 단편화 관점에서 재정의, (2) PagedAttention 알고리즘 제안, (3) vLLM 서빙 시스템 구현 및 기존 SOTA 대비 2~4배 처리량 달성.
Background
- 자기회귀 생성: 디코딩 단계마다 과거 토큰의 K/V를 누적 저장해야 하며, 시퀀스 길이에 선형 비례.
- 기존 서빙 기법:
- FasterTransformer(NVIDIA): 정적 배칭, 사전 할당.
- Orca(OSDI’22): iteration-level(연속) 배칭은 도입했으나 KV 캐시는 여전히 연속 버퍼.
- OS 가상 메모리 비유: 프로세스 가상 주소공간 ↔ 논리 KV 블록, 물리 프레임 ↔ GPU 물리 블록, 페이지 테이블 ↔ 블록 테이블.
Method (PagedAttention + vLLM)
- PagedAttention: KV 캐시를 고정 크기
B토큰 단위 블록으로 분할. attention 연산 시 블록 테이블을 따라 비연속 블록들을 gather하여 softmax(QKᵀ)V 계산. - 블록 테이블(Block Table): 시퀀스의 논리 블록 번호 → 물리 블록 번호 매핑. 새 토큰이 추가될 때만 필요 시 물리 블록 할당.
- Copy-on-Write(CoW): 병렬 샘플링/빔 서치에서 공통 프롬프트의 물리 블록을 공유하다가, 분기점에서 쓰기가 발생하면 해당 블록만 복사.
- 스케줄링: FCFS + preemption. 메모리 부족 시 (a) 저우선 요청의 KV를 재계산 또는 (b) 호스트 RAM으로 스와핑 후 재개.
- 분산 실행: 텐서 병렬(Megatron-style)에서 각 GPU가 자신의 헤드 서브셋에 해당하는 블록만 보유, 블록 ID는 전역 동기화.
Experiments
- 모델: OPT-13B/66B/175B, LLaMA-7B/13B on NVIDIA A100.
- 데이터셋: ShareGPT, Alpaca 트레이스(다양한 입출력 길이 분포).
- 비교: FasterTransformer, Orca(oracle/pow2/max 변형).
- 핵심 결과: 동일 지연 예산에서 vLLM이 Orca(oracle) 대비 1.7
2.7배, Orca(max) 대비 2.24.3배 처리량(Figure 12~14, Section 7). - 병렬 샘플링/빔 서치: CoW 덕에 KV 메모리 사용량 최대
55% 감소, 처리량 추가 향상(Figure 1516). - 블록 크기 민감도: B=16 부근이 단편화와 커널 효율의 sweet spot(Figure 18).
| Model/Method | Workload | Metric | Score | vs. Baseline |
|---|---|---|---|---|
| vLLM (OPT-13B) | ShareGPT | Throughput(req/s) | 2.7× | vs. Orca(oracle) |
| vLLM (OPT-13B) | ShareGPT | Throughput(req/s) | 4.3× | vs. Orca(max) |
| vLLM (OPT-66B) | Alpaca | Throughput | 2.0~3.5× | vs. FasterTransformer |
| vLLM + CoW | Parallel sampling (n=4) | KV mem 절감 | ~55% | vs. no-sharing |
Discussion / Limitations
- 블록 단위 접근으로 커널 구현·튜닝 비용 증가.
- 스와핑/재계산의 정책이 단순(FCFS)하며, SLA-aware 스케줄링은 미포함.
- 블록 크기가 워크로드 분포에 민감.
- 보안/격리: 공유 블록이 서로 다른 사용자 간 존재할 경우 side-channel 우려는 논의되지 않음.
Insights
- 주목할 점: 딥러닝 시스템 문제를 OS 고전 기법으로 환원한 드문 사례.
- 연결 고리: FlashAttention이 “on-chip SRAM 레벨 데이터이동”을 최적화했다면, PagedAttention은 “HBM 레벨 할당 단위”를 최적화 — 두 기법은 직교적이고 결합 가능.
- 시사점: Serving의 SOTA 기준이 “커널 속도”에서 “메모리 레이아웃 설계”로 이동.
- 비판적 코멘트: 블록 공유가 빔 서치에서 가장 빛나지만, 오늘날의 샘플링 파이프라인(temperature/top-p 단일 샘플)에서는 이득이 제한적.
Discussion Points
- 논쟁점: 블록 크기를 모델/워크로드별로 자동 튜닝해야 하는가, 하드코딩이 실전에 충분한가.
- 검증 필요 가정: 호스트 RAM 스와핑이 PCIe 대역 경쟁 환경에서도 여전히 재계산보다 싼가.
- 후속 연구: prefix caching, RadixAttention(SGLang), chunked prefill(DistServe) 등으로 확장.
메타데이터
| 항목 | 내용 |
|---|---|
| 제목 | Efficient Memory Management for Large Language Model Serving with PagedAttention |
| 저자 | Kwon, Li, Zhuang, Sheng, Zheng, Yu, Gonzalez, Zhang, Stoica |
| 소속 | UC Berkeley, Stanford, UCSD |
| 연도 | 2023 |
| 발표 | SOSP 2023 / arXiv:2309.06180 |
| 링크 | arXiv, vLLM GitHub |
| 키워드 | KV cache, paging, attention, throughput, serving |
왜 이 연구를 하는가?
핵심 질문
“LLM 서빙 처리량을 실제로 제한하는 것은 연산인가, 메모리 레이아웃인가?”
기존 접근법의 한계
| 한계 | 설명 |
|---|---|
| 내부 단편화(internal) | 요청의 실제 생성 길이 < 예약 최대 길이 → 예약 블록 내부가 빈다. |
| 외부 단편화(external) | 서로 다른 시퀀스 간 연속 영역이 깨져 사용 가능한 메모리가 조각난다. |
| 예약 낭비(reservation) | 아직 생성하지 않은 미래 토큰 슬롯을 미리 잡아둬, 그 시간 동안 유휴. |
| KV 공유 불가 | 동일 프롬프트의 빔/병렬 샘플이 각자 별도 복사본을 유지. |
핵심 통찰
- KV 캐시는 “프로세스가 성장시키는 가상 주소공간”과 구조가 같다 → 페이지(블록) 단위 간접주소로 해결.
- 연속 메모리 가정을 버리면 단편화 3종이 동시에 사라진다.
방법 (Method)
프레임워크 개요
flowchart LR subgraph Seq1["시퀀스 1 (논리 블록)"] L1a[Block 0\ntokens 0-15] L1b[Block 1\ntokens 16-31] L1c[Block 2\ntokens 32-...] end subgraph Seq2["시퀀스 2 (논리 블록)"] L2a[Block 0\ntokens 0-15] L2b[Block 1\ntokens 16-...] end subgraph BT["Block Table (per-seq)"] BT1[Seq1: 0→P3, 1→P7, 2→P1] BT2[Seq2: 0→P3*, 1→P5] end subgraph Phys["GPU 물리 KV 블록 풀"] P1[(Phys 1)] P3[(Phys 3\nshared)] P5[(Phys 5)] P7[(Phys 7)] P9[(Phys 9\nfree)] end Seq1 --> BT1 Seq2 --> BT2 BT1 --> Phys BT2 --> Phys P3 -. Copy-on-Write\n(분기 시 복제) .-> P9
핵심: 논리 블록은 시퀀스 관점 연속, 물리 블록은 GPU 풀에서 임의 위치. 프리픽스가 같은 두 시퀀스는 동일 물리 블록(P3)을 공유하다가, 한쪽이 쓰기를 하면 해당 블록만 CoW로 P9에 복제된다.
핵심 구성요소
- PagedAttention 커널: 블록 테이블을 입력으로 받아 gather-style attention 수행.
- Block Manager: 물리 블록 free list, 참조 카운트, CoW 트리거.
- Scheduler: 연속 배칭(continuous batching) + 메모리 부족 시 preempt→swap/recompute.
- 분산 실행 모듈: 텐서 병렬 worker 간 블록 ID 동기화.
발견 (Findings)
주요 결과
| 비교 기준 | vLLM 이점 |
|---|---|
| vs. Orca(oracle) | 1.7~2.7× 처리량 (Figure 12) |
| vs. Orca(max) | 2.2~4.3× 처리량 (Figure 12) |
| vs. FasterTransformer | OPT-66B에서 2~3.5× |
| 병렬 샘플링(CoW) | KV 메모리 최대 55% 절감 |
| 블록 크기 | B=16 근처 최적 (Figure 18) |
핵심 발견
- 메모리 낭비율이 기존 시스템 60~80% → vLLM 4% 수준(Section 6).
- 동일 GPU로 동시 실행 가능한 시퀀스 수가 증가 → GEMM batch size 증가 → 산술 강도(arithmetic intensity) 개선.
KV 캐시 낭비 유형 해결 방식
| 낭비 유형 | 기존 시스템 원인 | vLLM 해결 방식 |
|---|---|---|
| Internal fragmentation | 예약된 최대 길이 내부의 미사용 슬롯 | 블록 단위 온디맨드 할당 (마지막 블록만 부분 낭비) |
| External fragmentation | 시퀀스별 서로 다른 크기의 연속 버퍼 | 고정 크기 블록 풀 → 외부 단편화 0 |
| Reservation waste | 미래 토큰용 사전 예약 | 실제 생성 시점에 블록 할당 (Lazy) |
| 중복 저장 (빔/병렬 샘플) | 시퀀스별 독립 KV 사본 | Copy-on-Write로 공유 물리 블록 |
이론적 의의
OS-DL 추상화 교환
딥러닝 서빙 스택에 OS 30년의 페이징 유산을 직접 이식했다. 이는 “DL 시스템이 자신의 메모리 관리를 처음부터 재발명할 필요가 없다”는 방법론적 선언에 가깝다.
메모리-중심 서빙 패러다임
처리량의 상한이 FLOPs가 아닌 **“GPU에 동시에 올려둘 수 있는 시퀀스 수”**임을 실증. 이후 prefix cache, RadixAttention, chunked prefill 등 KV 레이아웃 연구 계열의 출발점이 되었다.
공유 가능한 계산의 일반화
CoW는 단순 최적화가 아니라 “prompt → 연산 그래프”의 공통 접두를 공유 자원으로 보는 관점. 트리 탐색(ToT), 스펙큘레이티브 디코딩 등 분기형 디코딩의 기반이 된다.
재현성 및 신뢰도 평가
| 항목 | 등급 | 비고 |
|---|---|---|
| 코드 공개 | ✅ | vLLM 오픈소스, 산업계 표준으로 채택 |
| 데이터 공개 | ✅ | ShareGPT/Alpaca 트레이스 공개 |
| 하이퍼파라미터 | ✅ | 블록 크기·스케줄러 파라미터 명시 |
| 실험 환경 | ✅ | A100 80GB, NVLink, CUDA 버전 기술 |
| 통계적 신뢰도 | ⚠️ | 다회 평균 보고하나 분산·신뢰구간 제한적 |
| 종합 등급 | A | 산업 배포로 재현성 사실상 증명 |
주장별 신뢰도
| # | 주장 | 근거 | 신뢰도 |
|---|---|---|---|
| 1 | Orca 대비 2~4배 처리량 | Figure 12~14, 다양한 모델/워크로드 | 🟢 |
| 2 | 메모리 낭비 60~80% → 4% | Section 6 측정 | 🟢 |
| 3 | CoW로 KV ~55% 절감 | Figure 15 빔 서치 실험 | 🟢 |
| 4 | 블록 크기 B=16 최적 | Figure 18, 단일 워크로드 | 🟡 |
| 5 | 스와핑이 재계산과 유사 비용 | Section 7.3, 환경 의존 | 🟡 |
읽기 난이도: ⭐⭐
OS 페이징 기초와 Transformer attention을 알고 있으면 직관적. CUDA 커널 디테일까지 따라가려면 ⭐⭐⭐.
관련 연구 비교 매트릭스
| 축 | 본 논문(vLLM) | Orca (OSDI’22) | FasterTransformer | FlashAttention (NeurIPS’22) |
|---|---|---|---|---|
| 핵심 접근 | KV 캐시 페이징 + CoW | Iteration-level batching | 정적 배칭, 커널 최적화 | on-chip tiling/fusion |
| 문제 정의 | 메모리 단편화 | 배칭 단위의 synchrony | 커널 효율 | attention의 HBM I/O |
| 데이터 | ShareGPT/Alpaca | 자체 트레이스 | 합성 | 합성 |
| 핵심 메트릭 | 2~4× 처리량 | ~1.9× vs static | 커널 TFLOPs | 2~4× 속도 |
| 확장성 | 모델/길이에 강건 | 긴 시퀀스서 약함(단편화) | 동일 문제 | 모든 attention에 보조적 |
| 한계 | 커널 복잡도 | KV 단편화 미해결 | 사전 할당 낭비 | 메모리 할당은 미해결 |
| 코드 공개 | ✅ | ⚠️ | ✅ | ✅ |
관련 연구
- Attention Methods — attention 계열 비교 맥락
- GQA - Training Generalized Multi-Query Transformer Models — KV 헤드 수 감소로 캐시 크기를 직접 축소하는 직교적 접근
- Mamba - Linear-Time Sequence Modeling with Selective State Spaces — KV 캐시 자체를 제거하는 대안 아키텍처
원자적 인사이트 (Zettelkasten)
💡 DL 서빙 문제는 OS 문제로 재환원 가능하다
출처: PagedAttention - Efficient Memory Management for LLM Serving with vLLM (Kwon et al., 2023)
유형: 방법론적 / 연결
“가변 길이 시퀀스의 KV 캐시”는 “가변 크기 힙을 할당하는 프로세스”와 대수적으로 동형이다. OS 가상 메모리(페이지 테이블, 물리 프레임, CoW)를 구조째 가져오면 단편화 3종과 공유 문제가 한 번에 풀린다. 이는 DL 시스템 연구의 탐색 공간에 “고전 OS 기법 포팅”을 정식 전략으로 추가한다.
핵심 조건/맥락: 시퀀스가 append-only로 성장하고, 접근 패턴이 순차적이어서 TLB-스타일 간접접근 오버헤드가 계산 비용에 묻힐 때.
연결: FlashAttention, Virtual Memory in Operating Systems
활용 가능성: activation checkpointing, optimizer state sharding 등에도 페이징/스와핑 유사 적용 가능.
💡 처리량 병목은 FLOPs가 아니라 “동시 시퀀스 수”다
출처: 동 논문 Section 6~7
유형: 실험적
KV 캐시 낭비를 6080% → 4%로 줄이면 동일 GPU에 올릴 수 있는 시퀀스 수가 몇 배로 늘고, 이것이 그대로 처리량 24×로 이어진다. 즉 배치 내 산술 강도가 증가해 메모리-bound 구간이 연산-bound로 이동한다.
핵심 조건/맥락: 디코딩 지배적 워크로드(인코더 prefill 비중이 작을 때). prefill이 크면 chunked prefill 기법이 별도로 필요.
연결: Arithmetic Intensity, Continuous Batching
활용 가능성: 하드웨어 선택(HBM 용량 vs TFLOPs) 의사결정의 기준.
💡 Copy-on-Write는 분기형 디코딩의 1차 프리미티브다
출처: 동 논문 Section 4.3
유형: 방법론적
빔 서치, 병렬 샘플링, 트리 탐색(ToT), 스펙큘레이티브 디코딩은 모두 “공통 접두 + 분기”라는 공통 구조를 가진다. CoW는 이 구조를 KV 레벨에서 직접 지원하는 최소 기제다. 이후 등장한 RadixAttention(SGLang), prefix caching은 이 인사이트의 일반화다.
핵심 조건/맥락: 분기 지점에서 새 쓰기가 희소할 때 이득이 크다. 완전히 독립적인 샘플링이면 이득이 사라진다.
연결: Tree of Thoughts, Speculative Decoding, RadixAttention
활용 가능성: agent 시스템의 rollout 공유, multi-turn session 간 prefix 공유.
💡 블록 크기는 단편화-커널효율의 trade-off 파라미터다
출처: 동 논문 Figure 18
유형: 실험적 / 실패-한계
블록이 작을수록 단편화가 줄지만 GPU 커널의 메모리 접근 효율이 떨어지고(짧은 배치 내 gather), 커질수록 반대다. 논문은 B=16을 경험적 sweet spot으로 제시하지만, 이 값은 모델 구조/시퀀스 분포/하드웨어에 의존한다.
핵심 조건/맥락: A100·OPT·평균 길이 수백~수천 토큰 워크로드.
연결: Cache Line Size, Tiling in GPU Kernels
활용 가능성: 워크로드 프로파일 기반 auto-tuning 모듈의 설계 근거.
💡 “메모리 레이아웃 설계”가 SOTA 서빙의 축으로 부상했다
출처: 동 논문 Related Work + 후속 연구 군집
유형: 이론적 / 연결
FasterTransformer 시대의 경쟁축은 “커널이 얼마나 빠른가”였다. vLLM 이후는 “캐시를 어떻게 배치·공유·교체하는가”가 추가되었고, 이는 prefix cache, chunked prefill, disaggregated serving으로 확산된다.
핵심 조건/맥락: 장문 생성·고동시성·다중 사용자 전제.
연결: DistServe, SGLang, Prefix Caching
활용 가능성: 서빙 스택 로드맵 수립 시 “레이아웃 최적화 레이어”를 필수 계층으로 포함.
핵심 용어 정리
| 용어 | 정의 |
|---|---|
| KV 캐시 | 디코딩 중 과거 토큰의 attention key/value 텐서를 저장한 버퍼. 길이에 비례. |
| PagedAttention | KV 캐시를 고정 크기 블록으로 쪼개 비연속 저장을 허용하는 attention 커널. |
| 논리 블록 / 물리 블록 | 시퀀스 관점의 순차 블록 번호 / GPU 메모리 풀의 실제 위치. |
| 블록 테이블 | per-sequence 논리→물리 매핑. OS의 페이지 테이블에 해당. |
| Copy-on-Write(CoW) | 공유 블록에 쓰기 발생 시 해당 블록만 복제하는 정책. |
| Internal/External fragmentation | 예약 영역 내부의 미사용 / 시퀀스 간 연속 영역의 파편화. |
| Reservation waste | 아직 생성되지 않은 미래 토큰을 위해 잡아두는 사전 예약 낭비. |
| Continuous batching | 요청별이 아니라 iteration 단위로 배치를 재구성하는 스케줄링 (Orca). |
| 재계산(recomputation) | preempt된 요청의 KV를 버리고 prompt부터 다시 계산하는 복구 방식. |
| 스와핑(swapping) | preempt된 요청의 KV를 CPU RAM으로 옮겼다가 복원하는 방식. |