Technische Samenvatting: GraphPO - Graph-gebaseerde Beleidsoptimalisatie voor Redeneringsmodellen

1. Probleemstelling

Reinforcement Learning met Verifieerbare Beloningen (RLVR) is de standaard geworden voor het verbeteren van Large Reasoning Models (LRM's). De huidige RLVR-methoden kampen echter met twee primaire beperkingen:

1. Redundante Exploratie: Onafhankelijke bemonstering van responsen leidt vaak tot trajecten die verschillende tussenliggende redeneerstappen bevatten. Dit leidt tot verspilde berekening en beperkt de diversiteit van de exploratie.
2. Spaarzame Beloningssignalen: RLVR vertrouwt doorgaans op binaire beloningen voor het eindantwoord. Deze schaarste maakt het moeilijk om krediet toe te wijzen aan specifieke tussenliggende redeneerstappen die bijdragen aan het uiteindelijke antwoord.

Hoewel boomgebaseerde methoden (bijv. TreeRL, PROS) een deel van de redundantie aanpakken door prefixen te delen en fijnmazige signalen te geven bij vertakkingspunten, behandelen zij afwijkende takken nog steeds als onafhankelijke paden. Bijgevolg, als verschillende takken semantisch vergelijkbare tussenliggende staten bereiken, kunnen zij geen informatie delen, wat leidt tot herhaalde exploratie en een hogere variantie in de schatting van het voordeel (advantage estimation).

2. Methodologie: GraphPO

De auteurs stellen GraphPO voor, een nieuw RL-framework dat redeneringsrollouts modelleert als een Directed Acyclic Graph (DAG) in plaats van een keten of een boom.

2.1 Grafiekconstructie en Samenvoeging

• Structuur: In GraphPO worden redeneerstappen gerepresenteerd als randen (edges), en tussenliggende semantische staten (samengevat uit het redeneringspad beginnend vanaf de prompt) worden gerepresenteerd als knopen (nodes).
• Equivalentieklassen: Het framework construeert de graaf incrementeel door semantisch vergelijkbare staten over verschillende paden te detecteren met behulp van node-embeddings (via cosine similarity). Wanneer de gelijkenis een drempelwaarde $\kappa$ overschrijdt, worden knopen samengevoegd tot equivalentieklassen.
• Budget Herallocatie: Wanneer een pad een bestaande equivalentieklasse bereikt, wordt verdere expansie als waarschijnlijk redundant beschouwd. GraphPO halveert het budget voor de volgende laag voor dat pad (waarbij ten minste één voortzetting behouden blijft) en heralloceert de bespaarde berekening naar nieuwe frontier-staten, waardoor bredere exploratie wordt gestimuleerd.

2.2 Grafiekbeloning (Proces-supervisie vanuit Resultaat)

GraphPO zet schaarse resultaatbeloningen om in dichte stap-niveau beloningen zonder dat geannoteerde proceslabels vereist zijn:

• State Scoring: Elke knoop krijgt een score gebaseerd op de geverifieerde antwoorden die vanuit deze knoop bereikbaar zijn. Als een knoop deel uitmaakt van een equivalentieklasse, wordt de score ervan gepooled met de scores van andere knopen in die klasse, gewogen door een pooling-coëfficiënt $w$.
• Stap-beloningen: De beloning voor een specifieke rand (stap) wordt berekend als het verschil in state-scores tussen de bestemmings- en bronknopen, gedisconteerd door de gelijkenis tussen de eindpunten. Dit stelt vroegtijdig gestopte takken in staat om krediet te ontvangen van equivalente partners die succesvol een correct antwoord hebben bereikt.

2.3 Dual-Group Graph Advantage

Om zowel de redeneerefficiëntie als de krediettoewijzing te verbeteren, introduceert GraphPO een dual-group advantage schatting:

1. Correctheidsgroep ($A_{cor}$): Vergelijkt uitgaande stappen vanuit dezelfde semantische staat. Het berekent het voordeel van een specifieke stap relatief aan andere stappen die uit dezelfde staat komen, wat zorgt voor fijnmazige krediettoewijzing.
2. Efficiëntiegroep ($A_{eff}$): Vergelijkt inkomende paden die dezelfde samengevoegde staat bereiken. Het beloont kortere paden (minder tokens/stappen) die een nuttige semantische staat bereiken, waardoor het beleid (policy) wordt aangemoedigd om efficiëntere redeneringstrajecten te vinden.

2.4 Beleidsoptimalisatie

Het beleid wordt geoptimaliseerd met een PPO-achtige doelstelling die de dual-group advantage combineert ($A_{dual} = A_{cor} + \lambda_{eff} A_{eff}$). De doelfunctie maximaliseert het verwachte rendement terwijl een KL-divergentie beperking wordt gehandhaafd ten opzichte van een referentiebeleid.

3. Belangrijkste Bijdragen

• Grafiekgebaseerd Rollout-framework: GraphPO is het eerste RL-framework dat redeneringsrollouts als een DAG representeert, waarbij het expliciet equivalente redeneringsstaten aggregeert om suffix-delen en budgetherallocatie mogelijk te maken.
• Dual-Group Advantage Schatting: Het artikel stelt een methode voor om gelijktijdig te optimaliseren voor redeneringscorrectheid (door uitgaande stappen te vergelijken) en redeneerefficiëntie (door inkomende paden te vergelijken), wat de variantie van de advantage-schatting vermindert.
• Proces-supervisie zonder Annotaties: De methode afleidt dichte stap-niveau supervisie uit schaarse resultaatbeloningen door gebruik te maken van de grafiekstructuur en equivalentieklassen, waardoor de noodzaak voor kostbare Process Reward Model (PRM) annotaties vervalt.

4. Experimentele Resultaten

Experimenten werden uitgevoerd op drie LLM's (Qwen2.5-7B-Math, Qwen3-8B-Base, Deepseek-R1-Distill-Qwen-7B) over wiskundige redeneringsbenchmarks (AIME24/25, MATH500, GPQA, LiveCodeBench) en agentische zoektaken.

• Prestaties: GraphPO presteerde consistent beter dan keten-gebaseerde (GRPO, DAPO) en boom-gebaseerde baselines (TreeRL, SPO, PROS, TreePO) over alle modellen en datasets onder hetzelfde token- en responsbudget. Bijvoorbeeld, op het Qwen2.5-7B-Math model bereikte GraphPO een gemiddelde nauwkeurigheid van 40,9%, waarmee het de beste boom-gebaseerde baseline (PROS met 37,7%) overtrof.
• Exploratie-efficiëntie: GraphPO demonstreerde een hogere exploratie-efficiëntie, wat betekent dat een groter deel van de berekening werd toegewezen aan nuttige redeneringsprogressie in plaats van redundante expansies. Het behield een hogere entropie tijdens de training vergeleken met boom-gebaseerde methoden, die de neiging hebben sneller te convergeren naar specifieke redeneringspatronen.
• Respons Lengte: GraphPO produceerde kortere responsen dan boom-gebaseerde methoden door equivalente staten samen te voegen en kortere paden te belonen, waardoor de inferentie-efficiëntie werd verbeterd.
• Agentische Taken: De methode toonde superieure prestaties in diepe zoek- en agentische taken (General AI Assistant, WebWalker, BrowseComp, XBench), wat de toepasbaarheid ervan op sequentiële besluitvormingsprocessen valideert.
• Vergelijking met PRM's: GraphPO presteerde beter dan PRM-gebaseerde methoden (ReasonFlux-PRM) zonder extra geannoteerde procesdata te gebruiken.

5. Betekenis en Claims

Het artikel claimt dat GraphPO een praktische mechanisme biedt om zelf-emergerende proces-supervisie te verkrijgen uit enkel resultaatbeloningen. Door rollouts als een grafiek te modelleren, pakt het de structurele beperkingen van bomen aan, die geen equivalente staten kunnen representeren die door verschillende paden zijn bereikt.

De auteurs stellen dat GraphPO:

1. Variantie Vermindert: Het samenvoegen van equivalente staten en het poolen van downstream bewijs verlaagt de variantie van de advantage-schatting.
2. Efficiëntie Verhoogt: Het heralloceert computationele budgetten weg van redundante expansies naar diverse exploratie en beloont kortere redeneringspaden.
3. Utilisatie Verbetert: Het stabiliseert beleidsupdates door vroegtijdig gestopte takken krediet te laten ontvangen van equivalente succesvolle partners, wat de benutting van het rollout-budget verbetert.

Het werk suggereert dat grafiekgestructureerde rollouts een robuust alternatief bieden voor boom-gebaseerde methoden voor het opschalen van de redeneercapaciteiten van grote taalmodellen onder instellingen met verifieerbare beloningen.