Relation Reasoning with LLMs in Expensive Optimization

Riepilogo Tecnico: R2SAEA – Ragionamento sulle Relazioni con LLM nell'Ottimizzazione Costosa

Enunciato del Problema
I Problemi di Ottimizzazione Costosa (EOP) sono caratterizzati da funzioni obiettivo a scatola nera in cui le valutazioni sono costose (ad esempio, esperimenti fisici, simulazioni ad alta fedeltà) e i gradienti non sono disponibili. Il collo di bottiglia principale nella risoluzione degli EOP è il budget di valutazione limitato. Sebbene gli Algoritmi Evolutivi Assistiti da Surrogati (SAEA) mitigino questo problema utilizzando modelli appresi per filtrare i candidati, i surrogati convenzionali (modelli di regressione, classificazione o relazione) richiedono tipicamente un addestramento frequente man mano che la popolazione evolve. Questo ciclo "addestra-predici" comporta un significativo sovraccarico computazionale, che può annullare i guadagni di efficienza dell'assistenza tramite surrogati. Inoltre, sebbene i Modelli Linguistici di Grande Dimensione (LLM) abbiano mostrato promesse nell'ottimizzazione, il dispiegamento diretto di modelli all'avanguardia nei cicli evolutivi è spesso impraticabile a causa degli alti costi di inferenza e della latenza, mentre i modelli più piccoli mancano delle capacità di ragionamento specifiche richieste per un'affidabile inferenza delle relazioni.

Metodologia: R2SAEA
Il documento propone R2SAEA (Algoritmo evolutivo assistito da surrogato LLM basato su relazioni addestrato per rinforzo), un framework che sostituisce il ciclo tradizionale di ri-addestramento con un surrogato basato su relazioni e solo inferenza, alimentato da un LLM fine-tuned. La metodologia consta di tre componenti fondamentali:

1. Ragionamento sulle Relazioni come Apprendimento in Contesto:
   Invece di addestrare un modello parametrico, il documento formula la modellazione del surrogato delle relazioni come un compito di ragionamento pairwise in contesto. L'LLM viene sollecitato a prevedere la superiorità relativa tra coppie di soluzioni basandosi su un insieme di esempi etichettati (contesto). Sono supportati due criteri principali:

   • Criterio Funzionale (C1): Etichettatura binaria ($+1/-1$) basata sulla superiorità del valore obiettivo.
   • Criterio di Categoria (C2): Etichettatura ternaria ($+1/0/-1$) che distingue le relazioni inter-classe (buono vs. cattivo) e intra-classe.

2. Costruzione Iterativa del Contesto Basata su Ancore:
   Per affrontare la complessità quadratica dei confronti pairwise ($O((n+q)^2)$) che supera i limiti del contesto, gli autori introducono una strategia iterativa basata su ancore.

   • Il compito viene decomposto in $n$ round di inferenza, dove ogni soluzione esistente nell'insieme del contesto agisce come un'"ancora" fissa.
   • Per ogni ancora, l'LLM riceve un prompt contenente le relazioni etichettate tra l'ancora e le altre soluzioni del contesto, più le relazioni non etichettate tra l'ancora e le soluzioni candidate.
   • Questo riduce la complessità del prompt a lineare ($O(n+q)$) per round, garantendo stabilità e scalabilità.

3. Aggregazione Basata sul Voto:
   L'LLM produce una matrice di relazioni pairwise. Queste vengono aggregate in punteggi di qualità assoluti per la selezione dei candidati tramite un meccanismo di voto:

   • Per C1, il punteggio è la somma negativa delle relazioni previste (contando quante ancore un candidato batte).
   • Per C2, viene calcolato un punteggio normalizzato in base a quanto spesso i candidati sono giudicati "migliori" o "peggiori" dai gruppi di ancore "buone" e "cattive".

4. Fine-Tuning con Apprendimento per Rinforzo (GRPO):
   Per abilitare un dispiegamento efficiente, zero-shot, senza ri-addestramento per generazione, gli autori effettuano il fine-tuning di un LLM compatto (Qwen2.5-7B) utilizzando l'Ottimizzazione della Politica Relativa di Gruppo (GRPO).

   • Dati: Le traiettorie di addestramento sono generate da esecuzioni evolutive su funzioni di benchmark (LZG, CEC), creando coppie di istruzioni dove la verità fondamentale è la relazione pairwise effettiva.
   • Ricompensa: Una funzione di ricompensa basata su regole valuta la conformità al formato di output JSON, l'accuratezza delle relazioni e la diversità dell'output (penalizzando le previsioni degeneri).
   • Vantaggio: GRPO elimina la necessità di un modello critico separato, utilizzando la normalizzazione della ricompensa a livello di gruppo per fornire segnali di apprendimento stabili per le etichette di relazione discrete.

