PagedAttention Analysis

PagedAttention 심층 분석 — LLM KV 캐시 메모리 관리

vLLM · KV Cache Paging · Block Table · Copy-on-Write · Continuous Batching · KV Offloading

개요

PagedAttention(Kwon et al., SOSP 2023)은 운영체제의 가상 메모리·페이징을 LLM의 KV 캐시 관리에 적용한 기법입니다. 기존 서빙 시스템이 단편화와 과다 예약으로 KV 캐시 메모리의 60~80%를 낭비하던 문제를, KV 캐시를 고정 크기 블록으로 쪼개고 블록 테이블로 비연속 관리함으로써 4% 미만으로 줄였습니다. 그 결과 동일 하드웨어에서 처리량을 2~4배 끌어올렸고, 이를 구현한 vLLM은 사실상의 표준 서빙 엔진이 되었습니다. 본 문서는 단편화 문제 → OS 페이징 유추 → 블록 테이블·커널 → copy-on-write·프리픽스 공유 → 성능 → 메모리 티어링/오프로딩 연결의 순서로 분석합니다.

PagedAttention은 단일 요청의 메모리 낭비를 줄이는 데서 끝나지 않습니다. 여러 요청이 같은 프리픽스를 공유할 때 copy-on-write로 블록을 재사용하고, 블록 크기를 고정해 스왑·오프로딩 단위를 명확하게 만듭니다. 이 때문에 서빙 처리량, 배치 유연성, 계층형 메모리 연계가 함께 좋아집니다.

핵심 개념

• KV 블록: KV 캐시를 고정 크기 토큰 묶음으로 나눈 단위입니다.
• 블록 테이블: 논리 블록 번호를 비연속 물리 블록에 매핑하는 표입니다.
• on-demand 할당: 필요한 시점에만 물리 블록을 붙여 내부 단편화를 마지막 블록 하나로 제한합니다.
• copy-on-write: 공유 중인 블록에 쓰기가 필요한 순간에만 복사해 메모리를 절약합니다.

1. 문제 — KV 캐시의 메모리 낭비

LLM 서빙에서 디코딩은 메모리 바운드이므로, 처리량을 높이려면 더 많은 요청을 한 번에 배치해야 합니다. 그런데 각 요청의 KV 캐시가 크고 동적이라, 이를 어떻게 메모리에 담느냐가 곧 처리량을 결정합니다. 기존 시스템은 딥러닝 프레임워크의 '연속 텐서' 제약 때문에 요청마다 최대 시퀀스 길이만큼의 연속 메모리를 미리 예약했고, 이것이 큰 낭비를 낳았습니다.

그림 1. 연속 할당 방식의 세 가지 KV 캐시 낭비(예약·내부 단편화·외부 단편화)

세 가지 낭비와 그 규모

• 예약(reserved) — 미래 토큰용으로 잡아둔 슬롯. 지금 다른 요청이 쓰지 못함.

• 내부 단편화(internal fragmentation) — 실제 시퀀스 길이가 예약한 최대 길이보다 짧아 영영 안 쓰이는 공간.

• 외부 단편화(external fragmentation) — 연속 청크들 사이에 생기는, 크기가 맞지 않아 재사용 불가능한 틈.

vLLM 자료에 따르면 기존 시스템은 KV 캐시 메모리의 60~80%를 낭비했고, 실제 토큰이 차지하는 비율은 Orca 계열에서 13.3~38.2%에 불과했습니다. 13B OPT 모델 기준 토큰 1개의 KV 캐시는 약 800KB, 시퀀스 1개는 최대 1.6~1.7GB(OPT/LLaMA-13B)에 달하므로, 이 낭비는 곧 배치 크기와 처리량의 직접적 손실입니다.

2. 핵심 아이디어 — OS 페이징을 KV 캐시에

PagedAttention의 통찰은 이 문제가 운영체제가 이미 푼 문제와 같다는 것입니다. OS는 프로세스의 메모리를 고정 크기 페이지로 나누고, 페이지 테이블로 가상 주소를 비연속 물리 프레임에 매핑해 외부 단편화를 없앱니다. 같은 발상을 KV 캐시에 적용합니다.

그림 2. OS 가상메모리와의 대응, 그리고 블록 테이블의 논리→물리 매핑

대응 관계

