Technische Samenvatting: Distributie-bewust Algoritmisch Ontwerp met LLM-agenten

Probleemstelling

Dit artikel adresseert een lacune in de klassieke leertheorie waarbij het geleerde object een uitvoerbare solver-code is in plaats van een voorspellend model. In traditionele settings wordt generalisatie gemeten aan de hand van nauwkeurigheid (correctheid). Wanneer de output echter een algoritme is, kunnen twee solvers beide geldige oplossingen teruggeven op een implementatiedistributie, maar toch aanzienlijk verschillen in runtime. De auteurs betogen dat voor uitvoerbare procedures generalisatie zowel oplossingskwaliteit als berekening moet omvatten.

De kernuitdaging is distributie-bewust programmaleeren: gegeven steekproeven uit een onbekende implementatiedistributie $D$, moet de leerder solver-code teruggeven die is gespecialiseerd voor $D$. Het doel is niet louter het oplossen van de omringende probleemklasse (bijv. algemene SAT of TSP), maar het leren van een algoritme wiens uitvoering is geoptimaliseerd voor de specifieke structurele regelmatigheden van het doelregime. Dit bevindt zich tussen worst-case algoritmisch ontwerp (dat geen distributie-informatie aanneemt) en gemiddelde-complexiteit (die een analytische beschrijving van de distributie aanneemt).

Methodologie: De Solver-hint Abstractie

Het artikel introduceert een centrale abstractie genaamd een solver-hint: een herbruikbare structuur die wordt afgeleid uit steekproeven en wordt gecompileerd tot gespecialiseerde solver-code. Het leerproces wordt gefactoreerd als $S \mapsto \hat{h}_S \mapsto \hat{c}_S = \text{Comp}(\hat{h}_S)$, waarbij:

1. $S$: Een steekproef van instanties uit de onbekende distributie.
2. $\hat{h}_S$: Een solver-hint (bijv. een backdoor-set in SAT, een latente decompositie in grafen, of een patroon van resource-bottlenecks).
3. $\text{Comp}(\hat{h}_S)$: Een gecompileerde solver die deze hint benut.

Cruciaal is dat het framework correctheid scheidt van geleerde berekening. Correctheid wordt vaak gegarandeerd door een fallback naar een complete, generieke solver. De steekproef wordt uitsluitend gebruikt om te identificeren welke computatiekorte weg moet worden gecompileerd, waardoor de runtime op toekomstige instanties wordt verminderd.

LLM-synthesepijplijn

De auteurs instantiëren dit framework met LLM-code-agenten. Het syntheseproces omvat voor elke kandidaat drie sequentiële stadia:

1. Hypothese ($H_c$): De agent stelt een gestructureerde beschrijving in natuurlijke taal voor van een vermoedelijke distributieregel (bijv. "latente Boolese regels" of "geplante paletten").
2. Analyse ($A_c$): Een train-tijd programma dat de hint schat uit de publieke trainingssteekproef, en een compacte, herbruikbare samenvatting produceert (de empirische hint).
3. Solver ($s_c$): Een deploy-tijd programma dat een nieuwe instantie en de herstelde samenvatting neemt om een oplossing te produceren.

Het systeem maakt gebruik van een beam search over kandidaten. Het verfijnt, splitst of vervangt kandidaten iteratief op basis van validatiemetrics (kwaliteit, optimaliteit en runtime). Diversiteit wordt behouden door "diversiteitssleutels" (brede verklarende klassen) bij te houden om ervoor te zorgen dat de zoektocht verschillende structurele hypothesen verkent.

Theoretische Bijdragen

Het artikel biedt formele garanties voor twee regimes:

1. Runtime-bewuste ERM over een Vaste Bibliotheek:
   De auteurs bewijzen dat als een solver-bibliotheek $\mathcal{C}$ vaststaat, de empirisch snelste steekproef-consistente solver generaliseert in zowel correctheid als runtime. Specifiek nadert met hoge waarschijnlijkheid de runtime van de geselecteerde solver de beste correcte distributie-gespecialiseerde solver in de klasse, tot op een term die afhankelijk is van de bibliotheekgrootte en het aantal steekproeven. Dit vestigt dat empirische runtime-minimalisatie een geldige strategie is voor het identificeren van distributie-specifieke solvers wanneer de specialisatie in de bibliotheek bestaat.

