PagedAttention과 RadixAttention으로 LLM KV 캐시 최적화

이 요약은 AI가 원문을 분석해 생성했습니다. 정확한 내용은 원문 기준으로 확인하세요.

TL;DR

긴 컨텍스트 LLM serving에서 KV 캐시는 시퀀스 길이에 비례해 커지며 GPU 메모리, 동시성, 처리량을 제한하는 핵심 병목입니다. PagedAttention은 KV 캐시를 16 또는 32토큰 단위의 비연속 블록으로 나누고 block table로 주소를 변환해 메모리 단편화와 과잉 예약을 줄입니다. RadixAttention은 반복되는 prompt prefix를 radix tree에 저장하고 가장 긴 일치 prefix의 KV 상태를 재사용해 suffix만 계산하므로 prefill 비용과 Time to First Token을 낮춥니다. vLLM의 chain hashing도 같은 prefix 재사용을 제공하며, cache salting, 계층형 KV caching, cache-aware routing은 멀티테넌트 보안과 분산 serving으로 확장하기 위한 후속 기법입니다.

섹션별 상세

01

긴 컨텍스트를 처리하는 LLM serving에서는 모델 연산 자체보다 KV 캐시가 GPU 메모리의 주요 병목이 됩니다. Transformer는 새 토큰을 생성할 때 이전 토큰의 Key와 Value 벡터를 반복해서 참조하므로 이를 KV 캐시에 저장해 재계산을 피하지만, 캐시 크기는 시퀀스 길이에 선형으로 증가합니다. Llama-3 8B급 모델의 예에서 32개 레이어, 8개 KV head, head dimension 128, FP16 조건이면 토큰 하나가 약 128 KiB를 차지하고 100,000토큰 컨텍스트에는 약 12.8 GiB가 필요해 동시 요청 수와 처리량이 제한됩니다.

근거

Llama-3 8B급 모델에서 100,000토큰 컨텍스트는 batching과 추가 요청을 고려하기 전에도 약 12.8 GiB의 KV 캐시 메모리를 요구합니다. — KV 캐시 병목을 설명하는 도입부의 메모리 계산 예시

02

PagedAttention은 요청마다 최대 컨텍스트 길이에 가까운 연속 메모리를 미리 예약하던 방식에서 벗어나 KV 캐시를 고정 크기 블록으로 나누고 실제 토큰이 생성될 때만 블록을 할당합니다. 각 요청의 block table이 논리 블록 ID를 GPU의 물리 블록 위치로 변환하므로 물리적으로 흩어진 KV 데이터를 attention kernel이 하나의 연속 시퀀스처럼 읽을 수 있습니다. 일반적인 블록 크기는 16 또는 32토큰이며, 60토큰을 생성하는 요청에는 실제로 필요한 블록만 배정되어 내부 단편화와 요청 길이 차이로 생기는 외부 단편화를 함께 줄입니다.

논리 KV 블록이 GPU DRAM의 서로 떨어진 물리 블록에 매핑되는 구조를 나타낸 도식입니다. — Diagram왼쪽에는 요청의 토큰이 논리 블록에 순서대로 배치되고, 가운데 block table이 논리 블록 번호와 물리 블록 번호를 연결합니다. 오른쪽 GPU DRAM에서는 Block 7, Block 1, Block 3처럼 물리 위치가 흩어져 있지만 block table을 통해 요청 순서대로 읽을 수 있어 PagedAttention의 비연속 메모리 할당 원리를 보여줍니다.

근거

PagedAttention은 KV 캐시를 16 또는 32토큰 단위의 고정 크기 블록으로 나누고 block table을 통해 논리 블록과 GPU 물리 블록을 연결합니다. — PagedAttention 작동 방식의 블록 분할과 block table 단계 및 이미지 1

03

