Technische Samenvatting: Large Language Models als Optimalisatoren

Probleemstelling

Reële optimalisatieproblemen ontstaan vaak uit natuurlijke taalbeschrijvingen (bijv. logistieke beperkingen, experimentele doelen) die vertaald moeten worden naar formele wiskundige programma's voordat traditionele solvers (bijv. Gurobi, CPLEX, Z3) deze kunnen verwerken. Hoewel Large Language Models (LLM's) veelbelovend zijn gebleken bij het overbruggen van deze kloof, stuit hun toepassing in complexe wiskundige optimalisatie op aanzienlijke hindernissen. De kernuitdaging ligt in het navigeren door de afweging tussen de flexibiliteit van directe LLM-redenering en de wiskundige strengheid van externe solvers, vooral naarmate de complexiteit van de problemen toeneemt. Huidige architecturen worstelen met een "redeneergat" (reasoning gap), waarbij LLM's vertrouwen op patroonherkenning in plaats van op werkelijke algoritmische redenering, wat leidt tot formulatiefouten die blijven bestaan zelfs wanneer solvers code uitvoeren zonder syntactische fouten.

Methodologie: Drie Paradigma's

De survey categoriseert LLM-gebaseerde optimalisatie in drie onderscheidende paradigma's, elk met unieke mechanismen en prestatiekenmerken:

1. Directe Optimalisatie

In dit paradigma fungeert de LLM zelf als de optimalisator, waarbij het de oplossingsruimte navigeert zonder externe solvers.

• Mechanisme: Het model genereert kandidaat-oplossingen, ontvangt feedback over objectiefwaarden en verfijnt deze iteratief met behulp van promptingstrategieën zoals Chain-of-Thought (CoT), Tree-of-Thought (ToT) en iteratieve prompting (bijv. OPRO, SGE).
• Evolutie: De aanpak is geëvolueerd van eenvoudige prompting naar fine-tuning (bijv. E2E CO Solver, LLaMoCo), waarbij modellen optimalisatieheuristieken internaliseren via supervised fine-tuning (SFT) en reinforcement learning (RL) in plaats van vanaf nul te redeneren.
• Scope: Effectief voor slecht gestructureerde problemen en settings met dure evaluaties (bijv. hyperparameter tuning, chemische synthese) waar domeinkennis de zoektocht versnelt.

2. Tool-Augmented Optimalisatie (Tool-versterkte Optimalisatie)

Hier fungeert de LLM als een vertaler en orchestrator, die natuurlijke taal omzet in formele specificaties (LP, MILP, SAT) die naar externe solvers worden verzonden.

• Mechanisme: De workflow volgt een pijplijn: Natuurlijke Taal $\rightarrow$ LLM Formulering $\rightarrow$ Solver Code $\rightarrow$ Executie $\rightarrow$ Foutfeedback. Geavanceerde systemen maken gebruik van multi-agent architecturen (Formulator/Programmer/Evaluator) of data-centrische fine-tuning (bijv. ORLM, SIRL) om de nauwkeurigheid van de formulering te verbeteren.
• Focus: De primaire uitdaging is "formuleringcorrectheid". Recent onderzoek (2025–2026) richt zich op het detecteren van "stille formulatiefouten", waarbij code weliswaar foutloos wordt uitgevoerd, maar het verkeerde probleem codeert. Technieken omvatten semantische ankerreconstructie (SAC-Opt), combinatorische zoektocht naar alternatieve modellen (Autoformulation) en gedragsverificatie (ReLoop).

3. Tool-Creating Optimalisatie (Tool-creërende Optimalisatie)

Dit paradigma gebruikt LLM's om herbruikbare algoritmen of heuristieken te ontdekken die opereren binnen solver- of metaheuristische kaders, in plaats van individuele probleeminstanties op te lossen.

• Mechanisme: LLM's fungeren als mutatie-operators in evolutionaire zoektochten (bijv. FunSearch, EoH) of genereren "verbale gradiënten" om heuristieken te verfijnen (ReEvo).
• Economisch Model: Hoewel dit hoge voorafgaande LLM-kosten met zich meebrengt voor het genereren van een tool, bereiken deze benaderingen effectief nul marginale LLM-kosten bij implementatie, aangezien de herbruikbare tool wordt geamortiseerd over herhaald gebruik.

Belangrijkste Bijdragen en Resultaten

Prestatiefrontiers en Benchmarks

De paper synthetiseert prestatiegegevens uit recente literatuur om de huidige grenzen vast te stellen:

