Riassunto Tecnico: LLaMEA-SAGE

Definizione del Problema

La Progettazione Automatica di Algoritmi (AAD - Automated Algorithm Design) utilizzando i Large Language Models (LLM) è emersa come un paradigma promettente per la scoperta di algoritmi di ottimizzazione direttamente da prompt in linguaggio naturale. Tuttavia, gli approcci basati su LLM esistenti, come LLaMEA, si affidano quasi esclusivamente al feedback della fitness (prestazioni sui benchmark) per guidare la ricerca evolutiva. Questo ciclo di feedback a "scatola nera" lascia una quantità sostanziale di informazioni contenute nel codice generato inutilizzate. Di conseguenza, le strategie di ricerca spesso faticano a bilanciare esplorazione e sfruttamento in spazi di codice ampi ed eterogenei, portando a una stagnazione prematura o a un uso inefficiente di costose query agli LLM. Inoltre, esiste una comprensione limitata di come migliorare sistematicamente gli algoritmi generati dagli LLM dopo la generazione iniziale e di come tali miglioramenti si confrontino con i metodi allo stato dell'arte (SOTA) sotto benchmark controllati.

Metodologia: LLaMEA-SAGE

Il documento propone LLaMEA-SAGE, un framework che integra il feedback della XAI (Explainable AI) strutturato e spiegabile nel processo di progettazione algoritmica evolutiva di LLaMEA. Il meccanismo centrale consiste nell'estrarre caratteristiche strutturali dal codice dei candidati algoritmi e utilizzarle per guidare le mutazioni successive.

1. Estrazione delle Caratteristiche Strutturali

Ogni algoritmo candidato è rappresentato come codice Python eseguibile. Il sistema analizza il codice tramite un Albero di Sintassi Astratta (AST) per costruire un grafo diretto. Da questo grafo, il sistema estrae un ricco set di caratteristiche, tra cui:

• Statistiche della teoria dei grafi: Conteggio di nodi/archi, statistiche di grado (media, varianza, entropia), profondità dell'albero, coefficienti di clustering e metriche basate sui percorsi (diametro, percorso minimo medio).
• Indicatori di complessità: Complessità ciclomatica, conteggio dei token delle funzioni e conteggio dei parametri aggregati tra le funzioni.

2. Modellazione Surrogata Basata su Archivio

Durante il processo evolutivo, tutte le soluzioni valutate, i loro punteggi di fitness e le loro caratteristiche di codice estratte vengono memorizzati in un archivio. Una volta raggiunto un numero minimo di elementi nell'archivio, viene addestrato un modello di regressione ad alberi potenziati dal gradiente (XGBoost) per approssimare la relazione tra le caratteristiche del codice e la fitness osservata. Questo modello surrogato apprende le relazioni non lineari tra la struttura algoritmica e le prestazioni.

3. IA Spiegabile (SHAP) per la Guida

Per derivare istruzioni azionabili, il sistema applica SHAP (SHapley Additive exPlanations) al modello surrogato addestrato. I valori SHAP quantificano il contributo di ogni caratteristica alla fitness predetta. La caratteristica con il maggior valore assoluto di attribuzione viene selezionata, e il segno del suo valore SHAP determina se il valore della caratteristica debba essere aumentato o diminuito per migliorare le prestazioni.

4. Prompt di Mutazione Guidata

La guida strutturale viene tradotta in un'istruzione in linguaggio naturale che aumenta il prompt di mutazione standard fornito all'LLM. Ad esempio, se l'analisi suggerisce che aumentare la complessità ciclomatica correla con migliori prestazioni, il prompt viene modificato in: "In base all'analisi dell'archivio, prova ad aumentare la complessità ciclomatica totale della soluzione."
Fondamentalmente, questa guida orienta il modello di generazione dell'LLM verso regioni strutturali empiricamente vantaggiose senza imporre vincoli sintattici rigidi o template predefiniti, preservando l'espressività dell'LLM.

Contributi Chiave

1. Framework LLaMEA-SAGE: La proposta di un nuovo meccanismo che guida l'AAD utilizzando un feedback guidato dalle caratteristiche derivate da AST e analisi della complessità, mediato da un modello surrogato e dall'analisi SHAP.
2. Benchmarking Sistematico: Un confronto sperimentale completo con i metodi di progettazione euristica basati su LLM allo stato dell'arte, specificamente MCTS-AHD (Monte Carlo Tree Search per l'Algorithm Heuristic Design) e LHNS (LLM-driven Heuristic Neighborhood Search), insieme alla baseline LLaMEA vanilla.
3. Validazione Empirica: Dimostrazione che la guida strutturata migliora la qualità e la robustezza degli algoritmi su benchmark di ottimizzazione black-box, supportata da un'estesa analisi tramite Code Evolution Graphs (CEG) e test statistici.

