🤖 AI

When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning

Dit artikel presenteert een theoretisch kader dat aantoont dat in-context zoeken via zelfreflectie exponentiële verbeteringen in steekproefcomplexiteit kan bereiken ten opzichte van basismodellen door efficiënte posteriore updates mogelijk te maken wanneer reflecties fouten in een vroeg stadium betrouwbaar lokaliseren, een capaciteit die zowel robuust leerbaar is als equivalent is aan optimale reinforcement learning-policies.

Oorspronkelijke auteurs: Yotam Wolf, Noam Wies, Amnon Shashua

Gepubliceerd 2026-07-09

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yotam Wolf, Noam Wies, Amnon Shashua

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

Het Grote Plaatje: De "Twijfel"-Superkracht

Stel je voor dat je probeert een heel moeilijk doolhof op te lossen. Je hebt een vriend (het AI-model) die goed is in het raden van het juiste pad, maar soms loopt hij vast in een doodlopende weg.

Er zijn twee manieren waarop je vriend dit kan proberen:

De "Dobbelsteen"-methode (Parallel Sampling): Je vriend sluit zijn ogen, kiest een willekeurig pad en loopt tot hij tegen een muur aanloopt. Als hij faalt, begint hij weer helemaal opnieuw bij het begin, waarbij hij een volledig nieuw willekeurig pad kiest. Hij blijft dit doen totdat hij geluk heeft.
De "Twijfel"-methode (In-Context Search): Je vriend loopt een pad af, loopt tegen een muur aan en zegt dan: "Wacht, ik maakte drie stappen geleden een fout." Hij gaat terug naar die specifieke plek, probeert een andere afslag en gaat dan verder. Hij houdt een lijst bij van alle doodlopende wegen die hij tot nu toe heeft gevonden en zorgt ervoor dat hij nooit meer die specifieke paden bewandelt.

Dit paper stelt een simpele vraag: Wanneer werkt de "Twijfel"-methode eigenlijk beter dan gewoon steeds de "Dobbelsteen" gooien?

De Kernontdekking: Het Komt Aan op Wanneer Je de Fout Opmerkt

De auteurs ontdekten dat de "Twijfel"-methode een superkracht is, maar alleen als je vriend goed is in het vroegtijdig opmerken van de fout.

Het Winnaarsscenario: Vroege Detectie

Stel je voor dat je door een bos wandelt.

Het Probleen: Het bos is enorm groot. Als je bij de allereerste splitsing de verkeerde afslag neemt, kun je mijlenver dwalen voordat je beseft dat je verdwaald bent.
De Magie: Als je vriend direct kan zeggen: "Hé, die eerste afslag was fout," dan kan hij de hele bos van verkeerde paden achter die afslag direct afsnijden.
Het Resultaat: In plaats van dat hij miljoenen willekeurige paden moet proberen (exponentiele inspanning), hoeft hij slechts een paar dozijn specifieke paden te proberen (polynomiale inspanning). Hij lost het probleem snel op omdat hij de verkeerde takken efficiënt wegknipt.

Het Verliescenario: Late Detectie

Stel je nu voor dat je vriend slecht is in het opmerken van fouten.

Het Probleem: Hij loopt helemaal naar het einde van het doolhof, loopt tegen een doodlopende weg aan, en zegt dan pas: "O, ik denk dat ik een fout heb gemaakt."
De Realiteit: Tegen de tijd dat hij de fout doorheeft, heeft hij al veel tijd verspild aan het lopen door een lang, fout pad. Als hij teruggaat en het opnieuw probeert, neemt hij misschien nog steeds datzelfde lange, foutieve pad omdat hij niet besefte dat het begin het probleem was.
Het Resultaat: In dit geval biedt "Twijfelen" geen voordeel ten opzichte van gewoon de "Dobbelsteen" gooien. Sterker nog, het kan zelfs langzamer zijn omdat de vriend tijd verspilt aan het analyseren van lange, mislukte paden die eerder vermeden hadden kunnen worden.

