🤖 AI

Forge: Quality-Aware Reinforcement Learning for NP-Hard Optimization in LLMs

Het artikel introduceert OPT-BENCH, een uitgebreid kader dat kwaliteitsbewuste versterkingsleer met verifieerbare beloningen (RLVR) gebruikt om grote taalmodellen te trainen op NP-moeilijke optimalisatieproblemen, waarbij aanzienlijke verbeteringen in oplossingskwaliteit en generalisatie over diverse redeneertaken worden aangetoond in vergelijking met bestaande modellen en benaderingen met binaire beloningen.

Oorspronkelijke auteurs: Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Yang Li, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen

Gepubliceerd 2026-05-12

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Yang Li, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een zeer slimme robotassistent hebt (een Large Language Model, of LLM) die uitstekend is in het beantwoorden van vragen zoals "Is dit wiskundeprobleem correct opgelost?" of "Heb ik dit woord goed gespeld?". Al lang trainen we deze robots door te zeggen "Goed gedaan!" als het antwoord juist is en "Probeer opnieuw" als het fout is. Dit is vergelijkbaar met het nakijken van een meerkeuzetoets waarbij er slechts één juist antwoord is.

Maar wat als de taak niet alleen gaat om het antwoord juist te krijgen, maar om het antwoord het beste te krijgen?

Dit is het probleem dat het artikel FORGE aanpakt. Het is alsof je de robot niet alleen vraagt om een route naar de supermarkt te vinden, maar om de kortste, snelste mogelijke route te vinden, zelfs als er miljoenen andere geldige routes zijn die gewoon langer duren.

Hier is een eenvoudige uiteenzetting van hoe ze dit hebben gedaan:

1. Het Probleem: "Voldoende" versus "Het Beste"

Stel je voor dat je een koffer inpakt.

Oude Methode (Binair Beloningssysteem): Je vraagt de robot om in te pakken. Als alles in de tas past, zeg je "Succes!". Als het overloopt, zeg je "Mislukt". De robot leert dan alleen maar om de items in te passen, zelfs als het de helft van de koffer leeg laat of zware items bovenop kwetsbare spullen legt.
De FORGE-Methode (Kwaliteitsbewuste Beloningen): Je vertelt de robot: "Succes is goed, maar als je meer spullen in dezelfde ruimte kunt passen, of het zo kunt ordenen dat het lichter is, krijg je een grotere beloning." De robot leert dan om te blijven proberen de inpakking te verbeteren totdat het perfect is.

Het artikel stelt dat huidige AI-modellen uitstekend zijn in het vinden van "geldige" oplossingen (zoals een route die werkt), maar slecht in het vinden van "optimale" oplossingen (de absolute beste route). Dit is een groot probleem voor echte wereldproblemen zoals logistiek, planning en netwerkontwerp, die bekend staan als NP-harde problemen (wiskundeproblemen die ongelooflijk moeilijk zijn om perfect op te lossen).

2. De Oplossing: De "Forge"-Fabriek

De auteurs bouwden een fabriek genaamd FORGE-ENGINE om deze robots te trainen om betere optimaliseerders te worden. Denk hierbij aan een sportschool voor het brein van de AI, maar in plaats van gewichten te tillen, lost het complexe puzzels op.

De fabriek heeft drie hoofdonderdelen:

De Generator: Deze machine creëert miljoenen oefenpuzzels. Het kan ze makkelijk maken (zoals een puzzel van 5 stukjes), gemiddeld, of moeilijk (zoals een puzzel van 1.000 stukjes).
De Validator: Dit is de strenge scheidsrechter. Het controleert of de oplossing van de robot daadwerkelijk de regels volgt (bijvoorbeeld: "Heb je elke stad precies één keer bezocht?").
De Heuristische Oplosser (Het Geheimzame Ingrediënt): Dit is het belangrijkste onderdeel. Het is een supersnel, traditioneel computerprogramma dat de puzzel bijna perfect oplost. Het fungeert als een "gouden standaard" of een coach.
- De Analogie: Stel je voor dat de robot een student is die een toets maakt. De Validator controleert of het antwoord correct is geschreven. De Heuristische Oplosser is de leraar die het antwoordblad heeft. Als de robot 80% van de punten haalt, zegt de leraar niet alleen "Fout". De leraar zegt: "Je hebt 80%. Probeer het tot 90% te brengen." Dit geeft de robot een continue score in plaats van een simpele "Geslaagd/Niet Geslaagd".

3. De Trainingsmethode: "De Berg Beklimmen"

Je kunt een robot niet direct in een puzzel van 1.000 stukjes gooien; het zou verward raken en opgeven. Daarom gebruikt het artikel een strategie genaamd Curriculum Learning:

Eenvoudige Fase: De robot lost kleine, simpele puzzels op om de regels te leren.
Gemiddelde Fase: De puzzels worden groter. De robot leert vooruit te plannen.
Moeilijke Fase: De robot neemt enorme, complexe puzzels aan.
De Herhaal-Truc: De auteurs merkten op dat als je alleen vooruitgaat (Eenvoudig → Moeilijk), de robot vergeet hoe het de makkelijke dingen moet doen. Daarom lieten ze de robot periodiek de makkelijke en gemiddelde niveaus herhalen. Dit houdt zijn vaardigheden scherp terwijl hij het moeilijke materiaal leert.

