Sinkformers: Transformers with Doubly Stochastic Attention

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

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.

Introduction

The standard Transformer architecture relies on the SoftMax operator to normalize its attention matrices. While this ensures each row sums to one (row-wise stochasticity), it leaves column sums unconstrained. This asymmetry can lead to "attention sinks" where certain keys are disproportionately attended to while others are ignored.

Sinkformers address this by enforcing doubly stochastic attention matrices—where both rows and columns sum to one—using Sinkhorn’s algorithm. This structural change acts as an informative prior, reflecting a natural tendency observed in trained standard Transformers, and provides a rigorous mathematical link to physical processes like heat diffusion.

Theoretical Foundation: Attention as a Prior

A key motivation for Sinkformers is the observation that standard Transformers naturally evolve toward doubly stochasticity during training. As training progresses, the distribution of column sums in the attention matrix tends to flatten toward unity, suggesting that the model naturally seeks a more balanced attention distribution.

Distribution of attention column sums across different training epochs in standard Transformers, showing a natural trend toward double stochasticity.

By enforcing this property structurally, Sinkformers adopt a "democratic" principle where every data point must both give and receive a fixed amount of total attention. Theoretically, this allows self-attention to be viewed as a discretized Wasserstein gradient flow. In the limit of infinite depth and samples, the Sinkformer's operation simplifies to the heat equation, a fundamental model of diffusion in physics.

Methodology

The core innovation is the replacement of the SoftMax operation with Sinkhorn’s algorithm. This iterative process alternately normalizes rows and columns to achieve double stochasticity.

  • Efficiency: In practice, 3 to 5 iterations are sufficient for near-convergence. Because these operations are simple matrix-vector products, they are easily parallelized on GPUs.
  • Implementation: The algorithm is fully differentiable, making it a "drop-in" replacement for SoftMax in existing deep learning frameworks.
  • Invariance: Sinkhorn attention is invariant to adding constants to entire rows or columns of the cost matrix, making the mechanism more robust to certain types of input noise.

Experimental Results

The authors evaluated Sinkformers across 3D vision, NLP, and image classification tasks, finding consistent improvements over standard Transformer baselines.

Performance Gains

  • 3D Vision: On ModelNet40, the Set Sinkformer achieved 89.1% accuracy, significantly outperforming the standard Set Transformer's 87.8%.
  • NLP: For sentiment analysis (IMDb), Sinkformers showed faster convergence and higher final accuracy. In translation (IWSLT'14), they achieved a BLEU score of 34.73.
  • Vision Transformers (ViT): Sinkformers consistently improved performance, particularly when using smaller patch sizes where the attention mechanism handles more tokens.
Training and test performance of Sinkformers with varying numbers of Sinkhorn iterations.

As shown in the training curves, increasing the number of Sinkhorn iterations generally leads to lower test error and loss, validating the benefit of enforcing double stochasticity more strictly. Even a small number of iterations (e.g., 5) provides a noticeable boost over the single-iteration baseline.

Conclusion

Sinkformers provide a simple yet powerful modification to the Transformer architecture. By enforcing doubly stochastic attention, they improve performance across diverse domains while grounding the mechanism in the physics of gradient flows and diffusion. Future work includes extending this approach to decoders with causal masking and exploring more efficient scaling for massive models.

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},
}

Loading related content...

Figure