🤖 machine learning

Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching

Het artikel introduceert Sketch-and-Verify, een kosteneffectieve schaalstrategie voor inferentie in kleine code-modellen die flat sampling overtreft door diverse algoritmische schetsen te enumereren en deze op te vullen met meerdere kandidaten, hoewel het de prestaties van sterkere modelniveaus niet volledig kan vervangen.

Oorspronkelijke auteurs: Shan Jiang, Zijian Yi, Chenguang Zhu

Gepubliceerd 2026-05-12

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Shan Jiang, Zijian Yi, Chenguang Zhu

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 lastige puzzel probeert op te lossen, maar je hebt alleen een kleine, goedkope robot om je te helpen. Deze robot is snel en goedkoop, maar heeft een slechte gewoonte: wanneer hij een probleem probeert op te lossen, kiest hij bijna altijd dezelfde verkeerde denkwijze. Als je hem vraagt om 100 keer te proberen, krijg je gewoon 100 lichtjes verschillende versies van hetzelfde verkeerde antwoord.

Dit is het probleem dat het artikel "Schets-en-Verifieer" probeert op te lossen. Het biedt een nieuwe manier om die kleine, goedkope robot te gebruiken, zodat hij meer problemen kan oplossen zonder dat je moet upgraden naar een superduurzame, gigantische robot.

Hier is hoe de methode werkt, opgesplitst in simpele stappen:

1. Het Probleem: "Hetzelfde Oude Liedje"

Normaal gesproken vragen we een AI om code te schrijven door te zeggen: "Probeer het 100 keer en geef me de beste."

De Tekortkoming: Als het "standaard" idee van de AI verkeerd is, is het vragen om 100 pogingen hetzelfde als iemand vragen om 100 verschillende versies van een slecht liedje te schrijven. Je verandert misschien de tekst of het tempo, maar de melodie is nog steeds verkeerd. De AI blijft steken in een lus van "cosmetische" veranderingen (het wijzigen van variabele namen of opmaak) zonder ooit een fundamenteel andere aanpak te proberen.

2. De Oplossing: "De Architect en de Bouwer"

De auteurs stellen een tweestapsproces voor genaamd Schets-en-Verifieer. In plaats van de AI direct de volledige code te laten schrijven, verdelen ze de taak in twee rollen:

Stap 1: De Architect (De Schets)
Eerst vragen ze de AI om te fungeren als een architect. Ze zeggen: "Schrijf de code nog niet. Noem gewoon 5 volledig verschillende manieren om dit probleem op te lossen."
- Voorbeeld: "Strategie A: Gebruik een kaart. Strategie B: Sorteer eerst de lijst. Strategie C: Gebruik een lus."
- Zodra de AI een strategie kiest, tekent de AI een ruwe "blauwdruk" (een schets) met gaten erin. De blauwdruk heeft de hoofdstructuur (de muren en het dak), maar laat de specifieke details (de verfkleur, de deurkruk) over als lege vakken gemarkeerd met ??.
- Waarom dit helpt: Dit dwingt de AI om te stoppen en na te denken over verschillende paden voordat hij begint met bouwen. Het garandeert dat de AI verschillende "buurten" van oplossingen verkent in plaats van alleen maar in cirkels te lopen in dezelfde buurt.
Stap 2: De Bouwer (Het Invullen)
Nu, voor elke blauwdruk, fungeert de AI als een bouwer. Hij vult de ?? gaten in om een compleet programma te maken.
- Als de AI 5 blauwdrukken (strategieën) heeft gemaakt en elke 10 keer heeft ingevuld, heeft hij nu 50 volledig verschillende programma's om te testen.
- Omdat de blauwdrukken verschillend waren, zijn deze 50 programma's structureel divers. Het zijn niet alleen herschrijvingen van hetzelfde idee; het zijn echt verschillende aanpakken.
Stap 3: De Inspecteur (Verifiëren)
Tot slot draaien ze al deze programma's door een test. Ze houden de werkende exemplaren over en kiezen de beste uit.

