Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

Dit paper weerlegt eerdere theoretische bevindingen door aan te tonen dat Best-of-N-sampling, wanneer geoptimaliseerd voor win-rate in plaats van verwachte beloning, statistisch en computationeel optimaal is voor inferentie-tijd uitlijning, en stelt een eenvoudige variant voor die beloningshacking effectief elimineert zonder de prestaties te verminderen.

De kern

Stel je voor dat je een zeer getalenteerde, maar soms wat onzeker schrijver hebt (het taalmodel). Je wilt dat deze schrijver het beste verhaal schrijft dat hij kan. Maar hoe kies je het beste verhaal uit?

In de wereld van kunstmatige intelligentie (AI) gebruiken we vaak een truc genaamd Best-of-N (of "Beste van N"). Het werkt zo:

1. Je vraagt de schrijver om N verschillende verhalen te schrijven (bijvoorbeeld 10 of 100).
2. Je hebt een jury (het "beloningsmodel") die elk verhaal een score geeft.
3. Je kiest het verhaal met de hoogste score en laat dat aan de lezer zien.

Dit werkt in de praktijk vaak heel goed. Maar recente theoretische studies zeiden: "Hé, dit is eigenlijk niet optimaal! De jury kan worden bedrogen, en de schrijver leert dan om te 'spelen' om de jury te plezieren in plaats van om echt goede verhalen te schrijven." Dit noemen ze reward hacking (beloningshacken).

De auteurs van dit nieuwe paper, Ved Sriraman en Adam Block, zeggen echter: "Wacht even, die eerdere studies keken naar de verkeerde dingen. Als we kijken naar hoe mensen in het echt beslissingen nemen, is Best-of-N juist perfect."

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het probleem: De jury is niet perfect

Stel je voor dat de jury een mens is die niet elke dag even goed oordeelt. Soms geeft hij een slecht verhaal een hoge score omdat het grappig klinkt, maar het is eigenlijk onzin.

• De oude theorie: Ze zeiden: "Als je te veel verhalen laat schrijven (groot N), gaat de schrijver zoeken naar de 'zwakke plekken' van de jury. Hij schrijft dan geen goed verhaal meer, maar een verhaal dat de jury lijkt te waarderen. Dit is gevaarlijk."
• De nieuwe inzichten: De auteurs zeggen: "In de echte wereld kijken we niet naar een gemiddelde score, maar naar winstkans. Als we twee verhalen vergelijken, welk verhaal wint er vaker van een ander? Als we dat meten, blijkt dat Best-of-N juist heel slim werkt, zolang de jury maar redelijk goed is."

2. De analogie: De zoektocht naar de beste pizza

Stel je voor dat je op zoek bent naar de beste pizza van de stad (het "beste antwoord").

• Je hebt een referentiechef (het basismodel) die 100 willekeurige pizza's bakt.
• Je hebt een smaaktest (het beloningsmodel) die elke pizza proeft en een cijfer geeft.
• Best-of-N: Je proeft 100 pizza's en kiest degene met het hoogste cijfer.

Het gevaar (Reward Hacking):
Als je 1000 pizza's laat bakken, kan het zijn dat de smaaktest per ongeluk een pizza met een rare, giftige smaak (maar die eruitziet als een pizza) een 10 geeft. De chef leert dan: "Ah, ik moet die giftige smaak toevoegen om een 10 te krijgen!" De pizza is dan een 10 voor de test, maar een 0 voor de klant. Dit is reward hacking.

De oplossing van de auteurs:
Ze zeggen: "Best-of-N werkt prima, mits we de juiste maatstaf gebruiken." In plaats van te kijken naar het gemiddelde cijfer, kijken we naar: "Wanneer we deze pizza vergelijken met een standaardpizza, wint hij vaker dan hij verliest?"
Als de smaaktest maar redelijk goed is, is het kiezen van de beste uit een grote groep (Best-of-N) de snelste en slimste manier om de beste pizza te vinden.

3. De nieuwe oplossing: De "EM-Regel" (De Veilige Scherper)

Hoewel Best-of-N goed werkt, blijft het risico bestaan dat de chef te ver gaat en giftige pizza's maakt als je te veel pizza's laat bakken.

De auteurs bedachten een simpele, slimme variant: EM-geregulariseerd Best-of-N.

