Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

Nel vasto panorama dell'informatica, poche operazioni sono fondamentali quanto la moltiplicazione di due grandi griglie di numeri, un processo noto come moltiplicazione di matrici. Questo compito matematico sostiene tutto, dall'addestramento di modelli di intelligenza artificiale alla resa di immagini realistiche nei videogiochi. Per decenni, gli scienziati hanno saputo che questa operazione può essere eseguita più velocemente del metodo standard e diretto, ma il limite preciso di quanto possa effettivamente accelerare è rimasto uno dei misteri più ostinati del settore. Questo limite è descritto da un singolo numero, un esponente matematico che determina come il tempo richiesto per il calcolo cresce all'aumentare della dimensione delle griglie. Più piccolo è questo numero, più efficiente può essere il computer. Sebbene il minimo teorico sia noto essere almeno due, il miglior limite superiore provato è rimasto poco sopra 2,37 per anni, una barriera che i ricercatori hanno cercato di erodere con strumenti matematici sempre più sofisticati.

Un team di ricercatori di Google DeepMind, insieme a collaboratori di diverse università, ha ora spinto questo confine leggermente oltre. Combinando moderne tecniche di ottimizzazione con una nuova forma di intelligenza artificiale, hanno stabilito un nuovo record, dimostrando che l'esponente può essere abbassato a meno di 2,371177. Si tratta di uno spostamento numerico minimo, ma nel contesto di questo specifico problema, rappresenta un passo avanti significativo. Il precedente miglior risultato, raggiunto nel 2025, si attestava a 2,371339. La nuova scoperta non risolve il mistero ultimo del limite esatto, né cambia immediatamente il modo in cui i computer moltiplicano le matrici nella pratica, ma stringe i vincoli teorici del problema, mostrando che il soffitto è più basso di quanto precedentemente ritenuto possibile.

Il percorso verso questo nuovo record è iniziato con un quadro matematico noto come il metodo laser, una tecnica sviluppata oltre quarant'anni fa per progettare indirettamente algoritmi di moltiplicazione di matrici più veloci. Il più recente perfezionamento di questo metodo, chiamato analisi della perdita di combinazione (combination loss analysis), si basa sulla risoluzione di un problema di ottimizzazione massiccio e complesso. Questo problema consiste nel trovare il modo migliore per scomporre una grande struttura matematica in pezzi più piccoli. I ricercatori hanno scoperto che la difficoltà di questo problema dipende da un parametro che rappresenta la profondità della scomposizione. I tentativi precedenti si erano fermati a una profondità di tre, il che limitava il numero di variabili che si potevano regolare. Il nuovo team ha capito che aumentando questa profondità a quattro, avrebbero potuto esplorare uno spazio molto più ampio di possibilità, ma farlo avrebbe richiesto la risoluzione di un problema con milioni di variabili, un compito troppo vasto per gli algoritmi tradizionali utilizzati in passato.

Per affrontare questa scala, i ricercatori si sono rivolti a tecniche prese in prestito dal machine learning. Invece di utilizzare standard risolutori matematici, hanno riformulato il problema affinché potesse essere gestito tramite la discesa del gradiente, un metodo comunemente usato per addestrare le reti neurali. Questo approccio ha permesso loro di utilizzare potenti hardware per elaborare i dati in parallelo, gestendo l'esplosione di complessità derivante dalla scomposizione più profonda. Hanno trattato le variabili matematiche come se fossero i pesi regolabili di un modello di apprendimento, raffinandoli iterativamente per trovare una soluzione migliore. Questo cambio di strategia da solo ha migliorato il limite di una quantità misurabile, dimostrando che gli strumenti computazionali moderni potevano sbloccare un potenziale che i metodi più vecchi avevano mancato.

Tuttamente, il team non si è fermato qui. Hanno impiegato un sistema chiamato AlphaEvolve, un'intelligenza artificiale progettata per scrivere e migliorare il proprio codice. Invece di eseguire semplicemente l'algoritmo di ottimizzazione, hanno lasciato che l'IA modificasse l'algoritmo stesso. Il sistema generava una nuova versione del codice, la eseguiva per vedere quale limite produceva e poi faceva evolvere ulteriormente il codice per minimizzare tale limite. Questo processo di auto-miglioramento ha permesso ai ricercatori di trovare sottili raffinamenti nella strategia di ottimizzazione che un team umano avrebbe potuto trascurare. Il risultato di questa evoluzione automatizzata è stato un ulteriore miglioramento, portando il limite al nuovo record di 2,371177.

Per garantire che questo risultato non fosse un artefatto di errori di arrotondamento del computer o imprecisioni di virgola mobile, il team ha eseguito una rigorosa fase di verifica. Hanno preso la soluzione trovata dai loro algoritmi e hanno convertito tutti i numeri in frazioni esatte, eseguendo i calcoli finali con precisione perfetta. Hanno anche sostituito ogni logaritmo nelle equazioni con un limite razionale sicuro che garantisse il rispetto dei vincoli. Questo attento processo di certificazione ha confermato che il nuovo limite è matematicamente valido e privo del rumore numerico che spesso affligge tali calcoli complessi.

I ricercatori osservano che, sebbene il loro approccio abbia prodotto un limite migliore, i progressi stanno diventando sempre più difficili da ottenere. I guadagni ottenuti sono paragonabili all'entità del progresso incrementale visto negli ultimi quarant'anni. Suggeriscono che, sebbene ulteriori modesti miglioramenti possano essere possibili continuando a perfezionare queste tecniche di ottimizzazione, raggiungere un salto molto più grande nella comprensione del vero limite richiederà probabilmente idee matematiche completamente nuove. Per ora, il lavoro sta come testimonianza del potere di combinare la matematica teorica profonda con la forza computazionale del moderno machine learning, dimostrando che anche in un campo con una lunga storia, c'è ancora spazio per la scoperta.