🤖 machine learning

LLM Program Optimization via Retrieval Augmented Search

Dit artikel introduceert Retrieval Augmented Search (RAS) en AEGIS, innovatieve blackbox-adaptatiemethoden die door gebruik te maken van door LLM gegenereerde natuurlijke taalbeschrijvingen en atomische bewerkingen de huidige state-of-the-art strategieën aanzienlijk overtreffen bij het optimaliseren van C++- en Python-programma's, terwijl de interpreteerbaarheid wordt verbeterd en de code-wijzigingen worden geminimaliseerd.

Oorspronkelijke auteurs: Sagnik Anupam, Alexander Shypula, Osbert Bastani

Gepubliceerd 2026-06-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sagnik Anupam, Alexander Shypula, Osbert Bastani

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een zeer getalenteerde maar onervaren chef hebt (het Large Language Model, of LLM) die probeert een maaltijd te bereiden. Het doel is niet alleen om het eten lekker te laten smaken; het doel is om het eten sneller te laten koken zonder de smaak te veranderen.

De paper presenteert twee nieuwe manieren om deze chef slimmer te laten werken, gebruikmakend van een "bibliotheek van eerdere recepten" (een dataset van trage versus snelle code) om hen te begeleiden.

Het Probleem: De Chef Zit Vast

Normaal gesproken, als je deze chef vraagt om een recept te versnellen, kan hij willekeurig gokken of proberen het hele ding in één keer te herschrijven. Hij faalt vaak omdat hij niet genoeg voorbeelden heeft gezien van hoe je dingen sneller kunt maken. Hij heeft een coach nodig die hem specifieke trucjes laat zien.

Methode 1: RAS (Retrieval Augmented Search)

De Analogie: De "Slimme Bibliothecaris" versus de "Zoekopdracht op Trefwoorden"

Stel je voor dat de chef in een enorme bibliotheek een vergelijkbaar recept moet vinden om inspiratie op te doen.

De Oude Manier (Code Retrieval): De chef kijkt naar de ingrediëntenlijst (de eigenlijke code) van het huidige gerecht en zoekt in de bibliotheek naar recepten met vergelijkbare ingrediënten. Dit is als zoeken naar "bloem en eieren" en dan een recept voor een cake terugkrijgen, terwijl je eigenlijk een soeprecept nodig hebt dat toevallig ook bloem gebruikt. Het is te letterlijk.
De Nieuwe Manier (Contextual Retrieval): De chef vraagt de bibliothecaris om eerst een samenvatting van het gerecht te schrijven (bijv. "Dit is een soep die groenten laat sudderen om smaak te extraheren"). De bibliothecaris zoekt vervolgens in de bibliotheek naar andere gerechten die hetzelfde doen, ongeacht de specifieke ingrediënten.
- Waarom het werkt: Het vindt recepten die hetzelfde probleem oplossen, niet alleen recepten die er op papier hetzelfde uitzien.

Het Zoekproces (Beam Search):
In plaats van de chef te vragen om het recept in één grote sprong te verbeteren, breekt RAS het af.

De chef maakt een kleine verbetering.
De bibliothecaris vindt een nieuw, relevant voorbeeld gebaseig op deze nieuwe versie.
De chef probeert het opnieuw, gebruikmakend van dat nieuwe voorbeeld.
Ze herhalen deze lus, zoals het beklimmen van een berg stap voor stap, waarbij ze altijd het pad kiezen dat het snelst omhoog gaat.

Het Resultaat: Deze methode maakte C++ programma's tot wel 2 keer sneller dan eerdere beste methoden en verbeterde de snelheid van Python programma's aanzienlijk.

Methode 2: AEGIS (Atomic Edit Guided Search)

De Analogie: De "Lego Master" versus de "Sloopploeg"

Zelfs met de slimme bibliothecaris kan de chef nog steeds enorme, verwarrende veranderingen aan het recept aanbrengen (zoals de volledige kookmethode vervangen). Dit is moeilijk te begrijpen en riskant.

AEGIS verandert de bibliotheek zelf. In plaats van hele "Trage versus Snelle" receptparen op te slaan, breekt het deze af in Atomaire Edits.

Het Proces: Het systeem neemt een traag recept en een snel recept en vraagt een expert om het verschil in piepkleine, enkelvoudige stappen uit te leggen.
- Stap 1: "Vervang de houten lepel door een metalen lepel (snellere warmteoverdracht)."
- Stap 2: "Hak de uien fijner (kookt sneller)."
- Stap 3: "Gebruik een deksel om stoom vast te houden."
De Generalisatie: Het herschrijft deze stappen vervolgens naar algemene regels (bijv. "Gebruik metalen keukengerei voor hoge hitte") zodat ze op elk recept kunnen worden toegepast, niet alleen op dat specifieke gerecht.