KV 캐시를 고정 크기 KV 블록(블록당 B개 토큰의 K·V)으로 나누고 비연속 물리 메모리에 배치합니다. 블록 크기가 모두 같으므로 외부 단편화가 원천 제거되고, 블록을 필요할 때(on-demand) 할당하므로 내부 단편화는 시퀀스당 마지막 블록 하나(최대 B−1=15토큰)로 제한됩니다. 이것이 낭비 4% 미만의 근거입니다. 어텐션은 과거 K/V를 순회만 하면 되므로 비연속 저장이 정확도에 영향을 주지 않습니다.

3. PagedAttention 커널 — 블록 단위 어텐션

KV 캐시가 비연속 블록에 흩어져 있으므로, 어텐션 커널도 이를 블록 단위로 순회하도록 재정식화합니다. 수학적으로는 기존 어텐션과 완전히 동일하며, 단지 K/V를 블록 묶음으로 나누어 부분합을 누적할 뿐입니다.

그림 3. query가 비연속 KV 블록을 블록 단위로 fetch하여 어텐션을 계산

블록 단위 어텐션 (개념적 의사코드)

• vLLM 커널에서 한 블록은 한 헤드의 16토큰 × head_dim(예: 128) = 2048개 요소를 담으며, 워프(32 스레드)가 한 번에 한 블록을 처리합니다.

• 비용: 블록 테이블 조회와 추가 분기 때문에 비페이지드 커널 대비 약 20~26% 느립니다(논문 측정). 그러나 메모리 절약으로 배치를 크게 키울 수 있어 전체 처리량은 크게 향상됩니다.

• vLLM은 이 indirection 오버헤드를 어텐션 등 다른 연산과 GPU 커널을 융합(fuse)해 완화합니다.

4. 메모리 공유 — Copy-on-Write와 프리픽스 공유

블록 테이블이라는 간접 계층은 단편화 제거를 넘어 또 하나의 강력한 능력을 줍니다. 여러 시퀀스가 같은 물리 블록을 공유하고, 쓰기가 필요한 순간에만 복사하는 copy-on-write입니다. 이는 OS가 fork된 프로세스끼리 페이지를 공유하는 방식과 같습니다.

그림 4. 병렬 샘플링의 COW와 공유 프리픽스(시스템 프롬프트) 공유

공유 시나리오

• 병렬 샘플링 — 한 프롬프트로 여러 답을 생성할 때, 프롬프트의 KV 블록을 참조 카운트와 함께 공유하고, 각 샘플이 분기해 서로 다른 토큰을 쓰는 순간(ref>1 감지)에만 블록을 복사합니다.

• 빔서치 — 후보(beam)들이 프롬프트뿐 아니라 중간 블록까지 공유하며, 공유 패턴이 동적으로 진화합니다. 기존 시스템의 잦은 KV 복사를 블록 공유로 대체합니다.

• 공유 프리픽스 — 시스템 프롬프트나 few-shot 예시처럼 모든 요청이 공유하는 앞부분의 KV를 미리 캐시해두면, 프리픽스 계산은 1회로 끝나고 메모리도 1벌만 차지합니다.

메모리 절감(논문 실측) — 병렬 샘플링과 빔서치에서 최대 55% 절감(빔서치 37.6~55.2%, 병렬 샘플링 6.1~9.8%, ShareGPT 워크로드에선 16.2~30.5%). 논리→물리 매핑 계층이 공유의 복잡성을 숨기므로, 서로 다른 샘플링 요구를 가진 요청들도 한 배치에 섞을 수 있습니다.

자동 프리픽스 캐싱(APC)

vLLM은 각 KV 블록을 '프리픽스 토큰들의 해시'로 식별해 전역 해시 테이블에 등록함으로써, 트리 구조 없이도 공통 프리픽스를 자동으로 공유합니다(enable_prefix_caching). SGLang의 RadixAttention은 같은 목표를 radix tree(트라이)로 달성하는 대안입니다.

5. 성능과 vLLM 시스템

PagedAttention의 메모리 효율은 그대로 처리량으로 이어집니다. 낭비를 없앤 만큼 더 많은 요청의 KV가 메모리에 들어가고, 더 큰 배치가 디코딩의 메모리 대역폭을 더 잘 활용하기 때문입니다.

그림 5. KV 메모리 활용률(96.3% vs 13~38%)과 처리량 향상, continuous batching과의 상보성

Continuous Batching과의 상보성

