Technische Samenvatting: Formaliseer, Optimaliseer niet: De Heuristische Valstrik in door LLM's gegenereerde Combinatoire Oplossers

Probleemstelling

Grote Taalmodellen (LLM's) worstelen met het oplossen van complexe combinatorische problemen via directe autoregressieve redenering vanwege de "redeneerflesnek" die inherent is aan het navigeren door grote zoekruimtes en het handhaven van globale consistentie over lange-termijn beperkingen. Hoewel recente neuro-symbolische benaderingen proberen dit te mitigeren door LLM's te laten synthetiseren uitvoerbare oplossers, blijven twee kritieke ontwerpvragen onopgelost:

1. Representatie: Hoe moet de LLM de oplossing vertegenwoordigen? Is een native algoritmische aanpak (Python) superieur aan declaratieve modellering (MiniZinc) of integratie van oplosser-API's (Python + OR-Tools)?
2. Optimalisatie: Moet de LLM worden geprompt om actief het zoekproces te optimaliseren (bijvoorbeeld via heuristieken, pruning of grenzen), of moet het probleem strikt formaliseren voor een geverifieerde backend?

Vorig werk evalueert deze instellingen vaak geïsoleerd of op een aggregatieniveau van het probleem, waardoor het falen om uitkomsten op instance-niveau te ontleden in correctheid, schema-validiteit en betrouwbaarheid. Bovendien is de impact van op efficiëntie gerichte prompting op de betrouwbaarheid van gegenereerde oplossers niet systematisch geauditeerd.

Methodologie

De auteurs introduceren CP-SynC-XL, een benchmark die het CP-SynC-dataset uitbreidt met 100 heterogene Constraint Satisfaction Problems (CSP's) en Constraint Optimization Problems (COP's), in totaal 4.577 geparametriseerde instances. De studie evalueert drie frontier LLM's (GPT-5.3-CODEX, GEMINI 3.1 PRO, DEEPSEEK-V3.2) over drie paradigma's voor het bouwen van oplossers:

1. Native Algoritmische Zoek (Python): De LLM genereert een zelfstandig Python-algoritme dat uitsluitend de standaardbibliotheek gebruikt, waarbij het volledige zoekproces wordt ontworpen (bijvoorbeeld branch-and-bound, DP).
2. Constraint Modellering via Python API (Python + OR-Tools): De LLM codeert variabelen, beperkingen en doelen met behulp van de OR-Tools CP-SAT Python API, en delegeert de zoekopdracht aan de oplosser.
3. Declaratieve Constraint Modellering (MiniZinc + OR-Tools): De LLM genereert een MiniZinc-model, dat vervolgens wordt gecompileerd en opgelost door dezelfde OR-Tools CP-SAT backend.

De studie hanteert een gecontroleerd factorieel ontwerp waarbij een baseline prompt (alleen vragen om correctheid) wordt vergeleken met een heuristische prompt (expliciet verzoek om op efficiëntie gerichte ontwerpen, zoals strakkere grenzen, pruning of zoekannotaties).

De evaluatiepijplijn omvat:

• Verfijningsprotocol: Een iteratief verfijningslus van vier rondes waarbij mislukte runs (crashes, time-outs, formaatfouten) teruggekoppeld worden naar de LLM.
• Metingen:
  • Provided: Fractie van instances die een schema-conforme output teruggeven.
  • Correct: Fractie van provided outputs die de referentie-verifier doorstaan.
  • Fidelity: De ratio van Correct/Provided (het aandeel van teruggegeven oplossingen dat daadwerkelijk geldig is).
• Code-niveau Audit: Een gepareerde analyse van baseline versus heuristische oplossers om specifieke faalmodi en codepatronen te identificeren.

Belangrijkste Bijdragen

1. De CP-SynC-XL Benchmark

De auteurs introduceren een grootschalige benchmark (4.577 instances) die is ontworpen om door LLM's gesynthetiseerde oplossers op instance-niveau te evalueren, waarbij provided outputs worden gescheiden van geverifieerde correctheid om conditionele betrouwbaarheid te meten.

2. Representatieve Divergentie

De studie onthult een significante divergentie in oplosserprestaties gebaseerd op het modelleringssurface, zelfs wanneer de onderliggende oplosser-backend (OR-Tools CP-SAT) identiek is:

• Python + OR-Tools bereikt de hoogste absolute correctheid over alle LLM's heen.
• MiniZinc + OR-Tools vertoont een lagere absolute dekking (meer "geen oplossing" time-outs) ondanks dezelfde backend, wat wijst op een bottleneck in de vlotheid van de LLM met het declaratieve surface in plaats van de capaciteit van de oplosser.
• Native Python heeft het hoogste percentage "stille fouten" – het teruggeven van schema-geldige oplossingen die de verificatie falen – wat aangeeft dat LLM's worstelen met het ontwerpen van complete, sound zoekalgoritmes vanaf nul.

3. De Heuristische Valstrik

Het artikel identificeert een "heuristische valstrik" waarbij het prompten van LLM's om zoekopdrachten te optimaliseren onbetrouwbare resultaten oplevert:

• Marginaal Voordeel, Hoog Risico: Heuristische prompts produceren slechts kleine mediane snelheidswinsten (1,03–1,12×) maar veroorzaken een sterk bimodaal effect. Hoewel sommige instances sneller worden, vertragen veel andere, en daalt de correctheid scherp bij een lange staart van problemen.
• Zes Faalmodi: Een code-niveau audit identificeert zes paradigma-specifieke faalmodi die worden geactiveerd door heuristische prompts:
  • Ongeverifieerde Grenzen (Python + OR-Tools): LLM's injecteren "strakke" grenzen die geen stellingen zijn, wat leidt tot onhaalbaarheid.
  • Verzwakte Propagatie (Python + OR-Tools): Semantisch equivalente herschrijvingen (bijvoorbeeld Big-M) die de propagatie-engine van de oplosser lamleggen.
  • Harde Seeding (Python + OR-Tools): Het omzetten van heuristische kandidaten in harde beperkingen, waardoor haalbare gebieden worden verwijderd.
  • Verlies van Volledigheid (Python): Het vervangen van volledige zoek door incomplete lokale zoek of iteratiecaps.
  • COP→SAT Ineenstorting (MiniZinc): Onjuist aannemen van een optimale waarde en het omzetten van optimalisatie naar satisfactie.
  • Redundante Machine (MiniZinc): Het toevoegen van excessieve hulpbeperkingen die het afvlakkingsproces van de oplosser overweldigen.

Resultaten

• Correctheid Ranking: Python + OR-Tools > Python ≳ MiniZinc + OR-Tools. Het delegeren van zoek naar een geverifieerde backend (CP-SAT) presteert aanzienlijk beter dan native algoritmisch ontwerp.
• Fidelity Ranking: MiniZinc + OR-Tools > Python + OR-Tools > Python. Wanneer een oplossing wordt aangeboden, zijn MiniZinc-modellen het meest waarschijnlijk correct (hoogste conditionele betrouwbaarheid) omdat het typesysteem en de checks voor goedvorming van de taal veel coderingsfouten filteren voordat de oplosser draait. Native Python is het minst betrouwbaar, vaak met het teruggeven van zelfverzekerde maar incorrecte oplossingen.
• Impact van Heuristiek: Bij sterkere LLM's (GPT-5.3-CODEX, GEMINI 3.1 PRO) leveren heuristische prompts marginale, inconsistente winsten op (±3,6 procentpunten). Bij zwakkere LLM's (DEEPSEEK-V3.2) veroorzaken heuristische prompts significante degradatie (bijvoorbeeld -7,4 pp correctheid op Python + OR-Tools).
• Foutanalyse: De dominante baseline faalmodus is UNSAT (de oplosser geeft een oplossing terug die door de referentie-verifier wordt afgewezen), voornamelijk veroorzaakt door vertaalfouten van natuurlijke taal naar formele taal (bijvoorbeeld het laten vallen van beperkingen, verkeerd interpreteren van outputschema's). Heuristische prompts verergeren dit door het introduceren van ongeverifieerde grenzen en het overbeperken van het model.

Betekenis en Ontwerpprincipes

Het artikel stelt dat de primaire bottleneck voor door LLM's gegenereerde combinatorische oplossers vlotheid van het modelleringssurface is, en niet de capaciteit van de onderliggende oplosser. De bevindingen ondersteunen een conservatief ontwerpprincipe:

"Formaliseer, Optimaliseer niet."

LLM's moeten primair worden gebruikt om variabelen, beperkingen en doelen te formaliseren voor geverifieerde oplossers. Pogingen om LLM's zoekoptimalisaties te laten genereren (heuristieken, grenzen, pruning-strategieën) moeten met scepsis worden behandeld. Het artikel concludeert dat elke door een LLM geschreven zoekoptimalisatie onafhankelijk moet worden gevalideerd voordat deze wordt gebruikt, aangezien de "heuristische valstrik" vaak ongeverifieerde grenzen of algoritmische substituties introduceert die zowel correctheid als betrouwbaarheid verminderen. De meest betrouwbare strategie is de LLM dicht bij het formalisatie-interface te houden en te vertrouwen op de native machine van de oplosser voor de zoekopdracht.