TL;DR
SAMSA (SAMpling-Self-Attention) introduces a novel, differentiable sampling-without-replacement mechanism that slashes the quadratic complexity of Transformers to linear. Unlike previous "efficient" models that rely on data-specific hacks, SAMSA is truly modality-agnostic, delivering state-of-the-art performance across text, graphs, and point clouds while being significantly faster during inference.
What Problem Does This Paper Address?
The "Standard" Transformer is a victim of its own success. Its core strength—the self-attention mechanism—allows every token to look at every other token. However, this comes with a "quadratic tax": as the number of tokens ($n$) grows, the computational cost grows by $n^2$.
To fix this, researchers have proposed "efficient" Transformers, but these usually come with a catch. They often rely on inductive biases specific to one type of data. For example, "sliding window" attention works great for text (where nearby words are usually most relevant) but fails miserably on non-rigid structures like 3D point clouds or complex graphs. This lack of versatility hinders the development of true "foundational models" that can handle any data type.
Methods
The authors propose SAMSA, which stands for SAMpling-Self-Attention. The core idea is simple: instead of attending to all tokens, why not just attend to the most important ones?
The challenge is making that "choice" differentiable so the model can learn which tokens matter during training. SAMSA introduces several key innovations:
- Differentiable Sampling without Replacement: The authors developed a parallelizable method using a "Gumbel-Sigmoid" trick. This allows the model to pick a subset of $k$ tokens and pass gradients through that discrete choice.
- Mixture of Attention Experts: Inspired by Mixture-of-Experts (MoE), each attention head in SAMSA can choose a different subset of tokens. This effectively broadens the model's "receptive field" without increasing the cost per head.
- Graph-Bridge: To handle graphs, they treat both nodes and edges as tokens and use a unique subtraction-based positional encoding to preserve the directionality of edges.
- Learnable Support Vector Paddings: This ensures the model remains stable even when the input sequence is shorter than the requested sample size $k$.
Datasets
The authors tested SAMSA across three distinct modalities to prove its versatility:
- Sequence (Text/Images): The Long Range Arena (LRA) benchmark, including tasks like ListOPS, Text classification, and Image recognition.
- Graphs: The Long Range Graph Benchmark (LRGB), specifically the Peptides-func and Peptides-struct datasets.
- Point Clouds: ModelNet40 (for 3D object classification) and ShapeNetPart (for part segmentation).
Key Insights and Ideas
- The "Sampling Nonlinearity": Interestingly, SAMSA often outperforms full self-attention. The authors suggest that sampling acts as a form of regularization (similar to Dropout), preventing the model from over-focusing on redundant or noisy tokens early in training.
- Hard vs. Soft Sampling: During training, "soft" sampling (using gradients) is used. During inference, the model can switch to "hard" sampling, which is computationally "free" and significantly boosts speed without a major performance hit.
- Breaking the Modality Barrier: By treating everything (nodes, edges, pixels, words) as tokens and letting the data define importance, SAMSA avoids the need for specialized architectures for different fields.
Key Results
- Efficiency: SAMSA achieves linear complexity $O(n)$. For a sequence of 1024 tokens, it is up to 2.17x faster in inference than standard Flash Attention v2.
- Graph SOTA: On the Peptides-func graph benchmark, SAMSA achieved a score of 0.7221, outperforming highly specialized graph models like GraphGPS and Graph ViT.
- Point Cloud Speedup: In 3D point cloud tasks, SAMSA was over 18x faster than PointNet while maintaining competitive accuracy.
- LRA Performance: It outperformed the vanilla Transformer on 4 out of 5 LRA tasks, proving that "less is more" when the "less" is chosen intelligently.
Limitations and Future Work
The primary limitation identified is the gradient misalignment in the "hard" sampling formulation. In very complex reasoning tasks (like the LRA "Pathfinder" task), the gap between the training approximation and the inference reality can lead to volatile learning curves.
The authors suggest that future work should focus on more precise gradient estimation for the "non-chosen" paths to help the model converge more reliably on these difficult edge cases. They also aim to scale SAMSA to even larger foundational models to see if the efficiency gains hold at the multi-billion parameter scale.
Summary updated