Treeformer: Dense Gradient Trees for Efficient Attention Computation

Understand

Standard inference and training with transformer based architectures scale quadratically with input sequence length.

• This is prohibitively large for a variety of applications especially in web-page translation, query-answering etc.
• Consequently, several approaches have been developed recently to speedup attention computation by enforcing different attention structures such as sparsity, low-rank, approximating attention using kernels.
• In this work, we view attention computation as that of nearest neighbor retrieval, and use decision tree based hierarchical navigation to reduce the retrieval cost per query token from linear in sequence length to nearly logarithmic.