Post #3030770

2025-05-15 15:22 UTC

@highergeometer@mathstodon.xyz I was not involved with the matrix multiplication results mentioned in the broader announcement (my collaboration basically comprises Section 3.2 of the white paper). My best guess is that the statement of the results got oversimplified at some point between the actual generation of the result and the release of the white paper. (Unlike an academic collaboration with a small number of authors, the papers at Deepmind go through multiple layers of review by different sets of people, including some tasked with simplifying the exposition but who are not domain experts in the field.) From context, I believe Deepmind was implicitly restricting attention to those matrix multiplication methods that can be iterated to give a Strassen-type algorithm for large matrices. Not all representations of, say 5 x 5 matrix multiplication, are suitable for this task, for instance those that rely on the commutativity of the entries cannot be directly inserted into Strassen's method.

Replies (2)

@tao@mathstodon.xyz 2025-05-15 19:57

@highergeometer@mathstodon.xyz I checked with one of the authors of the paper. There is indeed an oversimplification in how the results were presented. AlphaEvolve improved the ability to decompose the tensor corresponding to 4 x 4 complex matrix multiplication, giving a rank 48 decomposition instead of the previous record of 49. This also gives a way to express 4 x 4 complex matrix multiplication using only 48 scalar multiplications; however not every such expression arises from a tensor decomposition, which is what one needs if one is to iterate the operation in the style of Strassen to speed up the multiplication of very large matrices. So instead of AlphaEvolve being the first to multiply 4 x 4 matrices using 48 multiplications, they should have wrote they are the first to find a tensor decomposition of 4 x 4 matrix multiplication that uses 48 multiplications, which is a slightly different statement.

Open ##3030771
@highergeometer@mathstodon.xyz 2025-05-15 20:02

@tao@mathstodon.xyz Yes, I appreciate that they are improving *tensor decomposition* methods, but it's a pity whoever wrote/approved "For 56 years, designing an algorithm with fewer than 49 multiplications over any field with characteristic 0 was an open problem. AlphaEvolve is the first method to find an algorithm to multiply two 4 × 4 complex-valued matrices using 48 multiplications." didn't pause to think whether other custom methods other than Strassen's were known in small cases, particularly as it is a very prominent result mentioned multiple times (to the extent that Matt Parker's video—part of a coordinated publicity campaign, it looks like—on the results features the new 4x4 multiplication as the thumbnail). It would certainly have taken a bit of wind out of the sails to have to include a footnote saying it's not actually an improvement on SOTA using any methods in their headline example. But for the sake of intellectual integrity, I think the paper needs to be corrected.

Open ##3030773