vLLM은 PagedAttention을 continuous batching(iteration-level scheduling, Orca에서 유래)과 결합합니다. Continuous batching이 매 디코딩 스텝마다 완료된 요청을 빼고 새 요청을 넣어 GPU를 꽉 채우는 스케줄링 측면이라면, PagedAttention은 메모리 낭비를 없애 더 많은 요청의 working set이 메모리에 들어가게 하는 메모리 측면입니다. 두 기법은 상보적이며, 함께 작동해 처리량을 극대화합니다. vLLM은 UC Berkeley에서 시작해 2000명 이상이 기여하는 대표적 오픈소스 서빙 엔진으로 성장했습니다.

6. 선점·스왑·재계산과 트레이드오프

메모리 부족 시 — 스왑 vs 재계산

요청이 몰려 GPU 메모리가 부족하면 vLLM은 FCFS로 최신 요청을 선점(preempt)하고, 두 가지 방법으로 복구합니다.

• 스왑(swapping) — 퇴출된 블록을 CPU RAM으로 복사합니다. vLLM은 GPU 블록 할당기 외에 CPU 블록 할당기를 두며, CPU로 스왑되는 블록 수는 GPU 물리 블록 총수를 넘지 않으므로 스왑 공간의 상한이 정해집니다.

• 재계산(recomputation) — 퇴출 후 다시 admit할 때 prefill을 재실행합니다. PCIe 대역폭을 쓰지 않아 블록 크기에 무관하게 일정한 오버헤드를 가지며, 수 GB의 KV를 PCIe로 왕복시키느니 재계산이 더 빠른 경우가 많습니다. vLLM V1에서는 기본 선점 모드가 SWAP이 아니라 RECOMPUTE입니다.

• all-or-nothing 퇴출 — 한 시퀀스의 모든 블록을 함께 스왑/재계산합니다(요청 처리에 모든 토큰 상태가 GPU에 있어야 한다는 점을 활용). OS 페이징에는 없는 LLM 특화 최적화입니다.

블록 크기의 트레이드오프

블록이 너무 작으면 블록 테이블 조회 횟수와 관리 오버헤드가 늘고, 너무 크면 짧은 응답에서 내부 단편화가 커집니다. 논문 실험에서 ShareGPT(긴 시퀀스)는 16~128, Alpaca(짧은 시퀀스)는 16~32가 좋았고, 결론적으로 16이 GPU 활용에는 충분히 크고 단편화 방지에는 충분히 작아 기본값이 되었습니다.

대안 — vAttention

vAttention(ASPLOS 2025)은 PagedAttention의 비연속 레이아웃이 새 커널 이식을 어렵게 하고 커널 성능을 떨어뜨린다고 비판하며, user-space 페이징 대신 CUDA 가상 메모리 API(가상 주소는 연속 예약, 물리 메모리는 on-demand 매핑)로 같은 목표를 달성합니다. 미수정 어텐션 커널을 그대로 쓰면서 최대 1.23배 처리량 향상을 보고했습니다("up to" 값).

7. 메모리 티어링·KV 캐시 오프로딩 연결

PagedAttention의 고정 크기 블록은 단편화 해결을 넘어, KV 캐시를 다른 메모리 계층으로 옮기는 '이동 단위'로도 자연스럽게 쓰입니다. 이는 메모리 티어링의 페이지와 동형이며, KV 캐시 오프로딩 연구의 직접적 기반이 됩니다.

그림 6. 블록을 이동 단위로 하는 메모리 계층과 KV 오프로딩 연구의 계보

오프로딩 관련 연구의 흐름은 아래 표와 같이 이어집니다.

왜 PagedAttention이 기반인가

• 고정 크기 블록은 그 자체로 관리·이동의 단위 → 메모리 티어링의 페이지와 동형. 'KV 블록을 어느 티어에 둘 것인가'가 곧 promotion/demotion 정책 문제로 환원됩니다.

• vLLM은 이미 CPU 블록 할당기로 블록을 CPU로 스왑합니다. 계층은 GPU HBM(~3.35TB/s) → CPU DRAM(~63GB/s PCIe5) → NVMe(~7GB/s) → 원격/CXL로 이어집니다.

• CXL의 의의는 PCIe 오프로딩(8~12GB/s)의 대역폭·지연 한계를 완화하고, CXL→GPU 직접 경로를 가능케 한다는 점입니다. Tang et al.은 CXL-GPU 전송이 CPU-GPU 전송과 대등함을 실험으로 보였습니다.

