Elamur Research⌕
☰
home / papers / 2022 / FNet: Mixing Tokens with Fourier Transforms

FNet: Mixing Tokens with Fourier Transforms

Summary

The authors ask whether the self-attention sublayers of a Transformer encoder are truly necessary, or whether cheaper token-mixing operations can replace them. They first swap attention for two learned dense matrix multiplications, one acting along the sequence and one along the hidden dimension. Because this already works well, they move to fast structured linear maps and find that a standard Fourier Transform, which has no trainable weights, performs almost as well as dense mixing. The resulting model, FNet, is compared with BERT on GLUE and with efficient Transformers on the Long Range Arena (LRA) benchmark.

On GLUE, FNet reaches 92% of BERT-Base accuracy and 97% of BERT-Large accuracy at 512 tokens. Its training is also quicker, by roughly 80% on GPUs and 70% on TPUs. On LRA, its accuracy is close to the strongest efficient models, while it runs faster and uses less memory. These results suggest that, for at least some text classification tasks, attention may not be what makes Transformers work. Searching for new mixing mechanisms could therefore be more productive than approximating attention more cleverly.

Key points

  • The Fourier sublayer is computed either with the FFT (Cooley–Tukey, O(N log N)) or by multiplying by the DFT (Vandermonde) matrix. It has no learnable parameters.
  • On GLUE, FNet reaches 92% of BERT-Base and 97% of BERT-Large accuracy. Hybrid variants that replace only the final two Fourier sublayers with self-attention reach 97–99% of BERT while staying 40–70% faster.
  • LRA GPU training speed:
    • At 512 tokens, FNet runs 43 steps/s versus 21 for the Transformer (2.0x).
    • At 2048 tokens, the speedup grows to 3.2x, and peak memory is 2.2 GB versus 12.2 GB.
    • At 8192 tokens, FNet still trains (7.4 GB), while the Transformer runs out of memory from 4096 onward.
  • LRA GPU inference on the Text task at length 4096 takes 43 ms per batch for FNet versus 244 ms for the Transformer (5.7x). FNet also outpaces Performer, the fastest efficient Transformer evaluated.
  • On TPUs, FNet is fastest only at shorter lengths; the models that beat it at long lengths are less accurate. No model solves Path-X.

Interesting ideas

  • I1. Fixed transform as a probe. Swapping a costly learned component for a fixed, parameter-free operation shows how much that component actually contributes. This kind of ablation could be run on any architecture before investing in more elaborate variants.
  • I2. Sparse use of expensive layers. Keeping attention only in the last couple of layers recovers most of the accuracy at a fraction of the cost. This gives a simple speed–accuracy dial that could suit resource-limited deployments, for example NLP models for lower-resource languages.
  • I3. Measure real costs, not just complexity. The paper benchmarks wall-clock speed and peak memory on actual hardware rather than relying on asymptotic complexity. Large hidden constants can make a theoretically linear method slower in practice, so any efficiency claim should be checked this way.
  • I4. Choose the implementation per hardware. The same transform can be computed by FFT or by plain matrix multiplication, and which is faster depends on the device and sequence length (GPU vs TPU). Keeping both implementations is a cheap way to tune throughput.
  • I5. Small mixing models as distilled students. Because small FNet models compare well with Transformers on speed and accuracy, the authors propose distilling them from large Transformer teachers. This could be a lightweight route to production or edge deployment.

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: Natural language processing

Cited by

74 papers of our library cite it (of the 140884 whose bibliographies we read); 2 of them have a page here, 72 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2022.naacl-main.319

