Stanford CME295 Transformers & LLMs | Autumn 2025 | Lecture 3 - Tranformers & Large Language Models

Host 0:05 Cool. Hello, everyone, and, uh, welcome to Lecture 3 of CME295. Uh, so today is a very exciting day because we're going to finally introduce Large Language Models. Uh, but I guess before we go into that, I'm just going to start traditionally with, uh, some announcements. Um, so some of you wanted to have the slides before the class, so just a heads-up that in case you want to use the slides to do some annotations, uh, they're on the website right now, so feel free to get them. And, uh, with Shervine, we'll try to just on a regular basis every Thursday evening, have them published on the website so that you can download them and annotate. Cool. So with that, let's start. And as usual, we're going to recap, uh, last week's episode. So if

Host 1:02 you remember, you know, Lecture 1 and Lecture 2 were all about introducing the concept of self-attention and linking them to the construct of the transformer. And what we did last lecture was look at all the types of models that there are out there and how they were all based on the transformer. So there are three categories-- three main categories of models. So the first one that we saw was encoder-decoder model, which basically relies on the transformer. It has the encoder of the transformer, the decoder of the transformer, and typically, the tasks there are input text, so text in, text out. So we saw that one example was T5 and all the variations. The second type of model is where we remove the decoder from the trans-transformer, and we obtain an encoder-only model. So, uh, we went, uh, deeper into BERT, which is the typical encoder-only model. And, uh, I guess we also saw that what BERT has is this nice property that its encoded embeddings are very meaningful and expressive of the inputs. And so, yeah, we saw, like, the example of classification, sentiment extraction. So what we did was, in particular, um, take into consideration the encoded embedding of the CLS token. So, uh, I guess in real life, BERT is used to encode documents, to encode sentences, and we're go-going to see later in the class how these models are useful. And then last but not least, we have the third category of models, which is decoder-only. So we only keep the decoder part of the transformer, and so here we also do a little bit of a, of a modification, so we remove the cross-attention 'cause, uh, we don't need it anymore. We don't have an encoder. And these kinds of models are text in, text out. And so GPT is a very good example of such models, and actually, most models these days, they're only-- like, they are decoder-only. So these are the three main kinds of models that you can see out there. So far so good for everyone?

Host 3:43 Cool. So with that, I'm going to introduce the term LLM. So LLM sta-stands for Large Language Model. So what is a large language model? So first of all, a large language model is a language model. So a language model is a model that assigns probability to sequences of tokens. So in this case, our model always predicts the probability of the next token, so it's in that sense a language model. But also a large language model is large. So why is it large? So we're going to see that these models, they are actually scaled up in terms of size. So first of all, uh, in terms of model size, so these days, uh, it's not uncommon to see models on the order of hundreds of billions of parameters. But yeah, typically, when we say LLM, we say at least on the order of a billion. Um, these models, they've also been trained on a huge amount of data, and here by amount of data, we quantify that by the number of tokens that they were pre-trained with. And this is on the order of magnitude of hundreds of billions of tokens or even trillions of tokens. So I think the biggest o- biggest ones are, like, on the tens of trillions of tokens, so it's, like, huge training sets. And they're also large because they ne-need a lot of compute. So typically, uh, you need a bunch of GPUs to make them work, although these days there's been a lot of, um, optimizations to have them work on, uh, consumer-based GPUs. So we're going to see that, uh, later on. But an LLM is large according to these categories. So another thing that I want to point out is that all these terminologies, they're relatively new. So, um, I remember in twenty-eighteen, nineteen, there was nothing-- like, there was no real definition of an LLM. I think no one actually talked about LLMs. In the beginning, maybe people talked about LLMs. They included BERT But BERT is an encoder-only model that does not produce text. So with the current definition of an LLM, which right now has been pretty well-established, BERT would not be an LLM because it doesn't produce text. So here we only consider language models that do text-to-text that are very large in size in terms of, uh, amount of data they've been trained on and in terms of compute. Cool. And as we saw before, these models are decoder-only. So here what we do is we remove the encoder, we only keep the masked self-attention, the feed forward neural network, and then the, you know, addition and normalization. So we only keep this. And this is the backbone of LLMs. And, uh, so I mentioned, uh, you know, GPT is a kind of a good example, but it's not just that. You have plenty of other models. So you may have heard of, uh, Llama from Meta, Gemma from Google, uh, DeepSeek, Mistral, Qwen, so on. Like, the, the li- list is long. I would say roughly, I mean, more than ninety percent of, uh, like, modern-day LLMs, they're all decoder-only. So I think that's, uh, something to keep in mind. Cool. Um, okay. So now you know how LLMs are made of,

Host 7:37 but there is something else that people these days also introduce to these models and we're going to see that in a bit. So I mentioned that these models are huge in size. Again, typically hundreds of billions of parameters. So it takes a lot of compute to just compute one inference or also to train these models. But you may wonder, do you really need to have all these parameters be activated during a forward pass to make a simple prediction? So I'm going to, um, like, have a little metaphor. So let's suppose you enter in a room and in the room there is a mathematician, a physicist, a chemist, and a historian. So you come in this class, there is a bunch of people who are expert in what they do. And you have a question-- you have a math question. And so the question I have for you is, who would you ask your question? Would you ask the mathematician? Would you ask the chemist? Would you ask everyone? Well, right now we ask everyone. We ask all parameters of the model to be involved in the computation of, uh, you know, the generation. And so the idea here is given an input, maybe it's not necessary to ask everyone to be involved in the computation. So the idea is let's actually just have a subset of the model be involved in the computation of the next token. So I'm just introducing this idea of experts. So let's suppose we're introducing, uh, the following notation. So let's suppose we have N experts. So think of it as your mathematician, your chemist, historian, like, whatever. So these are your experts, and the idea is given an input X, you're going to ask yourself who should be involved in the generation of the output. So you're going to have, let's say, another network. We'll call-- we're going to call it G, like gate, but it's also sometimes called router. So let's suppose you have some gate that tells us which expert should be involved in the inference. So if we have that, so let's suppose here the gate tells us, "Okay, so actually expert number two is well-suited to answer your question." So here the idea is that the input is just going to flow into that expert, but not the other experts. So this has a name. It's called Mixture of Experts. So it's ca- so denoted MoE. Uh, everyone talks about MoE, so these are Mixture of Experts. And so the formula that you will see a lot is this one. So the output Y, which is denoted Y-hat, is the sum of the expert output weighted by some quantity, which is the output of the gate, which tells you how important the output of each expert is. Yeah. Great question. So the question is, how do you train G? How do you train E? So typically you train them jointly. So we're going to see that maybe in a, yeah, a little later, but you can think of it as, you know, just training as usual. You do your forward pass, you compute the loss, and you backprop. And it's actually an interesting question because there is some challenges that come with training MoEs that we're going to see in a second. Yep Uh, question is, uh, what are these Es? Uh, what is the architecture of these Es? So let's suppose right now that they're just some network. We're not specifying them for now, but we're going to see-- see this in a second. Let's suppose for now it's like some network. Cool? Okay. So I told you that, you know, what if we don't activate everyone? What if we activate a subset? But this formula actually, um, I guess, uh, assumes that we're actually considering all expert outputs.

