Technische Samenvatting: LLM-gestuurde Evolutionaire Zoektocht voor Herformulering van Constraint Modellen

Probleemstelling

Combinatorische problemen zijn alomtegenwoordig in industriële toepassingen en worden vaak gemodelleerd met behulp van Constraint Programming (CP). Hoewel Large Language Models (LLMs) het vermogen hebben getoond om correcte declaratieve constraint-modellen te genereren vanuit natuurlijke taal, garandeert correctheid alleen nog geen efficiëntie. Een model dat semantisch correct is, kan nog steeds computationeel duur zijn om op te lossen door suboptimale modelleringskeuzes (bijv. variabelen-perspectieven, constraint-formuleringen of coderingen). Het handmatig herformuleren van deze modellen om de solver-prestaties te verbeteren, is een kritieke flessenhals. Bestaande automatiseringsbenaderingen vertrouwen vaak op regelgebaseerde transformaties of het toevoegen van "streamliners" (aanvullende constraints) aan een vaste modelstructuur, in plaats van het uitvoeren van holistische herformuleringen die het perspectief of de variabelen-codering van het model veranderen.

Methodologie

De auteurs stellen een LLM-gestuurd evolutionair zoekframework voor, gericht op prestatiegerichte herformulering van constraint-modellen. Geïnspireerd door Automatic Heuristic Design (AHD), genereert, evalueert en selecteert het systeem iteratief modelherformuleringen.

Kernworkflow

1. Initialisatie: Een basismodel ($B$) wordt vastgesteld en de runtime-prestaties ervan worden gemeten op een trainingsset ($D_{tr}$).
2. Iteratieve Loop: Voor $T$ iteraties:
   • Context Selectie: Een zoekstrategie ($\sigma$) selecteert een subset van eerdere pogingen (ratio, model en feedback) om de prompt-context ($R_t$) te vormen.
   • Generatie: De LLM ontvangt een prompt met de taakbeschrijving, het basismodel, de runtime-historie en de geselecteerde context. Het produceert een ratio ($\rho_t$) en een kandidaat-model ($m_t$).
   • Evaluatie: De kandidaat wordt uitgevoerd op $D_{tr}$. De evaluator controleert de oplosbaarheid van de oplossing (om er zeker van te zijn dat het antwoord van de kandidaat overeenkomt met het antwoord van het basismodel voor dezelfde instantie) en meet de totale runtime.
   • Historie Update: De poging wordt opgenomen in de historie $H_t$.
3. Finale Selectie: Nadat de zoektocht eindigt, worden alle geldige oplossingen geëvalueerd op een aparte validatieset ($D_{val}$). Het model met de laagste totale runtime op $D_{val}$ wordt als definitieve output geselecteerd. Deze stap is cruciaal om overfitting op de trainingsinstanties te voorkomen.

Zoekstrategieën

Het artikel vergelijkt tien strategieën voor het selecteren van de context $R_t$ die aan de LLM wordt verstrekt:

• Baselines: Sampling (geen context), Full-history (alle eerdere pogingen), Last-k (recentheid) en Top-k (kwaliteit/snelheid).
• Hybride: Combineert recentheid en kwaliteit.
• Evolution of Heuristics (EoH): Houdt een populatie van modellen bij en gebruikt specifieke operatoren (bijv. "distinct approach", "compatible combination") om generatie te sturen, met en zonder prestatiefeedback.
• Profile-Diverse Retention (PDR): Een nieuwe strategie die in dit werk wordt geïntroduceerd. PDR streeft expliciet naar gedragsmatige diversiteit. Het representeert elk model als een vector van genormaliseerde runtimes over de trainingsinstanties. Het gebruikt Maximal Marginal Relevance (MMR) om een set pogingen te selecteren die zowel snel zijn (hoge kwaliteit) als gedragsmatig onderscheidend (lage gelijkenis in runtime-profielen) van elkaar.

Experimentele Opzet

