Technische Samenvatting: Wanneer meer sampling schadelijk is: Het modale plafond en het correlatieplafond van test-time scaling

Probleemstelling

Huidige redeneersystemen maken vaak gebruik van test-time scaling, specifiek herhaalde sampling (het genereren van $n$ responsen op één enkele prompt), om de prestaties te verbeteren. De gangbare metriek voor succes is coverage (pass@k), gedefinieerd als het fractie van problemen waarbij ten minste één van de $n$ samples correct is. Coverage-curves stijgen doorgaans gestaag naarmate $n$ toeneemt, wat suggereert dat het simpelweg verhogen van het sampling-budget leidt tot continue capaciteitswinsten.

Deployed systemen moeten echter een enkel antwoord teruggeven zonder toegang tot een perfecte verifieerder om juistheid te certificeren. Dit vereist selectie (bijv. via meerderheidsstemming, self-consistency, of reward modellen). Het artikel identificeert een kritieke discrepantie: terwijl de coverage doorgaans blijft stijgen bij meer samples, stagneert de selectie-accuratesse vaak of daalt deze zelfs. Het kernprobleel is dat de gemeenschap het vermogen om een correct antwoord te genereren verward met het vermogen om het te herkennen en te selecteren. Het artikel betoogt dat voorbij een bepaald punt, extra sampling computationele kosten toevoegt zonder de prestaties te verbeteren, en het uiteindelijke geselecteerde antwoord zelfs kan schaden.

Methodologie

Het artikel herkadert test-time sampling vanuit het perspectief van cluster sampling uit de survey-statistiek, in plaats van onafhankelijke trekkingen.

1. Cluster Sampling Framework: Een enkele prompt en de $n$ herhaalde pogingen worden behandeld als een cluster. De pogingen worden gemodelleerd als uitwisselbare (exchangeable) binaire variabelen (correct/incorrect) in plaats van onafhankelijke en identiek verdeelde (i.i.d.) variabelen.
2. Intraclass Correlatie ($\rho$): De afhankelijkheid tussen pogingen op hetzelfde probleem wordt gekwantificeerd door de intraclass correlatie $\rho$.
   • Tussen-probleem correlatie ($\rho_b$): Ontstaat door de heterogeniteit van de probleemcomplexiteit.
   • Binnen-probleem correlatie ($\rho_w$): Ontstaat door de interne staat van het model of de decoding-configuratie.
3. Effectieve Sample Grootte ($n_{eff}$): Gebruikmakend van de design effect ($deff = 1 + (n-1)\rho$), leidt het artikel het effectieve aantal onafhankelijke samples af:
   $$n_{eff} = \frac{n}{1 + (n-1)\rho}$$
   Deze grootte convergeert naar een correlatieplafond van $1/\rho$ wanneer $n \to \infty$.
4. Scheiding van Metrieken: De analyse ontkoppelt expliciet drie verschillende doelstellingen:
   • Coverage: De waarschijnlijkheid dat ten minste één correct antwoord wordt gegenereerd.
   • Selectie: De waarschijnlijkheid dat het meest voorkomende antwoord (de modus) correct is.
   • Estimatie: De precisie van het schatten van de gemiddelde accuratesse van de benchmark.

Kernbijdragen

1. Het Correlatieplafond (Estimatie-limiet)

Het artikel stelt vast dat voor het schatten van de benchmark-accuratesse, het effectieve aantal samples niet groter kan zijn dan $1/\rho$.

• Mechanisme: Naarmate $n$ toeneemt, neemt de marginale waarde van elk extra sample kwadratisch af ($O(1/n^2)$).
• Resultaat: Zelfs met enorme budgetten (bijv. $10^4$ samples), als $\rho \approx 0.5$, is de effectieve informatie gelijk aan slechts $\approx 2$ onafhankelijke samples. Dit verklaart waarom de schattingen van de benchmark-accuratesse een plateau bereiken ondanks massale sampling-inspanningen.

2. Het Modale Plafond (Selectie-limiet)

Het artikel identificeert een distinct plafond voor selectiemethoden (self-consistency, plurality voting) dat onafhankelijk is van het correlatieplafond.

• Mechanisme: Selectie convergeert naar de modus van de antwoordverdeling ($a^*_q$). Als het meest voorkomende antwoord incorrect is ($a^*_q \neq c_q$), lost het verhogen van $n$ de fout niet op; het maakt het model slechts zelfverzekerder in het foute antwoord.
• Resultaat: De selectie-accuratesse wordt begrensd door de modale hit-rate ($\pi_{mode}$), de waarschijnlijkheid dat het meest frequente antwoord van het model correct is.
• Anti-scaling: Op problemen waar de modus fout is maar het correcte antwoord wel bereikbaar is, zorgt het verhogen van $n$ ervoor dat de selectie-accuratesse daalt richting 0, terwijl de coverage stijgt richting 1. Dit fenomeen wordt anti-scaling genoemd.

