Technische Samenvatting: Leren Redeneren met Curriculum II: Compositionele Generalisatie

1. Probleemstelling

Het artikel onderzoekt de theoretische fundamenten van compositionele generalisatie—het vermogen om complexe problemen op te lossen door oplossingen voor eenvoudigere deelproblemen te combineren—een mechanisme dat centraal staat in chain-of-thought (CoT) redeneren in kunstmatige intelligentie. De kernvraag die wordt behandeld is: Wanneer en waarom levert het ontleden van een probleem in delen een efficiëntere leerervaring op dan het direct oplossen ervan?

Om dit te beantwoorden, formaliseren de auteurs het probleem met behulp van semiautomata-simulatie. Een semiautomaton wordt gedefend door een onbekende, Markoviaanse, stationaire transitiefunctie $\pi^*: S \times \Sigma \to S$. Gegeven een initiële toestand $s_0$ en een invoerwoord $w_{1:T}$, is het doel om de terminale toestand $s_T$ te voorspellen na $T$ stappen. De intermediaire toestanden $s_{1:T}$ vormen een chain of thought. Dit model vangt state tracking, reguliere taalherkenning en modulaire rekenkunde op.

Het artikel bestudeert twee specifieke leeromgevingen:

1. Interactieve Chain-of-Thought Supervisie (iSFT): De leerling heeft toegang tot een oracle dat de toestand op elk stap $t$ van een berekening kan retourneren tegen een kostenpost van één eenheid. Het doel is om het aantal oracle-queries (query-complexiteit) en trainingsinstanties (sample-complexiteit) te minimalen die nodig zijn om een model met een lage foutmarge te leren.
2. Reinforcement Learning met Verifieerbare Beloningen (RLVR): De leerling heeft toegang tot een vooraf getraind "zwak" referentiemodel $\pi_{ref}$ dat korte instanties van lengte $B \ll T$ met een constante waarschijnlijkheid kan oplossen, en een outcome verifier die de correctheid van een terminale toestand-gok controleert. Het doel is om het referentiemodel te verbeteren zodat het instanties van lengte $T$ efficiënt kan oplossen, waarbij de exponentiële daling in succeswaarschijnlijkheid die optreedt bij het uitrollen van een zwak model over lange horizonten wordt overwonnen.

2. Methodologie

De auteurs stellen autocurriculum-gebaseerde benaderingen voor die lange sequenties recursief ontleden in kortere deelproblemen, deze oplossen, en de oplossingen componeren. Deze aanpak bouwt voort op Deel I van de serie, gebruikmakend van een template van compositie en boosting.

Kerncomponenten van het algoritme

• Compositie: Een model dat getraind is om instanties van lengte $\tau$ op te lossen, kan $L$ keer gecomponeerd worden (waarbij $T = L\tau$) om instanties van lengte $T$ op te lossen. Echter, fouten accumuleren onder compositie; daarom moeten de kort-bereik modellen getraind worden met een hoge nauwkeurigheid.
• Boosting: Om de nodige hoge nauwkeurigheid op korte deelproblemen te bereiken, gebruiken de auteurs een multiscale boostingstrategie. Dit houdt in dat een ensemble van zwakke leerlingen wordt getraind op hergewogen distributies die zich richten op "moeilijke" instanties (waar het huidige ensemble faalt) en deze aggregeert (bijv. via een meerderheidsstemming).
• Zelf-gegenereerd Curriculum: In plaats van een vastgesteld schema, selecteert de leerling adaptief op welke deelproblemen getraind moet worden op basis van de mislukkingen van modellen die getraind zijn op fijnere schalen.

Belangrijke Technische Innovaties

• Inverted Sampling: Een centrale technische bijdrage is een nieuwe samplingtechniek om de distributieverschuiving te behandelen die inherent is aan boosting. Standaard rejection sampling vanuit hergewogen mengsels van marginalen is inefficiënt (vereist $\Omega(L)$ samples in het slechtste geval). De auteurs introduceren inverted sampling, waarbij eerst onafhankelijk rejection sampling wordt toegepast op alle $L$ sub-instanties binnen een lange sequentie, en vervolgens één van de geaccepteerde instanties uniform wordt geselecteerd. Dit bereikt een acceptatiekans die proportioneel is aan het aantal sub-instanties, wat de sample-complexiteit aanzienlijk vermindert terwijl voldoende benaderingsgaranties voor het leeralgoritme behouden blijven.
• Multiscale Recursie: Het algoritme (AutoLearn) past de boosting + compositie template recursief toe. Het ontleedt instanties van lengte $T$ in deelproblemen van lengte $\tau$, die verder worden ontleed tot lengte-1 (next-token prediction) wordt bereikt. Dit creëert een hiërarchie waarbij modellen die kortere, makkelijkere problemen oplossen, worden gecomponeerd om moeilijkere problemen op te lossen.
• Guess-and-Check voor RLVR: In de RLVR-setting, waar intermediaire state labels niet direct beschikbaar zijn, simuleren de auteurs de interactieve oracle met behulp van het zwakke referentiemodel en de verifier. Door rollouts voor elk blok te genereren en de terminale toestand van het blok te verifiëren, kunnen ze effectief de intermediaire toestanden "labelen" om het curriculum te construeren.

