BigBird buduje rzadką macierz attention z trzech komponentów: (1) Window attention — każdy token attentuje na W sąsiadów (jak SWA, w pracy W=3, czyli ±1), (2) Random attention — każdy token attentuje dodatkowo na R losowo wybranych keys (w pracy R=2–3), z perspektywy teorii grafów to dodanie losowych krawędzi do grafu attention, co radykalnie skraca średnią odległość między dowolnymi dwoma tokenami, (3) Global attention — g wybranych tokenów attentuje na wszystkich i wszyscy attentują na nich (g zwykle 2–8, np. [CLS] + tokeny pytania w QA). Łącznie każda warstwa wykonuje O((W+R)·T + g·T) ≈ O(T) operacji. Implementacyjnie BigBird reorganizuje sekwencję w bloki — random attention jest sparsy w obrębie pre-permutowanych bloków, by zachować efektywność na GPU. Autorzy publikują dwa warianty: ETC (Extended Transformer Construction) — bez random attention, tylko window + global; oraz pełny BigBird ITC (Internal Transformer Construction) z całą trójką. Random attention jest kluczowy dla teoretycznych dowodów.
Wcześniejsze sparse attention (Longformer/SWA, Sparse Transformer) działały empirycznie, ale brakowało im teoretycznych gwarancji ekspresywności — nie było jasne, czy ograniczenie attention do okna i kilku tokenów globalnych nie odbiera modelowi fundamentalnych zdolności. BigBird formalizuje problem: dowodzi (1) że SWA + global + random jest uniwersalnym aproksymatorem funkcji sekwencji, (2) że jest Turing-zupełny i (3) że okno musi mieć dolne ograniczenie liczby tokenów globalnych O(√T) by te własności zachować. Praktycznie: pozwala bezpiecznie skalować Transformer do sekwencji 4096–8192 tokenów (8×–16× ponad BERT) bez utraty jakości.
Każdy token attentuje na W najbliższych sąsiadów. Mechanizm zaczerpnięty bezpośrednio z SWA/Longformer — odpowiada za zachowanie lokalnej spójności.
Oficjalna
Każdy token attentuje na R losowo wybranych pozycji (z ustalonym ziarnem). Z perspektywy teorii grafów dodaje losowe krawędzie do grafu attention, dzięki czemu średnia odległość między dowolnymi dwoma tokenami spada do O(log T) — kluczowe dla dowodu uniwersalności.
g wybranych tokenów attentuje na całą sekwencję i jest widziane przez wszystkie pozostałe tokeny. Praktycznie [CLS], [SEP] i/lub tokeny pytania w QA. Dolne ograniczenie teoretyczne: g = Ω(√T).
Oficjalna
Bez komponentu random BigBird redukuje się do Longformera (SWA + global) i traci formalne gwarancje uniwersalności. ETC jest świadomym kompromisem; przypadkowe pominięcie psuje semantykę.
Praca formalnie wymaga g = Ω(√T) global tokens, by zachować ekspresywność. Dla T=8192 to ~90 tokenów. Stosowanie tylko g=2 ([CLS]+[SEP]) na bardzo długich sekwencjach degraduje jakość poniżej teoretycznych przewidywań.
Dosłowny random scatter-gather po sekwencji jest dla GPU katastrofalny (random access). Wymaga blokowej permutacji.
Pierwsza szeroko cytowana praca o deterministycznej sparsyfikacji attention (lokalne + strided). Empiryczne wyniki, brak teoretycznych dowodów ekspresywności.
Beltagy, Peters, Cohan (AI2) wprowadzają SWA + global attention. Pokazują empirycznie, że taka kombinacja działa dla encoderów long-document, ale teorii brak.
Zaheer i in. (Google) publikują BigBird na NeurIPS 2020. Wprowadzają trzeci komponent (random attention) i — kluczowo — DOWODZĄ, że SWA + global + random zachowuje uniwersalność aproksymacji i Turing-zupełność standardowego Transformera. To pierwsze teoretyczne uzasadnienie sparse attention.
Google publikuje na Hugging Face wytrenowane modele BigBird (oparte na RoBERTa i Pegasus) dla zadań QA i summarization. Wsparcie w bibliotece Transformers.
Nowsze duże LLM (Mistral, Mixtral, Gemma) wybierają sam SWA bez random attention — random okazuje się trudniejszy do efektywnej implementacji na GPU i empirycznie L·W (głębokość × okno) jest wystarczające. BigBird pozostaje ważnym teoretycznym punktem odniesienia.
Złożoność czasowa: O((W + R) · T · d + g · T · d) ≈ O(T · d) per warstwa. Złożoność przestrzenna: O(T · (W + R + g) · d) aktywacji + O(T · d) KV cache.
Realny bottleneck BigBird to wzorzec dostępu do pamięci w random attention — bez blokowej permutacji byłby katastrofalny na GPU. Z permutacją jest akceptowalny, ale wciąż wolniejszy niż pure SWA. To główny powód, dla którego nowsze LLM (Mistral, Gemma) wybierają sam SWA.
Liczba lokalnych sąsiadów per token. W oryginalnej pracy bardzo małe (W=3, czyli ±1) — wzór BigBird zakłada, że ekspresywność uzyskuje się głównie z random+global, nie z dużego okna.
Liczba losowych keys, na które attentuje każdy token. Mały, ale niezerowy — kluczowy dla teoretycznych dowodów. Praca używa R=2–3.
Liczba tokenów z pełnym attention. Dolne ograniczenie teoretyczne to O(√T). W praktyce typowo 2–32 specjalnych tokenów (np. [CLS], tokeny pytania).
ETC: window + global, bez random — łatwiejszy implementacyjnie, używany na encoder QA. ITC: pełny window + random + global — wariant z mocnymi gwarancjami teoretycznymi.
Implementacyjny parametr: random attention jest realizowane na poziomie bloków (nie pojedynczych tokenów), aby zachować ciągły dostęp do pamięci. Praca używa rozmiaru bloku 64.
Tokeny globalne są w trybie „dense" (attention na całą sekwencję), reszta tokenów w trybie „sparse" — to wariant mieszany.
Brak uczonego routingu. Window i global są deterministyczne, random jest losowy (z ustalonym ziarnem) ale nieuczony.
Wszystkie trzy strumienie (window, random, global) są równoległe w obrębie warstwy. Random attention jest realizowane przez blokową permutację sekwencji, aby zachować dostęp do pamięci sekwencyjny (efektywny na GPU).
Random attention wymaga starannej blokowej implementacji, by uniknąć random access do VRAM. Z blokami 64×64 BigBird osiąga dobre wykorzystanie tensor cores, choć gorsze niż dense lub samo SWA.
Oryginalna implementacja Google była zoptymalizowana pod TPU — blokowy random attention bardzo dobrze mapuje się na strukturę TPU systolic array.
Sam algorytm działa wszędzie, ale realna efektywność wymaga blokowych kerneli — na CPU/AVX BigBird jest wolniejszy niż pełne attention dla T<2048.
