Technische Samenvatting: Contrastive Concept-Tree Search voor LLM-ondersteunde Algoritme-ontdekking

Probleemstelling

LLM-ondersteunde algoritme-ontdekking werkt als een iteratief, black-box optimalisatieproces waarbij een LLM kandidaat-programma's voorstelt en een externe evaluator taakfeedback geeft. Hoewel recente paradigma's (bijv. FunSearch, AlphaEvolve) succesvol oplossingen hebben herontdekt of verbeterd voor combinatorische problemen (zoals Erdős-achtige problemen), vertrouwen zij grotendeels op fitness-gestuurde evolutionaire updates. In deze bestaande systemen wordt de selectie van ouders bepaald door de ruwe prestatie (fitness) van programma's, en verloopt de zoektocht als een wandeling over de afstamming van programma's geordend op prestatie.

Een kritieke beperking van deze aanpak is dat de programmaregelmatige ruimte zwak gestructureerd blijft. Zelfs wanneer beperkt door een LLM, missen gegenereerde algoritmen vaak duidelijke notions van lokaliteit, vloeiende variatie of compositionele structuur die door zoekalgoritmen kunnen worden geëxploiteerd. Bijgevolg wordt sturing afgeleid uit primaire fitness-signalen en de impliciete prior van de LLM, in plaats van uit een expliciet, geleerd begrip van welke semantische componenten van de algoritmen daadwerkelijk nuttig zijn. Dit artikel adresseert de openstaande vraag hoe de interne representatie van de programmaregelmatige ruimte van de LLM maximaal kan worden geëxploiteerd om de efficiëntie en interpreteerbaarheid van de zoektocht te verbeteren.

Methodologie: Contrastive Concept-Tree Search (CCTS)

De auteurs introduceren Contrastive Concept-Tree Search (CCTS), een framework dat de sturing van de zoektocht verschuift van ruwe fitness naar een geleerde, hiërarchische semantische conceptruimte. De kernhypothese is dat algoritmen beschreven kunnen worden door een onderliggende semantische conceptruimte die georganiseerd is als een hiërarchie, waarbij knopen concepten vertegenwoordigen en randen verfijning of specialisatie coderen.

1. Conceptrepresentatie en Boomconstructie

• Feature Extractie: Elk kandidaat-programma $x$ wordt in kaart gebracht naar een semantische feature-representatie $b = \Phi(x)$, geëxtraheerd door de LLM te instrueren een lijst met relevante concepten te genereren.
• Hiërarchische Structuur: Deze concepten worden georganiseerd in een gewortelde conceptboom. Een conceptvector $b$ is een indicatorvector waarbij activaties ancestor-gesloten zijn (het activeren van een kind-concept impliceert het activeren van alle voorouders). De boom is dynamisch en groeit naarmate er nieuwe concepten worden ontdekt tijdens de zoektocht.

2. Contrastief Leren van Concept-utiliteit

In plaats van ouders te selecteren uitsluitend op basis van hun fitness-score, leert CCTS welke concepten empirisch geassocieerd zijn met hoge prestaties via een contrastieve aanpak:

• Partitionering: Het archief van geëvalueerde programma's wordt verdeeld in "goede" ($y_i \ge \tau_t$) en "slechte" ($y_i < \tau_t$) subsets op basis van een prestatiedrempel.
• Model Fitting: Twee probabilistische modellen, $\hat{p}_{\eta^+}(b)$ en $\hat{p}_{\eta^-}(b)$, worden gefit aan de feature-distributies van de respectievelijk goede en slechte subsets. De auteurs maken gebruik van een Tree-structured Parzen Estimator (TPE)-achtige aanpak met een gefactoriseerde hiërarchische Bernoulli-model. Dit model gaat uit van conditionele onafhankelijkheid van features gegeven hun ouder in de hiërarchie.
• Likelihood Ratio Scoring: Een likelihood-ratio score (log-concept-utiliteit) wordt berekend voor elk programma:
  $$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$$
  Deze score kwantificeert hoe sterk een specifieke set concepten hoogpresterende oplossingen onderscheidt van laagpresterende oplossingen.

3. Ouderselectie en Zoekdynamiek

