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

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