Risultati Sperimentali

Gli autori hanno valutato LLaMEA-SAGE attraverso due esperimenti primari utilizzando il toolkit di benchmarking IOH-BLADE.

Esperimento 1: Confronto Controllato (SBOX-COST)

• Configurazione: Confronto tra LLaMEA vanilla e LLaMEA-SAGE su un sottoinsieme della suite SBOX-COST (10 dimensioni, 5 istanze).
• Risultati: LLaMEA-SAGE ha ottenuto prestazioni migliori più velocemente rispetto a LLaMEA vanilla, in particolare nelle prime fasi del processo evolutivo. Sebbene entrambi i metodi abbiano raggiunto prestazioni finali simili entro il budget, l'approccio guidato ha mostrato una minore varianza tra le esecuzioni.
• Significatività Statistica: LLaMEA-SAGE ha mostrato un miglioramento medio di 11,1 unità dell'Area Under the Convergence Curve (AUC) con un grande effetto (Cliff's $\delta$ = 0,60). Tuttavia, a causa del numero limitato di esecuzioni indipendenti (5 seed), la differenza non ha raggiunto la significatività statistica ($p=0,44$).
• Analisi Comportamentale: I Code Evolution Graphs hanno rivelato che la guida ha influenzato con successo l'esplorazione strutturale. In particolare, il prompt "refine" ha portato a un aumento della complessità del codice quando guidato, mentre il prompt "random new" spesso ignorava la guida o risultava in una complessità inferiore.

Esperimento 2: Benchmark su Larga Scala (MA-BBOB)

• Configurazione: Valutazione sulla suite Many Affine BBOB (MA-BBOB), uno standard per le competizioni GECCO, confrontando LLaMEA-SAGE con LLaMEA vanilla, MCTS-AHD e LHNS.
• Risultati: LLaMEA-SAGE ha superato costantemente tutti i baseline, inclusi i metodi SOTA MCTS-AHD e LHNS. Ha raggiunto livelli di fitness che LLaMEA vanilla non poteva raggiungere nemmeno dopo l'intero budget di valutazione.
• Efficienza: In termini di utilizzo di token, LLaMEA-SAGE è stato marginalmente più costoso di LLaMEA vanilla ma significativamente più efficiente di MCTS-AHD (che interroga l'LLM più volte per ogni soluzione).
• Generalizzazione: La validazione finale su istanze non viste (diverse dimensioni e istanze del problema) ha mostrato che il miglior algoritmo scoperto da LLaMEA-SAGE ha superato gli altri algoritmi progettati automaticamente e il vincitore della competizione MA-BBOB 2025 nei compiti a 10 e 20 dimensioni, sebbene non abbia superato il vincitore della competizione ottimizzato per il compito a 5 dimensioni.

Significato e Rivendicazioni

Il documento afferma che LLaMEA-SAGE riesce a colmare il divario tra struttura del codice e feedback delle prestazioni comprensibile all'uomo nella progettazione automatica di algoritmi. Traducendo i segnali strutturali in linguaggio naturale, il metodo fornisce un bias induttivo basato sui dati che guida l'evoluzione guidata dagli LLM senza limitare la capacità creativa del modello.

Gli autori sottolineano che anche correlazioni imperfette e rumorose derivate dalle caratteristiche del codice sono sufficienti per influenzare positivamente l'esplorazione nelle fasi iniziali dell'AAD. Il lavoro dimostra che i segnali derivati dal codice possono effettivamente migliorare l'efficienza e la stabilità della scoperta di algoritmi, offrendo un'alternativa scalabile e priva di template rispetto agli approcci basati su euristiche esistenti.

Limitazioni e Lavori Futuri

Gli autori notano con modestia diverse limitazioni:

• Dipendenza dall'LLM: Gli esperimenti sono stati condotti con un singolo backend LLM (GPT-5-mini), sebbene l'ablation preliminare su Gemini abbia mostrato tendenze coerenti.
• Ambito: La valutazione è stata limitata all'ottimizzazione black-box continua a dimensioni moderate; la generalizzazione a problemi ad alta dimensionalità, rumorosi o fondamentalmente diversi rimane una questione aperta.
• Analisi Statica: L'attuale set di caratteristiche cattura solo proprietà strutturali statiche, ignorando il comportamento di esecuzione dinamico o gli effetti di interazione durante le sessioni di ottimizzazione.

Il lavoro futuro proposto mira a combinare le caratteristiche strutturali con descrittori di runtime, esplorare la guida adattiva multi-caratteristica e integrare il meccanismo in altri framework di AAD basati su LLM.