Computer scientists have discovered a new way to multiply large matrices faster by eliminating a previously unknown inefficiency, leading to the largest improvement in matrix multiplication efficiency in a decade. This could eventually speed up artificial intelligence models that rely heavily on matrix multiplication.
The multiplication of two rectangular number arrays, known as matrix multiplication, plays a crucial role in modern AI models, including speech and image recognition, and is used by chatbots from all major developers, artificial intelligence image generators, and video synthesis models. Beyond AI, matrix mathematics is important for modern computing (think image processing and data compression), and even a slight increase in efficiency can lead to computational and energy savings, reports ArsTechnica.
Graphics processing units (GPUs) perform matrix multiplication tasks due to their ability to handle many calculations simultaneously. They break large matrix problems into smaller segments and solve them simultaneously using an algorithm.
Improvements to this algorithm have been key to breakthroughs in matrix multiplication efficiency over the last century — even before computers were invented. In October 2022, a new technique was invented by Google’s DeepMind AI model called AlphaTensor, focusing on practical algorithmic improvements for specific matrix sizes such as 4×4 matrices.
In contrast, the new research by a team of scientists from Tsinghua University, the University of California, Berkeley, and the Massachusetts Institute of Technology, focuses on theoretical improvements to reduce the complexity index ω to improve performance for all matrix sizes. Instead of looking for immediate practical solutions such as AlphaTensor, the new technique aims for fundamental improvements that can change the efficiency of matrix multiplication on a more general scale.
The traditional method of multiplying two n by n matrices requires n³ separate multiplications. However, the new technique, which improves on the «laser» method introduced by Volker Strassen in 1986, has reduced the upper bound on the exponent (denoted as the aforementioned ω), bringing it closer to the ideal value of 2, which represents the theoretically minimum number of operations required.
The traditional method of multiplying two grids filled with numbers can require up to 27 calculations for a 3×3 grid. But with these improvements, the process is accelerated by significantly reducing the required multiplication steps. This minimizes the number of operations to a little more than twice the size of one side of the grid squared, adjusted by a factor of 2.371552. This is very important because it almost achieves the optimal efficiency of doubling the square size, which is the fastest speed we could ever hope for.
The 2023 breakthrough was made possible by the discovery of «hidden losses» in the laser method, where useful data blocks were inadvertently discarded. In the context of matrix multiplication, «blocks» refer to smaller segments into which a large matrix is divided for easier processing, and «block labeling» — is a technique for categorizing these segments to determine which ones to keep and which ones to discard, optimizing the multiplication process for speed and efficiency. By modifying the way the blocks are labeled, the researchers were able to reduce waste and significantly improve efficiency.
What is the practical application of this? For AI models, reducing the number of computational steps in matrix math can lead to shorter training times and more efficient task performance. This will allow more complex models to be trained faster, potentially leading to improved AI capabilities and the development of more sophisticated AI applications. In addition, efficiency gains can make AI technologies more affordable by reducing the computing power and energy consumption required to perform these tasks.
The exact impact on the speed of AI models depends on the specific architecture of the system and how much its tasks rely on matrix multiplication. Improving algorithmic efficiency often needs to be combined with hardware optimization to fully realize the potential speed gains. Still, over time, as improvements in algorithmic methods accumulate, AI will become faster.