Answers.Body: <p>Let's start with RNN. A well known problem is vanishin/exploding gradients, which means that the model is biased by most recent inputs in the sequence, or in other words, older inputs have practically no effect in the output at the current step. </p>
  
  <p>LSTMs/GRUs mainly try to solve this problem, by including a separate memory (cell) and/or extra gates to learn when to let go of past/current information. Check these series of <a href="https://youtu.be/QEw0qEa0E50" rel="noreferrer">lectures</a> for more in-depth discussion. Also check the interactive parts of <a href="https://distill.pub/2019/memorization-in-rnns/" rel="noreferrer">this article</a> for some intuitive understanding of dependency on past elements.</p>
  
  <p>Now, given all this, information from past steps <em>still</em> goes through a sequence of computations and we're relying on these new gate/memory mechanisms to pass information from old steps to the current one. </p>
  
  <p>One major advantage of the transformer architecture, is that at each step we have <strong>direct</strong> access to all the other steps (self-attention), which practically leaves no room for information loss, as far as message passing is concerned. On top of that, we can look at both future and past elements at the same time, which also brings the benefit of bidirectional RNNs, without the 2x computation needed. And of course, all this happens in parallel (non-recurrent), which makes both training/inference much faster. </p>
  
  <p>The self-attention with every other token in the input means that the processing will be in the order of <span class="math-container">$\mathcal{O}(N^2)$</span> (glossing over details), which means that it's going to be costly to apply transformers on long sequences, compared to RNNs. That's probably one area that RNNs still have an advantage over transformers. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T16:26:25.107Z
Answers.Text: Why can you look at both the future and past elements at the same time without 2x computation?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T16:35:28.803Z
Answers.Text: A bidrectional RNN has a forward and a backward RNN, which means we process the whole sequence 2 times. It's basically a hack so that we have some way to look at the future using the backward RNN. In transformers, this is done in "one" operation, which is just calculating the result of `softmax(QK) x V`
Answers.UserDisplayName: olix20
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-14T18:03:21.120Z
Answers.Text: Any benefit of Positional Encoding? Does it make possible Self Attention for longer sentence?
Answers.UserDisplayName: Cloud Cho
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T16:20:25.827Z
Answers.LastActivityDate: 2020-04-07T16:25:10.303Z
Answers.LastEditDate: 2020-04-07T16:25:10.303Z
Answers.UserDisplayName: olix20
Answers.Body: <p><a href="https://i.sstatic.net/ULJvS.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ULJvS.jpg" alt="arxiv:1706.03762" /></a>
  <em>table is on page 6 from <a href="https://arxiv.org/abs/1706.03762" rel="nofollow noreferrer">arxiv:1706.03762 Attention Is All You Need</a></em></p>
  <p>It's because of the path length. If you have a sequence of length n. Then a transformer will have access to each element with O(1) sequential operations where a recurrent neural network will need at most O(n) sequential operations to access an element. <br>
  Very long sequences gives you problem with exploding and vanishing gradients because of the chain rule in backprop. <br> Transformers don't have this problem as the distance to each element in the sequence is always O(1) sequential operations away. (as it selects the right element instead of trying to &quot;remember&quot; it)</p>
  <p>Yet there is a paper to handle longer input using RNN structure.<br />
  <strong><a href="https://arxiv.org/abs/2103.05487" rel="nofollow noreferrer">(arxiv:2103.05487) UnICORNN: A recurrent model for learning very long time dependencies</a><br> <br></strong>
    &quot;The design of RNNs that can accurately handle sequential inputs with long-time dependencies is very challenging.<br>
    This is largely on account of the exploding and vanishing
  gradient problem (EVGP).&quot; <br></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-14T16:51:45.607Z
