Sinkformers: Transformers with Doubly Stochastic Attention

Michael E. Sander, Pierre Ablin, Mathieu Blondel, Gabriel Peyré

Introduction

In the standard Transformer architecture, the attention mechanism relies on the SoftMax operator to normalize attention weights. This ensures that the weights for each "query" sum to one, making the attention matrix row-wise stochastic. However, this creates a fundamental asymmetry: while every query must distribute its attention across keys, a specific "key" might be completely ignored by all queries or, conversely, over-attended to.

This lack of balance is a missed opportunity. The authors of "Sinkformers" observe that during the training of standard Transformers, attention matrices naturally tend toward becoming doubly stochastic—where both rows and columns sum to one. By explicitly enforcing this property, Sinkformers provide a stronger theoretical foundation and improved empirical performance.

The Sinkformer Approach

The core innovation of the Sinkformer is the replacement of the SoftMax layer with Sinkhorn’s algorithm. This iterative process alternately normalizes the rows and columns of a matrix, eventually converging to a doubly stochastic state. This follows a "Democratic Principle": unlike SoftMax, which can allow a single interaction to dominate, Sinkhorn normalization ensures all data points are involved in interactions to some degree.

Empirical evidence shows that standard Transformers naturally drift toward double stochasticity, where column sums (coefficients) cluster around 1.0.

Theoretical Foundations

Beyond empirical gains, the Sinkformer offers a clean physical and mathematical interpretation. The authors analyze the model in two theoretical limits:

  1. Infinite Depth (Neural ODEs): Sinkformers can be interpreted as a discretized gradient flow for the Wasserstein metric, a property standard Transformers lack.
  2. Infinite Particles (Mean-field limit): As the number of data points increases, the Sinkformer’s operation converges to the heat equation (diffusion). This provides a physical analogy for how information spreads through the model, connecting the "black box" of attention to well-understood partial differential equations.

Key Results and Performance

The authors evaluated Sinkformers across 3D vision (ModelNet40), NLP (IMDb, IWSLT’14), and computer vision (MNIST).

  • 3D Classification: The "Set Sinkformer" achieved 89.1% accuracy on ModelNet40, outperforming the standard Set Transformer's 87.8%.
  • Translation: On the IWSLT’14 task, Sinkformers achieved a BLEU score of 34.73, slightly higher than the baseline, with negligible computational overhead.
  • Training Stability: Enforcing double stochasticity acts as an informative "prior," helping the model reach a better state faster. As shown in training curves, increasing the number of Sinkhorn iterations generally leads to more stable convergence and lower test error.
Training curves for Sinkformers show that increasing Sinkhorn iterations (from 1 to 21) leads to more stable convergence and lower error/loss across training epochs.

Conclusion and Future Work

Sinkformers demonstrate that enforcing double stochasticity in attention is a simple yet powerful "drop-in" replacement for SoftMax. While the current study primarily focused on encoders due to the challenges of applying Sinkhorn normalization to masked decoders, the results suggest significant potential for scaling this approach. Future research will likely explore the impact of Sinkhorn normalization on massive Large Language Models (LLMs) and further refine the application of these principles to causal architectures.

Summary updated

Abstract

Attention based models such as Transformers involve pairwise interactions between data points, modeled with a learnable attention matrix. Importantly, this attention matrix is normalized with the SoftMax operator, which makes it row-wise stochastic. In this paper, we propose instead to use Sinkhorn's algorithm to make attention matrices doubly stochastic. We call the resulting model a Sinkformer. We show that the row-wise stochastic attention matrices in classical Transformers get close to doubly stochastic matrices as the number of epochs increases, justifying the use of Sinkhorn normalization as an informative prior. On the theoretical side, we show that, unlike the SoftMax operation, this normalization makes it possible to understand the iterations of self-attention modules as a discretized gradient-flow for the Wasserstein metric. We also show in the infinite number of samples limit that, when rescaling both attention matrices and depth, Sinkformers operate a heat diffusion. On the experimental side, we show that Sinkformers enhance model accuracy in vision and natural language processing tasks. In particular, on 3D shapes classification, Sinkformers lead to a significant improvement.
BibTeX
@inproceedings{sander2022sinkformers,
  author = {Michael E. Sander and Pierre Ablin and Mathieu Blondel and Gabriel Peyré},
  title = {{Sinkformers: Transformers with Doubly Stochastic Attention}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=Uk8LvM3TBj},
}
Figure