Riepilogo Tecnico: Allocazione delle Risorse Computazionali nella Ricerca Evolutiva

Enunciato del Problema

I sistemi di ricerca evolutiva guidati da Large Language Model (LLM) (ad es. FunSearch, AlphaEvolve, CodeEvolve) hanno ottenuto risultati all'avanguardia nella scoperta matematica e nell'ottimizzazione combinatoria. Tuttavia, la letteratura esistente riporta prevalentemente il singolo risultato migliore da un numero non specificato di esecuzioni, lasciando undocumented la distribuzione tra le diverse esecuzioni. Inoltre, i costi computazionali riportati variano di ordini di grandezza, rendendo difficile valutare l'affidabilità di una singola esecuzione entro un budget fisso.

Il problema centrale affrontato è l'allocazione delle risorse computazionali: dato un budget fisso di chiamate LLM ($C$), come dovrebbe essere distribuito questo budget tra profondità (raffinamento sequenziale di una singola traiettoria) e ampiezza (esplorazione parallela di multiple traiettorie)? I sistemi attuali spesso fissano questi iperparametri (ad es. dimensione della popolazione e numero di generazioni) senza una comprensione sistematica di come l'allocazione influisca sulle prestazioni attese e sull'affidabilità.

Metodologia

1. Caratterizzazione Empirica dell'Allocazione Profondità-Ampiezza

Gli autori hanno condotto uno studio empirico sistematico su tre compiti di ottimizzazione geometrica (Circle Packing, MinMaxDist, Heilbronn Triangle) e quattro dimensioni di modello (da Qwen3-1.7B a 14B, più Llama-3.1-8B). Hanno definito il problema di allocazione come la suddivisione del budget $C$ in $T$ generazioni di $N$ figli paralleli ($C = T \times N$).

• Inviluppo Fitness-Risorse Computazionali: Hanno analizzato la relazione tra il fitness ottenibile e i FLOPs effettivi (tenendo conto della dimensione del modello e dell'efficienza della cache). Hanno osservato che, sebbene i modelli più grandi abbiano il vantaggio a parità di numero di chiamate, il loro ordinamento delle prestazioni collassa in gran parte quando misurato rispetto ai FLOPs effettivi, a condizione che la coppia modello-compito sia "capace".
• Regolarità Profondità-Ampiezza: Hanno adattato un modello bilineare parametrico al paesaggio del fitness:
  $$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$$
  dove $V$ è il fitness. Il coefficiente di interazione $c$ determina la geometria dell'allocazione ottimale:
  • Ottimi agli Angoli ($|c| \approx 0$): Compiti come Circle Packing mostrano ampi plateau dove molte allocazioni producono risultati simili, spesso favorendo la profondità.
  • Ridghe Interne ($c < 0$): Compiti come MinMaxDist mostrano una cresta netta dove è necessaria una miscela equilibrata di profondità e ampiezza per prestazioni ottimali.
  • Soglia di Capacità: Queste regolarità valgono solo per i modelli che hanno superato una soglia di capacità per il compito specifico; i modelli deboli non riescono a esibire scambi strutturati tra profondità e ampiezza.

2. BaSE: Bandit-based Self-Evolving

Motivati dall'alta varianza nei risultati delle esecuzioni (dove configurazioni identiche producono punteggi di fitness finali molto diversi a causa della stocasticità nel processo di mutazione dell'LLM), gli autori hanno proposto BaSE.

• Meccanismo: BaSE tratta la ricerca evolutiva come un problema di Multi-Armed Bandit (MAB). Invece di impegnare l'intero budget in una singola traiettoria (Greedy) o in un insieme fisso di isole (protocollo Island), BaSE mantiene $K$ traiettorie parallele.
• Allocazione Adattiva: Ad ogni passo, un algoritmo bandit (UCB, EXP3.P o Thompson Sampling) seleziona quale traiettoria estendere con la successiva chiamata LLM. Questo instrada dinamicamente le risorse computazionali lontano dalle esecuzioni che stagnano verso quelle promettenti.
• Ortogonalità: BaSE non altera il modello di base, il prompt o la logica di campionamento dei genitori all'interno di una traiettoria. Opera rigorosamente a livello di allocazione delle risorse tra le traiettorie.

