📊 statistics

Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Provers

Dit artikel toont aan dat hiërarchische stellingbewijzers een exponentiële reductie in steekproefcomplexiteit bereiken ten opzichte van vlakke bewijzers door herbruikbare bewijsstructuren te leren uit docentsporen, waardoor de redundante herhaling van moeilijke deelbewijzen die inherent is aan afgevlakte representaties wordt vermeden.

Oorspronkelijke auteurs: Sho Sonoda, Shunta Akiyama, Yuya Uezato

Gepubliceerd 2026-05-11

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sho Sonoda, Shunta Akiyama, Yuya Uezato

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 student leert een zeer complex puzzel op te lossen, zoals een enorm legpuzzel of een moeilijk wiskundeprobleem. Het doel is om de student de oplossing zo snel en efficiënt mogelijk te laten vinden, met een beperkte hoeveelheid tijd en inspanning.

Dit artikel stelt een simpele vraag: Is het beter om de student te leren het hele puzzel elke keer opnieuw vanaf nul op te lossen, of om hen te leren kleinere, opgeloste stukken van het puzzel te herkennen en opnieuw te gebruiken?

De auteurs betogen dat het leren van de student om stukken opnieuw te gebruiken (een hiërarchische aanpak) exponentieel efficiënter is dan hen te dwingen elk klein stapje opnieuw vanaf nul op te lossen (een vlakke aanpak), zelfs als de "stukken" zelf moeilijk te doorgronden zijn.

Hier is de uiteenzetting met alledaagse analogieën:

1. De Twee Manieren van Leren

De "Vlakke" Student (De Hardwerkende)
Stel je een student voor die een recept krijgt voor een enorm banket. Telkens als het recept zegt "maak de saus", moet de student vanaf nul beginnen: de uien hakken, de knoflook pellen, de tomaten laten sudderen en alles blenderen. Zelfs als het recept de saus tien keer vraagt, maakt deze student tien aparte batches saus, waarbij de uien tien keer worden gehakt.

In het artikel: Dit is een "vlakke" bewijzer. Het ziet het hele bewijs als één lange, rechte lijn van stappen. Als een specifiek logisch argument (zoals een lemma) vijf keer nodig is, moet de student die vijf stappen vijf keer apart leren en uitvoeren.

