This is an interesting case where an AI company pays mathematicians to write up a result and expand and generalize it.
Apparently, an employee at Anthropic was trying to prove a hardness result in cryptography (average-case hardness of Zero-k-Clique), but Claude instead developed this algorithm.
Anthropic then shared the result with Josh Alman and Virginia Vassilevska Williams for verification, the authors of most recent breakthroughs in fast matrix multiplication. (They are shown in this cartoon: https://www.smbc-comics.com/comic/mathematicians)
As far as I can tell, the idea is to interpret rectangular matrix algorithms like Schonhage's as a tree, and then very carefully extract only some of the entries.
This way you can compute N^2/√D positions of an (N×D)×(D×N) matrix multiplication in subquadratic time, O(N^2/D^0.063)
Since LLMs began being used for math I have wondered why the first task in LLM self-improvement wouldn't be improving the underlying algorithms. Even a tiny improvement in matrix multiplication or the other many algorithms that is required would yield would have a huge payoff in efficiency and power-use and a direct impact on profitability, sustainability etc.
Are there any examples of this path being pursued?
This is an interesting case where an AI company pays mathematicians to write up a result and expand and generalize it.
Apparently, an employee at Anthropic was trying to prove a hardness result in cryptography (average-case hardness of Zero-k-Clique), but Claude instead developed this algorithm.
Anthropic then shared the result with Josh Alman and Virginia Vassilevska Williams for verification, the authors of most recent breakthroughs in fast matrix multiplication. (They are shown in this cartoon: https://www.smbc-comics.com/comic/mathematicians)
As far as I can tell, the idea is to interpret rectangular matrix algorithms like Schonhage's as a tree, and then very carefully extract only some of the entries. This way you can compute N^2/√D positions of an (N×D)×(D×N) matrix multiplication in subquadratic time, O(N^2/D^0.063)
Since LLMs began being used for math I have wondered why the first task in LLM self-improvement wouldn't be improving the underlying algorithms. Even a tiny improvement in matrix multiplication or the other many algorithms that is required would yield would have a huge payoff in efficiency and power-use and a direct impact on profitability, sustainability etc.
Are there any examples of this path being pursued?
Google AI improved the fast matrix-multiplication here: https://arxiv.org/abs/2608.16884
Most of what the labs are pursuing with "Recursive Self Improvement" is basically improving the underlying algorithms.