# Why are non-local blocks really slow?

I have added non-local blocks into my CNN decoder, but this increases the training time by four times the original time without, so i don't really want to use it! What is the reason it is too slow? My images are cells and therefore there are lots of datapoints in each image, so i wonder using non-local blocks is like overkill for small data points?

Is there a way to speed it up?

Non-local blocks are a generalization of transformer blocks. The reason why they are slow is the matrix multiplication $$A^TA$$. The speed can be increased by decreasing the matrix size. Other possibilities are: applying the multiplication only on patches of images (https://arxiv.org/pdf/2010.11929.pdf), sparse attention (https://arxiv.org/pdf/2009.14794.pdf), perform some kind of channel attention (https://arxiv.org/abs/1709.01507). Non-local blocks do not depend on the data size because the matrix multiplication is not performed on the batch size.