De "Hiërarchische" Student (De Slimme Organisator)
Stel je nu een slimmere student voor. Wanneer ze "maak de saus" zien, beseffen ze: "Dit heb ik al eerder gedaan!" Ze schrijven een notitie: "Sausrecept: Hakken, pellen, sudderen." De volgende keer dat het recept saus vraagt, zeggen ze gewoon: "Gebruik het Sausrecept", en hoeven ze de uien niet opnieuw te hakken. Ze bouwen een bibliotheek van opnieuw te gebruiken "blokken" (lemma's).

In het artikel: Dit is een "hiërarchische" bewijzer. Het splitst het probleem op in een kaart (een DAG, of Gerichte Acyclische Grafiek) waarbij gedeelde delen één keer worden opgelost en vervolgens vele malen worden geraadpleegd.

2. De Kernontdekking: De "Exponentiële" Kloof

De belangrijkste bevinding van het artikel gaat over stapelcomplexiteit. In eenvoudige termen betekent dit: "Hoeveel voorbeelden moet de student bestuderen om goed te worden in de taak?"

De auteurs bewijzen dat als een probleem het herhaaldelijk opnieuw gebruiken van een moeilijk sub-stap vereist, de "Vlakke" student dat moeilijke stap exponentieel vaker in hun trainingsdata moet zien dan de "Hiërarchische" student.

De Analogie van de Bibliotheek:

Vlakke Student: Om te leren hoe je een boek schrijft dat 1.000 keer een beroemd gedicht citeert, moet deze student het hele boek 1.000 keer lezen en de 10 regels van het gedicht elke keer opnieuw memoriseren. Ze hebben een enorme bibliotheek aan boeken nodig om dit te leren.
Hiërarchische Student: Deze student leest het boek één keer. Ze memoriseren de 10 regels van het gedicht één keer en zetten ze in een "Citatiedoos". Wanneer ze het opnieuw moeten citeren, wijzen ze gewoon naar de doos. Ze hebben een kleine bibliotheek nodig om hetzelfde te leren.

Het artikel laat zien dat als het "gedicht" (het moeilijke sub-bewijs) moeilijk is, de Vlakke student misschien miljoenen voorbeelden nodig heeft om het te leren, terwijl de Hiërarchische student misschien slechts tientallen nodig heeft. Het verschil is niet een beetje; het is een exponentiële kloof.

3. Waarom gebeurt dit?

De auteurs modelleren dit met een concept dat een MDP (Markov Beslissingsproces) wordt genoemd, wat gewoon een chique manier is om een spel met regels, toestanden en zetten te beschrijven.

De Leraar: Een perfecte oplossing die de student succesvolle bewijzen laat zien.
De Data: De student leert door deze succesvolle bewijzen te bekijken.
Het Probleem: Als het bewijs van de leraar vijf keer een slimme afkorting (een lemma) gebruikt, ziet de "Vlakke" weergave van de data eruit als vijf aparte, lange, moeilijke paden. De student moet vijf aparte paden leren.
De Oplossing: De "Hiërarchische" weergave ziet dat die vijf paden eigenlijk slechts één pad zijn dat wordt herhaald. De student hoeft alleen dat ene pad te leren.

Het artikel levert wiskundige formules (grenzen) om te bewijzen dat het aantal trainingsvoorbeelden dat nodig is voor de Hiërarchische student klein blijft, terwijl het aantal dat nodig is voor de Vlakke student explodeert naarmate het probleem dieper wordt.

4. Wat dit betekent voor AI Bewijsvoeringssystemen

Het artikel richt zich op Agentic Theorema Bewijzers – AI-systemen die proberen wiskundige stellingen te bewijzen. Deze systemen proberen vaak grote problemen op te splitsen in kleinere "subdoelen" of "lemma's".

Het Standpunt van de Scepticus: "Waarom moeite doen om het op te splitsen? Het bewijzen van het kleine lemma is moeilijk. Waarom tijd verspillen eraan?"
Het Antwoord van het Artikel: "Omdat als je het niet opsplitst en de oplossing niet opnieuw gebruikt, je datzelfde moeilijke probleem keer op keer opnieuw moet oplossen. De 'verspilling' van het één keer oplossen van het lemma is eigenlijk een enorme besparing vergeleken met het duizend keer oplossen."

Samenvatting

Stel het je voor als het bouwen van een huis:

Vlakke Aanpak: Je bouwt het huis door elke enkele baksteen individueel te leggen, zelfs als je hetzelfde muurpatroon 100 keer moet bouwen. Je hebt een berg bakstenen en veel tijd nodig.
Hiërarchische Aanpak: Je bouwt één keer een "muurmodule". Vervolgens stapel je die voorgefabriceerde module gewoon 100 keer. Je hebt veel minder grondstoffen en minder tijd nodig.

Het artikel bewijst wiskundig dat voor complexe problemen de "module"-aanpak (hiërarchisch) exponentieel minder trainingsvoorbeelden nodig heeft om te leren dan de "steen-voor-steen"-aanpak (vlak). Dit verklaart waarom moderne AI bewijsvoeringssystemen die "lemma's" en "subdoelen" gebruiken statistisch efficiënter zijn dan die welke proberen alles in één lange, vlakke lijn op te lossen.

Titel: Exponentiële Steekproefcomplexiteitsseparatie tussen Vlakke en Hiërarchische Agentische Theoremaprovers

Auteurs: Sho Sonoda, Shunta Akiyama, Yuya Uezato
Affiliaties: CyberAgent, RIKEN AIP
Datum: 7 mei 2026

1. Probleemstelling

Recente agentische theoremaprovers maken vaak gebruik van decompositiestrategieën – zoals het genereren van tussenliggende lemma's, bewesschetsen of subdoel-decomposities – voordat ze een zoektocht op tactica-niveau starten. Hoewel de klassieke bewistheorie suggereert dat lemma's afleidingen kunnen verkorten, blijft de statistische leerkost van het ontdekken en bewijzen van deze tussenstappen een open vraag. Specifiek: als het bewijzen van een lemma op zichzelf moeilijk is, waarom zou een geleerde prover dan moeite steken in het bewijzen ervan?

Het artikel behandelt het statistische leerprobleem of het leren van een herbruikbare bewijsstructuur (hiërarchisch) de kans vergroot om binnen een vast zoekbudget een geverifieerd bewijs te vinden, vergeleken met leren uit volledig ingevoegde bewijstraces (vlak). De auteurs focussen op de data-distributie die wordt gegenereerd door een "leraar"-prover, bestaande uit initiële stellingen en succesvolle geverifieerde bewijstraces, in plaats van de worst-case bewijscomplexiteit over alle formules.

2. Methodologie

De auteurs modelleren theoremaproving als een deterministisch Markov-beslissingsproces (MDP) met een eindige horizon, waarbij toestanden bewijstoestanden zijn en acties tactieken, inferentieregels of hoog-niveau decompositiebewegingen. Ze analyseren offline imitatielearning uit succesvolle leraar-traces onder drie verschillende scenario's:

Scenario 1 (Vlak): De leraar genereert volledig ingevoegde laag-niveau bewijstraces. De student imiteert deze traces zonder graafvoorspelling of memoization. Herhaalde subbewijzen verschijnen als distincte, gekopieerde voorkomens in de trainings- en testdata.
Scenario 2 (Hiërarchisch): De leraar construeert een hoog-niveau bewijs-Directed Acyclic Graph (DAG) waarbij knopen herbruikbare bewijsblokken vertegenwoordigen. De student leert een graafvoorspeller en beleidsregels voor hoog-niveau graafacties (selecteren, uitbreiden, hergebruiken van blokken) en laag-niveau lokaal oplossen. De trainingsdata bestaat uit ingevoegde traces, waardoor de student de latente bewijs-DAG-structuur moet afleiden.
Scenario 3 (Vergelijking): Zowel een vlakke student als een hiërarchische student worden getraind op dezelfde brondata gegenereerd door de hiërarchische leraar (ingevoegde traces). De vlakke student verwijdert de latente graafstructuur, terwijl de hiërarchische student deze afleidt. Dit scenario isoleert het effect van representatie op de steekproefcomplexiteit.

De analyse rust op drie sleutelgrootheden:

$L$ (Gemiddelde Lengte): Het gemiddelde aantal beslissingen in een succesvol bewijs.
$\eta$ (Intrinsieke Zoekverlies): De waarschijnlijkheidsmassa die verloren gaat omdat de volgende actie van de leraar niet in de top- $k$ kandidatenlijst van de student staat (lokale voorspelbaarheid).
$e$ (Imitatiefout): De Kullback-Leibler (KL)-divergentie tussen het beleid van de student en het beleid van de leraar.

De auteurs veronderstellen een Tsybakov-type randvoorwaarde om imitatiefout om te zetten in een top-k-uitsluitingswaarschijnlijkheid en veronderstellen zoekvolledigheid als de acties van de leraar binnen de top- $k$ -lijst van de student vallen.

3. Belangrijkste Bijdragen

Formalisatie: Het artikel formuleert verifieergestuurde theoremaproving als een MDP met een eindige horizon en definieert "statistische bewijsbaarheid" als de gemiddelde kans om binnen een budget een geverifieerd bewijs te vinden over een distributie van initiële toestanden.
Succesgaranties: De auteurs leiden eindige-steekproef succesgrenzen af voor zowel vlakke studenten (getraind op ingevoegde traces) als hiërarchische studenten (getraind om herbruikbare DAG's te voorspellen). De grenzen scheiden expliciet het aantal beslissingen, intrinsiek top-verlies en geleerde rangschikkingsfout.
Exponentiële Separatie: Het primaire theoretische resultaat is een exponentiële separatie in voldoende steekproefcomplexiteit. Wanneer een herbruikbare bewijs-DAG wordt platgelegd tot een boom, worden identieke subbewijzen exponentieel vaak gedupliceerd. Het artikel bewijst dat het voldoende-steekproefcertificaat voor de hiërarchische leerder exponentieel kleiner kan zijn dan dat van de vlakke leerder, zelfs wanneer ze op dezelfde brondata worden getraind.
Latente Graaflearning: Het artikel levert leersnelheden voor een hiërarchische student die latente bewijs-DAG's moet afleiden uit ingevoegde traces met behulp van een EM-achtige posterior-gewogen aanpak, rekening houdend met graafvoorspellingsfouten en posterior-mismatch.

4. Resultaten

Het kernresultaat wordt gepresenteerd in Stelling 6, die de gecertificeerde voldoende steekproefaantallen ( $\bar{N}$ ) vergelijkt die nodig zijn voor de vlakke en hiërarchische studenten om een doel-faalkans $\delta$ te bereiken.

Vlakke Grens: $\bar{N}_{flat}(\delta) \propto (L_{flat}/\delta)^{1/(p\gamma)}$
Hiërarchische Grens: $\bar{N}_{hier}(\delta) \propto \max(L_{hi}, L_{lo}/\delta)^{1/(p\gamma)}$

Waarbij $L_{flat}$ de lengte van de uitgevouwen trace is en $L_{hier} = L_{hi} + L_{lo}$ de lengte van de hiërarchische representatie.

Het artikel toont aan dat voor een familie stellingen geïndexeerd door een grootte/depth-parameter $D$ , als het platleggingsproces de bewijslengte exponentieel doet groeien ( $L_{flat}/L_{hier} = \exp(\Omega(D))$ ), dan de verhouding van vereiste steekproeven ook exponentieel groeit:
$\bar{N}_{flat}(\delta) / \bar{N}_{hier}(\delta) \geq \exp(\Omega(D))$

Deze separatie ontstaat omdat de vlakke leerder hetzelfde harde lokale argument onafhankelijk voor elke voorkoming moet leren, terwijl de hiërarchische leerder het gedeelde blok eenmaal leert en hergebruikt. Het artikel gebruikt een cut-eliminatie-voorbeeld (Bijlage G) om te illustreren hoe het verwijderen van tussenliggende lemma's (platleggen) de bewijsgrootte exponentieel kan laten exploderen, waardoor de steekproefcomplexiteit voor vlakke leerlingen wordt opgeblazen.

5. Betekenis en Claims

Het artikel claimt een concreet statistisch mechanisme te bieden dat uitlegt waarom hiërarchisch bewijzen helpt, onderscheiden van worst-case bewijscomplexiteitsargumenten. De betekenis ligt in het identificeren dat het voordeel van decompositie niet alleen gaat over het verkorten van de logische afleiding, maar over het verminderen van de statistische last op de leerder.

Bewustzijn van Data-distributie: Het resultaat benadrukt dat de efficiëntie van leren afhangt van de structuur van de data-distributie. Als succesvolle bewijzen tussenliggende argumenten hergebruiken, vangt een hiërarchische representatie deze deling op, terwijl een vlakke representatie deze vernietigt, wat leidt tot redundante leertaken.
Beperkingen: De auteurs zijn bescheiden in hun claims. Ze stellen dat dit geen worst-case ondergrens is en niet uitsluit dat vlakke leerlingen perfect kunnen canonicaliseren (perfect identieke subproblemen herkennen zonder expliciete hiërarchie). De separatie geldt specifiek wanneer platleggen herbruikbare bewijsstructuur vernietigt en de data-distributie bewijzen bevat waarbij dergelijke deling prevalent is.
Praktische Implicatie: De bevindingen suggereren dat voor verifieer-based theoremaproving, het leren om herbruikbare bewijsstructuren (lemma's, subdoelen) te voorspellen, de steekproefcomplexiteit exponentieel kan verminderen die nodig is om een bepaalde succeswaarschijnlijkheid te bereiken, mits de graafvoorspeller het certificaat van de leraar met hoge waarschijnlijkheid kan dekken.

Het artikel concludeert dat de "duur omweg" van het bewijzen van lemma's statistisch gerechtvaardigd is wanneer die lemma's herbruikbaar zijn, aangezien de kost van het eenmaal leren ervan veel lager is dan de kost van het herhaaldelijk opnieuw ontdekken ervan in een vlak kader.