PagedAttention은 메모리 배치 문제를 해결하지만 동일한 prompt prefix를 새 요청마다 다시 계산하는 비용까지 제거하지는 못합니다. RadixAttention은 완료된 요청의 KV 상태를 버리지 않고 토큰 경로를 radix tree에 연결해 공통 prefix를 한 번만 보관하며, 새 요청이 들어오면 가장 긴 일치 경로를 찾아 기존 KV를 재사용하고 일치하지 않는 suffix만 Transformer에 통과시킵니다. 예를 들어 2,000토큰 요청 중 1,900토큰이 이미 캐시에 있으면 100토큰만 prefill하므로 긴 대화, RAG, coding assistant, agent loop에서 Time to First Token을 줄이는 효과가 커집니다.

공유되는 프롬프트 prefix를 radix tree의 공통 경로로 저장하는 구조입니다. — DiagramRoot 아래에서 동일한 문장 조각이 먼저 공유되고 이후 User, Admin, French, Spanish처럼 토큰이 달라지는 지점에서 가지가 나뉩니다. 이 구조는 여러 요청의 반복 prefix를 하나의 경로로 보관해 RadixAttention이 긴 일치 prefix를 찾도록 하는 방식을 시각화합니다.

Prefix Cache가 없을 때와 있을 때 입력 토큰의 KV tensor 계산량을 비교한 흐름도입니다. — Diagram캐시가 없으면 세 요청이 공통으로 포함한 프롬프트 전체에 대해 매번 KV tensor를 계산합니다. Prefix Cache를 사용하면 공통 prompt 부분의 KV tensor를 캐시에서 조회하고 새로 들어온 suffix만 모델에서 계산하므로 반복 prefill을 줄이는 과정을 보여줍니다.

RadixAttention이 공유 prefix의 KV를 재사용하고 요청별 suffix만 계산하는 과정을 나타낸 도식입니다. — DiagramRequest A는 shared prefix와 suffix A를 함께 처리해 prefix KV와 전체 요청 KV를 radix tree cache에 저장합니다. Request B가 들어오면 longest-prefix match로 KV(prefix)를 불러오고 suffix B만 prefill해 새 KV 경로를 추가하므로, 동일한 leading token IDs에 대한 재계산을 피합니다.

두 요청이 공유하는 KV Cache를 재사용해 계산 토큰 수를 줄이는 예시입니다. — DiagramRequest I의 What, day, is, it, today 다섯 토큰을 먼저 계산한 뒤 Request II의 What day is it 부분을 재사용하고 tomorrow 한 토큰만 계산합니다. 이미지의 5 tokens computed와 1 token computed 비교는 공통 prefix가 길수록 새 prefill 작업이 줄어드는 원리를 보여줍니다.

radix tree에 새 단어 firm의 토큰 경로를 삽입하는 과정을 나타낸 도식입니다. — Diagram기존 tree에는 dog, dot, pump, fat, fire 경로가 있고, Insert firm 단계에서 f와 i, r 경로를 공유한 뒤 마지막 m 노드를 새로 추가합니다. 녹색으로 표시된 경로는 기존 토큰을 재사용하면서 새로운 suffix만 삽입하는 RadixAttention의 동작을 나타냅니다.

근거

RadixAttention은 가장 긴 일치 token prefix의 KV 텐서를 재사용하고 일치하지 않는 suffix만 계산해 반복적인 prefill 연산을 줄입니다. — RadixAttention의 prefix matching과 suffix 계산 단계 및 이미지 4와 이미지 5

04

RadixAttention은 요청 처리 후 새로 계산한 KV 텐서를 radix tree에 삽입해 다음 요청이 더 긴 prefix를 재사용하도록 만들고, GPU 메모리가 부족해지면 공유 interior prefix를 보호하면서 leaf branch부터 제거합니다. 이 leaf-based eviction은 여러 요청이 함께 사용하는 경로보다 최근 사용되지 않은 개별 경로를 우선 축출해 캐시 적중률을 유지하려는 방식입니다. PagedAttention이 GPU 메모리의 저장 위치와 할당을 최적화한다면 RadixAttention은 이미 계산한 상태를 검색하고 재사용하는 계산 최적화이므로 두 기법은 경쟁 관계가 아니라 서로 다른 계층에서 결합됩니다.

