Riepilogo Tecnico: Scoperta di Algoritmi con LLM: Ricerca Evolutiva incontra l'Apprendimento per Rinforzo

Enunciato del Problema

La scoperta di algoritmi efficienti per problemi complessi, in particolare in matematica e ottimizzazione combinatoria, ha storicamente fatto affidamento su una sostanziale competenza umana. Sebbene i recenti progressi nei Large Language Models (LLM) combinati con la ricerca evolutiva (ad esempio, il metodo FunSearch) abbiano mostrato promesse nell'automazione di tale scoperta, gli approcci esistenti trattano l'LLM come un generatore statico. Questi metodi utilizzano l'LLM per proporre nuovi programmi basati sui successi precedenti, ma non riescono ad aggiornare i parametri interni del modello in base ai segnali ottenuti durante l'esplorazione evolutiva. Di conseguenza, perdono l'opportunità di sfruttare la natura parametrica dell'LLM per affinare la sua politica di ricerca nel tempo, portando potenzialmente a una convergenza subottimale o a un'esplorazione inefficiente dello spazio delle soluzioni.

Metodologia: EvoTune

Gli autori propongono EvoTune, un framework che integra strettamente la ricerca evolutiva con l'Apprendimento per Rinforzo (RL) per affinare continuamente l'operatore di ricerca dell'LLM. Il metodo opera in un ciclo iterativo costituito da due fasi alternate:

1. Ricerca Evolutiva (Esplorazione):

   • L'LLM genera programmi Python candidati (algoritmi) basati su prompt costruiti a partire da programmi ad alto punteggio scoperti nelle iterazioni precedenti.
   • Questi programmi vengono valutati su specifici compiti di ottimizzazione combinatoria (ad esempio, Bin Packing, Traveling Salesman Problem, Flatpack) per ottenere punteggi di ricompensa (tipicamente il gap di ottimalità negativo).
   • I programmi validi e i loro punteggi vengono archiviati in un database di programmi, organizzati in "isole" per mantenere la diversità e prevenire una convergenza prematura.
   • La ricerca impiega una strategia di "bootstrapping", in cui l'LLM analizza le differenze tra programmi ad alte prestazioni e programmi a basse prestazioni per guidare la generazione di nuovi candidati.

2. Addestramento RL (Raffinamento):

   • Periodicamente (ogni $f_{RL}$ iterazioni), la politica di generazione dell'LLM ($\pi_\theta$) viene aggiornata utilizzando i dati accumulati dalla ricerca evolutiva.
   • Gli autori formulano questo problema come un problema di Ottimizzazione delle Preferenze. Costruiscono un dataset di preferenze $D_{pref}$ costituito da terne $(x, y^+, y^-)$, dove $x$ è il prompt, $y^+$ è un programma con una ricompensa più alta e $y^-$ è un programma con una ricompensa più bassa.
   • Il modello viene fine-tunato utilizzando l'Ottimizzazione Diretta delle Preferenze (DPO). A differenza della DPO offline standard, EvoTune opera in un setting off-policy dove i dati sono generati dinamicamente dal modello stesso in evoluzione.
   • Preservazione della Diversità: Una scelta progettuale critica è l'uso della regolarizzazione KL Forward (in contrapposizione alla più comune Reverse KL) all'interno dell'obiettivo DPO. Questo incoraggia un comportamento di "copertura della massa", impedendo al modello di collassare in una singola modalità e preservando la diversità dell'output essenziale per una ricerca evolutiva efficace.

Contributi Chiave

