Add Multi Resolution Analysis (MRA) 
Author: novice03
Pull request: yes
Labels: name: WIP

# Add Multi Resolution Analysis (MRA) for Approximate Self-Attention (Old PR)

This PR adds the MRA model to the repository. 

Paper: [https://arxiv.org/pdf/2207.10284.pdf](https://arxiv.org/pdf/2207.10284.pdf)
Code: [https://github.com/mlpen/mra-attention](https://github.com/mlpen/mra-attention)

To-do:

- [ ] Improve loading cuda kernels
- [ ] Improve formatting and documentation
- [ ] Upload checkpoints

Comments:
cc @amyeroberts and @NielsRogge 

Hello @amyeroberts, thank you so much for going over the code! I've made changes to my branch and left some questions in the above suggestions. Please take a look at them when you are available. I also have a few additional questions and clarifications:

> Can you add any necessary optional dependencies

If I'm not mistaken MRA does not need any optional dependencies. All functions/ classes only require torch and the CUDA kernels. Unfortunately, unlike YOSO, MRA requires CUDA kernels - it cannot run without them. Could it be that the tests are failing because the kernels are not being loaded? If so, how can we handle this dependency on CUDA kernels in the HF implementation? 

Hello @amyeroberts, pinging to follow up on this PR. 

Hi @novice03 - thanks for the ping. Re-reviewing now! 

Before I start reviewing more, could you:
- fix the conflicts
- make sure all tests pass (you can run them locally with pytest)
- make sure all quality checks pass (you can run `make fixup` for most changes that can be automated then look at `make repo-consistency` locally to see where other quality scripts are unhappy).

The docs for this PR live [here](https://moon-ci-docs.huggingface.co/docs/transformers/pr_20573). All of your documentation changes will be reflected on that endpoint.

Thank you for the second review @amyeroberts. I've made most, if not all, the changes you suggested. 

I'm now working on fixing the tests. `tests_torch` fails because the CUDA kernels are not being loaded correctly. I've added some extra code (for e.g. calling `load_cuda_kernels()` in `mra2_attention()`) for debugging purposes, which I'll remove it later. @sgugger  I might need your help in understanding how to correctly load the kernels. I get `RuntimeError: Ninja is required to load C++ extensions` for `test_determinism`. Are Ninja and CUDA not available when running the tests?

No they are not, as most users won't have them installed. Both are only installed in the runners that run the nightly tests.

Thanks @sgugger. How can I use the nightly test runners instead? 

@novice03 Unfortunately you can't use the nightly tests environment for the full test suite. As @sgugger notes, most users won't have ninja and cuda installed in their environment - this is something for which the model will need to be robust. 

I mentioned in one of [my comments](https://github.com/huggingface/transformers/pull/20573/files#r1072316307) that deformable DETR has a safe way of loading the CUDA kernels. I think this would be the first things to address as this handles the case when ninja and cuda aren't in the environment. 

Thank you @amyeroberts. I didn't notice that DETR can run using regular PyTorch - without CUDA kernels. MRA does not have this functionality yet, so I will be working on this. 

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/main/CONTRIBUTING.md) are likely to be ignored.

Hello @amyeroberts, I've been talking to the authors about writing non-CUDA PyTorch code for MRA. It seems that writing a PyTorch alternative for MRA, especially the `sparse_max` function, will be extremely inefficient and infeasable. I am currently looking into other alternatives for running CUDA kernels on machines without Ninja. How about pre-compiling the CUDA kernels, add the .so .egg etc files in the repo, and import it during run-time? This way we can provide the pre-compiled kernels to users - we can compile it on a machine that has Ninja and import it later. 

Hi @novice03 - thanks for the update. 

I realise my previous comment might not have been completely clear and didn't catch that in your reply. The models relying on custom CUDA kernels don't have pytorch equivalents implemented. Rather, they have a safe way of importing the models if ninja and cuda aren't available e.g. [in deformable detr](https://github.com/huggingface/transformers/blob/a5392ee7470f34bb48417ca2af97b9189f0eda70/src/transformers/models/deformable_detr/modeling_deformable_detr.py#L54), the `is_torch_cuda_available` and `is_ninja_available` functions are used to conditionally load the cuda kernels. If they aren't available, [dummy variables are used](https://github.com/huggingface/transformers/blob/a5392ee7470f34bb48417ca2af97b9189f0eda70/src/transformers/models/deformable_detr/modeling_deformable_detr.py#L62). 

Thanks for the clarification. I assumed we needed a PyTorch implementation since I saw one in [deformable detr](https://github.com/huggingface/transformers/blob/a5392ee7470f34bb48417ca2af97b9189f0eda70/src/transformers/models/deformable_detr/modeling_deformable_detr.py#L548). However, if equivalent PyTorch functions are not required, then I can just add dummy variables/functions for MRA. 

Hello @amyeroberts and @sgugger, I've added safe loading of the CUDA kernels and made sure all the tests pass. I also uploaded a checkpoint to the hub. Please take a look at the updated code. 

Hi @sgugger and @amyeroberts, I've resolved all conflicts and ensured that all the tests pass. Can you please take a look at the updated code?

Thank you @sgugger. I've addressed all of your suggestions. Please take a look at the updated code. 

Thanks for the corrections @sgugger! I've made all the changes suggested and taken another look at the code (fixed some urls and tests). It looks like there are merge conflicts because of the .mdx files on my branch. How do you recommend resolving the conflicts? Should I change all the .mdx files to .md?

Yes, you will need to merge main into your branch (or rebase if you prefer) to fix the conflicts and also switch all your mdx to md.

This is because GitHub recently made changes to the UI of the diffs for MDX files, which makes it really hard to review PRs, so we switched everything to Markdown. Sorry about that.

Hi @sgugger, I might need some help in correctly switching from mdx to md. I tried renaming and git mv, but this still creates a lot of conflicts. What do you suggest?

No you can't rename them in this PR, you need to rebase on main or merge the main branch into yours.

Continuing in #24513