LRU 정책에서 가장 오래 사용되지 않은 캐시 항목을 축출하는 과정을 보여주는 도식입니다. — Diagram캐시 항목은 Most Recently Used에서 Least Recently Used 방향으로 정렬되며 새 데이터가 들어올 때 오래 사용되지 않은 항목이 하단에서 제거됩니다. 기사에서 설명한 RadixAttention의 leaf-based eviction과 연결해 보면 공유 interior prefix를 보존하면서 사용 빈도가 낮은 말단 경로를 우선 정리하는 캐시 관리 원리를 이해할 수 있습니다.

근거

PagedAttention은 메모리 할당과 배치를 최적화하고 RadixAttention은 요청 사이의 KV 상태 재사용을 최적화하므로 두 기법은 서로 다른 문제를 해결하며 함께 사용할 수 있습니다. — PagedAttention과 RadixAttention 비교 표 및 결론

05

vLLM은 Radix tree 대신 chain hashing으로 prefix caching을 구현합니다. 각 KV 블록의 hash를 부모 블록 hash, 현재 블록의 token IDs, 선택적 LoRA ID 또는 multimodal input hash로 만들기 때문에 동일한 토큰 prefix는 같은 hash 연쇄를 생성하며, 새 요청은 첫 번째 hash miss가 발생한 지점부터 새 블록을 할당합니다. SGLang의 RadixAttention이 longest-prefix traversal을 사용하는 반면 vLLM은 순차적인 hash matching을 사용하지만 두 방식 모두 반복 prefix의 prefill을 건너뛰고 모델 출력을 바꾸지 않습니다.

요청 prefix를 hash로 변환해 GPU VRAM의 KV Cache를 조회하고 hit 또는 miss로 분기하는 흐름입니다. — Diagram요청의 prefix에서 hash를 만든 뒤 KV Cache Lookup을 수행하며, hit이면 VRAM에서 tensor를 불러오고 miss이면 처음부터 계산합니다. 이미지에는 hit 비용이 $0.50/M tokens, miss 비용이 $5.00/M tokens로 표시되어 prefix 재사용 여부가 비용 차이로 이어지는 예시를 제공합니다.

근거

vLLM은 radix tree가 아니라 부모 hash, 현재 블록 token IDs, 선택적 메타데이터를 연결한 chain hashing으로 자동 prefix caching을 구현합니다. — vLLM의 prefix caching 구현과 Radix tree 대 chain hashing 비교 절

06

Prefix caching은 성능을 높이지만 여러 사용자가 같은 serving 인프라를 공유할 때 캐시 적중 여부가 타이밍 기반 정보 유출의 단서가 될 수 있습니다. 공격자가 선택한 prefix의 Time to First Token이 비정상적으로 짧은지 관찰하면 다른 사용자가 같은 prefix를 최근 처리했는지 추측할 수 있으므로, serving 엔진은 prompt token만이 아니라 tenant별 salt를 cache identifier 생성에 포함해야 합니다. 장기적으로는 GPU HBM, host RAM, 분산 저장소를 계층화한 KV 캐시와 cache-aware routing을 사용해 자주 쓰는 prefix를 가까운 계층과 동일한 replica에 유지하고, CUDA Virtual Memory Management로 가상 주소와 물리 페이지를 분리하는 방식도 발전 방향으로 제시됩니다.

Prefix cache aware router가 요청을 캐시 상태가 맞는 worker로 분배하는 구조입니다. — Diagram서로 다른 요청이 Prefix Cache Aware Router로 들어오고, 각 worker는 보유한 cached prefixes와 KV cache 비율을 표시합니다. 라우터가 요청의 prefix와 worker의 캐시 locality를 함께 고려하면 같은 대화 요청이 캐시가 없는 GPU로 이동해 발생하는 miss를 줄일 수 있다는 점을 나타냅니다.

KV 캐시 블록을 GPU VRAM, CPU DRAM, NVMe Storage의 계층에 나누어 저장하는 구조입니다. — DiagramGPU VRAM은 자주 접근하는 Hot KV Cache Blocks를 보관하고 CPU DRAM은 Warm 블록, NVMe Storage는 드물게 접근하거나 보관하는 Cold 블록을 담당합니다. 빈도가 낮은 데이터를 아래 계층으로 offload하고 필요할 때 prefetch하는 방식으로 GPU 용량보다 큰 유효 KV 캐시를 구성하는 계층형 KV caching을 나타냅니다.

