Elamur Research⌕
☰
home / papers / 2021 / Linear algebra with transformers

Linear algebra with transformers

Paper · 2021 · François Charton

Summary

Earlier research suggested that sequence models handle numerical work poorly: they struggle with arithmetic and fail outside their training distribution. François Charton (Meta AI) asks whether small transformers can learn numerical linear algebra purely from examples. He selects nine tasks of increasing difficulty: transposition, addition, matrix-vector and matrix-matrix products, eigenvalues, eigenvectors, singular values, SVD and inversion.

Training data consists of random matrices, mostly 5×5, generated on the fly, with solutions computed by NumPy linalg and rounded to three significant digits. Real numbers are turned into tokens using one of four schemes: P10, P1000, B1999 and FP15. The models are standard encoder-decoder transformers with up to 6 layers. Several of them use lopsided designs with a single-layer encoder or decoder.

On every task, accuracy exceeds 90%, and most tasks pass 99% within a small L1 tolerance. The models also cope with noisy training data. They generalize out of distribution when the training matrices are chosen carefully.

The work does not aim to replace numerical libraries. Its value is in showing that transformers can serve as computational building blocks for AI-for-science.

Key points

  • Number encodings trade sequence length against vocabulary size.
    • P10 uses 5 tokens per number with a vocabulary of about 210.
    • FP15 uses 1 token per number with a vocabulary of about 30,000.
    • A 20×20 matrix therefore takes 2002 tokens in P10 but only 402 in FP15.
    • Pairing FP15 inputs with P1000 outputs often gave the best results.
  • Models are small: 512 dimensions, 8 attention heads and 10–50M parameters, trained with Adam. The harder tasks (eigenvectors, SVD, inversion) needed 4 GPUs for 3–7 days.
  • Out-of-distribution generalization is asymmetric.
    • Models trained on symmetric matrices with Laplace-distributed eigenvalues generalize to Wigner matrices and to positive-definite matrices.
    • The reverse fails: training on Wigner matrices does not carry over to those other distributions.
  • Speed lags behind NumPy, and scale is limited.
    • For 5×5 matrices, eigenvalues take 0.5 ms with the model versus 0.07 ms with NumPy; inversion takes 1 ms versus 0.04 ms.
    • Because quadratic attention limits sequence length, the approach probably cannot go beyond about 50×50 dense matrices.
  • Code is public as LAWT at github.com/facebookresearch/LAWT.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

💡 Concepts 1Key ideas and methods explained on our concept pages.Latent semantic indexing · 29 works

Cite

Cite as François Charton. 2021. Linear algebra with transformers. arXiv:2112.01898.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2112.01898 · arXiv 2112.01898

@misc{charton2021linear,
  title = {{Linear algebra with transformers}},
  author = {François Charton},
  year = {2021},
  doi = {10.48550/arxiv.2112.01898},
  eprint = {2112.01898},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2112.01898}
}

References