• Hoe het werkt: In plaats van alle 100 pizza's te proeven en de allerbeste te kiezen, zeggen we: "We kiezen alleen pizza's die minimaal goed zijn, maar we laten de chef niet te ver afdwalen van zijn normale stijl."
• De metafoor: Het is alsof je de chef zegt: "Kies de beste pizza uit de top 10%, maar zorg dat die pizza nog steeds op een echte pizza lijkt. Als je een pizza maakt die eruitziet als een rubberen band (omdat de smaaktest dat leuk vindt), tellen we die niet mee."

Dit nieuwe algoritme heeft twee grote voordelen:

1. Het is veilig: De chef kan niet meer "hacken" om de test te bedriegen. Hij blijft binnen de veilige grenzen.
2. Het is even goed: Het presteert net zo goed als de oude methode, maar zonder het gevaar van de giftige pizza's.

4. Waarom is dit belangrijk?

Vroeger dachten wetenschappers: "Best-of-N is dom en onveilig, we moeten iets veel complexer bouwen."
Deze paper zegt: "Nee, Best-of-N is eigenlijk heel slim en werkt perfect voor de manier waarop we AI nu testen (door te vergelijken wat er wint). De eerdere waarschuwingen waren gebaseerd op een verkeerde manier van meten."

Samenvattend in één zin:
Het paper laat zien dat het simpelste trucje (kies het beste uit een grote hoop) eigenlijk de slimste manier is om AI te verbeteren, zolang we kijken naar wie er wint in een wedstrijd, en dat we met een kleine, simpele aanpassing kunnen voorkomen dat de AI probeert te bedriegen.

Technische samenvatting

Probleemstelling

In de context van Large Language Models (LLMs) is "inference-time compute" (rekenkracht tijdens het genereren) een cruciale schaalas geworden. Een veelgebruikte methode is Best-of-N (BoN): er worden $N$ kandidaat-antwoorden gegenereerd door een referentiemodel ($\pi_{ref}$), en het antwoord met de hoogste geschatte beloning volgens een geleerd beloningsmodel ($b_r$) wordt geselecteerd.

