title: Faster Causal Attention Over Large Sequences Through Sparse Flash
    Attention
summary: Transformer-based language models have found many diverse applications
  requiring them to process sequences of increasing length. For these
  applications, the causal self-attention -- which is the only component scaling
  quadratically w.r.t. the sequence length -- becomes a central concern. While
  many works have proposed schemes to sparsify the attention patterns and reduce
  the computational overhead of self-attention, those are often limited by
  implementations concerns and end up imposing a simple and static structure over
  the attention matrix. Conversely, implementing more dynamic sparse attentions
  often results in runtimes significantly slower than computing the full
  attention using the Flash implementation from Dao et al. (2022). We extend
  FlashAttention to accommodate a large class of attention sparsity patterns
  that, in particular, encompass key/query dropping and hashing-based attention.
  This leads to implementations with no computational complexity overhead and a
  multi-fold runtime speedup on top of FlashAttention. Even with relatively low
  degrees of sparsity, our method improves visibly upon FlashAttention as the
  sequence length increases. Without sacrificing perplexity, we increase the
  training speed of a transformer language model by 2.0times and 3.3times
  for sequences of respectively 8k and 16k tokens.
paper_authors._id: 647d50f383cdb93baf7764e5
paper_authors.name: Matteo Pagliardini
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2023-06-06T08:40:20.242Z
paper_authors._id: 647e2802e4d52fe0e01f1f33
paper_authors.avatarUrl: /avatars/38a6c66bce327eded16993932b62986b.svg
paper_authors.fullname: Matteo Pagliardini
paper_authors.type: user
paper_authors.user: MatPag
paper_authors._id: 647d50f383cdb93baf7764e6
paper_authors.name: Daniele Paliotta
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2023-06-05T10:07:14.332Z
paper_authors._id: 6213d73ecf7928035e813503
paper_authors.avatarUrl: /avatars/62c0fd60b1219697af0b07e175a48260.svg
paper_authors.fullname: Daniele Paliotta
paper_authors.type: user
paper_authors.user: dpstart
paper_authors._id: 647d50f383cdb93baf7764e7
paper_authors.name: Martin Jaggi
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2023-11-08T16:45:13.779Z
paper_authors._id: 654baf61d625e083383dfd00
paper_authors.avatarUrl: /avatars/e933b2b9d7226e9bb72f77916c2be4f1.svg
paper_authors.fullname: Martin Jaggi
paper_authors.type: user
paper_authors.user: mjaggi
paper_authors._id: 647d50f383cdb93baf7764e8
paper_authors.name: François Fleuret
paper_authors.status: extracted_pending
paper_authors.statusLastChangedAt: 2023-08-22T16:03:24.882Z
paper_authors._id: 6318c37e69ef5467e18fc63f
paper_authors.avatarUrl: /avatars/7f1ac593608a89926f4107b4c3dd91d4.svg
paper_authors.fullname: François Fleuret
paper_authors.type: user
paper_authors.user: francoisfleuret
paper_title: Faster Causal Attention Over Large Sequences Through Sparse Flash
    Attention
paper_summary: Transformer-based language models have found many diverse applications
  requiring them to process sequences of increasing length. For these
  applications, the causal self-attention -- which is the only component scaling
  quadratically w.r.t. the sequence length -- becomes a central concern. While
  many works have proposed schemes to sparsify the attention patterns and reduce
  the computational overhead of self-attention, those are often limited by
  implementations concerns and end up imposing a simple and static structure over
  the attention matrix. Conversely, implementing more dynamic sparse attentions
  often results in runtimes significantly slower than computing the full
  attention using the Flash implementation from Dao et al. (2022). We extend
  FlashAttention to accommodate a large class of attention sparsity patterns
  that, in particular, encompass key/query dropping and hashing-based attention.
  This leads to implementations with no computational complexity overhead and a
  multi-fold runtime speedup on top of FlashAttention. Even with relatively low
  degrees of sparsity, our method improves visibly upon FlashAttention as the
  sequence length increases. Without sacrificing perplexity, we increase the
  training speed of a transformer language model by 2.0times and 3.3times
  for sequences of respectively 8k and 16k tokens.
paper_ai_keywords: causal self-attention attention patterns computational overhead key/query dropping hashing-based attention FlashAttention computational complexity runtime speedup perplexity transformer language model