Hoe het helpt: Wanneer de chef een nieuw gerecht moet optimaliseren, zegt het systeem niet: "Hier is een heel nieuw recept." Het zegt: "Hier is een specifieke, kleine truc: 'Vervang de houten lepel door een metalen lepel.' Probeer dat eens." De chef past één kleine truc toe, controleert het resultaat, en probeert dan de volgende.

Het Resultaat:

Het maakt de veranderingen kleiner en gemakkelijker te begrijpen (zoals het vervangen van één Lego-blokje in plaats van het hele kasteel te herbouwen).
Het verminderde de omvang van de wijzigingen met 17% tot 30% vergeleken met de eerste methode.
Het maakte programma's nog steeds sneller, hoewel iets minder dan de eerste methode, maar met veel meer controle en duidelijkheid.

Samenvatting van de Resultaten

RAS is als een slimme coach die je door een reeks kleine, geïnformeerde stappen leidt, waarbij de beste weg naar een sneller programma wordt gevonden. Het versloeg de vorige beste methode met 2x voor C++ en verbeterde de Python snelheid gemiddeld met 10%.
AEGIS is als een coach die het probleem afbreekt in kleine, beheersbare Lego-blokjes. Het maakt de wijzigingen 1.37x beter in termen van efficiëntie en maakt de edits veel kleiner en veiliger, waardoor het programma niet kapot gaat terwijl het probeert sneller te worden.

Kortom, de paper leert ons dat om AI-code sneller te maken, we niet simpelweg moeten vragen om te "gokken". We moeten het voorzien van een bibliothecaris die het verhaal van de code begrijpt (Contextual Retrieval) en een set kleine, specifieke tools (Atomic Edits) om kleine, veilige verbeteringen aan te brengen, één voor één.

Technische Samenvatting: Optimalisatie van LLM-programma's via Retrieval Augmented Search

Probleemstelling

Large Language Models (LLMs) hebben een aanzienlijk potentieel getoond bij codegeneratie, maar hebben moeite met programma-optimalisatie uit de basisversie. Traditionele trainingsdatasets bevatten onvoldoende gegevens over de prestaties van programma's, waardoor directe adaptatie moeilijk is. Hoewel recent werk (Shypula et al., 2024) de "Performance Improving Edits" (PIE) benchmark introduceerde en aantoonde dat dynamische code-retrieval (het ophalen van trage-snelle programma-paren op basis van code-embedding gelijkenis) de prestaties verbetert, blijven bestaande benaderingen "end-to-end". Ze vragen een LLM om direct een geoptimaliseerde versie van een programma te produceren op basis van enkele voorbeelden. Dit staat in contrast met moderne compilers, die programma's systematisch aanpassen via een reeks incrementele passes. Bov�elijke produceren end-to-end benaderingen vaak grote, moeilijk te interpreteren wijzigingen.

Methodologie

Het artikel stelt twee primaire methoden voor om deze beperkingen aan te pakken: Retrieval Augmented Search (RAS) en Atomic Edit GuIded Search (AEGIS).

1. Retrieval Augmented Search (RAS)

RAS is een blackbox-adaptatiemethode die een beam search uitvoert over kandidaat-optimalisaties, waarbij twee belangrijke inzichten worden geïntegreerd om dynamische retrieval te verbeteren:

Contextuele Retrieval: In plaats van voorbeelden te ophalen op basis van de ruwe broncode, gebruikt RAS een LLM ( $F_{context}$ ) om een natuurlijke taalbeschrijving te genereren van de kernalgoritmen en datastructuren van het programma. Deze beschrijving wordt vervolgens ingebed ( $\psi$ ) om de meest relevante trage-snelle trainingsparen op te halen. De auteurs hypothetiseren dat deze abstractie het systeem in staat stelt om voorbeelden te ophalen op basis van intentie en logica, in plaats van oppervlakkige syntactische gelijkenissen.
Iteratieve Beam Search: In plaats van één keer een vaste set voorbeelden op te halen, voert RAS een retrieve-optimize-evaluate loop uit. In elke stap $i$ , gegeven het huidige programma $p_{i-1}$ , haalt het systeem de top- $k$ trainingsparen op die het meest lijken op $p_{i-1}$ (gebaseerd op de contextuele embedding). De LLM ( $F_{opt}$ ) genereert vervolgens $k$ kandidaat-optimalisaties. Het systeem selecteert het snelste correcte programma als $p_i$ en herhaalt het proces voor $m$ stappen.

2. Atomic Edit GuIded Search (AEGIS)

Om het interpreteerbaarheidsprobleem van grote, monolithische wijzigingen aan te pakken, introduceert AEGIS een voorverwerkingsstap om trainingsvoorbeelden te deconstrueren in "atomaire edits".

