Technische Samenvatting: Een Relatieve Budgettheorie voor Reinforcement Learning met Verifieerbare Beloningen in LLM-redeneren

1. Probleemstelling

Reinforcement learning met verifieerbare beloningen (RLVR) is een dominante paradigm geworden voor het verbeteren van de redeneervaardigheden van Large Language Models (LLM's), wat langdurige planning en iteratieve zelfcorrectie mogelijk maakt. De empirische effectiviteit varieert echter aanzienlijk tussen taken en computationele budgetten. Bestaande theoretische kaders falen vaak in het verklaren van de dynamische relatie tussen taakcomplexiteit en computationele budgetten, met name in online leeromgevingen. Praktijkgebruikers missen richtlijnen voor het efficiënt toewijzen van computationele middelen, wat het risico met zich meebrengt dat enorme middelen worden toegewezen aan regimes waarin leren theoretisch inefficiënt is of waar het leersignaal verdwijnt.

Dit artikel adresseert de kloof in het theoretisch begrip door te analyseren hoe de verhouding tussen het beschikbare tokenbudget en de inherente moeilijkheid van een taak de steekproefefficiëntie en convergentie van RLVR bepaalt.

2. Methodologie en Theoretisch Kader

2.1. Het Relatieve Budget ($\xi$)

De auteurs introduceren een centrale grootheid genaamd het relatieve budget, gedefinieerd als:
$$\xi := \frac{H}{E[T]}$$
waarbij $H$ de generatiehorizon (tokenbudget) is en $E[T]$ het verwachte aantal tokens dat nodig is om de eerste correcte oplossing te bereiken onder een basisbeleid $\pi_b$. Deze metriek verenigt computationele beperkingen en taakcomplexiteit.

2.2. Modelleringsoverwegingen

Het redeneerproces wordt gemodelleerd als een eindige Markov-beslissingsproces (MDP) met binaire beloningen. De tijd-tot-oplossing $T(\tau)$ wordt geanalyseerd onder specifieke distributionele aannames:

• Momenten: De variantie van $T(\tau)$ schaalt met het kwadraat van het gemiddelde ($v_x = \Theta(\mu_x^2)$).
• Linkerstaartgedrag: De waarschijnlijkheid om een probleem binnen een fractie van de verwachte tijd op te lossen volgt een functie $f(z)$ die polynomiaal in plaats van exponentieel afneemt nabij de oorsprong.
• Gamma-distributie: Voor concrete analyse wordt $T(\tau)$ gemodelleerd met een Gamma-distributie, die dient als een continue benadering voor de discrete token-aantallen in complexe redeneertaken.

2.3. Analytische Aanpak

Het artikel analyseert de anti-concentiecoëfficiënt $c_0(\xi)$, die de waarschijnlijkheid vertegenwoordigt van het samplen van trajecten met een hoge beloning (oplossingen die aanzienlijk sneller worden gevonden dan het gemiddelde). Deze coëfficiënt reguleert direct de steekproefcomplexiteit van RL. De auteurs leiden eindige steekproefgaranties af voor online RL, waarbij de evolutie van $\xi$ over iteraties wordt gevolgd naarmate het beleid verbetert.

3. Belangrijkste Bijdragen en Theoretische Resultaten

Het artikel stelt vast dat de prestaties van RLVR worden beheerst door drie verschillende regimes gebaseerd op de waarde van $\xi$:

3.1. Drie Regimes van Leerefficiëntie

1. Tekortschietend Regime ($\xi \to 0$):
   • Conditie: Het tokenbudget $H$ is veel kleiner dan de verwachte tijd-tot-oplossing.
   • Dynamiek: Trajecten met een hoge beloning zijn extreem zeldzaam. De anti-concentiecoëfficiënt verdwijnt ($c_0 \to 0$), waardoor de steekproefcomplexiteit explodeert. Leren is theoretisch onuitvoerbaar.
2. Gebalanceerd Regime ($\xi = \Theta(1)$):
   • Conditie: Het tokenbudget is vergelijkbaar met de verwachte tijd-tot-oplossing.
   • Dynamiek: Informatieve trajecten komen voor met een niet-verwaarloosbare waarschijnlijkheid. De anti-concentiecoëfficiënt is begrensd weg van nul ($c_0 = \Theta(1)$), wat leidt tot maximale steekproefefficiëntie.
   • Contrast met SFT: Dit regime vormt een "sweet spot" voor RL, maar is het "worst-case" scenario voor Supervised Fine-Tuning (SFT). In het gebalanceerde regime is de heterogeniteit van succesvolle oplossingspaden (variërende lengtes en strategieën) gemaximaliseerd, wat imitatie-leren moeilijk maakt voor SFT.
3. Overvloedig Regime ($\xi \to \infty$):
   • Conditie: Het tokenbudget overstijgt de verwachte tijd-tot-oplossing aanzienlijk.
   • Dynamiek: Leren blijft stabiel met een begrensde anti-concentiecoëfficiënt. Echter, de marginale winst per iteratie neemt af naarmate de taak triviaal wordt ten opzichte van het budget, en de steekproefcomplexiteit neemt lineair toe met $\xi$.

3.2. Eindige Steekproefgaranties voor Online RL

De auteurs bewijzen dat in een online setting, naarmate het beleid verbetert, de verwachte tijd-tot-oplossing afneemt, waardoor het relatieve budget $\xi$ lineair groeit over iteraties.

• Stelling 6.4: Onder het Gamma-model drijft online RL $\xi$ naar een lineaire groei ($\xi_i - \xi_0 \geq i(2K)^{-1}$).
• Trade-off: Terwijl het beleid convergeert naar het tokenbudget $H$, vereist het behouden van een monotone verbetering in het overvloedige regime een toenemend aantal rollout-samples (kwadratische degradatie in steekproefcomplexiteit ten opzichte van $\xi$).

3.3. Optimale Budgetallocatie

Theoretische analyse met behulp van de Gamma-distributie identificeert een optimaal relatief budget $\xi^*$ dat het leersignaal (beloningsvariantie) maximaliseert terwijl een stabiele anti-concentiecoëfficiënt behouden blijft.

• Theoretische Voorspelling: Het optimale $\xi^*$ valt in het bereik $1.0 \leq \xi^* \leq 1.4$.
• Implicatie: Het toewijzen van een budget dat iets groter is dan de verwachte moeilijkheid ($\xi \gtrsim 1$) is cruciaal voor betrouwbare leersignalen.

4. Empirische Resultaten

De auteurs hebben hun theorie gevalideerd met standaard LLM's (Llama-3.2-3B, Phi-4-mini, Qwen3-4B) op redeneer-benchmarks (GSM8K, MATH-500).

• Faseovergang: Experimenten bevestigden een faseovergang bij $\xi \approx 1.0$. In het tekortschietende regime ($\xi < 0.8$) waren de beloningsvariantie en anti-concentie verwaarloosbaar.
• Piekleersignaal: Het leersignaal (beloningsvariantie) piekte in het bereik $\xi \in [1.5, 2.0]$, wat iets hoger is dan de theoretische minimumwaarde vanwege de lang-staart aard van token-generatiedistributies.
• Prestatiecorrelatie: De post-training nauwkeurigheid op redeneertaken vertoonde een scherpe stijging naarmate $\xi$ de 1 naderde (het gebalanceerde regime) en verzadigde in het overvloedige regime ($\xi > 2.0$).
• Modelrobuustheid: De theoretische voorspellingen bleven standhouden over verschillende modellen en datasets, zelfs voor modellen (zoals Qwen3) die bimodale token-distributies vertoonden, wat suggereert dat de kern van de theorie robuust is tegen specifieke distributionele afwijkingen.

5. Betekenis en Claims

Het artikel claimt een verenigd theoretisch kader te bieden dat de regime-afhankelijke successen van RLVR in LLM-redeneren verklaart. De primaire betekenis ligt in:

1. Definiëren van de "Grens van Bekwaamheid": Het rechtvaardigt theoretisch de empirische observatie dat RL het meest effectief is wanneer taken noch triviaal, noch onuitvoerbaar zijn, specifiek wanneer het computationele budget vergelijkbaar is met de inherente moeilijkheid van de taak.
2. Begeleiding van Computationele Allocatie: De theorie biedt een concreet richtlijn voor praktijkgebruikers: wijs tokenbudgetten toe zodanig dat $\xi \in [1.5, 2.0]$. Dit garandeert de aanwezigheid van informatieve trajecten zonder de verminderde meeropbrengsten van excessieve budgetten.
3. Verklaren van de RL vs. SFT Divergentie: Het verduidelijkt waarom verifier-gebaseerde RL beter presteert dan SFT bij het schalen van test-time compute, met name in het gebalanceerde regime waar heterogeniteit in oplossingen imitatie-leren hindert maar exploratie-gebaseerde RL juist helpt.
4. Duurzame AI-ontwikkeling: Door te identificeren wanneer RL verminderde meeropbrengsten oplevert, beoogt het kader verspillende trainingsruns te voorkomen, wat de financiële en milieukosten van grootschalige modeltraining vermindert.

De auteurs merken op dat hun analyse steunt op een continue proxy-beloning om de variantieanalyse hanteerbaar te maken, en dat het uitbreiden van de theorie naar strikt binaire beloningen een openstaand probleem blijft. De empirische overeenstemming met realistische settings suggereert echter dat het relatieve budget $\xi$ een fundamentele factor is in de effectiviteit van redeneringsgeoriënteerde RL.