How much memory does Longformer use?
deep learning machine learning nlp natural language processing machine translation arxiv google attention mechanism attention transformer tensor2tensor rnn recurrent seq2seq
A calculation of the memory requirements of the Longformer.

Original video: https://youtu.be/_8KNb5iqblE
Paper: https://arxiv.org/abs/2004.05150

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
 So I wanted to come back to this paper here about the longformer. I have done a video on this. If you haven't seen it then this video is probably not going to make much sense to you. But in the video I go over what the longformer is, what it does, how it compares and so on. And the gist of the longformer is that it can now do a transformer model on a long document as you can read here. So I've gotten a lot of questions of like does that mean we can now have much longer documents, right? The BERT model doesn't fit into my memory, can this solve my problem? And I just kind of want to go into the math of the longformer memory requirements here because I think I've alluded to it but it is quite a... I think the graphics here are just a bit misleading from the way they implement it. Now I've already gone over something like this in the last thing. So Roberta, let's spell this correctly, Roberta, that is their baseline, has a size, a let's call that N0 of 512. So they can have 512 tokens at the same time. So if you have a sequence that is way longer than 512 you need to chunk it up into pieces of 512 and usually you do something like overlapping pieces or something like this, right? And now the promise of the longformer as it is in the paper is that you can put all of this into the longformer, right? And it will do this sliding window attention thing where it basically slides a window here, this window, across this input sequence and only does this local attention, right, within the window. And then it also has some global attention that it constantly has. Now what I find interesting is that in their experiments their window size here, so the longformer window size is 512, right? So within that window you have the classic N squared full attention, right? So let's just go into that. How much memory does the longformer really do? We've already calculated it here a bit but I want to take this still apart a bit. So as you can see on the left here you have N times W that you have for this middle band, right? So this middle band is N times W. Then you want to add the global attention, right? So the global attention, you can already see it right here, if you have one, two, three, four locations of global attention you have four times two because you also have them in this direction, right? You have them in both directions times your full sequence length. So plus two times full sequence length times the number of global attention. I call this S over here. So as we saw up here the window size here was N zero in their experiments. So let's replace this window size by N zero and actually let's factor out the N. So we'll get to N times N zero plus 2S. Alright, so you can already see that Roberta originally had N zero squared. Now if N is larger than N zero that means you already use more here. The kind of trick, it's not really a trick, it is true that this is order of N, right? If N is your input sequence length but in this here is technically order of N squared if N, if this is N. But the sequence length in Roberta was the window size of the long former. So this is N zero squared, right? And here technically you'd have to say this is N times N zero. So if N is larger than N zero you can see that this uses more memory given that. So in their experiments they use a model that on paper uses more memory than the baseline model and saying that it scales linearly with sequence length is because, I mean of course it scales linearly because they can now input these long sequences, right? And the attention, sorry the memory requirements scales basically linear and also linear with the window size. Now the window size still needs to be apparently large-ish in order to achieve the performance. So the fact that the performance is equal or better is not really a secret because it uses more memory, right? It's not like this model uses less memory but outperforms the old one, it uses more. If you want to look at it you have to ask, okay I have Roberta and right now I can do N squared. So this is N, this is N, so there's N zero, N zero. This is my sequence length that I can put into Roberta. You have to ask yourself what kind of sequence do I want to put in? And if you say I want to put in a sequence that's twice as long, right? I want to put in this long of a sequence, so N here would be twice N zero. Then you have to take this, put it here, put it here and then you realize, yes, that your window size of the long former can only be half, right? So if you have the same amount of memory you can double your sequence length at the cost of having your window size but that doesn't yet include the cost of the global attention. So any global attention you do will come basically on top of the window size. You see this here, right? So you decide on, let's do it like this, you decide on how long you want your thing, your input sequence length to be, then you decide, and that means that's this rectangle here, then you decide how many global attentions do I want and here I say I want one global attention and you have to cross out as many rows here as you want global attention and what remains is your window. Actually you have to cross out twice but we don't have, we only have one left, but you get the point. You have to cross out two times S rows of how many global attentions you want and what remains will be your window size. In this case it's just a window size of one. So that's how you would construct a longformer that takes in the same amount of memory as a your classic model but can take a full n sequence length. Alright? So I just wanted to kind of make that clear, go through the calculation myself and I hope that helped. Thanks for listening and if you liked this consider subscribing, liking and bye bye.
 So I wanted to come back to this paper here about the longformer. I have done a
 video on this. If you haven't seen it then this video is probably not going to
 make much sense to you. But in the video I go over what the longformer is, what it
 does, how it compares and so on. And the gist of the longformer is that it can
 now do a transformer model on a long document as you can read here. So I've
 gotten a lot of questions of like does that mean we can now have much longer
 documents, right? The BERT model doesn't fit into my memory, can this solve my
 problem? And I just kind of want to go into the math of the longformer memory
 requirements here because I think I've alluded to it but it is quite a...
 I think the graphics here are just a bit misleading from the way they implement
 it. Now I've already gone over something like this in the last thing. So Roberta,
 let's spell this correctly, Roberta, that is their baseline, has a size, a
 let's call that N0 of 512. So they can have 512 tokens at the same time. So if
 you have a sequence that is way longer than 512 you need to chunk it up into
 pieces of 512 and usually you do something like overlapping pieces or
 something like this, right? And now the promise of the longformer as it is in
 the paper is that you can put all of this into the longformer, right? And it
 will do this sliding window attention thing where it basically slides a window
 here, this window, across this input sequence and only does this local
 attention, right, within the window. And then it also has some global attention
 that it constantly has. Now what I find interesting is that in their experiments
 their window size here, so the longformer window size is 512, right? So
 within that window you have the classic N squared full attention, right? So let's
 just go into that. How much memory does the longformer really do? We've
 already calculated it here a bit but I want to take this still apart a bit. So
 as you can see on the left here you have N times W that you have for this middle
 band, right? So this middle band is N times W. Then you want to add the global
 attention, right? So the global attention, you can already see it right here, if you
 have one, two, three, four locations of global attention you have four times two
 because you also have them in this direction, right? You have them in both
 directions times your full sequence length. So plus two times full sequence
 length times the number of global attention. I call this S over here. So as
 we saw up here the window size here was N zero in their experiments. So let's
 replace this window size by N zero and actually let's factor out the N. So we'll
 get to N times N zero plus 2S. Alright, so you can already see that Roberta
 originally had N zero squared. Now if N is larger than N zero that means you
 already use more here. The kind of trick, it's not really a trick, it is
 true that this is order of N, right? If N is your input sequence length but in
 this here is technically order of N squared if N, if this is N. But the
 sequence length in Roberta was the window size of the long former. So this
 is N zero squared, right? And here technically you'd have to say this is N
 times N zero. So if N is larger than N zero you can see that this uses more
 memory given that. So in their experiments they use a model that on
 paper uses more memory than the baseline model and saying that it scales
 linearly with sequence length is because, I mean of course it scales linearly
 because they can now input these long sequences, right? And the attention, sorry
 the memory requirements scales basically linear and also linear with the window
 size. Now the window size still needs to be apparently large-ish in order to
 achieve the performance. So the fact that the performance is equal or better is
 not really a secret because it uses more memory, right? It's not like this model
 uses less memory but outperforms the old one, it uses more. If you want to look at
 it you have to ask, okay I have Roberta and right now I can do N squared. So this
 is N, this is N, so there's N zero, N zero. This is my sequence length that I can put
 into Roberta. You have to ask yourself what kind of sequence do I want to put
 in? And if you say I want to put in a sequence that's twice as long, right? I
 want to put in this long of a sequence, so N here would be twice N zero. Then you
 have to take this, put it here, put it here and then you realize, yes, that your
 window size of the long former can only be half, right? So if you have the same
 amount of memory you can double your sequence length at the cost of having
 your window size but that doesn't yet include the cost of the global
 attention. So any global attention you do will come basically on top of the window
 size. You see this here, right? So you decide on, let's do it like this, you
 decide on how long you want your thing, your input sequence length to be, then
 you decide, and that means that's this rectangle here, then you decide how many
 global attentions do I want and here I say I want one global attention and you
 have to cross out as many rows here as you want global attention and what
 remains is your window. Actually you have to cross out twice but we don't have, we
 only have one left, but you get the point. You have to cross out two times S rows
 of how many global attentions you want and what remains will be your window
 size. In this case it's just a window size of one. So that's how you would
 construct a longformer that takes in the same amount of memory as a your classic
 model but can take a full n sequence length. Alright? So I just wanted to kind
 of make that clear, go through the calculation myself and I hope that helped.
 Thanks for listening and if you liked this consider subscribing, liking and
 bye bye.