Deconstructie: Een LLM ( $F_{decomp}$ ) analyseert een trage-snelle programma-paar $(p, p')$ en deconstrueert de transformatie in een sequentie van natuurlijke taalbeschrijvingen $[s_1, ..., s_r]$ , waarbij elke $s_i$ een specifieke incrementele verandering en de bijbehorende prestatierationale uitlegt.
Generatie en Generalisatie: Het systeem gebruikt een LLM ( $F_{edit}$ ) om elke beschrijving $s_i$ sequentieel toe te passen op het trage programma om tussenliggende programma's te genereren. Vervolgens herschrijft een generalisatie-LLM ( $F_{gen}$ ) elke specifieke edit-beschrijving naar een generaliseerbare "atomaire edit" $e_i$ die op een breder scala aan programma's van toepassing is.
Zoeken met Atomaire Edits: De resulterende dataset $\Pi_{atomic}$ bestaat uit tupels $(e_i, (p_{i-1}, p_i))$ . RAS wordt vervolgens uitgevoerd op deze dataset, waarbij de retrieval-stap de meest relevante atomaire edit vindt en de LLM wordt geprompt om die specifieke incrementele edit toe te passen op het huidige programma. Dit dwingt het optimalisatieproces om meer incrementeel en interpreteerbaar te zijn.

Belangrijkste Bijdragen

Superioriteit van Contextuele Retrieval: Het artikel demonstreert dat het ophalen van voorbeelden op basis van door LLM gegenereerde natuurlijke taalbeschrijvingen aanzienlijk beter presteert dan retrieval op basis van ruwe broncode-embeddings. Dit suggereert dat het abstraheren van de algoritmische intentie cruciaal is voor effectief few-shot leren in optimalisatie.
RAS Framework: De auteurs stellen RAS voor, dat contextuele retrieval combineert met iteratieve beam search. Deze benadering behandelt optimalisatie als een sequentieel zoekprobleem in plaats van een single-step generatietaak.
AEGIS voor Interpreteerbaarheid: Het artikel introduceert AEGIS, een methode om trainingsdata te distilleren tot atomaire, generaliseerbare edits. Dit stelt het systeem in staat om optimalisaties in kleinere, interpreteerbare stappen uit te voeren terwijl de prestatiewinst behouden blijft.
Uitgebreide Evaluatie: De methoden worden geëvalueerd op de PIE benchmark (C++) en de Mercury benchmark (Python), waarbij ze worden vergeleken met state-of-the-art baselines, inclus\u00ad bij dynamische retrieval, instruction-only prompting en menselijke prestaties.

Resultaten

C++ Optimalisatie (PIE Benchmark)

RAS Prestaties: Met gebruik van Qwen3-Coder bereikte RAS een gemiddelde versnelling van 8.70×, vergeleken met 4.23× voor de vorige state-of-the-art dynamische retrieval baseline. Dit is een verbetering van 2.06× ten opzichte van de baseline.
AEGIS Prestaties: Met gebruik van GPT-4o bereikte AEGIS een gemiddelde versnelling van 6.08×. Hoewel dit iets lager is dan de volledige RAS (die hogere versnellingen behaalde met specifieke modellen), produceerde AEGIS aanzienlijk kleinere edits.
Edit Grootte: AEGIS verminderde de gemiddelde edit-grootte (gemeten via string edit distance) met 17% vergeleken met RAS (met GPT-4o) en met 30% wanneer alleen de eerste edit in het zoekproces wordt beschouwd.
Nauwkeurigheid: In GPT-4o experimenten behield RAS een nauwkeurigheidspercentage van 99.5% (programma's die alle testgevallen passeren), terwijl AEGIS 100% behaalde. Formele verificatie met CBMC op een subset van DeepSeek 3.2 outputs bevestigde semantische equivalentie in 8/10 gevallen; de overige 2 verschilden slechts in minimale opmaak (nieuwe regels).

Python Optimalisatie (Mercury Benchmark)

Bij gebruik van RAS met Qwen2.5-7B-Instruct verbeterde de gemiddelde runtime percentile metric (Beyond@1) met 10.27 ten opzichte van de baselines, waardoor de prestatiekloof tussen dit model en grotere reasoning-modellen aanzienlijk werd verkleind.

Betekenis en Claims

Het artikel claimt dat het opdelen van programma-optimalisatie in incrementele stappen via retrieval-augmented search aanzienlijk verbetert hoe LLM's code kunnen optimaliseren. De auteurs benadrukken dat contextuele retrieval (het gebruik van natuurlijke taalbeschrijvingen) een kritieke factor is om de prestaties van code-gebaseerde retrieval te overtreffen. Bovendien stellen zij dat AEGIS een levensvatbaar pad biedt om LLM-gestuurde optimalisaties interpreteerbaarder en veiliger te maken door incrementele wijzigingen af te dwingen, zonder substantiële prestatiewinst op te offeren. Dit werk positioneert deze blackbox-adaptatiestrategieën als een praktisch alternatief voor fine-tuning, in staat om bestaande trainingsdatasets van trage-snelle paren te gebruiken om state-of-the-art resultaten te behalen in programma-optimalisatie.