3. De Resultaten: Goedkoop versus Duur

De onderzoekers testten dit op een standaard codetest genaamd HumanEval+ met drie versies van Google's Gemini AI:

Lite: Het kleine, goedkope, snelle model.
Flash: Het middelgrote model.
Pro: Het grote, dure, slimme model.

De Grote Bevindingen:

Voor de Goedkope Robot (Lite): De "Schets-en-Verifieer"-methode was een gamechanger.
- Als ze de Lite-robot gewoon vroegen om normaal 100 keer te proberen (Flat Sampling), loste hij ongeveer 53% van de moeilijke problemen op.
- Als ze de Schets-en-Verifieer-methode gebruikten (10 blauwdrukken maken en deze 10 keer invullen), loste hij 79% van de moeilijke problemen op.
- De Analogie: Het is alsof je een student zegt: "Schrijf niet gewoon 100 essays over hetzelfde onderwerp. Maak 10 schetsen voor 10 verschillende onderwerpen en vul ze dan in." De student leert meer en krijgt een betere cijfer voor dezelfde hoeveelheid inspanning.
Voor de Duurdere Robot (Pro): De methode hielp niet veel.
- De Pro-robot is al zo slim dat zijn "standaard" idee meestal juist is. Het dwingen om verschillende strategieën te schetsen maakte hem zelfs iets slechter, omdat hij werd afgeleid van zijn beste instinct.
- De Regel: Als je een superslimme robot hebt, laat hem dan gewoon hard nadenken (Greedy). Als je alleen een goedkope robot hebt, gebruik dan Schets-en-Verifieer om hem te dwingen creatief na te denken.

4. De Conclusie

Het artikel betoogt dat Schets-en-Verifieer een slimme manier is om extra rekenkracht te besteden wanneer je vastzit aan een kleiner, goedkoper AI-model.

Het is geen magie: Het maakt een zwak model niet sterker dan een sterk model. Als je je het dure "Pro"-model kunt veroorloven, gebruik dan gewoon dat.
Het is een strategie: Als je moet werken met het goedkope model (vanwege budget of snelheid), is deze methode de beste manier om extra prestaties uit het te halen. Het voorkomt dat de AI vast komt te zitten in een sleur en dwingt hem om verschillende oplossingen te verkennen, net als een menselijke brainstormsessie.

Kortom: Vraag de AI niet om harder te proberen; vraag hem om anders te proberen.

Technische Samenvatting: Sketch-and-Verify: Gestructureerde Inference-Time Scaling via Program Sketching

1. Probleemstelling

Het artikel behandelt een specifieke operationele beperking waaruit practitioners worden geconfronteerd: gegeven een vast, klein en kosteneffectief code-model (bijvoorbeeld Gemini 3.1 Flash Lite) dat is gekozen omwille van latentie of budget, hoe moet men een beperkt bedrag aan extra compute-tijd toewijzen om de nauwkeurigheid te verbeteren?

Standaardbenaderingen omvatten flat sampling (het genereren van $N$ onafhankelijke kandidaatprogramma's en het selecteren van de beste via uitvoering). De auteurs betogen dat flat sampling inefficiënt is omdat het de programmaruimte als homogeen behandelt. Grote taalmodellen (LLM's) wijzen vaak een hoge waarschijnlijkheidsmassa toe aan één enkele "modale" algoritmische strategie. Bijgevolg mist het resulterende kandidatenbestand, zelfs bij hoge temperatuur of grote $N$ , structurele diversiteit; het bestaat voornamelijk uit oppervlakkige cosmetische varianten (verschillende variabele namen, opmaak) van dezelfde 2–3 strategieën. Als de standaardstrategie van het model voor een specifiek probleem onjuist is, zal flat sampling waarschijnlijk falen om de juiste oplossing te ontdekken, ongeacht het aantal steekproeven.

2. Methodologie: SKETCHVERIFY

