Technische Samenvatting: Voorbij Inference-Time Search

1. Probleemstelling

Huidige Large Language Models (LLM's) behandelen combinatorische optimalisatie doorgaans als een procedure tijdens de inferentie, waarbij elke probleeminstantie afzonderlijk wordt opgelost via sampling, search of herhaald prompting. Dit paradigma brengt een "marginale kost" van redenering met zich mee voor elke nieuwe query. De auteurs onderzoeken of Reinforcement Learning (RL) deze redeneringskost kan verschuiven naar de gewichten van het model, waardoor de synthese van een herbruikbare solver voor een hele probleemfamilie mogelijk wordt, in plaats van het genereren van oplossingen per instantie.

De studie richt zich op Synergistic Dependency Selection (SDS), een gecontroleerde, sterk NP-hard variant van het Quadratic Knapsack Problem. SDS is ontworpen als een "misleidend" optimalisatielandschap waarin:

• Lokale signalen in strijd zijn met globale optimaliteit: Quadratische interactietermen domineren lineaire gewichten, waardoor greedy heuristieken falen.
• Strikte haalbaarheidsbeperkingen: Oplossingen moeten voldoen aan cardinaliteit, volgorde, wederzijdse uitsluiting en groepslimieten.
• Template retrieval versus operationalisatie: Hoewel basismodellen vaak de syntaxis van geschikte solvers kunnen ophalen (bijv. Simulated Annealing), slagen ze er vaak niet in om de uitvoerbare logica correct te implementeren (bijv. verkeerd toepassen van acceptatieregels).

Het artikel behandelt drie kernonderzoeksvragen:

1. Competence Wall: Kan uitgebreide sampling tijdens de testfase (Best-of-N) de prestaties van een RL-getrainde policy herstellen in misleidende landschappen, of stuit het basismodel op een plafond?
2. Semantische Reparatie: Wanneer RL slaagt, scherpt het dan enkel de frequentie van correcte oplossingen, of repareert het uitvoerbare algoritmische logica die naïeve sampling niet kan herstellen?
3. Geamortiseerde Solver Synthese: Kan optimalisatie tijdens de trainingsfase redenering distilleren tot een lichtgewicht, herbruikbaar programma dat beter presteert dan herhaalde search per instantie?

2. Methodologie

De auteurs stellen Hero voor, een policy die is fine-gefine-tuned met Group Relative Policy Optimization (GRPO) op het Qwen2.5-Coder-14B-Instruct-model. De aanpak is bewust minimalistisch, waarbij veelvoorkomende stabilisatoren (zoals KL-penaliteiten, oracle-ankering) worden verwijderd om de effecten van een recept dat prioriteit geeft aan haalbaarheid te isoleren.

Belangrijkste Componenten:

• Gestructureerde Systeemprompt: De prompt dwingt een redeneerlus van "Deconstrueren-Hypothese-Kritiek" af. Het waarschuwt het model expliciet voor greedy heuristieken en moedigt het ontwerpen van search-strategieën aan die exploratie en exploitatie in evenwicht brengen.
• Hiërarchisch Reward Ontwerp: Een samengestelde reward $r(o)$ prioriteert structurele naleving boven ruwe optimaliteit:
  • Formaat & Uitvoering ($R_{exec}$): Zorgt voor geldige Python-syntaxis, schema-conformiteit en graaf-theoretische structuur. Cruciaal bevat het een anti-lazy sorting penalty om de neiging van het voorgetrainde model te onderdrukken om lineaire greedy heuristieken te gebruiken die quadratische interacties negeren.
  • Haalbaarheids-gesloten Optimaliteit ($R_{nom}$): Het primaire optimalisatiesignaal is strikt afgesloten. Als een oplossing een harde beperking schendt (cardinaliteit, volgorde, enz.), is de reward nul, ongeacht de objectieve score. Dit dwingt de policy om prioriteit te geven aan het voldoen aan beperkingen voordat het de objectieve functie optimaliseert.
• Trainingsregime: Het model wordt getraind gedurende 90 globale stappen op 12 NVIDIA GH200 GPU's, waarbij slechts ongeveer 4,5% van een volledige prompt-level epoch wordt waargenomen, maar er 23.040 redeneersporen worden gegenereerd.

3. Belangrijkste Bijdragen

De bijdragen van het artikel zijn empirisch en mechanistisch van aard, eerder dan algoritmisch:

1. Identificatie van een Competence Wall: Onder identiek prompting satureren Best-of-64 samples van het basismodel op een gaping van 28,7% ten opzichte van de Virtual Best Solver (VBS). Hoewel het basismodel oppervlakkig geschikte solver-templates ophaalt (bijv. 21,9% van de unieke basiscodes lijken op Simulated Annealing), faalt het om deze correct te operationaliseren.
2. Demonstratie van Semantische Reparatie: De RL-getrainde policy (Hero) convergeert in 99,8% van de haalbare outputs naar een haalbaarheidsbewuste Simulated Annealing-template. Het repareert de "Global Best Bug" die voorkomt in samples van het basismodel, waarbij de acceptatielogica buren onjuist vergelijkt met de lopende globale beste in plaats van met de huidige staat. Deze correctie maakt echt annealing-gedrag mogelijk.
3. Validatie van Geamortiseerde Solver Synthese:
   • Prestatie: Hero bereikt een gaping van 5,0% ten opzichte van VBS, wat significant beter is dan het basismodel en klassieke heuristieken zoals Local Search (10,0% gaping).
   • Efficiëntie: Hero is 91× goedkoper in uitvoerings/search-kosten na generatie in vergelijking met de cumulatieve kosten van Best-of-64 evaluatie.
   • Herbruikbaarheid: Een "compile-once" evaluatie toont aan dat een enkele bevroren solver, gegenereerd per seed, zeer concurrerend blijft (97,87% slaagpercentage, 4,34% gaping) wanneer deze onveranderd wordt hergebruikt over de hele testset, wat bewijst dat het model een herbruikbaar artefact synthetiseert in plaats van een generator per instantie.

4. Resultaten en Ablaties

• Hoofdprestatie: Hero bereikt een slaagpercentage van 97,8% en een gaping van 5,0% ten opzichte van VBS. Het presteert beter dan de verfriste ShinkaEvolve-baseline (die sterke proprietaire modellen gebruikt tijdens de deployment) en benadert de prestaties van CP-SAT (1,0% gaping) terwijl het 6,3× sneller is in uitvoering.
• Ablatiestudies:
  • Structurele Scaffolding: Het verwijderen van de structurele reward (anti-lazy sorting en graaf-structuurcontroles) zorgt ervoor dat de prestaties instorten tot een gaping van 34,7%, aangezien het model terugvalt op broze greedy heuristieken.
  • Haalbaarheidspoort: Het vervangen van de harde haalbaarheidspoort door een zachte penalty degradeert de prestaties aanzienlijk (57,4% slaagpercentage versus 97,8%), wat bevestigt dat de harde poort noodzakelijk is om modale instorting naar ongeldige oplossingen te voorkomen.
  • Oracle/Variatie: Het toevoegen van oracle-ankering of variatie-penaliteiten degradeert de prestaties, wat suggereert dat spaarzame, haalbaarheidsgerichte feedback effectiever is dan dichte uitkomstvorming in dit domein.
• Generalisatie:
  • Geen Catastrofaal Vergeten: Het model behoudt algemene codeer-capaciteiten (HumanEval Pass@1: 80,9% versus Basis 82,3%).
  • Cross-Domein: Het toepassen van hetzelfde recept op Job Shop Scheduling (JSSP) levert positieve resultaten op (99,3% slaagpercentage, 6,12% gaping), hoewel de auteurs opmerken dat dit een nauwere bewijslast is van transfer in plaats van bewijs van domein-agnostische robuustheid.

5. Betekenis en Claims

Het artikel claimt aan te tonen dat RL een code-LLM kan verplaatsen van een regime van search per instantie naar synthese van herbruikbare solvers. De betekenis ligt in de bevinding dat RL niet slechts fungeert als een "distributie-scherper" (het verbeteren van de efficiëntie om bestaande oplossingen te vinden), maar als een functionele compiler die uitvoerbare logica repareert (bijv. het herstellen van de Metropolis acceptatieregel) die naïeve sampling niet betrouwbaar kan herstellen.

De auteurs benadrukken dat dit succes berust op een gedisciplineerde, haalbaarheidsgerichte scaffolding in plaats van een universeel recept. De methode is afhankelijk van specifieke ontwerpkeuzes, zoals de harde haalbaarheidspoort en structurele penaliteiten, en is gevoelig voor reward-normalisatie. Het werk suggereert dat voor complexe, misleidende optimalisatielandschappen de "redenering" die nodig is om een solver te bouwen, kan worden gedistilleerd naar de gewichten van het model, waardoor een inzetbaar artefact ontstaat dat aanzienlijk efficiënter is dan herhaalde search tijdens de inferentie.