Competition-Level Code Generation with AlphaCode (Paper Review)
#ai #alphacode #deepmind

AlphaCode is an automated system that can solve competitive programing exercises. The authors found an interesting combination of language models, large-scale sampling, and clever techniques to filter and subsequently cluster the resulting programs, which lets the system perform on the level of an average competitor in real competitions. In this video, we take a deep dive into AlphaCode's design, architecture, and experimental evaluation. The paper is very well structured and the empirical results are super interesting!

OUTLINE:
0:00 - Intro
2:10 - Paper Overview
3:30 - An example problem from competitive programming
8:00 - AlphaCode system overview
14:00 - Filtering out wrong solutions
17:15 - Clustering equivalent generated programs
21:50 - Model configurations & engineering choices
24:30 - Adding privileged information to the input & more tricks
28:15 - Experimental Results (very interesting!)

Paper: https://storage.googleapis.com/deepmind-media/AlphaCode/competition_level_code_generation_with_alphacode.pdf
Code: https://github.com/deepmind/code_contests

Abstract: Programming is a powerful and ubiquitous problem-solving tool. Developing systems that can assist programmers or even generate programs independently could make programming more productive and accessible, yet so far incorporating innovations in AI has proven challenging. Recent large-scale language models have demonstrated an impressive ability to generate code, and are now able to complete simple programming tasks. However, these models still perform poorly when evaluated on more complex, unseen problems that require problem-solving skills beyond simply translating instructions into code. For example, competitive programming problems which require an understanding of algorithms and complex natural language remain extremely challenging. To address this gap, we introduce AlphaCode, a system for code generation that can create novel solutions to these problems that require deeper reasoning. Evaluated on recent programming competitions on the Codeforces platform, AlphaCode achieved on average a ranking of top 54.3% in programming competitions with more than 5,000 participants. We found that three key components were critical to achieve good and reliable performance: (1) an extensive and clean competitive programming dataset for training and evaluation, (2) large and efficient-to-sample transformer-based architectures, and (3) large-scale model sampling to explore the search space, followed by filtering based on program behavior to a small set of submissions.

Authors: Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu and Oriol Vinyals

