2026-09-21T12:00:23Zhttps://api.repository.cam.ac.uk/server/oai/request

oai:www.repository.cam.ac.uk:1810/3493932023-12-22T13:31:21Zcom_1810_213729com_1810_256065col_1810_219485

Random Features for Efficient Attention Approximation https://doi.org/10.17863/CAM.96501 Likhosherstov, Valerii Weller, Adrian Transformers are, perhaps, the most widespread architectures in today's landscape of deep learning. They, however, do not scale well with long sequences, resulting in O(L^2) computational complexity for the sequence length L. In this thesis, we propose a holistic approach for reducing this complexity to linear O(L) via an unbiased approximation of the softmax kernel appearing in self-attention, the main component in the Transformer backbone. The obtained efficient Transformer architecture is referred to as Performer. Compared to other developments in the area of efficient Transformers, Performer is theory-grounded and the problem of long-sequence processing can be reduced to a theoretical derivation of random features with certain properties minimizing the variance of the approximation. This thesis describes an evolution of mechanisms for random-feature approximation: from the so-called FAVOR, to FAVOR+ and, finally, to FAVOR++. The FAVOR++ mechanism has the tightest concentration properties and the best performance in practice. On the way to FAVOR++, we also discuss several extensions of the proposed efficient self-attention mechanism, among which are masked self-attention, sub-linear memory Performers, generalized attention, and more. For each proposed method, this thesis contains empirical evaluations in real-life large-scale learning setups and thorough theoretical analyses with proofs. University of Cambridge 2022-12-01 Thesis Doctoral Doctor of Philosophy (PhD) eng Cambridge University Department of Engineering and Cambridge Trust https://www.repository.cam.ac.uk/handle/1810/349393 https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/7a2e8fbd-a502-47c3-9ce5-20d7d9640bcc/download 671700c6e9ad52eaab165ce4c28451ce https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6aae78a5-080c-4b06-aca4-0db634b88daf/download 87eda9de84448d1f82354d60eee3eb5f https://www.rioxx.net/licenses/all-rights-reserved/ deep learning self-attention Transformer networks