Reformer: The Efficient Transformer
deep learning machine learning nlp natural language processing machine translation arxiv google attention mechanism attention transformer seq2seq bert memory lsh locality sensitive hashing reversible revertible flow long sequence
The Transformer for the masses! Reformer solves the biggest problem with the famous Transformer model: Its huge resource requirements. By cleverly combining Locality Sensitive Hashing and ideas from Reversible Networks, the classically huge footprint of the Transformer is drastically reduced. Not only does that mean the model uses less memory, but it can process much longer input sequences, up to 16K tokens with just 16gb of memory!

https://arxiv.org/abs/2001.04451
https://ai.googleblog.com/2020/01/reformer-efficient-transformer.html

Abstract:
Large Transformer models routinely achieve state-of-the-art results on a number of tasks but training these models can be prohibitively costly, especially on long sequences. We introduce two techniques to improve the efficiency of Transformers. For one, we replace dot-product attention by one that uses locality-sensitive hashing, changing its complexity from O(L2) to O(LlogL), where L is the length of the sequence. Furthermore, we use reversible residual layers instead of the standard residuals, which allows storing activations only once in the training process instead of N times, where N is the number of layers. The resulting model, the Reformer, performs on par with Transformer models while being much more memory-efficient and much faster on long sequences.

Authors: Nikita Kitaev, Łukasz Kaiser, Anselm Levskaya

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
 Hi there! Today we'll look at Reformer, the efficient transformer by Nikita Kitaev, Lukas Kaiser and Anselm Levskaia. This is a paper that tries to reduce the extreme resource requirements of the transformer model. Now if you haven't seen the transformer model before, that's this thing, I suggest you go watch for example my video on it, Attention is All You Need, it's called, where the transformer is introduced. The most famous transformer is called BERT, B-E-R-T, and you can also look that up, I've made a video about this. So what's the issue here? If you remember transformers, they need a lot of memory. And why? That's because they compute, in each layer they compute these attention things. Let's recap shortly. In a transformer you propagate information layer by layer. So you have layer here with some signal, and then the next layer that you try to propagate the signal. Now what you do, you assign, you assign key queries to each of the next layer. So each of the next layer has queries, and queries are just vectors. This is a vector, this is a vector, this is a vector, and so on. So basically the next layer has the ability to ask, to ask the last layer what it wants. This is a kind of an intrinsic property of attention, and I, as I said, I explained this in detail in the video, Attention is All You Need. Basically these are what's called queries, Q. And then this layer is exposing what are called keys, and keys again are vectors. So vector, vector, vector, vector, and so on. So keys are vectors, and the way that the information is propagated to the next layer is whenever, whatever, we consider for example this node here, right, this node, let's make that yellow. When we consider this node here, it is going to look in the last layer which, which keys match my key the most. And in this case it will probably be this key and this key, right, they match the key the most. And here we look at the inner product, so the angle between the vectors. And then information is aggregated by simply having a weighted average of the values. So information is coming in here and here. Actually information is coming into all the nodes, but since only these keys match, the information will be propagated like this, to this unit. We could do this for another unit, for example this unit right here. What's the value of this unit? Well we have to look at the key here. Which key is it going to be matched to? It's probably going to be matched to this key right here. And probably no other key really. Maybe this key a little bit. So the information of that node in the next layer will be whatever's information is coming in here, routed there, and a little bit of this information. So this is kind of a, it's not a hard, it's called soft attention. So there's a little bit of information going everywhere, but the majority of the information is coming from the nodes where the keys match. So these are queries, these are keys, and technically these things coming in here are called values. But imagine the values simply as the information to be propagated, and the queries and the keys are responsible for routing that information to the next layer. All of these things are learned. So the queries, the keys, and the values. Now what's the problem? The problem is between the queries and the keys. As you can see, what you have to do is you have to match every single query with every single key in order to find out where information goes. So this becomes order of, if you have D keys and D queries, order of D squared operations that you have to do. And of course D squared values that you have to compute. And since these are all vectors, of course there is D will not only be the number of keys, but then again this is multiplied, so there is an inner multiplication with the dimensionality, let's call that capital D, of the... no sorry that's not an inner multiplication. Let's just remain at this. So D squared inner products between vectors of capital D dimensions. So it's not an easy thing for resources to do. You need a lot of resources to hold this, all of this in memory at the same time and to compute all of these things. The reformer aims to solve this problem. So this giant space problem that the transformers have, space, memory, also computational problem to a lesser degree. Mostly it's a memory issue. Alright, so what is happening here? And you see here that this product between two matrices clearly gives you this kind of squared thing. So what's happening in the reformer to do this? The trick is, if we go back to this drawing, the trick is to create what's called a hashing scheme or buckets. In creating buckets what you want to do is you want to group similar things together. So let's say we create four buckets. Bucket one, bucket two, bucket three, bucket four. And each bucket we label. And bucket one we label with the up direction, this with the right direction, with the down direction, the left direction as vectors. And now we simply put each of the things into the bucket where it belongs most. So let's for example this vector here, it goes here. Sorry, that is like absolutely not the right place. It goes probably here, right? This vector here, probably this one goes here, right? And so on. So you'll end up each of these assigning a bucket. So these all go into that bucket. Let's continue, actually let's also put the keys in the same buckets. So also the keys, this key here probably goes to this bucket. This key here probably goes to this bucket. Let's say this key here probably goes to the bucket over here. You already see, so before, right before, we cared about this particular query and this particular key. We just looked and we said those two will probably route information to each other because they're similar. And now you can see they both ended up in the same bucket. So the idea is to create a scheme where you throw these things into buckets such that if two vectors are similar they will end up in the same bucket with high probability. So you'll only have to really compare things within the same bucket and not across all of these d squared elements. That's the idea and the technique here is called locality sensitive hashing. So locality sensitive hashing. And short this is called LSH. The idea is the following, if you have two vectors v1 and v2 and they have and you have a distance measure distance measure d. D is a distance. What you want is if the distance between v1 and v2 is small, I'm getting confused with color, with small then you want them in the same bucket. And if the distance is large then you want them in a different bucket. Different buckets. You know with high probability. So all of these things where you say you want them in the same bucket with probability p with probability p with high probability p and here you want them in different buckets with high probability. Or you want them in the same pocket with low probability. That's an equivalent form of stating. This is all formalized and I can direct you to the Wikipedia page of that. It's pretty good. It gives a concise definition. Here you can see that and it gives a number of examples. So one example I'd like to give here for locality sensitive hashing is of course the scheme of bucketing will all depend on what your distance measure is. If you consider the distance measure simply to be the jacquard distance. So let's say we have two vectors 0 1 0 1 and here we have 1 0 1 1 0 1 and here it's 0 0 0 1. Alright so maybe you can see the first two vectors here are much more close together than the last vector. Now in terms of bit differences, one scheme to do locality sensitive hashing is to simply sub sample bits. So in this case this is a slightly constructed example. We will just sub sample the first two bits and then construct the buckets according to these bit values. So if since we sample two bits we have four buckets. Here is 0 0, here is 0 1, here is 1 0 and here is 1 1. That's the concept of locality sensitive hashing. You have these buckets and then you can say alright this vector has 1 0, goes into this, this goes into this and then that goes into the 0 1 bucket. And you end up with what you have. You have the two close vectors in the same bucket and the two far apart vectors in that bucket. Of course that doesn't always work. You can be unlucky in sub sampling but that's kind of trade-off you'll have to go for. If things that are close together happen with it's a low probability but if they happen to end up in the different buckets then basically you lose the fact that they are close to each other and that's the trade-off. The kind of locality sensitive hashing they use in the reformer now is what are called random projections. So let's say you have a bunch of vectors and that's really what we care about. You have a bunch of vectors and what you want, you want the keys and queries. So you have a bunch of vectors like this and you want to create buckets such that vectors that are close together will end up in the same bucket and vectors that are far apart will end up in the in different buckets. A cool way to do is, and this is in the cosine distance so we care about the angle between vectors, a cool way to do this is to use random plane projections and the cool thing about it is it works for the cosine distance and you can basically choose how many buckets you create. Let's say we want to create four buckets here again. What we need is two hyper planes and what we'll do is, so here is the origin, we'll simply create two hyper planes through the origin at random. So I'm gonna draw a random hyper plane here like this and then a second random hyper plane like this. So you would agree those are pretty random hyper planes as much as I can be a random generator and then we'll simply label, so this will label hyper plane one, this will label hyper plane two. Now we simply assign each vector bits according to the, on which side of the hyper plane they lie. So let's call this here the plus side and this here the minus side or even yeah let's call this the plus and the minus and here also we call this the plus side and this the minus side. So this vector here is, its signs are plus plus right because it's on the plus side of both of hyper planes. This vector plus plus, this one plus plus, this one here is called, it's on the negative side of plane two but on the positive side of plane one so it's plus minus, this one here minus minus, minus minus, minus minus and these are your buckets. So you would group these vectors together because they have they have the same signs. You would group that vector, you would group these vectors together. The combination of this with attention, since in attention you've seen attention uses a softmax and the softmax is dominated usually by the largest elements and since we compute inner products it means that this softmax thing is dominated by vectors that have small inner products. So basically you don't have to look at all of these d squared vectors if you can find the ones that have the closest distance. You can pretty much ignore the others. And LSH allows you to do this. So build buckets of vectors with similar directions. Then you only have to care about these vectors comparing them to each other. So that's not a lot of vectors generally and that's how you save a lot of work. So you will only have to care about these three vectors if your key vector for example is right here. You'll only have to care about these things in the same bucket and you can ignore all of that rest of the space. Of course the more hyperplanes you have the more buckets you'll have, the less vectors you'll have in the same bucket. That's the general idea. I find this explanation to be a bit easy. You can equivalently explain it by doing these kind of random rotations in the space. You can think about how that will end up actually being the exact same thing as what I just explained. I just like that my explanation better I think. Alright so the way they use this, they have an illustration right here, is the following. So they have these keys right? Sequence of queries and keys. So they do equivalent queries and keys which is a thing you can do in transformers. Don't worry too much about it whether they're different or not. But then they do this LSH bucketing and here the color of the cell is just the bucket, the LSH bucket which will end up. Then they sort that right as you can see and now they do an additional thing which is called the chunk. As you can see there are not the same amount of vectors in each bucket and that is sometimes a problem because even though you've reduced the memory, the memory requirements are still dominated by the largest bucket. By whatever bucket has the most number of vectors that will pretty much be your memory requirement. Because now you don't have to, if this is D, you have to compute all the D squared things anymore. But you'll only have to compute this quantity, let's call that B. So the maximum bucket size. But that could still be large right? If you look at a distribution it's probably going to be something like this right? Where most buckets have a kind of a standard number of vectors but some buckets will have a lot of vectors and that's, sorry, some few buckets will have a lot of vectors and your memory requirement is still dominated by this. So they do an additional thing which is called chunking which means they actually take fixed size chunks here, fixed size. Here they always take four and they say all right these are our chunks and we will only compute attention within the chunks right? So it could be that there's the same bucket is actually split between chunks and that's why they do an additional thing is that you can attend two things in a different chunk right here. You can attend two things in your neighboring chunks so you're restricted to either your own chunk or your neighboring chunk. Note that there aren't any any arrows going over here. So you can attend, they have this diagram here, which things you can attend to. You can attend to yourself or attend to your neighboring thing but not to any other thing or the other way around right? So that's basically the the concept of saving memory. Now your memory requirements are, if we call this quantity now, we call the other one B, let's call this the chunk size C right? Your memory requirements are pretty much C squared plus whatever this unidirectional, so not this isn't squared, plus probably O of C something like this. So you bring your memory requirements down quite a bit. Now that's the general idea here. The problem they face again is, so they face another problem where they say hold on, I can't find it right here, they say hold on, we do have actually another problem and that is that these transformers have to back propagate. So you'll have to forward propagate these things and now we've kind of solved this D square computation issue but what you'll have to do is if you go from layer to layer right? Layer, layer, layer, layer. What you have to do is if you propagate information forward you still have to back propagate and in order to back propagate usually, usually you'll have to remember all of these activations right? So these activations, these activations. In order to do back prop it is often the case that you actually have to remember the activations because in each forward propagation, in each layer here you might lose some information. Imagine you have a layer that maps these two-dimensional vectors both to, so here actually let's make this blue, maps these three vectors to the following configuration. So a layer maps these vectors to this, this and this. So it maps two things to one thing which you know can be if you in a linear layer can decide to map it to a lower dimensional subspace. So you could actually decide to map it to in fact two points right? This is also a possibility. You could do dimension reduction. So because all of this in order to do back prop you actually have to remember these things in order to do proper back prop. This is a problem again for the transformer because all these activations even though we've gotten rid of the d-square computation they will have to be remembered and that takes a lot of memory. The way to solve this is actually to do invertible layers. What that means is that if I propagate information forward, forward, forward, forward, I can figure out what the information here was simply by looking at the back prop activations. And this happens if the layer is invertible. So if this function here is invertible. So if f here technically is invertible. So I can actually write down the inverse of f and that is defined. This of course is a pretty big restriction and the way they achieve it, I like to go to the blog here, the way they achieve it is they do what's called an idea from reversible networks where they always have two sets of activations. That's what you see here. X1 and X2. And in each layer only one of them is updated in a residual fashion. You can see here layer 1 updates X2 but X1 remains the same and goes to Y1. And then in the next layer, layer 2 only updates Y1 in order to construct Z1. But Y2 remains the same to be Z2. And then you can revert the layers. You can basically figure out what the activations were from the back prop signal. Now that's extremely good if you want to save memory but of course it restricts clearly. You have to be restricted to this kind of architecture similar. This idea actually isn't new. This has been used many times in things like normalizing flows and I want to highlight this paper. Actually want to highlight specific... I chose this paper because they have these nice diagrams where they show exactly this. You see they have two sets X1 and X2 that in forward propagation they only update one of them. And then in backward in what's called inverse propagation they can figure out what those were. And they couple these in exactly the same way. Like here this drawing might be even more similar where they alternate between updating the two activations. So you can think of this as a way to simply make the function that you're representing with the neural network invertible. That is a giant constraint on your architecture but these methods here, these normalizing flow methods, use that so they can actually define an invertible layer because they need the Jacobian inverse in order to compute their normalizing flow. So you see that's why they originally did it. And I'm sure that that's not a new idea or particularly new again. Strangely I haven't found any of the flow literature cited. They do cite the reversible residual net paper that they probably got the idea from. So with these two things now you can save the giant computation. And you can also not store the forward activations. So they say they can take now giant giant giant input sizes. You may remember transformers like BERT. So BERT it can use something like 512 tokens. In its input sequence. That means the sequence that you can look at with BERT at a time is 512 long and not a bit longer. There have been some extensions to that. For example I believe in XL net. So XL net has pushed this to something like C times 512 where C is a smallish constant. That where you can kind of carry over information between sequences. But this thing here as you can see they calculate it could take up something like 64,000 tokens and that would use in total 16 gigabytes of memory. Which is available on a high-end GPU. So this is a giant this is a giant step forward in in producing transformers that can actually take large models. And here you see the memory and time complexity. You can look at these things yourself but you can see maybe here that these squares here from the original transformer they now vanish from this. And all of these constants are a lot of these constants are actually smaller. For example that chunk size is in there instead of kind of the entire sequence length. So that's basically the the paper. They show that I can actually input those long sequences. They can apply this to images. You see there's image net pixel by pixel which is a lot of pixels and would have been absolutely unthinkable with one of the original transformers. And with that I invite you to check out the paper and the blog post and I'll see you next time. Bye bye.
 Hi there! Today we'll look at Reformer, the efficient transformer by Nikita
 Kitaev, Lukas Kaiser and Anselm Levskaia. This is a paper that tries to reduce the
 extreme resource requirements of the transformer model. Now if you haven't
 seen the transformer model before, that's this thing, I suggest you go watch for
 example my video on it, Attention is All You Need, it's called, where the
 transformer is introduced. The most famous transformer is called BERT, B-E-R-T,
 and you can also look that up, I've made a video about this. So what's the issue
 here? If you remember transformers, they need a lot of memory. And why? That's
 because they compute, in each layer they compute these attention things. Let's
 recap shortly. In a transformer you propagate information layer by layer. So
 you have layer here with some signal, and then the next layer that you try to
 propagate the signal. Now what you do, you assign, you assign key queries to each of
 the next layer. So each of the next layer has queries, and queries are just
 vectors. This is a vector, this is a vector, this is a vector, and so on. So
 basically the next layer has the ability to ask, to ask the last layer what it
 wants. This is a kind of an intrinsic property of attention, and I, as I said, I
 explained this in detail in the video, Attention is All You Need. Basically
 these are what's called queries, Q. And then this layer is exposing what are
 called keys, and keys again are vectors. So vector, vector, vector, vector, and so on.
 So keys are vectors, and the way that the information is propagated to the next
 layer is whenever, whatever, we consider for example this node here, right, this
 node, let's make that yellow. When we consider this node here, it is going to
 look in the last layer which, which keys match my key the most. And in this case
 it will probably be this key and this key, right, they match the key the most.
 And here we look at the inner product, so the angle between the vectors. And then
 information is aggregated by simply having a weighted average of the values.
 So information is coming in here and here. Actually information is coming into
 all the nodes, but since only these keys match, the information will be propagated
 like this, to this unit. We could do this for another unit, for example this unit
 right here. What's the value of this unit? Well we have to look at the key here.
 Which key is it going to be matched to? It's probably going to be matched to
 this key right here. And probably no other key really. Maybe this key a little
 bit. So the information of that node in the next layer will be whatever's
 information is coming in here, routed there, and a little bit of this
 information. So this is kind of a, it's not a hard, it's called soft attention.
 So there's a little bit of information going everywhere, but the majority of the
 information is coming from the nodes where the keys match. So these are
 queries, these are keys, and technically these things coming in here are called
 values. But imagine the values simply as the information to be propagated, and the
 queries and the keys are responsible for routing that information to the next
 layer. All of these things are learned. So the queries, the keys, and the values.
 Now what's the problem? The problem is between the queries and the keys. As you
 can see, what you have to do is you have to match every single query with every
 single key in order to find out where information goes. So this becomes order
 of, if you have D keys and D queries, order of D squared operations that you
 have to do. And of course D squared values that you have to compute. And
 since these are all vectors, of course there is D will not only be the number
 of keys, but then again this is multiplied, so there is an inner
 multiplication with the dimensionality, let's call that capital D, of the... no
 sorry that's not an inner multiplication. Let's just remain at this. So D squared
 inner products between vectors of capital D dimensions. So it's not an
 easy thing for resources to do. You need a lot of resources to hold this, all of
 this in memory at the same time and to compute all of these things. The reformer
 aims to solve this problem. So this giant space problem that the
 transformers have, space, memory, also computational problem to a lesser degree.
 Mostly it's a memory issue. Alright, so what is happening here? And you see
 here that this product between two matrices clearly gives you this
 kind of squared thing. So what's happening in the reformer to do this?
 The trick is, if we go back to this drawing, the trick is to create
 what's called a hashing scheme or buckets. In creating buckets what you
 want to do is you want to group similar things together. So let's say we create
 four buckets. Bucket one, bucket two, bucket three, bucket four. And each
 bucket we label. And bucket one we label with the up direction, this with the right
 direction, with the down direction, the left direction as vectors. And now we
 simply put each of the things into the bucket where it belongs most. So let's
 for example this vector here, it goes here. Sorry, that is like absolutely not
 the right place. It goes probably here, right? This vector here, probably this one
 goes here, right? And so on. So you'll end up each of these assigning a bucket. So
 these all go into that bucket. Let's continue, actually let's also
 put the keys in the same buckets. So also the keys, this key here probably goes
 to this bucket. This key here probably goes to this bucket. Let's say this key
 here probably goes to the bucket over here. You already see, so before, right
 before, we cared about this particular query and this particular key. We just
 looked and we said those two will probably route information to each other
 because they're similar. And now you can see they both ended up in the same
 bucket. So the idea is to create a scheme where you throw these things into
 buckets such that if two vectors are similar they will end up in the same
 bucket with high probability. So you'll only have to really compare things within
 the same bucket and not across all of these d squared elements. That's the idea
 and the technique here is called locality sensitive hashing. So locality
 sensitive hashing. And short this is called LSH. The idea is the following, if
 you have two vectors v1 and v2 and they have and you have a distance measure
 distance measure d. D is a distance. What you want is if the distance between v1
 and v2 is small, I'm getting confused with color, with small then you want them in the
 same bucket. And if the distance is large then you want them in a different bucket.
 Different buckets. You know with high probability. So all of these things
 where you say you want them in the same bucket with probability p with
 probability p with high probability p and here you want them in different
 buckets with high probability. Or you want them in the same pocket with low
 probability. That's an equivalent form of stating. This is all formalized and I
 can direct you to the Wikipedia page of that. It's pretty good. It gives a concise
 definition. Here you can see that and it gives a number of examples. So one
 example I'd like to give here for locality sensitive hashing is of course
 the scheme of bucketing will all depend on what your distance measure is. If you
 consider the distance measure simply to be the jacquard distance. So let's say we
 have two vectors 0 1 0 1 and here we have 1 0 1 1 0 1 and here it's 0 0 0 1.
 Alright so maybe you can see the first two vectors here are much more close
 together than the last vector. Now in terms of bit differences, one scheme
 to do locality sensitive hashing is to simply sub sample bits. So in this case
 this is a slightly constructed example. We will just sub sample the first two
 bits and then construct the buckets according to these bit values. So if
 since we sample two bits we have four buckets. Here is 0 0, here is 0 1,
 here is 1 0 and here is 1 1. That's the concept of locality sensitive hashing.
 You have these buckets and then you can say alright this vector has 1 0,
 goes into this, this goes into this and then that goes into the 0 1 bucket.
 And you end up with what you have. You have the two close vectors in the same
 bucket and the two far apart vectors in that bucket. Of course that doesn't
 always work. You can be unlucky in sub sampling but that's kind of
 trade-off you'll have to go for. If things that are close together
 happen with it's a low probability but if they happen to end up in the different
 buckets then basically you lose the fact that they are close to each other and
 that's the trade-off. The kind of locality sensitive hashing they use in
 the reformer now is what are called random projections. So let's say you have
 a bunch of vectors and that's really what we care about. You have a bunch
 of vectors and what you want, you want the keys and queries. So you have a
 bunch of vectors like this and you want to create buckets such that vectors that
 are close together will end up in the same bucket and vectors that are far
 apart will end up in the in different buckets. A cool way to do is,
 and this is in the cosine distance so we care about the angle between vectors,
 a cool way to do this is to use random plane projections and the cool
 thing about it is it works for the cosine distance and you can basically
 choose how many buckets you create. Let's say we want to create four
 buckets here again. What we need is two hyper planes and what we'll do is, so
 here is the origin, we'll simply create two hyper planes through the origin at
 random. So I'm gonna draw a random hyper plane here like this and then a second
 random hyper plane like this. So you would agree those are pretty random
 hyper planes as much as I can be a random generator and then we'll simply
 label, so this will label hyper plane one, this will label hyper plane two.
 Now we simply assign each vector bits according to the, on which
 side of the hyper plane they lie. So let's call this here the plus side and
 this here the minus side or even yeah let's call this the plus and the minus
 and here also we call this the plus side and this the minus side. So this vector
 here is, its signs are plus plus right because it's on the plus side of both of
 hyper planes. This vector plus plus, this one plus plus, this one here is called,
 it's on the negative side of plane two but on the positive side of plane one so
 it's plus minus, this one here minus minus, minus minus, minus minus and these
 are your buckets. So you would group these vectors together because they have
 they have the same signs. You would group that vector, you would group these
 vectors together. The combination of this with attention, since in attention you've
 seen attention uses a softmax and the softmax is dominated usually by the
 largest elements and since we compute inner products it means that this softmax
 thing is dominated by vectors that have small inner products. So basically
 you don't have to look at all of these d squared vectors if you can find the
 ones that have the closest distance. You can pretty much ignore the others.
 And LSH allows you to do this. So build buckets of vectors with
 similar directions. Then you only have to care about these vectors comparing them
 to each other. So that's not a lot of vectors generally and that's how you
 save a lot of work. So you will only have to care about these three vectors if
 your key vector for example is right here. You'll only have to care about these
 things in the same bucket and you can ignore all of that rest of the space. Of
 course the more hyperplanes you have the more buckets you'll have, the less
 vectors you'll have in the same bucket. That's the general idea. I find this
 explanation to be a bit easy. You can equivalently explain it by doing these
 kind of random rotations in the space. You can think about how that will end up
 actually being the exact same thing as what I just explained. I just like that
 my explanation better I think. Alright so the way they use this, they have an
 illustration right here, is the following. So they have these keys right?
 Sequence of queries and keys. So they do equivalent queries and keys which is a
 thing you can do in transformers. Don't worry too much about it whether they're
 different or not. But then they do this LSH bucketing and here the color of the
 cell is just the bucket, the LSH bucket which will end up. Then they sort that
 right as you can see and now they do an additional thing which is called the
 chunk. As you can see there are not the same amount of vectors in each bucket
 and that is sometimes a problem because even though you've reduced the
 memory, the memory requirements are still dominated by the
 largest bucket. By whatever bucket has the most number of vectors that will
 pretty much be your memory requirement. Because now you don't have to, if
 this is D, you have to compute all the D squared things anymore. But you'll
 only have to compute this quantity, let's call that B. So the maximum
 bucket size. But that could still be large right? If you look at a
 distribution it's probably going to be something like this right? Where most
 buckets have a kind of a standard number of vectors but some buckets will have a
 lot of vectors and that's, sorry, some few buckets will have a lot of vectors and
 your memory requirement is still dominated by this. So they do an
 additional thing which is called chunking which means they actually take
 fixed size chunks here, fixed size. Here they always take four and they say all
 right these are our chunks and we will only compute attention within the chunks
 right? So it could be that there's the same bucket is actually split
 between chunks and that's why they do an additional thing is that you can attend
 two things in a different chunk right here. You can attend two things
 in your neighboring chunks so you're restricted to either your own chunk or
 your neighboring chunk. Note that there aren't any any arrows going over here.
 So you can attend, they have this diagram here, which things you can
 attend to. You can attend to yourself or attend to your neighboring thing but not
 to any other thing or the other way around right? So that's basically the
 the concept of saving memory. Now your memory requirements are, if we call this
 quantity now, we call the other one B, let's call this the chunk size C right?
 Your memory requirements are pretty much C squared plus whatever this
 unidirectional, so not this isn't squared, plus probably O of C something
 like this. So you bring your memory requirements down quite a bit. Now
 that's the general idea here. The problem they face again is, so they face
 another problem where they say hold on, I can't find it right here, they say hold on,
 we do have actually another problem and that is that these transformers
 have to back propagate. So you'll have to forward propagate these things and now
 we've kind of solved this D square computation issue but what you'll have to
 do is if you go from layer to layer right? Layer, layer, layer, layer. What you
 have to do is if you propagate information forward you still have to
 back propagate and in order to back propagate usually, usually you'll have to
 remember all of these activations right? So these activations, these activations.
 In order to do back prop it is often the case that you actually have to remember
 the activations because in each forward propagation, in each layer here you might
 lose some information. Imagine you have a layer that maps these
 two-dimensional vectors both to, so here actually let's make this blue, maps these
 three vectors to the following configuration. So a layer maps these
 vectors to this, this and this. So it maps two things to one thing which
 you know can be if you in a linear layer can decide to map it to a lower
 dimensional subspace. So you could actually decide to map it to in fact
 two points right? This is also a possibility. You could do dimension reduction.
 So because all of this in order to do back prop you actually have to remember
 these things in order to do proper back prop. This is a problem again for the
 transformer because all these activations even though we've gotten rid
 of the d-square computation they will have to be remembered and that takes a
 lot of memory. The way to solve this is actually to do invertible layers. What
 that means is that if I propagate information forward, forward, forward,
 forward, I can figure out what the information here was simply by looking
 at the back prop activations. And this happens if the layer is invertible.
 So if this function here is invertible. So if f here technically is invertible.
 So I can actually write down the inverse of f and that is defined. This of course
 is a pretty big restriction and the way they achieve it, I like to go to the blog
 here, the way they achieve it is they do what's called an idea from reversible
 networks where they always have two sets of activations. That's what you see here.
 X1 and X2. And in each layer only one of them is updated in a residual fashion.
 You can see here layer 1 updates X2 but X1 remains the same and goes to Y1.
 And then in the next layer, layer 2 only updates Y1 in order to
 construct Z1. But Y2 remains the same to be Z2. And then you can revert the layers.
 You can basically figure out what the activations were from the back prop
 signal. Now that's extremely good if you want to save memory but of course it
 restricts clearly. You have to be restricted to this kind of architecture
 similar. This idea actually isn't new. This has been used many times in things
 like normalizing flows and I want to highlight this paper. Actually want to
 highlight specific... I chose this paper because they have these nice diagrams
 where they show exactly this. You see they have two sets X1 and X2 that in
 forward propagation they only update one of them. And then in backward in what's
 called inverse propagation they can figure out what those were. And they
 couple these in exactly the same way. Like here this drawing might be even more
 similar where they alternate between updating the two activations. So you can
 think of this as a way to simply make the function that you're representing
 with the neural network invertible. That is a giant constraint on your
 architecture but these methods here, these normalizing flow methods, use that
 so they can actually define an invertible layer because they need the
 Jacobian inverse in order to compute their normalizing flow. So you see that's
 why they originally did it. And I'm sure that that's not a new idea or
 particularly new again. Strangely I haven't found any of the flow
 literature cited. They do cite the reversible residual net paper that they
 probably got the idea from. So with these two things now you can save the
 giant computation. And you can also not store the forward activations. So
 they say they can take now giant giant giant input sizes. You may remember
 transformers like BERT. So BERT it can use something like 512 tokens.
 In its input sequence. That means the sequence that you can look at with BERT
 at a time is 512 long and not a bit longer. There have been some
 extensions to that. For example I believe in XL net. So XL net has pushed this to
 something like C times 512 where C is a smallish constant. That where you
 can kind of carry over information between sequences. But this thing here
 as you can see they calculate it could take up something like 64,000 tokens and
 that would use in total 16 gigabytes of memory. Which is available on a high-end
 GPU. So this is a giant this is a giant step forward in in producing
 transformers that can actually take large models. And here you see the memory
 and time complexity. You can look at these things yourself but you can see
 maybe here that these squares here from the original transformer they now
 vanish from this. And all of these constants are a lot of these constants
 are actually smaller. For example that chunk size is in there instead of kind
 of the entire sequence length. So that's basically the the paper. They show that
 I can actually input those long sequences. They can apply this to images.
 You see there's image net pixel by pixel which is a lot of pixels and would have
 been absolutely unthinkable with one of the original transformers. And with that
 I invite you to check out the paper and the blog post and I'll see you next time.
 Bye bye.