Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

In der weiten Landschaft der Informatik sind nur wenige Operationen so grundlegend wie das Multiplizieren zweier großer Zahlenraster, ein Prozess, der als Matrixmultiplikation bekannt ist. Diese mathematische Aufgabe bildet die Grundlage für alles – vom Training künstlicher Intelligenzmodelle bis hin zum Rendern realistischer Bilder in Videospielen. Seit Jahrzehnten wissen Wissenschaftler, dass diese Operation schneller durchgeführt werden kann als mit der standardmäßigen, direkten Methode, aber die präzise Grenze dessen, wie schnell es möglich sein kann, blieb eines der hartnäckigsten Rätsel des Fachgebiets. Diese Grenze wird durch eine einzige Zahl beschrieben, einen mathematischen Exponenten, der bestimmt, wie stark die benötigte Zeit für die Berechnung ansteigt, wenn sich die Größe der Raster vergrößert. Je kleiner diese Zahl ist, desto effizienter kann der Computer sein. Während der theoretische Minimalwert bekanntlich bei mindestens zwei liegt, pendelte die beste bewiesene obere Schranke jahrelang knapp über 2,37 – eine Barriere, an der Forscher mit immer ausgefeilteren mathematischen Werkzeugen abgetragen haben.

Ein Team von Forschern von Google DeepMind, zusammen mit Kooperationspartnern von mehreren Universitäten, hat diese Grenze nun ein Stück weiter verschoben. Durch die Kombination moderner Optimierungstechniken mit einer neuen Form der künstlichen Intelligenz haben sie einen neuen Rekord aufgestellt und bewiesen, dass der Exponent auf weniger als 2,371177 gesenkt werden kann. Dies ist eine kleine numerische Verschiebung, aber im Kontext dieses spezifischen Problems stellt es einen bedeutenden Schritt nach vorn dar. Das vorherige beste Ergebnis, das im Jahr 2025 erzielt wurde, lag bei 2,371339. Der neue Befund löst nicht das ultimative Rätsel um die exakte Grenze und verändert auch nicht unmittelbar, wie Computer Matrizen in der Praxis multiplizieren, aber er verengt die theoretischen Beschränkungen des Problems und zeigt, dass die Decke niedriger liegt, als bisher für möglich gehalten wurde.

Der Weg zu diesem neuen Rekord begann mit einem mathematischen Rahmenwerk, das als Laser-Methode bekannt ist – eine Technik, die vor über vierzig Jahren entwickelt wurde, um Algorithmen für die indirekte Beschleunigung der Matrixmultiplikation zu entwerfen. Die jüngste Verfeinerung dieser Methode, genannt „Combination Loss Analysis“, beruht auf der Lösung eines massiven, komplexen Optimierungsproblems. Dieses Problem beinhaltet die Suche nach dem besten Weg, eine große mathematische Struktur in kleinere Teile zu zerlegen. Die Forscher fanden heraus, dass die Schwierigkeit dieses Problems von einem Parameter abhängt, der die Tiefe der Zerlegung repräsentiert. Frühere Versuche hielten bei einer Tiefe von drei an, was die Anzahl der Variablen einschränkte, die sie anpassen konnten. Das neue Team erkannte, dass sie durch die Erhöhung dieser Tiefe auf vier einen viel größeren Raum an Möglichkeiten explorieren könnten, dies jedoch die Lösung eines Problems mit Millionen von Variablen erfordern würde – eine Aufgabe, die für die in der Vergangenheit verwendeten traditionellen Algorithmen viel zu groß war.

Um diese Größenordnung zu bewältigen, griffen die Forscher auf Techniken zurück, die dem maschinellen Lernen entlehnt sind. Anstatt Standard-Solver zu verwenden, formulierten sie das Problem so um, dass es durch das Gradientenverfahren (Gradient Descent) behandelt werden konnte – eine Methode, die üblicherweise zum Trainieren neuronaler Netze verwendet wird. Dieser Ansatz ermöglichte es ihnen, leistungsstarke Computerhardware zur parallelen Verarbeitung der Daten zu nutzen und so die Explosion der Komplexität zu bewältigen, die mit der tieferen Zerlegung einherging. Sie behandelten die mathematischen Variablen so, als wären sie die anpassbaren Gewichte in einem Lernmodell, und verfeinerten sie iterativ, um eine bessere Lösung zu finden. Dieser Strategiewechsel allein verbesserte die Schranke um einen messbaren Betrag und demonstrierte, dass moderne computergestützte Werkzeuge Potenzial freisetzen können, das ältere Methoden übersehen hatten.

Doch das Team blieb nicht dabei stehen. Sie setzten ein System namens AlphaEvolve ein, eine künstliche Intelligenz, die darauf ausgelegt ist, ihren eigenen Code zu schreiben und zu verbessern. Anstatt nur den Optimierungsalgorithmus auszuführen, ließen sie die KI den Algorithmus selbst modifizieren. Das System generierte eine neue Version des Codes, führte ihn aus, um zu sehen, welche Schranke er lieferte, und entwickelte den Code dann weiter, um diese Schranke zu minimieren. Dieser Prozess der Selbstverbesserung ermöglichte es den Forschern, subtile Verfeinerungen in der Optimierungsstrategie zu finden, die einem menschlichen Team entgangen wären. Das Ergebnis dieser automatisierten Evolution war eine weitere Verbesserung, die die Schranke auf den neuen Rekord von 2,371177 drückte.

Um sicherzustellen, dass dieses Ergebnis kein Artefakt von Rundungsfehlern oder Ungenauigkeiten bei Gleitkommazahlen ist, führte das Team einen strengen Verifizierungsschritt durch. Sie nahmen die durch ihre Algorithmen gefundene Lösung und wandelten alle Zahlen in exakte Brüche um, wobei die abschließenden Berechnungen mit perfekter Präzision durchgeführt wurden. Sie ersetzten zudem jedes Logarithmus in den Gleichungen durch eine sichere, rationale Schranke, die garantierte, dass die Bedingungen erfüllt waren. Dieser sorgfältige Zertifizierungsprozess bestätigte, dass die neue Schranke mathematisch gültig und frei von dem numerischen Rauschen ist, das solch komplexe Berechnungen oft plagt.

Die Forscher merken an, dass obwohl ihr Ansatz eine bessere Schranke geliefert hat, die Verbesserungen zunehmend schwieriger zu erreichen sind. Die Gewinne, die sie erzielten, sind vergleichbar in ihrer Größenordnung mit den inkrementellen Fortschritten der letzten vierzig Jahre. Sie deuten an, dass zwar weitere moderate Verbesserungen durch die fortlaufende Verfeinerung dieser Optimierungstechniken möglich sein könnten, das Erreichen eines wesentlich größeren Sprungs im Verständnis des wahren Limits jedoch wahrscheinlich völlig neue mathematische Ideen erfordern wird. Für den Moment steht die Arbeit als Zeugnis für die Kraft der Verbindung von tiefer theoretischer Mathematik mit der rechnerischen Muskelkraft moderner maschineller Lernprozesse und beweist, dass selbst in einem Feld mit einer langen Geschichte noch Raum für Entdeckungen bleibt.