Contributi Chiave

1. Formulazione: Il documento formula la modellazione del surrogato basata sulle relazioni come un problema di ragionamento LLM in contesto sotto i criteri C1 e C2, introducendo un meccanismo di costruzione iterativa del prompt basato su ancore per ridurre la complessità del contesto da quadratica a lineare.
2. Strategia di Aggregazione: È stata progettata una strategia di aggregazione basata sul voto per convertire le relazioni pairwise previste in punteggi assoluti per la classificazione dei candidati, consentendo agli operatori di selezione SAEA standard di utilizzare gli output degli LLM.
3. Pipeline RL: È stata stabilita una pipeline di fine-tuning RL end-to-end utilizzando traiettorie evolutive e GRPO. I modelli risultanti (ReLLM-C1/C2) dimostrano un'accuratezza di previsione delle relazioni superiore rispetto a potenti LLM generici e abilitano il dispiegamento zero-shot senza ri-addestramento.
4. Prestazioni: Il framework ottiene prestazioni all'avanguardia (SOTA) sia su benchmark di ottimizzazione costosa mono-obiettivo (SOP) che multi-obiettivo (MOP), superando i SAEA classici (regressione, classificazione e basati su relazioni) e le linee di base LLM generiche.

Risultati Sperimentali

• Prestazioni di Ottimizzazione: Sui benchmark mono-obiettivo (suite LZG, YLL), R2SAEA-SOP ha ottenuto il miglior rango medio (2,69) tra sette algoritmi, superando DRSO basato su relazioni in 22/45 casi e l'Ottimizzazione Bayesiana in 23/45 casi. Nei test multi-obiettivo (DTLZ, WFG, MaF), R2SAEA-MOP si è classificato primo con un rango medio di 2,84, superando significativamente i surrogati basati su classificazione (CPS-MOEA, CSEA) e regressione (K-RVEA).
• Previsione delle Relazioni: Le valutazioni offline hanno mostrato che i modelli ReLLM fine-tuned con RL hanno superato significativamente i loro modelli base pre-fine-tuning e gli LLM generici all'avanguardia (inclusi GPT-4o, Gemini-2.5-Pro e Qwen3-235B) in accuratezza delle relazioni pairwise e coerenza di classificazione (Spearman's $\rho$). In modo notevole, gli LLM generici hanno spesso prodotto correlazioni vicine allo zero o negative, fallendo nel produrre classifiche significative senza addestramento specifico per il compito.
• Scalabilità e Robustezza: Il modello ha dimostrato robustezza rispetto agli spostamenti nella dimensionalità dello spazio delle decisioni ($D \in \{5, 10, 30\}$) e alla dimensione del contesto. È stato scoperto che la normalizzazione locale (a livello di prompt) è superiore alla normalizzazione globale per l'inferenza relazionale.
• Dispiegamento: Le varianti quantizzate (4-bit e 8-bit) di un modello da 3 miliardi di parametri hanno mantenuto un'alta accuratezza abilitando al contempo un'inferenza efficiente su dispositivi edge (ad esempio, Jetson Orin NX), supportando un paradigma di surrogato pratico a livello hardware.

Significato e Affermazioni
Il documento afferma che R2SAEA colma il divario tra l'alto potenziale di ragionamento degli LLM e i rigorosi requisiti di efficienza dell'ottimizzazione costosa. Spostandosi da un paradigma "addestra-predici" a un paradigma "solo inferenza", il metodo elimina il sovraccarico del frequente ri-addestramento dei surrogati. Gli autori sottolineano che il loro approccio fornisce un paradigma di surrogato zero-shot, in cui un singolo modello specializzato può essere incorporato nei cicli evolutivi senza ulteriore adattamento. Il lavoro rappresenta il primo fine-tuning esplicito di LLM specificamente per l'ottimizzazione evolutiva assistita da surrogati, offrendo una via fattibile verso un'ottimizzazione in tempo reale e hardware-friendly in ambienti con risorse limitate.