LLM 서빙 처리량을 극대화하는 PagedAttention과 KV 캐시 메모리 가상화 아키텍처

대규모 언어 모델(LLM)을 프로덕션 환경에 서빙할 때 가장 큰 병목은 모델 파라미터 자체의 크기가 아니라, 자기회귀(Autoregressive) 생성 과정에서 동적으로 누적되는 KV 캐시(Key-Value Cache) 메모리입니다. 각 토큰을 생성할 때마다 이전 토큰들의 Key와 Value 텐서를 계속 보관해야 하므로, 배치 크기(Batch Size)와 동시 요청 수가 증가할수록 고가의 GPU VRAM이 급격히 고갈됩니다.

전통적인 서빙 프레임워크는 사전 할당(Pre-allocation) 방식을 채택하여 최대 시퀀스 길이(예: 4,096 토큰)에 맞춘 연속된 메모리 공간을 요청마다 통째로 예약했습니다. 이로 인해 실제 생성된 토큰 수가 적을 때 발생하는 내부 단편화(Internal Fragmentation)와 메모리 예약 시점의 외부 단편화(External Fragmentation)로 인해 전체 VRAM의 60~80%가 낭비되는 비효율이 발생했습니다. 본 글에서는 운영체제의 가상 메모리 페이징(Virtual Memory Paging) 메커니즘을 트랜스포머 어텐션 연산에 도입하여 메모리 낭비를 4% 미만으로 억제한 vLLM의 PagedAttention 아키텍처를 심층 분석합니다.

1. KV 캐시 메모리 단편화의 구조적 원인

• 동적 시퀀스 길이의 불확실성: 요청이 들어오는 시점에는 모델이 몇 개의 토큰을 생성하고 종료(EOS)할지 알 수 없으므로, 시스템은 안전을 위해 max_model_len 크기의 연속 메모리를 사전에 확보해야 했습니다.
• 예약 낭비(Reservation Waste): 4,096 토큰 용량을 예약했으나 사용자가 200 토큰만 생성하고 종료하면, 나머지 3,896 토큰 분량의 VRAM은 다른 요청에 할당되지 못한 채 유휴 상태로 방치됩니다.
• 메모리 공유 불가능: 동일한 시스템 프롬프트(System Prompt)나 문맥을 공유하는 여러 요청이 들어와도 연속 메모리 제약으로 인해 프롬프트 캐시를 복제해야만 했습니다.

2. PagedAttention의 핵심 원리: 블록 테이블과 논리-물리 주소 변환

PagedAttention은 연속된 거대 텐서 공간을 요구하지 않습니다. 대신 고정된 크기(예: 16 또는 32 토큰)의 논리 블록(Logical Block)으로 KV 텐서를 분할하고, 실제 GPU VRAM에는 불연속적으로 분산된 물리 블록(Physical Block)에 매핑합니다.

# PagedAttention 논리 블록 및 블록 테이블 매핑 개념 구현체
from dataclasses import dataclass
from typing import List, Dict

BLOCK_SIZE = 16  # 블록당 수용 가능한 토큰 수

@dataclass
class PhysicalTokenBlock:
    block_number: int
    ref_count: int = 1

class BlockTable:
    def __init__(self, request_id: str):
        self.request_id = request_id
        self.logical_to_physical: List[int] = []  # 물리 블록 번호 리스트

    def append_token(self, token_idx: int, free_block_pool: List[int]) -> int:
        logical_block_number = token_idx // BLOCK_SIZE
        offset_in_block = token_idx % BLOCK_SIZE

        # 새 논리 블록이 필요한 시점에만 물리 블록 할당
        if logical_block_number >= len(self.logical_to_physical):
            new_physical_block = free_block_pool.pop(0)
            self.logical_to_physical.append(new_physical_block)
            return new_physical_block

        return self.logical_to_physical[logical_block_number]

트랜스포머 어텐션 커널을 실행할 때, PagedAttention은 블록 테이블(Block Table)을 참조하여 물리적으로 흩어져 있는 메모리 주소에서 Key와 Value 벡터를 동적으로 패치(Fetch)하여 내적을 수행합니다. 이를 통해 메모리 낭비율은 마지막 블록 내부의 미사용 공간(평균 BLOCK_SIZE / 2)으로 국한되며, 전체 VRAM 낭비율은 4% 미만으로 극적으로 감소합니다.

3. Copy-on-Write 기반의 프롬프트 공유 및 디코딩 최적화

PagedAttention은 다중 병렬 샘플링(Beam Search, Best-of-N)이나 긴 공통 프롬프트를 처리할 때 운영체제의 Copy-on-Write(CoW) 기법을 완벽하게 재현합니다.

# Copy-on-Write 기반 프롬프트 블록 공유 메커니즘
class KVCacheManager:
    def __init__(self):
        self.physical_blocks: Dict[int, PhysicalTokenBlock] = {}
        self.free_pool: List[int] = list(range(1024))  # 가용 물리 블록 풀

    def fork_sequence(self, parent_table: BlockTable, new_request_id: str) -> BlockTable:
        child_table = BlockTable(request_id=new_request_id)
        # 물리 블록을 복사하지 않고 참조 카운트(ref_count)만 증가시켜 즉시 공유
        for p_block_num in parent_table.logical_to_physical:
            child_table.logical_to_physical.append(p_block_num)
            self.physical_blocks[p_block_num].ref_count += 1
        return child_table

    def resolve_cow(self, table: BlockTable, token_idx: int) -> int:
        logical_block_num = token_idx // BLOCK_SIZE
        current_p_block = table.logical_to_physical[logical_block_num]

        # 새 토큰 생성으로 쓰기 발생 시, 참조 카운트가 2 이상이면 물리 블록 복제
        if self.physical_blocks[current_p_block].ref_count > 1:
            self.physical_blocks[current_p_block].ref_count -= 1
            new_p_block = self.free_pool.pop(0)
            self.physical_blocks[new_p_block] = PhysicalTokenBlock(block_number=new_p_block)
            table.logical_to_physical[logical_block_num] = new_p_block
            return new_p_block

        return current_p_block

4. 결론 및 기대 효과

vLLM의 PagedAttention은 하드웨어 업그레이드 없이 소프트웨어 아키텍처 혁신만으로 LLM 서빙 처리량을 2~4배 향상시킨 대표적인 시스템 엔지니어링 사례입니다. 가상 메모리 페이징 기법을 어텐션 연산에 이식함으로써, 메모리 단편화를 제거하고 프로덕션 AI 인프라의 단위 서빙 비용을 획기적으로 낮출 수 있습니다.

출처 및 1차 공식 기술 문서

• Woosuk Kwon et al. — Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023)
• vLLM Official Documentation — High-Throughput and Memory-Efficient LLM Serving
• vLLM GitHub Repository — Open Source PagedAttention Implementation