Het Geheime Recept: Hoe de AI Leert te "Snoeien"

Het paper legt uit hoe de AI dit efficiënt leert. Het gebruikt een concept genaamd Posterior Updates, wat een chique manier is om te zeggen: "leren van falen."

Beschouw het brein van de AI als een kaart met veel paden.

De Prior (De Initiële Kaart): In het begin denkt de AI dat elk pad even waarschijnlijk de juiste weg is.
De Reflectie (De Criticus): Wanneer de AI een pad probeert en faalt, kijkt een "reflectie"-mechanisme naar de poging.
De Update (De Kaart Wissen): Als de reflectie correct identificeert: "Je sloeg bij stap 3 naar links af, en dat was fout," dan wist de AI effectief die linkse afslag van zijn kaart. De AI zegt niet alleen "Ga deze keer niet naar links"; de AI zegt: "De kans dat je naar links gaat is nu nul."

Het paper bewijst wiskundig dat als dit "wissen" betrouwbaar gebeurt voor vroege fouten, de AI problemen kan oplossen die anders eeuwig zouden duren. Als het wissen alleen gebeurt voor late fouten, blijft de kaart vol met doodlopende wegen en loopt de AI vast.

Wat Betreft de Training? (Hoe krijgen we de AI zover?)

Je vraagt je misschien af: "Hoe leren we een AI om fouten vroeg te spotten?"

Het paper laat zien dat dit gedrag leerbaar is.

Supervised Learning: Als je de AI voorbeelden laat zien van mensen die problemen oplossen door hun werk te controleren en fouten vroegtijdig te corrigeren, kan de AI hetzelfde doen. De AI hoeft geen genie te zijn; hij hoeft alleen het patroon "proberen, controleren, vroegtijdig herstellen" te leren.
Reinforcement Learning (RLVR): Het paper koppelt dit ook aan een populaire trainingsmethode waarbij de AI een "beloning" krijgt voor het vinden van het juiste antwoord. Ze laten zien dat als de AI wordt getraind om zijn kansen op het juiste antwoord te maximaliseren, de AI van nature evolueert naar een strategie die precies lijkt op dit gedrag van "vroegtijdige foutdetectie" en "verkeerde paden wissen".

Het Nadeel: Redeneringslussen

Het paper wijst ook op een gevaar. Als de AI in de war raakt en steeds opnieuw begint vanaf dezelfde verkeerde plek (zoals een hamster in een loopwiel), verspilt hij tijd. Dit wordt een "redeneringslus" genoemd. De theorie gaat ervan uit dat de AI slim genoeg is om te beseffen: "Ik heb al geprobeerd vanaf dit punt te starten en dat is mislukt; ik moet dit niet nog een keer doen." Real-world modellen worstelen hier soms mee, maar de theorie houdt stand wanneer de AI deze lussen vermijdt.

Samenvatting in één zin

In-context search (denken, controleren en herzien) is een enorme afkorting voor het oplossen van moeilijke problemen, maar alleen als de AI goed is in het precies spotten waar het aan het begin fout ging; als hij de fout pas aan het einde opmerkt, krijgt hij geen snelheidsvoordeel ten opzichte van gewoon willekeurig gokken.

Technische Samenvatting: Wanneer helpt in-context zoeken? Een sampling-complexiteitstheorie van reflectiegestuurde redenering

Probleemstelling

Large Language Models (LLM's) getraind met uitgebreide redeneercapaciteiten, zoals Reinforcement Learning with Verifiable Rewards (RLVR), vertonen "in-context zoeken". In dit paradigma genereren, bekritiseren en herzien modellen iteratief oplossingspogingen binnen het contextvenster, waarbij de volledige geschiedenis van mislukkingen behouden blijft. Hoewel dit heeft geleid tot de opkomst van Large Reasoning Models (LRM's) zoals DeepSeek-R1 en Kimi-k1.5 die eerdere modellen overtreffen op complexe redeneertaken, blijft het theoretisch onduidelijk wanneer dit sequentiële, in-context zoeken werkelijke voordelen biedt ten opzichte van parallelle sampling vanuit een basismodel, en wanneer het geen asymptotische voordelen biedt.

