Een nieuwe onderzoeksstudie toont aan dat agentic AI in staat is om niet alleen optimalisatiealgoritmen te ontwerpen, maar ook om de wiskundige correctheid en efficiëntie ervan formeel te bewijzen in de programmeertaal Lean.
In een recent gepubliceerd wetenschappelijk artikel beschrijft onderzoeker Per Kristian Lehre een doorbraak in het automatiseren van algoritmisch ontwerp. Waar eerdere methoden voor het ontwerpen van optimalisatieheuristieken, zoals AlphaEvolve, hoofdzakelijk steunden op empirische tests, introduceert dit nieuwe onderzoek een systeem dat wiskundige garanties biedt over de prestaties van de gegenereerde algoritmen. Volgens de publicatie op arxiv.org gebeurt dit zonder dat de algoritmen tijdens het proces empirisch met elkaar vergeleken hoeven te worden.
De werking van de agentic pipeline
Het systeem maakt gebruik van een gestructureerde pipeline die is gemodelleerd naar de wetenschappelijke methodologie voor het analyseren van evolutionaire algoritmen. De AI-agent stelt eerst black-box optimalisatiealgoritmen voor. Deze ontwerpen worden vervolgens gefilterd door 'guards' in Lean, een interactieve stellingbewijzer, om foutieve ontwerpen direct te elimineren.
Vervolgens definieert de agent een potentiële functie en bewijst deze zogenaamde 'drift bounds'. Deze bewijzen garanderen dat het nieuwe algoritme een verbeterde verwachte looptijd heeft ten opzichte van een basisalgoritme. De effectiviteit van deze gefaseerde aanpak werd bevestigd via een ablatiestudie: wanneer de agent direct werd gevraagd om een ontwerp met een looptijdgarantie te produceren zonder deze tussenstappen, resulteerde dit enkel in onvolledige bewijzen of kopieën van het basisalgoritme (random search), zoals beschreven in de .
Concrete resultaten en prestaties
De pipeline heeft concrete resultaten geboekt bij verschillende probleemklassen. Zo genereerde de agent een algoritme voor het 'CycleUncover'-probleem met een verwachte looptijd van $O(n^2)$, terwijl het klassieke (1+1) EA voor hetzelfde probleem een exponentiële looptijd van $e^{\Omega(n)}$ vereist. Daarnaast werd een algoritme ontworpen voor integer-valued submodulaire minimisatie met een looptijd van $O(n^{2+2c})$, en wist het systeem de optimale orde van $O(n^2)$ te matchen op 'LeadingOnes'.
Uit de tests bleek dat 12 van de 15 pogingen met geavanceerde modellen de volledige pipeline succesvol doorliepen en eindigden met een door de machine gecontroleerde grens voor de verwachte looptijd.
Context: De opkomst van Agentic AI
Deze ontwikkeling past in een bredere trend naar 'Agentic AI'. In tegenstelling tot traditionele chatbots die enkel tekst genereren, is agentic AI in staat om zelfstandig doelen na te streven door plannen te maken, tools te gebruiken en acties aan te passen op basis van resultaten. Volgens agentic.ai onderscheidt dit type AI zich doordat het een loop doorloopt van beslissen, handelen en observeren totdat een doel is bereikt.
Deze autonome benadering stelt systemen in staat om complexe, meerstaps workflows te automatiseren, wat volgens MIT Sloan een significant verschil maakt ten opzichte van generatieve AI-tools. De kern van agentic AI ligt in de capaciteit om onafhankelijk beslissingen te nemen en interactie aan te gaan met software-omgevingen, zoals API's of databases, om een specifiek resultaat te behalen.
De integratie van deze autonomie met formele verificatietools zoals Lean betekent dat machine-gecontroleerde specificaties in de toekomst empirische evaluaties kunnen vervangen bij het ontdekken van nieuwe algoritmen. Zoals uitgelegd door geeksforgeeks.org, kenmerkt agentic AI zich door doelgericht gedrag en adaptief leren, wat in dit specifieke onderzoek is toegepast om wiskundige bewijzen te leveren voor computationele efficiëntie.