• Biased Sampling: Ouders worden geselecteerd uit het archief met een waarschijnlijkheid proportioneel aan hun likelihood-ratio score. Dit stuurt de zoektocht richting programma's die conceptcombinaties bevatten die empirisch geassocieerd zijn met verbetering.
• Exploratiemechanisme: Om voortijdige convergentie te voorkomen en de ontdekking van nieuwe concepten te stimuleren, bevat CCTS een lichtgewicht exploratiemechanisme. Dit omvat:
  • Beta Priors: Het gladstrijken van tellingen om ervoor te zorgen dat nieuw ontdekte concepten nooit een nul-waarschijnlijkheid hebben.
  • Novelty Bias: Het downweighten van concepten die veelvuldig zijn geprobeerd, om onontgonnen regio's van de conceptboom te bevoordelen.
  • Mixture Strategy: Een mengeling van exploitatie (gebaseerd op het geleerde contrastieve model) en exploratie (gebaseerd op nieuwheid) stuurt de selectie van concepten aan om in de prompt van de LLM te injecteren voor de generatie van kinderen.

Belangrijkste Bijdragen

1. Expliciete Semantische Structuur: Het artikel stelt voor om de latente structuur van de algoritmische ruimte expliciet te maken door een hiërarchische conceptboom te leren, waarmee men verder gaat dan de ongestructureerde programmaregelmatige ruimte die in standaard evolutionaire algoritmen wordt gebruikt.
2. Contrastieve Sturing: Het introduceert een contrastief statistisch framework dat leert welke concepten geprioriteerd moeten worden en, cruciaal, welke concepten vermeden moeten worden, in plaats van alleen bij te houden welke programma's het best presteren.
3. Interpreteerbaarheid: De methode produceert interpreteerbare, taakspecifieke conceptbomen die de verkende semantische structuur van de zoektocht onthullen, wat inzichten biedt in de ontdekte algoritmische strategieën.
4. Synthetische Validatie: De auteurs construeren een gecontroleerde synthetische omgeving met een "teacher" conceptboom en grondwaarheid-utiliteiten. Dit stelt hen in staat te valideren dat CCTS de onderliggende semantische structuur herstelt en dat de geobserveerde zoekdynamiek wordt gedreven door het leren van concept-utiliteiten in plaats van specifieke LLM-artefacten.

Experimentele Resultaten

De auteurs evalueerden CCTS op een benchmark van open Erdős-achtige combinatorische problemen, inclusief circle packing, de Arithmetische Kakeya-conjectuur, Heilbronn's driehoeks-probleem en het squares-in-square probleem.

• Prestatiewinst: CCTS behaalde consistent hogere scores en snellere verbetering vergeleken met baseline-strategieën (Uniform, Greedy, en $k$-elite selectie) over meerdere taken.
• Mechanisme van Verbetering: Analyse toonde aan dat de prestatiewinsten grotendeels worden gedreven door het leren welke concepten te vermijden. Succesvolle runs identificeerden een vergelijkbare set hoog-utiliteitsconcepten als onsuccesvolle runs, maar vertoonden een significant beter vermogen om laag-utiliteits (schadelijke) concepten te onderdrukken. Dit suggereert dat CCTS de zoektocht stabiliseert door onproductieve exploratie te verminderen die wordt veroorzaakt door misleidende correlaties in de initiële prior van de LLM.
• Synthetische Validatie: In de synthetische omgeving vertoonden de geleerde concept-utiliteiten een sterke correlatie ($r=0.94$) met de grondwaarheid-teacher-utiliteiten, wat bevestigt dat de methode effectief betekenisvolle semantische representaties herstelt.
• Structuurafhankelijkheid: Er werd gevonden dat de optimale balans tussen exploratie en exploitatie afhangt van de structuur van de onderliggende conceptboom (bijv. vertakkingsratio), wat suggereert dat zoekstrategieën moeten worden aangepast aan de specifieke topologie van de probleemruimte.

Betekenis en Claims

Het artikel claimt dat CCTS een fundamentele mismatch in huidige LLM-ondersteunde algoritme-ontdekking aanpakt: hoog scorende algoritmen genereren niet noodzakelijkerwijs sterke nakomelingen omdat fitness een slechte proxy is voor evolueerbaarheid in een zwak gestructureerde ruimte. Door selectie te verschuiven van ruwe fitness naar semantisch bewijs van verbetering, stelt CCTS de zoektocht in staat om te opereren in een conceptruimte waar afstand, recombinatie en zoekrichting betekenisvol zijn.

De auteurs positioneren dit werk als een methodologische vooruitgang naar meer betrouwbare en schaalbare algoritme-ontdekking. Zij benadrukken dat hoewel de huidige resultaten relatieve verbeteringen laten zien ten opzichte van baselines op specifieke benchmarks, de primaire bijdrage de demonstratie is van hoe expliciete, menscompatibele semantische conceptstructuren automatische ontdekking transparanter, controleerbaarder en efficiënter kunnen maken. Het werk suggereert dat toekomstige systemen zich moeten richten op het leren en exploiteren van deze latente semantische hiërarchieën in plaats van enkel te vertrouelen op black-box fitness-signalen.