De kernvraag die wordt geadresseerd is: Hoeveel sequentiële pogingen (of backtracks) zijn vereist om met een hoge succeswaarschijnlijkheid te bereiken via in-context zoeken vergeleken met onafhankelijke parallelle sampling? Specifiek: onder welke condities transformeert de inferentie-tijd sampling-complexiteit van exponentieel (typisch voor parallelle sampling) naar polynomiaal?

Methodologie

De auteurs modelleren in-context zoeken als benaderende inferentie over redeneertracés. Ze formaliseren het proces met drie componenten:

Prior: Het basismodel definieert een priorverdeling $P_\theta$ over redeneertracés (sequenties van semantische stappen).
Reflectie: Een mechanisme dat mislukte pogingen observeert en fouten lokaliseert, waarbij feedback geeft over welke transities ongeldig zijn.
Posterior Updates: Conditionering op de geaccumuleerde reflectiegeschiedenis induceert een impliciete herweging van kandidaat-continuaties, wat effectief transities die als incorrect zijn geïdentificeerd, naar beneden weegt.

Het framework behandelt redeneertracés als paden in een boom waarbij prefixes toestanden zijn. De analyse richt zich op de sampling-complexiteit — het aantal benodigde sequentiële rondes $T$ om met een hoge waarschijnlijkheid een correcte oplossing te samplen.

Belangrijke Theoretische Aannames

$\gamma$ -lokale ondersteuning: Het basismodel kent een niet-verwaarloosbare waarschijnlijkheid ( $\gamma$ ) toe aan correcte volgende stappen langs een geldige redeneertracée.
Adaptieve Reflectie: Het reflectiemechanisme kan de eerste incorrecte stap in een mislukte tracée met een niet-verwaarlozierbare waarschijnlijkheid ( $p_r$ ) identificeren zodra die specifieke foutmodus is tegengekomen $m_r$ keer.
Contextuele Bereikbaarheid: Het model herneemt niet herhaaldelijk de generatie vanaf prefixes die al als incorrect zijn geïdentificeerd (het vermijden van redeneerlussen).
In-Context Herweging: Transities die als ongeldig zijn geïdentificeerd, worden multiplicatief omlaag gewogen in de logit-ruimte door een factor $e^{-\eta}$ voor elke occurence.

Belangrijkste Bijdragen en Resultaten

1. De Kritieke Rol van Vroege Foutlokalisatie

Het paper stelt een scherp onderscheid vast in de efficiëntie van in-context zoeken op basis van de timing van de reflectie:

Foutmodus (Late Reflectie): Als reflecties pas fouten identificeren in latere stadia (bijv. na diepte $n/2$ ), biedt in-context zoeken geen asymptotische verbetering ten opzichte van parallelle sampling. De kans op het selecteren van een correcte eerste stap blijft ongewijzigd omdat de zoekruimte niet vroeg genoeg wordt gepruned. Bovendien kan misleidende positieve feedback (het versterken van incorrecte stappen) de prestaties strikt verslechteren.
Succesconditie (Vroege Reflectie): Als reflecties betrouwbaar de eerste incorrecte stap identificeren, bereikt in-context zoeken exponentiële winst. Problemen waarbij de pass-rate van het basismodel exponentieel afneemt met de diepte ( $O(e^{-n})$ ), kunnen met een hoge waarschijnlijkheid worden opgelost met slechts een polynomiaal aantal sequentiële pogingen ( $T = \tilde{O}(n)$ ).

Theorem 4.3 formaliseert dit: Onder vroege reflectie schaalt het aantal vereiste rondes polynomiaal met de redeneelengte $n$ , de vertakkingsfactor $W$ en de reflectieparameters, terwijl onafhankelijke sampling exponentieel schaalt.