Host 12:43 So I just want to distinguish two kinds of MoEs. So there's one kind that is called a dense MoE. So a dense MoE actually does not have any constraints on the number of experts that are involved. So these weights, they can be anywhere between zero and one. So, so think of them as a probability distribution, but it's just going to put more weight towards some experts compared to others. So back, back to the example that I had. So let's suppose I have a, a math question. So I'm going to ask the mathematician, the chemist, the historian. So I'm probably going to add a higher weight to what the mathematician says compared to, let's say, the historian. So this is the idea. But then the interesting thing is when we constrain the number of experts that are activated, because here, as we mentioned previously, what we're interested in is to not involve everyone, is to make some savings in the amount of compute that we do. So there's a second kind of MoE that's called the Sparse MoE, and what it does is it only selects the quote-unquote, "top K experts." So K can be equal to one, so one expert or even two. So it's a hyperparameter that you choose. And so here the expression of the output becomes the sum over all the chosen experts of, uh, G of X times, uh, E of X. So far, so good? Cool. Uh, and of course, there's a lot more to it, so in case you are interested in learning more, uh, feel free to go into the resources that are at the bottom of the slide. Um, so one thing that I will say is that we have a unit of measure of the amount of compute that these models produce, uh, for each, uh, each pass. So you will see the term FLOPS. So have you, have you seen the term FLOPS out there? No, not really. So it stands for Floating Point Operations. So it quantifies how many operations, like think of it as like additions, multiplications, are involved in a, a forward pass, let's say. And it basically quantifies how compute-heavy is your task. So typically, what we say is when we go through a Sparse MoE, as opposed to a Dense MoE, we have a lower amount of FLOPS. So this is the unit of measure that you will see.

Host 15:48 But back to your question. So what are these experts? So if you remember, I mean, ten minutes ago, we said that LLMs, they are decoder-only models. So I have a question for you. Let's suppose we wanted to put some MoEs in our LLM. Where would, would we put it? So here, I guess we have, uh, three choices. We have, uh, the masked self-attention layer, we have the feed forward neural network, and then we have, like, this normalization. So question for you, I guess, where would you put this? I guess where do you think is, I guess the most complex part of the network? Where is there a lot of operations? Feed forward? Yes. Yeah. Great, great answer. So, uh, it's indeed the feed forward neural network. And the reason for that is, I think, uh, Shervine, uh, mentioned it, I think, in lecture one. So if you remember, the feed forward neural network is a network such that you have the input, which is your, you know, d dimensional input vector. And then you have, uh, this being projected into, let's say, uh, dFF dimensional space, and then it goes back to the d dimensional, um, I guess, uh, space. So the dFF is typically larger than your dimension of, I guess, the input. When I say input, it's here. So it's typically larger. So the amount of parameters that you have in that feed forward neural network is something on the order of magnitude of d model times dFF times two plus some bias. So it's basically your order of magnitude. And the attention layer, if you think about-- if you remember, it's basically composed of the projection matrices. What is the dimension of the projection matrices? So it's d model times the dimension of keys, the dimension of queries, the dimension of values. And this dimension is typically much lower. So think of it O of 100. So your D model is typically O of 100, O of 1000, and then the projection here, the DFF is O, O of 1000, O of 10,000. Cool. So is everyone now convinced that this is a good way-- good place to put the Mixture of Experts? Yeah? Cool. So this is actually how it's done. So in modern day, day LLMs, this idea of not involving everyone in the computation of the next token prediction is such that you would pu-put the Mixture of Experts where the FFN is. It's basically here, and typically you would have a sparse Mixture of Experts, meaning that-- So back to your question. So these experts are actually, uh, fit for neural network. So you wouldn't-- you would have several networks that you can train, but you would only activen- activate one. So typically, K would be equal to one. It could be also equal to two, but it would only be a subset, so that's my point. Um, and this routing would be done at the token level. So if you remember, you know, the decoder, it basically takes, uh, something as input, so, you know, a bunch of tokens. And here, what I'm saying is that each token will be processed by an expert that may be different from the other token. So the rider-- router here would take the representation of the token as input and figure out which expert should be best for this token to flow towards. Does this idea make sense? So I have a little, um, illustration later on that hopefully will help. So now back to your question about how you train this model. Like, do you train the router separately? Do you train the expert separately? So one challenge that people have is when they train these MoE-based models to make sure that all experts are, I guess, having a weight, are being used. 'Cause it's very possible that you train your model and that somehow only, I don't know, one or two experts always get activated, and the other one, they always are inactive. They're never involved in the computation. So this problem is called routing collapse. So why is it called routing collapse? It's because the rier-- router always chooses some experts, but not others. So this is a challenge, and the way people try to mitigate this challenge is by changing the last function and adding it some extra term, which is written here. So it's basically some hyperparameter alpha times the number of experts times the sum of quantities that depend on whether or not tokens went to a, a certain expert I and then summed over all experts. So it's not super important that you completely understand exactly how that formula works. The only thing that I think you should take away from this slide is that this extra loss allows these quantities to converge more towards uniform distributions. So what are these quantities? Just as a reminder. So F of I is the fraction of tokens that are routed to expert I and P of I is the average routing probability for expert I. So when I say that, you know, all experts should be used kind of, uh, the same, what I'm saying is, I want this probability to be kind of uniform across experts. Yeah. Yeah. So the question is, uh, I guess, uh, when do you compute these quantities? So yeah, like, you can think of it as, like, you know, regular training, uh, process. Like, you know, you do some, like, mini batch. You kind of, like, go, go through that through, like, the, the model, and then you compute all these quantities. And then what you do is you do your, um, your back propagation based on that. And I guess what I want you to remember is that this incentivizes the probability, um, I guess the, the choice of the router to be more uniform across experts, which is something that mitigates this routing collapse phenomena. Yeah. Yeah. So the question is, can we use dropout? Of course. You can always, like, bundle that with some other techniques. So people have just kind of found this to be very helpful. So speaking of o-other techniques, there is something that I've not talked about, which is very similar to the dropout, um, idea. So it's called noisy gating. Noisy gating is basically, uh, you have your, your predictions from the gate, but then you add some noise to it. So basically, it's, uh, you know, by pure chance, it just, uh, allows other experts to be involved in the computation. So it's also some other technique. There's a bunch of techniques, but yeah, dropout is, uh, indeed quite useful for, like, things like overfeeding, and the idea can be reused in, in different settings. Yep. Yep. So the question is, how can you differ-- So you mean differentiable? So here, I guess, how do you take the derivative? Is that your, your question? Uh, how is the deri-- So c-can you explain a bit more what your concern is? Mm-hmm. So I guess, uh, to this question, um, so the average routing probability, so that one is a function of the gate output, right? That one. Pi, right? So I guess your question is for Fi. For Fi-- Okay, I don't have a good answer on top of my head, but, uh, I think, like, people have some techniques. And these days, you know, you just don't even have to do this by hand. You have, uh, like, the built-in thing. Um, so maybe I can follow up with you for Fi. But for P of I, do you see that this one is, is quite clean? It's just a average of, uh, the probabilities from the gates. Uh, yeah. So basically, the probability-- the output probability from the, the gate, you can think of it as just the vector being projected on a space of N, where N corresponds to your number of experts. And then it's gone through softmax, so your output is basically summing up to one. And each of these dimensions, they represent the value corresponding to what expert I would be, I guess, used for. Like, for instance, the first dimension would be for expert one, second dimension will be for expert two, and so on. So you just take the average of this. And like this one, you can express it from, you know, all the parameters, so I think you should be, you should be fine with that one. Awesome. Yeah. So the question is, if we increase the number of MoEs, does it increase the number of, uh, model parameters? So it's a great question. So it's actually, actually one of the ideas behind MoE-based models, which is that you can scale the model without having to incur the costs of having significantly more compute at inference time. So you can increase-- So people say capacity. You can increase your, the capacity of your model, but you will still keep some, I guess, like, controlled amount of active parameters. And active parameters are the parameters that are, that are used for a forward pass. So yeah, people just kind of use that. So yeah, it will just increase the number of parameters. So that's why you see some MoE-based models that are, uh, even bigger than the ones that we kind of had, like, on the order of hundreds of billions. We even have on the order of trillions of parameters. So for instance, here, uh, one reading I-I recommend is, uh, Switch Transformer, which scaled up to one-point-something trillion parameters. So yes, definitely more. Uh, but that being said-- So if you read the paper, you will also see that these models, they are more what they call sample efficient. So they take less time to be as good as what the model would have been with a lower number of parameters. So if you look at, like, uh, if you draw the, you know, training, training curve, uh, as a function of, like, the training time, you see that these models, they're typically more sample efficient. Sorry? Yeah, yeah. Exactly. Everything here is a trade-off. Everything here is a trade-off. Yeah. Thanks. Cool. Yep. Um, so the question is, each attention head will have a number of experts. So it's actually regardless of the attention heads. So the attention heads are-- You can think of them as being, like, independent, you know, something else. And the number of experts is independent of that. Does that make sense? Yeah. Right. Right. Oh, right. Yeah. The question is, uh, whether every block will have a number of experts. The answer is yes. And typically, those weights are na- not shared. So typically, you-- So actually, we're going to see an example. Um, it can very well be that layer one, there is the expert number, I don't know, three that was chosen, but layer two, there is, like, expert number one. And, you know, it's, it's, like, it's all, uh, free. It's trainable. So the, so the question is, uh, we will decide where to, uh, where the expert will go to. So all of that is decided by the gate, which is this quantity. Everything is, uh, decided by the gate, which has trainable weights. So you can think of this as just some projection from, uh, the input X to, uh, an N-dimensional space, where N is the number of experts. Uh, so question is, at what point during the inference is it decided? So, um, let's suppose we're at inference time. I'm going to walk you through how it works. So you have your X. So you have this, you know, attention mechanism, so it interacts with, uh, all tokens from the past, given that it's decoder only, so it's like masked. It goes here, and at the beginning of the feed-forward neural network block, the token is, of course, contextual, so it has the information from, like, these other tokens because it's, uh, attended. And what it does is it goes here. So X first goes into G. G computes, uh, this, you know, probability distribution over all experts. And given here that we are in a sparse MoE setting, we will only choose the top K. So let's suppose it's the top one, just, uh, the highest, uh, probability, um, and you will s-- you will know which expert this one will be. And so as a result of that, you will only compute the, the output value of the expert that the input was chosen. S- mm-hmm. So can you elaborate on that, actually? Yep. At what point exactly? So it's after the self-attention layer. Yeah. Uh, so the question is, uh, do we have different classification for different heads? No. So there's on- only one router. So, uh, I think I, I understand your question. So your question is, what do you do given that you have different attention computations going on in parallel with the heads? So if you remember, the attention layer has it- these different heads. But at the end of it, what it does is it concatenates all the results from each of these heads and then projects it once again in the D model space. Yep. Yep. Mm-hmm. Yep. Yeah. So the question is, do we have different Gs? So the only thing I can tell you is that the G is just layer specific. It's layer specific, it's trainable, so it's basically going to learn how to process all these, uh, inputs. So the G, the only thing I can tell you for, for your question is it's going to be layer specific. So the G is going to be one G for, let's say, the first layer, se- another G for the second layer, and so on. And that one's going to be trained. Cool. Great. I'm looking at the time. Do we have any other questions here? We're good? Perfect. So now I just wanted to show you a cool thing that, um, I believe, uh, the Mistral, uh, team was showing in one of their papers. So what they were showing here was for a given piece of text to show in which expert each token was routed. So as we noted before, um, so experts are different from one layer to another. So I believe here it's, uh, yeah, for layer zero, so it's like for one given layer. And we do see that, you know, roughly these tokens, I guess they leverage like a uniform amount of experts, more or less. What you would not want to see is to have every token be the same color. But luckily, it is not. But yeah. So that's one cool way of just representing how the routing is done, is to just have your input text and just represent where each token-- in which expert each token went. Cool. Okay. Oof. So what we just saw was one way that modern-day LLMs change their architecture to incorporate the fact that we may want to scale the model but not increase the computation complexity for one forward pass. And we saw that with MoEs. So you will see a lot of MoE-based LLMs out there. And now what we will do is knowing that we have an LLM, we're going to focus on-- [clattering sound] Ugh, don't worry. [laughs] Uh, we're going to focus on how a response is being generated.