De auteurs stellen SKETCHVERIFY voor, een methode die inference-time compute herstructureert door de zoekruimte te factoriseren in algoritmische strategie en implementatiedetails. Geïnspireerd door program sketching (Solar-Lezama, 2008, 2013) en eerdere werken over door LLM's aangedreven compiler-testen (OBsmith, Jiang et al., 2026b), werkt de methode in vier fasen:

Fase 1: Sketch-Generatie (Categorie-Eerste Prompting)
- Categorie-Enumeratie: De LLM wordt geprompt om $K$ fundamenteel verschillende algoritmische strategieën (bijvoorbeeld "hash map", "twee pointers", "dynamisch programmeren") in natuurlijke taal te lijsten. Dit dwingt het model om na te denken over de strategieruimte voordat het codeert.
- Sketching: Voor elke strategie genereert de LLM een gedeeltelijk programma (een "sketch") waarbij het algoritme, de datastructuren en de controleflow volledig zijn gespecificeerd, maar implementatiedetails (expressies, condities, loopgrenzen) zijn vervangen door ??-placeholders. Het doel is 4–8 gaten per sketch.
- Kerninnovatie: Dit tweestapsproces voorkomt dat het autoregressieve model vastzit aan één standaardstrategie, waardoor structurele diversiteit over de $K$ sketches wordt gewaarborgd.
Fase 2: Invullen
- Elke geldige sketch wordt $M$ keer ingevuld om $K \times M$ volledige kandidaatprogramma's te produceren.
- Om variatie binnen een enkele sketch te stimuleren, wordt elke derde invulling geconditioneerd op de vorige invulling en wordt er gevraagd om een andere implementatie te leveren.
Fase 3: Verificatie
- Kandidaten worden gefilterd op compilatie en crash-vrije uitvoering.
- Overlevende kandidaten worden uitgevoerd op $D$ diverse testinputs (gegenereerd via een vergelijkbare sketch-gebaseerde aanpak).
- Er wordt een uitvoeringsvingerafdruk gegenereerd voor elke kandidaat: een vector van (status, output)-paren. Identieke vingerafdrukken duiden op gedrags-equivalentie.
Fase 4: Selectie
- Kandidaten worden geklusterd op basis van hun uitvoeringsvingerafdrukken.
- Het grootste cluster (dat de meest robuuste gedragsconsensus vertegenwoordigt) wordt geselecteerd.
- Uit het grootste cluster wordt het kortste programma teruggegeven (Ockhams scheermes). Deze selectieregel is identiek aan de gelijktijdige "Semantic Voting"-lijn van werk, waardoor het voordeel van gestructureerde generatie wordt geïsoleerd van het selectiemechanisme.

3. Belangrijkste Bijdragen

SKETCHVERIFY Framework: Introduceert een binnen-tier kosten-prestatiebeleid dat program sketching toepast op inference-time scaling. Het factoriseert de zoekruimte in $K$ (strategieën) en $M$ (implementaties), waardoor een steilere pass@1-scalingcurve wordt bereikt dan flat sampling op zwakke modellen.
Kosten-Kwaliteit Pareto-analyse: Biedt een rigoureuze analyse op de HumanEval+ benchmark, specifiek een heranalyse van een "moeilijke subset" van 19 problemen waarbij het basisline Lite-model (greedy) faalt.
- Binnen-tier: Sketching domineert flat sampling bij gelijkgestelde aantallen kandidaten. Op de moeilijke subset herstelt Lite Sketch ( $K=2, M=5$ ) 58% van de problemen versus 26% voor flat sampling ( $N=10$ ). Zelfs met een budgetverhoging van 3x bereikt flat sampling ( $N=50$ ) slechts 47%, en verliest het nog steeds van de goedkopere sketch-configuratie.
- Tussen-tier: Sketching vervangt niet het upgraden van modellen. Sterkere tiers (bijvoorbeeld Gemini Pro greedy) domineren Lite+Sketch-configuraties op zowel kosten als nauwkeurigheid. Sketching is een aanvulling op, geen vervanging voor, het upgraden van de model-tier.
Categorie-Eerste Decompositie: Stelt een specifieke promptingstrategie voor (het enumereren van strategienamen voordat er wordt gecodeerd) die cruciaal is voor het genereren van structurele diversiteit in plaats van cosmetische varianten.
K-vs-M Trade-off Karakterisering: Door middel van scalingsweeps tonen de auteurs aan dat de relatie tussen $K$ en $M$ niet-monotoon is. Gemengde toewijzingen (bijvoorbeeld $K=2, M=5$ ) presteren vaak beter dan pure-flat ( $K=1$ ) of pure-sketch ( $M=1$ ) extremen, en het simpelweg verhogen van $K$ levert niet altijd lineaire winsten op (bijvoorbeeld $K=5, M=10$ presteerde in sommige metrics slechter dan $K=2, M=5$ ).
Composabiliteit: Demonstreert dat gestructureerde generatie zich schoon combineert met uitvoeringsgebaseerde selectie (Semantic Voting). De methode fungeert als een generator van een divers kandidatenbestand, terwijl de selector onafhankelijk blijft van de generatiemethode.

