SAMSA: Efficient Transformer for Many Data Modalities

Minh Lenhat, Viet‐Anh Nguyen, Khoa Dang Nguyen, Duong Duc Hieu, Dao Huu Hung, Truong Son Hy

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

Abstract

The versatility of self-attention mechanism earned transformers great success in almost all data modalities, with limitations on the quadratic complexity and difficulty of training. Efficient transformers, on the other hand, often rely on clever data-modality-dependent construction to get over the quadratic complexity of transformers. This greatly hinders their applications on different data modalities, which is one of the pillars of contemporary foundational modeling. In this paper, we lay the groundwork for efficient foundational modeling by proposing SAMSA - SAMpling-Self-Attention, a context-aware linear complexity self-attention mechanism that works well on multiple data modalities. Our mechanism is based on a differentiable sampling without replacement method we discovered. This enables the self-attention module to attend to the most important token set, where the importance is defined by data. Moreover, as differentiability is not needed in inference, the sparse formulation of our method costs little time overhead, further lowering computational costs. In short, SAMSA achieved competitive or even SOTA results on many benchmarks, while being faster in inference, compared to other very specialized models. Against full self-attention, real inference time significantly decreases while performance ranges from negligible degradation to outperformance. We release our source code in the repository: https://github.com/HySonLab/SAMSA
BibTeX
@misc{lenhat2024samsa,
  author = {Minh Lenhat and Viet‐Anh Nguyen and Khoa Dang Nguyen and Duong Duc Hieu and Dao Huu Hung and Truong Son Hy},
  title = {{SAMSA: Efficient Transformer for Many Data Modalities}},
  year = {2024},
  eprint = {2408.05391},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.05391},
}
Figure