Sparse Transformer dzieli attention na DWIE FAKTORYZOWANE głowy działające równolegle: (1) Local attention — każdy token i attentuje na L poprzednich tokenów (gdzie L=√T), (2) Strided/Fixed attention — drugi wzorzec zapewniający, że co najmniej jedna pozycja w każdym „kawałku" kontekstu jest widoczna. Strided variant: token i attentuje też na pozycje i-L, i-2L, i-3L, … (co L-ty token wstecz). Fixed variant: w obrębie sekwencji wybrane są pozycje „streszczające" (jeden token na każde L pozycji), które attentują na całe poprzednie L i są widoczne dla wszystkich kolejnych — odpowiednik global tokens w Longformer/BigBird. Kluczowe twierdzenie: po jednej warstwie token i komunikuje się z O(L)=O(√T) pozycjami. Po DWÓCH warstwach — z całą sekwencją (każde dwa tokeny mają wspólnego sąsiada w grafie attention). To zapewnia, że dwuwarstwowa kompozycja sparse jest funkcjonalnie równoważna jednej warstwie dense, ale przy koszcie O(T·√T) zamiast O(T²). Praktycznie modele OpenAI miały 128 warstw, co dawało ogromny zapas głębokości na propagację.
Standardowe self-attention skaluje się jako O(T²·d) — dla T=12 288 (typowa rozdzielczość obrazów CIFAR-10 64×64 jako sekwencja pikseli) macierz attention zajmuje ~600 MB na warstwę. Praktyczny limit dla 16GB GPU ery 2019 wynosił ~3000 tokenów. Sparse Transformer rozwiązuje to przez deterministyczne sparse wzorce: zamiast pełnej macierzy [T, T], każda głowa wylicza tylko [T, √T]. Dzięki temu OpenAI mogło wytrenować modele autoregresywne dla obrazów, raw audio (Wavenet-skala) i muzyki MIDI — co wcześniej było niemożliwe z dense attention.
Pierwsza z dwóch faktoryzowanych głów. Każdy token attentuje na L poprzednich pozycji (kauzalnie). Odpowiada za precyzję lokalną.
Oficjalna
Druga faktoryzowana głowa. Wariant strided: token attentuje na pozycje i-L, i-2L, … co zapewnia globalną komunikację. Wariant fixed: wybrane tokeny streszczające co L pozycji są widoczne dla wszystkich kolejnych. Bez tej głowy propagacja globalna wymaga O(T/L) warstw.
Oficjalna
Implementacyjny komponent kluczowy dla efektywności. Operuje na blokach o stałym rozmiarze (typowo 32×32 lub 64×64), nigdy nie materializując pełnej macierzy [T, T]. Bez niego sparse pattern nie daje realnej oszczędności.
Oficjalna
Realizacja sparse pattern przez maskowanie pełnej macierzy [T, T] zachowuje koszt O(T²) — niweluje cały sens metody. Sparse Transformer wymaga kernela operującego natywnie na blokach.
Optymalność O(T·√T) zachodzi tylko dla L ≈ √T. Zbyt małe L = za wiele warstw potrzebne do propagacji globalnej. Zbyt duże L = utrata oszczędności kosztu względem dense.
Strided świetnie pasuje do danych periodycznych (obrazy, audio), fixed do nieperiodycznych (tekst). Użycie strided dla tekstu daje gorsze wyniki niż prosta dense baseline dla krótkich kontekstów.
Oryginalny Transformer z O(T²·d) attention. Praktyczny limit długości sekwencji rzędu 512–1024 tokenów na sprzęcie 2017–2018. Punkt wyjścia dla wszystkich sparse alternatyw.
Dai et al. (CMU/Google) wprowadzają rekurencję między segmentami — alternatywne podejście do long-context bez modyfikacji samej macierzy attention. Równoległa praca dla Sparse Transformer (publikacje w odstępie kilku miesięcy).
Child, Gray, Radford, Sutskever publikują Sparse Transformer (arXiv:1904.10509). Pierwsza praktyczna autoregresywna architektura z deterministycznym sparse attention. Wprowadza faktoryzację głów, custom CUDA block-sparse kernel i 128-warstwowe modele. Trenuje na obrazach, audio i tekście do T=12 288.
OpenAI w GPT-3 (175B) używa naprzemiennych warstw dense i sparse (wariant Sparse Transformer) — pierwsze wdrożenie sparse attention w wielkim językowym modelu produkcyjnym.
Bezpośrednia spadkobierczyni Sparse Transformer dla encoderów. Upraszcza wzorzec do okna lokalnego + global tokens, rezygnując ze strided.
Google publikuje BigBird, który łączy SWA + global + random i dowodzi formalnie uniwersalności takiej kombinacji. Zamyka teoretyczną lukę pozostawioną przez empiryczne Sparse Transformer.
Mistral AI wypuszcza Mistral 7B z kauzalnym SWA. Kontynuacja linii Sparse Transformer → Longformer → SWA, ale w nowoczesnym dużym LLM. Sparse Transformer pozostaje historycznym punktem odniesienia.
Złożoność czasowa: O(T · √T · d) per warstwa (zamiast O(T² · d) dense). Złożoność przestrzenna: O(T · √T · d) aktywacji + O(T · d) KV.
Bez efektywnego block-sparse kernela cała oszczędność O(T·√T) jest tracona. To największe ograniczenie historyczne — wymagało custom CUDA, co długi czas było barierą wdrożeniową.
Rozmiar lokalnego okna i odstępu strided. Optymalnie L ≈ √T, by koszt każdej głowy wynosił O(T·√T). Dla T=12 288 daje L≈128.
Strided: równomierne odstępy co L pozycji — działa dobrze dla danych z silną strukturą periodyczną (obrazy, audio). Fixed: tokeny streszczające co L pozycji — działa lepiej dla danych nieperiodycznych (tekst).
Sposób rozdzielenia dwóch wzorców między głowy MHA. Praca testuje warianty: (a) wszystkie głowy mają oba wzorce sekwencyjnie, (b) połowa głów local, połowa strided, (c) interleaved per warstwa.
Praca wprowadza zoptymalizowany gradient checkpointing dla długich sekwencji — pozwala trenować 128-warstwowe modele na sekwencjach 12 288 tokenów na jednym V100.
OpenAI w pracy publikuje też custom CUDA kernel („block-sparse attention") dla efektywnego wykonania na GPU — operuje na blokach o stałym rozmiarze.
Brak uczonego routingu — sparsity jest deterministyczna (geometryczne wzorce strided/fixed).
Obie głowy faktoryzowane (local i strided/fixed) są równoległe. Wzorce sparse są deterministyczne i statycznie znane, więc można je precompute'ować przed treningiem.
Sparse Transformer został zaprojektowany razem z custom block-sparse CUDA kernel'em pod V100. Blokowa natura wzorca dobrze mapuje się na tensor cores.
Bez block-sparse kernela metoda jest wolniejsza niż dense dla T<2048. Realna korzyść wymaga dedykowanej implementacji niskopoziomowej.
