Linear algebra with transformers
Authors: Francois Charton
Venue: Accepted by TMLR ()

Abstract: Transformers can learn to perform numerical computations from examples only. I study nine problems of linear algebra, from basic matrix operations to eigenvalue decomposition and inversion, and introduce and discuss four encoding schemes to represent real numbers. 
On all problems, transformers trained on sets of random matrices achieve high accuracies (over 90\%). The models are robust to noise, and can generalize out of their training distribution. In particular, models trained to predict Laplace-distributed eigenvalues generalize to different classes of matrices: Wigner matrices or matrices with positive eigenvalues. The reverse is not true. 


Published in Transactions on Machine Learning Research (10/2022)
Linear algebra with transformers
François Charton Meta AI
fcharton@meta,co com
Reviewed OpenReview:
Abstract
Transformers can learn to perform numerical computations from examples only. I study nine problems of linear algebra, from basic matrix operations to eigenvalue decomposition and inversion, and introduce and discuss four encoding schemes to represent real numbers. On all problems, transformers trained on sets of random matrices achieve high accuracies (over 90%). The models robust to noise, and can generalize out of their training distribution. In particular, models trained to predict Laplace-distriutted eigenvalues generalize to different classes of matrices: Wigner matricos or matrices with positive cigenvalues. The reverse is not true.
1 Introduction
Since their introduction for machine translation by Vaswani al. 2017 transformers were applied to a wide range of problems, from text generation (Radford et al., 2018 2019 to image processing (Carion et al. 2020 and speech recognition (Dong et al.
2018). where they now achieve state-of-the-art performance (Dosovitskiy
ct al.
2021 Wang et al. 2020b). Transformers have also been proposed for problems of symbolic mathematics,
like integration (Lample & Charton 2019 theorem proving (Polu & Sutskever 2020), formal logic (Hahn)
et al.
2021), SAT solving (Shi et al.
2021 symbolic regression (Biggio et al. 2021] and dynamical systems
Charton (2020). In these works, transformers perform symbolic computations, i.c. manipulate abstract
mathematical symbols.
Beyond symbol manipulation, mathematics also involve numerical calculations (c.g. arithmetic, numerical solutions of equations). On these lasks, experiments with transformers and other sequence models have been disappointing. Basic arithmetic operations, like multiplication or modulus, prove very difficult to learn (Kaiser & Sutskever] 2015 Palamas 2017), and models struggle with gencralization out of their training distribution (Nouueira el al. 2021). could even be shown (Shalev-Shwartz el al. 2017) that some arithmetic tasks camnot be solved using gradient descent. Such results might severely restrict the applicability of transformers science. Most practical problems of mathematics mix symbolic and numerical computations. If transformers "cannot compute", their use in science is very limited.
In this paper, I investigate the capability of transformers to learn to perform numerical computations with high accuracy. 1 focus on nine problems of linear algebra, from basic operations on dense matrices to inversion, eigen and singular value decomposition. show that small transformers can be trained, from examples only, to compute approximate solutions (up to few percents of the T.1 norm) with more than 90% accuracy (over 99% in most cases). I propose and discuss four encodings to represent real numbers, and train small sequence to sequence transformers (up to 6 layers, 10 to 50 million trainable parameters) from generated datasets of random matrices. investigate different architectures, in particular asymmetric configurations where the encoder or decoder has only one layer. Finally, I show that the models are robust to noisy data, and that they can generalize out of their training distribution if special attention is paid to training data generation.
Caveat. This paper does not advocate replacing existing linear algebra algorithms with transformer based implementations. Numerical packages are faster, more accurate, and scale better. My motivation is twofold: better understand the capabilities and limitations of transformers in mathematics, and investigate their potential use tools for the emerging field of AT for science.

---

Published in Transactions on Machine Learning Research (10/2022)
In applications to mathematics, while previous research has shown that transformers struggle with basic arithmetic, I demonstrate that they can learn complex computations, like eigenvalue decompasition. T also show that leveraging the theory of random matrices can help understand the mechanisms of out-of-domain generalization, a known limitation of transformers in mathematics (Welleck et al. 2021 and a difficult problem because of the lack metrics over problem space.
Beyond mathematics, transformers are fast becoming the "default model" for many deep learning applications. Their potential use end to end tools for AI for Science has received lot of attention recently. I believe that demonstrating that transformers handle some of the computational building blocks of many scientific problems, like the problems of linear algebra discussed here, is pre-requisite to their wider generalization.
The source code for the model and experiments is available al gttab.cco//accbbokreeara/////
2 Problems and datasets
Let M and N be m x real matrices and V E I This paper considers nine problems of linear algebra:
matrix transposition: find M a n x m matrix, mairix addition: find M + N, m x n matrix, matrix-vector multiplication: find M in R",
n matrix, eigenvalues: M symmetric, find its (real) eigenvalues, sorted in descending order, eigenvectors: M symmetric, find D diagonal and Q orthogonal such that QMQT = D, set as (n+ + 1) x a matrix, with (sorted) cigenvalues in its first row,
matrix multiplication: find M N,
singular values: find the n eigenvalues of M M, sorted in descending order, singular value decomposition: find orthogonal U, V and diagonal S such that S UM,, set as a
(m + n + 1) x min(m, n) matrix,
inversion: M square and invertible, find its inverse P, such that MP PM Id.
These problems range from operations single coefficients of the matrices (transposition and addition), to computations over rows and columns, involving several arithmetic operations (multiplication), and complex nonlinear transformations involving the whole matrix (decompositions and inversion).
For cach problem, the training data is generated by sampling random input matrices I (sec section 2.2 and computing the out put with a linear algebra package (NumPy linalg). All coefficients in and O are set base ten floating-pols point representation, and rounded to three significant digits in the mantissa. If problem has several input or output matrices, they are concatenated into one (for instance, the two m n operands of the addition task are concatenated into one x 2n matrix I).
2.1 Encoding matrices as sequences
The input and output to all problems studied here are matrices. Transformers process sequences of tokens. To encode x matrix as sequence, its dimensions are encoded two symbolic tokens (Vm and Vn), and its mn coefficients are then enumerated and encoded. 1 propose four encoding schemes for matrix coefficients (set in scientific notation with three significant digits): P10, P1000, B1999, and FP15.
Base positional encoding (P10) represents numbers as sequences of five tokens one sign token (+ or -), digits (from to 9) for the mantissa, and symbolic token (from E-100 to E+100) for the exponent. For instance, 3.14 is represented as 314.10-2, and encoded as [+, 3, 1, 4, E-2].
Base 1000 positional encoding (P1000) provides more compact representation. The mantissa is encoded as single token (from 0 to 999) and a number is represented as the triplet (sign, mantissa, exponent).
Balanced base 1999 (B1999) encodes the sign and mantissa as a single token (from -999 to 999).
bit floating point (FP15) encodes floating point number x m10² as single token FPm/b. Table 1 provides examples for the four encodings. More information be found in Appendix A
2

---

Published in Transactions on Machine Learning Research (10/2022)
Encoding
3.14
6.02.10
Tokens coefficient
Size vocabulary
P10
[+, 3, 1, 4, E-2]
[-, 6, 0, 2, E21]
210
P1000
[+, 314, E-2]
[-, 602, E21]
1100
B1999
[314, E-2]
[-602, E21]
2
2000
FP15
[FP314/-2]
[FP-602/21]
30000
Table 1: Four encodings for matrix coefficients.
Choosing an encoding is a tradc-off. Long encodings (P10, P1000) use a small vocabulary, and embed knowledge about numbers that the model can use (e.g. that numbers can be crudely compared from their signs and exponents only, that addition and multiplication can be learned by memorizing small tables). Compact encodings use a larger vocabulary (harder learn) but result in shorter sequences that facilitate training with transformers. In P10, 20 20 matrix is sequence of 2002 tokens, close to the practical limit of transformers with quadratic attention. In FP15, it is only 402 tokens long.
The decision to round matrix coefficients to three significant digits is mainly motivated by the need to keep FP15 vocabulary at sizes that small transformers can learn without pre-training. Experiments about the impact of number precision can be found in appendix C
2.2 Random matrix generation
In most experiments, training and test data are random matrices with coefficients uniformly distributed A] (with A A= 10). When symmetric, these matrices are known as Wigner matrices. Their eigenvalues have a centered distribution with standard deviation converges as n grows to the semi-circle law p(A) = 4 - X2 X2 (2mo²). the coefficients follow a gaussian distribution, the associated eigenvectors are uniformly distributed over the unit sphere.
An/3 (see Mehta (2004) and Appendix H) that
In section 4.4 while investigating out-of-distribution generalization, I will need to generate random symmetric matrices with specific eigenvalue distributions (i.e. classes of random matrices with non-independent coefficients). To this effect, I sample random symmetric matrices M with gaussian coefficients, and compute their eigenvalue decomposition M = PDP"" with P an orthogonal matrix of eigenvectors (uniformly distributed over the unit sphere because the coefficients are gaussian). Replacing D, the diagonal matrix of eigenvalues of M, with diagonal D' sampled from a different distribution, and recomputing M' PD' pT yields symmetric matrix (since / is orthogonal) with eigenvalues following the desired distribution, and eigenvectors uniformly distributed over the unit sphere.
3 Models and experimental settings
Models and training. All models use the transformer architecture from Vaswani et al. 2017): encoder and a decoder connected by cross-attention. Models have 512 dimensions, 8 attention heads and up to 6 layers (experiments with larger models can be found in Appendix D.3 Training is supervised, minimizes the cross-entropy between model predictions and correct solutions, and uses the Adam optimiser (Kingma & Ba 2014) with a learning rate of 10-4, a linear warm-up phase of 10,000 steps and cosine scheduling (Loshchilov & Hutter p. Training data is generated on the fly in batches of 64. All models are trained on an internal cluster, using NVIDIA Volta GPU with 32GB memory. Basic operations on matrices and eigenvalues train 1 GPU in less than day (from few hours for transposition and addition, a day for multiplication and eigenvalues). Eigenvectors, SVD and inversion train on 4 GPU, and take from 3 days to week.
Evaluation. At the end of every epoch (300,000 examples), random test set (10,000 examples) is generated and model accuracy is evaluated. A predicted sequence is a correct solution to the problem (I,O) O) (I and O the input and output matrices) if it can be decoded as a valid matrix P and approximates the correct solution to a given tolerance r. In most problems, chock that P verifies PP < r||O||- When computing eigenvectors, verify that the predicted solution (Q, can reconstruct the input matrix, I!QIQT -DI < value decomposition, I check that |UTV - SS| < T||S||, and for matrix inversion, that ||PT Td]l <<||Td| T.
+|| For singular
3

---

Published in Transactions on Machine Learning Research (10/2022)
The L' norm, |||||=
= Eng |رييl, for A (as,)), is used in all experiments. With other norms, like L or L the error is weighted in favor of correct predictions of the largest coefficients in the solution. For eigenvalue and singular value prediction, this amounts to finding the largest values, a different and easier problem. More discussion and comparisons between norms can be found in Appendix
Numerical tolerance. All results are provided with tolerance T between 0.5 and 5%. Since coefficients are rounded three significant digits, 0.5% the best we can achieve when computations are subject rounding error. As computations become more complex, error accumulates, and larger values of r should be considered. I consider 0% for transposition, T= 2 or 5% for non linear operations (dccomposition, inversion).
1% for basic matrix operations (addition and multiplication), and
Problem size. All experiments are performed on dense matrices. In most cases, focus on 5 x 5 matrices (or rectangular matrices with as many coefficients: e.g. 6 x 4,2 x 13), and scale to larger dimensions, from 8 15 15, and datasots of matricos with variable dimensions (e.g. 5 x to 15 x 15). In this paper, the emphasis is on problems that can be solved by small transformers (up to 6 layers). I discuss scaling and larger models in Appendix D.3
4 Experiments and results
This section presents experimental results for the nine problems considered. I compare encodings for different matrix sizes and tolerance levels, using the best choice of hyperparameters for each problem (i.e. the smallest architecture that can achieve high accuracy). I also show that our models are robust to noise in the training data. Learning curves and experiments with model size can be found in Appendix D alternative architectures in Appendix E (LSTM and GRU) and E.2 (universal transformers), and additional tasks (re-training, joint
training) Appendix F
4.1 Transposition
Learning to transposc matrix amounts to learning a permutation of its elements. For square matrix, all cycles in the permutation have length 1 or 2. Longer cycles may appear in rectangular matrices. This task involves no arithmetic operations: tokens in the imput sequence are merely copied to different positions in the output. This paper investigates two cases. In the fixed-dimension case, all matrices in the dataset have the same dimensions and only one permutation must be learned. In the variable-dimension case, the dataset includes matrices of different formats, and several permutations must be learned (one per matrix format). these experiments, models have one layer, 256 dimensions and 8 attention heads, and use the four encodings.
After training, all models achieve 99% exact accuracy (0% tolerance) for fixed-size matrices with dimensions up to 30 x 30. This holds for all encodings and input and output sequence lengths up to 2000 tokens. The variable-size case proves more difficult, because the model must learn many different permutations. Still, the model achieve 99% accuracy on matrices with 5 to 15 dimensions, and 96% for matrices with 5 to 20 dimensions. Table 2 summarizes the results.
Fixed dimensions
Variable dimensions
Square 5-15
Rectangular
5x5
10x10
20x20
30x30
5x6
7x8
9x11
5-20
5-15
5-20
P10
100
100
100
100
100
100
100
97.0
P1000
100
100
99.9
100
100
100
99.9
98.4
B1999
100
100
99.9
100
100
100
100
100
96.6
99.6
91.4
FP15
99.8
99.5
99.4
99.8
99.8
99.5
99.3
99.8
99.6
99.4
96.1
Table 2: Exact prediction of matrix transposition for different matrix dimensions. Transformers with one layer, 256 dimensions and 8 attention heads.
4

---

Published in Transactions on Machine Learning Research (10/2022)
4.2 Addition
To add two matrices, the model must. learn the correspondence between input and output positions and the algorithm for adding two numbers in scientific notation. Then, it must apply the algorithm to mn pairs of cocfficients. In these experiments, models have one or two layers, 8 attention heads and 512 dimensions.
All models achieve 99% accuracy at 1% tolerance (98% at 0.5%) on sums of fixed-size matrices with dimensions up to 10 x 10, for all four encodings. B1999 models achieve 99.5% accuracy at 0.5% tolerance for 15 15 matrices and 87.9% accuracy at 1% tolerance on 20 20 matrices. As dimensions increase, models using long encodings (P (P1000 and P10) become more difficult to train their imput sequences grow longer. For instance, adding two 15 x 15 matrices involves 450 coefficients, input of 1352 tokens in P1000 and 2252 in P10.
On variable-size matrices, models achieve 99.5% accuracy at 1% tolerance for dimensions up to 10, with 2-layer transformers using the B1999 encoding. Their accuracy drops to 48 and 37% for square and rectangular matrices with 15 dimensions. This can be mitigated by increasing the depth of the decoder: models with one layer in the encoder and 6 in the decoder achieve 77 and 87% accuracy. Table summarizes these results.
Fixed dimensions
Variable dimensions
Square
Rectangular
Size Layers
5x5
6x4
3x8
10x10
15x15
20x20
5-10
5-15
5-15
5-10
5-15
5-15
2/2
2/2
2/2
2/2
2/2
1/1
2/2
1/1
1/6
2/2
2/2
1/6
5%
100
99.9
99.9
100
100
98.8
100
63.1
99.3
100
72.4
99.4
2%
100
99.5
99.8
100
100
98.4
99.8
53.3
88.1
99.8
50.8
94.9
1%
100
99.3
99.7
100
99.9
87.9
99.5
47.9
77.2
99.6
36.9
86.8
0.5%
100
98.1
98.9
100
99.5
48.8
98.9
42.6
72.7
99.1
29.7
80.1
Table 3: Accuracies of matrix sums, for different tolerances. B1999 encoding, 512 dimension and attention
heads.
4.3 Multiplication
Multiplication of matrix M of dimension between V and the lines of M. Each calculation features multiplications and additions, and involves one row in the matrix and all coefficients in the vector. The model must now learn two operations: add and multiply. Experiments with modcls with and 2 layers show that high accuracy can only be achioved with the P10 or P1000 encoding, with P1000 performing better on average. The number of layers, on the other hand, makes little difference.
by vector V R" amounts to computing m dot products
P10
P1000
P1000
Variable 5-10 (P1000)
5x5
5x5
10x10
14x2
9x3
4x6
2x10
Square
Rectangular
Tolerance
2/2 layers
2/2
2/2
1/1
1/1
2/2
2/2
4/4
2/2
5%
100
100
100
99.3
99.9
100
100
72.4
41.7
2%
99.9
100
100
99.0
99.7
100
99.8
68.4
35.0
1%
98.5
99.9
99.9
98.7
99.5
99.2
60.1
20.1
0.5%
81.6
99.5
98.4
98.1
99.0
98.6
94.5
30.8
4.4
Table Accuracies of matrix-vector products, different: tolerances. All model have 512 dimensions and heads.
On this task, models achieve 99.9% accuracy at 1% tolerance for 5 x 5 and 10 x 10 square matrices, and 99% for rectangular matrices with about 30 coefficients. The variable-size case proves much harder. Models achieve non-trivial results: 60% accuracy with 1% tolerance for square matrices, but larger models are needed for high accuracy. Table summarizes the results.
Multiplication of matrices M and P scaled-up version of matrix- vector multiplication, now performed for every column in matrix P. As above, high accuracy only achieved with the P10 and P1000 encoding.
5

---

Published in Transactions on Machine Learning Research (10/2022)
Square matrices
Rectangullr matrices
5x5
5x5
2x13
2x12
3x8
4x6
6x4
8x33
12x2
13x2
Tolerance
P10 2/2 layers
1/4
4/4
4/4
2/6
1/4
1/6
1/6
1/6
1/4
5%
100
100
100
100
100
100
100
100
2%
100
100
100
100
100
100
100
100
99.7
99.8
1%
99.8
100
99.9
100
100
99.9
100
99.9
99.3
99.8
0.5%
64.5
99.9
97.1
98.5
99.6
99.7
99.5
99.5
99.0
99.8
Table 5: Accuracy of matrix multiplication, for different tolerances. Fixed-size matrices with 24-26 coefficients. All encodings P1000 unless specified. Models have 512 dimensions and attention heads.
Models achieve 99% accuracy at 1% tolerance for x 5 square matrices and rectangular matrices of comparable dimensions (see Table Performance is the same as matrix-vector multiplication, simpler task. However, matrix multiplication needs deeper models (especially decoders), and more training time.
4.4 Eigenvalues
Compared to basic operations on matrices, computing the eigenvalues of symmetric matrices is a much harder problem, non-linear and typically solved by iterative algorithms. Deeper models, with 4 or 6 layers, are used in this task. They achieve 100% accuracy at. 5% tolerance, and 99% at 2%, for 5 x and 8 matrices. High accuracy is achieved with all four encodings, but P1000 proves more efficient with 8 matrices.
On fixed-size datasets, scaling to larger problems proves difficult. It takes 360 million examples for our best models to reach 25% accuracy on 10 x 10 matrices. As comparison, 40 million examples are required to train 5 x models to 99% accuracy, and 60 million for 8x8 models. This limitation can be overcome by training on variable-size datasets, achieving 100% accuracy al 5% tolerance, and 100, 100 and 76% at 2%, for sets 5-10, 5-15 and 5-20 matrices. Table summarizes the results.
Fixed dimensions
Variable dimensions
5x5
5x5
5x5
5x5
8x8
8x8
10x10
5-10
5-15
5-20
Encoding Layers
P10
P1000
B1999
FP15
P1000
FP15
FP15
FP15
FP15
FP15
6/6
4/1
6/6
6/1
6/1
1/6
1/6
4/1
6/6
4/1
5%
100
100
100
100
100
25.3
100
100
2%
100
99.9
100
100
99.2
97.7
0.4
99.8
100
75.5
1%
99.8
98.6
99.7
84.7
77.9
94.3
45.3
0.5%
93.7
88.5
73.0
91.8
31.1
23.9
37.2
40.6
22.5
Table 6: Accuracy of cigenvalues for different tolerances and dimensions. All models have 512 dimensions and attention heads, except the 10x10 model, which has 510 and 12.
Larger models. In the fixed-dimension case, 6-layer models are limited to 8 matrices. Experiments with deeper models show that they solve larger problems. For instance, 12-layer transformers compute the eigenvalues of 12 x 12 matrices. Large models also need less examples to train to high accuracy. Table 7 summarizes these results. Detailed results are in Appendix D.3
Accuracy
Sample size (millions)
Layers
1/8
1/12
1/24
1/8
1/12
1/24
8 x 8 matrices
100
100
100
28.8
11.4
11.1
10 matrices
100
100
100
85.2
36.6
32.1
12 x 12 matricus
3
97
100
99.3
Table 7: Eigenvalues, larger models. Accuracy to 5% tolerance, and sample size to reach 99% accuracy.

---

Published in Transactions on Machine Learning Research (10/2022)
4.5 Eigenvectors
In this task, the model predicts both the eigenvalues and an associated orthogonal matrix of eigenvectors. Models using the P10 and P1000 encoding achieve 97 and 94% accuracy at 5% tolerance for 5 x 5 matrices. P1000 models also reach 82% accuracy on 6 x 6 matrices. Whereas FP15 models only reach 52% accuracy, an asymmerric model, coupling a 6-layer FP15 encoder and a 1-layer P1000 decoder, achieves 94% accuracy at 5% and 87 at 2%; the best result. on this task. Table summarizes these results.
5x55
6x6
P10
P1000
FP15
FP15 PP15/P1000
P1000
4/4 layers
6/6
1/6
6/1
6/1
5%
97.0
94.0
51.6
93.5
81.5
2%
83.4
77.9
12.6
87.4
67.2
1%
31.2
41.5
0.6
67.5
11.0
0.5%
0.6
2.9
0
11.8
0.1
Table 8: Accuracies of cigenvectors, for different tolerances and depths (512 dimensions, 8 heads).
Analysis of failure cases. On this task, models achieve significantly less than 100% accuracy. This makes it possible to investigate failure cases. For this analysis, I use the trained FP15 /P1000 6/1 layer model from table S (93% accuracy), generate a new test sample of 10 000 problems, predict solutions, and evaluate performance on various metrics. On this new test set, the model achieves 91.1% accuracy with 5% tolerance, and 82.1, 45.2 and 1.4% at 2, 1 and 0.5 tolerance.
First,, one notes that almost all model predictions (9999 out of 10000) are well-formed matrices: the model produces no meaningless output, such as incorrect encoding of numbers, or matrices with the wrong number of elements. This is consistently observed in all experiments: output syntax is learned to near-perfection at the beginning of training. Also, accuracy increases with tolerance: 95.6% accuracy at 25% tolerance. This suggests that, even when they fail to predict the correct solution, models do not hallucinate irrelevant. predictions (as was reported on natural language tasks). Instead, they predict syntactically correct solutions that often turn out to be "rough approximations" of the correct answer.
When computing cigenvectors, the model prodicts two matrices, a diagonal matrix of eigenvalues D and orthogonal matrix of eigenvectors H. Accuracy is measured as the _ distance between H² IH (I the input matrix) and D, i.e how well H diagonalizes the imput into D. A different metric, the distance between H HDH and 1, could be used instead, which is associated to a related, but weaker, problem: finding approximations to of the form HDH" (D diagonal). With this metric, the model achieves slightly higher accuracy: 95.7% at 5% tolerance (92.9, 88.4 and 73.0 at 2, and 0.5%). This confirms our previous observation that, many failure cases, the model predicts solutions that are "somehow relevant" " eigen decomposition (here, solutions to the weak problem).
We also know from theory that D should contain the eigenvalues of the input matrices, and that H should be orthogonal (all lines and columns orthogonal, with unit norm). Translating these properties into metrics can help us understand failure cases, and the relevance of incorrect model predictions.
First, eigenvalues are always correctly predicted: the corresponding accuracy is 100% at 5% tolerance, and 99.4% 0.5%. The (casier) sub-task of eigenvalue prediction has boen learned by the model. Second, all the norms of the columns of H are within 5% of 1 in 99.9% of the test examples (within 1% in 99.2%). All predicted eigenvectors have unit norm. This indicates that failed model predictions actually succeed in computing the cigenvalues, and a set of unit vectors. In other words, those two properties of eigen decomposition have been learned by the model, in the sense that they are respected even in incorrect predictions.
To measure the orthogonality of the eigenvectors, I compute the dot products of successive eigenvectors, which should be all be On the test set, all dot products are within -0.05 and 0.05 93.6 of the cases (and within -0.01 and 0.01 in 85.1). This suggests that when the model fails, proveds the correct eigenvalues, and unit eigenvectors, but fails to make the "eigenvectors" strictly orthogonal. This observation suggests a criterion for
7

---

Published in Transactions on Machine Learning Research (10/2022)
predicting model accuracy: can test the orthogonality of predicted H by measuring its condition number (the ratio of its largest and smallest singular values), which should be one if H is orthogonal, and larger if it. is not. In fact, in 98% of correct predictions, the predicted H has a condition number smaller than 1.035. For 98% of failures, the condition number of H is larger than 1.04.
To summarize, when trained on eigen decomposition, the model learns the easier sub-task of predicting eigenvalues, with 100% accuracy. It also learns preserve theoretical properties of the result, like the unit norm of cigenvectors, and their (approximate) orthogonality. All failures concentrate orthogonalizing the eigenvectors. This allows us to derive accurate predictor of model failure: the condition number of the predicted matrix H.
specific sub-task:
4.6 Inversion
Computing the inverses of 5x5 matriies proves the hardest. lask so far. Models using the P10 and P1000 encodings, with 6-layer encoders and 1-layer decoders and 8 attention heads, achieve 74 and 80% accuracy 5% tolerance. Adding more heads in the encoder bring no gain in accuracy, but makes training faster: 8-head models need 250 millions examples to train to 75% accuracy, 10 and 12-head models only 120. As in the previous task, asymmetric models achieve the best results. 90% accuracy at 5% tolerance can be reached with a 6-layer FP15 encoder with 12 attention heads, and a I-layer P1000 decoder with 8 heads.
P10
P1000
FP15/P1000
Tolerance
8/8 heads
8/8 heads
10/8 heads
12/8 heads
10/4 heads 12/8 heads
5%
73.6
80.4
78.8
76.9
88.5
90.0
2%
46.9
61.0
61.7
52.5
78.4
81.8
1%
15.0
30.1
34.2
16.2
55.5
60.0
0.5%
0.2
3.1
5.9
0.1
20.9
24.7
Table 9: 5x5 matrix inversion. models have 512 dimension and 6/1 layers, except P1000 10 heads, which has
6/6.
Analysis of failure cases. I proceed as in section 4.5 and use the 6/1 layer, 12/8 heads, FP15/P1000 model from table g (90% accuracy). Model accuracy on the new test set is 89.6% at 5% tolerance, and 81.7, 59.1 and 23.7 at 2, 1 and 0.5% tolerance. As previously, all 10000 model predictions are well-formed matrices, and accuracy increases with tolerance: 96.6% at 25%. Again, even when the model fails, it provides a "relevant" " bad approximation of the solution, instead of hallucinating an unrelated guess.
For this task, the accuracy metric is the distance between PT (P the predicted matrix, T the input) and identity (in L norm). This measures that the inverse has indeed been found. However, since the inverse is unique, might as well use the distance between P and r-1 (i.e. the distance the model is minimizing during training). On this alternative metric, the model achieves 98.2% accuracy at 5% tolerance, and 96.0, 92.3 and 84.5% at 2, and 0.5 tolerance. In this metric, all failure cases are bad approximations: the model achieves 99.5% accuracy at 25% tolerance.
This suggests that. most model failures happen because the approximation of the J-1 predicted by the model is not "good inverse" of I, the sense that PI is not close identity. Theory tells us this happens when the condition number of the input matrix (the ratio of largest smallest singular values) is large. Indeed, 98% of correct predictions correspond to matrices with condition number below 51.5. On the other hand, 98% of failures are matrices with condition numbers larger than 51.5. The condition number of the input matrix proves to be a very accurate predictor of model success.
These results provide a complete explanation of model failures for this task. They indicate that failures are not due to the architecture or learning technique, but to the mathematical limitations of the computation of matrix inverses, which apply to every numerical algorithm. They also indicate that failures are concentratod small class of problems, and can be predicted in advance (without running the model, in this case).
8

---

Published in Transactions on Machine Learning Research (10/2022)
They also suggest two directions for improvement. First, could oversample ill-conditioned matrices in the training set, in manner of curriculum learning. Second, since ill-conditioning amplifies the effect of rounding and approximate computations, training with increased precision should improve accuracy.
4.7 Singular value decomposition (SVD)
For symmetric matrices, singular value and eigenvalue dccompositions are related: the singular values of a symmetric matrix are the square roots of the absolute values of its eigenvalues, and the vectors are the same. Yet, this task proves more difficult. than computing the eigenvectors. Models achieve 100 accuracy at 5% tolerance, and 86.7% at 1% when predicting the singular values of 4 x symmetric matrices. For the full dccomposition, models achieve 98.9 and 75.3% accuracy. However, the SVD of 5x5 matrices could not be predicted using transformers with up layers, and using the P10 P1000 encoding. Table 10 summarizes these results, models with 512 dimensions and 8 attention heads.
Singular values
Singular vectors
P10 2/2 layers P1000 4/4 layers
P10 1/6 layers P1000 6/6 layers
5%
100
100
71.5
98.9
2%
98.5
99.8
15.6
95.7
1%
84.5
86.7
0.4
75.3
0.5%
41.1
39.8
0
6.3
Table 10: Accuracies of SVD for 4x4 matrices.
4.8 Experiments with noisy data
Because experimental data is often noisy, robustneess noise a key feature of efficient models. In this section, 1 investigate model behavior in the presence of random error when computing the sum and eigenvalues of 5 x 5 matrices. A random gaussian error added all coefficients of the input matrices in the train and test sets, for three levels of noise: standard deviation equal to 1,2 and 5% of the standard deviation of the random matrix coefficients (a 5.77 for uniform coefficients in [-10, 10)) For a linear operation like addition, one expects the model to predict correct results so long tolerance is larger than error. For non-linear computations like eigenvalues, expected outcomes are unclear, as errors may be amplified by non-linearities or reduced by concentration laws.
Addition
Eigenvalues
Encoding Dimension
B1999
FP15
P1000
256
512
512
1024
512
1024
5% tolerance 0.01a error
100
6.1
100
100
0.02
100
100
100
100
100
100
0.05c
41.5
41.2
99.1
99.3
99.3
99.0
2% tolerance
0.01a
99.8
99.9
0.7
99.8
99.3
99.6
0.02c
43.7
44.2
97.0
97.1
97.3
97.9
0.05g
0
37.9
38.4
40.1
37.3
1% tolerance
0.01g error
39.8
41.7
0.1
82.1
79.7
83.8
0.02
0.1
0.1
47.8
51.3
46.2
47.5
0.05g
0
0
3.8
4.2
4.1
3.8
Table 11: Accuracy with noisy data, for different error levels and tolerances (5 x 5 matrices).
Addition. Training on noisy data causes no loss in accuracy in the models, so long the ratio between the standard deviation of noise and that of the coefficients is lower than tolerance. Within 5% tolerance, models

---

Published in Transactions on Machine Learning Research (10/2022)
trained with 0.01o and 0.02 noise reach 100% accuracy, do models trained with trained with 0.010 noise at 2% tolerance. Accuracy drops to about 40% when error levels are approximately equal to tolerance, and to zero once eтror exceeds tolerance. Model size and encoding have no impact on robustness (see Table [1 2-1ayer, 8-head models and Table 27 in Appendix F.3..
Eigenvalues. Models trained with the P1000 encoding prove more robust to noise when computing eigenvalues than when calculating sums. For instance, they achieve 99% accuracy at 5% tolerance with noise equal to 0.05ø, vs only 41% for addition. As before, model size has no impact robustness. However, FP15 models prove more difficult to train noisy data than P1000 (see Table I1 and Table 28 in Appendix F. for additional results, models have 4 layers and 8 heads).
5 Out-of-domain generalization
So far, model accuracy was measured on test sets of matrices generated with the same procedure as the training set. In this section, I investigate accuracies on test sets with different distributions. I focus on one task: predicting the eigenvalues of symmetric matrices (with tolerance 2%).
Wigner matrices. All models are trained on datasets of random symmetrie real matrices, with independent and identically distributed (iid) coefficients sampled from uniform distribution over A]. These are known Wigner matrices (see 2.2 and constitute very common class of random matrices. Yet, matrices with different cigenvalue distributions (and non iid cocfficients) appear in important problems. For instance, statistical covariance matrices have all their eigenvalues positive, and the adjacency matrices of scale-free and other San-Erdos-Renyy graphs have centered but non semi semi-circle distributions of eigenvalues (Preciado & Rahimian 2017). We now investigate how models trained on Wigner matrices perform on test sets of matrices with different distributions.
Testing on different distributions. Matrix coefficients in the training set are sampled from U[-10, 10], with standard deviation or, = 5.77. First, I consider test sets of Wigner matrices with different standard deviation Test. Models achieve high accuracy (96% at 2% tolerance) so long 0.60,, < Orse < Otr. Out of this range, model accuracy drops: to 54% for 0.40tr; to 26% for 1.10tr, to 2% for 1.3 and to 0% for 0.20,r. Then, the model is tested on sets of matrices with different eigenvalue distributions: positive, uniform, Gaussian and Laplace (generated as per section 2.2), with standard deviation or and 0.60 With Tist = Oir the model achieves 26% accuracy for Laplace, 25 for Gaussian, 19 for uniform, and for positive. With Isst 0.60.r, model accuracy is slightly higher, 28, 44, 60 and 0% respectively, but remains low overall. Matrices with positive eigenvalues cannot be predicted at all. These results are summarized in line 1 of Table 12 These results confirm previous observations (Welleck et al. 2021): transformers only generalize to a narrow neighborhood around their training distribution.
Training on different distributions. A commin approach to improving out-of-distributtin accuracy is to make the training set more diverse. Models trained from a mixture of Wigner matrices with different standard deviation (A E [1, 100), line 2 of Table 12) generalize to Wigner matrices of all standard deviation (which are no longer test. set. But they do not generalize to positive matrices. A model trained on mixture of Wigner and positive eigenvalues (line 3 of Table 12 can predict positive eigenvalues (now in-domain), but its performance degrades on all other test sets.
and achieve better performances on the uniform, Gaussian and Laplace
Training on mixtures of Wigner and Gaussian eigenvalues, or Wigner and Taplace eigenvalues (lines and of Table 12. achicves high accuracies over all test sets, including the out-of-distribution sets: uniform and positive eigenvalues, and Wigner with low high standard deviations.
Finally, models trained matrices with Laplace eigenvalues only, or mixture of uniform, Gaussian and Laplace cigenvalues (all non-Wigner matrices) achieve 95% accuracy over all test sets (lines 6 and 7 of Table 12.. These results confirm that out-of-distribution generalization is possible, if attention is paid to the training data distribution. They also suggest that Wigner matrices, the default model for random matrices, is not the best choice for training transformers: models trained on Wigner matrices do not generalize out of distribution, whereas models trained on non- non-Wrgner matrices, with non-iid coefficients, do generalize Wigner matrices.
10

---

Published in Transactions on Machine Learning Research (10/2022)
Train set distribution
Test set eigenvalue distribution
Wigner
Positive
Uniform
Gaussian
Laplace 0.6
Otat/Otr
0.3
1.0
1.2
0.6
0.6
1
0.6
1
1
Wigner, A=10 (baseline)
12
100
7
0
0
60
19
44
25
28
26
Wigner, A E [1, 100]
99
98
97
0
0
68
60
65
59
57
53
Wigner- Positive
99
88
99
23
31
23
17
20
Wigner- Gaussian
88
100
100
99
99
96
98
93
97
84
90
Wigner- Laplace
98
100
100
100
100
100
100
99
100
96
99
Laplace
95
99
99
100
100
98
98
97
98
94
96
Gaussian- Uniform-Laplace
99
100
100
100
100
100
100
99
100
97
99
Table 12: Out-of-distribution eigenvalue accuracy (tolerance 2%) for different training distributions. All models have 512 dimensions and 8 attention heads, and use the P1000 encoding.
6 Related work
Neural networks for linear algebra. Neural networks that compute eigenvalues and eigenvectors
have been proposed since the early 1990s (Samardzija & Waterland, 1991 Cichocki & Unbehauen 1992 Oja
1992
Yi et al. 2004), and are still an active field of research (TTng & Li 2010; Finol et al.) 2019 They
leverage the Universal Approximation Theorem (Cybenko 1989 Hornik 1991 which states that, under weak
conditions on their activation functions, neural networks can approximate any continuous mapping in this case, the mapping betweon a matrix and its cigenvalues or vectors. In these works, the network represents a differential equations involving matrix coefficients, which features the eigenvalues in its solution (Brockett 1991p. The matrix to decompose is encoded in the input, and prediction errors are pack-ppopagated until solution to the differential equation is found, from which eigenvalues can be recovered. Note that these models compute their solutions during training, and must be retrained every time new matrix is to be
processed. Similar techniques have been proposed for other problems of linear algebra (Wang 1993a b Zhang
et al. 2008
Arithmetic with neural networks. Neural networks for binary addition and multiplication have been proposed since the 1990s (Siu & Roychowdhury 1992). Since 2015, recurrent architectures have been used,
from LSTM (Kalchbrenner et al. 2015)) to RNN Zaremba et al., 2015), Neural Turing Machines (Castellini 2019h and Neural GPU (Kaiser & Sutskever) 2015). All authors nole that sequential models struggle to generalize out of their training distribution (i.e. to larger numbers), and that their architectures only perform satisfactorily on binary numbers. Neural Arithmetic Logic Units (NALU (Trak et al. 2018) were introducod as solution to the generalization problem. They can perform exact additions, substractions, multiplication and divisions by raining the weights of linear network to remain close to 0, 1 or -1. NALU (and Neural GPU) can extrapolate to numbers far larger than those they were trained on, and could serve as building blocks for larger models. The use of language models for arithmetic and problem solving has been studied by
Saxton et al. 2019). Palamas (017)) experiments with modular arithmetic Nogueira et al. 2021 investigates
the limitations of transformers.
Transformers for mathematics. Early applications of transformers to mathematics focused on symbolic computation. Lample & Charton (019) used transformers to compute symbolic integrals and solve differential oquations. Davis (2019) and Welleck et al. 22221) discuss the limits of their approach, ospocially with respect out-of-distribution generalization. Transformers have also been applied to theorem proving (Polu & Sutskever
2020: Han et al. 2021), temporal logic (Hahn et al.] 2021), and have been proposed
replacement for the
genetic algorithms used in symbolic regression (Biggio et al. 2021 d d'Ascoli et al. 2022). In more numerical applications, Charton et al. (2020) use them to predict the numerical properties of differential systems, and Dersy el al. 2022) to simplify formulas involving polylogarithms.
With the advent of large language models (Bommasani et al.) 2021 a new line of rescarch focuses on informal mathematics: solving problems of mathematics written in natural language, as language task (Griffith &
Kalita, 2021 Meng & Rumshisky 2019 Cobbe al. 2021 Lewkowyez et al. (022) show that very large
11

---

Published in Transactions on Machine Learning Research (10/2022)
(540 billion parameters) pre-trained transformer can be retrained large math corpus to solve grade and high school problems of mathematics. [Welleck et al. (2022) apply similar techniques to theorem proving.
Other architectures for mathematics. Graph Neural Networks (Scareelli et al. 2009) have been widely used in scientific applications of AI, because of their capacity to integrate problem or domain-specific inductive biases into the network structure. They have been applied a wide range of mathematical problems, from dynamical systems (lakovlev et al. 2020) to combinatorial optimization (Cappart et al. 2021) and knot theory
Davics et al., 2021 Vinyals et al. (2015) proposed pointer networks to solve combinatorial problems. Blalock]
& Guttag 2022] use machine learning techniques to improve existing algorithms for matrix multiplication, in the specific case where one fixed matrix should be multiplied by many others.
7 Discussion
Encodings and architecture. Our best results are achieved using the P1000 and FP15 encodings. For most problems, P10 is dominated by the more economical P1000, and B1999 never finds its use, between the more compact FP15 and the more efficient P1000. P1000 emerges as a good choice for problems of moderate size, and FP15 when sequences grow long. For the hardest problems, eigenvectors and inversion, asymmetric encodings, FP15 in the encoder and P1000 in the decoder, achieve the best results. I believe that the longer and meaningful P1000 output representation provide better error feedback to the model, facilitating learning, while the FP15 encoding provides a compact representation of the input, which is casier to train.
Experiments also showcase the efficacy of asymmetric architectures, with one layer in either the encoder or decoder. Whether the encoder or the decoder should be shallow is unclear: on the eigenvalue and eigenvector tasks, the 6/1 and 1/6 architecture scem equally efficient. Finally, increasing the number of attention heads seems to help. Most transformers architectures (from Vaswani BERT) maintain a dimension caeaniioonhhadd head ratio of 64, increased to 96 or more in very large models like GPT-3. For eigenvalue and inversion, using 10 12 heads with dimension 512, i.e. dimension/ head ratio between 40 and 50, improves model accuracy.
Model limitations, scaling to large dimensions. Most experiments feature dense matrices with 5 to 10 dimensions. Experiments with eigenvalues suggest that larger problems can be solved by training from samples of matrices of variable size, or by using larger models. However, scaling to larger dense matrices will be limited by the length of the sequences a transformer can handle. For quadratic attention models (i.e. most current transformer architectures), sequence length can hardly exceed few thousand tokens, and the methods proposed in this paper could probably not scale beyond 50 x 50 matricos. Experimenting with transformers with linear or log-linear attention (Zaheer et al. 2021 Wang et al. 2020a; Vyas et al. 2020 Child et al. 2019) is a natural extension of this work. Problems of larger dimension usually feature sparse matrices, and therefore are out of the scope of this work. Extension to sparse matrices constitutes a future rescarch direction.
Out-of-distributiio experiments. These are our most signíficant results. They prove that transformers trained on random data can generalize to a wide range of test distributions, provided their training data distribution is chosen with care. Selecting a training distribution can be counter-intuitive. In our experiments, Wigner matrices are the "obvious" random model, but "special" matrices (with non-iid coefficients and Laplace eigenvalues) produce models that better generalize, notably on Wigner matrices. This matches the intuitive idea that we learn more from edge cases than averages.
Result verification. One common criticism of deep learning models that they provide no guarantee on the correctness of their output. This limitation does not apply here, as the model achieves 100% accuracy on basic matrix operations and eigenvalue calculations, and our analysis of failure cases propose a mitigation for the harder problems of eigenvectors and matrix inversion.
Do the models memoize? Transformers are often accused of using the large capacity of their food-forward networks lo memorize training examples, and interpolating between them at inference. Three observations lead me to believe that this is not the case here First, in section 4.4 the eigenvalues of matrices with more than 9 dimensions cannot be learned from training set where all matrices have the same size. However, training on a mixture of matrices from 5 x to 20 20 allows all dimensions to be learned. If memoization happened, a training set with just one dimension would be easier to train than mixture. Second, in
12

---

Published in Transactions on Machine Learning Research (10/2022)
retraining model on matrices of a different dimension takes significantly less examples than training it from scratch. In memoization setting, there would be little benefit to retraining. Finally, the results on out-of-domain generalization seem to rule out interpolation. A model trained on matrices with Laplace distributed eigenvalues (which can be positive or negative) will generalize to positive definite matrices, a different ensemble, with very little overlap (almost no Laplace matrix positive).
appendix F.1
Comparison with numerical packages. Given the practical importance of linear algebra, optimized numerical libraries exist for most programming languages and environment. Since my models run in Python, compare them with Numpy.
Calculating the eigenvalues of a 5 x 5 matrix takes 0.5 millisecond on a trained 4/1 layer transformer rumning pyTorch on a single GPU machine. Matrix inversion takes 1 ms with a 6/1 layer transformer, running py Torch on a single GPU machine, On the same machine, the optimized algorithms in Numpy (linalg.eigvall and linalg.ivv) are faster 0.07 millisccond for eigenvalues and 0.04 ms for inversion. However, the current code was not designed for speed. An optimized version of the models might achieve inference speeds comparable to those of numerical packages. Note, however, that the memory footprint of transformer would be considerably larger).
For these two tasks, the algorithms implemented in Numpy and other packages have asymptotic complexity O(n²) (O(n2.77) for the best known bounds) for n x n matrices. The attention mechanism of the transformers used in this paper is quadratic in the length of the sequence (O(n))), which makes it O(n*). Linear attention models could reduce complexity O( lower than known algorithms, but the memory requirement of transformers would offset this advantage for large n. As stated in the introduction, there no clear advantage to replace existing algorithms with transformers.
8 Conclusion.
have shown that transformers learn to perform numerical computations from examples only. I also proved that they generalize out of domain when their training distribution is carefully selected. This suggests that applications of transformers to mathematics are not limited to symbolic computation, and can cover a broader range of scientific problems. I believe that these results pave the way for wider use of transformers in science.
13

---

Published in Transactions on Machine Learning Research (10/2022)
References
Luca Biggio, Tommaso Bendinelli, Alexander Neitz, Aurelien Lucchi, and Giambattista Parascandolo. Neural symbolic regression that scales. arXiv preprint arXiv:2106004227, 2021.
Davis Blalock and John Guttag. Multiplying matrices without multiplying. arXiv preprint arXiv:2106.10800 2021.
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bossclut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quincy Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha. Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Ben Newman, Allen Nic, Juan Carlos Nicbles, Hamed Nilforoshan, Julian Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitrion, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghmnathan, Rob Reich, Hongyu Ren, Frieda Rong, Yusuf Roohani, Camilo Ruiz, Jack Ryan, Christopher Ré, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishnan Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Perey Liang. On the opportunities and risks of foundation modcls, 2021.
Roger W Brockett. Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems. Linear Algebra and its applications, 146:79 91, 1991.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličkovié. Combinatorial optimization and reasoning with graph neural networks, 2021.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. arXiv preprint 1rX17:2005.12872, 2020.
Jacopo Castellini. Learning numeracy: Binary arithmetic with neural turing machines. arXiv preprint arXiv:1904.02478, 2019.
François Charton, Amaury Hayat, and Guillaume Lample. Learning advanced mathematical computations from examples. arXiv preprint axXiv:2006.06462 2020.
Rewon Child, Scott Gray, Alec Radford, and Πlya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10599 2019.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rmn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.11 2014.
Andrzej Cichocki and Rolf Unbehauen. Neural networks for computing eigenvalues and eigenvoctors. Biological Cybernetics, 68(2):155-D3 -64155164441116 1992.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichir Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.1416: 2021.
Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The neural data router: Adaptive control flow in transformers improves systematic generalization. arXiv preprint arXiv:2110.07332 2021.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303 314, 1989.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Stéphane d'Ascoli, Pierro-Alexandre Kamienny, Guillaume Lample, and François Charton. Deep symbolic regression for recurrent sequences, 2022.
A Davies, Velickovie, Buesing, S Blackwell, D Zheng, N Tomasev, R Tanburn, P Battaglia, C Blundell, A Juhasz, et al. Advancing mathematics by guiding human intuition with ai. Nature, 2021.
Ernest Davis. The use of deep learning for symbolic integration: A review of (lample and charton, 2019). arXiv preprint arxiv:1912.05722, 2019.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.0381) 2018.
Aurélien Dersy, Matthew D. Schwartz, and Xiaoyuan Zhang. Simplifying polylogarithms with machine learning, 2022.
Linhao Dong, Shuang Xu, and Bo Xu. transfrtransfoomme:: A no-recurrence sequence-to-sequeeec model for speech recognition. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing 2018.
(ICASSP), pp.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby, An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11999, 2021.
David Finol, Yan Lu, Vijay Mahadevan, and Ankit Srivastava. Deep convolutional neural networks for cigenvalue problems in mechanics. International Journal for Numerical Methods in Engineering, 118(5): 258 275, 2019.
Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint 2016.
Kaden Griffith and Jugal Kalita, Solving arithmetic word problems with transformers and preprocessing of problem text. arXiv preprint arXiv:2106.00803, 2021.
Christopher Hahn, Frederik Schmitt, Jens U. Kreber, Markus N. Rabe, and Bernd Finkbeiner. Teaching temporal logies to neural networks. arXiv preprint arXiv:2003.04213 2021.
Jesse Michael Han, Jason Rute, Yuhuai Wu, Edward W. Ayers, and Stanislas Polu. Proof artifact co-training for theorem proving with language models. arXiv preprint arxiv:2102.06203, 2021.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735-178) 1997.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251-25: 1991.
Valerii lakovlev, Markus Heinonen, and Harri Lähdesmäki. Learning contimonu--imm pdes from sparse data with graph neural networks, 2020.
Eukasz Kaiser and Πya Sutskever. Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228, 2015.
Nal Kalchbrenner, Tvo Danihelka, and Alex Graves. Grid long short-term memory. arXiv preprint arxiv:1507.01533 2015.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1412.698) 2014.
arXiv preprint
Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison- Wesley, third edition, 1997.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Guillaume Lample and François Charton. Deep learning for symbolic mathematics. arXiv preprint arXiv:1912.01412, 2019.
Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Tmanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with language models, 2022.
Nya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint
arXiv:1608.03983, 2016.
Madan Lal Mchta. Random Matrices. Academic Press, 3rd edition, 2004.
Yuanliang Meng and Anna Rumshisky, Solving math word problems with double-decoder transformer. arXiv preprint arXiv:1908. 10924, 2019.
Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2102.13019 2021.
Erkki Oja. Principal components, minor components, and linear neural networks. Neural networks, 5(6): 927-935, 1992.
Theodoros Palamas. Investigating the ability of neural networks to learn simple modular arithmetic. 2017.
Stanislas Polu and Tlya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint 2XXi::2009.03393, 2020.
Victor M. Preciado and M. Amin Rahimian. Moment-based spectral analysis of random graphs with given expected degrees. arXiv preprint arXiv:1512.03488 2017.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAT blog, 18):99 2019.
Nikola Samardzija and RL Waterland. A neural network for computing eigenvectors and eigenvalues. Biological Cybernetics, 65(4):21112) 1991.
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. arXiv preprint 0115 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Shai Shalev-Shwartz Ohad Shamir, and Shaked Shammah. Failures of gradient- based deep learning. In Doina Precup and Yee Whye Tch (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3067-3075. PMLR, 06 11 Aug 2017.
Feng Shi, Chonghan Lee, Mohammad Khairul Bashar, Nikhil Shukla, Song-Chun Chun Zhu, and Vijaykrishnan Narayanan. Transformer-basee machine learning for fast sat solvers and logic synthesis. arXiv preprint. arXiv:2107.07116, 2021.
Kai-Yeung Siu and Vwani Roychowdhury. Optimal depth neural networks for multiplication and related problems. In S. Hanson, J. Cowan, and C. Giles (cds.), Advances in Neural Information Processing Systems. volume 5. Margan-Kaufmann 1992.
Ying Tang and Jianping Li. Another neural network based approach for computing cigenvalues and eigenvectors of real skew-symmelric matrices. Computers & Mathematics with Applications, 60(5):1385-13) 1392, 2010.
Andrew Trask, Felix Hill, Scott Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. arXiv preprint ar X 808.808..0000 808.00508, 2018.
16

---

Published in Transactions on Machine Learning Research (10/2022)
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 6000 6010, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks, 2015.
Apoory Vyas, Angelos Katharopoulos, and François Fleuret. Fast transformers with clustered attention. arXiv preprint arXiv:2007.04525, 2020.
Jun Wang. A recurrent neural network for real-time matrix inversion. Applied Mathematics and Computation, 55(1):89 100, 1993a.
Jun Wang. Recurrent neural networks for solving linear matrix equations. Computers & Mathematics with Applications, 26(9):23-34 34, 1993b.
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.0477 2020a.
Yongqiang Wang, AbdeIrahman Mohamed, Due Le, Chunxi Liu, Alex Xiao, Jay Mahadeokar, Hongzhao Huang, Andros Tjandra, Xiaohui Zhang, Frank Zhang, and et al. Transformer-based acoustic modeling for hybrid speech recognition. 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), May 2020b.
Scan Welleck, Peter West, Jize Cao, and Yejin Choi. Symbolic brittleness in sequence models: on systematic generalization in symbolic mathernttics. arXiv preprint arXiv:2109.1300 2021.
Sean Wellock, Jiacheng Liu, Ximing Lu, Hannanch Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models, 2022.
Zhang Yi, Yan Fu, and Hua Jin Tang. Neural networks based approach for computing eigenvectors and eigenvalues of symmetric matrix. Computers Mathematics with Applications, 47(8-9):1155 1164, 2004.
Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. arXiv preprint 1rX6v 2021.
Wojciech Zaremba, Tomas Mikolov, Armand Joulin, and Rob Fergus. Learning simple algorithms from examples, 2015.
Yunong Zhang, Weimu Ma, and Binghuang Cai. From zhang neural network to newton iteration for matrix inversion. IEEE Transactions Circuits and Systems I: Regular Papers, 56(7):1405-141) 4415-115, 2008.
17

---

Published in Transactions on Machine Learning Research (10/2022)
A Number encodings
Let x be non-zero real number, it can be represented uniquely as s.m.10e, with s E {-1,1) 1, m E [100, 1000[ and e E 2. Rounding m to the nearest integer n (and potentially adjusting for round-up to 1000), we get the base ten, floating-poin representation of x, with three significant digits:
x 8.m.10,, (s, m, e) E (-1,1) x
x Z
By convention, 0 is encoded as +0.10 All encodings are possible representations of the triplets (s, this paper, e is restricted to [-100, 100), and m to [100, 999].
m, e). In
In base N positional encoding, 8 (the sign) and e (the exponent) are encoded as unique tokens: or for 8, and one token from E-100 to E100 for e. The mantissa, m, is encoded as the representation of m in base N (e.g. binary representation if N 2, decimal representation if N 10), sequence of [logw (1000)] Lokens from O to N-1. Overall, number will be encoded as sequence of [logx (1000) + tokens, from vocabulary of 202 + N tokens.
For instance, x = ex x 23.14069, will be represented by +231.10 and encoded in P10 (base 10 positional) as the sequence [,,,,3,1,E-1] and in P1000 (base 1000 positional) as [+, 2,,31,EE-1] æ = -0.5 will be represented as 500.100- and encoded in P10 as 0, N could be considered, as well as different bases for the exponent, and different lengths for the mantissa. This paper uses two positional encodings: P10, which encodes numbers rounded to three significant digits, with absolute value in [10-100 , as sequences of 5 tokens, using vocabulary of 213 tokens (10 digits, 2 signs, and 202 values of the exponent), and P1000 which encodes numbers as sequences of 3 tokens, with a vocabulary of 1104.
and P1000 as [-,500, E-3). Other bascs
Balanced base 2a + 1 uses digits between -a and a (Knuth 1997j. For instance, in balanced base 11, digits range from -5 to 5. An every day example of a balanced base can be found in the way we state the hour as "twenty to two", or "twenty past two". Setting a to 999 defines B1999, which encodes the sign and mantissa single token between -99 and 999, and the exponent in P10 and P1000. Numbers are encoded on two lokens, with a vocabulary of 2004.
For an even more compact representation, floating point numbers can be encoded as unique tokens, by rewriting any number as x = m10', with m E [-999, 999), b E [-(p + 2)/2, (p + 2)/2] and p 2 = 0, [2], and representing it as the unique token FPm,b. This allows represent numbers with 3 significant digits and a dynamic range of 108+2, using vocabulary of 1800(p 3) tokens. Setting p = 14, this paper introduces FP15, which encodes numbers as unique tokens with a vocabulary of 30, 000.
B 1,,, 1,2 and 0 norms for evaluation
The accuracy of trained models is evaluated by decoding their predictions and verifying that they approximate the correct solution up to fixed tolerance т. In the general case, if the model predicts sequence Sr, and the solution of the problem is O, the prediction is considered to be correct if Sp can be decoded into matrix P and
PP- 011 < <|||0||
(1)
For eigenvalue decomposition, the solution is correct it can be decomposed as a pair (Q, D) that verifies: IIQT (QQ-D] < T|| (I the input matrix), i.c. that Q diagonalizes I into D. For singular value decomposition, the solution must verify ||UVV - S|| < +||S]|, and for matrix inversion || |I Id] < 7 r||ld|| = t. The matrix norm Lt: ||A||| Ex, |اويl for A = (as,5) is used throughout this paper. This section discusscs its advantage
over two other possible norms: T,2 (|] = Σi, )f and I (|| = max,, (d,
Using Lt- norm in equation Jmoonns to comparing the average absolute error on the predicted coefficients (P-O) to the average absolute value of coefficients of O. L compares the squared values and errors, and L the largest absolute error to the largest coefficient in |O]. Compared to L', I and I (Max) emphasize large absolute errors, and large absolute coefficients of O. The impact of the norm varies from one problem to another. Figure 1 presents learning curves using the three norms for our best models, different problems.
18

---

Published in Transactions on Machine Learning Research (10/2022)
Transposition
Addition 10x10 matrices
Matrix vector multiplication 5x5 matrices
5-15 rectangular matrices
30-
10-
80-
Max
Eigenvalues
Eigenvalues 5-15 matrices
Eigenvalues 10x10 matrices
5x5 matrices
120
100
130
40-
0-
10
100
200
360
460
560
42o
750
a2o
400
000
a5o
1000
1202
Singular Values
Eigenvectors
Matrix Inversion
4x4 matrices
6x6 matrices
5x5 matrices
130
100
130-
125
120
175
55
300
200
250
500
420
Figure 1: Learning accuracies for different problems measured with norms L', Laand d (Max).
For basic arithmetic operations (transposition, addition, multiplication), there little difference between I,1 and 2 accuracics, and no reason to prefer one over the other for model evaluation. L provides a stricter criterion for accuracy, but has little practical impact.
For eigenvalue and singular value problems, L accuracies reach high value early during training, long before the model begins to learn according to the other norms. This is due to the fact that the cigenvalues of Wigner matrices lend to be regularly spaced over the interval [-2o, 2n] (a Viis with 8 the standard deviation of coefficients and n the dimension of the matrix). This means that the model can predict the largest absolute cigenvalues from the distribution of the coefficients, which can be computed from the dataset. For this reason, L accuracy is not good evaluation metric for the eigenvalue singular value problem. This particularly clear in the 10 10 case: transformers struggle with such matrices, and I,1 and 7
19

---

Published in Transactions on Machine Learning Research (10/2022)
accuracies remain very low even after thousand epochs (300 million examples), but L accuracy is close to 100% since the beginning of training.
A similar phenomenon takes place for eigenvector calculations: L and - accuracy rise steeply, long before the model begins to learn according to the L' norm. In this task, the model predicts both the eigenvalues and the coefficients of the matrix of eigenvectors Q. Because Q is orthogonal, small absolute values, compared to those of eigenvalues. As training goes on, the largest eigenvalue is first predicted, which causes the rise in the L curve, then other cigenvalues are, which cause the rise in the L correctly predicted, which is depicted in the (much slower) rise of the
coefficients will usually have
curve, and finally the eigenvectors I curve. Again, using I or L amounts to evaluating an casier problem (computing cigenvalues) than the one we are currently solving (eigen decomposition).. These observations motivate the choice of L as our evaluation norm.
C Impact of number precision
In all experiments, matrix coefficients are rounded to three significant digits. Three-digit precision was selected in order to keep the size of the FP15 vocabulary manageable. With three-digit precision, FP15 uses vocabulary of 30 000 words, with four digits, would use 300 000 words, and would be difficult train on the small transformers this paper focuses on.
In this section, I investigate the impact of number precision on 10 10 matrix addition and 5 x 5 cigenvalue computation. Random matrices are rounded to two, three and four significant digits, using the P100, P1000 and P10000 encoding (i.e. numbers encoded on three Lokens, mantissa in base 100, 1000 and 10000). train transformers with 512 dimensions, attention heads, and 2/2 layers (addition) or 4/1 layers (eigenvalues).
Results for 10, 5, 2, 1, 0.5 and 0.1% tolerance are presented in tables 13 and 14
On the addition task, rounding precision has impact for tolerances larger than 1%: all models achieve close to 100% accuracy. At 0.5 tolerance, models trained with 2-digit precision are penalised by rounding error, but there is no significant difference between 3 and 4-digit precision. However, 4-digit models need significantly more examples to train: whereas 2 and 3-digit models achieve 99% accuracy at 5% tolerance after 5 million examples, a 4-digit model need 21 millions to reach 99% accuracy.
Tolerance
0.5
0.1
2-digit precision, P100
100
100
100
99.4
60.8
0
3-digit precision, P1000
100
100
99.3
98.1
97.2
66.4
4-digit precision, P10000
99.5
99.4
99.4
99.0
98.8
17.3
Table 13: Accuracy of 10 x matrix addition, for different precision and tolerance, after training on
million examples.
For eigenvalues, all models achieve 100% accuracy at 5% lolerance. At lower tolerance (1 0.5%), accuracy increases with precision. On this task, learning speed is comparable for all models: 2, 3 and 4-digit models achieve 99% accuracy (with 5% tolerance) after 9, 8 and 7 million examples respectively. Overall, number precision has a marginal effect on accuracy.
Tolerance
10
5
2
0.5
0.1
2-digit precision, P100
100
100
94.3
87.4 .4.4
80.1
24.1
3-digit precision, P1000
100
100
99.9
98.2
78.9
4-digit precision, P10000
100
100
99.9
99.0
85.6
1.4
Table 14: Accuracy of x 5 eigenvalue calculation, for different precision and tolerance, after training on 60 million examples.
20

---

Published in Transactions on Machine Learning Research (10/2022)
Addition (10x10); test loss
Addition (10x10); 5% accuracy
Addition (10x10); 1% accuracy
P10 layars
228
P1000 2/2 layers
B1999
81999 layers
FP15 2/2 layers
layers
50
100
120
140
206
120
146
Eigenvalues: test loss
Eigenvalues: 5% accuracy
Eigenvalues: 1% accuracy
layers
220
P10 4/1 layers
P1000
25-
P1000 layers
B. 91999 6/6 layers
layers
40
40-
15-
30-
125
375
200
100
175
25
350
Eigenvectors: test loss
Eigenvectors: 5% accuracy
Eigenvectors: 1% accuracy
layers
P10 ti6 layers
4/4 loyers
P1000 6/1 layers
300
FP1 1/01 layers
layers
40-
Inversion: test loss
Inversion: 5% accuracy
Inversion: 1% accuracy
P1000 8/8 heeds
P1000 12/8 heads
50-
FP15/P1000 1014 heads
FP15/P1000 12/8 heads
60-
320 470
3/0
séc
Epochs
Figure 2: Learning curves for different problems. All problems except addition use x matrices. All models have 512 dimensions and 8/8 heads (except when mentioned the legend). Inversion models have 6/1 layers. Epochs correspond to 300,000 training examples. Test loss is cross-entropy.
21

---

Published in Transactions on Machine Learning Research (10/2022)
D Additional experimental results
D.1 Learning curves for different encodings and architectures
Figure presents learning curves (test loss, and 1% accuracy) for (10 X 10) addition, and (5 x 5eigenvalues, eigenveclors and inversion. The best models learn to perform addition (1% tolerance) in less than 10 epochs (3 million examples). For other tasks, training size increases with operation complexity: from 20 million (70 epochs) for eigenvalues, to million for eigenvectors, and over 120 million for matrix inversion. Some of the learning curves exhibit the "step shapes" often observed in arithmetic tasks: losses are subject to brutal drops, corresponding to steep increases in accuracy.
The learning curves for the harder problems (eigenvalues, eigenvectors and inversion) are noisy. This is caused by the learning rates: our models usually need small learning rates (5 x 10 before scheduling is typical) and there is a trade-off between low rates that will stabilize the learning curve, and larger rates that accelerate training.
D.2 Impact of model size accuracy and learning speed
Two main factors inffuence model size: the number of layers and the number of dimensions (see Appendix G for precise calculations). This section discusses their impact on accuracy and learning speed, when adding x 10 matrices, multiplying 5 x matrix by a vector, and computing the eigenvalues of a x matrix. All the models in this section are symmetric (same dimension and number of layers the encoder and decoder) and have 8 attention heads.
For the addition task, tables 15 and 16 present the accuracy after 60 epochs (18 million examples) and the number of epochs (of 300,000 examples) needed to reach 95% accuracy, for models using the P1000 and B1999 encoding. Shallow architectures (i.e. or 2 layers) learn addition with high accuracy for both encodings, but the more compact B1999 supports smaller models (256 dimensions). In terms of speed, shallow (2-layer) B1999 and deep (6-layer) P100 prove fastest.
B1999
P1000
dimension
128
256
512
128
256
1/1 layers
31
7
82
100
0
0
1
40
2/2 layers
0
100
100
0
0
0
99
4/4 layers
0
14
0
0
98
6/6 layers
0
0
Table 15: Accuracy of matrix addition for different model sizes. 10 x 10 matrices, 60 epochs (18 millions
examples), 5% Volerance.
B1999
P1000
dimension
64
128
256
512
64
128
256
512
1/1 layers
2/2 layers
26
6
37
4/4 layers
63
6/6 layers
23
Table 16: Learning speed of matrix addition for different model sizes. Number epochs needed to reach 95% accuracy (5% tolerance). epoch 300,000 examples.
Table 17 presents the learning speed of models of different sizes for the matrix/veclor product and eigenvalue computation tasks (5 x matrices, and P1000 encoding). For each problem, there exists a minimal dimension and depth under which models struggle to learn: one layer and 128 dimensions for products, one layer or 128 dimensions for eigenvalues. Over that limit, increasing the dimension accelerates learning. Increasing the depth, the other hand, bring clear improvement in speed accuracy.
22

---

Published in Transactions on Machine Learning Research (10/2022)
Matrix product
Figenvalung lues
128
256
512
128
256
512
1024
1/1 layers
29
18
2/2 layers
24
12
7
102
36
23
4/4 layers
28
244
6/6 layers
24
10
6
129
16
8/8 layers
18
Table 17: Learning speed of matrix and vector products and eigenvalue calculations for different model sizes. Number of epochs needed to reach 95% accuracy (with 5% tolerance). 1 epoch = 300,000 examples. 5 x matrices, P1000 encoding.
D.3 Scaling to larger models
This paper mostly focuses small models, with up to 6 layers and 50 million parameters. In this section, investigate the performance of larger models, with up to 24 layers and over 400 million parameters. All models are asymmetric, featuring either deep encoder and a shallow (1-layer) decoder, or the reverse. Shallow models have one layer, 512 dimensions and 8 attention heads. Deep models range from small (6 layers) to medium (8 layers), large (12 layers) and extra-large (24 layers). By default, they have a dimension of 512, 640, 768 and 1024, and 8, 10, 12 and 16 heads respectively. For each size, also experiment with models with 50% more dimensions and attention heads. The basic encoding FP15/P1000, but also experiment with two alternative configurations: FP15/FP15 and P1000/P1000. Table 18 summarizes the configurations that were tested.
Model size
Base configuration
Larger dimension
More heads
Small: 6 layers
512 dimensions, 8 heads
768
12
Medium: 8 layers
640 dimensions, 10 heads
960
15
Large:
12 layers
768 dimensions, 12 heads
1152
18
Extra-large:
24 layers
1024 dimensions, 16 heads
1536
Table 18: Large model configurations. All three configurations are tested for the encoder and decoder, and with the three encodings: FP15/P1000, P1000/P1000, FP15/FP15.
For the eigenvalue lask, models are trained on x 8, 10 x 10 and 12 x 12 matrices. Table 19 presents the best performing configurations, for different tolerance levels, and the sample size needed to achieve 99% accuracy (with 5% tolcrance). In general, architectures combining a deep decoder with a shallow encoder outperform deep encoders and shallow decoders. Deeper models tend to learn faster, and solve larger problems, but for a given number of layers, there is not clear advantage of increasing dimension or the number of attention heads. In particular, models with 12 24 layers can compute the eigenvalues of 12 12 matrices, task inaccessible to small architectures. Learning to predict the eigenvalues of 8 8 matrices takes over 50 million examples for 6-layer models, but only 11 million for 24-layer architectures. For 10 x 10 matrices, 8-layer models need about 85 million examples, whereas 12 and 24-layer models need 38 and 36. Finally, it is interesting to note that larger models achieve better precision: 12-layer models routinely achieve accuracies over 90% with 0.5% tolerance, while smaller models struggle at such precision levels.
23

---

Published in Transactions on Machine Learning Research (10/2022)
Model
Dimensions
5%
2%
1%
0.5%
Sample size*
Small (6 layers)
E:1 2511/51/8//1 /F//11 D:6/516/12/PP1M
8x8
100
99.5
88.8
35.9
51
/:1/512/8/ //12/8/FP11 /FP15 D:6/ /100//000010
8x8
100
97.7
86.5
50.3
64.2
000/768/8/P1000 D:1/512/8/P100
8x8
80.8
28.1
64.8
2:1/512/8/FPP) D:6/ D6//68//8 768/8//1000
8x8
100
97.9
69.8
17.7
71.7
E:1/512/8/TPI5 D6//11/11/P10N
10x10
99.7
72.6
22.3
2.2
194.7
2:1/512/8/FPI1 D:6/768/8/FPP)
10x10
83.6
17.0
1.5
0.1
Medium (8 layers)
2:8//44/10//1100
D:1/512/8/P1000
8x8
99.4
99.0
97.0
60.1
120.9
B:1/512/8/FFPL1 D:8/645 1155/5//1100 PP000
8x8
100
99.9
95.9
56.1
45
B:1/512/8/FFF /FP15 D:8/960 160/10/P1100
8x8
100
99.9
95.4
55.9
34.8
E:1/512/8/
5F/11 /FP15 D:8 D:8/6/0/10/ P0000
8x8
100
99.8
92.0
42.0
43.8
E:1/512/8/ FFP1 D:8/ /00/////1100000000
10x10
100
98.4
70.2
11.2
85.2
E:1/512/8/FP15 D/8/645/15/P10M
10x10
99.1
62.9
14.1
1.0
108.6
E:1/512/8/TPII D:8/645/15/FP15
12x12
3.0
0
0
Large (12 layers)
E:1/512/8/FPIL
D:12/1152/12/P1000
8x8
100
100
100
99.1
13.2
E:1/512/8/FP115 D:12/766/12/P1000
8x8
100
100
99.9
93.5
42
8:1/512/8/FPPJ D:12/766/12/P1000
10x10
100
100
99.8
89.3
68.7
E:1/512/8/FPI1 FFP1 D:12/1155/112/P1000
10x10
100
100
99.7
96.8
37.5
E:1/512/8/FPDI /FP15 D:12/768/12/P1000
12x12
96.7
24.2
1.5
0.1
E:1/512/8/FP15 D:12/76/12/FF11
12x12
85.2
11.8
0.6
Extra-large (24 layers)
E:1/512///TP15
D:24/1024/16/P100
8x8
100
100
100
99.2
11.1
E:1/512/8/FP15
8x8
100
100
100
93.9
14.1
B:1/512/8/FPI1 D:24 D:24/1032/24/FP1
8x8
100
100
99.7
82.6
19.5
B:L/512/8/FFPI5 D:24/ D:24/1024/ 1024/16/P1000
10x10
100
100
99.6
75.9
36.3
B:1/512/8/FFPL
222/1032/24/P100
10x10
100
100
99.5
69.3
42.6
E:1/512/8/FPP /FP15 D:21/1032/24/P100
12x12
100
99.6
95.5
43.7
99.6
T:1/512/8/FP15 D:21/1021/16/P100
12x12
100
99.6
88.9
23.0
99.3
Table 19: Large models: accuracy of cigenvalue computations. E-EEncoer, D=Decoder 1/512/8 later, 512 dimensions, 8 heads. Sorted by 1% accuracy. *Millions of examples reach 99% accuracy
D.4 Model performance on different training sets
The models presented the main part of this paper are trained on Wigner matrices (matrices with independent and identically distributed, iid, coefficients) with fixed-range coefficient. In section 5 argued that different training sets allowed for better out-of-domain generalization. Table 20 summarizes in-domain performance (Lee accuracy when the test set is has the same distribution the training set) different training sets.
Wigner matrices with uniform or Gaussian distributed, and fixed or variable-range, coefficients are learned to high accuracy (more than 99%) by all models. The eigenvalues of non- WonnWr matrices with Gaussian or Laplace distributed eigenvalues, and mixtures Wigner and non- Wigner matrices, are also predicted high accuracy by all models. Over matrices with positive uniformly distributed eigenvalues, smaller models using the FP15 encoding prove difficult train.
24

---

Published in Transactions on Machine Learning Research (10/2022)
FP15
P1000
4/1 layers
6/1 layers
4/1 layers
6/1 layers
Wigner matrices (iid coefficients)
Uniform iid A=10
99.6
100
99.8
100
Gaussian iid A=10
99.8
100
99.8
100
Uniform iid A=1,100
99.0
99.2
99.8
100
Uniform tid A=1,1000
99.2
99.5
99.7
99.8
Non Wigner
Positive 1
12.7
100
100
100
Uniform A=10
8.2
10.8
99.9
100
Gaussian A=10
99.6
100
100
100
Laplace A=10
99.4
99.9
99.9
99.9
- -aplere A=10
3.8
99.8
99.6
99.9
Wigner and non- Winner mixtures
+ A=10
99.5
99.9
98.0
99.7
iid did+-post positive A=10
99.8
99.9
99.8
99.8
iid +iplaae A=10
99.6
99.8
99.6
99.5
fid ond+pon positiie----asssinn A=10
99.8
99.9
99.7
99.9
lid posiiiii--ee--plce A=10
99.0
99.8
99.6
99.8
Table 20: In-distribution eigenvalue accuracy (tolerance 2%) for different training distributions, All models have 512 dimensions, and attention heads, and trained on 5x5 matrices.
E
Alternative architectures
E.1 Other sequence to sequence models : LSTM and GRU
eepeermented with two popular recurrent architectures: long short-term memories (LSTM Hochreiter & Schmidhuber (1997)), and gated recurrent units (GRU Cho et al. (2014)), on three tasks addition of 5 and x matrices, cigenvalues and matrix inversion x matrices. All models are sequence-to-sequene architectures: encoder and decoder (LSTM or GRU), with 2 to layers, and 1024 2048 hidden dimensions. The input and output sequences, encoded in the rest of the paper, are pre-processed (and decoded) via embedding layer with 256 or 512 dimensions.
Addition, a very easy task for transformers (see section 4.2 proves difficult for LSTM and GRU. None of the models can learn addition of 10 10 matrices. Some models can learn addition of 5 5 matrices, but whereas transformers achieve 100% accuracy for all tolerances, the best LSTM and GRU only exceed 90% at 1% tolerance. GRU seem to perform better than LSTM on this task, and 2-layer models perform better than 4-layer models, but transformers have distinct advantage over L.TT and GRU for addition.
Both LSTM and GRU can be trained to predict eigenvalues of 5 x 5 matrices with the same accuracy transformers, for the P1000 and FP15 encoding (table 22 Matrix inversion, on the other hand, cannot be learned. Overall, these experiments show that other sequence to sequence architectures, LSTM and GRU, can learn tasks like cigenvalues and addition of small matrices. However, they are less efficient on addition (in terms of precision and scaling to larger matrices) and fail on more complex lasks, like matrix inversion.
E.2 Shared-layer transformers: Universal transformers
In the Universal Transformer (Dehghani et al. 2018), the stacked layers of usual transformer inplemennattinns are replaced by one layer that is looped through fixed number of times (feeding the output of one itcration into the input of the next). This amounts to sharing the weights of the different layers, therefore greatly reducing the number of parameters in the model. This technique can be applied to the encoder, the decoder or both. The number of iterations is fixed hyperparameter, but the original paper also proposed halting mechanism inspired by Adaptive Computation Time (Graves) 2016), adaptively control loop length at the token level. In this version, stopping probability is learned for every position in the input sequence, and
25

---

Published in Transactions on Machine Learning Research (10/2022)
layers
layers
Hidden dimension
1024
2048
1024
2048
Embedding dimension
256
512
256
512
256
512
256
512
Long short-term memory
5% tolerance
100
100
2% tolerance
98
0
100
0
0
1% tolerance
95
86
0.5% lolerance
34
0
1
0
0
Gated recurrent Units
5% tolerance
100
100
0
100
100
0
2% tolerance
100
0
100
99
1% tolerance
44
91
74
0.5% tolerance
0
0
9
4
Table 21: matrix addition using LSTM and GRU.
FP15
P1000
Hidden dimension
1024
2048
1024
2048
Layers
4
6
8
4
6
8
4
6
8
4
8
LSTM
5% tolerance
100
100
100
100
100
6
100
100
5
100
100
100
2% tolerance
95
100
100
99
100
1
100
100
1
100
99
100
1% tolerance
78
98
99
91
98
0
97
98
0
100
92
99
0.5% lolerance
46
81
83
62
68
0
78
88
0
89
57
76
Gated recurrent Units
5% tolerance
100
100
100
100
100
100
100
100
100
100
100
2% tolerance
98
99
100
100
100
100
99
100
100
100
100
1% tolerance
96
97
95
98
0.5% tolerance
53
68
75
78
83
65
65
76
63
75
0
66
Table 22: Eigenvalue computation with LSTM and GRU, x 5 matrices.
once it reaches certain threshold, the layer merely copies the input onto the output. The iteration stops when all positions have halted, specific value is reached. A recent paper (Csordás et al., 2021 proposes to use similar copy-gating mechanism to skip iterations in a fixed-length loop. experiment with these three variants (fixed length, adaptive halting, copy gating) on the addition (of 10 x 10 matrices), eigenvalue and matrix inversion tasks (5 x 5 matrices).
For the addition task, train universal transformers with one layer and in the encoder and decoder, 256 or 512 dimensions and attention heads, and use the B1999 encoding for the data. experiment with looped encoder, looped decoder, and loop in both, loop length of 4, copy-gating and ACT (the 4 loops in then maximum number of iterations)and copy-gating. Table 23 summarizes my findings. Only models with encoder loops learn to add, and models with 512 dimensions learn with over 95% accuracy for all tolerances. Universal Transformers with one layer (looped-encoder only) perform as well as 2/2 transformers.
On the eigenvalue task, experiment on the P1000 and FP15 encoding, with encoder-loop only 1/1 Uni- versal Transformers with 8 loops. Universal transformers using the P1000 encoding achieve the same performances (with only one layer) than transformers from section 4.4 4 loop transformers seem to perform best, gating does not seem to improve performance and ACT slightly degrades it. With the FP15 encoding, universal transformers become very difficult to train: only the 4 loop gated version achieves significant. accuracy (still lower than the 6/1 transformers).
Finally, experimented with matrix inversion, with FP15/P1000 and P1000/P1000 encodings, and or 8 loops in the encoder. A gated universal transformer using FP15 in the input and P1000 the output achieved 73% accuracy, a significant result albeit lower than the best result achieved with 6/1 transformers using the same encodings (90%). With the P1000 encoding, the best universal transformers reach 55% accuracy,
26

---

Published in Transactions on Machine Learning Research (10/2022)
5%
2%
0.5%
Looped encoder
256 dimensions, loops
15
1
512 dimensions, 1 loops
100
100
100
100
256 dimensions, loops, gated
66
512 dimensions, 4 loops, gated
100
100
100
100
256 dimensions, loops, ACT
100
92
512 dimensions, 4 loops, ACT
100
100
98
96
Looped decoder
0
0
0
Looped encoder and decoder
0
0
2/2 transformer (baseline)
100
100
100
100
Table 23: Accuracy Universal transformers, 10 x matrix addition for different tolerances.
2%
1%
0.5%
P1000
4 loops
100
100
97
87
8 loops
100
99
93
69
4 loops, gated
100
100
98
91
8 loops, gated
100
100
99
90
4 loops, ACT
97
89
8 loops, ACT
100
95
77
42
FP15
4 loops
0
0
8 loops
0
0
4 loops, gated
94
84
57
23
8 loops, gated
1
0
4 loops, ACT
0
0
8 loops, ACT
0
4/1 transformer (P1000 baseline)
100
100
99
6/1 transformer (FP15 baseline)
100
100
100
92
Table 24: Accuracy of Universal transformers, x matrices eigenvalue computation for different tolerances.
compared to 80% for their 6/1 transformer counterparts. Overall, Universal Transformers seem to achieve comparable performances with deep transformers (except on the inversion tasks), using less parameters. This makes shared layer transformers an interesting direction for future work.
F
Additional experiments
F.1
Retraining
Models trained on mairices given size do not generalize to different dimensions, but they can be retrained over samples of matrices of different size. This takes comparatively few examples: 5 x 5 model, that takes 40 million examples to be trained,
learn to prodict with high accuracy eigenvalues of matrices of dimension 6 and with about 25 million additional examples. Table 25 presents those results. The possibility to retrain large transformers (such as GPT-3) on different tasks is well documented, it is interesting to observe the same phenomenon in smaller models.
27

---

Published in Transactions on Machine Learning Research (10/2022)
Encoding
Retrain dimensions
Accuracy (5%)
Accuracy (2%)
Retrain examples
P10
5-6
100
99.9
10M
P10
5-7
100
93.6
25M
P1000
5-6
100
97.7
25M
Table 25: Model accuracy after retraining. Models trained over 5x5 matrices, retrained over 5-7. Overall performance after reiraining (tolerance 5 and 2%), and number of examples needed for retraining, All models have 512 dimensions and 8 attention heads
F.2 Joint training: learning perform several operations
All models so far are trained on just one task. In this section, I investigate joint learning: training one model to perform several operations. To this effect, a token is added at the beginming of the input and output sequence, to indicate the task (e.g. Transpose or Add), and generate training data by randomly mixing examples of the different operations to be performed.
Transformers with 4 layers, 512 dimensions and 8 attention heads are trained eight datasets corresponding to the following joint training goals (all operations in equal proportions):
Transpose and add (TA)
Transpose, add and dot product (vector matrix multiplication) (TAD)
Transpose, add, dot product and matrix multiplication (TADM)
Transpose, add, dot product, matrix multiplication and eigenvalues (TADME)
Transpose, add, dot product, matrix multiplication, cigenvalues and cigenvectors (TADMEF) Transpose, add, dot product, matrix multiplication, eigenvalues, eigenvectors and matrix inversion (TADMEFI)
Eigenvalues, cigenvectors and matrix inversion (EFI)
Table 26 summarizes results.
T
A
D
M
E
TA
100
100
TAD
100
100
100
TADM
100
100
100
100
TADME
100
100
100
80
TADMEF
100
100
100
100
3
0
TADMEFI
100
100
100
100
3
EFT
100
22
0
Table 26: Accuracy of joint training, 5 x matrices, 5% tolerance.
Over mixtures of the four basic operations (transposition, addition, dot products and multiplication: goals TA, TAD and TADM), models predict all operations with almost perfect accuracy. Joint training on the basic operations and eigenvalue computations (the TADME task) allows the model to predict eigenvalues with 80% accuracy, in exchange for a loss of performances on the dot product task. As the number of non-basic tasks increases, the model keeps learning basic operations to 100% accuracy (as in the TADM sctting), but the more advanced operations are not. learned. Joint training on the advanced lasks only (eigenvalues, vectors and inversion) results in 100% accuracy on eigenvalue computation, 22% on eigenvectors, and 0 on inversion. These results demonstrate the feasibility of joint training on basic matrix operations, but also suggest that further research is needed if one wants to extend joint training to all the tasks considered in this paper.
F.3 Additional results with noisy data
See tables
27 and
28
28

---

Published in Transactions on Machine Learning Research (10/2022)
B1999
P1000
2/2 layers 256
4/4
layers
2/2
layers
4/4 layers
512
256
512
256
512
256
512
5% tolerance
0.01a error
100
100
100
100
99.4
100
0.02c
100
100
99.8
100
100
100
100
100
0.05g
41.5
41.2
41.7
41.6
39.3
41.2
39.4
40.7
2% tolerance 0.01 eтror
99.8
99.9
99.8
99.9
99.4
100
98.2
99.9
0.02c
43.7
44.2
42.1
44.7
39.0
44.9
42.6
45.3
0.05g
0
0
0
0
0
1% tolerance
0.01a error
39.8
41.7
39.6
44.0
36.6
44.0
28.9
44.6
0.02c
0.1
0.1
0.1
0.1
0.1
0.05g
0
0
0
0
0
0
0
Table 27: Accuracy of noisy 5 x matrix addition for different error levels and tolerances.
FP15
P1000
4/4 layers
6/6 layers
4/4 layers
6/6 layers
512
1024
512
1024
512
1024
512
1024
5% tolerance 0.01a error
6.1
100
5.1
6.0
100
100
100
100
0.02
100
100
6.7
100
100
100
100
100
0.05g
99.1
99.3
99.3
6.4
99.3
99.0
99.0
98.8
2% tolerance 0.01a error
0.7
99.8
0.5
0.8
99.3
99.6
99.9
99.8
0.02
97.0
97.1
0.8
88.4
97.3
97.9
93.1
95.4
0.05a
37.9
38.4
40.6
0.5
40.1
37.3
37.5
35.3
1% tolerance
0.01 error
0.1
82.1
0.1
0.2
79.7
83.8
87.9
83.8
0.02o
47.8
51.3
0.1
26.1
46.2
47.5
36.4
41.3
0.05o
3.8
4.2
4.1
0.1
4.1
3.8
3.9
3.4
Table 28: Accuracy of noisy eigenvalue computations, for different error levels and tolerances, 5
matrices.
G Number of parameters
The number of parameters in the sequence- sequence-to-sequenee to-sequence transformers used in this paper can be calculated as follows.
self-attention mechanism with dimension d has 4d(d+ 1) parameters: it composed four linear layers (K, Q V and the output layer), with input, d output and bias.
A cross-attention mechanism with de dimensions in the encoder, and in the decoder has 2d(d+ +2) parameters (K and V are d, x d layers).
A FFN with one hidden layer, d input and output, and h hidden units has d(h + 1) + h(d + 1) parameters.
A layer normalization with d dimensions has 2d parameters.
An encoder layer with dimension has a self-attention mechanism, a FFN with 4d hidden units (in this implementation) and two layer normalizations, for a total number of parameters of 12d + 13d.
A decoder layer has cross-attention layer (encoding dimension de) and layer normalization on top of encoder, for total of 14d2 19d 2d.d parameters.
29

---

Published in Transactions on Machine Learning Research (10/2022)
An embedding of dimension d for vocabulary of words will use dw parameters, and 2d more if it is coupled to a layer normalization.
The final prediction layer with an output dimension of d and a decoded vocabulary of w words will use (d + 1 w parameters (but in this case, dw will be shared with the decoder embedding).
Overall, the number of parameters for transformer with ne encoding layers with dimension de, n decoding layers with dimension da, an imput vocabulary of w; words, an output vocabulary of w, words and a positional embedding of up words (corresponding to the maximum sequence length) can be computed by the formula:
P de (w: wp + 2) ((w, + wi 2)da w.) made(12d, 13) + mada + 2d 19)
the four terms in the sum corresponding to the input embedding, the output embedding, the encoder and the decoder.
Table 29 provides the number of parameters for some of the models used in this paper. For the positional embedding, the number of words is the longest input and output sequence studied with that model.
Experiment
Model
Parameters
Transposition
1/1 layers 256 dimensions P10
2,276,171
1/1 layers 256 dimensions P1000
2,737,871
1/1 layers 256 dimensions B1999
3,297,554
1/1 layers 256 dimensions FP15
17,045,441
Addition
2/2 layers, 512 dimensions, B1999
17,619,218
Matrix vector multiplication
2/2 layers 512 dimensions P10
15,578,443
2/2 layers 512 dimensions P1000
16,500,943
4/4 layers 512 dimensions P1000
31,213,775
Matrix multiplication
1/4 layers 512 dimensions P1000
21,756,623
1/6 layers 512 dimensions P1000
30,164,687
Eigen decomposition
1/6 layers 512 dimensions FP15
58,751,937
6/1 layers 512 dimensions FP15
53,493,69
6/1 layers 512 dimensions P1000
24,906, .17
6/6 layers 512 dimensions P1000
15,926,607
Matrix inversion
6/1 layers 512 dimensions FP15/P1000
39,186,127
Table 29: Number of parameters of transformers used in the paper.
H Eigenvalue distribution of Wigner matrices, an empirical justification
Figure 3 provides an empirical confirmation of the property of Wigner matrices mentioned in sections 2.2 and 5 the standard deviation of their eigenvalues a function of their dimension and standard deviation of their coefficients only, and does not depend on the actual distribution of the coefficients. Tn particular, for coefficients with standard deviation
10/ 10/v3- = 5.77, we expect the standard deviation of their eigenvalue distribution to be 12.91, 18.26, 22.36 and 25.81 for square matrices of dimension 10, 15 and 20.
For three distributions, uniform, Laplace and gaussian, and four dimensions (5, 10, 15, and 20), 100 000 random matrices with the same standard deviation of coefficients were generated, and their cigenvalues were computed. Standard deviations are within 0.01 of theoretical values for all distributions and dimensions. It is interesting to note how the distributions (which correspond to the original coefficient distribution for n = 1) are similar to the scmi-cirele as dimension incrcases.
30

---

Published in Transactions on Machine Learning Research (10/2022)
5x5
10x10
15x15
20x20
12.92
18.25
22.36
25.82
unifom
0 12.91
0 = 18.25
g 22.37
0 25.82
gaussian
402
202
a 12.90
== 18.25
G 22.37
25.83
2002
2502
laplace
1002
302
Figure 3: Empirical distributions of eigenvalues for Wigner matrices, dimension 5x5 (left) to 20x20 (right), with uniform (top), gaussian (middle) and Laplace (bottom) coefficients. All distributions computed from 100 000 random matrices.
31


Reviews:
[{"review_id": "ebIZXXa6FW", "reviewer": "Reviewer_cm5p", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The paper presents a comprehensive set of experiments on solving linear algebra problems using transformers. \n\n2. It proposes four different encodings of input matrices.\n\n3. The paper also shows the models are robust to noise (random errors of matrix entries).\n\n4. The paper presents a specific result on out-of-distribution generalization, namely models trained to predict Laplace-distributed eigenvalues generalize to other classes of matrices such as Wigner matrices or matrices with positive eigenvalues. \n\nWeaknesses\n\n1. The results are limited to very small matrix sizes. Can the model generalize to matrix sizes not trained? For example, there has been techniques since 2015: \n\n[1] Making Neural Programming Architectures Generalize via Recursion \n\nJonathon Cai, Richard Shin, Dawn Song\n\nICLR 2017\n\n[2] Neural GPUs Learn Algorithms\n\nŁukasz Kaiser, Ilya Sutskever\n\n2015\n\n2. Theoretically all problems of such small sizes should be solved with 100% accuracy with transformers. Can the authors train with more data or better synthetic training data to achieve that? \n\n3. The results are just reported as they are without any deeper insights. For those not achieving 100% accuracy currently, what errors does the model make? It was known that models take short cuts. For example, not able to learn general algorithms to solving addition or multiplication, but learns specific algorithms limited to input length. What exactly are transformers learning? I would encourage the authors provide deep insights as done in other papers, e.g.\n\n[3] Transformers discover an elementary calculation system exploiting local attention and grid-like problem representation\n\nSamuel Cognolato, Alberto Testolin\n\n2022\n\n4. The results presented on alternative model architectures, LSTM and GRU also lack insights. What makes transformers learn better than LSTM and GRU? I believe if LSTM and GRU are properly designed and tuned on hyperparameters, and with the right training data, one can achieve 100% accuracy.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies how well transformer can solve linear algebra problems. The problems considered include basic matrix operations (addition, multiplication, transpose) to eigenvalue decomposition and inversion. The paper uses dense transformers and mostly train a specific network for each problem. The problem size is limited to small matrices. The main finding is that transformers can perform well on these tasks, up to a small pre-set error threshold (tolerance). The paper also provides specific results on robustness to noise and out-of-distribution generalization. For OOD, it shows that models trained to predict Laplace-distributed eigenvalues generalize to other classes of matrices such as Wigner matrices or matrices with positive eigenvalues. \n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please address weaknesses pointed out in the previous section of my review.\n\nNote that co-training is a standard term in ML. Quoting wikipedia, \"co-training is a semi-supervised learning technique that requires two views of the data. It assumes that each example is described using two different sets of features that provide complementary information about the instance.\" Please replace co-training with joint training.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "w0QyhEniBO", "reviewer": "Reviewer_zbpq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The paper provides a good example of the importance of having the right inductive bias -- and demonstrates that vanilla transformers are not the right tool for attempting to do numerical linear algebra (NLA), or even learning unknown linear-algebraic from pairs of examples.  It's a useful cautionary tale that there's no magic neural architecture which can solve all of the world's problems and considerable creativity is occasionally needed to design appropriate architectures to address new classes of problems.\n\n* The paper conducts extensive numerical experiments, and the writing is generally clear. \n\nWeaknesses:\n\n* The paper makes minimal attempt to explain why transformers could be a good choice for solving linear algebra problems (apart from being powerful learners for language and vision problems), and uses standard transformers without trying to modify them or exploit any problem structure.  Why did you focus on transformers, and why do you think that densely-connected nets, or res-nets, or perhaps some wavenet-like architectures may not be a better fit?  The only notable attempt at adapting to the new problem is exploring 4 different representation of floating point numbers. For example, matrices are represented as a sequence of numbers, with the only hint to the neural-net about how to interpret them by providing two constants -- the number of rows and number of columns.  Do you have evidence that the transformer is indeed using these two variables successfully?  I suspect that keeping the input in matrix or tensor-form (akin to color-images) might do significantly better (and it's reasonable to expect that for problems that work on matrices the shape would be known a-priori).  For example keeping two matrices A and B stacked into MxNx2 tensor seems like it should have a far easier time to represent at least the addition operation.\n\n* There's only a vague hint about the practical motivation for the problem.  There are many successful applications of neural nets which try to speed up a complex numerical computation, for example solving Navier-Stokes equations in air-flow calculations,  Jin, X., Cai, S., Li, H., & Karniadakis, G. E. (2021). NSFnets (Navier-Stokes flow nets): Physics-informed neural networks for the incompressible Navier-Stokes equations. Journal of Computational Physics, 426,   or using graph-neural nets to approximately solve combinatorial optimization problems:  Cappart, Quentin, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. \"Combinatorial optimization and reasoning with graph neural networks.\" arXiv preprint arXiv:2102.09544 (2021).   In these approaches neural nets have been carefully designed to take advantage of the problem structure (engineer an appropriate inductive bias) -- rather than applying a generic architecture designed for an unrelated task.   I suspect that using custom-made layers -- something akin to OptNet (Amos, B., & Kolter, J. Z. (2017, July). Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning (pp. 136-145). ) -- would be needed to provide a convincing attempt at learning NLA (numerical linear algebra) functions.  \n\n* What is the goal here?  Even if the performance was much better (~90% accuracy for linear algebra restricted to specific random matrices of miniscule size is utterly underwhelming -- useful NLA algorithms are accurate to close-to-numeric precision), I still don't understand how it could be used in practice.   Multiplying,  inverting or eigen-value decomposition of 5x5 or 10x10 matrices takes from 1 micro-second to about 20 micro-seconds on a generic cpu.  So even ignoring the multiple days of intense model training on several GPUs, at test-time feeding the matrices through the transformer to make predictions would not be faster.  If the goal is to learn an unknown complex function which may involve multiple linear-algebraic operations -- then there's a mature field called 'system identification', which has a collection of tools, which should be studied / mentioned / compared too.  For example, there are clearly much more effective tools to learn linear and bi-linear functions from data than feeding them through a transformer.  I think building a custom neural net which may borrow some modules from that literature may provide a dramatically better solution.  Also you should be more specific of what kind of phenomena you're trying to learn? -- maybe give some specific examples (linear algebra at large is too vague)...  There's a reason linear systems are so prevalent in science and engineering -- akin to gaussian distributions -- they indeed can serve as a very accurate description for a variety of natural phenomena -- hence why linear algebra is so widely used. \n\n* The choice of random matrices as a test-suite could be very problematic -- random matrices are a very special sub-family of matrices, for example they exhibit strong concentration of measure (although it's probably more relevant to dimensions higher than 5x5).  For example, columns of random matrices will be approximate orthogonal, and will have a certain norm.  So it's not clear if the net is learning something about the linear-algebraic task, or some property pertaining to the specific random matrix ensemble.  It would be very interesting to see how the learned net performs on a generic collection of matrices arising in real applications, or in common test-suites for linear-algebra -- for example perhaps something like the matrix market collection from NIST (US national institute of standards and technology). \n\n* Given 100's of millions of examples of 5x5 matrices,  it seems like you may be pretty well covering the space of such matrices -- so you may simply be memoizing local neighborhoods rather than really learning how to do NLA.  How would something like a basic K-NN method compare with a similar number of examples?  Alexey Efros presented some evidence that simple KNNs with gigantic training collections can sometimes compare to state-of-the art neural nets on some vision and annotation tasks (Neurips 2017 presentation on unreasonable effectiveness of nearest neighbors).  Are you doing something significantly more effective than simply memorizing neighborhoods of these 100's of millions of examples? The difficulty that you have with applying a single transformer to learn NLA with matrices of different size -- suggests that it's likely not learning much about specific NLA operations... \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies solving a collection of most common linear algebra problems using a classical transformer architecture.  While there are robust industry-strength algorithms for all of these problems that can solve them to numeric precision,  the goal here is not to compete with them, but instead to learn a rough approximation of the mapping from a gigantic collection of input-output example pairs: say given a collection of matrices and their inverses, the neural net should learn how to invert a new matrix from scratch.  The paper considers both fixed-size inputs and the harder case of variable size inputs (where the same architecture has to learn to invert 5x5 and 10x10 matrices), and uses collections of random (iid) matrices as training examples. On comprehensive collection of tests, it shows that for small examples (5x5 to 10x10 or so) indeed one can learn an approximate mapping after seeing hundreds of millions of paired examples, but the evidence seems to indicate that the network is mostly memoizing the neighborhood of the examples it has seen rather than learning much about how to really perform linear algebra.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I feel the paper would be much stronger if instead of asking \"whether one can force transformers to do numerical linear algebra?\" -- it would ask -- \"what is the best neural architecture which can approximate linear algebraic functions?\" -- and came up with something that has at least remotely conceivable practical use.  Giving some hint at specific problems where there's an unknown NLA-like function which one wants to learn from a large collection of input-output pairs would be helpful -- currently there's only a vague hint of possible applications. \n\nAlso trying to review/ apply existing system-identification approaches as a baseline would improve the scholarship in the paper, e.g.:\nLjung, Lennart. \"System identification.\" Signal analysis and prediction. Birkhäuser, Boston, MA, 1998. 163-173.\n\nIn the current form the message that I learned from the paper -- is roughly that transformers are not a great fit to do NLA, and it takes enormous effort to make them show even a remote hint of learning in a highly restricted setting.  I think there's still value in the message -- \"it's not a good idea to eat soup with a fork\" -- but giving some analysis of why the problem structure is hard for transformers, and taking steps to address it would be significantly more valuable. ", "broader_impact_concerns": "It's important to stress/study the limitations of the proposed method -- as it has not ability to certify that its results are accurate or not.  I suspect that the choice of random matrices is strongly biasing the results, and may give over-confidence in the ability of the net to generalize.  e.g. if you give some specific non-random matrices (e.g. with high correlations or near-singularity) outside of your training distribution, the accuracy may be low -- and it's impossible to tell whether to trust the transformer or not. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2NoY31QnF8", "reviewer": "Reviewer_XmY7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- Nine linear algebra operations are studied in this paper, which covers a wide range of possible linear algebra operations. \n- Four encoding schemes are proposed to represent the numerical real numbers, providing feasible solutions for the learnable numerical calculation problem. \n- In general, the Transformer achieved high accuracy under certain error thresholds on the nine problems. \n\n## Weaknesses\n- Technically, the main contribution of this paper is the utilization of Transformer to solve the nine linear algebra problems. The application is somehow novel. But from the algorithm and model perspectives, there is not much contribution and new insights in this paper. \n- In the main paper, there is no other baseline except for Transformer. For example, in Related Work, the authors stated: **\"Algorithms using neural networks to compute eigenvalues and eigenvectors have been proposed since the early 1990s\", \"In a recent paper, Blalock & Guttag (2021) use learning techniques to refine known approximate algorithms for matrix multiplication.\"**. Basic LST, GRU, and a variant of Transformer (Universal Transformer) are experimented in the Supplimentary. But the line-to-line comparison is missing, which is not easy to compare. \n- The Related work is too short. There are various related and previous works in dealing with mathematical, combinational problems using Deep neural networks, RNNs, etc. For example, the pointer network [R1] was proposed to solve the convex hull and TSP problems. \n- I wonder about the potential value and usage of the proposed algorithm. Of course, some investigations and research tries are encouraged and need not necessarily surpass all existing algorithms/packages, if some insights can be given. In this paper, I did not see the real value of using Transformer to solve linear algebra problems, e.g. efficiency? large-scale capability? Moreover, all the experiments are with very small-scale matrices ($5\\times 5$ to $20\\times 20$). On such a small scale, one can even manually compute these results without any computer aids. \n- For the more difficult SVD and eigenvector problem, this paper can only deal with the $5\\times 5$ or $4\\times 4$ scale, which is far from the real application. But the simple addition/transpose/multiplication only involves add/multiply operations, which are quite easy to solve and parallel in a deep learning era. \n- For the precision, three significant digits in the mantissa are utilized. This is relatively small. Are there any other comparison methods/algorithms? \n- How about the inference time? Is it comparable to or faster than existing numerical packages? \n\n\n\n\n\n[R1] Vinyals, Oriol, Meire Fortunato, and Navdeep Jaitly. \"Pointer networks.\" Advances in neural information processing systems 28 (2015).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the numerical approximation of nine linear algebra problems, utilizing the Transformer. \n\nFor effective problem representation, four encoding schemes are proposed to represent real numbers in a matrix. \n\nRandom matrices and their corresponding solutions to each problem have been generated as the training data for Transformer. On small size (e.g. from 5$\\times$5 to 20$\\times$20) matrices, the Transformer architecture achieved high accuracy under the pre-defined error thresholds. \n\nMoreover, noisy input and out-of-domain distributions are studied to show the robustness of the Transformer in dealing with generalization issues. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- More related work and a thorough comparison with existing works are encouraged. \n- More baselines are suggested. \n- The real value and potential application should be detailed. \n- How about the inference time for different problems? \n\nFor more questions, please refer to the above weaknesses. ", "broader_impact_concerns": "I do not have the concerns about this paper. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear Authors and Reviewers,

Thank you all for the hard work and for having engaged in the discussions. The outcome of the discussions lead all three reviewers to recommend rejection. Nevertheless, I have decided to recommend to ACCEPT the paper, and below I explain the reasons for that decision that goes against the reviewers consensus.

I recall the TMLR Editorial Policies found here: https://jmlr.org/tmlr/editorial-policies.html The present paper adresses a problem related to the third point in the TMLR scope: "accounts of applications of existing techniques that shed light on the strengths and weaknesses of the methods"

In the TMLR guidelines, it is explained that the acceptance or not of a paper is set by the answer to two main questions:

    Are the claims made in the submission supported by accurate, convincing and clear evidence? I believe the numerical experiments are extensive and convincing.

    Would some individuals in TMLR's audience be interested in the findings of this paper? I believe so, as some of the reviewers also pointed out)

In the present case, despite the paper does not give an answer nor true insights to the "why" (as raised by all reviewers and I agree with them), it nevertheless convincingly shows that Transformers are not at the moment really appropriate for linear algebra tasks; so this paper "accounts applications of existing techniques that shed light on weaknesses of the methods" Indeed, despite some encouraging results on their learning capabilities, I agree with the reviewers that the sizes of the instances studied here and the number of training examples needed to reach results that are far from being on-par with standard linear algebra packages, lead me to concluding that Transformers are not competitive. Concerning the comments by some reviewers on trying to achieve almost 100% accuracy for linear algebra problems of small sizes: the fact that this is not the case despite the large data sets employed here is in itself a relevant observation, potentially surprising given the power of Transformers on some other seemingly more complex tasks, so I do not see that as a negative point of the paper. So from a certain perspective these are results in themselves backed up by extensive numerical tests (criteria 1) that may trigger interest in some of the TMLR audience (criteria 2) on "why is that the case?" and "how to improve this?". So overall I believe that in spite of the valid and meaningful concerns raised by the reviewer, both TMLR criteria are met and so the paper deserves publication.

Decision: Accept (poster)