BigBird Causal Attention
Author: JamesDeAntonis
Pull request: no

# 🚀 Feature request

I'd like to use bigbird sparse attention in a decoder.  Isn't that feasible if we apply a causal mask [here](https://github.com/huggingface/transformers/blob/master/src/transformers/models/big_bird/modeling_big_bird.py#L665)?

So long as we know which entries correspond to (i, j) entries where i < j, we could apply a mask there which would do the trick.  Do you agree?

## Motivation

This would allow use of sparse attention in decoder setting as well as encoder

## Your contribution

I would be happy to try to tackle this, so long as people agree with my logic


Comments:
Pinging @vasudevgupta7 and @patrickvonplaten 

There are several issues, we will have to keep in mind before we decide to implement bigbird block sparse attention in decoder.

1) Initial number of tokens in decoder side must be > `5 x block_size + 2 x num_random_blocks x block_size` (for bigbird block sparse attention to work). Typically `block_size=64`, `num_random_blocks=3`, then we need at least 708 tokens initially.
2) I am assuming your task involves at least 1024 tokens in decoder side. Since, else it is recommended to use `original_full` attention by authors.
3) Also, if model is given 1024 tokens (block size = 64 let's say), then for predicting 1025th token, model will first `<pad>` to 1024 + 64 tokens, since this attention will work only when sequence length is multiple of block size. & similarly for predicting every single token, we will have to pad again & again. This way inference can become expensive, I believe.
4) Also, if you want to use Encoder-Decoder model, we will have to write block sparse attention in cross-attention completely. Else cross-attention layer will be very expensive if both encoder & decoder are given very long sequences.

Yeah training decoder in the bigbird block sparse attention fashion is possible if we just change masks in this [line](https://github.com/huggingface/transformers/blob/3d339ee6595b9e42925559ae21a0f6e77f032873/src/transformers/models/big_bird/modeling_big_bird.py#L2119). But again, there are several issues:

5) Currently, we have 1st & last block as global. So, if we mask for autoregressive, we will have only 1st block as global during training.
6) Because of masking all the right tokens, we will reduce number of random tokens which were chosen from the complete sequence earlier.
7) Sliding tokens will also reduce by half. 

So, this way number of tokens which each query can attend, will be reduced by large amount. 5,6,7 can be resolved if we decide to implement modify a lot in current block sparse attention (instead of just changing masks). But 1,2,3,4 are still a problem.

There may be several other issues. But these are my initial thoughts on this. Let me know if I am unclear or wrong somewhere.

Thanks for the response!  I was on vacation when you posted and am coming back to this now.

>Initial number of tokens in decoder side must be > 5 x block_size + 2 x num_random_blocks x block_size (for bigbird block sparse attention to work). Typically block_size=64, num_random_blocks=3, then we need at least 708 tokens initially.
I am assuming your task involves at least 1024 tokens in decoder side. Since, else it is recommended to use original_full attention by authors.
Also, if model is given 1024 tokens (block size = 64 let's say), then for predicting 1025th token, model will first <pad> to 1024 + 64 tokens, since this attention will work only when sequence length is multiple of block size. & similarly for predicting every single token, we will have to pad again & again. This way inference can become expensive, I believe.

Yes, we are using a large input size so the motivation to implement causal is there regardless.

I see how there is a minimum threshold input size below which BigBird is obsolete.  That said, even in that case, hyper-parameters could be tweaked such as decreasing block size and number of random blocks.  Not to mention, this minimum threshold applies to other efficient attention algos as well such as performer.

>Also, if you want to use Encoder-Decoder model, we will have to write block sparse attention in cross-attention completely. Else cross-attention layer will be very expensive if both encoder & decoder are given very long sequences.

Are you saying that BigBird is not possible in cross attention?  Could use some more color on this.

>Currently, we have 1st & last block as global. So, if we mask for autoregressive, we will have only 1st block as global during training.
Because of masking all the right tokens, we will reduce number of random tokens which were chosen from the complete sequence earlier.
Sliding tokens will also reduce by half.

The attention mask is applied after computing the sparse attention matrix, so doesn't the full global attention piece still pull weight? 


> Thanks for the response! I was on vacation when you posted and am coming back to this now.
> 
> > Initial number of tokens in decoder side must be > 5 x block_size + 2 x num_random_blocks x block_size (for bigbird block sparse attention to work). Typically block_size=64, num_random_blocks=3, then we need at least 708 tokens initially.
> > I am assuming your task involves at least 1024 tokens in decoder side. Since, else it is recommended to use original_full attention by authors.
> > Also, if model is given 1024 tokens (block size = 64 let's say), then for predicting 1025th token, model will first  to 1024 + 64 tokens, since this attention will work only when sequence length is multiple of block size. & similarly for predicting every single token, we will have to pad again & again. This way inference can become expensive, I believe.
> 
> Yes, we are using a large input size so the motivation to implement causal is there regardless.
> 
> I see how there is a minimum threshold input size below which BigBird is obsolete. That said, even in that case, hyper-parameters could be tweaked such as decreasing block size and number of random blocks. Not to mention, this minimum threshold applies to other efficient attention algos as well such as performer.
> 
> > Also, if you want to use Encoder-Decoder model, we will have to write block sparse attention in cross-attention completely. Else cross-attention layer will be very expensive if both encoder & decoder are given very long sequences.
> 
> Are you saying that BigBird is not possible in cross attention? Could use some more color on this.

It might be possible to implement as cross-attention if we think something but major problem will that:
For bigbird block sparse attention to work, this must hold `query sequence length // block size == key sequence length // block size`. Now this can be managed during training but during inference, I am not sure if we can.

> 
> > Currently, we have 1st & last block as global. So, if we mask for autoregressive, we will have only 1st block as global during training.
> > Because of masking all the right tokens, we will reduce number of random tokens which were chosen from the complete sequence earlier.
> > Sliding tokens will also reduce by half.
> 
> The attention mask is applied after computing the sparse attention matrix, so doesn't the full global attention piece still pull weight?

During training, we will have to mask the last global block right; so they won't contribute to the context layer & effectively global tokens will reduce by half.


pinging @patrickvonplaten for putting some light on this issue.


Thanks for the issue & the detailed answer @vasudevgupta7. To be honest, I just don't think it's worth yet to do any kind of sparse attention on neither the cross_attention layers nor the decoder attention layers because the output is usually quite small (think summarization, question_answering). For tasks like translation, it's often better to split per sentence anyways so here it also doesn't make too much sense. => Overall IMO, this is low priority

This issue has been automatically marked as stale because it has not had recent activity. If you think this still needs to be addressed please comment on this thread.

Please note that issues that do not follow the [contributing guidelines](https://github.com/huggingface/transformers/blob/master/CONTRIBUTING.md) are likely to be ignored.