• Directe Optimalisatie: Behaalt sterke resultaten op kleine schaal of specifieke domeinen (bijv. +50% verbetering op BBH via OPRO; verbeteringen in chemische opbrengst van 25,2% naar 60,7% via LLAMBO). De prestaties nemen echter significant af voorbij ~20 variabelen (bijv. op TSP), waar eenvoudige heuristieken beter presteren dan LLM's.
• Tool-Augmented Optimalisatie: Behaalt bijna perfecte nauwkeurigheid op eenvoudige benchmarks (bijv. 97,3% op NL4Opt) maar staat voor een "complexiteitsklif". Op reële industriële problemen (IndustryOR) daalt de nauwkeurigheid naar 57%, en in scenario's met samengestelde meerdere restricties (RetailOpt-190) daalt deze naar 31,1%.
• Tool-Creating Optimalisatie: Heeft state-of-the-art (SOTA) resultaten opgeleverd in algoritmeontdekking, zoals bin-packing strategieën die klassieke heuristieken overtreffen (FunSearch) en scheduling-heuristieken die op Google's Borg-cluster worden ingezet (AlphaEvolve) met een snelheidswinst van 23%.

Het Redeneergat (The Reasoning Gap)

Een cruciale bijdrage van de survey is de identificatie van het "redeneergat".

• Haalbaarheid versus Correctheid: Modellen zoals DeepSeek-V3.2 bereiken 91,1% solver-haalbaarheid, maar slechts 0,5% formuleringcorrectheid in samengestelde scenario's.
• Patroonherkenning: Bewijs suggereert dat LLM's vertrouwen op patroonherkenning in plaats van algoritmische redenering. Wanneer de probleemcomplexiteit toeneemt, piekt de redeneerinspanning en neemt deze vervolgens af, wat leidt tot een "volledige nauwkeurigheidsinstorting".
• Fouttypen: Systematische fouten omvatten ontbrekende restricties, onjuiste variabelen types en mismatches in de objectieffunctie.

Vergelijkende Trade-offs

De survey biedt een vergelijkende analyse (Tabel II) die benadrukt dat:

• Tool-Augmented benaderingen de hoogste controleerbaarheid en formele garanties bieden (indien de formulering correct is), maar worden gehinderd door de nauwkeurigheid van de formulering.
• Directe benaderingen een lage controleerbaarheid en geen formele garanties bieden, maar uitblinken in kleinschalige of slecht gestructureerde contexten.
• Tool-Creating benaderingen nieuwe SOTA-heuristieken bieden met een gemiddelde controleerbaarheid, waarbij een hoge initiële kost wordt afgewogen tegen nul marginale kosten bij implementatie.

Betekenis en Claims

De paper betoogt dat de keuze van een paradigma afhangt van de specifieke probleemrestricties en modelcapaciteiten.

• Beperkingen van Directe Benaderingen: Hoewel directe optimalisatie groeit, beperkt het redeneergat bij hogere complexiteit de schaalbaarheid.
• Het Gevolg van Tool-Making: De auteurs stellen dat "tool-making" (het creëren van herbruikbare solver-componenten of formuleringstemplates) de meest veelbelovende richting is voor de toekomst. Zelfs naarmens modellen krachtiger worden, kan de opportuniteitskost per instantie bij direct oplossen groter zijn dan de voordelen. Het creëren van een herbruikbare tool amorteert de redeneerkosten van de LLM over hele families van problemen, wat een operationeel efficiënter pad biedt dan redeneren per instantie.
• Reproductiecrisis: De survey wijst op een crisis in het subveld van tool-creatie, waarbij SOTA-claims (bijv. de cap set van FunSearch) vaak gebaseerd zijn op resultaten die moeilijk onafhankelijk te reproduceren zijn vanwege propriëtaire infrastructuur of pad-afhankelijkheid. De auteurs pleiten voor gemeenschapsnormen om claims van gesloten systemen te labelen en resultaatverdelingen te rapporteren in plaats van alleen de beste resultaten.

Concluderend stelt de survey dat hoewel LLM's steeds meer betrokken zijn bij optimalisatie, het veld de "complexiteitsklif" en de "formuleringcorrectheid"-bottleneck moet aanpakken. De toekomstige trajectorie zal waarschijnlijk de voorkeur geven aan hybride of tool-creënde strategieën die LLM's gebruiken voor algoritmeontdekking en templategeneratie, terwijl formele solvers worden gereserveerd voor executie en verificatie.