We investigate the capabilities of transformer models in relational reasoning tasks. In these tasks, models are trained on a set of strings that encode abstract relationships and then tested out-of-distribution on data containing symbols that did not appear in the training data set. We prove that for any relational reasoning task in a large family of tasks, transformers learn abstract relations and generalize to the test set when trained using gradient descent on sufficiently large amounts of training data. This contrasts with classical fully connected networks, which we show do not learn to reason. Our results inspire modifications to the transformer architecture that add only two trainable parameters per head and that we empirically show improve the efficiency of data learning to reason.