• Benchmarks: Acht verzadigingsproblemen uit CSPLib (bijv. Tail Assignment, Car Sequencing, Covering Arrays).
• Model: DeepSeek V4 Flash (1M token context).
• Solver: OR-Tools CP-SAT via CPMpy.
• Metrieken: Geometrisch Gemiddelde (GM) van de versnellingen op de uitgesloten testinstanties ($D_{test}$), gebruikmakend van PAR2 (penalized average runtime) voor timeouts.

Belangrijkste Bijdragen

1. Evolutionair Framework: Een aanpassing van AHD specifiek voor de volledige modelherformulering van declaratieve CP-modellen, waardoor de LLM in staat is om perspectieven, variabelen en coderingen te veranderen, in plaats van alleen extra constraints toe te voegen.
2. Profile-Diverse Retention (PDR): Een contextselectiestrategie die MMR toepast op instantie-niveau runtime-vectoren. Het behoudt pogingen die snel zijn maar verschillende oplosgedragingen vertonen, met als doel de zoekruimte te diversifiëren voorbij eenvoudige recentheids- of kwaliteitsmetrieken.
3. Systematische Evaluatie: Een uitgebreide vergelijking van tien zoekstrategieën over acht problemen, waarbij wordt aangetoond dat het behouden van een diverse context beter presteert dan strategieën die alleen de meest recente of snelste pogingen behouden.
4. Validatie-gebaseerde Selectie: De introductie van een validatie-gebaseerde finale modelselectiestap (vaak afwezig in AHD-pipelines) laat consequent zien de prestaties op uitgesloten data te verbeteren en overfitting te beperken.

Resultaten

• Prestatiewinst: De evolutionaire zoektocht produceert substantiële versnellingen op uitgesloten testinstanties. De beste strategie (Pluis) behaalde een geometrisch gemiddelde versnelling van 2,26× over alle problemen, met specifieke instanties die winsten tot 250,7× lieten zien (op Covering Arrays).
• Diversiteit telt: Strategieën die een diverse context behouden (PDR, EoH met feedback) presteren over het algemeen beter dan strategieën die enkel vertrouwen op recentheid (Last-1) of kwaliteit (Top-1). PDR presteerde 1,30× beter dan de kwaliteit-gebaseerde Top-5 strategie.
• Whole-Model vs. Streamliners: De voorgestelde volledige modelherformuleringsaanpak presteerde aanzienlijk beter dan een aangepaste baseline die alleen additieve streamliners genereert (StreamLLM-single), die slechts een 1,02× versnelling behaalde.
• Kostenefficiëntie: Hoewel Sampling de meeste tokens genereerde, bleef Full-history kosteneffectief dankzij KV-caching. PDR leverde de hoogste versnelling tegen een lagere kosten dan Sampling.
• Betrouwbaarheid: Geen van de geselecteerde modellen gaf ongeldige antwoorden of foutieve "onvervulbaar"-resultaten op testinstanties. Validatie-gebaseerde selectie filterde succesvol kandidaten uit die overfitten op de trainingsdata.

Betekenis en Claims

Het artikel claimt dat iteratieve herformulering gestuurd door LLM's de ontdekking van hoogwaardige constraint-modellen kan automatiseren, waarbij significante versnellingen worden behaald zonder menselijke tussenkomst. Het benadrukt dat gedragsmatige diversiteit in de zoekcontext een cruciale factor is voor succes, die traditionele metrieken zoals recentheid of ruwe snelheid overtreft.

De auteurs merken bescheiden op dat hoewel de resultaten veelbelovend zijn, de studie beperkt is tot één enkele LLM, één solver-configuratie en acht specifieke verzadigingsproblemen. Zij suggereren dat toekomstig werk optimalisatieproblemen, andere solvers en meer expliciete, solver-rijke feedback (zoals conflict-counts, zoekboomdiepte) kan verkennen om de diversiteitsmetrieken verder te verfijnen. Dit werk positioneert zich als een stap richting de automatisering van de "heilige graal" van constraint-modellering, waarbij de focus verschuift van louter correctheid naar prestatiegerichte automatisering.