Attention Sparsity Review

Faster Causal Self Attention

This paper presents an important advancement in making transformer attention mechanisms more efficient for processing long sequences. Here are the key points:

1. Core Innovation: The authors introduce Sparse Causal Flash Attention (SCFA), which extends the existing FlashAttention algorithm to handle irregular/sparse attention patterns while maintaining high computational efficiency.

2. Two Main Applications:

3. Query/Key (QK) dropping: Selectively removing certain query and key pairs

4. Hash-based attention: Using locality-sensitive hashing to group similar queries and keys together

5. Key Results:

6. Achieves 2.0× speedup for sequences of 8,192 tokens
7. Achieves 3.3× speedup for sequences of 16,384 tokens
8. Maintains comparable perplexity to standard attention

9. Outperforms previous approaches like Reformer in both speed and accuracy

10. Main Advantages:

11. No computational complexity overhead compared to regular FlashAttention
12. Supports dynamic sparsity patterns rather than just static ones
13. Achieves exact computation (unlike some previous approaches that approximate)

14. Works particularly well for longer sequences

15. Technical Innovation: The key technical achievement is modifying FlashAttention to handle non-triangular causal masks, which enables more flexible attention patterns while maintaining the memory and computational benefits of the original FlashAttention algorithm.

This work is significant because it helps address one of the main bottlenecks in transformer models - the quadratic computational cost of attention with respect to sequence length - while maintaining exact computation and allowing for dynamic sparsity patterns.

Sparser is Faster: Long-Range Attention with Linear Complexity

Here's a summary of the key points from this paper about SparseK Attention:

Key Innovation: - Introduces SparseK Attention, a novel sparse attention mechanism that offers both computational and memory efficiency for long sequences - Uses a scoring network and differentiable top-k mask operator to dynamically select important key-value pairs for each query

Main Advantages: 1. Efficiency: - Linear time complexity and constant memory footprint - Better speed than previous sparse attention methods - Efficient for both training and inference

1. Performance:
2. Outperforms previous sparse attention approaches
3. Matches or exceeds full attention quality while being faster

4. Can handle sequences up to 16,384 tokens effectively

5. Technical Features:

6. Integrates with sliding window attention
7. Compatible with pre-trained LLMs through fine-tuning
8. Uses an IO-aware implementation based on Flash Attention

Results: - Language modeling tests show better perplexity than baseline methods - Achieves 2.0× speedup for 8k sequences and 3.3× for 16k sequences - Maintains performance while significantly reducing compute and memory requirements

Key Limitation: - Currently validated only up to 1.1B parameter models and 16k token contexts due to computational constraints - Only tested on decoder-only architectures and text tasks - Some overhead for short sequences, though benefits increase with sequence length

The paper demonstrates that SparseK Attention can make transformer models more efficient for long sequences while maintaining or improving quality, offering a practical solution for scaling up context windows in language models.

MoA

This paper introduces MoA (Mixture of Attention), a novel method for compressing large language models (LLMs) by automatically optimizing sparse attention patterns. Here are the key points:

1. Problem & Motivation:
2. LLMs struggle with long contexts due to quadratic memory and computation costs from attention
3. Existing sparse attention methods use uniform patterns across all attention heads, ignoring that different heads serve different purposes

4. Current approaches fail to extend effective context length beyond their attention span

5. Key Innovation - MoA:

6. Automatically discovers heterogeneous sparse attention patterns tailored to each attention head
7. Uses elastic rules that allow attention spans to scale differently with input length

8. Maintains different patterns for different layers and heads based on their functions

9. Technical Approach:

10. Profiles the influence of each attention position on model predictions using gradient-based analysis
11. Constructs a search space of various attention patterns and scaling rules
12. Uses calibration datasets with long-range dependencies

13. Optimizes patterns automatically through a multi-objective framework

14. Key Results:

15. Increases effective context length by 3.9× compared to baseline methods
16. Improves retrieval accuracy by 1.5-7.1× over uniform attention baselines
17. Reduces maximum performance drop from 9-36% to within 5% on benchmarks
18. Achieves 6.6-8.2× throughput improvement over FlashAttention2

19. Reduces GPU memory usage by 1.2-1.4×

20. Limitations:

21. Performance degrades under extremely low-density constraints
22. May benefit from dynamic attention patterns (left for future work)
23. Could explore non-linear elastic rules

The paper demonstrates that automatically discovering heterogeneous attention patterns can significantly improve both the efficiency and capabilities of LLMs in handling long contexts, while maintaining model performance.