2. Synthese via Leerbare Hints:
   Voor rijkere settings waarin de specialisatie niet vooraf wordt opgesomd, modelleert het artikel het herstel van een hint uit een eindige hint-ruimte $\mathcal{H}$. Onder een realiseringsaanname (de ware distributie komt overeen met een zekere $h^* \in \mathcal{H}$) en een randvoorwaarde (de ware hint is statistisch onderscheidbaar van anderen), bewijst het artikel dat $O(\frac{1}{\gamma^2} \log \frac{|\mathcal{H}|}{\delta})$ steekproeven voldoende zijn om de juiste hint te herstellen met hoge waarschijnlijkheid.

   • Concreet Voorbeeld: Het artikel beschrijft een Hidden SAT Backdoor-model. Hier is de hint een set variabelen die, wanneer vastgezet, de formule reduceren tot een hanteerbare klasse. De theorie toont aan dat een salientiestatistiek deze backdoor kan identificeren uit steekproeven, waardoor de gecompileerde solver een exponentiële snelheidswinst bereikt op de implementatiedistributie terwijl correctie via fallback wordt behouden.

Experimentele Resultaten

De auteurs evalueerden het framework op 21 gestructureerde combinatorisch-optimale doel-distributies over zeven probleemklassen: Graph Coloring, MAXSAT, Maximum Independent Set (MIS), Minimum Dominating Set (MDS), Packing LP, Multidimensionale Knapsack (MDKP) en Traveling Salesperson Problem (TSP).

Belangrijkste Prestatiemetrics

• Kwaliteit: De gesynthetiseerde solvers behaalden een gemiddelde genormaliseerde kwaliteit van 0,971. Dit vertegenwoordigt een verbetering van +0,224 ten opzichte van het gemiddelde heuristische pool en +0,098 ten opzichte van de heuristiek met de hoogste kwaliteit.
• Runtime: De gesynthetiseerde solvers waren aanzienlijk sneller dan baselines:
  • 336,9× sneller dan de heuristiek met de beste kwaliteit.
  • 342,8× sneller dan Gurobi (met een tijdslimiet van 10 seconden).
  • 16,1× sneller dan de geselecteerde exacte backend met tijdslimiet.
• Externe Validatie (PACE 2025): Op vrijgegeven privé-instanties van het Dominating Set-probleem was de gesynthetiseerde solver geldig op alle 100 grafen en liep ongeveer twee ordes van grootte sneller dan de topwedstrijdsolvers (bijv. Fontan–Verger, Root), hoewel met een gematigde kwaliteitskloof (oplossingsgrootte ~3,3% groter).

Mechanisme van Verbetering

Analyse van de gegenereerde code onthult dat winsten voortkomen uit het veranderen van de computatieschaal. De gesynthetiseerde solvers vervangen vaak omringende exponentiële zoektocht of algemeen doelgerichte optimalisatie door lagere-orde, distributie-specifieke berekeningen. Voorbeelden zijn:

• Vervanging van $O^*(2^n)$ zoektocht door template-verificatie en begrensd herstel.
• Het gebruik van dichtheidsortering voor actieve resources in Packing LP in plaats van volledige LP-oplossing.
• Het benutten van latente geometrische structuren in TSP om rondreizen te construeren zonder volledige dynamische programmering.

Betekenis en Claims

Het artikel claimt een constructieve route naar distributie-specifieke hanteerbaarheid te bieden. In tegenstelling tot gesmoorde analyse of geparametriseerde complexiteit, die vertrouwen op handontworpen routes, leert dit framework de route direct uit steekproeven.

De auteurs benadrukken dat het geleerde object dichter bij een gespecialiseerd algoritme voor het implementatieregime staat dan bij een afgestemde heuristiek voor geïsoleerde instanties. De "solver-hint" dient als een herbruikbare beschrijving van distributie-specifieke structuur die de kosten van inferentie afstoot: een eenmalige synthesekost tegenover steekproeven levert een solver op met lagere kosten per instantie.

Het werk is bescheiden in zijn scope: het claimt niet de omringende probleemklassen in het worst-case scenario op te lossen. In plaats daarvan toont het aan dat voor gestructureerde distributies, steekproeven herbruikbare shortcuts kunnen onthullen die het LLM-agenten mogelijk maken solvers te compileren die zowel uiterst nauwkeurig als dramatisch sneller zijn dan state-of-the-art algemeen doelgerichte tools. Het framework benadrukt dat runtime een leerbare eigenschap is wanneer de implementatiedistributie toegankelijk is via steekproeven.