Competition-Level Code Generation with AlphaCode (Paper Review)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper alphacode alpha code deepmind deepmind code deepmind alphacode alphacoder codex copilot ai code ai programmer ai competitive programming ai leetcode machine learning leetcode deepmind leetcode codeforces large scale sampling language models language models for code ai python programmer deep mind fuzzing google deepmind competitive programming ai
#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
 Alpha code 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 Alpha code, 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 talk 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 Alpha code. 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. 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 Alpha code'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 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 and 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. Okay, 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 test server, they have a whole bunch more of these test cases, 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 inputs. So 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 line and then read as many inputs. Then you need to build lists and reverse lists. Then you go into a while loop where you pop of 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 a challenging task. And this is just one data point. The next data point isn't going to be another variant on two strings and typing the back space button. The next data point is going to be a completely different problem. Like searching for shortest paths and some graph or something with denominators of numbers or numerators or something like this, right? 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 our question today. If you guessed that it has something to do with large language models, then and transformers and so on. And yes, 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 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 OpenAI's codex model. So OpenAI's codex model is trained on code from GitHub. And it 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. It's very good. But it can give me like longer snippets than an autocomplete. But it cannot 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 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 text 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 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 by 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 this 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 end coder. And then the decoder obviously there is 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 a language modeling objective in the decoder. They do say it's quite important to have the master 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, it put 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 nucleus sampling and whatnot. But you can generate diverse outputs from the decoder. And they do, they sample 1000s 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 with 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 sample 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 we could replace this, because we have this approach as well in, for example, Ali, 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? 10% 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. 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. 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 ones. 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. 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, 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. But this 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. Then 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. But 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? The reasoning is that 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 autoregressively 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 autoregressively. 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, they use 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 makes sampling a lot faster. So that is how they make this sampling even tractable, right? Because these choices influence how many solutions you can generate at once. And yeah, they already say it's a massive effort to generate these solutions at runtime. Although I wonder, what does that mean, like a couple of seconds 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 codecs right here. What do they mean by, 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 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 also tags, tags might help you. For example, this is dynamic programming, the implementation. I don't know what implementation tag is. Oh, maybe you must implement an actual algorithm instead of just solving a decidability problem, a rating to indicate how hard the problem is. 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 not 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 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 in 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 quite smart to include sort of data that you only know at training time and then use that in a creative manner. It'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 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 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 tens of thousands of candidate samples for many problems. So that's why they filter them. 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. So 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 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 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 datasets is like, or that that would confer to these is so large. It is really astonishing to me to see that there is really this improvement. It's log linear. Yes, this is a log scale. But still, it seems crazy that you can actually get a better performance by just 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 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 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, 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. So as you can see, if they restrict themselves to GitHub, but Python only instead of GitHub all languages and all languages means 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 built the model. No, no, no. It's, you know, if I just built 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 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 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, but 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. You can see right here 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 shines quite out shines its competitors quite a bit. And this is the one 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 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. It 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 they report that their validation loss after 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 too throughout. You can see right here, the solve rate increasing throughout the run. First diminishing returns, but it does continue to increase, which means that the validation loss is not necessarily a good metric. They 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 learned to produce solution one for problem A, which is a correct solution, but the current data point wants the model to produce solution two, right? Because you're doing language modeling, you need to select one that you train on. Then that would technically be wrong. And therefore, if you measure this on the validation set, 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 thing? I mean, it's fine, you know, the validation loss goes up, I can understand why and why that might not be necessarily a problem. But 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, they have lots of other stuff, they augment the data set with some fuzzing procedure. They do lots, lots of different things and investigations. The paper also has a long appendix. 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.
 Alpha code 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 Alpha code,
 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 talk 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 Alpha code.
 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.
 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 Alpha code'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 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 and 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.
 Okay, 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 test server, they have a whole
 bunch more of these test cases, 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 inputs.
 So 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 line and then read as many
 inputs.
 Then you need to build lists and reverse lists.
 Then you go into a while loop where you pop of 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 a challenging task.
 And this is just one data point.
 The next data point isn't going to be another variant on two strings and typing the back
 space button.
 The next data point is going to be a completely different problem.
 Like searching for shortest paths and some graph or something with denominators of numbers
 or numerators or something like this, right?
 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 our question today.
 If you guessed that it has something to do with large language models, then and transformers
 and so on.
 And yes, 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 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 OpenAI's codex model.
 So OpenAI's codex model is trained on code from GitHub.
 And it 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.
 It's very good.
 But it can give me like longer snippets than an autocomplete.
 But it cannot 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 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 text 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 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 by
 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 this 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 end coder.
 And then the decoder obviously there is 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 a language modeling objective in the decoder.
 They do say it's quite important to have the master 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, it put 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 nucleus sampling and whatnot.
 But you can generate diverse outputs from the decoder.
 And they do, they sample 1000s 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 with 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 sample 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 we could replace this, because we have this approach as well in, for example,
 Ali, 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?
 10% 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.
 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.
 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 ones.
 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.
 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, 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.
 But this 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.
 Then 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.
 But 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?
 The reasoning is that 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 autoregressively 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 autoregressively.
 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, they use 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 makes sampling a lot faster.
 So that is how they make this sampling even tractable, right?
 Because these choices influence how many solutions you can generate at once.
 And yeah, they already say it's a massive effort to generate these solutions at runtime.
 Although I wonder, what does that mean, like a couple of seconds 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 codecs right here.
 What do they mean by, 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 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 also tags, tags might help you.
 For example, this is dynamic programming, the implementation.
 I don't know what implementation tag is.
 Oh, maybe you must implement an actual algorithm instead of just solving a decidability problem,
 a rating to indicate how hard the problem is.
 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 not 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 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 in 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 quite smart to include sort of data that you only know at training
 time and then use that in a creative manner.
 It'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 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 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 tens of thousands of candidate samples for
 many problems.
 So that's why they filter them.
 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.
 So 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 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 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 datasets is like, or that that would confer
 to these is so large.
 It is really astonishing to me to see that there is really this improvement.
 It's log linear.
 Yes, this is a log scale.
 But still, it seems crazy that you can actually get a better performance by just 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 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 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, 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.
 So as you can see, if they restrict themselves to GitHub, but Python only instead of GitHub
 all languages and all languages means 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 built the model.
 No, no, no.
 It's, you know, if I just built 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 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 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, but 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.
 You can see right here 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 shines quite out shines its competitors quite a bit.
 And this is the one 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 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.
 It 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 they report that their validation loss after 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 too throughout.
 You can see right here, the solve rate increasing throughout the run.
 First diminishing returns, but it does continue to increase, which means that the validation
 loss is not necessarily a good metric.
 They 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 learned to produce solution one for problem A, which is a correct solution,
 but the current data point wants the model to produce solution two, right?
 Because you're doing language modeling, you need to select one that you train on.
 Then that would technically be wrong.
 And therefore, if you measure this on the validation set, 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 thing?
 I mean, it's fine, you know, the validation loss goes up, I can understand why and why
 that might not be necessarily a problem.
 But 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, they have lots of other stuff, they augment the data set with some fuzzing
 procedure.
 They do lots, lots of different things and investigations.
 The paper also has a long appendix.
 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.