@inproceedings{leethorp2022fnet,
  title = {{FNet: Mixing Tokens with Fourier Transforms}},
  author = {Lee-Thorp, James and Ainslie, Joshua and Eckstein, Ilya and Ontañón, Santiago},
  booktitle = {Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies},
  year = {2022},
  doi = {10.18653/v1/2022.naacl-main.319},
  url = {https://doi.org/10.18653/v1/2022.naacl-main.319}
}

References

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

  1. Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. 2021. Rethinking attention with performers. In 9th International… find
  2. Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. 2020. Etc: Encoding long and structured inputs in transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processi… find our card
  3. Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. 2019. What does BERT look at? an analysis of BERT’s attention. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 276–286, Florence, Italy. Association for Computationa… find
  4. Andrew R Barron. 1993. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory, 39(3):930–945. find
  5. James W Cooley and John W Tukey. 1965. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):297– 301. find
  6. Iz Beltagy, Matthew E Peters, and Arman Cohan. 2020. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150. find
  7. George Cybenko. 1989. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303–314. find
  8. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chri… find
  9. 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. 2021. An image is worth 16x16 words: Transformers for image recognition at scale. In 9th In… find
  10. Hazem M El-Bakry and Qiangfu Zhao. 2004. Fast object/face detection using neural networks and fast fourier transform. International Journal of Signal Processing, 1(3):182–187. find
  11. Matteo Frigo and Steven G Johnson. 2005. The design and implementation of fftw3. Proceedings of the IEEE, 93(2):216–231. find
  12. Kfir Goldberg, Stav Shapiro, Elad Richardson, and Shai Avidan. 2020. Rethinking fun: Frequency-domain utilization networks. arXiv preprint arXiv:2012.03357. — [arXiv:2012.03357](https://arxiv.org/abs/2012.03357) find
  13. Himanshu Gothwal, Silky Kedawat, Rajesh Kumar, et al. 2011. Cardiac arrhythmias detection in an ecg beat signal using fast fourier transform and artificial neural network. Journal of Biomedical Science and Engineering, 4(04):289. find
  14. Mandy Guo, Joshua Ainslie, David Uthus, Santiago Ontanon, Jianmo Ni, Yun-Hsuan Sung, and Yinfei Yang. 2021. Longt5: Efficient text-to-text transformer for long sequences. arXiv preprint arXiv:2112.07916. find our card
  15. John Hewitt and Percy Liang. 2019. Designing and interpreting probes with control tasks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 2733–2743, Hong Kong, Chi… find
  16. Tyler Highlander and Andres Rodriguez. 2015. Very efficient training of convolutional neural networks using fast fourier transform and overlap-and-add. In Proceedings of the British Machine Vision Conference 2015, BMVC 2015, Swansea, UK, September 7-10, 2015, pages 160.1–160.9. BMVA Press. find
  17. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. 2020. Transformers are rnns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pages 5156–5165. PMLR. find
  18. Young Jin Kim and Hany Hassan. 2020. FastFormers: Highly efficient transformer models for natural language understanding. In Proceedings of SustaiNLP: Workshop on Simple and Efficient Natural Language Processing, pages 149–158. Association for Computational Linguistics. find
  19. Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. 2020. Reformer: The efficient transformer. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. find our card
  20. Renée Koplon and Eduardo D Sontag. 1997. Using fourier-neural recurrent networks to fit sequential input/output data. Neurocomputing, 15(3-4):225–248. find
  21. Taku Kudo and John Richardson. 2018. SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 66–71, Brussels, Belgium. Associ… find our card
  22. Henry O. Kunz. 1979. On the equivalence between one-dimensional discrete walsh-hadamard and multidimensional discrete fourier transforms. IEEE Computer Architecture Letters, 28(03):267–268. find
  23. Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. 2021. Gshard: Scaling giant models with conditional computation and automatic sharding. In 9th International Conference on Learning Representations, ICLR 2021, Virtual… find
  24. Zongyi Li, Nikola Borislavov Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew M. Stuart, and Anima Anandkumar. 2021. Fourier neural operator for parametric partial differential equations. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Even… find
  25. Andrei Ivanov, Nikoli Dryden, Tal Ben-Nun, Shigang Li, and Torsten Hoefler. 2020. Data movement is all you need: A case study of transformer networks. arXiv preprint arXiv:2007.00072. find
  26. Sheng Lin, Ning Liu, Mahdi Nazemi, Hongjia Li, Caiwen Ding, Yanzhi Wang, and Massoud Pedram. 2018. Fft-based deep learning deployment in embedded systems. In 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1045–1050. IEEE. find
  27. Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. 2020. TinyBERT: Distilling BERT for natural language understanding. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 4163–4174. Association for Computational Linguistics. find
  28. Peter J. Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. 2018. Generating wikipedia by summarizing long sequences. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Pr… find our card
  29. Michael Mathieu, Mikael Henaff, and Yann LeCun. 2014. Fast training of convolutional networks through ffts: International conference on learning representations (iclr2014), cbls, april 2014. In 2nd International Conference on Learning Representations, ICLR 2014. find
  30. Kei-ichiro Minami, Hiroshi Nakajima, and Takeshi Toyoshima. 1999. Real-time discrimination of ventricular tachyarrhythmia with fourier-transform neural network. IEEE transactions on Biomedical Engineering, 46(2):179–185. find
  31. Martina Mironovova and Jirí Bíla. 2015. Fast fourier transform for feature extraction and neural network for classification of electrocardiogram signals. In 2015 Fourth International Conference on Future Generation Communication Technology (FGCT), pages 1–6. IEEE. find
  32. Marcin Moczulski, Misha Denil, Jeremy Appleyard, and Nando de Freitas. 2016. ACDC: A structured efficient linear layer. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings. find
  33. Sharan Narang, Hyung Won Chung, Yi Tay, Liam Fedus, Thibault Fevry, Michael Matena, Karishma Malkan, Noah Fiedel, Noam Shazeer, Zhenzhong Lan, Yanqi Zhou, Wei Li, Nan Ding, Jake Marcus, Adam Roberts, and Colin Raffel. 2021. Do transformer modifications transfer across implementations and application… find
  34. Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. 2018. Image transformer. In International Conference on Machine Learning, pages 4055–4064. PMLR. find
  35. Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A. Smith, and Lingpeng Kong. 2021. Random feature attention. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. find
  36. Harry Pratt, Bryan Williams, Frans Coenen, and Yalin Zheng. 2017. Fcnn: Fourier convolutional neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 786–798. Springer. find
  37. Jiezhong Qiu, Hao Ma, Omer Levy, Wen-tau Yih, Sinong Wang, and Jie Tang. 2020. Blockwise self-attention for long document understanding. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2555–2565. Association for Computational Linguistics. find
  38. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1–67. find
  39. Alessandro Raganato, Yves Scherrer, and Jörg Tiedemann. 2020. Fixed encoder self-attention patterns in transformer-based machine translation. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 556–568. Association for Computational Linguistics. find
  40. Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Lukas Gruber, Markus Holzleitner, Thomas Adler, David P. Kreil, Michael K. Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. 2021. Hopfield networks is all you need. In 9th International Conference o… find
  41. Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. 2021. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53–68. find our card
  42. Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01108. find
  43. Noam Shazeer. 2019. Fast transformer decoding: One write-head is all you need. arXiv preprint arXiv:1911.02150. find
  44. Sam Shleifer and Alexander M Rush. 2020. Pre-trained summarization distillation. arXiv preprint arXiv:2010.13002. — [arXiv:2010.13002](https://arxiv.org/abs/2010.13002) find
  45. Vikas Sindhwani, Tara N Sainath, and Sanjiv Kumar. 2015. Structured transforms for small-footprint deep learning. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 2, pages 3088–3096. find
  46. Alex Tamkin, Dan Jurafsky, and Noah Goodman. 2020. Language through a prism: A spectral approach for multiscale language representations. In Advances in Neural Information Processing Systems, volume 33, pages 5492–5504. Curran Associates, Inc. find
  47. Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. 2020a. Synthesizer: Rethinking self-attention in transformer models. arXiv preprint arXiv:2005.00743. — [arXiv:2005.00743](https://arxiv.org/abs/2005.00743) find
  48. Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. 2020b. Sparse sinkhorn attention. In International Conference on Machine Learning, pages 9438–9447. PMLR. find
  49. Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. 2021a. find
  50. Long range arena : A benchmark for efficient transformers. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. find our card
  51. Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. 2020c. Efficient transformers: A survey. arXiv preprint arXiv:2009.06732. find our card
  52. Yi Tay, Mostafa Dehghani, Jai Prakash Gupta, Vamsi Aribandi, Dara Bahri, Zhen Qin, and Donald Metzler. 2021b. Are pretrained convolutions better than pretrained transformers? In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint C… find
  53. Ian Tenney, Dipanjan Das, and Ellie Pavlick. 2019. BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4593– 4601, Florence, Italy. Association for Computational Linguistics. find our card
  54. Ilya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. 2021. Mlp-mixer: An all-mlp architecture for vision. Advances in Neural Information Processing Systems, 34. find
  55. Iulia Turc, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Well-read students learn better: On the importance of pre-training compact models. arXiv preprint arXiv:1908.08962. find our card
  56. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems, 30. find
  57. Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. 2018. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 353–355,… find our card
  58. Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. 2020. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768. find
  59. Weiqiu You, Simeng Sun, and Mohit Iyyer. 2020. Hard-coded Gaussian attention for neural machine translation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7689–7700. Association for Computational Linguistics. find
  60. Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. 2020. Big bird: Transformers for longer sequences. Advances in Neural Information Processing Systems, 33:17283–17297. find our card
  61. Jiong Zhang, Yibo Lin, Zhao Song, and Inderjit Dhillon. 2018. Learning long term dependencies via fourier recurrent units. In International Conference on Machine Learning, pages 5815–5823. PMLR. find
  62. Y Zhang and Lai-Wan Chan. 2000. Forenet: fourier recurrent networks for time series prediction. In 7th International Conference on Neural Information Processing (ICONIP 2000), pages 576–582. find
  63. Zhenyou Zhang, Yi Wang, and Kesheng Wang. 2013. Fault diagnosis and prognosis using wavelet packet decomposition, fourier transform and artificial neural network. Journal of Intelligent Manufacturing, 24(6):1213–1227. find
  64. Jesse Vig and Yonatan Belinkov. 2019. Analyzing the structure of attention in a transformer language model. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 63–76, Florence, Italy. Association for Computational Linguistics. find our card
  65. Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. 2019. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5797–5808, Florence, I… find our card
  66. Apoorv Vyas, Angelos Katharopoulos, and François Fleuret. 2020. Fast transformers with clustered attention. Advances in Neural Information Processing Systems, 33:21665–21674. *Table 5: Loss and accuracy pre-training metrics on TPUs. The GPU metrics are very similar. “B” denotes Base, “L” is Large an… find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/thorp-2022-fnet-mixing-tokens-fourier-transforms/