Host 36:36 So remember when I told you that, you know, these, uh, modern-day LLMs, what they do is they take some text in, and they have some text out So it's typically this task, task of next token prediction. So you have a token in, so let's say beginning of sentence. You go through your LLM, and it just, uh, generates the next word or the next token, so A. And then you take A, and it goes to teddy, and then teddy bear is, et cetera, et cetera. But so far, we have never really dug into exactly how we chose the next token. So what we're going to do right now is to see exactly how we're generating the next token. So as you know, here, our LLM is just a decoder-only, uh, architecture. So here, what you have is a decoder with your input here and then your output there. So let's suppose for a second that we know everything that's happening in the middle, and we're just obtaining output probabilities that are going to look a little bit like this. So given a token or some sequence of token as inputs, you have an output probability distribution that represents what the model thinks is the likelihood that there will be a next token, let's say, that is equal to A, to airplane, to fluffy, et cetera. So this is what you have. So now my question to you is, if we told you we have some sequence as input, and we want to choose the next token, and if I told you that our model is giving out actually a probability distribution,

Host 38:34 I guess, how would you choose the next token based on this? Sorry? Great. The token with maximum probability. There's-- Okay, great. So yeah, so first idea, let's just take the token with highest probability. So, so it's a very natural approach, but I'm not sure if you've been using, uh, things like ChatGPT or Gemini. Every time you ask something, it always responds-- it responds something that is slightly different, right? So if you always choose the token with the highest probability, given that the computation here we're going to see is all deterministic, what that means is you're always going to generate the same thing regardless of, uh, I guess, with the same input, right? So that's one, one limitation. So it's not very, like, div-diverse. The second problem is if you choose the highest probability token on a, I guess, iterative basis, you're locally optimal, but you're not necessarily globally optimal. So what does that mean? So I guess if you think about it, our objective is for us to produce a sequence-- an output sequence of tokens that is, I guess, of a high probability. But the problem is, if you always choose the highest probability token, you will not necessarily obtain the highest probability sequence. Are you convinced of this statement, by the way? So let me give you an example. So let's suppose you have the next token where one token is point eight, the other one is point seven, and then you choose to go with the point eight. No, actually, it's not point seven because it has to sum to one, so let's say point two. So let's suppose if you go ahead with the sequence that go-- that starts with the point eight, let's suppose all other token probabilities are very low. Basically, you will have an output sequence that will have a lower probability than, let's say, the other path, which would, let's suppose, have higher probability predictions in the later steps, right? So we're going to see this in a second, but this is the idea. So if you choose the highest predicted probability, it's a good first idea, but it's locally optimal, but not necessarily globally optimal. And this is the reason why we have a, a second method that is about keeping track of the K most probable path. So I'm not sure if you've heard of beam search. So that's what beam search does. So here, K is sometimes called the beam size or the beam width. So if you hear these terms, these are just names that are given to the number of paths that we keep track of. And so this works as follows. So let's suppose we start our generation with the beginning of sentence token. We want to figure out what the next token is. So let's suppose we have, uh, here in this example, very basic example, like three tokens. And let's suppose the two highest probable tokens are A and Z. So if we have K equal to two, what we're going to do is to keep track of these two branches. So it's the first iteration. The second iteration is we're going to look at all the probabilities of next token prediction for these two tokens, and we're going to always save the two most probable path. And here, for instance, let's suppose if it's like the and then fluffy, and then A and cute. So back to what I was saying laters-- uh, earlier. So what I was saying was, here, if you were choosing the path that went along the highest probability token path, like the the, it's very much possible that the highest probability token after the would be a much lower probability than the one after a. And so this is what beam search tries to do. It tries to have a more globally optimal solution. So let's suppose we continue that, and then at the end of the day, we obtain, uh, I guess a number of, uh, potential, I guess, choices, uh, and the k potential choices, and then we, we pick the one that is the kind of highest likely, the sequence with the highest probability. So people typically what they do is they take the sum of the logarithm of the probabilities of the token. So they, they-- what they say is they say, uh, okay, so the log probability of the sequence is the sum of the log probability of each next token prediction. So it's the log probability of a, uh, knowing bos and, and then cute knowing bos and a, and so on and so forth. But I just want to point out one limitation of this approach, which is that the more you generate tokens, the lower your, I guess, uh, end sequence probability will be. 'Cause if you think about it, you know, all these probabilities, they're between zero and one. So think of it like in the kind of multiplied sense. So let's suppose you have the probability of the whole sequence, which is just a multiplication of the probability of the next token. The more you add probabilities be-below, like, less than one, the more this quantity will, I guess, go towards zero. So I guess, uh, this method as is will prioritize sequences that are shorter. And so for that reason, beam search has some, uh, additional term that basically counteracts that, that effect. So something on the order of, like, one over number of tokens to the power of something. So in practice, there is some, uh, technique to make sure that, you know, things kind of work relatively well. But okay, let's suppose we figure out all these things. Uh, the problem is that we need to keep track of this most probable path. We need to do all this, uh, kind of, uh, saving, etcetera, and it just, like, requires a lot of computation. And the other thing is we're still interested in the most probable path, which basically will lead to a sequence that is, you know, very-- that the model thinks is very likely. But sometimes what you want is for your output to be more diverse or more creative. So that's why beam search is actually not something that people typically use. People use beam search for things like machine translation, where you actually need to have something that is close to, uh, something being very likely. But actually,