Links:
Merch: http://store.ykilcher.com
TabNine Code Completion (Referral): http://bit.ly/tabnine-yannick
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
LinkedIn: https://www.linkedin.com/in/ykilcher
BiliBili: https://space.bilibili.com/2017636191

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

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 AlphaCode is a system by DeepMind that does automated competitive programming. You're able to give this system a lead code style problem in natural language and it will come up with code by itself that solves the problem. It does this by using a combination of language modeling, sampling, filtering and clustering before it finally decides on the solutions that it's going to try out to submit to the server. What is mind blowing is that this system was able to perform in human competitions and be about as good as the average programmer in these competitions, which is crazy because previous systems were nowhere near human level. So here's how it goes. This video right here is a comprehensive paper review where I will go through the paper with you and explain to you the most important parts of the paper, what's in there and what I think is good and what I think is bad. After this video, you'll have a good understanding of the paper and of how the system works and what its potential weaknesses are. However, in the next video released tomorrow, I will interview the authors of AlphaCode, which is a huge privilege and I'll be able to ask them anything I want and they will have seen my paper review and they'll be directly able to respond to any criticism that I've raised there to any questions that I had and to whatever I did wrong in my paper review. On top of that, you're able to get a behind the scenes look into their work. Even at places like DeepMind, things go wrong, things don't work out. They've had results that they thought were too good to be true and they turned out not to be true and many more things. On top of that, we talked about how the project came to be and also how they've dealt with media reception because this paper has made big waves. So I absolutely invite you to watch both this video and the interview part because they're very much complimentary. Let me know how I can improve these videos for you. If you like, leave a like, tell someone to subscribe and I'll see you around. Bye. Hello there. Today we're going to look at competition level code generation with AlphaCode. This is by researchers of DeepMind and presents a novel system that can take part in competitive programming challenges. These are challenges where you as a user you'd register and then you'd be given lead code style problems to solve and these aren't easy problems. These aren't just solving some or writing down some SQL statement. These are legitimate, difficult programming challenges where you need to think of algorithms and solutions to problems and so on. So having a system that can actually take part and compete against humans is very remarkable. They've submitted this system to 10 of these challenges. And as you can see, the orange lines here is AlphaCode's relation to other humans. They perform about as well as a median human would like an average middle of the road competitive programmer, if you will. So this is pretty remarkable, especially since the baseline system so far had been sort of in the third or fourth percentile, not very good. So this represents a significant boost. And today we're going to find out how they did it. But first, here is what such a problem might look like. So this is one problem. This is one data point in this in this data set or one such challenge that you have to solve. You can see it starts with a description. So the title is Backspace. It starts with a description. You're given two strings, S and T, both consisting of lowercase English letters, yada, yada, yada. What you should note right here is that the description is in natural language. It's made for humans and therefore it's just natural that it is a natural language. There is no other form. There's no machine readable form right here. This is it. This is what the algorithm alpha code sees and gets as an input. There's also a description of the input again in natural language. There's description of the output. And there is also this part right here. This is an important part. It consists of a bunch of example inputs and outputs. So here is an example input. For example, there are four problems in this problem set. All of this will be described in the input section. So the input section here says the first line is a single integer, the number of test cases and so on. So that's the four. Then we have this is a problem. So this is S and this is T of the first problem. The goal is to type S and strategically type the backspace button instead of the letter at S to go from S to T. So in this case, we start with S. So the first letter is A, but we choose to type the backspace button, which would not type A and would delete what we have, but we have nothing. So yeah, then we would type B. Sorry about that. And we would type B. Then we would type A, then we would type B. And instead of the last A, we get again type the backspace button, which would delete the letter before it. And we'd end up with B, A. Therefore, we got from S to T. And therefore we output the letter the word Yes. So we are tasked with writing an algorithm that automatically determines whether it's possible to go from S to T in any of these test cases, and output the corresponding answer. This is challenging by itself, but you only get the problem right, if you can do it for all the test cases. And the way these problems are evaluated is that on the on the test server, they have a whole bunch more of these test cases, and including checking all the corner cases like very long inputs, no input at all, only inputs containing the letter A. If for some reason you expected a B to be there. And so they test all the edge cases, and you need to be correct in all of them in order to get the points. This is extremely challenging even for a human, the output that you're supposed to give is an algorithm like this, you can see it's not an easy thing. It's not just a snippet, it's a full blown algorithm, it contains input. So you read, you read the inputs, even that to program an algorithm to come up with that piece of code is already challenging by itself to firstly read that first, let the first line and then read as many inputs, then you need to build lists and reverse lists, and you go into a while loop where you pop off things of list depending on comparisons. And in the end, you output the correct thing depending on whether that list is zero, or empty or not empty. So as you can see, this is this is a challenging, challenging task. And this is just one data point. The next data point isn't going to be another variant on two strings and and typing the backspace button. The next data point is going to be a completely different problem, right? Like searching for shortest paths and some graph or something with denominators of numbers or numerators or, or something like this, right? It is, it is very diverse set of problems and very challenging even for humans. And the fact that an algorithm can tackle it is very remarkable. So how do they do it? That's that's our question today. If you guessed that it has something to do with large language models, then and transformers and so on, then yes, you know, kudos, you got it. But there is a lot more to it. And this is really an engineering effort. And I think we should appreciate just, you know, how far you can push a system to get continuous improvements. What they do first, though, is they collect a data set. They do train on a open source code from GitHub. That is the pre training data set. This is very similar to open AI codex model. So open as codex model is trained on code from GitHub. And you can simply do next token prediction on code. And I have to say I've tried codex and I'm pretty happy with its suggestions is very good. But it can give me like longer snippets than an auto complete. But it cannot like solve any kind of problems like this, it can just continue code. In any case, they collect this pre training data set, they have whatever 700 gigabytes of code that they train on. And they do run their regular language modeling objective on that piece of code. Then they fine tune on an appropriate data set of code contests. So this is a mixture data set that they scrape from multiple websites, for example, code forces description to code, code net, these are these are papers, previous papers, or competition settings that they have collected these data sets from and the data sets again, this here is one data point, right? This is a problem description. And usually these, these data sets, they contain one or multiple solutions, not all of them might be correct. But they contain about an order of magnitude more solutions than they contain texts or problem descriptions. So first, they collect a data set, and then they train on that data set. So that could be the story right here, but it is not. The entire pipeline is a bit more complicated. You can see first, there's GitHub, we collect pre training data, we do pre training, then fine tuning on pairs of problems and solutions of these code contests data set. This is as I said, a collection of various data sets that contain these that contain these code challenge type of problems, lead code style problems, and they do fine tuning. By the way, their model is a transformer model, you could guess it, they do have a special they have an encoder decoder model. So you have some sort of an encoder, and they choose to make the encoder shallow and the decoder, the decoder deep. And there are specific reasons for that, which we'll get to in a second. But the encoder mainly handles the this description, which is so the description is natural language mostly contains, you know, some some code snippets and so on. However, it contains mostly the description. That's the encoder. The benefit of using an encoder decoder architecture over a decoder only is that you do get bi directionality in the encoder. And as they do here, you can make them different sizes, which means that you can shrink the encoder, which makes you sample able to sample faster and sampling is going to be very important for the system right here in just a second. And then the decoder will be a autoregressive decoder, where they just well int j equals five, yada yada yada. So this is this is actually going to produce the code token by token in sort of a language modeling way. Their objective is is they have a masked language model objective at the encoder. And then the decoder obviously there's cross attention right here. There's there's self attention in the encoder, there's self attention, causal self attention in the decoder. And then there is cross attention from the decoder to the encoder. And they have a language modeling objective in the decoder. And they do say, it's quite important to have the masked language modeling loss additionally in the encoder, because it apparently makes the encoder understand this, the stuff in inside of it, the stuff that it's fed a lot better, I'm just going to believe them right here. So now that we have this model, we can, we can fine tune it on these data sets, right, we can feed a description right here. And we can feed one of the solutions, and that could already be it. However, that's not it. It turns out that most of the time, this doesn't actually solve the problem. So you feed in a description, and you sample the solution, it is not it does not go well. So what do they do? Well, there are two ways. The first way is you try to make your model a lot better at like thinking and coming up with solutions and reasoning abstractly and so on. But that doesn't sound very deep learning and transformer like so what do we do is we just do large scale sampling. That essentially means you have a problem, you get a new problem, you feed this into your decoder right here. And then you just sample like a bunch of solutions from your decoder. Sorry, I just said decoder over here. You store this into the encoder, you let the decoder run, and you generate a ginormous, a ginormous amount of outputs. So you can do this with language models, you can sample according to some temperature, you can do some other stuff, you do nuclear sampling and whatnot. But you can generate diverse outputs from the decoder. And they do, they sample thousands up to a million different outputs from the decoder. So now they have this large set of potential solutions. And what do they do with it? This is very important, they do filter, and they cluster. So first the filtering happens. And it might not surprise you, but the filtering happens on these example inputs that we saw right here. So for every problem, you get a tiny amount of example inputs and corresponding example outputs. They simply let all of the programs they generate run on these example inputs. And the ones that don't crash, they evaluate whether they do get the example outputs. And if they do get the example outputs correctly, they keep them around, otherwise they discard them. This is obviously vastly different from how humans solve these things. Humans don't just generate giant amounts of solutions and then let them run on this tiny amount of example problems. But this eliminates, as they say, it eliminates over 99% of these sampled things. So you end up with a slice right here of this data that you've generated by simply evaluating on these example cases that you had. So it's quite important that these are there for the system to work. I wonder if like, we could replace this, because we have this approach as well in for example Dali, where a lot of stuff is generated and then clip is used to rerank. I wonder if something like this could be done here. But they have several helper models in here in order to help the system during training. So I don't know if another helper model might be even appropriate. So this leaves them with a tiny amount of solutions, which could still be a lot, right? 99% out of a million is still a lot of solutions. And they keep themselves to just submitting 10 of them. As a human, sometimes these code platforms, they have actually a limit on how many things you can try to submit and 10 is like a reasonable limit. It gives you a little bit of as a human, a little bit of you're not anxious to submit a solution. If you think it's the correct one, sorry. But you also you can submit a few times, but not too often. Like you can't brute force the test set that's on the server. So they need to get down from these still large amount of solutions to 10 solutions. And that's where this clustering comes in. So the goal is to end up with this small select set of candidates to execute and evaluate. And what do they do with the clustering? This is where one of these helper models gets in. So all of these things right here, they are programs, they're programs that could take inputs and outputs, and there are many, many of them. What we want to do is we want to cluster them, a lot of these programs are going to be different in the tokens that they use, like in the exact code, but they're going to be essentially the equivalent program to each other, like they're going to be the same program isomorphic to each other. However, graph isomorphism, like let's say we parse them in a syntax tree and check graph isomorphism, that's, I do believe that's like a really hard problem. I might be mistaken, but I think that's used in cryptography to show like a really hard problem. So it's not really graph isomorphism on the syntax tree, it might not even get all the isomorphic programs. So what do we do? Our plan is going to be we want to group these programs into the same one. So maybe these three here are actually the same. And this one here is actually the same. So we'd like to figure that out. How do we do it? We just feed like a whole bunch of inputs, like we just generate a whole bunch of inputs to the programs. And this is we train a little model that can take descriptions, like problem descriptions, and generate new input output pairs, not even input output pairs, just inputs. So we take a problem, and we take these example inputs, and it can generate new ones. Now we don't care what the output is, what we do care is we just feed all of them to all of the models, like all of them go to all of the models, and we just observe the outputs. And we say, well, whenever two programs have the same outputs on all of these test cases that we came up with, they are the same program, we don't, we don't, again, we don't know the solutions to these inputs, because we made them up. But we can assume that if two programs output the same thing for all kinds of inputs, that they're essentially the equivalent program. Note that we can't just input random garbage right here, because the programs might differ with respect to how they handle edge cases and so on. So it is good to have an informed model be the one that's inputting things into these models. So that lets us figure out groups, let's say, okay, all of these models responded the same to all of these inputs that we gave them. So we'll just consider that the same program, and we'll just submit one of them as the one of the 10. And we go to the next bucket, submit one of those, and so on, we start with the largest bucket, and then we progressively go to the smaller buckets. And if we still have some some budget left, we go to the largest bucket again and sample a different one. And that's essentially how we group programs, and that's how they get it down to fairly small set of candidates. Why do they start with the largest bucket? Their reasoning is that is that wrong, there are many ways that wrong programs can be wrong. So selecting the largest bucket, I don't know, we'll have to read what they're saying. But essentially, they say there are many ways to introduce bugs, and therefore they expect the wrong programs to be in smaller, but distinct buckets. And that's the system. That is how they solve the programming competition. This might not be as flashy as you know, you imagined, but it's still very, very impressive. This strategy of generating a whole bunch of things and then selecting, I think has been popularized more and more in recent times. As I said, for example, with systems like Dali, we've seen that generative models can be used to generate very diverse sets of outputs. If they are post processed correctly, we can end up with something that the generative model by itself could not necessarily have done. Right? This is the base of the system. Now, as I already said, there are a lot of engineering things right here. Most notably, if you are going to sample such a large amount of things, in order to answer a single data point, sampling needs to be very, very fast. And a lot of their engineering choices are in order to make sampling fast. For example, as you can see, their encoders are consistently smaller than their decoders. They have shallow encoders, but deep decoders. Precisely for that reason, making the encoder more shallow saves on parameters saves on forward propagation makes sampling a lot faster. Hey, this is Janek from the future, just a small correction right here. I claimed that the shallowness of the encoder would help with the sampling speed, which is not entirely true. In fact, in sampling, the decoder is the bottleneck because you can reuse the encoders encoding over and over again as you auto aggressively sample. So the decoder being small would help the sampling speed, but they figured that the decoder really needs to be deep in order to keep up performance. The encoder being shallow helps really during training because during training, I don't do anything auto aggressively, and therefore any part being smaller really helps the speed during training. So just small correction back to the video. They also use the shared the user and a user a system like a transformer variant that shares all of the values and keys across the heads. As you can see right here, for example, here we have six query heads, but all of the keys and values are shared among those heads. This again saves computation and make sampling a lot faster. So that is that is how they make this sampling even tractable, right? Because these choices influence how many solutions you can generate at once. And yeah, that's they already say it's a massive, it's a massive effort to generate these solutions at runtime. Although I wonder like, what does that mean? Like a couple of seconds or or what? Because humans are time limited in these challenges. And that's one of the major obstacles is that you're under time pressure as a human. So I wonder how that kind of plays into into codecs right here. What do they mean by, you know, it's a lot of effort to generate these things and how much time does it actually take? In any case, they have a lots of intricacies right here. For example, they add additional meta information to the problem description. So they feed this stuff here into the problem description as well. For example, what the language is, whether or not, whether or not the solution that the training, so in the training data, they know whether a solution is correct or not. Whether or not it's the correct solution. And for example, and also tags, tags might help you. For example, this is dynamic programming, the implementation, I don't know what implementation tag is. You must implement an actual algorithm instead of just solving a decidability problem, a rating to indicate how hard the problem is. This these things are not known at test time. However, they've discovered that if they include them at training time, it helps a lot. And obviously, at test time, you can just always input correct solution, right? That's how you can let your model train on even incorrect solutions, and still not have the incorrect solutions during training contaminate, like the model trying to produce correct solutions. So there's potentially something that the model can learn from the incorrect solutions. Yeah, at test time, you just always put correct solution. It's a bit pretentious, but you know, it is what it is. And they also discover that by varying the tags right here, obviously, they don't have the tags because they could give a hint and how you solve the problem. But they can just put like random tags there. And that would even increase the diversity of the things they sample. And that's ultimately what they go for right here, a very diverse set of potential solutions that they can then filter down and cluster down. So I thought this was this was quite smart to include sort of data that you only know at training time, and then use that in a creative manner. That's sort of like prompt engineering in GPT-3. But in an automated and planned fashion, right. So they go through a lot of things, right? I don't have no time to go through all of this, but I highly encourage you to read all of it. They have various techniques right here. They do tempering, they do value conditioning that also helps value prediction that also helps this is a little bit like reinforcement learning where you add additional proxy losses in order to make the model understand the problem space better or maybe learn more relevant features. They do reweighting of the gradient with this technique called gold. And yeah, as I can just, if you're interested, this is very, very detailed paper. And I found it also quite easy and straightforward to read. And I hope you have the same experience. As we said, they get to the filtering, and they say filtering removes approximately 99% of model samples, although the exact amount depends on the problem and the model. And filtering can still leave thousands or 10s of thousands of candidate samples for many problems. So that's why they filter them down and after filtering, they use this clustering algorithm, which I've already described. So I won't do that again right here. But now we go into the results already and the results are themselves quite interesting. Not only because of the performance of the model, which is pretty good, at least for some of the models. They train different models right here in different sizes, but also because they do very detailed investigations into what the individual contributions that they introduced brought. So as you can see right here, for example, this metric right here, by the way, 10 at 10k, it means they submit 10 examples at the end. So this is after the whole clustering and so on. And they generate 10,000 candidate solutions. So at that size, if they consult their 9 billion parameter model, you can see they get a pass rate or a solve rate of 22.6% of the validation set examples that they have. If they use their 41 billion parameter model, that increases. And if they additionally use clustering, instead of just randomly sampling 10 examples from the filtered data set, they get 26.2%. You can see right here both size and the additional features that they build in, get them a large gain and this is consistent across all the sizes and so on. And what you can also see is that sampling more distinctly helps. For example, if you go to 100,000 or a million samples, even though you only submit 10 of them at the end, still, if you sample more, all of the models automatically get better, as you can see. Yeah, so that is I think that that is a good a good lesson and an indication of what could be done more in the future to augment our generative models with post processing. So the paper is quite long, it's actually copied again, right here, we'll just jump more into the results section, because there are some other very interesting things. For example, if you look at how the models compare in their size, there's clearly as we already saw, there is an advantage to being larger, which you can see right here, 300 million parameters performing okay, 41 billion parameters performing a lot better. You can see at this point right here, the small model solves not even 20% of problems, the large model solves more than half of the problems more than the small model. You can also see that when they are unrestricted, so unlimited attempts instead of just 10 attempts. So unlimited attempts, we don't need clustering, we don't need filtering, we could filter right because like there's zero chance that a problem that doesn't pass the test inputs will actually pass the server inputs. But no clustering, no selecting, no sub selecting, you can see that the models, they just get better as you sample more, which makes sense, right? This must be a monotonous function as you sample more, your chance of getting some of some solution being correct is like gets more and more. But there are so many programs, like the space of possible programs is so huge, even the space of possible programs in these data sets is like, or that that would confer to these is so large, that is really astonishing to me to see that there is really this this improvement. It's log linear, yes, this is a log scale, but still it seems it seems crazy, that you can actually get a better performance by just you know, sampling more searching through the space more according to the language models. Also notable is that the large models have a bigger slope than the small models. I've overdone it a bit with my drawing right here. But I hope you can still see it. So the large models have better scaling properties with respect to sampling from them, which is also interesting, and will be another, I think, addition to to the common knowledge of how these models like of the scaling laws of these models. So whether you filter them down to 10 problems, which at some point gets you diminishing returns, or whether you not don't filter them, in which case, I don't see any diminishing returns right here, it just kind of speeds up. Again, these are log scales on the bottom. So it seems to concur very well with the scaling laws we have in that in order to get like a linear improvement in performance, you need an exponential improvement in data compute, or in this case, samples. The next thing they so they look at they look at various things right here, like how long they train, obviously, with more training compute, again, our solve rate goes up. Again, this seems to be a log linear relationship, which is also very interesting. And also the the solve rate goes up with more sampling compute, which is kind of the same plot as above. But here it's measured in terms of compute, and not necessarily in terms of of number of samples. Obviously, the larger models, they do take longer time to forward propagate and therefore use more compute. But interestingly, because of their scaling property, you can see that at the beginning, because they take longer, they need more compute to reach the same pass rate or solve rate. However, as you go up with the compute, because of their slope being being higher right here, they eventually will surpass the other models. And even seen from a compute perspective, it will be cheaper to use the larger model than to use the small models for the same performance. Yeah, here, they investigate their decisions with respect to how fast they can sample. You see right here, the alpha code model can sample at 4.74 samples per TPU second. If they were to use a decoder only model, they would be a lot slower, because now obviously the decoder has a bigger length, which means the attention matrix has a bigger, a bigger size, I guess, they also allocate more blocks to the decoder so that the parameters are approximately equal, which then means all in all means that this architecture is in total slower, because it has more connections, it has more blocks. Then they also they test with the regular transformer like standard multi-head attention, and that's just kind of abysmal. So this is due to the fact that they use this shared query attention right here in their architecture and yeah, yes, okay, this is the same encoder decoder split, but they use a different, they don't use the shared query. So that is speed. Now what I also find interesting is the pre-training data set. I'm sorry, we'll go through a lot of results right here, but they're all very interesting. So the pre-training data set used also influences the performance at the end. But as you can see, if they restrict themselves to GitHub, but Python only, instead of GitHub all languages, and all languages mean something like Python and C++ and Julia and things like this, but it's still programming languages. So if they use Python only, their solve rate drops dramatically. However, if they use Massive Text, and Massive Text does contain some GitHub data, but it's also a natural language data set, it doesn't drop as much. I just I think that's quite interesting. Like why might that be? I don't know. Yeah, here they list up all the advancements and don't want to go through them, but you can just see how just how engineering plays in here. It's not just I have an idea and I build the model. No, no, no. It's, you know, if I just build the model, I get 10.4% right here. But then I add multi, I add the encoder loss of the mask language model, I add the tempering, I add the tags and ratings. So the little snippet they put in front that they randomize at test time, right? I add value predictions, I add this, this weighting of the gradient, I add the clustering, you can see that with everything they add, they get improvement after improvement. So I guess what the lesson here is that there might always be a way to sort of push your system even further by just adding something, something smart, or alternatively just scaling by a factor of 10. But you know, that I guess that's the sad story of deep learning, right? Because these these things, they kind of give you a constant improvement, right? You can see that across all of the things right here. For example, the first the mask language modeling gives you maybe not here, but maybe not here, but here, like a 2%. This is about 2%. This is about 2% improvement. And you know, some of these things, they scale with size, but some of them also kind of give you a constant improvement. And the you can always get the same improvement by just scaling up models, right? In fact, you look at you have to get all of these improvements right here. Or you just scale up the model by a factor of 10, and you get like also an improvement. Sad story of deep learning. Yeah, this right here is a comparison of this is a comparison of the filtering and clustering algorithms. So if they just do no filtering, they just select 10 outputs at random, obviously, their solve rate is just zero, because they generate, like most of the generated samples, they are just garbage, they don't, well, they don't solve the problem. So if they now filter that already gives the biggest boost, right, that eliminates the 99%, that fail on the test inputs. And therefore, that is that is pretty, pretty significant improvement. If they also add clustering, then as you can see, especially at the larger sample budgets, the clustering helps a lot. And the blue line here is a theoretical upper bound. So the blue line is where they just submit every single thing that they sample, and see how much that would solve. So this is theoretical upper bound, if they could always sample and select, not sample the correct, but if they could always select the correct things from the things they sampled, you can see that there is still a big gap. So even though they do this whole clustering thing, they seem to be still unable in, let's say about 10%, or so about 10 percentage points or so of solutions to actually come up with the to select the correct solution among all of their candidates, which is surprising, right? Maybe not. Maybe not. I mean, yeah, I don't know. They do test against baselines. And I guess the only thing to be said is that the baselines, they sometimes succeed on easy problems. I'm sure that in the introductory problems, something like codex doesn't perform too poorly. However, as soon as you go to like competition level problems, and this is a different data set right here in different methodologies in order to make the models comparable, and their alpha code just outshines its competitors quite a bit. And this is the one billion model. This is not even the larger model. They do compare whether or not the model just copies over code. And they have a lot of ways to investigate that. And they find that largely no, it doesn't copy more code than humans copy. Therefore, so also humans in these competitions, they have some algorithm in mind that they've seen somewhere, they just write it down again, or they even actively copy from other solutions. They do investigate quantitatively and qualitatively that right here. And they find that the model largely does not copy over entire solutions from somewhere else. Like, it doesn't just try out all the things that it has seen so far. There are other tricks right here. Sorry, there are also ablations, which I this video is already too long. So I don't want to necessarily go into it into all of the things. One interesting thing is that the report that their validation loss after a very short time increases. So you can see right here, the validation loss drops. And after a while, it increases again, this would indicate overfitting usually, and you can see that for the rest of the run, the validation loss increases. However, their real metric, the true metric, the solve rate actually increases to throughout you can see right here, the solve rate increasing throughout the run, there's diminishing returns, but it does continue to increase, which means that the validation loss is not necessarily a good metric. And I do have an explanation for this, namely, that these coding models, there's not one correct solution, not even in the data set, right, the data set contains many instances of problem A, and then solution one, solution two, solution three, solution four. So if the model learn to produce solution one for problem A, which is a correct solution, but the current data point wants the model to produce solution to write, because you're doing language modeling, you need to select one that you train on, then that would technically, you know, be wrong. And therefore, if you measure this on the validation set, you might, you might, you know, you might actually get worse. Yet still, you might actually increase in your ability to solve the actual problems. This leads me to believe a little bit that, you know, is the training loss even appropriate for this for this thing? I mean, it's fine, you know, the validation loss goes up, I can understand why and why that's might not be necessarily a problem. But is does that kind of mean that the training loss itself should be rethought? And that we should have a better training loss for these types of models where multiple continuations, multiple solutions exist in the data set to the same prefix? I don't know. That is one of many questions that I have right here. As I said, there's lots of other stuff, they augment the data set with some some fuzzing procedure. They, they do lots, lots of different things and investigations. The paper also has a long appendix. If you're if you're into that, you can see a lot more stuff, a lot more analysis. But I think I'm going to leave it here and jump over to the interview. Thanks so much. And I hope you enjoy that as well.
[{"start": 0.0, "end": 11.32, "text": " AlphaCode is a system by DeepMind that does automated competitive programming."}, {"start": 11.32, "end": 16.080000000000002, "text": " You're able to give this system a lead code style problem in natural language and it will"}, {"start": 16.080000000000002, "end": 20.16, "text": " come up with code by itself that solves the problem."}, {"start": 20.16, "end": 25.28, "text": " It does this by using a combination of language modeling, sampling, filtering and clustering"}, {"start": 25.28, "end": 30.840000000000003, "text": " before it finally decides on the solutions that it's going to try out to submit to the"}, {"start": 30.840000000000003, "end": 31.840000000000003, "text": " server."}, {"start": 31.840000000000003, "end": 37.56, "text": " What is mind blowing is that this system was able to perform in human competitions and"}, {"start": 37.56, "end": 43.88, "text": " be about as good as the average programmer in these competitions, which is crazy because"}, {"start": 43.88, "end": 47.24, "text": " previous systems were nowhere near human level."}, {"start": 47.24, "end": 48.58, "text": " So here's how it goes."}, {"start": 48.58, "end": 53.82, "text": " This video right here is a comprehensive paper review where I will go through the paper with"}, {"start": 53.82, "end": 59.88, "text": " you and explain to you the most important parts of the paper, what's in there and what"}, {"start": 59.88, "end": 62.6, "text": " I think is good and what I think is bad."}, {"start": 62.6, "end": 67.46000000000001, "text": " After this video, you'll have a good understanding of the paper and of how the system works and"}, {"start": 67.46000000000001, "end": 69.64, "text": " what its potential weaknesses are."}, {"start": 69.64, "end": 75.9, "text": " However, in the next video released tomorrow, I will interview the authors of AlphaCode,"}, {"start": 75.9, "end": 80.52, "text": " which is a huge privilege and I'll be able to ask them anything I want and they will"}, {"start": 80.52, "end": 86.11999999999999, "text": " have seen my paper review and they'll be directly able to respond to any criticism that I've"}, {"start": 86.11999999999999, "end": 92.16, "text": " raised there to any questions that I had and to whatever I did wrong in my paper review."}, {"start": 92.16, "end": 96.64, "text": " On top of that, you're able to get a behind the scenes look into their work."}, {"start": 96.64, "end": 100.6, "text": " Even at places like DeepMind, things go wrong, things don't work out."}, {"start": 100.6, "end": 105.56, "text": " They've had results that they thought were too good to be true and they turned out not"}, {"start": 105.56, "end": 108.22, "text": " to be true and many more things."}, {"start": 108.22, "end": 113.16, "text": " On top of that, we talked about how the project came to be and also how they've dealt with"}, {"start": 113.16, "end": 116.96, "text": " media reception because this paper has made big waves."}, {"start": 116.96, "end": 122.1, "text": " So I absolutely invite you to watch both this video and the interview part because they're"}, {"start": 122.1, "end": 124.1, "text": " very much complimentary."}, {"start": 124.1, "end": 126.5, "text": " Let me know how I can improve these videos for you."}, {"start": 126.5, "end": 131.28, "text": " If you like, leave a like, tell someone to subscribe and I'll see you around."}, {"start": 131.28, "end": 132.28, "text": " Bye."}, {"start": 132.28, "end": 133.28, "text": " Hello there."}, {"start": 133.28, "end": 137.6, "text": " Today we're going to look at competition level code generation with AlphaCode."}, {"start": 137.6, "end": 143.72, "text": " This is by researchers of DeepMind and presents a novel system that can take part in competitive"}, {"start": 143.72, "end": 145.68, "text": " programming challenges."}, {"start": 145.68, "end": 151.07999999999998, "text": " These are challenges where you as a user you'd register and then you'd be given lead code"}, {"start": 151.07999999999998, "end": 155.12, "text": " style problems to solve and these aren't easy problems."}, {"start": 155.12, "end": 159.16, "text": " These aren't just solving some or writing down some SQL statement."}, {"start": 159.16, "end": 165.74, "text": " These are legitimate, difficult programming challenges where you need to think of algorithms"}, {"start": 165.74, "end": 168.68, "text": " and solutions to problems and so on."}, {"start": 168.68, "end": 176.12, "text": " So having a system that can actually take part and compete against humans is very remarkable."}, {"start": 176.12, "end": 179.48000000000002, "text": " They've submitted this system to 10 of these challenges."}, {"start": 179.48000000000002, "end": 184.04000000000002, "text": " And as you can see, the orange lines here is AlphaCode's relation to other humans."}, {"start": 184.04000000000002, "end": 192.48000000000002, "text": " They perform about as well as a median human would like an average middle of the road competitive"}, {"start": 192.48000000000002, "end": 193.98000000000002, "text": " programmer, if you will."}, {"start": 193.98, "end": 200.06, "text": " So this is pretty remarkable, especially since the baseline system so far had been sort of"}, {"start": 200.06, "end": 204.88, "text": " in the third or fourth percentile, not very good."}, {"start": 204.88, "end": 209.23999999999998, "text": " So this represents a significant boost."}, {"start": 209.23999999999998, "end": 211.72, "text": " And today we're going to find out how they did it."}, {"start": 211.72, "end": 215.64, "text": " But first, here is what such a problem might look like."}, {"start": 215.64, "end": 217.6, "text": " So this is one problem."}, {"start": 217.6, "end": 224.44, "text": " This is one data point in this in this data set or one such challenge that you have to"}, {"start": 224.44, "end": 225.44, "text": " solve."}, {"start": 225.44, "end": 228.04, "text": " You can see it starts with a description."}, {"start": 228.04, "end": 230.04, "text": " So the title is Backspace."}, {"start": 230.04, "end": 231.48, "text": " It starts with a description."}, {"start": 231.48, "end": 237.28, "text": " You're given two strings, S and T, both consisting of lowercase English letters, yada, yada,"}, {"start": 237.28, "end": 238.28, "text": " yada."}, {"start": 238.28, "end": 243.12, "text": " What you should note right here is that the description is in natural language."}, {"start": 243.12, "end": 247.4, "text": " It's made for humans and therefore it's just natural that it is a natural language."}, {"start": 247.4, "end": 248.54, "text": " There is no other form."}, {"start": 248.54, "end": 250.96, "text": " There's no machine readable form right here."}, {"start": 250.96, "end": 252.48000000000002, "text": " This is it."}, {"start": 252.48000000000002, "end": 257.78000000000003, "text": " This is what the algorithm alpha code sees and gets as an input."}, {"start": 257.78000000000003, "end": 261.44, "text": " There's also a description of the input again in natural language."}, {"start": 261.44, "end": 264.44, "text": " There's description of the output."}, {"start": 264.44, "end": 267.48, "text": " And there is also this part right here."}, {"start": 267.48, "end": 269.28000000000003, "text": " This is an important part."}, {"start": 269.28000000000003, "end": 273.16, "text": " It consists of a bunch of example inputs and outputs."}, {"start": 273.16, "end": 275.44, "text": " So here is an example input."}, {"start": 275.44, "end": 278.86, "text": " For example, there are four problems in this problem set."}, {"start": 278.86, "end": 281.84, "text": " All of this will be described in the input section."}, {"start": 281.84, "end": 285.64, "text": " So the input section here says the first line is a single integer, the number of test cases"}, {"start": 285.64, "end": 286.64, "text": " and so on."}, {"start": 286.64, "end": 288.76, "text": " So that's the four."}, {"start": 288.76, "end": 290.74, "text": " Then we have this is a problem."}, {"start": 290.74, "end": 293.94, "text": " So this is S and this is T of the first problem."}, {"start": 293.94, "end": 301.36, "text": " The goal is to type S and strategically type the backspace button instead of the letter"}, {"start": 301.36, "end": 305.15999999999997, "text": " at S to go from S to T."}, {"start": 305.16, "end": 311.56, "text": " So in this case, we start with S. So the first letter is A, but we choose to type the backspace"}, {"start": 311.56, "end": 316.72, "text": " button, which would not type A and would delete what we have, but we have nothing."}, {"start": 316.72, "end": 321.24, "text": " So yeah, then we would type B. Sorry about that."}, {"start": 321.24, "end": 327.8, "text": " And we would type B. Then we would type A, then we would type B. And instead of the last"}, {"start": 327.8, "end": 332.0, "text": " A, we get again type the backspace button, which would delete the letter before it."}, {"start": 332.0, "end": 333.48, "text": " And we'd end up with B, A."}, {"start": 333.48, "end": 340.8, "text": " Therefore, we got from S to T. And therefore we output the letter the word Yes."}, {"start": 340.8, "end": 347.76, "text": " So we are tasked with writing an algorithm that automatically determines whether it's"}, {"start": 347.76, "end": 356.88, "text": " possible to go from S to T in any of these test cases, and output the corresponding answer."}, {"start": 356.88, "end": 362.52000000000004, "text": " This is challenging by itself, but you only get the problem right, if you can do it for"}, {"start": 362.52, "end": 364.56, "text": " all the test cases."}, {"start": 364.56, "end": 369.76, "text": " And the way these problems are evaluated is that on the on the test server, they have"}, {"start": 369.76, "end": 376.76, "text": " a whole bunch more of these test cases, and including checking all the corner cases like"}, {"start": 376.76, "end": 383.65999999999997, "text": " very long inputs, no input at all, only inputs containing the letter A. If for some reason"}, {"start": 383.65999999999997, "end": 386.15999999999997, "text": " you expected a B to be there."}, {"start": 386.15999999999997, "end": 391.96, "text": " And so they test all the edge cases, and you need to be correct in all of them in order"}, {"start": 391.96, "end": 394.4, "text": " to get the points."}, {"start": 394.4, "end": 401.76, "text": " This is extremely challenging even for a human, the output that you're supposed to give is"}, {"start": 401.76, "end": 404.88, "text": " an algorithm like this, you can see it's not an easy thing."}, {"start": 404.88, "end": 409.59999999999997, "text": " It's not just a snippet, it's a full blown algorithm, it contains input."}, {"start": 409.59999999999997, "end": 416.47999999999996, "text": " So you read, you read the inputs, even that to program an algorithm to come up with that"}, {"start": 416.48, "end": 423.04, "text": " piece of code is already challenging by itself to firstly read that first, let the first"}, {"start": 423.04, "end": 429.40000000000003, "text": " line and then read as many inputs, then you need to build lists and reverse lists, and"}, {"start": 429.40000000000003, "end": 434.68, "text": " you go into a while loop where you pop off things of list depending on comparisons."}, {"start": 434.68, "end": 442.32, "text": " And in the end, you output the correct thing depending on whether that list is zero, or"}, {"start": 442.32, "end": 443.98, "text": " empty or not empty."}, {"start": 443.98, "end": 449.6, "text": " So as you can see, this is this is a challenging, challenging task."}, {"start": 449.6, "end": 451.36, "text": " And this is just one data point."}, {"start": 451.36, "end": 456.16, "text": " The next data point isn't going to be another variant on two strings and and typing the"}, {"start": 456.16, "end": 457.52000000000004, "text": " backspace button."}, {"start": 457.52000000000004, "end": 461.52000000000004, "text": " The next data point is going to be a completely different problem, right?"}, {"start": 461.52000000000004, "end": 470.36, "text": " Like searching for shortest paths and some graph or something with denominators of numbers"}, {"start": 470.36, "end": 473.96000000000004, "text": " or numerators or, or something like this, right?"}, {"start": 473.96000000000004, "end": 479.48, "text": " It is, it is very diverse set of problems and very challenging even for humans."}, {"start": 479.48, "end": 484.2, "text": " And the fact that an algorithm can tackle it is very remarkable."}, {"start": 484.2, "end": 488.2, "text": " So how do they do it?"}, {"start": 488.2, "end": 489.24, "text": " That's that's our question today."}, {"start": 489.24, "end": 495.72, "text": " If you guessed that it has something to do with large language models, then and transformers"}, {"start": 495.72, "end": 501.26000000000005, "text": " and so on, then yes, you know, kudos, you got it."}, {"start": 501.26000000000005, "end": 504.68, "text": " But there is a lot more to it."}, {"start": 504.68, "end": 508.12, "text": " And this is really an engineering effort."}, {"start": 508.12, "end": 513.5600000000001, "text": " And I think we should appreciate just, you know, how far you can push a system to get"}, {"start": 513.5600000000001, "end": 515.84, "text": " continuous improvements."}, {"start": 515.84, "end": 520.6, "text": " What they do first, though, is they collect a data set."}, {"start": 520.6, "end": 526.1, "text": " They do train on a open source code from GitHub."}, {"start": 526.1, "end": 528.0400000000001, "text": " That is the pre training data set."}, {"start": 528.0400000000001, "end": 530.82, "text": " This is very similar to open AI codex model."}, {"start": 530.82, "end": 535.48, "text": " So open as codex model is trained on code from GitHub."}, {"start": 535.48, "end": 539.76, "text": " And you can simply do next token prediction on code."}, {"start": 539.76, "end": 544.2, "text": " And I have to say I've tried codex and I'm pretty happy with its suggestions is very"}, {"start": 544.2, "end": 545.96, "text": " good."}, {"start": 545.96, "end": 550.5, "text": " But it can give me like longer snippets than an auto complete."}, {"start": 550.5, "end": 555.6600000000001, "text": " But it cannot like solve any kind of problems like this, it can just continue code."}, {"start": 555.6600000000001, "end": 562.0600000000001, "text": " In any case, they collect this pre training data set, they have whatever 700 gigabytes"}, {"start": 562.0600000000001, "end": 564.72, "text": " of code that they train on."}, {"start": 564.72, "end": 571.76, "text": " And they do run their regular language modeling objective on that piece of code."}, {"start": 571.76, "end": 577.04, "text": " Then they fine tune on an appropriate data set of code contests."}, {"start": 577.04, "end": 581.52, "text": " So this is a mixture data set that they scrape from multiple websites, for example, code"}, {"start": 581.52, "end": 590.08, "text": " forces description to code, code net, these are these are papers, previous papers, or"}, {"start": 590.08, "end": 597.86, "text": " competition settings that they have collected these data sets from and the data sets again,"}, {"start": 597.86, "end": 600.68, "text": " this here is one data point, right?"}, {"start": 600.68, "end": 602.64, "text": " This is a problem description."}, {"start": 602.64, "end": 609.7399999999999, "text": " And usually these, these data sets, they contain one or multiple solutions, not all of them"}, {"start": 609.7399999999999, "end": 611.1999999999999, "text": " might be correct."}, {"start": 611.1999999999999, "end": 618.3199999999999, "text": " But they contain about an order of magnitude more solutions than they contain texts or"}, {"start": 618.3199999999999, "end": 620.8199999999999, "text": " problem descriptions."}, {"start": 620.8199999999999, "end": 626.12, "text": " So first, they collect a data set, and then they train on that data set."}, {"start": 626.12, "end": 631.44, "text": " So that could be the story right here, but it is not."}, {"start": 631.44, "end": 635.74, "text": " The entire pipeline is a bit more complicated."}, {"start": 635.74, "end": 641.7, "text": " You can see first, there's GitHub, we collect pre training data, we do pre training, then"}, {"start": 641.7, "end": 648.32, "text": " fine tuning on pairs of problems and solutions of these code contests data set."}, {"start": 648.32, "end": 653.7, "text": " This is as I said, a collection of various data sets that contain these that contain"}, {"start": 653.7, "end": 661.0200000000001, "text": " these code challenge type of problems, lead code style problems, and they do fine tuning."}, {"start": 661.0200000000001, "end": 667.1400000000001, "text": " By the way, their model is a transformer model, you could guess it, they do have a special"}, {"start": 667.1400000000001, "end": 669.34, "text": " they have an encoder decoder model."}, {"start": 669.34, "end": 674.46, "text": " So you have some sort of an encoder, and they choose to make the encoder shallow and the"}, {"start": 674.46, "end": 678.5, "text": " decoder, the decoder deep."}, {"start": 678.5, "end": 682.1800000000001, "text": " And there are specific reasons for that, which we'll get to in a second."}, {"start": 682.18, "end": 689.4599999999999, "text": " But the encoder mainly handles the this description, which is so the description is natural language"}, {"start": 689.4599999999999, "end": 694.06, "text": " mostly contains, you know, some some code snippets and so on."}, {"start": 694.06, "end": 697.66, "text": " However, it contains mostly the description."}, {"start": 697.66, "end": 699.4, "text": " That's the encoder."}, {"start": 699.4, "end": 705.3199999999999, "text": " The benefit of using an encoder decoder architecture over a decoder only is that you do get bi"}, {"start": 705.3199999999999, "end": 708.18, "text": " directionality in the encoder."}, {"start": 708.18, "end": 713.12, "text": " And as they do here, you can make them different sizes, which means that you can shrink the"}, {"start": 713.12, "end": 718.9599999999999, "text": " encoder, which makes you sample able to sample faster and sampling is going to be very important"}, {"start": 718.9599999999999, "end": 722.02, "text": " for the system right here in just a second."}, {"start": 722.02, "end": 729.9, "text": " And then the decoder will be a autoregressive decoder, where they just well int j equals"}, {"start": 729.9, "end": 732.4599999999999, "text": " five, yada yada yada."}, {"start": 732.4599999999999, "end": 737.64, "text": " So this is this is actually going to produce the code token by token in sort of a language"}, {"start": 737.64, "end": 738.98, "text": " modeling way."}, {"start": 738.98, "end": 745.66, "text": " Their objective is is they have a masked language model objective at the encoder."}, {"start": 745.66, "end": 748.9, "text": " And then the decoder obviously there's cross attention right here."}, {"start": 748.9, "end": 753.26, "text": " There's there's self attention in the encoder, there's self attention, causal self attention"}, {"start": 753.26, "end": 754.46, "text": " in the decoder."}, {"start": 754.46, "end": 758.8199999999999, "text": " And then there is cross attention from the decoder to the encoder."}, {"start": 758.8199999999999, "end": 765.14, "text": " And they have a language modeling objective in the decoder."}, {"start": 765.14, "end": 769.9, "text": " And they do say, it's quite important to have the masked language modeling loss additionally"}, {"start": 769.9, "end": 776.66, "text": " in the encoder, because it apparently makes the encoder understand this, the stuff in"}, {"start": 776.66, "end": 780.9, "text": " inside of it, the stuff that it's fed a lot better, I'm just going to believe them right"}, {"start": 780.9, "end": 782.1999999999999, "text": " here."}, {"start": 782.1999999999999, "end": 787.68, "text": " So now that we have this model, we can, we can fine tune it on these data sets, right,"}, {"start": 787.68, "end": 789.92, "text": " we can feed a description right here."}, {"start": 789.92, "end": 795.4599999999999, "text": " And we can feed one of the solutions, and that could already be it."}, {"start": 795.4599999999999, "end": 797.42, "text": " However, that's not it."}, {"start": 797.42, "end": 801.76, "text": " It turns out that most of the time, this doesn't actually solve the problem."}, {"start": 801.76, "end": 808.04, "text": " So you feed in a description, and you sample the solution, it is not it does not go well."}, {"start": 808.04, "end": 809.5799999999999, "text": " So what do they do?"}, {"start": 809.5799999999999, "end": 812.5999999999999, "text": " Well, there are two ways."}, {"start": 812.5999999999999, "end": 817.14, "text": " The first way is you try to make your model a lot better at like thinking and coming up"}, {"start": 817.14, "end": 820.1, "text": " with solutions and reasoning abstractly and so on."}, {"start": 820.1, "end": 826.06, "text": " But that doesn't sound very deep learning and transformer like so what do we do is we"}, {"start": 826.06, "end": 829.68, "text": " just do large scale sampling."}, {"start": 829.68, "end": 834.74, "text": " That essentially means you have a problem, you get a new problem, you feed this into"}, {"start": 834.74, "end": 837.16, "text": " your decoder right here."}, {"start": 837.16, "end": 843.5, "text": " And then you just sample like a bunch of solutions from your decoder."}, {"start": 843.5, "end": 845.7, "text": " Sorry, I just said decoder over here."}, {"start": 845.7, "end": 851.6400000000001, "text": " You store this into the encoder, you let the decoder run, and you generate a ginormous,"}, {"start": 851.6400000000001, "end": 855.34, "text": " a ginormous amount of outputs."}, {"start": 855.34, "end": 861.3000000000001, "text": " So you can do this with language models, you can sample according to some temperature,"}, {"start": 861.3000000000001, "end": 865.38, "text": " you can do some other stuff, you do nuclear sampling and whatnot."}, {"start": 865.38, "end": 870.7800000000001, "text": " But you can generate diverse outputs from the decoder."}, {"start": 870.78, "end": 878.66, "text": " And they do, they sample thousands up to a million different outputs from the decoder."}, {"start": 878.66, "end": 883.8199999999999, "text": " So now they have this large set of potential solutions."}, {"start": 883.8199999999999, "end": 885.56, "text": " And what do they do with it?"}, {"start": 885.56, "end": 889.06, "text": " This is very important, they do filter, and they cluster."}, {"start": 889.06, "end": 892.26, "text": " So first the filtering happens."}, {"start": 892.26, "end": 898.3399999999999, "text": " And it might not surprise you, but the filtering happens on these example inputs that we saw"}, {"start": 898.3399999999999, "end": 899.3399999999999, "text": " right here."}, {"start": 899.34, "end": 905.14, "text": " So for every problem, you get a tiny amount of example inputs and corresponding example"}, {"start": 905.14, "end": 906.14, "text": " outputs."}, {"start": 906.14, "end": 911.5400000000001, "text": " They simply let all of the programs they generate run on these example inputs."}, {"start": 911.5400000000001, "end": 916.76, "text": " And the ones that don't crash, they evaluate whether they do get the example outputs."}, {"start": 916.76, "end": 921.34, "text": " And if they do get the example outputs correctly, they keep them around, otherwise they discard"}, {"start": 921.34, "end": 922.34, "text": " them."}, {"start": 922.34, "end": 926.0400000000001, "text": " This is obviously vastly different from how humans solve these things."}, {"start": 926.04, "end": 931.74, "text": " Humans don't just generate giant amounts of solutions and then let them run on this tiny"}, {"start": 931.74, "end": 933.8199999999999, "text": " amount of example problems."}, {"start": 933.8199999999999, "end": 940.3399999999999, "text": " But this eliminates, as they say, it eliminates over 99% of these sampled things."}, {"start": 940.3399999999999, "end": 950.98, "text": " So you end up with a slice right here of this data that you've generated by simply evaluating"}, {"start": 950.98, "end": 954.38, "text": " on these example cases that you had."}, {"start": 954.38, "end": 958.98, "text": " So it's quite important that these are there for the system to work."}, {"start": 958.98, "end": 966.74, "text": " I wonder if like, we could replace this, because we have this approach as well in for example"}, {"start": 966.74, "end": 971.46, "text": " Dali, where a lot of stuff is generated and then clip is used to rerank."}, {"start": 971.46, "end": 975.54, "text": " I wonder if something like this could be done here."}, {"start": 975.54, "end": 982.98, "text": " But they have several helper models in here in order to help the system during training."}, {"start": 982.98, "end": 992.22, "text": " So I don't know if another helper model might be even appropriate."}, {"start": 992.22, "end": 996.34, "text": " So this leaves them with a tiny amount of solutions, which could still be a lot, right?"}, {"start": 996.34, "end": 1000.1, "text": " 99% out of a million is still a lot of solutions."}, {"start": 1000.1, "end": 1004.04, "text": " And they keep themselves to just submitting 10 of them."}, {"start": 1004.04, "end": 1008.54, "text": " As a human, sometimes these code platforms, they have actually a limit on how many things"}, {"start": 1008.54, "end": 1014.3, "text": " you can try to submit and 10 is like a reasonable limit."}, {"start": 1014.3, "end": 1020.98, "text": " It gives you a little bit of as a human, a little bit of you're not anxious to submit"}, {"start": 1020.98, "end": 1022.3399999999999, "text": " a solution."}, {"start": 1022.3399999999999, "end": 1024.58, "text": " If you think it's the correct one, sorry."}, {"start": 1024.58, "end": 1028.58, "text": " But you also you can submit a few times, but not too often."}, {"start": 1028.58, "end": 1032.3799999999999, "text": " Like you can't brute force the test set that's on the server."}, {"start": 1032.38, "end": 1038.6200000000001, "text": " So they need to get down from these still large amount of solutions to 10 solutions."}, {"start": 1038.6200000000001, "end": 1041.7800000000002, "text": " And that's where this clustering comes in."}, {"start": 1041.7800000000002, "end": 1048.94, "text": " So the goal is to end up with this small select set of candidates to execute and evaluate."}, {"start": 1048.94, "end": 1051.22, "text": " And what do they do with the clustering?"}, {"start": 1051.22, "end": 1053.3400000000001, "text": " This is where one of these helper models gets in."}, {"start": 1053.3400000000001, "end": 1058.5800000000002, "text": " So all of these things right here, they are programs, they're programs that could take"}, {"start": 1058.58, "end": 1063.82, "text": " inputs and outputs, and there are many, many of them."}, {"start": 1063.82, "end": 1069.02, "text": " What we want to do is we want to cluster them, a lot of these programs are going to be different"}, {"start": 1069.02, "end": 1072.6, "text": " in the tokens that they use, like in the exact code, but they're going to be essentially"}, {"start": 1072.6, "end": 1078.6999999999998, "text": " the equivalent program to each other, like they're going to be the same program isomorphic"}, {"start": 1078.6999999999998, "end": 1079.82, "text": " to each other."}, {"start": 1079.82, "end": 1085.1, "text": " However, graph isomorphism, like let's say we parse them in a syntax tree and check graph"}, {"start": 1085.1, "end": 1089.98, "text": " isomorphism, that's, I do believe that's like a really hard problem."}, {"start": 1089.98, "end": 1094.78, "text": " I might be mistaken, but I think that's used in cryptography to show like a really hard"}, {"start": 1094.78, "end": 1095.78, "text": " problem."}, {"start": 1095.78, "end": 1102.34, "text": " So it's not really graph isomorphism on the syntax tree, it might not even get all the"}, {"start": 1102.34, "end": 1104.06, "text": " isomorphic programs."}, {"start": 1104.06, "end": 1105.1799999999998, "text": " So what do we do?"}, {"start": 1105.1799999999998, "end": 1108.98, "text": " Our plan is going to be we want to group these programs into the same one."}, {"start": 1108.98, "end": 1111.5, "text": " So maybe these three here are actually the same."}, {"start": 1111.5, "end": 1113.74, "text": " And this one here is actually the same."}, {"start": 1113.74, "end": 1116.46, "text": " So we'd like to figure that out."}, {"start": 1116.46, "end": 1117.46, "text": " How do we do it?"}, {"start": 1117.46, "end": 1124.66, "text": " We just feed like a whole bunch of inputs, like we just generate a whole bunch of inputs"}, {"start": 1124.66, "end": 1126.6200000000001, "text": " to the programs."}, {"start": 1126.6200000000001, "end": 1134.42, "text": " And this is we train a little model that can take descriptions, like problem descriptions,"}, {"start": 1134.42, "end": 1140.58, "text": " and generate new input output pairs, not even input output pairs, just inputs."}, {"start": 1140.58, "end": 1145.54, "text": " So we take a problem, and we take these example inputs, and it can generate new ones."}, {"start": 1145.54, "end": 1151.22, "text": " Now we don't care what the output is, what we do care is we just feed all of them to"}, {"start": 1151.22, "end": 1156.62, "text": " all of the models, like all of them go to all of the models, and we just observe the"}, {"start": 1156.62, "end": 1157.62, "text": " outputs."}, {"start": 1157.62, "end": 1164.76, "text": " And we say, well, whenever two programs have the same outputs on all of these test cases"}, {"start": 1164.76, "end": 1170.36, "text": " that we came up with, they are the same program, we don't, we don't, again, we don't know the"}, {"start": 1170.36, "end": 1174.4199999999998, "text": " solutions to these inputs, because we made them up."}, {"start": 1174.4199999999998, "end": 1181.1, "text": " But we can assume that if two programs output the same thing for all kinds of inputs, that"}, {"start": 1181.1, "end": 1183.5, "text": " they're essentially the equivalent program."}, {"start": 1183.5, "end": 1189.74, "text": " Note that we can't just input random garbage right here, because the programs might differ"}, {"start": 1189.74, "end": 1192.62, "text": " with respect to how they handle edge cases and so on."}, {"start": 1192.62, "end": 1197.62, "text": " So it is good to have an informed model be the one that's inputting things into these"}, {"start": 1197.62, "end": 1198.62, "text": " models."}, {"start": 1198.62, "end": 1202.6599999999999, "text": " So that lets us figure out groups, let's say, okay, all of these models responded the same"}, {"start": 1202.6599999999999, "end": 1204.78, "text": " to all of these inputs that we gave them."}, {"start": 1204.78, "end": 1210.32, "text": " So we'll just consider that the same program, and we'll just submit one of them as the one"}, {"start": 1210.32, "end": 1211.32, "text": " of the 10."}, {"start": 1211.32, "end": 1215.6599999999999, "text": " And we go to the next bucket, submit one of those, and so on, we start with the largest"}, {"start": 1215.6599999999999, "end": 1219.2399999999998, "text": " bucket, and then we progressively go to the smaller buckets."}, {"start": 1219.2399999999998, "end": 1223.62, "text": " And if we still have some some budget left, we go to the largest bucket again and sample"}, {"start": 1223.62, "end": 1225.3, "text": " a different one."}, {"start": 1225.3, "end": 1229.6, "text": " And that's essentially how we group programs, and that's how they get it down to fairly"}, {"start": 1229.6, "end": 1231.5, "text": " small set of candidates."}, {"start": 1231.5, "end": 1233.58, "text": " Why do they start with the largest bucket?"}, {"start": 1233.58, "end": 1243.52, "text": " Their reasoning is that is that wrong, there are many ways that wrong programs can be wrong."}, {"start": 1243.52, "end": 1251.1399999999999, "text": " So selecting the largest bucket, I don't know, we'll have to read what they're saying."}, {"start": 1251.14, "end": 1258.24, "text": " But essentially, they say there are many ways to introduce bugs, and therefore they expect"}, {"start": 1258.24, "end": 1263.48, "text": " the wrong programs to be in smaller, but distinct buckets."}, {"start": 1263.48, "end": 1264.66, "text": " And that's the system."}, {"start": 1264.66, "end": 1267.8000000000002, "text": " That is how they solve the programming competition."}, {"start": 1267.8000000000002, "end": 1276.0200000000002, "text": " This might not be as flashy as you know, you imagined, but it's still very, very impressive."}, {"start": 1276.02, "end": 1281.34, "text": " This strategy of generating a whole bunch of things and then selecting, I think has"}, {"start": 1281.34, "end": 1286.46, "text": " been popularized more and more in recent times."}, {"start": 1286.46, "end": 1293.62, "text": " As I said, for example, with systems like Dali, we've seen that generative models can"}, {"start": 1293.62, "end": 1296.86, "text": " be used to generate very diverse sets of outputs."}, {"start": 1296.86, "end": 1302.02, "text": " If they are post processed correctly, we can end up with something that the generative"}, {"start": 1302.02, "end": 1306.22, "text": " model by itself could not necessarily have done."}, {"start": 1306.22, "end": 1307.22, "text": " Right?"}, {"start": 1307.22, "end": 1309.66, "text": " This is the base of the system."}, {"start": 1309.66, "end": 1315.84, "text": " Now, as I already said, there are a lot of engineering things right here."}, {"start": 1315.84, "end": 1324.54, "text": " Most notably, if you are going to sample such a large amount of things, in order to answer"}, {"start": 1324.54, "end": 1329.86, "text": " a single data point, sampling needs to be very, very fast."}, {"start": 1329.86, "end": 1333.4599999999998, "text": " And a lot of their engineering choices are in order to make sampling fast."}, {"start": 1333.4599999999998, "end": 1340.26, "text": " For example, as you can see, their encoders are consistently smaller than their decoders."}, {"start": 1340.26, "end": 1344.4599999999998, "text": " They have shallow encoders, but deep decoders."}, {"start": 1344.4599999999998, "end": 1349.34, "text": " Precisely for that reason, making the encoder more shallow saves on parameters saves on"}, {"start": 1349.34, "end": 1352.86, "text": " forward propagation makes sampling a lot faster."}, {"start": 1352.86, "end": 1356.6999999999998, "text": " Hey, this is Janek from the future, just a small correction right here."}, {"start": 1356.7, "end": 1361.6200000000001, "text": " I claimed that the shallowness of the encoder would help with the sampling speed, which"}, {"start": 1361.6200000000001, "end": 1363.22, "text": " is not entirely true."}, {"start": 1363.22, "end": 1369.26, "text": " In fact, in sampling, the decoder is the bottleneck because you can reuse the encoders encoding"}, {"start": 1369.26, "end": 1372.82, "text": " over and over again as you auto aggressively sample."}, {"start": 1372.82, "end": 1377.98, "text": " So the decoder being small would help the sampling speed, but they figured that the"}, {"start": 1377.98, "end": 1383.06, "text": " decoder really needs to be deep in order to keep up performance."}, {"start": 1383.06, "end": 1388.06, "text": " The encoder being shallow helps really during training because during training, I don't"}, {"start": 1388.06, "end": 1393.54, "text": " do anything auto aggressively, and therefore any part being smaller really helps the speed"}, {"start": 1393.54, "end": 1394.7, "text": " during training."}, {"start": 1394.7, "end": 1397.78, "text": " So just small correction back to the video."}, {"start": 1397.78, "end": 1408.58, "text": " They also use the shared the user and a user a system like a transformer variant that shares"}, {"start": 1408.58, "end": 1412.6599999999999, "text": " all of the values and keys across the heads."}, {"start": 1412.66, "end": 1418.42, "text": " As you can see right here, for example, here we have six query heads, but all of the keys"}, {"start": 1418.42, "end": 1421.42, "text": " and values are shared among those heads."}, {"start": 1421.42, "end": 1427.8600000000001, "text": " This again saves computation and make sampling a lot faster."}, {"start": 1427.8600000000001, "end": 1433.78, "text": " So that is that is how they make this sampling even tractable, right?"}, {"start": 1433.78, "end": 1439.66, "text": " Because these choices influence how many solutions you can generate at once."}, {"start": 1439.66, "end": 1446.0800000000002, "text": " And yeah, that's they already say it's a massive, it's a massive effort to generate these solutions"}, {"start": 1446.0800000000002, "end": 1447.26, "text": " at runtime."}, {"start": 1447.26, "end": 1449.42, "text": " Although I wonder like, what does that mean?"}, {"start": 1449.42, "end": 1452.1000000000001, "text": " Like a couple of seconds or or what?"}, {"start": 1452.1000000000001, "end": 1455.5800000000002, "text": " Because humans are time limited in these challenges."}, {"start": 1455.5800000000002, "end": 1462.74, "text": " And that's one of the major obstacles is that you're under time pressure as a human."}, {"start": 1462.74, "end": 1466.42, "text": " So I wonder how that kind of plays into into codecs right here."}, {"start": 1466.42, "end": 1470.54, "text": " What do they mean by, you know, it's a lot of effort to generate these things and how"}, {"start": 1470.54, "end": 1472.5800000000002, "text": " much time does it actually take?"}, {"start": 1472.5800000000002, "end": 1478.26, "text": " In any case, they have a lots of intricacies right here."}, {"start": 1478.26, "end": 1484.5, "text": " For example, they add additional meta information to the problem description."}, {"start": 1484.5, "end": 1489.74, "text": " So they feed this stuff here into the problem description as well."}, {"start": 1489.74, "end": 1496.58, "text": " For example, what the language is, whether or not, whether or not the solution that the"}, {"start": 1496.58, "end": 1502.26, "text": " training, so in the training data, they know whether a solution is correct or not."}, {"start": 1502.26, "end": 1504.9, "text": " Whether or not it's the correct solution."}, {"start": 1504.9, "end": 1509.7, "text": " And for example, and also tags, tags might help you."}, {"start": 1509.7, "end": 1515.3, "text": " For example, this is dynamic programming, the implementation, I don't know what implementation"}, {"start": 1515.3, "end": 1516.3, "text": " tag is."}, {"start": 1516.3, "end": 1521.62, "text": " You must implement an actual algorithm instead of just solving a decidability problem, a"}, {"start": 1521.62, "end": 1524.5, "text": " rating to indicate how hard the problem is."}, {"start": 1524.5, "end": 1528.7, "text": " This these things are not known at test time."}, {"start": 1528.7, "end": 1534.52, "text": " However, they've discovered that if they include them at training time, it helps a lot."}, {"start": 1534.52, "end": 1539.04, "text": " And obviously, at test time, you can just always input correct solution, right?"}, {"start": 1539.04, "end": 1544.3, "text": " That's how you can let your model train on even incorrect solutions, and still not have"}, {"start": 1544.3, "end": 1551.34, "text": " the incorrect solutions during training contaminate, like the model trying to produce correct solutions."}, {"start": 1551.34, "end": 1555.26, "text": " So there's potentially something that the model can learn from the incorrect solutions."}, {"start": 1555.26, "end": 1558.1399999999999, "text": " Yeah, at test time, you just always put correct solution."}, {"start": 1558.1399999999999, "end": 1563.06, "text": " It's a bit pretentious, but you know, it is what it is."}, {"start": 1563.06, "end": 1568.8999999999999, "text": " And they also discover that by varying the tags right here, obviously, they don't have"}, {"start": 1568.8999999999999, "end": 1573.36, "text": " the tags because they could give a hint and how you solve the problem."}, {"start": 1573.36, "end": 1576.6599999999999, "text": " But they can just put like random tags there."}, {"start": 1576.6599999999999, "end": 1580.78, "text": " And that would even increase the diversity of the things they sample."}, {"start": 1580.78, "end": 1586.9199999999998, "text": " And that's ultimately what they go for right here, a very diverse set of potential solutions"}, {"start": 1586.9199999999998, "end": 1590.1599999999999, "text": " that they can then filter down and cluster down."}, {"start": 1590.1599999999999, "end": 1596.58, "text": " So I thought this was this was quite smart to include sort of data that you only know"}, {"start": 1596.58, "end": 1601.1599999999999, "text": " at training time, and then use that in a creative manner."}, {"start": 1601.16, "end": 1605.42, "text": " That's sort of like prompt engineering in GPT-3."}, {"start": 1605.42, "end": 1610.3400000000001, "text": " But in an automated and planned fashion, right."}, {"start": 1610.3400000000001, "end": 1612.5, "text": " So they go through a lot of things, right?"}, {"start": 1612.5, "end": 1617.76, "text": " I don't have no time to go through all of this, but I highly encourage you to read all"}, {"start": 1617.76, "end": 1618.76, "text": " of it."}, {"start": 1618.76, "end": 1621.48, "text": " They have various techniques right here."}, {"start": 1621.48, "end": 1626.8400000000001, "text": " They do tempering, they do value conditioning that also helps value prediction that also"}, {"start": 1626.84, "end": 1632.3799999999999, "text": " helps this is a little bit like reinforcement learning where you add additional proxy losses"}, {"start": 1632.3799999999999, "end": 1638.1799999999998, "text": " in order to make the model understand the problem space better or maybe learn more relevant"}, {"start": 1638.1799999999998, "end": 1639.5, "text": " features."}, {"start": 1639.5, "end": 1645.4599999999998, "text": " They do reweighting of the gradient with this technique called gold."}, {"start": 1645.4599999999998, "end": 1655.1, "text": " And yeah, as I can just, if you're interested, this is very, very detailed paper."}, {"start": 1655.1, "end": 1659.2199999999998, "text": " And I found it also quite easy and straightforward to read."}, {"start": 1659.2199999999998, "end": 1662.8799999999999, "text": " And I hope you have the same experience."}, {"start": 1662.8799999999999, "end": 1668.54, "text": " As we said, they get to the filtering, and they say filtering removes approximately 99%"}, {"start": 1668.54, "end": 1674.4399999999998, "text": " of model samples, although the exact amount depends on the problem and the model."}, {"start": 1674.4399999999998, "end": 1679.26, "text": " And filtering can still leave thousands or 10s of thousands of candidate samples for"}, {"start": 1679.26, "end": 1683.6599999999999, "text": " many problems."}, {"start": 1683.66, "end": 1690.7, "text": " So that's why they filter them down and after filtering, they use this clustering algorithm,"}, {"start": 1690.7, "end": 1691.7, "text": " which I've already described."}, {"start": 1691.7, "end": 1695.42, "text": " So I won't do that again right here."}, {"start": 1695.42, "end": 1702.8200000000002, "text": " But now we go into the results already and the results are themselves quite interesting."}, {"start": 1702.8200000000002, "end": 1709.14, "text": " Not only because of the performance of the model, which is pretty good, at least for"}, {"start": 1709.14, "end": 1710.14, "text": " some of the models."}, {"start": 1710.14, "end": 1714.3000000000002, "text": " They train different models right here in different sizes, but also because they do"}, {"start": 1714.3000000000002, "end": 1721.3400000000001, "text": " very detailed investigations into what the individual contributions that they introduced"}, {"start": 1721.3400000000001, "end": 1722.3400000000001, "text": " brought."}, {"start": 1722.3400000000001, "end": 1728.1000000000001, "text": " So as you can see right here, for example, this metric right here, by the way, 10 at"}, {"start": 1728.1000000000001, "end": 1732.5400000000002, "text": " 10k, it means they submit 10 examples at the end."}, {"start": 1732.5400000000002, "end": 1736.3400000000001, "text": " So this is after the whole clustering and so on."}, {"start": 1736.3400000000001, "end": 1740.0800000000002, "text": " And they generate 10,000 candidate solutions."}, {"start": 1740.08, "end": 1747.3799999999999, "text": " So at that size, if they consult their 9 billion parameter model, you can see they get a pass"}, {"start": 1747.3799999999999, "end": 1754.74, "text": " rate or a solve rate of 22.6% of the validation set examples that they have."}, {"start": 1754.74, "end": 1759.9199999999998, "text": " If they use their 41 billion parameter model, that increases."}, {"start": 1759.9199999999998, "end": 1765.1399999999999, "text": " And if they additionally use clustering, instead of just randomly sampling 10 examples from"}, {"start": 1765.14, "end": 1770.14, "text": " the filtered data set, they get 26.2%."}, {"start": 1770.14, "end": 1775.7800000000002, "text": " You can see right here both size and the additional features that they build in, get them a large"}, {"start": 1775.7800000000002, "end": 1780.0, "text": " gain and this is consistent across all the sizes and so on."}, {"start": 1780.0, "end": 1784.5, "text": " And what you can also see is that sampling more distinctly helps."}, {"start": 1784.5, "end": 1790.74, "text": " For example, if you go to 100,000 or a million samples, even though you only submit 10 of"}, {"start": 1790.74, "end": 1799.38, "text": " them at the end, still, if you sample more, all of the models automatically get better,"}, {"start": 1799.38, "end": 1801.26, "text": " as you can see."}, {"start": 1801.26, "end": 1807.78, "text": " Yeah, so that is I think that that is a good a good lesson and an indication of what could"}, {"start": 1807.78, "end": 1814.6200000000001, "text": " be done more in the future to augment our generative models with post processing."}, {"start": 1814.6200000000001, "end": 1820.3, "text": " So the paper is quite long, it's actually copied again, right here, we'll just jump"}, {"start": 1820.3, "end": 1828.1399999999999, "text": " more into the results section, because there are some other very interesting things."}, {"start": 1828.1399999999999, "end": 1835.62, "text": " For example, if you look at how the models compare in their size, there's clearly as"}, {"start": 1835.62, "end": 1841.18, "text": " we already saw, there is an advantage to being larger, which you can see right here, 300"}, {"start": 1841.18, "end": 1847.86, "text": " million parameters performing okay, 41 billion parameters performing a lot better."}, {"start": 1847.86, "end": 1855.32, "text": " You can see at this point right here, the small model solves not even 20% of problems,"}, {"start": 1855.32, "end": 1861.74, "text": " the large model solves more than half of the problems more than the small model."}, {"start": 1861.74, "end": 1868.2199999999998, "text": " You can also see that when they are unrestricted, so unlimited attempts instead of just 10 attempts."}, {"start": 1868.2199999999998, "end": 1873.6399999999999, "text": " So unlimited attempts, we don't need clustering, we don't need filtering, we could filter right"}, {"start": 1873.64, "end": 1879.0600000000002, "text": " because like there's zero chance that a problem that doesn't pass the test inputs will actually"}, {"start": 1879.0600000000002, "end": 1882.42, "text": " pass the server inputs."}, {"start": 1882.42, "end": 1889.8200000000002, "text": " But no clustering, no selecting, no sub selecting, you can see that the models, they just get"}, {"start": 1889.8200000000002, "end": 1894.48, "text": " better as you sample more, which makes sense, right?"}, {"start": 1894.48, "end": 1899.76, "text": " This must be a monotonous function as you sample more, your chance of getting some of"}, {"start": 1899.76, "end": 1904.22, "text": " some solution being correct is like gets more and more."}, {"start": 1904.22, "end": 1910.84, "text": " But there are so many programs, like the space of possible programs is so huge, even the"}, {"start": 1910.84, "end": 1917.3, "text": " space of possible programs in these data sets is like, or that that would confer to these"}, {"start": 1917.3, "end": 1925.66, "text": " is so large, that is really astonishing to me to see that there is really this this improvement."}, {"start": 1925.66, "end": 1933.42, "text": " It's log linear, yes, this is a log scale, but still it seems it seems crazy, that you"}, {"start": 1933.42, "end": 1938.26, "text": " can actually get a better performance by just you know, sampling more searching through"}, {"start": 1938.26, "end": 1940.98, "text": " the space more according to the language models."}, {"start": 1940.98, "end": 1945.96, "text": " Also notable is that the large models have a bigger slope than the small models."}, {"start": 1945.96, "end": 1948.68, "text": " I've overdone it a bit with my drawing right here."}, {"start": 1948.68, "end": 1950.68, "text": " But I hope you can still see it."}, {"start": 1950.68, "end": 1958.22, "text": " So the large models have better scaling properties with respect to sampling from them, which"}, {"start": 1958.22, "end": 1964.5600000000002, "text": " is also interesting, and will be another, I think, addition to to the common knowledge"}, {"start": 1964.5600000000002, "end": 1968.6200000000001, "text": " of how these models like of the scaling laws of these models."}, {"start": 1968.6200000000001, "end": 1975.5, "text": " So whether you filter them down to 10 problems, which at some point gets you diminishing returns,"}, {"start": 1975.5, "end": 1980.1000000000001, "text": " or whether you not don't filter them, in which case, I don't see any diminishing returns"}, {"start": 1980.1, "end": 1982.86, "text": " right here, it just kind of speeds up."}, {"start": 1982.86, "end": 1986.04, "text": " Again, these are log scales on the bottom."}, {"start": 1986.04, "end": 1992.9399999999998, "text": " So it seems to concur very well with the scaling laws we have in that in order to get like"}, {"start": 1992.9399999999998, "end": 1999.02, "text": " a linear improvement in performance, you need an exponential improvement in data compute,"}, {"start": 1999.02, "end": 2002.6399999999999, "text": " or in this case, samples."}, {"start": 2002.6399999999999, "end": 2008.12, "text": " The next thing they so they look at they look at various things right here, like how long"}, {"start": 2008.12, "end": 2014.6599999999999, "text": " they train, obviously, with more training compute, again, our solve rate goes up."}, {"start": 2014.6599999999999, "end": 2021.52, "text": " Again, this seems to be a log linear relationship, which is also very interesting."}, {"start": 2021.52, "end": 2028.02, "text": " And also the the solve rate goes up with more sampling compute, which is kind of the same"}, {"start": 2028.02, "end": 2029.34, "text": " plot as above."}, {"start": 2029.34, "end": 2035.3999999999999, "text": " But here it's measured in terms of compute, and not necessarily in terms of of number"}, {"start": 2035.3999999999999, "end": 2036.3999999999999, "text": " of samples."}, {"start": 2036.4, "end": 2042.18, "text": " Obviously, the larger models, they do take longer time to forward propagate and therefore"}, {"start": 2042.18, "end": 2043.48, "text": " use more compute."}, {"start": 2043.48, "end": 2048.36, "text": " But interestingly, because of their scaling property, you can see that at the beginning,"}, {"start": 2048.36, "end": 2055.9, "text": " because they take longer, they need more compute to reach the same pass rate or solve rate."}, {"start": 2055.9, "end": 2063.76, "text": " However, as you go up with the compute, because of their slope being being higher right here,"}, {"start": 2063.76, "end": 2067.0200000000004, "text": " they eventually will surpass the other models."}, {"start": 2067.0200000000004, "end": 2073.0600000000004, "text": " And even seen from a compute perspective, it will be cheaper to use the larger model"}, {"start": 2073.0600000000004, "end": 2077.9, "text": " than to use the small models for the same performance."}, {"start": 2077.9, "end": 2086.5400000000004, "text": " Yeah, here, they investigate their decisions with respect to how fast they can sample."}, {"start": 2086.54, "end": 2095.2599999999998, "text": " You see right here, the alpha code model can sample at 4.74 samples per TPU second."}, {"start": 2095.2599999999998, "end": 2100.82, "text": " If they were to use a decoder only model, they would be a lot slower, because now obviously"}, {"start": 2100.82, "end": 2108.22, "text": " the decoder has a bigger length, which means the attention matrix has a bigger, a bigger"}, {"start": 2108.22, "end": 2114.46, "text": " size, I guess, they also allocate more blocks to the decoder so that the parameters are"}, {"start": 2114.46, "end": 2121.3, "text": " approximately equal, which then means all in all means that this architecture is in"}, {"start": 2121.3, "end": 2126.78, "text": " total slower, because it has more connections, it has more blocks."}, {"start": 2126.78, "end": 2133.46, "text": " Then they also they test with the regular transformer like standard multi-head attention,"}, {"start": 2133.46, "end": 2136.86, "text": " and that's just kind of abysmal."}, {"start": 2136.86, "end": 2141.86, "text": " So this is due to the fact that they use this shared query attention right here in their"}, {"start": 2141.86, "end": 2150.1800000000003, "text": " architecture and yeah, yes, okay, this is the same encoder decoder split, but they use"}, {"start": 2150.1800000000003, "end": 2157.96, "text": " a different, they don't use the shared query."}, {"start": 2157.96, "end": 2159.44, "text": " So that is speed."}, {"start": 2159.44, "end": 2163.94, "text": " Now what I also find interesting is the pre-training data set."}, {"start": 2163.94, "end": 2169.9, "text": " I'm sorry, we'll go through a lot of results right here, but they're all very interesting."}, {"start": 2169.9, "end": 2175.62, "text": " So the pre-training data set used also influences the performance at the end."}, {"start": 2175.62, "end": 2183.6600000000003, "text": " But as you can see, if they restrict themselves to GitHub, but Python only, instead of GitHub"}, {"start": 2183.6600000000003, "end": 2189.9, "text": " all languages, and all languages mean something like Python and C++ and Julia and things like"}, {"start": 2189.9, "end": 2193.7400000000002, "text": " this, but it's still programming languages."}, {"start": 2193.7400000000002, "end": 2197.82, "text": " So if they use Python only, their solve rate drops dramatically."}, {"start": 2197.82, "end": 2205.06, "text": " However, if they use Massive Text, and Massive Text does contain some GitHub data, but it's"}, {"start": 2205.06, "end": 2208.9, "text": " also a natural language data set, it doesn't drop as much."}, {"start": 2208.9, "end": 2211.7000000000003, "text": " I just I think that's quite interesting."}, {"start": 2211.7000000000003, "end": 2213.86, "text": " Like why might that be?"}, {"start": 2213.86, "end": 2215.82, "text": " I don't know."}, {"start": 2215.82, "end": 2224.5800000000004, "text": " Yeah, here they list up all the advancements and don't want to go through them, but you"}, {"start": 2224.58, "end": 2229.66, "text": " can just see how just how engineering plays in here."}, {"start": 2229.66, "end": 2232.74, "text": " It's not just I have an idea and I build the model."}, {"start": 2232.74, "end": 2233.74, "text": " No, no, no."}, {"start": 2233.74, "end": 2239.18, "text": " It's, you know, if I just build the model, I get 10.4% right here."}, {"start": 2239.18, "end": 2245.62, "text": " But then I add multi, I add the encoder loss of the mask language model, I add the tempering,"}, {"start": 2245.62, "end": 2248.84, "text": " I add the tags and ratings."}, {"start": 2248.84, "end": 2255.06, "text": " So the little snippet they put in front that they randomize at test time, right?"}, {"start": 2255.06, "end": 2261.1000000000004, "text": " I add value predictions, I add this, this weighting of the gradient, I add the clustering,"}, {"start": 2261.1000000000004, "end": 2266.56, "text": " you can see that with everything they add, they get improvement after improvement."}, {"start": 2266.56, "end": 2273.34, "text": " So I guess what the lesson here is that there might always be a way to sort of push your"}, {"start": 2273.34, "end": 2281.3, "text": " system even further by just adding something, something smart, or alternatively just scaling"}, {"start": 2281.3, "end": 2283.82, "text": " by a factor of 10."}, {"start": 2283.82, "end": 2289.88, "text": " But you know, that I guess that's the sad story of deep learning, right?"}, {"start": 2289.88, "end": 2294.2400000000002, "text": " Because these these things, they kind of give you a constant improvement, right?"}, {"start": 2294.2400000000002, "end": 2296.86, "text": " You can see that across all of the things right here."}, {"start": 2296.86, "end": 2303.1400000000003, "text": " For example, the first the mask language modeling gives you maybe not here, but maybe not here,"}, {"start": 2303.14, "end": 2305.14, "text": " but here, like a 2%."}, {"start": 2305.14, "end": 2306.94, "text": " This is about 2%."}, {"start": 2306.94, "end": 2310.8199999999997, "text": " This is about 2% improvement."}, {"start": 2310.8199999999997, "end": 2316.2999999999997, "text": " And you know, some of these things, they scale with size, but some of them also kind of give"}, {"start": 2316.2999999999997, "end": 2318.46, "text": " you a constant improvement."}, {"start": 2318.46, "end": 2325.22, "text": " And the you can always get the same improvement by just scaling up models, right?"}, {"start": 2325.22, "end": 2329.8199999999997, "text": " In fact, you look at you have to get all of these improvements right here."}, {"start": 2329.82, "end": 2335.34, "text": " Or you just scale up the model by a factor of 10, and you get like also an improvement."}, {"start": 2335.34, "end": 2337.86, "text": " Sad story of deep learning."}, {"start": 2337.86, "end": 2349.06, "text": " Yeah, this right here is a comparison of this is a comparison of the filtering and clustering"}, {"start": 2349.06, "end": 2350.06, "text": " algorithms."}, {"start": 2350.06, "end": 2355.5800000000004, "text": " So if they just do no filtering, they just select 10 outputs at random, obviously, their"}, {"start": 2355.58, "end": 2361.24, "text": " solve rate is just zero, because they generate, like most of the generated samples, they are"}, {"start": 2361.24, "end": 2365.24, "text": " just garbage, they don't, well, they don't solve the problem."}, {"start": 2365.24, "end": 2370.18, "text": " So if they now filter that already gives the biggest boost, right, that eliminates the"}, {"start": 2370.18, "end": 2373.68, "text": " 99%, that fail on the test inputs."}, {"start": 2373.68, "end": 2380.44, "text": " And therefore, that is that is pretty, pretty significant improvement."}, {"start": 2380.44, "end": 2387.7000000000003, "text": " If they also add clustering, then as you can see, especially at the larger sample budgets,"}, {"start": 2387.7000000000003, "end": 2389.66, "text": " the clustering helps a lot."}, {"start": 2389.66, "end": 2392.6, "text": " And the blue line here is a theoretical upper bound."}, {"start": 2392.6, "end": 2398.12, "text": " So the blue line is where they just submit every single thing that they sample, and see"}, {"start": 2398.12, "end": 2400.36, "text": " how much that would solve."}, {"start": 2400.36, "end": 2406.62, "text": " So this is theoretical upper bound, if they could always sample and select, not sample"}, {"start": 2406.62, "end": 2412.9, "text": " the correct, but if they could always select the correct things from the things they sampled,"}, {"start": 2412.9, "end": 2416.16, "text": " you can see that there is still a big gap."}, {"start": 2416.16, "end": 2422.7, "text": " So even though they do this whole clustering thing, they seem to be still unable in, let's"}, {"start": 2422.7, "end": 2430.74, "text": " say about 10%, or so about 10 percentage points or so of solutions to actually come up with"}, {"start": 2430.74, "end": 2436.9799999999996, "text": " the to select the correct solution among all of their candidates, which is surprising,"}, {"start": 2436.9799999999996, "end": 2438.2599999999998, "text": " right?"}, {"start": 2438.2599999999998, "end": 2439.2999999999997, "text": " Maybe not."}, {"start": 2439.2999999999997, "end": 2440.2999999999997, "text": " Maybe not."}, {"start": 2440.2999999999997, "end": 2444.8199999999997, "text": " I mean, yeah, I don't know."}, {"start": 2444.8199999999997, "end": 2447.02, "text": " They do test against baselines."}, {"start": 2447.02, "end": 2454.8199999999997, "text": " And I guess the only thing to be said is that the baselines, they sometimes succeed on easy"}, {"start": 2454.8199999999997, "end": 2455.8199999999997, "text": " problems."}, {"start": 2455.82, "end": 2465.06, "text": " I'm sure that in the introductory problems, something like codex doesn't perform too poorly."}, {"start": 2465.06, "end": 2471.98, "text": " However, as soon as you go to like competition level problems, and this is a different data"}, {"start": 2471.98, "end": 2476.9, "text": " set right here in different methodologies in order to make the models comparable, and"}, {"start": 2476.9, "end": 2484.02, "text": " their alpha code just outshines its competitors quite a bit."}, {"start": 2484.02, "end": 2487.74, "text": " And this is the one billion model."}, {"start": 2487.74, "end": 2491.08, "text": " This is not even the larger model."}, {"start": 2491.08, "end": 2496.98, "text": " They do compare whether or not the model just copies over code."}, {"start": 2496.98, "end": 2499.58, "text": " And they have a lot of ways to investigate that."}, {"start": 2499.58, "end": 2505.46, "text": " And they find that largely no, it doesn't copy more code than humans copy."}, {"start": 2505.46, "end": 2510.88, "text": " Therefore, so also humans in these competitions, they have some algorithm in mind that they've"}, {"start": 2510.88, "end": 2516.9, "text": " seen somewhere, they just write it down again, or they even actively copy from other solutions."}, {"start": 2516.9, "end": 2520.84, "text": " They do investigate quantitatively and qualitatively that right here."}, {"start": 2520.84, "end": 2531.06, "text": " And they find that the model largely does not copy over entire solutions from somewhere"}, {"start": 2531.06, "end": 2532.06, "text": " else."}, {"start": 2532.06, "end": 2537.62, "text": " Like, it doesn't just try out all the things that it has seen so far."}, {"start": 2537.62, "end": 2539.58, "text": " There are other tricks right here."}, {"start": 2539.58, "end": 2544.54, "text": " Sorry, there are also ablations, which I this video is already too long."}, {"start": 2544.54, "end": 2549.18, "text": " So I don't want to necessarily go into it into all of the things."}, {"start": 2549.18, "end": 2557.48, "text": " One interesting thing is that the report that their validation loss after a very short time"}, {"start": 2557.48, "end": 2558.7799999999997, "text": " increases."}, {"start": 2558.7799999999997, "end": 2561.7999999999997, "text": " So you can see right here, the validation loss drops."}, {"start": 2561.7999999999997, "end": 2567.34, "text": " And after a while, it increases again, this would indicate overfitting usually, and you"}, {"start": 2567.34, "end": 2570.86, "text": " can see that for the rest of the run, the validation loss increases."}, {"start": 2570.86, "end": 2578.82, "text": " However, their real metric, the true metric, the solve rate actually increases to throughout"}, {"start": 2578.82, "end": 2585.44, "text": " you can see right here, the solve rate increasing throughout the run, there's diminishing returns,"}, {"start": 2585.44, "end": 2591.2000000000003, "text": " but it does continue to increase, which means that the validation loss is not necessarily"}, {"start": 2591.2000000000003, "end": 2593.7000000000003, "text": " a good metric."}, {"start": 2593.7, "end": 2601.02, "text": " And I do have an explanation for this, namely, that these coding models, there's not one"}, {"start": 2601.02, "end": 2606.04, "text": " correct solution, not even in the data set, right, the data set contains many instances"}, {"start": 2606.04, "end": 2612.62, "text": " of problem A, and then solution one, solution two, solution three, solution four."}, {"start": 2612.62, "end": 2618.24, "text": " So if the model learn to produce solution one for problem A, which is a correct solution,"}, {"start": 2618.24, "end": 2624.6, "text": " but the current data point wants the model to produce solution to write, because you're"}, {"start": 2624.6, "end": 2629.9599999999996, "text": " doing language modeling, you need to select one that you train on, then that would technically,"}, {"start": 2629.9599999999996, "end": 2631.56, "text": " you know, be wrong."}, {"start": 2631.56, "end": 2637.3599999999997, "text": " And therefore, if you measure this on the validation set, you might, you might, you"}, {"start": 2637.3599999999997, "end": 2640.56, "text": " know, you might actually get worse."}, {"start": 2640.56, "end": 2646.8399999999997, "text": " Yet still, you might actually increase in your ability to solve the actual problems."}, {"start": 2646.84, "end": 2652.1600000000003, "text": " This leads me to believe a little bit that, you know, is the training loss even appropriate"}, {"start": 2652.1600000000003, "end": 2653.8, "text": " for this for this thing?"}, {"start": 2653.8, "end": 2658.5, "text": " I mean, it's fine, you know, the validation loss goes up, I can understand why and why"}, {"start": 2658.5, "end": 2661.36, "text": " that's might not be necessarily a problem."}, {"start": 2661.36, "end": 2668.52, "text": " But is does that kind of mean that the training loss itself should be rethought?"}, {"start": 2668.52, "end": 2673.04, "text": " And that we should have a better training loss for these types of models where multiple"}, {"start": 2673.04, "end": 2679.52, "text": " continuations, multiple solutions exist in the data set to the same prefix?"}, {"start": 2679.52, "end": 2680.52, "text": " I don't know."}, {"start": 2680.52, "end": 2684.64, "text": " That is one of many questions that I have right here."}, {"start": 2684.64, "end": 2689.52, "text": " As I said, there's lots of other stuff, they augment the data set with some some fuzzing"}, {"start": 2689.52, "end": 2690.52, "text": " procedure."}, {"start": 2690.52, "end": 2696.64, "text": " They, they do lots, lots of different things and investigations."}, {"start": 2696.64, "end": 2698.66, "text": " The paper also has a long appendix."}, {"start": 2698.66, "end": 2703.66, "text": " If you're if you're into that, you can see a lot more stuff, a lot more analysis."}, {"start": 2703.66, "end": 2708.52, "text": " But I think I'm going to leave it here and jump over to the interview."}, {"start": 2708.52, "end": 2709.52, "text": " Thanks so much."}, {"start": 2709.52, "end": 2736.8, "text": " And I hope you enjoy that as well."}]