Why and when transformers are better than CNN's in sequence modeling tasks?

Transformers have made a revolution in the domain of NLP and gave rise to a rapid boost of neural networks in a variety of language modelling problems, TTS and, recently, achieved competitive accuracy with CNN in computer vision problems https://arxiv.org/abs/2010.11929.

However, in terms of performance and architectural principles transformers are usually compared against RNN architectures. The advantages of the self-attention mechanism are the following :

• Possibility for parallel execution
• Capturing long-range context. Vanilla RNNs store information about all the previous timestamps in the hidden state and this information is gradually washed out. Modifications like LSTM and GRU can solve this issue only partially via the introduction of the carrier channel, and this approach doesn't help for very long sequences.

Despite these advantages, transformers in the original formulation https://arxiv.org/abs/1706.03762 suffer from $$O(n^2)$$ scaling of computational complexity and memory storage, which prohibits their use for very long sequences and in the problem, where there is strict restriction on the number of computations.

A lot of effort in the past years was dedicated to speed-up the attention mechanism - Sparse Attention, Linformers, Reformers, Performers, XL-Transformer and e.t.c, e.t.c. These approaches allow one to have almost the same or the same accuracy in comparison with the vanilla formulation with the complexity scaling as $$O(n), O(n \log n), O(n^{3/2})$$, depending on the model.

However, it is not absolutely clear to me, why deep enough CNNs cannot achieve the same performance. For shallow CNN's the feature map at the given pixel can attend to the neighbourhood determined by the receptive field. Without dilations and strides, this receptive field increases linearly with the number of layers. Hence, in order to capture long-range context, one would need rather a deep model with a large number of parameters and computations.

In order to combat this issue, one can use exponentially increasing receptive field as in the WaveNet model https://deepmind.com/blog/article/wavenet-generative-model-raw-audio. For 12 layers, like in the BERT, the receptive field would be $$2^{12} = 4096$$, which is rather competitive with the modern transformers.

Is there any intuition or some theoretical argument, that transformers with the same number of parameters and computational complexity would be more efficient and expressive in the sequence modelling problems, than CNNs?