Host 46:36 people use a third method. And this method is called also the sampling method. So I told you we have a probability distribution over tokens regarding what the next token should be. And so what people do is they just sample the next token using the probability distribution. Does this make sense? So in this example, uh, fluffy, gentle, kind, and let's say smart will have a higher probability of being drawn as opposed to, let's say, airplane and, uh, where that have a lower probability of occurring. Non-zero probability, but they have a probability of occurring. Cool? Any questions so far? Yeah. Right. Uh, so the question is, it's not for training, it's for inference? Yes, correct. So this is the-- You can think of it as, uh, response generation. So let's suppose you have your model that is trained. What you want is to generate an output. So what would you do? Yeah. So I guess, uh, just to complete my answer. So during training, what you would do is care about the output probabilities and then compare them with the actual label, uh, which is most of the time like a hard label. Uh, and yeah, this is what you would compare. So this one is, let's suppose you have an LLM that is trained. How would you generate a response? Cool. Everyone good? Yeah. Yeah. Yeah. So question is: How do you do sampling in this situation? So it's actually my next slide, but I just want to make sure everyone was [laughs] uh, on the same page regarding just the intuition. So highest probability is called greedy decoding. It's probably not something that we want. Beam search is a little bit better. It's more something that is globally optimal. It's not globally optimal, but more towards that. So it's better, but it lacks diversity, it lacks creativity, which is why what we want to do is to actually sample each token Um, and I guess we have a few methods that, um, also restrict the kinds of tokens that we want to sample from because I mentioned, you know, these very low probability tokens, they can still, again, theoretically be, uh, sampled, but it's not necessarily something that we want. So what people do is they typically restrict the highest probability tokens and only sample from them. So you may have heard of this term top-K sampling. Who has heard of this term? Yeah, a little bit. Okay. So what you do is you select the top highest probable K-- So the top K highest probable tokens, and you sample from them. So let's suppose, uh, if K is equal to four, you take the highest-- four highest probable, and then you just sample with them, and there's something else that is, uh, quite similar in idea, which is called top-P. So top-P is that you limit yourself to the top-- to the highest probable tokens such that their cumulative probability is more than a threshold P. So again, it will do the same thing. It will, uh, select the highest probable, um, tokens. But then there is a part that I still left out, which is how do you obtain these probabilities to start with? So if you remember, here I had mentioned that we just assume we have the probabilities, we just have them, and we want to choose what the next token is. But now the question that I'm asking is, now that we know what we will do with these probabilities, I guess one question is: How do you obtain these probabilities to start with? So if you remember, these transformer-based architecture basically computes an encoded representation of the input. And what you have is some final layers at the very top of the figure, which aims at projecting the vector into the space of the vocabulary. 'Cause what you wanna do is to have a probability number for how probable it is for you to sample a given token, right? So here, what you would do is, uh, at the very top of the, of the architecture, have your, uh, input, which is your encoded embedding of the token, go through a linear layer, which basically projects your D model vector into a space of dimension size of V. And of course, what you want is probability, so you would have a softmax layer, which basically converts everything to probabilities such that everything sums to one.

Host 52:24 And in order to compute the probabilities, this is the formula that you would use, which is the softmax layer. So there is a, a hyperparameter that is quite important that I want to talk to you about, which is the temperature T. And so this is where it, uh, pops up. So you have the probability of the next token being a given word, which is equal to the exponential of the input with respect to that given word over temperature, and then you normalize that by the sum of all the other exponential of the quantity over T. And now what, what we're going to see is what that T is used for or what that T actually, uh, does in practice. So before we go into that, just one question: Has anyone heard about temperatures when it comes to response generation? Yeah? Cool. So hopefully that will kind of give you a better idea of how the temperature kind of influences your output predictions. So I guess the question that I want to ask you is: What would be the impact of having a low temperature versus a high temperature? So low temperature would correspond to diverse-- W-why? Yeah. Yeah. Mm-hmm.

Speaker 54:35 So-

