Technische Samenvatting: Voorbij de Grens: Stochastische Terugvervolging voor Efficiënte Schaling tijdens Testtijd

Probleemstelling

Schaling tijdens testtijd (TTS) heeft tot doel het redeneren van Large Language Models (LLM) te verbeteren door extra rekenkracht tijdens de inferentie toe te wijzen om meerdere oplossingspaden te verkennen. Hoewel Process Reward Models (PRM) zijn opgekomen als een standaardmechanisme om dit zoeken te sturen door tussenliggende voorvoegsels te scoren, lijden de huidige state-of-the-art methoden aan een kritieke beperking: zoekopdrachten die uitsluitend de grens (frontier) betreffen.

Bij benaderingen die uitsluitend de grens betreffen (bijvoorbeeld standaard Beam Search, SMC) wordt de zoektoestand beperkt tot nieuw gegenereerde kinderen op elk moment. Eerder gegenereerde voorvoegsels worden onomkeerbaar gesnoeid op basis van ruisachtige PRM-scores. Dit creëert een faalmodus van "voortijdige toewijzing":

1. Onomkeerbare Beslissingen: Een voorvoegsel dat correct laag wordt gescoord vanwege PRM-ruis (of een mismatch tussen de trainingsrollout van de PRM en de ingezette basis-LLM) wordt permanent verworpen, zelfs als het een correcte voortzetting toelaat.
2. Ineenstorting van Diversiteit: Te hoog gescoord incorrecte voorvoegsels domineren de zoektocht, waardoor het systeem rekenkracht verspilt aan onproductieve paden terwijl toegang tot potentieel correcte historische staten verloren gaat.
3. Inefficiëntie: Het onvermogen om historische staten opnieuw te bezoeken, dwingt het model om excessive tokens te besteden om zich te herstellen van vroege snoefouten.

Methodologie

Het artikel stelt Stochastische Terugvervolging over een Persistente Pool voor, een raamwerk dat een pool van historische voorvoegsels met lineair geheugen onderhoudt, waardoor de zoektocht eerder gegenereerde staten opnieuw kan bezoeken en uitbreiden in plaats van beperkt te blijven tot de huidige grens. De auteurs concretiseren dit raamwerk met twee complementaire algoritmen:

1. Subpool-selectie (SPS)

SPS adresseert het "blokkerprobleem" bij greedige selectie, waarbij te hoog gescoord incorrecte voorvoegsels permanent toegang blokkeren tot correcte maar lager gescoord historische voorvoegsels.

• Mechanisme: In plaats van de top-$M$ kandidaten te selecteren uit de volledige persistente pool (wat hoge-score blokkers begunstigt), construeert SPS een willekeurige subpool $D_t$ van grootte $K_t$ uit de historische pool $P_{t-1}$.
• Selectie: Vervolgens selecteert het de top-$M$ kandidaten strikt binnen deze willekeurige subpool.
• Adaptieve Ratio: De grootte van de subpool wordt bepaald door een adaptieve ratio $\rho_t$, berekend op basis van het gemiddelde PRM-score van de huidige pool. Als de pool weinig vertrouwen heeft (laag gemiddeld score), is de subpool kleiner om hoge-score incorrecte voorvoegsels te vermijden; anders is deze groter.
• Effect: Deze stochastische sampling geeft "geblokkeerde" historische voorvoegsels een kans om geselecteerd en uitgebreid te worden, waardoor de dominantie van te hoog gescoord grenskandidaten wordt omzeild.

2. Power Backtrack Sequential Monte Carlo (PB-SMC)

PB-SMC breidt Sequential Monte Carlo (SMC) methoden uit tot de persistente pool, waardoor stochastisch herstel mogelijk is van eerdere snoeibeslissingen.

• Persistente Pool Doel: In tegenstelling tot standaard SMC, deelt deeltjes beperkt tot de huidige grens, onderhoudt PB-SMC een pool die zowel nieuw gegenereerde kinderen als een behouden subset van historische voorvoegsels bevat.
• Gepowerde PRM-scores: De methode past een macht $\beta_t$ toe op PRM-scores ($r_{PRM}(z)^{\beta_t}$) om de beloningsverdeling scherper te maken, waardoor hoge-score voorvoegsels worden benadrukt en lage-score voorvoegsels worden afgezwakt.
• Gewichten gecorrigeerd voor Mengsels: Het algoritme behandelt de zoektocht als een Multiple Importance Sampling (MIS) probleem. Het definieert een mengselvoorstelverdeling $q_{mix}$ die combineert:
  • $q_{new}$: Nieuwe kinderen gegenereerd vanuit de vorige stap.
  • $q_{hist}$: Historische voorvoegsels behouden uit vorige stappen.
• Gewichtsberekening: Het leidt specifieke gewichten $W_t(z)$ af die corrigeren voor het mengselvoorstel, zodat de schatter convergeert naar de doelwit gepowerde proxy-verdeling. Dit stelt het systeem in staat om stochastisch historische deeltjes opnieuw te bemonsteren die eerder waren gesnoeid.