4. De Resultaten: Een Slimmer Brein

Ze testten hun nieuwe robot (genaamd FORGE) op 10 verschillende soorten moeilijke puzzels (zoals het plannen van de kortste route voor een bezorgvrachtwagen of het plannen van vergaderingen zonder conflicten).

De Score: De robot vond niet zomaar een oplossing; het vond geweldige oplossingen. Het versloeg het beroemde GPT-4o-model met een enorme marge. Terwijl GPT-4o ongeveer 62% van de tijd geldige oplossingen vond, deed FORGE dit 93% van de tijd. Belangrijker nog: de oplossingen van FORGE lagen veel dichter bij het "perfecte" antwoord.
Het Bonus-effect: Hier komt het coolste deel. Toen ze de robot trainden op deze moeilijke optimalisatiepuzzels, werd het niet alleen beter in puzzels. Het werd ook beter in alles anders.
- Het werd beter in wiskunde.
- Het werd beter in logica.
- Het werd beter in het volgen van instructies.
- De Analogie: Het is als het trainen van een schaker tot een grootmeester. In het proces worden ze niet alleen beter in schaken; ze worden ook beter in strategie, geduld en plannen in hun dagelijks leven. Het artikel suggereert dat het leren om te "optimaliseren" (de beste oplossing vinden) de AI een algemene vaardigheid leert van diep nadenken en het verfijnen van zijn antwoorden, wat het helpt bij allerlei taken.

Samenvatting

Het artikel introduceert FORGE, een nieuwe manier om AI te trainen. In plaats van AI alleen te leren het "juiste" antwoord te geven, leren ze het de beste mogelijke antwoord te vinden door het een constante score te geven over hoe goed zijn oplossing is. Dit verandert de AI in een meester-optimaliseerder die niet alleen moeilijke wiskundepuzzels beter oplost dan huidige topmodellen, maar ook slimmer wordt in algemeen redeneren, logica en het volgen van instructies.

Technische Samenvatting: FORGE-ENGINE

Probleemstelling