Cache-Aware Router가 요청 유형에 따라 pre-prefill, prefill, decode 노드와 분산 KV 캐시를 연결하는 아키텍처입니다. — Diagram라우터는 cache hit가 낮은 cold request를 Pre-Prefill Nodes로, hit가 높은 warm request를 Prefill Nodes로, 생성 단계의 요청을 Decode Nodes로 보냅니다. 각 노드는 Distributed KV Cache와 비동기 read, write 및 고속 RDMA로 연결되어 여러 저장소에 분산된 KV 상태를 요청 처리에 활용합니다.

근거

멀티테넌트 환경에서는 tenant별 cache salt를 cache identifier에 포함해 동일한 prompt라도 테넌트 간 KV 캐시 적중을 차단해야 합니다. — Prefix cache side channel과 cache salting을 다룬 보안 절

용어 해설

KV 캐시(KV Cache): — Transformer가 이전 토큰의 Key와 Value 벡터를 저장해 다음 토큰 생성 때 재계산을 피하는 메모리 구조입니다. 시퀀스가 길어질수록 토큰 수에 비례해 커지므로 GPU 메모리 사용량, 동시 처리 요청 수, 지연 시간에 직접 영향을 줍니다.
PagedAttention: — KV 캐시를 요청마다 하나의 연속 메모리 영역에 배치하지 않고 고정 크기 블록으로 나누어 필요할 때 할당하는 방식입니다. 논리 블록과 GPU의 물리 블록을 block table로 연결해 메모리 단편화를 줄이고 동시 처리량을 높입니다.
RadixAttention: — 반복되는 프롬프트 prefix와 이에 대응하는 KV 상태를 radix tree에 저장한 뒤 새 요청에서 가장 긴 일치 prefix를 찾아 재사용하는 방식입니다. 이미 계산한 토큰을 건너뛰고 일치하지 않는 suffix만 처리해 prefill 연산과 Time to First Token을 줄입니다.
Radix Tree: — 토큰 시퀀스의 공통 prefix를 하나의 경로로 공유하는 압축 trie 자료구조입니다. 요청마다 토큰이 달라지는 지점에서만 가지를 만들기 때문에 동일한 시스템 프롬프트나 대화 이력에 연결된 KV 캐시를 중복 저장하지 않고 검색할 수 있습니다.
Prefix Caching: — 여러 요청에 반복되는 프롬프트 앞부분의 KV 상태를 캐시에 보관하고 이후 요청에서 같은 토큰 prefix를 다시 계산하지 않는 기법입니다. 반복 요청의 prefill 비용을 줄이지만 테넌트 간 캐시 공유가 타이밍 정보 유출로 이어질 수 있어 cache salting이 필요합니다.
Cache-Aware Routing: — 분산 LLM serving 환경에서 요청의 캐시 적중 가능성을 고려해 이미 필요한 KV 캐시를 가진 replica로 요청을 보내는 라우팅 방식입니다. 단순한 부하 균등화 대신 cache locality를 반영해 다른 GPU로 요청이 흩어지면서 발생하는 prefix cache miss를 줄입니다.

기술

PagedAttention
RadixAttention
vLLM
SGLang
CUDA Virtual Memory Management (VMM)
FP16
LoRA
RAG

활용 사례

긴 컨텍스트 LLM serving
다중 사용자 챗봇
멀티턴 대화
RAG 파이프라인
Coding assistant
Agent loop
Beam search
Parallel sampling

PagedAttention과 RadixAttention으로 LLM KV 캐시 최적화

TL;DR

섹션별 상세

용어 해설

기술

활용 사례

관련 토론

댓글

관련 기사

vLLM의 핵심 기술인 PagedAttention의 작동 원리와 메모리 효율화 방식

LLM 추론 지연을 Prefill과 Decode로 진단하기

Grouped Query Attention의 작동 원리와 KV cache 최적화

LLM 추론 속도를 200배 높이는 Prompt Caching의 원리

원리 기반 LLM 추론 성능 모델링