비교/분석

PagedAttention은 OS 가상 메모리와 같은 추상화를 사용해 KV 캐시를 다룹니다.

블록 테이블 조회 의사코드

# 블록 테이블: 논리 블록 번호 → 물리 블록 번호
# query q_i 에 대해 흩어진 KV 블록들을 순회하며 부분 softmax 누적
out_i = 0
denom = 0
running_max = -inf
for j in range(num_blocks):                # 논리 블록 0..n
    phys = block_table[seq][j]             # 물리 블록 위치 조회
    K_j = K_cache[phys]                    # 블록 내 B(=16)개 토큰의 Key
    V_j = V_cache[phys]                    # 블록 내 B개 토큰의 Value
    s   = (q_i @ K_j.T) / sqrt(d)          # 블록에 대한 점수
    # 온라인 softmax (FlashAttention 스타일)로 max/분모/누적을 갱신
    out_i, denom, running_max = online_softmax_update(
        out_i, denom, running_max, s, V_j
    )
o_i = out_i / denom                        # 최종 어텐션 출력

처리량 비교

장단점

장점

• KV 캐시를 고정 크기 블록으로 관리해 외부 단편화를 사실상 제거하고, 내부 단편화도 마지막 블록 하나로 제한합니다.
• copy-on-write와 프리픽스 공유를 통해 병렬 샘플링, 빔서치, 시스템 프롬프트 재사용에서 메모리 절감 효과를 바로 얻을 수 있습니다.
• continuous batching, CPU 스왑, 계층형 KV 오프로딩과 결합하기 쉬워 서빙 엔진 전체의 확장성과 운영 유연성을 높입니다.

단점

• 블록 테이블 조회와 비연속 접근 때문에 전용 어텐션 커널이 필요하고, 커널 자체 성능은 연속 레이아웃 대비 불리할 수 있습니다.
• 블록 크기 선택이 어렵습니다. 너무 작으면 관리 오버헤드가 커지고, 너무 크면 짧은 응답에서 내부 단편화가 다시 늘어납니다.
• GPU 메모리가 부족할 때는 스왑 또는 재계산 정책을 추가로 설계해야 하므로, 단순 연속 할당보다 런타임 정책이 복잡해집니다.

관련 기술 및 참고 문헌

• Kwon et al., "Efficient Memory Management for Large Language Model Serving with PagedAttention", SOSP 2023 / arXiv:2309.06180.
• vLLM Project Documentation, "Paged Attention" 및 prefix caching, preemption, continuous batching 관련 문서.
• Tang et al., CXL 기반 KV cache offloading 연구(CXL-KV) 발표 자료 및 프리프린트.
• LMCache, Mooncake, vAttention 논문/프로젝트 문서.

핵심 정리

PagedAttention은 OS 페이징을 KV 캐시에 적용해, 캐시를 고정 크기 블록으로 쪼개고 블록 테이블로 비연속 관리함으로써 기존의 60~80% 낭비를 4% 미만으로 줄였다. 블록 단위 어텐션 커널은 수학적으로 동일하며, 참조 카운팅과 copy-on-write로 병렬 샘플링·빔서치·공유 프리픽스에서 KV를 공유한다. continuous batching과 결합한 vLLM은 처리량을 2~4배, HuggingFace 대비 14~24배까지 끌어올려 사실상의 표준이 되었다. 고정 블록 추상화는 스왑·재계산을 거쳐 CXL·계층형 메모리로의 KV 오프로딩으로 이어지며, 이는 'KV 블록을 어느 티어에 둘 것인가'라는 메모리 티어링 문제와 직접 맞닿는다.

주의 — 본문 수치는 1차 논문(arXiv 2309.06180)·vLLM 공식 자료의 실측이나 모델(OPT/LLaMA)·데이터셋(ShareGPT/Alpaca)·하드웨어(A100/A10G) 조건에 따른 값이다(14~24배는 HF 비배치 대비, 2~4배는 Orca/FasterTransformer 대비). CXL-KV의 'GPU 87% 절감'류 수치는 측정이 아니라 ROI 모델 추정치(필요 GPU 수 기준)이며, CXL-PNM 등 2025말~2026초 프리프린트의 'up to' 값은 동료심사 여부에 유의해야 한다. vLLM V0/V1은 선점 기본 모드가 다르다.