Risultati Chiave

1. Regolarità Empiriche

• Collasso della Capacità: Per i modelli capaci, l'inviluppo delle prestazioni è determinato dai FLOPs effettivi piuttosto che dalla sola dimensione del modello.
• Geometria Dipendente dal Compito: La divisione ottimale tra profondità e ampiezza non è universale; dipende dalla "famiglia algoritmica" del compito (ad es. se la soluzione richiede una libreria specifica come scipy o una costruzione analitica specifica).
• Stocasticità: Anche con allocazione fissa, le singole esecuzioni variano significativamente. Alcune esecuzioni convergono verso un alto fitness, mentre altre stagnano precocemente a causa dell'aggancio a una famiglia algoritmica subottimale.

2. Prestazioni di BaSE

• Miglioramento del Fitness Medio: Su 8 celle (modello, compito), BaSE ha migliorato il miglior fitness medio del 12,3% rispetto ai baselines più forti del protocollo Island (ad es. OpenEvolve, CodeEvolve, ShinkaEvolve) senza modificare il modello o il prompt.
• Guadagni di Affidabilità: I guadagni più significativi sono stati osservati in contesti ad alta varianza. Ad esempio, sul compito Heilbronn Triangle con Llama-3.1-8B, i metodi non-BaSE spesso fallivano nel produrre soluzioni valide (fitness $\approx 0$), mentre BaSE (Thompson Sampling) ha raggiunto un fitness medio di 0,4387.
• Efficienza del Campione: BaSE ha raggiunto le soglie di fitness target significativamente più velocemente (meno generazioni e FLOPs) rispetto ai baselines greedy o ad allocazione fissa. Ad esempio, su MinMaxDist, UCB ha raggiunto una soglia di 0,95 in 92 generazioni, mentre il baseline greedy ne ha richieste 485.
• Ablazione: Dimensioni moderate del pool di braccia ($K \in \{5, 10, 20\}$) hanno fornito il miglior compromesso tra diversità e profondità di raffinamento.

Significato e Affermazioni

Il documento afferma che l'allocazione delle risorse computazionali è una leva distinta e critica per migliorare la ricerca evolutiva guidata da LLM, separata dal scaling del modello o dall'ingegneria del prompt.

• Allocazione vs Ingegneria: Gli autori sottolineano che i loro miglioramenti non sono dovuti a prompt o modelli migliori. In effetti, notano che alcuni baselines (come ShinkaEvolve) hanno ottenuto punteggi elevati su compiti specifici anche grazie a indizi indotti dal prompt (ad es. suggerendo scipy.optimize), mentre BaSE ottiene guadagni puramente attraverso l'instradamento adattivo delle risorse.
• Affidabilità: Il contributo principale è lo spostamento del focus dalla segnalazione del "migliore scenario" alla prestazione "attesa". BaSE fornisce un guadagno di affidabilità, assicurando che un praticante sia meno propenso a sprecare un budget fisso su una traiettoria che è già stagnante.
• Complementarietà: BaSE è presentato come complementare ai meccanismi esistenti all'interno dell'esecuzione (come il campionamento dei genitori). Può essere sovrapposto ai protocolli esistenti (Greedy, Island) per migliorare ulteriormente le prestazioni, in particolare in contesti instabili o ad alta varianza.

Il lavoro conclude che, sebbene la capacità del modello fissi il limite superiore di ciò che è raggiungibile, l'allocazione governa quanto efficientemente un metodo si avvicina a quel limite, e l'allocazione adattiva tramite bandit è una strategia robusta per la ricerca con budget finito.