1. Integrazione dell'RL nella Ricerca Evolutiva: Il documento afferma di essere il primo a dimostrare il potenziale dell'integrazione stretta tra ricerca evolutiva basata su LLM e fine-tuning con RL nel ciclo. A differenza dei metodi precedenti che utilizzano gli LLM esclusivamente come generatori statici, EvoTune aggiorna i pesi del modello per sfruttare meglio le intuizioni acquisite durante l'esplorazione.
2. Accelerazione della Scoperta di Algoritmi: Affinando la politica di ricerca tramite RL, il metodo accelera la scoperta di algoritmi superiori. Gli esperimenti su tre LLM istruiti (Llama3.2 1B, Phi 3.5 Mini, Granite 3.1 2B) mostrano guadagni di prestazioni coerenti rispetto al metodo FunSearch di base.
3. Allineamento che Preserva la Diversità: Gli autori dimostrano il vantaggio di utilizzare un obiettivo di allineamento modificato (DPO regolarizzato con Forward KL) per preservare la diversità dell'output. Questo è critico per le strategie evolutive, poiché il collasso modale può ostacolare la scoperta di soluzioni nuove.
4. Ampia Applicabilità: Il metodo è stato validato su benchmark diversificati, inclusi problemi combinatori standard (Bin Packing, TSP, Flatpack), sfide reali di Google Hash Code (Ottimizzazione Datacenter, Self-Driving Rides) e compiti di regressione simbolica (LLM-SR).

Risultati Sperimentali

Gli autori hanno valutato EvoTune rispetto a una baseline in stile FunSearch (ricerca evolutiva senza addestramento del modello) su più compiti e modelli:

• Guadagni di Prestazioni: EvoTune ha ottenuto costantemente punteggi di ricompensa finali più alti (gap di ottimalità più bassi) per i primi 50 programmi scoperti rispetto alla baseline. Il divario di prestazioni si è spesso ampliato all'aumentare del budget di campionamento, suggerendo che budget più grandi amplificano i vantaggi del metodo.
• Generalizzazione: I programmi evoluti hanno dimostrato robustezza su set di validazione perturbati e set di test estratti dalla stessa distribuzione, indicando che le politiche apprese generalizzano oltre le istanze specifiche osservate durante l'addestramento.
• Benchmark Reali:
  • Sul compito Google Hash Code Datacenter Optimization, EvoTune ha ottenuto un punteggio di 418, superando il punteggio umano più alto di 407 e battendo la baseline FunSearch (414).
  • Sui compiti di Regressione Simbolica (LLM-SR), EvoTune ha superato la baseline evolutiva e, in modo notevole, ha battuto le baseline che utilizzavano modelli più grandi o proprietari (ad esempio, Mixtral 8x7B, GPT-3.5-turbo) pur utilizzando un modello più piccolo (Phi-3.5 Mini, 3,8 miliardi di parametri).
• Studi di Ablazione:
  • Forward vs Reverse KL: Gli esperimenti hanno confermato che la regolarizzazione Forward KL produce ricompense più elevate e un numero maggiore di soluzioni uniche rispetto alla Reverse KL, validando l'importanza della preservazione della diversità.
  • RL Alternativo: Gli autori hanno testato ReSTEM (Fine-Tuning Superviso su output ad alto punteggio) come alternativa alla DPO. I risultati hanno indicato che la DPO ha superato costantemente ReSTEM ed è stata meno sensibile alla regolazione degli iperparametri.

Significato e Affermazioni

Il documento posiziona EvoTune come un passo significativo in avanti nella progettazione automatizzata di algoritmi affrontando la "Bitter Lesson" (Sutton, 2019), che sostiene che ricerca e apprendimento sono sinergici. Gli autori affermano che:

• Sinergia: La ricerca genera nuovi dati, mentre l'apprendimento distilla pattern da quei dati per guidare l'esplorazione futura in modo più efficace.
• Efficienza: Integrare l'RL permette al sistema di andare oltre il semplice aumento del punteggio medio di una popolazione; guida attivamente la ricerca evolutiva verso soluzioni superiori (misurate dalle prestazioni top-k) mantenendo la diversità necessaria per l'innovazione.
• Scalabilità: Il metodo dimostra potenziale per scalare verso scenari reali, come dimostrato dal suo successo su problemi complessi e non sintetici come l'ottimizzazione dei datacenter e la modellazione sforzo-deformazione.

Gli autori riconoscono modestamente le limitazioni, notando che i loro esperimenti sono stati condotti con modelli che vanno da 1 a 3,8 miliardi di parametri e che è necessaria un'ulteriore scalatura delle dimensioni del modello e dei budget di campionamento per comprendere appieno il potenziale del metodo. Evidenziano inoltre il compromesso tra i costi computazionali aggiuntivi della fase di addestramento RL e i guadagni in termini di efficienza di inferenza e qualità della soluzione.