Add FAVOR+ / Performer attention
Author: norabelrose
Pull request: yes

## What does this PR do?

Adds support for the Performer / FAVOR+ attention mechanism, as described in the paper "Rethinking Attention with Performers" by Choromanski et al., 2020. Fixes #7675.

## How is it implemented?

Since Performer attention can be an unbiased estimator of traditional softmax attention, and pretrained models can be finetuned to work with it, the general consensus in the discussion on #7675 was that it should not be implemented as a single separate Transformer model. Ideally, we want all or most models in the transformers library to be able to use Performer attention.

In view of this, I've implemented the feature by creating three new classes: `PerformerAttention`, `TFPerformerAttention`, and `PerformerAttentionConfig`. These are implemented in the files `modeling_performer_attention.py`, `modeling_tf_performer_attention.py`, and `configuration_performer_attention.py` respectively in `src/transformers`.

Models are marked as supporting Performer attention by adding the `@supports_performer_attention` class decorator to the corresponding config class. This decorator adds the `attention_type: str` and `performer_attention_config: Optional[Union[dict, PerformerAttentionConfig]]` attributes to the config class, and also adds some boilerplate code to the class's `to_dict()` method to make sure JSON serialization works properly. It also registers the class so that the user can get a full list of Performer attention-supporting models with the function `performer_supporting_models_and_configs()`.

This isn't quite enough to get Performer attention to work for a new model, though. Adding Performer support to a model is inherently a somewhat tedious process, but I've tried to make it less tedious by implementing a `@init_performer_attention()` function decorator which can be added to the `__init__` method on the immediate parent of an attention module within a model— this will initialize either the model's own softmax attention module, or a `PerformerAttention` module, depending on how `attention_type` is set. You can see how this is implemented in `performer_attention_utils.py`.

This is all that you need to do for some models, although others will need a bit of extra work due to idiosyncracies in their implementation. I've already added Performer support to the following models: DistilBERT, BERT, RoBERTa, ELECTRA, LayoutLM, and TAPAS (in both PyTorch and TensorFlow). My hope is that other contributors will add support to other models relatively quickly.

Unit tests can be found in `test_performer_attention.py`. They do an exhaustive grid search of the enum and boolean config options and make sure that none of the 4.6k+ combinations causes a crash or a shape mismatch, and also make sure that the PyTorch and TensorFlow implementations have the same output, within numerical error, under all configurations.

## Rough edges

While I added extensive docstrings to `PerformerAttention` and `PerformerAttentionConfig`, which can be used to generate documentation, I haven't actually made the documentation files themselves. That will have to be left to another contributor, or to my future self— although honestly I've put quite a lot of time into this PR and would like to get on to other projects, so I would really appreciate it if someone else did it.

`PerformerAttention` supports using a custom CUDA kernel from the `fast_transformers` library to implement causally masked attention, although I have never actually been able to test this functionality because I don't have root access to the GPU server I use and therefore can't install NVCC. I'm hoping a reviewer could do that— it's a relatively straightforward feature so if there are any bugs in it it should be pretty easy to fix.

Also, the current code throws some odd linter errors which I haven't been able to figure out how to resolve and which don't seem to be consequential. Something about the code in RoBERTA, LayoutLM, etc. that is marked as being copied from BERT not matching the BERT code exactly. If a reviewer could figure out how to silence that error that would be greatly appreciated.

## Who can review?

@patrickvonplaten commented on #7675 and seemed excited about the PR, so I think he would be a good reviewer for this.

Comments:
@norabelrose Great job! Thanks for letting me know about this :)

@norabelrose - you've done an amazing job here! Having Performer in PyTorch is a huge contribution.

I completely understand that you've already invested a lot of time in making this PR and we're happy to complete your PR!

also pinging @TevenLeScao here. 