4. Experimentele Resultaten

Benchmarks: Geëvalueerd op HumanEval+ (164 Python-problemen met uitgebreide test suites). Cross-benchmark validatie op MBPP+ en LiveCodeBench wordt aangegeven als toekomstig werk.
Modellen: Drie tiers van Google Gemini-modellen (Pro, Flash, Flash Lite) bij lage denk-niveaus.
Prestaties op de Moeilijke Subset (19 problemen waarbij Lite greedy faalt):
- Lite Sketch ( $K=10, M=10$ ): 79% pass@1.
- Lite Flat ( $N=100$ ): 53% pass@1.
- Lite Sketch ( $K=2, M=5$ ): 58% pass@1 (bij een lagere kost dan Flat $N=50$ ).
- Flash/Pro Greedy: Presteert beter dan alle Lite-configuraties, wat bevestigt dat modelcapaciteit de primaire drijver van nauwkeurigheid is.
Scaling Curves: Op de volledige HumanEval+-set verzadigt Lite flat sampling bij ~89% pass@1. SKETCHVERIFY doorbreekt dit plafond en bereikt 93% bij $K=10, M=10$ . Echter, op Flash en Pro, waar modellen bijna verzadigd zijn, zijn de winsten van sketching marginaal of niet-bestaand in vergelijking met greedy decoding.

5. Betekenis en Claims

Het artikel positioneert SKETCHVERIFY als een binnen-tier kosten-prestatiebeleid, geen universele verbetering van de nauwkeurigheid.

Practitioner-regel: Als een sterkere model-tier beschikbaar is, gebruik dan greedy decoding op die tier. Als men beperkt is tot een zwakker model (vanwege latentie, implementatie of budget), is SKETCHVERIFY de meest kosteneffectieve manier om extra compute-tijd te besteden.
Mechanisme: De methode slaagt door expliciet de exploratie van verschillende algoritmische strategieën (structurele diversiteit) af te dwingen in plaats van te vertrouwen op de stochasticiteit van flat sampling om per ongeluk een nieuwe aanpak te vinden.
Beperkingen: De auteurs erkennen beperkingen, waaronder de afhankelijkheid van één modelfamilie (Gemini), één denk-niveau, en het feit dat de kwaliteit van sketches wordt begrensd door de eigen strategieverdeling van het model (als het model de juiste strategie niet kan bedenken, kan sketching deze niet genereren). Zij merken ook een token-overhead van ongeveer 7% op voor de sketch-generatiefase.

Het artikel concludeert dat sketching, hoewel zeer effectief voor zwakke modellen die worstelen met strategische diversiteit, geen wondermiddel is voor modellen die al hun capaciteitsplafond hebben bereikt, of voor problemen waarbij de juiste strategie volledig buiten het latente kennis van het model ligt.