65 references, 11 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Luca Biggio, Tommaso Bendinelli, Alexander Neitz, Aurelien Lucchi, and Giambattista Parascandolo. Neural symbolic regression that scales. arXiv preprint arXiv:2106.06427, 2021. — [arXiv:2106.06427](https://arxiv.org/abs/2106.06427) find
  2. Davis Blalock and John Guttag. Multiplying matrices without multiplying. arXiv preprint arXiv:2106.10860, 2021. — [arXiv:2106.10860](https://arxiv.org/abs/2106.10860) find
  3. Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quincy Davis, Dora De… — On the Opportunities and Risks of Foundation Models
  4. Roger W Brockett. Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems. Linear Algebra and its applications, 146:79–91, 1991. find
  5. Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks, 2021. find
  6. Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. arXiv preprint arXiv:2005.12872, 2020.
  7. Jacopo Castellini. Learning numeracy: Binary arithmetic with neural turing machines. arXiv preprint arXiv:1904.02478, 2019. — [arXiv:1904.02478](https://arxiv.org/abs/1904.02478) find
  8. François Charton, Amaury Hayat, and Guillaume Lample. Learning advanced mathematical computations from examples. arXiv preprint arXiv:2006.06462, 2020. find
  9. Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509, 2019.
  10. Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078, 2014.
  11. Andrzej Cichocki and Rolf Unbehauen. Neural networks for computing eigenvalues and eigenvectors. Biological Cybernetics, 68(2):155–164, 1992. find
  12. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.
  13. 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.07732, 2021. find
  14. George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303–314, 1989. find
  15. Stéphane d’Ascoli, Pierre-Alexandre Kamienny, Guillaume Lample, and François Charton. Deep symbolic regression for recurrent sequences, 2022. find
  16. A Davies, P Velickovic, L 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. find
  17. Ernest Davis. The use of deep learning for symbolic integration: A review of (lample and charton, 2019). arXiv preprint arxiv:1912.05752, 2019. find
  18. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Łukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018. find
  19. Aurélien Dersy, Matthew D. Schwartz, and Xiaoyuan Zhang. Simplifying polylogarithms with machine learning, 2022. find
  20. Linhao Dong, Shuang Xu, and Bo Xu. Speech-transformer: A no-recurrence sequence-to-sequence model for speech recognition. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5884–5888, 2018. find
  21. 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…
  22. David Finol, Yan Lu, Vijay Mahadevan, and Ankit Srivastava. Deep convolutional neural networks for eigenvalue problems in mechanics. International Journal for Numerical Methods in Engineering, 118(5): 258–275, 2019. find
  23. Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv:1603.08983, 2016. find
  24. Kaden Griffith and Jugal Kalita. Solving arithmetic word problems with transformers and preprocessing of problem text. arXiv preprint arXiv:2106.00893, 2021. — [arXiv:2106.00893](https://arxiv.org/abs/2106.00893) find
  25. Christopher Hahn, Frederik Schmitt, Jens U. Kreber, Markus N. Rabe, and Bernd Finkbeiner. Teaching temporal logics to neural networks. arXiv preprint arXiv:2003.04218, 2021. find
  26. 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. find
  27. Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735–1780, 1997. find
  28. Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251–257, 1991. find
  29. Valerii Iakovlev, Markus Heinonen, and Harri Lähdesmäki. Learning continuous-time pdes from sparse data with graph neural networks, 2020. find
  30. Łukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228, 2015. find
  31. Nal Kalchbrenner, Ivo Danihelka, and Alex Graves. arxiv:1507.01526, 2015. find
  32. Diederik P Kingma and Jimmy Ba. arXiv:1412.6980, 2014.
  33. Adam: A method for stochastic optimization. Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, third edition, 1997. find
  34. Grid long short-term memory. arXiv preprint arXiv preprint Guillaume Lample and François Charton. arXiv:1912.01412, 2019. find
  35. Deep learning for symbolic mathematics. Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with… — Solving Quantitative Reasoning Problems with Language Models
  36. Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.03983, 2016. find
  37. Madan Lal Mehta. Random Matrices. Academic Press, 3rd edition, 2004. find
  38. Yuanliang Meng and Anna Rumshisky. Solving math word problems with double-decoder transformer. arXiv preprint arXiv:1908.10924, 2019. — [arXiv:1908.10924](https://arxiv.org/abs/1908.10924) find
  39. Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2102.13019, 2021. find
  40. Erkki Oja. Principal components, minor components, and linear neural networks. Neural networks, 5(6): 927–935, 1992. find
  41. Theodoros Palamas. Investigating the ability of neural networks to learn simple modular arithmetic. 2017. find
  42. Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03393, 2020.
  43. Victor M. Preciado and M. Amin Rahimian. Moment-based spectral analysis of random graphs with given expected degrees. arXiv preprint arXiv:1512.03489, 2017. — [arXiv:1512.03489](https://arxiv.org/abs/1512.03489) find
  44. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. 2018. find
  45. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019. find
  46. Nikola Samardzija and RL Waterland. A neural network for computing eigenvectors and eigenvalues. Biological Cybernetics, 65(4):211–214, 1991. find
  47. David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. arXiv preprint arXiv:1904.01557, 2019.
  48. 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. find
  49. Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In Doina Precup and Yee Whye Teh (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. find
  50. Feng Shi, Chonghan Lee, Mohammad Khairul Bashar, Nikhil Shukla, Song-Chun Zhu, and Vijaykrishnan Narayanan. Transformer-based machine learning for fast sat solvers and logic synthesis. arXiv preprint arXiv:2107.07116, 2021. — [arXiv:2107.07116](https://arxiv.org/abs/2107.07116) find
  51. Kai-Yeung Siu and Vwani Roychowdhury. Optimal depth neural networks for multiplication and related problems. In S. Hanson, J. Cowan, and C. Giles (eds.), Advances in Neural Information Processing Systems, volume 5. Morgan-Kaufmann, 1992. find
  52. Ying Tang and Jianping Li. Another neural network based approach for computing eigenvalues and eigenvectors of real skew-symmetric matrices. Computers & Mathematics with Applications, 60(5):1385–1392, 2010. find
  53. Andrew Trask, Felix Hill, Scott Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. arXiv preprint arXiv:1808.00508, 2018. arXiv preprint Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention i… find
  54. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks, 2015. find
  55. Apoorv Vyas, Angelos Katharopoulos, and François Fleuret. Fast transformers with clustered attention. arXiv preprint arXiv:2007.04825, 2020. — [arXiv:2007.04825](https://arxiv.org/abs/2007.04825) find
  56. Jun Wang. A recurrent neural network for real-time matrix inversion. Applied Mathematics and Computation, 55(1):89–100, 1993a. find
  57. Jun Wang. Recurrent neural networks for solving linear matrix equations. Computers & Mathematics with Applications, 26(9):23–34, 1993b. find
  58. Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768, 2020a. find
  59. Yongqiang Wang, Abdelrahman 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… find
  60. Sean Welleck, Peter West, Jize Cao, and Yejin Choi. Symbolic brittleness in sequence models: on systematic generalization in symbolic mathematics. arXiv preprint arXiv:2109.13986, 2021. — [arXiv:2109.13986](https://arxiv.org/abs/2109.13986) find
  61. Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models, 2022. find
  62. 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. find
  63. 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 arXiv:2007.14062, 2021.
  64. Wojciech Zaremba, Tomas Mikolov, Armand Joulin, and Rob Fergus. Learning simple algorithms from examples, 2015. find
  65. Yunong Zhang, Weimu Ma, and Binghuang Cai. From zhang neural network to newton iteration for matrix inversion. IEEE Transactions on Circuits and Systems I: Regular Papers, 56(7):1405–1415, 2008. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/charton-2021-linear-algebra-transformers/