Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences

Yifan Chen; Qi Zeng; Dilek Hakkani-Tur; Di Jin; Heng Ji; Yun Yang

Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences

Yifan Chen, Qi Zeng, Dilek Hakkani-Tur, Di Jin, Heng Ji, Yun Yang

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (Scopus)

Abstract

Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. To address this limitation, Linformer and Informer reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection, respectively. These two models are intrinsically connected, and to understand their connection we introduce a theoretical framework of matrix sketching. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention with column sampling, adaptive row normalization and pilot sampling reutilization. Experiments on the Long Range Arena benchmark demonstrate that our methods outperform alternatives with a consistently smaller time/space footprint.

Original language	English
Title of host publication	Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics
Subtitle of host publication	Human Language Technologies
Publisher	Association for Computational Linguistics (ACL)
Pages	5187-5199
Number of pages	13
ISBN (Electronic)	9781955917711
Publication status	Published - Jul 2022
Event	2022 Conference of the North American Chapter of the Association for Computational Linguistics, NAACL 2022 - Virtual, Seattle, United States Duration: 10 Jul 2022 → 15 Jul 2022 https://2022.naacl.org/ (Conference website)

Conference

Conference	2022 Conference of the North American Chapter of the Association for Computational Linguistics, NAACL 2022
Country/Territory	United States
City	Seattle
Period	10/07/22 → 15/07/22
Internet address	https://2022.naacl.org/ (Conference website)

Scopus Subject Areas

Computer Networks and Communications
Hardware and Architecture
Information Systems
Software

Cite this

Chen, Y., Zeng, Q., Hakkani-Tur, D., Jin, D., Ji, H., & Yang, Y. (2022). Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics : Human Language Technologies (pp. 5187-5199). Association for Computational Linguistics (ACL).

@inproceedings{9f04978d69a34f01adeaaa4e5390b616,

title = "Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences",

abstract = "Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. To address this limitation, Linformer and Informer reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection, respectively. These two models are intrinsically connected, and to understand their connection we introduce a theoretical framework of matrix sketching. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention with column sampling, adaptive row normalization and pilot sampling reutilization. Experiments on the Long Range Arena benchmark demonstrate that our methods outperform alternatives with a consistently smaller time/space footprint.",

author = "Yifan Chen and Qi Zeng and Dilek Hakkani-Tur and Di Jin and Heng Ji and Yun Yang",

note = "We thank the anonymous reviewers for their helpful suggestions. This research is based upon work supported by U.S. NSF grant DMS-1810831, DARPA AIDA Program No. FA8750-18-2-0014 and U.S. DARPA KAIROS Program No. FA8750-19-2-1004. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein. Publisher Copyright: {\textcopyright} 2022 Association for Computational Linguistics.; 2022 Conference of the North American Chapter of the Association for Computational Linguistics, NAACL 2022 ; Conference date: 10-07-2022 Through 15-07-2022",

year = "2022",

month = jul,

language = "English",

pages = "5187--5199",

booktitle = "Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics",

publisher = "Association for Computational Linguistics (ACL)",

address = "United States",

url = "https://2022.naacl.org/",

}

Chen, Y, Zeng, Q, Hakkani-Tur, D, Jin, D, Ji, H & Yang, Y 2022, Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences. in Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics : Human Language Technologies. Association for Computational Linguistics (ACL), pp. 5187-5199, 2022 Conference of the North American Chapter of the Association for Computational Linguistics, NAACL 2022, Seattle, Washington, United States, 10/07/22.

Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences. / Chen, Yifan; Zeng, Qi; Hakkani-Tur, Dilek et al.
Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics : Human Language Technologies. Association for Computational Linguistics (ACL), 2022. p. 5187-5199.

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences

AU - Chen, Yifan

AU - Zeng, Qi

AU - Hakkani-Tur, Dilek

AU - Jin, Di

AU - Ji, Heng

AU - Yang, Yun

N1 - We thank the anonymous reviewers for their helpful suggestions. This research is based upon work supported by U.S. NSF grant DMS-1810831, DARPA AIDA Program No. FA8750-18-2-0014 and U.S. DARPA KAIROS Program No. FA8750-19-2-1004. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein. Publisher Copyright: © 2022 Association for Computational Linguistics.

PY - 2022/7

Y1 - 2022/7

N2 - Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. To address this limitation, Linformer and Informer reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection, respectively. These two models are intrinsically connected, and to understand their connection we introduce a theoretical framework of matrix sketching. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention with column sampling, adaptive row normalization and pilot sampling reutilization. Experiments on the Long Range Arena benchmark demonstrate that our methods outperform alternatives with a consistently smaller time/space footprint.

AB - Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. To address this limitation, Linformer and Informer reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection, respectively. These two models are intrinsically connected, and to understand their connection we introduce a theoretical framework of matrix sketching. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention with column sampling, adaptive row normalization and pilot sampling reutilization. Experiments on the Long Range Arena benchmark demonstrate that our methods outperform alternatives with a consistently smaller time/space footprint.

UR - http://www.scopus.com/inward/record.url?scp=85138342119&partnerID=8YFLogxK

UR - https://aclanthology.org/2022.naacl-main.381/

M3 - Conference proceeding

AN - SCOPUS:85138342119

SP - 5187

EP - 5199

BT - Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics

PB - Association for Computational Linguistics (ACL)

T2 - 2022 Conference of the North American Chapter of the Association for Computational Linguistics, NAACL 2022

Y2 - 10 July 2022 through 15 July 2022

ER -

Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences

Abstract

Conference

Scopus Subject Areas

Other files and links

Fingerprint

Cite this