Host 54:36 Has anyone-- So we, we'll come to that in a second. So yeah. Do you have a... A lower temperature? Increase in temperature. So I guess back to your, um, the explanation about like, uh, I guess, lowering the temperature and h-what impact it will do to the-- So I guess, like, do you have a, a suggested, uh, a response to that? I guess, like-- Yeah, lower temperature. Let's suppose you have a lower temperature. What happens? Mm-hmm. Yeah. Yeah. Yeah. Yeah. So I guess, um, so the long story short is low temperature will create a spiky distribution, and then high temperature will create a uniform distribution. But I guess-- So I, I think you had the right, like, intuition. Um, I'm going to maybe write this in more mathematical terms. So... Whoops. Okay. Um, let's suppose you have, uh, donc your probability, which is, uh, you know, the exponential of Xi over T over the sum of exponential of Xj over T. So just mathematically, you can actually prove, uh, what is happening here. So let's suppose you have the index of the highest Xi. So let's call that K. So let's suppose what I do is I will factor by this, uh, quantity. So actually here I don't have space, so let's do here. So it'll be Ae of K temperature, and then here you have the sum of over all j of exponential of Xj over T minus Xk over T. So what I did is I just multiplied the numerator and the denominator by exponential of Xk over T. So I multiplied numerator and denominator, and of course they cancel out. But then what I have here is XY minus Xk over T, and here Xj minus Xk over T. So when I is equal to K, this term is zero, right? It's exactly zero, regardless of the temperature. And here, Xj minus A-- Xk is always negative or zero, right? So here, if I is equal to K, you have zero over T, so here it's one. And then you have one plus, I guess, some quantity, so j minus Xk over T, which is going to be negative. So the T going to zero. So that one will be, I guess, uh, going to, mm, let's say, minus infinity. So exponential of minus infinity is zero. So what you will end up with is something where for I equal to K, you will have a non-zero probability. But then for I not equal to K, you will have zero over something that is not equal to zero, which is zero. So just mathematically, if you factor by exponential of Xk over T, where K is the index of the highest value, uh, I guess the highest logit or the highest activation vector, can actually show that for a small temperature, only the highest... So the index of the, I guess, highest, um, value will be the one that will be, uh, I guess, highest probable with a spike there. And then when you have a high temperature, basically it will look like a uniform distribution because all these, all these quantities. So when T tends to plus infinity, this tends to zero. So exponential of zero is just E. [chuckles] Uh, sorry, not E. Uh, one.

Speaker 59:52 Yeah.

Host 59:53 It's one. So it's one over the number of j. So it's one. So just a uniform distribution across all the tokens of your vocabulary. Yep. Um, so the question is, how can I interpret a small... Mm-hmm. Mm-hmm, mm-hmm. So the question is, can I interpret that as a Gaussian? I think-- So it's kind of tough because a Gaussian, you have like some con-continuous quantity as in the X-axis. So here you have, um, you know, you have, uh, tokens, so it's kinda discrete, and it's not like, uh, something that you can order. So just probably interpret that as small temperature is very spiky. So here you will really have, uh, a given set of tokens that are the highest probable that will appear more. And if you have a high temperature, then basically tokens, even the ones that were not, uh, there to be kind of the highest probable, will actually have an adjusted probability that, that will be higher. Yes. So you can think of it as like some kind of scaling in that sense. So long story short, what I want to tell you is if you have a small temperature, it will encourage the next token to be geared towards being the highest probable token. And then if you, if you have a high temperature, I guess the distribution of probabilities will be kind of closer to a uniform if you really increase that temperature by a lot. So your output will be more creative. You'll have tokens that, um, you would have not drawn that will be drawn. And so what that means in practice, if you're-- I don't know, if you're with your favorite LLM, and let's suppose you want to, uh, I don't know, write something very creative. So which one would you use? Would you use a low temperature or high temperature? High temperature? Yes. So if you want something that's more deterministic, more, I guess, closer to, uh, something that is very, um, I guess what you think would be high quality, you will use more of a lower, uh, temperature. So one note here is that if you have a strictly positive temperature, every time you run your model over an input, you will obtain a different output, right? So something I want to point out is nothing in the transformer architecture is probabilistic. Everything is deterministic. The only thing that is not deterministic is how you sample the next token. It's the only thing that is not deterministic. So what will you do to have, like, a deterministic output? We have T equal to zero. T equal to zero, you know for sure that your output will be just one thing and nothing else. Well, that's what is, uh, kind of, uh, the theoretical, uh, property. But in practice, you have some stuff that is happening in the computation that introduces some non-deterministic operations. So it's very-- it's much more advanced than the scope of this class, much more advanced of the scope of this class. I just want to call out that in practice, T equal to zero may lead to different results because of this, um, kind of practical piece. So what I recommend-- So there's a suggested reading in case you're-- completely optional. So there's a very recent article around defeating non-determinism in LLM inference, so I recommend that you read it in case you're interested. So the high level idea is our GPUs, our hardware, when they reduce some of these operations, sometimes they are reducing numbers that are on really different scales. So the order at which these operations are happening is actually quite important. So the idea is if these operations, they happen in different order, it may lead to different results. Even if in theory it should be exactly the same, in practice it may not be the same, and this article actually does a great job at just explaining the intuition. So yeah, just if you're interested. Completely

Host 1:04:53 optional. Cool. Uh, I know I'm, uh, kinda late, so I guess, um, last thing that I want to say is let's suppose what you want to do is to generate an output in a very specific format. Let's suppose a JSON, JSON format. So I guess a very naive approach would be to tell your LLM, "Well, uh, please generate this in, let's say, JSON," and then, uh, it produces something and then you kind of, uh, try to see if it's a valid JSON. If it's not, you repeat. You just tell it to generate again until it, uh, does something well. So that's the first naive approach. Well, there is a second approach that is called guided decoding, and what that does is during the generation process, it filters out what it calls invalid next tokens. So here, uh, let's suppose I want to generate this JSON. I know for sure that my first token must be, uh, something that opens the, you know, the-- I forgot what the English word was for this, but, you know, it just opens the-- the brackets. Yeah. [chuckles] Open the brackets. So you can only have this, and then you can only have the property name. It's-- And so on and so forth. And sometimes you can have more than one permitted next token, in which case you would go back to our, you know, next token strategy. Yeah. So the question is: How do you restrict, uh, the, the other tokens? So there's a bunch of papers that go into that. We will not cover this, uh, but I can give you some pointers. Uh, just type finite state machine FSM, uh, context grammar. So there's a bunch of papers that do that. We'll not cover that here. Cool. And I think with that, we will, uh, go to the second part, uh, with Shervin. Great. Thank you, Afshin.