Geheugen- en Rekenkrachtefficiëntie

• Lineair Geheugen: De persistente pool slaat alleen tekststaten en PRM-scores op, geen volledige Key-Value (KV) caches. KV caches worden alleen opnieuw berekend wanneer een historisch voorvoegsel wordt geselecteerd voor uitbreiding.
• Overhead: Het artikel betoogt dat de rekenkrachtoverhead van het opnieuw berekenen van KV caches voor terugvervolgde staten verwaarloosbaar is in vergelijking met de winst in nauwkeurigheid en token-efficiëntie.

Belangrijkste Bijdragen

1. Identificatie van Falen bij Uitsluitend Grens: Het artikel identificeert onomkeerbare selectie die uitsluitend de grens betreft als een primaire faalmodus in PRM-gestuurde TTS, waarbij ruisachtige scores leiden tot permanent verlies van correcte oplossingspaden.
2. Raamwerk met Persistente Pool: Introductie van een alternatief met lineair geheugen dat historische voorvoegsels in aanmerking houdt voor toekomstige uitbreiding, waardoor zoektoegang wordt ontkoppeld van de directe grens.
3. Twee Nieuwe Algoritmen:
   • Subpool-selectie (SPS): Een verbetering van greedige zoektocht die willekeurige subpools gebruikt om te hoog gescoord blokkers te omzeilen.
   • Power Backtrack SMC (PB-SMC): Een SMC-extensie die gebruikmaakt van gepowerde PRM-scores en gewichten gecorrigeerd voor mengsels om stochastische terugvervolging mogelijk te maken.
4. Theoretische Waarborgen: Bewijs dat PB-SMC in waarschijnlijkheid convergeert naar het gepowerde PRM-gedefinieerde proxy-doelwit, waardoor asymptotische correctheid ten opzichte van het proxy-doelwit wordt gewaarborgd.

Experimentele Resultaten

De methoden werden geëvalueerd op vier wiskundige redeneringsbenchmarks (MATH500, AMC23, AIME24, Minerva Math) met drie LLM's (Qwen2.5-7B, Qwen2.5-3B, Phi-4-mini) en de Qwen2.5-Math-PRM-7B.

• Token-efficiëntie: Zowel SPS als PB-SMC behaalden concurrerende of superieure nauwkeurigheid met slechts $N=8$ kandidaten per stap, terwijl sterke baselines (Beam Search, SMC, DVTS) $N=32$ vereisten.
  • SPS: Verminderde tokenverbruik met gemiddeld 49,4% terwijl de nauwkeurigheid verbeterde.
  • PB-SMC: Verminderde tokenverbruik met gemiddeld 36,7% terwijl de nauwkeurigheid verbeterde.
• Nauwkeurigheidsverbeteringen:
  • Op Qwen2.5-7B-Instruct behaalde SPS een gemiddelde nauwkeurigheid van 54,66%, wat beter was dan DVTS (51,40%) en Beam Search (52,12%).
  • Op Phi-4-mini-Instruct behaalde PB-SMC de hoogste algehele nauwkeurigheid (48,69%).
• Ablatiestudies:
  • Terugvervolging: Het toevoegen van terugvervolging aan SMC (Backtrack SMC) verbeterde de gemiddelde nauwkeurigheid van 49,11% naar 52,27%.
  • Stochasticiteit: Het vervangen van globale greedige selectie door Subpool-selectie (SPS) verbeterde de gemiddelde nauwkeurigheid van 51,61% naar 54,66%.
• Uitvoeringstijd: Ondanks de potentiële overhead van het opnieuw berekenen van KV caches, waren de methoden ongeveer 2,5x sneller dan Beam Search vanwege de verkleinde grootte van de kandidaatset ($N=8$ versus $N=32$), met een verwaarloosbare uitvoeringstijdstraf (~10%) in vergelijking met de dichtstbijzijnde concurrerende baselines.

Betekenis en Claims

Het artikel beweert dat stochastische terugvervolging met persistente pool een eenvoudige en effectief mechanisme biedt om de afweging tussen nauwkeurigheid en tokens te verbeteren bij schaling tijdens testtijd. De kernbetekenis ligt in het verschuiven van de optimalisatiefocus van het louter scoren van voorvoegsels naar het behouden van toegang tot deze. Door de zoektocht toe te staan historische staten opnieuw te bezoeken, mitigeren de methoden de risico's van ruisachtige PRM-scores en voortijdige toewijzing.

De auteurs positioneren hun werk als een praktische oplossing voor implementaties met beperkte middelen, waarbij wordt aangetoond dat effectieve schaling tijdens testtijd geen enorme toename van rekenkracht vereist, maar eerder een intelligentere toewijzing van bestaande rekenkracht via zoektochten die rekening houden met de geschiedenis. De resultaten suggereren dat toegang tot geschiedenis een kritieke, vaak over het hoofd geziene factor is in het maximaliseren van de efficiëntie van LLM-redenering.