Big Bird — 더 긴 시퀀스를 위한 트랜스포머
Digest: BERT류 트랜스포머는 self-attention(모든 토큰 쌍 간 상호작용)의 O(n²) 메모리/연산 때문에 512 토큰 근방에서 막혀 있었고, 긴 문서 QA·요약·유전체 서열처럼 수천~수만 토큰 맥락이 필요한 과제에 부적합했다. Big Bird의 핵심 통찰은 “full attention 그래프를 sparse graph로 대체해도, 적절한 확장자(expander) 성질만 확보되면 정보가 몇 홉 안에 모든 노드로 전파되어 표현력이 보존된다”는 그래프 이론적 관찰이다. 이 통찰을 토대로 (1) Window attention(지역 문맥, BERT의 CNN-유사 귀납 편향), (2) Random attention(무작위 r개 토큰, expander graph 역할로 짧은 경로 보장), (3) Global tokens(CLS 같은 소수 토큰이 모든 토큰과 양방향 연결, 정보 허브 역할) 세 가지 패턴을 block-sparse로 결합해 O(n) 복잡도를 달성한다. 이론적으로는 이 sparse attention이 여전히 universal approximator of sequence functions이며 Turing-complete임을 증명했고(이전 sparse 방법들은 이 보장이 없었음), 실험적으로는 동일 하드웨어에서 8배 긴 시퀀스(4096 tokens) 처리가 가능해 TriviaQA/HotpotQA/Natural Questions에서 SOTA, Arxiv/PubMed 요약에서 Longformer·Pegasus를 상회, 그리고 DNA promoter/chromatin-profile 예측에서도 큰 폭 개선을 보였다(Table 3/6/11 등). 한계로는 (i) random+window sparsity가 GPU에서 효율적이려면 block 단위 구현이 필수여서 실제 속도 이득은 구현 의존적이고, (ii) universal approximation 증명은 O(n) layer가 필요할 수 있어 근사 상수가 실용 상수와 괴리가 있으며, (iii) decoder용 causal 변형은 제한적임이 지적된다. 열린 질문: expander 성질을 더 강하게 부여한 결정론적 패턴이 random보다 우수한가? 더 긴 컨텍스트(100K+)에서 global-token 용량은 어떻게 스케일링해야 하는가? Linformer·Reformer·Performer(커널/LSH/저랭크 근사) 같은 다른 sub-quadratic 계열 대비 Big Bird의 sparsity-graph 접근이 언제 우위인가?
섹션별 요약
Introduction
- 문제 의식: Transformer의 self-attention은 시퀀스 길이 n에 대해 메모리·연산이 O(n²)로, BERT/RoBERTa는 512 토큰 한도에서 학습됨. 이는 긴 문서 QA, 장문 요약, 유전체 서열 분석처럼 장거리 의존성이 본질인 과제를 가로막는 병목.
- 기여:
- Big Bird — global+window+random 세 요소를 결합한 block-sparse attention 제안.
- 이론적 보장: sparse attention이 (i) 시퀀스-투-시퀀스 함수의 universal approximator이며, (ii) Turing-complete임을 증명.
- 실용적 성과: QA/요약/유전체에서 SOTA. DNA promoter region prediction 등 새 응용 개척.
- 관찰: full attention 그래프의 스펙트럼적 성질(expander-like)만 유지하면, 정보가 logarithmic 홉으로 전 토큰에 도달 가능하다는 그래프 이론적 사실이 설계 원리가 됨.
Methods
- Sparse attention 패턴(각 토큰 i가 참여하는 key 집합 A(i)):
- Window (w): |i − j| ≤ w/2인 지역 이웃 (예: w=3 블록).
- Random (r): 각 query마다 무작위로 선택된 r개 key (Erdős–Rényi 랜덤 그래프).
- Global (g): g개의 “global tokens”가 모든 토큰과 양방향 attend. 두 가지 변형:
- ITC (Internal Transformer Construction): 기존 토큰 중 일부(예: CLS)를 global로 승격.
- ETC (Extended Transformer Construction): 별도의 global 토큰을 추가.
- 블록화: GPU/TPU에서 비정형 sparsity는 비효율적. Big Bird는 토큰을 block(보통 64)으로 묶어 모든 sparsity를 block-level에서 계산 → dense matmul로 가속.
- 복잡도: 각 토큰의 attend 수가 O(w + r + g) = O(1) (n과 무관) → 전체 O(n).
- Encoder 중심: 주로 encoder-only(BERT류)에 적용. 요약의 decoder는 full attention 유지(출력 길이는 짧음).
Theory
- Theorem 1 (Universal Approximation): Big Bird 스타일 sparse attention을 가진 Transformer는 임의의 연속 시퀀스-투-시퀀스 함수를 컴팩트 도메인에서 근사 가능. 증명 핵심은 global token이 contextual mapping을 구성할 수 있게 해준다는 점.
- Theorem 2 (Turing Completeness): Big Bird는 Turing-complete. 즉, full attention Transformer의 계산 능력을 보존.
- Theorem 3 (Lower Bound / No Free Lunch): 어떤 희소 어텐션 메커니즘은 full attention이 한 층으로 풀 수 있는 문제를 Ω(n) 층이 필요하게 만들 수 있음 → sparsity가 “공짜”는 아님을 명시.
- Graph-theoretic 관점: attention 그래프가 expander 성질(충분히 연결되고 spectral gap이 큰 그래프)을 가지면, 임의 두 토큰이 O(log n) 홉 안에 도달. Window만으로는 지름이 O(n), Random 간선 r개를 추가하면 expander가 됨 → 이것이 random attention이 “충분한” 이유.
Experiments
- QA (long-document):
- HotpotQA (distractor): Big Bird-ETC base가 Longformer base 상회.
- Natural Questions (long answer): Big Bird-ETC large F1 77.8 (Table 3 류).
- TriviaQA: 당시 SOTA 달성.
- 요약:
- Arxiv/PubMed/BigPatent: ROUGE 1/2/L에서 Pegasus·Longformer 대비 개선 (Table 6).
- 유전체 (Genomics) — 신규 응용:
- Promoter Region Prediction: 정확도 99.9%(제시된 방법 대비 큰 개선, Table 10).
- Chromatin Profile Prediction (919 target tracks): AUC 평균 향상 (Table 11).
- Pretraining: MLM objective로 Wikipedia+Books+CC+Stories에 대해 4096 길이로 사전학습.
Discussion
- 한계:
- Universal approximation 증명의 상수가 크고 layer 수가 O(n)까지 필요할 수 있음 → 실용적 bound와 괴리.
- Random attention은 재현성/디버깅 어려움(매번 다른 그래프). 구현에서는 보통 고정 seed.
- Block-sparse 구현이 필수라 hand-tuned CUDA kernel 의존성.
- Causal/autoregressive 확장은 Routing Transformer·Sparse Transformer 대비 덜 명확.
- 향후: 더 긴 컨텍스트, 다른 modality(단백질/음성), global token 학습 전략, expander 패턴의 결정론적 설계.
Insights
- 주목할 점: sparsity 설계를 “어떻게 뽑을까”가 아니라 “graph property를 어떻게 보존할까”로 프레이밍한 것이 핵심.
- 연결 고리: Longformer의 dilated/window + global과 유사하나, Big Bird는 거기에 random 간선을 추가해 expander 성질을 이론적으로 정당화.
- 시사점: 이후 모든 long-context 연구(Flash Attention, Mamba 등)에 “global + local” 이분법의 표준을 제시.
- 비판적 코멘트: “O(n)“은 점근적일 뿐 block size·random 비율의 상수항이 크다. 실측에서는 full attention 대비 짧은 시퀀스에선 오히려 느림.
Discussion Points
- 논쟁점: Random attention이 실제 성능에 기여하는가, 아니면 window+global만으로 충분한가? 일부 ablation은 random의 기여가 marginal임을 시사.
- 검증 필요 가정: expander 그래프의 이론적 지름 보장이 실제 학습 동역학에서도 효율적 정보 전파로 이어지는가?
- 후속 연구: LongT5, ETC, Performer, Hyena, Mamba — 모두 Big Bird의 “local + global” 스케폴딩을 변주.
메타데이터
| 항목 | 내용 |
|---|---|
| 제목 | Big Bird: Transformers for Longer Sequences |
| 저자 | Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, Amr Ahmed |
| 소속 | Google Research |
| 연도 | 2020 |
| 발표 | NeurIPS 2020 / arXiv:2007.14062 |
| 링크 | arXiv, GitHub |
| 키워드 | sparse attention, long-context, expander graph, universal approximation, Turing completeness |
왜 이 연구를 하는가?
핵심 질문
Transformer의 표현력과 계산 보편성을 잃지 않으면서, self-attention의 O(n²) 복잡도를 O(n)으로 낮추는 sparse pattern을 설계할 수 있는가?
기존 접근법의 한계
| 한계 | 설명 |
|---|---|
| O(n²) 메모리 | BERT류는 512 토큰이 한계, 긴 문서 QA/요약 불가 |
| Truncation/Sliding window 편법 | 장거리 의존성 상실, 일관된 표현 부재 |
| 기존 sparse 방법(Sparse Transformer, Reformer) | 이론적 보장(approximation/Turing completeness) 부재, 주로 경험적 |
| Longformer | window+global만 사용 — random간선의 이론적 이점 부재 |
핵심 통찰
- Attention을 그래프로 보면, full attention은 완전그래프. 완전그래프의 핵심 성질은 “작은 지름”인데, 이는 expander graph로도 달성 가능.
- Window(지역 CNN-유사 귀납편향) + Random(Erdős–Rényi 간선으로 spectral gap 확보) + Global(star graph로 hub) → 세 그래프의 합이 expander → 정보가 O(1) 층 만에 전파.
- 따라서 O(n) 복잡도로도 universal approximator를 유지할 수 있다는 것이 “random이 충분한 이유”의 graph-theoretic 근거.
방법 (Method)
프레임워크 개요
flowchart TB subgraph Input["입력 토큰 시퀀스 (길이 n, 블록 단위)"] T1[Block 1] T2[Block 2] T3[Block 3] Tdots[...] Tn[Block n/b] end subgraph Attention["Big Bird Sparse Attention Pattern"] direction LR W[Window Attention<br/>각 block이 좌우 w개 block attend<br/>→ 지역 문맥] R[Random Attention<br/>각 block이 무작위 r개 block attend<br/>→ expander graph, 단축 경로] G[Global Tokens<br/>g개 token이 모든 block과 양방향 attend<br/>→ 정보 허브] end Input --> Attention W --> Combine[Block-sparse Matmul<br/>GPU/TPU 가속] R --> Combine G --> Combine Combine --> Out[O(n) 복잡도<br/>4096 tokens 처리 가능] Out --> Theory{{"이론 보장:<br/>✓ Universal Approximator<br/>✓ Turing Complete"}}
핵심 구성요소
1) Window Attention (W)
- 각 query block은 좌우
w블록(보통 w=3)에 attend. - 역할: 지역 정보 집계(BERT/CNN-유사 귀납 편향). 언어의 국소성 가정과 일치.
2) Random Attention (R)
- 각 query block은 무작위로 선택된
r개 key block에 attend (학습 중 고정, 논문에선 r=3). - 역할: window-only 그래프의 지름은 O(n/w)이지만, 무작위 간선을 섞으면 expander graph가 되어 지름이 O(log n)으로 줄어듦 → 임의의 두 토큰이 몇 홉 안에 정보 교환 가능.
3) Global Tokens (G)
g개 특수 토큰(예: CLS, 추가 global slot)이 모든 토큰에 attend/attended.- 두 변형:
- ITC: 기존 토큰 일부(CLS)를 global로 사용.
- ETC: 별도 global 토큰을 prepend.
- 역할: 전역 “칠판(blackboard)” — 모든 토큰이 이 허브를 경유하면 2홉만에 통신 가능. Universal approximation 증명에서 contextual mapping의 핵심.
4) Block-sparse 구현
- 토큰을 block size b(보통 64)로 묶음.
- Random/window/global 마스크를 block 단위로 정의 → dense block matmul의 gather/scatter로 구현.
- 복잡도: O(n) (block 단위 GPU kernel 활용).
발견 (Findings)
주요 결과
| 과제 | 데이터셋 | 메트릭 | Big Bird | 비교 베이스라인 |
|---|---|---|---|---|
| Long-doc QA | Natural Questions (long) | F1 | 77.8 (ETC-large) | RoBERTa-large < 73 |
| Long-doc QA | HotpotQA (distractor) | Joint F1 | Big Bird-ETC > Longformer | Longformer base |
| Long-doc QA | TriviaQA (wiki) | EM | SOTA (당시) | RoBERTa, Longformer |
| 요약 | Arxiv | ROUGE-L | 41.8 | Pegasus 38.8, Longformer-LEDbase 36.2 |
| 요약 | PubMed | ROUGE-L | 39.8 | Pegasus 38.3 |
| 요약 | BigPatent | ROUGE-L | 55.7 | Pegasus 52.3 |
| 유전체 | Promoter Pred. | Accuracy | 99.9% | CNNProm < 96% |
| 유전체 | Chromatin Profile | AUC | 개선(평균) | DeepSEA baseline |
| Pretraining | MLM | bpc/PPL | Full-attention과 유사 | — |
※ 수치는 논문 Table 3, 6, 10, 11 기준 근사치.
핵심 발견
- 길이 8배 확장: 동일 16GB GPU에서 512 → 4096 토큰 처리.
- Sparse ≈ Full: MLM 사전학습에서 full attention과 동등한 perplexity → sparsity가 표현력 손실을 거의 일으키지 않음.
- Global token의 중요성: ablation에서 global token 제거 시 성능 급락 — 이론적 보장(approximation)에서도 필수.
- Random의 marginal 기여: window+global만으로도 상당 성능, random 추가는 태스크에 따라 0~1% 이득.
- 도메인 일반성: 텍스트 이외 DNA 서열(8000 bp window)에도 적용 → 긴 시퀀스가 본질인 도메인 전반에 활용 가능.
이론적 의의
Sparse Attention의 Universal Approximation
Big Bird는 기존 sparse attention 연구들이 경험적 성공만 보여준 것과 달리, (global token을 포함한) sparse pattern이 연속 시퀀스-투-시퀀스 함수를 근사할 수 있음을 증명. 증명의 핵심은 global token이 contextual mapping을 구성해 임의 위치 정보를 임의 위치로 라우팅할 수 있다는 것. 이는 sparse attention이 “근사 트레이드오프”가 아니라 “완전한 계산 대체”일 수 있음을 시사.
Expander Graph와 Random Attention의 존재 이유
Window만 있는 attention의 그래프는 지름이 O(n/w)로 선형. 정보가 한쪽 끝에서 반대쪽 끝까지 전파되려면 O(n) 층 필요. 하지만 Erdős–Rényi 랜덤 간선 r개를 각 노드에 추가하면 그래프가 expander가 되어 지름이 O(log n)으로 급감. 이는 Ramanujan graph 이론과 연결되며, “random attention이 왜 필요한가?”에 대한 graph-theoretic 정당화를 제공.
No Free Lunch
Theorem 3은 sparsity가 공짜가 아님을 명시: 특정 문제(예: 모든 토큰 쌍의 함수를 한 층에 계산)는 full attention은 O(1) 층, sparse는 Ω(n) 층이 필요. 이는 sparse 방법이 “실용적 trade-off”임을 인정하는 정직한 경계선.
재현성 및 신뢰도 평가
| 항목 | 등급 | 비고 |
|---|---|---|
| 코드 공개 | ✅ | google-research/bigbird TF 구현 공개, HuggingFace 포팅 존재 |
| 데이터 공개 | ✅ | NQ/HotpotQA/TriviaQA/Arxiv/PubMed 모두 공개 벤치, 유전체 데이터도 공개 |
| 하이퍼파라미터 | ✅ | block size, w/r/g 값, learning rate 명시 |
| 실험 환경 | ⚠️ | TPU 기반, GPU 재현은 block-sparse kernel 차이로 속도 편차 |
| 통계적 신뢰도 | ⚠️ | 단일 run 결과 다수, std/다중 시드 부족 |
| 종합 등급 | B | 코드·데이터는 A급이나 통계적 엄밀성 보통 |
주장별 신뢰도
| # | 주장 | 근거 | 신뢰도 |
|---|---|---|---|
| 1 | Big Bird는 universal approximator이다 | 논문 Theorem 1 증명 (formal proof) | 🟢 |
| 2 | Big Bird는 Turing complete이다 | Theorem 2 증명 | 🟢 |
| 3 | O(n) 복잡도로 8배 긴 시퀀스 처리 가능 | 실측 throughput, 동일 GPU에서 4096 tokens | 🟢 |
| 4 | Random attention이 성능에 유의한 기여 | Ablation 결과는 태스크별 상이, marginal 개선도 존재 | 🟡 |
| 5 | 긴 시퀀스 도메인(DNA)에 일반화 가능 | Promoter/chromatin 실험 1회 결과 | 🟡 |
| 6 | Ω(n) lower bound(Theorem 3) | 증명 존재하나 상수가 실용과 괴리 | 🟡 |
읽기 난이도: ⭐⭐⭐
- 필요 배경: Transformer/BERT 구조, attention 수식, 그래프 이론(spectral graph, expander, Ramanujan graph), universal approximation 이론, block-sparse kernel 개념.
- 증명 섹션(Appendix)은 특히 infeasible hard; 메인 아이디어만 파악해도 응용은 충분.
관련 연구 비교 매트릭스
| 축 | Big Bird | Longformer | Sparse Transformer | Reformer |
|---|---|---|---|---|
| 핵심 접근 | Window + Random + Global 블록 어텐션 | Sliding window + dilated + task-specific global | Strided/Fixed 고정 패턴 (2D factorized) | LSH hashing + reversible layers |
| 복잡도 | O(n) | O(n) | O(n√n) | O(n log n) |
| 이론 보장 | ✅ Universal approx. + Turing complete 증명 | ❌ 경험적 | ❌ 경험적 | ❌ 경험적 (근사 보장만) |
| Randomness | ✅ (r개 random key) | ❌ | ❌ | ✅ (LSH) |
| Global tokens | ✅ (ITC/ETC) | ✅ (task-specific) | ❌ | ❌ |
| 데이터 | NQ, HotpotQA, TriviaQA, Arxiv/PubMed, DNA | WikiHop, TriviaQA, arxiv 요약 | ImageNet, Enwik8, 음악 | enwik8, imagenet64, 번역 |
| 핵심 메트릭 | NQ F1 77.8, ROUGE-L 41.8 (Arxiv) | TriviaQA F1 77.3 | enwik8 1.03 bpc | enwik8 1.05 bpc |
| 최대 시퀀스 | 4096 (text), 8000+ (DNA) | 4096 | 12288 | 64K |
| 확장성 | Block-sparse, 길이에 선형 | 지역+global, 선형 | CUDA 의존 높음 | LSH bucket 효율 의존 |
| 한계 | Random 효과 미미, block size 상수 큼 | Random 없음 → 그래프 직경 이슈 | 이론 보장 없음, 고정 패턴 경직 | 짧은 시퀀스 비효율, autoregressive 전용 |
| 코드 공개 | ✅ | ✅ | ✅ | ✅ |
관련 연구
- Longformer - The Long-Document Transformer — Big Bird 직전 발표된 장문 트랜스포머, window+global은 공유하나 random 없음.
- Sparse Transformer - Generating Long Sequences — 고정 strided sparsity, Big Bird의 이론적 “전신”.
- Reformer - The Efficient Transformer — LSH 기반 대안적 sub-quadratic attention.
- Linformer - Self-Attention with Linear Complexity — 저랭크 투영 기반, Big Bird와 다른 패러다임.
- Performer - Rethinking Attention with Performers — 커널 근사로 O(n), Big Bird의 sparsity와 직교.
- Mamba - Linear-Time Sequence Modeling with Selective State Spaces — 포스트-트랜스포머 선형 시퀀스 모델링.
원자적 인사이트 (Zettelkasten)
💡 Random attention이 “충분한” 이유 — Expander Graph의 지름 축소
출처: BigBird - Transformers for Longer Sequences (Zaheer et al., 2020)
유형: 이론적
Window-only sparse attention의 토큰 그래프는 path graph에 가까워 지름이 O(n/w)이다. 여기에 각 노드마다 **무작위 간선 r개(Erdős–Rényi)**만 추가하면 그래프는 높은 확률로 expander가 되고 지름이 O(log n)으로 급감한다. Transformer의 “정보 전파 깊이”가 곧 필요한 레이어 수이므로, random attention은 소수의 간선으로 전역 연결성을 구매하는 극히 효율적인 수단이다.
핵심 조건/맥락: r이 상수여도 expander 성질은 성립하지만, global token 없이 random만으로는 universal approximation은 보장되지 않는다. r=3 정도면 실용적으로 충분.
연결: Longformer - The Long-Document Transformer (random 없음 → 지름 문제 미해결), Ramanujan Graphs (이론적 배경)
활용 가능성: GNN의 long-range 문제(over-squashing), 대규모 분산 시스템의 gossip 프로토콜, MoE 라우팅 설계에 직접 차용 가능.
💡 Global Token은 “Contextual Mapping의 허브” — Universal Approximation의 핵심
출처: BigBird - Transformers for Longer Sequences (Zaheer et al., 2020)
유형: 이론적
Big Bird가 universal approximator임을 증명할 때 결정적 역할을 하는 것은 random이 아니라 소수 global token이다. Global token은 모든 위치와 양방향으로 연결되어 있어 임의 위치 간 2홉 정보 라우팅이 가능하고, 이 허브 구조가 임의 함수의 contextual mapping 구성을 가능케 한다. 즉, “전역성”은 sparse attention의 이론적 표현력을 결정짓는 요소이다.
핵심 조건/맥락: Global token 수 g는 상수여도 충분(보통 2~6개). 단, g=0이면 universal approximation이 깨진다.
연결: Attention Is All You Need (CLS 토큰의 원형), ETC - Encoding Long and Structured Inputs (global-local 분리 심화)
활용 가능성: 멀티모달 트랜스포머의 modality-level token, MoE의 shared expert, agent 아키텍처의 “working memory” 슬롯 설계.
💡 Sparsity는 공짜가 아니다 — Ω(n) 층 하한의 정직성
출처: BigBird - Transformers for Longer Sequences (Zaheer et al., 2020)
유형: 실패/한계
논문의 Theorem 3은 어떤 sparse attention도 특정 문제(예: 모든 쌍 함수를 1층에 계산)에 대해 Ω(n) 층이 필요함을 증명한다. 이는 “O(n) 복잡도”가 “모든 것에 대해 full attention과 동등”을 의미하지 않음을 명시한다. 실제로 길이 대비 레이어 수가 제한된 상황(고정 L)에서는 sparse 방법이 일부 계산 패턴을 표현할 수 없다.
핵심 조건/맥락: 하한은 worst-case; 자연어/유전체 등 구조화된 도메인에선 몇 층 만에 충분한 경우가 대부분.
연결: Theoretical Limits of Transformers, On the Expressive Power of Self-Attention
활용 가능성: Sparse 방법을 배포할 때 태스크의 상호작용 깊이를 사전에 분석하는 체크리스트로 활용.
💡 Block-Sparse 구현이 “O(n)“의 실용적 실체
출처: BigBird - Transformers for Longer Sequences (Zaheer et al., 2020)
유형: 방법론적
점근적 O(n)은 종이 위 복잡도이고, GPU에서 실현되는 O(n)은 block-size b(보통 64) 단위의 dense matmul로 sparsity를 시뮬레이션해야 한다. 비정형 sparsity(element-wise mask)는 GPU에서 오히려 느리다. 따라서 sparse attention 설계는 항상 “block-aligned”로 해야 실속이 있다 — 이는 이후 Flash-Attention, Triton block-sparse kernel의 설계 원칙으로 이어짐.
핵심 조건/맥락: 매우 긴 시퀀스(n ≫ 2048)에서만 full attention 대비 속도 이득. 짧은 시퀀스에서는 오히려 느림.
연결: FlashAttention - Fast and Memory-Efficient Exact Attention, Triton - Block-Sparse Matmul
활용 가능성: 새로운 attention 패턴을 제안할 때 항상 “block-align 가능한가?”를 먼저 확인.
💡 Long-context의 표준 레시피 — “Local + Global” 이분법
출처: BigBird - Transformers for Longer Sequences (Zaheer et al., 2020)
유형: 연결
Big Bird(와 Longformer)가 정립한 “local window attention + small global tokens”는 이후 LongT5, ETC, GPT-Neo의 local layer, 심지어 Mamba의 local conv + global SSM 혼합에 이르기까지 long-context 모델링의 지배적 스캐폴딩이 되었다. Random 요소는 사라져도 “local은 많이, global은 적게, 하지만 반드시 둘 다”의 구조는 살아남았다.
핵심 조건/맥락: 대부분의 자연 시퀀스(언어/코드/DNA)에서 정보는 지역적으로 조밀하고 일부만 장거리 의존 → 이분법이 자연스러움.
연결: LongT5, ETC, Mamba - Linear-Time Sequence Modeling with Selective State Spaces, Hyena Hierarchy
활용 가능성: 새로운 도메인(비디오, 단백질 구조)에 long-context 모델 설계 시 첫 baseline 선택.
핵심 용어 정리
| 용어 | 정의 |
|---|---|
| Self-attention | 시퀀스의 모든 토큰 쌍에 대해 Q·K 내적으로 가중치를 계산해 V를 가중합하는 연산. 복잡도 O(n²). |
| Sparse attention | Attention 마스크의 일부만 계산하여 O(n²) 미만 복잡도로 근사하는 기법 총칭. |
| Window attention | 각 토큰이 좌우 w개 이웃 토큰에만 attend하는 지역 패턴. |
| Random attention | 각 토큰이 무작위로 선택된 r개 토큰에 attend. Erdős–Rényi 그래프의 간선 역할. |
| Global token | 모든 토큰과 양방향으로 연결되는 특수 토큰. CLS의 일반화. |
| Expander graph | Sparse하지만 spectral gap이 커서 지름이 작은(≈log n) 그래프. Random regular graph의 전형적 성질. |
| Block-sparse | Attention 마스크를 토큰 단위가 아닌 block(예: 64 tokens) 단위로 정의해 GPU matmul로 가속. |
| Universal approximator | 임의의 연속 함수를 임의 정밀도로 근사할 수 있는 함수족. 여기선 sequence-to-sequence 함수 부류. |
| Turing completeness | 임의의 Turing machine 계산을 시뮬레이션 가능한 계산 모델의 성질. |
| Contextual mapping | 각 토큰이 자신의 맥락에 따라 유일한 표현을 갖도록 하는 매핑. UA 증명의 핵심 lemma. |
| ITC / ETC | Internal / Extended Transformer Construction — 기존 토큰을 global로 쓰는지 별도 global 토큰을 두는지의 차이. |
| Erdős–Rényi 랜덤 그래프 | 각 간선을 독립적으로 확률 p로 포함시키는 랜덤 그래프 모델. |
태그
paper #2020 attention bigbird sparse random block long-context transformer graph-theory