local-global attention
**Local-Global Attention** is a **hybrid sparse attention pattern that combines efficient sliding window (local) attention with a small number of global attention tokens that attend to and from every position in the sequence** — achieving O(n × (w + g)) complexity instead of O(n²), where w is the local window size and g is the number of global tokens, enabling long-sequence processing while maintaining the ability to capture long-range dependencies through the global tokens that serve as information bottlenecks connecting distant parts of the sequence.
**What Is Local-Global Attention?**
- **Definition**: An attention pattern where most tokens use local sliding window attention (attending only to nearby tokens within window w), but a designated set of "global" tokens attend to ALL positions and are attended to BY all positions — creating information highways that connect the entire sequence.
- **The Problem**: Pure local attention (sliding window) is efficient but blind to long-range dependencies. A token at position 50,000 cannot directly attend to a critical fact at position 100. Information must cascade through hundreds of layers to travel that distance.
- **The Solution**: Insert global attention tokens that see the entire sequence. These tokens aggregate information from the full context, and other tokens can access this global summary, restoring long-range connectivity without full O(n²) attention.
**Types of Global Tokens**
| Type | How Selected | Example | Advantage |
|------|-------------|---------|-----------|
| **Fixed Position** | Pre-determined positions (CLS, first token, every k-th token) | Longformer uses CLS token as global | Simple, no learning required |
| **Task-Specific** | Tokens relevant to the task get global attention | Question tokens in QA attend globally to find answer | Task-optimized information flow |
| **Learned** | Model learns which tokens should be global | Trainable global token selection | Most flexible |
| **Hierarchical** | Aggregate local regions into summary tokens at regular intervals | Every 512th token is global | Balanced coverage |
**Complexity Analysis**
| Pattern | Per-Token Compute | Total for n=100K |
|---------|------------------|-----------------|
| **Full Attention** | Attend to all n tokens | 10B operations |
| **Local Only (w=512)** | Attend to w tokens | 51M operations |
| **Local-Global (w=512, g=128)** | Attend to w + g tokens | 64M operations |
| **Benefit** | | 156× less than full attention |
**Local-Global in Practice**
| Component | Tokens | Attention Pattern | Purpose |
|-----------|--------|------------------|---------|
| **Local tokens** | ~99% of tokens | Attend within window w only | Efficient local context capture |
| **Global tokens** | ~1% of tokens | Attend to/from ALL positions | Long-range information conduit |
| **Local→Global** | Local tokens attend to global tokens | Provides access to global context | "Read" global summaries |
| **Global→Local** | Global tokens attend to all local tokens | Captures full sequence information | "Write" global summaries |
**Models Using Local-Global Attention**
| Model | Local Window | Global Tokens | Total Context | Key Design |
|-------|-------------|--------------|--------------|------------|
| **Longformer** | 256-512 | CLS + task-specific | 16,384 | + dilated windows in upper layers |
| **BigBird** | 256-512 | Fixed set (64-128) | 4,096-8,192 | + random attention connections |
| **LED** | 512-1024 | Encoder CLS | 16,384 | Encoder-decoder variant of Longformer |
| **ETC** | Configurable | Hierarchical global tokens | 8,192+ | Extended Transformer Construction |
**Local-Global Attention is the most practical efficient attention pattern for long documents** — combining the O(n × w) efficiency of sliding window attention with strategically placed global tokens that maintain full-sequence information flow, enabling models like Longformer and BigBird to process documents of 4K-16K+ tokens on standard GPUs while preserving the ability to capture long-range dependencies that pure local attention patterns would miss.