Hoewel Large Language Models (LLM's) via Reinforcement Learning met Verifieerbare Beloningen (RLVR) aanzienlijk succes hebben behaald in redeneerbenchmarks (wiskunde, coderen, logica), lijden bestaande evaluatieparadigma's aan een kritieke beperking: ze richten zich uitsluitend op correctheid (haalbaarheid) in plaats van optimaliteit. In veel real-world scenario's, zoals logistiek of toewijzing van middelen, is een louter "geldige" oplossing ontoereikend; het doel is om de oplossing te vinden die een objectieve functie maximaliseert of minimaliseert. Huidige benchmarks vertrouwen vaak op binaire beloningen (slagen/mislukken), die niet de dichte, continue feedback bieden die nodig is om modellen naar optimale oplossingen te leiden. Bovendien ontbreken er in bestaande NP-moeilijke benchmarks mechanismen om grondwahrheidsoptimale waarden te genereren, wat de berekening van fijnmazige beloningen verhindert en de training terugbrengt tot inefficiënte binaire feedbacklussen.

Methodologie: FORGE-ENGINE

De auteurs stellen FORGE-ENGINE voor, een uitgebreid framework ontworpen om LLM's te trainen en te evalueren op NP-moeilijke optimalisatieproblemen met behulp van Kwaliteitsbewuste RLVR. Het framework bestaat uit drie kerncomponenten:

1. Dataconstructiepijplijn

Het framework maakt gebruik van een schaalbare, vierstaps pijplijn om trainingsdata te genereren voor 10 verschillende NP-moeilijke taken die vijf categorieën bestrijken: Graph Clustering, Resource Scheduling, Graph Partitioning, Subset Selection en Path Planning.

Controleerbare Generatoren: Produceren oneindige instanties met gestructureerde moeilijkheidsgraden (Makkelijk, Gemiddeld, Moeilijk) met een "constructie-by-design"-aanpak om het bestaan van haalbare oplossingen te garanderen.
Op regels gebaseerde Verificators: Valideren automatisch de naleving van constraints en berekenen objectieve waarden, waardoor absolute correctheid wordt gegarandeerd zonder menselijke labeling.
Heuristische Oplossers: Een cruciale innovatie waarbij taakspecifieke heuristische algoritmen (bijv. multi-start nearest-neighbor met 2-opt voor TSP) bijna-optimale baselines berekenen voor elke instantie. Deze baselines dienen als grondwahrheid voor de berekening van beloningen.
Curriculumkalibratie: Moeilijkheidsniveaus worden empirisch gekalibreerd om doelwitsuccespercentages te bereiken (bijv. Makkelijk: 70-90%, Moeilijk: 10-40%) om progressief leren te faciliteren.

2. FORGE-BENCH

Een rigoureuze evaluatiebenchmark bestaande uit 1.000 hoog-complexe instanties (100 per taak), ontworpen om onbekend te zijn tijdens de training. In tegenstelling tot eerdere werken, evalueert het modellen met twee complementaire metrics:

Succespercentage (SR): Het percentage instanties waarbij het model een geldige oplossing genereert die aan alle constraints voldoet.
Kwaliteitsratio (QR): Een continue metric die de oplossingskwaliteit meet ten opzichte van de heuristische baseline (bijv. $QR = \text{Heuristisch} / \text{Model}$ voor minimalisatie). Dit onderscheidt tussen louter haalbare en bijna-optimale oplossingen.

3. Kwaliteitsbewuste RLVR Framework

De trainingsstrategie vervangt schaarse binaire signalen door fijnmazige, continue beloningen die zijn afgeleid van de heuristische baselines.

Beloningsfunctie: Een hiërarchisch beloningssysteem evalueert outputs op drie dimensies:
1. Format Beloning ( $R_{format}$ ): Zorgt voor gestructureerd redeneren (bijv. <thought> tags).
2. Haalbaarheidsbeloning ( $R_{feasibility}$ ): Straft constraintschendingen af (bijv. -1.5) en geeft de optimaliteitsscore voor geldige oplossingen.
3. Optimaliteitsbeloning ( $R_{optimal}$ ): Een continue score gebaseerd op de verhouding tussen de objectieve waarde van het model en de heuristische baseline, wat dichte feedback biedt voor optimalisatie.
Multi-stadium Curriculum Replay: Om het "cold start"-probleem en catastrofaal vergeten te mitigeren, hanteert de training een cyclische strategie (Makkelijk $\to$ Gemiddeld $\to$ Moeilijk) die meerdere keren door moeilijkheidsniveaus itereren, waardoor fundamentele vaardigheden worden versterkt terwijl er progressief complexe optimalisatie wordt aangepakt.

Belangrijkste Resultaten

Experimenten zijn uitgevoerd op Qwen2.5-7B-Instruct-1M, getraind op 15.000 voorbeelden (15K totaal over drie fasen).

In-Domein Prestaties: Het resulterende model, FORGE, behaalde een succespercentage van 93,1% en een kwaliteitsratio van 46,6% op FORGE-BENCH. Dit presteert aanzienlijk beter dan GPT-4o (62,1% SR, 36,2% QR) en overtreft substantieel de prestaties van het basismodel (29,6% SR, 14,6% QR).
Out-of-Domein (OOD) Generalisatie: Training op FORGE-ENGINE vertaalde zich naar diverse redeneertaken, wat resulteerde in winst in:
- Opvolging van instructies: +6,1%
- Kennisredeneren: +4,1%
- Wiskunde: +2,2%
- Logica: +1,2%
Ablatiestudies:
- Beloningsontwerp: Kwaliteitsbewuste beloningen verbeterden de oplossingskwaliteit met 28,8% ten opzichte van binaire beloningen, voorkwamen beloningshacking en leidden het model naar ware optimaliteit.
- Curriculumstrategie: Multi-stadium curriculum replay presteerde beter dan lineaire single-pass strategieën, brak prestatiedekkels en voorkwam stagnatie.
- Taakdiversiteit versus Hoeveelheid: De studie vond dat training op een diverse set van 10 taken betere generalisatie opleverde dan training op minder taken met meer data, wat suggereert dat blootstelling aan gevarieerde probleemstructuren een sleutelfactor is voor redeneercapaciteiten.
- RLVR versus SFT: Hoewel Supervised Fine-Tuning (SFT) op optimale oplossingen de in-domein prestaties verbeterde, leed het aan catastrofale OOD-degradatie (-12,0 punten). Daarentegen bevorderde RLVR robuuste, overdraagbare strategieën voor constraintvoldoening.

Betekenis en Claims

Het artikel stelt dat FORGE-ENGINE het eerste uitgebreide framework is dat RLVR succesvol toepast op NP-moeilijke optimalisatieproblemen door heuristische oplossers te integreren om fijnmazige optimaliteitsbeloningen te bieden.

De auteurs stellen dat dit werk de kloof overbrugt tussen haalbaarheid en optimaliteit in LLM-redeneren. Door verder te gaan dan binaire correctheid, stelt het framework modellen in staat om iteratieve optimalisatiezoektochten te ondernemen. Cruciaal biedt het artikel empirisch bewijs dat optimalisatietraining een overdraagbare "optimaliseringsmindset" bevordert – het vermogen om kandidaten te genereren en zichzelf te verfijnen – wat bredere redeneercapaciteiten verbetert die verder gaan dan de specifieke optimalisatietaken. De bevindingen suggereren dat voor het schalen van RLVR taakdiversiteit en kwaliteitsbewuste beloningen kritiekere factoren zijn dan pure datahoeveelheid.

Het werk wordt gepresenteerd als een fundamentele stap voor het integreren van LLM's met op optimalisatie gebaseerd redeneren, en biedt een schaalbare infrastructuur en benchmark voor toekomstig onderzoek in complex redeneren.