Faster Sort by DeepMind

With all the yick-yack about AI “exterminating” us, there has been little explanation of just how this might happen.  What, exactly, are machine learning models supposed to do that will wipe out humans?**

Classically, in Clarke-Asimov days, it was imagined that computer intelligences would be turned to optimizing themselves, initiating a feedback loop that accelerated the capabilities of computer intelligences. Soon enough, Carbon-based units would be left behind, unable to even understand what their Silicon-based offspring are up to.

If not extinction exactly, humans might face irrelevance.  Ouch!

While ChatGPT and friends have been putting on their comedy shows, this summer the folks at DeepMind report on actual progress on this front [2]. 

In earlier research, DeepMind found improved algorithms for matrix multiplication, which is huge. Among other things, more efficient matrix multiplies can potentially make deep learning models more efficient—precisely the kind of feedback we have been expecting.

The new work has found faster ways to sort numbers, which is pretty much “the other thing” computers do, besides multiply matrices.  In a way, these results are even more astonishing than the matrix multiplies, because so much Carbon-based brain power has gone into thinking about sort-based algorithms.

The really super, massively, cool thing, though is that they made the system very general, so it can find better algorithms to do anything.  How did they do it?  They did it the way AlphaGo conquered Go—they gamified it. [1]

Basically, the task is to generate a program to solve a problem, with each assembly language statement considered a “move”.  The generated program is run, and points awarded for correct answers.  The machine learning system learns from a bunch of assembly language examples, which guide its search for the best move. 

(As we used to quip, “Programming is easy: just generate every possible program, and throw away the ones that don’t work.”  : – ) )

Wow!

Not only does the dog dance, it is a champion dancer!

As many commentators noted, these improved sort fragments have been dropped into widely used open source library (libc++), which is used by, well, everything [3].  A 1% improvement in these inner loops will speed up, well, every damn program in the world!

Put that on you resume!

Very, very cool.

And, like AlphaGo’s championship games, these results are fascinating reading for us puny Carbon-based programmers. 

---

One interesting thing about this methodology is that it rings true to the psychology of the best human programmers.  I’ve always held that messing about with software is the greatest game ever invented, and we even get paid to do it!   Good programmers intuitively tackle their problems as a strategic game.  We are making moves, looking for a winning combination.

In this case, the reinforcement schedule reflects “the adversary”, which captures the specifications and, implicitly, the limitations of time, space, etc.  The AlphaDev system systematically searches the “game space” of possible programs, which humans navigate intuitively.

---

1. Matthew Hutson, DeepMind AI creates algorithms that sort data faster than those built by people. Nature, 618  June 7 2023. https://www.nature.com/articles/d41586-023-01883-4
2. Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, Thomas Köppe, Kevin Millikin, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kieran Milan, Robert Tung, Minjae Hwang, Taylan Cemgil, Mohammadamin Barekatain, Yujia Li, Amol Mandhane, Thomas Hubert, Julian Schrittwieser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals, and David Silver, Faster sorting algorithms discovered using deep reinforcement learning. Nature, 618 (7964):257-263, 2023/06/01 2023. https://doi.org/10.1038/s41586-023-06004-9
3. Armando Solar-Lezama, AI learns to write sorting software on its own. Nature, 618:240-241, June 7 2023. https://www.nature.com/articles/d41586-023-01812-5

Alphacode AI Can Code OK

…but not really that great.

The year, GPTChat is making headlines this fall, demonstrating an ability to generate highly plausible BS.

The same technology tackled another challenging task, generating plausible computer code.  There have been plenty of coding assistants over the last half century, but AlphaCode tackled the problem human coders actually face:  given a natural language description of the desired result, create computer code to implement it [1]. This is actually a pretty hard problem, which is why computer programmers get paid to do it.

Researchers at DeepMind report a study / demonstration where the machine learning model was entered in a programming contest [3].  This gives a sort of blind comparison between the computer and human programmers.

The interesting thing about the AlphaCode model is that it knows nothing about coding and certainly doesn’t do any fancy theorem proving or other stuff designed to generate programs.  It basically learned from zillions of examples on Github, and apparently learned what code looks like based on problem specifications.  Ethics and legality aside (code on Github has licenses which may or may not permit such reuse), this is pretty amazing.  This really should not work at all!

It’s not so much how well the dog programs, it that he programs at all!  : – )

Now, the computer’s entries were rated in the middle of the pack of human coders.  Is this a success or a failure?  On the one hand, the intuition is it shouldn’t work at all, so that’s a success.  On the other hand, this is a lot of work and expense to match the performance of a “novice” human programmer. ([3], p. 3) 

On the other other hand, there are plenty of ways to improve these results by including actual knowledge of programming.  Like human novices, AlphaCode can get a lot better.  As I tell novice programmers, a lot of coding is just details.  You can learn the details (or, learn how to look up the details).  I’m sure a big computer program like AlphaCode can learn all sorts of details.

This demonstration does raise some interesting points about the overall task we call “coding”.  As J. Zico Kolter snarks, “Is ignoring everything that is known about code the best way to write programs?” [2]  This begs the question of what is the goal of “coding” anyway?  Generating small bits of code that match small bits of specification?  Or solving problems?  And what are the real problems being solved here?

