Sintesi Tecnica: GraphPO - Ottimizzazione della Politica Basata su Grafi per Modelli di Ragionamento

1. Definizione del Problema

L'Apprendimento per Rinforzo con Ricompense Verificabili (RLVR) è diventato il paradigma standard per potenziare i Grandi Modelli di Ragionamento (LRM). Tuttavia, gli attuali metodi RLVR affrontano due limitazioni primarie:

1. Esplorazione Ridondante: Il campionamento indipendente delle risposte spesso produce traiettorie differenti che contengono passaggi di ragionamento intermedi simili. Ciò porta a uno spreco di computazione e limita la diversità dell'esplorazione.
2. Segnali di Ricompensa Sparsi: L'RLVR si basa tipicamente su ricompense binarie sulla risposta finale. Questa scarsità rende difficile assegnare il merito (credit assignment) a specifici passaggi di ragionamento intermedi che contribuiscono alla risposta finale.

Sebbene i metodi basati su alberi (ad es., TreeRL, PROS) affrontino parte della ridondanza condividendo i prefissi e fornendo segnali granulari nei punti di ramificazione, essi trattano ancora le branche divergenti come percorsi indipendenti. Di conseguenza, se diverse branche raggiungono stati intermedi semanticamente simili, non possono condividere informazioni, portando a un'esplorazione ripetitiva e a una maggiore varianza nella stima dell'advantage.

2. Metodologia: GraphPO

Gli autori propongono GraphPO, un nuovo framework di RL che modella i rollout di ragionamento come un Grafo Diretto Aciclico (DAG) anziché come una catena o un albero.

2.1 Costruzione e Fusione del Grafo

• Struttura: In GraphPO, i passaggi di ragionamento sono rappresentati come archi (edges), e gli stati semantici intermedi (riassunti dal percorso di ragionamento partendo dal prompt) sono rappresentati come nodi.
• Classi di Equivalenza: Il framework costruisce incrementalmente il grafo rilevando stati semanticamente simili attraverso diversi percorsi utilizzando gli embedding dei nodi (tramite similarità del coseno). Quando la similarità supera una soglia $\kappa$, i nodi vengono fusi in classi di equivalenza.
• Riallocazione del Budget: Quando un percorso raggiunge una classe di equivalenza esistente, l'ulteriore espansione è considerata probabilmente ridondante. GraphPO dimezza il budget del livello successivo per quel percorso (mantenendo almeno una continuazione) e rialloca la computazione risparmiata verso nuovi stati di frontiera, incoraggiando così un'esplorazione più ampia.

2.2 Ricompensa del Grafo (Supervisione di Processo da Risultato)

GraphPO converte le ricompense di risultato sparse in ricompense dense a livello di step senza richiedere etichette di processo annotate:

• Scoring degli Stati: Ogni nodo riceve un punteggio basato sulle risposte verificate raggiungibili da esso. Se un nodo appartiene a una classe di equivalenza, il suo punteggio viene aggregato con i punteggi degli altri nodi in quella classe, pesato da un coefficiente di pooling $w$.
• Ricompense degli Step: La ricompensa per un arco specifico (step) è calcolata come la differenza tra i punteggi degli stati del nodo di destinazione e del nodo di origine, scontata dalla similarità tra i due endpoint. Ciò consente alle branche interrotte precocemente di ricevere il merito dai partner equivalenti che hanno raggiunto con successo una risposta corretta.

2.3 Dual-Group Graph Advantage

Per migliorare sia l'efficienza del ragionamento che l'assegnazione del merito, GraphPO introduce una stima dell'advantage a doppio gruppo:

1. Gruppo di Correttezza ($A_{cor}$): Confronta gli step in uscita dallo stesso stato semantico. Calcola l'advantage di uno specifico step rispetto ad altri step che escono dallo stesso stato, fornendo un'assegnazione del merito granulare.
2. Gruppo di Efficienza ($A_{eff}$): Confronta i percorsi in entrata che raggiungono lo stesso stato fuso. Premia i percorsi più brevi (meno token/step) che raggiungono uno stato semantico utile, incoraggiando la politica a trovare traiettorie di ragionamento più efficienti.