3. Belangrijkste Bijdragen en Resultaten

Setting I: iSFT (Interactieve Supervisie)

Het artikel presenteert AutoLearn, een algoritme dat semiautomata leert met een subpolynomiale query- en sample-complexiteit in de sequentielengte $T$.

• Resultaat: De query- en sample-complexiteit zijn begrensd door $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$.
• Vergelijking: Dit doorbreekt de $\Omega(T)$ barrière die inherent is aan directe simulatiemethoden.
  • Full CoT Supervision: Vereist $\Omega(T)$ queries per instantie om elke toestand te labelen.
  • End-to-End Feedback: Vereist $\Omega(T)$ sample-complexiteit vanwege het onvermogen om te generaliseren van terminale toestanden zonder intermediaire gronding.
• Mechanisme: Door adaptief sub-problemen te selecteren en inverted sampling te gebruiken om distributieverschuiving te beheren, bereikt AutoLearn een complexiteit die subpolynomial is in $T$, specifiek $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$.

Setting II: RLVR (Verifieerbare Beloningen)

Het artikel presenteert AutoLearn.RL, die een zwak referentiemodel $\pi_{ref}$ verbetert van blok-niveau competentie ($B$) naar volledige lengte competentie ($T$).

• Resultaat: Het algoritme bereikt een hoge nauwkeurigheid op instanties van lengte $T$ met kosten die worden bepaald door de dekking van het referentiemodel op de kortere bloklengte $B$, in plaats van de volledige lengte $T$.
• Dekkingsexpansie: Standaard RLVR-methoden vereisen dat het referentiemodel een niet-triviale dekking heeft op lengte $T$, wat exponentieel onwaarschijnlijk is als het alleen dekking heeft op lengte $B$ (d.w.z. $C^{(T)}_{seq} \approx (C^{(B)}_{seq})^{T/B}$). AutoLearn.RL vermindert deze vereiste tot dekking op lengte $B$.
• Complexiteit:
  • Sample-complexiteit: $\tilde{\mathcal{O}}(d/\varepsilon)$.
  • Query-complexiteit: $\tilde{\mathcal{O}}(d/\varepsilon) + \tilde{\mathcal{O}}(\frac{T}{B} \cdot d C^{(B)}_{ans} + d C^{(B)}_{seq})$.
  • Computationele kosten: $\tilde{\mathcal{O}}(dT/\varepsilon) + \tilde{\mathcal{O}}(dT C^{(B)}_{ans} + dB C^{(B)}_{seq})$.
• Significantie: De "burn-in" kosten zijn afhankelijk van de dekking op de korte schaal $B$, waardoor de effectieve dekking op lengte $T$ kan expanderen van exponentieel klein naar constant door het curriculum.

4. Betekenis en Claims

Het artikel claimt dat compositie gecombineerd met een zelf-gegenereerd curriculum een superpolynomiale reductie kan bereiken in supervisie- en computationele kosten vergeleken met niet-curriculum gebaseerde baselines.

• Theoretische Fundering: Het biedt een rigoureus theoretisch kader dat uitlegt waarom het ontleden van problemen hels: het stelt de leerling in staat om de sequentielengte af te wegen tegen de nauwkeurigheidseisen via compositie, terwijl boosting de noodzakelijke nauwkeurigheid op deelproblemen garandeert.
• Efficiëntie: De resultaten laten zien dat voor taken zoals semiautomata-simulatie, leren kan worden bereikt met $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ complexiteit, een drastische verbetering ten opzichte van de lineaire $\Omega(T)$ complexiteit van standaard benaderingen.
• Generalisatie: De bevindingen suggereren dat autocurricula, waarbij de leerling zijn eigen problemen ontwerpt, niet slechts heuristieken zijn maar theoretisch gerechtvaardigd kunnen worden als een mechanisme om de statistische en computationele barrières van langdurige redenering te overwinnen.
• Beperkingen en Toekomstig Werk: De auteurs erkennen vereenvoudigingen, zoals het beperken van de modelklasse tot Markoviaanse modellen (wat volledige historie-attention zoals Transformers uitsluit) en het aannemen van deterministische transities. Ze merken op dat het uitbreiden van deze resultaten naar niet-Markoviaanse modellen en stochastische transities een belangrijke richting is voor toekomstig onderzoek. Ze benadrukken ook dat hoewel hun huidige resultaten een subpolynomiale afhankelijkheid van $T$ bereiken, het bereiken van een polylogaritmische afhankelijkheid een open vraag blijft, wat mogelijk sterkere aannames vereist zoals eindige foutgrenzen (finite mistake bounds).

Samenvattend stelt het artikel vast dat compositionele generalisatie, wanneer gestuurd door een adaptief curriculum en ondersteund door technieken zoals inverted sampling, een bewezen efficiënt pad biedt voor het leren van complexe sequentiële taken die onhandelbaar zijn voor directe leermethoden.