Answers.Text: Is the Sequential Operations for a layer or entire structure for Transformer? My guess is that Sequential Operations for LSTM is entire structure. By the way is the Complexity per Layer sounds like Space Complexity (not Time Complexity)
Answers.UserDisplayName: Cloud Cho
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-16T11:46:53.157Z
Answers.Text: It's per layer. Yes, a lstm block is considered to be a single layer (as they tend to be stacked). What do you mean with entire structure, do you mean the unrolled architecture? They basically just say what the span is of the architecture, for lstm's you have to wait for the previous token to finish computing before computing the next one so you get a span of O(n), where self attention and convolution (during training) don't have to wait sequentially O(1) span.
Answers.UserDisplayName: hal9000
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-16T11:57:35.910Z
Answers.Text: For convolution I've to check but the time and space complexity of attention is O(n^2*d) and for recurrent O(n*d^2).
Answers.UserDisplayName: hal9000
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-18T03:49:31.987Z
Answers.Text: For the "entire structure", I meant whole network strtucture not one module (ref: https://colah.github.io/posts/2015-08-Understanding-LSTMs/). For the complexity, I still don't get clear picture. Thanks for additional explantion though.
Answers.UserDisplayName: Cloud Cho
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-19T12:14:24.857Z
Answers.Text: The post you send shows for a single layer the unrolled structure, so repetition of the lstm's module along the sequence length. We look at the layer perspective in this case, so for the lstm that is a single unrolled layer. (this can be different from the whole network structure as you can also layer these unrolled lstm layers on-top of each-other)
Answers.UserDisplayName: hal9000
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-19T12:24:34.067Z
Answers.Text: (the stacking can be done by feeding the (Ht-n,..,Ht-1,Ht,Ht+1,...,Ht+n as the (entire) Xt sequence for the layer ontop. The O(n) time and memory complexity for the lstm comes from the unrolling over the entire sequence, so it needs to process each and every element in the sequence at-least once (and store it for the computational graph to do backprop). In self attention (from attention is all you need) you have O(n^2) memory and compute since you have every element in the sequence message pass to every other element in the sequence. O(n^2)
Answers.UserDisplayName: hal9000
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-19T12:28:53.790Z
Answers.Text: in causal (self) attention you just mask away the messages so the structure is causal, but the full n^2 matrix (from the dot product between the key and queries, what when normalized with the softmax will represent the amount of "communication" between each token (element in the sequence)) is still formed it's just masked with a triangular zero's matrix.
Answers.UserDisplayName: hal9000
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-19T12:33:01.010Z
Answers.Text: so the O(n) for lstm's comes from the fact they form a chain and pass messages along the chain sequentially and self attention forms a fully connected graph where at once all nodes messages pass to all other nodes giving a O(n^2). This is also why the path length is so short in attention as each node (item in the sequence) is at-most 1 edge away from every other node, where in lstm's (or other recurrent networks) it tends to be a chain so at-most you are n-1 edges away  from another node
Answers.UserDisplayName: hal9000
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-19T12:33:40.467Z
Answers.Text: I hope this sheds a bit more light on it. :)
Answers.UserDisplayName: hal9000
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T11:24:48.357Z
Answers.LastActivityDate: 2024-08-20T15:05:37.273Z
Answers.LastEditDate: 2024-08-20T15:05:37.273Z
Answers.UserDisplayName: hal9000
Answers.Body: <p>First: RNN is one part of the Neural Network family for processing sequential data. The way in which RNN is able to store information from the past is to loop in its architecture, which automatically keeps information from the past stored.
  Second: sltm / gru is a component of regulating the flow of information referred to as the gate and GRU has 2 gates, namely reset gate and gate update. If we want to make a decision to eat like the analogy above, resetting the gate on the GRU will determine how to combine new inputs with past information, and update the gate, will determine how much past information should be kept.
  source : <a href="https://link.springer.com/article/10.1007/s00500-019-04281-z" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s00500-019-04281-z</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T00:41:28.833Z
Answers.Text: Hi @Lutfizain, welcome to AI stack exchange! Please [see the tour](https://ai.stackexchange.com/tour) and look around to see how this site works. I think you aren't answer the question, OP is asking why transformer (kind of NN architecture) performs better than RNN/LSTM on that context, and you didn't mention it
Answers.UserDisplayName: malioboro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-21T14:25:52.257Z
Answers.LastActivityDate: 2020-04-21T14:25:52.257Z
Answers.UserDisplayName: lutfizain
Answers.Body: <p>I'll list some bullet points of the main innovations introduced by transformers , followed by bullet points of the main characteristics of the other architectures you mentioned, so we can then compared them.</p>
  <h1>Transformers</h1>
  <p>Transformers (<a href="https://arxiv.org/pdf/1706.03762.pdf" rel="noreferrer">Attention is all you need</a>) were introduced in the context of machine translation with the purpose to avoid recursion in order to allow parallel computation (to reduce training time) and also to reduce drops in performance due to long dependencies. The main characteristics are:</p>
  <ul>
  <li><strong>Non sequential</strong>: sentences are processed as a whole rather than word by word.</li>
  <li><strong>Self Attention</strong>: this is the newly introduced 'unit' used to compute similarity scores between words in a sentence.</li>
  <li><strong>Positional embeddings</strong>: another innovation introduced to replace recurrence. The idea is to use fixed or learned weights which encode information related to a specific position of a token in a sentence.</li>
  </ul>
  <p>The first point is the main reason why transformer do not suffer from long dependency issues. The original transformers do not rely on past hidden states to capture dependencies with previous words. They instead process a sentence as a whole. That is why there is no risk to lose (or &quot;forget&quot;) past information. Moreover, multi-head attention and positional embeddings both provide information about the relationship between different words.</p>
  <h1>RNN / LSTM</h1>
  <p>Recurrent neural networks and Long-short term memory models, for what concerns this question, are almost identical in their core properties:</p>
  <ul>
  <li><strong>Sequential processing</strong>: sentences must be processed word by word.</li>
  <li><strong>Past information retained through past hidden states</strong>: sequence to sequence models follow the Markov property: each state is assumed to be dependent only on the previously seen state.</li>
  </ul>
  <p>The first property is the reason why RNN and LSTM can't be trained in parallel. In order to encode the second word in a sentence I need the previously computed hidden states of the first word, therefore I need to compute that first. The second property is a bit more subtle, but not hard to grasp conceptually. Information in RNN and LSTM are retained thanks to previously computed hidden states. The point is that the encoding of a specific word is retained only for the next time step, which means that the encoding of a word strongly affects only the representation of the next word, so its influence is quickly lost after a few time steps. LSTM (and also GruRNN) can boost a bit the dependency range they can learn thanks to a deeper processing of the hidden states through specific units (which comes with an increased number of parameters to train) but nevertheless the problem is inherently related to recursion. Another way in which people mitigated this problem is to use bi-directional models. These encode the same sentence from the start to end, and from the end to the start, allowing words at the end of a sentence to have stronger influence in the creation of the hidden representation. However, this is just a workaround rather than a real solution for very long dependencies.</p>
  <h1>CNN</h1>
  <p>Also convolutional neural networks are widely used in nlp since they are quite fast to train and effective with short texts. The way they tackle dependencies is by applying different kernels to the same sentence, and indeed since their first application to text (<a href="https://arxiv.org/pdf/1408.5882.pdf" rel="noreferrer">Convolutional Neural Networks for Sentence Classification</a>) they were implement as multichannel CNN. Why do different kernels allow to learn dependencies? Because a kernel of size 2 for example would learn relationships between pairs of words, a kernel of size 3 would capture relationships between triplets of words and so on. The evident problem here is that the number of different kernels required to capture dependencies among all possible combinations of words in a sentence would be enormous and unpractical because of the exponential growing number of combinations when increasing the maximum length size of input sentences.</p>
  <p>To summarize, Transformers are better than all the other architectures because they totally avoid recursion, by processing sentences as a whole and by learning relationships between words thanks to multi-head attention mechanisms and positional embeddings. Nevertheless, it must be pointed out that also transformers can capture only dependencies within the fixed input size used to train them, i.e. if I use as a maximum sentence size 50, the model will not be able to capture dependencies between the first word of a sentence and words that occur more than 50 words later, like in another paragraph. New transformers like <a href="https://arxiv.org/abs/1901.02860" rel="noreferrer">Transformer-XL</a> tries to overcome exactly this issue, by kinda re-introducing recursion by storing hidden states of already encoded sentences to leverage them in the subsequent encoding of the next sentences.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-17T13:12:40.763Z
Answers.Text: It's not clear from this answer what you mean when you say that "transformers process sentences as a whole". Do you mean that first you create word embeddings that represent whole sentences rather than words? I think that you should have mentioned the encoder-decoder architecture with LSTMs, because it seems that this "processing sentences as a whole" already existed in other machine translation architectures with LSTMs (like neural machine translation and stuff like that), so that would not be a novel thing.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T16:12:04.617Z
Answers.LastActivityDate: 2022-01-26T09:18:34.963Z
Answers.LastEditDate: 2022-01-26T09:18:34.963Z
Answers.UserDisplayName: Edoardo Guerriero
Body: <p>I am reading the article <a href="https://towardsdatascience.com/transformers-141e32e69591" rel="noreferrer">How Transformers Work</a> where the author writes</p>
  
  <blockquote>
    <p>Another problem with RNNs, and LSTMs, is that it’s hard to parallelize the work for processing sentences, since you have to process word by word. Not only that but there is no model of <strong>long and short-range dependencies</strong>. </p>
  </blockquote>
  
  <p>Why exactly does the transformer do better than RNN and LSTM in <strong>long-range context dependencies</strong>?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-07T15:46:52.513Z
Comments.Text: I think it's incorrect to say that LSTMs cannot capture long-range dependencies. Well, it depends on what you mean by "long-range". They certainly can capture _certain_ long-range dependencies. Also, when the author of that article says "there is no model of long and short-range dependencies.", this probably answers the question. The transformer probably has a "model" (whatever the author means by that) that models long-range dependencies explicitly (whatever "explicitly" means). Honestly, I am currently not familiar with the details of the transformer, so I cannot provide a formal answer now.
Comments.UserDisplayName: nbro
Tags: <machine-learning><natural-language-processing><recurrent-neural-networks><long-short-term-memory><transformer>
Title: Why does the transformer do better than RNN and LSTM in long-range context dependencies?
UserDisplayName: DRV
ThreadText: # Why does the transformer do better than RNN and LSTM in long-range context dependencies?
  
  (Asked by: username_0 on 2020-04-07)
  
  I am reading the article [How Transformers Work](https://towardsdatascience.com/transformers-141e32e69591) where the author writes
  
  > Another problem with RNNs, and LSTMs, is that it’s hard to parallelize the work for processing sentences, since you have to process word by word. Not only that but there is no model of **long and short-range dependencies**.
  
  Why exactly does the transformer do better than RNN and LSTM in **long-range context dependencies**?
  
  **Tags:** machine-learning, natural-language-processing, recurrent-neural-networks, long-short-term-memory, transformer
  > **Comments:**
  > **username_1**: I think it's incorrect to say that LSTMs cannot capture long-range dependencies. Well, it depends on what you mean by "long-range". They certainly can capture _certain_ long-range dependencies. Also, when the author of that article says "there is no model of long and short-range dependencies.", this probably answers the question. The transformer probably has a "model" (whatever the author means by that) that models long-range dependencies explicitly (whatever "explicitly" means). Honestly, I am currently not familiar with the details of the transformer, so I cannot provide a formal answer now.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_7 on 2020-04-07. Score: 66 | Accepted answer
  
  I'll list some bullet points of the main innovations introduced by transformers , followed by bullet points of the main characteristics of the other architectures you mentioned, so we can then compared them.
  
  # Transformers
  
  Transformers ([Attention is all you need](https://arxiv.org/pdf/1706.03762.pdf)) were introduced in the context of machine translation with the purpose to avoid recursion in order to allow parallel computation (to reduce training time) and also to reduce drops in performance due to long dependencies. The main characteristics are:
  
  * **Non sequential**: sentences are processed as a whole rather than word by word.
  * **Self Attention**: this is the newly introduced 'unit' used to compute similarity scores between words in a sentence.
  * **Positional embeddings**: another innovation introduced to replace recurrence. The idea is to use fixed or learned weights which encode information related to a specific position of a token in a sentence.
  
  The first point is the main reason why transformer do not suffer from long dependency issues. The original transformers do not rely on past hidden states to capture dependencies with previous words. They instead process a sentence as a whole. That is why there is no risk to lose (or "forget") past information. Moreover, multi-head attention and positional embeddings both provide information about the relationship between different words.
  
  # RNN / LSTM
  
  Recurrent neural networks and Long-short term memory models, for what concerns this question, are almost identical in their core properties:
  
  * **Sequential processing**: sentences must be processed word by word.
  * **Past information retained through past hidden states**: sequence to sequence models follow the Markov property: each state is assumed to be dependent only on the previously seen state.
  
  The first property is the reason why RNN and LSTM can't be trained in parallel. In order to encode the second word in a sentence I need the previously computed hidden states of the first word, therefore I need to compute that first. The second property is a bit more subtle, but not hard to grasp conceptually. Information in RNN and LSTM are retained thanks to previously computed hidden states. The point is that the encoding of a specific word is retained only for the next time step, which means that the encoding of a word strongly affects only the representation of the next word, so its influence is quickly lost after a few time steps. LSTM (and also GruRNN) can boost a bit the dependency range they can learn thanks to a deeper processing of the hidden states through specific units (which comes with an increased number of parameters to train) but nevertheless the problem is inherently related to recursion. Another way in which people mitigated this problem is to use bi-directional models. These encode the same sentence from the start to end, and from the end to the start, allowing words at the end of a sentence to have stronger influence in the creation of the hidden representation. However, this is just a workaround rather than a real solution for very long dependencies.
  
  # CNN
  
  Also convolutional neural networks are widely used in nlp since they are quite fast to train and effective with short texts. The way they tackle dependencies is by applying different kernels to the same sentence, and indeed since their first application to text ([Convolutional Neural Networks for Sentence Classification](https://arxiv.org/pdf/1408.5882.pdf)) they were implement as multichannel CNN. Why do different kernels allow to learn dependencies? Because a kernel of size 2 for example would learn relationships between pairs of words, a kernel of size 3 would capture relationships between triplets of words and so on. The evident problem here is that the number of different kernels required to capture dependencies among all possible combinations of words in a sentence would be enormous and unpractical because of the exponential growing number of combinations when increasing the maximum length size of input sentences.
  
  To summarize, Transformers are better than all the other architectures because they totally avoid recursion, by processing sentences as a whole and by learning relationships between words thanks to multi-head attention mechanisms and positional embeddings. Nevertheless, it must be pointed out that also transformers can capture only dependencies within the fixed input size used to train them, i.e. if I use as a maximum sentence size 50, the model will not be able to capture dependencies between the first word of a sentence and words that occur more than 50 words later, like in another paragraph. New transformers like [Transformer-XL](https://arxiv.org/abs/1901.02860) tries to overcome exactly this issue, by kinda re-introducing recursion by storing hidden states of already encoded sentences to leverage them in the subsequent encoding of the next sentences.
  
  > **Comments:**
  > **username_1**: It's not clear from this answer what you mean when you say that "transformers process sentences as a whole". Do you mean that first you create word embeddings that represent whole sentences rather than words? I think that you should have mentioned the encoder-decoder architecture with LSTMs, because it seems that this "processing sentences as a whole" already existed in other machine translation architectures with LSTMs (like neural machine translation and stuff like that), so that would not be a novel thing.  
  
  ---
  
  ### Answer by username_2 on 2020-04-07. Score: 12
  
  Let's start with RNN. A well known problem is vanishin/exploding gradients, which means that the model is biased by most recent inputs in the sequence, or in other words, older inputs have practically no effect in the output at the current step.
  
  LSTMs/GRUs mainly try to solve this problem, by including a separate memory (cell) and/or extra gates to learn when to let go of past/current information. Check these series of [lectures](https://youtu.be/QEw0qEa0E50) for more in-depth discussion. Also check the interactive parts of [this article](https://distill.pub/2019/memorization-in-rnns/) for some intuitive understanding of dependency on past elements.
  
  Now, given all this, information from past steps *still* goes through a sequence of computations and we're relying on these new gate/memory mechanisms to pass information from old steps to the current one.
  
  One major advantage of the transformer architecture, is that at each step we have **direct** access to all the other steps (self-attention), which practically leaves no room for information loss, as far as message passing is concerned. On top of that, we can look at both future and past elements at the same time, which also brings the benefit of bidirectional RNNs, without the 2x computation needed. And of course, all this happens in parallel (non-recurrent), which makes both training/inference much faster.
  
  The self-attention with every other token in the input means that the processing will be in the order of $\mathcal{O}(N^2)$ (glossing over details), which means that it's going to be costly to apply transformers on long sequences, compared to RNNs. That's probably one area that RNNs still have an advantage over transformers.
  
  > **Comments:**
  > **username_1**: Why can you look at both the future and past elements at the same time without 2x computation?  
  > **username_2**: A bidrectional RNN has a forward and a backward RNN, which means we process the whole sequence 2 times. It's basically a hack so that we have some way to look at the future using the backward RNN. In transformers, this is done in "one" operation, which is just calculating the result of `softmax(QK) x V`  
  > **username_3**: Any benefit of Positional Encoding? Does it make possible Self Attention for longer sentence?  
  
  ---
  
  ### Answer by username_4 on 2022-01-26. Score: 2
  
  [![arxiv:1706.03762](https://i.sstatic.net/ULJvS.jpg)](https://i.sstatic.net/ULJvS.jpg)
  *table is on page 6 from [arxiv:1706.03762 Attention Is All You Need](https://arxiv.org/abs/1706.03762)*
  
  It's because of the path length. If you have a sequence of length n. Then a transformer will have access to each element with O(1) sequential operations where a recurrent neural network will need at most O(n) sequential operations to access an element.   
  Very long sequences gives you problem with exploding and vanishing gradients because of the chain rule in backprop.   
   Transformers don't have this problem as the distance to each element in the sequence is always O(1) sequential operations away. (as it selects the right element instead of trying to "remember" it)
  
  Yet there is a paper to handle longer input using RNN structure.
  
  > **Comments:**
  > **username_3**: Is the Sequential Operations for a layer or entire structure for Transformer? My guess is that Sequential Operations for LSTM is entire structure. By the way is the Complexity per Layer sounds like Space Complexity (not Time Complexity)  
  > **username_4**: It's per layer. Yes, a lstm block is considered to be a single layer (as they tend to be stacked). What do you mean with entire structure, do you mean the unrolled architecture? They basically just say what the span is of the architecture, for lstm's you have to wait for the previous token to finish computing before computing the next one so you get a span of O(n), where self attention and convolution (during training) don't have to wait sequentially O(1) span.  
  > **username_4**: For convolution I've to check but the time and space complexity of attention is O(n^2*d) and for recurrent O(n*d^2).  
  > **username_3**: For the "entire structure", I meant whole network strtucture not one module (ref: https://colah.github.io/posts/2015-08-Understanding-LSTMs/). For the complexity, I still don't get clear picture. Thanks for additional explantion though.  
  > **username_4**: The post you send shows for a single layer the unrolled structure, so repetition of the lstm's module along the sequence length. We look at the layer perspective in this case, so for the lstm that is a single unrolled layer. (this can be different from the whole network structure as you can also layer these unrolled lstm layers on-top of each-other)  
  > **username_4**: (the stacking can be done by feeding the (Ht-n,..,Ht-1,Ht,Ht+1,...,Ht+n as the (entire) Xt sequence for the layer ontop. The O(n) time and memory complexity for the lstm comes from the unrolling over the entire sequence, so it needs to process each and every element in the sequence at-least once (and store it for the computational graph to do backprop). In self attention (from attention is all you need) you have O(n^2) memory and compute since you have every element in the sequence message pass to every other element in the sequence. O(n^2)  
  > **username_4**: in causal (self) attention you just mask away the messages so the structure is causal, but the full n^2 matrix (from the dot product between the key and queries, what when normalized with the softmax will represent the amount of "communication" between each token (element in the sequence)) is still formed it's just masked with a triangular zero's matrix.  
  > **username_4**: so the O(n) for lstm's comes from the fact they form a chain and pass messages along the chain sequentially and self attention forms a fully connected graph where at once all nodes messages pass to all other nodes giving a O(n^2). This is also why the path length is so short in attention as each node (item in the sequence) is at-most 1 edge away from every other node, where in lstm's (or other recurrent networks) it tends to be a chain so at-most you are n-1 edges away  from another node  
  > **username_4**: I hope this sheds a bit more light on it. :)  
  
  ---
  
  ### Answer by username_5 on 2020-04-21. Score: 1
  
  First: RNN is one part of the Neural Network family for processing sequential data. The way in which RNN is able to store information from the past is to loop in its architecture, which automatically keeps information from the past stored.
  Second: sltm / gru is a component of regulating the flow of information referred to as the gate and GRU has 2 gates, namely reset gate and gate update. If we want to make a decision to eat like the analogy above, resetting the gate on the GRU will determine how to combine new inputs with past information, and update the gate, will determine how much past information should be kept.
  source : <https://link.springer.com/article/10.1007/s00500-019-04281-z>
  
  > **Comments:**
  > **username_6**: Hi @Lutfizain, welcome to AI stack exchange! Please [see the tour](https://ai.stackexchange.com/tour) and look around to see how this site works. I think you aren't answer the question, OP is asking why transformer (kind of NN architecture) performs better than RNN/LSTM on that context, and you didn't mention it  
  
  ---
  
  