Host 1:07:08 So, uh, now together we're going to look at, uh, different prompting strategies. So now that we know how responses are generated, we're going to see how to get, uh, responses and how to get great responses. So let's go back to our favorite example about our cute teddy bear. Uh, so just I want to introduce one piece of vocabulary. So when you have some kind of input, uh, you have the length of your input measured in number of tokens. Uh, and you will see in the literature that it can have different names. So you can, uh, see it called context length, context size, window size, and I think the latest tools, like if you code on, you know, Cursor or any other, uh, code assistant tool, I think they call it a more context length. But, like, all these terms are, uh, equivalent, and they note the same thing. Okay. So now I want to take some time to discuss, like, what can be some orders of magnitude here. So, uh, like modern-day LLMs, they tend to be in the order of magnitude of tens of thousands, hundreds of thousands or millions of input tokens as inputs. So this is the kind of input it can take. So sometimes you hear some new LLM boast some number, and then that number of context length is exactly that. So it's like how much tokens can it accommodate in a single pass? Okay, great. And then, yeah, the models, you have seen, uh, like maybe some, like, advertisement of these models. So I think like Gemini and others, they're in the million territory. Um, and, uh, you know, does that mean it's all nice and pretty? You know, do we-- If we have, like, more context length, is it going to solve everything? Actually not. There is a phenomenon that was recently dubbed as context rot in a paper from earlier this summer, where basically the authors are experimenting the capacity of the model to retrieve some piece of information, uh, in a test called needle in a haystack. So basically, they ask some question, and in larger and larger pieces of text, they bury the answer. And they tr-they try to look at the capacity of the model to surface that answer. And then you can see that with respect to an increasing context length, that ability to ground the information with the answer that is in the context decreases. And, uh, yeah, the paper, I think, is a very interesting one. It, uh, like, controls with respect to what else is in the context. Like, there is a term of, like, distractors where they, like, put some noise and then they see distractors basically contribute in, uh, decreasing the retrieval capability. So, you know, also what is in your context matters. Um, so this is why in general when you have a retrieval problem where you want to use your LLM to solve it, you have some good incentive to try to target as much as possible the right piece of context for your LLM to see and predict on. Okay, great. And yep. Yep. So the con-- Yeah. So the question is, uh, is the context length exactly what is shown during self-attention? Uh, yes. Yeah. So and then we're going to see-- So I think we saw last time that, uh, sometimes there are, like, some, uh, tricks that are used for the, like, complexity of the self-attention mechanism not to be N squared. So this is what is being used to, uh, like manage basically the complexity of the computations as the context length grows. Yeah. But great call-out to that. That's exactly, uh, what is it about. Okay, great. Any questions? Any other questions? Okay, great. Um, so now let's define what do, uh, prompts usually look like. So there is no formal theory on how to structure a given prompt, but this is-- these are the main lines that are usually found in, uh, prompts presented to models. So you can distinguish a part that is, uh, like setting up the context where you, like, just put the setting. You know, you, you make it clear to the model what, you know, kind of query you want to, to issue. Then, uh, let's say if you have some tasks that you want the model to perform, you have instructions, and then these instructions are like some sort of function that take as input something. So you add some input and, uh, in order to get what you want out of the model's response, you may want to add some constraints, uh, out of it. So here we, we took our favorite example with a teddy bear. Uh, the context is, you know, like what is the teddy bear? Basically, what is the mood of the teddy bear? What do we want, uh, you know, to do in order to, um, like, make our teddy bear happy? And then, uh, we, we give some input regarding where the story that we want to generate is, and then, uh, we give some constraints. If you want some other example, uh, in the LLMs that you query every day. So the context could be, um, you know, some sentence that says, "You are ChatGPT. It is, uh, you know, we are October 10th. Uh, it is, uh, 4:44 PM." So you set the setup The instructions can be, uh, basically what the user queries alongside the input and then constraints might be thi-things that you don't see as a user but that might be, um, you know, present in the prompts given to the LLM such as safety instructions. For example, do not generate any contents that might lead to harm or things like this. So, you know, every time you see an input being fed to an LLM, uh, I think this projection into four-- these four dimensions can be a good mental model of seeing, you know, which pieces correspond to what goal, um, in, in that structure. Does that make sense?

Host 1:14:09 Okay, great. So now that we know, uh, like what kind of mindset we might have for inputs to an LLM, let's see how we can get an LLM to do what we want. And let's see how we can get an LLM to do what we want without tuning any weights. And we can do so with a concept called in-context learning, where the learning is a bit of a term that is overloaded because you don't actually learn anything with respect to the weights of the LLM, but you can, uh, like distill some knowledge inside of it, um, you know, as part of the context in order to do what you want. So you distinguish two main categories of in-context learning. So there is one category that is very simple, you know, in mindset. It's called zero-shot. It's basically you don't give anything other than your input, um, your input query. You know, you just ask the LLM to do what, what you want to do. And then there is another, uh, school of thought called a few-shot learning, where you give examples of inputs and outputs to the LLM before asking the input that you're interested in. So in the case of teddy bears and the bedtime stories, so you might, you know, name your teddy bear. So maybe you have a teddy, teddy bear that's called Teddy and you generated a story. So you put your query, you put the story that you want to generate, and you give multiple such examples. And let's say you have another teddy bear that's called, you know, Bob, you know, and then you want to generate a story for Bob. So you put all of these examples, and you ask the LLM to generate, uh, the story that you're interested in, and then this is basically what we call a few shots setting. Okay, great. So now, um, generally when you look at the performance of the, of the given, um, like of the resulting task, giving examples tends to steer the LLM nicely into the task that you're interested in just because you have like given an idea to the model of what you are looking for. And then it can use what it has learned during its training process to connect the dots and, uh, basically replicate. Um, and then, uh... But of course you need to gather such examples, so this is costly. Uh, this will put some more, uh, tokens in the context window, so you will need to like more compute. Uh, but, uh, there is an interesting trade-off here that we see in recent models. So they're gaining more and more reasoning capabilities, which is why I put the generally, um, nuance in italic here. So they're generally better few shots, but not always. Because these days, uh, with these like better models, people have seen that with, uh, like basically making the instruction better, you could make the performance of in-context learning on par or even better than if you provide examples. 'Cause basically when you think of it, when you provide examples, you constrain your model into given sets of examples that are finite. So when you are at inference time, let's say you want to perform a task on a distribution of data that has not been seen, it is harder for the model to generalize because it will try to align on what it has seen in the context. Whereas if you turn your instructions into something that is more reasoning-based, you explain how to do the task with natural language, it can use its reasoning abilities to actually do it. And then this is something that you see more and more these days. Um, so the literature on this I think is still in, in progress, but you have some papers like, uh, Plan and Solve, uh, that I think, uh, came out recently and that shows, you know, if you ask the LLM to plan itself and then solve something, uh, it can have very good performance. So yeah, this is an interesting, uh, this is an interesting

Host 1:18:35 fact. Okay, great. So now that we have seen, uh, basically the kinds of learning that we have, now we're going to see what we can do to improve the quality of the response. So there is this concept called chain of thought where, uh, researchers have seen that if you force the model to come up with some rationale to some answer before actually giving it, it would give higher performance. So this is what you-- what people call as chain of thought. It's basically what's led you to the answer. So here, for example, if you, uh, you know, ask yourself, you know, "How old is this teddy bear?" And if you force the model to respond directly with a number, it might not be able to do the connection as to exactly why the teddy bear is a given age. Whereas when you give the kind of full chain of reasoning, then it becomes clearer as to, you know, what led to that response. So I think this is the main mindset behind this technique. And, uh, basically this is something that is-- that can be used in in-context learning. So if you give, uh, like, few shot examples, you know, how old was, was this teddy bear? You give some number, and then you slightly change the query. And then based on the reasoning formatting and then the response, the LLM can adjust the reasoning and the response accordingly, and it will force the model to output some reasoning alongside the response, which shows an improvement in um, in basically, uh, metrics. Okay, great. And then, yeah, something else that I want to say, you know, let's say you are, uh, you want to do a task and you want to do it well. You know, oftentimes you will always have some samples that do not work, and then for them you, you want to have debugging ability, right? And usually when you debug with LLMs, you don't debug like the old days. You don't look at weights, at, at the intrinsics of the LLM. What you want is something more interpretable that comes out of it in terms of tokens and usually, uh, you know, with these techniques, you can see the reasoning that the model had before outputting a given response, and you can debug basically what went wrong. So if you ask, "How old will, will the bear be next year?" And if in the chain of thought it says, uh, "Hey, we're in twenty nineteen," you know that somehow in your context, you know, oh, maybe I put the wrong dates, you know, in there. So you can, like, trace back to... You can do some root causing very easily. So it's also used for that and, uh, you know, exactly in the same way as other techniques that increase the number of tokens, uh, this is a trade-off that you have to manage that it will of course take more time, um, you know, to infer because you need to, to generate more tokens. But typically we're fine with it. Any questions on CoT? Okay, great. So now let's take it one step further. Um, so I want to introduce, you know, even to make CoT even stronger, you can sample your model several times, look at the answers it generates, and then do some majority voting to select the answer that was predicted most of the times by a given LLM, and this is what we call self-consistency, where basically you sample responses multiple times and then parse the actual answer. So basically you kind of factor out the whole reasoning and then try to target the answer. And then by majority voting, you can come up to an answer in a more, um, robust way. Yep. Yep. So the question is: Do you need to have some benchmark to know if it's better? And yes, absolutely. I think the paper operates on top of, uh, all the arithmetic and then mathematical-based ones. And then I think one tangential question to yours is how can you locate the answer and then do majority v- majority voting on it? So typically you can put into the context some instruction that says, "Put the actual answer last." So you can just, like, extract the last. People, I think, uh, use regex-based techniques otherwise to extract the answer or you could even think of using some other LLM to extract the answer. So there is always a way to kind of do it. Uh, but, uh, yeah, to your point, yes, we need, uh, some benchmark and then ground truth labels to assert that this is indeed better. Yep. So the request here-- So the question is, uh: Is it going to be sent to the same request as example? So typically you sample it in parallel. So basically you ask your model exactly what Afshin just mentioned. You sample from the probability distribution of BOS and whatever tokens you had, the next token, and you do that in several other, uh, kind of branches. And you do that, all of that in parallel, and then you kind of parse the answer at the end of it. So basically the latency of this process is equal roughly to the maximum latency of either parallel generation, 'cause you can do all of this in parallel. Yeah. So n- so none of these go into the context of each other. They're all done in parallel, and then you get final answer. Okay, great. All good? Okay, great. So now that we have seen a few prompting techniques, uh, I want to cover together, um, tricks that

