Come la Ricerca Evolutiva Bidirezionale Migliora l'Auto-Miglioramento degli LLM

Il collo di bottiglia del campionamento nell’auto-miglioramento degli LLM

I modelli linguistici di grandi dimensioni (LLM) e i sistemi agentici possono risolvere compiti di ragionamento complessi, ma il loro auto-miglioramento dipende dalla generazione di campioni di alta qualità. In fase di addestramento, campioni migliori consentono un post-training più efficace; in fase di inferenza, guidano lo scaling in tempo di test. I metodi di campionamento dominanti — best-of-N e tree search — condividono due limitazioni fondamentali.

In primo luogo, si basano su segnali di verifica sparsi, tipicamente feedback binari o a grana grossa, che forniscono poca guida durante la ricerca. In secondo luogo, costruiscono i candidati estendendo le traiettorie in modo autoregressivo, confinando l'esplorazione a regioni con una massa di probabilità sostanziale del modello. Nei problemi difficili, le soluzioni corrette spesso si trovano in regioni a bassa probabilità che questi metodi raggiungono raramente. Questo articolo introduce un framework che affronta entrambi i problemi simultaneamente.

Ricerca Evolutiva Bidirezionale: Un Nuovo Framework

La Ricerca Evolutiva Bidirezionale (BES) unisce una ricerca evolutiva in avanti con un processo di scomposizione degli obiettivi all'indietro. La ricerca in avanti potenzia l'espansione autoregressiva standard con operatori evolutivi che ricombinano traiettorie parziali, generando candidati al di fuori della distribuzione tipica del modello. La ricerca all'indietro scompone ricorsivamente il compito originale in sotto-obiettivi verificabili, producendo un feedback intermedio denso che guida la ricerca in avanti.

Questo design bidirezionale permette a BES di scoprire soluzioni che né l'espansione pura né la ricerca a ricompensa sparsa possono raggiungere, rendendolo efficace sia per la generazione di campioni in post-training che per la risoluzione di problemi in fase di inferenza.

Ricerca in Avanti: Operatori Evolutivi oltre l'Espansione Autoregressiva

La ricerca in avanti mantiene una popolazione di traiettorie parziali (nodi). Ad ogni passo, applica uno dei cinque operatori: espansione (campionamento di nuovi passi dalla politica) o uno dei quattro operatori evolutivi ispirati alla ricombinazione biologica.

• Combinazione fonde i suffissi di due traiettorie oltre un prefisso condiviso.
• Cancellazione rimuove un passo interno per produrre un candidato più corto.
• Traslocazione trapianta un singolo passo da una traiettoria all'altra.
• Crossover giunta il prefisso di una traiettoria sulla coda di un'altra.

I genitori sono selezionati tramite una distribuzione di Boltzmann sui punteggi all'indietro (e punteggi di coppia per operatori a due genitori), con annealing della temperatura dall'esplorazione allo sfruttamento. Questi operatori permettono alla ricerca di ristrutturare e ricombinare traiettorie esistenti, generando candidati che nessun singolo rollout della politica potrebbe produrre.

Ricerca all'Indietro: Feedback Denso tramite Scomposizione degli Obiettivi

La ricerca all'indietro costruisce un albero degli obiettivi radicato, scomponendo ricorsivamente il compito di primo livello in sotto-obiettivi più fini tramite prompt alla politica. Ogni sotto-obiettivo $g$ è dotato di un verificatore locale $V_g(x,n) \in [0,1]$ che verifica quanto bene un nodo candidato $n$ lo soddisfi.

Il punteggio di un nodo è calcolato ricorsivamente:

$s(n,g) = \alpha \cdot V_g(x,n) + (1-\alpha) \cdot \frac{1}{|\text{ch}(g)|} \sum_{g' \in \text{ch}(g)} s(n,g')$

dove $\alpha$ bilancia i contributi del genitore e dei figli. Per i sotto-obiettivi foglia, $s(n,g) = V_g(x,n)$. Se un obiettivo è completamente soddisfatto, il punteggio va in cortocircuito a 1. Per gli operatori a due genitori, un punteggio di coppia $s(n_a, n_b)$ utilizza il massimo degli output dei verificatori dei due genitori, favorendo candidati complementari che coprono diverse parti dell'albero degli obiettivi.

Questo segnale denso e interpretabile guida la selezione dei genitori anche quando nessun candidato ha completamente risolto il problema, migliorando drasticamente l'efficienza della ricerca.