The programming contest eliminates this strategic question, creating an artificial situation where the goal is to, well, generate small bits of code that match small bits of specification.  However well one does this task, there is considerable question about the external validity of the results.  Does “winning” this contest predict ability to solve other programming problems?  Most teachers would say, “no”.  And most managers probably will not want to bet the farm on programmers who are good at this challenge but have no other skills.

On the other other other hand, the fact that the general language model does so well at this task reveals the dirty little secret that programming is really about reading specifications.  The actual coding part of “coding” is relatively trivial, you just write code that does what the specification says.  Programmers who don’t understand this are really bad programmers!

And, of course, truly brilliant programmers are able to infer “the real requirements”, or to invent a solution that is better than what the specification asked for.  Indeed, the best programmers are famous for correcting mistakes in the specifications themselves, and then implementing what the specifications should have said.

And then there is the question of whether the code is actually correct or not!  It is ironic to use a massive amount of computing power to generate “novice” results, and not use any of that computing power to check or test the program!  Honestly, I’d rather have hundreds of test cases that hundreds of novice snippets of code.  (I bet AlphaCode could be AlphaTester, generating, auto generating test suites.)

Anyway.  AlphaCode is kind of neat, though the code it generates may be the least interesting thing about it.

---

1. Mack DeGeurin, DeepMind’s AlphaCode Can Outcompete Human Coders, in Gizmodo, December 8, 2022. https://gizmodo.com/deepmind-ai-google-alphacode-coding-1849869346
2. J. Zico Kolter, AlphaCode and “data-driven” programming. Science, 378 (6624):1056-1056, 2022/12/09 2022. https://doi.org/10.1126/science.add8258
3. 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, Competition-level code generation with AlphaCode. Science, 378 (6624):1092-1097, 2022/12/09 2022. https://doi.org/10.1126/science.abq1158

AI Learning To Invent Algorithms

These days “The Singularity” has become very mystical and Hollywood, and, frankly, seems to be a techno version of racist replacement theory / Elders of Zion shtick.  (‘You will be replaced by godless aliens’) Back in the day—even Alan Turing’s day—the original concept was really about using ‘computation to improve computation’, accelerating computational capabilities by self-improvement of algorithms.

In the 80-some years of the current computational age, computers have indeed accelerated technological developments on all fronts, though “AI” has been a relatively small contribution to this process, compared to things like miniaturization, precise measurement and rapid data networks have been far, far more revolutionary than anything to do with super “brains” or human like “thinking”.

In recent years, we have (finally?) seen “AI” improving computational capabilities, with useful contributions such as generating, optimizing, and debugging code.  But, honestly, the growth in AI has been mostly due to growth in hardware—Moore’s Law, not technological bootstrapping.

So I was interested to see some cool new results from DeepMind AI, which has developed new, more efficient algorithms for matrix multiplication [1]. 

OK, even I can do matrix multiplication, and I know that a lot of important code, including lots of AI-y stuff, does a lot of matrix multiplications.  In fact, a significant chunk of total compute time is tied up doing zillions of matrix multiplications, every day, all the time.

Which means that shaving even a few percent off the time is potentially “huge”, as my benchmarking friends would say [2].

How does it work?  I’m sure I don’t understand it, exactly.  But the general idea is to represent the matrix multiplication as a higher order tensor.  (I.e., 2 x 2 multiplication is represented as a 3D tensor.) Among other things, this trades space for time, which is the oldest trick in the book. 

The other interesting thing is that the AI was given the problem as a game to be solved.  Basically, the goal is to find a sequence of moves that represents the matrix multiply.  At each turn there are zillions of possible moves, just like Go or other games.  And, sure enough they used their winning Go program to learn to solve these problems [2].

Given this representation and some examples of right answers, the AI was tasked to search for the best way(s) to operate on these tensors.  The results were new algorithms that required fewer costly multiplications to get the results.

And, as in the case of Go, the results are superhuman and also inhuman.  The algorithms discovered are not intuitive, indeed they are alien. 

This is, indeed, huge.  But even though the results show an alien intelligence, it really doesn’t feel like a coming singularity to me.

For one thing, computers are already insanely better at matrix multiplication than puny Carbon-based units.  My laptop can compute many orders of magnitude faster than me, so a few percent more doesn’t seem like much.  And in any case, the matrix multiplication doesn’t seem very “intelligent”, even though it is an important part of a lot of “intelligent” computations (such as NLP, vision, and every kind of search).

However, feed this performance improvement back into DeepMind, and put the slightly faster system to work on other key targets, and you’ve finally started the march.  There are plenty of targets, including optimizing the tensors themselves.

“a limitation of AlphaTensor is the need to pre-define a set of potential factor entries F, which discretizes the search space but can possibly lead to missing out on efficient algorithms. An interesting direction for future research is to adapt AlphaTensor to search for F.”

([1], p. 52)

---

1. Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis, and Pushmeet Kohli, Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610 (7930):47-53, 2022/10/01 2022. https://doi.org/10.1038/s41586-022-05172-4
2. Matthew Hutson, DeepMind AI invents faster algorithms to solve tough maths puzzles, in Nature – News, October 5, 2022. https://www.nature.com/articles/d41586-022-03166-w