On the Expressive Power of Transformers for Contextual Relations

Abstract:Transformers have revolutionized machine learning by making attention a central mechanism for modeling interactions within a context. Despite the central role of attention, the theoretical capabilities of Transformers for representing contextual relations remain unclear. In this work, we address this question by developing a mathematical framework based on probability and optimal transport. We view a text as a distribution of its representations and attention as a probabilistic relation between them. This perspective reveals a connection between attention normalization and optimal transport: standard softmax normalization produces conditional relations, while Sinkhorn normalization produces joint relations with prescribed marginals. Thus, both mechanisms provide structured probabilistic relations from attention scores. Under mild conditions, we establish universal approximation results for both settings. We show that Transformer architectures with Sinkhorn normalization can approximate arbitrary contextual relations represented as joint probabilities, while standard softmax Transformers can approximate arbitrary contextual relations represented as conditional probabilities. These results provide a mathematical characterization of the expressive power of Transformers for contextual relations and show how the choice of normalization determines the probabilistic structure of the relations represented by attention.

Machine Learning (stat.ML); Machine Learning (cs.LG)

arXiv:2603.25860 [stat.ML]

(or arXiv:2603.25860v4 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2603.25860 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.