2.4 Ottimizzazione della Politica

La politica è ottimizzata utilizzando un obiettivo di tipo PPO che combina l'advantage a doppio gruppo ($A_{dual} = A_{cor} + \lambda_{eff} A_{eff}$). La funzione obiettivo massimizza il ritorno atteso mantenendo un vincolo di divergenza KL rispetto a una politica di riferimento.

3. Contributi Chiave

• Framework di Rollout Basato su Grafi: GraphPO è il primo framework di RL che rappresenta i rollout di ragionamento come un DAG, aggregando esplicitamente gli stati di ragionamento equivalenti per consentire la condivisione dei suffissi e la riallocazione del budget.
• Stima dell'Advantage a Doppio Gruppo: Il documento propone un metodo per ottimizzare simultaneamente la correttezza del ragionamento (confrontando gli step in uscita) e l'efficienza del ragionamento (confrontando i percorsi in entrata), riducendo la varianza della stima dell'advantage.
• Supervisione di Processo senza Annotazioni: Il metodo deriva una supervisione densa a livello di step dalle ricompense di risultato sparse sfruttando la struttura del grafo e le classi di equivalenza, eliminando la necessità di costose annotazioni di Modelli di Ricompensa di Processo (PRM).

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su tre LLM (Qwen2.5-7B-Math, Qwen3-8B-Base, Deepseek-R1-Distill-Qwen-7B) su benchmark di ragionamento matematico (AIME24/25, MATH500, GPQA, LiveCodeBench) e compiti agentici di ricerca.

• Performance: GraphPO ha superato costantemente i baseline basati su catene (GRPO, DAPO) e su alberi (TreeRL, SPO, PROS, TreePO) su tutti i modelli e i dataset sotto gli stessi budget di token e risposte. Ad esempio, sul modello Qwen2.5-7B-Math, GraphPO ha raggiunto un'accuratezza media del 40,9%, superando il miglior baseline basato su alberi (PROS al 37,7%).
• Efficienza di Esplorazione: GraphPO ha dimostrato una maggiore efficienza di esplorazione, il che significa che una percentuale maggiore di computazione è stata allocata a progressi di ragionamento utili piuttosto che a espansioni ridondanti. Ha mantenuto un'entropia più alta durante l'addestramento rispetto ai metodi basati su alberi, che tendono a collassare più velocemente in specifici pattern di ragionamento.
• Lunghezza della Risposta: GraphPO ha prodotto risposte più brevi rispetto ai metodi basati su alberi fondendo gli stati equivalenti e premiando i percorsi più brevi, migliorando così l'efficienza dell'inferenza.
• Compiti Agenti: Il metodo ha mostrato prestazioni superiori nei compiti di ricerca profonda e agentici (General AI Assistant, WebWalker, BrowseComp, XBench), validando la sua applicabilità ai processi decisionali sequenziali.
• Confronto con i PRM: GraphPO ha superato i metodi basati su PRM (ReasonFlux-PRM) senza utilizzare alcun dato di processo annotato aggiuntivo.

5. Significato e Rivendicazioni

Il documento afferma che GraphPO fornisce un meccanismo pratico per ottenere una supervisione di processo auto-emergente partendo solo dalle ricompense di risultato. Modellando i rollout come un grafo, esso affronta i limiti strutturali degli alberi, che non possono rappresentare stati equivalenti raggiunti da percorsi differenti.

Gli autori asseriscono che GraphPO:

1. Riduce la Varianza: Fondendo gli stati equivalenti e aggregando le evidenze a valle, si abbassa la varianza della stima dell'advantage.
2. Migliora l'Efficienza: Rialloca i budget computazionali dalle espansioni ridondanti verso un'esplorazione diversificata e premia i percorsi di ragionamento più brevi.
3. Migliora l'Utilizzo: Stabilizza gli aggiornamenti della politica permettendo alle branche interrotte precocemente di ricevere il merito da partner di successo equivalenti, migliorando l'utilizzo del budget di rollout.

Il lavoro suggerisce che i rollout strutturati su grafi offrano un'alternativa robusta ai metodi basati su alberi per scalare le capacità di ragionamento dei grandi modelli linguistici in contesti di ricompensa verificabile.