In terms of next steps, I think we should do the following (We're happy to take over those tasks @norabelrose :-)) : 

- Check that the added PyTorch and Tensorflow Performer self-attention yields identical results as the flax version: Compare Bert model to this Performer BertFlax model: https://github.com/huggingface/transformers/pull/8358
- Fine-tune some pre-trained weighs to be compatible with Performer attention (ideally Bert or DistilBert)

Now, the painful discussion on how to integrate Performer.

**Context**:

Performer attention is special in the sense that it is fully compatible with a pre-existing model architecture and does not require any weights to be different from normal attention. This means that a `bert-base-cased` model does not require any changes in its architecture to use Performer's attention. The only change will be how the weights are used to compute the self-attention layer output. 
One can easily see this on the original code base: https://github.com/google-research/google-research/tree/master/performer/fast_attention/jax#jax-variant-of-favor where only the attention function has to be changed to `make_fast_softmax_attention` with no changes required to the parameters dict.

This is a huge argument for simply making Performer's self-attention available to all models by changing their respective `modeling_....py` file. 

**My opinion on the integration into Transformers**

Nevertheless, I'm in favor of implementing Performer **only** in a stand-alone file (at least at first), a.k.a. `PerformerModel` or maye in this case `PerformerBertModel`, which is **different** from the current version of the PR. I've the following arguments:

- It's the standard in Transformers to add a new model for a new attention function. We've done the same for Longformer even though the Longformer attention could have been added for each model. It's easier for users to navigate between models, *e.g.* Performer will have its own model page vs. some docstring in utils.
- It's actually not that easy to convert an existing BERT-like model to a Performer-BERT model. E.g. le'ts say we integrate Performer attention into `modeling_bert.py`. If one wants to convert the model to performer attention, the user would have to manually copy the positional embeddings (which are limited to 512 in Bert) to be as long as 64K+. We could write a convert function for this, but this convert function would probably be different for each model.
- Performer cannot support all the functionalities of Bert. This means if we integrate Performer into Bert, a ```BertModel.from_pretrained(...., is_performer=True)``` model will not have all the functionalities that a Bert model will have, such as `output_attentions=True`, `is_decoder=True`, `is_encoder_decoder=True` -> Performer never creates the complete attention_mask so the `ouput_attentions=True` functionality gets lost, Performer does not support Encoder-Decoder out-of-the-box without requiring more if-else clauses. This will necessarily lead to many issues and some `if self.is_performer` code in BERT which I don't want to do.
- Performer is still a very novel feature that is still somewhat experimental IMO. If Performer really takes off, we can always integrate the Performer attention more deeply into the library as proposed in this PR. The `modeling_bert.py` code is now used by 100K+ people, so I want to be very very careful with changes to this code especially. It's just a safer option to have a standalone Performer model in the beginning IMO. 
- I don't really think that users are interested to be able to use Performer Attention for all models. I think the models of interest will be `Bert` (`DistilBERT`), `GPT2`, `T5`, and `Bart`. Some models will never be used with Performer, such as Reformer, XLNet, Transfo-XL, Longformer, ConvBert, Routing Transformer, LED. 


I'd be thrilled you hear your opinions here @norabelrose, @sgugger, @LysandreJik, and @thomwolf

Thanks for this amazing contribution! 

I think long document classification and summarisation tasks are an important use case for this so having performer attention for some representative models in those scenarios would be fantastic. Personally I am looking forward to using performer attention with Roberta sequence and token classification models, but I understand not every model can get performer support right away so it would be great to also have a few examples on how we could add performer attention to other models ourselves, if possible.

Really excited about this, thanks so much!

@patrickvonplaten Thank you for the thoughtful feedback. I understand your concerns about building Performer attention right into existing models like BERT. On the other hand, as @onclue mentioned, having only one model that supports Performer attention would really restrict the usefulness of the feature.

It seems like there should be some "compromise" option here. What if we just added simple Performer-supporting subclasses to a few different models, something like this:
```
@supports_performer_attention
class PerformerBertConfig(BertConfig):
	pass
```

and have `PerformerBertModel` be a subclass of `BertModel` that uses the following module for its attention mechanism:

```
class PerformerBertAttention(BertAttention):
	@init_performer_attention_bertlike(BertSelfAttention)
	def __init__(self, config):
		super().__init__(self, config)
```

And then the same process could be done for RoBERTa, DistilBERT, GPT-2, etc. I recognize that trying to add Performer support to "all" models is sort of silly and wouldn't work, but there are quite a few models that would benefit from it. It would also be nice if `PerformerAttention` and `PerformerAttentionConfig` remained public APIs, as they are in this PR, so that users could just take the attention mechanism and drop it into whatever custom model they want.

Thanks for your answer @norabelrose! I understand your point. The goal should definitely to support all the "highly" used models: DistilBERT, BERT, RoBERTa, T5, Bart

I think we need to dive a bit deeper into the PR and play around with Performer to see how to best integrate the model, but in general the philosophy of the library has always been:

- Model files should be kept as independent from each other as possible
- Readability is more important than the drawback of duplicated code -> so we don't mind it too much if we duplicate Performer code across 5 or so model files
- We try to minimize "magic" internal functionalities that are hard to understand when first seeing the code to a minimum meaning that we're not a huge fan of function decorators for important functionalities in general. 

But we'll have to dive deeper into the PR to get a better understanding here - sorry for being so slow here!

Also, is there already a model that has successfully been fine-tuned to "long" inputs?

@norabelrose Where do the keys, queries & values come from when calling the Performer attention? 

def call(self, query, key, value, mask=None, head_mask=None, output_attentions=False):

The call method of the Bert attention its replacing (i guess) takes the hidden states instead and then calculates q,k,v; 

How does it work from a coding perspective that it can have different call inputs? 
& Should i just feed in the hidden states 3x for q, k, v when using performer attention? 




To get the TFPerformerAttention working I had to had to apply three fixes:
- Swap all shape calls for shape_list
- Add       mask = tf.reshape(mask, shape=(shape_list(k_prime)[0], shape_list(k_prime)[2])) in compute_attention_with_projected_queries_and_keys due to problems with the extended attn mask
- Remove the reshapes in _finalize_attention_output, as we need the shape to stay in [..., num_heads, dim_per_head]-like shape

perhaps it helps sb else // @norabelrose can correct me if im doing sth wrong

Hello,

Amazing work @norabelrose! I have been trying your performer implementation. I have copied your attention implementation
```PerformerAttention``` and have replaced that attention with the normal self-attention in Mobilebert. I have tracked some metrics with respect to other implementations. I have seen that the memory consumption on 512 tokens long it consume the same memory that the normal self attention. And it is also the same fast.

I have logged the metrics with Wandb:
https://wandb.ai/gaceladri/new_berts/reports/Memory-and-speed-comparison--Vmlldzo0NDA4MTI  

Does that makes sense? I have seen in Long Range Arena https://arxiv.org/abs/2011.04006 that it is 1.2x faster with 1k tokens but I have not tried with that long. The point where I am confused is with the memory consumption. At shorter values, the attention mechanism, being linear with respect to sequence length, not should be consuming less memory?

@norabelrose I tried the `TFPerformerAttention` with some minor adaptions and it works fine during training. I must say it is a very nice implementation 👍 
However, when I train my model, I save the weights at each checkpoint, and I quantize it into `model.pb` as well as into a `TF-Lite` model. When loading all the models again (from saved weights, quantized and tensorflow lite), the output of the model with loaded weights differ from the rest. Any idea why this is the case? 

@gcuder Would you mind sharing your code? I have been getting speed & memory improvements but the TFPerformer doesn't really converge... 



What are the plans for this MR @patrickvonplaten ?

Based on @norabelrose great work, I set up a fork with the performer as a separate model at [https://github.com/Muennighoff/transformers](https://github.com/Muennighoff/transformers). I removed the decorators but kept the separate performer attention config. For now I only added Distilbert, the question being whether we should add new performer_xyz folders for each model or fit them in one performer folder.
It can just be used as 
`from transformers import DistilBertPerformerModel, DistilBertPerformerConfig`
`configuration = DistilBertPerformerConfig()`
`model = DistilBertPerformerModel(configuration)`

Here's an example notebook comparing the distilbert perf/trans performance on seq. classification:
[https://colab.research.google.com/drive/1o8ioYUIvvIol7PXrDguftQtHyCpyDSJL#scrollTo=JGxH15LIN66M](https://colab.research.google.com/drive/1o8ioYUIvvIol7PXrDguftQtHyCpyDSJL#scrollTo=JGxH15LIN66M)

perhaps it can help us bring this forward? @marrrcin @patrickvonplaten 



Hey guys, sorry I don't really have the bandwidth to take a closer look here at the moment, but it's definitely on my ToDo List! One thing that would be extremely useful would be to have a script that shows how a pretrained model such as `distilbert` can be extended to a its performer version and subsequently be fine-tuned for long-range sequence modeling. @TevenLeScao ran some initial experiments and didn't find the fine-tuning to be that easy...

Can it be made compatible with T5? As far as I know Performer and relative attention together is an open research question.

How about this? If I understand correctly Performer calculates `Q' * (K' * V)` instead of `softmax(Q * K) * V`  (Q: queries, K: keys, V: values, *: matmul). T5 calculates `softmax(Q * K + B) * V` (B: relative positional biases). A new kind of model that initializes most of its weights from T5 could calculate `(softmax(Q * K) + B') * V = (Q' * K' + B') * V = Q' * (K' * V) + B' * V`. This way at least the first term can be calculated with FAVOR+ and the second term is much smaller/faster to calculate even if its complexity is quadratic. `B'` could be initialized in a way that on average the activations in the training set remain unchanged. We loose backward compatibility so more finetuning is necessary.

> How about this? If I understand correctly Performer calculates `Q' * (K' * V)` instead of `softmax(Q * K) * V` (Q: queries, K: keys, V: values, *: matmul). T5 calculates `softmax(Q * K + B) * V` (B: relative positional biases). I could calculate `(Q' * K' + B') * V` but then I would not gain much from using FAVOR+. But if I calculate `Q' * (K' * V) + B' * V` then at least the first term can be calculated with FAVOR+ and the second term is much smaller/faster to calculate even if it's quadratic complexity. `B'` can be initialized with `B` and finetuned.

that's an interesting idea! I will try to add T5 to the repo I set up so we can experiment with that; Currently for some reason only distilbert converges, while bert doesn't (https://colab.research.google.com/drive/1o8ioYUIvvIol7PXrDguftQtHyCpyDSJL#scrollTo=9pom5i196Bwg), so i need to figure that out first;; if anybody got bert to work let me know!

I refactored a lot of code & now works like a charm for me 
Here's a large notebook with TF & Torch comparisons for Perf/Trans on BERT, DBERT, T5 on short sequences (SST2 Dataset): https://colab.research.google.com/drive/1A9reiUZbA7DELuJ8keTo73sIQ4dJJVoT?usp=sharing

To add a new model all one needs to do is: 
- Copy over the config, tf/torch modeling file of the model you want favor attention for to its own folder [here](https://github.com/Muennighoff/transformers/tree/master/src/transformers/models/performer)
- Add a modelXPerformer Config (should be about the same as the current  modelXperformer configs)
- Init favor attention directly in the self attention module (i.e. one level lower than in the implementation of this PR) - this is preferrable as it scales better to models with different attention modules / linear layers
- feed q,k,v,mask after their linear layers through the favor attention to get back the final attention output
- Remove all the softmax business😃 
- Last thing to adapt is the (extended) attention mask -- We want the shape to be (bs, 1, seq_len, 1) instead of (bs, 1, 1, seq_len) & we don't want to fill it with the -infs, i.e. just leave it as 1's & 0's, as we multiply it not add it
- If you want to import it with `from transformers import ModelXPerformer` like the current performer models, rename the models & add them to the `__init__.py` in the performer folder & transformer parent folder

Reg. T5: 
- Based on @marton-avrios proposal, I added T5 - it got a bit more complex due to the attn mask so I compute:
	- `Q' @ ((K' * M) @ V) + (B * M) @ V` & it converges🎉
- However,  B is a matrix of (bs, n_heads, L, L) where L is the seq len so it scales quadratically with seq len, the exact problem performers try to solve ;_; 
- Removing the Rel Pos Encoding entirely surprisingly has about the same performance and is much faster (i got a 30% speedup for 1000 seq_len) - Still need to test it for EncDec model; Another option is just using bert's abs. pos. embeddings.; The pretrained model shouldnt be affected much 

Decoders:
- Only worked with T5Encoder so far; The code for doing causal perf. attention should be there, so adding EncDec / GPT-2 like models should be pretty simple; If somebody wants to try it let me know!; We just need to be careful with the attn mask when we implement it

A couple pointers if you dont get the desired performance:
- The approximation error propagates through the layers, i.e. the more layers the worse it may get  (A 6-layer bert performer gives me about as good a performance as a 12-layer one)
- Try increasing the random features & the feature drawing interval - The more random features the better the softmax approximation, though it also gets more expensive
- Make sure the masking is correct!

I'm sorry I haven't responded to mentions on this PR recently— I've been quite busy with an unrelated project.

Thank you @Muennighoff for all your hard work extending/refining the PR! I just merged your changes.

wow, great work @Muennighoff !

Regarding T5:
 - despite still being quadratic complexity have you measured any speed/memory improvements compared to vanilla T5? Or significantly worse (better?) performance? In vanilla T5 there are 2 computations of quadratic complexity: `QK` and `B` but the calculation of `QK` plays a much bigger role in the overall speed of T5. Also it is calculated (and stored) in every layer while `B` is only calculated (and stored) in the first layer.
 - when you mention 30% speedup and same performance by removing relative positional attention is it a PerformerT5 compared to a PerformerT5 without it or a vanilla T5 compared to a vanilla T5 without it? Because if it is a PerformerT5 comparison then I think it means that it cannot learn meaningful weights for `B` anyway.

> wow, great work @Muennighoff !
> 
> Regarding T5:
> 
> * despite still being quadratic complexity have you measured any speed/memory improvements compared to vanilla T5? Or significantly worse (better?) performance? In vanilla T5 there are 2 computations of quadratic complexity: `QK` and `B` but the calculation of `QK` plays a much bigger role in the overall speed of T5. Also it is calculated (and stored) in every layer while `B` is only calculated (and stored) in the first layer.
> * when you mention 30% speedup and same performance by removing relative positional attention is it a PerformerT5 compared to a PerformerT5 without it or a vanilla T5 compared to a vanilla T5 without it? Because if it is a PerformerT5 comparison then I think it means that it cannot learn meaningful weights for `B` anyway.

Check out the T5 Tensorflow experiments here: https://colab.research.google.com/drive/1A9reiUZbA7DELuJ8keTo73sIQ4dJJVoT?usp=sharing
For each configuration (performer/transformer /// raw/pretrained) i ran it w/ & w/o pos bias, but only on short seq task of sst-2. 

For the 1000 seq len task i mentioned, i ran only performer encoders (w/ & w/o pos bias) on byte-text level classification from the LRA paper & they had the same performance within +- 1% accuracy.

i'm not yet sure what to make of it; I think we could confirm that they are of no use after training a full t5 enc-dec model in performer mode & benchmarking that

I realized a mistake in my formulation which would explain why PerformerT5 could not make use of `B'`.

Vanilla T5 calculates this: `inverse(D) * exp(Q * t(K) + B) * V`
- ...which is equivalent to `softmax(Q * t(K) + B) * V`
- ...where `D = diag(exp(Q * t(K) + B) * 1L)`, `t()` is the transpose function and `1L` is the all 1 vector of length L.

I propose to calculate this: `inverse(D) * (exp(Q * t(K)) + B') * V`
- ...which is equivalent to `inverse(D) * exp(Q  * t(K)) * V + inverse(D) * B' * V`
- ...where `D = diag(exp(Q * t(K)) * 1L + B' * 1L)`
- ...and when finetuning `B'` should not be initialized from `B` but randomly instead.

I propose to approximate it with: `inverse(D') * Q' * t(K') * V + inverse(D') * B' * V`
- ...where `D' = diag(Q' * t(K') * 1L + B' * 1L)`.

My previous (incorrect) approximation was: `inverse(D') * Q' * t(K') * V + B' * V`
- ...which approximates `inverse(D) * exp(Q  * t(K)) * V + B' * V`
- ...and NOT `inverse(D) * exp(Q  * t(K)) * V + inverse(D) * B' * V`.

> * inverse



> I realized a mistake in my formulation which would explain why PerformerT5 could not make use of `B'`.
> 
> Vanilla T5 calculates this: `inverse(D) * exp(Q * t(K) + B) * V`
> 
> * ...which is equivalent to `softmax(Q * t(K) + B) * V`
> * ...where `D = diag(exp(Q * t(K) + B) * 1L)`, `t()` is the transpose function and `1L` is the all 1 vector of length L.
> 
> I propose to calculate this: `inverse(D) * (exp(Q * t(K)) + B') * V`
> 
> * ...which is equivalent to `inverse(D) * exp(Q  * t(K)) * V + inverse(D) * B' * V`
> * ...where `D = diag(exp(Q * t(K)) * 1L + B' * 1L)`
> * ...and when finetuning `B'` should not be initialized from `B` but randomly instead.
> 
> I propose to approximate it with: `inverse(D') * Q' * t(K') * V + inverse(D') * B' * V`
> 
> * ...where `D' = diag(Q' * t(K') * 1L + B' * 1L)`.
> 
> My previous (incorrect) approximation was: `inverse(D') * Q' * t(K') * V + B' * V`
> 
> * ...which approximates `inverse(D) * exp(Q  * t(K)) * V + B' * V`
> * ...and NOT `inverse(D) * exp(Q  * t(K)) * V + inverse(D) * B' * V`.

Yeah you're right the previous approximation wasn't correct; I also forgot to include it in D when doing the code experiments;
We could try the approximation you propose. 

Another angle could be:
Since 
`exp(Q @ t(K) + B) = exp(Q @ t(K)) * exp(B)`
and 
`exp(Q @ t(K)) ~ ϕ(Q) @ t(ϕ(K))` 
i think we can do
`exp(Q @ t(K) + B) ~ ϕ(Q) @ t(ϕ(K)) * exp(B) `
but rearranging 
`(ϕ(Q) @ t(ϕ(K)) * exp(B)) @ V `
to avoid calculating Q @ K first is a pain 

Is this close?  My teammates and I want to use performers in T5

I was just looking through the code and this is stuff of legends!  Great work.

In the T5 implementation, I noticed that performer attention forward method is called with position bias, yet it is not currently a valid parameter.  Is that residual from the conversation about the above position bias conversations?

EDIT: Ignore the above, I was looking at the wrong implementation of `PerformerAttention`

> I was just looking through the code and this is stuff of legends! Great work.
> 
> In the T5 implementation, I noticed that performer attention forward method is called with position bias, yet it is not currently a valid parameter. Is that residual from the conversation about the above position bias conversations?
> 
> EDIT: Ignore the above, I was looking at the wrong implementation of `PerformerAttention`

I removed the position bias temporarily, as not using it at all worked best. I havn't tried @marton-avrios most recent idea though, so perhaps somebody might want to try it and report back. 

If you only need an Encoder T5, you should be able to work with what's there -- For Encoder-Decoder, The causal decoder is currently still prohibitively expensive due to the for loop & cumsum operation (@mymusise and me are working on it [here](https://github.com/mymusise/gpt2-quickly/issues/5)). Let us know if you get the decoder to perform! 

I'm thinking about the position bias, and it doesn't seem like there's a good way to include it.  What's been mentioned above seems correct, that the mathematical starting point is 

(Q'K'^T * B')V, where B' = e^B (elementwise)

But, this can't be computed without computing Q'K'^T first, defeating the purpose.

The alternative is to add some position encoding into each of Q' and K' (a la 'Attention Is All You Need').  I think this is the only / best way to do position bias in this context.  That said, it would be getting kind of wonky / outside the spirit of the performers paper, so I'm not sure position bias should even be allowed in this PR.

Do you all agree with this?

Hi, I have been trying to run finetuning with `T5PerformerForConditionalGeneration` using this pull request branch, and I have got few minor issues or questions I wanted to ask about.

1. Merge conflict comments were still left under `/src/transformers/__init__.py`, which is not a serious issue.
2. After getting the attention output from `PerformerAttention`, I had to add `unshape` call it to concat the head attentions and multiply to `W0` in `forward()` of `T5Attention`. I found original call to unshape was commented out since it included matmul of `V`.
3. Both in encoder and decoder, I was getting matrix multiplication exception by wrong dimension on the line when multiplying(in `PerformerAttention`) `mask` to `k_prime`. Was this the reason why @norabelrose mentioned T5 Decoders is not fully working yet? I am trying to fix this attention mask issue for the decoder, but for encoder case, is transposing the attention mask the right way to fix?
> Decoders:
> 
> Only worked with T5Encoder so far; The code for doing causal perf. attention should be there, so adding EncDec / GPT-2 like models should be pretty simple; If somebody wants to try it let me know!; We just need to be careful with the attn mask when we implement it

> Hi, I have been trying to run finetuning with `T5PerformerForConditionalGeneration` using this pull request branch, and I have got few minor issues or questions I wanted to ask about.
> 
> 1. Merge conflict comments were still left under `/src/transformers/__init__.py`, which is not a serious issue.
> 2. After getting the attention output from `PerformerAttention`, I had to add `unshape` call it to concat the head attentions and multiply to `W0` in `forward()` of `T5Attention`. I found original call to unshape was commented out since it included matmul of `V`.
> 3. Both in encoder and decoder, I was getting matrix multiplication exception by wrong dimension on the line when multiplying(in `PerformerAttention`) `mask` to `k_prime`. Was this the reason why @norabelrose mentioned T5 Decoders is not fully working yet? I am trying to fix this attention mask issue for the decoder, but for encoder case, is transposing the attention mask the right way to fix?
> 
> > Decoders:
> > Only worked with T5Encoder so far; The code for doing causal perf. attention should be there, so adding EncDec / GPT-2 like models should be pretty simple; If somebody wants to try it let me know!; We just need to be careful with the attn mask when we implement it

I think 1,2 & 3 are all fixed here: https://github.com/Muennighoff/transformers ; 
The masking for the decoder however may not yet work


> > Hi, I have been trying to run finetuning with `T5PerformerForConditionalGeneration` using this pull request branch, and I have got few minor issues or questions I wanted to ask about.
> > 
> > 1. Merge conflict comments were still left under `/src/transformers/__init__.py`, which is not a serious issue.
> > 2. After getting the attention output from `PerformerAttention`, I had to add `unshape` call it to concat the head attentions and multiply to `W0` in `forward()` of `T5Attention`. I found original call to unshape was commented out since it included matmul of `V`.
> > 3. Both in encoder and decoder, I was getting matrix multiplication exception by wrong dimension on the line when multiplying(in `PerformerAttention`) `mask` to `k_prime`. Was this the reason why @norabelrose mentioned T5 Decoders is not fully working yet? I am trying to fix this attention mask issue for the decoder, but for encoder case, is transposing the attention mask the right way to fix?
> > 
> > > Decoders:
> > > Only worked with T5Encoder so far; The code for doing causal perf. attention should be there, so adding EncDec / GPT-2 like models should be pretty simple; If somebody wants to try it let me know!; We just need to be careful with the attn mask when we implement it
> 
> I think 1,2 & 3 are all fixed here: https://github.com/Muennighoff/transformers ;
> The masking for the decoder however may not yet work

Thanks @Muennighoff, I ended up using your forked project and currently tyring to test `T5PerformerForConditionalGeneration`. I think finetuning seems to run fine with the `CausalDotProduct` from `pytorch-fast-transformer`, although I did not check the loss or verified anything yet. When you mentioned that the docoder might not yet work, did you mean that the loss or performance of the model is not there yet even though we can run it?
Also, is there any reason why further fixes have not been merged into this pull request?

I've been in [this issue](https://github.com/mymusise/gpt2-quickly/issues/5) the past few days, and it seems like everything works on the Pytorch end now that `CausalDotProduct` is used (like @ice-americano was saying).  Is the only remaining issue doing causal dot product in tensorflow?

@JamesDeAntonis Causal dot product in TensorFlow would require rewriting the CUDA C++ code on the fast-transformers end. That would be quite a bit of work and would probably require actually creating an entirely separate library, since the fast-transformers library is purely PyTorch. I don't think the code would belong in huggingface/transformers since my sense is that there is a general policy against including custom CUDA kernels directly in the transformers library itself. That's why I originally coded it so that `PerformerAttention` would just detect if fast-transformers is installed, and use it if it is.

To be honest I'm hesitant to recommend merging this PR in its current form, mainly because of all the other fast linear attention algorithms that have come out in the past few months, such as the [Nystromformer](https://www.youtube.com/watch?v=m-zrcmRd7E4) and this [ostensibly improved variation](https://arxiv.org/abs/2103.02143) on the Performer random feature approach that came out a couple weeks ago. I'm all in favor of getting fast attention mechanisms out there in an easy to use format, it seems wrong to create multiple different copies of the big models (BERT, T5, GPT2, etc.), one for each new fast attention mechanism that comes out. It's not at all clear to me that the Performer will end up becoming the dominant fast attention mechanism— it does well on [the benchmarks](https://github.com/google-research/long-range-arena), but it's not the best, and the fact that it includes non-trainable orthogonal random matrices which you have to routinely redraw in order for the model to converge is definitely sub-optimal.

My ideal solution, I think, would be to do broader refactoring of the huggingface/transformers codebase so that you could more easily plug in different attention mechanisms and reuse code, but that seems to directly go against the philosophy of the maintainers. So idk what the best solution is. It might be best to make a fork of the fast-transformers library itself, which was actually built to be an extensible framework for different types of fast attention/transformers, and just copy and paste most of the BERT/T5/GPT2/whatever implementations from this repo into that fork. Or maybe the fast-attention maintainers would actually be open to including implementations of those big models in their repo— I haven't asked.

>(1) That's why I originally coded it so that PerformerAttention would just detect if fast-transformers is installed, and use it if it is.

I'm fine with this because my team uses pytorch.  That said, I think this would make TF performer really slow (potentially not a big deal because it could still be memory efficient)

>(2) because of all the other fast linear attention algorithms that have come out in the past few months, such as the Nystromformer and this ostensibly improved variation on the Performer random feature approach that came out a couple weeks ago

>(3) more easily plug in different attention mechanisms and reuse code

I agree that the ideal scenario for implementing efficient attn in huggingface/transformers is to refactor the codebase so that the attention computation always bottles up in one place.  Then, we could have all attn algos in one place, implemented only once for plug-and-play on any model.  I share your sense that they wouldn't go for that.  (@patrickvonplaten is that right?)

>(4) It might be best to make a fork of the fast-transformers library itself, which was actually built to be an extensible framework for different types of fast attention/transformers, and just copy and paste most of the BERT/T5/GPT2/whatever implementations from this repo into that fork.

I might be on board, but wouldn't this make things equally messy?  e.g. you would still have the issue of having to rewrite a whole bunch of code.  There would be an improvement in having attention be bottled up in one place for easy efficient transformer plug-and-play, but also at a further annoyance of having all of it outside of hf

@JamesDeAntonis It looks like the BigBird linear attention model [just got merged](https://github.com/huggingface/transformers/pull/10183) and will be included in the next release. BigBird actually outperforms the Performer on the Long Range Arena benchmark, and it doesn't require repeatedly sampling orthogonal random features during training.

Ironically, as the author of this pull request, I'd like to close the PR. I don't think this library should be cluttered with another linear attention mechanism that has no obvious benefits over BigBird. That said, I'm glad to see that others found my code useful and were able to fork it and use it for their own projects.

Thanks a lot for your efforts, @norabelrose . I am a bit sad that Performers won't make it in after all this work, but I understand the reasoning. Cheers!

Is it possible to use sequences > 512 tokens with pretrained Bert to see the effective improvement of performer?