Host 1:25:00 people have come up with at inference time to make the generation as efficient as possible. So, um, and basically, uh, yeah, so in modern day, uh, models you have a lot of parameters. You want to generate a lot of tokens. How do you do it the most effent- efficiently possible? So I want to ask- To divide this thought process into two parts. So we're going to see, you know, what methods we can come up with that give up-- uh, that give us increased efficiency on an exact level. So you exactly do the same computations as you were supposed to do, but, you know, in a more efficient way, and I put some, um, you know, hints as to what kind of techniques we're going to explore. So, you know, let's take-- let's try to look for techniques that avoid redundancies. Let's try to see what we could do to, uh, manage the memory in the best way. And also let's try to see if we can, uh, reformulate, uh, the equations inside the LLM in a way that could simplify the, the generation in practice. Then there is a second category that we're going to explore as well, uh, that is going to focus on what kind of approximations it might be fine to do and, uh, get a high-quality answer, uh, at a le-- uh, at, at a lesser cost. Uh, but, you know, it would be approximate. So we have, you know, what kind of, um, variations we could do on the architecture. Is there something we could do on the embeddings, um, to make them more efficient? And then, uh, maybe on the token prediction side, is there something we could, uh, do to make it, you know, faster? Does that sound good? So we have approximately twenty-two minutes. We're going to try to go through all of them, um, here. Okay, so I grouped the categories of techniques into exact and approximate techniques. Uh, but actually we're going to look at them in a grouped manner. First, looking at the attention layer, uh, seeing what kind of techniques we could, um, have there. And then in a second ti-- in a second part, we're going to look at the output layer and then see, you know, what we can do at the level of token generation to make things, uh, you know, as, as good as possible. Okay, so let's start at the attention level. So we have seen that, uh, you know, for every token, you need the current token to attend to the previous ones, right? In this masked self-attention. So let's say you generate your sequence. You are at a given token. So let's say, you know, you have generated a cute teddy bear, and then now you are at is. Now you have the query is. You will compute the key representation and the, and the value representation of is, because of course you have to do it, it's your current token. But we want to have a way to reuse the past computations we had done to compute the key representation of the previous tokens and the value representation of the previous tokens. Does that make sense as a goal? Does everyone agree? Okay. And more precisely, basically, we want to find a way for the key and value matrices to be saved. And, um, you know, I'm not underlining the q, the q part here because of course, the query corresponding to the previous tokens are not going to be of interest, uh, for the, the present token. So it's like the key and value part. Okay. So there is, uh, like this concept of KV cache, where the goal is to store these key and value matrices somewhere, um, and reuse them directly from the cache. So like what I just mentioned here, you know, when you want to compute a given token, you would reuse the key and the value directly from the cache instead of computing it again. So yeah, so, um, yeah, so this is basically, um, you know, representation of what we just mentioned here. Um, yeah. Does that make sense? Okay, awesome. So what else we could, could we do? Oh, yeah. Yeah, great question. So during training, do we do KV caching? I would say during, uh, training, you have this concept of teacher forcing, where you put all your inputs and pass it all together at once. So this concept of KV caching, CA-caching doesn't even come up. Uh, yeah. Yeah, but great point. Yep. Yep. Yep. Yep. So yeah, so the question was, uh, you know, what is the point of all this? We want to just reuse, uh, like the computations that were already done, and then your answer is yes, spot on. Any other questions? Okay, great. So now that we have seen, you know, that we could cache these quantities, so what else could we do? So is there something from last week's lecture that we could reuse? You know, maybe something that reduces the amount of cache, you know, the key and value. Do we have some techniques? Sparse attention. Um- Yeah, that, that could be. That could be. But, uh, not here. Like, let's say you are not-- you're attending to everyone, and you focus on the number of keys and values. Is there a, a way to reduce this number? So just to recap, we have... Here I'm operating in the context of multi-head attention, which is you have your H heads. So you have H number of query projections, H key projections, H value projections. Is there, is there any technique from last week that we could reuse that could reduce this number? Yeah, I heard it. Yeah. Group query attention. Yeah, exactly. So we had this, um, you know, concept of grouping keys and values together, uh, where basically the general formulation is called group query attention, where you group these and then the external values H and one denotes respectively the full multi-head attention and then multi-query attention. And then in, uh, modern day LLMs, uh, like a lot of papers, they use, uh, GQA, uh, with, with some, uh, group that is a sensible value. Yeah. So this is also something we can do. Okay, great. And now I'm going to go a little bit into the hardware side of things. So if we were to store the cache for all these values in a naive way, you know, at inference time. So let's say you receive-- So let's say I'm an inference server. I receive queries from multiple users, and let's

