Wnioskowanie

PagedAttention

2023AktywnyOpublikowano: 29 maja 2026Aktualizacja: 29 maja 2026Opublikowany

Algorytm zarządzania KV cache wzorowany na pamięci wirtualnej OS: cache podzielony na stałe bloki alokowane on-demand. Eliminuje fragmentację i umożliwia continuous batching w serwowaniu LLM.

Kluczowa innowacja

Stronicowanie KV cache wzorowane na pamięci wirtualnej systemu operacyjnego — eliminuje fragmentację pamięci w serwowaniu LLM, umożliwia continuous batching i sharing cache między requestami, dając 2-4× wyższy throughput.

Kategoria

Wnioskowanie

Poziom abstrakcji

Wzorzec

Poziom operacji

InferencjaUdostępnianie

Zastosowania

Produkcyjne serwowanie LLM (vLLM jest dominującym serwerem inferencji open-source)Continuous batching dla wysokiej concurrencyParallel sampling (n>1 odpowiedzi per prompt) — sharing prefix cacheBeam search inferencePrompt caching między requestami z wspólnym system promptemMulti-tenant LLM serving z różnymi długościami kontekstu

Jak działa

KV cache jest podzielony na fizyczne bloki w HBM (typowo 16 tokenów per blok per warstwa). Każda sekwencja w batchu posiada logiczną listę bloków (block table) mapującą indeks logicznego bloku na fizyczny adres w HBM. Bloki są alokowane on-demand w miarę wzrostu sekwencji — brak preallokacji max_context. Custom CUDA kernel attention obsługuje non-contiguous cache, czytając bloki przez block table. Sharing prefixów realizowany przez reference counting na blokach: gdy dwie sekwencje mają wspólny prefix, dzielą fizyczne bloki tego prefixu. Modyfikacja (zapis do współdzielonego bloku) wyzwala copy-on-write. Continuous batching dynamicznie dodaje/usuwa sekwencje z batcha bez restartu, jako że alokacja per-blok eliminuje konieczność rezerwowania ciągłego obszaru.

Rozwiązany problem

Tradycyjne serwowanie LLM alokuje KV cache jako ciągły blok per request o rozmiarze max_context, co prowadzi do 60-80% marnotrawstwa pamięci HBM przez fragmentację — drastycznie ogranicza throughput i maksymalny batch size.

Komponenty

Block table

Per-sekwencja mapowanie logicznych indeksów bloków na fizyczne adresy w HBM — analog page table w OS.

Block manager

Komponent alokujący/zwalniający fizyczne bloki KV cache w HBM, utrzymujący wolną pulę bloków.

Custom paged attention CUDA kernel

Wyspecjalizowany kernel attention obsługujący non-contiguous KV cache poprzez indirection przez block table.

Reference counting + copy-on-write

Mechanizm sharing bloków prefixu między sekwencjami z lazy duplication przy modyfikacji.

Implementacja

Implementacje referencyjne

vLLM

Python / CUDA · vLLM Project (UC Berkeley / community)

Oficjalna

NVIDIA TensorRT-LLM (PagedKVCache)

C++ / CUDA / Python · NVIDIA

Oficjalna

SGLang

Python / CUDA · SGLang team (UC Berkeley / Stanford)

LMDeploy

Python / CUDA · InternLM

Pułapki implementacyjne

Wymagany custom CUDA kernelŚrednia

Standard attention kernels (FlashAttention, cuDNN) zakładają contiguous KV cache. PagedAttention wymaga dedykowanego kernela z indirection przez block table.

Rozwiązanie:Użyj gotowych implementacji (vLLM, TensorRT-LLM, SGLang) zamiast pisania własnego kernela.

Block size jako kompromisNiska

Mały block size = mniej marnotrawstwa, ale więcej overhead block table i mniej regularny dostęp do pamięci. Duży block size = większe marnotrawstwo dla krótkich sekwencji.

Rozwiązanie:Domyślne 16 tokenów jest dobre dla większości workloadów; benchmarkuj przy specyficznych długościach.

Złożoność systemowaNiska

Block manager, reference counting, copy-on-write to znaczna złożoność systemowa — debugowanie problemów pamięci jest trudniejsze niż w prostszych serwerach.

Rozwiązanie:Polegaj na dojrzałych implementacjach (vLLM ma najszerszą bazę użytkowników i bugfixów).

Ewolucja

Oryginalny paper · 2023 · SOSP 2023 · Woosuk Kwon

Efficient Memory Management for Large Language Model Serving with PagedAttention

Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion Stoica

2023

vLLM open-source release (czerwiec 2023)

Zespół UC Berkeley uwalnia vLLM jako open-source jeszcze przed publikacją papieru — natychmiastowa adopcja w społeczności.

2023

Publikacja w SOSP 2023 (Kwon et al.)

Punkt przełomowy

Formalna publikacja PagedAttention na flagowej konferencji systemowej. 2-4× throughput vs konkurencja, near-zero memory waste.

Efficient Memory Management for Large Language Model Serving with PagedAttention (artykuł)

2024

Standard de facto serwowania LLM

vLLM staje się najpopularniejszym serwerem inferencji open-source. PagedAttention adoptowane przez TensorRT-LLM, SGLang, LMDeploy.

2024

Automatic Prefix Caching w vLLM

Rozszerzenie PagedAttention o automatyczne wykrywanie i sharing prefixów między requestami bez konieczności jawnego zaznaczania.

Złożoność obliczeniowa

Wąskie gardło obliczeniowe

HBM bandwidth (zachowane vs standard KV cache)

PagedAttention eliminuje fragmentację bez wprowadzania znaczącego narzutu obliczeniowego. Indirection przez block table dodaje minimalny overhead (~1-2%) skompensowany przez wyższy throughput z batchowania.