3. De Identificeerbaarheidskloof (Identifiability Gap)

Het artikel definieert de identificeerbaarheidskloof als de set problemen waar het correcte antwoord aanwezig is in de sample-pool (hoge coverage) maar niet het meest frequente antwoord is (lage selectie).

• Dit representeert de "oplosbare maar onselecteerbare" problemen.
• Het artikel toont aan dat deze kloof significant is in real-world logs, waar de coverage 1.00 kan bereiken terwijl self-consistency stagneert op 0.87 (GSM8K) of 0.45 (MATH).

4. Empirische Validatie op Real-world Logs

De auteurs valideren hun theoretische framework met behulp van vrijgegeven sampling-logs:

• Brown et al. [2] (Onafhankelijke Trekkingen): Analyseerde GSM8K en MATH datasets. Vond een hoge tussen-probleem correlatie ($\hat{\rho}_b \approx 0.4\text{--}0.6$), wat het correlatieplafond voor estimatie bevestigt. Observeerde de divergentie tussen coverage (stijgend naar 1.0) en self-consistency (stagnerend).
• Beeching et al. [20] (Afhankelijke Trekkingen): Analyseerde MATH-500 met 256 samples per probleem. Vond dat de binnen-probleem correlatie ($\hat{\rho}_w$) nabij nul ligt, maar dat de antwoordverdeling zeer geconcentreerd is (mediaan ~13 verschillende waarden). Dit bevestigde dat het selectieplafond wordt gedreven door antwoord-modus collaps, en niet door run-to-run drift.

Resultaten

• Coverage vs. Selectie: Coverage volgt een power-law stijging (door de heterogeniteit van de moeilijkheidsgraad) en heeft geen hard plafond behalve de modelcapaciteit. Selectie daarentegen raakt een harde muur bij $\pi_{mode}$.
• Verminderende Meeropbrengsten: De marginale waarde van de $n$-de sample neemt snel af. Voor estimatie moet het budget worden beperkt tot $n \approx 1/\rho$. Voor selectie moet het budget worden beperkt tot het effectieve aantal unieke antwoorden.
• Inefficiëntie van grote $n$: Het samplen van $10^4$ keer per probleem levert de statistische precisie op van slechts ~2 onafhankelijke samples voor benchmark-estimatie.
• Anti-scaling: In scenario's waar het meest voorkomende antwoord van het model fout is, verslechtert het verhogen van $n$ de accuratesse van het geselecteerde output actief.

Betekenis en Claims

Het artikel claimt een citeerbare afleiding te bieden in plaats van een nieuw algoritme. De primaire betekenis ligt in:

1. Herformulering van de Bottleneck: Het verschuift de focus van test-time scaling van "een juist antwoord genereren" naar "één herkennen". De bottleneck is niet het sampling-budget, maar de identificeerbaarheid van het correcte antwoord binnen de distributie.
2. Correctie van Misinterpretaties: Het verklaart waarom "meer sampling" in de praktijk vaak niet lineair schaalt, door dit toe te schrijven aan het correlatieplafond (voor estimatie) en het modale plafond (voor selectie).
3. Actiegerichte Metrieken: Het stelt voor om het effectieve aantal samples ($n_{eff}$) te rapporteren naast het nominale aantal $n$ om de werkelijke informatieve inhoud van een sampling-run te onthullen.
4. Budgetallocatie: Het betoogt dat computationele budgetten doelafhankelijk moeten zijn:
   • Voor estimatie: Stop bij $n \approx 1/\rho_b$ en besteed het resterende rekenvermogen aan meer problemen.
   • Voor selectie: Stop zodra de meerderheid (plurality) stabiliseert (vaak binnen enkele tientallen samples) en focus op decorrelatie (bijv. temperatuur, prompt diversiteit) in plaats van het verhogen van $n$.
   • Voor coverage (met een verifieerder): Sampling kan onbeperkt doorgaan omdat er geen binnen-probleem plafond is.

Het artikel concludeert dat de "modale plafond" en het "correlatieplafond" fundamentele limieten zijn die willekeurige test-time scaling inefficiënt maken. De echte uitdaging is niet het genereren van meer samples, maar het ontwerpen van systemen die het correcte antwoord beter kunnen onderscheiden van de modale fout.