Big Bird: Transformers for Longer Sequences (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper google google research bigbird big bird bert attention attention is all you need longformer random attention quadratic attention attention mechanism qa natural questions hotpot qa genomics nlp natural language processing transformer transformers fully connected sparse attention graph star graph turing complete universal approximation window attention convolution
#ai #nlp #attention

The quadratic resource requirements of the attention mechanism are the main roadblock in scaling up transformers to long sequences. This paper replaces the full quadratic attention mechanism by a combination of random attention, window attention, and global attention. Not only does this allow the processing of longer sequences, translating to state-of-the-art experimental results, but also the paper shows that BigBird comes with theoretical guarantees of universal approximation and turing completeness.

OUTLINE:
0:00 - Intro & Overview
1:50 - Quadratic Memory in Full Attention
4:55 - Architecture Overview
6:35 - Random Attention
10:10 - Window Attention
13:45 - Global Attention
15:40 - Architecture Summary
17:10 - Theoretical Result
22:00 - Experimental Parameters
25:35 - Structured Block Computations
29:30 - Recap
31:50 - Experimental Results
34:05 - Conclusion

Paper: https://arxiv.org/abs/2007.14062

My Video on Attention: https://youtu.be/iDulhoQ2pro
My Video on BERT: https://youtu.be/-9evrZnBorM
My Video on Longformer: https://youtu.be/_8KNb5iqblE
... and its memory requirements: https://youtu.be/gJR28onlqzs

Abstract:
Transformers-based models, such as BERT, have been one of the most successful deep learning models for NLP. Unfortunately, one of their core limitations is the quadratic dependency (mainly in terms of memory) on the sequence length due to their full attention mechanism. To remedy this, we propose, BigBird, a sparse attention mechanism that reduces this quadratic dependency to linear. We show that BigBird is a universal approximator of sequence functions and is Turing complete, thereby preserving these properties of the quadratic, full attention model. Along the way, our theoretical analysis reveals some of the benefits of having O(1) global tokens (such as CLS), that attend to the entire sequence as part of the sparse attention mechanism. The proposed sparse attention can handle sequences of length up to 8x of what was previously possible using similar hardware. As a consequence of the capability to handle longer context, BigBird drastically improves performance on various NLP tasks such as question answering and summarization. We also propose novel applications to genomics data.

Authors: Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, Amr Ahmed

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
Parler: https://parler.com/profile/YannicKilcher
LinkedIn: https://www.linkedin.com/in/yannic-kilcher-488534136/

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hi there, today we'll look at Big Bird Transformers for Longer Sequences by Manil Zahir and Gurugar Uganesh et al. of Google Research. So this paper on a high level proposes to replace the quadratic attention mechanism in transformers by a mix of random attention, windowed attention, and selective global attention, therefore achieving a complexity of linear memory requirement instead of quadratic memory requirement. And as a result of that, they can process longer sequences than traditional transformers like BERT and achieve better results in some NLP tasks, and they also evaluate on genomics tasks. So we'll go through this paper a bit, look a bit at the proof because they give a theoretical kind of guarantee that their random attention mechanism can still be Turing complete and can still achieve the same things as a full attention mechanism, but we'll also look at the drawbacks. I sort of have mixed feelings about this paper, and I think I'll voice my concerns as we go through here. But first, let's look at the paper, let's look at the architecture, and I think this is actually a pretty cool paper for the empirical progression of the field to process longer sequences with transformers. As always, if you like content like this, feel free to share it around, leave a like and tell me in the comments what you think about the paper and about what I think, whatever, you just, just go nuts. Alright, so the basic premise right here is that the transformers, they've been pretty impactful, especially in NLP. So they say transformer based models such as BERT have been one of the most successful deep learning models for NLP. Unfortunately, one of their core limitations is the quadratic dependency, mainly in terms of memory, on the sequence length due to their full attention mechanism. So really briefly, the full attention mechanism, and I've done numerous videos about attention mechanism BERT, attention is all you need, and so on. So if you want a detailed explanation of what that is, just go look up the corresponding videos. But briefly, what you'll have in NLP is a set of tokens, a sequence of tokens as an input, and you want to transform them layer after layer into sort of a higher order representation of that same sequence. And for that, you build these layers out of nodes and you have as many nodes usually as you have tokens in the sequence. And the next set of, so each token is represented by a vector at the beginning, and each layer transforms the sequence, as I said, into sort of a higher level representation. So you want the vector of this token right here to be a better representation than the vector was right here. And you do that by incorporating information from all the other tokens into that particular vector. Now, as I said, this is called an attention mechanism, and we don't actually have to go into how it works right here, but you can see pretty clearly that if you want to do this for every token, you need to have information routed from every token to every token, like from here to here, from here to here, and so on. And this is just one token, and then you need to do it for this token and for this token and for this token. So what you'll ultimately get, if n is your sequence length, you'll get some n squared amount of computation and memory requirements for this. So this is a problem. And usually, this means that, you know, this sequence length in BERT, this is limited to something like 512 tokens, which is okay for some applications. But if you want to summarize, you know, entire articles, entire books, even, or do question answering with lots of context, it's not really enough. So people have been thinking about how to scale this input, how to scale this. And of course, the main culprit is this quadratic attention mechanism, because if you, you know, scale the 512, you need, you know, four times the amount of compute and memory. So how does this paper go about reducing that quadratic dependency? The goal right here is, of course, to get this to some O of n, right? Because then, as we double the input length, we simply need to double the compute requirements, and that would be fantastic. And that's what this paper does. And it does so without sacrificing the properties of the transformer. So here's the architecture that Big Bird proposes. By the way, Big Bird, another character from Sesame Street, I guess, will continue the naming here after Elmo and BERT. You know, I'm waiting for the model that's the count. Yeah, that's going to be a fun model. So Big Bird basically has three different types of attention. And here, these are adjacency matrices in this attention mechanism. So here is the input layer, and the output layer is right here. So that basically means that node i right here would be connected. Sorry, that's not a straight line, would be connected to this particular node and also to this particular node. So we're now trying, if we have node i right here, we're now trying to not connect it to all of these nodes, but we'll say, we'll just select some at random and then connect it to that. Okay, this is what we call random attention. And you can pretty clearly see if you connect each of the i nodes to r equals 2, to two random nodes, then you don't have an n squared anymore. But you'll have a like an O of r times n, which you know, if r is a constant is an O of n attention mechanism. Okay, so the main goal between the random attention mechanism is that for each query, basically, you select random tokens that you attend to, and that random number is a fixed number that's not dependent on the sequence length. And the paper is a little bit unclear about whether or not those random ones are the same for every sequence or are switched up, or the same for every layer or are switched up. But they formulate all of this as sort of in sort of a graph in sort of a random graph. So they're, they formulate the attention mechanism in form of a graph. So if we transform all of these nodes into a graph, a full attention mechanism would mean that each graph, each node is connected to each of the other nodes, right, fully connected graph, I don't, maybe that's it. So that would be a full attention mechanism. And then they say, well, if we just have random connections between these things, then there are some theorems from graph theory that say that each random walk in this graph is going to, so this graph is going to mix pretty quickly. So I can get from each node to each other node by a random walk in a logarithmic time. And this random walk, which basically means that you go from here to here, this would be one layer of the transformer. And then if you want to go from here to here, that you would have to do that in the next layer. So this formulation as a random graph leads me to believe that layer after layer, the random attention pattern is going to be the same. But also the formulation of the paper leads me to believe that the this random attention differs from sequence to sequence. So I believe what's happening is that they get a new sequence, then they decide on this pattern right here once and then they use this layer after layer, the same pattern again. So you can see that in the traditional attention, information can basically flow from each of the nodes to each other node in one single step, right? Because each node is connected to each other node. You see this in the graph right here. However, if we only select a subset, then you know, it needs to if I want to go from, as I said, from here to here, then I need to do it in two steps. And therefore I need two layers. And that's going to be the culprit of this method here. And while it is mentioned in the paper, it's sort of I feel at least that's my my assessment of this paper, it's kind of swept under the rug a little bit. I mean, they do have a theorem that clearly says we can construct an example of a task that in the full attention setting can be solved with a single step. So a single layer that in our random attention setting needs a lot of layers, a lot of steps. But you know, the rest of the paper is sort of shaky on on this thing. But nevertheless, you can see how the random attention can, if you have enough layers, do the same information routing as the full attention. Okay. However, this is not a property of the random attention. And we'll see this in the next thing right here. So the next ingredient that this paper uses is window attention. And you can see over here that Big Bird is ultimately going to be a combination of the three types of attention, which will, which we are looking at here. So window attention basically means that each each i each token at the i of position is going to attend to itself, of course. So here is i, but it is also going to attend to its neighbors. So here is i minus one and here is i plus one. And this is a you know, this is a window size w that you can that is a parameter, but also it is a constant and therefore you again go from n squared to w times n, which you know is o of n if w is a constant. And this might be familiar to you, because we've already seen this in the long former paper. We made a video or I think even two videos on the long former, which used exactly the window attention in combination with the global attention. And if you want to know more about that, go watch these videos. But the new thing in Big Bird right here is this addition of the random attention. Again, the the window here is is has exactly the same properties as the random attention. So you have instead of a fully connected graph, you have a sparsely connected graph. Now if you have random attention, the sparsely connected graph is like like the one on the right. But if you have a windowed attention, you can it is kind of not randomly connected, but each node is connected to its neighbors like this. And you can also see that if I want to go from this node to this node right here, I can't do it in one step, but I can do it in two steps. I go here and I go here. So in the terms of the attention layers, if I want to go from node one to node three, I have to do it in two steps because each node is only connected to its neighbors. So the connection patterns would sort of look like this. So I have to go from one to two and then in the next layer from two to three. So the paper basically makes up for the lack of full attention by adding layers. And you also might recognize this from a convolution operation. This basically because it is a convolution operation, right in a convolution, each node only aggregates input from its neighbors for the next layer. And then we know that as we go up the layers, the de facto window that each node looks at is going to be like a cone kind of like this. So this is very similar to how a convolutional neural network works. And the reasoning is very similar because the reasoning is, well, in a sentence, the most important words for any given word are probably going to be its neighbors, like the words around it. And as you go up the layers, you branch out more and more. But ultimately, this neighborhood principle holds in NLP as well. So again, we already saw this in the long former, but that's the reason behind the window attention and that's the second ingredient. And then the third ingredient is this global attention. Now the global attention is selected tokens that are so important and that's fixed by the developers that are so important that they are connected to everything else. So for example, in these transformers, you often have what's this kind of CLS token. So this is a special token that you prepend to some piece of text and the output of this token is going to be your classification output because you don't want to bind your classification if you need to classify the entire sequence. You don't want to bind that decision to one particular word. What you want to do is you want to have an extra token and that's this CLS token that kind of aggregates information from all of this. So layer after layer, layer after layer, you'll have, so if we go here, layer after layer, we have this one special node. And in each step, every single other node is able to send information right here to this node and receive information from this node. So now, as a result of this, as you may be able to see, every single path is kind of a maximum length of two because if I want to go from any node to any other node, I can simply send information to this global node and then the global node in the next step can send information to whatever other node. And that is a property that they use in their proof that this attention mechanism is as sort of as powerful as the classic full attention mechanism. And we'll go through that in one second. But first, I hope this was clear that this combination of random attention, window attention and global attention is what is called Big Bird. They have some engineering tricks that go along with this, but in concept, you can imagine Big Bird being long former plus these random attention right here. And as an engineer, as an NLP engineer, that makes kind of total sense. I totally believe that the introduction, the addition of these random attention of these random attention patterns can absolutely help your classification or whatever your NLP tasks because more attention, better. And I also am completely willing to believe that using the full attention matrix, while it is, of course, more accurate, it won't hurt too much to leave some of that attention away because essentially all the path lengths are just becoming two or even with the random attention are really short or logarithmic to route information from a node to some other node. So the loss that you incur is kind of in a logarithmic scale in terms of performance, while the gain that you make is sort of in a in a quadratic or like a linear scale, you go from quadratic to linear. And that seems to me like a good empirical trade off. All right, however, the the proofs here, the proof of of how how these how these things are constructed are a little bit. I don't know. So what they do in the proof that this function can sort of is a universal approximator. People have already shown that full attention mechanisms are universal approximators. So they show here that this sparse attention mechanism is also a universal approximator. They make big use of star graphs. What they say is, OK, if we have a star graph, which is one node connected right here to every other node, this is a star graph. If we have a star graph, we can achieve the same thing than with a full graph. A full graph is where every node is connected to every other node. But as I already said, what they need for this is multiple layers of this star graph. So and that has to do with the fact that if I want to route information, I basically have to go via this middle node right here. And there is an additional complication because this middle node in our case right here is only one node. I can't route information at the same like I can't have this routing right here at the same time that I have this routing right here, like going from here to here, because I only have one middle node. And I kind of this is not how that like this is very dumb math. But maybe you have to imagine that there is one memory slot. And you can only use that one memory slot at the same time for one of these things. So essentially, what you'll have to do is you'll have to do the green thing first. And then in the next step, you'll have to do the blue thing second. And then so these are now pairwise routing between nodes. But ultimately, what an attention mechanism does is it does everything to everything right in a single layer, it routes information from all the nodes to all the other nodes. And to achieve that, so you need multiple rounds of this. And it turns out that in the worst case, you actually need n rounds of this. So you know, you trade off your you go from n squared to n memory and compute requirements in a single layer. But in the worst case, you need n layers to recover the power of the full of the full transformer. And that is the last one of their theoretical results right here. So first, they prove universal approximations. And second, they prove Turing completeness. These two properties have been proven for full attention mechanisms. And third, they prove that there are tasks where you actually do need n layers to solve them with their limited attention. So you know, I'm not sure but I feel you can make any sort of polynomial algorithm into a linear algorithm like this. Like I have a I have like a cool sorting algorithm, right? So if this is my sequence that I want to sort, what I can do is I can simply, you know, take a random subset of them, like this, this and this and then kind of go and sort them and then put them like I send them to the to the global memory like this, I sort them, and then I put them back, right? And if I do this for enough, if I do this for enough rounds, okay, you know, if I do this for enough rounds, you know, at the worst case, I need n rounds to sort my or log n rounds if I do it smartly. But you know, in, you know, the single step here is the single step is just O of n. So I have now an O of n sorting algorithm. I you know, I have my sort of a bit of worry to express things like that. And yeah, but you know, it is from an empirical standpoint, I absolutely believe that this this is enough. Now my second coral right here is that if you look at the proof, first of all, what it makes use is this star graph, and the star graph corresponds to the global attention. So that's not much to do with the random attention, though they use the random attention in their proof, but I at least believe that it would be possible with the global attention only. And then the second thing is if you look at the parameters that they use for the for the experiments, and I've already said this in the long former video. So in the long form of video, it turned out that if you look at how big these window attention is, it turns out that it you're still well, you know, the original BERT attended to 512 tokens. And then you look at the window and the window was still 512 tokens. It's just that the global attention was even more so ultimately they ended up using more memory than the original BERT. And here, if I look at the parameters of their thing, and they have multiple experiments right here, and I believe this is the the base version. So this is the base version, they also have this large version. But here, this is the 12 layer version. And you can see they have this block length. And we'll get into the block length in one second. But then you can see that their window size is three times the block length, the number of random tokens is three times the block length, and the number of global tokens is two times the block length. So that results in eight times B. So eight times 64 is, you know, Can I calculate this? Or am I stupid? It's 512. Yes, actually calculated this before. So this is 512 tokens. So you know, you you go from from BERT that has 512 tokens and attends to 512 tokens to also attending to 512 tokens. Of course, the advantage here is that they now have 4096 sequence length. So they have the freedom to not attend to as many tokens as they have in the input length. But you know, to put it in perspective, this here uses more memory and more compute on on its face than BERT, because BERT attends to as many tokens but has a smaller input sequence. And you know, I, there's sort of a thing where in order to make these sparse attention things work, you have to go pretty, pretty, you know, high in the number of things you attend to, you can leave away some but it's not like you can scale up orders of magnitude of your input sequence length. So that's the this promise of linear attention is sort of it's kind of fulfilled but not there yet. The second thing I would like to point out is that in a lot of cases, the number of random tokens is actually set to zero. So really making use, I believe, of these of the of the global of the number of global tokens. So it that seems a bit strange in that they continuously refer to their random attention mechanism. But then in a lot of experiments, they don't actually have a random attention mechanism. I believe they have to do that because that's kind of what makes them different from the long former in principle, but still, yeah. So the last novelty, let's say is an engineering novelty in that they now always consider not single, for example, they don't consider single random attention, they always consider these in blocks. And that's because our current hardware is really bad at sparse stuff. Really bad at single indexing, gathering single things. So if you can do everything in blocks, you basically get you get these blocks almost for free. So it takes only marginally longer to retrieve this full two by two block right here than it would to retrieve the single instance right here. Of course, that means you have, you know, four times you still use four times more memory, but it is not four times slower than the original thing. So you can use these blocks right here. You can do it for the random attention, you can do it for the window attention, as you can see here. So you break this window pattern a little bit into blocks. And that makes it a lot faster. So that speeds up, get the speed up almost for free. And then they make another approximation in that the way they do this windowing is, and I just go really briefly. So you can see right here that it would be very cumbersome to gather. So what we need, we're just going to focus this this dotted thing right here is a bit confusing. So you want to attend to these things. And these you can just get out with a matrix slice really easy. But then you want to attend to this kind of blocky thing right here from the window attention, right, like this thing. And this is hard to get out because you'd have to kind of index each row individually. And that's very slow. So what they do, there is this matrix roll operation, where you can sort of roll the axis around. So what you'll do is you'll take this thing right here, and you put it to the left right here, and you'll take, for example, this thing right here, and you'll put it to the right or no, like it's, it's up and down. But in essence, that's what you do. And you can you can fold all of this blue stuff into a rectangular matrix. If you know if you can see right here. So you kind of roll this back, roll this back, roll this forward, and you replace whatever is missing by these. Now this again gives you some inaccuracies because this block right here was never intended to be attended to. And all of a sudden you see you have the K6 in here. So it gives you a bit of inaccuracies at the edges of the sequence. But you can take that, you know, you can take that hit for the increased performance that you gain by now having a rectangular matrix. TPUs are really efficient at this, not as efficient at this. And then the only thing that's really slow is gathering these random blocks right here. But also by having the same amount of random blocks per input token, what you'll do is you'll end up with just one of these columns right here, or you know, R of these columns. And that again gives you a rectangular matrix. So this thing right here you can process very, very efficiently using a TPU. And you know, the mistakes you make are basically this thing right here and this thing right here, because those weren't intended and are at the edges of the sequence. So these were the tricks of Big Bird to quickly summarize. Big Bird is basically taking a transformer saying, well, why do we need all of this attention, all of this full attention, maybe we only need some of that and can already do a big job, a good job, especially, you know, considering the attention mechanism goes over multiple layers. So we don't need a routing from each token to each token, we can make up for not having a fully connected graph by simply running multiple layers. So their sparsity is first of all, you have this random attention, which I believe changes from sequence to sequence, but stays within or among the layers of the same sequence. Then you have the window attention with the reasoning. So the reasoning behind the random attention is that if you have a randomly connected graph, the path lengths are on average logarithmic. So you can route information efficiently. The reasoning behind the window attention is that probably neighbor information is very important and that has been shown empirically. And then the global attention, the reasoning behind this is that some of the tokens that are fixed by the developers are so important that it's very beneficial that each other node is connected to them and that they are connected to each other node. The result of that is the Big Bird attention mechanism, which is basically long former, which already had these two plus the random attention. This achieves a linear complexity in terms of memory and compute, though linear has to be qualified a bit because it's modified by the window size, by the number of random attention tokens, by the number of global tokens, and in practice often ends up being fairly large ish. And also the theoretical guarantees now come with the fact that you need multiple layers. In the worst case, you need sequence length amount of layers, which in the worst case would result right back into a quadratic requirement for memory and compute. They do some engineering, some engineering tricks right here, and their results are pretty good. So the results in various tasks and we'll, we'll look at some of the tasks right here. So these are def set results using base size models. For example, where you can see they do outperform basic Roberta models, they outperform long former, which may mean that the random attention is useful, but you know, in these things, it's also always may just mean that you've thrown more compute at it. At least I'm not really looking that they outperform the models because as you can see right here, if they compare to state of the art and you know, granted, these are models that have been trained specifically for these tasks and are crafted and engineered and Big Bird manages to Big Bird manages to hold itself against them in a lot of tasks and even get state of the art on some. What I'm more interested in is that it, you know, it can reach good numbers. It doesn't necessarily have to be state of the art, but it can reach good numbers, which tells me that, okay, probably the, the empirical hit that I take by not having the full attention is, you know, is justifiable by the speed up and memory savings I do get. Yeah, especially when result, when you see results mixed like this, you know, sometimes the other model is good and sometimes the Big Bird is good on different variations and so on. I would not, you know, I would not make a big deal out of the fact that it is state of the art. I get that the authors have to do that. I would do so as well, but you know, you don't, don't think that this is the, like the best thing now. It's very probable. They just thrown also a lot of compute at it. What is cool is they do some genomics experiments. So not only do they have NLP state of the art, but also they go into genomics and experiment with data there. I don't want to go into that because ultimately it's another task and I believe the paper is about the architecture. All right. So that was Big Bird. I hope you enjoyed this video and learned. I learned something. Certainly. If you want to check out the proofs, they're actually pretty entertaining to read and yeah, I'll see you next time. Bye bye.
 Hi there, today we'll look at Big Bird Transformers for Longer Sequences by Manil Zahir and Gurugar
 Uganesh et al. of Google Research.
 So this paper on a high level proposes to replace the quadratic attention mechanism
 in transformers by a mix of random attention, windowed attention, and selective global attention,
 therefore achieving a complexity of linear memory requirement instead of quadratic memory
 requirement.
 And as a result of that, they can process longer sequences than traditional transformers
 like BERT and achieve better results in some NLP tasks, and they also evaluate on genomics
 tasks.
 So we'll go through this paper a bit, look a bit at the proof because they give a theoretical
 kind of guarantee that their random attention mechanism can still be Turing complete and
 can still achieve the same things as a full attention mechanism, but we'll also look at
 the drawbacks.
 I sort of have mixed feelings about this paper, and I think I'll voice my concerns as we go
 through here.
 But first, let's look at the paper, let's look at the architecture, and I think this
 is actually a pretty cool paper for the empirical progression of the field to process longer
 sequences with transformers.
 As always, if you like content like this, feel free to share it around, leave a like
 and tell me in the comments what you think about the paper and about what I think, whatever,
 you just, just go nuts.
 Alright, so the basic premise right here is that the transformers, they've been pretty
 impactful, especially in NLP.
 So they say transformer based models such as BERT have been one of the most successful
 deep learning models for NLP.
 Unfortunately, one of their core limitations is the quadratic dependency, mainly in terms
 of memory, on the sequence length due to their full attention mechanism.
 So really briefly, the full attention mechanism, and I've done numerous videos about attention
 mechanism BERT, attention is all you need, and so on.
 So if you want a detailed explanation of what that is, just go look up the corresponding
 videos.
 But briefly, what you'll have in NLP is a set of tokens, a sequence of tokens as an input,
 and you want to transform them layer after layer into sort of a higher order representation
 of that same sequence.
 And for that, you build these layers out of nodes and you have as many nodes usually as
 you have tokens in the sequence.
 And the next set of, so each token is represented by a vector at the beginning, and each layer
 transforms the sequence, as I said, into sort of a higher level representation.
 So you want the vector of this token right here to be a better representation than the
 vector was right here.
 And you do that by incorporating information from all the other tokens into that particular
 vector.
 Now, as I said, this is called an attention mechanism, and we don't actually have to go
 into how it works right here, but you can see pretty clearly that if you want to do
 this for every token, you need to have information routed from every token to every token, like
 from here to here, from here to here, and so on.
 And this is just one token, and then you need to do it for this token and for this token
 and for this token.
 So what you'll ultimately get, if n is your sequence length, you'll get some n squared
 amount of computation and memory requirements for this.
 So this is a problem.
 And usually, this means that, you know, this sequence length in BERT, this is limited to
 something like 512 tokens, which is okay for some applications.
 But if you want to summarize, you know, entire articles, entire books, even, or do question
 answering with lots of context, it's not really enough.
 So people have been thinking about how to scale this input, how to scale this.
 And of course, the main culprit is this quadratic attention mechanism, because if you, you know,
 scale the 512, you need, you know, four times the amount of compute and memory.
 So how does this paper go about reducing that quadratic dependency?
 The goal right here is, of course, to get this to some O of n, right?
 Because then, as we double the input length, we simply need to double the compute requirements,
 and that would be fantastic.
 And that's what this paper does.
 And it does so without sacrificing the properties of the transformer.
 So here's the architecture that Big Bird proposes.
 By the way, Big Bird, another character from Sesame Street, I guess, will continue the
 naming here after Elmo and BERT.
 You know, I'm waiting for the model that's the count.
 Yeah, that's going to be a fun model.
 So Big Bird basically has three different types of attention.
 And here, these are adjacency matrices in this attention mechanism.
 So here is the input layer, and the output layer is right here.
 So that basically means that node i right here would be connected.
 Sorry, that's not a straight line, would be connected to this particular node and also
 to this particular node.
 So we're now trying, if we have node i right here, we're now trying to not connect it to
 all of these nodes, but we'll say, we'll just select some at random and then connect it
 to that.
 Okay, this is what we call random attention.
 And you can pretty clearly see if you connect each of the i nodes to r equals 2, to two
 random nodes, then you don't have an n squared anymore.
 But you'll have a like an O of r times n, which you know, if r is a constant is an O
 of n attention mechanism.
 Okay, so the main goal between the random attention mechanism is that for each query,
 basically, you select random tokens that you attend to, and that random number is a fixed
 number that's not dependent on the sequence length.
 And the paper is a little bit unclear about whether or not those random ones are the same
 for every sequence or are switched up, or the same for every layer or are switched up.
 But they formulate all of this as sort of in sort of a graph in sort of a random graph.
 So they're, they formulate the attention mechanism in form of a graph.
 So if we transform all of these nodes into a graph, a full attention mechanism would
 mean that each graph, each node is connected to each of the other nodes, right, fully connected
 graph, I don't, maybe that's it.
 So that would be a full attention mechanism.
 And then they say, well, if we just have random connections between these things, then there
 are some theorems from graph theory that say that each random walk in this graph is going
 to, so this graph is going to mix pretty quickly.
 So I can get from each node to each other node by a random walk in a logarithmic time.
 And this random walk, which basically means that you go from here to here, this would
 be one layer of the transformer.
 And then if you want to go from here to here, that you would have to do that in the next
 layer.
 So this formulation as a random graph leads me to believe that layer after layer, the
 random attention pattern is going to be the same.
 But also the formulation of the paper leads me to believe that the this random attention
 differs from sequence to sequence.
 So I believe what's happening is that they get a new sequence, then they decide on this
 pattern right here once and then they use this layer after layer, the same pattern again.
 So you can see that in the traditional attention, information can basically flow from each of
 the nodes to each other node in one single step, right?
 Because each node is connected to each other node.
 You see this in the graph right here.
 However, if we only select a subset, then you know, it needs to if I want to go from,
 as I said, from here to here, then I need to do it in two steps.
 And therefore I need two layers.
 And that's going to be the culprit of this method here.
 And while it is mentioned in the paper, it's sort of I feel at least that's my my assessment
 of this paper, it's kind of swept under the rug a little bit.
 I mean, they do have a theorem that clearly says we can construct an example of a task
 that in the full attention setting can be solved with a single step.
 So a single layer that in our random attention setting needs a lot of layers, a lot of steps.
 But you know, the rest of the paper is sort of shaky on on this thing.
 But nevertheless, you can see how the random attention can, if you have enough layers,
 do the same information routing as the full attention.
 Okay.
 However, this is not a property of the random attention.
 And we'll see this in the next thing right here.
 So the next ingredient that this paper uses is window attention.
 And you can see over here that Big Bird is ultimately going to be a combination of the
 three types of attention, which will, which we are looking at here.
 So window attention basically means that each each i each token at the i of position is
 going to attend to itself, of course.
 So here is i, but it is also going to attend to its neighbors.
 So here is i minus one and here is i plus one.
 And this is a you know, this is a window size w that you can that is a parameter, but also
 it is a constant and therefore you again go from n squared to w times n, which you know
 is o of n if w is a constant.
 And this might be familiar to you, because we've already seen this in the long former
 paper.
 We made a video or I think even two videos on the long former, which used exactly the
 window attention in combination with the global attention.
 And if you want to know more about that, go watch these videos.
 But the new thing in Big Bird right here is this addition of the random attention.
 Again, the the window here is is has exactly the same properties as the random attention.
 So you have instead of a fully connected graph, you have a sparsely connected graph.
 Now if you have random attention, the sparsely connected graph is like like the one on the
 right.
 But if you have a windowed attention, you can it is kind of not randomly connected,
 but each node is connected to its neighbors like this.
 And you can also see that if I want to go from this node to this node right here, I
 can't do it in one step, but I can do it in two steps.
 I go here and I go here.
 So in the terms of the attention layers, if I want to go from node one to node three,
 I have to do it in two steps because each node is only connected to its neighbors.
 So the connection patterns would sort of look like this.
 So I have to go from one to two and then in the next layer from two to three.
 So the paper basically makes up for the lack of full attention by adding layers.
 And you also might recognize this from a convolution operation.
 This basically because it is a convolution operation, right in a convolution, each node
 only aggregates input from its neighbors for the next layer.
 And then we know that as we go up the layers, the de facto window that each node looks at
 is going to be like a cone kind of like this.
 So this is very similar to how a convolutional neural network works.
 And the reasoning is very similar because the reasoning is, well, in a sentence, the
 most important words for any given word are probably going to be its neighbors, like the
 words around it.
 And as you go up the layers, you branch out more and more.
 But ultimately, this neighborhood principle holds in NLP as well.
 So again, we already saw this in the long former, but that's the reason behind the window
 attention and that's the second ingredient.
 And then the third ingredient is this global attention.
 Now the global attention is selected tokens that are so important and that's fixed by
 the developers that are so important that they are connected to everything else.
 So for example, in these transformers, you often have what's this kind of CLS token.
 So this is a special token that you prepend to some piece of text and the output of this
 token is going to be your classification output because you don't want to bind your classification
 if you need to classify the entire sequence.
 You don't want to bind that decision to one particular word.
 What you want to do is you want to have an extra token and that's this CLS token that
 kind of aggregates information from all of this.
 So layer after layer, layer after layer, you'll have, so if we go here, layer after layer,
 we have this one special node.
 And in each step, every single other node is able to send information right here to
 this node and receive information from this node.
 So now, as a result of this, as you may be able to see, every single path is kind of
 a maximum length of two because if I want to go from any node to any other node, I can
 simply send information to this global node and then the global node in the next step
 can send information to whatever other node.
 And that is a property that they use in their proof that this attention mechanism is as
 sort of as powerful as the classic full attention mechanism.
 And we'll go through that in one second.
 But first, I hope this was clear that this combination of random attention, window attention
 and global attention is what is called Big Bird.
 They have some engineering tricks that go along with this, but in concept, you can imagine
 Big Bird being long former plus these random attention right here.
 And as an engineer, as an NLP engineer, that makes kind of total sense.
 I totally believe that the introduction, the addition of these random attention of these
 random attention patterns can absolutely help your classification or whatever your NLP tasks
 because more attention, better.
 And I also am completely willing to believe that using the full attention matrix, while
 it is, of course, more accurate, it won't hurt too much to leave some of that attention
 away because essentially all the path lengths are just becoming two or even with the random
 attention are really short or logarithmic to route information from a node to some other
 node.
 So the loss that you incur is kind of in a logarithmic scale in terms of performance,
 while the gain that you make is sort of in a in a quadratic or like a linear scale, you
 go from quadratic to linear.
 And that seems to me like a good empirical trade off.
 All right, however, the the proofs here, the proof of of how how these how these things
 are constructed are a little bit.
 I don't know.
 So what they do in the proof that this function can sort of is a universal approximator.
 People have already shown that full attention mechanisms are universal approximators.
 So they show here that this sparse attention mechanism is also a universal approximator.
 They make big use of star graphs.
 What they say is, OK, if we have a star graph, which is one node connected right here to
 every other node, this is a star graph.
 If we have a star graph, we can achieve the same thing than with a full graph.
 A full graph is where every node is connected to every other node.
 But as I already said, what they need for this is multiple layers of this star graph.
 So and that has to do with the fact that if I want to route information, I basically have
 to go via this middle node right here.
 And there is an additional complication because this middle node in our case right here is
 only one node.
 I can't route information at the same like I can't have this routing right here at the
 same time that I have this routing right here, like going from here to here, because I only
 have one middle node.
 And I kind of this is not how that like this is very dumb math.
 But maybe you have to imagine that there is one memory slot.
 And you can only use that one memory slot at the same time for one of these things.
 So essentially, what you'll have to do is you'll have to do the green thing first.
 And then in the next step, you'll have to do the blue thing second.
 And then so these are now pairwise routing between nodes.
 But ultimately, what an attention mechanism does is it does everything to everything right
 in a single layer, it routes information from all the nodes to all the other nodes.
 And to achieve that, so you need multiple rounds of this.
 And it turns out that in the worst case, you actually need n rounds of this.
 So you know, you trade off your you go from n squared to n memory and compute requirements
 in a single layer.
 But in the worst case, you need n layers to recover the power of the full of the full
 transformer.
 And that is the last one of their theoretical results right here.
 So first, they prove universal approximations.
 And second, they prove Turing completeness.
 These two properties have been proven for full attention mechanisms.
 And third, they prove that there are tasks where you actually do need n layers to solve
 them with their limited attention.
 So you know, I'm not sure but I feel you can make any sort of polynomial algorithm into
 a linear algorithm like this.
 Like I have a I have like a cool sorting algorithm, right?
 So if this is my sequence that I want to sort, what I can do is I can simply, you know, take
 a random subset of them, like this, this and this and then kind of go and sort them and
 then put them like I send them to the to the global memory like this, I sort them, and
 then I put them back, right?
 And if I do this for enough, if I do this for enough rounds, okay, you know, if I do
 this for enough rounds, you know, at the worst case, I need n rounds to sort my or log n
 rounds if I do it smartly.
 But you know, in, you know, the single step here is the single step is just O of n.
 So I have now an O of n sorting algorithm.
 I you know, I have my sort of a bit of worry to express things like that.
 And yeah, but you know, it is from an empirical standpoint, I absolutely believe that this
 this is enough.
 Now my second coral right here is that if you look at the proof, first of all, what
 it makes use is this star graph, and the star graph corresponds to the global attention.
 So that's not much to do with the random attention, though they use the random attention in their
 proof, but I at least believe that it would be possible with the global attention only.
 And then the second thing is if you look at the parameters that they use for the for the
 experiments, and I've already said this in the long former video.
 So in the long form of video, it turned out that if you look at how big these window attention
 is, it turns out that it you're still well, you know, the original BERT attended to 512
 tokens.
 And then you look at the window and the window was still 512 tokens.
 It's just that the global attention was even more so ultimately they ended up using more
 memory than the original BERT.
 And here, if I look at the parameters of their thing, and they have multiple experiments
 right here, and I believe this is the the base version.
 So this is the base version, they also have this large version.
 But here, this is the 12 layer version.
 And you can see they have this block length.
 And we'll get into the block length in one second.
 But then you can see that their window size is three times the block length, the number
 of random tokens is three times the block length, and the number of global tokens is
 two times the block length.
 So that results in eight times B. So eight times 64 is, you know,
 Can I calculate this?
 Or am I stupid?
 It's 512.
 Yes, actually calculated this before.
 So this is 512 tokens.
 So you know, you you go from from BERT that has 512 tokens and attends to 512 tokens to
 also attending to 512 tokens.
 Of course, the advantage here is that they now have 4096 sequence length.
 So they have the freedom to not attend to as many tokens as they have in the input length.
 But you know, to put it in perspective, this here uses more memory and more compute on
 on its face than BERT, because BERT attends to as many tokens but has a smaller input
 sequence.
 And you know, I, there's sort of a thing where in order to make these sparse attention things
 work, you have to go pretty, pretty, you know, high in the number of things you attend to,
 you can leave away some but it's not like you can scale up orders of magnitude of your
 input sequence length.
 So that's the this promise of linear attention is sort of it's kind of fulfilled but not
 there yet.
 The second thing I would like to point out is that in a lot of cases, the number of random
 tokens is actually set to zero.
 So really making use, I believe, of these of the of the global of the number of global
 tokens.
 So it that seems a bit strange in that they continuously refer to their random attention
 mechanism.
 But then in a lot of experiments, they don't actually have a random attention mechanism.
 I believe they have to do that because that's kind of what makes them different from the
 long former in principle, but still, yeah.
 So the last novelty, let's say is an engineering novelty in that they now always consider not
 single, for example, they don't consider single random attention, they always consider these
 in blocks.
 And that's because our current hardware is really bad at sparse stuff.
 Really bad at single indexing, gathering single things.
 So if you can do everything in blocks, you basically get you get these blocks almost
 for free.
 So it takes only marginally longer to retrieve this full two by two block right here than
 it would to retrieve the single instance right here.
 Of course, that means you have, you know, four times you still use four times more memory,
 but it is not four times slower than the original thing.
 So you can use these blocks right here.
 You can do it for the random attention, you can do it for the window attention, as you
 can see here.
 So you break this window pattern a little bit into blocks.
 And that makes it a lot faster.
 So that speeds up, get the speed up almost for free.
 And then they make another approximation in that the way they do this windowing is, and
 I just go really briefly.
 So you can see right here that it would be very cumbersome to gather.
 So what we need, we're just going to focus this this dotted thing right here is a bit
 confusing.
 So you want to attend to these things.
 And these you can just get out with a matrix slice really easy.
 But then you want to attend to this kind of blocky thing right here from the window attention,
 right, like this thing.
 And this is hard to get out because you'd have to kind of index each row individually.
 And that's very slow.
 So what they do, there is this matrix roll operation, where you can sort of roll the
 axis around.
 So what you'll do is you'll take this thing right here, and you put it to the left right
 here, and you'll take, for example, this thing right here, and you'll put it to the right
 or no, like it's, it's up and down.
 But in essence, that's what you do.
 And you can you can fold all of this blue stuff into a rectangular matrix.
 If you know if you can see right here.
 So you kind of roll this back, roll this back, roll this forward, and you replace whatever
 is missing by these.
 Now this again gives you some inaccuracies because this block right here was never intended
 to be attended to.
 And all of a sudden you see you have the K6 in here.
 So it gives you a bit of inaccuracies at the edges of the sequence.
 But you can take that, you know, you can take that hit for the increased performance that
 you gain by now having a rectangular matrix.
 TPUs are really efficient at this, not as efficient at this.
 And then the only thing that's really slow is gathering these random blocks right here.
 But also by having the same amount of random blocks per input token, what you'll do is
 you'll end up with just one of these columns right here, or you know, R of these columns.
 And that again gives you a rectangular matrix.
 So this thing right here you can process very, very efficiently using a TPU.
 And you know, the mistakes you make are basically this thing right here and this thing right
 here, because those weren't intended and are at the edges of the sequence.
 So these were the tricks of Big Bird to quickly summarize.
 Big Bird is basically taking a transformer saying, well, why do we need all of this attention,
 all of this full attention, maybe we only need some of that and can already do a big
 job, a good job, especially, you know, considering the attention mechanism goes over multiple
 layers.
 So we don't need a routing from each token to each token, we can make up for not having
 a fully connected graph by simply running multiple layers.
 So their sparsity is first of all, you have this random attention, which I believe changes
 from sequence to sequence, but stays within or among the layers of the same sequence.
 Then you have the window attention with the reasoning.
 So the reasoning behind the random attention is that if you have a randomly connected graph,
 the path lengths are on average logarithmic.
 So you can route information efficiently.
 The reasoning behind the window attention is that probably neighbor information is very
 important and that has been shown empirically.
 And then the global attention, the reasoning behind this is that some of the tokens that
 are fixed by the developers are so important that it's very beneficial that each other
 node is connected to them and that they are connected to each other node.
 The result of that is the Big Bird attention mechanism, which is basically long former,
 which already had these two plus the random attention.
 This achieves a linear complexity in terms of memory and compute, though linear has to
 be qualified a bit because it's modified by the window size, by the number of random attention
 tokens, by the number of global tokens, and in practice often ends up being fairly large
 ish.
 And also the theoretical guarantees now come with the fact that you need multiple layers.
 In the worst case, you need sequence length amount of layers, which in the worst case
 would result right back into a quadratic requirement for memory and compute.
 They do some engineering, some engineering tricks right here, and their results are pretty
 good.
 So the results in various tasks and we'll, we'll look at some of the tasks right here.
 So these are def set results using base size models.
 For example, where you can see they do outperform basic Roberta models, they outperform long
 former, which may mean that the random attention is useful, but you know, in these things,
 it's also always may just mean that you've thrown more compute at it.
 At least I'm not really looking that they outperform the models because as you can see
 right here, if they compare to state of the art and you know, granted, these are models
 that have been trained specifically for these tasks and are crafted and engineered and Big
 Bird manages to Big Bird manages to hold itself against them in a lot of tasks and even get
 state of the art on some.
 What I'm more interested in is that it, you know, it can reach good numbers.
 It doesn't necessarily have to be state of the art, but it can reach good numbers, which
 tells me that, okay, probably the, the empirical hit that I take by not having the full attention
 is, you know, is justifiable by the speed up and memory savings I do get.
 Yeah, especially when result, when you see results mixed like this, you know, sometimes
 the other model is good and sometimes the Big Bird is good on different variations and
 so on.
 I would not, you know, I would not make a big deal out of the fact that it is state
 of the art.
 I get that the authors have to do that.
 I would do so as well, but you know, you don't, don't think that this is the, like the best
 thing now.
 It's very probable.
 They just thrown also a lot of compute at it.
 What is cool is they do some genomics experiments.
 So not only do they have NLP state of the art, but also they go into genomics and experiment
 with data there.
 I don't want to go into that because ultimately it's another task and I believe the paper
 is about the architecture.
 All right.
 So that was Big Bird.
 I hope you enjoyed this video and learned.
 I learned something.
 Certainly.
 If you want to check out the proofs, they're actually pretty entertaining to read and yeah,
 I'll see you next time.
 Bye bye.