2. Leerbaarheid en Robuustheid

De auteurs demonstreren dat het vereiste gedrag van de posterior update robuust en leerbaar is:

Benaderende Updates: Een exacte implementatie van de herwegingsregel is niet noodzakelijk; stapgewijze benaderingen die geleerd zijn via standaard cross-entropy training op search rollouts volstaan om de efficiëntiegaranties te herstellen met polynomiale sample-complexiteit.
RLVR Connectie: Onder een stadige abstractie van RLVR (waarbij policies worden uitgebreid om redeneerpogingen toe te voegen geconditioneerd op eerdere feedback), implementeert de optimale policy extensie onder ruisige maar grotendeels correcte reflectie-feedback van nature dezelfde exponentiële posterior herwegingsregel. Dit biedt een theoretisch mechanisme voor de opkomst van search-achtige redenering in met RLVR getrainde modellen.

3. Empirische Validatie

De kwalitatieve voorspellingen van de theorie worden gevalideerd op echte LRM's (DeepSeek-R1-Distill-Qwen varianten) en synthetische data:

Foutlokalisatie: Modellen vertonen een niet-verwaarloosbaar vermogen om de eerste incorrecte stap te lokaliseren in rekenkundige en vergelijking-oplossende taken, hoewel met enige vertraagde reflecties.
Pass Rate Dynamiek: Analyse van prefix-geconditioneerde pass rates op AIME 2025 onthult dat succesvolle trajecten een progressieve toename in pass rate vertonen (accumulatie van posterior massa), terwijl onsuccesvolle trajecten een lage, oscillerende gedrag vertonen. Zelfcorrectie-segmenten produceren ijle, soms grote, positieve veranderingen in de pass rate, wat consistent is met een herverdeling van de waarschijnlijkheidsmassa in plaats van monotone accumulatie.
Redeneerlussen: Empirische analyse laat zien dat een aanzienlijk deel van de mislukte trajecten in huidige modellen "redeneerlussen" omvat (het herzoeken van geïnvalideerde prefixes), wat de theoretische noodzaak van de contextuele bereikbaarheidsaanname voor efficiënt zoeken ondersteunt.

Betekenis en Claims

Het paper claimt de eerste theoretische karakterisering te bieden van wanneer reflectiegestuurd in-context zoeken de sampling-complexiteit reduceert van exponentieel naar polynomiaal.

Theoretisch Inzicht: Het identificeert vroege foutlokalisatie als de noodzakelijke en voldoende voorwaarde voor exponentiële efficiëntiewinst. Zonder dit is in-context zoeken asymptotisch equivalent aan of slechter dan parallelle sampling.
Mechanisme van Opkomst: Het biedt een geprincipeerde verklaring voor waarom search-achtige redenering opkomt in RLVR-getrainde modellen: de optimale strategie voor het uitbreiden van een policy onder ruisige feedback is het uitvoeren van posterior herweging, wat overeenkomt met het geobserveerde gedrag in de praktijk.
Praktische Implicaties: De resultaten suggereren dat de effectiviteit van grote redeneermodellen zwaar afhangt van het vermogen van het model om de grondoorzaak van falen vroeg in de redeneerketen te diagnosticeren. Als een model niet in staat is om vroege fouten te lokaliseren, levert het uitbreiden van het contextvenster met mislukte pogingen een afnemend rendement op.

De auteurs hanteren een bescheiden standpunt door te merken dat hun resultaten een geïdealiseerd regime karakteriseren (uitgaande van geen redeneerlussen en specifieke reflectie-eigenschappen) en dat de prestaties in de echte wereld afhangen van de mate waarin modellen aan deze theoretische condities voldoen. Het werk stelt geen nieuwe trainingsalgoritmen voor, maar analyseert de theoretische fundamenten van bestaande zoekgebaseerde redeneerparadigma's.