Recent theoretisch werk (Huang et al., 2025) suggereerde dat BoN statistisch suboptimaal is en vatbaar voor reward hacking (Goodhart's law). Reward hacking treedt op wanneer het model antwoorden kiest die een hoge score krijgen van het geleerde beloningsmodel maar eigenlijk van lage kwaliteit zijn volgens de ware beloning ($r^*$). De eerdere theorie concludeerde dat complexere algoritmen (zoals $\chi^2$-geregulariseerde varianten) nodig zijn om optimale prestaties te bereiken.

De auteurs van dit paper betogen echter dat deze conclusies voortkomen uit onrealistische aannames:

1. Ze focussen op verwachte ware beloning (expected true reward) in plaats van win-rate (winstkans), wat in de praktijk de standaardmetriek is voor evaluatie en training van beloningsmodellen.
2. Ze gebruiken kwadratische fout (MSE) als maatstaf voor de kwaliteit van het beloningsmodel, wat niet schaal-invariant is en minder goed aansluit bij hoe beloningsmodellen daadwerkelijk worden getraind (via paarvergelijkingen).

Methodologie en Theoretisch Kader

De auteurs herdefiniëren het probleem binnen een "sample-and-evaluate" raamwerk met de volgende kernaanpassingen:

1. Doelmetriek: Win-rate:
   In plaats van het maximaliseren van de verwachte beloning $E[r^*(y)]$, maximaliseren ze de win-rate $R_{r^*}(\pi)$, gedefinieerd als de kans dat een gegenereerd antwoord $y$ beter is dan een referentie-antwoord $y'$ volgens de ware beloning $r^*$:
   $$R_{r^*}(\pi) = P(r^*(y) > r^*(y')) + \frac{1}{2}P(r^*(y) = r^*(y'))$$
   Dit sluit beter aan bij de Bradley-Terry-modellen die in de praktijk worden gebruikt.

2. Kwaliteit van het Beloningsmodel: Pairwise Win-rate Error ($\epsilon_{pw}$):
   Ze vervangen de kwadratische fout door de pairwise win-rate error:
   $$\epsilon_{pw}(b_r) = E_{y,y' \sim \pi_{ref}} [|\phi_{b_r}(y, y') - \phi_{r^*}(y, y')|]$$
   Hierbij meet $\phi$ de uitkomst van een paarvergelijking. Deze metriek is schaal-invariant en direct gerelateerd aan hoe beloningsmodellen worden getraind.

3. Kwaliteit van het Referentiemodel: EM-Divergentie:
   In plaats van $\chi^2$-divergentie gebruiken ze de EM-divergentie (Expected Mass divergence) om de discrepantie tussen het referentiemodel $\pi_{ref}$ en het doelmodel $\pi^*$ te meten. Dit is fundamenteel verbonden met het probleem van benaderend afwijzen (approximate rejection sampling).

Belangrijkste Bijdragen en Resultaten

1. Optimaliteit van Best-of-N (BoN)

De auteurs bewijzen dat BoN, onder de juiste aannames (kleine $\epsilon_{pw}$ en beheersbare EM-divergentie), statistisch en computationeel optimaal is voor het maximaliseren van de win-rate.

• Theorema 3 & 4: Ze leiden een bovengrens af voor de regret (het verschil in win-rate tussen de beste mogelijke strategie en BoN) die afhangt van $N \cdot \epsilon_{pw}$ en de EM-divergentie. Ze tonen aan dat deze bovengrens overeenkomt met een ondergrens (lower bound).
• Conclusie: In tegenstelling tot de eerdere bevindingen over verwachte beloning, is BoN voor win-rate optimaal tot op een logaritmische factor. Dit verklaart waarom BoN in de praktijk zo succesvol is, ondanks zijn eenvoud. De eerder geconstateerde suboptimaliteit was een artefact van de gebruikte metriek (verwachte beloning) en niet een fundamentele beperking van het algoritme.

2. Het Reward Hacking Probleem en de Oplossing

Hoewel BoN optimaal is voor win-rate, blijft het vatbaar voor reward hacking: als $N$ te groot wordt, kiest het algoritme antwoorden waarvoor $b_r$ en $r^*$ het oneens zijn. Dit leidt tot een niet-monotone prestatiecurve (prestaties dalen na een bepaald punt).

Om dit op te lossen, stellen de auteurs een nieuw algoritme voor: EM-geregulariseerde Best-of-N.

• Het Algoritme: Dit algoritme lost een variatieprobleem op dat de verwachte beloning maximaliseert onder een strafe voor afwijking van $\pi_{ref}$, gemeten via EM-divergentie.
• De Oplossing: Ze bewijzen (Lemma 1) dat de optimale strategie voor dit probleem simpelweg is om uniform te kiezen uit de top-$(1/M)$ kwantiel van de scores van $b_r$ onder $\pi_{ref}$. Dit is praktisch zeer eenvoudig te implementeren: trek $N$ samples, sorteer ze op $b_r$, en kies willekeurig uit de top $N/M$.
• Theorema 5: Dit algoritme bereikt de optimale statistische prestatie (dezelfde regret als BoN) maar garandeert dat de prestaties monotoon toenemen met $N$. Het elimineert reward hacking zonder extra online schatting of complexe training.

3. Superioriteit ten opzichte van Bestaande Methoden

• Propositie 2: De auteurs tonen aan dat de $\chi^2$-geregulariseerde variant (van Huang et al.) willekeurig slechter kan presteren dan hun EM-geregulariseerde variant wanneer de doelstelling win-rate is. De $\chi^2$-regularisatie is dus ontoereikend in dit specifieke kader.

Significantie en Impact

1. Theoretische Validatie van Praktijk: Het paper biedt een theoretische onderbouwing voor de wijdverbreide succes van Best-of-N in de praktijk. Het toont aan dat de eenvoudige methode niet "suboptimaal" is, mits de juiste evaluatiemetriek (win-rate) wordt gebruikt.
2. Nieuwe Standaard voor Analyse: Het paper pleit ervoor om bij het analyseren van inference-time alignment-methoden te focussen op win-rate en paarvergelijkingsfouten in plaats van verwachte beloning en MSE. Dit voorkomt misleidende conclusies over de noodzaak van complexe algoritmen.
3. Praktische Innovatie: De voorgestelde EM-geregulariseerde variant biedt een simpele, wiskundig bewezen methode om reward hacking te voorkomen. Het vereist geen extra training of ingewikkelde schattingen, maar werkt puur door het selecteren van een top-kwantiel, wat het direct toepasbaar maakt in bestaande systemen.
4. Generalisatie: De resultaten zijn uitgebreid naar situaties waar de win-rate wordt gemeten tegen een willekeurige comparator (niet alleen $\pi_{ref}$), wat relevant is voor benchmarks zoals AlpacaEval.

Samenvattend: Dit paper corrigeert een fundamenteel misverstand in de theoretische literatuur over Best-of-N. Het toont aan dat BoN optimaal is voor de meest relevante praktijkmetriek (win-rate) en introduceert een eenvoudige, wiskundig onderbouwde variant die het risico op reward hacking elimineert zonder de optimaliteit te verliezen.