Rewire ha pubblicato un articolo su un risultato ottenuto da Google DeepMind’s AlphaEvolve. Nel 1969 Volker Strassen scoprì come moltiplicare due matrici 4×4 usando solo 49 moltiplicazioni anziché le 64 del metodo canonico riga-per-colonna, e da allora nessuno riuscì a migliorare il risultato: ora AlphaEvolve ha trovato un metodo che ne richiede solo 48. Il preprint relativo è interessante per due motivi: il primo è che non parla solo di questo risultato ma di un corpus di problemi in cui ci sono stati altri casi di risultati migliorati rispetto a quanto noto in letteratura (ma anche di casi in cui non ci è proprio arrivato…), il secondo è che oltre ai due dipendenti di Google i coautori sono Javier Gómez-Serrano, matematico catalano ora alla Brown University che è stato uno dei primi a studiare la possibilità di usare l’IA per migliorare risultati matematici noti ma non dimostrati ottimali, e l’altro è Terry Tao, di cui non serve spiegare nulla. Detto in altri termini, la parte matematica è sicuramente stata controllata bene.

Quello che ho trovato molto interessante è l’approccio usato per questi problemi. Tenete conto che siamo generalmente parlando di problemi combinatori, per cui il numero di possibili combinazioni da testare è oltre la possibilità di un calcolatore per quanto potente; questa è una delle ragioni per cui trovare nuovi e migliori risultati è un compito praticamente impossibile. Personalmente già l’algoritmo originale di Strassen è stato qualcosa di incredibile. Per la precisione Strassen ha dimostrato che bastavano sette moltiplicazioni anziché 8 per moltiplicare due matrici 2times;2; il risultato indicato all’inizio è una banale conseguenza ottenuta considerando la matrice 4times;4 come formata da quattro matricette 2times;2. Però con la matrice più piccola ci sono relativamente poche possibilità di giocare con i parametri e quindi con costanza e fortuna si può trovare qualcosa. Raddoppiando le dimensioni questo tipo di approccio non funziona. Che fa allora AlphaEvolve? Innanzitutto non cerca un risultato nello spazio delle soluzioni, ma lavora nello spazio degli algoritmi, cioè cerca di scrivere un programma che dia il risultato cercato. Ma anche così il compito sarebbe impervio, visto che il numero di algoritmi possibili è dell’ordine di 10³³. Quello che invece fa è far evolvere gli algoritmi, usando gli LLM come generatori di mutazioni. Ci sono cinque componenti:

• La specificazione del problema, data dagli umani: non solo il prompt iniziale (un algoritmo non necessariamente ottimale) ma anche una funzione di valutazione che deve essere semplice da verificare e dare un punteggio. In questo specifico caso la funzione era data dalla correttezza formale dell’algoritmo e dal numero di moltiplicazioni necessarie.
• La base dati degli algoritmi trovati man mano, da cui si pesca quello statisticamente più promettente.
• Il selezionatore, che prende dalla base dati un algoritmo promettente e lo trasforma in un prompt “ricco” per un LLM;
• La mutazione semantica ottenuta con gli LLM, che essendo addestrati sul codice riescono spesso a fornire ottimizzazioni… che magari danno però la soluzione a un altro problema: l’equivalente algoritmico delle allucinazioni di un chatbot standard.
• Il valutatore-selettore, che controlla che l’LLM non sia andato per farfalle e sceglie i candidati più promettenti.

La parte di mutazione semantica può – anzi vi dovrebbe – fare venire in mente gli algoritmi genetici che erano di moda alcuni decenni fa, dove si facevano modifiche casuali a un algoritmo per vedere se migliorava o no. La differenza fondamentale in questo caso è che gli LLM possono partire per la tangente, ma lo fanno in un modo formalmente corretto, semplificando la vita. Per fare un esempio, la chiave per eliminare la quarantanovesima moltiplicazione è stata il passare alle operazioni con i numeri complessi, che apparentemente complicano la situazione – moltiplicare due numeri complessi significa fare quattro moltiplicazioni rispetto a quella singola nel caso di due numeri reali – ma in un caso particolare permettono un allineamento cosmico per cui moltissime moltiplicazioni si ripetono identiche in più punti, riducendo il numero totale necessario. Tao ha commentato, in maniera un po’ più formale della mia parafrasi, che si sfrutta il fatto stesso che gli LLM sparino parole a caso.

Ho già detto in passato che non bisogna aspettarsi chissà che cosa dall’attuale stato dell’arte delle IA. A dirla tutta, ho il sospetto che passare da 49 a 48 moltiplicazioni (un 2% di guadagno…) non sia chissà cosa. Ma devo riconoscere che per tutta una serie di problemi prettamente combinatori dove lo spazio delle soluzioni è sterminato sono già un grande aiuto.