Garanzie Teoriche: Sfuggire al Guscio Entropico

L'articolo fornisce due motivazioni teoriche. In primo luogo, sotto ipotesi lievi (sorpresa per passo limitata, dipendenza dai passi decrescente e correlazione totale a blocchi lineare), il Teorema 4.4 dimostra che la ricerca per sola espansione è confinata a un ristretto guscio entropico $A_\epsilon(T) = \{y : |-\log P(y) - H_T| \le \epsilon T\}$, la cui dimensione è al massimo $\exp(H_T + \epsilon T)$. Al contrario, gli operatori evolutivi che ricombinano blocchi da traiettorie indipendenti producono candidati con log-probabilità attesa strettamente al di là di questo guscio, con una frazione positiva che ne sfugge.

In secondo luogo, il Teorema 4.5 mostra che la scomposizione all'indietro in sotto-obiettivi produce una riduzione esponenziale della complessità campionaria. La ricerca solo terminale richiede $\Omega(1/\prod_i p_i)$ candidati per trovare una soluzione completa, mentre la ricerca guidata all'indietro necessita solo di $O(p_{\min}^{-1} \log(m/\delta))$ per raccogliere evidenza per tutti gli $m$ sotto-obiettivi. Nel caso simmetrico $p_i = p$, il rapporto è $\Omega(p^{-(m-1)} / \log(m/\delta))$, esponenziale nel numero di sotto-obiettivi.

Post-Training e Inferenza: Guadagni Sperimentali

BES è stato valutato sia su compiti di post-training che di inferenza.

Post-training. Nel ragionamento logico (Knights-and-Knaves), GRPO e MaxRL hanno mostrato scarsi miglioramenti, mentre BES ha aumentato costantemente l'accuratezza di validazione (Figura 3). Nel ragionamento multi-hop (MuSiQue), BES ha superato nettamente GRPO e Tree-GRPO su due scale di modello (Tabella 1).

Metodo	Accuratezza (%)	# Ricerche valide	# Azioni valide	Tasso di completamento
Llama-3.2-3B-Instruct
Modello base	4.0	–	–	–
+ GRPO	2.1 (-1.9)	0.84	0.20	0.64
+ Tree-GRPO	3.9 (-0.1)	1.50	2.14	0.64
+ BES	7.0 (+3.0)	2.31	3.29	0.97
Llama-3.1-8B-Instruct
Modello base	6.6	–	–	–
+ GRPO	5.6 (-1.0)	1.46	1.83	0.37
+ Tree-GRPO	7.4 (+0.8)	0.65	1.36	0.71
+ BES	10.4 (+3.8)	2.11	3.05	0.94

Inferenza. Su tre benchmark aperti di risoluzione di problemi (Circle Packing, Heilbronn Convex), BES ha superato tutti i framework open-source sia nelle prestazioni medie che in quelle migliori, con varianza inferiore (Tabella 2).

Strategia	Circle Packing (Quad.)	Circle Packing (Rett.)	Heilbronn (Convesso)
	Media	Migliore	Media
OpenEvolve	2.531	2.541	2.267
GEPA	2.613	2.628	2.326
ShinkaEvolve	2.464	2.541	2.335
BES	2.623	2.632	2.349

Ablazione, Costo e Conclusioni

Uno studio di ablazione sul ragionamento logico ha confermato che sia gli operatori evolutivi che la ricerca all'indietro contribuiscono ai guadagni di BES (Figura 4). Rimuovere uno qualsiasi dei due componenti ha ridotto le prestazioni, sebbene entrambe le ablazioni abbiano comunque superato GRPO e MaxRL.

L'analisi dei costi ha mostrato che BES aggiunge un overhead di wall-clock inferiore al 30% rispetto a Tree-GRPO, offrendo al contempo un'accuratezza e un comportamento di ricerca sensibilmente migliori. Sui problemi aperti, BES ha comportato un costo API aggiuntivo modesto ($14–$19 per esecuzione) rispetto a ShinkaEvolve ($12–$13), ma ha ottenuto valori obiettivo costantemente più elevati.

In sintesi, BES affronta le due sfide della verifica sparsa e dell'esplorazione limitata attraverso una ricerca evolutiva bidirezionale. Combinando la ricombinazione in avanti con la decomposizione all'indietro degli obiettivi, scopre soluzioni di alta qualità che sfuggono ai metodi esistenti, consentendo miglioramenti costanti sia nel post-training che nell'inferenza in diversi domini di ragionamento.