Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

In het uitgestrekte landschap van de informatica zijn weinig operaties zo fundamenteel als het vermenigvuldigen van twee grote rasters met getallen, een proces dat matrixvermenigvuldiging wordt genoemd. Deze wiskundige taak vormt de basis voor alles, van het trainen van kunstmatige intelligentiemodellen tot het renderen van realistische beelden in videogames. Decennialang hebben wetenschappers geweten dat deze operatie sneller kan worden uitgevoerd dan de standaard, rechtstreekse methode, maar de exacte limiet van hoe snel het mogelijk kan gaan, is een van de meest hardnekkige mysteries in het vakgebied gebleven. Deze limiet wordt beschreven door een enkel getal, een wiskundige exponent die bepaalt hoe de tijd die nodig is voor de berekening groeit naarmate de omvang van de rasters toeneemt. Hoe kleiner dit getal, hoe efficiënter de computer kan zijn. Hoewel het theoretische minimum bekend is als ten minste twee, is de beste bewezen bovengrens jarenlang net boven de 2,37 gebleven, een barrière waar onderzoekers met steeds geavanceerdere wiskundige instrumenten aan hebben geprobeerd te slijten.

Een team van onderzoekers van Google DeepMind, samen met medewerkers van verschillende universiteiten, heeft deze grens nu iets verder verlegd. Door moderne optimalisatietechnieken te combineren met een nieuwe vorm van kunstmatige intelligentie, hebben zij een nieuw record gevestigd door te bewijzen dat de exponent kan worden verlaagd naar minder dan 2,371177. Dit is een kleine numerieke verschuiving, maar in de context van dit specifieke probleem vertegenwoordigt het een belangrijke stap voorwaarts. Het vorige beste resultaat, behaald in 2025, stond op 2,371339. De nieuwe bevinding lost het uiteindelijke mysterie van de exacte limiet niet op, noch verandert het onmiddellijk de manier waarop computers matrices vermenigvuldigen in de praktijk, maar het verfijnt de theoretische beperkingen van het probleem en laat zien dat het plafond lager ligt dan voorheen werd aangenomen.

Het pad naar dit nieuwe record begon met een wiskundig kader dat bekend staat als de laser-methode, een techniek die meer dan veertig jaar geleden is ontwikkeld om indirect snellere algoritmen voor matrixvermenigvuldiging te ontwerpen. De meest recente verfijning van deze methode, genaamd combination loss analysis, berust op het oplossen van een enorm, complex optimalisatieprobleem. Dit probleem houdt in dat men de beste manier moet vinden om een grote wiskundige structuur op te splitsen in kleinere stukken. De onderzoekers ontdekten dat de moeilijkheid van dit probleem afhangt van een parameter die de diepte van de opsplitsing vertegenwoordigt. Eerdere pogingen stopten bij een diepte van drie, wat het aantal variabelen dat zij konden aanpassen beperkte. Het nieuwe team realiseerde zich dat door deze diepte te verhogen naar vier, zij een veel grotere ruimte van mogelijkheden konden verkennen, maar dat het doen hiervan een probleem zou vereisen met miljoenen variabelen, een taak die veel te groot is voor de traditionele algoritmen die in het verleden werden gebruikt.

Om deze schaal aan te pakken, maakten de onderzoekers gebruik van technieken geleend uit machine learning. In plaats van standaard wiskundige solvers te gebruiken, herformuleerden zij het probleem zodat het kon worden afgehandeld door gradiëntafdaling (gradient descent), een methode die veel wordt gebruikt bij het trainen van neurale netwerken. Deze aanpak stelde hen in staat om krachtige computerhardware te gebruiken om de gegevens parallel te verwerken, waardoor de explosie in complexiteit die gepaard ging met de diepere opsplitsing werd opgevangen. Zij behandelden de wiskundige variabelen alsof het de aanpasbare gewichten in een leermodel waren, waarbij ze deze iteratief verfijnden om een betere oplossing te vinden. Deze verschuiving in strategie verbeterde de bovengrens alleen al met een meetbaar bedrag, wat aantoont dat moderne computationele instrumenten potentieel konden ontsluiten dat door oudere methoden over het hoofd was gezien.

Het team stopte echter niet daar. Zij gebruikten een systeem genaamd AlphaEvolve, een kunstmatige intelligentie die ontworpen is om zijn eigen code te schrijven en te verbeteren. In plaats van alleen het optimalisatiealgoritme uit te voeren, lieten zij de AI het algoritme zelf aanpassen. Het systeem genereerde een nieuwe versie van de code, voerde deze uit om te zien welke bovengrens het produceerde, en liet de code vervolgens verder evolueren om die bovengrens te minimaliseren. Dit proces van zelfverbetering stelde de onderzoekers in staat om subtiele verfijningen in de optimalisatiestrategie te vinden die een menselijk team wellicht over het hoofd had gezien. Het resultaat van deze geautomatiseerde evolutie was een verdere verbetering, die de bovengrens omlaag drukte naar het nieuwe record van 2,371177.

Om er zeker van te zijn dat dit resultaat geen artefact was van afrondingsfouten van de computer of onnauwkeurigheden in drijvende komma-getallen, voerde het team een rigoureuze verificatiestap uit. Zij namen de oplossing die door hun algoritmen was gevonden en zetten alle getallen om in exacte breuken, waarbij de uiteindelijke berekeningen met perfecte precisie werden uitgevoerd. Zij vervingen ook elke logaritme in de vergelijkingen door een veilige, rationale bovengrens die garandeerde dat aan de beperkingen werd voldaan. Dit zorgvuldige certificeringsproces bevestigde dat de nieuwe bovengrens wiskundig geldig is en vrij is van de numerieke ruis die dergelijke complexe berekeningen vaak teistert.

De onderzoekers merken op dat hoewel hun aanpak een betere bovengrens heeft opgeleverd, de verbeteringen steeds moeilijker te realiseren zijn. De winst die zij boekten is vergelijkbaar in omvang met de incrementele vooruitgang die de afgelopen veertig jaar is gezien. Zij suggereren dat hoewel verdere bescheiden verbeteringen mogelijk zijn door deze optimalisatietechnieken verder te verfijnen, het bereiken van een veel grotere sprong in het begrip van de werkelijke limiet waarschijnlijk geheel nieuwe wiskundige ideeën zal vereisen. Voor nu staat het werk als een bewijs van de kracht van het combineren van diepe theoretische wiskunde met de computationele kracht van moderne machine learning, wat aantoont dat er zelfs in een vakgebied met een lange geschiedenis nog steeds ruimte is voor ontdekking.