Host 1:33:09 say I receive a query one and I receive a query two. Um, you know, a naive way of storing the key and, and value, um, you know, matrices would be in reserving a pro-- a portion of the memory at the beginning that correspond to the entire context length because you don't know, you know, where you're going to stop, right? You're decoding because you stop your decoding when you hit the EOS token. So you would have like this whole block of size, uh, you know, context length, like maximum context length that could be reserved. So one observation is that it leads to a lot of waste. So let's say if your context length is of size like two K, you have, uh, two K reserved for a given, uh, you know, request, two K there. So at any given time, like let's say you want to get more requests, you want to serve more requests, your memory will very quickly not have enough space to, uh, accommodate, uh, them. Does these constraints or does this challenge make sense? Yeah. Okay. And then, uh, there is this paper, uh, that, uh, that is called PagedAttention, and it defines several, um, like, uh, quantities. So there is this like reserved quantity, internal fragmentation, and external fragmentation. Internal fragmentation is basically the space that is being reserved by the model to complete the request, and the reserved spot is the subset of it that corresponds to tokens that were actually being used. So it's the kind of space that's actually used. Internal fragmentation, there is nothing in there, but it was reserved. And external fragmentation, it's the memory, uh, management system that doesn't necessarily put one, uh, you know, block one after another, but has its own way of allocating, uh, memory blocks, so it might leave some other gaps. And they came up with a system that is called a PagedAttention, uh, that is, um, you know, powering, uh, one inference package called the vLLM that, uh, solves this issue by mapping, uh, like the generation process by blocks of fixed size. So instead of, uh, allocating a whole portion of the memory to answer a given request, it breaks it down by smaller chunks. So I think the paper takes, uh, like a value of sixteen for blocks. So as you can see, let's say you are in a generation process and you have used a given row, you would just start using another row without, um, you know, wasting more space than that. And then you have some dictionary that maps token position indices to, uh, to basically their, uh, their cache values. So there is like a smart way of managing it, and they show that it reduces fragmentation by quite a lot. Yeah. Okay, great. Now let's do something else with this KV cache. So, uh, we just saw that, you know, you have your internal representation of your token, and you project it into query, key, and value. And then key and value is actually something that is of a dimension that is, like, non-negligible, and you need to store, uh, H copies of it in each transformer block. So you have many of these, uh, vectors that you need to keep track of. And is there a way to make that representation somehow more compact? And this is a topic that, uh, DeepSeek has, um, you know, tried to tackle in a concept called, um, I think it was called multi-latent attention. We're going to see Uh, so, you know, l-let's look at the vanilla case. You know, if you are in multi-head attention, then for a given representation of a token, you have H projection matrices that turn it into a key. Does everyone agree with that? So the kind of, uh, self-attention formula, you know, you have a projection matrix W, uh, K for keys that will project the token representation into some key, and you have H heads. You have H such projections, and you have H such resulting embeddings that you need to store in your cache. 'Cause you have that for keys, you have that for values. That's a lot of, um, vectors to store, and these keys and values, they are, uh, you know, quite long as well. Uh, so l-let's see if we can, like, um, make it smaller. What multi-latent attention does is that it factorizes these, um, you know, projection matrix into an intermediary space that is of lower dimension than the space of keys. You have a first transformation that reduces the dimension and then another one that decompresses it. So this is the first, uh, operation kind of that they did in order to make the rep-representation more compact. But they did something else that is very smart. They said that the compression matrix could be shared across keys and values, which says for a given token representation, the cache that you need to store for keys and for values is the same. And then you would have, um, you know, still different matrices here for the decompression part to, like, actually learn different representations for a key and value. But, you know, one, um, simplification here has been to, like, share it for, like, across keys and values, and even better, share it across the H heads. So instead of having H such embeddings, you have just one. Uh, and then you do that, you know, for key, you do that for value. So at the end of it, for every transformer block, you have a single representation or token. Does that make sense? So not only you have, you know, less things to store, the DeepSeekV2 paper also showed a performance improvement that it's, uh, kind of credited, like some regularization, um, consequence of doing so. So it, it learns representations that are maybe more useful and shared across keys and values. So, you know, apparently there is also, um, performance benefits to it that is not just hardware-based. Okay, great. So now we have seen some tw-- Oh, yeah. Yeah. So the question is: Do you tune the low-rank dimension? So the dimension itself is a design choice. It's fixed. So the question is: Is it the same, uh, like, lower dimension for everyone? So the dimension size is fixed and is the same for everyone, I think. So, but it's a design choice. Yeah, you, you could have different ones. But I think in practice, it's, it might be the same one. Yep. Any other questions? Okay, great. So now we have less than ten minutes. We are going to cover techniques that operate at the output token level, um, and then start with a concept called speculative deco-decoding. That is, um, kind of this very interesting method that uses some smaller model to help the generation of a bigger model and then uses some scheme that makes the distribution outputs match the one of the target one. So it uses a combination of tricks of using, like, a smaller model to generate things and then gates it with some mathematical-based properties to ensure we get a distribution that looks like the one of the big model. So here's what is the mind-- like, here's the mindset of it. So let's just come back to our favorite example about teddy bears. So what you do is that you ask a, a smaller model, uh, that we-- that the paper calls draft to generate next words. So you have, like, my teddy bear, you know, what could be next words. So you have one pass, you know. You find token IS. You fit token IS here again. You find cute and smart. Since the LLM is small, this is typically done faster than with the big LLM. And then once you have all of these, you put the tokens that are predicted by the smaller LLM all as input to the target, uh, LLM, that is, like, the bigger model, like the one that you use to generate probability distributions for each of them. And then we're going to see that by having some rule on the output distribution of each of these tokens, you can simulate A distribution-- a probability distribution of each token, of each next token that's, um, kind of looks like the one of the target models. So here's basically how it goes. Um, so it looks at the probability of the, uh, the token that the draft model has predicted. So if the probability of the draft model is bigger than the one of the draft model in the draft model's output distribution, then you just accept the token. Otherwise, you have some acceptance, rejection mechanism that either accepts the token or rejects it. And, uh, you know, let's say everything is accepted, then in a single pass, you are able to advance, you know, by way more tokens. Um, and then if it fails, then basically you resume the process of generation from that token onwards with some, uh, adjustments on the distribution. So one question that you might ask from all of this, you know, this looks like a recipe. Like, why is that matching the target distribution? So if you start from the law of total probability and write each term with these quantities, then you will find the target distribution at the end. So it's a s- an exercise that I encourage you to do. And the to-- the paper that is attached to the slide here demonstrates it in like, uh, just a few lines, so it's a very simple proof. Uh, and I, I think it's a very, very interesting one. Does that, does that make sense? Yep. Yeah. So I think it's, uh-- Yeah, the question is, is that rejection something? Yep. So some of you might be familiar with it already. Does that make sense? Yeah. And then one thing that I didn't say is that why did we even put the last token here? You know, we put all the draft tokens, but also the last one that was predicted. Because by doing a single forward pass with all these draft tokens, you get for free the probability distribution of the token that comes after that, that you can then just sample from QK plus one. So, like, just to give some summary of the rationale, um, doing a single pass is, like, as expensive as doing one pass at a time because at inference time, you are memory-bound. Like, in other words, uh, computations are not the limiting factor. It's basically the memory that will bottleneck your computation. So you want to do it on a smaller model, and then on the big models, you want to compute all of these probability distributions at once. Does that make sense? Okay. Great. And then I want to talk about one last technique that is called multi-token prediction. It's the same, uh-- So by the way, this previous technique was called speculative decoding, and then this one is basically doing the same, but so it's doing exactly a different thing, but the draft model is embedded in the same model, which is, uh, very powerful. So basically, it's a model that's, uh, attaches multiple heads on top of the representation of the last decoder. And the process here is that at training time, it doesn't do next word prediction. It does multi-word prediction. And at test time, the draft model is all your heads, and your, uh, main model is just the first head. So you have, like, all your draft, uh, tokens that you then feeds back to the first head and then do accept- acceptance and rejection. So the paper does it in a greedy way. So it doesn't do it with this, like, formula because since the architecture and then the objective function has changed, you don't have this, like, nice property of finding again the, like, next token predictions distribution, but you have, like, a slight variation of it. And, uh, yeah. So, like, the interesting notes out of the multi-token prediction is the change in objective function, and then second, the, um, the fact that the draft model and the target model are basically embedded in the same one. So don't have to, like, separate the two. And, um, yeah. So you do remember the slides. We have explored techniques that can remedy each of these, uh, aspects. So yeah, I highly recommend, you know, taking a look at the associated papers as well. And with that, thank you very much.